Транспортная задача (2)

1. Транспортная задача

Пример № 1
На трех базах находится однородный груз. На базе
А1 в количестве 300 т., на базе А2 в количестве 150 т.,
на базе А3 в количестве 50 т. Весь этот груз
необходимо развести четырем заказчикам так,
чтобы стоимость перевозок была наименьшей.
Заказчику в пункте В1 должно поступить 170 т., в
пункте В2 – 110 т., в пункте В3 – 100 т., в пункте
В4 – 120 т. Расстояния между базами и пунктами
назначения приведены в таблице 1 в угловых
скобках.

2. 1. Описание транспортной задачи

3.

Заказчики
Базы
В1
А1
А2
А3
Потребности
заказчика
170 т.
В2
Запасы на
В3
В4
базах
70
50
15
80
80
90
40
60
50
10
90
11
110 т.
100 т.
120 т.
300 т.
150 т.
50 т.
500 т.
500 т.

4. 2. Формирование опорного решения

5.

Заказчики
Базы
А1
А2
А3
Потребности
заказчика
В1
В2
Запасы на
В3
В4
базах
70
50
15
80
80
90
40
60
50
10
90
11
170
—
—
170 т.
110 т.
100 т.
120 т.
300 т.
150 т.
50 т.
500 т.
500 т.

6.

Заказчики
Базы
А1
А2
А3
Потребности
заказчика
В1
В2
70
170
—
В4
базах
50
15
80
90
40
60
10
90
11
—
50
170 т.
В3
110
80
—
Запасы на
—
110 т.
100 т.
120 т.
300 т.
150 т.
50 т.
500 т.
500 т.

7.

Заказчики
Базы
А1
А2
А3
Потребности
заказчика
В1
В2
70
170
50
80
170 т.
В4
15
базах
80
—
20
90
40
60
10
90
11
—
50
—
В3
110
—
Запасы на
—
110 т.
100 т.
120 т.
300 т.
150 т.
50 т.
500 т.
500 т.

8.

Заказчики
Базы
А1
А2
А3
Потребности
заказчика
В1
В2
70
170
50
80
170 т.
80
40
60
90
11
80
10
110 т.
базах
—
20
—
—
В4
15
90
50
—
В3
110
—
Запасы на
—
100 т.
120 т.
300 т.
150 т.
50 т.
500 т.
500 т.

9.

Заказчики
Базы
А1
А2
А3
Потребности
заказчика
В1
В2
70
170
50
80
170 т.
110 т.
80
40
80
10
60
70
90
—
100 т.
базах
—
20
—
—
В4
15
90
50
—
В3
110
—
Запасы на
11
50
120 т.
300 т.
150 т.
50 т.
500 т.
500 т.

10. Стоимость перевозок по опорному (первоначальному) плану составит: Fнач = 70·170 + 50·110 + 15·20 + 40·80 + 60·70 + 11·50 =

25650 (т.км.)

11. Решение транспортной задачи методом потенциалов

12. Пересчитывать опорный план можно с помощью потенциалов. Тариф сij базисных переменных представляется в виде суммы сij = αi -

Пересчитывать опорный план можно с
помощью потенциалов.
Тариф сij базисных переменных
представляется в виде суммы
сij = αi β j
αi - потенциалы баз,
βj – потенциалы заказчиков.

13. Тариф свободной клетки обозначают как cij и называют косвенным тарифом. Алгебраическая сумма тарифов свободной клетки

Тариф свободной клетки обозначают
как c ij и называют косвенным
тарифом.
Алгебраическая сумма тарифов
свободной клетки определяется
разностью истинного и косвенного
тарифов.
sij = cij – c‘ij

14.

Заказчики
Базы
А1
А2
А3
Потребности
заказчика
В1
В2
70
170
50
80
170 т.
110 т.
80
40
80
10
60
70
90
—
100 т.
базах
—
20
—
—
В4
15
90
50
—
В3
110
—
Запасы на
11
50
120 т.
300 т.
150 т.
50 т.
500 т.
500 т.

15.

16.

Значение одного из данных неизвестных
можно выбирать произвольно. Например,
можно принять, что α1 = 0.
Тогда решение системы примет вид:

17.

Значение одного из данных неизвестных
можно выбирать произвольно. Например,
можно принять, что α1 = 0.
Тогда решение системы примет вид:
α1 = 0,
α2 = 25,
α3 = – 24,
β1 = 70,
β2 = 50,
β3 = 15,
β4 = 35

18.

.
Посчитаем алгебраические суммы свободных
клеток
s14 = c14 – c'14= 80 – (0 + 35) = 45
s21 = c21 – c'21 = с21 – (α2 + β1) = 80 – (25 + 70) = 15,
s22 = c22 – c'22 = с22 – (α2 + β2) = 90 – (25 + 50) = 15,
s31 = c31 – c'31 = с31 – (α3 + β1) = 50 – (–24 + 70) = 4,
s32 = c32 – c'32 = с32 – (α3 + β2) = 10 – (–24 + 50) = 16,
s33 = c33 – c'33 = с33 – (α3 + β3) = 90 – (–24 + 15) = 99.

19.

Циклы пересчета строятся только для тех
свободных клеток, для которых алгебраические
суммы тарифов отрицательны.
80
20
170
(2;1) (2;3) (1;3) (1;1) (2;1),
80
100
90
50
70
80
20
110
(3;2) (3;4) (2;4) (2;3) (1;3) (1;2) (3;2)
70
60
50
120
30

20.

Новая стоимость перевозок находится по
формуле:
F
F
- m s
нов нач
ij
Т.е стоимость перевозок уменьшится на
число:
m s
ij

21.

m s
21
80 15 1 200
m s 32 50 16 800
Принимается наибольшее уменьшение
стоимости перевозок.
Строим таблицу, соответствующую
самому выгодному циклу:

22.

23.

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

24.

Fопт. = 70 ·140 + 50 · 60 + 15 · 100 + 80 · 30 + 60 ·120 + 10 · 50 =
24400 (т.км.),
что меньше стоимости перевозки по первоначальному
плану (Fнач.= 25650 т.км.) на 1250 т.км