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

Сентябрь 11, 2022

Главная
Экономика
Транспортная задача

Содержание

2. Постановка задачи Имеется m поставщиков A1 , A2, …, Am и n потребителей B1 , B2,
3. Пусть X = (xij) – m×n матрица, где xij – объем перевозок от i-го поставщика к
4. Математическая постановка транспортной задачи определяется задачей линейного программирования: при условиях
5. Решение X = (xij) транспортной задачи, удовлетворяющее условиям и имеющее не более m+n–1 занятой клетки ,
6. Задача 1 Решите транспортную задачу методом потенциалов. В ответе укажите минимальную стоимость всех перевозок. 400 400
7. 1. Метод «северо-западного угла» 80 40 20 130 30 100 Начальный опорный план: z(X) = 1·80
8. 2. Метод наименьшей стоимости 80 130 60 30 10 90 Начальный опорный план: z(X) = 1·80
9. Теорема Если опорный план X = (xij) транспортной задачи является оптимальным, то существуют потенциалы поставщиков ui,
10. Метод потенциалов - 17 - 21 - 1 5 9 - 3
11. Цикл 80 60 90 + + - - + + - - 80 140 10 Δ
12. Новый опорный план - 9 - 17 - 21 - 10 5 - 3 z(X) =
13. Цикл 30 10 10 + + - - + + - - 20 10 20 Δ
14. Новый опорный план - 4 - 12 - 16 - 10 - 5 - 3 z(X)
15. Модель транспортной задачи называется открытой, если (суммарные запасы не равны суммарным потребностям). Открытая модель транспортной задачи
16. Открытая модель транспортной задачи Открытую модель можно свести к закрытой: 1. Если , то вводят фиктивного
17. Задача 2 Решите транспортную задачу методом потенциалов. В ответе укажите минимальную стоимость всех перевозок. 400 370
18. Метод «северо-западного угла» z(X) = 3·90 + 7·10 + 13·70 + 24·30 + 18·170 = 5030
19. Метод потенциалов 14 17 6 - 1 23 12 - 11 - 18
20. Цикл 30 0 170 + + - - + + - - 30 30 140 Δ
21. - 9 - 6 - 17 - 1 - 23 - 11 12 5 Новый опорный
22. Цикл 90 10 30 + + - - Δ = min (90, 70, 140) = 70
23. 3 6 - 5 - 13 - 12 - 23 - 11 - 7 Новый опорный
24. Цикл 20 70 70 + + - - + + - - 90 20 50 Δ
25. Новый опорный план - 6 - 3 - 11 - 13 - 6 - 23 -
26. Задача 3 Решите транспортную задачу методом потенциалов. В ответе укажите минимальную стоимость всех перевозок. 260 300
27. Метод наименьшей стоимости z(X) = 1·60 + 2·40 + 16·25+ 4·75 + 4·50 + 6·10 =
28. Метод потенциалов 2 - 9 2 - 23 - 25 - 22 - 4 10 -
29. Цикл 25 10 40 + + - - + + - - 25 35 15 Δ
30. Новый опорный план - 8 - 9 2 - 10 - 13 - 15 - 12
31. Цикл 60 40 35 + + - - + + - - 75 35 25 Δ
32. Новый опорный план - 10 - 9 - 12 - 2 - 11 - 13 -
33. Транспортные задачи с дополнительными ограничениями В некоторых транспортных задачах наложены дополнительные ограничения на перевозку грузов. 1.
34. 2. Если дополнительным условием в задаче является обеспечение перевозки от поставщика Ai к потребителю Bj в
35. 4. Если от поставщика Ai к потребителю Bj требуется перевезти не более aij единиц груза, то
37. Скачать презентацию

Слайд 2

Постановка задачи
Имеется m поставщиков A1 , A2, …, Am и n

потребителей B1 , B2, …, Bn некоторого груза.
Для каждого поставщика и потребителя заданы запасы ai ≥ 0, i = 1, 2, …, m и объем потребления bj ≥ 0, j = 1, 2, …, n.
Известна стоимость перевозки единицы груза сij ≥ 0 от i-го поставщика к j-му потребителю.
Требуется найти объемы всех перевозок xij от i-го поставщика к j-му потребителю, при которых общая стоимость минимальна.

Слайд 3

Пусть X = (xij) – m×n матрица, где
xij – объем

