Принятие решений с помощью моделей на бихроматических графах

Нажмите для полного просмотра!

Принятие решений с помощью моделей на бихроматических графах, слайд №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

Принятие решений с помощью моделей на бихроматических графах, слайд №29

Принятие решений с помощью моделей на бихроматических графах, слайд №30

Принятие решений с помощью моделей на бихроматических графах, слайд №31

Принятие решений с помощью моделей на бихроматических графах, слайд №32

Принятие решений с помощью моделей на бихроматических графах, слайд №33

Принятие решений с помощью моделей на бихроматических графах, слайд №34

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Принятие решений с помощью моделей на бихроматических графах. Доклад-сообщение содержит 34 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 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, - то к Шагу 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. Метода эталонов.