Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Обращение базиса и симплекс-множители



Вспомним вид общей задачи ЛП в стандартной форме:

Минимизировать

при ограничениях

(3.1)

Матрица A может быть разбита следующим образом:

A = (BR) (3.2)

где B - матрица с коэффициентом на диагонали x1, x2,…, xm, a R – матрица размерностью m × nm (остаток матрицы A).

Запишем уравнение (3.1) в виде

(BR) x = b (3.3)

Канонический вид для некоторого базиса может быть получен умножением вектора исходных ограничении на матрицу, полученную обращением этого базиса. Таким образом, каноническая форма для базиса получается умножением уравнения (3.3) на матрицу В-1.

B 1 (BR) x = B 1 b,

Тогда получим соотношение

Im (B- 1 R) x =b / (это - уравнение (3.2а)) (3.4)

или

(3.4б)

что соответствует канонической форме для ограничений. В (3.4) Im единичная матрица, b / = B 1 b

Если аj — столбец из коэффициентов при переменной хj в ограничении (3.1), то

(3.4а)

представляет собой столбец из коэффициентов при хj в канонической форме для всех столбцов j = m +1,…, n.

В каждой канонической форме относящиеся к ней базисные переменные были исключены из целевой функции z. В симплекс-методе это делается итеративно, например на каждой стадии с использованием исходного вида ограничений (3.1).





Дата публикования: 2015-01-10; Прочитано: 306 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.007 с)...