перевозок от i-го поставщика к j-му потребителю.
Общие затраты на перевозку груза определяются функцией:

Математическая постановка задачи

Слайд 4

Математическая постановка транспортной задачи определяется задачей линейного программирования:
при условиях

Слайд 5

Решение X = (xij) транспортной задачи, удовлетворяющее условиям и имеющее не

более m+n–1 занятой клетки , будем называть опорным планом транспортной задачи.
Закрытая модель: суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.
Открытая модель:

Слайд 6

Задача 1
Решите транспортную задачу методом потенциалов. В ответе укажите минимальную

стоимость всех перевозок.

400

Слайд 7

1. Метод «северо-западного угла»
80
40
20
130
30
100
Начальный опорный план:
z(X) = 1·80 + 11·40 +

3·20 + 8·130 + 2·30 + 6·100 = 2280

Слайд 8

2. Метод наименьшей стоимости
80
130
60
30
10
90
Начальный опорный план:
z(X) = 1·80 + 4·30 +

5·10 + 14·90 + 3·60 + 2·130 = 1950 < 2280

Слайд 9

Теорема
Если опорный план X = (xij) транспортной задачи является оптимальным,

то существуют потенциалы поставщиков ui,
i = 1,…, m и потребителей vj, j = 1,…, n, удовлетворяющие условиям:
ui + vj = сij при xij > 0 (для занятых клеток),
Δij = ui + vj - сij ≤ 0 при xij = 0 (для свободных клеток).

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

Слайд 10

Метод потенциалов
- 17
- 21
- 1
5
9
- 3

Слайд 11

Цикл
80
60
90
+
+
-
-
+
+
-
-
80
140
10
Δ = min (80, 90) = 80

Слайд 12

Новый опорный план
- 9
- 17
- 21
- 10
5
- 3
z(X) = 3·80 +

5·10 + 4·30 + 14·10 + 3·140 + 2·130 = 1230 < 1950

Слайд 13

Цикл
30
10
10
+
+
-
-
+
+
-
-
20
10
20
Δ = min (10, 30) = 10

Слайд 14

Новый опорный план
- 4
- 12
- 16
- 10
- 5
- 3
z(X) = 3·80

+ 5·20 + 4·20 + 8·10 + 3·140 + 2·130 = 1180 < 1230

План оптимален!

Слайд 15

Модель транспортной задачи называется открытой, если (суммарные запасы не равны суммарным

потребностям).

Открытая модель транспортной задачи

Слайд 16

Открытая модель транспортной задачи
Открытую модель можно свести к закрытой:
1. Если ,

то вводят фиктивного потребителя Вn+1 с потребностью и нулевыми тарифами перевозок в столбце.
2. Если ,то вводят фиктивного поставщика А m+1 с запасом и нулевыми тарифами перевозок в строке.

Слайд 17

Задача 2
Решите транспортную задачу методом потенциалов. В ответе укажите минимальную

стоимость всех перевозок.

400

370

Слайд 18

Метод «северо-западного угла»
z(X) = 3·90 + 7·10 + 13·70 +

24·30 + 18·170 = 5030

Слайд 19

Метод потенциалов
14
17
6
- 1
23
12
- 11
- 18

Слайд 20

Цикл
30
0
170
+
+
-
-
+
+
-
-
30
30
140
Δ = min (30, 170) = 30

Слайд 21

- 9
- 6
- 17
- 1
- 23
- 11
12
5
Новый опорный план
z(X) = 3·90

+ 7·10 + 13·70 + 7·30 + 18·140 + 12·30 = 4130 < 5030

Слайд 22

Цикл
90
10
30
+
+
-
-
Δ = min (90, 70, 140) = 70
-
+
70
140
+
+
+
-
-
-
70
80
100
20
70

Слайд 23

3
6
- 5
- 13
- 12
- 23
- 11
- 7
Новый опорный план
z(X) = 3·20

+ 7·80 + 8·70 + 12·30 + 18·70 + 7·100 = 3500 < 4130

Слайд 24

Цикл
20
70
70
+
+
-
-
+
+
-
-
90
20
50
Δ = min (20, 70) = 20

Слайд 25

Новый опорный план
- 6
- 3
- 11
- 13
- 6
- 23
- 11
- 1
z(X)

= 8·90 + 7·80 + 12·30 + 7·100 + 7·20 + 18·50 = 3380 < 3500

