Віды задач лінейнага праграмавання

Лінейнае праграмаванне - метад рашэння задач аптымізацыі.

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

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

Функцыя мэты ў задачы лінейнага праграмавання звычайна запісваецца так:

.

Або ў скарочаным выглядзе з Сігма:

.

Можна сустрэць абазначэнне мэтавай функцыі і праз C, і праз F.

Сістэма абмежаванняў ў задачы лінейнага праграмавання ў кананічнай форме запісваецца так:

.

Або ў скарочаным выглядзе:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Прыклад 1. Схема задачы выкарыстання сыравіны.

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

Для вырабу двух відаў прадукцыі і патрабуецца чатыры віды рэсурсаў (сыравіны): , , , . Запасы сыравіны - адпаведна , , , адзінкі.

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

Рашэнне. Для зручнасці спачатку ўсе дадзеныя запішам у выглядзе табліцы:

Тады на падставе табліцы запішуцца няроўнасці (абмежавання):

На самай справе, для вырабу кожнай адзінкі прадукцыі неабходна адзінак сыравіны , А для вырабу адзінак патрабуецца адзінак сыравіны . для вырабу адзінак прадукцыі патрабуецца адзінак сыравіны . Бо запасы сыравіны складаюць , То расход не можа перавышаць . У выніку атрымаем першае няроўнасць:

З астатніх радкоў табліцы складзем яшчэ 3 няроўнасці сістэмы.

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

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

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

Прыклад 2. Схема задачы аб сумесях.

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

Патрабуецца знайсці найбольш танны набор з даступных зыходных матэрыялаў, якія забяспечваюць атрыманне сумесі з зададзенымі ўласцівасцямі. Атрыманыя сумесі павінны мець на свойму складзе n розных кампанент у пэўных колькасцях, а самі кампаненты з'яўляюцца складовымі часткамі m зыходных матэрыялаў. Для спрашчэння прымем, што n = 3 і m = 4. Хай кошт адной адзінкі матэрыялу адпаведна складае , , , . У сваю чаргу неабходную колькасць кожнай з кампанент у сумесі складае адпаведна , , .

Рашэнне. Будуем табліцу:

Каэфіцыенты паказваюць колькасць j -й кампаненты ў адзінцы i -га матэрыялу. Патрабуецца атрымаць сумесь з зададзенымі ўласцівасцямі пры найменшых выдатках на набыццё матэрыялаў.

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

пры абмежаваннях

Адным з прыватных выпадкаў агульнай задачы аб сумесях служыць задача аб харчаванні. Да яе зараз жа і пяройдзем.

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

Прыклад 3. Схема задачы аб харчаванні.

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

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

Рашэнне. Будуем табліцу:

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

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

Атрымаем сістэму няроўнасцей (абмежаванняў):

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

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

Прыклад 4. Схема задачы аб выкарыстанні магутнасцяў абсталявання.

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

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

Магутнасць машын зададзена наступнай табліцай:

У гэтай табліцы - колькасць адзінак прадукцыі, якое вырабляецца за адзінку часу.

Кошт адной адзінкі працоўнага часу на выраб адной адзінкі прадукцыі на кожнай машыне зададзена наступнай табліцай:

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

Запішам задачу ў выглядзе матэматычных суадносін. Невядомым з'яўляецца час загрузкі машын па вытворчасці прадукцыі. абазначым праз час загрузкі машыны па вырабе прадукцыі, праз - час загрузкі машыны па вырабе прадукцыі. аналагічна - час загрузкі машыны па вырабе прадукцыі, - час загрузкі машыны па вырабе прадукцыі, - час загрузкі машыны па вырабе прадукцыі, час загрузкі машыны па вырабе прадукцыі.

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

Машына вырабам прадукцыі занятая адзінкі часу на адзінкі прадукцыі. Машына вырабам занятая адзінкі часу па адзінкі прадукцыі.

Аналагічна машына вырабам занятая адзінкі часу, па адзінкі прадукцыі і г.д. Усяго трэба адзінак прадукцыі і адзінкі.

Гэта значыць атрымліваем яшчэ адну сістэму:

Тады агульны кошт усёй прадукцыі запішацца ў выглядзе роўнасці:

.

Канчаткова атрымліваем сістэму абмежаванняў, якая складаецца з суадносін:

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

Прыклад 5. Транспартная задача (схема).

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

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

Скласці такі план перавозак, каб агульны кошт усіх перавозак была мінімальнай.

Рашэнне. Лічым, што запас усяго грузу на абодвух пунктах адпраўлення роўны патрэбы ў гэтым грузе на ўсіх трох пунктах прызначэння, т. Е.

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

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

Тады сістэма абмежаванняў запішацца ў выглядзе раўнанняў:

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

На сайце ёсць артыкул, прысвечаны вырашэнню транспартнай задачы размеркавальным метадам .

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

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

Прыклад 6. Запісаць сістэму няроўнасцей

ў выглядзе раўнанняў для прывядзення задачы лінейнага праграмавання да кананічнай.

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

Такім чынам, як бы ні былі першапачаткова зададзены абмежаванні задачы лінейнага праграмавання, іх заўсёды можна прывесці да сістэмы раўнанняў, выкарыстоўваючы для гэтай мэты дадатковыя зменныя.

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

На нашым сайце таксама дадзены прыклады рашэння задач лінейнага праграмавання графічным метадам без ведама задачы да кананічнай і сімплекс-метадам з папярэдніх звядзеннем задачы да кананічнай .

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

Тэарэма 1. Мноства ўсіх дапушчальных рашэнняў сістэмы абмежаванняў задачы лінейнага праграмавання з'яўляецца выпуклым.

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

Пра тое, што такое выпуклыя мноства - на ўроку Сістэмы лінейных няроўнасцей і выпуклыя мноства кропак .

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

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

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

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

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

Справядлівасць гэтага сцвярджэння выцякае з тэарэм 2 і 4.

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

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

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