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

Орловская, Татьяна Геннадьевна

Исследование задач и алгоритмов целочисленного программирования на основе регулярных разбиений и унимодулярных преобразований тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Орловская, Татьяна Геннадьевна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Омск МЕСТО ЗАЩИТЫ

2013 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

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

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

005060509

На правах рукописи

ОРЛОВСКАЯ Татьяна Геннадьевна

ИССЛЕДОВАНИЕ ЗАДАЧ И АЛГОРИТМОВ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ НА ОСНОВЕ РЕГУЛЯРНЫХ РАЗБИЕНИЙ И УНИМОДУЛЯРНЫХ ПРЕОБРАЗОВАНИЙ

Специальность 01.01.09 - Дискретная математика и математическая кибернетика

Автореферат

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

3 О ПАЙ 2013

Екатеринбург - 2013

005060509

Работа выполнена в Омском филиале Федерального государственного бюджетного учреждения науки Института математики им. C.JT. Соболева Сибирского отделения Российской академии наук

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

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

Официальные оппоненты: Хачай Михаил Юрьевич,

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

Институт математики и механики

им. H.H. Красовского УрО РАН,

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

Девятерикова Марина Владимировна,

кандидат физико-математических наук, доцент, Омский государственный технический университет, доцент кафедры математических методов и информационных технологий в экономике

Ведущая организация: Федеральное государственное бюджетное

учреждение науки

Институт вычислительной математики и математической геофизики СО РАН

Защита состоится "19" июня 2013 г. в 16 часов на заседании диссертационного совета Д 004.006.04 при Федеральном государственном бюджетном учреждении науки Институте математики и механики им. H.H. Красовского Уральского отделения Российской академии наук (ИММ УрО РАН) по адресу: 620990, Российская Федерация, г. Екатеринбург, ул. Софьи Ковалевской, д. 16.

С диссертацией можно ознакомиться в библиотеке Института математики и механики им. H.H. Красовского УрО РАН.

Автореферат разослан " /5 " ма^ 2013 г.

Ученый секретарь диссертационного совета • доктор физико-математических паук

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

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

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

В настоящее время в целочисленном программировании активно развивается предложенный A.A. Колоколовым метод регулярных разбиений [9, 23], на основе которого исследована L - структура задач ЦП [31], построены алгоритмы и оценки числа итераций [8], введены новые классы отсечений [9], изучены вопросы устойчивости задач и алгоритмов дискретной оптимизации [4].

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

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

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

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

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

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

• разработать варианты алгоритма перебора L - классов (LCE) с учетом специфики задач о рюкзаке, изучить их поведение с использованием свойств L- структуры задач булева программирования (БП);

• исследовать г - алгоритм Вотякова A.A. для решения задач ЦЛП на основе регулярных разбиений;

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

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

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

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

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

Апробация работы. Результаты диссертации докладывались на IV и V Всероссийских конференциях "Проблемы оптимизации и экономические приложения!'' (Омск, 2009 и 2012), VII Международной научно-технической конференции "Динамика систем, механизмов и машин" (Омск, 2009), Российской конференции "Дискретная оптимизация и исследование операций" (Алтай, 2010), 8-й и 9-й Международных конференциях "Интеллектуализация обработки информации" (Кипр, 2010 и Черногория, 2012), XIV Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 2011), XV Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 2011), Международной конференции "Алгебра и линейная оптимизация", посвященной 100-летию С.Н. Черникова (Екатеринбург, 2012), на заседании научного семинара отдела математического программирования Института математики и механики им. H.H. Красовского УрО РАН (Екатеринбург, 2012), а также на заседаниях научного семинара "Математическое моделирование и дискретная оптимизация" Омского филиала Института математики им. С.Л. Соболева, СО РАН и Института математики и информационных технологий ОмГУ им. Ф.М. Достоевского (Омск, 2009 - 2012).

Публикации. Основные результаты диссертации опубликованы в 11 научных работах [22-32], две из них — в журналах из списка ВАК [22,23].

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

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

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

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

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

Для исследования задач и алгоритмов на основе регулярных разбиений нами используется задача ЦП в лексикографической постановке [9], в которой требуется найти

