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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Принятие решений с помощью моделей на бихроматических графах, слайд №1Принятие решений с помощью моделей на бихроматических графах, слайд №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.7

Слайд 2


СОДЕРЖАНИЕ Часть 1. Общие положения, обозначения и определения Часть 2. Задача 1 о назначениях – минимизация затрат Часть 3. Поиск стратегии, минимизирующей стоимость выполнения плана при ограничении на время его выполнения Часть 4. Поиск стратегии, обеспечивающей минимизацию времени выполнения плана при ограничении на фонд заработной платы Часть 5. Многокритериальная задача о назначениях.
Описание слайда:
СОДЕРЖАНИЕ Часть 1. Общие положения, обозначения и определения Часть 2. Задача 1 о назначениях – минимизация затрат Часть 3. Поиск стратегии, минимизирующей стоимость выполнения плана при ограничении на время его выполнения Часть 4. Поиск стратегии, обеспечивающей минимизацию времени выполнения плана при ограничении на фонд заработной платы Часть 5. Многокритериальная задача о назначениях.

Слайд 3


Часть 1 Общие положения, определения и обозначения
Описание слайда:
Часть 1 Общие положения, определения и обозначения

Слайд 4


Обозначения и определения Х – множество вершин неориентированного графа G(X,U); - «левое» подмножество вершин; - «правое» подмножество вершин (X’+X”=X); U – множество ребер графа G(X,U); r(i,j) – вес ребра Содержательная постановка задачи о максимальном паросочетании: На множестве ребер U графа G(X,U) выделить подмножество , такое, что: - существует не более одного ребра, принадлежащего U’ и инцидентного каждой вершине подмножества X’; - существует не более одного ребра принадлежащего U’ и , инцидентного каждой вершине подмножества X”; - мощность множества U’ максимальна.
Описание слайда:
Обозначения и определения Х – множество вершин неориентированного графа G(X,U); - «левое» подмножество вершин; - «правое» подмножество вершин (X’+X”=X); U – множество ребер графа G(X,U); r(i,j) – вес ребра Содержательная постановка задачи о максимальном паросочетании: На множестве ребер U графа G(X,U) выделить подмножество , такое, что: - существует не более одного ребра, принадлежащего U’ и инцидентного каждой вершине подмножества X’; - существует не более одного ребра принадлежащего U’ и , инцидентного каждой вершине подмножества X”; - мощность множества U’ максимальна.

Слайд 5


ОПРЕДЕЛЕНИЕ ПАРОСОЧЕТАНИЯ Подмножество U’ ребер называется паросочетанием, если любые два ребра из него не имеют общей вершины.
Описание слайда:
ОПРЕДЕЛЕНИЕ ПАРОСОЧЕТАНИЯ Подмножество U’ ребер называется паросочетанием, если любые два ребра из него не имеют общей вершины.

Слайд 6


ГРАФИЧЕСКАЯ ИЛЛЮСТРАЦИЯ
Описание слайда:
ГРАФИЧЕСКАЯ ИЛЛЮСТРАЦИЯ

Слайд 7


Формальная постановка задачи поиска максимального паросочетания
Описание слайда:
Формальная постановка задачи поиска максимального паросочетания

Слайд 8


Часть 2 Задача 1 о назначениях – минимизация затрат
Описание слайда:
Часть 2 Задача 1 о назначениях – минимизация затрат

Слайд 9


Задача о назначениях –минимизация затрат
Описание слайда:
Задача о назначениях –минимизация затрат

Слайд 10


Формальная постановка задачи минимизации затрат
Описание слайда:
Формальная постановка задачи минимизации затрат

Слайд 11


Форма представления исходных данных (пример для случая n=3)
Описание слайда:
Форма представления исходных данных (пример для случая 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.
Описание слайда:
Алгоритм 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. Конец алгоритма. На множестве нулей полученной матрицы есть оптимальное назначение.
Описание слайда:
Алгоритм 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)
Описание слайда:
Пример 1 (n=5)

Слайд 15


РЕШИТЬ САМОСТОЯТЕЛЬНО
Описание слайда:
РЕШИТЬ САМОСТОЯТЕЛЬНО

Слайд 16


Часть 3 Поиск стратегии, минимизирующей стоимость выполнения плана при ограничении на время его выполнения
Описание слайда:
Часть 3 Поиск стратегии, минимизирующей стоимость выполнения плана при ограничении на время его выполнения

Слайд 17


Задача 2: минимизация стоимости выполнения работ при ограничении на время их выполнения Задача отличается от ранее рассмотренной тем, что кроме стоимости известно время выполнения каждым рабочим каждой работы. Если i-й рабочий не может выполнять j-ю работу, то: где: r1(i,j) – стоимость выполнения i-ым рабочим j-ой работы. r2(i,j) – время выполнения i-ым рабочим j-ой работы Т – плановый период.
Описание слайда:
Задача 2: минимизация стоимости выполнения работ при ограничении на время их выполнения Задача отличается от ранее рассмотренной тем, что кроме стоимости известно время выполнения каждым рабочим каждой работы. Если i-й рабочий не может выполнять j-ю работу, то: где: r1(i,j) – стоимость выполнения i-ым рабочим j-ой работы. r2(i,j) – время выполнения i-ым рабочим j-ой работы Т – плановый период.

