Пример 25

Построить сетевой граф, найти минимально возможный критический путь и стоимость работ до сжатия и после него, если условия проекта заданы в следующей таблице:

Решение.

По условию задачи составим сетевой граф:

60 90

30 20

Рис.20

Найдем все пути и их продолжительность:

200 дней – критический путь

180 дней

80 дней

Найдем наклон кривой «затраты – продолжительность» для каждой операции. Наклон равен отношению прироста стоимости к приросту продолжительности (рис.19). Результат запишем в таблице:

Найдем продолжительность путей, сжимая операции, имеющие наименьший наклон. Построим граф, учитывая максимальный режим.

80 65

Рис.21

157 дней – критический путь

72 дня

157 дней – критический путь

Найдем стоимость при нормальном режиме:

Критический путь 200 дней, стоимость работ 265 тыс. руб.

Найдем стоимость сжатия работ:

(0,1): 30 тыс. руб. – 20 тыс. руб. = 10 тыс. руб.;

(1,2): 60 тыс. руб. – 40 тыс. руб. = 20 тыс. руб.;

(2,4): 70 тыс. руб. – 60 тыс. руб. = 10 тыс. руб.;

(3,4): 35 тыс. руб. – 25 тыс. руб. = 10 тыс. руб.;

(4,5): 25 тыс. руб. – 20 тыс. руб. = 5 тыс. руб.;

10 тыс. руб. + 20 тыс. руб. + 10 тыс. руб. + 10 тыс. руб. + 5 тыс. руб. = 55 тыс. руб.

Критический путь может быть уменьшен до 157 дней, при этом минимальная стоимость работ составляет 265 тыс. руб. + 55 тыс. руб. = 320 тыс. руб.

Вопросы к экзамену

1. Сформулировать транспортную задачу (экономическая постановка).

2. Математическая модель транспортной задачи.

3. Методы построения исходного опорного плана перевозок.

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

5. Метод наименьшей стоимости.

6. Нахождение потенциалов поставщиков и потребителей.

7. Критерий оптимальности решения транспортной задачи.

8. Понятие открытой модели транспортной задачи.

9. Понятие закрытой модели транспортной задачи.

10. Алгоритм метода потенциала решения транспортной задачи.

11. Экономическое истолкование оптимального решения транспортной задачи.

12. Предмет и задачи теории игр.

13. Решение матричных игр в чистых стратегиях. Матричные игры с нулевой суммой.

14. Принцип максимина, нижнее значение игры.

15. Принцип минимакса, верхнее значение игры.

16. Ситуация равновесия в чистых стратегиях, седловая точка, цена игры.

17. Решение матричных игр в смешанных стратегиях.

18. Методы решения игр без седловой точки. Смешанные стратегии.

19. Игры с природой. Оптимальность в играх с природой.

20. Решение статистических игр по различным критериям: Байеса – Лапласа, максиминный критерий крайнего пессимизма Вальда, пессимизма – оптимизма Гурвица, минимаксного риска Сэвиджа.

21. Определение графа. Примеры.

22. Матрицы смежности и инцидентности графа.

23. Путь и цикл в графе.

24. Связность графа, деревья.

25. Эйлеровы графы, пример.

26. Гамильтоновы графы, пример.

27. Ориентированные графы, источник, сток, маршрут, матрица инцидентности.

28. Сеть, критический путь.