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

Презентация:



Advertisements
Похожие презентации
Управление надежностью как инструмент достижения долгосрочных целей ОАО «ОГК-1»
Advertisements

Маршруты на графах Нахождение компонент связности Поиск маршрутов, удовлетворяющим определённым требованиям Кратчайшие маршруты.
ЛЕКЦИИ 2-3. Курс: Проектирование систем: Структурный подход Каф. Коммуникационные сети и системы, Факультет радиотехники и кибернетики Московский физико-технический.
1 Интеллектуальные системы Лекция 3. Информированный (эвристический) поиск Вахтин А. А.
КРИТЕРИИ ОЦЕНКИ ИНФОРМАЦИОННЫХ СИСТЕМ Дмитрий Петренко Донецкий Национальный Технический Университет.
1. Теория множеств. Операции над множествами. Диаграммы Эйлера – Венна. Соответствие между множествами. Примеры.
Презентация по Информатике Тема: «Графы» Выполнил: Бычков Георгий.
Кирийчук Дмитрий Леонидович ХЕРСОНСКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ КАФЕДРА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ.
Деревья, сети, графы. Система - это любой объект, состоящий из множества взаимосвязанных частей и существующий как единое целое.
Остовные деревья Лекция 4. Задача «Минимальное остовное дерево» Дано: Граф G, веса c: E(G) R. Найти остовное дерево в G наименьшего веса или определить,
Алгоритм
Задача о максимальном потоке в сети Алгоритм Фалкерсона-Форда.
Лабораторные информационные системы как инструмент управления деятельностью клинико-диагностических лабораторий © 2009 Promedichi® Денис Бугров,
1 Комбинаторные алгоритмы Задача о k-центрах. 2 Метрическая задача o k центрах Дано: Полный граф G = (V, E), стоимости ребер cost: E Q + такие, что для.
1 Приближенные алгоритмы Комбинаторные алгоритмы.
Алгоритм Флойда-Уоршалла Находит кратчайшие расстояния между всеми парами вершин графа Идея: Строится специальная матрица D, элементы которой – кратчайшие.
1 Лекция 6 Графы. 2 Граф – это множество вершин и соединяющих их ребер. Примеры графов:
Теория графов Основные определения. Дуга Пусть имеется множество вершин V={V 1,V 2,…,V n } и пусть на нем задано бинарное отношение Г V×V, – V i Г V j.
Матроиды Лекция 12. Введение Даны система множеств (E, F ), то есть конечное множество E, F 2 E и стоимостная функция c : F R, найти элемент из F, стоимость.
Общая математическая модель распределения вычислительных ресурсов в многопроцессорных системах М.Х. Прилуцкий, С.Ю. Петри Нижегородский государственный.
Транксрипт:

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

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

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

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

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

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

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