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

Транспортна задача є задачею лінійного програмування, яку можна розв’язати симплекс-методом. Але специфічна структура транспортної задачі дає змогу використовувати для її розв’язування ефективніший метод, який повторює, по суті, кроки симплекс-алгоритму. Таким є метод потенціалів.

Алгоритм методу потенціалів складається з таких етапів.

1. Визначення типу транспортної задачі (відкрита чи закрита).

2. Побудова першого опорного плану транспортної задачі.

3. Перевірка плану транспортної задачі на оптимальність.

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

5. Новий план знову перевіряють на оптимальність, тобто повторюють дії п. 3, і т. д.

Розглянемо докладно кожний етап цього алгоритму.

1. Якщо під час перевірки збалансованості (5) виявилося, що транспортна задача є відкритою, то її необхідно звести до закритого типу. Це виконується введенням фіктивного умовного постачальника у разі перевищення загального попиту над за­­пасами із запасом . Якщо ж загаль­ні запаси постачальників перевищують попит споживачів , то до закритого типу задача зводиться введенням фіктивного умовного споживача з потребою .

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

Дата добавления: 2014-10-31