Транспортная задача. Лекция 5

1.

Липецкий государственный технический университет
Кафедра прикладной математики
Прикладная математика
Лекция 5
Транспортная задача
1

2.

Постановка транспортной задачи
Имеется m пунктов отправления некоторого груза и n пунктов
назначения этого груза.
Запас груза на пункте отправления Ai cоставляет aii единиц,
а заявка пункта назначения Bj – b j единиц, i 1, 2, ..., m, j 1, 2, ..., n.
Стоимость перевозки единицы груза из пункта отправления Ai в
пункт назначения Bj составляет cij единиц.
Требуется найти план перевозок, имеющий минимальную общую
стоимость.
Будем считать сначала, что сумма запасов равна сумме заявок
(закрытая задача): a1 ... am b1 ... bn .
2

3.

Постановка транспортной задачи
Обозначим xij – количество груза, перевозимого из пункта
отправления Ai в пункт назначения Bj. Тогда задача примет
следующий вид.
L c11x11 c12 x12 ... cmn xmn min
Ограничения на запасы:
x11 x12 ... x1n a1
...
x x ... x a
m1 m 2
mn
m
Ограничения на заявки:
x11 x21 ... xm1 b1
...
x x ... x b
1n
2n
mn
n
Условия неотрицательности: x11 0, x12 0, ..., xmn 0.
3

4.

Транспортная задача
Для решения транспортной задачи применяются специальные
методы, такие как метод потенциалов, венгерский метод и т.д.
Представим данные в виде таблицы.
B1
B2
A1
x11 c
A2
…
Bn
Всего
x12
c12
…
x1n
c1 n
a1
x21 c
x22
c22
…
x2 n
c2 n
a2
…
…
…
…
…
Am
xm1 c
xm 2
…
xmn
cmn
am
Всего
b1
b2
11
21
m1
cm 2
bn
4

5.

Транспортная задача
Так как большинство
xij 0,
они записываться в таблицу не
будут, а клетки в этом случае будут называться пустыми.
Решение задачи проводится в два этапа:
1) Нахождение опорного плана.
2) Нахождение оптимального плана.
Для первого этапа будем применять метод северо-западного угла,
а для второго этапа метод потенциалов.
В отличие от задачи линейного программирования транспортная
задача всегда имеет решение. Кроме того, если все запасы и заявки
являются целыми числами, то решение также будет целочисленным.
5

6.

Нахождение опорного плана
методом северо-западного угла
Алгоритм северо-западного угла
1) Если a1 b1 , то полагаем, что x11 b1 и делаем шаг вправо;
2) Если a1 b1 , то полагаем, что x11 a1 и делаем шаг вниз;
3) Если a1 b1 , то получается вырожденный случай;
4) Вычеркиваем из таблицы заполненную строку или столбец,
уменьшаем количество груза в незаполненном столбце или
строке, переходим к первому пункту.
Повторяем эту процедуру до тех пор, пока не будет найден
опорный план.
6

7.

Нахождение опорного плана
методом северо-западного угла
Подсчитаем число
непустых клеток
n 1 m 1 1 m n 1.
Невырожденный план
должен иметь ровно
m n 1
непустую
клетку.
Это требование не
является достаточным для
невырожденного плана.
7

8.

Метод потенциалов решения транспортной задачи
Для нахождения оптимального плана будем использовать метод
потенциалов, наиболее распространенный и быстрый среди всех
методов.
Алгоритм метода потенциалов для транспортной задачи впервые
был предложен в 1949 г. Л.В. Канторовичем и М.К. Гавуриным.
Позже
на
базе
общих
идей
линейного
программирования
аналогичный метод был предложен Дж. Данцигом.
8

9.

Метод потенциалов решения транспортной задачи
Леонид Витальевич Канторович (1912 1986) — советский математик и экономист,
лауреат Нобелевской премии по экономике
1975 года (совместно с Т. Купмансом) «за
вклад
в
теорию
распределения
оптимального
ресурсов».
Один
из
создателей линейного программирования.
Награждён 2
Трудового
орденами
Красного
Ленина
Знамени
(1967,
(1949,
1982),
1953,
3
орденами
1975),
орденом
Отечественной войны 1-й степени (1985), орденом «Знак Почёта»
(1944). Почётный доктор многих университетов мира.
9

10.

Нахождение оптимального плана методом потенциалов
~ и
Составим каждому пункту отправления Ai некоторое число a
i
каждому пункту назначения Bj некоторое число b~j , так чтобы для
~
любой непустой клетки a~ b c .
i
j
ij
~
Эти числа a~i и b j называются псевдоплатежами.
Для их нахождения получаем линейную систему из
уравнений на
m n
произвольно (обычно
m n 1
неизвестных. Одну неизвестную можно взять
a~1 0 ). Тогда остальные псевдоплатежи
находятся единственным образом по цепочке.
10

11.

