Рашэнне аптымізацыйных задач кіравання метадам лінейнага праграмавання
Раней я апісаў, як прымаць рашэнні з улікам абмяжоўваюць фактараў . Мэта такіх рашэнняў - вызначыць асартымент прадукцыі (вытворчы план), максімальна які павялічвае прыбытак кампаніі. Рашэнне заключалася ў тым, каб размеркаваць рэсурсы паміж прадуктамі згодна маржынальнасць прыбытку, атрыманага на адзінку абмежаваных рэсурсаў, пры захаванні любых іншых абмежаванняў, такіх як максімальны ці мінімальны попыт на асобныя віды прадукцыі. [1]
Калі які абмяжоўвае фактар адзін (напрыклад, дэфіцытны станок), рашэнне можа быць знойдзена з прымяненнем простых формул (гл. Спасылку ў пачатку артыкула). Калі ж з абмежаваннямі фактараў некалькі, ужываецца метад лінейнага праграмавання.
Лінейнае праграмаванне - гэта назва, дадзенае камбінацыі інструментаў, які выкарыстоўваецца ў навуцы аб кіраванні. Гэты метад вырашае праблему размеркавання абмежаваных рэсурсаў паміж канкуруючымі відамі дзейнасці з тым, каб максымізаваць або мінімізаваць некаторыя лікавыя велічыні, такія як маржынальнасць прыбытак або выдаткі. У бізнэсе ён можа выкарыстоўвацца ў такіх галінах як планаванне вытворчасці для максімальнага павелічэння прыбытку, падбор камплектуючых для мінімізацыі выдаткаў, выбар партфеля інвестыцый для максімізацыі даходнасці, аптымізацыя перавозак тавараў у мэтах скарачэння адлегласцяў, размеркаванне персаналу з мэтай максімальна павялічыць эфектыўнасць працы і складанне графіка работ у мэтах эканоміі часу.
Спампаваць нататку ў фармаце Word , Малюнкі ў фармаце Excel
Лінейнае праграмаванне прадугледжвае пабудову матэматычнай мадэлі разгляданай задачы. Пасля чаго рашэнне можа быць знойдзена графічна (разгледжана ніжэй), з выкарыстаннем Excel (будзе разгледжана асобна) або спецыялізаваных кампутарных праграм. [2]
Мабыць, пабудова матэматычнай мадэлі - найбольш складаная частка лінейнага праграмавання, якая патрабуе перакладу разгляданай задачы ў сістэму пераменных велічынь, раўнанняў і няроўнасцей - працэс, у канчатковым выніку які залежыць ад навыкаў, вопыту, здольнасцяў і інтуіцыі складальніка мадэлі.
Разгледзім прыклад пабудовы матэматычнай мадэлі лінейнага праграмавання
Мікалай Кузняцоў кіруе невялікім механічным заводам. У будучыні месяцы ён плануе вырабляць два прадукту (А і У), па якіх ўдзельная маржынальнасць прыбытак ацэньваецца ў 2500 і 3500 руб., Адпаведна.
Выраб абодвух прадуктаў патрабуе выдаткаў на машынную апрацоўку, сыравіну і праца (мал. 1). На выраб кожнай адзінкі прадукту А адводзіцца 3 гадзіны машыннай апрацоўкі, 16 адзінак сыравіны і 6 адзінак працы. Адпаведныя патрабаванні да адзінкі прадукту У складаюць 10, 4 і 6. Мікалай прагназуе, што ў наступным месяцы ён можа даць 330 гадзін машыннай апрацоўкі, 400 адзінак сыравіны і 240 адзінак працы. Тэхналогія вытворчага працэсу такая, што не менш за 12 адзінак прадукту У неабходна вырабляць у кожны канкрэтны месяц.
Мал. 1. Выкарыстанне і прадастаўленне рэсурсаў
Мікалай хоча пабудаваць мадэль з тым, каб вызначыць колькасць адзінак прадуктаў А і В, якія ён дакладзены вырабляць у наступным месяцы для максімізацыі маржынальнасць прыбытку.
Лінейная мадэль можа быць пабудаваная ў чатыры этапы.
Этап 1. Вызначэнне пераменных
Існуе мэтавая пераменная (пазначым яе Z), якую неабходна аптымізаваць, то ёсць максымізаваць або мінімізаваць (напрыклад, прыбытак, выручка або выдаткі). Мікалай імкнецца максымізаваць маржынальнасць прыбытак, такім чынам, мэтавая пераменная:
Z = сумарная маржынальнасць прыбытак (у рублях), атрыманая ў наступным месяцы ў выніку вытворчасці прадуктаў А і В.
Існуе шэраг невядомых шуканых зменных (пазначым іх х1, х2, х3 і інш.), Чые значэння неабходна вызначыць для атрымання аптымальнай велічыні мэтавай функцыі, якая, у нашым выпадку з'яўляецца сумарнай маржынальнасць прыбыткам. Гэтая маржынальнасць прыбытак залежыць ад колькасці вырабленых прадуктаў А і В. Значэнні гэтых велічынь неабходна разлічыць, і таму яны ўяўляюць сабой шуканыя зменныя ў мадэлі. Такім чынам, пазначым:
х1 = колькасць адзінак прадукту А, вырабленых у наступным месяцы.
х2 = колькасць адзінак прадукту У, вырабленых у наступным месяцы.
Вельмі важна дакладна вызначыць усе зменныя велічыні; асаблівую ўвагу надасце адзінкам вымярэння і перыяду часу, да якога адносяцца зменныя.
Этап. 2. Пабудова мэтавай функцыі
Мэтавая функцыя - гэта лінейнае раўнанне, якое павінна быць або максымізаваць або мінімізавана. Ён ўтрымлівае мэтавую зменную, выяўленую з дапамогай шуканых зменных, то ёсць Z выяўленую праз х1, х2 ... у выглядзе лінейнага ўраўненні.
У нашым прыкладзе кожны выраблены прадукт А прыносіць 2500 руб. маржынальнасць прыбытку, а пры вырабе х1 адзінак прадукту А, маржынальнасць прыбытак складзе 2500 * х1. Аналагічна маржынальнасць прыбытак ад вырабу х2 адзінак прадукту У складзе 3500 * х2. Такім чынам, сумарная маржынальнасць прыбытак, атрыманая ў наступным месяцы за кошт вытворчасці х1 адзінак прадукту А і х2 адзінак прадукту У, гэта значыць, мэтавая пераменная Z складзе:
Z = 2500 * х1 + 3500 * х2
Мікалай імкнецца максымізаваць гэты паказчык. Такім чынам, мэтавая функцыя ў нашай мадэлі:
Максымізаваць Z = 2500 * х1 + 3500 * х2
Этап. 3. Вызначэнне абмежаванняў
Абмежаванні - гэта сістэма лінейных раўнанняў і / або няроўнасцей, якія абмяжоўваюць велічыні шуканых зменных. Яны матэматычна адлюстроўваюць даступнасць рэсурсаў, тэхналагічныя фактары, умовы маркетынгу і іншыя патрабаванні. Абмежаванні могуць быць трох відаў: «менш або роўна", "больш або роўна», «строга роўна».
У нашым прыкладзе для вытворчасці прадуктаў А і В неабходны час машыннай апрацоўкі, сыравіну і праца, і даступнасць гэтых рэсурсаў абмежаваная. Аб'ёмы вытворчасці гэтых двух прадуктаў (гэта значыць значэння х1 их2) будуць, такім чынам, абмежаваныя тым, што колькасць рэсурсаў, неабходных у вытворчым працэсе, не можа перавышаць наяўных месцаў. Разгледзім сітуацыю з часам машыннай апрацоўкі. Выраб кожнай адзінкі прадукту А патрабуе трох гадзін машыннай апрацоўкі, і калі выраблена х1, адзінак, то будзе выдаткавана З * х1, гадзін гэтага рэсурсу. Выраб кожнай адзінкі прадукту У патрабуе 10 гадзін і, такім чынам, калі выраблена х2 прадуктаў, то спатрэбіцца 10 * х2 гадзін. Такім чынам, агульны аб'ём машыннага часу, неабходнага для вытворчасці х1 адзінак прадукту А і х2 адзінак прадукту У, складае 3 * х1 + 10 * х2. Гэта агульнае значэнне машыннага часу не можа перавышаць 330 гадзін. Матэматычна гэта запісваецца наступным чынам:
3 * х1 + 10 * х2 ≤ 330
Аналагічныя меркаванні прымяняюцца да сыравіны і працы, што дазваляе запісаць яшчэ два абмежаванні:
16 * х1 + 4 * х2 ≤ 400
6 * х1 + 6 * х2 ≤ 240
Нарэшце варта адзначыць, што існуе ўмова, згодна з якім павінна быць выраблена не менш за 12 адзінак прадукту У:
х2 ≥ 12
Этап 4. Запіс умоў неадмоўнага
Шуканыя зменныя не могуць быць адмоўнымі лікамі, што неабходна запісаць у выглядзе няроўнасцей х1 ≥ 0 і х2 ≥ 0. У нашым прыкладзе другое ўмовы з'яўляецца залішнім, так як вышэй было вызначана, што х2 не можа быць менш 12.
Поўная мадэль лінейнага праграмавання для вытворчай задачы Мікалая можа быць запісана ў выглядзе:
Максымізаваць: Z = 2500 * х1 + 3500 * х2
Пры ўмове, што: 3 * х1 + 10 * х2 ≤ 330
16 * х1 + 4 * х2 ≤ 400
6 * х1 + 6 * х2 ≤ 240
х2 ≥ 12
х1 ≥ 0
Разгледзім графічны метад рашэння задачы лінейнага праграмавання.
Гэты метад падыходзіць толькі для задач з двума пазовам зменнымі. Мадэль, пабудаваная вышэй, будзе выкарыстаная для дэманстрацыі метаду.
Восі на графіцы ўяўляюць сабой дзве шуканыя зменныя (мал. 2). Не мае значэння, якую зменную адкласці ўздоўж, якой восі. Важна выбраць маштаб, які ў канчатковым выніку дазволіць пабудаваць наглядную дыяграму. Паколькі абедзве зменныя павінны быць неадмоўнага, малюецца толькі I-й квадрант.
Мал. 2. Восі графіка лінейнага праграмавання
Разгледзім, напрыклад, першае абмежаванне: 3 * х1 + 10 * х2 ≤ 330. Гэта няроўнасць апісвае вобласць, якая ляжыць ніжэй прамы: 3 * х1 + 10 * х2 = 330. Гэтая прамая перасякае вось х1 пры значэнні х2 = 0, то ёсць раўнанне выглядае так: 3 * х1 + 10 * 0 = 330, а яго рашэнне: х1 = 330/3 = 110
Аналагічна вылічаем пункту перасячэння з восямі х1 і х2 для ўсіх умоў-абмежаванняў:
Вобласць дапушчальных значэнняў Мяжа дапушчальных значэнняў Скрыжаванне з воссю х1 Скрыжаванне з воссю х2 3 * х1 + 10 * х2 ≤ 330 3 * х1 + 10 * х2 = 330 х1 = 110; х2 = 0 х1 = 0; х2 = 33 16 * х1 + 4 * х2 ≤ 400 16 * х1 + 4 * х2 = 400 х1 = 25; х2 = 0 х1 = 0; х2 = 100 6 * х1 + 6 * х2 ≤ 240 6 * х1 + 6 * х2 = 240 х1 = 40; х2 = 0 х1 = 0; х2 = 40 х2 ≥ 12 х2 = 12 ня перасякае; ідзе паралельна восі х1 х1 = 0; х2 = 12
Графічна першае абмежаванне адлюстравана на мал. 3.
Мал. 3. Пабудова вобласці дапушчальных рашэнняў для першага абмежаванні
Любая кропка ў межах выдзеленага трыкутніка або на яго межах будзе адпавядаць гэтаму абмежаванню. Такія кропкі называюцца дапушчальнымі, а кропкі за межамі трыкутніка называюцца недапушчальнымі.
Аналагічна адлюстроўваем на графіцы астатнія абмежаванні (мал. 4). Значэння х1 і х2 на або ўнутры заштрыхаванай вобласці ABCDE будуць адпавядаць усім абмежаванням мадэлі. Такая вобласць называецца вобласцю дапушчальных рашэнняў.
Мал. 4. Галiна дапушчальных рашэнняў для мадэлі ў цэлым
Цяпер у вобласці дапушчальных рашэнняў неабходна вызначыць значэнні х1 і х2, якія максімізуе Z. Для гэтага ў раўнанні мэтавай функцыі:
Z = 2500 * х1 + 3500 * х2
падзелім (або памножым) каэфіцыенты перад х1 і х2 на адно і тое ж лік, так каб атрымаліся значэння патрапілі ў дыяпазон, адбіваны на графіцы; у нашым выпадку такі дыяпазон - ад 0 да 120; таму каэфіцыенты можна падзяліць на 100 (ці 50):
Z = 25х1 + 35х2
затым прысвоім Z значэнне роўнае твору каэфіцыентаў перад х1 і х2 (25 * 35 = 875):
875 = 25х1 + 35х2
і, нарэшце, знойдзем кропкі скрыжавання прамой з восямі х1 і х2:
Раўнанне мэтавай функцыі Скрыжаванне з воссю х1 Скрыжаванне з воссю х2 875 = 25х1 + 35х2 х1 = 35; х2 = 0 х1 = 0; х2 = 25
Вырабім гэта мэтавае раўнанне на графік аналагічна абмежаванняў (мал. 5):
Мал. 5. Нанясенне мэтавай функцыі (чорная пункцірнай лінія) на вобласць дапушчальных рашэнняў
Значэнне Z пастаянна на ўсім працягу лініі мэтавай функцыі. Каб знайсці значэння х1 і х2, якія максімізуе Z, трэба паралельна пераносіць лінію мэтавай функцыі да такой кропцы ў межах вобласці дапушчальных рашэнняў, якая размешчана на максімальным выдаленні ад зыходнай лініі мэтавай функцыі уверх і направа, то ёсць да кропкі С (мал. 6) .
Мал. 6. Лінія мэтавай функцыі дасягнула максімуму ў межах вобласці дапушчальных рашэнняў (у кропцы С)
Можна зрабіць выснову, што аптымальнае рашэнне будзе знаходзіцца ў адной з крайніх кропак вобласці прыняцця рашэння. У якой менавіта, будзе залежаць ад кута нахілу мэтавай функцыі і ад таго, якую задачу мы вырашаем: максімізацыі або мінімізацыі. Такім чынам, не абавязкова чарціць мэтавую функцыю - усё, што неабходна, гэта вызначыць значэнні х1 і х2 ў кожнай з крайніх кропак шляхам счытвання з дыяграмы або шляхам вырашэння адпаведнай пары раўнанняў. Знойдзеныя значэння х1 і х2 затым падстаўляюцца ў мэтавую функцыю для разліку адпаведнай велічыні Z. Аптымальным рашэннем з'яўляецца тое, пры якім атрымана максімальная велічыня Z пры рашэнні задачы максімізацыі, і мінімальная - пры рашэнні задачы мінімізацыі.
Вызначым, напрыклад значэння х1 і х2 ў кропцы С. Заўважым, што кропка З знаходзіцца на скрыжаванні ліній: 3х1 + 10х2 = 330 і 6х1 + 6х2 = 240. Рашэнне гэтай сістэмы раўнанняў дае: х1 = 10, х2 = 30. Вынікі разліку для усіх вяршыняў вобласці дапушчальных рашэнняў прыведзены ў табліцы:
Кропка Значэнне х1 Значэнне х2 Z = 2500х1 + 3500х2 А 22 12 97 000 У 20 20 120 000 З 10 30 130 000 D 0 33 115 500 E 0 12 за 42 000
Такім чынам, Мікалай Кузняцоў павінен запланаваць на наступны месяц вытворчасць 10 вырабаў А і 30 вырабаў У, што дазволіць яму атрымаць маржынальнасць прыбытак у памеры 130 тыс. Руб.
Коратка сутнасць графічнага метаду рашэння задач лінейнага праграмавання можна выкласці наступным чынам:
- Накрэсліце на графіцы дзве восі, якія, па сутнасці два параметры рашэння; намалюйце толькі I-й квадрант.
- Вызначыце каардынаты кропак перасячэння ўсіх межавых умоў з восямі, падстаўляючы ў ўраўненні межавых умоў па чарзе значэння х1 = 0 і х2 = 0.
- Нанесці лініі абмежаванняў мадэлі на графік.
- Вызначыце на графіцы вобласць (званую дапушчальнай вобласцю прыняцця рашэння), якая адпавядае ўсім абмежаванням. Калі такая вобласць адсутнічае, значыць, мадэль не мае рашэння.
- Вызначыце значэння шуканых зменных у крайніх кропках вобласці прыняцця рашэння, і ў кожным выпадку разлічыце адпаведнае значэнне мэтавай зменнай Z.
- Для задач максімізацыі рашэнне - кропка, у якой Z максімальна, для задач мінімізацыі, рашэнне - кропка, у якой Z мінімальна.
[1] Сапраўдная нататка напісана па матэрыялах CIMA .
[2] Гл., Напрыклад, тут .
