🗊Презентация Теория расписаний. Минимизация приоритето-порождающих функций

Категория: Математика
Нажмите для полного просмотра!
Теория расписаний. Минимизация приоритето-порождающих функций, слайд №1Теория расписаний. Минимизация приоритето-порождающих функций, слайд №2Теория расписаний. Минимизация приоритето-порождающих функций, слайд №3Теория расписаний. Минимизация приоритето-порождающих функций, слайд №4Теория расписаний. Минимизация приоритето-порождающих функций, слайд №5Теория расписаний. Минимизация приоритето-порождающих функций, слайд №6Теория расписаний. Минимизация приоритето-порождающих функций, слайд №7Теория расписаний. Минимизация приоритето-порождающих функций, слайд №8Теория расписаний. Минимизация приоритето-порождающих функций, слайд №9Теория расписаний. Минимизация приоритето-порождающих функций, слайд №10Теория расписаний. Минимизация приоритето-порождающих функций, слайд №11Теория расписаний. Минимизация приоритето-порождающих функций, слайд №12Теория расписаний. Минимизация приоритето-порождающих функций, слайд №13Теория расписаний. Минимизация приоритето-порождающих функций, слайд №14Теория расписаний. Минимизация приоритето-порождающих функций, слайд №15Теория расписаний. Минимизация приоритето-порождающих функций, слайд №16Теория расписаний. Минимизация приоритето-порождающих функций, слайд №17Теория расписаний. Минимизация приоритето-порождающих функций, слайд №18Теория расписаний. Минимизация приоритето-порождающих функций, слайд №19Теория расписаний. Минимизация приоритето-порождающих функций, слайд №20Теория расписаний. Минимизация приоритето-порождающих функций, слайд №21
Скачать

Содержание ▲

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

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

Слайд 1


Теория расписаний Минимизация приоритето-порождающих функций
Описание слайда:
Теория расписаний Минимизация приоритето-порождающих функций

Слайд 2


Минимизация приоритето-порождающих функций Задача 1/out — tree/ ∑Cj Решить задачу 1/out — tree/ ∑Cj , в которой имеется 10 требований. Требование 3 предшествует требованию 4, которое, в свою очередь, предшествует требованиям 1, 7 и 9. Длительности обслуживания pj заданы в таблице:
Описание слайда:
Минимизация приоритето-порождающих функций Задача 1/out — tree/ ∑Cj Решить задачу 1/out — tree/ ∑Cj , в которой имеется 10 требований. Требование 3 предшествует требованию 4, которое, в свою очередь, предшествует требованиям 1, 7 и 9. Длительности обслуживания pj заданы в таблице:

Слайд 3


Минимизация приоритето-порождающих функций Обозначим Пr - множество всех перестановок πr = (i1, ... , ir) элементов множества N = {1, ..., n}, r = 1, ..., n П0 = {π0} = {()}
Описание слайда:
Минимизация приоритето-порождающих функций Обозначим Пr - множество всех перестановок πr = (i1, ... , ir) элементов множества N = {1, ..., n}, r = 1, ..., n П0 = {π0} = {()}

Слайд 4


