Міністерство загальної та професійної освіти РФ
Південно-Уральський державний університет
Кафедра «Системи управління»
Курсова робота
З дослідження операцій
Варіант 14 Група ПС-317
Виконав: Родіонова Є.В.
Перевірив: Плотнікова Н.В.
Челябінськ, 2004
Зміст Завдання 1 лютого
Завдання 2 квітня
Завдання 6 березня
Завдання 8 квітня
Задача 1 № 14
Умова:
Нафтопереробний завод отримує 4 напівфабрикату: x1 тис. л. алкілату, x2 тис. л. крекінг-бензину, x3 тис. л. бензину прямої перегонки і x4 тис. л. ізопентану. У результаті змішування цих чотирьох компонентів у різних пропорціях утворюється три сорти авіаційного бензину: бензин А (а1: а2: а3: а4), бензин В (b1: b2: b3: b4) і бензин С (з1: с2: с3: с4) .
Вартість 1 тис. л. бензину кожного сорту дорівнює y1 руб., y2 руб. і y3 руб.
Визначити співвідношення компонентів, при якому буде досягнута максимальна вартість всієї продукції.
№ вар.
| x1
| x2
| x3
| x4
| y1
| y2
| y3
| а1
| а2
| а3
| а4
| b1
| b2
|
1
| 400
| 250
| 350
| 100
| 120
| 100
| 150
| 2
| 3
| 5
| 2
| 3
| 1
|
№ вар.
| b1
| b2
| c1
| c2
| c3
| c4
|
1
| 2
| 1
| 2
| 2
| 1
| 3
|
Рішення:
Складемо
математичну модель задачі.
Позначимо через t1 кількість бензину А;
через t2 кількість бензину В;
через t3 кількість бензину С.
Тоді, цільова
функція буде
L = y1t1 + y2t2 + y3t3 = 120t1 +100 t2 +150 t3 → max
Система обмежень:
Наведемо систему обмежень до виду основного
завдання лінійного програмування (введемо нові
змінні t4, t5, t6, t7, які входять в цільову функцію з нульовими коефіцієнтами):
Виберемо t1, t2, t3 вільними змінними, а t4, t5, t6, t7 - засадничими і приведемо до
стандартного вигляду для вирішення за допомогою симплекс-таблиці:
L = 0 - (-120t1-100t2-150t3)
Складемо симплекс-таблицю.
Це рішення опорне, тому що всі вільні члени позитивні.
Т. оскільки всі коефіцієнти в цільовій
функції негативні, то можна взяти будь-який стовпець дозволяючим (нехай t1). Виберемо як дозволяє елемента той, для якого відношення до нього вільного члена буде мінімально (це t7)
| b
| t1
| t2
| t3
| |
L
| 0
| | -120
| | -100
| | -150
| | |
| 6000
| | 60
| | 60
| | 180
| |
t4
| 400
| | 2
| | 3
| | 2
| | 400 / 2 = 200
|
| -100
| | -1
| | -1
| | -3
| |
t5
| 250
| | 3
| | 1
| | 2
| | 250 / 3 = 83,3
|
| -150
| | -1,5
| | -1,5
| | -4,5
| |
t6
| 350
| | 5
| | 2
| | 1
| | 350 / 5 = 70
|
| -250
| | -2,5
| | -2,5
| | -7,5
| |
t7
| 100
| | 2
| | 1
| | 3
| | 100 / 2 = 50
|
| 50
| | 0,5
| | 0,5
| | 1,5
| |
Далі змінюємо t2 і t1.
| b
| t7
| t2
| t3
| |
L
| 6000
| | 60
| | -40
| | 30
| | |
| 4000
| | 40
| | 80
| | 120
| |
t4
| 300
| | -1
| | 2
| | -1
| | 300 / 2 = 150
|
| -200
| | -2
| | -4
| | -6
| |
t5
| 100
| | -1,5
| | -0,5
| | -2,5
| | |
| 50
| | 0,5
| | 1
| | -4,5
| |
t6
| 50
| | -2,5
| | -0,5
| | -6,5
| | |
| 50
| | 0,5
| | 1
| | -7,5
| |
t1
| 50
| | 0,5
| | 0,5
| | 1,5
| | 50 / 0,5 = 100
|
| 100
| | 1
| | 2
| | 1,5
| |
| b
| t7
| t1
| t3
|
L
| 10000
| | 100
| | 80
| | 150
| |
| | | | | | | |
t4
| 100
| | -3
| | -4
| | -7
| |
| | | | | | | |
t5
| 150
| | -1
| | 1
| | -1
| |
| | | | | | | |
t6
| 100
| | -2
| | 1
| | -5
| |
| | | | | | | |
t2
| 100
| | 1
| | 2
| | 3
| |
| | | | | | | |
Оскільки коефіцієнти при змінних в цільовій функції позитивні, отже, це оптимальне рішення.
Таким чином, t1 = t3 = 0; t2 = 100; L = 10000.
Тобто для отримання максимального прибутку варто робити тільки бензин В (100 тис. л.), при цьому виручка складе 10000 руб.
ВІДПОВІДЬ: для отримання максимального прибутку варто робити тільки бензин В (100 тис. л.), При цьому виручка складе 10000 руб.
Задача 2 № 34
Умова:
За допомогою симплекс-таблиць знайти рішення задачі лінійного
програмування: визначити екстремальне значення цільової функції Q = CTx за умови Ax ³ £ B,
де CT = [c1 c2. . . c6] T, Вt = [b1 b2. . . b6] T,
XT = [x1 x2. . . x6] T, А = [aij] (i = 1,6; j = 1,3).
№ вар.
| с1
| с2
| с3
| с4
| С5
| С6
| b1
| b2
| b3
| Знаки обмежень
| a11
| a12
| a13
| a14
|
1
| 2
| 3
|
34
| 3
| 3
| 1
| 1
| 0
| 0
| 4
| 4
| 15
| =
| =
| =
| 2
| 0
| 3
| 1
|
№ вар.
| a15
| a16
| a21
| a22
| a23
| a24
| a25
| a26
| a31
| a32
| a33
| a34
| a35
| a36
| Тип екстрем.
| |
1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
| 9
| 10
| 11
| 12
| 13
| 14
| 15
| |
1. 34
| 0
| 0
| 1
| 0
| -1
| 2
| 3
| 0
| 3
| 3
| 6
| 3
| 6
| 0
| max
| |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
Рішення:
Вихідна система:
Цільова функція Q = x1 +3 x2 + x3 +3 x5.
Нехай х3, х4 - вільні змінні, х1, х2, х5 - базисні.
Наведемо систему і цільову функцію до стандартного вигляду, для побудови симплекс-таблиці:
Q = 9 - (9/2x3-1/2x4)
Складемо симплекс-таблицю:
| b
| x3
| x4
| |
Q
| 9
| | 9 / 2
| | -1 / 2
| | |
| 2 / 3
| | -5 / 6
| | 1
| |
x1
| 2
| | 3 / 2
| | 1 / 2
| | 2 / 0, 5 = 4
|
| -2 / 3
| | 5 / 6
| | -1
| |
x2
| 7 / 3
| | 4 / 3
| | 0
| | |
| 0
| | 0
| | 0
| |
x5
| 2 / 3
| | -5 / 6
| | 1 / 2
| | 2 / 3: 1 / 2 = 4 / 3
|
| 4 / 3
| | -5 / 3
| | 2
| |
Це опорне рішення, тому що вільні члени позитивні.
Оскільки коефіцієнт при х4 негативний, то це і буде дозволяє стовпець. В якості дозволяє елемента той, для якого відношення до нього вільного члена буде мінімально (це х5).
| b
| x3
| x5
|
Q
| 29 / 3
| | 11 / 3
| | 1
| |
| | | | | |
x1
| 4 / 3
| | 2 / 3
| | -1
| |
| | | | | |
x2
| 7 / 3
| | 4 / 3
| | 0
| |
| | | | | |
x4
| 4 / 3
| | -5 / 3
| | 2
| |
| | | | | |
Оскільки коефіцієнти при змінних в цільовій функції позитивні, отже, це оптимальне рішення.
Т. о. Q = 29 / 3
x3 = x5 = 0; x1 = 4 / 3; x2 = 7 / 3; x4 = 4 / 3.
ВІДПОВІДЬ: Q = 29/3ж
x3 = x5 = 0; x1 = 4 / 3; x2 = 7 / 3; x4 = 4 / 3.
Задача 3 № 14
Умова:
Рішення транспортної задачі:
1. Записати умови задачі у матричній формі.
2. Визначити опорний план задачі.
3. Визначити оптимальний план задачі.
4. Перевірити рішення задачі методом потенціалів.
№ вар.
| а1
| а2
| а3
| b1
| b2
| b3
| b4
| b5
| с11
| з12
| з13
|
14
| 90
| 50
| 30
| 15
| 45
| 45
| 50
| 15
| 45
| 60
| 40
|
С14
| з15
| С21
| с22
| с23
| С24
| С25
| С31
| С32
| С33
| С34
| С35
|
60
| 95
| 35
| 30
| 55
| 30
| 40
| 50
| 40
| 35
| 30
| 100
|
Рішення:
Складемо таблицю транспортної задачі і заповнимо її методом північно-західного кута:
| B1
| B2
| B3
| B4
| B5
| a
|
A1
| | 45
| | 60
| | 40
| | 60
| | 95
| 90
|
15
| | 45
| | 30
| | | | | |
A2
| | 35
| | 30
| | 55
| | 30
| | 40
| 50
|
| | | | 15
| | 35
| | | |
A3
| | 50
| | 40
| | 35
| | 30
| | 100
| 30
|
| | | | | | 15
| | 15
| |
b
| 15
| 45
| 45
| 50
| 15
| 170
|
Це буде опорний план.
Кількість заповнених осередків r = m + n-1 = 6.
1) Розглянемо цикл (1,2) - (1,3) - (2,3) - (3,2):
с1, 2 + с2, 3> c1.3 + c3.2 (60 +55> 30 +40)
Кількість одиниць товару, що переміщуються по циклу: min (с1, 2; с2, 3) = 15
2) Розглянемо цикл (2,4) - (2,5) - (3,5) - (3,4):
c2, 4 + с3, 5> c2.5 + c3.4 (30 +40> 30 +100)
Кількість одиниць товару, що переміщуються по циклу: min (с2, 4; с3, 5) = 15
У результаті вийде наступний план:
| B1
| B2
| B3
| B4
| B5
| a
|
A1
| | 45
| | 60
| | 40
| | 60
| | 95
| 90
|
15
| | 30
| | 45
| | | | | |
A2
| | 35
| | 30
| | 55
| | 30
| | 40
| 50
|
| | 15
| | | | 20
| | 15
| |
A3
| | 50
| | 40
| | 35
| | 30
| | 100
| 30
|
| | | | | | 30
| | | |
b
| 15
| 45
| 45
| 50
| 15
| 170
|
Більше циклів з «негативної ціною» немає, значить, це оптимальне рішення.
Перевіримо методом потенціалів:
Приймемо α1 = 0, тоді βj = cij - αi (для заповнених клітин).
Якщо рішення правильне, то у всіх порожніх клітинках
таблиці Δij = cij - (αi + βj) ≥ 0
Очевидно, що Δij = 0 для заповнених клітин.
У результаті отримаємо наступну таблицю:
| β1 = 45
| β2 = 60
| β3 = 40
| β4 = 60
| β5 = 70
| |
α1 = 0
| | 45
| | 60
| | 40
| | 60
| | 95
| 90
|
15
| | 30
| | 45
| | 0
| | +
| |
α2 = -30
| | 35
| | 30
| | 55
| | 30
| | 40
| 50
|
+
| | 15
| | +
| | 20
| | 15
| |
α3 = -30
| | 50
| | 40
| | 35
| | 30
| | 100
| 30
|
+
| | +
| | +
| | 30
| | +
| |
| 15
| 45
| 45
| 50
| 15
| 170
|
Δ1, 4 = 0 показує, що існує ще один цикл з такою ж ціною (1,2) - (1,4) - (2,4) - (2,2). Але так як при цьому загальна вартість не зміниться, то немає сенсу міняти перевезення.
Таким чином, рішення правильне, тому що Δij ≥ 0.
ВІДПОВІДЬ:
| B1
| B2
| B3
| B4
| B5
| a
|
A1
| | 45
| | 60
| | 40
| | 60
| | 95
| 90
|
15
| | 30
| | 45
| | | | | |
A2
| | 35
| | 30
| | 55
| | 30
| | 40
| 50
|
| | 15
| | | | 20
| | 15
| |
A3
| | 50
| | 40
| | 35
| | 30
| | 100
| 30
|
| | | | | | 30
| | | |
b
| 15
| 45
| 45
| 50
| 15
| 170
|
Задача 4 № 59
Умова:
Визначити екстремум цільової функції виду
F = c11x12 + c22x22 + c12x1x2 + b1x1 + b2x2
за умов
a11x1 + a12x2 <=> p1
a21x1 + a22x2 <=> p2.
1. Знайти стаціонарну точку цільової функції та дослідити її (функцію) на опуклість (увігнутість) в околицях стаціонарної точки.
2. Скласти функцію Лагранжа.
3. Отримати систему
нерівностей,
відповідно до теореми Куна-Таккера.
4. Використовуючи метод штучних змінних скласти симплекс-таблицю і знайти рішення отриманої завдання лінійного програмування.
5. Дати відповідь з урахуванням умов доповнює нежорсткими.
№
| b1
| b2
| c11
| c12
| c22
| extr
| a11
| a12
| a21
| a22
| p1
| p2
| Знаки огр. 2 Січень
|
59
| 4.5
| 1.5
| -5
| -2
| -1
| max
| 2
| -3
| 5
| 4
| 9
| 13
| ³
| ³
|
Рішення:
Цільова функція: F =- 5x12-x22-2x1x2 +4.5 x1 +1.5 x2
Обмеження g1 (x) і g2 (x):
→
1) визначимо відносний максимум функції, для цього визначимо стаціонарну крапку (х10, х20):
→
→
2) Досліджуємо стаціонарну крапку на максимум, для чого визначаємо опуклість або увігнутість функції
F11 (х10, х20) = -10 <0
F12 (х10, х20) = -2
F21 (х10, х20) = -2
F22 (х10, х20) = -2
Оскільки умова виконується, то цільова функція є строго ввігнутої в околиці стаціонарної точки
3) Складаємо функцію Лагранжа:
L (x, u) = F (x) + u1g1 (x) + u2g2 (x) =
=- 5x12-x22-2x1x2 +4.5 x1 +1.5 x2 + u1 (2x1-3x2-9) + u2 (5x1 +4 x2-13)
Отримаємо рівняння сідлової точки, застосовуючи теорему Куна-Таккера:
i = 1, 2
Об'єднаймо
нерівності в систему А, а рівності в систему В:
Система А:
Система В:
Перепишемо систему А:
4) Введемо нові змінні
V = {v1, v2} ≥ 0; W = {w1, w2} ≥ 0
в систему А для
того, щоб нерівності перетворити на рівності:
Тоді
.
Отже, система В прийме вигляд:
- Це умови доповнює нежорсткими.
5) Вирішимо систему А за допомогою методу штучних змінних.
Введемо змінні Y = {y1; y2} в 1 і 2 рівняння системи
і створимо псевдоцелевую функцію Y = My1 + My2 → min
Y '=- Y =-My1-My2 → max.
В якості вільних виберемо х1, х2, v1, v2, u1, u2;
а в якості базисних y1, y2, w1, w2.
Наведемо систему і цільову функцію до стандартного вигляду, для побудови симплекс-таблиці:
Вирішимо за допомогою симплекс-таблиці. Знайдемо опорне рішення:
Примітка: обчислення проводилися програмно, см Додаток
| b
| x1
| x2
| u1
| u2
| v1
| v2
|
Y '
| -6M
| | -12M
| | -4M
| | -M
| | 9M
| | M
| | M
| |
| | | | | | | | | | | | | |
y1
| 4,5
| | 10
| | 2
| | -2
| | -5
| | -1
| | 0
| |
| | | | | | | | | | | | | |
y2
| 1,5
| | 2
| | 2
| | 3
| | -4
| | 0
| | -1
| |
| | | | | | | | | | | | | |
w1
| -9
| | -2
| | 3
| | 0
| | 0
| | 0
| | 0
| |
| | | | | | | | | | | | | |
w2
| -13
| | -5
| | 4
| | 0
| | 0
| | 0
| | 0
| |
| | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
| b
| w1
| x2
| u1
| u2
| v1
| v2
|
Y '
| 48M
| | -6M
| | -22M
| | -1M
| | 9M
| | 1M
| | 1M
| |
| | | | | | | | | | | | | |
y1
| -40,5
| | 5
| | 17
| | -2
| | -5
| | -1
| | 0
| |
| | | | | | | | | | | | | |
y2
| -7,5
| | 1
| | 5
| | 3
| | -4
| | 0
| | -1
| |
| | | | | | | | | | | | | |
x1
| 4,5
| | -0,5
| | -1,5
| | 0
| | 0
| | 0
| | 0
| |
| | | | | | | | | | | | | |
w2
| 9,5
| | -2,5
| | -3,5
| | 0
| | 0
| | 0
| | 0
| |
| | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
| b
| w1
| x2
| y1
| u2
| v1
| v2
|
Y '
| 68,25 M
| -8,5 M
| | -30,5 M
| -0,5 M
| | 11,5 M
| 1,5 M
| | 1M
| |
| | | | | | | | | | | | | |
u1
| 20,25
| | -2,5
| | -8,5
| | -0,5
| | 2,5
| | 0,5
| | 0
| |
| | | | | | | | | | | | | |
y2
| -68,25
| | 8,5
| | 30,5
| | 1,5
| | -11,5
| | -1,5
| | -1
| |
| | | | | | | | | | | | | |
x1
| 4,5
| | -0,5
| | -1,5
| | 0
| | 0
| | 0
| | 0
| |
| | | | | | | | | | | | | |
w2
| 9,58
| | -2,5
| | -3,5
| | 0
| | 0
| | 0
| | 0
| |
| | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
| b
| w1
| x2
| y1
| y2
| v1
| v2
|
Y '
| 0
| | 0
| | 0
| | M
| | M
| | 0
| | 0
| |
| | | | | | | | | | | | | |
u1
| 5,413043
| | | | | | | | | | | | |
| | | | | | | | | | | | | |
u2
| 5,934783
| | | | | | | | | | | | |
| | | | | | | | | | | | | |
x1
| 4,5
| | | | | | | | | | | | | |
| | | | | | | | | | | | | |
w2
| 9,5
| | | | | | | | | | | | | |
| | | | | | | | | | | | | |
Т. о, w1 = x2 = y1 = y2 = v1 = v2 = 0; u1 = 5,413043; u2 = 5,934783; x1 = 4.5; w2 = 9.5.
б) Умови доповнює нежорсткої не виконуються (u2w2 ≠ 0), значить рішення вихідної задачі квадратичного програмування не існує.
ВІДПОВІДЬ: не існує.
Додаток # Include <math.h>
# Include <stdio.h>
main ()
{
int i, j, k, m;
double h, n, a [5] [7], b [5] [7];
clrscr ();
printf ("Введіть числа
матриці А");
for (i = 0; i <5; i + +) {for (j = 0; j <7; j + +) {scanf ("% lf", & n); a [i] [j] = n;}}
printf ("Введіть координати дозволяє елемента \ n");
scanf ("% d", & k);
scanf ("% d", & m);
printf ("матріцa A \ n");
for (i = 0; i <5; i + +)
{For (j = 0; j <7; j + +) printf ("% lf", a [i] [j]); printf ("\ n");}
printf ("координати \ n");
printf ("% d% d", k, m);
h = 1 / a [k] [m];
b [k] [m] = h;
printf ("\ nh =% lf", h);
for (i = 0; i <7; i + +)
{If (i! = m) b [k] [i] = a [k] [i] * b [k] [m];}
for (i = 0; i <5; i + +)
{If (i! = k) b [i] [m] =- a [i] [m] * b [k] [m];}
for (i = 0; i <5; i + +)
{
for (j = 0; j <7; j + +)
if ((i! = k) & & (j! = m)) b [i] [j] = a [i] [j] + a [k] [j] * b [i] [m];
}
printf ("\ n результат");
printf ("матріцa B \ n");
for (i = 0; i <5; i + +)
{For (j = 0; j <7; j + +) printf ("% lf", b [i] [j]); printf ("\ n");}
getch ();
}