Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Поиск решения задач, формальные модели которых сводятся к многокритериальным задачам о назначениях. Лекция 8

Содержание

Содержательная постановка многокритериальной задачи о назначениях Заданы n работ и n рабочих, причем известна стоимость r(i, j) и время t(i,j) выполнения i-м рабочим j-й работы. Требуется распределить работы между рабочими т.о., чтобы:1. Все работы были выполнены;2.
МОДЕЛИРОВАНИЕ СИСТЕМЛекция 8Поиск решения задач, формальные модели которых сводятся к многокритериальным задачам Содержательная постановка многокритериальной задачи о назначениях Заданы n работ и n рабочих, Формальная постановка задачи Примечание: если i-й рабочий не может делать j-ю работу, то r(i,j)=∞ Формальная постановка задачи поиска нижней границы минимизации затрат в системе (1) Формальная постановка задачи поиска верхней границы объема затрат в на выполнение работ в системе (1) Формальная постановка задачи поиска нижней границы времени выполнения плана в системе (1) Формальная постановка задачи поиска верхней границы времени выполнения плана в системе (1) Формальная постановка задачи с нормированными целевыми функциямиПримечание: если i-й рабочий не может Графическая иллюстрацияЛюбому допустимому вектору «У» системы (6) соответствует точка А в системе Формальная постановка задачи с нормированными целевыми функциями Теоремы, облегчающие поиск решения системы (1):Теорема 1: Оптимальное решение системы (7) является Алгоритм поиска решения системы (7) (первые 6 шагов)Шаг 1. R = ∞.Шаг Алгоритм поиска решения системы (7) (последние 5 шагов)Шаг 6. Вычисляется значение целевой ПРИМЕРРешить задачу (1) сведением ее к виду (7), если данные матриц r РЕШЕНИЕШаг 1. R = ∞.Шаг 2. π =Шаг 3. Smax =53; Smin=0; САМОСТОЯТЕЛЬНОРешить задачу (1) сведением ее к виду (7), если данные матриц r
Слайды презентации

Слайд 2 Содержательная постановка многокритериальной задачи о назначениях
Заданы n

Содержательная постановка многокритериальной задачи о назначениях Заданы n работ и n

работ и n рабочих, причем известна стоимость r(i, j)

и время t(i,j) выполнения i-м рабочим j-й работы. Требуется распределить работы между рабочими т.о., чтобы:

1. Все работы были выполнены;

2. Все рабочие были заняты;

3. Суммарные задачи на выполнение всего
цикла работ были минимальны.

4. Время выполнения всех работ было минимально.

Слайд 3 Формальная постановка задачи

Примечание: если i-й рабочий не

Формальная постановка задачи Примечание: если i-й рабочий не может делать j-ю работу, то r(i,j)=∞

может делать j-ю работу, то r(i,j)=∞


Слайд 4 Формальная постановка задачи поиска нижней границы минимизации затрат

Формальная постановка задачи поиска нижней границы минимизации затрат в системе (1)

в системе (1)



Слайд 5 Формальная постановка задачи поиска верхней границы объема затрат

Формальная постановка задачи поиска верхней границы объема затрат в на выполнение работ в системе (1)

в на выполнение работ в системе (1)



Слайд 6 Формальная постановка задачи поиска нижней границы времени выполнения

Формальная постановка задачи поиска нижней границы времени выполнения плана в системе (1)

плана в системе (1)



Слайд 7 Формальная постановка задачи поиска верхней границы времени выполнения

Формальная постановка задачи поиска верхней границы времени выполнения плана в системе (1)

плана в системе (1)



Слайд 8 Формальная постановка задачи с нормированными целевыми функциями

Примечание: если

Формальная постановка задачи с нормированными целевыми функциямиПримечание: если i-й рабочий не

i-й рабочий не может делать j-ю работу, то r(i,j)=∞


Слайд 9 Графическая иллюстрация
Любому допустимому вектору «У» системы (6) соответствует

Графическая иллюстрацияЛюбому допустимому вектору «У» системы (6) соответствует точка А в

точка А в системе координат «χ, τ»:

χ
1
χ1





0


0 τ1 1 τ

А(τ1 , χ1 )

L(0,A)= χ1^2 + τ1 ^2


Слайд 10 Формальная постановка задачи с нормированными целевыми функциями


Формальная постановка задачи с нормированными целевыми функциями

Слайд 11 Теоремы, облегчающие поиск решения системы (1):
Теорема 1: Оптимальное

Теоремы, облегчающие поиск решения системы (1):Теорема 1: Оптимальное решение системы (7)

решение системы (7) является одним из оптимальных по Парето

решений системы (1).
Теорема 2: Существует единственное значение, минимизирующее целевую функцию F системы (7).

Слайд 12 Алгоритм поиска решения системы (7) (первые 6 шагов)
Шаг

Алгоритм поиска решения системы (7) (первые 6 шагов)Шаг 1. R =

1. R = ∞.
Шаг 2. Строится перестановка π компонент

Матрицы исходных данных М такая, что для её k-й компоненты t(i,j) и (k+1)-й компоненты t(p,q) справедливо: t(i,j) ≤ t(p,q).
Шаг 3. k=1.
Шаг 4. T присваивается значение, равное t(i,j) на k-м месте в перестановке π .
Шаг 5.
Шаг 6. После этого матрица М’, содержащая лишь r(i,j), используется для решения «классической» задачи о назначениях.



Слайд 13 Алгоритм поиска решения системы (7) (последние 5 шагов)
Шаг

Алгоритм поиска решения системы (7) (последние 5 шагов)Шаг 6. Вычисляется значение

6. Вычисляется значение целевой функции F системы (7).
Шаг 7.

Если F < R, то перейти к шагу 8, в противном случае – к шагу 10
Шаг 8. k = k + 1.
Шаг 9. Перейти к шагу 4.
Шаг 10. Конец алгоритма. Величина R равна оптимальному значению целевой функции системы (7).

Слайд 14 ПРИМЕР
Решить задачу (1) сведением ее к виду (7),

ПРИМЕРРешить задачу (1) сведением ее к виду (7), если данные матриц

если данные матриц r и t приведены ниже:

Матрица “r” Матрица “t”

Слайд 15 РЕШЕНИЕ
Шаг 1. R = ∞.
Шаг 2. π =


Шаг

РЕШЕНИЕШаг 1. R = ∞.Шаг 2. π =Шаг 3. Smax =53;

3. Smax =53; Smin=0; Tmax=15; Tmin=0.
Шаг 4. T=5; S=51;

F=1,037.
Шаг 5. T=6; S=51; F=1,236.
Шаг 6. Конец алгоритма. R= 1,037.

Читать таблицу слева направо сверху вниз.



  • Имя файла: poisk-resheniya-zadach-formalnye-modeli-kotoryh-svodyatsya-k-mnogokriterialnym-zadacham-o-naznacheniyah-lektsiya-8.pptx
  • Количество просмотров: 114
  • Количество скачиваний: 0