Методы отсечения

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

Исторически первой задачей целочисленного типа является опубликованная венгерским математиком Е. Эгервари в 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 < 0, неверное. Теорема доказана.

Следствие. Любое оптимальное решение x(£, C) (£, C) тАУ задачи, не являющееся допустимым решением (£ц, C) тАУ задачи, неудовлетворяет условию правильного отсечения (17).

Доказательство. Пусть х (£, C) тАУ оптимальное решение (£, C) тАУ задачи, xi0 тАУ дробное.

Покажем, что х (£, C) не удовлетворяет условию отсечения. Поскольку план оптимален, все небазисные переменные xi, для jÎN равны нулю. Поэтому . Учитывая это, подставим xio в формулу (17):

zi(x (£, C))= тАУ {xi0}+0<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) тАУ задачи. Выберем i0=min {iiÎ(1, 2,тАж, ), xi0kтАУ нецелое} и строим правильное отсечение по формулам (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. Пусть Ване удовлетворяет условию допустимости. Тогда выбирается

i0= min {i| 1<i<1, хj0k тАУ не удовлетворяет (29)}.

4. Для выбранного номера i=i0 строится правильное отсечение, т.е. вводится дополнительная переменная

где определяется формулой (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-й итерации ал

Вместе с этим смотрят:


РЖнварiантнi пiдпростори. Власнi вектори i власнi значення лiнiйного оператора


РЖнтегральнi характеристики векторних полiв


РЖнтерполювання функцiй


Автокорреляционная функция. Примеры расчётов


Аксонометричнi проекцii