Міністерство Освіти Російської Федерації
Південно-Уральський державний університет
Кафедра Системи Управління
Курсова робота
з дисципліни: Дослідження операцій
Варіант 8
Керівник:
Плотнікова Н.В.
«___»__________ 2004
Автор проекту:
студентка групи
ПС - 317
Куликова Марія
«___»__________ 2004
Проект захищений
з оцінкою
«___»__________ 2004
Челябінськ
2004
Зміст.
Задача 1 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .3
Задача 2 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .8
Задача 3 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 10
Задача 4 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 13
Завдання 1 (№ 8)
Умова:
На виробництві чотирьох видів кабелю виконується п'ять груп технологічних операцій. Норми витрат на 1 км. кабелю даного виду на кожній з груп операцій, прибуток від реалізації 1 км. кожного виду кабелю, а також загальний фонд робочого часу, протягом якого можуть виконуватися ці операції, вказані в таблиці.
Визначити такий план випуску кабелю, при якому загальний прибуток від реалізації виготовленої продукції є максимальною.
Рішення:
Складаємо математичну модель задачі:
нехай x1-довжина першого кабелю (км);
x2 - довжина другого кабелю (км);
x3 - довжина 3-ого кабелю (км);
x4 - довжина четвертий кабелю (км)
тоді цільова функція L - загальний прибуток від реалізації виготовленої продукції, буде мати наступний вигляд
L = В1x1 + В2x2 + В3x3 + В4x4 = x1 + 2x2 + 1,5 x3 + x4 → max
Отримаємо систему обмежень:
1,5 x1 + x2 + 2x3 + x4 £ 6500;
x1 + 2x2 + 0x3 +2 x4 £ 4000;
4x1 + 5x2 + 5x3 +4 x4 £ 11000;
2x1 + x2 +1,5 x3 +0 x4 £ 4500;
x1 + 2x2 +1,5 x3 +4 x4 £ 4500.
Наведемо отриману математичну модель до виду ОЗЛП за допомогою додаткових невід'ємних змінних, число яких дорівнює числу нерівностей:
1,5 x1 + x2 + 2x3 + x4 + x5 = 6500;
x1 + 2x2 + 0x3 +2 x4 + x6 = 4000;
4x1 + 5x2 + 5x3 +4 x4 + x7 = 11000;
2x1 + x2 +1,5 x3 +0 x4 + x8 = 4500;
x1 + 2x2 +1,5 x3 +4 x4 + x9 = 4500.
Отже, виберемо x1, x2, x3, x4 - вільними змінними, а x5, x6, x7, x8, x9 - засадничими змінними (кожна з них зустрічаються в системі лише в одному рівнянні з коефіцієнтом 1, а в решті з нульовими коефіцієнтами). Наведемо систему до стандартного вигляду, висловивши для цього всі базисні змінні через вільні:
x5 = 6500 - (1,5 x1 + x2 + 2x3 + x4);
x6 = 4000 - (x1 + 2x2 + 0x3 +2 x4);
x7 = 11000 - (4x1 + 5x2 + 5x3 +4 x4);
x8 = 4500 - (2x1 + x2 +1,5 x3 +0 x4);
x9 = 4500 - (x1 + 2x2 +1,5 x3 +4 x4)
L = 0 - (- x1-2x2 - 1,5 x3 - x4)
Вирішимо методом симплекс-таблиць:
Це рішення опорне, тому що всі вільні члени позитивні.
Виберемо стовпець у таблиці, який буде дозволяючим, нехай це буде x1, виберемо як дозволяє елемента той, для якого відношення до нього вільного члена буде мінімально (це x8).
Міняємо
Міняємо
Бачимо, що коефіцієнти при змінних в цільовій функції позитивні, значить, знайдене рішення буде оптимальним.
Отже,
Відповідь: якщо підприємство буде виготовляти тільки три види дроту 1,2,3 причому 3875 / 3 км, 2750 / 3 км, 250 км відповідно, то загальний прибуток від реалізації виготовленої продукції буде максимальною і рівної 3500 (од).
Задача 2 (№ 28)
Умова:
За допомогою симплекс-таблиць знайти рішення задачі лінійного програмування: визначити екстремальне значення цільової функції 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).
Рішення:
Отримаємо систему:
4 x1 + x2 + x3 +2 x4 + x5 = 8;
2x1 - x2 + x4 = 2;
x1 + x2 + x5 = 3
L =-6x1 + x3-x4-x5 → max
Нехай x2, x4 - вільні змінні, а x1, x3, x5 - базисні змінні. Наведемо систему і цільову функцію до стандартного вигляду, для побудови симплекс-таблиці:
x5 = 2 - (1,5 x2 -0,5 x4);
x3 = 6 - (1,5 x2 +0,5 x4);
x1 = 1 - (-0,5 x2 +0,5 x4)
L =- 2 - (3x2-x4) → max
Складемо симплекс-таблицю:
Виберемо дозволяючим стовпцем x4, тому що тільки перед цієї змінної в цільовій функції від'ємне число, виберемо як дозволяє елемента той, для якого відношення до нього вільного члена буде мінімально (це x1). Міняємо x4 і x1
Отримали оптимальне рішення, тому що всі коефіцієнти позитивні.
Отже, x1 = x2 = 0, x3 = 5, x4 = 2, x5 = 3, L = 0.
Відповідь: x1 = x2 = 0, x3 = 5, x4 = 2, x5 = 3, L = 0.
Завдання 3 (№ 8)
Умова:
Рішення транспортної задачі:
1. Записати умови задачі у матричній формі.
2. Визначити опорний план задачі.
3. Визначити оптимальний план задачі.
4. Перевірити рішення задачі методом потенціалів.
Рішення:
Складемо таблицю транспортної задачі. Заповнимо таблицю методом північно-західного кута:
Кількість заповнених осередків r = m + n-1 = 6.
Перевіримо суму по стовпцях, суму по рядках і кількість базисних (заповнених) клітин:
r = 6, å ai = å bj = 1000, все виконується, значить, знайдений план є опорним.
L = 25 * 200 +30 * 200 +40 * 100 +10 * 200 +12 * 100 +21 * 200 = 22400
Постараємося поліпшити план перевезень.
1) Розглянемо цикл (1; 1) - (1, 2) - (2, 2) - (2; 1)
Підрахуємо ціну циклу: j = 15-30 +21-25 =- 19 <0
L = 21 * 200 +15 * 200 +40 * 100 +10 * 200 +12 * 100 +21 * 200 = 18600
2) Розглянемо цикл (2; 1) - (2, 2) - (3, 2) - (3; 1)
j =- 15 +30 +23-40 =- 2 <0
L = 21 * 200 +15 * 100 +30 * 100 +23 * 100 +10 * 200 +12 * 100 +21 * 200 = 18400
Перевіримо методом потенціалів:
Приймемо α1 = 0, тоді βj = cij - αi (для заповнених клітин).
Якщо рішення правильне, то у всіх порожніх клітинках таблиці Δij = cij - (αi + βj) ≥ 0
Очевидно, що Δij = 0 для заповнених клітин.
У результаті отримаємо наступну таблицю:
Таким чином, рішення правильне, тому що Δij> 0 для всіх порожніх клітин і Δij = 0 для всіх заповнених.
Тоді сума всіх перевезень:
L = 18400
Відповідь:
Південно-Уральський державний університет
Кафедра Системи Управління
Курсова робота
з дисципліни: Дослідження операцій
Варіант 8
Керівник:
Плотнікова Н.В.
«___»__________ 2004
Автор проекту:
студентка групи
ПС - 317
Куликова Марія
«___»__________ 2004
Проект захищений
з оцінкою
«___»__________ 2004
Челябінськ
2004
Зміст.
Задача 1 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .3
Задача 2 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .8
Задача 3 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 10
Задача 4 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 13
Завдання 1 (№ 8)
Умова:
На виробництві чотирьох видів кабелю виконується п'ять груп технологічних операцій. Норми витрат на 1 км. кабелю даного виду на кожній з груп операцій, прибуток від реалізації 1 км. кожного виду кабелю, а також загальний фонд робочого часу, протягом якого можуть виконуватися ці операції, вказані в таблиці.
Визначити такий план випуску кабелю, при якому загальний прибуток від реалізації виготовленої продукції є максимальною.
| Технологічна операція | Норми витрат часу на обробку 1 км кабелю виду | Загальний фонд робочого часу (ч) | |||
| 1 | 2 | 3 | 4 | ||
| Волочіння | А11 | А12 | А13 | А14 | А1 |
| Накладення ізоляцій | А21 | А22 | А23 | А24 | А2 |
| Скручування елементів в кабель | А31 | А32 | а33 | а34 | А3 |
| Освінцовиваніе | А41 | А42 | А43 | а44 | А4 |
| Випробування і контроль | А51 | а52 | а53 | а54 | А5 |
| Прибуток від реалізації 1 км кабелю | В1 | В2 | В3 | В4 | |
| № вар. | А11 | А12 | А13 | А14 | А21 | А22 | А23 | А24 | А31 | А32 | а33 | а34 | А41 |
| 1 | 1,5 | 1 | 2 | 1 | 1 | 2 | 0 | 2 | 4 | 5 | 5 | 4 | 2 |
| № вар. | А42 | А43 | а44 | А51 | а52 | а53 | а54 | А1 | А2 | А3 | А4 | 5 |
| 1 | 1 | 4 | 0 | 1 | 2 | 1,5 | 4 | 6500 | 4000 | 11000 | 4500 | 4500 |
| В1 | В2 | В3 | В4 |
| 1 | 2 | 1,5 | 1 |
Рішення:
Складаємо математичну модель задачі:
нехай x1-довжина першого кабелю (км);
x2 - довжина другого кабелю (км);
x3 - довжина 3-ого кабелю (км);
x4 - довжина четвертий кабелю (км)
тоді цільова функція L - загальний прибуток від реалізації виготовленої продукції, буде мати наступний вигляд
L = В1x1 + В2x2 + В3x3 + В4x4 = x1 + 2x2 + 1,5 x3 + x4 → max
Отримаємо систему обмежень:
1,5 x1 + x2 + 2x3 + x4 £ 6500;
x1 + 2x2 + 0x3 +2 x4 £ 4000;
4x1 + 5x2 + 5x3 +4 x4 £ 11000;
2x1 + x2 +1,5 x3 +0 x4 £ 4500;
x1 + 2x2 +1,5 x3 +4 x4 £ 4500.
Наведемо отриману математичну модель до виду ОЗЛП за допомогою додаткових невід'ємних змінних, число яких дорівнює числу нерівностей:
1,5 x1 + x2 + 2x3 + x4 + x5 = 6500;
x1 + 2x2 + 0x3 +2 x4 + x6 = 4000;
4x1 + 5x2 + 5x3 +4 x4 + x7 = 11000;
2x1 + x2 +1,5 x3 +0 x4 + x8 = 4500;
x1 + 2x2 +1,5 x3 +4 x4 + x9 = 4500.
Отже, виберемо x1, x2, x3, x4 - вільними змінними, а x5, x6, x7, x8, x9 - засадничими змінними (кожна з них зустрічаються в системі лише в одному рівнянні з коефіцієнтом 1, а в решті з нульовими коефіцієнтами). Наведемо систему до стандартного вигляду, висловивши для цього всі базисні змінні через вільні:
x5 = 6500 - (1,5 x1 + x2 + 2x3 + x4);
x6 = 4000 - (x1 + 2x2 + 0x3 +2 x4);
x7 = 11000 - (4x1 + 5x2 + 5x3 +4 x4);
x8 = 4500 - (2x1 + x2 +1,5 x3 +0 x4);
x9 = 4500 - (x1 + 2x2 +1,5 x3 +4 x4)
L = 0 - (- x1-2x2 - 1,5 x3 - x4)
Вирішимо методом симплекс-таблиць:
Це рішення опорне, тому що всі вільні члени позитивні.
Виберемо стовпець у таблиці, який буде дозволяючим, нехай це буде x1, виберемо як дозволяє елемента той, для якого відношення до нього вільного члена буде мінімально (це x8).
| A | |||||
| L | 0 2250 | -1 0,5 | -2 0,5 | -1,5 2 | -1 0 |
| 6500 -3375 | 1,5 -0,75 | 1 -0,75 | 2 -3 | 1 0 | |
| 4000 -2250 | 1 -0,5 | 2 -0,5 | 0 -2 | 3 0 | |
| 11000 -9000 | 4 -2 | 5 -2 | 5 -8 | 4 0 | |
| x8 | 4500 2250 | 2 0,5 | 1 0,5 | 4 2 | 0 0 |
| x9 | 4500 -2250 | 1 -0,5 | 2 -0,5 | 1,5 -2 | 4 0 |
Міняємо
| A | x8 | ||||
| L | 2250 1000 | 0,5 -1 | -1,5 0,5 | 0,5 -1,5 | -1 2 |
| 3125 -500 / 3 | -0,75 1 / 6 | 0,25 -1/12 | -1 0,25 | 1 -1 / 3 | |
| 1750 -1000 | -0,5 1 | 1,5 -0,5 | -2 1,5 | 3 -2 | |
| 2000 2000 / 3 | -2 -2 / 3 | 3 1 / 3 | -3 -1 | 4 4 / 3 | |
| 2250 -1000 / 3 | 0,5 1 / 3 | 0,5 -1 / 6 | 2 0,5 | 0 -2 / 3 | |
| x9 | 2250 -1000 | -0,5 1 | 1,5 -0,5 | -0,5 1,5 | 4 -2 |
Міняємо
| A | x8 | ||||
| L | 3250 250 | -0,5 0,5 | 0,5 -0,5 | -1 1 | 1 2 |
| 8875 / 3 187,5 | -7/12 0,375 | -1/12 -0,375 | -0,75 0,75 | 2 / 3 1,5 | |
| 750 125 | 0,5 0,25 | -0,5 -0,25 | -0,5 0,5 | 1 1 | |
| 2000 / 3 250 | -2 / 3 0,5 | 1 / 3 -0,5 | -1 1 | 4 / 3 2 | |
| 5750 / 3 -625 | 5 / 6 -1,25 | -1 / 6 1,25 | 2,5 -2,5 | -2 / 3 -5 | |
| x9 | 250 250 | 0,5 0,5 | -0,5 -0,5 | 1 1 | 2 2 |
| A | x8 | x9 | |||
| L | 3500 | 0 | 0 | 1 | 3 |
| 18875 / 6 | -5/24 | -11/24 | 0,75 | 13 / 6 | |
| 875 | 0,75 | -0,75 | 0,5 | 2 | |
| 2750 / 3 | -1 / 6 | -1 / 6 | 1 | 10 / 3 | |
| 3875 / 3 | -5/12 | 13/12 | -2,5 | -17 / 3 | |
| 250 | 0,5 | -0,5 | 1 | 2 |
Отже,
Відповідь: якщо підприємство буде виготовляти тільки три види дроту 1,2,3 причому 3875 / 3 км, 2750 / 3 км, 250 км відповідно, то загальний прибуток від реалізації виготовленої продукції буде максимальною і рівної 3500 (од).
Задача 2 (№ 28)
Умова:
За допомогою симплекс-таблиць знайти рішення задачі лінійного програмування: визначити екстремальне значення цільової функції 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 | |||||||||||||||
| 28 | -6 | 0 | 1 | -1 | -1 | 0 | 8 | 2 | 3 | = | = | = | 4 | 1 | 1 | 2 | |
| № вар. | a15 | a16 | a21 | a22 | a23 | a24 | a25 | a26 | a31 | a32 | a33 | a34 | a35 | a36 | Тип екстрем. |
| 1. 34 | 1 | 0 | 2 | -1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | max |
Отримаємо систему:
4 x1 + x2 + x3 +2 x4 + x5 = 8;
2x1 - x2 + x4 = 2;
x1 + x2 + x5 = 3
L =-6x1 + x3-x4-x5 → max
Нехай x2, x4 - вільні змінні, а x1, x3, x5 - базисні змінні. Наведемо систему і цільову функцію до стандартного вигляду, для побудови симплекс-таблиці:
x5 = 2 - (1,5 x2 -0,5 x4);
x3 = 6 - (1,5 x2 +0,5 x4);
x1 = 1 - (-0,5 x2 +0,5 x4)
L =- 2 - (3x2-x4) → max
Складемо симплекс-таблицю:
Виберемо дозволяючим стовпцем x4, тому що тільки перед цієї змінної в цільовій функції від'ємне число, виберемо як дозволяє елемента той, для якого відношення до нього вільного члена буде мінімально (це x1). Міняємо x4 і x1
| b | x2 | x4 | ||
| L | -2 2 | 3 -1 | -1 2 | |
| x1 | 1 2 | -0,5 -1 | 0,5 2 | 1 / 0, 5 = 2 |
| 6 -1 | 1,5 0,5 | 0,5 -1 | 6 / 0, 5 = 12 | |
| 2 1 | 1,5 -0,5 | -0,5 1 |
| b | x2 | x1 | |
| L | 0 | 2 | 2 |
| x4 | 2 | -1 | 2 |
| 5 | 2 | -1 | |
| 3 | 1 | 1 |
Отже, x1 = x2 = 0, x3 = 5, x4 = 2, x5 = 3, L = 0.
Відповідь: x1 = x2 = 0, x3 = 5, x4 = 2, x5 = 3, L = 0.
Завдання 3 (№ 8)
Умова:
Рішення транспортної задачі:
1. Записати умови задачі у матричній формі.
2. Визначити опорний план задачі.
3. Визначити оптимальний план задачі.
4. Перевірити рішення задачі методом потенціалів.
| № вар. | а1 | а2 | а3 | b1 | b2 | b3 | b4 | b5 | с11 | з12 | з13 |
| 8 | 200 | 200 | 600 | 200 | 300 | 200 | 100 | 200 | 25 | 21 | 20 |
| С14 | з15 | С21 | с22 | с23 | С24 | С25 | С31 | С32 | С33 | С34 | С35 |
| 50 | 18 | 15 | 30 | 32 | 25 | 40 | 23 | 40 | 10 | 12 | 21 |
Складемо таблицю транспортної задачі. Заповнимо таблицю методом північно-західного кута:
| B1 | B2 | B3 | B4 | B5 | ai | |
| A1 | 25 200 | 21 | 20 | 50 | 18 | 200 |
| A2 | 15 | 30 200 | 32 | 25 | 40 | 200 |
| A3 | 23 | 40 100 | 10 200 | 12 100 | 21 200 | 600 |
| bj | 200 | 300 | 200 | 100 | 200 | 1000 |
Перевіримо суму по стовпцях, суму по рядках і кількість базисних (заповнених) клітин:
r = 6, å ai = å bj = 1000, все виконується, значить, знайдений план є опорним.
L = 25 * 200 +30 * 200 +40 * 100 +10 * 200 +12 * 100 +21 * 200 = 22400
Постараємося поліпшити план перевезень.
1) Розглянемо цикл (1; 1) - (1, 2) - (2, 2) - (2; 1)
Підрахуємо ціну циклу: j = 15-30 +21-25 =- 19 <0
| B1 | B2 | B3 | B4 | B5 | ai | |
| A1 | 25 | 21 200 | 20 | 50 | 18 | 200 |
| A2 | 15 200 | 30 | 32 | 25 | 40 | 200 |
| A3 | 23 | 40 100 | 10 200 | 12 100 | 21 200 | 600 |
| bj | 200 | 300 | 200 | 100 | 200 | 1000 |
2) Розглянемо цикл (2; 1) - (2, 2) - (3, 2) - (3; 1)
j =- 15 +30 +23-40 =- 2 <0
| B1 | B2 | B3 | B4 | B5 | ai | |
| A1 | 25 | 21 200 | 20 | 50 | 18 | 200 |
| A2 | 15 100 | 30 100 | 32 | 25 | 40 | 200 |
| A3 | 23 100 | 40 | 10 200 | 12 100 | 21 200 | 600 |
| bj | 200 | 300 | 200 | 100 | 200 | 1000 |
Перевіримо методом потенціалів:
Приймемо α1 = 0, тоді βj = cij - αi (для заповнених клітин).
Якщо рішення правильне, то у всіх порожніх клітинках таблиці Δij = cij - (αi + βj) ≥ 0
Очевидно, що Δij = 0 для заповнених клітин.
У результаті отримаємо наступну таблицю:
| B1 = 6 | B2 = 21 | B3 =- 7 | B4 =- 5 | B5 = 4 | ai | |
| A1 = 0 | 25-6> 0 | 21-21 = 0 200 | 20 +7> 0 | 50 +5> 0 | 18-4> 0 | 200 |
| A2 = 9 | 15-9-6 = 0 100 | 30-21-9 = 0 100 | 32-9 +7> 0 | 25 +5-9> 0 | 40-4-9> 0 | 200 |
| A3 = 17 | 23-17-6 = 0 100 | 40-21-17> 0 | 10 +7-17 = 0 200 | 12 +5-17 = 0 100 | 21-4-17 = 0 200 | 600 |
| bj | 200 | 300 | 200 | 100 | 200 | 1000 |
Тоді сума всіх перевезень:
L = 18400
Відповідь:
| B1 | B2 | B3 | B4 | B5 | ai | |
| A1 | 25 | 21 200 | 20 | 50 | 18 | 200 |
| A2 | 15 100 | 30 100 | 32 | 25 | 40 | 200 |
| A3 | 23 100 | 40 | 10 200 | 12 100 | 21 200 | 600 |
| bj | 200 | 300 | 200 | 100 | 200 | 1000 |
Завдання 4 (№ 53)
Умова:
Визначити екстремум цільової функції виду
F = c11x12 + c22x22 + c12x1x2 + b1x1 + b2x2
за умов:
a11x1 + a12x2 <=> p1
a21x1 + a22x2 <=> p2.
1. Знайти стаціонарну точку цільової функції та дослідити її (функцію) на опуклість (увігнутість) в околицях стаціонарної точки.
2. Скласти функцію Лагранжа.
3. Отримати систему нерівностей, відповідно до теореми Куна-Таккера.
4. Використовуючи метод штучних змінних скласти симплекс-таблицю і знайти рішення отриманої завдання лінійного програмування.
5. Дати відповідь з урахуванням умов доповнює нежорсткими.
Рішення:
Цільова функція:
F =-2x12-x22-4x1x2 +6 x1 +1,5 x2 → max
Обмеження g1 (x) і g2 (x): 2,5 x1-x2 ³ 7 2,5 x1-x2-7 ³ 0
3x1 +2,5 x2 ³ 13 3x1 +2,5 x2-13 ³ 0
1) визначимо відносний максимум функції, для цього визначимо стаціонарну крапку (х10, х20):
2) Досліджуємо стаціонарну крапку на максимум, для чого визначаємо опуклість або увігнутість функції
F11 (х10, х20) = -4 <0
F12 (х10, х20) =- 4
F21 (х10, х20) =- 4
F22 (х10, х20) =- 2
F11 F12 -4 -4
F21 F22 -4 -2
Оскільки умова виконується, то цільова функція є строго опуклою в околиці стаціонарної точки
3) Складаємо функцію Лагранжа:
L (x, u) = F (x) + u1g1 (x) + u2g2 (x) =- 2x12-x22-4x1x2 +6 x1 +1,5 x2 + u1 (2,5 x1-x2-7) + u2 (3x1 + 2,5 x2-13).
Отримаємо рівняння сідлової точки, застосовуючи теорему Куна-Таккера:
Об'єднаймо нерівності в систему А, а рівності в систему В:
Система А:
Система В:
Перепишемо систему А:
6-4x1-4x2 +2,5 u1 +3 u2 <0
1,5-4x1-2x2-u1 +2,5 u2 <0
2,5 x1-x2-7 ³ 0
3x1 +2,5 x2-13 ³ 0
4) Введемо нові змінні
V = {v1, v2} ≥ 0; W = {w1, w2} ≥ 0
в систему А для того, щоб нерівності перетворити на рівності:
6-4x1-4x2 +2,5 u1 +3 u2 + v1 = 0
1,5-4x1-2x2-u1 +2,5 u2 + v2 = 0
2,5 x1-x2-7-w1 = 0
3x1 +2,5 x2-13-w2 = 0
Тоді
- V1 = 6-4x1-4x2 +2,5 u1 +3 u2
- V2 = 1,5-4x1-2x2-u1 +2,5 u2
w1 = 2,5 x1-x2-7
w2 = 3x1 +2,5 x2-13
Отже, система В прийме вигляд:
5) Вирішимо систему А за допомогою методу штучних змінних.
Введемо змінні Y = {y1; y2} в 1 і 2 рівняння системи
6-4x1-4x2 +2,5 u1 +3 u2 + v1-y1 = 0
1,5-4x1-2x2-u1 +2,5 u2 + v2-y2 = 0
2,5 x1-x2-7-w1 = 0
3x1 +2,5 x2-13-w2 = 0
і створимо псевдоцелевую функцію Y = My1 + My2 → min
Y '=- Y =-My1-My2 → max.
В якості вільних виберемо х1, х2, v1, v2, u1, u2;
а в якості базисних y1, y2, w1, w2.
Наведемо систему і цільову функцію до стандартного вигляду, для побудови симплекс-таблиці:
y1 = 6 - (4x1 +4 x2-2, 5u1-3u2 - v1)
y2 = 1,5 - (4x1 +2 x2 + u1-2, 5u2-v2)
w1 =- 7 - (-2,5 x1 + x2)
w2 =- 13 - (-3x1-2, 5x2)
Y '=- Y =- My1-My2 =- 7,5 M-(-8x1-6x2 +1,5 u1 +5,5 u2 + v1 + v2) M
Вирішимо за допомогою симплекс-таблиці. Знайдемо опорне рішення:
Міняємо 
Міняємо 
Міняємо 
Міняємо 
Отже, 
6) Умови доповнює нежорсткої виконуються
Відповідь: існує.
Література.
1) Курс лекцій Плотнікова Н.В.
2) Пантелєєв А.В., Лєтова Т.А. «Методи оптимізації в прикладах і задачах».
Умова:
Визначити екстремум цільової функції виду
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 Січень | |
| 53 | 6 | 1,5 | -2 | -4 | -1 | max | 2,5 | -1 | 3 | 2,5 | 7 | 13 | ³ | ³ |
Цільова функція:
F =-2x12-x22-4x1x2 +6 x1 +1,5 x2 → max
Обмеження g1 (x) і g2 (x): 2,5 x1-x2 ³ 7 2,5 x1-x2-7 ³ 0
3x1 +2,5 x2 ³ 13 3x1 +2,5 x2-13 ³ 0
1) визначимо відносний максимум функції, для цього визначимо стаціонарну крапку (х10, х20):
2) Досліджуємо стаціонарну крапку на максимум, для чого визначаємо опуклість або увігнутість функції
F11 (х10, х20) = -4 <0
F12 (х10, х20) =- 4
F21 (х10, х20) =- 4
F22 (х10, х20) =- 2
F11 F12 -4 -4
F21 F22 -4 -2
Оскільки умова виконується, то цільова функція є строго опуклою в околиці стаціонарної точки
3) Складаємо функцію Лагранжа:
L (x, u) = F (x) + u1g1 (x) + u2g2 (x) =- 2x12-x22-4x1x2 +6 x1 +1,5 x2 + u1 (2,5 x1-x2-7) + u2 (3x1 + 2,5 x2-13).
Отримаємо рівняння сідлової точки, застосовуючи теорему Куна-Таккера:
Об'єднаймо нерівності в систему А, а рівності в систему В:
Система А:
Система В:
Перепишемо систему А:
6-4x1-4x2 +2,5 u1 +3 u2 <0
1,5-4x1-2x2-u1 +2,5 u2 <0
2,5 x1-x2-7 ³ 0
3x1 +2,5 x2-13 ³ 0
4) Введемо нові змінні
V = {v1, v2} ≥ 0; W = {w1, w2} ≥ 0
в систему А для того, щоб нерівності перетворити на рівності:
6-4x1-4x2 +2,5 u1 +3 u2 + v1 = 0
1,5-4x1-2x2-u1 +2,5 u2 + v2 = 0
2,5 x1-x2-7-w1 = 0
3x1 +2,5 x2-13-w2 = 0
Тоді
- V1 = 6-4x1-4x2 +2,5 u1 +3 u2
- V2 = 1,5-4x1-2x2-u1 +2,5 u2
w1 = 2,5 x1-x2-7
w2 = 3x1 +2,5 x2-13
Отже, система В прийме вигляд:
5) Вирішимо систему А за допомогою методу штучних змінних.
Введемо змінні Y = {y1; y2} в 1 і 2 рівняння системи
6-4x1-4x2 +2,5 u1 +3 u2 + v1-y1 = 0
1,5-4x1-2x2-u1 +2,5 u2 + v2-y2 = 0
2,5 x1-x2-7-w1 = 0
3x1 +2,5 x2-13-w2 = 0
і створимо псевдоцелевую функцію Y = My1 + My2 → min
Y '=- Y =-My1-My2 → max.
В якості вільних виберемо х1, х2, v1, v2, u1, u2;
а в якості базисних y1, y2, w1, w2.
Наведемо систему і цільову функцію до стандартного вигляду, для побудови симплекс-таблиці:
y1 = 6 - (4x1 +4 x2-2, 5u1-3u2 - v1)
y2 = 1,5 - (4x1 +2 x2 + u1-2, 5u2-v2)
w1 =- 7 - (-2,5 x1 + x2)
w2 =- 13 - (-3x1-2, 5x2)
Y '=- Y =- My1-My2 =- 7,5 M-(-8x1-6x2 +1,5 u1 +5,5 u2 + v1 + v2) M
Вирішимо за допомогою симплекс-таблиці. Знайдемо опорне рішення:
| -7,5 M 4,5 M | -8M 12M | -6M 3M | 1,5 M 3M | 5,5 M -7,5 M | M 0 | M -3M | |
| 6 -3 | 4 -8 | 4 -2 | -2,5 -2 | -3 5 | -1 0 | 0 2 | |
| 1,5 3 / 4 | 4 2 | 2 0,5 | 1 0,5 | -2,5 -5 / 4 | 0 0 | -1 -0,5 | |
| -7 -3 / 4 | -2,5 -2 | 1 -0,5 | 0 -0,5 | 0 5 / 4 | 0 0 | 0 0,5 | |
| -13 15 / 8 | -3 5 | -2,5 5 / 4 | 0 5 / 4 | 0 -25/16 | 0 0 | 0 -5 / 4 |
| -3M 3M | 4M -4M | 3M -2M | 4,5 M -4,5 M | -2M M | M -M | -2M 2M | |
| 3 3 / 2 | -4 -2 | -2 -1 | -4,5 -9 / 4 | 2 0,5 | -1 -0,5 | 2 1 | |
| 3 / 4 15 / 8 | 2 -2,5 | 0,5 -5 / 4 | 0,5 -45/16 | -5 / 4 5 / 8 | 0 -5 / 8 | -0,5 5 / 4 | |
| -31 / 4 -15 / 8 | -4,5 2,5 | -0,5 5 / 4 | -0,5 45/16 | 5 / 4 -5 / 8 | 0 5 / 8 | 0,5 -5 / 4 | |
| -89 / 8 75/32 | 2 -25 / 8 | 5 / 4 -25/16 | 5 / 4 -225/64 | -25/16 25/32 | 0 -25/32 | -5 / 4 25/16 |
| 0 0 | 0 0 | M 0 | 0 0 | M 0 | 0 0 | 0 0 | |
| 3 / 2 77 / 8 | -2 -1 | -1 -3 / 4 | -9 / 4 -37/16 | 0,5 5 / 8 | -0,5 -5 / 8 | 1 3 / 4 | |
| 21 / 8 77/32 | -0,5 -1 / 4 | -3 / 4 -3/16 | -37/16 -37/64 | 5 / 8 5 / 32 | -5 / 8 -5/32 | 3 / 4 -3/16 | |
| -77 / 8 77/16 | -2 -0,5 | 3 / 4 -3 / 8 | 37/16 -37/32 | -5 / 8 5 / 16 | 5 / 8 -5/16 | -3 / 4 3 / 8 | |
| -281/32 693/128 | -9 / 8 -9/16 | -5/16 -27/64 | -145/64 -333/256 | 25/32 45/128 | -25/32 -45/128 | 5 / 16 27/64 |
| 0 0 | 0 0 | M 0 | 0 0 | M 0 | 0 0 | 0 0 | |
| 89 / 8 431/18 | -1 -16 / 9 | -7 / 4 | -73/16 | 9 / 8 | -9 / 8 | 7 / 4 | |
| 161/32 431/72 | -1 / 4 -4 / 9 | -15/16 | -185/64 | 25/32 | -25/32 | 9 / 16 | |
| 77/16 431/36 | -0,5 -8 / 9 | -3 / 8 | -37/32 | 5 / 16 | -5/16 | 3 / 8 | |
| -431/32 431/18 | -9/16 -16 / 9 | -47/64 | -913/256 | 145/128 | -145/128 | 47/64 |
| 0 | 0 | M | 0 | M | 0 | 0 | |
| 2525/72 | |||||||
| 3173/288 | |||||||
| 2417/144 | |||||||
| 431/18 |
6) Умови доповнює нежорсткої виконуються
Відповідь: існує.
Література.
1) Курс лекцій Плотнікова Н.В.
2) Пантелєєв А.В., Лєтова Т.А. «Методи оптимізації в прикладах і задачах».