автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Разработка и анализ алгоритмов целочисленного линейного программирования с использованием L-разбиения

804607740

4 г-

КОЛОСОВ Антон Павлович

РАЗРАБОТКА И АНАЛИЗ АЛГОРИТМОВ ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ

^РАЗБИЕНИЯ

05.13.18 — Математическое моделирование, численные методы и комплексы

программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

- 2 СЕН 2010

Омск - 2010

004607740

Работа выполнена в Учреждении Российской академии наук, Омском фили але Института математики им. С.Л. Соболева Сибирского отделения РАН

Научный руководитель:

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

Колоколов Александр Александрович

Официальные оппоненты:

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

Дементьев Владимир Тихонович, кандидат технических наук, с.н.с.

Забиняко Герард Идельфонович

Ведущая организация:

Учреждение Российской академии наук, Институт математики и механики УрО РАН

Защита состоится 28 сентября 2010 г. в 1630 часов на заседании диссертационного совета Д 003.061.02 при Учреждении Российской академии наук, Институте вычислительной математики и математической геофизики Сибирского отделения Российской академии наук по адресу: проспект Академика Лаврентьева, 6, г. Новосибирск, 630090, Россия.

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук, Институте вычислительной математики и математической геофизики Сибирского отделения Российской академии наук.

Автореферат разослан _"_2010 г.

Ученый секретарь диссертационного совета д.ф.-м.н.

С.Б. Сорокин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Исследование и решение многих задач, возникающих в экономике, планировании, технике и других областях, ввиду их сложности осуществляется на основе математического моделирования, в том числе с использованием аппарата целочисленного линейного программирования (ЦЛП). Условие целочисленности позволяет учесть такие факторы, как неделимость объектов, дискретность процессов, наличие альтернатив, фиксированные доплаты и ряд других. Значительный интерес к задачам целочисленного программирования обусловлен их Л/"7?-трудностыо.

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

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

Значительный вклад в развитие этих направлений внесли работы известных учёных - А. Е. Бахтина, В. Л. Береснева, В. П. Булатова, Э. X. Ги-мади, В. Т. Дементьева, В. А. Емеличева, И. И. Ерёмина, Г. И. Забиняко,

A. А. Корбута, H. Н. Кузюрина, В. К. Леонтьева, В. Д. Мазурова, Э. А. Муха-чёвой, В. К. Попкова, И. В. Сергиенко, И. X. Сигала, Ю. Ю. Финкельштейна, М. Ю. Хачая, Ю. Ю. Червака, В. Н. Шевченко, Ж. Бендерса, Ф. Гловера, Р. Гомори, Р. Джерослоу, А. Дойг, Э. Лэнд, Дж. Немхаузера, А. Схрейвера,

B. Хватала, Д. Эдмондса, Р. Юнга и других.

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

С теоретической точки зрения указанные алгоритмы по некоторым на-

^ \ -, ■

3 V

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

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

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

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

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

4. Разработать алгоритмы перебора Ь - классов для решения дискретной задачи планирования производства в стандартной и интервальной постановках.

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

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

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

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

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

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

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

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

4. Создано программное обеспечение, в котором реализованы рассматриваемые алгоритмы, проведены экспериментальные исследования, в том числе на тестовых задачах из известной электронной библиотеки СЖ-ЫЬгагу, показавшие перспективность предложенных алгоритмов.

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

Апробация работы. Результаты диссертации докладывались на XXIX Региональной научной студенческой конференции ОмГУ «Молодежь третьего тысячелетия» (Омск, 2005), III Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 2006), XIII Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 2007), IV Всероссийской научной молодежной конференции «Под знаком Сигма» (Омск, 2007), Российской конференции «Дискретная оптимизация и исследование операций» (Владивосток, 2007), VI Международной научно-технической конференции «Динамика систем, механизмов и машин» (Омск, 2007), XIV Байкальской международной школе-семинаре (Иркутск-Северобайкальск, 2008), а также на научных семинарах в Омском филиале Института математики им. С.Л. Соболева СО РАН, Омском государственном университете им. Ф. М. Достоевского (2005-2010) и Институте вычислительной математики и математической геофизики СО РАН.

Публикации. Основные результаты диссертации опубликованы в 10 научных работах [1-Ю], три из них - в изданиях из списка ВАК.

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

В п. 1.1 рассматривается модель ЦЛП для задачи планирования производства выпуска неделимой продукции. Пусть с^ - прибыль, получаемая от реализации единицы ¿-Л продукции, 3 = 1, ..., щ - доступное количество г-го ресурса, г = 1, ..., т\ а^ - расход г-го ресурса на выпуск единицы ^'-й продукции г = 1, ..., т, у = 1, ..., га. Переменные задачи: х^ - объём выпуска ]-ж продукции, 7 = 1, ..., п. Задача ЦЛП имеет вид:

ТЬ

/ (х) = ^ с^х^ —» тах (1)

.7=1

при условиях п

-Ь'<' г = 1' ■■■' т> (2)

3=1

Хз > о, з = 1, ..., п, (3)

х^еЪ, з = \, п. (4)

Здесь су, Ьг, € К, г = 1, ..., т, з = 1, ..., п, Ъ - множество всех целых чисел, х = (х\,..., х„).

Далее формулируется задача планирования производства с интервальными данными в правой части системы ограничений. Обозначим через М(Ъ) множество, определяемое неравенствами (2), (3), Ь = (61,..., Ьт).

Предположим, что объемы имеющихся ресурсов изменяются в интервалах, ограниченных величинами Ь^ и 6,-, где 0 < Ь{ < 6;, г = 1,..., т. Интервальная задача состоит в отыскании точки г* б 2", удовлетворяющей условиям:

1) г* е М(Ь); 2) /(г*) > /(г) для всех г е М(Ь) П Ъп (см. Рис. 1).

Для исследования алгоритмов ЦЛП нами используется задача поиска некоторой целочисленной точки выпуклого многогранного множества

М = | х € К" : £ Оу-я, < Ьи г = 1,..., т, X] > 0, 3 = 1,..., п |.

Рис. 1: Геометрическая интерпретация для задачи с интервальными данными в правой части ограничений.

