відну, заповнюють також. Постачальник виключається з розгляду, якщо його запаси закінчуються. Споживач виключається з розгляду, якщо його запити задоволені повністю. На кожному кроці виключається або один постачальник, або один споживач. При цьому якщо постачальник не виключений, але його запаси дорівнюють нулю, то на тому кроці, коли від нього вимагається поставити вантаж, у відповідну клітину таблиці заноситься базисний нуль і лише потім постачальник виключається з розгляду. Аналогічно поступають із споживачем;
2. Перевірити отриманий опорний план на невироджені.
План називається виродженим, якщо кількість базисних клітин в ньому менше, ніж m + n - 1.Опорно план - невирождени, якщо число ненульових перевезень одно n + m-1, тому і початковий план також повинен задовольняти цій вимозі;
. Знайти потенціали опорного рішення.
Метод потенціалів призначено остаточної оптимізації рішення транспортної задачі.
Якщо допустиме рішення, i = 1,2, ..., m; j = 1,2, ... n транспортної задачі є оптимальним, то існують потенціали (числа) постачальників i = 1,2, ..., m і споживачів j = 1,2, ..., n, яке задовольняє наступним чином:
В
Група рівностей (2.1) використовується як система рівнянь для знаходження потенціалів. Дана система рівнянь має m + n невідомих i = 1,2, ..., m і j = 1,2, ..., n. Число рівнянь системи, як і число відмінних від нуля координат невиродженого опорного рішення, так само m + n-1. Так як число невідомих системи на одиницю більше числа рівнянь, то однією з них можна задати значення довільно, а інші знайти з системи. p> Група нерівностей (2.2) використовується для перевірки оптимальності опорного рішення. Ці нерівності зручніше представити в наступному вигляді:
(2.3)
Числа називаються оцінками для вільних клітин таблиці (векторів умов) транспортної задачі.
Опорна рішення є оптимальним, якщо для всіх векторів умов (клітин таблиці) оцінки недодатні.
Оцінки для вільних клітин транспортної таблиці використовуються при поліпшенні опорного рішення. Для цього знаходять клітку (l, k) таблиці, відповідну. Якщо, то рішення оптимальне. Якщо ж, то для відповідної клітини (l, k) будують цикл і покращую рішення, перерозподіляють вантаж по цьому циклу;
4. Обгрунтування результату
3. Рішення завдання вручну
1 Перевіримо на збалансованість.
Вартість доставки одиниці вантажу з кожного пункту відправлення у відповідні пункти призначення задана матрицею тарифів:
ЕлеваторХлебозаводЗапаси зерна1231203050420026020401200Потребность в зерне100020001600
Запаси зерна на елеваторах:
