Основы математического программирования (стр. 22 )

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

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

Как и в обычной транспортной задаче:

имеется m поставщиков с запасами однородного груза в количестве

a1, a2, …, am

и n потребителей с запросами

b1, b2, …, bn

Известно tij, i = 1, 2, …, m, j = 1, 2, …, n – время, за которое груз доставляется от каждого i-ого поставщика каждому j-ому потребителю.

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

Составим математическую модель.

Обозначим xij – объемы перевозимого груза от i-ого поставщика j-потребителю.

Система ограничений не отличается от системы ограничений обычной транспортной задачи.

Пусть X = (xij) – некоторое опорное решение.

Обозначим через Т(х) наибольшее значение элементов матрицы Т = (tij) соответствующих клеткам таблицы, занятых опорным решением:

Т(х) = max {tij}

xij>0

Математическая модель имеет вид:

Т(х) = max (tij) min

xij>0

n

∑ xij = ai, i = 1, 2, …, m

j =1

m

∑ xij = bj, j = 1, 2, …, m

i =1

xij > 0 i = 1, 2, …, m, j = 1, 2, …, m

Задача решается в следующем порядке:

1. Находится начальное опорное решение X1.

2. Определяется значение целевой функции

3. Находится значение целевой функции

T(X1) = max {tij} = tl1k1

xij>0

4. Все свободные клетки, которым соответствует значения tij ≥ T(X1), исключаются из рассмотрения (перечеркиваются). Занимать эти клетки нецелесообразно, т. к. повысится значение целевой функции.

5. Чтобы понизить значение целевой функции необходимо очистить клетку (l1, k1), в которой tij достигает максимума.

6. Построение разгрузочного цикла. В каждом разгрузочном цикле, начиная с разгружаемой клетки (l1, k1) расставляются поочередно знаки «-» и «+» и осуществляется сдвиг на величину. Циклы могут содержать несколько пустых клеток.

Q = min {xij}

«-»

7. Если удается эту клетку разгрузить, т. о. она исключается из рассмотрения (зачеркивается). Получаем новое опорное решение Х2.

8. Процесс продолжается до тех пор, пока возможность разгрузить соответствующую клетку не исчезнет.

Пример.

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

bj ai	20	30	40	60
20	10	6	3	2
30	5	8	7	4
50	2	4	5	12
50	15	5	9	4

Решение:

1. Составим начальное опорное решение по методу северо-западного угла. Базисные нули не записываем.

bj ai	20	30	40	60
20	20 10	6	3	2
30	5	30 8	7	4
50	2	4	40 5	10 12
50	15	5	9	50 4

2. Максимум целевой функции T(X1) = max {10, 8, 5, 12, 4} = 12

xij>0

достигается в клетке (3, 4).

Перечеркнем клетку (4, 1), в которой время доставки не меньше 12.

Построим цикл от ячейки (3,4)

bj ai	20	30	40	60
20	20 10	6	3	2
30	5	30 8	7	4
50	2	4	40 5	10 12
50	15	5	9	50 4

3. Найдем Qmin = {30, 10} = 10. Осуществляем сдвиг по циклу и получаем новое опорное решение

bj ai	20	30	40	60
20	20 10	6	3	2
30	5	20 8	7	10 4
50	2	10 4	40 5	12
50	15	5	9	50 4

4. Максимум целевой функции T(X2) = max {10, 8, 4, 5, 4} = 10