Слайд 18


Формальная постановка задачи 2
Описание слайда:
Формальная постановка задачи 2

Слайд 19


Решение задачи 2 Решение задачи 1 сводится к решению задачи 1 - «классической» задачи о назначениях, если исходную матрицу М преобразовать в M’ следующим образом:   Иными словами считаем, что если время выполнения i-м рабочим j-й работы больше Т, то i-й рабочий не может делать j-ю работу.   После этого матрица М’, содержащая лишь r1(i,j), используется для решения «классической» задачи о назначениях.
Описание слайда:
Решение задачи 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.
Описание слайда:
ПРИМЕР 2 Решить задачу с вектором критериев на бихроматическом графе, заданном (n x n) матрицей М, если n = 4, в верхней части каждой ячейки (i,j) матрицы М приведены величины r1(i,j), а в нижней – r2(i,j). Верхняя граница времени выполнения всех работ Т = 12.

Слайд 21


ПРИМЕР 2 (продолжение)
Описание слайда:
ПРИМЕР 2 (продолжение)

Слайд 22


РЕШИТЬ САМОСТОЯТЕЛЬНО
Описание слайда:
РЕШИТЬ САМОСТОЯТЕЛЬНО

Слайд 23


Часть 4 Поиск стратегии, обеспечивающей минимизацию времени выполнения плана при ограничениях на фонд заработной платы
Описание слайда:
Часть 4 Поиск стратегии, обеспечивающей минимизацию времени выполнения плана при ограничениях на фонд заработной платы

Слайд 24


ЗАДАЧА 3: Минимизация времени выполнения плана при ограничениях на затраты Пусть «С» – верхняя граница затрат на выполнение плана. Остальные обозначения совпадают с принятыми для задачи 2. Требуется таким образом распределить работу между исполнителями, чтобы: а) суммарные затраты не превысили величины С; б) все исполнители были заняты; в) все работы были выполнены; г) время выполнения работ должно быть минимально.
Описание слайда:
ЗАДАЧА 3: Минимизация времени выполнения плана при ограничениях на затраты Пусть «С» – верхняя граница затрат на выполнение плана. Остальные обозначения совпадают с принятыми для задачи 2. Требуется таким образом распределить работу между исполнителями, чтобы: а) суммарные затраты не превысили величины С; б) все исполнители были заняты; в) все работы были выполнены; г) время выполнения работ должно быть минимально.

Слайд 25


ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ 3
Описание слайда:
ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ 3

Слайд 26


АЛГОРИТМ 3 (начало)
Описание слайда:
АЛГОРИТМ 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. Конец алгоритма.
Описание слайда:
АЛГОРИТМ 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 (исходные данные)
Описание слайда:
ПРИМЕР 3 (исходные данные)

Слайд 29


ПРИМЕР 3 (решение) Перестановка π, полученная на шаге 2, имеет вид: π= {(2,1); (3,3); (1,2); (2,2); (1,1); (2,3); (3,2); (1,3); (3,1)} .
Описание слайда:
ПРИМЕР 3 (решение) Перестановка π, полученная на шаге 2, имеет вид: π= {(2,1); (3,3); (1,2); (2,2); (1,1); (2,3); (3,2); (1,3); (3,1)} .

Слайд 30


РЕШИТЬ САМОСТОЯТЕЛЬНО
Описание слайда:
РЕШИТЬ САМОСТОЯТЕЛЬНО

Слайд 31


ЧАСТЬ 5 Многокритериальная задача о назначениях
Описание слайда:
ЧАСТЬ 5 Многокритериальная задача о назначениях

Слайд 32


МИНИМИЗАЦИЯ ЗАТРАТ И ВРЕМЕНИ ВЫПОЛНЕНИЯ ПЛАНА
Описание слайда:
МИНИМИЗАЦИЯ ЗАТРАТ И ВРЕМЕНИ ВЫПОЛНЕНИЯ ПЛАНА

Слайд 33


ГРАФИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ
Описание слайда:
ГРАФИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ

Слайд 34


САМОСТОЯТЕЛЬНО Предложить алгоритмы решения многокритериальной задачи о назначениях на базе: 1. Взвешенной суммы критериев. 2. Лексикографического упорядочения критериев. 3. Метода эталонов.
Описание слайда:
САМОСТОЯТЕЛЬНО Предложить алгоритмы решения многокритериальной задачи о назначениях на базе: 1. Взвешенной суммы критериев. 2. Лексикографического упорядочения критериев. 3. Метода эталонов.

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию