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

За деяких умов, наприклад, при перевезенні продукції, що швидко псується; матеріалів для аварійних та рятівних робіт то-що вартість перевезень має другорядне значення, а на перше міс-це виходить завдання мінімізації того часу, протягом якого здійснюються всі перевезення. Так виникає транспортна задача за критерієм часу. Нехай задано 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). Якщо вони задовольняються, то знайдений план оптимальний і . Якщо ж ні, то дії, аналогічні до описаних, повторюють, поки не буде знайдено оптимальний план. Алгоритм скінченний, оскільки за умови балансу таблиця перевезень без заборонених клітин завжди може бути заповнена, а алгоритм забезпечує в разі потреби звільнення всіх клітин від заборони на перевезення.