Графічны метад рашэння задач лінейнага праграмавання

На гэтым уроку будзем знаёміцца ​​з графічным метадам рашэння задач лінейнага праграмавання , Гэта значыць, такіх задач, у якіх патрабуецца знайсці такое рашэння сістэмы лінейных раўнанняў і (або) няроўнасцей (сістэмы абмежаванняў), пры якім функцыя мэты - лінейная функцыя - прымае аптымальнае значэнне.

З прычыны таго, што навочнасць графічнага рашэння дасягаецца толькі на плоскасці, мы можам пазнаёміцца ​​з графічным прадстаўленнем задачы толькі ў двухмернай прасторы. Гэта прадстаўленне прыдатна для сістэмы абмежаванняў-няроўнасцей з дзвюма зменнымі або для сістэм ураўненняў, у якіх лік зменных на 2 перавышае лік раўнанняў, гэта значыць лік свабодных зменных роўна двум.

Таму графічны метад мае такія вузкія рамкі прымянення, што пра яго як пра адмысловы метадзе рашэння задач лінейнага праграмавання казаць нельга.

Аднак для выпрацоўкі наглядных уяўленняў аб рашэннях задач лінейнага праграмавання графічны метад ўяўляе пэўны цікавасць. Акрамя таго, ён дазваляе па-геаметрычнаму пацвердзіць справядлівасць тэарэм лінейнага праграмавання .

Сярод прамых згаданага сямейства паралельных прамых прамыя mn (зялёнага колеру) і MN (чырвонага колеру), якія назавем апорнымі. Апорнымі звычайна называюць такія прамыя, якія маюць з шматкутнік ABCDE хаця б адну агульную кропку, і шматкутнік ABCDE цалкам ляжыць па адзін бок ад гэтай прамой. Як відаць з чарцяжа, прамая mn з'яўляецца апорнай, бо яна датычыцца шматкутніка ў кропцы A і шматкутнік цалкам ляжыць правей (або вышэй) гэтай прамой. Прамая MN таксама з'яўляецца апорнай, бо мае з шматкутнікаў агульную кропку С і шматкутнік цалкам ляжыць лявей гэтай прамой.

з асноўных тэарэм лінейнага праграмавання вядома, што лінейная форма дасягае максімальнага і мінімальнага значэнняў у крайніх кропках мнагагранніка рашэнняў. Гэта значыць, што апорныя прамыя mn і MN характарызуюць экстрэмальныя значэння лінейнай формы (функцыі мэты), гэта значыць у кропках А і С лінейная форма дасягае аптымальных значэнняў. У кропцы А, якая знаходзіцца бліжэй да пачатку каардынатаў, функцыя мэты дасягае мінімальнага значэння, а ў кропцы З, якая знаходзіцца далей ад пачатку каардынатаў, - максімальнага значэння.

1. Пабудаваць шматкутнік рашэнняў сістэмы няроўнасцей.

4. Рухаючыся далей, прыйдзем да некаторага апорным становішчу, калі прамая будзе мець адну агульную кропку з шматкутніка рашэнняў. У гэтай кропцы функцыя мэты дасягае свайго максімуму.

5. Калі першапачаткова пабудаваная лінія роўных значэнняў перасякае шматкутнік рашэнняў, то функцыя мэты дасягае мінімальнага значэння ў вяршыні шматкутніка, размешчанай бліжэй да пачатку каардынатаў, а максімальнага значэння - у вяршыні, больш выдаленай ад пачатку каардынатаў.

Прыклад 1. Вырашыць графічным метадам задачу лінейнага праграмавання, у якой патрабуецца знайсці максімум функцыі пры абмежаваннях

Пабудуем шматкутнік рашэнняў. Для гэтага накрэсліць межавыя прамыя. З першага няроўнасці запішам раўнанне . Гэта раўнанне першай межавай прамой. Знойдзем кропкі перасячэння гэтай прамой з восямі каардынатаў. пры з раўнання атрымаем , пры атрымаем . Гэта значыць, што першая прамая адсякае ад восяў каардынат адрэзкі і .

Аналагічна будуем астатнія межавыя прамыя. Другая прамая ад восяў каардынат адсякае адрэзкі, роўныя 6. Трэцяя прамая праходзіць паралельна восі , Адсякаючы на ​​восі адрэзак, роўны 2. Чацвёртая прамая мае раўнанне . Яна супадае з воссю .

З малюнка ніжэй відаць, што мноства кропак чатырохкутніка ABDE задавальняе ўсім чатыром няроўнасць сістэмы.

Такім чынам, чатырохкутніка ABDE з'яўляецца шматкутнік рашэнняў сістэмы (заштрыхаваны ўнутр).

Накрэсліць лінію роўных значэнняў функцыі мэты. Прыняўшы ў роўнасці F = 1, атрымаем, што гэтая лінія адсякае адрэзкі 1 і 1/3 адпаведна на восі і на восі . Правядзем прамую праз гэтыя кропкі (на чарцяжы яна чорнага колеру).

