Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 62
Текст из файла (страница 62)
Таким образом можно сосредоточить внимание на выборе производящей строки в стационарных циклах. В стационарном цикле О,а 1, н поэтому (.~.0 а1е а 1) Откуда строка 1 может быть выбрана как производящая тогда и только тогда, когда (8) аж ( а1е. Заметим, что из условий (8) и (5) можно вывести следующее заключение: если свойство (5) не выполняется, то существует бесконечная последовательность таблиц, в которых строка выбирается в качестве производящей. Поэтому необходимо доказать, что можно выбирать производящую строку среди строк с а;, ) а;а и при этом будет иметь место свойство (5).
Доказательство этого факта моясет быть получено как следствие из теоремы 17.1. Тноэнмл 17.1. Пусть дана таблица, в которой строка е индексом о — производящая и столбец а, — ведущий. И пусть а,т — )-й элемент строки щ а а„— соответствующий коэффициент строки о в следующей таблице. Если отсечение (9) используется в качестве ведущей спероки, то о„)0 для всех 7ГУ1), кроме индекса к слабой переменной в (9) и а„( а„для всех 1 Е У. (10) ДОКАЗАтВЛЬСтВО. ДвйотннтЕЛЬНО, а„. = ае1 — ~ — ~ а„, ОтКуда аее а, аы гаев следует, что — = — — ~ — ~(1, и в силу а„)0 получаев1 ает ( а„,. Для того чтобы связать теорему 17.1 с нашими рассуждениями относительно правил выбора производящей строки, вначале 1) Х вЂ” множество индексов небаэнсных переменных после преобразования.— Прим.
верее. 1Ь1. ВВКДВНИБ И АЛГОРИТМ 353 отметим, что в стационарном цикле 11 — "111 = О. Таким образом, 1а,.81 а,а = ааа — — а„з, а,э — значение элемента (стоящего в нулевом столбце и в строке Р) в таблице, которая получилась в результате последнего переходного цикла. Теперь если а„ вЂ” а,з = у ) О, то, как следствие из ($0), имеем (при выборе любого з) аму — а,а = = у( у. Таким образом, если строка Р повторно выбирается в качестве производящей до тех пор, пока а„, > а„а — — - а,э, то конечная последовательность преобразований должна принести к таблице, в которой а„(» а,.а. Итак, можно обеспечить выполнение требований к допустимому правилу выбора производящей строки, если правило обладает следующим свойством: если в таблице для некоторой строки 1 а;, ) аш — — а;а и это условие выполняется в последующих таблицах, то стропа 1 будет выбираться как производящая до тех пор, пока не выполпится условие а1, » а1а (после чего строка 1' перестает быть производящей строкой).
Заслуживает внимания сходство этого правила с правилом выбора производящей строки в полностью целочисленном алгоритме Гомори. Следующие два правила представляют собой примеры допустимых правил выбора производящей строки. ПРАВило т а. Составить последовательный конечный список ипдексов строк таким образом, чтобы индекс каждой строки вошел в него по меньшей мере однп раз. Перейти к (6). б. Если список пуст или пе содерл1ит ни одного индекса нз 1Г (г), вернуться к (а); в противном случае найти в списке первый индекс и ~ Р" (з).
Выбрать строку Р как производящую строку. Вывести из списка индекс Р и все предшествующие ему индексы. - Перейти к (в). в. Последовательно выбирать строку и, взятую в (б), как производящую, до тех пор, пока и Е 1Г(г). Как только г б )Г(г), вернуться к (б). ПРАвило 2 а. Пусть $'1(г) — множество 1Г(г), соответствующее т-й таблице. Если 1Г1 (г) содержит болев одного элемента: )Г» (г) = = (и1, Рю..., РА+т), то в качестве производящей выбрать такую строку иа, что в последовательности Множеств р1 (г1), Р, (зэ),... ..., У1(г) строка Р появилась раньгпе (пе позднее) остальных Р1 Г )Г1 (з) и затем сохранялась вплоть до И1 (г); перейти к (б).
б. Последовательно выбирать строку Р, взятую в (а), до тех пор, пока в г )Г(з). Как только Р ( 1Г(г), вернуться к (а). Прежде чем окончательно сформулировать прямой алгоритм, скажем несколько слов относительно формы и структуры записи 23 т. хт гл. Рь пРямОЙ АПГОРитм задачи, которая была использована в наших рассуждениях. Пусть условия исходнрй задачи даны в виде уравнений следующим образоьг: найти максимум то =- ао7 — ~ аозх; 1=я+ 7 при условиях х;+ ~~ аих; = а7о 1= Р! х, — хт = О хо =:О (7=1, „И), (у=по+1, ..., и), (целые) (й = 1, 2, ..., и). (11) Эти условия отличаются от (1) только наличием тождественных соотношений хт — х7 = О (7' = т .)- 1, ..., и). В дальнейшем мы будем пользоваться и матричной записью уравнений 1„„х + +Ахи = ао, где х = (хо1 хп хо) хк = (хмы хо) и последние и — т строк матрицы А представляют собой тождественные соотношения.
Для удобства обозначения будем употреблять У как символ мяожества пебазисиых переменных в любой таблице. Форма и структура (11) будет использоваться как для описания исходной задачи, так и для текущих таблиц, Теперь дадим формальное описание прямого алгоритма. Ш а г О. Присоединить к исходной таблице строку (с индексом Ь), выражающую верхп7ою границу суммы небазисных переменных: хь — '. 2 ха= аьо 7ЕХ где полон ительное целое число а со выбирается так, чтобы выполнялось хь ) О для ли>бого целочисленного ре7пения, удовлетворяющего остальным ограничениям.
Перейти к шагу 1. Ш а г 1. Проверить условие оптимальпости: Если ао7 ) О для всех 7' Е .7, то текущее базисное решение оптимально и вычисления окончены. Иначе перейти к шагу 2, К(з) = (7) О( — "(О,) Ш а г 2. Выбрать ведущий столбец а„удовлетворяющий условиям аь, ) О и г, -.~ г„. для всех 1(ФР) Е,7 при аь; > О. Перейтя к шагу 3. Ш а г 3. Выбрать производяпгую строку 77 из множества 17.1. ВВИДКИИЗ И АЛГОРИТМ 355 согласно допустимому правилу выбора производящей строки.
Перейти к шагу 4. Ш а г 4. Добавить к таблице отсечение гь = ( — "~ + ~~ [ — ~ ( — ХА). (12) Перейти к шагу 5. Ш а г 5. Провести преобразование с ведущим столбцом а, и ведущей строкой (12). Перейти к шагу б. Ш а г 6. Вычеркнуть отсечение (12) из системы. Вернуться к шагу 1. Необходимо сделать несколько замечаний. 1) Нет необходимости в этом алгоритме проверять решение на неограниченность, поскольку Т строка (3) делает подобный исход невозможным.
Этот факт можно легко установить, заметив, что всегда аь, ) О. 2) Вычеркивание ведущей строки каждый раз после преобразования может создать неверное впечатление, будто при этом теряется существенная информация. Вычеркивание слабых переменных, соответствующих введенным ранее отсечениям Гомори, после того как.эти переменные снова становятся базисными, стало обычным приемом.
Если а, соответствует такой слабой переменной Гомори, то вычеркивание ведущей строки равносильно вычеркиванию слабой переменной. Пусть теперь а, соответствует одной из исходных небазисных переменных хА. Заметим, что таблица содержит тождественное соотношение (13) После преобразования строка (13) станет тождественной ведущей строке.
Поэтому, вычеркивая ведущую строку, мы просто исключим избыточное. представление для хь. Такой прием позволяет сохранять свойство формы (11), согласно которому только небазисные переменные имеют избыточное тождественное представление. 3) Поскольку новое отсечение Гомори всегда служит ведущей строкой, переменная, выводимая из базиса, всегда есть слабая переменная Гомори.
Соответственно нн одна переменная исходной задачи (11) не выйдет из базиса. Очевидно, размер системы остается постоянным от таблицы к таблице. 4) После того как преобразование завершено, небазисный столбец аь, соответствующий слабой переменной Гомори, которая сгала в результате этого преобразования небазисной, равен ведущему столбцу а„взятому со знаком минус, т. е. а„= — а,. 254 ГЛ.
17 ПРЯМОЙ ЛЛГОРИТМ хо= Х )«тет >«э при условиях 1хв + Пх„= а„ хв, х,«Ъ 0 (целые), где 0 и д«состоят из целых элементов и д« -О. Пусть хв = Ез и хк = $к является целочисленным решением. Для того чтобы превратить хз — — ~з, х>« =- $к в базисное допустимое целочисленное решение, поступим следующим образом. Вычислим другой целочисленный вектор-столбец б«1 (14) где «1> — вектор-столбец из Р. Поскольку ь = (ьз, $>7) — допустимое целочисленное решение, получаем О~~,=б,— П~„=б,— 6,, уда «1«< 11«. 5) Поскольку ведущая строка добавляется перед преобразованием, и сразу после преобразования вычеркивается, можно прямо представить переход от таблицы к таблице, как элементарное преОбразование по столбцам, в котором ведущий столбец, умножаемый на целые числа, складывается с каждым столбцом, прп этом целые множители получаются из текущой целочисленной ведущей строки.
Элементарное преобразование по столбцам не может изменить ранга таблицы. Из (11) ясно, что столбцы в первой таблице линейно независимы и поэтому столбцы всех последующих таблиц должны быть та кже линейно независимыми. Соответственно г» ~ г, для л>обой пары столбцов а„и а; в любой таблице, поскольку равенство означало бы пропорциональность, а значит, линейную зависимость столбцов а» и а;. Отсюда можно сделать вывод о том,что правило выбора ведущего столбца дает всегда однозначный результат.
6) Для работы прямого алгоритма требуется, чтобы исходная таблица содержала допустимое базисное целочисленное реп>ение; чтобы алгоритм работал эффективно, вероятно необходимо начинать с «хорошего» (т. е. почти оптимального) базисного целочяслепного решения. Во многих прикладных задачах «хорошие» решения 'часто известны или их легко получить. Однако может оказаться трудным выразить целочисленное решение как базисное решение. например, когда это решение является внутренней точкой мнох;ества решений задачи (11). Отметим один полезный прием, который можно использовать при решении целочисленных задач. Пусть требуется найти максимум 357 17.зл/Римкг Добавим к (14) 65 и новую пебазисную переменную хе. Расширенная задача выразится как х,+~бухт+а,х,=б„ (15) где 7 пробегает все значения гт'.
Поскольку е)5 ~~ е)о, то при выборе е)5 в качестве ведущего столбца, преобразование будет переходным циклом г). Проведем один (переходный) цикл с г)5 в качестве ведущего столбца. Используем получившуюся таблицу как начальную в прямом алгоритме. Если получено оптимальное решение хз, хл, хз задачи (15), то его можно преобразовать в оптимальное решение хв, хй задачи (14) подстановкой в (15): х, +~ адхд+бзх, =бм хв+л~~ е))х/+ (Х е)Аг) хз =-4» ха + ~„е); (х) + $)хз) = г(о. Итак, имеем ха=хе, хй=х +$ хю Такой способ является прямым приложением идей, предложенных Бен-Израслем и Чарпесом И7].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
