WWW.KNIGI.KONFLIB.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

 
<< HOME
Научная библиотека
CONTACTS

Pages:     || 2 | 3 |

«Задачи • исследование задач теории расписаний, выявлении их сложности (NPтрудности, полиномиальности); • нахождение свойств оптимальных решений исследуемых задач; • ...»

-- [ Страница 1 ] --

с.н.с. Лаборатории №68

Гафаров Евгений Рашидович

Графический метод

решения задач

комбинаторной оптимизации

Диссертационная работа на соискание ученой степени

доктора физико-математических наук

Специальность: 01.01.09

«Дискретная математика и математическая кибернетика»

Научный консультант: д.ф.-м.н., профессор Лазарев Александр

Алексеевич

Содержание презентации

Часть 1. Графический метод: точное решение.

Модификация метода динамического программирования.

Кусочно-линейные функции Беллмана.

Часть 2. Графический метод: приближенное решение.

Нахождение решения с заданной погрешностью.

Часть 3. Графические алгоритмы решения задач теории расписаний Исследование сложности задач.

Точные и приближенные алгоритмы решения.

Часть 4. Графические алгоритмы решения классических задач комбинаторной оптимизации Точные и приближенные алгоритмы решения.

Часть 5. Прочие результаты Сложность задач теории расписаний.

Программные продукты.

2 из Цель работы Разработка эффективных методов и алгоритмов решения задач комбинаторной оптимизации.

Задачи • исследование задач теории расписаний, выявлении их сложности (NPтрудности, полиномиальности);

• нахождение свойств оптимальных решений исследуемых задач;

• построение точных и приближённых графических алгоритмов решения задач теории расписаний и комбинаторной оптимизации, а также сравнение с существующими алгоритмами решения этих задач.

3 из Задачи комбинаторной оптимизации Выбрать лучшее (оптимальное) решение среди множества допустимых решений.

Множество слишком большое – полный перебор за разумное время невозможен.

Задача об одномерном ранце pjxj max Для n=80 порядка 280 решений!

n предметов, W – вместимость рюкзака;

230 опер/секунду -- быстрейший wj – вес предмета; wjxj W;

pj – cтоимость предмета. xj = 0 или 1. компьютер.

Необходимо: сократить область перебора, не исключив оптимальное решение.

Алгоритмическая (временная) сложность решения задач комб. оптимизации Класс P – задачи, решаемые за полиномиальное время («несложные»);

NP-трудные задачи, для которых полиномиальный алгоритм решения неизвестен («сложные»).

Известная математическая проблема: P = NP?

Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.

Хачиян Леонид Генрихович, ВЦ РАН, метод эллипсоидов, премия Фалкерсона.

Необходимо:

1. Определить, к какому классу (P или NP-трудные) относится задача.

2. Построить быстрый точный или приближенный алгоритм решения.

4 из Основные направления исследований в дис.работе Задачи Комбинаторная оптимизация Теория расписаний Задачи с кусочно- Задачи с кусочнолинейными линейными функциями Беллмана функциями Беллмана Графический метод Динамическое программирование Метод решения 5 из Часть 1. Графический метод: точное решение Некоторые сведения о трудоемкости алгоритмов M.A. Posypkin, I. Kh. Sigal, Speedup estimates for some variants of the parallel implementations of the branch-and-bound method, Computational Mathematics and Mathematical Physics, 46, N 12 (2006), 2189 –2 202.

Для задачи о ранце, ВСЕ алгоритмы ветвей и границ с полиномиальными алгоритмами расчета верхних/нижних оценок имеют трудоемкость не меньше 3 2+3/ 2 (+1) Thomas E. O’Neil and Scott Kerlin, A Simple 2( ) Algorithm for PARTITION and SUBSET SUM, 2010,4 pages (работа не опубликована).

Субэкспоненциальные алгоритмы динам. программирования для задач разбиение, одномерный ранец, клика, упаковка в паллеты трудоемкостью где x – длина входа.

Простая идея: сокращать интервал рассмотрения состояний.

Графический метод Функциональные уравнения Беллмана.

На стадии l, l = 1,2,…,n рассматриваются все целые точки (состояния) t из [0,A] (t) – функция Беллмана, Если = (например, = + ) на некотором интервале, +1, то можно построить графический алгоритм.

Графический алгоритм решения задачи максимизации суммарного запаздывания 0 оптимальное значение целевой функции, (t) – функция Беллмана, стадия (шаг), размерность задачи (количество требований), числовой параметр продолжительность обслуживания, числовой параметр директивный срок.

Вычисления в алгоритме динамического программирования Вычисления в графическом алгоритме Графический алгоритм решения задачи максимизации суммарного запаздывания Сдвинуть график функции влево на Решить уравнение + = 0, и увеличить наклон графика функции на 1 после точки t’ – корень уравнения.

Решить уравнение + =1 = 0, и увеличить наклон графика функции на 1 после точки t’’ – корень уравнения.

12 из Графический алгоритм решения задачи максимизации суммарного запаздывания Функция F1(t) Функция Fl-1(t) 14 из 15 из 16 из 17 из 18 из Графический алгоритм решения задачи максимизации суммарного запаздывания Трудоемкость алгоритма динамического программирования O(npj ).

Трудоемкость графического алгоритма O(n2).

Трудоемкость графического алгоритма для других задач Трудоемкость графического алгоритма (в т.ч. для других задач) зависит от количества точек излома ml+1 на стадии l.

Пусть M – суммарное количество точек излома на всех стадиях.

Если трудоемкость дин.прогр. равна O(nA), то трудоемкость графического алгоритма O(min{nA,M}) Количество точек излома равно количеству различных значений bk в таблице.

Часть 2. Графический метод:

приближенное решение Аппроксимация основанная на графическом алгоритме Количество точек излома равно количеству различных значений bk в таблице.

Трудоемкость каждого шага зависит линейно от количества точек излома.

Нужно сократить количество изломов.

FPTAS основанная на графическом алгоритме Fully polinomial time approximation schema (полная полиномиальная аппрокс. схема) Относительная погрешность не боле. Трудоемкость полиномиально зависит только от размерности задачи и 1/.

Функция Беллмана в графическом алгоритме В таблице, 0bl1 bl2 … т.к. функция Fl(t) неубывающая.

Сократить количество изломов = Сократить количество колонок.

FPTAS основанная на графическом алгоритме Чтобы сократить трудоемкость, мы можем округлить значения blkUB, чтобы в таблице было полиномиальное число различных значений blk Пусть решается задача минимизации и UB – верхняя оценка.

Пусть F(*) – оптимальное значение целевой функции и UB/ F(*) 2.

Пусть трудоемкость графического алгоритма равна O(n min{UB,А}).

Тогда… FPTAS основанная на графическом алгоритме Не более чем UB/ = 2n/ различных модифицированных blk.

Тогда не более чем 4n/ колонок в таблице задающей функцию.

Суммарная относительная погрешность не более чем n F(*).

Трудоемкость FPTAS равна Сравнение графического алгоритма и алгоритмов динам. программирования для одноприборных задач теории расписаний Экспериментальное сравнение графического алгоритма и алгоритмов динам.

программирования для задачи о ранце.

Время работы, сек Графический алгоритм эффективно решает примеры с миллионом предметов.

Преимущества графических алгоритмов Графический алгоритм работает не в режиме «калькулятора», а принимает во внимание аналитический вид целевой функции.

• возможность решать нецелочисленные примеры;

• легче строить FPTAS;

• теоретическая трудоемкость для многих задач меньше;

• можно решать примеры большого масштаба;

• находит решение для всех возможных точек старта обслуживания t [-,+];

• согласно результатам экспериментальных исследований, для большинства рассмотренных примеров трудоемкость графического алгоритма не превышает O(n3).

Задачи с переменным временем начала обслуживания требований:

Hoogeveen, H., and T’Kindt, V., 2010. Minimizing the Number of Late Jobs When the Starting Time of the Machine is Variable. Proceedings PMS, 235 – 238.

Публикации по графическому алгоритму для задач теории расписаний E.R. Gafarov, A.A. Lazarev and F. Werner (2012), Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one. Annals of Operations Research, 196 (1), 247-261.

E.R. Gafarov, A.A. Lazarev and F. Werner. (2012), A note on a single machine scheduling problem with generalized total tardiness objective function. Information Processing Letters, 112 (3), 72 – 76.

E.R. Gafarov, A.A. Lazarev and F. Werner (2010), Single machine total tardiness maximization problems: complexity and algorithms. Annals of Operation Research 3 статьи находятся на рецензии Часть 3. Графические алгоритмы решения задач теории расписаний Классические задачи Теории расписаний 1 прибор (нет простоев, не более 1го требования в каждый момент времени) n требований (прерывания в обслуживании запрещены) pj продолжительность обслуживания требования j dj директивный срок wj вес (значимость) Sj() время начала обслуживания требования j при расписании Сj() = Sj()+ pj время окончания обслуживания требования j при расписании Tj() = max{0, Сj() - dj } запаздывание wj Tj() = wj max{0, Сj() - dj } взвешенное запаздывание GTj() = max{0, min{pj, Сj() - dj }} обобщенное запаздывание Uj() = 1, если Сj() - dj 0 иначе Uj() = Bellman R. Mathematical aspects of scheduling theory // Journal of the Society of Industrial and Applied Mathematics. – 1956. – Vol. 4. –P. 168–205.

Танаев В.С., Шкурба В.В., Введение в теорию расписаний.

М.: Наука, 1975.

Классические задачи Теории расписаний Sj() время начала обслуживания требования j при расписании Сj() = Sj()+ pj время окончания обслуживания требования j при расписании Tj() = max{0, Сj() - dj } запаздывание wj Tj() = wj max{0, Сj() - dj } взвешенное запаздывание GTj() = max{0, min{pj, Сj() - dj }} обобщенное запаздывание Uj() = 1, если Сj() - dj 0 иначе Uj() = Задачи 1||Tj минимизация суммарного запаздывания Частный случай B-1: p1… pn, d1… dn, dn-d1 pn Док-во NP-трудности 1| dj =d| wjTj Задачи с обратными критериями оптимизации Максимизировать Tj, wjTj, Uj и т.п.

Допустимые расписания:

– обслуживание начинается в момент времени 0;

-- нет простоев прибора (no-idle).

Теоретическая значимость:

- для оценки худшего возможного решения;

- для отсечения плохих частичных решений;

- для решения би-критериальных задач.

Собственные практические интерпретации.

Задачи с обратными критериями оптимизации Сведение задачи разбиения к частному случаю.

Существует ли подмножество, что = B?

Лемма 1.5. Для частного случая (1.1)-(1.9) в любом допустимом расписании запаздывающих требований.

Лемма 1.6. Для любых двух канонических расписаний 1 и 2 выполняется |F(1 ) – F(2)| A Лемма 1.7. Для частного случая (1.1)-(1.9) все оптимальные расписания – канонические или могут быть преобразованы в них, применением правила SPT (упорядочить по возрастанию продолжительностей обслуживания) к первым требованиям.

Теорема 1.8. Задача 1(no-idle)||max wj Tj является NP-трудной в обычном смысле.

Доказательство: E.R. Gafarov, A.A. Lazarev and F. Werner (2013), Single machine total tardiness maximization problems: complexity and algorithms.// Annals of Operation Research, doi:10.1007/s10479-012-1288-x Задачи с обратными критериями оптимизации Полученные результаты:

1(no-idle)||max wj Tj - док-во NP-трудности в обычном смысле, графич. алгоритм.

1(no-idle)| rj | max Tj - док-во NP-трудности.

1(no-idle)|| max Tj - полиномиальный графический алгоритм решения.



Pages:     || 2 | 3 |
 


Похожие работы:

«Хеннинг Кёлер - Загадка страха Henning Kцhler Vom Rдtsel der Angst Wo die Angst begrьndet liegt, und wie wir mit ihr umgehen kцnnen 1992 Verlag Freies Geistesleben GmbH, Stuttgart Хеннинг Кёлер Загадка страха На чем основан страх и как с ним быть Перевод с немецкого И. Карташовой Редактор Н.Н. Федорова Корректор Н.И. Маркелова МОСКВА 2003 ББК 88.37 УДК 159.98 SBN 5-94610-023-8 © evidentis, 2003 Предисловие Эта небольшая книга о загадке страха написана не затем, чтобы извлечь выгоду из беды...»

«Большая школьная лаборатория Книга записей результатов наблюдений для 5-7 классов 1 Roland Full Опыт Личное дело пенопластового шарика 1 Масса, объём, длина окружности и площадь Findikus a Определение массы и объёма Наблюдение: Пенопластовый шарик: Масса: Объём (грубо): Объём (точно): Расчёт объёма (V = 4/3 r3 = 4/3 r r r 3,14): V = Подсказка: Если твои кухонные весы недостаточно чувствительны, чтобы показать массу пенопластового шарика, мы приводим её здесь: m = 0,9 г. Pfkus b Определение...»

«Умная теплица Рад сообщить дачникам приятнейшее известие. Наконец-то мне написал человек, не только по-настоящему понимающий предмет малых теплиц и парников, но и прекрасно пишущий об этом. Представляю: Константин Георгиевич Малышевский, клуб Лето, г. Красноярск. Он практически полностью автоматизировал свою тепличку без всякой электроники - само солнышко, с помощью простых гидроцилиндров, открывает фрамуги и включает полив! Результат - отличные урожаи овощей весь сезон, с самых ранних сроков...»

«• ИЗДАТЕЛЬСТВО ТГТУ • Министерство образования Российской Федерации ТАМБОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Ю.Ю. Громов, Н.А. Земской, А.В. Лагутин, О.Г. Иванова, В.М. Тютюнник СИСТЕМНЫЙ АНАЛИЗ В ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЯХ Допущено УМО вузов по университетскому политехническому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности 071900 – Информационные системы и технологии. Тамбов • Издательство ТГТУ • 2004 УДК 004(075) ББК...»

«А. В. Поляков ЗАЩИТА НАСЕЛЕНИЯ И ОБЪЕКТОВ ОТ ЧРЕЗВЫЧАЙНЫХ СИТУАЦИЯХ Курс лекций В двух частях Часть 1 ХАРАКТЕРИСТИКА, ПРОГНОЗИРОВАНИЕ И ПРЕДУПРЕЖДЕНИЕ ЧРЕЗВЫЧАЙНЫХ СИТУАЦИЙ 1 Поляков, А. В. Защита населения и объектов народного хозяйства в чрезвычайных ситуациях В 2 ч. Ч. 1. Характеристика, прогнозирование и предупреждение чрезвычайных ситуаций / А. В. Поляков. В первой части учебного пособия даны классификация и краткая характеристика чрезвычайных ситуаций, рассматриваются типовые ЧС,...»

«Б И Б Л И О Т Е К А А Л Е К С А Н Д Р А П О Г О Р Е Л Ь С К О Г О С Е Р И Я И С Т О Р И Я К У Л Ь Т У Р О Л О Г И Я АЛЕКСАНДР ДОБРОХОТОВ ИЗБРАННОЕ И З Д А Т Е Л Ь С К И Й Д О М Т Е Р Р И Т О Р И Я Б У Д У Щ Е Г О МОСКВА 2007 ББК 87(88.6) Р 83 : В. В. Анашвили, А. Л. Погорельский : В. Л. Глазычев, Л. Г. Ионин, В. А. Куренной А. Ф. Филиппов, Р. З. Хестанов L 83 Д А. Избранное. — М.: Издательский дом Территория будущего, 2007. (Серия Университетская библиотека Александра Погорельского). — 480 с....»

«Программа вступительного испытания (собеседование/устный экзамен) по дисциплине Физическая география и ландшафты и Экономическая и социальная география России, для поступающих на направление подготовки магистратуры 05.04.02 – География Физическая география и ландшафты России Объект и предмет региональной физической географии. Факторы пространственной физико-географической дифференциации и формирование ПТК регионального уровня. Природные компоненты и природные территориальные комплексы (ПТК)....»

«Основы программирования в среде Lazarus УДК 004 ББК 32.973-01 Рецензенты: доктор физико-математических наук, профессор Сопуев А.С. доктор физико-математических наук, профессор Сатыбаев А.С. М23 Мансуров К.Т. Основы программирования в среде Lazarus, 2010. – 772 с.: ил. ISBN 978-9967-03-646-8 В книге излагаются основы программирования на языке Паскаль. Она вводит читателя в круг тех идей, понятий, принципов и методов, на которых зиждется современное программирование. Изложение языка Паскаль...»

«Пультовая ВЭПП-2 Федеральное государственное бюджетное учреждение науки ИНСТИТУТ ЯДЕРНОЙ ФИЗИКИ ИМ.Г.И.БУДКЕРА Сибирского отделения РАН Первые коллайдеры ИЯФ. К 50-летию начала экспериментов по физике элементарных частиц. Главный редактор – академик А.Н.Скринский. Авторский коллектив: академик Г.Н.Кулипанов, академик А.Н.Скринский, д.ф.-м.н., профессор С.И.Середняков, д.ф.-м.н., профессор А.П.Онучин, д.ф.-м.н., профессор Г.М.Тумайкин, к.ф.-м.н. В.В.Петров. Новосибирск 2014 УДК 53:061 Первые...»

«Мистерии Бхагавата-пураны Песни 1-12 песни: I II III IV V VI VII VIII IX X XI XII “Бхагавата Пурана — зрелый плод древа ведической литературы.” (1.1.3.) “ИНСТИТУТ ПРАКТИЧЕСКОЙ МЕТАФИЗИКИ” Санкт-Петербург 2001 Сурендра Мохан дас (Неаполитанский С. М.) Мистерии Бхагаваты Пураны (Песни 1-12). — СПб.: “Институт практической метафизики”, 2001. — 432 с. В книге дается подробное изложение одного из самых известных и авторитетных ведических писаний — Бхагаваты Пураны (Шримад Бхагаватам). В ней...»






 
© 2013 www.knigi.konflib.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.