було довести.
Таким чином, якщо план потенціалів, то він оптимальний. Це і є тим критерієм, за яким судять про оптимальність плану.
Справедливо і зворотне положення: якщо план оптимальний, то він о6язательно потенціалом. Ця умова (необхідність) приймається без доведення. [5]
10. Особливості вирішення транспортних завдань з неправильним балансом
Може статися, що в розглянутих пунктах запаси не рівні потребам: або з АПАС перевершують потреби, або ж запаси не забезпечують потреб.
Така модель задачі називається відкритою. Для неї теж можна відшукати план з мінімумом транспортних витрат, але не будуть задоволені всі потреби, чи не буде вивезено весь вантаж, так як не можна підібрати таку систему чисел, яка при підсумовуванні по рядках давала б один результат, а при підсумовуванні по стовпцях - інший.
Для вирішення завдання поступаємо таким чином.
Перший випадок. . p> У математичну модель транспортної завдання введемо фіктивний ( l + l) - й пункт призначення. Для цього в матриці завдання передбачимо один стовпець, для якого потреба буде дорівнює надлишку вантажу:
,
Всі тарифи на доставку вантажу в цей пункт будемо вважати рівними нулю. Отримаємо нову задачу, причому для старої і нової завдання функціонал буде один і той же, тому що ціни на додаткові перевезення дорівнюють нулю:
min
Фіктивний споживач забезпечує спільність обмежень, не вносячи спотворень у вирішення.
Другий випадок.
Якщо запасів не вистачає для задоволення потреб, тобто , То вводимо фіктивний ( k +1) - Й пункт відправлення, якому приписуємо запас вантажу, рівний
,
тарифи на доставку вантажів з цього фіктивного складу знову, вважаємо нульовими. У матриці додасться один рядок. На функціоналі це не позначиться, а система обмежень задачі стане спільною, тобто стане можливим відшукання оптимального плану на мінімум вартості перевезень. [5]
11. Алгоритм вирішення транспортної задачі методом потенціалів
Алгоритм методу потенціалів розділяється на попередній крок, що виконується на початку рішення, і спільний крок, повторюваний до тих пір, поки не буде отриманий оптимум.
11.1 Попередній крок
Цей крок включає наступних три етапи.
1. Знаходимо допустимий ациклічний план.
2. Складаємо систему чисел - потенціалів пунктів відправлення і пунктів призначення.
3. Аналізуємо систему на потенційність. Якщо вона потенціальна (тобто план потенціали), то знайдений план оптимальний. Якщо система не потенціальна, приступаємо до загального кроці.
Перший етап: знаходження допустимого ациклического плану способом північно-західного кута.
Незважаючи на тарифи, починаємо складання плану з заповнення лівій верхній клітини (1,1) (з північно-зах...
