Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплексним методом і визначити оптимальний план іншої задачі. Оптимальні результати перевірити графічно.
Розв’язок
Розв’яжемо задачу лінійного програмування симплексним методом.
Визначимо мінімальне значення цільової функції F(X) = 4x1+2x2 при наступних умовах-обмежень.
x1-x2≤4
x1+3x2≤6
x1+2x2≥2
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних.
Оскільки маємо змішані умови-обмеження, то введемо штучні змінні x.
1x1-1x2 + 1x3 + 0x4 + 0x5 = 4
1x1 + 3x2 + 0x3 + 1x4 + 0x5 = 6
1x1 + 2x2 + 0x3 + 0x4-1x5 = 2
Для постановки задачі на мінімум цільову функцію запишемо так:
F(X) = 4x1+2x2 - Mx6 => max
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
План
Базис
В
x1
x2
x3
x4
x5
х6
0
х3
4
1
-1
1
0
0
0
x4
6
1
3
0
1
0
0
х6
2
1
2
0
0
-1
1
Індексний рядок
F(X0)
0
0
0
0
0
0
0
Переходимо до основного алгоритму симплекс-методу.
План
Базис
В
x1
x2
x3
x4
x5
x6
min
1
x3
4
1
-1
1
0
0
0
0
x4
6
1
3
0
1
0
0
2
x6
2
1
2
0
0
-1
1
1
Індексний рядок
F(X1)
0
0
0
0
0
0
0
0
Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х2, оскільки значення коефіцієнта за модулем найбільше.
План
Базис
В
x1
x2
x3
x4
x5
x6
min
2
x3
5
1.5
0
1
0
-0.5
0.5
3.33
х4
3
-0.5
0
0
1
1.5
-1.5
0
x2
1
0.5
1
0
0
-0.5
0.5
2
Індексний рядок
F(X2)
0
0
0
0
0
0
0
0
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х2.
План
Базис
В
x1
x2
x3
x4
x5
x6
min
3
x3
2
0
-3
1
0
1
-1
2
X4
4
0
1
0
1
1
-1
4
X1
2
1
2
0
0
-1
1
0
Індексний рядок
F(X3)
0
0
0
0
0
0
0
0
План
Базис
В
x1
x2
x3
x4
x5
x6
min
4
х5
2
0
-3
1
0
1
-1
0
X4
2
0
4
-1
1
0
0
0.5
X1
4
1
-1
1
0
0
0
0
Індексний рядок
F(X4)
0
0
0
0
0
0
0
0
План
Базис
В
x1
x2
x3
x4
x5
х6
5
х5
3.5
0
0
0.25
0.75
1
-1
х2
0.5
0
1
-0.25
0.25
0
0
х1
4.5
1
0
0.75
0.25
0
0
Індексний рядок
F(X5)
0
0
0
0
0
0
0
Оптимальний план можна записати так:
x5 = 3.5
x2 = 0.5
x1 = 4.5
F(X) = 4*4.5 + 2*0.5 = 19
Складемо двоїсту задачу до поставленої задачі лінійного програмування.
y1+y2+y3≥4
-y1+3y2+2y3≥2
4y1+6y2+2y3 => min
y1 ≥ 0
y2 ≥ 0
y3 ≤ 0
Рішення двоїстої задачі дає оптимальну оцінок ресурсів. Використовуючи останню інтиграцію прямої задачі знайдемо,оптимальний план двоїстої задачі. Із теореми двоїстості слідує, що Y = C*A-1.
Сформуємо матрицю A із компонентів векторів, які входять в оптимальний базис.
Визначивши обернену матрицю А-1 через алгебраїчне доповнення, отримаємо:
Як видно із останнього плану симплексної таблиці, обернена матриця A-1 розміщена у стовбцях додаткових змінних.
Тоді Y = C*A-1 =
Запишемо оптимальний план двоїстої задачі:
y1 = 2.5
y2 = 1.5
y3 = 0
Z(Y) = 4*2.5+6*1.5+2*0 = 19
Завдання 3
Розвязати транспортну задачц.
1
2
4
1
5
200
1
2
1
3
1
120
2
1
3
3
1
150
100
90
200
30
80
Розв’язок
Побудова математичної моделі. Нехай xij — кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача
. Оскільки
, то задачу треба закрити, тобто збалансувати (зрівняти) поставки й потреби:
У нашому випадку робиться це введенням фіктивного постачальника, оскільки
. З уведенням фіктивного постачальника в транспортній таблиці додатково заявляється n робочих клітинок (додатковий рядок).
Виникає проблема, які ціни присвоїти цим клітинкам, щоб фіктивний рядок був нейтральним щодо оптимального вибору планових перевезень. Нейтральність забезпечується тим, що всі ціни у фіктивних клітинках вибираються однаковими, а оскільки ці ціни при поставках не повинні впливати на значення цільової функції f, то їх беруть усі рівними нулю.
Занесемо вихідні дані у таблицю.
В1
В2
В3
В4
В5
Запаси
А1
1
2
4
1
5
200
А2
1
2
1
3
1
120
А3
2
1
3
3
1
150
А4
0
0
0
0
0
30
Потреби
100
90
200
30
80
Забезпечивши закритість розв'язуваної задачі, розпочинаємо будувати математичну модель даної задачі:
лінійний програмування математичний модель
Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом «північно-західного кута».
Ai
Bj
ui
b1 = 100
b2 = 90
b3 = 200
b4=30
b5=80
а1 = 200
1
100
2
90
4
[-] 10
1
[+]
5
u1 = 0
а2 = 120
1
2
1
120
3
1
u2 = -3
а3 = 150
2
1
3
[+] 70
3
[-] 30
1
50
u3 = -1
а4 = 30
0
0
0
0
0
30
u4 = -2
vj
v1 =1
v2 =2
v3 =4
v4 =4
V5 =2
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
Підрахуємо число зайнятих клітин таблиці, їх 8, а має бути m+n-1=8. Отже, опорний план є невироджених.
Перевіримо оптимальність опорного плану, складемо систему рівнянь (для заповнених клітин таблиці) для визначення потенціалів першого опорного плану:
Записана система рівнянь є невизначеною, і один з її розв’язків дістанемо, узявши, наприклад, u1 = 0. Тоді всі інші потенціали однозначно визначаються з цієї системи рівнянь: u1 =0, u2 = -3, u3 = -1, u4=-2, v1 =1, v2 =2, v3 =4 v4=4, v5=2. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.
Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ≤ cij (для порожніх клітинок таблиці):
А1B4 : u1 + v4 = 0 + 4 = 4 > 1;
А1B5 : u1 + v5 = 0 + 2 = 2 < 5;
А2B1 : u2 + v1 = -3 + 1 = -2 < 1;
А2B2 : u2 + v2 = -3 + 2 = -1 < 2;
А2B4 : u2 + v4 = -3 + 4 = 1 < 3;
А2B5 : u2 + v5 = -3 + 2 = -1 < 1;
А3B1 : u3 + v1 = -1 + 1 = 0 < 2;
А3B2 : u3 + v2 = -1 + 2 = 1 = 1;
А4B1 : u4 + v1 = -2 + 1 = -1 < 0;
А4B2 : u4 + v2 = -2 + 2 = 0 = 0;
А4B3 : u4 + v3 = -2 + 4 = 2 > 0;
А4B4 : u4 + v4 = -2 + 4 = 2 > 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij
А1B4 : u1 + v4 = 0 + 4 = 4 > 1;
А4B3 : u4 + v3 = -2 + 4 = 2 > 0;
А4B4 : u4 + v4 = -2 + 4 = 2 > 0.
Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (А1B4): 1
Ставимо в ній знак «+». Для визначення клітинки, що звільняється, будуємо цикл, починаючи з клітинки А1B4, та позначаємо вершини циклу почергово знаками «–» і «+». Тепер необхідно перемістити продукцію в межах побудованого циклу. Для цього у порожню клітинку А1B4 переносимо менше з чисел хij, які розміщені в клітинках зі знаком «–». Одночасно це саме число хij додаємо до відповідних чисел, що розміщені в клітинках зі знаком «+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «–».
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше,
, тобто
. Додаємо 10 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 10 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план. Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n + m – 1).
Отже, другий опорний план транспортної задачі матиме такий вигляд:
Ai
Bj
ui
b1 = 100
b2 = 90
b3 = 200
b4=30
b5=80
а1 = 200
1
100
2
[-] 90
4
1
[+] 10
5
u1 = 0
а2 = 120
1
2
1
120
3
1
u2 = 0
а3 = 150
2
1
[+]
3
80
3
[-] 20
1
50
u3 = 2
а4 = 30
0
0
0
0
0
30
u4 = 1
vj
v1 =1
v2 =2
v3 =1
v4 =1
V5 =-1
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij
(А3B1): 2 + 1 = 3 > 2;
(А3B2): 2 + 2 = 4 > 1;
(А4B1): 1 + 1 = 2 > 0;
(А4B2): 1 + 2 = 3 > 0;
(А4B3): 1 + 1 = 2 > 0;
(А4B4): 1 + 1 = 2 > 0.
Вибираємо максимальну оцінку вільної клітини (А3B2): 1
Для цього в перспективну клітку (А3B2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А3B4) = 20. Додаємо 20 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 20 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
Ai
Bj
ui
b1 = 100
b2 = 90
b3 = 200
b4=30
b5=80
а1 = 200
1
100
2
70
4
1
30
5
u1 = 0
а2 = 120
1
2
1
120
3
1
u2 = -3
а3 = 150
2
1
20
3
[-] 80
3
1
[+] 50
u3 = -1
а4 = 30
0
0
0
[+]
0
0
[-] 30
u4 = -2
vj
v1 =1
v2 =2
v3 =1
v4 =1
V5 =-1
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij
(А4B3): -2 + 4 = 2 > 0
Вибираємо максимальну оцінку вільної клітини (А4B3): 0
Для цього в перспективну клітку (А4B3) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А4B5) =30. Додаємо 30 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 30 з Хij, що стоять в мінусових клітинах.
В результаті отримаємо новий опорний план.
Ai
Bj
ui
b1 = 100
b2 = 90
b3 = 200
b4=30
b5=80
а1 = 200
1
100
2
70
4
1
30
5
u1 = 0
а2 = 120
1
2
1
120
3
1
u2 = -3
а3 = 150
2
1
20
3
50
3
1
80
u3 = -1
а4 = 30
0
0
0
30
0
0
u4 = -4
vj
v1 =1
v2 =2
v3 =4
v4 =1
V5 =2
Перевіримо оптимальність опорного плану, тобто повторюємо описані раніше дії.
Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Перевірка останнього плану на оптимальність за допомогою методу потенціалів показує, що він оптимальний.
Розрахуємо значення цільової функції відповідно до другого опорного плану задачі:
За оптимальним планом перевезень загальна вартість перевезень всієї продукції є найменшою і становить 640 грн.
Завдання 4
Знайти графічним методом екстремуми функції в області, визначеній нерівностями (в усіх варіантах вважати
)
,
,
,
Розв’язок
Побудуємо область допустимих рішень, тобто вирішимо графічно систему нерівностей. Для цього побудуємо кожну пряму і визначимо півплощини, задані нерівностями (півплощини позначені штрихом).
Межі області
Позначимо границі області багатокутника рішень.
Цільова функція F(x) => min
Розглянемо цільову функцію завдання F = 7X1+6X2 => min.
Побудуємо пряму, що відповідає значенню функції F = 0: F = 7X1+6X2 = 0. Будемо рухати цю пряму паралельним чином. Оскільки нас цікавить мінімальне рішення, тому рухався прямо до першого торкання позначеної області. На графіку ця пряма позначена пунктирною лінією.