Исследование операций. Транспортная задача (лекция 7)

1.

Исследование операций
Лекция 7
Транспортная задача

2.

Транспортная задача: постановка
Имеется
n поставщиков
и m потребителей
однородной продукции
Известна стоимость перевозки единицы продукции между
каждым потребителем и поставщиком
Найти: план перевозок, при котором
• удовлетворены потребности всех потребителей,
• израсходованы запасы всех поставщиков,
• причем общая стоимость всех перевозок минимальна

3.

Транспортная задача: математическая модель
Условие транспортной задачи записывается в виде таблицы
М1
a1
Сk означает k-го поставщика (склад)
Мk - k-го потребителя (магазин)
cij – стоимость перевозки
от i-го поставщика
С1
b1
…
c11
…
c1m
…
…
…
c1n
…
cnm
к j-му потребителю
ak – потребность магазина в продукции
bk – запас продукции у поставщика
Сn
bn
Мm
am
…

4.

Транспортная задача: пример
Условие транспортной задачи
М1
125
С1
70
С2
95
С3
75
М2
80
М3
35
2
7
4
12
3
9
5
6
8
Это задача закрытого типа, суммарный спрос на продукцию равен
суммарному предложению
125+80+35=240=70+95+75

5.

Транспортная задача: опорный план
Опорный план транспортной задачи это такая совокупность
перевозок от поставщиков к потребителям, при которой
удовлетворены
потребности
всех
потребителей
и
израсходованы запасы всех поставщиков
М1
125
С1
70
С2
95
С3
75
М2
80
2
М3
35
7
4
3
9
70
12
55
5
40
8
6
40
35

6.

Опорный план:
метод северо-западного угла
Построение опорного плана транспортной задачи:
Выбираем клетку в левом верхнем углу таблицы, записываем в нее максимальную
возможную поставку 70 (больше продукции у С1 нет)
С1
70
С2
95
С3
75
М1
125, 55
2
70
12
М2
80
М3
35
7
4
3
9
5
6
8
«закрываем» первую строку (1-й поставщик израсходовал весь свой запас),
потребность первого потребителя уменьшаем на 70, остается поставить ему 55 единиц
продукции

7.

Опорный план:
метод северо-западного угла
Построение опорного плана транспортной задачи:
Выбираем клетку в левом верхнем углу оставшейся части таблицы, записываем в нее
максимальную возможную поставку 55 (больше продукции М1 не требуется)
С1
70
С2
95, 40
С3
75
М1
125, 55
2
70
12
55
5
М2
80
М3
35
7
4
3
9
6
8
«закрываем» первый столбец (1-й потребитель получил требуемое количество
продукции), запас второго поставщика уменьшаем на 55, остается 40 единиц
продукции

8.

Опорный план:
метод северо-западного угла
Построение опорного плана транспортной задачи:
Выбираем клетку в левом верхнем углу оставшейся части таблицы, записываем в нее
максимальную возможную поставку 40 (больше продукции у С2 нет)
С1
70
С2
95, 40
С3
75
М1
125, 55
2
70
12
55
5
М2
80, 40
7
М3
35
4
3
9
40
6
8
«закрываем» вторую строку (2-й поставщик израсходовал весь свой запас),
потребность второго потребителя уменьшаем на 40, остается поставить ему 40 единиц
продукции

9.

Опорный план:
метод северо-западного угла
Построение опорного плана транспортной задачи:
Выбираем клетку в левом верхнем углу оставшейся части таблицы, записываем в нее
максимальную возможную поставку 40 (больше продукции М2 не требуется)
С1
70
С2
95, 40
С3
75
М1
125, 55
2
70
12
55
5
М2
80, 40
7
М3
35
4
3
9
40
8
6
40
35
«закрываем» второй столбец (2-й потребитель получил требуемое количество
продукции), запас третьего поставщика уменьшаем на 40, остается 35 единиц
продукции, записываем 35 в оставшуюся клетку.

10.

Опорный план:
метод северо-западного угла
С1
70
С2
95, 40
С3
75
М1
125, 55
2
70
12
55
5
М2
80, 40
7
М3
35
4
3
9
40
8
6
40
35
Стоимость опорного плана транспортной задачи:
2 * 70 + 12 * 55 + 3 * 40 + 6 * 40 + 8 * 35 = 1440

11.

Опорный план:
метод минимальной стоимости
Построение опорного плана транспортной задачи:
Выбираем клетку таблицы с наименьшей стоимостью перевозки, записываем в нее
максимальную возможную поставку 70 (больше продукции у С1 нет)
С1
70
С2
95
С3
75
М1
125, 55
2
70
12
М2
80
М3
35
7
4
3
9
5
6
8
«закрываем» первую строку (1-й поставщик израсходовал весь свой запас),
потребность первого потребителя уменьшаем на 70, остается поставить ему 55 единиц
продукции

12.

Опорный план:
метод минимальной стоимости
Построение опорного плана транспортной задачи:
Выбираем клетку в оставшейся части таблицы с наименьшей стоимостью перевозки 3,
записываем в нее максимальную возможную поставку 80 (больше продукции М2 не
требуется)
М1
М2
М3
С1
70
С2
95, 15
С3
75
125, 55
2
70
12
80
35
7
4
3
9
80
5
6
8
«закрываем» второй столбец (2-й потребитель получил требуемое количество
продукции), запас второго поставщика уменьшаем на 80, остается 15 единиц
продукции.

13.

Опорный план:
метод минимальной стоимости
Построение опорного плана транспортной задачи:
Выбираем клетку в оставшейся части таблицы с наименьшей стоимостью перевозки 5,
записываем в нее максимальную возможную поставку 55 (больше продукции М1 не
требуется)
М1
М2
М3
С1
70
С2
95, 15
С3
75, 20
125, 55
2
70
12
80
35
7
4
3
9
80
5
6
8
55
«закрываем» первый столбец (1-й потребитель получил требуемое количество
продукции), запас третьего поставщика уменьшаем на 55, остается 20 единиц
продукции.

14.

Опорный план:
метод минимальной стоимости
Построение опорного плана транспортной задачи:
Выбираем клетку в оставшейся части таблицы с наименьшей стоимостью перевозки 8,
записываем в нее максимальную возможную поставку 20 (больше продукции у С3 нет)
С1
70
С2
95, 15
С3
75, 20
М1
125, 55
2
70
12
М2
80
М3
35
7
4
3
9
80
5
6
55
15
8
20
«закрываем» третью строку (3-й поставщик израсходовал весь свой запас),
потребность третьего потребителя уменьшаем на 20, остается поставить ему 15 единиц
продукции, берем ее у оставшегося 2-го поставщика и получаем опорный план.

15.

Опорный план:
метод минимальной стоимости
С1
70
С2
95, 15
С3
75, 20
М1
125, 55
2
70
12
М2
80
М3
35
7
4
3
9
80
5
6
55
Стоимость опорного плана:
2 * 70 + 5 * 55 + 3 * 80 + 9 * 15 + 8 * 20 = 950
15
8
20

16.

Опорный план:
стоимость перевозки
С1
70
С2
95, 40
С3
75
М1
125, 55
2
70
12
55
5
М2
80, 40
7
М3
35
4
3
9
40
8
6
40
Метод северо-западного угла:
F=70*2+55*12+40*3+40*6+35*8
F=140+660+120+240+280
F=1440
35
С1
70
С2
95, 15
С3
75, 20
М1
125, 55
2
70
12
М2
80
М3
35
7
4
3
9
80
5
6
55
15
8
20
Метод минимальной стоимости:
F=70*2+80*3+15*9+55*5+20*8
F=140+240+135+275+160
F=950
Не всегда метод минимальной стоимости дает
более дешевый опорный план

17.

