Транспортная задача. Постановка и формы записи транспортной задачи

1. Глава 6. Транспортная задача

6.1. Постановка и формы записи
транспортной задачи

2. Содержательная постановка

1
Однородный продукт
Производители
Потребители
?
2

3. Формализация

2
Формализация
3

4. Развернутая запись (на примере)

3
Развернутая запись (на примере)
4

5. Векторная запись

4
Векторная запись
5

6. Принудительная балансировка

5
Принудительная балансировка
6

7. Замечание

6
Замечание
7

8.

6.2. Свойства транспортной задачи
8

9. Разрешимость

1
Разрешимость
9

10. Размерность

2
Размерность
10

11. Размерность

2
Размерность
11

12. Целочисленность

3
Целочисленность
12

13. Целочисленность

3
Целочисленность
13

14. Целочисленность

3
Целочисленность
14

15.

6.3. Построение исходных опорных
планов
15

16. Разложение векторов условий ТЗ

Столбцы
Строки
1
16

17. Критерий опорности плана перевозок

2
Критерий опорности плана перевозок
На матрице перевозок
На графе перевозок
17

18. Метод северо-западного угла

3
Метод северо-западного угла
На матрице перевозок
На графе перевозок
18

19. Метод минимального элемента

4
На матрице перевозок
(2
(4
(2
(3
(1
(3
На графе перевозок
19

20. Проблема вырождения опорных планов

5
Проблема вырождения опорных планов
На матрице перевозок
На графе перевозок
20

21. Устранение вырожденности -методом

6
Устранение вырожденности
-методом
21

22.

6.4. Критерий оптимальности
транспортной задачи
22

23. Задача, двойственная транспортной

1
Задача, двойственная транспортной
23

24. Задача, двойственная транспортной

1
Задача, двойственная транспортной
24

25. Задача, двойственная транспортной

1
Задача, двойственная транспортной
25

26. Критерий оптимальности

2
(2
(4
(2
(3
(1
(3
26

27. Матрица невязок

3
Матрица невязок
(2
2
(3
0
0
(2
(3
(4
3
(1
1
0
(4
(2
0
(3
6
4
(2
-4
0 (1
0 (3
2
4
6
0
-3
27

28.

6.5. Переход к новому опорному плану
28

29.

29

30. Определение вектора, включаемого в базис

1
Определение вектора, включаемого в базис
2
3
0
0
0
4
0
1
6
-4
0
0
30

31. Определение вектора, исключаемого из базиса

2
Определение вектора, исключаемого из базиса
31

32. Определение вектора, исключаемого из базиса

2
Определение вектора, исключаемого из базиса
2
3
0
0
0
4
0
1
6
-4
0
0
32

33. Преобразование плана перевозок

3
Преобразование плана перевозок
33

34. Преобразование плана перевозок

3
Преобразование плана перевозок
2
3
0
(2
(4
(2
0
1
6
(3
(1
(3
- включаемая перевозка
- исключаемая перевозка
34

35. Практический алгоритм метода потенциалов

4
ПОДГОТОВИТЕЛЬНЫЙ ЭТАП
1.
2.
3.
Балансировка (если необходимо)
Выбор Q и устранение вырожденности
Построение исходного опорного плана
ИТЕРАЦИЯ
4. Проверка на оптимальность:
нахождение потенциалов
построение матрицы невязок
проверка матрицы невязок на неотрицательность
5. Определение включаемой перевозки. Ей соответствует максимальный
(положительный) элемент матрицы невязок
6. Определение исключаемой перевозки
построение циклического (строка-столбец…) маршрута, замыкающегося на
вводимую перевозку
определение минимальной нечетной (в данном маршруте) перевозки
7. Преобразование плана перевозок
• нечетные перевозки уменьшаются на минимальную нечетную перевозку
• четные перевозки увеличиваются на минимальную нечетную перевозку
• не входящие в маршрут перевозки остаются прежними
• вводится новая перевозка
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП
8. Округление полученного оптимального плана с точностью до Q
35