Презентация Принятие решений с помощью моделей на бихроматических графах онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Принятие решений с помощью моделей на бихроматических графах абсолютно бесплатно. Урок-презентация на эту тему содержит всего 34 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:34 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:852.40 kB
- Просмотров:65
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: ПРИНЯТИЕ РЕШЕНИЙ С ПОМОЩЬЮ МОДЕЛЕЙ НА БИХРОМАТИЧЕСКИХ ГРАФАХ
Лекция 2.7
№2 слайд
Содержание слайда: СОДЕРЖАНИЕ
Часть 1. Общие положения, обозначения и определения
Часть 2. Задача 1 о назначениях – минимизация затрат
Часть 3. Поиск стратегии, минимизирующей стоимость выполнения плана при ограничении на время его выполнения
Часть 4. Поиск стратегии, обеспечивающей минимизацию времени выполнения плана при ограничении на фонд заработной платы
Часть 5. Многокритериальная задача о назначениях.
№3 слайд
Содержание слайда: Часть 1
Общие положения, определения и обозначения
№4 слайд
Содержание слайда: Обозначения и определения
Х – множество вершин неориентированного графа G(X,U);
- «левое» подмножество вершин;
- «правое» подмножество вершин (X’+X”=X);
U – множество ребер графа G(X,U);
r(i,j) – вес ребра
Содержательная постановка задачи о максимальном паросочетании: На множестве ребер U графа G(X,U) выделить подмножество , такое, что:
- существует не более одного ребра, принадлежащего U’ и инцидентного каждой вершине подмножества X’;
- существует не более одного ребра принадлежащего U’ и , инцидентного каждой вершине подмножества X”;
- мощность множества U’ максимальна.
№5 слайд
Содержание слайда: ОПРЕДЕЛЕНИЕ ПАРОСОЧЕТАНИЯ
Подмножество U’ ребер называется паросочетанием, если любые два ребра из него не имеют общей вершины.
№6 слайд
Содержание слайда: ГРАФИЧЕСКАЯ ИЛЛЮСТРАЦИЯ
№7 слайд
Содержание слайда: Формальная постановка задачи поиска максимального паросочетания
№8 слайд
Содержание слайда: Часть 2
Задача 1 о назначениях – минимизация затрат
№9 слайд
Содержание слайда: Задача о назначениях –минимизация затрат
№10 слайд
Содержание слайда: Формальная постановка задачи минимизации затрат
№11 слайд
Содержание слайда: Форма представления исходных данных (пример для случая n=3)
№12 слайд
Содержание слайда: Алгоритм 1
Шаг 1. i = 1
Шаг 2. В i – ой строке матрицы М выбирается элемент, вес которого равен Q = min M(i,j) и уменьшаем вес каждого элемента этой строки на Q.
Шаг 3. i = i + 1
Шаг 4. Если i>n, то перейти к Шагу 5, нет к Шагу 2.
Шаг 5. j = 1
Шаг 6. В j –ом столбце матрицы М выбирается элемент, вес которого равен D = min M(i,j).
Шаг 7. Вес каждого элемента j –го столбца уменьшается на величину D.
№13 слайд
Содержание слайда: Алгоритм 1 (продолжение)
Шаг 8. j=j+1.
Шаг 9. Если j>n, то перейти к Шагу 10, нет - к Шагу 6.
Шаг 10. Нули матрицы вычеркиваются минимальным числом линий L, проводимых по строкам и столбцам матрицы.
Шаг 11. Если L = n, то перейти к Шагу 14, в противном случае – к Шагу 12.
Шаг 12. На множестве неперечеркнутых элементов матрицы М выбирается тот, вес которого минимален и равен W.
Шаг 13. Вес неперечеркнутых элементов матрицы уменьшаем на W, а перечеркнутых дважды – увеличиваем на W. Перейти к Шагу 8.
Шаг 14. Конец алгоритма. На множестве нулей полученной матрицы есть оптимальное назначение.
№14 слайд
Содержание слайда: Пример 1 (n=5)
№15 слайд
Содержание слайда: РЕШИТЬ САМОСТОЯТЕЛЬНО
№16 слайд
Содержание слайда: Часть 3
Поиск стратегии, минимизирующей стоимость выполнения плана при ограничении на время его выполнения
№17 слайд
Содержание слайда: Задача 2: минимизация стоимости выполнения работ при ограничении на время их выполнения
Задача отличается от ранее рассмотренной тем, что кроме стоимости известно время выполнения каждым рабочим каждой работы. Если i-й рабочий не может выполнять j-ю работу, то:
где:
r1(i,j) – стоимость выполнения i-ым рабочим j-ой работы.
r2(i,j) – время выполнения i-ым рабочим j-ой работы
Т – плановый период.
№18 слайд
Содержание слайда: Формальная постановка задачи 2
№19 слайд
Содержание слайда: Решение задачи 2
Решение задачи 1 сводится к решению задачи 1 - «классической» задачи о назначениях, если исходную матрицу М преобразовать в M’ следующим образом:
Иными словами считаем, что если время выполнения i-м рабочим j-й работы больше Т, то
i-й рабочий не может делать j-ю работу.
После этого матрица М’, содержащая лишь r1(i,j), используется для решения «классической» задачи о назначениях.
№20 слайд
Содержание слайда: ПРИМЕР 2
Решить задачу с вектором критериев на бихроматическом графе, заданном (n x n) матрицей М, если n = 4, в верхней части каждой ячейки (i,j) матрицы М приведены величины r1(i,j), а в нижней – r2(i,j). Верхняя граница времени выполнения всех работ Т = 12.
№21 слайд
Содержание слайда: ПРИМЕР 2 (продолжение)
№22 слайд
Содержание слайда: РЕШИТЬ САМОСТОЯТЕЛЬНО
№23 слайд
Содержание слайда: Часть 4
Поиск стратегии, обеспечивающей минимизацию времени выполнения плана при ограничениях на фонд заработной платы
№24 слайд
Содержание слайда: ЗАДАЧА 3: Минимизация времени выполнения плана при ограничениях на затраты
Пусть «С» – верхняя граница затрат на выполнение плана. Остальные обозначения совпадают с принятыми для задачи 2. Требуется таким образом распределить работу между исполнителями, чтобы:
а) суммарные затраты не превысили величины С;
б) все исполнители были заняты;
в) все работы были выполнены;
г) время выполнения работ должно быть
минимально.
№25 слайд
Содержание слайда: ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ 3
№26 слайд
Содержание слайда: АЛГОРИТМ 3 (начало)
№27 слайд
Содержание слайда: АЛГОРИТМ 3 (ПРОДОЛЖЕНИЕ)
Шаг 6. Если значение целевой функции больше, чем С, то перейти к Шагу 7, нет – к Шагу 10.
Шаг 7. t = t + 1.
Шаг 8. Если t<q+1, то перейти к Шагу 4, если же t > q, - то к Шагу 9.
Шаг 9. Печать «Нет решения», перейти к Шагу 11.
Шаг 10. Время выполнения плана равно r2(i,j)t.
Шаг 11. Конец алгоритма.
№28 слайд
Содержание слайда: ПРИМЕР 3 (исходные данные)
№29 слайд
Содержание слайда: ПРИМЕР 3 (решение)
Перестановка π, полученная на шаге 2, имеет вид: π= {(2,1); (3,3); (1,2); (2,2); (1,1); (2,3); (3,2); (1,3); (3,1)} .
№30 слайд
Содержание слайда: РЕШИТЬ САМОСТОЯТЕЛЬНО
№31 слайд
Содержание слайда: ЧАСТЬ 5
Многокритериальная задача о назначениях
№32 слайд
Содержание слайда: МИНИМИЗАЦИЯ ЗАТРАТ И ВРЕМЕНИ ВЫПОЛНЕНИЯ ПЛАНА
№33 слайд
Содержание слайда: ГРАФИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ
№34 слайд
Содержание слайда: САМОСТОЯТЕЛЬНО
Предложить алгоритмы решения многокритериальной задачи о назначениях на базе:
1. Взвешенной суммы критериев.
2. Лексикографического упорядочения критериев.
3. Метода эталонов.
Скачать все slide презентации Принятие решений с помощью моделей на бихроматических графах одним архивом:
