Контрольная работа: Розв’язання лінійних задач методами лінійного програмування
Таким чином, в таблиці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 | × | × |
Транспортні витрати:
тобто при такому плані перевезення товару транспортні витрати знизилися на 50грн. в порівнянні з попереднім планом перевезення. Але, щоб визначити є отриманий план оптимальним чи ні, виконаємо перевірку.
Перевірку всіх вільних клітин зобразимо в таблиці9, в якій для всіх вільних клітин запишемо різницю між сумою потенціалів і транспортними витратами в клітині.
Таблиця9– Перевірка плану отриманого в результаті третього кроку пошуку оптимального рішення задачі
| | | | | |
| - | - | - | -7 | -2 |
| 2 | - | -5 | -9 | -3 |
| 8 | 4 | - | - | 3 |
| 3 | 4 | - | -8 | - |
З таблиці9 видно, що додатне значення отримали для клітин А2 В1 (2), А3 В1 (8), А3 В2 (4), А3 В5 (3), А4 В1 (3) і А4 В2 (4). Максимальне значення max(2;8;4;3;3;4)=8в клітині А3 В1 , тому заповнюємо і цикл будуємо для неї (цикл показано в таблиці8, результат дій в таблиці10).
Таблиця1– Четвертий крок пошуку оптимального рішення задачі
| Виробник | Споживач | Запаси продукту | | ||||
| | | | | |||
| 8 |  3 | 3 | 4 | 0 | 60 | 0 |
| 25 | 10 | 25 | |||||
| 5 | 2 | 7 | 5 | 0 | 20 | -1 |
| 20 | |||||||
| 5 | 4 | 8 | 2 | 0 | 30 | -3 |
| 15 | 15 | ||||||
| 7 | 1 | 5 | 7 | 0 | 20 | 2 |
| 5 | 15 | ||||||
| Потреба в продукті | 40 | 30 | 30 | 15 | 15 | 130 | × |
 | 8 | 3 | 3 | 5 | -2 | × | × |
Транспортні витрати:
що на 120грн. економніше попереднього варіанту розвезення продукції від постачальників до споживачів.
Перевірка всіх вільних клітин наведена в таблиці11.
Таблиця11– Різниця між сумою потенціалів і транспортними витратами для вільних клітин
 |  |  |  |  | |
 | - | - | - | 1 | -2 |
 | 2 | - | -5 | -1 | -3 |
 | - | -4 | -8 | - | -5 |
 | 3 | 4 | - | 0 | - |
План, зображений в таблиці10 не є оптимальним, оскільки отримали додатні значення в клітинах А1 В4 (1), А2 В1 (2), А4 В1 (3), А4 В2 (4). Заповнюємо клітину А4 В2 і будуємо опорний план (таблиця12).