Теоретические основы методов отсечения

Содержание

 

Введение 3 
1.Постановка линейной целочисленной задачи 5 
2.Теоретические основы методов отсечения 8 
   2.1 Первый алгоритм Гомори 12 
   2.2 Второй алгоритм Гомори 18 
Заключение 20 
Список используемых источников 23 

 

 

 

Введение

 

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

Исторически первой задачей целочисленного типа является опубликованная венгерским математиком Е. Эгервари в 1932 г. задача о назначении персонала.

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

Методы отсечений  относятся к численным методам решения дискретных задач оптимизации (методам дискретного программирования). Они предназначены для решения целочисленных задач линейного программирования (ЛП). Идея методов отсечения состоит в следующем.

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

1) полученное  нецелочисленное решение ему  не удовлетворяет;

2) все целочисленные  точки допустимого множества  исходной задачи ему удовлетворяют. Такое ограничение называется правильным отсечением.

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

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

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

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

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

 

 

 

1. Постановка линейной целочисленной задачи

 

Среди совокупности п неделимых предметов, каждый i-и (i=1,2,…, п) из которых обладает по i-й характеристике показателем и полезностью найти такой набор, который позволяет максимизировать эффективность использования ресурсов величины .

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

в области, определенной условиями

 (1);   (2); - целые, . (3)

найти решение  при котором максимизируется (минимизируется) значение целевой функции

 (4)

Если  , то (1–4) является моделью задачи целочисленного программирования, если - моделью задачи частично целочисленного программирования.

Частным случаем задачи целочисленного программирования является задача с булевыми переменными. Ее математическая модель в общем виде записывается следующим образом:

в области, определенной условиями

 (5); (6)

найти решение  , при котором максимизируется (минимизируется) значение функции

 (7)

 

К классу задач целочисленного программирования примыкают задачи, в которых условие целочисленности всех или части переменных заменено требованием дискретности. А именно, для каждой j-и переменной заранее определен набор значений (не обязательно целых), которые она может принимать: где .

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

в области, определенной условиями

(8); (9)

найти решение  , при котором максимизируется (минимизируется) линейная функция

 (10)

Условие (9) определило название этого класса; задач. Если , то (8–10) называется задачей дискретного программирования; если , то (8–10) называется задачей частично дискретного программирования.

Условие (2–3) задачи (1–4) и условие (6) задачи (5–7) являются частным случаем условия (9) задачи (8–10). Действительно, (2–3) соответствует тому случаю, когда для . Условие (9) соответствует случаю, когда .

Для задач целочисленного типа определено понятие допустимого и оптимального решения.

Вектор  , удовлетворяющий условиям (1–3) (соответственно (8–9)), называется допустимым решением задачи (1–4) (соответственно (8–10)). Допустимое решение, при котором функция (4) (соответственно (10)) достигает наибольшего (наименьшего) значения, называется оптимальным решением.

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

 

 

2. Теоретические основы методов отсечения

 

Запишем общую задачу целочисленного программирования: в области, определенной условиями

 (11);   (12); - целые, (13)

максимизировать функцию:  (14).

Назовем для кратности  задачу (11–14) (£^ц, C) – задачей. Соответствующую ей задачу без требования целочисленности переменных, т.е. задачу (11, 12, 14) назовем (£, C) – задачей. Поставим вопрос: нельзя ли решение (£^ц, C) – задачи получить путем решения некоторой специальным образом построенной задачи без требования целочисленности переменных и такой, что оптимальные решения исходной (£^ц, C) – задачи и задачи без требований целочисленности переменных будут совпадать. Другими словами: нельзя ли хорошо изученный аппарат решения задач линейного программирования приспособить к решению целочисленных задач. Принципиальный ответ на этот вопрос дает следующая теорема.

Теорема. Пусть £ – многогранник, £^ц – множество его целых точек, R – выпуклая, линейная оболочка множества £^ц, тогда:

1) R=R^ц – целочисленный многогранник;

2) R^ц = £^ц;

3) R* – множество опорных решений задачи (£^ц, C) содержится в многограннике R^ц.

Доказательство. Докажем, что R – целочисленный многогранник. По условию теоремы £ – многогранник, поэтому множество его целых точек (оно обозначено через £^ц) конечно. Поскольку R – выпуклая линейная оболочка этого конечного множества точек, R – тоже многогранник.

