Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

5.8. Транспортна задача за критерієм часу

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

Нехай задано m пунктів постачання А1, А2,…, Аm з відповідними запасами одиниць продукції та n споживачів , потреби яких становлять відповідно , причому .

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

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

Необхідно знайти оптимальний план перевезень , що задовольняє умови:

; (5.39)

. (5.40)

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

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

Отже, критерієм оптимальності плану є мінімальна тривалість здійснення всіх перевезень, що формально записують так:

. (5.41)

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

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

1. Знаходять мінімальний елемент матриці тривалостей перевезень Т. Позначимо мінімальний елемент, знайдений на першому кроці, через . Клітини транспортної таблиці, які відповідають мінімальному елементу, тобто де =, вважаються відкритими для перевезень, тоді як усі інші, де >, вважаються для них забороненими.

2. Розв’язують додаткову задачу з визначеною множиною заборонених для перевезень клітин . Якщо після цього кроку задовольняються умови задачі (5.39), (5.40), то оптимальний план знайдено і , а якщо ні, то переходять до третього кроку.

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

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

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

Нехай умови транспортної задачі задано таблицею (табл. 5.28):

Таблиця 5.28

1. Знаходимо мінімальний елемент з . В даному разі це 1, позначимо його через .

2. Розв’язуємо допоміжну задачу, де забороненими для перевезень є всі клітини, для яких > (у табл. 5.29 сірим кольором виділені заборонені клітини).

Таблиця 5.29

Задача розв’язана, проте план не оптимальний.

3. Знаходимо мінімальний елемент серед клітин, що є забороненими для перевезень. Наступний мінімальний елемент дорівнює двом. Отже, .

4. Приєднуємо до відкритих для перевезень клітин ті, для яких , і знову розв’язуємо допоміжну задачу.

Таблиця 5.30

Отриманий розв’язок (табл. 5.30) також не оптимальний.

5. Вибираємо наступний мінімальний елемент: .

6. Розв’язуємо наступну допоміжну задачу:

Таблиця 5.31

Це також не дає оптимального розв’язку (табл. 5.31).

7. Вибираємо мінімальний елемент .

8. Розв’язуємо задачу:

Таблиця 5.32

Умови оптимальності в табл. 5.32 виконуються, отже, цей план оптимальний. Звідси minТ = 4.