Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

1.7. Формирование дополнительных ограничений

Принципы формирования дополнительных ограничений основываются на результатах теорем, приводимых ниже. Теорема (5): если x̂j - переменная, на которую распространяется требование целочисленности, ws(s = 1,...,М) -параметры, связанные с x̂j соотношением x̂j = α0j + α1jw1 + .... +αMjwM, если ∀αsj (s∈1,...,M), то линейное неравенство

(1.18)

выполняется для всех ws, дающих целочисленное x̂j, и не выполняется для базисного решения (1.16), получаемого из (1.17) ∀ws = 0, s = 1,...,M.

Доказательство: вследствие не отрицательности (по предположению) величин αsj и ws (s = 1,...,M) минимальное значение x̂j не может быть меньше α0j, т. е. min x̂j ≥ α0j - отсюда следует x̂j ≥ [α0j] + 1 поскольку x̂j есть целое число. Вычитая это неравенство из выражения x̂j, приведенного в условии теоремы, приходим к соотношению (1.18), что и доказывает первую часть утверждения теоремы; доказательство второй части очевидно: fα0j ≤ 1 всегда (по определению f).□

Полученный результат легко преобразуется в дополнительное ограничение, используемое в методе Гомори.

Если записать условие x̂j0j] + 1 в виде равенства x̂j - x̂̂j = [α0j] + 1 (для этого переменная x̂̂j должна быть не отрицательной и целочисленной) и вычесть это равенство из выражения x̂j, то

(1.19)

Выбрав x̂̂j в качестве новой переменной и дополнив систему (1.17) уравнением (1.19), приходим к следующему: при обращении всех ws в нуль (этим определяется точка X) появится базисное решение


в котором одна переменная (именно x̂̂j) отрицательна, поскольку всегда f̄α0j > 0. Такое решение недопустимо,

следовательно, условие (1.19) не удовлетворяется в точке X̂, хотя во всех других точках, для которых рассматриваемая координата %j принимает целочисленные значения, оно выполнено (это следует из равенства x̂̂j = x̂j - [α0j] - 1, дающего целые неотрицательные значения x̂̂j при любом x̂j ≥ [α0j] + 1).

Таким образом, уравнение (1.19) может быть использовано для расширения системы (1.17) с целью отсечения X̂. Известным недостатком, ограничивающим область применения теоремы (5), является введенное выше требование не отрицательности коэффициентов αsj (s = 1,...,M; j∈J). Чтобы избежать связанных с этим неудобств, обратимся к доказательству еще одной теоремы (6): если x̂j (1≤j≤n, j∈J) и ws (s = 1,....,М) - целочисленные неотрицательные переменные, такие, что j = α0j+MΣs=1 αsjwsлинейное неравенство


выполняется для всех ws, дающих целое значение и не выполняется для базисного решения (1.16), получаемого из (1.17) при нулевых ws.

Доказательство: каждая величина αsj (s = 0,...,М) в выражении x̂j может быть представлена как αsj = [αsj]+fαsj тогда само выражение x̂j принимает вид


или после несложных преобразований


Левая часть этого равенства есть целое число вследствие целочисленности (по предположению) всех ws и xj, кроме того, все fαsj неотрицательны, что позволяет

отождествить возникшие здесь условия с условиями теоремы (5) (разница лишь в обозначениях коэффициентов при ws и переменной, стоящей в левой части). Следовательно, выводы теоремы (5) доказывают утверждения теоремы (6). □

Так же, как и в предыдущем случае, здесь можно ввести в рассмотрение целочисленную неотрицательную величину x̂̂j, определяемую выражением


или

(1.20)

Добавление уравнения (1.20) в систему (1.17) обеспечивает отбрасывание X̂ и не затрагивает точек, для которых координата x̂j остается целочисленной.

Теорема (6) тоже должна иметь ограниченную область применения из-за условия "все ws - целые числа", однако всегда существует возможность объединения результатов (1.19) и (1.20).

Теперь остается рассмотреть общий случай, когда переменные ws могут быть и дробными, и целочисленными, а коэффициенты asj при дробных ws не имеют ограничений на знак. Для упрощения формулировок введем следующие обозначения:

S1 - множество номеров s, для которых ws - целые и αsj>0;

