Графичка метода и примери 1, 2, 3, 4, 5 и 6

Решавање проблема линеарног програмирања графичком методом састоји се у испитивању низа вредности функције критеријума у екстремним тачкама области допустивих решења. Примена ове методе ограничена је на задатке са две или, у ређем случају, са три непознате променљиве величине. У једнодимензионалном простору (n = 1)примена графичке методе је тривијална. Испитивање односа две непознате величине [x₁, x₂], које се могу представити вектором X, врши се дотле док се не постигне вредност оптималног вектора X^*. Дакле:

Међутим, тзв. оптимално, односно најбоље решење односа компонената x₁ и x₂, пронађено у датим условима, представља само последицу која произилази из претходно пронађене екстремне вредности функције критеријума. У том смислу, поступци графичке методе своде се прво на: моделирање линеарних ограничења облика:

или у развијеној форми:

и функције критеријума за нпр. проблем максимума: max F(X) = c₁ x₁ + c₂ x₂. Свако ограничење типа (20)  представља по једну полураван у равни x₁ 0 x₂ чија је граница представљена правом облика:

(21)       a_i1 x₁ + a_i2 x₂ = b_i

Пресеком полуравни (20) одређен је конвексан (конкаван) полигон могућих решења, а тиме и област функције циља. Ако желимо да добијемо њен максимум (Сл. 4-6), испитивање екстремне вредности функције циља релативно је једноставно, и своди се на проналажење најудаљеније тачке на конвексном полигону. Геометријска интерпретација графичке методе се састоји у дефинисању полигона на основу система ограничења којим се формира област допустивих решења D. Поред тога, за познате вредности коефицијената у функцији критеријума c₁ и c₂, који се могу изразити путем вектора c = [c₁, c₂], и изједначавањем функције F(X) са нулом, постиже се најједноставнији положај праве линије у почетним фазама решавања модела ЛП. Одлуком да се функција критеријума изједначује са нулом, тј.

(22)        F(X) = c₁ x₁ + c₂ x₂ = 0 

не прави се грешка у почетној фази налажења решења, јер се постиже ненегативно решење, што је у складу са важећим ограничењима. Затим следи њено сукцесивно повећање, све до екстремног положаја, а које је означено као логички најмања или највећа вредност. Тачке у којима функција F(X) = c₁ x₁ + c₂ x₂ има константну вредност леже на правој која је паралелна почетној правој F(X) = 0 и представља тзв. линију нивоа (Сл. 5) за функцију:

(23)        F(X) = c₁ x₁ + c₂ x₂

Тако нпр., координате најближе екстремне тачке области D (нпр. Сл. 4) представ-љају компоненте оптималног вектора X^* за који функција циља има минимум, тј.

(24)        min F(X) = F(X) = c₁ x^*₁ + c₂ x^*₂                  

                         Сл. 4                                                         Сл. 5

                                          Сл. 6                                                         Сл. 7

                                          Сл. 8                                                         Сл. 9

Са методолошког становишта решавање проблема ЛП графичком методом погодно је због једноставности поступака методе и зато се обрађује у почетним фазама изучавања метода и модела ЛП. Са едукативног становишта код графичке методе смо у могућности да брзо препознамо у Еуклидовом линеарном простору релације између функције критеријума F(X), система линеарних ограничења типа a_i1 x₁ + a_i2 x₂ {<, =, >} b_i, и услова ненегативности у математичком моделу. Графички део поступка се обично комбинује са аналитичким, па се ова метода примењује у случају захтева за повећаном прецизности резултата ЛП. У тродимензионалном простору (n = 3) теже се примењује графичка метода, тј. метода се примењује уз помоћ поступака нацртне геометрије. У n-димензионалном простору за (n > 3) остају само геометријски термини, иначе се линеарни програми решавају алгебарским методама, без могућности базирања на геометријску очигледност.

Пример 1.

За потребе тржишта производе се два типа производа P₁ и P₂ на два технолошка система ТS₁ и ТS₂. Временски капацитет ТS₁ расположив је за коришћење до 600 /час/, а за ТS₂ до 700 /час/. Обрада производа P₁ на ТS₁ траје 72 /мин/ком/, а на ТS₂ 60 /мин/ком/. Производ P₂ се финализује, такође, кроз две операције, и то на ТS₁ операционо време је 60 /мин/ком/, а на ТS₂ 105 /мин/ком/. Пласман на тржишту није неограничен. Испитивањем је установљено да тржиште може примити до 450 /ком/ производа P₁ и до 300 /ком/ производа P₂. Такође су познате јединичне цене производа (у новчаним јединицама по комаду) и оне износе: за први производ c₁ = 9 /нј/ком/, а за други c₂ = 7,5 /нј/ком/. Потребно је:

1. Одредити оптималан план производње да би се постигао максимални ефекат добити.