Оптимальный план:

План оптимален!

Слайд 26

Задача 3
Решите транспортную задачу методом потенциалов. В ответе укажите минимальную

стоимость всех перевозок.

260

300

Слайд 27

Метод наименьшей стоимости
z(X) = 1·60 + 2·40 + 16·25+ 4·75 +

4·50 + 6·10 = 1100

Слайд 28

Метод потенциалов
2
- 9
2
- 23
- 25
- 22
- 4
10
- 2

Слайд 29

Цикл
25
10
40
+
+
-
-
+
+
-
-
25
35
15
Δ = min (25, 40) = 25

Слайд 30

Новый опорный план
- 8
- 9
2
- 10
- 13
- 15
- 12
- 4
- 2
z(X)

= 1·60 + 2·40 + 4·75 + 4·50 + 6·35 = 850 < 1100

Слайд 31

Цикл
60
40
35
+
+
-
-
+
+
-
-
75
35
25
Δ = min (35, 60) = 35

Слайд 32

Новый опорный план
- 10
- 9
- 12
- 2
- 11
- 13
- 12
- 2
0
План

оптимален!

Оптимальный план:

z(X) = 1·25 + 2·75 + 4·75 + 4·50 + 3·35 = 780 < 850

Слайд 33

Транспортные задачи с дополнительными ограничениями
В некоторых транспортных задачах наложены дополнительные ограничения

на перевозку грузов.
1. Если в закрытой задаче перевозки от поставщика Ai к потребителю Bj не могут быть осуществлены (стоит блокировка), для определения оптимального решения задач предполагают, что тариф перевозки единицы груза равен сколь угодно большому числу М.

Слайд 34

2. Если дополнительным условием в задаче является обеспечение перевозки от поставщика

Ai к потребителю Bj в точности aij единиц груза, в клетку AiBj записывают указанное число aij, а эту клетку считают свободной со сколь угодно большим тарифом М.
3. Если от поставщика Ai к потребителю Bj должно быть перевезено не менее aij единиц груза, то запасы пункта Ai и потребности Bj полагают меньше фактических на aij единиц. После нахождения оптимального плана перевозку в клетке AiBj увеличивают на aij единиц.

Слайд 35

4. Если от поставщика Ai к потребителю Bj требуется перевезти не

более aij единиц груза, то вводят дополнительного потребителя Bn+1 = Bij, которому записывают те же тарифы, что и для Bj, за исключением тарифа в i–й строке, который считают равным сколь угодно большому числу М.
Потребности пункта Bj считают равными
aij, а потребности Bij полагают равными
bj - aij.

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

Содержание

Постановка задачиИмеется m поставщиков A1 , A2, …, Am и n

Пусть X = (xij) – m×n матрица, где xij – объем

Математическая постановка транспортной задачи определяется задачей линейного программирования:при условиях

Решение X = (xij) транспортной задачи, удовлетворяющее условиям и имеющее не

Задача 1 Решите транспортную задачу методом потенциалов. В ответе укажите минимальную

1. Метод «северо-западного угла»80402013030100Начальный опорный план:z(X) = 1·80 + 11·40 +

2. Метод наименьшей стоимости8013060301090Начальный опорный план:z(X) = 1·80 + 4·30 +

Теорема Если опорный план X = (xij) транспортной задачи является оптимальным,

Метод потенциалов- 17- 21- 1 5 9- 3

Цикл806090++--++--8014010Δ = min (80, 90) = 80

Новый опорный план- 9- 17- 21- 105- 3z(X) = 3·80 +

Цикл301010++--++--201020Δ = min (10, 30) = 10

Новый опорный план- 4- 12- 16- 10- 5- 3z(X) = 3·80

