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

Наиболее часто критерием оптимальности перевозок оказывается их суммарная стоимость f. Однако возникают ситуации, когда в качестве критерия оптимальности необходимо использовать время Т, в течение которого все перевозки будут закончены.

В транспортной задаче по критерию времени наилучшим планом перевозок {Х_ij} называется план, продолжительность перевозок Т которого минимальна: Т —> min.

Сформулируем транспортную задачу по критерию времени. Допустим, заданы М пунктов отправления А₁ , А₂ ,..., А_м., в которых сосредоточены запасы груза в количествах а₁, а₂..., а_м, N пу, 2,..., M, j = 1, 2,..., N). Необходимо за минимальное время Т (Т—> min) организовать нктов назначения В₁, В₂,..., В_N, подавших заявки на груз в количествах b₁, b₂..., b_N, и время транспортировки груза t_ij из пункта A_i, в пункт Bj (Ai, —> Bj; t_ij, i =1 перевозки груза {х_ij} из Ai, в Bj так, чтобы из каждого пункта отправления Ai; весь запас груза a_i, был вывезен:

(2.1)

и в каждый пункт назначения Bj весь груз в соответствии с заявкой bj, был завезен:

(2.2)

Выразим продолжительность перевозок Т через время t_ij конкретных перевозок Хij. План перевозок считается выполненным в тот момент, когда заканчивается самая длительная из всех перевозок, т. е. продолжительность плана перевозок Т определяется максимальной длительностью t_ij ненулевых перевозок:

(2.3)

Следовательно, необходимо найти план перевозок {Хij}, удовлетворяющий условию

(2.4)

Транспортная задача по критерию времени не является задачей линейного программирования, так как целевая функция Т не является линейной функцией переменных х_ij.

Без ограничения общности можно считать, что рассматриваемая транспортная задача сбалансирована т.к. . Если это не так, то транспортную задачу всегда можно сбалансировать, пропорционально уменьшая избыточные запасы а_i; (заявки b_j) или вводя фиктивный пункт отправления а_ф, (назначения В_Ф) с запасами (заявками ) для недостающих заявок (запасов) и считая, что эти дополнительные перевозки происходят в течение очень большого промежутка времени t_ij.

Решение транспортной задачи по критерию времени может быть получено методом запрещенных клеток. Фактически этот метод состоит из двух этапов:

• на первом, находится начальный допустимый план;

• на втором, найденный план последовательно ускоряется.

Пример: Решить транспортныю задачу, минимизируя время перевозки.

Таблица 2.1

пост. Ai	45	25	20	25	35	25
потр.Вj
25	13	8	14	12	11	7
40	8	12	9	8	14	9
15	11	9	18	14	7	6
50	7	10	7	6	9	15
45	13	11	16	17	10	7

Первый опорный план строим методом наименьшего элемента. Находим клетку с наименьшем временем перевозки 6 (2.3) и помещаем туда наибольшую возможную перевозку (15 ед.). Далее переходим к клеткам со значением времени 7, и так далее до полного распределения перевозок.(таблица 2.2)

Перевозка продолжается 11ч, клетка 5.2. Необходимо закончить перевозки в возможно короткие сроки. Найдя все клетки с перевозкой менее 11: Х12, Х16, Х21, Х36, Х41, Х43, Х44, Х52, Х55 (таблица 3), строим контур пересчёта ходом ладьи, по которому можно перенести корреспонденцию из клетки с большим временем в клетку с меньшим временем перевозки. Строим контур 5.2 – 5.6. – 1.6 – 1.2 и переносим 10 единиц из клетки 5.2. в клетки с меньшей стоимостью перевозок. (таблица 2.3).

Таблица 2.2

пост. Ai	45	25	20	25	35	25
заяв. Bj
25	13	8 15	14	12	11	7 10
40	8 40	12	9	8	14	9
15	11	9	18	14	7	6 15
50	7 5	10	7 20	6 25	9	15
45	13	1 1 10	16	17	10 35	7

Таблица3

пост. Ai	45	25	20	25	35	25
заяв. Bj
25	13	8 25	14	12	11	7
40	8 40	12	9	8	14	9
15	11	9	18	14	7	6 15
50	7 5	10	7 20	6 25	9	15
45	13	11	16	17	10 35	7 10

После переноса время самой длинной перевозки уменьшилось с 11ч до 10ч. Для дальнейшего решения необходимо перенести перевозку из клетки 5.5., но контур пересчёта построить не удастся. Максимальное время перевозки соответствует 10ч.