Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 52
Текст из файла (страница 52)
Если сохранять все строки, соответствующие слабым переменным Гомори, то этя слабые переменные могут становиться базисными, после того как они были небазисными. Если слабая переменная Гомори вошла в базис с неотрицательным значением, то соответствующая строка представляет собой неравенство, справедливое при текущем решении, и зта строка может быть вычеркнута.
Если слабая переменная Гомори становится базисной с отрицательным значением, соответствующую строку следует использовать в качестве ведущей. Если сохранять все строки, соответствующие всем отсечениям Гомори, то, вообще говоря, потребуется меньшее число дополнительных ограничений, однако увеличение таблицы много более неприятно, чем введение лишних дополнительных ограничений. 13.2. Примеры (Гомори [79)) Приведем два примера, иллюстрирующие алгоритм. Производящую строку и ведущий столбец обозначим стрелкой, а ведущий элемент — (*). Для того чтобы ускорить получение решения, в отдельных примерах порядок выбора производящей строки по первому сверху нецелому элементу в нулевом столбце соблюдаться не будет. Справа от кая2дой таблицы выписаны некоторые замечания относительно отсечений, на которые читатель не должен обращать внимания.
Зти замечания относятся к последующим главам. Пример 1, Рассмотрим задачу целочисленного программирования: максимизировать ХО = 4Х2 .+ 5Х2 -~- Хз ГЛ. 1З. ЦИКЛИЧЕСКИЙ АЛГОРИТМ прн условиях Зхг+ 2хз (10, хз+ 4хз < 11, Зхг+ Зхз+ хз (13 х„х„хз >~ 0 (целые). Вводя слабые переменные х„хв, х„получаем: — хз — 11/4 — 1 1/4 о 10/4 а о 9/4 Р=-1 И 4=4 оо о Π— 1 О О 11 14 0 О ОО в= — хз 187/10 18/10 23/10 0 0 о 7/10 /) = 4 И 10/4= 10 Ведущий стоябеп, /) = 10 х 1 .= 10 2,'10 4/10 — 1/10 — 9/10 — 1 0 0 — 1/10 4/10 — 2/10 3/10 — 3/10 0 — 1 0 — 7/10 а ха хг хз хз хг хв хв зг ха хг хз хз хв хв хв ха хг хг хз хв хв Хв ха хг хг хз хв хв хв о о о о 10 11 13 — 4 — 1 о о 3 1 3 — 5 0 — 1 о 2 4а 3 5/4 о 1/4 0 — 2/4 — 1 — 3/4 — 7ДΠ— 2/10 3/10 о о :3/10 о о — 1 о 0 1 о о — 1 о о 1 — 1 0 о — 1 о о 1а группа неравенств т" 1 Производя- 10 — (7, 1, 7, 0)(2, 6, 2, 0) щаЯ стуока (4' 2' 4' О) (9' 7' 9' 0) (1, 3, 1, 0)(6, 8, 6, 0) (8, 4, 8, 0)(3, 9, 3, 0) Например: (7, 1, 7, 0]+ (4, 2, 4, 0) ви х- (1, 3, 1 0) (шов( 10) 13.2.
ПРИМКРЫ 293 Оптимальное решение задачи линейного программирования: хо = = 194/10, х1 = 18/10, хг = 23/10, хз = 7/10. П=10х = — 7 7 10 Группа яеразепств Š— (О, 1, 4, 0) (О, 3, 6, 0) 1 7 (О, 2, 1, 0)(0, б, 3, 0) (О, 3, 6, 0)(0, О, О, 0) (О, 4, 2, 0) — хз 4/7 — 2/7 3(7 — 3/7 0 — 10/7 Π— 1 Оптимальное целочисленное решение: х,=19, х,=2, х,=2, х,=1. Заметим, что, выразив х„х, и ха через исходные небазисные переменные х„хг н х„получим неравенство з.
) 0 с целыми коэффициентами: 7 1 7 — — + — (10 — Зх, — 2х ) + — (11 — х1 — 4хг) )~ О, 10 10 10 илн х, + Зхг ( 8. Этот вопрос обсуждается в 4 13.4. Чтобы получить матрицу, полностью целочисленную, просто продолжим введение отсечений: — хо 1/7 3/7 — 1/7 — 6/7 — 1 1/7 0 0 — 1/7 * хо х1 хз Производящая хз +— хо строка хо хо о1 оз Пример 2. Рассмотрим максимизировать х, = при условиях ЗХ1 — 5х1 2х1 задачу: Зх, — хг, — 2хг<З, — 4хг < — 10, + хг(5 х„хг>~0 (целые). хо х1 хз хз хз хо хо зз бз 19 2 2 1 0 О 0 0 хо хз хз Хо хо хо 11 19 2 2 1 0 1 0 0 1(7 3/7 — 1/7 — 6/7 1/7 0 о 4/7 — 2/7 3/7 — 3/7 0 — 10/7 0 — 1 — 4/7 1 0 0 1 0 0 — 1 0 0 1 0 о 0 о — 1 0 19 2 2 1 0 1 0 0 О 1 3 4 — б — 7 1 0 0 — 1 0 — 2 1 3 4 — 2 0 — 1 0 1 0 0 1 0 0 — 1 0 0 33.3. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ 295 43.3.
Геометрическая интерпретация Рассмотрим производящую строку г-й таблицы х =ао+ч ат( — х;), где х; — текущие пебазиспые переменные, а, = [а,1 + [о ) 0 1 ([а,] обозначает наиболыпее целое, не превосходящее ао). Из уравнения (1) получим отсечение Гопори а = — 7о+ Х 73хо' > О.
(2) В исходной таблице все коэффициенты аы — целые, а любая переменная х (базисная нли нет) представлена в виде целочисленной комбинации исходных небазисных переменных. Это означает, что правая часть уравнения (1) также должна быть представима в виде целочисленной комбинации исходных небазисных переменных хи Пусть Т1 ао+~,ат( — х,) =по-[-~птхи где ио = п~ = 0 (шоб 1), т. е. правая часть равенства (3) есть целочисленная форма относительно исходных пебазисных переменных. В 3-й таблице х = [а,] + 73.
Из уравнений (1) и (3) получаем х = ло+ ~ п3хт =- [ао]+ уз. (4) Уравнение (4) определяет гиперплоскость, проходящую через оптимальную вершину выпуклого множества в пространстве хи Мы утверждаем, что меноду гиперплоскостью (4) и гиперплоскостью по+1 итх~=[ао] (5) нет целочисленных точек.
Действительно, если бы такая точна существовала, скажем х,' = 0 (шой 1), то и, + ~ п,х; должно быть целым. В то же время между [ао1 и [ао] + ~о нет целых значений. Таким образом, гиперплоскость (4) можно перенести в положение (5), при этом все допустимые целочисленные точки удовлетворяют неравенству ио + Я~ итх, ( [а,1. В примере 1 х, = 10 — Зх, — 2хз ~ 0 и хо = 11 — х, — 4х, )~ О. Тогда хо + 7х, = 87 — 10х, — ЗОхз ) 0 или х, + Зхз ( 8,7. Откуда получаем отсечение Гомори х, + Зхо (8. гл. ы.
пикличвскии ллгогнтм В уравнении (1) х ьюжет быть и слабой переменной г, но, как будет показано в следующем параграфе, любая переменная з представима в виде целочисленной комбинации исходных неба- зискых переменных. Таким хз образом, геометрическая интерпретация остается справедливой н в этом случае. Па рис. 13.2 показано, что отсечение г~ ) О, нспользовап- Ъ нос в примере 1, является не- равенством с целыми коэффи,г 1 циектами при исходных неба- зисных переменных. "3~~д„ Заметим, что для получения ч4~ новой производящей строки о х 1 могут быть использованы целочисленные комбинации уравнений вида (1); скажем, сумма одного уравнения, умпок;екного на 5, и другого, умноженного па ( — 7). В таком случае левая часть производящей строки может и пе быть неотрицательной.
Однако если внимательно проследить, как было получено отсечение (9) в $13.1 из уравнения (4), то выяснится, что для левой части уравнения (4) требовалась только цолочислеппость. Процесс алгебраического сложения соотношения О = х~ (проб 1) соответствует алгебраическому сложению строк таблицы с единичной строкой 13.4. Свойства дополнительных неравенств (Гомори и Баумоль (87)) В этом параграфе будут приведены некоторые свойства дополнительных неравенств. Во-первых, будет показано, что дополнительное неравенство вида з= — 1, '+ХМ >О где з; — текущие небазисные переменные, становится неравепством с целочисленными коаффициептами, если его выразить через исходные небазисные переменные.
Чтобы понять зто утверждение, предположим, что рассматриваемое неравенство (1) является первым дополнительным неравенством, а производящая строка имеет вид (2) где х',. — либо исходные переменные, либо слабые переменные задачи (1) в $ 13.1. Каждую переменную х! можно выразить через огэд своиствд дополннтвлы!ых ннглвннств 297 исходные небазисные переменные, т. е. х'. =хг или х! =аод,,— в ~ ~а„.„;хь Таким образом, х' в уравнении (2) будут выражены через исходные небазнсные переменные. Поскольку любая переменная выражается через исходные небаанспые единственным образом, уравнение (2) должно приводиться к виду уравнений (1) в з 13.1, т. е.
либо х! = х~, либо х; = а д ь о — 1 а до ~хг. г —.ч В обоих случаях правая часть содержит только целочисленные коэффициенты. В полученном отсечении Гомори г;= — ~,— ~~г( — х;)= ! = [[а,[+~ [а,'[( — х;)) — (ао' — , '~а,'( — х,')[. (3) Первая скобка содержит только целые коэффициенты, поскольку [а„'), [а)] — целые части от а,' и ад соответственно.
Вторая скобка, как только что было покааано, таки е должна быть целочисленной комбинацией исходных переменных. Поэтому новое неравенство г; ) О содержит лишь целочисленные коэффициенты, если его выразить череа исходные переменные. Показав справедливость. утверждения для первого донолпительного неравенства, мы можем повторить доказательство и для второго, считая первое частью исходной задачи и т.
д. Таким обрааом, доказано, что дополнительные ограничейия Гомори представляют собой целочисленные комбинации исходных небазнсных переменных. Исследуя выражение (1) более подробно„ можно сделать еще ряд заключений. Рассмотрим первое дополнительное ограничение Гомори в виде (1). Разобьем множество переменных х; па два подмножества д и У. К Х отнесем те х;, 1 которые являются исходными небазиспыми переменными, а к У— х,', являющиеся исходными бааисными переменными. Выразив все хд в уравнении (1) через исходные переменные, получим э г;= — ~'о+ ~.
)Охд+ ~ ~ц(аго — ~~', а,дхд) ) О, (4) гег дзу д=д илн, по-другому, о — ~ю+ ~ 1па~оэ — ~~~~ ~ыхг+ ~ ~(~~'~магд)хд. (57 йм гег д=д Все члены в левой части неравенства (5),положительны, кроме — Ло, где О ( ~1о «1. Следовательно, левая часть неравенства (5) строго болыпе, чем ( — 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
