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