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

Таблицы 6.11—6.16 иллюстрируют шесть возможных случаев выбора ведущего элемента и изменения в результате итерации. Возможные исходы итераций могут быть использованы для дока­ зательства конечности алгоритма.

6.2. Прямо-двойственный метод1) (Данциг, Форд и Фалкерсон [40])

Поскольку существуют прямой и двойственный симплексметоды, не удивительно, что существуют методы, использующие идеи как прямого, так и двойственного алгоритмов. Метод, изла­ гаемый в настоящем параграфе, формально является двойствен­ ным, поскольку он сохраняет двойственную допустимость реше­ ний. Прямой симплекс-алгоритм используется как подалгоритм

Допустимое решение задачи (2) получается посредством весьма несложного ее анализа. Если с ^ 0, то я = 0 — допустимое решение задачи (2). Если условие с;- ^ 0 выполняется не для всех j и допустимое решение задачи (2) не очевидно, то задачи (1) и (2) можно слегка изменить следующим образом. Введем новую неотри­ цательную переменную хп+1 и добавим к ограничениям задачи (1) уравнение

где #т-н — достаточно большое положительное число. Очевидно, такое ограничение не изменит оптимального решения прямой задачи. Двойственная задача при этом будет иметь следующий вид:

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

118 ГЛ. 6. МЕТОД ОДНОВРЕМЕННОГО РЕШЕНИЯ

при условиях

Теперь легко выписать допустимое решение двойственной задачи

nm + 1 = min cj и я г = 0 (г = 1, . . /тг).

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

Если х — допустимое решение задачи (1), то условие (36) автома­ тически выполняется, поскольку ограничения задачи (1) пред­ ставляют собой уравнения. Пусть я — текущее допустимое реше­ ние задачи (2). Тогда часть ограничений этой задачи выполняется

может обращать в неравенства все ограничения задачи (2).) Для тех ограничений, которые удовлетворяются как равенства, условие (cj — яа7-) Xj = 0 выполняется при любых положительных значе­ ниях соответствующих переменных xj. Если же ограничение выполняется как неравенство, т. е. Cj — яа7- > 0, то для выполне­ ния условия (cj — яа;-) Xj = 0 необходимо приравнять соответ­ ствующую переменную xj нулю. Как найти х, удовлетворяющее

условию (За) и ограничениям задачи (1)?

поэтому условие (За) выполнится только при Xj = 0. Таким обра­ зом, если выразить вектор b через неотрицательную линейную комбинацию столбцов aj (/ 6 /), то коэффициенты Xj ^ 0 (j 6 J)

вместе с Xj (/ £ N \ J) составят оптимальное решение задачи (1), поскольку они удовлетворяют условиям дополняющей нежестко­ сти (3). Для нахождения неотрицательной линейной комбинации столбцов aj (/ 6 J) поставим следующую задачу, называемую

вспомогательной задачей:

удовлетворяющие условиям задачи (4), являются искомой линей­ ной комбинацией. Эти Xj (/ 6 J) вместе с xj = 0 (j € N \ J) пред­ ставляют собой допустимое и оптимальное 2) решение задачи (1).

Это решение допустимо, потому что ограничения задачи (4) при xf = 0 совпадают с ограничениями задачи (1), из которых вычеркнуты столбцы (j £ N \ J). (Вычеркивание столбца а7эквивалентно условию xj = 0.)

Если в оптимальном решении (4) £ > 0, то рассмотрим два слу­ чая. Обозначим оптимальное решение задачи, двойственной к (4),

J) Очевидно, xf есть невязка, характеризующая степень невыполнения условия (1), а | — сумма невязок. При £ = 0 вектор х есть решение зада­ чи (1).— Прим. ред.

2) Оптимальное, так как при этом решении выполняются условия (За).—

Прим. ред.

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

яЬ = | > 0 и я'Ь = (я -f- 0я) Ь — яЬ + 0яЬ,

а 0 можно придать любое положительное значение. Отсюда в силу теоремы двойственности задача (1 ) не имеет допустимых реше­

ний.

Тогда я '= я + 0я является допустимым решением при О < 0 < 0 1г поскольку

Кроме того, я' «лучше» исходного решения я:

я'Ь = яЬ |-0яЬ;>яЬ (так как яЬ = £ > 0 , 0>-О).

Таким образом, взяв 0: 0 < 0 ^ 0±, получим допустимое реше­ ние я' задачи (2 ) со значением целевой функции не меньшим, чем

при решении я. Исходя из полученного решения я' можно снова определить множество J = { / | я'а;- — Cj — 0}. Указанный про­ цесс может быть продолжен до тех пор, пока либо будут получены оптимальные решения задач (1) и (2), либо выяснено, что задача (1) не имеет допустимых решений 2)* .

Пример 1. Рассмотрим задачу: найти минимум

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