С целью решения этой задачи применяется постановка: найти лексикографически максимальную точку множества М П 2™, т.е.

2* = 1ехтах{МПЖп). (5)

Множество М> = {х : х £ М, х У г \/г £ М П Ъп} называется дробным накрытием задачи (5)..Во многих алгоритмах решения задач ЦЛП для нахождения оптимального решения дробное накрытие должно быть полностью удалено. «Объем» дробного накрытия может использоваться в качестве показателя сложности задачи.

В п. 1.2 дается определение Ь - разбиения и указывается ряд его свойств, которые используются при исследовании задач и алгоритмов. Это разбиение можно определить следующим образом. Каждая целочисленная точкам £ Ъп образует отдельный класс. Нецелочисленные точки х, у £ К™ (х У у) принадлежат одному классу, если они не являются отделимыми, т.е. не существует г £ И1, для которой х У г У у. Такой Ь-класс будет называться дробным. Здесь >— символ лексикографического сравнения. Разбиение произвольного множества X на ¿-классы называется Ь-структурой этого множества и обозначается Х/Ь. Множество Мщ/Ь называется Ь - накрытием задачи.

Пусть X, X — непустые множества в К". Будем говорить, что X лексикографически больше Х (Х У X'), если х У х для любого х £ X и любого х £ X'. Это отношение является линейным порядком для фактор-множества Х/Ь. Отсюда вытекает, что если X — ограничено, то Х/Ь можно записать следующим образом:

Х/Ь = {Уи...,Ур}, ЦуУш, 1 =

В п. 1.3 описаны базовый алгоритм перебора Ь - классов и лексикографический двойственный симплекс-метод (ЛДСМ) для решения задачи линейного программирования (ЛП), который используется в исследуемых алгоритмах.

Метод перебора Ь - классов предложен для решения задачи ЦЛП в следующей постановке:

/(х) -> тах, х е (М П Ъп), (6)

где М - выпуклое многогранное множество, определяемое системой (2)-(3).

Основной шаг алгоритма заключается в переходе от одного Ь - класса релаксационного множества М к следующему за ним в порядке лексикографического убывания с учетом рекордного значения целевой функции. Алгоритм порождает' последовательность 5 точек х^ 6 М, обладающую свойствами:

1. =

2. Все точки х^ принадлежат различным Ь - классам.

3. Если М П 2" / 0, то последовательность 5 содержит подпоследовательность целых точек <3 = {г^*к\к — 1,...,д} такую, что /(г(4>) > ¡{г^) как только Ь > ¿л-

Процесс перебора Ь - классов можно начинать с лексикографически максимальной точки € М, если она существует. Текущие точки х^ строятся посредством решения вспомогательных подзадач ЛП. Поиск лексикографического максимума для этих задач может быть осуществлен, например, с помощью ЛДСМ или последовательной оптимизации. Алгоритм завершает работу, когда не удается найти очередной Ь - класс. В случае, если задача разрешима, лучшее из найденных целочисленных решений является оптимальным. Если множество М ограничено, то за конечное число шагов алгоритм либо находит оптимум, либо устанавливает, что задача не имеет решения.

В используемом нами варианте ЛДСМ система уравнений, соответствующая задаче (1)-(4), представлена в матричной форме:

(7)

где х — (хо, XI,..., хп+т)Т, = (1, -х\,..., -хп)т. Начальная симплексная таблица, соответствующая матрице имеет вид

1 -XI ~Х2 хп

Хо 0 -С2 -Сп

XI 0 -1 0 0

х-1 0 0 -1 0

0 0 0 -1

Ъу ап «12 аы

Ьщ ат1 ат 2 тп

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

Пусть х £ - оптимальное решение задачи ЛП (1)-(3). Предположим, что х 2", 7 е К", 7 т^ 0, 7о 6 К. Линейное неравенство

Ь,х) <70 (8)

называется правильным отсечением, если (7, £) > 70 и (7, г) < 70 для всех г€ МП Ъп.

Нами исследуется основанный на ЛДСМ первый алгоритм Гомори (алгоритм О}) с отсечениями вида:

п

где {а} - дробная часть числа а, р — тт{г : {а.;о} ^ 0, г = 0,1,..., п + т}.

В п. 1.5 приводятся сведения об унимодулярных преобразованиях. Пусть х 6 25". Рассмотрим преобразование у = их, где V — (щ), щ 6 2, ■¿,7 = 1, .... п. Матрица V называется унимодулярной, если с1е(;£/ = ±1. Унимодулярные преобразования применяются при исследовании релаксационных множеств задач. Кроме того, их использование позволяет сокращать мощность Ь - накрытий и ускорять алгоритмы.

В главе 2 рассматриваются предложенные нами семейства задач ЦЛП, при решении которых число итераций алгоритма С?', алгоритма перебора Ь - классов и алгоритма ЬБ экспоненциально зависит от длины входа.

Вп. 2.1 исследуются семейства трудных задач К\ (а), /¡^(а), К"(а), К^а) и показывается, что их решение существенно облегчается, если предварительно использовать унимодулярные преобразования.

Семейство К: (а) имеет вид:

/(х) = х\ —> шах

при условиях

— (а — 1).Т1 + ах 2 < О

ах\ — (а — 1)ж2 < а

х\ > 0, > 0 - целые,

где а > 2 - целочисленный параметр.

Нами изучаются ¿-накрытия лексикографических задач следующего семейства Кх(а):

найти г* = 1ехтах(М1 (а) П Zu),

где М1 (а) - многогранники задач семейства К\(а). Введем функцию (а):

, , (а, если а - четное,

[ а - 1 - в противном случае.

Теорема 2.1 Мощность Ь-накрытия любой задачи семейства К\{а) равна <р(а).

Из этой теоремы непосредственно вытекает, что число итераций алгоритма ЬСЕ, требуемых для решения задач семейства К\(а), равно <£>(а)-

Пусть /д - число итераций некоторого исследуемого алгоритма А. Для алгоритма С} задачи семейства К\(а) также являются трудными, на что указывает

Теорема 2.3 Для алгоритма и семейства К ¡(а) справедливо следующее соотношение: 1С\ = (а).

Отметим, что число итераций алгоритма ЬВ для данного семейства тоже экспоненциально зависит от длины входа.

В работе изучается семейство Кг{а), которое отличается от К^а) наличием дополнительного ограничения х\ + х^ > 2. Задачи из этого семейства не имеют допустимых решений.

