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

кандидат физико-математических наук
Колосов,
Антон Павлович
город
Омск
год
2010
специальность ВАК РФ
05.13.18
Автореферат по информатике, вычислительной технике и управлению на тему «Разработка и анализ алгоритмов целочисленного линейного программирования с использованием L-разбиения»

Автореферат диссертации по теме "Разработка и анализ алгоритмов целочисленного линейного программирования с использованием L-разбиения"

804607740

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

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

^РАЗБИЕНИЯ

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 - классов, на основе которого были разработаны алгоритмы решения задачи о покрытии множества, задачи о рюкзаке, задач выполнимости и максимальной выполнимости.

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

^ \ -, ■

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

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

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)

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

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

Хз > о, з = 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 М, обладающую свойствами:

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

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

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

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

где х — (хо, 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},

где 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 г

Оглавление автор диссертации — кандидат физико-математических наук Колосов, Антон Павлович

Введение 2010 год, диссертация по информатике, вычислительной технике и управлению, Колосов, Антон Павлович

Заключение диссертация на тему "Разработка и анализ алгоритмов целочисленного линейного программирования с использованием L-разбиения"

БиблиографияКолосов, Антон Павлович, диссертация по теме "Математическое моделирование, численные методы и комплексы программ"