Содержание
- 2. СОДЕРЖАНИЕ Часть 1. Общие положения, обозначения и определения Часть 2. Задача 1 о назначениях – минимизация
- 3. Часть 1 Общие положения, определения и обозначения
- 4. Обозначения и определения Х – множество вершин неориентированного графа G(X,U); - «левое» подмножество вершин; - «правое»
- 5. ОПРЕДЕЛЕНИЕ ПАРОСОЧЕТАНИЯ Подмножество U’ ребер называется паросочетанием, если любые два ребра из него не имеют общей
- 6. ГРАФИЧЕСКАЯ ИЛЛЮСТРАЦИЯ X’ x”
- 7. Формальная постановка задачи поиска максимального паросочетания где:
- 8. Часть 2 Задача 1 о назначениях – минимизация затрат
- 9. Задача о назначениях –минимизация затрат Заданы n работ и n рабочих, причем известна стоимость r(i, j)
- 10. Формальная постановка задачи минимизации затрат Примечание: если i-й рабочий не может делать j-ю работу, то r(i,j)=∞
- 11. Форма представления исходных данных (пример для случая n=3)
- 12. Алгоритм 1 Шаг 1. i = 1 Шаг 2. В i – ой строке матрицы М
- 13. Алгоритм 1 (продолжение) Шаг 8. j=j+1. Шаг 9. Если j>n, то перейти к Шагу 10, нет
- 14. Пример 1 (n=5)
- 15. РЕШИТЬ САМОСТОЯТЕЛЬНО
- 16. Часть 3 Поиск стратегии, минимизирующей стоимость выполнения плана при ограничении на время его выполнения
- 17. Задача 2: минимизация стоимости выполнения работ при ограничении на время их выполнения Задача отличается от ранее
- 18. Формальная постановка задачи 2
- 19. Решение задачи 2 Решение задачи 1 сводится к решению задачи 1 - «классической» задачи о назначениях,
- 20. ПРИМЕР 2 Решить задачу с вектором критериев на бихроматическом графе, заданном (n x n) матрицей М,
- 21. ПРИМЕР 2 (продолжение) оптимальное решение.
- 22. РЕШИТЬ САМОСТОЯТЕЛЬНО
- 23. Часть 4 Поиск стратегии, обеспечивающей минимизацию времени выполнения плана при ограничениях на фонд заработной платы
- 24. ЗАДАЧА 3: Минимизация времени выполнения плана при ограничениях на затраты Пусть «С» – верхняя граница затрат
- 25. ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ 3
- 26. АЛГОРИТМ 3 (начало) Решение задачи 3 сводится к многократному решению задачи 1 - «классической» задачи о
- 27. АЛГОРИТМ 3 (ПРОДОЛЖЕНИЕ) Шаг 6. Если значение целевой функции больше, чем С, то перейти к Шагу
- 28. ПРИМЕР 3 (исходные данные) Решить задачу 3 для графа G(X, U) при С = 26. Исходные
- 29. ПРИМЕР 3 (решение) Перестановка π, полученная на шаге 2, имеет вид: π= {(2,1); (3,3); (1,2); (2,2);
- 30. РЕШИТЬ САМОСТОЯТЕЛЬНО
- 31. ЧАСТЬ 5 Многокритериальная задача о назначениях
- 32. МИНИМИЗАЦИЯ ЗАТРАТ И ВРЕМЕНИ ВЫПОЛНЕНИЯ ПЛАНА
- 33. ГРАФИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ F2 F1 0 Начало координат – сочетание эталонных значений целевых функций.
- 35. Скачать презентацию