Математичні моделі задач лінійного програмування (стр. 2 из 3)
Визначивши обернену матрицю А-1 через алгебраїчне доповнення, отримаємо:
Як видно із останнього плану симплексної таблиці, обернена матриця A-1 розміщена у стовбцях додаткових змінних.
Тоді Y = C*A-1 =
Запишемо оптимальний план двоїстої задачі:
y1 = 3
y2 = 0
y3 = 0
Z(Y) = 6*3+-2*0+35*0 = 18
Завдання 3
Розв’язати транспортну задачу.
| 2 | 4 | 5 | 8 | 6 | 180 |
| 7 | 3 | 6 | 4 | 5 | 300 |
| 8 | 5 | 6 | 5 | 3 | 230 |
| 110 | 140 | 220 | 190 | 120 |
Розв’язок
Побудова математичної моделі. Нехай xij — кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача
. Оскільки 
, то задачу треба закрити, тобто збалансувати (зрівняти) поставки й потреби: 
У нашому випадку робиться це введенням фіктивного постачальника, оскільки 
З уведенням фіктивного постачальника в транспортній таблиці додатково заявляється n робочих клітинок.
Ціни, додатковим клітинкам, щоб фіктивний рядок був нейтральним щодо оптимального вибору планових перевезень, призначаються усі рівні нулю.
Занесемо вихідні дані у таблицю.
| В1 | В2 | В3 | В4 | В5 | Запаси | |
| А1 | 2 | 4 | 5 | 8 | 6 | 180 |
| А2 | 7 | 3 | 6 | 4 | 5 | 300 |
| А3 | 8 | 5 | 6 | 5 | 3 | 230 |
| А4 | 0 | 0 | 0 | 0 | 0 | 70 |
| Потреби | 110 | 140 | 220 | 190 | 120 |
Забезпечивши закритість розв'язуваної задачі, розпочинаємо будувати математичну модель даної задачі:
Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
minZ=2x11+4x12+5x13+86x14+6x15+7x21+3x22+6x23+4x24+5x25+8x31+5x32+6x33+5x34+ +3x35+0x41+0x42+0x43+0x44+0x45.
Загалом математична модель сформульованої задачі має вигляд:
minZ=2x11+4x12+5x13+86x14+6x15+7x21+3x22+6x23+4x24+5x25+8x31+5x32+6x33+5x34+ +3x35+0x41+0x42+0x43+0x44+0x45.
за умов:
Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом «північно-західного кута».
| Ai | Bj | ui | ||||
| b1 = 110 | b2 = 140 | b3 = 220 | b4=190 | b5=120 | ||
| а1 = 180 | 2110 | 470 | 5 | 8 | 6 | u1 = 0 |
| а2 = 300 | 7 | 370 | 6[-]220 | 4[+]10 | 5 | u2 = -1 |
| а3 = 230 | 8 | 5 | 6 | 5[-]180 | 3[+]50 | u3 = 0 |
| а4 = 70 | 0 | 0 | 0[+] | 0 | 0[-]70 | u4 = -3 |
| vj | v1 =2 | v2 =4 | v3 =7 | v4 =5 | v5 =3 | |
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
Підрахуємо число зайнятих клітин таблиці, їх 8, а має бути m+n-1=8. Отже, опорний план є не виродженим.
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0
u1=0, u2=-1, u3=0, u4=-3, v1=2, v2=4, v3=7 v4=5, v5=3
Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.
Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ≤ cij (для порожніх клітинок таблиці).
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij
(1;3): 0 + 7 > 5
(3;3): 0 + 7 > 6
(4;2): -3 + 4 > 0
(4;3): -3 + 7 > 0
(4;4): -3 + 5 > 0
Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (А4B3): 0. Для цього в перспективну клітку (4;3) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
Тепер необхідно перемістити продукцію в межах побудованого циклу.
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (4;5) = 70.
Додаємо 70 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 70 з хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
Для цього у порожню клітинку А4B3 переносимо менше з чисел хij, які розміщені в клітинках зі знаком «–».
Одночасно це саме число хij додаємо до відповідних чисел, що розміщені в клітинках зі знаком «+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «–».
Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін.
Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n + m – 1).
Отже, другий опорний план транспортної задачі матиме такий вигляд
| Ai | Bj | ui | ||||
| b1 = 110 | b2 = 140 | b3 = 220 | b4=190 | b5=120 | ||
| а1 = 180 | 2110 | 4[-]70 | 5[+] | 8 | 6 | u1 = 0 |
| а2 = 300 | 7 | 3[+]70 | 6[-]150 | 480 | 5 | u2 = -1 |
| а3 = 230 | 8 | 5 | 6 | 5110 | 3120 | u3 = 0 |
| а4 = 70 | 0 | 0 | 070 | 0 | 0 | u4 = -7 |
| vj | v1 =2 | v2 =4 | v3 =7 | v4 =5 | v5 =3 | |
Перевіримо оптимальність опорного плану.Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij
(1;3): 0 + 7 > 5
(3;3): 0 + 7 > 6
Вибираємо максимальну оцінку вільної клітини (А1B3): 5
Для цього в перспективну клітку (А1B3) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-».
Цикл наведено в таблиці.
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А1B2) = 70.
Додаємо 70 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 70 з Хij, що стоять в мінусових клітинах.
В результаті отримаємо новий опорний план.
| Ai | Bj | ui | ||||
| b1 = 110 | b2 = 140 | b3 = 220 | b4=190 | b5=120 | ||
| а1 = 180 | 2110 | 4 | 570 | 8 | 6 | u1 = 0 |
| а2 = 300 | 7 | 3140 | 6[-]80 | 4[+]80 | 5 | u2 = 1 |
| а3 = 230 | 8 | 5 | 6[+] | 5[-]110 | 3120 | u3 = 2 |
| а4 = 70 | 0 | 0 | 070 | 0 | 0 | u4 = -5 |
| vj | v1 =2 | v2 =2 | v3 =5 | v4 =3 | v5 =1 | |
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij
(3;3): 2 + 5 > 6
Вибираємо максимальну оцінку вільної клітини (А3B3): 6
Для цього в перспективну клітку (А3B3) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А2B3) =80. Додаємо 80 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 80 з Хij, що стоять в мінусових клітинах.
В результаті отримаємо новий опорний план.
| Ai | Bj | ui | ||||
| b1 = 110 | b2 = 140 | b3 = 220 | b4=190 | b5=120 | ||
| а1 = 180 | 2110 | 4 | 570 | 8 | 6 | u1 = 0 |
| а2 = 300 | 7 | 3140 | 6 | 4160 | 5 | u2 = 0 |
| а3 = 230 | 8 | 5 | 680 | 530 | 3120 | u3 = 1 |
| а4 = 70 | 0 | 0 | 070 | 0 | 0 | u4 = -5 |
| vj | v1 =2 | v2 =3 | v3 =5 | v4 =4 | v5 =2 | |
Перевіримо оптимальність опорного плану, тобто повторюємо описані раніше дії.
Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Перевірка останнього плану на оптимальність за допомогою методу потенціалів показує, що він оптимальний.
Розрахуємо значення цільової функції відповідно до другого опорного плану задачі
F(x) = 2*110 + 5*70 + 3*140 + 4*160 + 6*80 + 5*30 + 3*120 + 0*70 = 2620
За оптимальним планом перевезень загальна вартість перевезень всієї продукції є найменшою і становить 2620 грн.
Завдання 4
Знайти графічним методом екстремуми функцій в області, визначеній нерівностями.
