Задача о критическом пути
Исходные данные содержатся в сетевом графике Г(m, n, S, T).Введем переменные
Тогда задача ЛП, эквивалентная задаче о критическом пути, выглядит следующим образом:
(13)
Заметим без
доказательства, что отбрасывание
последнего условия (
)
не изменяет оптимального решения задачи
(13),
т. е. исключив это условие, ее можно
решать как обычную задачу ЛП.
Задача о кратчайшем сроке
Введем переменные
.
Тогда задача о кратчайшем пути как
задача ЛП имеет следующую постановку:
(14)
Нетрудно установить, что задача (13) (без последнего условия) является двойственной к задаче (14).
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
Задача 1. Для данной транспортной задачи требуется:
1) составить соответствующую ей задачу линейного программи- рования;
2) составить двойственную ей задачу;
3) методом
северо-западного угла построить
начальный опорный план
:
4) методом потенциалов найти оптимальный опорный план перевозок.
|
|
|
20 |
30 |
30 |
10 |
|
1.1. |
30 |
2 |
3 |
2 |
4 |
|
20 |
3 |
2 |
5 |
1 | |
|
|
40 |
4 |
3 |
2 |
6 |
|
|
|
5 |
10 |
20 |
15 |
|
1.2. |
10 |
8 |
3 |
5 |
2 |
|
15 |
4 |
1 |
6 |
7 | |
|
|
25 |
1 |
9 |
4 |
3 |
|
|
|
20 |
34 |
16 |
10 |
|
1.3. |
30 |
2 |
6 |
3 |
4 |
|
35 |
1 |
5 |
6 |
9 | |
|
|
15 |
3 |
4 |
1 |
6 |
|
|
|
40 |
20 |
25 |
15 |
|
1.4. |
25 |
9 |
5 |
3 |
2 |
|
55 |
6 |
3 |
3 |
1 | |
|
|
20 |
3 |
8 |
4 |
7 |
|
|
|
40 |
25 |
15 |
20 |
|
1.5. |
30 |
3 |
5 |
2 |
5 |
|
25 |
4 |
7 |
8 |
1 | |
|
|
45 |
8 |
6 |
4 |
3 |
|
|
|
25 |
15 |
40 |
20 |
|
1.6. |
60 |
6 |
4 |
10 |
18 |
|
30 |
12 |
14 |
6 |
8 | |
|
|
10 |
14 |
16 |
2 |
6 |
|
|
|
15 |
45 |
20 |
20 |
|
1.7. |
25 |
10 |
18 |
20 |
6 |
|
55 |
6 |
12 |
4 |
16 | |
|
|
20 |
16 |
6 |
16 |
8 |
|
|
|
25 |
20 |
25 |
30 |
|
1.8. |
40 |
7 |
6 |
2 |
3 |
|
22 |
1 |
3 |
5 |
4 | |
|
|
38 |
9 |
4 |
4 |
1 |
|
|
|
45 |
30 |
50 |
25 |
|
1.9. |
45 |
5 |
2 |
3 |
1 |
|
65 |
7 |
9 |
6 |
3 | |
|
|
40 |
4 |
7 |
5 |
2 |
|
|
|
25 |
15 |
10 |
20 |
|
1.10. |
15 |
9 |
5 |
3 |
10 |
|
45 |
6 |
3 |
3 |
2 | |
|
|
10 |
3 |
8 |
4 |
8 |
|
|
|
20 |
20 |
15 |
15 |
|
1.11. |
45 |
2 |
5 |
6 |
1 |
|
5 |
7 |
4 |
1 |
2 | |
|
|
20 |
3 |
6 |
2 |
6 |
|
|
|
45 |
15 |
20 |
20 |
|
1.12. |
25 |
9 |
5 |
3 |
10 |
|
55 |
6 |
3 |
8 |
2 | |
|
|
20 |
3 |
8 |
4 |
8 |
|
|
|
30 |
10 |
20 |
40 |
|
1.13. |
20 |
5 |
1 |
3 |
2 |
|
50 |
2 |
4 |
8 |
1 | |
|
|
30 |
3 |
5 |
4 |
6 |
|
|
|
10 |
15 |
15 |
10 |
|
1.14. |
25 |
1 |
3 |
8 |
2 |
|
15 |
5 |
1 |
2 |
4 | |
|
|
10 |
7 |
6 |
3 |
2 |
|
|
|
15 |
25 |
20 |
30 |
|
1.15. |
40 |
3 |
1 |
6 |
2 |
|
30 |
5 |
2 |
1 |
7 | |
|
|
20 |
3 |
4 |
8 |
6 |
|
|
|
20 |
30 |
30 |
40 |
|
1.16. |
30 |
2 |
3 |
5 |
1 |
|
40 |
3 |
1 |
4 |
7 | |
|
|
50 |
2 |
5 |
1 |
9 |
|
|
|
25 |
20 |
25 |
30 |
|
1.17. |
40 |
4 |
1 |
8 |
5 |
|
20 |
3 |
7 |
2 |
3 | |
|
|
40 |
5 |
4 |
1 |
2 |
|
|
|
10 |
20 |
50 |
10 |
|
1.18. |
30 |
7 |
3 |
5 |
1 |
|
10 |
4 |
2 |
6 |
3 | |
|
|
50 |
9 |
7 |
3 |
1 |
|
|
|
20 |
30 |
10 |
20 |
|
1.19. |
35 |
2 |
7 |
8 |
5 |
|
25 |
1 |
9 |
3 |
1 | |
|
|
20 |
8 |
6 |
4 |
2 |
|
|
|
35 |
10 |
25 |
10 |
|
1.20. |
20 |
5 |
8 |
1 |
3 |
|
20 |
2 |
3 |
9 |
4 | |
|
|
40 |
1 |
5 |
2 |
1 |
|
|
|
20 |
20 |
30 |
30 |
|
1.21. |
30 |
3 |
9 |
5 |
1 |
|
20 |
2 |
1 |
8 |
6 | |
|
|
50 |
7 |
3 |
4 |
2 |
|
|
|
20 |
30 |
10 |
20 |
|
1.22. |
10 |
8 |
1 |
5 |
3 |
|
30 |
7 |
2 |
3 |
1 | |
|
|
40 |
4 |
1 |
5 |
2 |
|
|
|
20 |
25 |
35 |
10 |
|
1.23. |
20 |
5 |
1 |
2 |
3 |
|
40 |
3 |
4 |
6 |
9 | |
|
|
30 |
2 |
7 |
1 |
5 |
|
|
|
30 |
10 |
20 |
20 |
|
1.24. |
15 |
9 |
2 |
1 |
4 |
|
45 |
6 |
5 |
2 |
1 | |
|
|
20 |
3 |
2 |
5 |
8 |
|
|
|
15 |
10 |
15 |
40 |
|
1.25. |
20 |
1 |
3 |
9 |
2 |
|
25 |
5 |
4 |
8 |
3 | |
|
|
35 |
6 |
7 |
2 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
Задача 2. Дан сетевой график. Найти:
1) его графическое изображение;
2) кратчайший срок выполнения всего комплекса работ;
3) оптимальный календарный план;
4) резервы времени всех событий;
5) критический путь;
6) задачу ЛП, эквивалентную задаче о кратчайшем сроке;