Условия перехода от одной Р-матрицы ЗЛП к другой. Определение. Р-матрицей КЗЛП (3. 18) будем называть расширенную матрицу системы линейных уравнений, равносильной системе (3. 63)

ОПРЕДЕЛЕНИЕ Р-МАТРИЦЫ ЗЛП

Определение. Р-матрицей КЗЛП (3.18) будем называть расширенную матрицу системы линейных уравнений, равносильной системе (3.63), содержащую единичную подматрицу порядка m на месте n первых столбцов, все симплекс разности которой неотрицательны.

Очевидно, что всякая Р-матрица ЗЛП определяет некоторое базисное решение системы уравнений (3.63) (см. пример 3.5).

Определение. Базисное решение системы линейных уравнений (3.63), определяемое Р-матрицей, называется псевдопланом ЗЛП.

Пусть известна Р-матрица ЗЛП (3.18), определяющая псевдоплан

= , .

Условия перехода от матрицы к матрице составляют содержание теоремы 3.12.

Теорема 3.12. Пусть < 0 и в l -й строке матрицы есть хотя бы один отрицательный элемент. Тогда с помощью одного шага метода Жордана–Гаусса можно построить новую Р-матрицу , выбрав направляющий элемент из условия

. (3.65)

Замечание 1. Если в матрице нет < 0, то определяемый ею псевдоплан является решением ЗЛП.

Теорема 3.13. Пусть < 0 и в l -й строке матрицы нет ни одного отрицательного элемента. Тогда множество планов Р ЗЛП (3.18) пусто.

Замечание 2. При переходе от матрицы к матрице целевая функция изменяется в соответствии с формулой

f () = f () + = f () + , (3.66)

откуда следует, что

f () f (), (3.67)

так как < 0 и . Из неравенства (3.67) следует, что при переходе от одного псевдоплана к другому значение целевой функции не возрастает.

Дата добавления: 2014-12-29