Методика економіко-математичного програмування (стр. 2 из 3)
Ціни, додатковим клітинкам, щоб фіктивний стовбець був нейтральним щодо оптимального вибору планових перевезень, призначаються усі рівні нулю.
Занесемо вихідні дані у таблицю.
| В1 | В2 | В3 | В4 | В5 | В6 | Запаси | |
| А1 | 1 | 4 | 7 | 9 | 1 | 0 | 250 |
| А2 | 2 | 3 | 1 | 2 | 4 | 0 | 300 |
| А3 | 2 | 1 | 3 | 1 | 4 | 0 | 150 |
| Потреби | 110 | 80 | 100 | 90 | 70 | 250 |
Забезпечивши закритість розв'язуваної задачі, розпочинаємо будувати математичну модель даної задачі:
Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
minZ=1x11+4x12+7x13+9x14+1x15+0x16+2x21+3x22+1x23+2x24+4x25+0x26+2x31+1x32+3x33+1x34+ +4x35+0x36.
Загалом математична модель сформульованої задачі має вигляд:
minZ=1x11+4x12+7x13+9x14+1x15+0x16+2x21+3x22+1x23+2x24+4x25+0x26+2x31+1x32+3x33+1x34+ +4x35+0x36.
за умов:
Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом «північно-західного кута».
| Ai | Bj | ui | |||||
| b1 = 110 | b2 = 80 | b3 = 100 | b4=90 | b5=70 | b6=250 | ||
| а1 = 250 | 1110 | 480 | 7[-]60 | 9 | 1[+] | 0 | u1 = 0 |
| а2 = 300 | 2 | 3 | 1[+]40 | 290 | 4[-]70 | 0100 | u2 = -6 |
| а3 = 150 | 2 | 1 | 3 | 1 | 4 | 0150 | u3 = -6 |
| vj | v1 =1 | v2 =4 | v3 =7 | v4 =8 | v5 =10 | v6 =6 | |
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
Підрахуємо число зайнятих клітин таблиці, їх 8, а має бути m+n-1=8. Отже, опорний план є не виродженим.
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0:
u1=0, u2=-6, u3=-6, v1=1, v2=4, v3=7 v4=8, v5=10, v6=6. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.
Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ≤ cij(для порожніх клітинок таблиці).
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij
(1;5): 0 + 10 > 1
(1;6): 0 + 6 > 0
(3;4): -6 + 8 > 1
Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (А1B5): 1. Для цього в перспективну клітку (1;5) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
Тепер необхідно перемістити продукцію в межах побудованого циклу. З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (1;3) = 60. Додаємо 60 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 60 з хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
Для цього у порожню клітинку А1B5 переносимо менше з чисел хij, які розміщені в клітинках зі знаком «–». Одночасно це саме число хij додаємо до відповідних чисел, що розміщені в клітинках зі знаком «+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «–».
Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n + m – 1).
Отже, другий опорний план транспортної задачі матиме такий вигляд:
| Ai | Bj | ui | |||||
| b1 = 110 | b2 = 80 | b3 = 100 | b4=90 | b5=70 | b6=250 | ||
| а1 = 250 | 1110 | 4[-]80 | 7 | 9 | 1[+]60 | 0 | u1 = 0 |
| а2 = 300 | 2 | 3 | 1100 | 290 | 4[-]10 | 0[+]100 | u2 = 3 |
| а3 = 150 | 2 | 1[+] | 3 | 1 | 4 | 0[-]150 | u3 = 3 |
| vj | v1 =1 | v2 =4 | v3 =-2 | v4 =-1 | v5 =1 | v6 =-3 | |
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij
(2;1): 3 + 1 > 2
(2;2): 3 + 4 > 3
(3;1): 3 + 1 > 2
(3;2): 3 + 4 > 1
(3;4): 3 + -1 > 1
Вибираємо максимальну оцінку вільної клітини (А3B2): 1
Для цього в перспективну клітку (А3B2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А2B5) = 10. Додаємо 10 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 10 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
| Ai | Bj | ui | |||||
| b1 = 110 | b2 = 80 | b3 = 100 | b4=90 | b5=70 | b6=250 | ||
| а1 = 250 | 1110 | 4[-]70 | 7 | 9 | 170 | 0[+] | u1 = 0 |
| а2 = 300 | 2 | 3 | 1100 | 290 | 4 | 0110 | u2 = -3 |
| а3 = 150 | 2 | 1[+]10 | 3 | 1 | 4 | 0[-]140 | u3 = -3 |
| vj | v1 =1 | v2 =4 | v3 =4 | v4 =5 | v5 =1 | v6 =3 | |
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij
(1;6): 0 + 3 > 0
(3;4): -3 + 5 > 1
Вибираємо максимальну оцінку вільної клітини (А1B6): 0
Для цього в перспективну клітку (А1B6) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А1B2)=70. Додаємо 70 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 70 з Хij, що стоять в мінусових клітинах.
В результаті отримаємо новий опорний план.
| Ai | Bj | ui | |||||
| b1 = 110 | b2 = 80 | b3 = 100 | b4=90 | b5=70 | b6=250 | ||
| а1 = 250 | 1110 | 4 | 7 | 9 | 170 | 070 | u1 = 0 |
| а2 = 300 | 2 | 3 | 1100 | 2[-]90 | 4 | 0[+]110 | u2 = 0 |
| а3 = 150 | 2 | 180 | 3 | 1[+] | 4 | 0[-]70 | u3 = 0 |
| vj | v1 =1 | v2 =1 | v3 =1 | v4 =2 | v5 =1 | v6 =0 | |
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij
(3;4): 0 + 2 > 1
Вибираємо максимальну оцінку вільної клітини (А3B4): 1
Для цього в перспективну клітку (А3B4) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А3B6) =70. Додаємо 70 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 70 з Хij, що стоять в мінусових клітинах.
В результаті отримаємо новий опорний план.
| Ai | Bj | ui | |||||
| b1 = 110 | b2 = 80 | b3 = 100 | b4=90 | b5=70 | b6=250 | ||
| а1 = 250 | 1110 | 4 | 7 | 9 | 170 | 070 | u1 = 0 |
| а2 = 300 | 2 | 3 | 1100 | 220 | 4 | 0180 | u2 = 0 |
| а3 = 150 | 2 | 180 | 3 | 170 | 4 | 0 | u3 = -1 |
| vj | v1 =1 | v2 =2 | v3 =1 | v4 =2 | v5 =1 | v6 =0 | |
Перевіримо оптимальність опорного плану, тобто повторюємо описані раніше дії.
Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
математичний модель симплекс екстремум
Перевірка останнього плану на оптимальність за допомогою методу потенціалів показує, що він оптимальний.
Розрахуємо значення цільової функції відповідно до другого опорного плану задачі:
F(x) = 1*110 + 1*70 + 0*70 + 1*100 + 2*20 + 0*180 + 1*80 + 1*70 = 470
За оптимальним планом перевезень загальна вартість перевезень всієї продукції є найменшою і становить 470 грн.
Завдання 4
Знайти графічним методом екстремуми функцій в області, визначеній нерівностями.
