Алгоритм решения канонической задачи

а) записать исходную каноническую задачу одним из двух способов:

- в форме (11.1),(11.4),(11.3) при помощи линейных преобразований;

- в расширенной форме (11.5)—(11.7) с помощью перехода к М -задаче;

б) выделить базисные переменные (их можно подчеркнуть), входящие только в одно из уравнений системы (11.4) или (11.6) с коэффициентами 1, а во все остальные с коэффициентами, равными нулю;

в) выделить свободные переменные (все остальные, кроме базисных);

г) найти начальное базисное решение, полагая свободные переменные рав­ными нулю.

Шаг 2. Заполнить табл. 11.1:

а) столбец базисных переменных (БП);

б) столбец базисного решения (БР)\

в) строку и столбец с/ коэффициентов функции (11.1) или (11.5). В столбец С;в записываются коэффициенты, соответствующие базисным пере­менным;

г) совокупность коэффициентов 5)у- систем (11.4) или (11.6).

Шаг 3. Вычислить относительные оценки

т т

ДУ = с]-Цс1ваи = с/-*]’ г1 = Ъ%аЧ' j = \,#9632;..,m^-n,

1 = 1 /' = 1

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

Шаг 4. Проанализировать относительные оценки:

а) если все оценки А у неположительны, т.е.

А у lt;0, 7 = 1 ,...,/и + я,

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

Проанализировать полученное базисное решение:

- если число нулевых оценок Ау =0 равно числу базисных переменных,

задача имеет единственное решение. Если число нулевых оценок А у = 0 превыша­ет число базисных переменных, то задача имеет бесконечное множество решений;

- если все Ду неположительны, но базисное решение содержит хотя бы од­ну искусственную переменную, не равную нулю, то ограничения задачи несовме­стны;

б) если среди оценок есть положительные, то следует найти среди них мак­симальную:

Дг = шах Д/,

где У - множество индексов небазисных переменных, и проанализировать ко­эффициенты столбца таблицы, которому соответствует максимальная положи­тельная оценка (если таких оценок несколько, принято выбирать оценку с наи­меньшим номером).

Столбец, соответствующий выбранной оценке, помечается ® . Он называ­ется разрешающим.

Шаг 5. Поделить элементы столбца базисных решений (БР) на соответст­вующие элементы разрешающего столбца и среди полученных частных выбрать наименьшее. Строка, соответствующая выбранному отношению, помечается lt;8gt; . Она называется разрешающей.

Таким образом, новая переменная хг вводится на место переменной х5д,

удаляемой из числа базисных, номер которой 5д, а также номер 5 соответст­вующей строки таблицы, определяются из условия

ПИП

1 lt;1lt;,т

где Х;д - значение координаты текущего базисного решения, соответствующей /' -й строке; а1Г - коэффициент при координате хг в / -й строке. Если таких пе­ременных окажется больше одной, то из базиса выводится та переменная, кото­рая имеет больший номер. Заметим, что рассматриваются только неотрицатель­ные отношения, т.е. если коэффициент а1г отрицателен или равен нулю, то от­ношение не подсчитывается и на его месте в приведенных далее таблицах ста­вится знак

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

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

Шаг 6. Вычислить новое базисное решение, осуществив пересчет таблицы:

а) вместо координаты х8 в состав базисных ввести координату хг , значе­ние которой находится по формуле

X =^-

' а„'

и пересчитать 5-ю строку , в которой произошли изменения по базису:

asj .

= -=rL, у = +л.

Таким образом, каждый элемент строки, отмеченной ® , делится на раз­решающий элемент а5Г;

б) вычислить все остальные коэффициенты:

_ _ __ а5 } _

аи=а1]-а5]чг= аи--=^а(г, / = 1,... ,/и; / * 5; у = 1,...,т + л.

аэг

Новое базисное решение определить на основании текущего базисного решения по формулам

х1в = *1В - *В *

Для упрощения вычислений по приведенным формулам используется “правило прямоугольника”.

Пусть подсчитывается значение aij. Следует соединить элемент в пре-

дыдущей таблице с разрешающим элементом asr . Получена одна из диагоналей

прямоугольника. Вторую диагональ образует соединение элементов а1г и а8 Далее из текущего значения вычитается произведение элементов а1г и деленное на разрешающий элемент lt;5^. (рис. 11.1).

Рис. 11.1

quot;sj' air

аи=аи—=—

Перейти к шагу 3.

Замечания 11.2.

1. Если в задаче (11.1)—lt;11.3) в каждом уравнении имеется базисная пере­менная, то на шаге 1 нет необходимости делать линейные преобразования или вводить искусственные переменные.

2. Если решается задача поиска минимума, то стратегия симплекс-метода аналогична, только в базис вводится переменная, которой соответствует наи­меньшая отрицательная оценка Дг. Процесс перехода заканчивается, когда най­дено такое базисное решение, что все относительные оценки Ду, у = 1,...,т + я становятся неотрицательными: Ду gt; 0, у = 1,...,т + п.

Сходимость

Утверждение 11.2. При условии невырожденности симплекс-метод сходится за конечное число шагов [28].

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

В вырожденном случае, когда х8в = 0 и соответственно хг = = 0, про-

°5Г

исходит замена индексов базисных координат, но не их значений.

В ряде случаев в результате некоторого числа таких замен базиса процедура может прийти к зацикливанию. Предотвратить зацикливание можно используя ряд приемов: например, с помощью лексикографической процедуры, описанной в [29].

11.1.1.