Математичне програмування (стр. 3 из 3)
Опорний план не є оптимальним, тому щоіснуютьоцінкивільнихклітин для якихui + vi>cij
(1;6): 0 + 1 > 0
(2;1): 7 + 5 > 7
(2;5): 7 + 3 > 2
(2;6): 7 + 1 > 0
Вибираємомаксимальнуоцінкувільноїклітини (А2B5): 2
Для цього в перспективнуклітку (А2B5) поставимо знак «+», а в інших вершинах багатокутникачергуються знаки «-», «+», «-». Цикл наведено втаблиці.
Звантажів хijщо стоять в мінусовихклітинах, вибираємонайменше, тобто у = min (А2B2) = 20. Додаємо 20 до обсягіввантажів, що стоять в плюсовихклітинах і віднімаємо 20 з Хij, що стоять в мінусовихклітинах. В результатіотримаємоновийопорний план.
| Ai | Bj | ui | |||||
| b1 = 100 | b2 = 120 | b3 = 100 | b4=200 | b5=300 | B6=50 | ||
| а1 = 150 | 5[-] 30 | 1120 | 2 | 3 | 4 | 0[+] | u1 = 0 |
| а2 = 320 | 7 | 8 | 1100 | 1200 | 220 | 0 | u2 = -1 |
| а3 = 400 | 4[+] 70 | 1 | 3 | 1 | 2280 | 0[-] 50 | u3 = -1 |
| vj | v1 = 5 | v2 = 1 | v3 = 2 | v4 = 2 | v5= 3 | V6 = 1 | |
Перевіримо оптимальність опорного плану, тобто повторюємо описані раніше дії.
Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Перевірка останнього плану на оптимальність за допомогою методу потенціалів показує, що він неоптимальний. Тому знову будуємо новий опорний план.
| Ai | Bj | ui | |||||
| b1 = 100 | b2 = 120 | b3 = 100 | b4=200 | b5=300 | B6=50 | ||
| а1 = 150 | 5 | 1120 | 2 | 3 | 4 | 030 | u1 = 0 |
| а2 = 320 | 7 | 8 | 1100 | 1200 | 220 | 0 | u2 = 0 |
| а3 = 400 | 4100 | 1 | 3 | 1 | 2280 | 020 | u3 = 0 |
| vj | v1 = 4 | v2 = 1 | v3 = 1 | v4 = 1 | v5= 2 | V6 = 0 | |
Перевіримооптимальність опорного плану, тобто повторюємо описані раніше дії.
Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Перевірка останнього плану на оптимальність за допомогою методу потенціалів показує, що він оптимальний.
Розрахуємозначенняцільовоїфункціївідповідно до другого опорного плану задачі:
(x) = 1*120 + 0*30 + 1*100 + 1*200 + 2*20 + 4*100 + 2*280 + 0*20 = 1420
За оптимальним планом перевезень загальна вартість перевезень всієї продукції є найменшою і становить 540 грн.
Завдання 4
Знайти графічним методом екстремуми функції в області, визначеній нерівностями (в усіх варіантах вважати
) 
, 
, 
, 
Розв’язок
Побудуємо область допустимих рішень, тобто вирішимо графічно систему нерівностей. Для цього побудуємо кожну пряму і визначимо півплощини, задані нерівностями (півплощини позначені штрихом).
Межі області
Позначимо границі області багатокутника рішень.
Цільова функція F(x) =>min
Розглянемо цільову функцію завдання F = 7X1+9X2 =>min.
Побудуємо пряму, що відповідає значенню функції F = 0: F = 7X1+9X2 = 0. Будемо рухати цю пряму паралельним чином. Оскільки нас цікавить мінімальне рішення, тому рухався прямо до першого торкання позначеної області. На графіку ця пряма позначена пунктирною лінією.
Рівний масштаб
Перетином півплощини буде область, яка представляє собою багатокутник, координати точок якого задовольняють умові нерівностей системи обмежень задачі.Пряма F(x) = const перетинає область у точці A. Оскільки точка A отримана в результаті перетину прямих 2 i 5, то її координати задовольняють рівнянням цих прямих:
x1+2x2≥2
x1=0
Вирішивши систему рівнянь, одержимо: x1 = 0, x2 = 1
Звідки знайдемо мінімальне значення цільової функції:
F(X) = 7*0 + 9*1 = 9