Похожие презентации:
Транспортная задача. Постановка и формы записи транспортной задачи
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.
2930. Определение вектора, включаемого в базис
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