Министерство высшего ипрофессионального образования РФ
Тульский государственныйуниверситет
КАФЕДРА ПРИКЛАДНОЙМАТЕМАТИКИ И ИНФОРМАТИКИ
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовому проекту подисциплине
«ВАРИАЦИОННОЕ ИСЧИСЛЕНИЕИ ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ»
на тему:
«Методы отсечения»
Тула 2003 г.
Содержание
Введение
1. Постановка линейнойцелочисленной задачи
2. Теоретические основы методов отсечения
3. Первый алгоритм Гомори
4. Второй алгоритм Гомори
5. Алгоритм Дальтона иЛлевелина
6. Алгоритм Данцига
7. Некоторые выводы
Заключение
Список литературыПриложение
Введение
Среди практически важных задач отыскания условного экстремумалинейной функции важное место занимают задачи с требованием целочисленностивсех (части) переменных. Они получили название задач целочисленного (частичноцелочисленного) программирования.
Историческипервой задачей целочисленного типа является опубликованная венгерскимматематиком Е. Эгервари в 1932 г. задача о назначении персонала.
Существуют различные методы решения таких задач, и заметное местосреди них занимают методы отсечения. Рассмотрим в этой работе некоторые изметодов отсечения, предварительно более подробно разобравшись с постановкойлинейных целочисленных задач.
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)) достигает наибольшего(наименьшего) значения, называется оптимальным решением.
Определив понятие допустимого и оптимального решения, естественнопоставить вопрос об их нахождении. Казалось бы, что естественный путь решенияцелочисленной задачи состоит в решении соответствующей линейной задачи споследующим округлением компонент ее оптимального плана до ближайших целыхчисел. На самом деле такой путь в большинстве случаев не только уводит, от оптимума,но даже приводит иногда к недопустимому решению задачи.
ПРИМЕР. В области, определенной условиями
/>
/> – целые
найти максимум функции />.
Решим задачу геометрически (рис. 1). Область поискаэкстремума – многоугольник ODABC, но так как линия уровня целевой функциипараллельна стороне АВ многоугольника, экстремум достигается в вершинах /> и />, а также в любой точкеотрезка АВ, и равен 7.
/>
(рис. 1)
Однако нас интересуют лишь точки с целочисленными координатами,следовательно, ни А, ни Вне являются допустимым решением задачи.Округляя значение координат А, получим /> Ноточка А' не принадлежит области поиска. Можно показать, что целочисленныйоптимум достигается в точках N (3; 2) и M (2; 3) и равен 5. Обеточки внутри области поиска.
Построенный нами пример показал, что для решения задач стребованием целочисленности необходимо рассмотреть особые методы оптимизации;и, кроме того, мы видим, что оптимальное решение задач целочисленногопрограммирования не обязательно принадлежит границе многогранника(многоугольника) условий, что было характерно для задач линейногопрограммирования.
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).
Методы,основанные на использовании процедуры построения правильных отсечений, получилиназвание методов отсечения.
3. Первыйалгоритм Гомори
Следуя общейсхеме методов отсечения, решим (£, C) – задачу (11, 12, 14),соответствующую (£ц, C) – задаче (11–14). Пусть x(£, C) – ее оптимальноерешение. Проанализируем координаты x(£, C) на целочисленность.Если все координаты вектора x(£, C) целые, то x(£, C) = x(£ц, C). Если хотя бы однакоордината, пусть xi, будет нецелой, поступим следующим образом.
Обозначимчерез N совокупность небазисных переменных и на основании последней симплекснойтаблицы запишем разложение xi по небазисным переменным xi, jÎN
/> (16)
Так как xi – нецелая величина,обозначим ближайшее целое число, не превосходящее xi, через [xi] и определим дробнуючасть: {xi}= xi- [xi]. Очевидно, (xi)>0.
Покажем, чтопо i-и строке симплекснойтаблицы (£, C) – задачи (в которой стоит нецелая координата решения) можноопределить дополнительное линейное ограничение, обладающее свойствамиправильности.
Теорема. Пусть /> — допустимое решение (£ц,C) – задачи, тогдасоотношения
/>, (17)
/>, /> — целое,
определяютправильное отсечение.
Доказательство.
Запишемвыражение (16)в виде:
/>
Используя дляэтого выражения формулу (17), получим:
/>
или
/>
На основаниипредположений теоремы о допустимости решения
(£ц,C) – задачи xi – целое. Величины [xio], /> — целые по определению,следовательно, zi – тоже целое.
Итак, zi определенное формулой (17),целое. Докажем что />. Доказательствобудем вести от противного. Пусть />.-
Это значит,что />. По определению дробнойчасти />. По условию теоремы x – допустимое решение (£ц,C) – задачи, поэтому />. Следовательно,
/>
Тогда должновыполняться:
/>
Итак, изпредположения отрицательности zi, сразу же получаем /> т.е. zi – нецелое. Посколькуранее было показано, что zi, определенное формулой (17), является целым, тотем самым мы пришли к противоречию. Следовательно, предположение, что zi
Следствие.Любоеоптимальное решение x(£, C) (£, C)– задачи, не являющееся допустимым решением (£ц,C) – задачи, неудовлетворяетусловию правильного отсечения (17).
Доказательство. Пусть х (£, C) – оптимальное решение (£,C) – задачи, xi0– дробное.
Покажем, что х(£, C)не удовлетворяет условию отсечения. Поскольку план оптимален, все небазисныепеременные xi, для jÎN равны нулю. Поэтому />.Учитывая это, подставим xio в формулу (17):
zi(x(£, C))= – {xi}+0,
чтопротиворечит условию неотрицательности zi. Следствие доказано.
Очевидно, чтоколичество дополнительных ограничений будет нарастать по мере решениявспомогательных (£, C) – задач, оптимальные планы которых будут содержатьнецелые координаты, т.е. возникает проблема размерности.
Р. Гоморипредложил прием, позволяющий ограничить размеры рассматриваемых симплексныхтаблиц вспомогательных задач величиной (n+2) (k+1), где n – количество переменных (£,C) – задачи, k – число небазисныхпеременных ее. Этот прием основывается на том, что нас интересуетдополнительное ограничение лишь как способ отсечения нецелочисленногооптимального решения вспомогательной задачи, полученной на данном шаге, иперехода к следующей задаче.
Последовательность(£, C) –задач пометим индексом k=0,1,…, соответствующим номеру итерации в последовательномприближении к решению исходной (£ц, C) – задачи, и обозначим(£k, C). При этом (£0, C) – задачасоответствует (£, C) – задаче (задаче без требования целочисленности).
Переменную zi, которая определяетсядополнительным линейным ограничением (7) и строится по некоторойнецелочисленной координате оптимального решения (£k, C) – задачи (k =0, 1, 2,…) обозначим xn+k+l.
Чтобыразмерность последовательности (£k, C) – задач невозрастала, вычеркнем из симплекс-таблицы переменную, по которой построенодополнительное линейное ограничение.
Послесделанных замечаний перейдем непосредственно к изложению вычислительной схемы.
1. Решим (£k, C) – задачу (вначале k = 0) методомпоследовательного улучшения плана.
Пусть в базисоптимального решения вошли векторы As1,…, Asm. Параметры последнейсимплексной таблицы обозначим через xij:
/>.
Если, всебазисные составляющие /> оптимальногорешения x(£k, C) (£k, C) – задачи целые, тоx(£k, C) = x(£ц, C). Если некотораякоордината xio оптимального решения x(£k, C) нецелая, то перейдем кп. 2.
2. Если среди совокупностикоординат оптимального решения x(£k, C) имеется единственная нецелая координата, то дополнительноелинейное ограничение (17) строится по этой координате. Если нецелых координат вx(£k, C) более одной, то выберемкоординату с наименьшим номером. Пусть ею оказалась xi0. Составим дополнительноелинейное ограничение
/> (18)
/> (19)
3. Добавим условия (18, 19)к условиям (£k, C) – задачи. Получим новую (£k+1, C) – задачу. Так какоптимальное решение x(£k, C) (£k, C) – задачи определяло одну из вершин многогранникаусловий, то оно может быть выбрано в качестве первоначального опорного решениядля вновь полученной задачи. А это означает, что последнюю симплексную таблицу(£k, C) – задачи можно взять в качестве исходной для (£k+1, C) – задачи, дополнивее условием (18).
Итак,симплексная таблица для (£k+1, C) – задачиполучается из последней симплексной таблицы для (£k, C) – задачи путемокаймления (i+1) –й строкой с элементами:
/>
/>
где /> – небазисные переменные (£k, C) задачи.
/>
Получим новуюзадачу, переменными которой являются />. Условияэтой задачи разрешены относительно xsl,…, xsm переменных и новойпеременной xn+k+1, а линейная форма выражена через небазисныепеременные (£k, C) – задачи. Так как мы занимаемся максимизацией F(x) и решение х* для (£k, C) – задачиоптимально, то все Di > 0. Поэтому процесс перехода к новомурешению (£k+1, C) – задачи не может быть осуществлен по методу уточненияплана. В то же время /> и поэтому векторА0симплексной таблицы не является опорным решением для (£k+1, C) – задачи, так как решениемназывается вектор, все координаты которого неотрицательны и удовлетворяютусловию принадлежности области £k+l. Поэтому назовемполученный вектор /> псевдорешениемзадачи (£k+1, C) и перейдем к дальнейшему преобразованию симплекс-таблицы.
Обозначимчерез k номерпсевдорешения (£k, C) – задачи; тогда направляющей строкой является i+k+1-я строка, k =0, 1, 2,…. Поэтому накаждом этапе преобразования таблицы вектор Ai+k+i будет выводиться изтаблицы. Можно доказать, что через конечное число шагов либо будет найденоцелочисленное решение, либо будет обнаружена ее неразрешимость, а тем самымнеразрешимость (£ц, C) – задачи.
Если решение(£k, C) – задачи завершается построением оптимальногоцелочисленного решения x*, то m, первых его компонент определяют решениецелочисленной задачи; если среди координат х* есть дробные, то одна из дробныхкомпонент (ранее определенным правилом) порождает дополнительное ограничение ипроцесс решения должен быть продолжен с новой окаймляющей строкой. Строка,используемая ранее для окаймления, вычеркивается и больше для построениярасширенных задач не восстанавливается.
Процедурурешения (£k, C) – задачи (k=0, 1,…) и анализа полученного решения назовембольшой итерацией. Номер большой итерации совпадает с номером решаемой (£k, C) – задачи.
Результатомбольшой итерации является переход к новой (£k+1, C) – задаче либоокончание решения задачи.
Сделаемнекоторые пояснения к блок-схеме алгоритма.
/>
Введем: 1)ячейку i,в которойбудем запоминать номер строки, на основании которой строится очередноедополнительное линейное ограничение, 2) счетчик r, соответствующий номерупроводимой большой итерации. Обозначим x*(£r, C) оптимальное решение (£r, C) – задачи. Заметим,что обозначение (£r, C) – задача, эквивалентное (£r, C), введено в блок-схемедля удобства записи.
При некоторыхусловиях удается доказать теорему о конечности первого алгоритма Гомори,которую мы приведем без доказательства.
Теорема. Пусть множествооптимальных планов задачи (£0, C) ограничено ивыполняются следующие условия:
1) сi – целые коэффициенты целевойфункции F(x) (i =1,2,…, n), строка целевой функциив симплексной таблице учитывается при выборе строки для построения правильногоотсечения;
2) справедливоодно из двух утверждений: либо целевая функция /> ограниченаснизу на Сo, либо задача (£ц, C) имеет хотя бы один планх'.
Тогда первыйалгоритм Гомори требует конечного числа больших итераций.
4. Второйалгоритм Гомори
Второйалгоритм Р. Гомори предназначается для решения задач, в которых требованиецелочисленности наложено на некоторые переменные (в частности и на все). Мы егорассмотрим применительно к задачам частично целочисленного типа, понимая, чтовычислительная схема будет справедливой и для задач, полностью целочисленных.
Пусть вобласти, определенной условиями:
/> (20)
/> (21)
/> – целые, />(22)
требуетсямаксимизировать функцию
/> (23)
Метод решениязадачи (20–23) основывается на той же идее, что и метод решения полностьюцелочисленных задач. А именно: строится область £k, которая при k = 0 определяетсяусловиями (20–21); решается полученная при этом задача линейногопрограммирования (20–21, 23). Если задача (20–21, 23) оказывается разрешимой,то полученное оптимальное решение ее анализируется на допустимость для исходнойзадачи целочисленного программирования (20–23). Если найденное решениеоказывается целочисленным, то одновременно оно будет оптимальным для (20–23).Если оптимальное решение (£k, C) – задачи оказывается недопустимым для исходной задачи(20–23), то осуществляется построение правильного отсечения и переход к решениюновой задачи,
Второйалгоритм Р. Гомори формулируется в виде следующей теоремы:
Теорема. Пусть х(£k, C) – оптимальное решение (£k, C) – задачи, /> – элементы соответствующейему симплексной таблицы. Если /> – нецелое/>, то
/> (24)
/> – целое, (25)
где
/> (26)
определяетправильное отсечение. Блок-схема второго алгоритма Р. Гомори аналогична блок-схемепервого алгоритма Р. Гомори и отличается лишь правилом построениякоэффициентов правильного отсечения.
Правилопостроения правильного отсечения
Пусть x(£k, C) не удовлетворяет условиюцелочисленности, /> – элементысимплексной таблицы, соответствующей полученному оптимальному решению (£k, C) – задачи. Выберем i=min {i| iÎ(1, 2,…, n), xik– нецелое} и строим правильноеотсечение по формулам (24 – 26).
Условия конечности второго алгоритма Гомори:
1) Целевая функция F(x) удовлетворяет условиюцелочисленности. Это учитывается при выборе строки kдля построенияправильного отсечения.
2) Выполнено по крайней мере одно из двух условий:
2') целевая функция ограничена снизу на многогранном множестве £=£0;
2») задача (£0ц, C)имеет по крайнеймере один план.
С помощьювторого алгоритма Гомори можно (в случае n1=n) решать и полностьюцелочисленную задачу линейного программирования. Однако в этом случае нетоснований для сравнения эффективности второго и первого алгоритмов Гомори.
5. АлгоритмДальтона и Ллевелина
Второй алгоритм Гомори имеет дело с частично целочисленнымизадачами линейного программирования. Дальтон и Ллевелин рассматривают 0 олееширокий класс задач – частично дискретные задачи линейного программирования иприменительно к ним модифицируют второй алгоритм Гомори.
Напомним, чторешением задачи дискретного программирования будем называть вектор, координатыкоторого принадлежат £ц области вида:
/> (27)
/> (28)
/> (29)
имаксимизирует значение функции
/>/>/> (30)
Будемпредполагать, что /> проранжированы, т.е. /> и являются напередзаданными числами.
Теорема. Пусть x(£k, C) – оптимальное решениезадачи (27–28, 30), /> – элементысимплексной таблицы, соответствующей ему.
Если x(£k, C) является недопустимымрешением задачи (27–30) и />,тогда, используя i-ю строку симплексной таблицы, можно построить отсечение,обладающее свойством правильности по формулам:
/> (31)
/> (32)
где
/>
/> (33)
Доказательство. Проверим вначале условиеотсечения. Пусть в оптимальном решении x(£k, C) координата /> не удовлетворяет условию (29).Покажем, что в этом случае вектор х(£k, C) не удовлетворяетусловиям (31, 32). Поскольку Nk – множество индексовнебазисных переменных xi, которые в оптимальномрешении равны нулю, то равенство (31) принимает вид /> ибудет отрицательным согласно условию теоремы. Следовательно, />, т.е. условие отсечения невыполняется.
Проверимусловие правильности. Для этого покажем, что любое допустимое решение задачи (27–30)удовлетворяет условиям (31, 32).
Запишемразложение для координаты допустимого решения задачи (27–30) по небазиснымпеременным
/> (34)
и рассмотримдва случая: a)/>; б) />. Введем обозначения:
/>
и представим(34) в виде
/>
где
/>
Очевидно, /> так как />.
Рассмотримслучай а): />, или что все равно, />.
Отсюда />Но />/>поэтому
/> (35)
Домножим обечасти (35) на неотрицательную величину /> исложим с неотрицательной величиной />:
/> (36)
Рассмотримслучай б): /> или, что все равно, /> Так как по определению />, то /> Умножим обе частинеравенства /> на неотрицательнуювеличину /> и на -1, получим />. Прибавляя к полученномувыражению неравенство />, получим
/> (37)
Такимобразом, в а) и в б) случаях пришли к одному и тому же неравенству (36)и (37). Пользуясь ранее введенными обозначениями, их можно записать
/> (38)
Формула (38) определяетправильные отсечения. Сравнивая ее с выражением (31–32), приходим к выводу, чтокоэффициенты />определяются следующимобразом:
/>
Теоремадоказана.
АлгоритмДальтона – Ллевелина может быть описан следующим образом.
1. Решается (£k, C) – задача (27–30)(вначале k =0). Пусть x(£k, C), k = 0, 1, 2,… оптимальное решение(£k, C) – задачи, /> – симплекснаятаблица.
2.Проверяется условие допустимости по всем координатам оптимального векторарешения х(£k, C) (£k, C) – задачи. Если условие допустимости выполняется, тополученное решение является оптимальным решением исходной задачи (27–30). Еслиусловие допустимости не выполняется хотя бы по одной координате, осуществляетсяпереход к 3.
3. Пусть /> не удовлетворяет условиюдопустимости. Тогда выбирается
i= min{i| 1in1, хjk– не удовлетворяет (29)}.
4. Длявыбранного номера i=iстроится правильноеотсечение, т.е. вводится дополнительная переменная
/>
где />определяется формулой (33),
5. Добавляемлинейное ограничение, определяющее правильное отсечение, к условиям (£k, C) – задачи иполучаем новую (£k+1, C) – задачу. Полагая k= k+ 1, переходим к п. 1.
Приведем бездоказательства теорему о конечности алгоритма.
Теорема. Если: коэффициентыцелевой функции дискретны; F(x) ограничена снизу на многогранном множестве £; задача (£,C) имеет по крайней мереодно решение; выбор строки для построения правильного отсечения производится поправилу минимального номера и (£k, C) – задачи решаютсяметодом последовательного уточнения оценок, то алгоритм Дальтона и Ллевелинасходится.
6. АлгоритмДанцига
Способ построения правильных отсекающих плоскостей, предложенныйДанцигом значительно проще, чем все изложенные выше способы. Но, как показалиГомори и Гофман, конечность алгоритма Данцига гарантируется лишь для оченьузкого класса задач. На примере алгоритма Данцига видно, насколько тонкимявляется вопрос о построении правильных отсечений и сколь осторожно следуетподходить к различным упрощенным алгоритмам.
Рассматривается полностью целочисленная задача линейногопрограммирования:
Максимизировать
/> (39)
при условиях
/> (40)
/> (41)
/> – целые, />(42)
Ранг матрицы /> считаем равным m.
Теорема. Пусть x(£r, C)=xr является оптимальным опорным планом задачи (£r, C) и xr не удовлетворяет условиюцелочисленности, Nr – множество индексов, нумерующих небазисные переменные,соответствующие xr.
Тогда неравенство
/> (43)
являетсяправильным отсечением.
Правильное отсечение, отсекающее нецелочисленный оптимум x(£r, C) задачи (£r, C), можно записатьследующим образом:
/>
/> – целое.
Заметим, что каждая из вновь вводимых переменных /> однозначно определяетсязаданием переменных/>, так что />.
Обозначим через /> упорядоченныев порядке возрастания компоненты /> плана x задачи (39) – (41), такчто
/>/> (44)
Положим
/> (45)
Лемма. Еслидля некоторого плана x задачи (39) – (41)
/>, (46)
то
/> (47)
Доказательство проведем по индукции. Сначала докажем, что
/> (47¢)
По определению
/> (48)
Так как ранг матрицы /> равен m, то
/>
где /> – числоэлементов множества />. Из определениячисел /> получаем
/> (49)
/> (50)
Из (48), (49), (50) и (46) имеем
/>
Лемма доказана при р=1.
Теперь допустим, что лемма верна при />, и докажем ее при />:
/>
Лемма доказана.
Пользуясь леммой, докажем две теоремы.
Теорема 1. Если каждый оптимальный план задачи (39)– (42) содержитне менее (m+2) положительныхкомпонент, то алгоритм Данцига не будет конечным.
Доказательство. Допустим, что на s-й итерации алгоритмаДанцига получится искомый оптимальный план />.Рассмотрим числа
/> (51)
Все они целые и среди них должно быть (n-m) нулей – это небазисныепеременные />. Кроме того, по условиюсреди чисел />, должно быть по крайнеймере (m+2) положительных числа, т.е. не больше чем (n-m-2) нулей.
По определению чисел /> отсюдаследует, что
/>
а так как /> должно бытьцелым, то
/> (52)
Но по определению чисел />
/> (53)
Из (52) получаем
/> (54)
и по лемме
/> (55)
Из (52), (53) и (55) следует, что среди чисел (51) по крайней мере[1+(m+1)+s] = [m+2+s] положительных, аследовательно, не больше чем [n+s– (m+2+s)] = (n-m-2) нулей. Но выше былоотмечено, что среди чисел (51) должно быть (n-m) нулей. Получилосьпротиворечие. Теорема 1 доказана.
Следствие (из теоремы 1). Для того чтобы алгоритм Данцига былконечным, необходимо, чтобы искомый оптимальный план лежал на ребремногогранного множества (40) – (41) (предполагается, что задача (39) – (41) невырожденная).
Хотя это условие и является весьма жестким, ему удовлетворяют,например, все (невырожденные) задачи следующего вида.
Максимизировать
/> (56)
при условиях
/> (57)
/> (58)
/> (59)
/> – целое, />/>/> (60)
А это важный класс задач.
Однако приведенное в следствии необходимое условиеконечности алгоритма Данцига не является достаточным. Действительно, имеетместо следующая
Теорема 2. Если для некоторого оптимального плана x' задачи (39) – (42) и некоторогоплана x»задачи (39) –(41) имеют место неравенства
/> (61)
и
/> (62)
то алгоритм Данцига не будет конечным.
Доказательство. Допустим, что алгоритм Данцига конечен. Тогда из(61) следует, что точка x» была отсечена на некоторой (скажем, р-й) итерации, такчто
/> (63)
Но из (62) и леммы получим
/> (64)
Сравнивая (63) и(64), получаемпротиворечие. Теорема 2 доказана.
Итак, упрощенный алгоритм Данцига будет конечным лишь в весьмаредких случаях.
7. Некоторые выводы
Попробуем охарактеризовать поведение алгоритмов метода отсеченияпри решении задач целочисленного линейного программирования. В качестве мерыпродолжительности вычислений могут рассматриваться количество симплексныхитераций Iи количество правильных отсечений (дополнительных линейных ограничений) D.
Для первого алгоритма Гомори и различных его обобщений I и D также тесно связаны междусобой (как показывает эксперимент, в большинстве случаев решение отдельнойзадачи (£, С) требует сравнительно небольшого количества симплексныхитераций).
Переходим к изложению отдельных свойств алгоритмов методаотсечения.
Числа I и D имеют (в среднем) тенденцию к возрастанию с увеличением числапеременных и ограничений, ростом порядка коэффициентов задачи и увеличениемзаполненности матрицы />.
Это явление кажется естественным, но опыт показывает, что вдискретном программировании «естественное» и «правдоподобное» не всегдаоказывается правильным. Точнее говоря, опыт, накопленный на задачах ЛИНЕЙНОГОПРОГРАММИРОВАНИЯ, нельзя механически переносить на задачи ЦЕЛОЧИСЛЕННОГОЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.
Прежде всего, обращает на себя внимание «нерегулярность»,«непредсказуемость» поведения алгоритмов метода отсечения. Для ряда задачоптимальное решение не удавалось получить после многих тысяч итераций, в товремя как другие задачи решались за несколько десятков итераций.
Не удается установить непосредственную связь между размерами задач(т.е. числом ограничений m и переменных n) и числом итераций: неудачи были зафиксированы даже для небольшихзадач (m≤10, n≤10), а успехи – для задачдостаточно большого размера (m = 215, n = 2600). Возможно, впрочем, что попытка установленияподобной связи – это неправомерное перенесение результатов ЛИНЕЙНОГОПРОГРАММИРОВАНИЯ в область ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.
Быть может, более естественной характеристикой задачи (£, С)является не число m линейных ограничений, задающих многогранное множество £, ачисло mц — линейных ограничений, задающих многогранное множество V(£)*). Между темлегко привести примеры, когда при небольших m и n число mц будет достаточно велико.
«Нерегулярность» сказывается и в следующем факте, подмеченномрядом исследователей: иногда удается существенно сократить число итераций засчет перенумерации переменных.
Наконец, имеет место немонотонность приближения псевдоплана Хr к оптимальному плану X* – с ростом r расстояние ρ(Хr, X*) не обязательноуменьшается и лишь на последней итерации обязательно становится равным нулю.
Большое влияние на число итераций оказывает правило выборапорождающей строки. Здесь также имеет место «нерегулярность» – в то время какодно правило приводит к успеху за десятки итераций, другое не дает решенияпосле тысяч итераций.
При решении задач целочисленного линейного программирования пометоду отсечения имеются как успехи, так и неудачи.
К наиболее успешным работам следует отнести:
1) Задачи покрытия, в том числе задачи, связанные с минимизациейбулевых функций.
2) Применение к задачам оптимального кодирования.
3) Применение к задаче оптимального извлечения информации изпараллельных систем памяти.
Наиболее характерными задачами, для которых имела место неудача,являются:
1) Задачи коммивояжера.
2) Задача теории расписаний.
3) Некоторые из обобщенных задач покрытия.
В настоящий момент отсутствует исчерпывающее объяснение удач илинеудач различных вычислительных экспериментов. Все же для задачи коммивояжера изадачи теории расписаний является правдоподобным следующее соображение.
Формулировка этих задач на языке ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГОПРОГРАММИРОВАНИЯ является «неестественной». Для задачи сравнительно небольшой в«естественной» формулировке, в модели ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯфигурирует большое количество ограничений и переменных. Возможно, что для этихзадач более перспективными являются комбинаторные методы (например, методветвей и границ для задачи коммивояжера). Впрочем, последнее утверждениеявляется спорным, так как комбинаторные методы очень чувствительны к спецификезадач, введению дополнительных условий и т.п.
По-видимому, успех в решении задач покрытия связан с тем, чтоудалось напасть на класс задач, практически важных и в то же время успешнорешаемых. Было бы весьма интересно точно охарактеризовать класс задач покрытия,хорошо решаемых по методу отсечения. Это тем более интересно, что построеныпримеры обобщенных задач покрытия, для которых возникают значительныевычислительные трудности.
И вообще, выделение отдельных классов эффективно решаемых задач – важнаяи интересная проблема.
Заключение
Подведем некоторые итоги. Метод отсечения находится в стадииразвития и совершенствования. При реализации этого метода возникают трудности,носящие, по-видимому, не только технический, но и принципиальный характер. Внастоящий момент можно говорить о решении с помощью метода отсечения задач неболее чем среднего размера (сотни переменных и десятки ограничений).
Наиболее перспективными для дальнейших исследований по методуотсечения представляются следующие направления:
1) Исследование строения множеств £ц и V(£ц).
2) Исследование свойств правильных отсечений.
3) Указание новых способов построения правильных отсечений.
4) Развитие новых классов алгоритмов метода отсечения (например,прямых алгоритмов).
5) Выделение отдельных классов эффективно решаемых задач.
Список литературы
1. Корбут А.А., Финкельштейн Ю.Ю.Дискретное программирование, М.: Наука, – 1969.
2. Лященко И.Н. Линейноеи нелинейное программирование, М.: Наука, – 1985.
3. Санович К.М. Исследованиеопераций, М.: Наука, – 1989.
Приложение
1. ПРОГРАММА,РЕАЛИЗУЮЩАЯ ПЕРВЫЙ АЛГОРИТМ ГОМОРИ
#include
#include
#include
#include
#include
#include
class simplex {int n; // числопеременных +1
int m; // числоограничений
int *basis;
int*mi;
float*mc;
intflag;
public:simplex(int m1, FILE *fp, int f);
~simplex()
{if(mi)free(mi);
if(mc)free(mc);
if(basis)free(basis);
}
voidprintsimtable (int g);
voiditerac();
voidresultat();
};
simplex:simplex(int m1, FILE *fp, int f)
{FILE*fp1;
intfl, i;
if((fp1=fopen(«hell1», «w+»))==NULL) {printf («Ошибка выделения памяти!»);
exit(1);
};
m=m1;
n=0;
basis=NULL;
flag=f;
fl=1;
do{fread(&c, sizeof (struct koef), 1, fp);
if(! feof(fp))
{do{fread(&i, sizeof(int), 1, fp1);
if(! feof(fp1) && i==c.ind)
{fl=0;
break;
}
} while(! feof(fp1));
if(fl){fwrite (&c.ind, sizeof(int), 1, fp1);
n++;
fflush(fp1);
}
elsefl=1;
rewind(fp1);
}
} while(! feof(fp));
rewind(fp);
if (m>n-1) {printf («Число ограниченийбольше или равно числу переменных»);
getch();
exit(1);
}
mi=(int*) malloc (sizeof(int)*n);
mc=(float*) malloc (sizeof(float)*n*(m+1));
if (! mc ||! mi) {printf («Ошибка выделенияпамяти!»);
getch();
exit(1);
}
fread(mi, sizeof(int), n, fp1);
qsort(mi, n, sizeof(int), sort);
fclose(fp1);
remove(«hell1»);
for(fl=0; fl
for(i=0; i
*(mc+fl*n+i)=0;
fl=m;
do{fread(&c, sizeof (struct koef), 1, fp);
if(! feof(fp))
{if(c.ind)
{for(i=1; i
if(c.ind==*(mi+i))
{*(mc+fl*n+i)=*(mc+fl*n+i)+c.coef;
break;
}
}
else{*(mc+fl*n)=c.coef;
if(fl==m) fl=0;
elsefl++;
}
}
} while(! feof(fp));
}
voidsimplex:iterac()
{inti, j, fl, fl1, k, l;
floats, min;
for(i=1; i
{if(*(mc+m*n+i)!=0)
{fl=1;
for(j=0; j
if(*(mc+j*n+i)!=0){fl=0;
break;
}
if(fl) {printf («Не все перменныецелевой функции входят в ограничения»);
getch();
exit(1);
}
}
}
basis=(int*) malloc (sizeof(int)*m);
if(! basis) {printf («Ошибка выделения памяти»);
getch();
exit(1);
}
for(i=0; i
*(basis+i)=0;
i=0;
do
{fl=1;
fl1=0;
for(j=1; j
if(*(mc+i*n+j)>0){fl=0;
break;
}
if(fl) {printf («Переменные должны бытьположительны»);
getch();
exit(1);
}
s=*(mc+i*n+j);
for(l=0; l
*(mc+i*n+l)=*(mc+i*n+l)/s;
for(l=0; l
if(l!=i) {s=*(mc+l*n+j);
for(k=0; k
*(mc+n*l+k)=*(mc+l*n+k) –s*(*(mc+i*n+k));
}
for(l=0; l
{s=0;
for(k=1; k
s=s+fabs(*(mc+l*n+k));
if(s==0) {if(*(mc+l*n)==0) printf («Уравнения линейнозависимы»);
else printf («Система ограниченийнесовместна»);
getch();
exit(1);
}
}
*(basis+i)=j;
for(l=0; l
if(*(mc+l*n)
for(k=0; k
*(mc+l*n+k)=– (*(mc+l*n+k));
for(l=0; l
if((*(basis+l)==0)||(*(mc+l*n+(*(basis+l)))
} while(fl1);
printsimtable(0);
do{min=100000;
fl=0;
for(l=1; l
{if(*(mc+m*n+l)>0){fl=1;
fl1=1;
for(k=0; k
if(*(mc+k*n+l)>0)
{fl1=0;
s=*(mc+k*n)/(*(mc+k*n+l));
if(s
i=k;
j=l;
}
}
if(fl1){printf («Решения нет»);
getch();
exit(1);
}
break;
}
}
if(fl){s=*(mc+i*n+j);
for(l=0; l
*(mc+i*n+l)=*(mc+i*n+l)/s;
for(l=0; l
if(l!=i) {s=*(mc+l*n+j);
for(k=0; k
*(mc+l*n+k)=*(mc+l*n+k) –s*(*(mc+i*n+k));
}
printsimtable(0);
*(basis+i)=j;
}
} while(fl);
}
voidsimplex:resultat()
{inti, j, fl;
if(flag==-1) printf («Минимальное значениефункции цели равно % 8.2f\n»,*(mc+m*n));
else printf («Максимальное значениефункции цели равно % 8.2f\n», – (*(mc+m*n)));
printf(«Оптимальныйплан:»);
for(i=1; i
{fl=0;
for(j=0; j
if(*(mi+i)==*(basis+j)){fl=1;
break;
}
if(fl)printf («x % 02d=%-5.2f\n»,*(mi+i),*(mc+j*n));
elseprintf («x % 02d=0 \n»,*(mi+i));
printf(«»);
}
}
voidsimplex:printsimtable (int g)
{inti, j, k, v=g, raz;
clrscr();
raz=n-1–6*(v+1);
if((raz
elseif (raz>0) raz=6;
elsereturn;
for(j=0; j
{if(j!=1) {printf(«* * *»);
for(i=0; i
printf(»*»);
if(raz
}
else{if(*(mc+m*n)>=0) printf («* *%8.2f *»,*(mc+m*n));
elseprintf («* * -%-7.2f *», – (*(mc+m*n)));
for(i=1; i
if(*(mc+n*k+6*v+i)>=0)printf («%8.2f *»,*(mc+n*k+6*v+i));
elseprintf («-%-7.2f *», – (*(mc+n*k+6*v+i)));
if(raz
}
}
for(i=0; i
printf(«*»);
getch();
rewind(fp);
simplexob (no, fp, f);
gomori();
ob.iterac();
ob.resultat();
}