Минимизация приоритето-порождающих функций Функция F(π), определенная на множестве Пn называется приоритето-порождающей (ППФ), если существует функция ω(π), π  Π, называемая функцией приоритета, которая обладает следующими свойствами: для любых перестановок π = (π1, πα, πb, π2)  Πn и π' = (π1, πb, πα, π2)  Πn из ω(πα) > ω(πb) следует F(π) ≤ F(π') и из ω(πα) = ω(πb) следует F(π) = F(π').
Описание слайда:
Минимизация приоритето-порождающих функций Функция F(π), определенная на множестве Пn называется приоритето-порождающей (ППФ), если существует функция ω(π), π  Π, называемая функцией приоритета, которая обладает следующими свойствами: для любых перестановок π = (π1, πα, πb, π2)  Πn и π' = (π1, πb, πα, π2)  Πn из ω(πα) > ω(πb) следует F(π) ≤ F(π') и из ω(πα) = ω(πb) следует F(π) = F(π').

Слайд 5


Минимизация приоритето-порождающих функций Множество N является частично упорядоченным, если задано отношение предшествования (бинарное, транзитивное, антирефлексивное отношение), представленное графом редукции этого отношения G = (N, U). Граф G называется графом редукции отношения предшествования, если он получен из графа отношения частичного порядка путем удаления всех транзитивных дуг.
Описание слайда:
Минимизация приоритето-порождающих функций Множество N является частично упорядоченным, если задано отношение предшествования (бинарное, транзитивное, антирефлексивное отношение), представленное графом редукции этого отношения G = (N, U). Граф G называется графом редукции отношения предшествования, если он получен из графа отношения частичного порядка путем удаления всех транзитивных дуг.

Слайд 6


Минимизация приоритето-порождающих функций Многие задачи построения оптимальных расписаний сводятся к минимизации ППФ на частично упорядоченных множествах требований. Отношения предшествования присутствуют в задачах, где некоторые операции используют результаты других (предшествующих) операций.
Описание слайда:
Минимизация приоритето-порождающих функций Многие задачи построения оптимальных расписаний сводятся к минимизации ППФ на частично упорядоченных множествах требований. Отношения предшествования присутствуют в задачах, где некоторые операции используют результаты других (предшествующих) операций.

Слайд 7


Примеры приоритето-порождающих функций Можно доказать, что: для задачи 1/prec/ ΣCj целевая функция является ППФ с функцией приоритета ω (π) = |{π}|/Ρ (π) где Ρ (π) = Σpj, для задачи 1/prec/ ΣwjCj целевая функция является ППФ с функцией приоритета ω (π) = W(π)/Ρ(π), где W(π) = Σwj.
Описание слайда:
Примеры приоритето-порождающих функций Можно доказать, что: для задачи 1/prec/ ΣCj целевая функция является ППФ с функцией приоритета ω (π) = |{π}|/Ρ (π) где Ρ (π) = Σpj, для задачи 1/prec/ ΣwjCj целевая функция является ППФ с функцией приоритета ω (π) = W(π)/Ρ(π), где W(π) = Σwj.

Слайд 8


Методы минимизации приоритето-порождающих функций на частично упорядоченных множествах Пусть задано частично упорядоченное множество N с графом редукции отношения частичного порядка G = (N,U). Задача состоит в минимизации F(π), πΠn(G), где Πn(G) - множество всех перестановок элементов множества N, допустимых относительно G.
Описание слайда:
Методы минимизации приоритето-порождающих функций на частично упорядоченных множествах Пусть задано частично упорядоченное множество N с графом редукции отношения частичного порядка G = (N,U). Задача состоит в минимизации F(π), πΠn(G), где Πn(G) - множество всех перестановок элементов множества N, допустимых относительно G.

Слайд 9


Методы минимизации приоритето-порождающих функций на частично упорядоченных множествах Введем операции над бесконтурными орграфами, не содержащими транзитивных дуг (в т.ч. графами редукции отношения частичного порядка): Преобразование I - [t, s] отождествления вершин t и s: замена вершин t и s одной составной вершиной [t, s]. Все входящие (исходящие) дуги в вершины t и s заменяются на входящие (исходящие) дуги в составную вершину. Удаляются появившиеся тразитивные дуги. Преобразование II - (s, t) добавления дуги (s, t): добавление дуги (s, t) с последующим удалением тразитивных дуг.
Описание слайда:
Методы минимизации приоритето-порождающих функций на частично упорядоченных множествах Введем операции над бесконтурными орграфами, не содержащими транзитивных дуг (в т.ч. графами редукции отношения частичного порядка): Преобразование I - [t, s] отождествления вершин t и s: замена вершин t и s одной составной вершиной [t, s]. Все входящие (исходящие) дуги в вершины t и s заменяются на входящие (исходящие) дуги в составную вершину. Удаляются появившиеся тразитивные дуги. Преобразование II - (s, t) добавления дуги (s, t): добавление дуги (s, t) с последующим удалением тразитивных дуг.

Слайд 10


Методы минимизации приоритето-порождающих функций на частично упорядоченных множествах Цепь (i1, ..., ik), где компоненты ij являются составными вершинами, называется ω-цепью, если ω (il)  ω (il+1), l = 1, ..., k - 1. Если G представляет собой ω -цепь, то перестановка (i1, ..., ik) является оптимальной. Если граф G – лес, то существует последовательность преобразований I и II, переводящая G в ω -цепь.
Описание слайда:
Методы минимизации приоритето-порождающих функций на частично упорядоченных множествах Цепь (i1, ..., ik), где компоненты ij являются составными вершинами, называется ω-цепью, если ω (il)  ω (il+1), l = 1, ..., k - 1. Если G представляет собой ω -цепь, то перестановка (i1, ..., ik) является оптимальной. Если граф G – лес, то существует последовательность преобразований I и II, переводящая G в ω -цепь.

Слайд 11


Алгоритм минимизации ППФ на частично упорядоченных множествах Задача 1/out — tree/ F , где F – ППФ. Алгоритм минимизации ППФ на множестве Πn(G), где G - набор выходящих деревьев : 1. Вычисляем приоритеты не имеющих потомков (висячих) вершин. 2. Если G не есть набор изолированных вершин, то находим в G вершину i0, называемую опорной, все прямые потомки которой являются висячими. Пусть этим потомкам соответствуют ω-цепи C1, ..., Сl. Построим ω-цепь (i1, ..., iν), упорядочив все (составные) вершины цепей C1, ..., Cl по невозрастанию приоритетов.
Описание слайда:
Алгоритм минимизации ППФ на частично упорядоченных множествах Задача 1/out — tree/ F , где F – ППФ. Алгоритм минимизации ППФ на множестве Πn(G), где G - набор выходящих деревьев : 1. Вычисляем приоритеты не имеющих потомков (висячих) вершин. 2. Если G не есть набор изолированных вершин, то находим в G вершину i0, называемую опорной, все прямые потомки которой являются висячими. Пусть этим потомкам соответствуют ω-цепи C1, ..., Сl. Построим ω-цепь (i1, ..., iν), упорядочив все (составные) вершины цепей C1, ..., Cl по невозрастанию приоритетов.

Слайд 12


Алгоритм минимизации ППФ на частично упорядоченных множествах (продолжение) Построим цепь (i0, i1, ..., iν). Если ω(i0) > ω(i1), то цепь (i0, i1, ... ,iν) является ω-цепью. Если ω(i0) ≤ ω(i1), то объединяем i0 и i1 в составную вершину [i0, i1]. Далее сравниваем ω(i0, i1) и ω(i2) и, в случае необходимости, объединяем [i0, i1] и i2 и т.д. Процесс продолжается до тех пор, пока цепь (i0, i1, ..., iν) не будет преобразована в некоторую ω-цепь C 0 = ([i0, i1, …, ik], ik+1, ... , iv). Удаляем из G всех потомков вершины i0 и ставим ей в соответствие ω-цепь C 0.
Описание слайда:
Алгоритм минимизации ППФ на частично упорядоченных множествах (продолжение) Построим цепь (i0, i1, ..., iν). Если ω(i0) > ω(i1), то цепь (i0, i1, ... ,iν) является ω-цепью. Если ω(i0) ≤ ω(i1), то объединяем i0 и i1 в составную вершину [i0, i1]. Далее сравниваем ω(i0, i1) и ω(i2) и, в случае необходимости, объединяем [i0, i1] и i2 и т.д. Процесс продолжается до тех пор, пока цепь (i0, i1, ..., iν) не будет преобразована в некоторую ω-цепь C 0 = ([i0, i1, …, ik], ik+1, ... , iv). Удаляем из G всех потомков вершины i0 и ставим ей в соответствие ω-цепь C 0.

Слайд 13


Алгоритм минимизации ППФ на частично упорядоченных множествах (продолжение) 3. Повторяем описанный процесс до тех пор, пока не будет построен граф, состоящий из изолированных вершин. Последовательность (составных) вершин соответствующих ω-цепям, в которой вершины упорядочены по невозрастанию приоритетов, является оптимальным решением задачи.
Описание слайда:
Алгоритм минимизации ППФ на частично упорядоченных множествах (продолжение) 3. Повторяем описанный процесс до тех пор, пока не будет построен граф, состоящий из изолированных вершин. Последовательность (составных) вершин соответствующих ω-цепям, в которой вершины упорядочены по невозрастанию приоритетов, является оптимальным решением задачи.

Слайд 14


Алгоритм минимизации ППФ на частично упорядоченных множествах (продолжение) В случае, когда граф G – входящее дерево, в качестве опорной выбирается вершина i0, все непосредственные предшественники которой i1, ..., iν не имеют предшественников. Формируется цепь (i1, ..., iν, i0). Она преобразуется в ω-цепь путем сравнения ω(i0) и ω(iv). Составная вершина [iν, i0] образуется, если ω(iv) ≤ ω(i0). Далее процесс аналогичен случаю выходящего дерева.
Описание слайда:
Алгоритм минимизации ППФ на частично упорядоченных множествах (продолжение) В случае, когда граф G – входящее дерево, в качестве опорной выбирается вершина i0, все непосредственные предшественники которой i1, ..., iν не имеют предшественников. Формируется цепь (i1, ..., iν, i0). Она преобразуется в ω-цепь путем сравнения ω(i0) и ω(iv). Составная вершина [iν, i0] образуется, если ω(iv) ≤ ω(i0). Далее процесс аналогичен случаю выходящего дерева.

Слайд 15


Пример реализации алгоритма. Задача 1/out — tree/ ∑Cj Решить задачу 1/out — tree/ ∑Cj, в которой имеется 10 требований. Требование 3 предшествует требованию 4, которое, в свою очередь, предшествует требованиям 1, 7 и 9. Длительности обслуживания pj заданы в таблице:
Описание слайда:
Пример реализации алгоритма. Задача 1/out — tree/ ∑Cj Решить задачу 1/out — tree/ ∑Cj, в которой имеется 10 требований. Требование 3 предшествует требованию 4, которое, в свою очередь, предшествует требованиям 1, 7 и 9. Длительности обслуживания pj заданы в таблице:

Слайд 16


Пример реализации алгоритма (продолжение). 1. Вычислим значение функции приоритета для висячих вершин. Функция приоритета: ω (π) = |{π}|/Ρ (π) где Ρ (π) = Σpj,
Описание слайда:
Пример реализации алгоритма (продолжение). 1. Вычислим значение функции приоритета для висячих вершин. Функция приоритета: ω (π) = |{π}|/Ρ (π) где Ρ (π) = Σpj,

Слайд 17


Пример реализации алгоритма (продолжение). 2а. Опорной вершиной является вершина 4, все прямые потомки которой 1, 7 и 9 являются висячими. ω-цепь для потомков вершины 4: (7, 1, 9), поскольку значения функции ω вершин равны, соответственно, (1, 1/4, 1/9)
Описание слайда:
Пример реализации алгоритма (продолжение). 2а. Опорной вершиной является вершина 4, все прямые потомки которой 1, 7 и 9 являются висячими. ω-цепь для потомков вершины 4: (7, 1, 9), поскольку значения функции ω вершин равны, соответственно, (1, 1/4, 1/9)

Слайд 18


Пример реализации алгоритма (продолжение). 2б. Цепь (4, 7, 1, 9) не является ω-цепью, поскольку значения функции ω вершины 4 равно 1/5<1. Объединяем вершины 4 и 7 в составную вершину [4, 7]. Приоритет составной вершины [4, 7] равен 2/(5+1)=1/3. Цепь ([4, 7], 1, 9) является ω-цепью, т.к. 1/3>1/4. Удаляем из графа G всех потомков вершины 4 и ставим ей в соответствие ω-цепь.
Описание слайда:
Пример реализации алгоритма (продолжение). 2б. Цепь (4, 7, 1, 9) не является ω-цепью, поскольку значения функции ω вершины 4 равно 1/5<1. Объединяем вершины 4 и 7 в составную вершину [4, 7]. Приоритет составной вершины [4, 7] равен 2/(5+1)=1/3. Цепь ([4, 7], 1, 9) является ω-цепью, т.к. 1/3>1/4. Удаляем из графа G всех потомков вершины 4 и ставим ей в соответствие ω-цепь.

Слайд 19


Пример реализации алгоритма (продолжение). 3а. Опорной вершиной является вершина 3, ω-цепь для потомков вершины 3: ([4, 7], 1, 9)
Описание слайда:
Пример реализации алгоритма (продолжение). 3а. Опорной вершиной является вершина 3, ω-цепь для потомков вершины 3: ([4, 7], 1, 9)

Слайд 20


Пример реализации алгоритма (продолжение). 3б. Цепь (3, [4, 7], 1, 9) не является ω-цепью поскольку значения функции ω вершины 3 равно 1/3=1/3. Объединяем вершины 3 и [4, 7] в составную вершину [3, 4, 7]. Приоритет составной вершины [3, 4, 7] равен 3/(3+5+1)=1/3. Цепь ([3, 4, 7], 1, 9) является ω-цепью, т.к. 1/3>1/4. Удаляем из графа G всех потомков вершины 3 и ставим ей в соответствие ω-цепь.
Описание слайда:
Пример реализации алгоритма (продолжение). 3б. Цепь (3, [4, 7], 1, 9) не является ω-цепью поскольку значения функции ω вершины 3 равно 1/3=1/3. Объединяем вершины 3 и [4, 7] в составную вершину [3, 4, 7]. Приоритет составной вершины [3, 4, 7] равен 3/(3+5+1)=1/3. Цепь ([3, 4, 7], 1, 9) является ω-цепью, т.к. 1/3>1/4. Удаляем из графа G всех потомков вершины 3 и ставим ей в соответствие ω-цепь.

Слайд 21


Пример реализации алгоритма (продолжение). 4. Построен граф, состоящий из изолированных вершин. Последовательность (составных) вершин соответствующих ω-цепям, в которой вершины упорядочены по невозрастанию приоритетов (ω): ({2, 8}, 3, 4, 7, {1, 6, 10}, 5, 9). Данная последовательность является оптимальной. Ответ: ({2, 8}, 3, 4, 7, {1, 6, 10}, 5, 9), значение целевой функции равно 174.
Описание слайда:
Пример реализации алгоритма (продолжение). 4. Построен граф, состоящий из изолированных вершин. Последовательность (составных) вершин соответствующих ω-цепям, в которой вершины упорядочены по невозрастанию приоритетов (ω): ({2, 8}, 3, 4, 7, {1, 6, 10}, 5, 9). Данная последовательность является оптимальной. Ответ: ({2, 8}, 3, 4, 7, {1, 6, 10}, 5, 9), значение целевой функции равно 174.

Скачать

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