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

задачи, которая была использована в наших рассуждениях. Пусть условия исходной задачи даны в виде уравнений следующим образом:

найти максимум

П

Эти условия отличаются от (1) только наличием тождественных

и последние п — т строк матрицы А представляют собой тожде­

ственные соотношения. Для удобства обозначения будем употреб­ лять J как символ множества небазисных переменных в любой

таблице. Форма и структура (И) будет использоваться как для описания исходноц задачи, так и для текущих таблиц.

Теперь дадим формальное описание прямого алгоритма.

Ш а г 0. Присоединить к исходной таблице строку (с индек­ сом L), в ы р а ж а ю щ у ю верхнюю границу суммы небазисных пере­ менных:

Ш

где положительное целое число A lo выбирается так, чтобы выпол­ нялось х ь ^ О для любого целочисленного решения, удовлетво­

ряющего остальным ограничениям. Перейти к шагу 1.

356 ГЛ. 17. ПРЯМОЙ АЛГОРИТМ

5) Поскольку ведущая строка добавляется перед преобразова­ нием, и сразу после преобразования вычеркивается, можно прямо представить переход от таблицы к таблице, как элементарное пре­ образование по столбцам, в котором ведущий столбец, умножае­ м ы й на целые числа, складывается с каждым столбцом, при этом целые множители получаются из текущей целочисленной ведущей строки. Элементарное преобразование по столбцам не может изме­ нить ранга-таблицы. Из (11) ясно, что столбцы в первой таблице линейно независимы и поэтому столбцы всех последующих таблиц должны быть также линейно независимыми. Соответственно гд ф гjдля любой пары столбцов ад и ау в любой таблице, посколь­

ку равенство означало бы пропорциональность, а значит, линей­ ную зависимость столбцов ад и а Отсюда можно сделать вывод о том, что правило выбора ведущего столбца дает всегда однознач­ ный результат.

6) Для работы прямого алгоритма требуется, чтобы исходная таблица содержала допустимое базисное целочисленное решение; чтобы алгоритм работал эффективно, вероятно необходимо начи­ нать с «хорошего» (т. е. почти оптимального) базисного целочислен­ ного решения. Во многих прикладных задачах «хорошие» решения часто известны или их легко получить. Однако может оказаться трудным выразить целочисленное решение как базисное решение, например, когда это решение является внутренней точкой множе­ ства решений задачи (11). Отметим один полезный прием, который можно использовать при решении целочисленных задач.

где d^ — вектор-столбец из D. Поскольку \ = (|в,|^) — допусти

мое целочисленное решение, получаем

0 <1 \в = d0— Blv = d0— dg,

откуда dg < d0.

столбца, преобразование будет переходным циклом х). Проведем один (переходный) цикл с dg в качестве ведущего

столбца.

Используем получившуюся таблицу как начальную в прямом

Такой способ является прямым приложением идей, предложенных Бен-Израелем и Чарнесом [17].

17.2. Пример

Проиллюстрируем этот алгоритм при помощи примера. Произ­ водящая строка здесь будет выбираться при помощи правила 2, изложенного в § 17.1.

Рассмотрим задачу целочисленного программирования: максимизировать

х0 = Xi + х2 + хъ

при условиях

равными нулю , мы получаем возможность сделать эффективный шаг прямого

алгоритма и получить лучш ее целочисленное базисное решение.— Прим,

ред.