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

решения меньше, чем оптимальное значение второго (если сг > 0). Иными словами, чем дальше у г от решения задачи линейного программирования, тем хуже значение целевой функции.

Продолжая вычисления методом ветвей и границ, мы получаем оптимальное значение z*, наилучшее для найденных пока цело­ численных решений. Если вершина с нецелочисленным решением имеет оптимальное значение, большее чем z*, то все следующие за ней вершины должны иметь оптимальные значения, большие чем z*. Следовательно, не имеет смысла производить ветвление из этой вершины. Этот факт может быть использован для реше­ ния задач частично целочисленного программирования.

Рассмотрим аддитивный алгоритм решения задачи булевого

называется допустимым, если оно удовлетворяет также ограни­

ный здесь, может быть назван неявным перебором, поскольку мы систематически перебираем решения. Будем говорить, что допу­ стимое решение доминируется другим допустимым решением, если последнее имеет меньшее значение целевой функции. Для удобства мы используем оо в качестве значения целевой функции

для недопустимых решений. Таким образом, недопустимое реше­ ние всегда доминируется допустимым решением. Если мы после­ довательно проверяем решения на допустимость, некоторые из ре­ шений, которые еще не были проверены, могут доминироваться текущим наилучшим допустимым решением. В этом случае нет необходимости проверять все допустимые решения.

Для задачи булевого программирования с п переменными имеется 2п решений. Мы разобьем 2" решений на п 4- 1 подмно­

граммы, как это показано на рис. С-1(а) для п = 4.

Каждая вершина на рис. С-1(а) представляет решение. Внутри

С каждой дугой также сопоставляется свой индекс г. Этот индекс означает, что xt = 1 в вершине, где дуга кончается, и xt = О в вершине, где дуга начинается. Значения всех других перемен­ ных в двух вершинах, связанных дугой, одинаковы. Каждую вершину можно достичь из самой верхней вершины посредством многих различных цепей, соответствующих различным способам, которыми можно придавать значения Xj = 1. Если существует цепь из вершины N t в вершину Nj, то N t называется предшест­ вующей вершине Nj, a Nj называется следующей за вершиной N t. Все вершины являются следующими за самой верхней вершиной и предшествующими самой нижней. Все вершины частично упо­

,4 6 4 ПРИЛОЖЕНИЕ С

рядочены отношением «предшествует — следует». Проверяя реше­ ния на допустимость, мы не используем никакой техники линейного программирования. Решения непосредственно подставляем в огра­

ни одну из следующих за ней вершин.

Ниже приводятся 4 правила, которые могут быть использованы при проверке.

П р а в и л о 1. Поскольку 0 ^ щ ^ с 2 ^ . . . ^ сп, значе­

ние целевой функции сх для произвольного решения всегда боль­ ше значения целевой функции для решения, ему предшествую­ щего. Таким образом, если вершина допустима, нет необходимости проверять все вершины, следующие за ней. На рис. С-1(б) пред­ полагается, что xi = х2 = х3 == 0, ж4 = 1 — допустимое решение. Этот факт непосредственно исключает из рассмотрения 7 решений.

П р а в и л о 2. Пусть z* — минимальное среди значений целевой функции для рассмотренных пока допустимых значений.

переменные будем называть свободными, так как они могут при­ нимать значение 0 либо 1. Если N q недопустимо,’ то можно счи­ тать, что нет достаточного числа свободных переменных, которые бы удовлетворяли данному ограничению. Пусть, например, таким

но, то данное ограничение может заставить некоторые другие переменные также стать фиксированными. Пусть, например, огра­ ничением является 3xi — х2 — 2х3 = 0, а соответствующая вер­