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

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

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

, (6.26)

, i = 1, 2, ..., m, (6.27)

, j = 1, 2, ..., n, (6.28)

, i = 1, 2, ..., m; j = 1, 2, ..., n. (6.29)

Задача решается в следующем порядке. Находится начальное допустимое решение . Определяется значение целевой функции . Все свободные клетки, которым соответствуют значения , исключаются из рассмотрения (перечеркиваются). Занимать эти клетки нецелесообразно, так как повысится значение целевой функции. Чтобы понизить ее значение, необходимо освободить клетку (l, k), для которой достигает максимума. Для этого строят так называемые разгрузочные циклы, которые могут включать в свой состав несколько свободных клеток. В каждом разгрузочном цикле, начиная с разгружаемой клетки (l, k), расставляются поочередно знаки "-" и "+" и производится сдвиг на величину . Если удается эту клетку разгрузить, то она исключается из рассмотрения (зачеркивается). Получается новое допустимое решение , на котором значение целевой функции меньше, чем на . Из рассмотрения исключаются клетки таблицы, в которых значение . Далее пытаются разгрузить клетку, соответствующую . Процесс продолжается до тех пор, пока возможность разгрузить соответствующую клетку исчезает.

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

Т а б л и ц а 6.24

Решение. Составим начальное опорное решение по методу северо-западного угла (табл. 6.24). Базисные нули не записываем. Максимум целевой функции достигается в клетке (3, 4). Перечеркнем клетку (4, 1), в которой время доставки груза больше .

Т а б л и ц а 6.25

Для улучшения решения разгрузим клетку (3, 4) с помощью цикла (3, 4), (2, 4), (2, 2), (3, 2) (см. табл. 6.24). Означим цикл, найдем . Осуществив сдвиг по циклу, получим второе опорное решение (табл. 6.25). Максимум целевой функции на этом опорном решении {10, 8, 4, 5, 4} = 10 достигается в клетке (1, 1). Перечеркнем клетку (3, 4), так как время больше, чем . Разгрузим клетку (1, 1) с помощью цикла (1, 1), (1, 2), (2, 2), (2, 1). Означим цикл, найдем {20, 20} = 20. Осуществив сдвиг по циклу, получим третье опорное решение (табл. 6.26).

Т а б л и ц а 6.26

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

Т а б л и ц а 6.27

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