Нахождение опорных решений
Опорным решением системы линейных уравнений называется базисное решение, не содержащее отрицательных компонент.
Опорные решения системы находят методом Гаусса при выполнении следующих условий.
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; ; | |||||
. |