Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.10.2024
Просмотров: 218
Скачиваний: 0
332 ГЛ. 16. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ
Для того чтобы ограничение принадлежало параболическому
типу, требуется, |
чтобы квадратичная часть (1 ) была положитель |
||
но определенной |
или |
положительно полуопределенной, т. е. |
|
bi (Li (х))2 + . . . + bk (Lk (х))2 ^ 0 , и чтобы к + |
1 однородных |
||
линейных форм (2 ) были линейно независимыми. |
ограничение |
||
Для проверки |
того, |
что данное квадратичное |
|
ПП
&0 |
2 & i% i~Ь 2 |
d i j X i X j ^ ^ Q |
(6 ) |
|
|
' г=1 |
г, з=1 |
|
|
является параболическим, поступаем следующим образом. Если все ан — неположительны, то (6 ) — отрицательно определенная,
отрицательно полуопределенная или неопределенная функция. Если хотя бы одно из а.ц, скажем ап , положительно, то дополняя до полного квадрата подформу из (6 )
& \ \Х\ “Г ( ^ 1 2 "Ь &2l) Х{Х% |
• • • Н - (®1 п |
&ni ) ^ 1^-71) |
получим следующее выражение:
1 |
I а 12 + я21 |
I |
| я1п + яп1 „, \ 2 |
|||
|
11 1 + |
2 |
Z 2 T - — + |
2 |
Х п ) • |
|
Если (6) — ограничение параболического типа, то оставшаяся квадратичная часть из (6 ) должна быть положительно полуопре
деленной. Таким образом, мы можем продолжить процесс выде ления полных квадратов. В случае параболического ограничения, квадратичная часть из (6 ) в конце концов станет суммой п — 1
или меньше квадратов линейных форм.
Рассмотрим задачу целочисленного программирования с линей ной целевой функцией и параболическими ограничениями (неко торые из них могут быть линейными):
максимизировать
П
Со— 1 ] |
C j X j |
(7 ) |
3 = 1 |
|
|
при условиях |
|
|
a0o— L0(x) — bi {Ll ( x ) f — . .. —6ft(Lh(x))2 > |
О, |
|
Xj^tO (7 = |
1 , .. ., п). |
(8 ) |
Для простоты предположим, что имеется только одно ограничение в (8 ) и все хj в (7) и (8 ) являются небазисными. Если Cj ^ О^в (7),
то, полагая все небазисные переменные равными нулю, получим двойственно допустимое решение. В этом случае любое неотрица
тельное решение х' давало бы целевой 'функции с0—^CjXj значе
16.1. ВВЕДЕНИЕ |
333 |
ние меньшее, чем с0. Является ли данное двойственно допустимое решение прямо допустимым, зависит от знака а00.
Для выполнения условия (8 ) необходимо (но не достаточно),
чтобы
а00 — L0 (х) > 0, |
(9) . |
так как квадратичная часть в (8 ) всегда неотрицательна, т. е.
bl (Li( x ) f + . . . |
+ b h(Lk(x) ) ^ О (Ь ,> 0; г - 1 , ... ,&). |
Условие (9) представляет собой линейное ограничение, .которое должно выполняться при любом допустимом решении исходной задачи. Если а00 < 0 в условии (9), то можно рассматривать (9) как производящую строку и получить из нее отсечение Гомори, как это делалось в § 13.1. Если использовать отсечение Гомори как ведущую строку и произвести итерацию (линейное преобра зование небазисных переменных), то после подстановки в (7)
и(8 ) новых небазисных переменных получим новые ограничения
ицелевую функцикт. Соответственно будет получена новая линей ная часть в (9), которая рассматривается как производящая стро ка, если а00 в ней отрицательно. В дальнейшем будет показано, что этот процесс является конечным.
Геометрически гиперплоскость а00 — Ь0 (х) = 0 представляет
собой касательную плоскость к поверхности, определяемой огра ничением (8 ). Этот факт оформлен в виде следующей леммы.
Л емма 16.1. Гиперплоскость Т = {х | а00 — L0 (х) = 0} является касательной плоскостью к поверхности, образованной ограничениями (8 ). Она однозначйо определяется как касательная
плоскость, параллельная поляре к поверхности ограничения, про ходящей через начало координат.
Д оказательство. Поскольку условие (9) является следствием условия (8 ), все точки, удовлетворяющие (8 ), расположены по
одну сторону от гиперплоскости Т. Гиперплоскость Т является касательной к поверхности (8 ), так как пересечение Т и нульпространства L квадратичной части из (8 ) непусто, т. е.
Ь ( \ Т Ф 0 (L = { x| L1 (x) = 0, . . Lfc (х) = 0}).
Тот факт, что L f| Т ф 0 , следует из линейной независимости линейных форм L 0 (х), . . ., Lh (х). В то же время не существует другой касательной плоскости, параллельной Т. В противном случае существовала бы плоскость а00 — L 0 (х) = у, для которой выполнялось бы условие а00 — L0 (х) ^ у при всех значениях х, удовлетворяющих условию (8 ). Последнее замечание противоречит тому, что {х | а00 — L0 (х) ^ у} расположено по одну сторону
от Т, а выпуклый п-мерный параболоид — по другую. Поскольку Т представляет собой касательную плоскость к поверхности, определяемой условием (8 ), отсечение Гомори, полученное из Т.