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 не освобождается). Ответ: при оптимальном решении .

© 2011-2024 Контрольные работы по математике и другим предметам!