Тема 9. Матричний вид каноничної ЛП задачі. Опуклість множини допустимих рішень. Властивості рішень ЗЛП. Існування базисних допустимих рішень та іх геометрична інтерпретація
9. 1. Матричний вигляд каноничної ЛП задачі
Приведемо матричний вигляд каноничної форми ЛП задачі
Тут: при с э Rn , x э Rn, b э Rm,
A = A(m,n), rankA =m, (m), : x =(x1,x2,...,xn),
Нагадаю, що при m>n - рішень нема, m=n – єдине рішення при , (m), маємо ОДР
З матриці А и вектору b cконструюємо составну матрицю Ab:
Визначення 9.1.1.
Говорять, що стандартна ЛП задача невирождена, якщо кожна підматриця Аi(m*m), що вибрана з расширеної матриці Ab (m*(n +1))=[A|b], - невирождена.
В інакшому випадку говорять, що стандартна ЛП задача - вирождена задача (в цьому випадку маємо що небазисних змінних що мають=0, > ніж n-m штук)
Інше еквівалентне визначення - вироджена ЛПЗ, це така ЛПЗ, яка має вироджені плани (базисні рішення). Що таке вироджені базисні рішення - см нижче в розділі "базисні рішення".
Проблема в вироджених ЛПЗ –зациклівання алгоритму в вершинах симплексу, що відповідають виродженим базисним рішенням.
Вставка* П
Визначення. 9.1.2
Невироджена Матриця (інакше, неособлива матриця) НМ- квадратна матриця, визначник якої, відмінний від нуля. В іншому випадку, матриця називається виродженою.
Достарыңызбен бөлісу: |
