(Назад)
(Cкачать работу)забезпечується тим, що всі ціни у фіктивних клітинках вибираються однаковими, а оскільки ці ціни при поставках не повинні впливати на значення цільової функції f, то їх беруть усі рівними нулю.
Занесемо вихідні дані у таблицю.
| В1 | В2 | В3 | В4 | В5 | Запаси | |
| А1 | 1 | 4 | 7 | 8 | 1 | 200 |
| А2 | 2 | 3 | 1 | 4 | 1 | 150 |
| А3 | 5 | 1 | 3 | 2 | 3 | 350 |
| А4 | 0 | 0 | 0 | 0 | 0 | 40 |
| Потреби | 120 | 130 | 200 | 180 | 110 |
Забезпечивши закритість розв'язуваної задачі, розпочинаємо будувати математичну модель даної задачі: Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так: Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
minZ = 1x11 + 4x12 + 7x13 + 8x14 +1x15 + 2x21 + 3x22 + 1x23 + 4x24 +1x25 +5x31 + 1x32 + 3x33 + 2x34 +3x35 + 0x41+ 0x42 + 0x43 + 0x44+0x45.
Загалом математична модель сформульованої задачі має вигляд:
minZ = 1x11 + 4x12 + 7x13 + 8x14 +1x15 + 2x21 + 3x22 + 1x23 + 4x24 +1x25 +5x31 + 1x32 + 3x33 + 2x34 +3x35 + 0x41+ 0x42 + 0x43 + 0x44+0x45.
за умов:
Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом «північно-західного кута».
| Ai | Bj | ui | ||||
| b1 = 120 | b2 = 130 | b3 = 200 | b4=180 | b5=110 | ||
| а1 = 200 | 1120 | 480 | 7 | 8 | 1 | u1 = 0 |
| а2 = 150 | 2 | 350 | 1100 | 4 | 1 | u2 = -1 |
| а3 = 350 | 5 | 1 | 3100 | 2180 | 370 | u3 = 1 |
| а4 = 40 | 0 | 0 | 0 | 0 | 040 | u4 = -2 |
| vj | v1 =1 | v2 =4 | v3 =2 | v4 =1 | V5 =2 |
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі:
Z1 = 1 120 + 4 80 + 3 50 + 1 100 + 3 100+ 2 180 + 3 70 + 0 40 = 1560
Підрахуємо число зайнятих клітин таблиці, їх 8, а має бути m+n-1=8. Отже, опорний план є невироджених.
Перевіримо оптимальність опорного плану, складемо систему рівнянь (для заповнених клітин таблиці) для визначення потенціалів першого опорного плану: Записана система рівнянь є невизначеною, і один з її розв’язків дістанемо, узявши, наприклад, u1 = 0. Тоді всі інші потенціали однозначно визначаються з цієї системи рівнянь: u1 =0, u2 = -1, u3 = 1, u4=-2, v1 =1, v2 =4, v3 =2 v4=1, v5=2. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.
Потім згідно з алгоритмом методу потенціалів перевіряємо виконання