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

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

,

.

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

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

= , .

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

Шаг 2. Если ,

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

= ,

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

f ( ) = ( , )

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

Шаг 3. Если

, ,

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

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

.

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

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

, , .

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