Определение Р-матрицы ЗЛП

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

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

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

Условия перехода от одной Р-матрицы ЗЛП к другой

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

= ; .

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

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

(2.79)

Доказательство.

Получим условия, которым должен удовлетворять направляющий элемент , чтобы . Из соотношения следует, что при < 0, тогда и только тогда, когда < 0 – это первое условие, которое мы должны наложить на выбор направляющего элемента.

В соответствии с (2.62) имеем:

(*),

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

Если , то для того чтобы , необходимо выбрать из условия

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

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

Доказательство.

Выпишем l -oe функциональное ограничение ЗЛП.

Так как и , то при любом

левая часть ограничения неотрицательна, а правая отрицательна.

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

f () = f () + = f () + , (2.80)

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

f () f (), (2.81)

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

Алгоритм Р-метода

Будем считать, что известна исходная Р -матрица задачи линейного программирования, определяющая исходный псевдоплан

,

.

В методе последовательного уточнения оценок последовательно строят Р -матрицы , , …, , … задачи линейного программирования, пока не получат Р -матрицу задачи линейного программирования, определяющую ее оптимальный план.

Рассмотрим алгоритм S -й итерации метода последовательного уточнения оценок. В начале S -й итерации имеем Р -матрицу задачи линейного программирования, определяющую псевдоплан

= , .

Шаг 1. Найдем номер l из условия

Шаг 2. Если ,

то псевдоплан

= ,

является оптимальным опорным планом, а

f () = (, )

есть оптимальное значение линейной формы , иначе переходим к шагу 3.

Шаг 3. Если

, ,

то задача линейного программирования не имеет решения (множество планов Р пусто), иначе переходим к шагу 4.

Шаг 4. Вычисляем для столбцов матрицы (, i = 1, 2, …, m) симплекс-разности и находим номер k из условия

.

Направляющий элемент на S -й итерации метода есть элемент .

Шаг 5. Вычисляем компоненты вектора :

, , .

Шаг 6. Производим один шаг метода Жордана-Гаусса с направляющим элементом . Вычисляем элементы Р -матрицы методом Жордана-Гаусса. Присваиваем переменной алгоритма S значение S +1 и переходим к шагу 1.