Опорный план: нулевая поставка
М1
100
С1
70
С2
30
С3
100
М2
60
2
М3
40
7
4
3
10
9
5
6
8
70
Это задача закрытого типа, суммарный спрос на продукцию равен
суммарному предложению 100+60+40=200=70+30+100
Направляем в левую верхнюю клетку 70 единиц продукции, закрываем
первую строку

18.

Опорный план: нулевая поставка
М1
М2
М3
100, 30,0
60
40
2
4
7
С1
70
70
3
10
9
С2
30
30
5
8
6
С3
100
0
Направляем в клетку со стоимостью 3 поставку 30 единиц продукции, можем
закрыть вторую строку или первый столбец, но не одновременно!
Закроем вторую строку. Первому потребителю теперь нужно 0 единиц
продукции, именно столько и поставим в клетку стоимости 5 и закроем
первый столбец.

19.

Опорный план: нулевая поставка
С1
70
С2
30
С3
100
М1
100, 30,0
2
70
3
30
5
0
М2
60
М3
40
7
4
10
9
6
8
60
ВАЖНО: число
заполненных клеток
на 1 меньше общего
числа потребителей
и поставщиков
40
Направляем в оставшиеся 2 клетки
соответственно 60 и 40 единиц продукции,
Получаем опорный план.

20.

Транспортная задача: открытый тип
М1
100
С1
70
С2
95
С3
75
М2
80
М3
35
2
7
4
12
3
9
5
6
8
Суммарный запас
поставщиков не равен
суммарному спросу
потребителей
70+95+75=240
100+80+35=215
Поскольку у поставщиков продукции больше,
чем нужно потребителям,
вводим фиктивного потребителя
со стоимостью перевозки 0
и спросом 240-215=25

21.

Транспортная задача: открытый тип
М1
100
2
С1
70
С2 12
95
С3 5
75
М2
80
М3
35
7
4
МФ
25
0
3
9
0
6
8
0
Если у поставщиков продукции
больше,
чем нужно потребителям,
вводим фиктивного потребителя
со стоимостью перевозки 0
и спросом,
равным
разности
суммарного
спроса и общего запаса продукции
Теперь задача стала закрытой: суммарный
запас поставщиков равен суммарному
спросу потребителей
70+95+75=240
100+80+35+25=240

22.

Транспортная задача: открытый тип
М1
100
2
С1
70
С2 12
45
С3 5
75
СФ 0
25
М2
80
М3
35
7
4
3
9
6
8
0
0
Если у поставщиков продукции
меньше, чем нужно потребителям,
вводим фиктивного поставщика
со стоимостью перевозки 0 и запасом,
равным разности суммарного спроса
и общего запаса продукции
Суммарный запас поставщиков был меньше
суммарного спроса потребителей 70+45+75=190
100+80+35=215
Ввели фиктивного поставщика с запасом 215-190=25.
Теперь задача стала закрытой: суммарный запас
поставщиков равен суммарному спросу
потребителей
70+45+75+25=215
100+80+35=215

23.

Оптимизация опорного плана: метод потенциалов
Оптимизация опорного плана транспортной задачи:
Находим потенциалы строк и столбцов таблицы u1, u2, u3, v1, v2, v3.
В заполненных клетках сумма потенциалов должна быть равна стоимости
перевозки. Получаем СЛАУ из 5 уравнений с 6 переменными, для транспортной
задачи такая СЛАУ всегда
М1 u1
М2 u2
М3 u3
совместная и
125
80
35
недоопределенная.
2
4
7
С1 v1
Все переменные можно
70
70
выразить через какую-то
12
3
9
С2 v2
95
80
15
из них. Обычно полагают
5
8
6
С3 v3
u1=0 или v1=0.
75
55
20
Будем полагать u1=0.

24.

Метод потенциалов:
потенциалы строк и столбцов
Находим потенциалы строк и столбцов таблицы u1, u2, u3, v1, v2, v3 из системы