2*=1ехтах( nГ\Zn), (1)

где 0 — выпуклое замкнутое ограниченное сверху множество в пространстве М", т. е. существует вектор в, £ К" такой, что х < сI для всех х € П. Множество П называется релаксационным множеством задачи, а множество

Л, = {а: € П : х)~ г для всех гёГ2 П 2™}

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

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

требуется найти лексикографически максимальную точку множества К Г12",

где К — {х е К" : ^^ а1х] —Ь, 0<Xj <1, j = 1,..., п},

¿=1

предполагается, что а^- 6 К,= 1,..., тг, 6 е N.

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

Введем разбиение Р пространства К™, которое обладает рядом свойств, связанных со спецификой задач ЦП:

1) каждая точка г £ Ж" образует отдельный класс разбиения, остальные классы состоят из нецелочисленных точек и называются дробными;

2) если множество X С К" ограничено, то фактор-множество Х/Р конечно;

3) для произвольного X С и любого вектора г £ Ъп имеет место [X + г)/Р = XI ¥ + г.

Элементы из Х/Р называются Р-классами. Разбиение, удовлетворяющее 1) - 3), называется регулярным.

Для анализа рассматриваемой задачи (1), ее дробного накрытия и методов решения применяется разбиение Р, индуцирующее разбиение релаксационного множества Множество называется Р-накрытием задачи.

В настоящее время широко используется Ь - разбиение, которое определяется следующим образом. Каждая точка из Ъп образует отдельный Ь- класс, т.е. элемент разбиения. Точки х, у £ Кп (х >- у и х, у £ 2") называются Ь - эквивалентными (принадлежат одному дробному Ь - классу), если не существует отделяющей их точки г £ Жп, т.е. такой, что х У г У у. Будем называть рангом класса V £ Х/Ь и обозначать через г (У) номер первой дробной координаты представителя V £ V, если V — нецелочисленный вектор. Для целочисленной ТОЧКИ г(У) = 71+1.

Множества П/Ь и Г2«/1/ называются соответственно Ь - структурой и Ь - накрытием задачи. Во многих случаях сложность задач ЦП определяется мощностью Г2»/Ь.

Рис.1 Ь — структура задачи ЦЛП. 7

На рис. 1 представлено разбиение релаксационного многогранника М задачи ЦЛП на Ь - классы и входящее в него Ь - накрытие, которое состоит из четырех Ь - классов — частей вертикальных полос Ук = {х £ М : к < < к + 1}, к = 1,2, и частей вертикальных отрезков вида У'к = {х е М : х\ = к, 1 < х2 < 2}, к = 1,2. Отметим, что х = 1ехтах (М). Кроме того, в Ь - разбиение многогранника М входят еще несколько дробных классов и целочисленных точек.

Метод перебора Ь — классов [9,10] для решения задачи ЦЛП основан на Ь - разбиении исходного многогранника задачи и выделении в нем дробного накрытия, элементы которого могут быть выписаны в отношении лексикографического порядка. Идея алгоритма заключается в последовательном переходе от одного элемента разбиения к следующему с учетом лексикографического порядка, для чего осуществляется поиск представителей соответствующих Ь - классов.

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

В п. 1.3 рассматривается применение унимодулярных преобразований [6,17] к известным задачам ЦП как подход к улучшению Ь - структуры и ускорению процессов решения задач ЦЛП [21]. Унимодулярнъш называется преобразование в пространстве К", которое задается целочисленной матрицей с определителем, равным +1 или —1. Важным свойством данных преобразований является то, что целочисленная решетка инвариантна относительно любого унимодулярного преобразования. При этом даже простейшие преобразования позволяют существенно сокращать время решения задач.

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

Во многих случаях с помощью унимодулярных преобразований для исходной задачи может быть получена эквивалентная ей задача, у которой мощность Ь - накрытия значительно меньше и, таким образом, более подходящая для решения алгоритмами лексикографического типа [23,27,28,30].

Обозначим через Ы — класс унимодулярных преобразований, соответствующих перестановкам переменных задачи ЦЛП. Пусть — преобразование из класса 1А, приводящее к упорядочению коэффициентов Оу, ] = 1, ..., п, задачи (1) с множеством О. = К по невозрастанию, а {и^К) — образ релаксационного многогранника К.