Нахождение оптимального плана методом потенциалов
Далее находим псевдостоимости
~
c~ij a~i b j
для всех клеток.
Записываем их в левый угол каждой клетки.
B2
…
Bn
Всего
x11 c
…
…
…
a1
A2
…
…
…
…
a2
…
…
…
…
…
…
Am
…
…
…
…
am
Всего
b1
b2
…
bn
B1
A1
c~11
11
11

12.

Нахождение оптимального плана методом потенциалов
Если все
c~ij cij , то оптимальный план найден.
Любая клетка, в которой
c~ij cij
может быть взята в качестве
разрешающей.
Заполняя выбранную клетку, необходимо изменить объемы
поставок, записанных в ряде других занятых клеток и связанных с
заполняемой клеткой так называемым циклом.
12

13.

Нахождение оптимального плана методом потенциалов
Циклом пересчета называется замкнутая ломаная линия, все
стороны которой горизонтальны или вертикальны, одна вершина
находится в пустой клетке, а остальные – в непустых.
План называется невырожденным, если для любой пустой клетки
найдется единственный цикл пересчета.
Примеры некоторых циклов показаны на рисунке.
13

14.

Нахождение оптимального плана методом потенциалов
Находим цикл для разрешающей клетки. Далее расставляем
знаки: в разрешающую клетку ставим «+», а далее «–» и «+»
чередуются по обходу цикла. В любом цикле только четкое число
вершин, поэтому расстановка знаков не зависит от направления
обхода цикла.
Далее находим минимальное количество груза в клетках со
знаком «–». Если этот минимум достигается более чем в одной
клетке, получается вырожденный случай.
Если такого нет, то
делаем пересчет таблицы: в клетке с «+» добавляем этот минимум,
в клетке с «–» вычитаем его.
При этом пересчете количество непустых клеток и сумма строкам
и столбцам не меняется. После пересчета находим псевдоплатежи.
14

15.

Пример решения транспортной задачи (вариант 50)
B1
B2
B3
Всего
B4
A1
3
4
3
3
26
A2
3
5
3
4
25
A3
5
2
4
4
32
Всего
21
24
28
10
83
15

16.

Пример решения транспортной задачи (вариант 50)
B1
B2
B3
Всего
B4
3
4
3
3
26
A2
3
5
3
4
25
A3
5
2
4
4
32
A1
Всего
21
21
24
28
10
83
16

17.

Пример решения транспортной задачи (вариант 50)
B1
A1
21
B2
3
5
B3
Всего
B4
4
3
3
26
A2
3
5
3
4
25
A3
5
2
4
4
32
Всего
21
24
28
10
83
17

18.

Пример решения транспортной задачи (вариант 50)
B1
B2
B3
Всего
B4
3
5
4
3
3
26
A2
3
19
5
3
4
25
A3
5
2
4
4
32
A1
Всего
21
21
24
28
10
83
18

19.

Пример решения транспортной задачи (вариант 50)
B1
B2
B3
3
5
4
A2
3
19
5
A3
5
A1
Всего
21
21
6
2
24
28
Всего
B4
3
3
26
3
4
25
4
4
32
10
83
19

20.

Пример решения транспортной задачи (вариант 50)
B1
B2
B3
3
5
4
A2
3
19
5
A3
5
2
A1
Всего
21
21
24
Всего
B4
3
3
26
6
3
4
25
22
4
4
32
28
10
83
20

21.

Пример решения транспортной задачи (вариант 50)
B1
B2
B3
3
5
4
A2
3
19
5
A3
5
2
A1
Всего
21
21
24
Всего
B4
3
3
26
6
3
4
25
22
4
4
32
28
10
10
83
21

22.

Пример решения транспортной задачи (вариант 50)
B1
B2
B3
3
5
4
A2
3
19
5
A3
~
bj
5
A1
21
2
a~i
B4
3
3
6
3
4
22
4
10
0
4
22

23.

Пример решения транспортной задачи (вариант 50)
B1
A1
3
21
B2
3
A2
3
A3
~
bj
5
4
B3
5
4
19
5
2
a~i
B4
3
3
6
3
4
22
4
10
0
4
23

24.

Пример решения транспортной задачи (вариант 50)
B1
A1
3
21
B2
3
A2
3
A3
~
bj
5
3
4
B3
5
4
19
5
2
a~i
B4
3
3
6
3
4
22
4
10
0
4
4
24

25.

Пример решения транспортной задачи (вариант 50)
B1
B3
3
4
5
4
A2
3
5
19
5
A3
~
bj
5
A1
3
B2
21
3
2
a~i
B4
3
3
0
6
3
4
1
22
4
10
4
4
25

26.

Пример решения транспортной задачи (вариант 50)
B1
B3
3
4
5
4
A2
3
5
19
5
A3
~
bj
5
A1
3
B2
21
3
2
4
3
a~i
B4
3
3
0
6
3
4
1
22
4
10
4
2
26

27.

Пример решения транспортной задачи (вариант 50)
B1
B3
3
4
5
4
A2
3
5
19
5
3
A3
~
bj
5
2
4
A1
3
B2
21
3
4
a~i
B4
3
3
0
6
3
4
1
22
4
4
2
10
2
27

28.

