Реферат: Симлекс-метод

тогда

Если alj(k)<0, тогда al0(k+1) > 0, поскольку ai0(k) > 0 , aij(k) > 0.

Если alj(k)>0, то

будет больше нуля при всех l=1, 3. ..., m тогда и только тогда, когда

(3.3.20)

Преобразование Гаусса называют симплексным преобразованием, когда направляющий элемент определяют по следующим правилам:

a) направляющий столбец j выбирают из условия, что в нем имеется хотя бы один положительный элемент;

б) направляющую строку i выбирают так, чтобы отношение было минимально при условии, что aij>0.

При таком преобразовании в базис вводится вектор Aj и выводится вектор Аi. Теперь надо определить, как выбрать вектор, вводимый в базис, чтобы при этом значение целевой функции увеличилось.

Для этого используют так называемые оценки векторов Dj:

(3.3.21)

где Iб - множество индексов базисных векторов; xij- определяют из условия

(3.3.22)

Величины {Dj } равны симплекс-разницам для переменных {xj} с противоположным знаком. Следовательно, для того чтобы значение целевой функции увеличилось, необходимо выбрать направляющий столбец Аj с наибольшей по модулю отрицательной оценкой, то есть

.

Для решения задачи симплекс-методом на каждой итерации заполняют симплекс-таблицу 3.3.

Таблица 3.3.

c	c1	c2	c3	.	cj	.	cn
Bx	a00	A1	A2	A3	.	Aj	.	An
c1	x1	a1o	a11	a12	a13	.	a1j	.	a1n
c2	x2	a2o	a21	a22	a23	.	a2j	.	a2n
.	.	.	.	.	.	.	.	.	.
ci	xi	aio	ai1	ai2	ai3	.	aij	.	ain
.	.	.	.	.	.	.	.	.	.
cm	xm	amo	am1	am2	am3	.	amj	.	amn
D	D1	D2	D3	.	Dj	.	Dn

Последняя сторока таблицы - индексная -служит для определения направляющего столбца. Ее элементы Dj определяют по формуле (3.3.21). Очевидно, для всех базисных векторов {Ai} i=1,.,m оценки Dи=a0и=0.

Значение целевой функции a00 определяется из соотношения

.

В столбце Bx записываем базисные переменные {xi} i= 1, ..., т. Их значения определяются столбиком свободных членов ai0, то есть

xi=ai0, i=1, 2,.,m.

Направляющие строка Ai и столбец Aj указываются стрелками. Если в качестве направляющего элемента выбран aij, то переход от данной симплекс таблицы к следующей определяется соотношениями (3.3.16) - (3.3.18).

Итак, алгоритм решения задачи ЛП табличным симплексом-методом состоит из этапов.

1. Рассчитывают и заполняют начальную симплекс-таблицу с допустимым единичным базисом, включая индексную строку.

3. В качестве направляющего столбца выбирают Aj, для которого

.