§ 3. Описание алгоритма

3.1. Введем некоторые определения и обозначения. Рассмотрим задачу Напомним данное выше определение множества

Отметим, что поскольку каждое ограничение (1.9) содержит в точности одну переменную план полностью определяется множеством В самом деле, если

то

Считая, что мы будем иногда обозначать план через

Соответствующее значение целевой функции будем обозначать через Таким образом, или

Набор значений, принятых целевой функцией на планах (напоминаем, что для них вплоть до итерации обозначим через

Если множество не пусто, то наименьшее содержащееся в нем значение назовем рекордом для если пусто, то в качестве рекорда берется Таким образом, рекорд определяется как

При переходе к итерации вектор А подлежащий «введению в базис», будет выбираться из некоторого множества которое называется множеством улучшающих векторов для плана Точное определение будет дано ниже. Введем множества

Определим теперь величины которые будут служить критерием выбора «вводимого» столбца. Положим для плана

В ходе алгоритма значения отвечающие определенному плану будут последовательно вычеркиваться. Обозначим через множество тех для которых отвечающие плану вычеркнуты до получения плана Множество считается пустым. Далее определим множество

где объединение берется по всем для которых Таким образом, есть множество всех тех для которых отвечающие любому из планов для которых были вычеркнуты до получения плана

Определим для плана множество таких что при переходе от получающееся значение целевой функции будет не меньше рекорда для

Определим теперь множество таких что при переходе от ни одно отрицательное не увеличится:

Теперь можно определить множество улучшающих векторов для пробного плана

Ясно, что для плана будет

Рассмотрим два плана Определим аналогичное (3.10) множество тех что при переходе от значение целевой функции будет не меньше рекорда для

Наконец, положим

будем называть его множеством улучшающих векторов для плана остающимся после итерации 5.

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

3.2. Перейдем к пошаговому описанию одной итерации аддитивного алгоритма. Как уже упоминалось, в качестве начального плана берется вектор для которого

Пусть после итераций получен план для которого выполнены соотношения

Шаг 1. Просмотреть

1) Если положить Образовать, согласно (3.13), множества вычеркнуть все и перейти к шагу 5.

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

1) Если имеется для которого перейти к шагу 2.

Шаг 2. Найти множество улучшающих векторов для плана образовав, согласно (3.12), множества

2) Если перейти к шагу 5.

2) Если перейти к шагу 3.

Шаг 3. Для всех для которых проверить неравенства

где через обозначены отрицательные элементы матрицы А.

3') Если существует для которого (3.15) не выполнено, перейти к шагу 5.

3") Если все неравенства (3.15) окажутся строгими, найти, согласно (3.8), все для и выбрать так, чтобы

вычеркнуть и перейти к шагу 8.

3) Если все неравенства (3.15) выполняются и существует такое, что для оказываются равенствами, то определить множество тех для которых О хотя бы при одном Шаг 4. Проверить соотношение

4) Если (3.17) выполняется, вычеркнуть и для (не вычисляя их). Положить вычислить новое значение целевой функции

значения свободных переменных

и перейти к шагу 1 (т. е. начать новую итерацию).

4) Если (3.17) не выполняется, вычеркнуть для (не вычисляя их) и перейти к шагу 5,

Шаг 5. Для всех для которых найти, согласно (3.14), множества Просмотреть их в порядке убывания номеров до тех пор, пока не обнаружится такое что либо не выяснится, что все пусты.

5) Если Для всех при которых процесс закончен. Если при этом то задача не имеет планов. Если же то план для которого является оптимальным.

5) Если перейти к шагу 6.

Шаг 6. Для тех для которых проверить неравенства

при

6) Если ни одно из неравенств (3.20) при не выполняется, вычеркнуть для всех и повторить шаг 5 для заменив в шагах на Всякий раз, когда шаг 5 будет повторяться для в шагах 5 и 6 будет заменяться на

Если (3.20) не выполняется ни при одном для которого процесс окончен (см. п. 5)).

6) Если все неравенства (3.20) при оказываются строгими, выбрать так, чтобы

вычеркнуть и перейти к шагу 8.

6) Если при все неравенства (3.20) выполнены и существует такое подмножество что для все неравенства (3.20) выполняются как равенства, перейти к шагу 7.

Шаг 7. Проверить соотношение

где через обозначено множество тех для которых хотя бы при одном

7) Если неравенство (3.22) выполнено, вычеркнуть для всех Положить вычислить для нового плана значение целевой функции

свободных переменных

и перейти к шагу 1 (начать следующую итерацию).

7") Если (3.22) не выполнено, вычеркнуть для всех и повторить шаг 5 для Если (т. е. не существует), процесс закончен (см. п. 50).

Шаг 8. Положить и вычислить для нового плана значение целевой функции и свободных переменных:

Здесь определяется как номер последней вычеркнутой Перейти к шагу 1 (начать новую итерацию).

Процесс заканчивается при достижении плана для которого имеет место п. 50 либо 60, причем не выполняется ни при одном таком, что либо же п. и

Блок-схема аддитивного алгоритма дана на рис. 11.3.1.

3.3. Описанный процесс за конечное число шагов либо приводит к оптимальному плану, либо позволяет установить отсутствие допустимых планов у исходной задачи. На доказательстве этого факта ввиду его громоздкости мы останавливаться не будем.

(кликните для просмотра скана)

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