Розв'язування

Специфічними для транспортної задачі є такі дві обставини:

- кожна із змінних входить в два рівняння системи (1)-(2),

- всі коефіцієнти при змінних приймають лише два значення 0 або 1.

Умови 1) і 2) дозволили розробити для вирішення транспортної задачі алгоритми, суттєво простіші, ніж симплексний метод, що є одним з основних методів вирішення задач лінійного програмування. Найвідомішими з цих алгоритмів є метод потенціалів і угорський метод.

Метод потенціалів — це метод послідовного покращення плану (перевезень) з використанням другої теореми двоїстості для перевірки оптимальності.

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

Початковий опорний план

Для початку розв'язування слід визначити початковий опорний план, тобто значення , що задовольняють умови (1)-(3), при чому лише щонайбільше n + m + 1 з них є ненульовими і не обов'язково досягається мінімум лінійної функції Найпоширенішими методами пошуку початкових опорних планів є метод північно-західного кута, метод найменшої вартості і метод Фогеля.

Метод північно-західного кута]

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

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

Крок 2. Викреслюється рядок (або стовпець) з повністю реалізованою пропозицією (з задоволеним попитом). Це означає, що у викресленого рядку (стовпці) ми не будемо присвоювати значення іншим змінним (крім змінної, визначеної на першому етапі). Якщо одночасно задовольняються попит і пропозиція, викреслюється лише рядок або тільки стовпець.

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

Наприклад для попереднього прикладу початковий опорний план буде рівним:

					Кількість
Кількість

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

Дата добавления: 2015-11-16