Будем говорить, что унимодулярное преобразование II* из класса Ы является оптимальным в классе и для задачи (1) с множеством П = К,

если для любого U € U \ U* справедливо неравенство

\{U*K)/L\ < \(UK)/L\.

В п. 2.1. нами доказана следующая теорема [23,26-28].

Теорема 2.1. Унимодулярное преобразование Uopt является оптимальным в классе перестановочных преобразований U для задачи (1) с множеством Г2 = К и имеет место оценка:

\(и^К)/Ц < \К/L\.

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

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

В п. 2.2. анализируется L - структура задач о рюкзаке. Приводятся различные семейства трудных задач для алгоритмов лексикографического типа и строятся подходящие унимодуляриые преобразования [29-31].

Рассмотрим задачу поиска допустимой лексикографически максимальной целочисленной точки в следующем множестве:

Q = {z е В" : хх + 2 хз = к}> j=2

где В" = {i £ 1" : 0 < Xj < 1, j = 1, ..., n}, п > 3, к - четное, 1 < к < 2(п — 1).

Теорема 2.3. Для L - накрытия задачг1 (1) с множеством П = Q справедлива оценка

\Q*/L\ > 2k!2 — 1.

Из свойств изучаемой нами задачи (1) с множеством Г2 = К вытекает, что поиск лексикографически максимальной точки на очередном шаге алгоритма можно осуществлять аналитически. Для булевой задачи на очередном шаге алгоритма LCE при вычислении лексикографически максимального элемента: х\,... ,Xi — фиксированные целые числа,