Для задач семейств К\{а) и К2(а) предложено использовать унимодуляр-ное преобразование пространства Щ вида у\ = х\ — х^, уг — которое позволяет сделать мощность ¿-накрытий не зависящей от а. Благодаря этому задачи решаются исследуемыми алгоритмами за несколько итераций.

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

Рассмотрим семейство К?(а):

/(ж) = Xi —ь max

при условиях

— (а — + СХХ2 < О ах 1 — (а — 1 )х2 < а

— (а —1)ха + ах4 < О ах з — (а — 1)х4 < а

-(а - 1)х„_! + ахп < О axn-i - (а - 1)хп < а х\ > 0, ..., хп > 0 - целые.

где а > 2 - целочисленный параметр, п - четное. Нами изучается семейство К\(а) соответствующих лексикографических задач.

Теорема 2.11 Для алгоритма G} и семейства К?(а) справедливо следующее соотношение: Iqj = |v?(q).

В этом же разделе исследовано семейство (а), которое отличается от К"(а) наличием неравенства + хп > 2. Задачи данного семейства не имеют допустимых решений. Далее изучается семейство K^ia) лексикографических задач.

Теорема 2.12 Для алгоритма G} и семейства Щ{а) имеет место соотношение: IG\ = (а) — 1.

В п. 2.3 изучается зависимость поведения рассмотренных двойственных алгоритмов отсечения от правила выбора производящей строки.

В главе 3 рассматриваются вопросы устойчивости для алгоритмов ЦЛП, в том числе для первого алгоритма отсечения Гомори.

В п. 3.1 приводятся некоторые сведения об устойчивости алгоритмов, отмечен ряд известных результатов.

Используемое в работе понятие устойчивости алгоритма введено А. А Колоколовым и М. В. Девятериковой. Пусть Ф - некоторый бесконечный класс выпуклых многогранных множеств пространствам", М - непустое множество из Ф. Рассмотрим положительное число е и некоторую метрику р в R™. Определим множество

M(£) = {i£ln: р (М, х) < е) .

Множество М+ (е) £ Ф называется допустимым е-расширением М, если М С М+ (е) С М (е). Будем говорить, что непустое множество М~ S Ф является допустимым сужением М, если М~ СМ и М~ П Z" = М П Z".

Положим е'м = sup {s > 0 : М (е) Л Ъп = М Л 2п}_При е € (0, определим допустимое е-изменение М как множество М € Ф, удовлетворяющее условию М~ CMC М+ (е).

Обозначим через Л алгоритм решения задачи целочисленного программирования и через /д (М) - число итераций алгоритма при решении этой задачи с релаксационным множеством М. Будем говорить, что алгоритм А устойчив для задач ЦЛП на множествах из Ф, если существует ем € (0, ем) для любого М £ Фи найдется полином р (п), не зависящий от М, такие, что

имеет место соотношение _

Ia (М) <р(п)1л(М)

для всех допустимых е^-изменений М.

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

Теорема 3.1 Алгоритм G\ не является устойчивым по релаксационному множеству.

Эта теорема вытекает из приведенных ниже утверждений для семейств задач 51(a) и S3 (а). Семейство Si (а) имеет вид:

f(x) = х\ —> max

при условиях

2xi + 2рах2 < а(р + 1) xi — (а — 2)хг < 1 х\ > 0, xi > 0 - целые,

где а,р> 2 - целочисленные параметры.

Семейство 5з(а) отличается от Si(a) тем, что 2а;i + 2pa ■ Х2 < а(р + 1) заменяется на 2x2 < 1- Многогранники задач семейства S3 являются г-изменени-ями многогранников задач семейства Si.

Сформулируем указанные утверждения для описанных семейств:

• Для семейства Si (а) выполнено соотношение IG1 = а — 1.

• Для семейства S3 (а) имеет место соотношение IG\ — 1 при а > 2.

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

В главе 4 дается постановка дискретной задачи планирования производства (ДЗП) с интервальными данными, описывается модификация алгоритма перебора L - классов, учитывающая интервальный характер задачи, приводятся результаты вычислительного эксперимента.

В п. 4.1 рассматривается ДЗП с интервальными данными. Математическая модель ДЗП в обычной постановке имеет вид (1)-(4).

