Міністерство освіти і науки Російської Федерації
Південно-Уральський державний університет
Кафедра системи управління
Курсова робота
з дисципліни: дослідження операцій
Челябінськ
2004
Зміст
Завдання 1 Березня
Завдання 2 Червень
Завдання 9 березня
Завдання квітень 1911
Література 17
Завдання 1
Задача 9
Умова:
З трьох видів сировини необхідно скласти суміш, до складу якої має входити не менше a од. хімічної речовини А, b од. - Речовини В і c од. - Речовини С. Кількість одиниць хімічної речовини, що міститься в 1 кг. сировини кожного виду, вказано в таблиці. Там же приведена ціна 1 кг. сировини кожного виду. Скласти суміш, що містить не менше потрібної кількості речовин даного виду і має мінімальну вартість.
Рішення:
Складемо математичну модель задачі.
Позначимо через n1, n2, n3 кількість кг сировини 1, 2, 3 відповідно.
Тоді, цільова функція буде
L = D1n1 + D2n2 + D3n3 = 5n1 + 6n2 +7 n3 → min
Система обмежень:
_ EMBED Equation.3 ___
Наведемо систему обмежень до виду основного завдання лінійного програмування. Введемо цільову функцію з протилежним знаком L ', і нові змінні n4, n5, n6, які входять в цільову функцію з нульовими коефіцієнтами.
L '= 0 - (5n1 + 6n2 +7 n3) → max
_ EMBED Equation.3 ___
Виберемо n1, n2, n3 вільними змінними, а n4, n5, n6 - засадничими і приведемо до стандартного вигляду для вирішення за допомогою симплекс-таблиці:
L '= 0 - (5n1 + 6n2 +7 n3)
_ EMBED Equation.3 ___
Складемо симплекс-таблицю.
Це рішення не опорне, тому що вільні члени не позитивні.
Виберемо в першому рядку негативний елемент, наприклад на перетині n1 і n4, тоді дозволяє стовпець n1, а дозволяє елемент - n5 (мінімальний по відношенню вільного члена до елементів дозволяє стовпця).
Таблиця 1.1
Міняємо n 1 і n 5.
Таблиця 1.2
Міняємо n 5 і n 6.
Таблиця 1.3
Міняємо n 4 і n 6.
Таблиця 1.4
Оскільки коефіцієнти при всіх ni позитивні, то це і є оптимальне рішення.
Тоді n4 = n2 = n3 = 0, n6 = 2, n1 = 26, n5 = 22, L '= -130, отже, L = 130.
Необхідно взяти 26 кг перше сировини, і тоді отримаємо суміш, що містить не менше потрібної кількості речовин даного виду і має мінімальну вартість 130.
Відповідь: для отримання змішай з мінімальними витратами необхідно взяти 26 кг тільки першого сировини.
Завдання 2
Завдання 29
Умова:
Рішення задачі лінійного програмування.
За допомогою симплекс-таблиць знайти рішення задачі лінійного програмування: визначити екстремальне значення цільової функції Q = CTx за умови Ax ((B,
де ((= ((1 (2... (6 ((, У (= (b1 b2... b6 ((,
((= ((1 (2... (6 ((, А = ((((( ((= 1,6; (= 1,3).
Рішення:
Складемо систему:
_ EMBED Equation.3 ___
Цільова функція Q = 0x1 +5 x2 + x3-x4 + x5 → max
Наведемо систему обмежень до виду основного завдання лінійного програмування.
_ EMBED Equation.3 ___
Нехай х1, х2, х3, х4, х5 - вільні змінні, х6, х7, х8 - базисні.
Наведемо систему і цільову функцію до стандартного вигляду, для побудови симплекс-таблиці:
Q = 0 - (-5x2-x3 + x4-x5)
_ EMBED Equation.3 ___
Складемо симплекс-таблицю:
Це опорне рішення тому коефіцієнти bj> 0. Будемо шукати оптимальне рішення. Оскільки коефіцієнти при вільних членах <0 (крім при x1), то що дозволяє може бути будь-який стовпець. Нехай x2, тоді на перетині x2 і x6 отримаємо дозволяє елемент.
Таблиця 2.1
Міняємо x 2 і x 6.
Таблиця 2.2
Міняємо x 5 і x 8.
Таблиця 2.3
Міняємо x 5 і x 1.
Таблиця 2.4
Отримали оптимальне рішення, тому що всі коефіцієнти позитивні.
Отже Q = 35; x5 = x6 = x3 = x4 = x8 = 0; x1 = 8 / 3; x2 = 14 / 3; x7 = 26 / 3.
Відповідь: Q = 35; x5 = x6 = x3 = x4 = x8 = 0; x1 = 8 / 3; x2 = 14 / 3; x7 = 26 / 3.
Завдання 3
Задача 9
Умова:
Рішення транспортної задачі:
1. Записати умови задачі у матричній формі.
2. Визначити опорний план задачі.
3. Визначити оптимальний план задачі.
4. Перевірити рішення задачі методом потенціалів.
Таблиця 1
Рішення:
Складемо таблицю транспортної задачі.
Таблиця 2
Зауважимо, що сума запасів перевищує заявки. Це транспортна задача з надлишком запасів. Для того щоб привести до транспортної задачі з правильним балансом, введемо фіктивний пункт призначення В5 з нульовими перевезеннями. Додамо відсутнє число заявок b5 = 700. Тепер кількість заявок дорівнює кількості запасів і одно 2000.
Заповнимо таблицю. Для цього не будемо використовувати метод північно-західного кута, тому що він принесе багато клопоту, будемо заповнювати клітки зліва направо від заявок до запасів, виходячи з найменшої ціни.
Таблиця 3
Це буде опорний план.
Кількість заповнених осередків - 6. r = m + n-1 = 3 +6-1 = 8> 6, виходить, план є виродженим, тому що не вистачає 2 базисних клітин. Додамо їх, і зробимо план невиродженим. Для цього змінимо в деяких клітинах кількість запасів та заявок на малу величину _ EMBED Equation.3 ___
Південно-Уральський державний університет
Кафедра системи управління
Курсова робота
з дисципліни: дослідження операцій
Варіант 9
_Челябінськ
2004
Зміст
Завдання 1 Березня
Завдання 2 Червень
Завдання 9 березня
Завдання квітень 1911
Література 17
Завдання 1
Задача 9
Умова:
З трьох видів сировини необхідно скласти суміш, до складу якої має входити не менше a од. хімічної речовини А, b од. - Речовини В і c од. - Речовини С. Кількість одиниць хімічної речовини, що міститься в 1 кг. сировини кожного виду, вказано в таблиці. Там же приведена ціна 1 кг. сировини кожного виду. Скласти суміш, що містить не менше потрібної кількості речовин даного виду і має мінімальну вартість.
Речовина | Кількість одиниць речовини, що міститься в 1 кг сировини | ||
1 | 2 | 3 | |
А | d 11 | d 12 | d 13 |
У | d 21 | d 22 | d 23 |
З | d 31 | d 32 | d 33 |
Ціна 1 кг сировини | D 1 | D 2 | D 3 |
№ вар. | d 11 | d 12 | d 13 | d 21 | d 22 | d 23 | d 31 | d 32 | d 33 |
9 | 1 | 1 | 0 | 2 | 0 | 3 | 1 | 2 | 4 |
D 1 | D 2 | D 3 | а | b | c |
5 | 6 | 7 | 26 | 30 | 24 |
Складемо математичну модель задачі.
Позначимо через n1, n2, n3 кількість кг сировини 1, 2, 3 відповідно.
Тоді, цільова функція буде
L = D1n1 + D2n2 + D3n3 = 5n1 + 6n2 +7 n3 → min
Система обмежень:
_ EMBED Equation.3 ___
Наведемо систему обмежень до виду основного завдання лінійного програмування. Введемо цільову функцію з протилежним знаком L ', і нові змінні n4, n5, n6, які входять в цільову функцію з нульовими коефіцієнтами.
L '= 0 - (5n1 + 6n2 +7 n3) → max
_ EMBED Equation.3 ___
Виберемо n1, n2, n3 вільними змінними, а n4, n5, n6 - засадничими і приведемо до стандартного вигляду для вирішення за допомогою симплекс-таблиці:
L '= 0 - (5n1 + 6n2 +7 n3)
_ EMBED Equation.3 ___
Складемо симплекс-таблицю.
Це рішення не опорне, тому що вільні члени не позитивні.
Виберемо в першому рядку негативний елемент, наприклад на перетині n1 і n4, тоді дозволяє стовпець n1, а дозволяє елемент - n5 (мінімальний по відношенню вільного члена до елементів дозволяє стовпця).
Таблиця 1.1
b | n 1 | n 2 | n 3 | ||||||
L ' | 0 | 5 | 6 | 7 | |||||
-75 | 2,5 | 0 | -8 | ||||||
n 4 | -26 | -1 | -1 | 0 | 26 / 1 = 26 | ||||
15 | -1 | 0 | 1,5 | ||||||
n 5 | -30 | -2 | 0 | -3 | 30 / 2 = 15min | ||||
15 | -1 | 0 | 1,5 | ||||||
n 6 | -24 | -1 | -2 | -4 | 24 / 1 = 24 | ||||
15 | -1 | 0 | 1,5 |
Таблиця 1.2
b | n 5 | n 2 | n 3 | ||||||
L ' | -75 | 2,5 | 6 | -0,5 | |||||
-45 | 5 | -10 | 25 | ||||||
n 4 | -11 | -0,5 | -1 | 1,5 | 11 / 0,5 = 22 | ||||
9 | -1 | 2 | -5 | ||||||
n 1 | 15 | -0,5 | 0 | 1,5 | |||||
9 | -1 | 2 | -5 | ||||||
n 6 | -9 | -0,5 | -2 | -2,5 | 9 / 0, 5 = 18min | ||||
18 | -2 | 4 | 5 |
Таблиця 1.3
b | n 6 | n 2 | n 3 | |||||
L ' | -120 | 5 | -4 | 25 | ||||
-10 | 5 | 5 | -18 | |||||
n 4 | -2 | -1 | 1 | -4 | ||||
2 | -1 | -1 | 2,5 | |||||
n 1 | 24 | -1 | 2 | -3 | ||||
2 | -1 | -1 | 3,5 | |||||
n 5 | 18 | -2 | 4 | 5 | ||||
4 | -2 | -2 | 7 |
Таблиця 1.4
b | n 4 | n 2 | n 3 | |||||
L ' | -130 | 5 | 1 | 7 | ||||
| ||||||||
n 6 | 2 | -1 | -1 | 3,5 | ||||
n 1 | 26 | -1 | -1 | 0 | ||||
| ||||||||
n 5 | 22 | -2 | 2 | 12 | ||||
|
Тоді n4 = n2 = n3 = 0, n6 = 2, n1 = 26, n5 = 22, L '= -130, отже, L = 130.
Необхідно взяти 26 кг перше сировини, і тоді отримаємо суміш, що містить не менше потрібної кількості речовин даного виду і має мінімальну вартість 130.
Відповідь: для отримання змішай з мінімальними витратами необхідно взяти 26 кг тільки першого сировини.
Завдання 2
Завдання 29
Умова:
Рішення задачі лінійного програмування.
За допомогою симплекс-таблиць знайти рішення задачі лінійного програмування: визначити екстремальне значення цільової функції Q = CTx за умови Ax ((B,
де ((= ((1 (2... (6 ((, У (= (b1 b2... b6 ((,
((= ((1 (2... (6 ((, А = ((((( ((= 1,6; (= 1,3).
№ вар. | З 1 | з 2 | з 3 | з 4 | з 5 | з 6 | b 1 | b 2 | b 3 | |
29 | 0 | 5 | 1 | -1 | 1 | 0 | 2 | 2 | 10 |
Знаки обмежень | a 11 | a 12 | a 13 | a 14 | ||
1 | 2 | 3 | ||||
£ | £ | £ | -1 | 1 | 1 | 0 |
a 15 | a 16 | a 21 | a 22 | a 23 | a 24 | a 25 | a 26 |
0 | 0 | 1 | -2 | 0 | 1 | 0 | 0 |
a 31 | a 32 | a 33 | a 34 | a 35 | a 36 | Тип екстрем. |
2 | 1 | 1 | 1 | 2 | 0 | max |
Складемо систему:
_ EMBED Equation.3 ___
Цільова функція Q = 0x1 +5 x2 + x3-x4 + x5 → max
Наведемо систему обмежень до виду основного завдання лінійного програмування.
_ EMBED Equation.3 ___
Нехай х1, х2, х3, х4, х5 - вільні змінні, х6, х7, х8 - базисні.
Наведемо систему і цільову функцію до стандартного вигляду, для побудови симплекс-таблиці:
Q = 0 - (-5x2-x3 + x4-x5)
_ EMBED Equation.3 ___
Складемо симплекс-таблицю:
Це опорне рішення тому коефіцієнти bj> 0. Будемо шукати оптимальне рішення. Оскільки коефіцієнти при вільних членах <0 (крім при x1), то що дозволяє може бути будь-який стовпець. Нехай x2, тоді на перетині x2 і x6 отримаємо дозволяє елемент.
Таблиця 2.1
b | x 1 | x 2 | x 3 | x 4 | x 5 | ||||||||
Q | 0 | 0 | -5 | -1 | 1 | -1 | |||||||
10 | -5 | 5 | 5 | 0 | 0 | ||||||||
x 6 | 2 | -1 | 1 | 1 | 0 | 0 | 2 / 1 = 2min | ||||||
2 | -1 | 1 | 1 | 0 | 0 | ||||||||
x 7 | 2 | 1 | -2 | 0 | 1 | 0 | |||||||
4 | -2 | 2 | 2 | 0 | 0 | ||||||||
x 8 | 10 | 2 | 1 | 1 | 1 | 2 | 10 / 2 = 5 | ||||||
-2 | 1 | -1 | -2 | 0 | 0 |
Таблиця 2.2
b | x 1 | x 6 | x 3 | x 4 | x 5 | ||||||||
Q | 10 | -5 | 5 | 4 | 1 | -1 | |||||||
4 | 1,5 | -1 | -1 | 0,5 | 0,5 | ||||||||
x 2 | 2 | -1 | 1 | 1 | 0 | 0 | |||||||
0 | 0 | 0 | 0 | 0 | 0 | ||||||||
x 7 | 6 | -1 | 2 | 2 | 1 | 0 | |||||||
0 | 0 | 0 | 0 | 0 | 0 | ||||||||
x 8 | 8 | 3 | -1 | -1 | 1 | 2 | |||||||
4 | 6 | -2 | -2 | 2 | 0,5 | ||||||||
Міняємо x 5 і x 8.
Таблиця 2.3
b | x 1 | x 6 | x 3 | x 4 | x 8 | |||||||
Q | 14 | -3.5 | 4,5 | 3,5 | 1,5 | 0,5 | ||||||
21 | 5,25 | -2,625 | -2,625 | 2,625 | 2,625 | |||||||
x 2 | 2 | -1 | 1 | 1 | 0 | 0 | ||||||
8 / 3 | 2 / 3 | -1 / 3 | -1 / 3 | 1 / 3 | 1 / 3 | |||||||
x 7 | 6 | -1 | 2 | 2 | 1 | 0 | ||||||
8 / 3 | 2 / 3 | -1 / 3 | -1 / 3 | 1 / 3 | 1 / 3 | |||||||
x 5 | 4 | 1,5 | -0,5 | -1 | 0,5 | 0,5 | ||||||
8 / 3 | 2 / 3 | -1 / 3 | -1 / 3 | 1 / 3 | 1 / 3 |
Таблиця 2.4
b | x 5 | x 6 | x 3 | x 4 | x 8 | |
Q | 35 | 5,25 | 1,875 | 0,875 | 4,125 | 3,125 |
x 2 | 14 / 3 | 2 / 3 | 2 / 3 | 2 / 3 | 1 / 3 | 1 / 3 |
x 7 | 26 / 3 | 2 / 3 | 5 / 3 | 5 / 3 | 4 / 3 | 1 / 3 |
x 1 | 8 / 3 | 2 / 3 | -1 / 3 | -1 / 3 | 1 / 3 | 1 / 3 |
Отже Q = 35; x5 = x6 = x3 = x4 = x8 = 0; x1 = 8 / 3; x2 = 14 / 3; x7 = 26 / 3.
Відповідь: Q = 35; x5 = x6 = x3 = x4 = x8 = 0; x1 = 8 / 3; x2 = 14 / 3; x7 = 26 / 3.
Завдання 3
Задача 9
Умова:
Рішення транспортної задачі:
1. Записати умови задачі у матричній формі.
2. Визначити опорний план задачі.
3. Визначити оптимальний план задачі.
4. Перевірити рішення задачі методом потенціалів.
Таблиця 1
№ вар. | а 1 | а 2 | а 3 | b 1 | b 2 | b 3 | b 4 | b 5 | з 11 | з 12 | з 13 |
9 | 300 | 700 | 1000 | 200 | 100 | 400 | 600 | 200 | 23 | 40 | 10 |
з 14 | з 15 | з 21 | з 22 | з 23 | з 24 | з 25 | з 31 | з 32 | з 33 | з 34 | з 35 |
12 | 21 | 25 | 21 | 20 | 50 | 18 | 15 | 30 | 32 | 25 | 50 |
Складемо таблицю транспортної задачі.
Таблиця 2
B1 | B2 | B3 | B4 | B5 | a | |
A1 | ||||||
23 | 40 | 10 | 12 | 21 | 300 | |
A2 | ||||||
25 | 21 | 20 | 50 | 18 | 700 | |
A3 | ||||||
15 | 30 | 32 | 25 | 50 | 1000 | |
b | 200 | 100 | 200 | 600 | 200 |
Заповнимо таблицю. Для цього не будемо використовувати метод північно-західного кута, тому що він принесе багато клопоту, будемо заповнювати клітки зліва направо від заявок до запасів, виходячи з найменшої ціни.
Таблиця 3
B1 | B2 | B3 | B4 | B5 | В6 | a | |
A1 | 300 | ||||||
23 | 40 | 10 | 12 | 21 | 0 | 300 | |
A2 | 100 | 200 | 200 | 200 | |||
25 | 21 | 20 | 50 | 18 | 0 | 700 | |
A3 | 200 | 300 | 500 | ||||
15 | 30 | 32 | 25 | 50 | 0 | 1000 | |
b | 200 | 100 | 200 | 600 | 200 | 700 | 2000 |
Кількість заповнених осередків - 6. r = m + n-1 = 3 +6-1 = 8> 6, виходить, план є виродженим, тому що не вистачає 2 базисних клітин. Додамо їх, і зробимо план невиродженим. Для цього змінимо в деяких клітинах кількість запасів та заявок на малу величину _ EMBED Equation.3 ___
Таблиця 4
Перевіримо методом потенціалів:
Приймемо α1 = 0, тоді βj = cij - αi (для заповнених клітин).
Якщо рішення правильне, то у всіх порожніх клітинках таблиці Δij = cij - (αi + βj) ≥ 0
Очевидно, що Δij = 0 для заповнених клітин.
У результаті отримаємо наступну таблицю:
Таблиця 5
Таким чином, рішення правильне, тому що Δij> 0 для всіх порожніх клітин і Δij = 0 для всіх заповнених.
Тоді сума всіх перевезень:
L = 200 * 15 +10 * 21 +200 * 20 +300 * 12 +300 * 25 +200 * 18 +200 * 0 +500 * 0 = 23800
Відповідь:
Завдання 4
Завдання 54
Умова:
Визначити екстремум цільової функції виду
(= (11 (12 + (22 (22 + (12 (1 (2 + (1 (1 + (2 (2
за умов:
(11 (1 + (12 (2 <=> (1
(21 (1 + (22 (2 <=> (2.
Знайти стаціонарну точку цільової функції та дослідити її (функцію) на опуклість (увігнутість) в околицях стаціонарної точки.
Скласти функцію Лагранжа.
Отримати систему нерівностей, відповідно до теореми Куна-Таккера.
Використовуючи метод штучних змінних скласти симплекс-таблицю і знайти рішення отриманої завдання лінійного програмування.
1. Дати відповідь з урахуванням умов доповнює нежорсткими.
2.
Рішення:
1) Цільова функція: F = 4x12-2x22 +1,5 x1x2-7x1-2x2 → min
Розглянемо F '=- 4x12 +2 x22 -1,5 x1x2 +7 x1 +2 x2 → max
Обмеження g1 (x) і g2 (x): _ EMBED Equation.3 ___ → _ EMBED Equation.3 ___
Визначимо відносний максимум функції F ', для цього визначимо стаціонарну крапку (х10, х20):
_ EMBED Equation.3 ___ → _ EMBED Equation.3 ___ → _ EMBED Equation.3 ___
2) Досліджуємо стаціонарну крапку на максимум, для чого визначаємо опуклість або увігнутість функції:
F'11 (х10, х20) = -8 <0
F'12 (х10, х20) = -1,5
F'21 (х10, х20) = -1,5
F'22 (х10, х20) = 4
_ EMBED Equation.3 ___
Оскільки умова виконується, то цільова функція є строго опуклою в околиці стаціонарної точки
3) Складаємо функцію Лагранжа:
L (x, u) = F '(x) + u1g1 (x) + u2g2 (x) =
=- 4x12 +2 x22 -1,5 x1x2 +7 x1 +2 x2 + u1 (_ EMBED Equation.3 ___)+ u2 (_ EMBED Equation.3 ___)
Отримаємо рівняння сідлової точки, застосовуючи теорему Куна-Таккера:
_ EMBED Equation.3 ___ i = 1, 2
Об'єднаймо нерівності в систему А, а рівності в систему В:
Система А:
_ EMBED Equation.3 ___
Система В:
_ EMBED Equation.3 ___
Перепишемо систему А:
_ EMBED Equation.3 ___
4) Введемо нові змінні
V = {v1, v2} ≥ 0; W = {w1, w2} ≥ 0
в систему А для того, щоб нерівності перетворити на рівності:
_ EMBED Equation.3 ___
Тоді
_ EMBED Equation.3 ___.
Значить, система В прийме вигляд:
_ EMBED Equation.3 ___ - це умови доповнює нежорсткими.
5) Вирішимо систему А за допомогою методу штучних змінних.
Введемо змінні Y = {y1; y2} в 1 і 2 рівняння системи
_ EMBED Equation.3 ___
Потім створимо псевдоцелевую функцію Y = My1 + My2 → min
Y '=- Y =-My1-My2 → max.
Нехай вільні змінні: х1, х2, v1, v2, u1, u2;
а базисні y1, y2, w1, w2.
Наведемо систему і цільову функцію до стандартного вигляду, для побудови симплекс-таблиці:
_ EMBED Equation.3 ___
_ EMBED Equation.3 ___
Вирішимо за допомогою симплекс-таблиці. Знайдемо опорне рішення:
B1 | B2 | B3 | B4 | B5 | В6 | a | |
A1 | 300 | 300 | |||||
23 | 40 | 10 | 12 | 21 | 0 | ||
A2 | 100 | 200 | | 200 | 200 | 700 | |
25 | 21 | 20 | 50 | 18 | 0 | ||
A3 | 200 | 300 | 500 | 1000 | |||
15 | 30 | 32 | 25 | 50 | 0 | ||
b | 200 | 100 | 200 | 600 | 200 | 700 | 2000 |
Приймемо α1 = 0, тоді βj = cij - αi (для заповнених клітин).
Якщо рішення правильне, то у всіх порожніх клітинках таблиці Δij = cij - (αi + βj) ≥ 0
Очевидно, що Δij = 0 для заповнених клітин.
У результаті отримаємо наступну таблицю:
Таблиця 5
β1 = 2 | β2 = 8 | β3 = 7 | β4 = 12 | β5 = 6 | β6 =- 13 | a | |
α1 = 0 | 300 | 300 | |||||
23-2> 0 | 40-8> 0 | 10-7> 0 | 12-12 = 0 | 21-6> 0 | 0 - (-13)> 0 | ||
α2 = 13 | 100 | 200 | 200 | 200 | 700 | ||
25-13-2> 0 | 21-8-13 = 0 | 20-7-13 = 0 | 50-12-13> 0 | 18-6-13 = 0 | 0-13 +13 = 0 | ||
α2 = 13 | 200 | 300 | 500 | 1000 | |||
15-13-2 = 0 | 30-13-8> 0 | 32-13-7> 0 | 25-13-2 = 0 | 50-13-6> 0 | 0-13 +13 = 0 | ||
b | 200 | 100 | 200 | 600 | 200 | 700 | 2000 |
Тоді сума всіх перевезень:
L = 200 * 15 +10 * 21 +200 * 20 +300 * 12 +300 * 25 +200 * 18 +200 * 0 +500 * 0 = 23800
Відповідь:
B1 | B2 | B3 | B4 | B5 | В6 | a | |
A1 | 300 | ||||||
23 | 40 | 10 | 12 | 21 | 0 | 300 | |
A2 | 100 | 200 | 200 | 200 | |||
25 | 21 | 20 | 50 | 18 | 0 | 700 | |
A3 | 200 | 300 | 500 | ||||
15 | 30 | 32 | 25 | 50 | 0 | 1000 | |
b | 200 | 100 | 200 | 600 | 200 | 700 | 2000 |
Завдання 4
Завдання 54
Умова:
Визначити екстремум цільової функції виду
(= (11 (12 + (22 (22 + (12 (1 (2 + (1 (1 + (2 (2
за умов:
(11 (1 + (12 (2 <=> (1
(21 (1 + (22 (2 <=> (2.
Знайти стаціонарну точку цільової функції та дослідити її (функцію) на опуклість (увігнутість) в околицях стаціонарної точки.
Скласти функцію Лагранжа.
Отримати систему нерівностей, відповідно до теореми Куна-Таккера.
Використовуючи метод штучних змінних скласти симплекс-таблицю і знайти рішення отриманої завдання лінійного програмування.
1. Дати відповідь з урахуванням умов доповнює нежорсткими.
2.
№ | b 1 | b 2 | c 11 | c 12 | c 22 | extr | a 11 | a 12 | a 21 | a 22 | p 1 | p 2 | Знаки огр. 2 Січень | |
31 | -7 | -2 | 4 | 1.5 | -2 | min | -2 | 1.5 | 4 | -3 | 18 | 9 | £ | ³ |
1) Цільова функція: F = 4x12-2x22 +1,5 x1x2-7x1-2x2 → min
Розглянемо F '=- 4x12 +2 x22 -1,5 x1x2 +7 x1 +2 x2 → max
Обмеження g1 (x) і g2 (x): _ EMBED Equation.3 ___ → _ EMBED Equation.3 ___
Визначимо відносний максимум функції F ', для цього визначимо стаціонарну крапку (х10, х20):
_ EMBED Equation.3 ___ → _ EMBED Equation.3 ___ → _ EMBED Equation.3 ___
2) Досліджуємо стаціонарну крапку на максимум, для чого визначаємо опуклість або увігнутість функції:
F'11 (х10, х20) = -8 <0
F'12 (х10, х20) = -1,5
F'21 (х10, х20) = -1,5
F'22 (х10, х20) = 4
_ EMBED Equation.3 ___
Оскільки умова виконується, то цільова функція є строго опуклою в околиці стаціонарної точки
3) Складаємо функцію Лагранжа:
L (x, u) = F '(x) + u1g1 (x) + u2g2 (x) =
=- 4x12 +2 x22 -1,5 x1x2 +7 x1 +2 x2 + u1 (_ EMBED Equation.3 ___)+ u2 (_ EMBED Equation.3 ___)
Отримаємо рівняння сідлової точки, застосовуючи теорему Куна-Таккера:
_ EMBED Equation.3 ___ i = 1, 2
Об'єднаймо нерівності в систему А, а рівності в систему В:
Система А:
_ EMBED Equation.3 ___
Система В:
_ EMBED Equation.3 ___
Перепишемо систему А:
_ EMBED Equation.3 ___
4) Введемо нові змінні
V = {v1, v2} ≥ 0; W = {w1, w2} ≥ 0
в систему А для того, щоб нерівності перетворити на рівності:
_ EMBED Equation.3 ___
Тоді
_ EMBED Equation.3 ___.
Значить, система В прийме вигляд:
_ EMBED Equation.3 ___ - це умови доповнює нежорсткими.
5) Вирішимо систему А за допомогою методу штучних змінних.
Введемо змінні Y = {y1; y2} в 1 і 2 рівняння системи
_ EMBED Equation.3 ___
Потім створимо псевдоцелевую функцію Y = My1 + My2 → min
Y '=- Y =-My1-My2 → max.
Нехай вільні змінні: х1, х2, v1, v2, u1, u2;
а базисні y1, y2, w1, w2.
Наведемо систему і цільову функцію до стандартного вигляду, для побудови симплекс-таблиці:
_ EMBED Equation.3 ___
_ EMBED Equation.3 ___
Вирішимо за допомогою симплекс-таблиці. Знайдемо опорне рішення:
b | x1 | x2 | u1 | u2 | v1 | v2 | |||||||||
Y '/ M | -9 | -9,5 | 2,5 | 0,5 | 1 | 1 | 1 | ||||||||
8,3125 | 1,1875 | 1,7813 | -2,375 | -4,75 | -1,188 | 0 | |||||||||
y1 | 7 | 8 | 1,5 | -2 | -4 | -1 | 0 | ||||||||
0,875 | 0,125 | 0,1875 | -0,25 | -0,5 | -0,125 | 0 | |||||||||
y2 | 2 | 1,5 | -4 | 1,5 | 3 | 0 | -1 | ||||||||
-1,313 | -0,188 | -0,281 | 0,375 | 0,75 | 0,1875 | 0 | |||||||||
w1 | 18 | -2 | 1,5 | 0 | 0 | 0 | 0 | ||||||||
1,75 | 0,25 | 0,375 | -0,5 | -1 | -0,25 | 0 | |||||||||
w2 | 9 | -4 | 3 | 0 | 0 | 0 | 0 | ||||||||
3,5 | 0,5 | 0,75 | -1 | -2 | -0,5 | 0 | |||||||||
b | y1 | x2 | u1 | u2 | v1 | v2 | |||||||||
Y '/ M | -0,69 | 1,1875 | 4,2813 | -1,875 | -3,75 | -0,188 | 1 | ||||||||
0,6875 | -0,188 | -4,281 | 1 | 3,75 | 0,1875 | -1 | |||||||||
x1 | 0,875 | 0,125 | 0,1875 | -0,25 | -0,5 | -0,125 | 0 | ||||||||
0,0917 | -0,025 | -0,571 | 0,1333 | 0,025 | -0,133 | ||||||||||
y2 | 0,688 | -0,188 | -4,281 | 1,875 | 3,75 | 0,1875 | -1 | ||||||||
0,3667 | -0,1 | -2,283 | 0,5333 | 2 | 0,1 | -0,533 | |||||||||
w1 | 19,75 | 0,25 | 1,875 | -0,5 | -1 | -0,25 | 0 | ||||||||
0,1833 | -0,05 | -1,142 | 0,2667 | 1 | 0,05 | -0,267 | |||||||||
w2 | 12,5 | 0,5 | 3,75 | -1 | -2 | -0,5 | 0 | ||||||||
0,3667 | -0,1 | -2,283 | 0,5333 | 2 | 0,1 | -0,533 | |||||||||
b | y1 | x2 | y2 | u2 | v1 | v2 | |||||||||
Y '/ M | 0 | 1 | 0 | 1 | 0 | 0 | 0 | ||||||||
x1 | 0,967 | 0,1333 | |||||||||||||
u1 | 0,367 | -0,1 | -2,283 | 0,5333 | 2 | 0,1 | -0,533 | ||||||||
w1 | 19,93 | 0,2667 | |||||||||||||
w2 | 12,87 | 0,5333 | |||||||||||||
б) Умови доповнює нежорсткої виконуються (u2w2 = 0), значить рішення вихідної задачі квадратичного програмування існує.
ВІДПОВІДЬ: існує.
Література
Курс лекцій Плотнікова М. В.