10. Правила замены вектора в базисе

1. Определение вектора, вводимого в базис. Вычисляем (для небазисных переменных) Yk-Ck=min(Yj-Cj). Фактически это означает max по модулю отрицательного значения в строке Pk на следующей итерации ввода в базис. Если min достигается при нескольких векторах, то в базис вводится вектор с наименьшим индексом j.

2. Определение вектора, исключающегося из базиса. Вычисляем отношение (X_Br/y(rk))=min(X_Br/y(rk)) y(ik)>0 В этом случае из базиса исключается r-столбец матрицы В и заменяется вектором Pk. В случае неоднозначности выбираем вектор, для которого y(ik) наименьшее. Если этим неоднозначность не исключилась, то среди оставшихся векторов выбираем вектор с наименьшим индексом.

Общий вид симплекс таблицы в матричной записи

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

B=1;

Xb=b

yj=pj

Yj-Cj=Cb*pj-Cj

Если единичная матрица не содержится в матрице А, то присоединяем к матрице А необходимое число единичных векторов, чтобы такая матрица получилась. Дополнительные векторы называются искусственными векторами, а соответствующие им переменные искусственными переменными xai. Исходные переменные в отличие от искусственных принято называть истинными.

Далее решение осуществляется 2-мя путями: а) задачу ЛП решают в 2 этапа, для чего на первом этапе образуют искусственную целевую ф-ию

б) решение задачи ЛП без использования целевой ф-ии методом введения штрафов.

В этом случае значение искусственных переменых также нужно уменьшить до 0. Для этой цели коэф-ты целевой ф-ии, соотв-ие иску-ым переменным, полагают равными –М, где М-достаточно большое положительное число.

Если исходная задача имеет допустимое решение, тозначение искусственной переменной мб сделаны = 0. После того, как введены искусственные переменные и заданы некоторые значения М, исходная задача ЛП мб задана в следующем виде:

Максимизировать цел-ю ф-ию вида Y= cx-M1*xa  max при Ax+I*xa=b x>=0; xa>=0

Наччальное базисное допустимое решение для задачи будет иметь вид : Xb=b; yj=pj; Y=-M1b; Yj-Cj=-M1pj-Cj

Если матрица А содержит некоторый единичный в-р, то вводить его не надо.

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

Общий вид

Баз. Переем.	Cb	b	P1		pn
Xb1	Cb1	y10	y11		y1n
Xbm	Cbm	ym0	ym1		ymn
	Y=ym+1,i

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

Условия получения неограниченного решения и альтернативных оптимальных решений

Теория СМ утверждает, что оптимальное решение задач ЛП всегда соответствует допустимому базисному решению. Из этого правила сущ-ют 2 исключения:

1. Если линия значений ЦФ при оптимальном решении оказывается парал-ой линии одного из уравнений ограничений (не избыточного), то сущ-ют альтернативные оптимальные решения.

Для всех небазисных Xj, удовл-их условию оптимальности и по крайней мере, одна разность =0. Если вектор, ассоциированный с такой разностью =0 можно ввести в базис, то сущ-т и альтернативное оптимальное решение.

2. Ситуация, при которой условие оптимальности показывает, что небазисный вектор, будучи включенным в базис может улучшить решение, однако такой вектор сделать базисным нельзя. Это означает, что если Yj-Cj<0 и yij<0, то вводить вектор Pj нельзя, поскольку переменную, ассоциированную Xj, ассоциировать с вектором Pj можно увеличивать неограниченно, не влияя на допустимость решения задачи. В этом случае решение называется неограниченным.