Транспортная задача по критерию времени

Задача по критерию времени возникает при перевозке срочных грузов. Как и в обычной транспортной задаче, имеется т поставщиков с запасами однородного груза в количестве а ₁, а ₂, …, а_т и п потребителей, которым этот груз должен быть доставлен в объеме b ₁, b ₂, ..., b_n. Известно t_ij, i = 1, 2,..., m, j = 1, 2,..., n — время, за которое груз доставляется от каждого i -го поставщика каждому j -му потребителю. Требуется составить такой план перевозок груза, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и наибольшее время доставки всех грузов является минимальным.

Составим математическую модель этой задачи. Обозначим х_ij — объем перевозимого груза от i -го поставщика j -му потребителю. Система ограничений задачи не отличается от системы ограничений обычной транспортной задачи. Пусть X = (x_ij), i = 1, 2,..., т, j = 1, 2,..., п — некоторое опорное решение задачи. Запишем целевую функцию задачи. Обозначим через Т (Х)наибольшее значение элементов матрицы Т= (t_ij), i = 1,2,..., m, j = 1, 2,..., п,соответствующих клеткам таблицы, занятым опорным решением: Т (Х)= . Таким образом, за время Т (Х)план перевозок будет выполнен полностью. Математическая модель имеет вид

Т (Х)= → min,

, i =1,2,..., т,

, j= 1, 2,..., п.

х_ij ≥ 0, i =1,2,..., т, j= 1, 2,..., п.

Задача решается в следующем порядке. Находится начальное опорное решение Х _1.Определяется значение целевой функции Т (Х ₁) = = . Все свободные клетки, которым соответствуют значения t_ij > Т (Х ₁),исключаются из рассмотрения (перечеркиваются). Занимать эти клетки нецелесообразно, так как повысится значение целевой функции. Чтобы понизить ее значение, необходимо освободить клетку (l₁, k ₁),в которой t_ij достигает максимума. Для этого строят так называемые разгрузочные циклы, которые могут включать в свой состав несколько свободных клеток. В каждом разгрузочном цикле, начиная с разгружаемой клетки (l₁, k ₁), расставляются поочередно знаки «—» и «+» и осуществляется сдвиг на величину θ= { х_ij }. Если удается эту клетку разгрузить, то она исключается из рассмотрения (зачеркивается). Получается новое опорное решение Х ₂, на котором значение целевой функции меньше, чем на Х ₁.Далее снова пытаются разгрузить клетку, соответствующую Т (Х ₂) = = = . Процесс продолжается до тех пор, пока возможность разгрузить соответствующую клетку не исчезнет.

Пример 18. Найти минимальное время на осуществление всех перевозок для задачи, исходные данные которой приведены в таблице:

bj ai
		6
	2
	15

Решение. Составим начальное опорное решение Х ₁по методу северо-западного угла (см. табл.). Базисные нули не записываем. Максимум целевой функции Т (Х ₁) = {10, 8, 5, 12, 4} = 12 достигается в клетке (3, 4). Перечеркнем клетку (4, 1), в которой время доставки груза t ₄₁= 15 больше Т (Х ₁) = 12.

Для улучшения решения разгрузим клетку (3, 4) с помощью цикла (3, 4), (2, 4), (2, 2), (3, 2). Означим цикл, найдем θ= {10, 30} = 10. Осуществив сдвиг по циклу, получим второе опорное решение Х ₂:

bj ai	20

Максимум целевой функции на этом опорном решении Т (Х ₂) = {10,8,4,5,4}=10 достигается в клетке (1, 1). Перечеркнем клетку (3, 4), так как время t ₃₄=12 больше, чем Т (Х ₂)=10. Разгрузим клетку (1, 1) с помощью цикла (1, 1), (1, 2), (2, 2), (2, 1). Означим цикл, найдем θ= {20,20}=20. Осуществив сдвиг по циклу, получим третье опорное решение Х ₃. Максимум целевой функции на этом опорном решении Т (Х ₃) = {6,5,4,4,5,4}=6 и достигается в клетке (1, 2). Перечеркнем клетки (1,1), (2,2), (2,3) и (4,3): в них время t ₁₁ = 10, t ₂₂ = 8, t ₂₃=7 и t ₄₃=9 больше, чем Т (Х ₃)=6. Разгрузим клетку (1, 2) с помощью цикла (1, 2), (1, 3), (3, 3), (3, 2). Означим цикл, найдем θ= {20, 20}=20.

bj ai

Осуществив сдвиг по циклу, получим четвёртое опорное решение Х ₄. Максимум целевой функции на этом опорном решении Т (Х ₄) = {5,4,4,5,4}=5 и достигается в клетках (2, 1) и (3, 3). Перечеркнем клетки (1, 2), и (4, 2), в которых время перевозок не менее t ₂₁ = 5. С помощью оставшихся невычеркнутых клеток разгрузить клетки (2,1) и (3, 3) не удаётся, поэтому Х ₄ является оптимальным решением.

bj ai

Ответ: min Т (X) = 5 при X* = .