Далее изучается ДЗП с интервальными данными, обобщающая постановку, приведенную в 1.1. Отличие состоит в том, что не только запасы ресурсов Ь{, 2 = 1, ..., m, но и значения ay, г = 1, ..., т, j — 1, ..., п изменяются в некоторых интервалах.

Обозначим

п

М(а1, ..., ап, b) = {х S Rn : ^ a3xj < xj > 0, j = 1, ■ • ■, n},

i=i

где aJ S j = 1. ..., п. Положим

Mx = M(a\ ..., a", 6), M2 = M(a1, ..., an, b).

Вектор объемов ресурсов изменяется между границами b и 6, b < b, а расходы ресурсов - в пределах от а; до a?, aJ > aJ , j = 1, ..., п.

Задача состоит в отыскании точки z" 6 Zn, удовлетворяющей условиям: (ljz'eMfa1,..../.^

(2) /(л*) > f(z) для всех z € M(dl, ..., a",6) ПZn.

В п. 4.2 описан алгоритм LCEM для решения ДЗП с интервальными данными, являющийся модификацией базового алгоритма перебора L - классов.

Из постановки рассматриваемой задачи следует, что ее можно решать стандартным алгоритмом LCE (либо другим алгоритмом ЦЛП), однако учет специфики задачи позволяет построить специальные алгоритмы и ускорить процесс решения.

Работа алгоритма LCEM начинается с множества Отличие модифицированного алгоритма от стандартного заключается в следующем. Если подзадача ЛП на некоторых шагах неразрешима, то LCEM пытается решить задачу, но уже с множеством М таким, что М\ CMC Мг, причем М выбирается как наименьшее множество, при котором эта задача имеет решение. Смысл данной процедуры состоит в том, чтобы быстрее найти новую целую точку, улучшить рекорд и тем самым ускорить процесс решения. В остальном LCEM аналогичен LCE. Если множество Mi содержит те же целые точки, что и Mi, то LCEM находит оптимальное решение задачи. В случае Mi = М2 он совпадает со стандартным алгоритмом перебора ¿-классов. Нами предложены также дополнительные эвристики для ускорения процесса решения.

В алгоритме LCEM использовалось преобразование вида Ух = —xi — ... — х„ + С, У2 — Х2, ■ • •, Уп — хп, где С — некоторое целое число. Применение данного преобразования во многих случаях привело к сокращению времени работы алгоритма.

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

В нервом алгоритме (обозначим его LCEM 1) используется изменение правой части линейных ограничений задачи (6). Здесь Mi = М(а1, ..., ап, Ь), Mi = М(а1, ..., а", 6), где Ь = (1 — e)b, е > 0. Во втором алгоритме (обозначим его LCEM2) для получения сужения множества М изменяются элементы матрицы линейных ограничений. Здесь Mi = М, М\ — М(а}, ..., ап, Ъ), где а? = (1 + £-J)aJ', > 0, j = 1, .... п. При решении задачи этими алгоритмами могут пропускаться некоторые L-классы множества М, в том числе и целые точки. Поэтому для получения хорошего приближенного решения числа е и Sj, j = 1, ..., п должны выбираться достаточно малыми.

В п. 4.4 рассматриваются некоторые модификации алгоритма перебора L - классов для ДЗП, позволяющие значительно ускорить процесс решения, приведены результаты вычислительного эксперимента.

Разработанные алгоритмы перебора L-классов реализованы на языке С+-Ь и тестировались на ЭВМ Pentium-4 НТ (тактовая частота процессора 2.8 ГГц). Цель эксперимента состояла в изучении поведения предложенных алгоритмов при решении ДЗП с интервальными данными в целочисленной и булевой постановках, а также в исследовании возможностей их использования для нахождения приближенных решений исходной ДЗП.

Алгоритм LCEM 1 тестировался на двух классах задач. Первый класс состоял из серий задач с целочисленными неременными со случайными исходными данными. Каждая серия включала 30 задач одинаковой размерности. При этом п менялось в пределах от 40 до 1500, а т — от 10 до 300, Cj, ац е [1,10], j = 1, ..., п, г = 1, ..., т. Значение е принималось равным 0.01 и 0.02. Для задач с п > 300 е равнялся 0.001 и 0.002.

Второй класс — задачи с булевыми переменными из известной библиотеки OR-Library. Это трудные задачи, для многих из которых известны только рекордные значения целевой функции. В данном классе п менялось в пределах от 100 до 500, m — от 5 до 30, значения aij, Cj, i = 1, ..., т, j = 1, ..., п в основном лежали в интервале [500,800], fy — в интервале [15000,120000], г — 1, .... т.

Эксперимент показал, что задачи с интервальными данными в правой части при п значительно большем т решались алгоритмом LCEM1 заметно быстрее, чем задачи в стандартной постановке. Время решения интервальных задач было в среднем в 14 раз меньше, чем время решения задач в стандартной постановке для е = 0.01 и более чем в 130 раз — для е = 0.02. Кроме того, для нахождения допустимого решения задачи (1)-(4), которое

было бы не хуже решения, найденного LCEM1, алгоритму LCE в среднем требовалось времени в 1.3 рал больше в случае £ = 0.01 и в 3.2 раз больше при е — 0.02. При этом относительное отклонение приближенного значения целевой функции от оптимального в большинстве случаев не превышало величины е (относительного изменения правой части системы ограничений).

Для задач размерности п > 300 время решения интервальных задач в среднем оказалось в 31 раз меньше, чем время решения задач в стандартной постановке для е = 0.001 и в 87 раз — для е = 0.002. Кроме того, для нахождения допустимого решения задачи (1)-(4), которое было бы не хуже решения, найденного LCEM 1, алгоритму LCE в среднем требовалось времени в 3.5 раз больше в случае е = 0.001 и в 2.4 раз больше при г = 0.002.

Нами решались серии задач из библиотеки OR-Library алгоритмомLCEMI при е ~ 0.005 и £ = 0.01. Решение задач получалось достаточно быстро, причем относительное отклонение приближенного решения от точного не превосходило величины £ для всех серий. Следует отметить, что и в этом случае среднее время решения интервальных задач было значительно меньше, чем задач в обычной постановке.

Представлены результаты эксперимента по решению алгоритмом LCEM2 серий булевых задач со случайными данными. В этих задачах п менялось в пределах от 50 до 150, т — от 10 до 150. Как правило, интервальные задачи решались в несколько раз быстрее, чем задачи в обычной постановке.

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

В заключении приводятся основные результаты диссертации.

Опубликованные работы по теме диссертации

В рецензируемых э/сурпалах из списка ВАК:

[1] Девятерикова М.В., Колоколов A.A., Колосов А.П. Унтюдулярные преобразования для задач целочисленного программирования и анализ эффективности их применения // Тр. Ин-та математики и механики УрО РАН. 2010. Т. 16. №2. - С. 48-62.

[2] Девятерикова М.В., Колоколов A.A., Колосов А.П. Об одном подходе к решению дискретной задачи планирования производства с интервальными данными // Тр. Ин-та математики и механики УрО РАН. 2008. Т. 14. №2. - С. 48-57.

[3] Devyaterikova M.V., Kolokolov A.A., Kolosov A.P. L-class enumeration algorithms for one discrete production planning problem with interval input data // Computers and Operations

Research, Volume 36, Issue 2, February 2009. - С. 316-324.

в других изданиях

[4] Девятерикова М. В., Колоколов А. А., Колосов А. П.. Алгоритмы перебора L-классов для булевой задачи о рюкзаке с интервальными данными // Материалы III Всероссийской конференции «Проблемы оптимизации и экономические приложения» - Омск: Изд-во ОмГТУ, 2006. - С. 87.

[5] Девятерикова М.В., Колоколов A.A., Колосов А.П. Решение задачи о рюкзаке с интервальными данными на основе перебора L-классов // Материалы третьей международной конференции «Танаевские чтения» , Минск, 2007. - С. 51-55

[6] Девятерикова М.В., Колоколов A.A., Колосов А.П. Унимодулярные преобразования и некоторые алгоритмы целочисленного программирования //' Российская конференция «Дискретная оптимизация и исследование операций» : Материалы конф. (Владивосток, 7-14 сентября 2007). - Новосибирск: Изд-во Ин-та математики, 2007. - С. 124.

[7] Колоколов A.A., Колосов А.П. Анализ некоторых алгоритмов целочисленного программирования с использованием L-разбиения // Информационный бюллетень Ассоциации математического программирования. № 11. УрО РАН. - Екатеринбург, 2007. - С. 186.

[8] Колосов А.П. Оценки числа итераций для некоторых алгоритмов целочисленного программирования // Тезисы IV всероссийской научной молодежной конференции «Под знаком Сигма» , май 2007, на электронном носителе. - С. 244.

[9] Колосов А.П. О некоторых алгоритмах приближенного решения задачи о рюкзаке,// Материалы VI международной научно-технической конференции «Динамика систем, механизмов и машин» , Омск, ноябрь 2007, С. 49-53.

[10] Девятерикова М.В., Колоколов A.A., Колосов А.П. Исследование некоторых алгоритмов целочисленного программирования с использованием L-разбиения и унимодулярных преобразований: Препринт. - Омск: ОмГУ, 2009. - 20 с.

Подписано в печать 27.07.2010 Формат 60x84/16 Бумага писчая Гарнитура Times New Roman. Оперативный способ печати Уч.-печ. л. 1,0; тираж 100 экз., заказ № 131

Полиграфический центр КАН г. Омск, Красный Путь, 30; тел.: (381-2) 24-70-79 e-mail: pc_kan@mail.ru Лицензия ПЛД № 58-47 от 21.04.97 г

Введение

1 Некоторые методы анализа и решения задач целочисленного программирования

1.1 Постановки задач.

1.2 L - разбиение и его свойства.

1.3 Метод перебора L - классов

1.4 Двойственные дробные алгоритмы отсечения

1.5 Унимодулярные преобразования.

2 Построение оценок числа итераций

2.1 Анализ алгоритмов для семейств задач на плоскости.

2.2 Оценки числа итераций алгоритмов в n-мерном случае

2.3 О выборе производящей строки в первом алгоритме Гомори.

3 Исследование вопросов устойчивости алгоритмов

3.1 О неустойчивости некоторых алгоритмов отсечения.

3.2 Зависимость числа итераций первого алгоритма Гомори от целевой функции.

4 Алгоритмы перебора ^-классов для задачи планирования производства с интервальными данными

4.1 Дискретная задача планирования производства с интервальными данными.

4.2 Алгоритм перебора L - классов.

4.3 Алгоритмы приближенного решения задачи.

4.4 Экспериментальные исследования.

Актуальность темы. Исследование и решенне многих задач, возникающих в экономике, планировании, технике и других областях, ввиду их сложности осуществляется на основе математического моделирования, в том числе с использованием аппарата целочисленного линейного программирования (ЦЛП). Условие цело численности позволяет учесть такие факторы, как неделимрсть объектов, дискретность процессов, наличие альтернатив, фиксированные доплаты и ряд других. Значительный интерес к задачам целочисленного программирования обусловлен их NP-трудпо-стыо [7].

Актуальность исследования задач ЦЛП связана также с* тем, что модели и методы целочисленного программирования широко используются для анализа и решения различных классов задач дискретной оптимизации [3,15,20,26,66,67], например, планирования производства, оптимального размещения [4,5,23,38,57], оптимизации на графах, развозки продукции, о покрытии [64], об упаковке [36,56], выполнимости и максимальной выполнимости [1,30,31], задач проектирования с логическими ограничениями [39]. В работах [40,41] описаны параллельные алгоритмы для решения задачи выполнимости на базе моделей ЦЛП.

В настоящее время проблематика целочисленного программирования (ЦП) явл51ется достаточно широкой и включает исследование структуры и сложности решения задач, разработку и применение методов ветвей и границ, отсечения, декомпозиции, полиэдрального подхода, приближенных и гибридных алгоритмов, изучение устойчивости задач и алгоритмов, многокритериальные постановки и ряд других [2,6,8,21,22,28,29,33,35,38,

44,45,47,48,52,53, 58,61, 64, 68,70-73, 75, 79-83,85,98,99]. Во' многих алгоритмах используется аппарат непрерывной оптимизации [20,28,48,62,70]. С теоретической точки зрения алгоритмы ЦЛП по ряду направлений исследованы недостаточно. В частности, актуальными являются вопросы получения оценок числа итераций [36], построения семейств трудных задач, устойчивости алгоритмов при малых изменениях исходных данных [17,18], поиск унимодулярных преобразований пространства, позволяющих улучшать L - структуру задач и повышать эффективность алгоритмов [34].

В области ЦП широкое применение получил подход, предложенный А. А. Колоколовым, который основан на использовании регулярных разбиений евклидова пространства [28], в том числе, Zr-разбиения. С использованием этого подхода, в [8,22,28,29,33,35,68,81,91] и других работах были построены верхние и нижние оценки числа итераций для ряда алгоритмов, введены новые классы отсечений, получены результаты по устойчивости задач и алгоритмов дискретной оптимизации, исследована L - структура задач. Предложен метод перебора L — классов [28,29], на основе которого были разработаны алгоритмы решения задачи о покрытии, задачи о рюкзаке, задач выполнимости и максимальной выполнимости и ряда других.

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

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

Следует отметить, что дискретная задача планирования производства и ее варианты широко используются для моделирования большого числа практических задач, таких как выбор проектов, распределение капитала [95], расположение предметов в системах сборки по заказу [74] и других. Указанные задачи являются NP-трудными [94], поэтому актуальным'является построение алгоритмов их приближенного решения [89,100].

Цель диссертации — разработка, теоретическое и экспериментальное исследование алгоритмов целочисленного линейного программирования с использованием L - разбиения:

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

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

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

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

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

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

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

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

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

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

3. На основе одного из построенных семейств задач доказана неустойчивость первого алгоритма Гомори по релаксационному множеству.

4. Разработаны и апробированы алгоритмы перебора L - классов для решения дискретной задачи планирования производства с интервальными данными.

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

Апробация работы. Результаты диссертации докладывались на XXIX Региональной научной студенческой конференции ОмГУ «Молодежь третьего тысячелетия» (Омск, 2005), III Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 2006), XIII Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 2007), IV Всероссийской научной молодежной конференции «Под знаком Сигма> (Омск, 2007), Российской конференции «Дискретная оптимизация и исследование операций» (Владивосток, 2007), VI Международной научно-технической конференции «Динамика систем, механизмов и машин» (Омск, 2007), XIV Байкальской международной школе-семинаре (Иркутск-Северобайкальск, 2008), а также на научных семинарах в Омском филиале Института математики им. C.JI. Соболева СО РАН, Омском государственном университете им. Ф. М. Достоевского (2005-2010) и Институте вычислительной математики и математической геофизики СО РАН.

Публикации. Основные результаты диссертации опубликованы в 10 научных работах [9-14,37,42,43,78], три из них - в изданиях из списка ВАК.

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

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

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

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

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

4. Создано программное обеспечение, в котором реализованы рассматриваемые алгоритмы, проведены экспериментальные исследования, в том числе на тестовых задачах из известной электронной библиотеки OR-Library, показавшие перспективность предложенных алгоритмов.

Заключение

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

1. Аделыпин А.В. Исследование задач максимальной и минимальной выполнимости с использованием L-разбиения //Автоматика и телемеханика. - 2004. - т. - С. 35 -42.

2. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ «Регулярная и хаотичная динамика», 2001. - 288 с.

3. Бахтин А.Е., Колоколов А.А., Коробкова З.В. Дискретные задачи производственно-транспортного типа. Новосибирск: Наука. Сиб. отд-е, 1978. - 160 с.

4. Береснев B.JI. Дискретные задачи размещения и полиномы от булевых переменных. Изд-во Ин-та математики, Новосибирск, 2005. - 408 с.

5. Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. - 333 с.

6. Булатов В.П. Методы погружения в задачах оптимизации. Новосибирск: Наука, 1977. - 161 с.

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

8. Девятерикова М.В., Колоколов А.А. Анализ устойчивости некоторых алгоритмов дискретной оптимизации //Автоматика и телемеханика. 2004. - №3. - С. 48 - 54.

9. Девятерикова М.В., Колоколов А.А., Колосов А.П. Исследование некоторых алгоритмов целочисленного программирования с использованием /^разбиения и унимодулярных преобразований: Препринт. Омск: ОмГУ, 2009. - 20 с.

10. Девятерикова М.В., Колоколов А.А., Колосов А.П. Об одном подходе к решению дискретной задачи планирования производства с интервальными данными // Тр. Ин-та математики и механики УрО РАН. 2008. Т. 14. Ш. С. 48-57.

11. Девятерикова М.В., Колоколов А.А., Колосов А.П. Решение задачи о рюкзаке с интервальными данными на основе перебора L-классов // Материалы третьей международной конференции «Танаевские чтения» , Минск, 2007. С. 51-55

12. Девятерикова М.В., Колоколов А.А., Колосов А.П. Упимодулярные преобразования для задач целочисленного программирования и анализ эффективности их применения //Тр. Ин-та математики и механики УрО РАН. 2010. Т. 16. №2, С. 48-62.

13. Дементьев В.Т., Ерзин А.И., Ларин P.M., Шамардин Ю.В. Задачи оптимизации иерархических структур. Изд-во НГУ, Новосибирск, 1996. - 167 с.

14. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 1981. 344 с.

15. Емеличев В.А., Подкопаев Д.П. Устойчивость и регуляризация векторных задач целочисленного линейного программирования // Дискретный анализ и исследование операций. Серия 2, Институт математики им. С.Л.Соболева СО РАН, 2001, т. 8. С. 47-69.

16. Еремеев А.В., Заозерская Л.А., Колоколов А.А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискретный анализ и исследование операций Сер. 2, 2000. т.7. -С. 22-46.

17. Еремин И.И., Мазуров Вл.Д., Скарин В.Д., Хачай М.Ю. Математические методы в экономике. Екатеринбург: УрГУ - Центр "Фактория Пресс 2000. - 303 с.

18. Забиняко Г.И. Пакет программ целочисленного линейного программирования //Дискретный анализ и исследование операций. 1999. Т.6.- № 2. С. 32 - 41.

19. Заблоцкая О. А. Нижняя оценка числа итераций для одного алгоритма лексикографической оптимизации //Дискретная оптимизация и численные методы решения прикладных задач. Новосибирск: ВЦ СО АН СССР, 1986. - С. 21 - 27.

20. Забудскин Г.Г. О целочисленной постановке одной задачи размещения объектов на линии // Управляемые системы. 1990. - Вып. 30. -С. 35 - 45.

21. Заикина Г. М. Колоколов А. А. Левапова Т. В. Экспериментальное сравнение некоторых методов целочисленного программирования // Методы решения и анализа задач дискретной оптимизации. Омск: ОмГУ, 1992. С. 25-41.

22. Касселс Дж.В.С. Введение в геометрию чисел. Издательство «Мир» . М.: 1965. 421 с.

23. Ковалев М. М. Дискретная оптимизация (целочисленное программирование). Изд. 2-е, стереотипное. М.: Едиториал УРСС, 2003. — 192 с.

24. Колоколов А. А. Методы дискретной оптимизации. Учебное пособие. Омск: ОмГУ, 1984. -76 с.

25. Колоколов А.А. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журн. исследования операций. 1994. № 2.- С. 18-39.

26. Колоколов А.А. Регулярные разбиения в целочисленном программировании //Методы решения и анализа задач дискретной оптимизации.- Омск: ОмГУ, 1992. С. 67 - 93.

27. Колоколов А.А., Адельшин А.В., Ягофарова Д.И. Решение задач выполнимости и некоторых ее обобщений с использованием метода перебора ^классов //Прикладная математика и информационные технологии. Омск, 2005. - С. 68 - 79.

28. Колоколов А.А., Адельшин А.В., Ягофарова Д.И. Решение задачи выполнимости с использованием метода перебора ^классов // Информационные технологии. — 2009. — №2. С. 54-59.

29. Колоколов А.А., Девятерикова М.В. Алгоритмы перебора /^классов для задачи о рюкзаке с интервальными данными. Препринт. Омск: Изд-во ОмГУ, 2001. 20 с.

30. Колоколов А.А., Девятерикова М.В. Анализ устойчивости /^разбиения множеств в конечномерном пространстве //Дискретный анализ и исследование операций, 2000. Серия 2. Т.7. - №2. -С. 47 - 53.

31. Колоколов А.А., Девятерикова М.В. Задачи целочисленного программирования и унимодулярные преобразования // Труды XIV Байкальской международной школы-семинара. Иркутск, 2008. — Т.1. -С. 111 - 118.

32. Колоколов А.А., Девятерикова М.В., Заозерская JI.A. Регулярные разбиения в целочисленном программировании: Учебное пособие. Омск: ОмГУ. - 2007. - 48 с.

33. Колоколов А.А., Заозерская JI.A. О среднем числе итераций некоторых алгоритмов для решения задачи об упаковке множества // Труды XIV Байкальской международной школы-семинара. Иркутск, 2008. -Т.1. - С. 388 - 395.

34. Колоколов А.А., Колосов А.П. Анализ некоторых алгоритмов целочисленного программирования с использованием /^разбиения // Информационный бюллетень Ассоциации математического программирования. № 11. УрО РАН. Екатеринбург, 2007. - С. 186.

35. Колоколов А.А., Леванова Т.В. Алгоритмы декомпозиции и перебора /^классов для решения некоторых задач размещения //Вестник Омского университета. Омск: ОмГУ, 1996. - №1. - С. 21 - 23.

36. Колоколов А.А., Нагорная З.Е., Гуселетова О.Н., Ярош А.В. Математические модели и программный комплекс для проектирования эскизов одежды //Прикладная математика и информационные технологии. Омск, 2005. - С. 80 - 98.

37. Колоколов А.А., Тюрюмов А.Н., Ягофарова Д.И. Параллельный алгоритм перебора i^-классов для задачи выполнимости //Материалы III Всероссийской конференции «Проблемы оптимизации и экономические приложения». Омск, 2006. С. 102.

38. Колоколов А.А., Тюрюмов А.Н., Ягофарова Д.И. Разработка и экспериментальное исследование алгоритмов решения задач выполнимости и максимальной выполнимости: Препринт. Омск: ОмГУ, 2006 - 19 с.

39. Колосов А.П. О некоторых алгоритмах приближенного решения задачи о рюкзаке // Материалы VI Международной научно-технической конференции «Динамика систем, механизмов и машин» , Омск, ноябрь 2007. с. 49 - 53.

40. Колосов А.П. Оценки числа итераций для некоторых алгоритмов целочисленного программирования // Тезисы IV Всероссийской научной молодежной конференции «Под знаком Сигма» , май 2007, на электронном носителе. С. 244.

41. Корбут А.А., Сигал И.Х., Финкельштейн Ю.Ю. Гибридные методы в дискретной оптимизации //Изв. АН СССР. Техн. кибернетика. 1988.- т. С. 65 - 77.

42. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. -М.: Наука, 1969. 368 с.

43. Косарев Н.А., Рубанова Н.А. Об отсечениях Бендерса для некоторых задач размещения предприятий // Материалы Российской конф. «Дискретный анализ и исследование операций» . Новосибирск, 2004.- С. 164.

44. Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и приложения. -М. 2001. - С. 84 - 117.

45. Кузнецова А.А., Стрекаловский А.С., Цевээндорж И. Об одном подходе к решению целочисленных задач оптимизации //ЖВМ и МФ. -1999. Т.39. - М. - С. 9 - 16.

46. Кузюрин Н.Н. Полиномиальный в среднем алгоритм в целочисленном линейном программировании // Сибирский журнал исследования операций. 1994. Т.1, т. С. 38 - 48.

47. Левин В. И. Дискретная оптимизация в условиях интервальной неопределенности // Автоматика и телемеханика. 1992. N2 7. С. 97 - 106.

48. Левин В. И. Булево линейное программирование с интервальными коэффициентами // Автоматика и телемеханика. 1994. №7. С. 111 - 122.

49. Леонтьев В.К. Устойчивость в линейных дискретных задачах // Про-бл. кибернетики. М.: Наука, 1979. - Вып. 35. - С. 169 - 184.

50. Мазуров Вл.Д. Метод комитетов в задачах оптимизации и классификации. М.: Наука, 1990. - 248 с.

51. Мазуров Вл.Д., Хачай М.Ю. Комитеты систем линейных неравенств // Автоматика и телемеханика. 2004. - № 2. - С. 43 - 54.

52. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука., 1990. - 488 с.

53. Мухачева Э.А., Мухачева А.С. Задача прямоугольной упаковки: методы локального поиска оптимума на базе блочных структур // Автоматика и телемеханика. 2004. - № 2. - С. 101 - 112.

54. Панюков А.В. Квазицелочисленность релаксационного многогранника задачи Вебера // Тр. XI межд. Байкальской школы-семинара "Методы оптимизации и их приложения". Иркутск, 1998. - С. 171 - 174.

55. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. - 512 с.

56. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982. - 256 с.

57. Попков В.К. Гиперсетн и структурные модели сложных систем // Системное Моделированне-6, Новосибирск. 1981. - С. 26-48.

58. Попков В.К. Математические модели связности // 2-е изд., испр. и доп. Новосибирск: Изд. ИВМиМГ СО РАН. - 2006. - 490 с.

59. Попов Л.Д. Об одноэтапном методе решения лексикографических вариационных неравенств //Известия вузов. Математика. 1998. - №12 (439). - С. 71 - 81.

60. Привалова Ю.И. Некоторые эвристические алгоритмы для задачи о покрытии множества. Препринт. ОмГУ, Омск, 2007. - 17 с.

61. Сайко Л.А. Исследование мощности L-накрытий некоторых задач о покрытии //Дискретная оптимизация и анализ сложных систем. Новосибирск: ВЦ СО АН СССР, 1989. - С. 76 - 97.

62. Сергиенко И.В., Козерацкая Л.Н., Лебедева Т.Т. Исследование устойчивости и параметрический анализ дискретных оптимизационных задач. К.: Наук, думка, 1995. 170 с.

63. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наукова думка, 1988. - 472 с.

64. Сигал И.Х., Иванова А.П. Введение в прикладное и дискретное программирование: модули и вычислительные алгоритмы. М.: Физмат-лит, 2002. - 240 с.

65. Симанчев Р.Ю. О вполне регулярных отсечениях для задач целочисленной оптимизации //Управляемые системы. Новосибирск: ИМ СО АН СССР, 1990. - Вып. 30. - С. 61 - 71.

66. Страуструп Б. Язык программирования С++. Специальное издание. М.: Бином. - 2001. - 1099 с.

67. Схрейвер А. Теория линейного и целочисленного программирования: в 2-х т. М.: Мир, 1991. - 702 с.

68. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974. - 520 с.

69. Червак Ю.Ю., Червак О.Ю. Один из способов формулирования па-рето-лексикографических задач оптимизации // Кибернетика и системный анализ, 1996, №1. С. 108-110.

70. Шевченко В.Н. Качественные вопросы целочисленного программирования. М.: Физматлит, 1995. - 190 с.

71. Akcay Y., Xu S. Н. Joint inventory replenishment and component allocation optimization in an assemble-to-order system // Management Science. 2004. No. 50. P. 99 - 116.

72. Benders J. F., van Nunen J. A. E. E. A property of assignment type mixed integer linear programming problems // Operations Research Letters, Volume 2, Issue 2, June 1983. P. 47-52

73. Chvatal V., Cook W., Iiartmann M. On cutting-plane proofs in combinatorial optimization // Linear Algebra and its Applications, Volumes 114-115, March-April 1989. P. 455-499

74. Devyaterikova M.V., Kolokolov A. A. L-class enumeration algorithms for some interval production planning problem // Proc. 12th IFAC Symposium on Information Control Problems in Manufacturing INCOM'2006. St. Etienne, 2006. V. 3. P. 9 - 13.

75. Devyaterikova M.V., Kolokolov A.A., Kolosov A.P. L-class enumeration algorithms for one discrete production planning problem with interval input data // Computers and Operations Research, Volume 36, Issue 2, February 2009. C. 316 - 324.

76. Edmonds J.R., Pulleyblank W.R. Facets of 1-matching polyhedra // C. Berge, D.R. Chuadhuri (Eds.), Hypergraph Seminar, Springer-Verlag, Heidelberg, 1974. P. 214-242.

77. Eremeev A. Modeling and Analysis of Genetic Algorithm with Tournament Selection // Proc. of Artificial Evolution Conference. Lecture- Notes in Computer Science, 2000. Vol. 1829. - P. 84 - 95.

78. Eremeev A.V., Kolokolov A.A. On some genetic and Zr-class enumeration algorithms in integer programming //Proc. of the First Intertational Conference on Evolutionary Computation and its Applicatios. Moscow, 1996. - P. 297 - 303.

79. Glover F., Laguna M. Tabu Search. University of Colorado at Boulder Hardbound, July 1997. 408 p.

80. Goldberg D. Genetic Algorithms in Search, Optimization and Machine Learning. Reading: Addison Wesley, 1989. - 432 p.

81. Gomory R.E. Outline of an algorithm for integer solutions to linear programs // Bulletin of the American Mathematical Society 64 (1958). P. 275-278.

82. Hooker J.N. Generalized resolution and cutting planes //Annals of Operations Research. 1988. - V.12. - P. 217 - 239.

83. Jeroslow R. Cutting-plane theory: Algebraic methods // Discrete Mathematics, Volume 23, Issue 2, 1978. P. 121-150

84. Jeroslow R. Cutting-Plane Theory: Disjunctive Methods // Annals of Discrete Mathematics, Volume 1, 1977. P. 293-330

85. Jeroslow R. An Introduction to the Theory of Cutting-Planes // Annals of Discrete Mathematics, Volume 5, 1979. P. 71-95

86. Johnson D. Approximation algorithms for combinatorial problems //Journal of Comput. System Science. 1974. - V.9. - P. 256 - 278.

87. Kolokolov A. A., Dcvyaterikova M. V. Stability analysis of some discrete optimization algorithms. DOM'2004, Proceedings, Omsk 2004. P. 180 - 184.

88. Kolokolov A.A., Eremeev A.V., Zaozerskaya L.A. On hybrid L-class enumeration and genetic algorithm for set covering problem //15th Conference of International Federation of Operational Research Societies (IFORS'99): Abstracts. Pekin, 1999. - P. 117.

89. Kouvelis P., Yu G. Robust discrete optimization and its applications. Dordrecht: Kluwer Academic Publishers. 1997. 356 p.

90. Land A.H., Doig A.G. An Automatic Method for Solving Discrete Programming Problems. Econometrica, 28 (1960), P. 497-520.

91. Lin E. Y.-H. A bibliographical survey on some well-known non-standard knapsack problems // INFOR 36(4). 1998. P. 274-317.

92. Lu L. L., Chiu S. Y., Cox L. A. Optimal project selection: Stochastic knapsack with finite time horizon // Operations Research. 1999. No. 50. P. 645-650.

93. Manjoub A., Mihelic J., Rapine C., Robic B. k-center problem with uncertainty: flexible approach // Proc. of Discrete Optimization Methods in Production and Logistics (DOM-2004). Omsk, 2004. P. 75-80.

94. Martello S., Toth P. Knapsack problems : algorithms and computer implementations. John Wiley and Sons. 1990. 296 p.

95. Nemhauser G.L., Wolsey L.A. Integer and combinatorial optimization. A Wiley-Interscience Publication: John Wiley and Sons, inc., 1999. 784 p.

96. Reeves C. Genetic Algorithms for the Operation Researcher // INFORMS -Journal on Computing. 1997. - Vol.9, №3. - P. 231 - 250.

97. Vazirani Vijey V. Approximation Algorithms // Springer, 2002. 380 p.101. http://people.brunel.ac.uk/~mastjjb/jeb/orlib/mknapinfo.html