Рішення транспортної задачі лінійного програмування

курсовая работа

4. Критерій оптимальності базисного рішення транспортної задачі. Методи відшукання оптимального рішення

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

Звідси випливає спосіб відшукання оптимального рішення транспортної задачі, що складає в тім, що, маючи деяке базисне рішення, обчислюють алгебраїчні суми тарифів для всіх вільних кліток. Якщо критерій оптимальності виконаний, то дане рішення є оптимальним; якщо ж є клітки з негативними алгебраїчними сумами тарифів, то переходять до нового базису, роблячи перерахування по циклі, що відповідає однієї з таких кліток. Отримане в такий спосіб нове базисне рішення буде краще вихідного - витрати на його реалізацію будуть меншими. Для нового рішення також перевіряють критерій оптимальності і якщо буде потреба знову роблять перерахування по циклу для однієї із кліток з негативною алгебраїчною сумою тарифів і т.д.

Через кінцеве число кроків приходять до шуканого оптимального базисного рішення.

У випадку якщо алгебраїчні суми тарифів для всіх вільних кліток позитивні, ми маємо єдине оптимальне рішення; якщо ж алгебраїчні суми тарифів для всіх вільних кліток ненегативні, але серед них є алгебраїчні суми тарифів, рівні нулю, то оптимальне рішення не єдине: при перерахуванні по циклі для клітки з нульовою алгебраїчною сумою тарифів ми одержимо оптимальне ж рішення, але відмінне від вихідного (витрати по обох планах будуть однаковими).

Залежно від методів підрахунку алгебраїчних сум тарифів для вільних кліток розрізняють два методи відшукання оптимального рішення транспортної задачі:

Розподільний метод. При цьому методі для кожної порожньої клітки будують цикл і для кожного циклу безпосередньо обчислюють алгебраїчну суму тарифів.

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

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

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

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

Вище розглядалася закрита модель транспортної задачі, із правильним балансом, коли виконується умова (1.3). У випадку виконання (1.4) (відкрита модель) баланс транспортної задачі може порушуватися в 2-ух напрямках:

1. Сума запасів у пунктах відправлення перевищує суму поданих заявок (транспортна задача з надлишком запасів):

аi > bj ( де i=1,...,m ; j=1,...,n );

2. Сума поданих заявок перевищує наявні запаси (транспортна задача з надлишком заявок):

аi < bj ( де i=1,...,m ; j=1,...,n );

Розглянемо послідовно ці два випадки:

Транспортна задача з надлишком запасів.

Зведемо її до раніше розглянутої транспортної задачі із правильним балансом. Для цього, понад наявних n пункти призначення В1, B2, ... , Bn, уведемо ще один, фіктивний, пункт призначення Bn+1, якому припишемо фіктивну заявку, рівну надлишку запасів над заявками

bn+1 = аi - bj ( де i=1,...,m ; j=1,...,n ) ,

а вартість перевезень із всіх пунктів відправлення у фіктивний пункт призначення bn+1 будемо вважати рівної нулю. Введенням фіктивного пункту призначення B n+1 з його заявкою b n+1 ми зрівняли баланс транспортної задачі, і тепер її можна вирішувати, як звичайну транспортну задачу із правильним балансом.

Транспортна задача з надлишком заявок.

Цю задачу можна звести до звичайної транспортної задачі із правильним балансом, якщо ввести фіктивний пункт відправлення Am+1 із запасом am+1 рівним відсутньому запасу, і вартість перевезень із фіктивного пункту відправлення в усі пункти призначення прийняти рівної нулю.

Делись добром ;)