11. Модифицированный см

Модифицированный СМ

В данном методе на каждой итерации преобраз не все yj, а только матрица B(-1), Cb*B(-1), Yb, Y. Величины Yj-Cj и величина yk вычисляются по формулам Yj-Cj=( Cb* B^-1 )*Pj- Cj; yk= B^-1 *pk

При изложении МСМ рассматривают 2 случая :

1. когда в задачу вводятся искусственные переменные

2. когда не вводятся

Рассмотрим 2 случай.

Y=схmax при ограничениях Ах=b xj>=0

П усть базисное допустимое решение определяется матрицей В. Известно, что Y=Cb*xb=0 Тогда допустимое решение в векторном виде мб представлено следующим образом:

Столбцы, представляющие в целом матрицу размером (m+1)*n обозначим через 1…m, тогда все вычисления для СМ мб представлены в таблице стандартного вида

Баз. Перем.	1		m	Xb	yk
Y	01		0m	Y	Yk-Ck
Xbm	m1		mm	Xv	ymk

Предположим, что в таблицу внесены все данные, кроме столбца yk. Необходимо определить, явл ли это решение оптимальным и если нет, то на след итерации ввести в базис вектор.

Для этого ввести скалярное произведение первой строки и производственного ве-ра (для всех небазисных переменных) после чего найти разницу Yj-Cj. Если все разницы> 0 , то решение оптимально, если нет, то в соответствии с общим правилом СМ находим производственный в-р , который дб введен в базис.

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

строки и таблицы и производственного в-ра pk.Эти значения заносим в последний столбец. После этого исключаем в-р, определяемый фналогично СМ.

Затем табл преобразуется в новую, аналогичную таблицу, котор соотв новому базисному решению.

Рассмотрим случай, когда в задачу нужно ввести искусственные переменные.

В этом случае решение проводится в 2 этапа:

На первом этапе значение искусственных переменных уменьшается до 0, для этого все коэ-ты цел-ой ф-ии , соответствующие реальным переменным, полагают =0, независимо от их значения. А значения коэ-ов соотв-е иск-м переменным = -1. На втором этапе находится оптимальное базисное решение. На этом этапе коэ-ты целевой ф-ии полагают их реальным значениям, а коэ-ты искусств. переменных, оставшихся в базисе принимают = 0.

Предположим, что в задачу было введено m искусственных переменных. В этом случае на первом этапе максимизируется ф-я F/=-xa1-xa2-…-xam. На втором этапе максимизируется ф-я Y=cx. На втором этапе коэ-ты ц-ой ф-ии, соотв-е иск-м переменным должны быть =0. Поэтому, если после завершения 1-го этапа в базисе ост какие-то сискуств-е переменные =0, то в задавчу необходимо добавить ограничения, запрещающие эти переменные на их значениях.

Если исходная задача имеет решение, то по окончании первого этапа F=0 и в дальнейшем не меняется.

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