Опорний конспект лекцій з курсу Дослідження операцій Тема 9 Транспортні задачі лінійного програмування, НУДПСУ

Лекція №9. ТРАНСПОРТНІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ. Критерій оптимальності базисного розв'язку транспортної задачі. Методи відшукання оптимального розв'язку

План

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

2. Основний спосіб відшукання оптимального розв'язку транспортної задачі.

3. Методи підрахунку сум алгебри тарифів.

4. Розподільний метод.

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

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

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

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

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

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

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

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

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

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

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

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

Контрольні запитання

1. Який основний критерій оптимальності базисного розв'язку транспортної задачі?

2. Способи відшукання оптимального розв'язку транспортної задачі.

3. Які є методи підрахунку сум алгебри тарифів?

4. Що таке розподільний метод?

5. Що таке метод потенціалів?

З повагою ІЦ “KURSOVIKS”!