". Вибирається клітина з мінімальним тарифом і заповнюється максимально можливим числом, при цьому вичерпуються або запаси, які потреби (викреслюється рядок або стовпець), вибирається наступна клітина з мінімальним тарифом і т.д.
в) Метод апроксимації Фогеля.
Для заповнення кожної клітини необхідно знайти різниці між двома мінімальними тарифами по всіх стовпцях і рядках, записати їх, відповідно, внизу і праворуч таблиці. Серед знайдених різниць вибирають максимальну. У рядку (або стовпці), якій відповідає дана різниця, заповнюють клітину з мінімальним тарифом. Якщо максимальних різниць кілька однакових, вибирають ту, якої відповідає мінімальний тариф. Якщо мінімальний тариф однаковий для кількох клітин в рядку (стовпці), то заповнюють ту, яка стоїть в стовпці (рядку), що має найбільшу різницю між двома мінімальними тарифами.
Як правило, при побудові опорного плану цими трьома методами виконується наступне співвідношення: Fв (x) Fб (x) Fа (x).
1. Будують опорний план одним з методів.
Побудований опорний план слід перевірити на оптимальність, для чого використовують наступну теорему.
ТЕОРЕМА. Якщо для деякого опорного плану транспортної задачі існують такі числа і. що
для всіх і, то цей план є оптимальним.
ВИЗНАЧЕННЯ 4. Числа і (,) називаються потенціалами, відповідно, постачальників і споживачів.
Т.ч. знайшовши потенціали постачальників і споживачів, що задовольняють умовам теореми, ми доведемо оптимальність побудованого плану. Як їх знайти? Оскільки число заповнених клітин, xij> 0, так само n + m-1 (невироджених план), то система (4) з n + m невідомими містить n + m-1 рівняння. Покладемо одне з невідомих рівним нулю і послідовно знайдемо значення інших невідомих. Потім для всіх вільних клітин, xij = 0, визначимо числа.
Якщо серед чисел немає позитивних, то умови теореми виконані, і план є оптимальним. Якщо існує> 0, то побудований план не оптимальний, і його слід поліпшити.
Алгоритм поліпшення плану:
1) серед всіх> 0 вибирають максимальне;
2) для відповідної клітини будують цикл перерахунку;
3) позначають вершини циклу перерахунку послідовно знаками "+" і "-". починаючи з "+" у вихідній клітці;
4) серед чисел, що стоять в клітинах, позначених "-". визначають мінімальну;
5) до значень, що стоять в "+" - клітинах, додають це мінімальне число, а з значень, що стоять в "-" - клітинах, це число віднімають.
ВИЗНАЧЕННЯ 5. Циклом перерахунку називається ламана лінія, вершини якої розташовані в зайнятих клітинах, а ланки - уздовж рядків і стовпців, причому в кожній вершині циклу може бути тільки дві ланки.
Змінений у такий спосіб план знову перевіряють на оптимальність, тобто перехід до п. 2.
3. Метод диференціальних рент
На відміну від методу потенціалів, для якого спочатку будувався опорний план, а потім він послідовно поліпшувався, при вирішенні завдання методом диференціальних рент відразу найкращим чином розподіляють частина продукції між споживачами і на наступних ітераціях поступово зменшують загальну величину нерозподілених поставок.
Для визначення рішення транспортної задачі методом диференціальних рент використовують наступний алгоритм:
У кожному стовпці визначають мінімальний тариф і виділяють сответствует-щую клітку.
2. Виділені клітини заповнюють максимально можливими числами.
3. Оскільки в загальному випадку цей розподіл не задовольняє всіх споживча п-лей, щоб на наступних кроках скорочувати величину незадоволених потреб, необхідно оцінити постачальників.
ВИЗНАЧЕННЯ 6. Рядки, відповідні постачальникам, запаси яких вичерпані, а потреби виділених споживачів не задоволені, є негативними.
ВИЗНАЧЕННЯ 7. Рядки, відповідні постачальникам, запаси яких не вичерпані повністю, є позитивними.
ВИЗНАЧЕННЯ 8. Рядки, відповідні постачальникам, запаси яких вичерпані, а потреби виділених споживачів задоволені, мають нульову оцінку. При цьому, якщо друга заповнена клітина, що стоїть в стовпці, пов'язаному з даною рядком ще однієї заповненої кліткою, розташована в позитивній рядку, цей рядок з нульовою оцінкою вважається позитивною. В іншому випадку - негативною.
4. Для кожного стовпця, має виділений тариф в негативній рядку, знаходять різниці між виділеним тарифом і найближчим до нього за величиною тарифом, хто стоїть в позитивній рядку.
5. Серед отриманих різниць визначають мінімальну. Це число називають проміжної рентою.
6. Будують нову таблицю, при цьому тарифи, які стоять в позитивних рядках, переписуються без зміни, а тарифи, які стоять в негативних рядках, збільшуються на величину проміжної ренти.
7. Переходять до п.1.
ЗАУВАЖЕННЯ: а) якщо в рядку або стовпці виявляється більше однієї виділеної клітини, то заповнюють, в першу чергу, ті виділені клітини, які є єдиними в стовпці або рядку;
б) якщо вдається розподілити всі запаси, то отримують оптимальний план транспортної задачі.
4. Додаткові обмеження транспортної задачі
1. Заборонені маршрути.
Якщо з яких-небудь причин неможливо постачати продукцію з п. А i в п. В j. припускають тариф цього шляху як завгодно великою величиною М, сij =