Глава 6. Транспортная задача
Содержательная постановка
Формализация
Развернутая запись (на примере)
Векторная запись
Принудительная балансировка
Замечание
Разрешимость
Размерность
Размерность
Целочисленность
Целочисленность
Целочисленность
Разложение векторов условий ТЗ
Критерий опорности плана перевозок
Метод северо-западного угла
Метод минимального элемента
Проблема вырождения опорных планов
Устранение вырожденности -методом
Задача, двойственная транспортной
Задача, двойственная транспортной
Задача, двойственная транспортной
Критерий оптимальности
Матрица невязок
Определение вектора, включаемого в базис
Определение вектора, исключаемого из базиса
Определение вектора, исключаемого из базиса
Преобразование плана перевозок
Преобразование плана перевозок
Практический алгоритм метода потенциалов
6.34M
Category: mathematicsmathematics

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

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
English     Русский Rules