Властивості НМ:
• елементарними перетвореннями рядків (стовпців) невирождену матрицю M можна привести до одиничної матриці;
• ранг матриці дорівнює її розмірності.
Вставка* К
Зауваження 9.1.1.
Припущення про невироджені ЗЛП справедливи для більшості завдань, що зустрічаються на п рактиці. З рішенням вироджених задач, справляються наступним чином: - так як вирожденність призводить до зациклювання алгоритму в деякій вершині на шляху при переборі вершин симплексу, - треба трохи відхилитися від значення bj, так, що-б істотно не змінити рішення, але "роздвоїти" проблемну вершину.
9.2 . Властивості рішень ЗЛП
Рішення ЛП завдань симплекс методом базується на використанні наступних її основних властивостей:
(1) опуклість множини допустимих рішень;
(2) існування базисних допустимих рішень;
(3) тотожність базисних допустимих рішень і вершин множини допустимих рішень і
(4) збіг оптимального рішення задачі (якщо воно існує) з відповідною вершиною допустимої множини рішень.
Доведемо першу властивість.
9.3. Опуклість множини допустимих рішень
Нехай маємо ЛП завдання в канонічному вигляді: .
чи в матричному вигляді (9.3.0)
xi 0, i=1,...,n
Визначення 9.3.1
Множина X точок в Rn, задовольняючих обмеженням задачі ЛП (9.3.0.)
Ax = b, x 0,
є множина допустимих рішень ЛП задачі (9.3.0.), або коротше,
допустима множина задачі ЛП.
Твердження 9.3.1
Множина X допустимих рішень
X = { x э Rn: Ax = b, } (9.3.1)
задачі ЛП є опуклим.
Достарыңызбен бөлісу: |