S2 - множество номеров s, для которых ws - дробные и αsj>0;

S3 - множество номеров s, для которых ws - целые и αs<0;

S4 - множество номеров s, для которых ws - дробные и αsj<0.

Существует теорема (7): если x̂j - переменная, на которую распространяется требование целочисленности, и ws - параметры, связанные с x̂j соотношением x̂j = αoj+MΣs=1 αsjws, то линейное неравенство


выполняется для всех ws, дающих целочисленное x̂j, и не выполняется для базисного решения (1.16), получаемого из (1.17) при ∀ws = 0.

Не останавливаясь подробно на доказательстве, обратим внимание на важное обстоятельство: переменная x̂̂j, заданная здесь как


не обладает свойством целочисленности в отличие от (1.19) и (1.20); будучи введенной в систему (1.17), она не может использоваться на последующих шагах для формирования новых ограничений и лишь увеличивает размерность задачи. Следовательно, всегда имеет смысл обращаться к результатам теорем (5) или (6) (если это допускают условия конкретной задачи). Дополнительные пояснения дает следующий пример.

Пример: найти x1 ..., x4→min{-7/12+x1/4+4x3/3} при условиях: x1, x2, x3, x4 - целые неотрицательные числа, z - целое число и 2х1+x2+4x3/3 = 13/3; x1/2+3x3+x4 = 9/4.

Решение: отбрасывая требование целочисленности xj(j = 1,...,4) и z, видим, что оптимальное решение стандартной задачи линейного программирования можно указать сразу - x̂1 = 0, x̂2 = 13/3, x̂3 = 0, x̂4 = 9/4, z = -7/12; следовательно, положив x̂1 = w1 и x̂s = w3, получим из исходных условий систему типа (1.17):

(I)

свободные члены второй, четвертой и пятой строк (I) являются дробными, и необходимо ввести дополнительное ограничение; для его формирования удобно выбрать строку ẑ, где α0j = α0z = -7/12 и f̄α0i = 7/12; согласно рекомендациям теоремы (5) новая переменная (обозначаемая просто x̂5) определяется равенством x̂5 = -7/12+w1/4+w3/3, а расширенная система ограничений принимает вид

(II)

ясно, что x̂1 и x̂2 не могут оставаться свободными (при x̂1 = x̂3 = 0 величина x̂5 отрицательна); чтобы найти им замену, обратимся к задаче: найти x1, х2,....,х5→min{z = x5} при ограничениях (II); ее решением являются x̂1 = 45/21, x̂2 = 0, x̂3 = 1,28, x̂4 = 129/112, x̂5 = 0 или (в параметрическом представлении)

(III)

(полезно обратить внимание на то, что здесь ẑ = 0; отбрасывание

очередной точки X̂ может сопровождаться увеличением ẑ, и совсем не исключено, что оптимальное решение исходной целочисленной задачи может оказаться хуже - в смысле полученной величины z, - чем решения промежуточных задач); в строках системы (III) опять присутствуют дробные свободные члены, поэтому нужно вводить новое дополнительное ограничение; выбрав строку x̂3 с α03 = 1 /28 и fα03 = 27/28, получаем x̂6 = -27/28+3w3/28+6w5/7; отсюда следует формулировка третьей по счету линейной задачи - найти x1, х2,..., x6→min{z = x5} при

(IV)

решив ее, получаем x̂1 = 0, x̂2 = 3, x̂3 = 1, x̂4 = 3/2, x̂5 = 3/4, x̂6 = 0 или

(V)

результат (V) не удовлетворяет исходным требованиям целочисленности всех xj(j = 1,...,6), и в качестве еще одного ограничения, порождаемого строкой x̂5 в (V), принимается x̂7 = -1 /4+w1/4+w6/3; это приводит к очередной линейной задаче - найти x1,....,x7→min {z = x5} при

(VI)

и решению x̂1 = 1, x̂2 = 1, x̂3 = 1, x̂4 = 1, x̂5 = 1, x6 = 0, x̂7 = 0, ẑ = 1, которое полностью целочисленно и должно быть признано оптимальным для исходных условий, т. е. x*1 = 1, х*2 = 1, х*3 = 1, x*4 = 1, z* = 1.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"