Розв’язання лінійних задач методами лінійного програмування (стр. 3 из 6)
Таблиця5– Розподіл продукту по споживачам
| Виробник | Споживач | Запаси продукту | ||||
 |  |  |  |  | ||
 | 8 | 3 | 3 | 4 | 0 | 60 |
| 40 | 20 | |||||
 | 5 | 2 | 7 | 5 | 0 | 20 |
| 10 | 10 | |||||
 | 5 | 4 | 8 | 2 | 0 | 30 |
| 20 | 10 | |||||
 | 7 | 1 | 5 | 7 | 0 | 20 |
| 5 | 15 | |||||
| Потреба в продукті | 40 | 30 | 30 | 15 | 15 | 130 |
Таким чином, в таблиці5 отримали початковий опорний план, транспортні витрати за яким складають:
Недоліком використаного методу знаходження опорного плану є ігнорування величини тарифів на перевезення продукту.
Для визначення оптимального плану перевезень використаємо метод потенціалів. Для цього кожному виробнику Аі (кожному рядку) ставимо у відповідність деяке число
а кожному споживачу Ві (кожному стовпчику)– деяке число 
На основі таблиці5 складемо таблицю6, в якій додамо один стовпчик і один рядок для написання величини параметрів 
і 
. Їх знаходимо використовуючи першу умову оптимальності транспортної задачі: 
(для кожної зайнятої клітини сума потенціалів повинна дорівнювати вартості одиниці перевезення, що записана в цій клітині).Таблиця6– Перевірка оптимальності опорного плану
| Виробник | Споживач | Запаси продукту | | ||||
| | | | | | |||
| | 8 | 3 | 3 | 4 | 0 | 60 | 0 |
| 40 | 20 | ||||||
| | 5 | 2 | 7 | 5 | 0 | 20 | -1 |
| 10 | 10 | ||||||
| | 5 | 4 |  8 | 2 | 0 | 30 | 0 |
| 20 | 10 | ||||||
| | 7 | 1 | 5 | 7 | 0 | 20 | 5 |
| 5 | 15 | ||||||
| Потреба в продукті | 40 | 30 | 30 | 15 | 15 | 130 | × |
| | 8 | 3 | 8 | 2 | -5 | × | × |
Систему потенціалів можна побудувати лише для невирожденого опорного плану. Такий план містить m+n-1 лінійно незалежних рівнянь виду
з m+n невідомими (де m– кількість постачальників, n– кількість споживачів). Рівнянь на одне менше, ніж невідомих, тому система є невизначеною і для її розв’язку одному невідомому (нехай ним буде u1) придамо нульове значення.Для того, щоб план був оптимальним, повинна виконуватись умова: для кожної незайнятої клітини сума потенціалів повинна бути менша або дорівнювати вартості одиниці перевезення, що стоїть в цій клітині:
тобто 
Робимо перевірку для всіх вільних клітин: 
З розрахунків бачимо, що умова оптимальності не виконується для клітин, А1В3, А2В1, А3В1, А4В1, А4В2, і А4В3. Клітину, в якій додатне число отримали максимальним (А2В3, оскільки max(5;2;3;6;7;8)=8) зробимо зайнятою, для цього побудуємо цикл і отримуємо таблицю7.
Таблиця7– Другий крок пошуку оптимального рішення
| Виробник | Споживач | Запаси продукту | | ||||
| | | | | | |||
| | 8 |  3 | 3 | 4 | 0 | 60 | 0 |
| 40 | 20 | ||||||
| | 5 | 2 | 7 | 5 | 0 | 20 | -1 |
| 10 | 10 | ||||||
| | 5 | 4 | 8 | 2 | 0 | 30 | 0 |
| 15 | 15 | ||||||
| | 7 | 1 | 5 | 7 | 0 | 20 | -3 |
| 5 | 15 | ||||||
| Потреба в продукті | 40 | 30 | 30 | 15 | 15 | 130 | × |
| | 8 | 3 | 8 | 2 | 3 | × | × |
Транспортні витрати при такому плані перевезення складають:
Перевірка всіх вільних клітин:
Отримали від’ємні значення у всіх клітинах окрім А1В3 (5), А1В5 (3), А2В1 (2), А2В5 (2), А3В1 (3) і А3В5 (3). Максимальне значення max(5;3;2;2;3;3)=5в клітині А1В3, тому заповнюємо і цикл будуємо для неї (цикл показано в таблиці7, результат дій в таблиці8).
Таблиця8– Третій крок пошуку оптимального рішення
| Виробник | Споживач | Запаси продукту | | ||||
 | | | | | |||
| | 8 | 3 | 3 | 4 | 0 | 60 | - |
| 40 | 10 | 10 | |||||
| | 5 | 2 | 7 | 5 | 0 | 20 | -1 |
| 20 | |||||||
| | 5 | 4 | 8 | 2 | 0 | 30 | 5 |
| 15 | 15 | ||||||
| | 7 | 1 | 5 | 7 | 0 | 20 | 2 |
| 5 | 15 | ||||||
| Потреба в продукті | 40 | 30 | 30 | 15 | 15 | 130 | × |
| | 8 | 3 | 3 | -3 | -2 | × | × |
Транспортні витрати: