Диплом, курсовая, контрольная работа
Помощь в написании студенческих работ

Исследование и решение задач об упаковке множества на основе L-разбиения и лексикографической оптимизации

Диссертация: Исследование и решение задач об упаковке множества на основе L-разбиения и лексикографической оптимизации
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Научная новизна. В диссертации продолжены исследования в направлении применения метода регулярных разбиений для анализа и решения задач об упаковке множества, получены новые теоретические и экспериментальные результаты. Проведен анализ задач об упаковке множества с системами ограничений блочной структуры, которые являются математическими моделями проблем, возникающих при проектировании сложных… Читать ещё >

Содержание

  • Глава 1. Математические модели и методы для задач об упаковке множества
    • 1. 1. Постановки задач и
  • приложения
    • 1. 2. Задача о наибольшем независимом множестве
    • 1. 3. Полиномиально разрешимые случаи
    • 1. 4. Метод регулярных разбиений
    • 1. 5. Алгоритм перебора ¿-классов
  • Глава 2. Исследование задач об упаковке множества с системами ограничений блочной структуры
    • 2. 1. Проектирование одной системы радиосвязи
    • 2. 2. Анализ ¿-накрытий задач со связующими столбцами
    • 2. 3. Оценки мощности ¿-накрытий для некоторых семейств задач
    • 2. 4. ПодклассытР-трудных задач
  • Глава 3. Разработка и анализ алгоритмов
    • 3. 1. Исследование процесса перебора ¿-классов
    • 3. 2. Алгоритмы перебора ¿-классов и лексикографической оптимизации для задач об упаковке множества
    • 3. 3. Алгоритмы решения задач блочной структуры
    • 3. 4. О приближенном решении задач
  • Глава 4. Результаты вычислительного эксперимента
    • 4. 1. Описание разработанного комплекса программ
    • 4. 2. О среднем числе итераций метода перебора L-классов
    • 4. 3. Исследование алгоритмов для задач об упаковке множества
    • 4. 4. Решение задач об упаковке множества, блочной структуры

Исследование и решение задач об упаковке множества на основе L-разбиения и лексикографической оптимизации (реферат, курсовая, диплом, контрольная)

Актуальность темы

Исследование различных задач оптимизации, разработка и анализ методов их решения осуществляется на основе математического моделирования, в том числе с использованием аппарата целочисленного программирования (ЦП) [9.20,29.74.81,90.92]. Особый интерес к задачам ЦП вызван тем. что во многих случаях необходимо находить оптимальные решения, удовлетворяющие условию целочисленности. Указанные задачи имеют большое теоретическое и практическое значение.

Модели и методы целочисленного программирования [8,21.25,27.3739,69.78,85,91,93] применяются для анализа и решения задач дискретной оптимизации [4,39,64.67.73,85], например, оптимального размещения [57. 11. 32. 33. 52. 53, 77], о покрытии [26. 84]. максимальной выполнимости логической формулы [2, 3, 43, 44], о рюкзаке [49, 56, 129, 133], задач проектирования с логическими ограничениями [14. 54, 63]. оптимизации на графах [79.80], поэтому данной проблематике посвящено значительное число публикаций.

Задачи об упаковке множества занимают важное место в дискретной оптимизации и имеют широкий круг приложений в экономике, планировании, управлении, теории информации и других областях [24.68,96−98.121.131,140.142]. Для указанных задач изучается их структура и сложность, выделяются полиномиально разрешимые случаи и семейства трудных задач, устанавливаются новые свойства многогранников, разрабатываются и исследуются алгоритмы точного и приближенного решения [66, 96, 100, 106, 107. 111. 114, 116, 124, 132, 138].

Многие результаты получены с применением целочисленного линейного программирования и отражены в работах [34,47.71,115,134.136.137]. В связи с этим исследование задач об упаковке множества и разработка алгоритмов их решения является актуальным направлением.

При моделировании сложных экономических и технических систем часто возникают оптимизационные задачи большой размерности, которые относятся к задачам целочисленного программирования блочного типа [1, 94]. При этом блоки обычно представляют в моделях отдельные объекты, подразделения фирмы, части одного устройства, различные временные отрезки и т. п. Они могут быть соединены между собой ограничениями, в которых выражена необходимость использования общих ресурсов, обеспечения взаимосвязи решений для всего предприятия, технологического процесса или периода планирования. Некоторые постановки предстваляют собой задачи об упаковке множества блочной структуры. Перспективным направлением анализа и решения таких задач является применение декомпозиционных методов, в которых учитывается блочная структура модели. Так. в работе [94] исследуются дискретные задачи квазиблочного типа, в [72, 99] предлагаются различные методы приведения систем ограничений задач ЦП к блочному виду, в [76] строится алгоритм для решения задачи прямоугольной упаковки на базе использования блочных структур.

Для решения задач об упаковке множества можно применять алгоритмы, разработанные на основе известных методов целочисленного программирования, в частности схемы ветвей и границ [130. 138], различных процедур неявного перебора допустимых решений (см., например, [95]). метода лексикографической оптимизации [28], алгоритмов отсечений [10,31,40,87,88,118,135]. Среди процедур приближенного решения рассматриваемых задач наиболее известны генетические алгоритмы, методы локальной оптимизации, алгоритмы муравьиных колоний, схемы жадного типа [106,107,111,114] и другие.

Для иследоваиия задач целочисленного программирования, построения и анализа алгоритмов их решения A.A. Колоколовым был предложен метод регулярных разбиений [40—42. 47]. получивший применение и развитие во многих работах. В соответствии с этим подходом релаксационное множество задачи ЦП разбивается определенным образом на классы эквивалентности. Наиболее изученным является одно из таких разбиений — L-разбиепие, элементы которого называются L-классами. На его основе построены алгоритмы перебора L-классов, используемые для решения различных задач ЦП [3,43−45,47].

С помощью регулярных разбиений изучена структура и сложность ряда задач ЦП. разработаны и исследованы новые алгоритмы и классы правильных отсечений, построены оценки числа итераций для известных алгоритмов целочисленного линейного программирования, выполнены исследования устойчивости некоторых задач и процессов их решения, проведена серия вычислительных экспериментов [16−18,26,30,35,42,47.49, 55,84]. Значительное число результатов получено на основе L-разбиения [2, 3,19,35,42−45.47.50,51,57-С1,65.82.83,109.110.127].

В последнее время рассматриваются вопросы применения метода регулярных разбиений в сочетании с унимодулярными преобразованиями [46.89]. которые позволяют улучшить структуру задач и повысить эффективность алгоритмов их решения [18,129]. Выполнен анализ z-алгоритма решения задач ЦЛП [12], в частности исследована его регулярность относительно кубических и других разбиений [55].

В методах отсечений, ветвей и границ, переборе L-классов и других требуется исключить множество точек, находящихся между оптимальными решениями исходной и соответствующей ей непрерывной задач, которое называется дробным накрытием. Множество L-классов. входящих в дробное накрытие, образует L-накрытие задачи. Построение нижних и верхних оценок мощности L-накрытий задач имеет большое значение для анализа сложности их решения рассматриваемыми методами, и в свою очередь позволяет переходить к отысканию оценок числа итераций для указанных классов алгоритмов. Так, с использованием регулярных разбиений удалось построить оценки в среднем числа итераций ряда алгоритмов при решении задачи об упаковке множества и задачи о рюкзаке [34−30,49.70]. Поэтому представляется перспективным дальнейшее развитие и применение данного подхода для исследования задач об упаковке множества.

Целью диссертации является исследование задач об упаковке множества, в том числе с системами ограничений блочной структуры, разработка и анализ алгоритмов их решения на основе Ь-разбиения и лексикографической оптимизации.

Для достижения поставленной цели решались следующие задачи:

1) исследовать математические модели ряда проблем, возникающих при проектировании сложных систем, в частности систем связи с использованием задач об упаковке множества:

2) провести анализ структуры и сложности задач об упаковке множества, включая постановки блочного типа на основе Ь-разбиения, выделить и изучить семейства задач с Ь-накрытиями экспоненциальной мощности:

3) построить и исследовать алгоритмы, основанные на переборе ¿—классов и лексикографической оптимизации для решения рассматриваемых задач:

4) разработать научно-исследовательский вариант комплекса программ для задач об упаковке множества, в том числе с учетом ограничений блочного вида;

5) выполнить экспериментальные исследования предложенных алгоритмов.

Методы исследования. В работе используются фундаментальные положения математического моделирования, аппарат целочисленного программирования, в частности, метод регулярных разбиений и лексикографическая оптимизация, теория разработки программного обеспечения. Достоверность полученных научных результатов основывается на строгих формулировках и доказательствах. подтверждается проведенными вычислительными экспериментами.

Научная новизна. В диссертации продолжены исследования в направлении применения метода регулярных разбиений для анализа и решения задач об упаковке множества, получены новые теоретические и экспериментальные результаты. Проведен анализ задач об упаковке множества с системами ограничений блочной структуры, которые являются математическими моделями проблем, возникающих при проектировании сложных систем, в том числе систем связи, построены семейства и подклассы ЫР-трудных задач с ¿—накрытиями экспоненциальной мощности. Разработаны алгоритмы перебора Ь-классов и лексикографической оптимизации для решения указанных задач. Выполнено исследование предложенных алгоритмов, найдены нижние оценки числа их итераций.

Практическая ценность. Полученные в диссертации результаты представляют ценность в области развития методов целочисленного программирования. Они нашли применение в лаборатории дискретной оптимизации Омского филиала ФГБУН Института математики им. С. Л. Соболева СО РАН в научных исследованиях, в частности для изучения структуры и сложности задач ЦП, при анализе, разработке и тестировании алгоритмов, решении задач об упаковке множества на базе разработанного научно-исследовательского варианта комплекса программ. Кроме того, указанные результаты используются в учебном процессе на кафедре прикладной и вычислительной математики в Омском государственном университете им. Ф. М. Достоевского при подготовке специалистов по методам оптимизации и исследованию операций.

Апробация работы. Результаты диссертации докладывались и обсуждались на следующих конференциях: XXXIII научно-практической студенческой конференции «Молодежь III тысячелетия», (г. Омск. 2009), IV. V Всероссийских конференциях «Проблемы оптимизации и экономические приложения», (г. Омск, 2009, 2012), VII Международной научно-технической конференции «Динамика систем, механизмов и машин», (г. Омск. 2009), Российской конференции «Дискретная оптимизация и исследование операций», (Республика Алтай, 2010),.

XIV Всероссийской конференции «Математическое программирование и приложения», (г. Екатеринбург. 2011). XV Байкальской международной школе-семинаре «Методы оптимизации и их приложения», (г. Иркутск, 2011). Международной конференции «Optimization and Applications ОРТ1МА-2011». (г. Петровац, Черногория. 2011). Международной конференции «Алгебра и линейная оптимизация», посвященной 100-летию С. Н. Черникова (г. Екатеринбург, 2012), па заседании научного семинара лаборатории прикладных систем ФГБУН Института вычислительной математики и математической геофизики СО РАН (Новосибирск, 2013). а также на заседаниях научного семинара «Математическое моделирование и дискретная оптимизация» Омского филиала ФГБУН Института математики им. С. Л. Соболева СО РАН и Института математики и информационных технологий ОмГУ им. Ф. М. Достоевского (Омск, 2009;2013).

Публикации. Основные результаты диссертации опубликованы в 11 научных работах [50.51.57−61.65.82,83,128]. три из них — в журналах из списка ВАК [50,51,57].

Структура и объем диссертации

Диссертация состоит из введения, четырех глав, заключения и списка литературы (144 наименования). Объем диссертации — 129 страниц.

Основные результаты диссертации заключаются в следующем:

1. Проведено исследование задач об упаковке множества с системами ограничений блочной структуры, которые являются математическими моделями ряда проблем, возникающих при проектировании сложных систем, в том числе систем связи, построены семейства и подклассы КР-трудных задач с Ь-накрытиями экспоненциальной мощности.

2. Разработаны гибридные алгоритмы, основанные на переборе Ь-классов и методе лексикографической оптимизации для решения задач об упаковке множества в общей постановке и блочной структуры.

3. Построены нижние оценки числа итераций алгоритмов перебора Ь-классов при решении рассматриваемых задач.

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

5. Выполнены экспериментальные исследования эффективности предложенных алгоритмов для задач об упаковке множества.

Полученные результаты имеют важное значение в области развития методов математического моделирования и целочисленного программирования. Разработанные алгоритмы и комплекс программ могут применяться при исследовании задач об упаковке множества. Кроме того, они могут использоваться для решения прикладных задач.

Заключение

.

Настоящая работа посвящена исследованию и решению задач об упаковке множества на основе моделей целочисленного линейного программирования и теоретико-графовых постановок. Изучение рассматриваемых задач и построение алгоритмов их решения проводилось на основе Ь-разбиения. Особое внимание уделено задачам об упаковке множества с системами ограничений блочной структуры.

Показать весь текст

Список литературы

  1. И.Л., Цурков В. И. Целочисленные оптимизационные модели блочного типа // Математическое моделирование. 1990. — Т. 2, № 2. -С. 39−57.
  2. A.B. Исследование задач максимальной и минимальной выполнимости с использованием L-разбиения // Автоматика и телемеханика. 2004. — № 3. — С. 35−42.
  3. A.B., Кучин А. К. Алгоритмы точного и приближенного решения задачи максимальной выполнимости // Омский научный вестник. 2011. — № 1. — С. 5−9.
  4. М.О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ «Регулярная и хаотичная динамика», 2001. — 288 с.
  5. А.Е., Колоколов A.A., Коробкова З. В. Дискретные задачи производственно-транспортного типа. Новосибирск: Наука, 1978. -160 с.
  6. В.Л. Дискретные задачи размещения и полиномы от булевых переменных. Новосибирск: Изд-во Ин-та математики, 2005. — 408 с.
  7. В.Л., Гимади Э. Х., Дементьев В. Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. — 333 с.
  8. В.П. Методы погружения в задачах оптимизации. -Новосибирск: Наука, 1977. 161 с.
  9. Быкова B.B. FPT-алгоритмы и их классификация на основе эластичности // ПДМ, 2011. № 2. — С. 40−48.
  10. Васильев I4.JI. Метод отсечений для многогранника задачи о рюкзаке // Известия РАН. Теория и системы управления. 2009. -№ 1. — С. 74−81.
  11. И. Васильев И. Л., Климентова К. Б. Метод ветвей и отсечений для задачи размещения с предпочтениями клиентов // Дискретный анализ и исследование операций. 2009. — Т. 16, № 2. — С. 21−41.
  12. A.A. Некоторые вопросы целочисленного программирования / / Экономика и математические методы. -1968. Т. 4, вып. 4. — С. 611−621.
  13. В.Е. Теория вероятностей и математическая статистика. Учебное пособие. М.: Высшее образование, 2006. — 479 с.
  14. О.Н., Колоколов A.A. Решение задач дискретной оптимизации с логическими ограничениями при проектировании сложных изделий // Автоматика и телемеханика. 2008. — № 10. -С. 176−182.
  15. М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.:Мир, 1982. — 416 с.
  16. М.В., Колоколов A.A. Анализ устойчивости некоторых алгоритмов дискретной оптимизации // Автоматика и телемеханика. -2004. № 3. — С. 48−54.
  17. М.В., Колоколов A.A., Колосов А. П. Об одном подходе к решению дискретной задачи планирования производства с интервальными данными // Труды Института математики и механики УрО РАН. 2008. — Т. 14, № 2. — С. 48−57.
  18. М.В., Колоколов A.A., Колосов А. П. Унимодулярные преобразования для задач целочисленного программирования и анализ эффективности их применения // Труды Института математики и механики УрО РАН. 2010. — Т. 16, № 2. — С. 48−62.
  19. М.В., Колоколов A.A., Косарев H.A. Анализ устойчивости по целевой функции некоторых алгоритмов целочисленного программирования // Известия вузов. Математика. -2011. № 4. — С. 23−32.
  20. В.Т., Ерзин А. И., Ларин P.M., Шамардин Ю. В. Задачи оптимизации иерархических структур. Новосибирск: Изд-во НГУ, 1996. — 167 с.
  21. Ю.Г., Посыпкин М. А. Варианты метода неравномерных покрытий для глобальной оптимизации частично-целочисленных нелинейных задач // Доклады Академии наук. Т. 437, № 2. -С. 168−172.
  22. В.А., Ковалев М. М., Кравцов М. К. Многогранники, графы, оптимизация. М.: Наука, 1981. — 344 с.
  23. В.А., Кузьмин К. Г. Анализ чувствительности эффективного решения векторной булевой задачи минимизации проекций линейных функций на R+ и // Дискретный анализ и исследование операций. Серия 2. 2001. — Т. 12. — С. 24−43.
  24. В.А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. — 384 с.
  25. В.А., Подкопаев Д. П. Устойчивость и регуляризация векторных задач целочисленного линейного программирования // Дискретный анализ и исследование операций. Серия 2. 2001. — Т. 8. -С. 47−69.
  26. A.B., Заозерская Jl.А., Колоколов A.A. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискретный анализ и исследование операций. -2000. Т. 7. — № 2. — С. 22−46.
  27. И.И. Теория линейной оптимизации. Екатеринбург: УрО РАН, 1998. — 248 с.
  28. И.И., Мазуров Вл.Д., Скарин В. Д., Хачай М. Ю. Математические методы в экономике. Екатеринбург: УрГУ -Центр «Фактория Пресс», 2000. — 303 с.
  29. Г. И. Пакет программ целочисленного линейного программирования // Дискретный анализ и исследование операций. -1999. Т. 6, № 2. — С. 32−41.
  30. O.A. Нижняя оценка числа итераций для одного алгоритма лексикографической оптимизации // Дискретная оптимизация и численные методы решения прикладных задач. Новосибирск: ВЦ СО АН СССР, 1986. — С. 21−27.
  31. O.A., Колоколов A.A. Вполне регулярные отсечения в булевом программировании // Управляемые системы. 1983. — Вып. 23. — С. 55−63.
  32. Г. Г. О целочисленной постановке одной задачи размещения объектов на линии // Управляемые системы. 1990. — Вып. 30. -С. 35−45.
  33. Г. Г., Лагздин А. Ю. Полиномиальные алгоритмы решения минимаксной квадратичной задачи о назначениях на сетях // Дискретный анализ и исследование операций. 2011. — Т. 18, К5 4. — С. 49−65.
  34. Л.А., Колоколов A.A. О среднем числе итераций некоторых алгоритмов для решения задачи об упаковке множества //
  35. Труды XIV Байкальской международной школы-семинара «Методы оптимизации и их приложения». Иркутск, 2008. — Т. 1. — С. 388−395.
  36. Л.А., Колоколов A.A. Оценки среднего числа итераций для некоторых алгоритмов решения задачи об упаковке множества // ЖВМ и МФ. 2010. — Т. 50, № 2. — С. 242−248.
  37. Л.А., Колоколов A.A., Гофман Н. Г. Оценки среднего числа итераций для алгоритмов решения некоторых задач булева программирования // Дискретный анализ и исследование операций. -2011. Т. 18, № 3. — С. 49−64.
  38. В.М. Метод группировки для решения непрерывной задачи линейного раскроя // Дискретный анализ и исследование операций. -2009. Т. 3, № 16. — С. 47−62.
  39. В.М., Месягутов М. А., Мухачева Э. А., Филиппова A.C. Локальный поиск ортогональных упаковок с использованием нижних границ // Автоматика и телемеханика. 2009. — № 6. — С. 167−180.
  40. М.М. Дискретная оптимизация (целочисленное программирование). Изд. 2-е, стереотипное. М.: Бдиториал УРСС, 2003. — 192 с.
  41. A.A. Методы дискретной оптимизации. Учебное пособие. -Омск: Ом ГУ, 1984. 76 с.
  42. A.A. Применение регулярных разбиений в целочисленном программировании // Известия вузов. Математика. 1993. — № 12. -С. 11−30.
  43. A.A. Регулярные разбиения и отсечения в целочисленном программировании // Сибирский журнал исследования операций. -1994. № 2. — С. 18−39.
  44. A.A., Адельшин A.B., Ягофарова Д. И. Решение задач выполнимости и некоторых ее обобщений с использованием метода перебора L-классов // Прикладная математика и информационные технологии. Омск, 2005. — С. 68−79.
  45. A.A., Адельшин A.B., Ягофарова Д. И. Решение задачи выполнимости с использованием метода перебора L-классов // Информационные технологии. 2009. — № 2. — С. 54−59.
  46. A.A., Девятерикова М. В. Алгоритмы перебора L-классов для задачи о рюкзаке с интервальными данными. Препринт. Омск: Изд-во Ом ГУ, 2001. — 20 с.
  47. A.A., Девятерикова М. В. Задачи целочисленного программирования и унимодулярные преобразования // Труды XIV Байкальской международной школы-семинара «Методы оптимизации и их приложения». Иркутск, 2008. — Т. 1. — С. 111−118.
  48. A.A., Девятерикова М. В., Заозерская JI.A. Регулярные разбиения в целочисленном программировании. Учебное пособие. -Омск: Изд-во Ом ГУ, 2007. 60 с.
  49. A.A., Заозерская JI.A. О среднем числе итераций некоторых алгоритмов для решения задачи об упаковке множества // Труды XIV Байкальской международной школы-семинара «Методы оптимизации и их приложения». Иркутск, 2008. — Т. 1. — С. 388−395.
  50. A.A., Заозерская JI.A. Верхние оценки среднего числа итераций для некоторых алгоритмов решения задачи о рюкзаке // Труды VIII Международной конференции «Дискретные модели в теории управляющих систем». Москва, 2009. — С. 101−106.
  51. A.A., Корбут М. Ф. Исследование одного класса задач об упаковке множества // Вестник Омского университета. 2012. — № 4. -С. 21−26.
  52. A.A., Корбут М. Ф. Решение задачи об упаковке множества с ограничениями блочной структуры // Омский научный вестник. -2013. № 1(117). — С. 29−33.
  53. A.A., Леванова Т. В. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения // Вестник Омского университета. 1996. — № 1. — С. 21−23.
  54. A.A., Леванова Т. В., Федоренко A.C. Исследование декомпозиционного подхода для двухстадийной задачи размещения // Вестник Омского университета. 2010. — № 4(58). — С. 24−31.
  55. A.A., Нагорная З. Е., Гуселетова О. Н., Ярош A.B. Математические модели и программный комплекс для проектирования эскизов одежды // Прикладная математика и информационные технологии. Омск, 2005. — С. 80−98.
  56. A.A., Орловская Т. Г. Исследование одного алгоритма решения задач целочисленного линейного программирования // Труды Института математики и механики УрО РАН. 2010. — Т. 16, № 3. — С. 140−145.
  57. A.A., Орловская Т. Г. О некоторых унимодулярных преобразованиях для задачи о рюкзаке // Труды XV Байкальской международной школы-семинара «Методы оптимизации и их приложения». Иркутск, 2011. — Т. 4. — С. 161−166.
  58. A.A., Орловская Т. Г., Рыбалка М. Ф. Исследование алгоритмов целочисленного программирования с использованием регулярных разбиений и унимодулярных преобразований // Автоматика и телемеханика. -2012. 2. С. 178−190.
  59. A.A., Рыбалка М. Ф. Исследование и решение задачи об упаковке множества блочной структуры // Материалы VII Международной научно-технической конференции «Динамика систем, механизмов и машин». Омск: ОмГТУ, 2009. — Кн. 3. — С. 55−59.
  60. A.A., Рыбалка М. Ф. Анализ и решение одного класса задач об упаковке множества // Материалы Российской конференции «Дискретная оптимизация и исследование операций» Новосибирск: Изд-во Института математики, 2010. — С. 95.
  61. A.A., Рыбалка М. Ф. Анализ алгоритмов перебора L-классов для решения задачи об упаковке множества // XIV Всероссийская конференция «Математическое программирование и приложения»: Информационный бюллетень № 12. Екатеринбург, 2011. — С. 187.
  62. A.A., Тюрюмов А. Н., Ягофарова Д. И. Разработка и экспериментальное исследование алгоритмов решения задач выполнимости и максимальной выполнимости. Препринт. Омск: ОмГУ, 2006. — 19 с.
  63. A.A., Ярош A.B. Автоматизация проектирования сложных изделий с использованием дискретной оптимизации и информационных технологий // Омский научный вестник. 2010. -Т. 90, № 2. — С. 234−238.
  64. A.A., Сигал И. Х., Финкельштейн Ю. Ю. Гибридные методы в дискретной оптимизации // Изв. АН СССР. Техн. кибернетика. -1988. № 1. — С. 65−77.
  65. М.Ф. Решение задач об упаковке множества с использованием последовательной оптимизации и перебора L-классов. Препринт. -Омск: Ом ГУ, 2013. 24 с.
  66. А. Введение в прикладную комбинаторику. М.: Наука, 1975. — 480 с.
  67. Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и приложения. -М.: МГУ, 2001. С. 84−117.
  68. Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. — 432 с.
  69. A.A., Стрекаловский A.C., Цевээндорж И. Об одном подходе к решению целочисленных задач оптимизации // ЖВМ и МФ. 1999. — Т. 39, № 1. — С. 9−16.
  70. H.H. Полиномиальный в среднем алгоритм в целочисленном линейном программировании // Сибирский журнал исследования операций. 1994. — Т. 1, № 3. — С. 38−48.
  71. H.H., Фомин С. А. Эффективные алгоритмы и сложность вычислений. Учебное пособие. М.: МФТИ, 2007. — 312 с.
  72. Д.В., Свириденко A.B., Щербина O.A. Алгоритм выделения блочно-древовидной структуры в разреженных задачах дискретной оптимизации // Таврический Вестник Информатики и Математики. 2012. — № 1(20). — С. 44−55.
  73. В.К. Устойчивость в линейных дискретных задачах // Проблемы кибернетики. 1979. — Вып. 35. — С. 169−184.
  74. М. Математическое программирование. Теория и алгоритмы. -М.: Наука., 1990. 488 с.
  75. B.C., Кукса А. И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. М.: Наука, 1983. — 208 с.
  76. Э.А., Мухачева A.C. Задача прямоугольной упаковки: методы локального поиска оптимума на базе блочных структур // Автоматика и телемеханика. 2004. — № 2. — С. 101−112.
  77. A.B. Квазицелочисленность релаксационного многогранника задачи Вебера / / Труды XI Байкальской международной школы-семинара «Методы оптимизации и их приложения». -Иркутск, 1998. С. 171−174.
  78. X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. — 512 с.
  79. В.К. Математические модели связности // 2-е изд., испр. и доп. Новосибирск: Изд. ИВМиМГ СО РАН. — 2006. — 490 с.
  80. Г. В., Попков В. К., Величко В. В. Математические основы моделирования сетей связи. Учебное пособие. Москва: Горячая линия-Телеком, 2012. — 183 с.
  81. Л.Д. Опыт многоуровневого распараллеливания метода ветвей и границ в задачах дискретной оптимизации // Автоматика и телемеханика, 2007. Вып. 5. — С. 171−181.
  82. М.Ф. Решение некоторых задач об упаковке множества // Труды научно практической студенческой конференции «Молодежь III тысячелетия». — Омск, 2009. — С. 260−261.
  83. М.Ф. Анализ некоторых алгоритмов для задачи об упаковке множества с матрицей блочной структуры // Труды XV Байкальской международной школы-семинара «Методы оптимизации и их приложения». Иркутск, 2011. — Т. 4. — С. 197−202.
  84. Л.А. Исследование мощности ¿--накрытий некоторых задач о покрытии // Дискретная оптимизация и анализ сложных систем. -Новосибирск: ВЦ СОАН СССР, 1989. С. 76−97.
  85. И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наукова думка, 1988. — 472 с.
  86. И.Х., Иванова А. П. Введение в прикладное и дискретное программирование: модули и вычислительные алгоритмы. М.: Физматлит, 2002. — 240 с.
  87. Р.Ю. О вполне регулярных отсечениях для задач целочисленной оптимизации // Управляемые системы. 1990. -Вып. 30. — С. 61−71.
  88. Р.Ю. Выпуклые многогранники и фасетные неравенства. Учебно-методическое пособие. Омск: Изд-во ОмГУ, 1999. — 40 с.
  89. А. Теория линейного и целочисленного программирования: в 2 т. М.:Мир, 1991. — 702 с.
  90. М.Ю. Вычислительная сложность комбинаторных задач, индуцированных коллективными процедурами обучения распознаванию образов // Труды Института математики и механики УрО РАН. 2010. — Т. 16, № 3. — С. 276−284.
  91. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974. — 520 с.
  92. Ю.Ю., Червак О. Ю. Один из способов формулирования парето-лексикографических задач оптимизации // Кибернетика и системный анализ. 1996. — № 1. — С. 108−110.
  93. В.Н. Качественные вопросы целочисленного программирования. М.: Физматлит, 1995. — 190 с.
  94. O.A. О модифицированном локальном алгоритме решения блочных задач дискретного программирования // ЖВМ и МФ. -1986. Т. 26, № 9. — С. 1339−1349.
  95. Balas Е. An Additive Algorithm for Solving Linear Programs with Zero -One Variables // Operations Research. -1965. vol. 3, № 4. -P. 517−546.
  96. Borndorfer R. Aspects of Set Packing, Partitioning, and Covering. PhD thesis, Technische Universitat Berlin, 1998.
  97. Borndorfer R., Schlechte Т. Models for railway track allocation // Technical Report 07−02, Konrad-Zuse-Zentrum fur Informationstechnik Berlin, 2007a.
  98. Borndorfer R., Schlechte Т. Models for railway track allocation // Technical Report 07−02, Konrad-Zuse-Zentrum fur Informationstechnik Berlin, 2007b.
  99. Borndorfer R., Ferreira C.E., Martin A. Decomposing matrices into blocks // SI AM Journal on Optimization. 1998. — № 9. — P. 236−269.
  100. Bron C., Kerbosh J. Algorithm 457 Finding all cliques of an undirected graph // Communications of the ACM. — 1973. — № 16. — P. 575−577.
  101. Caprara M., Fischetti M., Toth P. Modeling and solving the train timetabling problem // Operations Research. 2002. — № 50(5). -P. 851−861.
  102. Chudnovsky M., Cornuejols G., Liu X., Seymour P., Vuskovic K., Cleaning for Bergeness // Technical report, Princeton University, 2003.
  103. Chudnovsky M., Seymour P. Recognizing Berge graphs // Technical report, Princeton University, 2003.
  104. Cornuejols G., Liu X., Vuskovic K. A polynomial algorithm for recognizing perfect graphs // Technical report, Carnegie Mellon University, 2003.
  105. Cramton P., Shoam Y., Steinberg R. Combinatorial Auctions // The MIT press: Cambridge, MA, 2006.
  106. Delorme X., Gandibleux X., Rodriguez J. GRASP for set packing problems // European Journal of Operational Research. 2004. -№ 153(3). — P. 564−580.
  107. Andrade D.V., Resende M., Werneck R.F. Fast local search for the maximum independent set problem // AT&T Labs Research Technical Report TD-7BBST2, 2008.
  108. Dirac G.A. On regid circuit graphs // Anh. Math. Sem. Univ. Hamburg. -1961. № 25. — P. 71−76.
  109. Eremeev A.V., Kolokolov A.A. On Some Genetic and L-class Enumeration Algorithms in Integer Programming // Proceedings of First International Conference on Evolutionary Computation and Its Applications. Moscow, 1996. — P. 297−303.
  110. Eremeev A.V., Kolokolov A.A., Zaozerskaya L.A. A Hybrid Algorithm for Set Covering Problem // Proc. of International Workshop «Discrete Optimization Methods in Scheduling and Computer-Aided Design». -Minsk, 2000. P. 123−129.
  111. Fisher M., Wolsey L. On the Greedy Heuristic for Covering and Packing Problems // SIAM Journal on Algebraic and Discrete Methods. 1982. -№ 3. — P. 584−591.
  112. Fulkerson D.R. Blocking and anti-blocking pairs of polyedra // Mathematical Programming. 1971. — № 1. — P. 168−194.
  113. Fulkerson D.R., Cross O.A. Incidence matrices and interval graphs // Pacific Journal of Mathematics. 1965. — № 15. — P. 835−855.
  114. Gandibleux X., Delorme X., T’Kindt V. An Ant Colony Optimisation Algorithm for the Set Packing Problem // Ant Colony Optimizationand Swarm Intelligence, Lecture Notes in Computer Sciences. 2004. -vol. 3172. — P. 49−60.
  115. Garfinkel R., Nemhauser G.L. Integer Programming // John Wiley and Sons, 1972. P. 302−305.
  116. Gavril F. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph // SIAM Journal on Computing. 1972. — № 1(2). — P. 180−187.
  117. Gavril F. The intersection graphs of subtrees in trees are exactly the chordal graphs // Journal of Combinatorial Theory (Series B). 1974. -№ 16. — P. 47−56.
  118. Gomory R.E. Outline of an algorithm for integer solutions to linear programs // Bulletin of the American Mathematical Society. 1958. -№ 64. — P. 275−278.
  119. Grotschel M., Lovasz L., Schrijver A. Polynomial algorithms for perfect graphs // Annals of Discrete Mathematics. 1984. — № 21. — P. 325−356.
  120. Grotschel M., Lovasz L., Schrijver A. Geometric Algorithms and Combinatorial Optimization. Springer: New York, 1988. — 362 p.
  121. Guo Y., Lim A., Rodrigues B., Zhu Y. Heuristics for a Brokering Set Packing Problem // Proceedings of eighth international symposium on artificial intelligence and mathematics. 2004. — P. 10−14.
  122. Halldorsson M.M., Radhakrishnan J. Greed is Good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs / / Algonthmica. 1997. — Vol. 18. — P. 145−163.
  123. Hoffman K.L., Padberg M. Solving Airline Crew Scheduling Problems by Branch-and-Cut // Management Science. 1993. — Vol. 39, № 6. -P. 657−682.
  124. Ibarra L. Fully dynamic algorithms for chordal graphs // Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms. 1999. -P. 923−924.
  125. Klein P. Efficient parallel algorithms for chordal graphs // SIAM Journal on Computing. 1996. — № 25(4). — P. 797−827.
  126. Kolokolov A.A. On the ?-structure of integer linear programming problems // System Modelling and Optimization: Proceedings of the 16th IFIP conference on the modelling and optimization. Springer Verlag. 1993. — P. 756−760.
  127. Kolokolov A.A., Kosarev N.A. Analysis of decomposition algorithms with Benders cuts for p -median problem //J. Math. Model. Algorithms. -2006. vol. 5, № 2. — P. 189−199.
  128. Krishnamoorthy B., Pataki G. Column basis reduction and decomposable knapsack problems // Discrete Optimization. 2009. — vol. 6, № 3. -P. 242−270.
  129. Land A.H., Doig A.G. An Automatic Method for Solving Discrete Programming Problems // Econometrica. 1960. — № 28. — P. 497−520.
  130. Lusby R., Larsen J., Ryan D., Ehrgott M. Routing Trains Through Railway Junctions: A New Set Packing Approach // Transportation Science. -2011. vol. 45, № 2. — P. 228−245.
  131. Maghout K. Applications de e’Algebre de Bool a la Theorie des Graphes // Cahiers du Centre d’Etudes de Recherche Operationnelle de Bruxelles. -1963. vol. 5. — № 1−2. — P. 21−54.
  132. Martello S., Toth P. Knapsack Problems: Algorithms and Computer Implementation. John Wiley and Sons, 1990. — 308 p.
  133. Nemhauser G.L., Wolsey L.A. Integer and combinatorial optimization // Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. John Wiley and Sons, Inc., New York, 1988. — 763 p.
  134. Padberg M.W. On the facial structure of set packing polyhedra // Mathematical Programming. 1973. — № 5. — P. 199−215.
  135. Padberg M.W. On the complexity of the set packing polyhedra // Annals of Discrete Mathematics. 1975. — № 1. — P. 421−434.
  136. Padberg M.W. Covering, Packing and Knapsack Problems // Annals of Discrete Mathematics. 1979. — № 47. — P. 19−46.
  137. Rebennack S., Oswald M., Theis D.O., Seitz H., Remelt G., Pardalos P.M. A Branch and Cut solver for the maximum stable set problem // Journal of Combinatorial Optimization. 2011. — Vol. 21, № 4. — P. 434−457.
  138. Rose D.J., Tarjan R.E., Lueker G.S. Algorithmic aspects of vertex elimination on graphs // SIAM Journal on Computing. 1976. — № 5(2). -P. 266−283.
  139. Tajima A., Misono S. Using a set packing formulation to solve airline seat allocation/reallocation problems // Journal of the Operations Research Society of Japan. 1999. — Vol. 42, № 1. — P. 32−44
  140. Tarjan R.E., Yannakakis M. Simple linear time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs // SIAM Journal on Computing. 1984. — Vol. 13, № 3. — P. 566−576.
  141. Wan P., Jia X., Yao F. Maximum Weighted Independent Set of Links under Physical Interference Model // Wireless Algorithms, Systems, and
  142. Applications. Lecture Notes in Computer Science. Springer-Verlag, Berlin Heidelberg, 2010. — Vol. 6221. — P. 68−74.
  143. Wilcoxon F. Individual comparisons by ranking methods // Biometrics Bulletin. 1945. — Vol. 1, № 6. — P. 80−83.
  144. Yildirim E.A., Fan-Orzechowski X. On Extracting Maximum Stable Sets in Perfect Graphs Using Lovdsz’s Theta Function // Computational Optimization and Applications. 2006. — № 33. — P. 229−247.
Заполнить форму текущей работой

На отлично!