По самому определению выпуклой линейной оболочки, она содержит все  опорные планы множества, на которое она натянута, т.е. многогранник R содержит все целочисленные точки £^ц. Поэтому R – целочисленный многогранник. Обозначим его через R^ц. Первая часть теоремы доказана.

Докажем, что R^ц совпадает с £^ц. Так как R – выпуклая оболочка точек множества £^ц, то £^ц ÍR^ц.

Покажем, что справедливо также  и противоположное неравенство–включение, т.е. R^цÍ£^ц. Для этого выберем некоторый произвольный элемент х°ÎR^ц. Поскольку R^ц содержит все опорные решения задачи (£^ц, C), то х° удовлетворяет условиям задачи (£^ц, C), т.е. х°Î£^ц. Но поскольку произвольный элемент из R^ц принадлежит £^ц, то очевидно, что справедливоR^цÍ£^ц. Сопоставляя противоположные включения R^цÍ£^ц и £^цÍR^ц приходим к выводу: что £^ц=R^ц. Вторая часть теоремы также доказана.

Доказательство 3-го пункта теоремы является совершенно очевидным. Так как R^* – множество опорных решений задачи (£^ц, C), то R^*Í£^ц но £^ц=R^ц, поэтому R^*ÍR^ц

Теорема доказана.

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

Доказанная теорема и следствие  из нее показывают принципиальную возможность  замены решения задачи типа (£^ц, C) некоторой процедурой построения и решения вспомогательной задачи типа (£, C), однако не дают алгоритма решений. К тому же построение выпуклой оболочки множества £^ц реальных задач – чрезвычайно сложная, а подчас практически неразрешимая задача,

В 1954 г. Дж. Данциг высказал идею о том, что построение выпуклой оболочки целочисленной области для задачи (£^ц, C) можно осуществлять поэтапно и решать получаемые при этом задачи. Однако при этом возникли вопросы как строить ограничения новой задачи и как обеспечить конечность процесса.

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

Алгоритм Р. Гомори состоит из следующих  процедур:

1. Решается (£, C) – задача, соответствующая исходной (£^ц, C) – задаче.
2. Полученное оптимальное решение (£, C) – задачи, если оно существует, проверяется на целочисленность. Если условие целочисленности выполняется по всем переменным, то оптимальное решение (£, C) – задачи есть оптимальное решение (£^ц, C) – задачи. Если условие целочисленности не выполняется хотя бы по одной координате, то переходят к третьему этапу. Если (£, C) – задача, оказывается неразрешимой, то (£^ц, C) – задача тоже решения не имеет.
3. Строится дополнительное ограничение, обладающее тем свойством, что с его помощью отсекается часть области, в которой содержится оптимальное решение (£, C) – задачи и не содержится ни одного допустимого решения (£^ц, C) – задачи. Процесс построения дополнительных ограничений и решения получаемых при этом (£, C) – задач продолжается до тех пор, пока не получим целочисленного решения или не убедимся в неразрешимости задачи.

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

1. дополнительное ограничение должно быть линейным, чтобы оставаться в области применимости аппарата линейного программирования;
2. дополнительное ограничение должно отсекать часть области, в которой не содержится допустимых решений целочисленной (£^ц, C) – задачи, но есть найденное оптимальное решение нецелочисленной (£, C) – задачи, т.е. ограничение должно обладать свойством правильности, которое не позволяет потерять оптимальное решение исходной (£^ц, C) – задачи.

Пусть х (£, C) – оптимальное решение (£, C) – задачи, которое является недопустимым решением для (£^ц, C) – задачи. Неравенство

 (15)

определяет правильное отсечение, если удовлетворяет

а) условию отсечения: x(£, C) удовлетворяет неравенству (15)

б) условию правильности: любое  допустимое решение задачи (£^ц, C), удовлетворяет неравенству (15).

Методы, основанные на использовании  процедуры построения правильных отсечений, получили название методов отсечения.

 

 

2.1 Первый алгоритм Гомори

Следуя общей схеме  методов отсечения, решим (£, C) – задачу (11, 12, 14), соответствующую (£^ц, C) – задаче (11–14). Пусть x(£, C) – ее оптимальное решение. Проанализируем координаты x(£, C) на целочисленность. Если все координаты вектора x(£, C) целые, то x(£, C) = x(£^ц, C). Если хотя бы одна координата, пусть x_i, будет нецелой, поступим следующим образом.