Пример решения транспортной задачи (вариант 50)
B1
B3
3
4
5
4
A2
3
5
19
5
3
A3
~
bj
5
2
4
A1
3
B2
21
3
4
a~i
B4
3
3
0
6
3
4
1
22
4
4
2
2
4
10
2
28

29.

Пример решения транспортной задачи (вариант 50)
B1
A1
3
A2
A3
~
bj
B2
B3
3
4
5
4
2
4
3
5
19
5
3
5
5
6
2
4
21
3
4
a~i
B4
3
2
3
0
6
3
3
4
1
22
4
4
4
2
2
10
2
29

30.

Пример решения транспортной задачи (вариант 50)
B1
A1
3
A2
A3
~
bj
B2
B3
3
4
5
4
2
4
3
5
19
5
3
5
5
6
2
4
21
3
4
a~i
B4
3
2
3
0
6
3
3
4
1
22
4
4
4
2
2
10
2
(4-3) min (21,19)=19,
(6-2) min (19,22)= 76, выбираем 76.
30

31.

Пример решения транспортной задачи (вариант 50)
B1
A1
3
A2
A3
~
bj
B2
B3
3
4
5
4
2
4
3
5
19
5
3
5
5
6
2
4
21
3
4
a~i
B4
3
2
3
0
6
3
3
4
1
22
4
4
4
2
2
10
2
31

32.

Пример решения транспортной задачи (вариант 50)
B1
A1
21
B2
3
A2
3
A3
~
bj
5
5
B3
4
5
19
2
a~i
B4
3
3
25
3
4
3
4
10
0
4
32

33.

Пример решения транспортной задачи (вариант 50)
B1
A1
3
21
B2
3
A2
3
A3
~
bj
5
3
4
5
B3
4
5
19
2
a~i
B4
3
3
25
3
4
3
4
10
0
4
4
33

34.

Пример решения транспортной задачи (вариант 50)
B1
A1
3
21
B2
3
A2
3
A3
~
bj
5
3
4
5
B3
4
5
2
19
2
a~i
B4
3
3
25
3
4
3
4
10
4
0
2
4
34

35.

Пример решения транспортной задачи (вариант 50)
B1
A1
3
21
B2
3
A2
3
A3
~
bj
5
3
4
5
B3
4
5
2
19
4
2
4
a~i
B4
3
3
25
3
4
3
4
6
4
10
4
0
2
6
35

36.

Пример решения транспортной задачи (вариант 50)
B1
A1
3
A2
A3
~
bj
B2
3
4
0
3
1
1
5
2
21
3
5
B3
4
5
19
4
2
6
3
4
3
25
3
6
a~i
B4
3
4
6
3
0
3
4
3
4
2
4
10
6
36

37.

Пример решения транспортной задачи (вариант 50)
B1
A1
3
A2
A3
~
bj
B2
3
4
0
3
1
1
5
2
21
3
5
B3
4
5
19
4
2
6
3
4
3
25
3
6
a~i
B4
3
4
6
3
0
3
4
3
4
2
4
10
6
37

38.

Пример решения транспортной задачи (вариант 50)
B1
B2
B3
3
4
A2
3
5
A3
~
bj
5
A1
21
24
2
3
25
3
a~i
B4
5
4
3
4
3
5
4
38

39.

Пример решения транспортной задачи (вариант 50)
B1
A1
3
A2
A3
~
bj
B2
B3
3
1
4
3
3
3
1
5
3
4
5
2
21
3
24
1
2
4
25
3
3
a~i
B4
3
3
3
3
4
4
5
5
3
0
4
0
4
1
3
Оптимальный план найден.
Lmin 21 3 25 3 24 2 5 3 3 4 5 4 63 75 48 15 12 20 233.
Ответ: Lmin 233.
39

40.

Задания для самоконтроля
1. План является вырожденным, если:
1) количество базисных клеток в нем меньше, чем m n 1,
2) количество базисных клеток в нем меньше, чем m n 1,
3) количество базисных клеток в нем больше, чем
m n 1,
4) количество базисных клеток в нем больше, чем
m n 1.
40

41.

Задания для самоконтроля
2. Какое утверждение верно для цикла?
1) несколько клеток, соединенных линией так, чтобы четыре
вершины были расположены в одной строке.
2) несколько клеток, соединенных замкнутой линией так, чтобы
две вершины были расположены в одном столбце.
3) несколько клеток, соединенных замкнутой ломаной линией
так, чтобы две соседние вершины ломаной были расположены либо
в одной строке, либо в одном столбце.
4) несколько клеток, соединенных незамкнутой ломаной линией
так, чтобы две соседние вершины ломаной не были расположены в
одной строке или в одном столбце.
41

42.

Задания для самоконтроля
3. Укажите верную расстановку знаков в цикле пересчета.
1)
2)
3
17 3 5 10 5
6
2 4 24
3
17 3 5 10 5
6
2 4 24
3)
4)
3
17 3 5 10 5
6
2 4 24
3
17 3 5 10 5
6
2 4 24
42

43.

43