Рухаючы гэтую прамую паралельна самой сабе ў напрамку градыенту - вэктару (Бардовага колеру), атрымаем апорныя прамыя. Першая прамая (зялёнага колеру) мае з шматкутнікаў агульную кропку A. Тут функцыя мэты дасягае мінімуму. Рухаючыся далей, прыйдзем да кропкі В. Тут максімум. Каардынаты кропкі Ў: (2, 4). Падстаўляючы ў функцыю мэты каардынаты кропкі У, т. Е. , , Атрымаем максімальнае значэнне функцыі мэты: .

На сайце ёсць Онлайн калькулятар рашэння задач лінейнага праграмавання сімплекс-метадам .

Прыклад 3. Вырашыць графічным метадам задачу лінейнага праграмавання, у якой патрабуецца знайсці максімум функцыі пры абмежаваннях

дзе .

Правільнае рашэнне і адказ .

Прыклад 4. Вырашыць графічным метадам задачу лінейнага праграмавання, у якой патрабуецца знайсці мінімум функцыі пры абмежаваннях

дзе .

Правільнае рашэнне і адказ .

Да гэтага часу атрыманыя высновы былі заснаваныя на тым, што мноства рашэнняў задачы лінейнага праграмавання сканфігуравана так, што аптымальнае рашэнне вядома і адзіна. Зараз разгледзім прыклады, калі гэта ўмова парушаецца. У гэтых прыкладах шматкутнік рашэнняў будуецца так, як паказана ў папярэдніх прыкладах, спынімся ж на прыкметах, якія адрозніваюць гэтыя выключныя прыклады.

Прыклад 5. Вырашыць графічным метадам задачу лінейнага праграмавання, у якой патрабуецца знайсці максімум функцыі пры абмежаваннях

Рашэнне. На малюнку намаляваны: неабмежаваная шматгранная вобласць рашэнняў дадзенай сістэмы абмежаванняў, зыходная лінія ўзроўню (чорнага колеру), вектар (бардовага колеру), які паказвае кірунак руху зыходнай лініі ўзроўню для знаходжання максімуму мэтавай функцыі.

Лёгка заўважыць, што функцыя F можа неабмежавана ўзрастаць пры зададзенай сістэме абмежаванняў, таму можна ўмоўна запісаць, што .

На сайце ёсць Онлайн калькулятар рашэння задач лінейнага праграмавання сімплекс-метадам .

Прыклад 6. Вырашыць графічным метадам задачу лінейнага праграмавання, у якой патрабуецца знайсці максімум функцыі пры абмежаваннях

Рашэнне. Намаляваная на малюнку ніжэй вобласць не ўтрымлівае ні адной агульнай пункту, якая б задавальняла ўсім няроўнасць сістэмы абмежаванняў. Гэта значыць сістэма абмежаванняў супярэчлівая і не можа ўтрымліваць ні аднаго рашэння, у тым ліку і аптымальнага.

На сайце ёсць Онлайн калькулятар рашэння задач лінейнага праграмавання сімплекс-метадам .

На сайце ёсць Онлайн калькулятар рашэння задач лінейнага праграмавання сімплекс-метадам .

Прыклад 8. Вырашыць графічным метадам задачу лінейнага праграмавання, у якой патрабуецца знайсці максімум функцыі пры абмежаваннях

Рашэнне. На малюнку ніжэй намаляваныя вобласць рашэнняў сістэмы абмежаванняў і лінія ўзроўню (чорнага колеру). Калі перарухаць лінію ўзроўню паралельна зыходнай ў кірунку вектара , То яна выйдзе з вобласці рашэнняў не ў адным пункце, як гэта было ў папярэдніх прыкладах, а сальецца з прамой CD, якая з'яўляецца межавай лініяй галіне рашэнняў.

Усе кропкі адрэзка CD даюць адно і тое ж значэнне функцыі мэты, якое і служыць яе аптымальным значэннем: . Такім чынам, маецца не адно, а незлічонае мноства аптымальных рашэнняў, супадальных з кропкамі адрэзка CD, у прыватнасці, з двума вуглавымі кропкамі C і D. Гэты прыклад паказвае, што ў некаторых выпадках адзінасць аптымальнага рашэння парушаецца.

На сайце ёсць Онлайн калькулятар рашэння задач лінейнага праграмавання сімплекс-метадам .

Напрыканцы варта заўважыць, што будаваць шматграннік рашэнняў можна і іншым спосабам, адрозным ад таго, які мы разглядалі. А менавіта: можна не шукаць кропкі перасячэння прамых з восямі каардынатаў, а шукаць кропкі перасячэння прамых. Для гэтага паслядоўна вырашаюцца сістэмы з двух раўнанняў, так, каб рашэннямі былі пункту перасячэння ўсіх прамых. Атрыманыя кропкі і будуць вяршынямі мнагагранніка рашэнняў. Гэты спосаб часам бывае зручным у выпадках, калі кропкі перасячэння прамых з восямі каардынатаў - дробавыя лікі і, няправільна адклаўшы кропку скрыжавання, можна атрымаць памылку і ў пошуку кропак перасячэння саміх прамых.

Пачатак тэмы "Лінейнае праграмаванне"

Падзяліцца з сябрамі