Математичне програмування (стр. 2 из 3)
Оптимальний план можна записати так:
x3 = 8
x1 = 4
x2 = 1
F(X) = 2*4 + 1*1 = 9
Визначаємо оптимальний план двоїстої задачі до поставленої задачі лінійного програмування.
F(Y)= -8Y1-3Y2+9Y3 (max)
Обмеження:
1Y1-1Y2+2Y3≤2
-4Y1+1Y2+1Y3≤1
Y1≥0
Y2≥0
Y3≥0
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних.
1x1-1x2 + 2x3 + 1x4 + 0x5 = 2
-4x1 + 1x2 + 1x3 + 0x4 + 1x5 = 1
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
| План | Базис | В | x1 | x2 | x3 | x4 | x5 |
| 0 | x4 | 2 | 1 | -1 | 2 | 1 | 0 |
| x5 | 1 | -4 | 1 | 1 | 0 | 1 | |
| Індексний рядок | F(X0) | 0 | 8 | 3 | -9 | 0 | 0 |
Перейдемо до основного алгоритму симплекс-метода.Оскільки в останньому стовбці присутньо кілька мінімальних елементів 1, то номер рядка вибираємо по правилу Креко.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | min |
| 1 | x4 | 2 | 1 | -1 | 2 | 1 | 0 | 1 |
| x5 | 1 | -4 | 1 | 1 | 0 | 1 | 1 | |
| Індексний рядок | F(X1) | 0 | 8 | 3 | -9 | 0 | 0 | 0 |
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | min |
| 2 | x3 | 1 | 0.5 | -0.5 | 1 | 0.5 | 0 | 0 |
| x5 | 0 | -4.5 | 1.5 | 0 | -0.5 | 1 | 0 | |
| Индекснаястрока | F(X2) | 9 | 12.5 | -1.5 | 0 | 4.5 | 0 | 0 |
| План | Базис | В | x1 | x2 | x3 | x4 | x5 |
| 3 | x3 | 1 | -1 | 0 | 1 | 0.3333 | 0.3333 |
| x2 | 0 | -3 | 1 | 0 | -0.3333 | 0.6667 | |
| Индекснаястрока | F(X3) | 9 | 8 | 0 | 0 | 4 | 1 |
Оптимальний план можливо записати так:
x3 = 1
x2 = 0
F(X) = -3*0 + 9*1 = 9
Завдання 3
Розв’язати транспортну задачу.
| 5 | 1 | 2 | 3 | 4 | 150 |
| 7 | 8 | 1 | 1 | 2 | 320 |
| 4 | 1 | 3 | 1 | 2 | 400 |
| 100 | 120 | 100 | 200 | 300 |
Розв’язок
Побудова математичної моделі. Нехай xij — кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача
. Оскільки 
, то задачу треба закрити, тобто збалансувати (зрівняти) поставки й потреби: 
У нашому випадку робиться це введенням фіктивного постачальника, оскільки 
. З уведенням фіктивного споживача в транспортній таблиці додатково заявляється n робочих клітинок (додатковий стовпчик).Виникає проблема, які ціни присвоїти цим клітинкам, щоб фіктивний стовпчик був нейтральним щодо оптимального вибору планових перевезень. Нейтральність забезпечується тим, що всі ціни у фіктивних клітинках вибираються однаковими, а оскільки ці ціни при поставках не повинні впливати на значення цільової функції f, то їх беруть усі рівними нулю.
Занесемовихіднідані у таблицю.
| В1 | В2 | В3 | В4 | В5 | В6 | Запаси | |
| А1 | 5 | 1 | 2 | 3 | 4 | 0 | 150 |
| А2 | 7 | 8 | 1 | 1 | 2 | 0 | 320 |
| А3 | 4 | 1 | 3 | 1 | 2 | 0 | 400 |
| Потреби | 100 | 120 | 100 | 200 | 300 | 50 |
Забезпечивши закритість розв'язуваної задачі, розпочинаємо будувати математичну модель даної задачі:
Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
minZ = 5x11 + 1x12 + 2x13 + 3x14 +4x15 + 0x16 +7x21 + 8x22 + 1x23 + 1x24 +2x25+0x26+4x31 + 1x32 + 3x33 + 1x34 +2x35 + 0x36.
Загалом математична модель сформульованої задачі має вигляд:
minZ = 5x11 + 1x12 + 2x13 + 3x14 +4x15 + 0x16 +7x21 + 8x22 + 1x23 + 1x24 +2x25+0x26+4x31 + 1x32 + 3x33 + 1x34 +2x35 + 0x36.
за умов:
Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом «північно-західного кута».
| Ai | Bj | ui | |||||
| b1 = 100 | b2 = 120 | b3 = 100 | b4=200 | b5=300 | B6=50 | ||
| а1 = 150 | 5[-] 100 | 1[+] 50 | 2 | 3 | 4 | 0 | u1 = 0 |
| а2 = 320 | 7 | 8[-] 70 | 1100 | 1[+] 150 | 2 | 0 | u2 = 7 |
| а3 = 400 | 4[+] | 1 | 3 | 1[-] 50 | 2300 | 050 | u3 = 7 |
| vj | v1 = 5 | v2 = 1 | v3 = -6 | v4 = -6 | v5= -5 | V6 = -7 | |
В результатіотримано перший опорний план, який є допустимим, оскількивсівантажі з баз вивезені, потреба магазинівзадоволена, а план відповідаєсистеміобмеженьтранспортноїзадачі.
Підрахуємо число зайнятих клітин таблиці, їх 8, а має бути m+n-1=8. Отже, опорний план є не вироджених.
Перевіримооптимальність опорного плану.Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Тоді всі інші потенціали однозначно визначаються з цієї системи рівнянь: u1 =0, u2 = 7, u3 = 7, v1 =5, v2 =1, v3 = -6 v4=1, v5= -5, v6= -7. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.
Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ≤ cij(для порожніх клітинок таблиці):
Опорний план не є оптимальним, тому щоіснуютьоцінкивільнихклітин для якихui + vi>cij
(2;1): 7 + 5 > 7
(3;1): 7 + 5 > 4
(3;2): 7 + 1 > 1
Тому відньогонеобхідно перейти до другого плану, змінившиспіввідношеннязаповнених і порожніхклітиноктаблиці. Вибираємомаксимальнуоцінкувільноїклітини (А3B1): 4
Ставимо в ній знак «+». Для визначення клітинки, що звільняється, будуємо цикл, починаючи з клітинки А3B1, та позначаємо вершини циклу почергово знаками «–» і «+». Тепер необхідно перемістити продукцію в межах побудованого циклу. Для цього у порожню клітинку А3B1 переносимо менше з чисел хij, які розміщені в клітинках зі знаком «–». Одночасно це саме число хij додаємо до відповідних чисел, що розміщені в клітинках зі знаком «+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «–».
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше,
, тобто 
. Додаємо 50 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 50 з Хij, що стоять в мінусових клітинах. В результатіотримаємоновийопорний план. Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n + m – 1).Отже, другий опорний план транспортної задачі матиме такий вигляд:
| Ai | Bj | ui | |||||
| b1 = 100 | b2 = 120 | b3 = 100 | b4=200 | b5=300 | B6=50 | ||
| а1 = 150 | 5[-] 50 | 1[+] 100 | 2 | 3 | 4 | 0 | u1 = 0 |
| а2 = 320 | 7 | 8[-] 20 | 1100 | 1200 | 2[+] | 0 | u2 = 7 |
| а3 = 400 | 4[+] 50 | 1 | 3 | 1 | 2[-] 300 | 050 | u3 = -1 |
| vj | v1 = 5 | v2 = 1 | v3 = -6 | v4 = -6 | v5= 3 | V6 = 1 | |
Перевіримооптимальністьопорного плану. Знайдемопотенціалиui, vi. по зайнятихклітинамтаблиці, в якихui + vi = cij, вважаючи, щоu1 = 0.