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

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

,

.

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

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

=, .

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

Шаг 2. Если ,

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

= ,

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

F ( ) = (,)

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

Шаг 3. Если

, ,

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

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

.

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

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

, , .

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

< Предыдущая		Следующая >