Нахождение опорных решений

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

Опорные решения системы находят методом Гаусса при выполнении следующих условий.

1. В исходной системе все свободные члены должны быть неотрицательны: .

2. Ключевой элемент выбирают среди положительных коэффициентов.

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

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

Замечание 2. Если в столбцах коэффициентов при свободных переменных нет ни одного положительного элемента, то переход к другому опорному решению невозможен.

Пример.

базис								;
	-6 -8	-1 -3	-39	-5 -5		-1 1		min;
	-8	1 -3	-10 -18	-2 -5				min;
	3 -4		-10 -1	-2 -11				min; ;
								.