Использование орграфов в задачах производственного планирования Дмитрий Петренко Донецкий Национальный Технический Университет. - презентация

1 Использование орграфов в задачах производственного планирования Дмитрий Петренко Донецкий Национальный Технический Университет

2 Математическая модель G(U,V) – орграф U i – вершина (состояние) i1..n V j – дуга (технологическая операция) j 1..m С j – вес дуги

3 Возможные задачи оптимизации Минимизация стоимости технологического процесса Минимизация количества технологических операций Максимизация общей надежности процесса

4 Формализация задачи 1. Взвесим ребра: p i - надежность операции c i - стоимость операции 2. Решение есть путь из V 1 в V n. 3. Представим его как множество дуг пути R={R 1, R 2,…,R k } c i p i V1V1 VnVn

5 Функции цели для задач Минимизация стоимости технологического процесса Минимизация количества технологических операций Максимизация общей надежности процесса

6 Алгоритмы поиска путей Алгоритм Флойда (сложность порядка N 2 ) Алгоритм Дейкстры (сложность порядка N 2 ) Комбинаторные алгоритмы (сложность NP)

7 Использование орграфов в задачах производственного планирования Дмитрий Петренко Донецкий Национальный Технический Университет