15. Окремі випадки розв`язків задачі лін. Оптимізації та їх ознаки в симплекс таблиці.
1. Неограниченность решения.
Признак: отсутствие положительных коэф. в столбце с отрицательной оценкой.
Причиной возникновения может быть неполнота условия, устранения этого недостатка может привести к ограниченности ОДР и соответственно возможности определения оптим. решения.
2. Вырожденное решение – опорное решение, в котором хотя бы одна базисная переменная равна 0. Причиной возникновения может быть наличие хотя бы одного избыточного ограничения.
Признаком
ее является наличие двух минимальных
значений, что делает невозможным
определения разрешающей строки без
дополнительного анализа.
.
По данной причине возможен вариант зацикливания, т.е.возврат к предыдущ.базису после нескольких итераций.
Для устранения этого разреш.строка выбирается как та, которой соответствует наименьшее соотношение элементов столбца с отрицательной оценкой, величина которой следующая после величины разрешающего столбца.
F=
(ГРАФИК)!!!
АОВ – обл.доп.реш.
Fmax=F(B), B(0;3)
,
,
,
- базис;
(0,0,2,2) – опорное.
|
|
|
|
|
|
|
|
|
0 |
|
2 |
1 |
1 |
1 |
0 |
2 |
2 |
0 |
|
2 |
1* |
2 |
0 |
1 |
2 |
1* |
|
|
F=0 |
-3* |
-1 |
0 |
0 |
|
|
0 |
|
0 |
0 |
-1 |
1 |
-1 |
|
|
3 |
|
2 |
1 |
2 |
0 |
1 |
|
|
|
|
F=6 |
0 |
5 |
0 |
3 |
|
|
(3;0;0;0)
опт.,
Fmax=6.
3. Альтернативний розв`язок.
Причина виникнення: рівнобіжність прямої (площини, гіперплощини), що відповідає ц.ф.та прямує одного із зв`язуючих обмежень.
Наслідком є наявність декількох точок, в яких одночасно ц.ф. набуває опт.значення.
Якщо х1,х2…хК це оптимальні розв`язки задачі, то загальний опт. розв`язок має вигляд:
,
є
(1-
)
Ознака:
Наявність хоча б однієї нульової оцінки вільної змінної при невід`ємності інших оцінок.
Уникнення: стовпчик вільної змінної з нульовою оцінкою приймається в якості розв`язуючого і т.д..
16. Метод штучного базису.
Якщо обмеження задачі є такими, що для виділення одиничного базису необхідно домножати окремий рядок на -1, то може виникнути ситуація, коли базисний розв`язок не є опорним.
Приклад:
F=
– базис.
(0;0;-1;6) базисний, який не є опорним.
У цьому випадку доцільно застосовувати метод штучного базису:
1. Побудова розширеної задачі.
А) в початкову задачу вводяться додаткові «штучні» невід`ємні змінні, к-ть яких = к-ті від`ємних базисних змінних.
Б) штучні змінні записуються в лівій частині відповідних обмежень в якості доданків з коеф.+1.
В) штучні змінні записуються в ц.ф. з коеф. –М (М→∞) в якості доданку.
2. Побудована М-задача дозволяє виділити одиничний базис, якому відповідає певний опорний розв`язок, тому воно розв`язується симплекс-методом.
Приклад:
– «штучна»
змінна.
,
,
≥0
F=
М
, - базис.
(0;0;0;6;1) – базисний опорний.
Застосовується симплекс-метод.
Отримавши (не отримавши) оптимальний розв`язок М-задачі робляться висновки відносно оптимального розв`язку початкової задачі:
1.
Якщо в оптимальному розв`язку М-задачі
усі
штучні змінні = 0, то оптимальний розв`язок
початкової задачі записується в формі
=
).
2. Якщо оптимальний розв`язок М-задачі містить хоча б одну штучну змінну відмінну від 0, то система обмежень вихідної задачі є пустою множиною, тобто не має розв`язку.
3. Якщо М-задача виявилась не розв`язною у зв`язку з необмеженістю ц.ф., то початкова задача також є нерозв`язною у зв`язку з не обмеж. ц.ф. або несумісною системи обмежень.