На головну

Геометричний метод розв'язання задач ЛП

  1.  C) вказати функціональну валюту підприємства і метод перекладу, використаний для визначення допоміжної інформації.
  2.  C. Неадекватність вихідної методологічної установки теоретико-інформаційного процесу феномену цілісності мислення
  3.  D. Про методологічної ролі концепції цілісності в дослідженні мислення
  4.  Event-менеджмент - поняття, основні методи.
  5.  FISH-метод забарвлення хромосом
  6.  I група Організаційно-стимулюючі методи
  7.  I етап - освоєння методики, запуск очисного механізму.

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

Розглянемо задачу в стандартній формі (1.4) - (1.6)

Знайти такий план Х = (Х1, Х2, ..., Хn) випуску продукції, що задовольняє системі

 
 


А11 * Х1 + А12 * Х2 + ... + А1N * Xn <= В1

а21 * Х1 + а22 * Х2 + ... + а2n * Xn <= В2 (1.4)

...............................

аm1 * Х1 + аm2 * Х2 + ... + аmn * Xn <= Вm

і умові Х1> = 0, X2> = 0, ..., Xn> = 0, (1.5)

при якому функція

F = С1 * Х1 + С2 * Х2 + ... + Сn * Xn (1.6)

приймає макс значення.

 
 

 з двома змінними (n = 2). До такої форми може бути зведена і канонічна задача (з обмеженнями у вигляді рівнянь), коли число змінних n більше числа рівнянь m на 2, тобто n - m = 2.

ABCDE - геометричне зображення системи обмежень. Необхідно серед точок цього багатокутника знайти таку точку, в якій лінійна функція F = С1 * Х1 + С2 * Х2 приймає макс або мін значення.

Розглянемо лінію, уздовж якої функція приймає одне і те ж фіксоване значення а, Тобто F = а, або

з1 * х1 + с2 * х2 = а.

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

Рівняння лінії з1 * х1 + с2 * х2 = а - це рівняння прямої лінії. При різних значеннях а лінії будуть паралельні, тому що їх кутові коефіцієнти визначаються співвідношенням між коефіцієнтами з 1 и с2 і, отже рівні.

Важлива властивість лінії рівня полягає в тому, що при паралельному зсуві лінії в одну сторону рівень тільки зростає, а при зсуві в іншу - тільки убуває.

Може бути необмежена прямокутна область:

 В даному прикладі є хв, але немає макс.

У вищенаведених прикладах макс і мін досягалися в одній точці, тобто задача мала єдине рішення.

А
 Можуть бути інші варіанти:

           
   
 
   
 з1 с2
 
 


На лівому малюнку видно, що лінія рівня з макс рівнем збігається з граничною лінією АВ багатокутника рішень АВСD. Отже, на відрізку АВ лінійна функція приймає одне і те ж макс значення. Це означає, що завдання має нескінченно багато оптимальних рішень (їх задають координати точок відрізка АВ), серед яких базисних оптимальних рішень два - відповідно в кутових точках А і В. Точки відрізка АВ задаються рівнянням відповідної прямої, де с1 <= Х1 <= c2 .

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

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

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

Плюси геометричного методу:

§ простий,

§ наочний,

§ швидко отримати відповідь.

Мінуси геометричного методу:

§ можливі технічні похибки,

§ можна застосовувати, коли в завданні тільки 2 змінних.

 




 лінійне програмування |  Поняття економіко-математичної моделі |  Завдання про розкрої матеріалів. |  Система m лінійних рівнянь з n змінними |  Геометричний сенс рішень нерівностей, рівнянь і їх систем |  Є опуклим багатокутником (або опуклою багатокутної областю). |  Знаходження оптимуму лінійної функції |  Особливі випадки симплексного методу |  сімплексні таблиці |

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