3.3. Опис методів пошуку оптимального рішення

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

Нехай є m пунктів відправлення (ПВ): , в яких зосереджені запаси якихось однорідних вантажів у кількості відповідно одиниць. Також є n пунктів призначення (ПП): , які подали заявки відповідно на одиниць вантажу. Вважаємо, що сума всіх заявок дорівнює сумі всіх запасів (збалансована транспортна задача):

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

Економіко-математична модель задачі має вигляд завдання лінійного програмування. Позначимо - кількість одиниць вантажу, що відправляється з i-го ПВ в j-й ПП. Сукупність чисел будемо називати планом перевезень, а самі величини - перевезеннями.

Необхідно знайти такий план перевезень, при якому цільова функція (сумарна вартість перевезень) буде мінімальною:

і який задовольняє наступним обмеженням:

1) Сумарна кількість вантажу, що направляється з кожного ПВ в усі ПН має дорівнювати запасу вантажу в даному пункті:

2) Сумарна кількість вантажу, що доставляється в кожен ПП з усіх ПЗ, має дорівнювати заявці, поданій даними пунктом:

3) Умова невід’ємності:

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

Отримавши перший опорний план перевезень, слід перевірити його на оптимальність і, якщо потрібно, перейти до нового опорного плану з меншою вартістю перевезень. Для цього можна використовувати метод потенціалів.

Після побудови вихідного опорного рішення всі змінні розбиті на дві групи: базисні (заповнені клітинки таблиці) та вільні (порожні, нульові елементи таблиці). Зіставимо кожному ПВ деяку величину , яку назвемо потенціалом постачальника , а кожному ПП поставимо у відповідність число - потенціал споживача . Сукупність рівнянь (де вартість перевезення з в ), складених для всіх базисних змінних, тобто для заповнених клітин, містить (m + n) невідомих потенціалів і (m + n-1) рівняння. Тому одну змінну u або v можна вибрати довільно, наприклад, . Значення інших потенціалів знаходять із системи однозначно.

Для кожної вільної клітини обчислюється числова характеристика - непряма вартість: .

Критерій оптимальності плану перевезень:

Для того, щоб певний опорний план транспортної задачі був оптимальним, необхідно і достатньо, щоб йому відповідала система з (m + n) чисел и , що задовольняють умовам:

1) , якщо (для заповнених клітин),

2) (для вільних клітин).

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

Якщо цей план перевезень не оптимальний, то у вільну комірку, якій відповідає найменша негативна непряма вартість , поміщають перевезення  і становлять цикл перерахунку (замкнута ламана лінія, що складається з горизонтальних і вертикальних відрізків прямих, перша вершина якої знаходиться у вільному комірку з перевезенням  , а інші в базисних (заповнених) комірках). За циклу перерахунку відновлюється баланс, порушений ненульовий перевезенням  .

Рис. 3.3.1.1 Цикл перевезення

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

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

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

1) Визначити початковий опорний план, розрахувати вартість перевезень.

2) Скласти систему рівнянь для заповнених клітин.

3) Визначити непрямі вартості вільних комірок за формулою:

4) Якщо всі непрямі вартості невід'ємні, то план перевезень оптимальний.

5) Якщо є негативні непрямі вартості, то у вільну комірку з найменшою негативною непрямої вартістю помістити перевезення і скласти цикл перерахунку.

6) Знайти максимальне значення за умови збереження невід’ємності всіх перевезень, скласти новий опорний план, розрахувати вартість перевезень.

7) Перейти до п.2.