1612726855-66ce2678ed92310585f0bb1a36623206 (828576), страница 14
Текст из файла (страница 14)
Решаем задачу ЛП (линейного программирования)(c, x) ® min ,x Î Qk ,где Q k – текущее многогранное приближение множества Q Í Q k .Пусть x k – оптимальное решение этой задачи. Если x k – допустимое решение задачи (1)-(3), то найдено ее оптимальное решение. На этом алгоритмзавершает свою работу. В противном случае переходим к выполнению следующего шага.2. Выберем ограничение с номером ik , для которого величина j ik ( x k ) > 0максимальна.
Перейдем к выполнению следующей итерации с новым многогранным приближением Q k +1 = Q k I {x | jik ( x k ) + (ji¢k ( x k ), x - x k ) £ 0} множества допустимых решений Q задачи (1)-(3).Корректность определения множества Q k +11. Так как ограничение jik ( x k ) + (ji¢k ( x k ), x - x k ) £ 0 линейно, то множество Q k +1 является многогранным.2.ПосколькумножествоQkифункцияj ikвыпуклые,тоjik ( x k ) + (ji¢k ( x k ), x - x k ) £ jik ( x ) для всех x Î Q k (теорема 1.4).
Тогда из неравенства j i k ( x) £ 0 , x Î Q , следует включение Q Í Q k +1 . Другими словами,ограничение ji k ( x k ) + (ji¢k ( x k ), x - x k ) £ 0 является отсечением, которое позволяет исключить точку x k из множества допустимых решений. Следовательно, гиперплоскость jik ( x k ) + (ji¢k ( x k ), x - x k ) = 0 строго отделяет [2, 3]точку x k от множества Q . Поэтому она называется секущей плоскостью.Если алгоритм останавливается через конечное число шагов, то текущееприближение – оптимальное решение задачи. Рассмотрим случай, когда последовательность {x k }kÎN бесконечна.76Теорема 3. Любая предельная точка последовательности {x k }k ÎN , порожденная методом секущих плоскостей, есть оптимальное решение задачи.Доказательство. Последовательность {( c, x k )}k ÎN монотонно неубывающая и ограничена сверху, так как существует оптимальное решение.
Поэтому, без ограничения общности считаем, что последовательность {x k }k ÎNограничена и сходится к x . Выберем произвольное ограничение с номеромi , i Î {1, K , m} . Пусть {x k }kÎT , где T Í N , – подпоследовательность элементов, для которых секущая плоскость порождалась с помощью i -го ограничения. Возможны два случая.1.
Множество T – конечное, тогда найдется номер k 0 такой, чтоj i ( x k ) £ 0 для всех k ³ k 0 . Поэтому ji ( x k ) ® ji ( x ) £ 0 при k ® ¥ .2. Множество T – бесконечное, тогда для любого k ¢ > k выполняетсяj i ( x k ) + (j i¢ ( x k ), x k ¢ - x k ) £ 0 . Следовательно, j i ( x k ) £ || j i¢ ( x k ) || || x k ¢ - x k || .Так как || x k ¢ - x k ||® 0 при k ® ¥ , что следует из сходимости последовательности, то || j i¢ ( x k ) || ® || j i¢ ( x ) || при k ® ¥ , j i Î C1( R n ) .Таким образом, j i ( x k ) ® j i ( x ) £ 0 при k ® ¥ . Следовательно, x – допустимое решение задачи в силу произвольного выбора i .
Но для любого kимеем ( c, x k ) £ ( c, x* ) , следовательно, ( c, x ) £ ( c, x* ) . То есть x – оптимальное решение задачи. ▄§ 3. Первый (или циклический) алгоритм ГомориВ данном параграфе рассматривается алгоритм решения задачи целочисленного линейного программирования (ЦЛП). Постановка такой задачи получается из задачи линейного программирования добавлением условий целочисленности переменных. Сформулируем идею алгоритма решения такихзадач. Рассмотрим разрешимую задачу ЦЛП. Известно [10], что выпуклуюоболочку множества допустимых решений задачи ЦЛП можно описать конечной системой линейных ограничений. Очевидно, что вершины соответствующего многогранного множества содержатся среди допустимых решенийзадачи ЦЛП. Далее применяется один из вариантов симплекс-метода.
Полученное таким способом оптимальное базисное допустимое решение являетсяоптимальным решением исходной задачи ЦЛП. Существенный недостатоктакого способа решения целочисленных задач связан с трудностями, возникающими при построении конечной системы линейных ограничений, определяющих выпуклую оболочку [10].77Данциг предложил более простой подход, основанный на использованиилинейной релаксации задачи ЦЛП, получаемой удалением условий целочисленности.
Если при решении линейной задачи с помощью симплекс-методаполученное оптимальное б.д.р. является целочисленным, то оно и есть искомое оптимальное решение задачи ЦЛП. В противном случае генерируется поопределенным правилам новое линейное ограничение, которое называетсяотсечением, и оно добавляется к ограничениям задачи ЦЛП. Решаем новуюлинейную релаксацию. И так далее. Поступая подобным образом, удаетсяотсечь те части многогранника линейной релаксации исходной задачи, которые не содержат целочисленных допустимых решений исходной задачи.
Приэтом оптимальное целочисленное решение может быть получено раньше, чемстягивающиеся допустимые области линейных релаксаций сократятся доразмеров выпуклой оболочки.3.1. Задача ЦЛП, отсечение ГомориПриведем постановку задачи ЦЛП, которую далее будем обозначать IP:cx ® minAx = b ,x³0,x j – целое, j = 1,K.n.Множество допустимых решений этой задачи будем обозначать как QIP .ЛП-релаксация задачи IP совпадает с задачей ЛП в канонической форме(3.1)-(3.3).Пусть x 0 – оптимальное решение ЛП-релаксации задачи IP. Если x0 Î Z n ,то x 0 – оптимальное решение задачи IP.
Иначе в соответствии с описаннымвыше рецептом следует добавить к ЛП-релаксации новое ограничение такое,что:– x 0 этому ограничению не удовлетворяет (отсекается);– все допустимые решения задачи ЦЛП остаются допустимыми решениями новой задачи ЛП.Опишем способ построения отсечений, впервые реализованный Гомори.Предположим, что оптимальное решение ЛП-релаксации получено с помощью двойственного симплекс-метода, изложенного в главе 3. Так как решение оказалось нецелочисленным, то среди уравнений (3.15), образующих оптимальную симплекс-таблицу, найдется такое уравнение, в котором значениебазисной компоненты zi 0 является нецелым. Рассмотрим это уравнение,опустив в нем для упрощения индекс i :x p = z p 0 - å z pj x j(13)jÎS ¢Для x Î QIP имеем78å ëz pj û x j £ z p0 .xp +jÎS ¢В силу целочисленности x p и x pj на множестве Q IP имеемx p + å ëz pj û x j £ ëz p0 û .jÎS ¢Из (13) получимz p0 ПреобразуемåjÎS ¢å ëz pj û x j £ ëz p0 û .z pj x j +jÎS ¢å ( ëz pj û - z pj ) x j £ ëz p 0 û - z p 0jÎS ¢илиå (- f pj ) x j £ - f p 0 ,jÎS ¢где f pj – дробная часть z pj = ëz pj û + f pj , 0 £ f pj < 1 .Если к задаче IP добавить ограниченияu = - f p0 -å ( - f pj ) x j ,jÎS ¢u ³ 0, uÎZ ,то получим эквивалентную задачу.3.2.
Первый алгоритм ГомориПриведем описание первого или циклического алгоритма отсечения Гомори. Он основывается на лексикографическом варианте двойственного симплекс-метода, изложенного в главе 3. В процессе работы алгоритма числоиспользуемых одновременно отсечений не превосходит числа небазисныхпеременных.Ниже приводится описание одной итерации алгоритма, состоящей из 5шагов. Шаг с номером 0 выполняется только один раз на первой итерации.Обозначим через n число итераций, на которых вводятся отсечения.Шаг 0. Начать с нормальной симплекс-таблицы.
Положить n := 0 .Шаг 1. Если симплекс-таблица прямо допустима и все элементы z p 0 ,p = 1,K, n , целые, то КОНЕЦ: получено оптимальное решение задачи ЦЛП.Шаг 2. Если симплекс-таблица прямо допустима, то выбрать минимальное p Î {1,K, n} такое, что z p 0 – нецелое; положить n := n + 1 .Строку с номером p назовем производящей. Этой строке соответствуетуравнение79lå z pj xt ( j ) ,x p = z p0 -j =1которое называется отсечением Гомори и используется для построения дополнительного ограничения, здесь l – число небазисных переменныхxn +n = - f p 0 -lå (- f pj ) xt ( j ) ³ 0 ,j =1где f pj – дробная часть числа z pj ( z pj = ëz pj û + f pj , 0 £ f pj < 1 ).К симплекс-таблице добавляется ( n + 1 )-ая строка (отсечение Гомори), соответствующая дополнительному ограничению с базисной переменной xn +n .Шаг 3.
Выбрать ведущую строку r такую, что zr 0 < 0, r Î {1,K, n} .Шаг 4. Если { j z pj < 0, j Î {1,K, l}} ¹ Æ , то выбрать ведущий столбец sпо правилуüïìï 11b s = lex min íb j zrj < 0, j Î {1,K, l}ý ,zrszïþîï rjиначе КОНЕЦ (текущая задача ЛП, а, следовательно, и исходная задача ЦЛП,неразрешима ввиду несовместности ее ограничений).Шаг 5. Преобразовать симплекс-таблицу; положить t ( s ) := n + n и отбросить ( n + 1 )-ую строку, если таковая имелась, иначе t ( s ) := r ;перейти на шаг 1 .Пусть x 0 = ( z10 ,K, zn 0 )T – базисное допустимое решение ЛП-релаксациицелочисленной задачи соответствующее текущей симплекс-таблице в моментвведения отсечения Гомори.
Из описания алгоритма следует, что это б.д.р.является оптимальным решением линейной релаксации задачи. Так как z p 0 –нецелое, то f p0 > 0 , следовательно,xn +n ( x 0 ) = - f p0 < 0 .Поэтому оптимальное решение линейной релаксации отсекается.Пустьxn +n = - f p 0 -lå (- f pj ) xt ( j ) ³ 0j =1является отсечением Гомори, полученным на шаге 2.
Так как - f p 0 < 0 , тоxn +n – единственная отрицательная базисная переменная. Следовательно,симплекс-таблица двойственно допустима, но не прямо допустима. Это означает, что на шаге 3 в качестве ведущей будет выбрана ( n + 1 )-ая строка, таккак это единственная строка, нарушающая прямо допустимость текущей симплекс-таблицы.80При элементарном преобразовании этой таблицы переменная xn +n станетнебазисной. Ведущая строка превращается в тождество xn +n = ( -1)( - xn +n ) ина шаге 5 удаляется из симплекс-таблицы.3.3.
Обоснование конечности алгоритма ГомориПри обосновании алгоритма будут использоваться следующие предположения.1. Известно, что оптимальное значение целевой функции ограниченноснизу некоторой константой.2. Целевая функция задачи ЦЛП принимает целочисленные значения намножестве допустимых решений QIP . Тогда переменная x0 будет приниматьцелочисленные значения и, следовательно, нулевая строка симплекс-таблицыможет быть использована в качестве производящей.Итерация алгоритма, то есть шаги с 1 по 5, называется LD-итерацией, если во время ее выполнения не вводится отсечение. И называется итерациейГомори, если на шаге 2 вводится отсечение.Элементы и столбцы симплекс-таблицы, полученной после выполненияпервых t итераций, обозначим zijt и b tj , соответственно.
Через zij0 обозначим элементы начальной симплекс-таблицы.Доказательство конечной сходимости алгоритма проведем методом отпротивного. Пусть при решении задачи алгоритмом Гомори выполняетсябесконечная последовательность итераций. Из описания LD-метода имеемb 00 f b 01 f b 02 f L f b 0t f b 0t +1 f K .(14)Из конечности этого метода следует, что число итераций Гомори бесконечно.Действительно, если число итераций Гомори конечно, то тогда, начиная снекоторого момента, LD-методом бесконечное число раз решается одна и таже задача ЛП, а это невозможно.Пусть ( tn + 1 ), n = 1,2,K , – порядковые номера этих итераций. Из (14)имеем02tt +1z00³ z100 ³ z00³ L ³ z00³ z00³K.Рассмотрим подпоследовательностьt1 t 2tnz00, z00 ,K, z00,K,состоящую из элементов(15)z00 тех симплекс-таблиц, которые являютсяtnвходными для итераций Гомори.
Пусть z 00– нецелое. Тогда на итерации( tn + 1 ) нулевая строка будет производящей и справедливоt +1nz00tntnt f= z00- z0ns 00.tf 0ns81tttТак как z0ns ³ 0 и z 0ns ³ f 0ns , тоë ûtn +1tntntntnz00£ z00- f 00= z00< z00.Таким образом, каждый интервал ( z, z + 1) , где z – целое, содержит не более одного нецелого элемента последовательности (15). Из монотонности иограниченности снизу этой последовательности следует, что она стабилизируется на некотором целом значении.
Тогда существует T0 такое, что дляtвсех t ³ T0 выполняется z00= z00 , где z00 – целое число.В силу строгого лексикографического убывания нулевого столбца выполняются соотношенияT +1Tz100 ³ z100tt +1³ L ³ z10³ z10³ K.(16)tnПо условию z10– нецелое. Тогда на итерации ( tn + 1 ) первая строка будетпроизводящей и выполняется равенствоt +1nz10tntnt f= z10- z1ns 10,tf1sn(17)tnгде 0 < f10< 1 и 0 < f1tsn < 1 .z1tns < 0 .Пустьtn +1z00=tnz00-tntn f10z0 s tf1snТаккакb stnf 0 ,тоz0tns > 0 .Изусловийtttn +1tn< z00, что проти, 0 < f10n < 1 , 0 < f1sn < 1 получим z00tn +1tnворечит равенству z00= z00. Таким образом из (17), учитывая неравенстваz1tns ³ 0 и z1tns / f1tsn ³ 1 , имеемë ûtnz10ë ûtn +1tntntntnz10£ z10- f10= z10< z10.tnz10ë ûtnz10Следовательно,<<+ 1 . Это означает, что каждый интервал( z, z + 1) , где z – целое, содержит не более одного нецелого элемента из последовательности (16).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
