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

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

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

Т(Х)= (26)

, i=1,2,…,m, (27)

, j=1, 2, …, n, (28)

, i=1,2,,…,m+1, j=1,2,…,n. (29)

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