Х{+1 = min |l, ^b - J2 djXj^ /a;+i| и все Xi+2,... ,x„ — равны 0, если значение дроби меньше или равно 1, иначе полагаем Х{+1 = 1 и повторяем

вычисления ДЛЯ следующей координаты £¿+2- Если номер координаты для вычисления превышает размерность задачи, то подходящего лексикографически максимального элемента нет. Обозначим указанную модификацию алгоритма ЬСЕ через ЬЕ\, трудоемкость Тье1 = п\М,/Ь\. Обращаем особое внимание на тот факт, что Т^ зависит от величины \М,/Ь\, которая может иметь экспоненциальный характер.

Аналогичная схема применима и для целочисленного варианта задачи о рюкзаке. Из теоремы 2.3 следует, что число итераций алгоритма ЬЕ\ для задачи (1) с множеством 0=2 также ограничено снизу экспонентой.

Множество О., в отличии от известного многогранника Джерослоу, содержит целочисленную точку при любом к. Для (2 построено унимодулярное преобразование, позволяющее перейти от задачи (1) с множеством Г2 = 2 к эквивалентной задаче с мощностью Ь - накрытия равной 0 и получить допустимое целочисленное решение за одну итерацию алгоритма ЬСЕ.

Введем обозначение

I п

<3 = {а: е В" : + 2 ^ х^ = к, ^ а,Х] = Ь}, ]=2 ]=1+1

где п > 3, к — четное, 1 < к < 2(п — 1), ^ 6 М, ; = 1,...,п, 6 € N. Ь - накрытие задачи (1) на данном множестве ограничено снизу величиной (2кI2 — 1). Вопрос о существовании допустимого целочисленного вектора зависит от второго уравнения с произвольными коэффициентами и правой частью (из множества М). Указанное семейство представляет собой подкласс Л/Т -трудных задач поиска допустимого вектора в множестве, каждая из которых имеет экспоненциальное (от значения параметра к) Ь- накрытие.

С помощью предложенных в диссертации семейств проведено исследование метода ветвей и границ (схема Лэнд и Дойг [17]), показано, что они являются трудными для решения, а положительное влияние применения уни-модулярных преобразований на структуру задачи сохраняется.

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

Дробный Ь - класс V £ К/Ь называется вершинным, если в нем содержится хотя бы одна вершина множества К. Будем называть ¿-класс V существенным, если найдется лексикографически максимальный элемент х € V. Отметим, что каждый существенный класс является вершинным.

Обозначим через 5 последовательность приближений, порождаемую при решении булевой задачи о рюкзаке алгоритмом перебора Ь - классов.

Для построения различных оценок числа итераций этого алгоритма можно использовать следующее установленное нами свойство [23].

Теорема 2.7. Для задачи о рюкзаке (1) с множеством П = К длина последовательности 5 совпадает с числом существенных классов в Ь - накрытии задачи.

Отметим, что мощность множества существенных классов не превышает числа вершинных классов, их в свою очередь не больше количества дробных вершин задачи. Таким образом, если у задачи или у ее £ - накрытия число дробных вершин ограничено сверху полиномом от п, тогда и трудоемкость алгоритма ЬСЕ будет полиномиальной.

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

В п 2.3. приведены результаты экспериментального исследования влияния переупорядочений переменных на Ь - структуру задачи и процесс перебора Ь - классов [23]. С этой целыо программно реализованы алгоритм ЬСЕ с учетом специфики задачи и алгоритм для вычисления мощности Ь - структуры для булевого и целочисленного вариантов одномерной задачи о рюкзаке. Решались задачи: исходная; с упорядочением коэффициентов а^ j = 1, ..., п, по невозрастанию и по неубыванию.

Для иллюстрации процессов решения задачи о рюкзаке с помощью рассматриваемых алгоритмов использовалось понятие ранговой функции. Пусть К/Ь = {VI,..., 1^}, тогда ранговой функцией Ь - структуры будем называть целочисленную функцию /(К/Ь) = (г(У1),..., г{У„)), где К - релаксационное множество задачи, г(Ц) — ранг Ь - класса V*, г = 1, ..., ц.

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

1 4 7 10 13 16 19 22 25 28 31 34 37 40 Vj

11 ^-----*--------

r(V;)

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

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

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

В п. 3.1. приводятся необходимые определения и этапы г - алгоритма.

Округлением вектора х° будем считать любую точку с координатами или + 1 (если {ж?} ф 0), где {а} — дробная часть числа а. Здесь и далее [aj - ближайшее целое число не большее а, [а] — ближайшее целое число не меньшее а.

Округлением вектора ж0, допустимым относительно релаксационного многогранника М задачи ЦЛП, будем называть вектор у £ Z™, если справедливо следующее соотношение {igM : Х{ > yit г = 1,..., п} ф 0.

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

(с, х) тах, х £ (М П Z"), (2)

где М — {i £ Е" : Ах < Ь}, с — n-вектор, Ъ — m-вектор, А — (m х п)-матрица, п < т. Отметим, что задача (2) имеет вид, удобный для полного округления, если существует точка х° £ М такая, что

шахх,; = ж.0, г = 1.... ,п, тах(с, х) = (с, х°).

Общая схема г - алгоритма для М описывается следующим процессом, каждая итерация t которого состоит из двух этапов:

• первый — приведение задачи к виду, удобному для полного округления на Mt-1 в точке хг, где хь — оптимальное решение задачи ЦЛП на итерации t;

• второй — применение группового отсечения путем введения систем дополнительных неравенств Цх < Щх*}, М( = {х € М : Цх < 1Уех'.|}, и решение полученной таким образом задачи ЦЛП, где Ц — это матрица унимодулярного преобразования, приводящего задачу к виду, удобному для полного округления в точке ха \_х\ - целочисленный вектор, который найден округлением вниз каждой координаты вектора х. Алгоритм завершает работу, если для некоторого ( = £ выполняется М= 0 /

или хь € М П Ъп. В первом случае задача не имеет допустимых целочисленных решений, во втором хь — одно из оптимальных решений соответствующей задачи ЦП.

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

Для анализа алгоритмов решения задач ЦЛП целесообразно использовать регулярные разбиения. Алгоритм считается регулярным относительно разбиения, если порождаемая им последовательность приближений обладает следующим свойством: в каждый класс разбиения попадает не более одного се элемента. Исследование регулярности алгоритма играет важную роль при анализе конечности и построении оценок числа итераций. Представляет интерес изучение случаев, когда алгоритм не является регулярным, по существует верхняя граница для числа порождаемых им приближений, попадающих в один класс регулярного разбиения. Например, для метода ветвей и границ (типа Лэнд и Дойг) и кубических разбиений эта граница равна п [9].

В п. 3.2. рассматривается вопрос о регулярности 2 - алгоритма при решении инвариантных задач относительно ряда регулярных разбиений [22,24,25].

Далее нам потребуются некоторые свойства векторов из К", связанные с округлениями их координат. Каждой вершине 5 = (¿1,... ,6„) единичного куба В" поставим в соответствие обозначаемое тем же символом отображение 8 : Е" —> Ъп, называемое округлением по правилу х 5(х) = (¿1(2:1), • ■ ■, 6п(хп))т, где

= \.хз\> ссли = иначе = , если = 1, ] = 1,..., п.

Округления 5 и &* называются взаимными, если для соответствующих им векторов выполняется <5 4- 5* = еп, где еп = (1,..., 1)т — п-вектор. Взаимными являются, например, округления, отвечающие векторам еп и 0„ = (0,..., 0)т. Их мы будем обозначать <5+, д~.

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

определяется условиями: каждая точка 2 6 образует отдельный класс

разбиения, а нецелочисленные точки х и у принадлежат одному классу, если 5{х) = 6(у). Кубические разбиения, отвечающие округлениям 5~ и будем называть соответственно нижним и верхним кубическими разбиениями. Пусть 5 и 6* — взаимные округления. Точки х и у принадлежат одному классу канонического разбиения, если одновременно выполняются соотношения: 5(х) =5(у), <5*(х) — 5*(у). Нами доказана (см. [22])

Теорема 3.3. Для L - разбиения, верхнего и нижнего кубических разбиений при решении инвариантных задач z - алгоритм является регулярным.

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

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

Положим Р = {х G Rn : Zj ^ xj ^ Xj,j S 1,..., п] , тогда справедлива следующая

Теорема 3.4. Число итераи,ий z - алгоритма не превосходит мощности фактор-множества М/5~, где М = М П Р.

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

более Yl(l^d ~~ zt) + 1 итераций. Нами предложено семейство задач ЦЛП,

¿=1

для которого данная оценка достигается [22].

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

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

Основные результаты работы заключаются в следующем: 1. Выделен и исследован класс унимодулярных преобразований перестановочного типа, улучшающих структуру задачи о рюкзаке и некоторых ее

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

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

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

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

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

Автор благодарит научного руководителя д.ф.-м.н., профессора Коло-колова A.A. за проявленное внимание и поддержку при подготовке данной работы.

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

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

[2] Васильев И.Л. Метод отсечений для многогранника задачи о рюкзаке // Известия РАН. Теория и системы управления. - 2009. № 1. -С. 74-81.

[3] Вотяков A.A. О задачах, инвариантных относительно г - округления // Экономика и математические методы. 1971. Том 7, вып. 2. - С. 259-2G4.

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

[5] Евтушенко Ю.Г., Посыпкин М.А. Варианты метода неравномерных покрытий для глобальной оптимизации частично-целочисленных нелинейных задач // Доклады Академии наук. - Т. 437, № 2. - С. 168-

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

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

[8] Заозерская JI.A., Колоколов A.A. Оценки среднего числа итераций для некоторых алгоритмов решения задачи об упаковке множества // Журнал вычислительной математики и математической физики. 2010.

- Т. 50, № 2. - С. 242-248.

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

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

[11] Кузнецова A.A., Стрекаловский A.C., Цевээндорж И. Об одном подходе к решению целочисленных задач оптимизации // ЖВМ и МФ.

- 1999. - Т. 39, № 1. - С. 9-16.

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

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

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

[15] Попов Л.Д. Опыт многоуровневого распараллеливания метода ветвей и границ в задачах дискретной оптимизации // Автомат, и телемех., 2007. - Вып. 5. - С. 171-181.

[16] Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. -2-е изд., испр. и доп. - М.: ФИЗМАТЛИТ, 2007. - 304 с.

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

[18] Хачай М.Ю. Вычислительная сложность комбинаторных задач, индуцированных коллективными процедурами обучения распознаванию образов // Тр. Ин-та матем. и мех. 2010. Т. 16, №3. - С. 276-284.

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

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

[21] Krishnamoorthy В., Pataki G. Column basis reduction and decomposable knapsack problem // Discrete Optimization. August 2009. 6(3). - P. 242-270.

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

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

[22] Колоколов A.A., Орловская Т.Г. Исследование одного алгоритма решения задач целочисленного линейного программирования // Тр. Инта матем. и мех. 2010. Т. 16, № 3. - С. 140-145.

[23] Колоколов A.A., Орловская Т.Г., Рыбалка М.Ф. Исследование алгоритмов целочисленного программирования с использованием регулярных разбиений и унимодулярных преобразований // Автоматика и телемеханика. № 2, 2012. - С. 178-190.

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

[24] Колоколов A.A., Орловская Т.Г. Исследование 2 - алгоритма для решения некоторых задач целочисленного программирования // Проблемы оптимизации и экономические приложения: материалы IV всероссийской конф. Омск: Полиграфический центр КАН, 2009. - С. 137.

[25] Колоколов A.A., Орловская Т.Г. О регулярности одного алгоритма решения задач целочисленного программирования // Динамика систем, механизмов и машин: материалы VII междунар. науч.-техн. конф. Омск: Изд-во ОмГТУ, 2009. Кн.З. - С. 51-55.

[26] Колоколов A.A., Орловская Т.Г. Исследование L- структуры задачи о рюкзаке // Дискретная оптимизация и исследование операций: материалы Российской конф. Новосибирск, 2010. - С. 96.

[27] Колоколов A.A., Орловская Т.Г. Методы улучшения L - структуры задачи о рюкзаке // Математическое программирование и приложения: Информационный бюллетень № 12 XIV Всероссийской конф. Екатеринбург, 2011. - С. 186.

[28] Колоколов A.A., Орловская Т.Г. О некоторых унимодулярных преобразованиях для задачи о рюкзаке // Методы оптимизации и их приложения: тр. XV Байкальской междунар. шк.-сем. Иркутск, 2011. Т. 4. - С. 161-166.

[29] Колоколов A.A., Орловская Т.Г. Анализ алгоритмов решения некоторых задач о рюкзаке на основе L - разбиения // Алгебра и линейная оптимизация: тезисы междунар. конф., посвященной 100-летию С.Н. Черникова. Екатеринбург, 2012. - С. 94-95.

[30] Колоколов A.A., Орловская Т.Г. Исследование некоторых постановок задачи о рюкзаке и алгоритмов их решения с использованием унимодулярных преобразований и L - разбиения // Интеллектуализация обработки информации: 9-ая междунар. конф. Черногория, г. Будва, 2012 г.: Сборник докладов. - М.: Торус Пресс, 2012. - С. 286-289.

[31] Орловская Т.Г. Улучшение структуры семейств задач о рюкзаке с использованием унимодулярных преобразований // Алгебра и линейная оптимизация: тезисы междунар. конф., посвященной 100-летию С.Н. Черникова. Екатеринбург, 2012. - С. 122-124.

[32] Kolokolov A.A., Orlovskaya T.G., Rybalka M.F. Analysis of some integer programming algorithms based on the method of regular partitions // Optimization and applications (OPTIMA-2011): Proceedings of II International Conference, Petrovac, Montenegro, September 25 -October 2, 2011. - P. 133-136.

Подписано в печать 07.05.2013. Формат 60x84/16. Бумага писчая. Оперативный способ печати. Усл. печ. л. 1,0. Тираж 140 экз. Заказ № 238.

Отпечатано в «Полиграфическом центре КАН» тел. (3812) 24-70-79, 8-904-585-98-84.

E-mail: pc_kan@mail.ru 644050, г. Омск, ул. Красный Путь, 30 Лицензия ПЛД № 58-47 от 21.04.97

Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Орловская, Татьяна Геннадьевна, Омск

Омский филиал

Федерального государственного бюджетного учреждения науки Института математики им. С.Л. Соболева Сибирского отделения Российской академии наук

На правах рукописи ПіуГп "Я95і і /

ОРЛОВСКАЯ Татьяна Геннадьевна

01.01.09 - Дискретная математика и математическая кибернетика

Диссертация на соискание ученой степени кандидата физико-математических наук

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

Омск - 2013

Оглавление

Введение 3

1 Модели и методы целочисленного программирования 9

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

1.2 Метод регулярных разбиений . . .................................14

1.3 О применении унимодулярных преобразований ................33

2 Исследование и решение задач о рюкзаке на основе Ь — разбиения 39

2.1 Унимодулярные преобразования для задач о рюкзаке..........40

2.2 Анализ Ь - структуры и алгоритмов решения задач о рюкзаке 48

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

3 Анализ г — алгоритма решения задач целочисленного линейного программирования 69

3.1 Специальный класс задач целочисленного линейного программирования иг- алгоритм........................................70

3.2 Исследование г - алгоритма с использованием регулярных разбиений ..............................................................75

3.3 Об оценках числа итераций........................................84

Заключение 88

Литература 90

Введение

Актуальность темы. Для решения многих задач, возникающих в планировании, управлении, проектировании и других областях, применяются модели и методы целочисленного программирования (ЦП), в которых учитываются такие факторы, как неделимость объектов, дискретность процессов, альтернативность выбора. Аппарат ЦП широко используется при исследовании различных классов задач дискретной оптимизации, в частности задач оптимального размещения [3-5,9,24,42,65], о покрытии [18,72], об упаковке [28,53,63], выполнимости логической формулы [1,34,35], задач с логическими и ресурсными ограничениями [43]. Значительный интерес к задачам ЦП обусловлен их MV - трудностью [12].

Проблематика ЦП является достаточно разнообразной и включает исследование структуры и сложности задач, разработку и анализ методов их решения, изучение вопросов устойчивости задач и алгоритмов, многокритериальные постановки и ряд других [1,2,4-8,13,16,17,19-21,31,32,35, 36,39,42,54-57,60,62,66,67,69,70,73-75,77,79-90,92,95,96].

В настоящее время в целочисленном программировании активно развивается предложенный A.A. Колоколовым метод регулярных разбиений [31, 32,52]. Наиболее изученным разбиением является L - разбиение, на основе которого разработаны алгоритмы решения задачи о покрытии, задачи о рюкзаке, задач выполнимости и других [27,31,39]. С помощью этого метода исследована L - структура некоторых задач ЦП [22,31,32,39,64], построены оценки числа итераций для ряда известных алгоритмов [21, 27, 29], введены новые классы отсечений [23,31,32,75], получены результаты по устойчивости задач и алгоритмов дискретной оптимизации [13,36].

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

Одним из таких направлений, показавших свою продуктивность и актуальность, является построение и исследование упимодулярных преобразований [17,30,77], с помощью которых исходная задача сводится к эквивалентной ей задаче ЦП [15,38]. Применение унимодулярпых преобразований сохраняет множество допустимых целочисленных точек, но может сделать структуру задачи более приемлемой для решения.

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

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

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

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

образований, улучшающих L - структуру задач о рюкзаке.

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

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

4. Исследовать 2 - алгоритм Вотякова A.A. для решения задач ЦЛП на основе регулярных разбиений.

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

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

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

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

Апробация работы. Результаты диссертации докладывались на IV и V Всероссийских конференциях 11 Проблемы оптимизации и экономические прилоэюения" (Омск, 2009 и 2012), VII Международной научно-тех-пической конференции "Динамика систем, механизмов и машин" (Омск, 2009), Российской конференции "Дискретная оптимизация и исследование операций" (Алтай, 2010), 8-й и 9-й Международных конференциях "Интеллектуализация обработки информации" (Кипр, 2010 и Черногория, 2012), XIV Всероссийской конференции 11 Математическое программирование и приложения1'1 (Екатеринбург, 2011), XV Байкальской международной школе-семинаре "Методы оптимизации и их прилоэюения" (Иркутск, 2011), Международной конференции " Алгебра и линейная оптимизация", посвященной 100-летию С.П. Черникова (Екатеринбург, 2012),

на заседании научного семинара отдела математического программирования Института математики и механики им. H.H. Красовского УрО РАН (Екатеринбург, 2012), а также на заседаниях научного семинара "Математическое моделирование и дискретная оптимизация" Омского филиала Института математики им. C.J1. Соболева СО РАН и Института математики и информационных технологий ОмГУ им. Ф.М. Достоевского (Омск, 2009 - 2012).

Публикации. Основные результаты диссертации опубликованы в 11 научных работах [44-52,64,91], две из них — в журналах из списка ВАК [46,52].

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

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

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

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

Глава 1

Модели и методы целочисленного программирования

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

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

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

В п. 1.3. рассматривается применение упимодулярных преобразований пространства как подход к улучшению Ь - структуры и ускорению процессов решения задач ЦЛП [15, 52]. Упимодулярлым называется преоб-

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

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

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

Рассмотрим следующую задачу ЦЛП общего вида:

xq = ^cjXj —max (1-1)

3=1

при условиях

УЧ CLijXj ^bi, г = 1, ..., га, (1.2)

3=1

Xj ^ о, .7 = 1, ..., п, (1.3)

х5 G Z, j = 1, ..., п. (1.4)

Здесь Cj, Ь{, dij 6 К, г = 1, ..., т, j = 1, ..., п, Z — множество всех целых чисел, х = (xi, ..., хп).

Задача (1.1)-(1.4) может рассматриваться как дискретная задача планирования производства в следующей формулировке. Пусть Cj — прибыль, получаемая от реализации единицы j-й продукции, j = 1, ..., п\ bi — доступное количество г-го ресурса, i = 1, ... , га; — расход г-ro ресурса на

выпуск единицы з~\\ продукции, г = 1, ..., га, ] — 1, ..., п. Переменные задачи: — объем выпуска ^'-й продукции, 3 = 1, ■ ■ ■, п. Требуется найти целочисленный вектор х* — (х^. ..., X'*), удовлетворяющий ограничениям по имеющимся ресурсам и максимизирующий суммарную прибыль от реализации продукции.

Эта постановка может рассматриваться как многомерная задача о рюкзаке. Пусть имеется п типов предметов и рюкзак с га измерениями. Обозначим через с^ ценность _;-го предмета, 3 = 1, ■ • •, та, а через — вместимость рюкзака по г-му измерению, г = 1, ..., га. Величина а^ определяет объем, который в г-м измерении занимает j-й предмет, г = 1, ..., га, 3 = 1, ■ ■ ■, п. Необходимо найти целочисленный вектор х* ~ {х\, ..., ж*), удовлетворяющий требованиям вместимости рюкзака по всем измерениям и максимизирующий суммарную ценность помещенных в него предметов. Математическая модель задачи имеет вид (1.1)-(1.4). При замене условий (1.3), (1.4) па требование х^ € {0, 1}, j = 1, ..., п, постановка соответствует булевой задаче о рюкзаке. Одномерная задача о рюкзаке является частным случаем многомерного варианта при га = 1.

Значительное внимание в данной работе уделяется различным вариантам задачи о рюкзаке. В главе 2 приведены результаты исследований указанной задачи на основе Ь - разбиения и проведенного вычислительного эксперимента.

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

найти лексикографически максимальный элемент множества П 271, т.е.

г* = 1ехтах (ПП%п), (1.5)

где ф 0 — выпуклое замкнутое ограниченное сверху множество в пространстве Кп, т. е. существует вектор (¡ей" такой, что х ^ с/ для всех х £ О. Множество называется релаксационным множеством задачи.

Важную роль в изучении задачи (1.5) и алгоритмов ее решения играет

множество

— {х 6 П : х У г для всех гЕ^П

которое называется дробным накрытием задачи (1.5) и последовательно 11 снимается" в процессе решения алгоритмами отсечения, ветвей и границ, перебора Ь - классов и другими. Отметим, что здесь и далее символом * обозначаются дробные накрытия задач целочисленного программирования. Во многих алгоритмах для нахождения оптимального решения дробное накрытие должно быть полностью удалено из релаксационного множества и, таким образом, его "объем" может использоваться в качестве характеристики сложности задачи.

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

М — < х € К" : агзхз ^ г = 1, ..., т, х^ ^ 0, з = 1, ..., п I

I ¿=1 )

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

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