Знаходження оптимального плану транспортної задачі методом потенціалів

Для знаходження оптимального плану транспортної задачі необхідно спочатку визначити опорний план перевезень з допомогою методу північно-західного кута чи методу мінімального елемента.

Теорема: Якщо Метод потенціалів — деякий опорнй план транспортної задачі, для якого виконуються наступні обмеження, а саме:

Метод потенціалівдля Метод потенціалів

Метод потенціалівдля Метод потенціалів

тоді даний опорний план є оптимальним. Метод потенціалів — називаються потенціалами пунктів відправлення та пунктів призначення.

Перевірку опорного плану на оптимальність здійснюють за допомогою методу потенціалів.

Алгоритм даного методу полягає в наступному:

1. Знаходимо потенціали пунктів відправлення (Метод потенціалів) і пунктів призначення (Метод потенціалів). Для цього, для кожної зайнятої клітинки будуємо лінійне рівняння виду:

Метод потенціалів

В результаті отримуємо систему лінійних рівнянь, розв'язавши яку знайдемо шукані потенціали. Зуваження: Зайнятих клітинок завжди є n+m-1. Значить ми отримаємо n+m-1 рівняння з n+mневідомими. Щоб розв'язати дану систему покладаємо Метод потенціалів.

2. Для усіх вільних клтінок знаходимо значення metod_potencialiv2.

Якщо всі едементи Метод потенціалів будуть додатніми, то побудований опорний план є оптимальним.

Якщо ж серед значень Метод потенціалів будуть від'ємні елементи, то це означає, що побудований опорний план не являється оптимальним і є можливість переходу до іншого опорного плану.

Алгоритм переходу до іншого опорного плану наступний:

1) серед усіх від'ємних Метод потенціалів знаходимо максимальне по модулю значення. Це означає, що дана клітинка повинна бути зайнятою;

2) для клітинки в якій знаходиться максимальне по модулю значення будуємо цикл перерахунку;

Означення: цикл перерахунку — це ламана лінія, вершини якої знаходяться в зайнятих клітинках і від кожної вершини виходять два відрізки, один з яких знаходиться в рядку, а другий в стовбці. Ламана лінія повинна бути замкнутою.

Якщо відрізки ламаної лінії перетиноються, то точка перетину вершиною не вважається.

Якщо правильно побудований опорний план, то завжди існує принаймі один цикл перерахунку.

3) починаючи з клітинки, де знаходиться Метод потенціалів, кожну вершину циклу позначаємо знаком плюс і мінус, чергуючи їх послідовно;

4) серед значень клітинок позначених мінусом вибираємо мінімальне значення;

5) до клітинок позначених знаком плюс додаємо це (мінімальне) значення, а від клітинок позначених знаком мінус — віднімаємо мінімальне значення.

Клітинка де знаходилось мінімальне значення стає вільною. В результаті отримуємо новий опорний план, який знову потрібно перевірити на оптимальність.

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар