На головну

II. Проблема виродженого базисного рішення

  1. Quot; Коли проблема стає проблемою "або особистісні кореляти труднощів юнацького самовизначення
  2. А) Проблема людини в філософії Китаю.
  3. Автомобільного транспорту та шляхи їх вирішення
  4. Алгоритм пошуку опорного і оптимального рішення
  5. Алгоритм рішення (алгоритм Дейкстри)
  6. Алгоритм рішення (алгоритм Літтла)

Приклад 5.8. Вирішити симплексним методом задачу:

 при обмеженнях:

Рішення.Після введення додаткових змінних, які візьмемо в якості основних, отримаємо:

I крок. Основні змінні: х3, х4, х5. Неосновні змінні: х1, х2.

Після перетворень:

Х1 = (0; 0; 2; 6; 14) - допустиме базисне рішення.  . Критерій оптимальності на max не виконано, переводимо в основні змінну х1 так як в вираз для F вона входить з позитивним коефіцієнтом. x1 = Min {2; 6/3; 14/6} = 2. Оціночні відносини в двох змінних рівняннях збігаються, тому в якості дозволяє можна взяти будь-який з них, наприклад перше.

II етап. Основні змінні: х1, х4, х5. Неосновні змінні: х2, х3.

Отримаємо після перетворень:

X2 = (2; 0; 0; 0; 2) - вироджений базисне рішення, основна компонента х4 = 0.

Лінійна функція мети, виражена через неосновні змінні, має вигляд: F = 4 + х2 - 2x3. перекладаючи змінну Х2 в основні, отримуємо: х2 = Min {  ; 0; 1} = 0, тому на наступному кроці зміни функції мети не відбудеться  . Це порушення принципу поліпшення рішення, який повинен виконуватися при використанні симплексного методу, тому уточнимо цей принцип: кожен наступний крок повинен поліпшити або, в крайньому разі, не погіршити значення лінійної функції.

III крок. Основні змінні: х1, х2, х5. Неосновні змінні: х3, х4.

Після перетворень отримаємо:

X3 = (2; 0; 0; 0; 2) - це базисне рішення теж виродилися. Покомпонентно воно збігається з Х2, Однак формально відрізняється набором основних змінних. Вираз лінійної функції через неосновні змінні має вигляд: F = 4 + х3 - x4, F(X3) = 4.

Виконаний крок хоча і не викликав збільшення значення лінійної функції, не є зайвим, оскільки привів до нового базисного рішення. Наявність "порожніх" кроків (  ) Може привести до так званого "зациклення", тобто поверненню до раніше знайденому допустимому базисного вирішення (з тим же набором основних і неосновних змінні), і в цьому випадку процес нескінченний. Уникнути "зациклення" можна за допомогою певних заходів, які в даному посібнику не розглядаються. Завдання з "зацикленням" зустрічаються надзвичайно рідко, так як до нього призводить не тільки виродження, але і поєднання його з іншими специфічними умовами,

Висновок. Якщо на якомусь етапі найбільше можливе значення змінної досягається в декількох рівняннях одночасно (збігаються їх оціночні відносини), то що дозволяє є будь-яка з них. На наступному кроці отримуємо вироджене базисне рішення, перехід до чергового базисного рішенням може не змінити функцію мети (  ).

Зауваження.Виродження, отримане при оптимальному рішенні, може привести до альтернативного оптимуму навіть при ненульових коефіцієнтах при всіх неосновних змінних в лінійній функції (про це згадувалося при розгляді I особливості).

III. Відсутність кінцевого оптимуму

Приклад 5.9. Вирішити симплексним методом задачу:

 при обмеженнях:

Рішення. Геометричне рішення цього завдання наведено в прикладі 4.3, б (див. Рис. 4.5,6). На черговому кроці вирішення цього завдання симплексним методом отримуємо.

Основні змінні: х1, х2, х5. Неосновні змінні: x3, x4.

 - Базисне рішення;  ; min не досягнуть, так як критерій оптимальності на min не виконано: змінна х3 має негативний коефіцієнт у виразі для F. визначаємо х3 = Min ( , ,  ) =  , Так як в кожне з трьох рівнянь ця змінна входить з тим же знаком, що і вільний член. Рівняння не обмежують зростання х3, Тому і значення функції F необмежено і негативно, тобто .

Якщо на якомусь етапі отримуємо, що у всіх рівняннях системи нескінченні оціночні відносини тієї змінної, яка перекладається в основні, то завдання не має кінцевого оптимуму (  , Якщо завдання на відшукання максимуму,  , Якщо завдання на відшукання мінімуму).

Підводячи підсумки, можна стверджувати, що якщо система обмежень несуперечлива, то виконання кінцевого числа послідовних кроків симплексного методу або призводить до знаходження оптимального рішення задачі, (воно може б неєдиним), або до встановлення того факту, що лінійна функція не має кінцевого оптимуму.



Попередня   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   Наступна

ЗАГАЛЬНА ПОСТАНОВКА ЗАВДАННЯ лінійного програмування | Економіко-математична модель | Приклади завдань лінійного програмування | Загальна задача лінійного програмування | Геометричний сенс рішень нерівностей, рівнянь і їх систем | ГЛАВА 4. ГЕОМЕТРИЧНИЙ МЕТОД ВИРІШЕННЯ ЗАВДАНЬ лінійного програмування | Геометрична інтерпретація симплексного методу | Відшукання максимуму лінійної функції | Відшукання мінімуму лінійної функції | при обмеженнях |

© um.co.ua - учбові матеріали та реферати