1. Витоки симплексного методу і його суть
2. Алгоритм симплекс-методу
3. Практичний приклад застосування симплексного методу

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

Найкраще спасибі - порекомендувати цю сторінку

Витоки симплексного методу і його суть

Симплекс-метод розв'язання задач лінійного програмування був розроблений американським математиком Джорджем Данцигом. Також великий вклад в його розвиток внесли вчені Кун і Таккер, більш відомі своїми розробками в області нелінійного програмування.

Суть симплексного методу полягає в наступному: необхідно максимізувати (відповідно мінімізувати) певний критерій при накладених лінійних обмеженнях. Цим критерієм може виступати валовий дохід від реалізації продукції, сукупні операційні витрати на виробництво товарів і так далі.

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

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

Алгоритм симплекс-методу

Послідовність дій можна описати таким чином:

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

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

Практичний приклад застосування симплексного методу

Вирішимо симплексним методом задачу. Максимізували функцію $$ L = X + Z \ rightarrow \ max $$ при обмеженнях $$ \ left \ {\ begin {array} {l} Y-X + Z = 1, \\ X-2Z + T = 2. \ End {array} \ right. $$ У нас є чотири змінні - $ X, Y, Z, T $ - причому критерій залежить лише від двох змінних. Приймемо $ Т $ і $ Y $ за базисні змінні і висловимо їх через інші дві вільні змінні. отримаємо:

$$ L = X + Z \ rightarrow \ max, $$ $$ \ left \ {\ begin {array} {l} Y = 1 + XZ, \\ T = 2-X + 2Z. \ End {array} \ right. $$

При $ X $ і $ Z $ рівних нулю, базисні змінні рівні $ Y = 1, T = 2 $. Значення критерію $ L = 0 $. Значить, точка $ (1,0,0,2) $ є базисним рішенням. Почнемо перебір вершин симплекса. Збільшити критерій можна збільшивши $ Z $ до одиниці. Тоді при $ Z = 1, X = 0 $ базисні змінні приймуть значення $ Y = 0, T = 4 $. Нове допустиме рішення - це точка $ (0,0,1,4) $, критерій дорівнює $ L = 1 $.

Тепер висловимо $ Z $ і $ T $ через $ Y $ і $ X $:

$$ L = 1-Y + 2X \ rightarrow \ max, $$ $$ \ left \ {\ begin {array} {l} Z = 1-Y + Z, \\ T = 4-2Y + X. \ End {array} \ right. $$

Збільшити $ L $ можна тільки збільшивши $ X $. Однак $ X $ можна збільшувати нескінченно, вихідним із системи рівнянь. Отже, критерій $ L $ братиме необмежено великі значення, рішення задачі симплекс-методом не існує. У цьому випадку говорять, що має випадок нескінченного симплекса.

Інші приклади розв'язання задач лінійного програмування ви знайдете в розділі: Завдання лінійного програмування з рішеннями (Десятки прикладів!).

Корисна сторінка? Збережи або розкажи друзям

додатково:

Симплексний метод на замовлення. Тільки на відмінно.