Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

« ^ О, ограничено или сделано ограниченным добавлением нера­

венства 2 иг < М, то задачи (3) и (3') эквивалентны, что является интересующим нас случаем. Конечно, мы не можем узнать, являет­ ся ли множество {и | иА4 ^ с4, и ^ 0} ограниченным, прежде чем решим'задачу (3). Подставив условия задачи (3') в (1), получим

•следующую задачу:

<(1 '), а сама задача является «чистой» задачей целочисленного

программирования, т. е. все ее переменные y t должны принимать целые значения.

Если известна оптимальная вершина и*, задачу (1') можно решить как «чистую» целочисленную задачу любым из существую­ щих способов и получить оптимальные значения z* и у*. Подста­ вив у* в условия (2), найдем минимум щх при условиях А4х ^3=

Если оптимальная вершина и* не известна, то можно, перебрав все вершины ир, найти решение задачи (1'). Трудность такого подхода состоит в том, что обычно существует слишком много вершин ир, поэтому для получения оптимальной вершины и* ■будем использовать следующую итеративную процедуру. Возьмем

любое допустимое значение и (не обязательно вершину), которое удовлетворяет условиям uAj ^ с4, и ^ 0 , подставим его в (1 '). Пусть для этого значения и решением задачи (1 ') будут z и у.

Используя у для решения задачи (3), найдем значение и, макси­

мизирующее и (Ь — АгУ)- Пусть решением будет и. Подставим и в условия (1 '), т. е. добавим еще одно неравенство, после чего

z* = с2у* + и* (Ь—А2у*),

а для произвольного и из (1 ') получим

z = c2y + u(b —А2у),

множеством всех ограничений в (1'). Оптимальное значение z* в (1 ) будет получено, если используются все значения ир или

оптимальное и*. Для того чтобы проверить, является ли и опти­

не существует, то задача (1) не имеет допустимых решений. Перей­ ти к шагу 1 .

Ш а г 1. Решить «чистую» целочисленную задачу:

Если z не ограничено снизу, то в качестве z взять любое неболь­ шое значение.

Ш аг 2. Используя у, полученное на шаге 1, решить линей­ ную программу

максимизировать

u(b — А2у)

при условиях

u A ^ C j, u^O .

Если и не ограничено, a u(b —А2у) ограничено, то добавить

Пусть решением этой программы будет и. Проверим выполне­ ние неравенства

z —C2y < u (b —А2у).

Если оно выполняется как равенство, то перейти к шагу 3. Если не выполняется, перейти к шагу 1 и добавить ограничение z

^ с2у + и (Ь — А2у) к существующему множеству ограничений

в задаче (Г). Неравенство в задаче (1') может быть опущено, если соответствующая ему слабая переменная принимает положитель­ ное значение.

Ш а г 3. Используя у, полученное на шаге 1, решить задачу линейного программирования:

наити минимум

С4Х

при условиях

AtX^b —А2у, х^&0 .

Пусть решением этой задачи будет х. Тогда х и у — оптимальные

Теперь докажем, что, во-первых, алгоритм конечен, во-вторых, он дает оптимальное решение и, в-третьих, в любое время можно получить верхнюю и нижнюю границы оптимального решения z*.

Для того чтобы доказать конечность алгоритма, заметим, что существует лишь конечное число вершин множества, задаваемого

Р и с . 1 5 . 2 .

условиями uAi ^ Ci, и ^ 0, если оно ограничено. Если оно не ограничено, то после добавления условия 2 ^ М множество

{и | иА! ^ сь и ^ 0, 2 ui ^ 5 М } становится ограниченным. Для

Доказательства конечности алгоритма следует выяснить только один вопрос: будет ли в итерационном процессе, состоящем из ша­ гов 1 и 2 , при решении задачи (3) получаться каждый раз новая

вершина ир? Выглядит вполне правдоподобным, что два неопти­ мальных значения у' и у" могут давать одну и ту же вершину и. Такой случай показан на рис. 15.2. К счастью, такая ситуация

никогда не возникает.

Пусть z и у — решение, полученное на шаге 1, т. е.

u (Ь—А2у) > и (Ь—А2у),

то и Ф и, а это означает, что либо мы всегда получаем новую вершину при каждом повторении шага 2 , либо получена опти­

мальная вершина.

Для доказательства того, что алгоритм приводит к оптималь­ ному решению, необходимо заметить, что если все ир выписаны в задаче (1 '), то оптимальное решение будет получено.

Чтобы убедиться, что можно получать верхнюю и нижнюю границы, рассмотрим в задаче (1 ') z, которое является нижней

границей оптимального значения z*. Поскольку в задаче (1') выписаны не все ограничения, для получения верхней границы z* дополним результат шага 2 решением задачи

минимизировать

CiX

где у — значение у, используемое на шаге 2. Тогда допустимым

Перепишем (8 ), считая у произвольно заданным (как указывалось

в начале параграфа.)

минимизировать

Ъх

минимизировать

Z

21 т. ху

2щ -|- 8 w2 -)- Зи3,