2. Одредити која функција ограничења не утиче на максималну вредност функције критеријума.

Решење:

Математички модел проблема обликован је на основу система ограничења:

и функције критеријума (добити):    

  Сл. 10 График области допустивог решења са функцијом критеријума D(X)

1. Како права D(X) = 9 x₁ + 7.5 x₂ = 4500 /нј/ лежи на ограничавајућој прави полуравни (1) решење садржи бесконачан скуп оптималних вектора решења. Крајње тачке оптималне дужи су тачке B и C. У тим тачкама оптималне количине производа су (Сл. 10):

 /ком/  и друго решење:  /ком/.

Вредности функције критеријума у обема тачкама су исте и износе:

 /нј/  и  /нј/.

Опште решење оптимума може се дефинисати као линеарна комбинација пронађених вектора: X = d X_B + (1 – d) X_C где је скалар: 0 £ d £ 1.

Нпр. за произвољну вредност d = 0,34 добијамо треће оптимално решење као:

 /ком/.

Функција добити и за тај случај, као и за прва два, остаје непромењена, тј:

/нј/.

2. На основу графика области допустивог решења и функције критеријума (Сл. 10) се види да ограничење (4), при постојећим условима, не утиче на формирање максималне вредности критеријумске функције и вектор(е) оптималних решења.

НАПОМЕНА

Пример 2.

Наћи минималну вредност функције критеријума F (X) = 6 x₁ + 3 x₂ ® min F (X), користећи графичку методу ЛП, уз следећа ограничења:

Поред тога одредити:

1. Оптимално решење датог проблема и минималну вредност функције критеријума.

2. Оптимално решење и максималну вредност функције критеријума при измени (1) неједначине функције ограничења, која се сада дефинише као једначина облика: x₁ + x₂ = 5.

3. Параметре a₁ и a₂ уз променљиве x₁ и x₂ првог ограничења облика a₁ x₁ + a₂ x₂ = 5 (уместо неједначине (1)), да би таква промена изазвала бесконачан број оптималних решења. Прокоментарисати вредност функције критеријума.

Решење:

1. Оптимално решење се добија на основу транслације функције критеријум од координатног почетка до тачке B (Сл. 11), са одговарајућим вредностима:

Сл. 11  Графичка интерпретација ЛП примера 2.а)

При томе минимална вредност функције критеријума износи min F (X) = F (X^*) = 22,5

2. У случају да се у систем ограничења уведе једначина x₁ + x₂ = 5, сва базно допустива решења се налазе на дужи АB. У тим условима су екстремне вредности једнаке:

  и 

Оптимално решење при измењеним условима ограничења и карактер функције критеријума се налази у тачки А,  тј. X_A =X^*, јер је одговарајућа функција критеријума највећа управо у тој тачки и износи:

max F (X) = max{F (X_A), F (X_B)}= max{27, 22,5}= 27.

Сл. 12  Графичка интерпретација ЛП примера 2.б)

3. Параметри уз променљиве x₁ и x₂ прве функције ограничења су одредиви на основу коефицијента правца критеријумске функције. Из једначине: 6x₁+3x₂ = 0 Þ x₂ = – 2 x₁ он износи -2. Према томе, исти угао нагиба у односу на x₁ осу мора имати и нова права ограничења: a₁ x₁ + a₂ x₂ = 5, на основу чега следи:

,  уз услов:  ,

где за тачку B: x₁ = x₂ = 2,5 следи да је:  a₂ = 2/3, и a₁ = 4/3.

На основу претходног, прва једначина ограничења сада гласи: , што се може графички интерпретирати (Сл. 13).

Сл. 13  Графичка интерпретација ЛП примера 2.ц)

Оптимална решења се налазе и у тачки B и у тачки C. Међутим, број оптималних решења је бесконачан и налази се на дужи BC, тако да сада добијамо за екстремне вредности вектора следеће: 

  и 

Како су и сва друга решења која се налазе на дужи BC такође оптимална, то се у векторском облику за произвољну тачку G, може уопштено написати да је:

Где за вредности:  d ® 0, X_G ® X_C,  и за  d ® 1, X_G ® X_B.

При тим променама се не мења вредност функције критеријума и она износи:

min F (X) = F (X_A) = F (X_C) = F (X_G) = 22,5.

Пример 3.

Коришћењем графичке методе решити проблем линеарног програмира-ња, ако је дата функција добити D (X) = 3x₁ + x₂, и систем ограничења:

Поред тога поступцима анализе:

1. одредити вредности x₁ и x₂ за које функција добити D (X) постиже максималну вредност, а да су истовремено задовољена сва претходна ограничења,

2. дефинисати један аналитички израз нове функције D (X) да би се у новим условима добило бесконачно много оптималних решења,

3. дати за ту функцију два примера оптималних решења.

