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

Задача по критерию минимума времени возникает при перевозке срочных грузов.

Пусть даны поставщиков и потребителей, - время перевозки от -го поставщика к -ому потребителю.

Запасы должны быть вывезены полностью, потребности полностью удовлетворены, - объём перевозки из пункта отправления в пункт назначения. Опорное решение X0 строим по любому методу, например, северо-западного угла или минимального элемента. Целевая функция - наибольшее значение элементов матрицы из занятых клеток опорного плана.

Все свободные клетки, которым соответствуют значения > исключаются (перечеркиваются). Чтобы понизить значение функции надо освободить клетку, в которой достигает максимума. Для этого строим разгрузочные циклы (которые содержат несколько свободных клеток). Циклы могут поворачивать и в свободных и в занятых клетках, могут проскакивать перечеркнутые клетки.

Цикл начинают в занятой клетке (разгружаемой), чтобы освободить её, тем самым уменьшить . Двигаемся паралельно строчкам или столбцам, расставляем поочередно «-», «+», «-», «+», начиная с разгружаемой клетки. Перераспределяемый груз выбирается из клеток с «-». Если эту клетку (или эти клетки) удаётся разгрузить, её (их) исключают (вычеркивают). Получаем новый план X1, на котором значение целевой функции меньше и определяем (элементы - из занятых клеток нового плана X1). Вычеркиваем свободные клетки с >. Далее снова пытаемся разгрузить занятую клетку с = построив новый цикл и т. д. до тех пор, пока такие разгрузочные циклы удаётся построить.

Пример. Найти минимальное время всех перевозок.

1 шаг: получаем опорный план методом северо-западного угла (см. таблицу 1)

20 40 50 70 30 13 20 - 8 10 + 7 11 40 6 + 7 30 - 9 10 8 50 5 12 5 40 10 10 60 19 6 14 6 60

Таблица 1

Находим по занятым клеткам таблицы максимум целевой функции . Вычеркиваем все свободные клетки с >13, т. е. клетки (4, 1), (4, 3) (см. таблицу 1).

2 шаг: стоим цикл, начиная с занятой клетки с наибольшим =13, т. е. с клетки (1; 1); определяем (выбираем по клеткам цикла с «-»). Перераспределяем груз в вершинах цикла; в клетках с «+» добавляем 20 единиц, в клетках с «-» вычитаем 20 единиц.

Новый план (новое опорное решение) .

Определяем , вычеркиваем свободные клетки с >10 (т. е. клетки (1;1), (1;4), (3;2)). Переходим к следующему 3 шагу.

	20	40	50	70
30	13	8 30	7	11
40	6 20	7 10	9 10 -	8 +
50	5	12	5 40 +	10 - 10
60	19	6	14	4 60

Таблица 2

3 шаг: Строим разгрузочный цикл, начиная с занятой клетки (3;4) с , в клетке (3;4) ставим «-», далее чередуем по циклу «+», «-», «+». Определяем и перераспределяем груз по циклу. Получим следующий план . Вычеркиваем свободные клетки с >8 в таблице 2, так как . Получаем таблицу 3.

	20	40	50	70
30	13	8 30	7	11
40	6 20	7 10	9	8 10
50	5	12	5 50	10
60	19	6	14	4

Таблица 3

Больше циклов, освобождающих клетки с = 8 построить не удаётся (клетка с = 8 не освобождается). Ответ: при оптимальном решении .

< Предыдущая		Следующая >