Помощь в учёбе, очень быстро...
Работаем вместе до победы

Исследование устойчивости задач и алгоритмов целочисленного программирования на основе регулярных разбиений

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

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

Содержание

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

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

Диссертация посвящена исследованию устойчивости задач и алгоритмов целочисленного программирования (ЦП), а также разработке алгоритмов для решения задач ЦП с интервальными исходными данными. В частности, рассмотрены задачи выпуклого целочисленного и булева программирования и некоторые специальные задачи целочисленного линейного программирования.

К задачам целочисленного программирования сводятся многие задачи, возникающие в экономике, управлении, планировании и других областях [45, 55, 57, 61, 68, 71]. Условие целочисленности позволяет учесть такие факторы как неделимость объектов, наличие альтернатив, дискретность процессов и т. д.

В настоящее время в целочисленном программировании развиваются такие направления как исследование структуры и сложности решения задач, теория двойственности, устойчивость решений, многокритериальные задачи, полиэдральный подход, методы отсечения, ветвей и границ, декомпозиции, множителей Лагранжа, приближенные и гибридные алгоритмы. Этим вопросам посвящены многие статьи и монографии [2−6, 20, 23, 26−28, 39, 40, 45−47, 55−57, 61, 62, 68, 69, 71, 82, 93, 94].

Значительная часть методов решения задач ЦП основана на использовании релаксационных множеств, дополнительных линейных ограничений (отсечений) и аппарата непрерывной оптимизации. Релаксационное множество задачи ЦП определяется системой ограничений, получающейся из исходной путем исключения условия целочисленности. В процессе решения задачи оно последовательно изменяется с помощью вводимых дополнительных линейных ограничений до получения оптимального решения или другого требуемого результата.

Важную роль в исследовании задач и алгоритмов ЦП играет дробное накрытие, которое является подмножеством релаксационного множества задачи. Оно состоит из всех точек релаксационного множества, лежащих между лексикографически оптимальными решениями задачи ЦП и соответствующей ей «непрерывной» задачи. «Объем» дробного накрытия определяет сложность решения задачи ЦП алгоритмами отсечения и некоторыми другими методами, основанными на непрерывной оптимизации.

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

Исследования устойчивости в дискретной оптимизации охватывают широкий круг вопросов, в том числе:

— определение и изучение областей устойчивости [31, 72−74];

— получение необходимых и достаточных условий устойчивости [1, 8, 30, 32, 36, 37, 54, 63, 84];

— вычисление и оценки радиусов устойчивости [3, 7, 20, 49, 50−54, 66, 67];

— построение алгоритмов нахождения радиуса устойчивости, оценки их сложности [2−6, 83];

— возможность покрытия любого шара в пространстве исходных данных шарами устойчивости [67];

— регуляризация неустойчивых задач [22, 38];

— параметрический анализ и разработка алгоритмов для задач с интервальными данными [34, 58, 59, 62, 64, 78, 88, 89].

В связи с указанной проблематикой представляют интерес исследования вопросов устойчивости в области непрерывной оптимизации, например, [25, 48, 62].

Во многих работах, посвягценых устойчивости задач дискретной оптимизации, рассматривается устойчивость задач целочисленного линейного программирования [54, 56, 70, 72, 74, 77, 92], а также устойчивость траекторных задач [1−7, 49−53, 83]. Значительная часть работ посвящена устойчивости многокритериальных (векторных) задач целочисленного программирования [8, 17−21, 30, 32, 36−38, 63, 84]. Вместе с тем ряд важных вопросов до последнего времени был недостаточно изучен. Один из них — устойчивость релаксационных множеств, в том числе дробных накрытий задач ЦП.

В диссертации развивается новый подход к исследованию устойчивости задач целочисленного программирования, основанный на методе регулярных разбиений. Указанный метод был предложен А.А. Колоко-ловым для исследования свойств задач ЦП, построения и анализа алгоритмов, связанных с релаксацией условия целочисленности. С использованием этого подхода исследуется сложность решения задач, изучается структура релаксационных множеств, вводятся и исследуются новые классы отсечений, строятся оценки числа итераций для ряда известных алгоритмов решения задач целочисленного программирования, разрабатываются новые алгоритмы [26, 27, 39, 40, 44, 65, 82, 87]. Значительное число результатов получено на основе L-разбиения, в частности, предложен метод перебора L-классов для решения задач целочисленного программирования. В последнее время найдены новые возможности применения метода регулярных разбиений — исследование вопросов устойчивости [9, 11−14, 41, 42, 79, 80, 85, 86]. Этот метод позволяет получить результаты не только об устойчивости решений и структуры задач ЦП, но и об устойчивости некоторых алгоритмов при изменении исходных данных.

Под устойчивостью задачи ЦП относительно некоторого регулярного разбиения пространства Rn мы будем понимать не более чем полиномиальный по отношению к размерности пространства рост мощности регулярного разбиения релаксационного множества задачи при достаточно малых «допустимых» изменениях этого множества. Наряду с понятием «устойчивость задачи» мы также будем использовать выражение «устойчивость регулярного разбиения релаксационного множества». Аналогично под устойчивостью алгоритмов понимается не более чем полиномиальный по отношению к размерности пространства рост числа итераций при достаточно малых изменениях релаксационного множества задачи.

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

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

Диссертация состоит из введения, трех глав и заключения.

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

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

2. Проведено исследование устойчивости указанных задач целочисленного программирования относительно L-разбиения, кубических и ряда других регулярных разбиений.

3. Построены верхние оценки числа итераций для некоторых алгоритмов отсечения и перебора L-классов при малых изменениях релаксационных множеств задач целочисленного программирования, из которых вытекает устойчивость указанных алгоритмов.

4. Разработаны алгоритмы перебора L-классов для задач ЦП с интервальными данными. Предложены алгоритмы приближенного решения, основанные на вариации релаксационного множества задачи. Проведено экспериментальное исследование этих алгоритмов на многомерной задаче о рюкзаке, которое показало целесообразность использования предложенного подхода.

Заключение

.

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

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

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

  1. JI.T. Об устойчивости приближенных решений задач маршрутной оптимизации / / Алгоритмы и программные средства параллельных вычислений. 1999. — N 3. — С. 16−33.
  2. Э.П. Полиномиальные алгоритмы вычисления радиуса устойчивости для двух классов задач выбора // Докл. АН СССР. 1987. — Т. 297, N 5. — С. 1040−1043.
  3. Э.Н. Алгоритмический и постоптимальный анализ устойчивости решений задач дискретной оптимизации: Дис.. д-ра физ.-мат. наук. М.: ВЦ АН СССР — 1992. — 247 с.
  4. Э.Н. Об устойчивости задач на узкие места // ЖВМ и МФ. 1993. — Т. 33, N 9. — С. 1391−1402.
  5. Э.Н., Леонтьев В. К. Траекторные параметрические задачи // ЖВМ и МФ. 1984. — Т. 24, N 1. — С. 37−46.
  6. Э.Н., Леонтьев В. К. Об оценках сложности табулирования траекторных задач // ЖВМ и МФ. 1985. — Т. 25, N 8.1. С. 1272−1275.
  7. Э.Н., Леонтьев В. К. Общий подход к исследованию устойчивости решений в задачах дискретной оптимизации // ЖВМ и МФ. 1996. — Т. 36, N 1. — С. 66−72.
  8. В.В., Рачковский Н. Н. Об устойчивости задач векторной оптимизации // Вестник АН БССР. Серия физ.-мат. наук. -1990. N 2. — С. 3−8.
  9. М.В. Об устойчивости L-накрытий задач булева программирования // Международная конференция «Дискретный анализ и исследование операций»: Тезисы докладов. Новосибирск, 2000. С. 145.
  10. М.В. Анализ устойчивости L-структуры задач булева программирования // Вестник Омского университета. Омск, 2001. N 1. — С. 15−17.
  11. М.В., Колоколов А. А. Об устойчивости дробных накрытий задач целочисленного программирования// Международная конференция «Проблемы оптимизации и экономические приложения»: Тезисы докладов. Омск, 1997. — С. 59−61.
  12. М.В., Колоколов А. А. Об устойчивости L-структуры задач целочисленного программирования // Международная конференция «Дискретный анализ и исследование операций»: Тезисы докладов. Новосибирск, 1998. — С. 63.
  13. М.В., Колоколов А. А. Устойчивость L-структуры задач целочисленного выпуклого программирования // Вестник Омского университета. Омск, 2000. — N 1. — С. 21−23.
  14. М.В., Колоколов А. А. Об одном алгоритме перебора L-классов для задачи о рюкзаке с интервальными данными // Всероссийская конференция «Алгоритмический анализ неустойчивых задач»: Тезисы докладов. Екатеринбург, 2001. — С. 207.
  15. М.В., Колоколов А. А. Алгоритмы перебора L-классов для задачи о рюкзаке с интервальными данными. // Препринт. Омск: ОмГУ, 2001. — 20 с.
  16. В.А., Кравцов М. К., Подкопаев Д. П. О радиусе квазиустойчивости многокритериальной траекторной задачи // Доклады АН Беларуси. 1996. — Т. 40, N 1. — С. 9−12.
  17. В.А., Кричко В. Н. О радиусе устойчивости паретовско-го оптимума векторной задачи булева программирования // Известия Академии наук республики Молдова. 1999. — N 1. — С. 79−84.
  18. В.А., Никулин Ю. В. Условия сильной квазиустойчивости векторной линейной траекторной задачи // Доклады АН Беларуси. Сер. физ.-мат. наук. — 2000. — N 2. — С. 38−41.
  19. В.А., Перепелица В. А. Сложность линейных многокритериальных задач // Дискретная математика. 1994. — Т. 6., вып. 1. — С. 3−33.
  20. В.А., Подкопаев Д. П. О количественной мере устойчивости векторной задачи целочисленного программирования // ЖВМ и МФ. 1998. — Т. 38, N 11. — С. 1801−1805.
  21. В.А., Янушкевич О. А. О регуляризации многокритериальной задачи целочисленного линейного программирования // Известия вузов. Математика. 1999. — N 1. — С. 38−42.
  22. А.В. Генетический алгоритм для задачи о покрытии // Дискретный анализ и исследование операций. 2000. — Сер. 2. Т. 7. N 1. — С. 47−60.
  23. И.И. Теория линейной оптимизации. Екатеринбург: УрО РАН, 1998. — 248 с.
  24. И.И. Общая теория устойчивости в линейном программировании // Известия вузов. Математика. 1999. — N 12. — С. 43−52.
  25. О.А. Нижняя оценка числа итераций для одного алгоритма лексикографической оптимизации// Дискретная оптимизация и численные методы решения прикладных задач. Новосибирск: ВЦ СО АН СССР, 1986. — С. 21−27.
  26. JI.A. Исследование и решение некоторых классов задач целочисленного программирования на основе регулярных разбиений: Автореф. дис. канд. физ.-мат. наук. Омск, 1998. — 16 с.
  27. В.П. Оценка точности алгоритма жадного спуска для задачи минимизации супермодулярной функции // Дискретный анализ и исследование операций. 1998. — Сер. 1. Т. 5. N 4. — С. 45−60.
  28. В.М. Устойчивость решений комбинаторных оптимизационных задач // Автоматика и вычислительная техника. 1987. -N 2. — С. 42−50.
  29. М.Г. Об устойчивости линейной задачи многокритериальной оптимизации // ЖВМ и МФ. 1987. — Т. 27, N 2.1. С. 178−188.
  30. JI.H. Области устойчивости одной задачи целочисленного программирования // Докл. АН УССР. Сер. А. — 1985.1. N 2. С. 57−60.
  31. Л.Н. Задачи векторной оптимизации: устойчивость в пространстве решений и в пространстве альтернатив // Кибернетика и системный анализ. 1994. — N 6. — С. 122−133.
  32. Л.Н., Лебедева Т. Т., Сергиенко И. В. Вопросы устойчивости, параметрический и постоптимальный анализ задач дискретной оптимизации // Кибернетика. 1983. — N 4 — С. 83−92.
  33. Л.Н., Лебедева Т. Т., Сергиенко И. В. Исследование задач дискретной оптимизации // Кибернетика и системный анализ. 1993. — N 3. — С. 78−93.
  34. Л.Н., Лебедева Т. Т., Сергиенко И. В. Задачи дискретной оптимизации: исследование устойчивости // Обозрение прикладной и промышленной математики. 1995. — N 1.
  35. Л.И., Лебедева Т. Т., Сергиенко Т. В. Необходимые и достаточные условия устойчивости многокритериальных задач целочисленного программирования // Докл. АН УССР. Сер. А. -1988. N 19. — С. 76−78.
  36. Л.Н., Лебедева Т. Т., Сергиенко Т. В. Задача частично-целочисленной векторной оптимизации: вопросы устойчивости // Кибернетика. 1991. — N 1. — С. 58−61.
  37. Л.Н., Лебедева Т. Т., Сергиенко Т. В. О регуляризации задач целочисленной векторной оптимизации // Кибернетика.1993. N 3. — С. 172−176.
  38. А.А. Регулярные разбиения в целочисленном программировании // Методы решения и анализа задач дискретной оптимизации. Омск: ОмГУ, 1992. — С. 67−93.
  39. А.А. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журнал исследования операций.1994, N 2. С. 18−39.
  40. А.А., Девятерикова М. В. Регулярные разбиения и устойчивость задач целочисленного программирования // Информационный бюллетень Ассоциации математического программирования. Екатеринбург: УрО РАН, 1999. — N 8. — С. 161−162.
  41. Колоколов А. А, Девятерикова М. В. Анализ устойчивости L-раз-биения множеств в конечномерном пространстве // Дискретный анализ и исследование операций. Новосибирск, 2000. — Сер. 2,1. Т. 7, N 2. С. 47−53.
  42. А.А., Заозерская JI.A. Регулярные разбиения и лексикография: Учебно-методическое пособие. Омск: ОмГУ, 1999. -31 с.
  43. А.А., Леванова Т. В. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения // Вестник Омского университета. Омск: ОмГУ, 1996. — N 1. — С.21−23.
  44. А.А., Финкелыптейн Ю. Ю. Дискретное программирование. М.: Наука, 1969. — 368 с.
  45. Ю.А. Вероятностные алгоритмы локального поиска для задач дискретной оптимизации // Международная конференция «Дискретный анализ и исследование операций»: Материалы конференции. Новосибирск, 1998. — С. 21−24.
  46. А.А., Стрекаловский А. С., Цевээндорж И. Об одном подходе к решению целочисленных задач оптимизации // ЖВМ и МФ. 1999. — Т. 39, N 1. — С. 9−16.
  47. В.И. Задачи нелинейной оптимизации с интервальными параметрами // Информационные технологии. 2000. — N 1.1. С. 15−19.
  48. В.К. Устойчивость задачи коммивояжера // ЖВМ и МФ. 1975. — Т. 15, N 5. — С. 1293−1309.
  49. В.К. Устойчивость в комбинаторных задачах выбора // Докл. АН СССР. 1976. — Т. 228, N 1. — С. 23−25.
  50. В.К. Устойчивость в линейных дискретных задачах // Проблемы кибернетики. М.: Наука, 1979. Вып. 35. — С. 169−184.
  51. В.К. Устойчивость решений в линейных экстремальных задачах: Дис.. д-ра физ.-мат. наук. М.: ВЦ АН СССР, 1981. -228 с.
  52. В.К., Гордеев Э. Н. Качественное исследование траектор-ных задач // Кибернетика. 1986. — N 5. — С. 82−89, 105.
  53. В.К., Мамутов К. Х. Устойчивость решений в задачах линейного булева программирования // ЖВМ и МФ. 1988.
  54. Т. 28, N 10. С. 1475−1481.
  55. В.Д. Метод комитетов в задачах оптимизации и классификации. М.: Наука. 1990. — 248 с.
  56. Математическая оптимизация: вопросы разрешимости и устойчивости // Под ред Е. Г. Белоусова, Б. Банка. М.: МГУ, 1986. -216 с.
  57. X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. 512 с.
  58. В.А., Семенова Н. В., Сергиенко И. В. Вопросы решения и исследования одного класса задач неточного целочисленного программирования // Кибернетика. 1989. — N 2. — С. 42−47.
  59. В.А., Семенова Н. В., Сергиенко И. В. Декомпозиционный подход к решению некоторых задач целочисленного программирования с неточными данными // ЖВМ и МФ. 1990. — Т. 30, N 5. -С. 786−791.
  60. Н.В. Решение одной задачи обобщенного целочисленного программирования // Кибернетика. 1984. — N 5. — С. 25−31.
  61. И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наукова думка, 1988. — 472 с.
  62. И.В., Козерацкая JI.H., Лебедева Т. Т. Исследование устойчивости и параметрический анализ дискретных оптимизационных задач. Киев: Наукова думка, 1995. — 170 с.
  63. Т.И. Об устойчивости по ограничениям многокритериальной задачи целочисленного программирования // Докл. АН УССР. Сер. А. 1989. — N 3. — С. 79−81.
  64. И.В., Семенова Н. В. Задачи целочисленного программирования с неоднозначно заданными данными: точные и приближенные решения // Кибернетика и системный анализ. 1995.1. N 6. С. 75−86.
  65. Р.Ю. О вполне регулярных отсечениях для задач целочисленной оптимизации // Управляемые системы. Новосибирск: ИМ СО АН СССР, 1990. — Вып. 30. — С. 61−71.
  66. Ю.Н. Радиус устойчивости е-приближенного решения булевой задачи минимизации линейной формы // Препринт N 21. -Минск: Институт техн. кибернетики АН Белоруси, 1991. 28 с.
  67. Ю.Н. Исследование устойчивости приближенного решения булевой задачи минимизации линейной формы // ЖВМ и МФ. 1993. — Т. 33, N 5. — С. 785−795.
  68. А. Теория линейного и целочисленного программирования. Т. 2. М.: Мир. 1991. — 342 с.
  69. B.C., Сотсков Ю. Н., Струсевич В. А. Теория расписаний. Многостадийные системы. М.: Наука, 1989. — 328 с.
  70. С.М. Исследование устойчивости транспортных задач // ЖВМ и МФ. 1978. — Т. 18, N 1. — С. 235−240.
  71. В.Н. Качественные вопросы целочисленного программирования. М.: Физмат лит. — 1995. — 190 с.
  72. Bank В. Stability analysis in pure and mixed integer linear programming // Lecture notes in control and inf. sci. 1980.1. N 23. P. 148−153.
  73. Bank В., Hansel R. Stability of mixed-integer quadratic programming problems // Math. Progr. Study. 1984. — N 21.
  74. Bank В., Mandel R. Quantitative stability of (mixed) integer linear optimization // Lect. Notes Econ. Math. Syst. 1988. — N 304, P. 3−15.
  75. Blair С. E., Jeroslow R.G. The value function of an integer program: II // Discr. Math. 1979. — Vol. 25, N 1. — P. 28−47.
  76. Blair C.E., Jeroslow R.G. Computational complexity of some problems in parametric discrete programming. I // Math. Oper. res. 1986. -N 11, P. 241−250.
  77. Cook W., Gerards A.M.H., Schrijver A., Tardos E. Sensitivity theorems in integer linear programming // Math. Progr. 1986. -Vol. 34, N 3. — P. 251−264.
  78. Cooper A.W. Postoptimality analysis in nonlinear integer programming the right-hand side case // Nav. Res. Log. Quart. 1981.-Vol. 28, N 2. — P. 301−307.
  79. Devyaterikova M.V., Kolokolov A.A. On L-structure stability of integer convex programming problems // International Conference on Operations Research: Abstracts. Dresden, 2000. — P. 37.
  80. Devyaterikova M.V., Kolokolov A.A. Analysis of L-structure stability of convex integer programming problems // Operations Research Proceedings, Springer, 2000. P. 49−54.
  81. Devyaterikova M.V., Kolokolov A.A. L-class enumeration algorithms for knapsack problem with interval data // International Conference on Operations Research: Book of Abstracts. Duisburg, 2001. — P. 118.
  82. Eremeev A.V., Kolokolov A.A. On Some Genetic and L-class Enumeration Algorithms in Integer Programming // Proc. of the First International Conference on Evolutionary Computation and Its Applications. Moscow, 1996. — P. 297−303.
  83. Gordeev E., Leontev V. Polynomial algorithms for stability analysis // International Conference on Operations Research: Abstracts. -Dresden, 2000. P. 36.
  84. Iacob P. The solution of the pareto optimization problems in decision space and in the objective space, stability properties // Proc. Colloq. Approximation and Optimization Clui-Napoca. — 1984. — P. 254−259.
  85. Kolokolov A.A., Devyaterikova M.V. On stability of L-structure of integer programming problems // International Conference on Operations Research: Abstracts. Zurich, 1998. — P. 52−53.
  86. Kolokolov A.A., Devyaterikova M.V. Analysis of L-structure stability of a knapsack problem // International Conference «Combinatorial Optimization 2000»: Abstracts. England, Greenwich, 2000. — P. 8.
  87. Kolokolov A.A., Eremeev A.V., Zaozerskaya L.A. On Hybrid L-class Enumeration and Genetic Algorithm for Set Covering Problem // 15-th Conference of International Federation of Operational Research Societies (IFORS'99): Abstracts. Pekin, 1999. — P. 117.
  88. Libura M. Integer programming problems with inexact objective function // Contr. and Cybern. 1980. — Vol. 9, N 4. — P. 189−202.
  89. Non-linear parametric optimization / B. Bank, J. Guddat. J. Klatte at all. // Berlin: Akad.-Verlag. 1982. — 226 p.
  90. Seelander J. Einige Bemerkungen zur Bestimmung von Stabilitatsbereichen in der reinganzzahligen linearen Optimierung // Math. Operationsforsch. und Statist., Ser. Optimiz. 1980. — 11, N 2.- S. 261−271.
  91. Sensivity, stability and parametric analysis // Math, program, study.- 1984. Vol. 21, N 1−6. — P. 1−242.
  92. Sturmfels В., Thomas R.R. Variation of cost functions in integer programming // Math. Prog. 1997. — Vol. 77, N 3. — P. 357−387.
  93. Vazirani V.V. Approximation algorithms. Springer. — 2001. — 378 p.
  94. Zhang L.S., Gao F., Zhu W.X. Nonlinear integer programming and global optimization //J. Comput. Math. 1999. — Vol. 17, N 2.1. P. 179−190.
Заполнить форму текущей работой

Пора сдавать?