Решење:

1. Одређивање оптималног решења и максималне добити. Оптимално решење се налази у тачки B (Сл. 14), у пресеку правих које ограничавају област (p2) и (p5).

Највећа добит је у том случају одређена као:  /нј/ 

Сл. 14 Графичка интерпретација ЛП примера 3.а)

2. Тражени аналитички израз следи из резултата изједначавања коефицијента правца нове праве D (X) = c₁ x₁ + c₂ x₂ = 167,5 /нј/ и праве која ограничава област (p5) тј. 8x₁ + 6x₂ = 480. Дати поступак се своди на трансформацију израза (p5), у смислу његовог изједначавања са израчунатом вредношћу функције критеријума:

,  те добијамо:    /нј/.

Према томе, тражена функција критеријума (Сл. 15) је облика:

Сл. 15 Графичка интерпретација ЛП примера 3.б)

3. Један пример оптималног решења, као што је већ констатовано, се налази у тачки B. Други пример следи из резултата пресека праве (p4) и (p5) у тачки C, па имамо:

; 

Вредност функције добити за обе тачке остаје максимална и непромењена. Дакле:

max D (X) = D (X_B) = 2,792 x₁^* + 2,094 x₂^* = 167,5 /нј/

max D (X) = D (X_C) = 2,792 x₁^** + 2,094 x₂^** = 167,5 /нј/

Пример 4.

За задату функцију критеријума (трошкова) Т(X) = 3/2 x₁ – 1/2 x₂ и скуп ограничења:

1. одредити оптимално решење и минималну вредност функције критеријума,

2. одредити вредности коефицијента у функцији критеријума тако да нађени  трошкови у тачки (под а)) износе T (X) = 0  /нј/,

3. одредити оптимално решење и минималне трошкове ако коефицијент уз x₂, функције трошкова, промени смер, тј. постане позитиван. Колике су разлике у трошковима тиме изазване у односу на решење добијено под а).

Решење:

1. Најбоље решење налази се у тачки Е (Сл. 16) и износи:

при томе су минимални трошкови:   /нј/

Сл. 16  Графички приказ модела ЛП примера 4.

2. Функција трошкова може бити једнака нули у случају да пролази кроз координатни почетак и да тангира одабрану екстремну тачку, у овом случају тачку Е (Сл. 17). При томе је коефицијенат правца тангентне праве одређен из односа:

Једно од могућих решења јединичних цена је: c₁ = 341 и c₂ = 162, па је тада тражена вредност функције трошкова:

Т(X*) = 341 x₁^* – 162 x₂^* = 0 /нј/.

Сл. 17  Графички приказ модела ЛП примера 4.б)

3. Из услова промене предзнака уз коефицијент променљиве x₂ нова функција критеријума добија облик:

Конкретна вредност ове функције, за тачку Е (Сл. 18), износи:

 /нј/.

Сл. 19  Графички приказ модела ЛП примера 4.ц)

За функцију K(X) добијамо исту тачку оптимума (Е), као и за критеријум T(X), али се трошкови при томе повећавају за вредност:

 /нј/.

Пример 5.

Производњу два производа Р₁ и Р₂ потребно је реализовати на три машине М₁, М₂ и М₃. Временски нормативи t_ij израде производа на овим машинама /мин/ком/, расположиви временски капацитети машина у /час/ и предвиђена јединична добит од продаје /нј/ком/, дати су у следећој табели (Т-2).

(Т-2)

Поред тога продаја производа на тржишту је ограничена, и то за производ Р₁ пласман је могућ до највише 55 комада, а за производ Р₂ ограничење је до 65 ком.

1. Извршити анализу плана производње да би се постигло највеће искоришћење временског капацитета свих машина.

2. У циљу максимизације добити одредити оптималан план производње.

Решење:

1. Формирање математичког модела проблема мора бити у складу са датим параметрима производње, продаје и променљивим величинама за Р₁ (x₁) и за Р₂ (x₂). Поред тога мора се водити рачуна о усклађености временских мерних јединица. За решавање задатка, усвојени су часови (односно /час/ком/) као основне терминске јединице. У том смислу имамо следећи систем ограничења:

Коефицијенти у функцији критеријума добијају се на основу збира времена израде појединачних производа, узимајући у обзир да је време сваке операције на појединим машинама дато у /час/ком/, уместо у /мин/ком/ као у (Т-2). Из тог разлога следи да су нормативи времена за израду производа P₁, односно P₂, респективно:

t₁ = 7,5 + 7 + 4,5 /час/ком/ и t₂ = 7,5 + 13 + 1,5 = 22 /час/ком/.

Функција искоришћености капацитета је тада облика: max K(X) = 19 x₁ + 22 x₂

Са овако дефинисаним ограничењима и функцијом циља (капацитета) оптимално решење се налази, применом геометријске методе, у тачки D (Сл. 19) са вредностима:

 /ком/.