Модель транспортной задачи называется открытой, если (суммарные запасы не равны суммарным

Открытая модель транспортной задачиОткрытую модель можно свести к закрытой:1. Если ,

Задача 2 Решите транспортную задачу методом потенциалов. В ответе укажите минимальную

Метод «северо-западного угла»z(X) = 3·90 + 7·10 + 13·70 +

Метод потенциалов14176- 12312- 11- 18

Цикл300170++--++--3030140Δ = min (30, 170) = 30

- 9- 6- 17- 1- 23- 11125Новый опорный планz(X) = 3·90

Цикл901030++--Δ = min (90, 70, 140) = 70-+70140+++---70801002070

36- 5- 13- 12- 23- 11- 7Новый опорный планz(X) = 3·20

Цикл207070++--++--902050Δ = min (20, 70) = 20

Новый опорный план- 6- 3- 11- 13- 6- 23- 11- 1z(X)

Задача 3 Решите транспортную задачу методом потенциалов. В ответе укажите минимальную

Метод наименьшей стоимостиz(X) = 1·60 + 2·40 + 16·25+ 4·75 +

Метод потенциалов2- 92- 23- 25- 22- 410- 2

Цикл251040++--++--253515Δ = min (25, 40) = 25

Новый опорный план- 8- 92- 10- 13- 15- 12- 4- 2z(X)

Цикл604035++--++--753525Δ = min (35, 60) = 35

Новый опорный план- 10- 9- 12- 2- 11- 13- 12- 20План

Транспортные задачи с дополнительными ограничениямиВ некоторых транспортных задачах наложены дополнительные ограничения

2. Если дополнительным условием в задаче является обеспечение перевозки от поставщика

4. Если от поставщика Ai к потребителю Bj требуется перевезти не

Похожие презентации

Постановка задачи
Имеется m поставщиков A1 , A2, …, Am и n

Пусть X = (xij) – m×n матрица, где
xij – объем

Математическая постановка транспортной задачи определяется задачей линейного программирования:
при условиях

Задача 1
Решите транспортную задачу методом потенциалов. В ответе укажите минимальную

1. Метод «северо-западного угла»
80
40
20
130
30
100
Начальный опорный план:
z(X) = 1·80 + 11·40 +

2. Метод наименьшей стоимости
80
130
60
30
10
90
Начальный опорный план:
z(X) = 1·80 + 4·30 +

Теорема
Если опорный план X = (xij) транспортной задачи является оптимальным,

Метод потенциалов
- 17
- 21
- 1
5
9
- 3

Цикл
80
60
90
+
+
-
-
+
+
-
-
80
140
10
Δ = min (80, 90) = 80

Новый опорный план
- 9
- 17
- 21
- 10
5
- 3
z(X) = 3·80 +

Цикл
30
10
10
+
+
-
-
+
+
-
-
20
10
20
Δ = min (10, 30) = 10

Новый опорный план
- 4
- 12
- 16
- 10
- 5
- 3
z(X) = 3·80

Открытая модель транспортной задачи
Открытую модель можно свести к закрытой:
1. Если ,

Задача 2
Решите транспортную задачу методом потенциалов. В ответе укажите минимальную

Метод «северо-западного угла»
z(X) = 3·90 + 7·10 + 13·70 +

Метод потенциалов
14
17
6
- 1
23
12
- 11
- 18

Цикл
30
0
170
+
+
-
-
+
+
-
-
30
30
140
Δ = min (30, 170) = 30

- 9
- 6
- 17
- 1
- 23
- 11
12
5
Новый опорный план
z(X) = 3·90

Цикл
90
10
30
+
+
-
-
Δ = min (90, 70, 140) = 70
-
+
70
140
+
+
+
-
-
-
70
80
100
20
70

3
6
- 5
- 13
- 12
- 23
- 11
- 7
Новый опорный план
z(X) = 3·20

Цикл
20
70
70
+
+
-
-
+
+
-
-
90
20
50
Δ = min (20, 70) = 20

Новый опорный план
- 6
- 3
- 11
- 13
- 6
- 23
- 11
- 1
z(X)

Задача 3
Решите транспортную задачу методом потенциалов. В ответе укажите минимальную

Метод наименьшей стоимости
z(X) = 1·60 + 2·40 + 16·25+ 4·75 +

Метод потенциалов
2
- 9
2
- 23
- 25
- 22
- 4
10
- 2

Цикл
25
10
40
+
+
-
-
+
+
-
-
25
35
15
Δ = min (25, 40) = 25

Новый опорный план
- 8
- 9
2
- 10
- 13
- 15
- 12
- 4
- 2
z(X)

Цикл
60
40
35
+
+
-
-
+
+
-
-
75
35
25
Δ = min (35, 60) = 35

Новый опорный план
- 10
- 9
- 12
- 2
- 11
- 13
- 12
- 2
0
План

Транспортные задачи с дополнительными ограничениями
В некоторых транспортных задачах наложены дополнительные ограничения