Сл. 19  Графичка интерпретација проблема временског капацитета

Очигледно временски капацитет треће машине није у потпуности искоришћен, и у апсолутном износу та вредност параметара износи: D₃ = 270 – 185 = 85 /час/

Укупан степен искоришћења капацитета за све три машине израчунава се као однос стварног и теоријског капацитета машина, и у овом случају је:

   тј.  95,2%

Дакле, није искоришћено укупно: D = D₃ = 1780 – 1695 = 85 /час/. 

Искоришћеност капацитета добија се сабирањем стварно попуњених капацитета (у апсолутном износу h = 1780 – D = 1695 /час/), или на основу функције критеријума, као:

max K(X^*) = 19 x₁^* + 22 x₂^* = 1695 /час/.

Добит при максималном искоришћењу временског капацитета последично износи:

2. Код изналажења највеће добити од продаје производа Р₁ и Р₂ функција критеријума има одговарајућу форму профита. На основу полазних параметара (Т-2) се формира као:

max D(X) = 45 x₁ + 36 x₂

Ограничења остају истоветна, као што су раније дефинисана. На бази таквог математичког модела може се графички решити и интерпретирати проблем ЛП за овај случај, као:

Сл. 20 Графичка интерпретација проблема добити

Оптимално решење се налази у тачки C и износи:

 /ком/.

За ове оптималне вредности функција добити је максимална (Сл. 20) са износом од:

max D(X^**) = 45 x₁^** + 36 x₂^** = 3330 /нј/,

док је искоришћеност временског капацитета сада секундаран циљ и он последично износи:

K(X^**) = 19 x₁^** + 22 x₂^** = 1610 /час/

Временски капацитет друге машине није у потпуности искоришћен, и у апсолутном износу тај параметар је сада: D₂ = 910 – 740 = 170 /час/. Укупан степен искоришћења свих машина износи:

тј. 90,4%

Очигледно да се овде добијају резултати супротних тенденција, који се огледају у два случаја:

Пример 6.

Нека фабрика производи два артикла А₁ и А₂ на машинама М₁ и М₂. На изради јединице артикла А₁ машина М₁ утроши 2,5 часа, а машина М₂ 6 часова. На изради артикла А₂ машина М₁ утроши 5,5 часова, а машина М₂ 3,5 часа. Машина М₁ може највише да ради 15 часова дневно, а машина М₂ највише 21 час дневно. Ови подаци се могу прегледно дати следећом табелом (Т-3).

(Т-3)

Испитати графичком методом колику количину артикала А₁ и артикала А₂ треба дневно произвести да би се максимално искористио укупан капацитет машина. Колика оптимална количина производа износи за 97 радних дана?

Решење:

За производњу јединице артикла А₁ укупно се утроши 8,5 /час/ком/, а за произ-водњу јединице артикла А₂, 9 /час/ком/, па је функција степена искоришћења капацитета облика K(X) = 8,5 x₁ + 9x₂ ® max K(X)

Констатујмо да се за израду x₁ (јединице артикла А₁) и x₂ (јединица артикла А₂), машина М₁ експлоатише: 2,5 x₁ + 5,5 x₂ часова, са могућношћу рада до 15 часова, а машина М₂ експлоатише: 6x₁ + 3,5 x₂ часова, са могућношћу рада до 21 часа дневно. При томе, дакле, морају бити задовољена следећа ограничења,

2,5 x₁ + 5,5 x₂ £ 15  или 

6x₁ + 3,5 x₂ £ 21  или

уз природне услове ненегативности који подразумевају да је: x₁ ³ 0,  x₂ ³ 0. На основу геометријске интерпретације (Сл. 21) види се да је област D одређена системом ограничења са четвороуглом OABC, где су тачке са координатама: О(0,0), А(7/2, 0), B(252/97, 150/97) и C(0, 30/11).

Сл. 21 Графичка интерпретација модела ЛП примера 6.

Ако праву K(X)=0, транслирамо паралелно ка најудаљенијој тачки конвексног полигона, достићи ћемо гранични положај критеријумске функције која се налази у тачки B. При томе је оптимални вектор решења:

 /ком/.

У тој тачки K(X) има максималну вредност, јер је померање вршено у правцу повећања вредности функције расположивог капацитета. Зато је:

max K(X) = 8,5 x₁^* + 9x₂^* = 36 /час/.

Укупни капацитет, као што се види из иницијалне табеле (Т-3) и постигнутог резултата, у потпуности је испуњен. Значи максимална искоришћеност машина биће, само у случају, ако се дневно буде производило 252/97»2,6 јединице артикла А₁ и »1,54 јединица артикла А₂. За временски период од t = 97 /дана/, оптимална произведена количина артикала ће износити: