Simplex метода (пример 10)

Проблем ЛП се решава итеративном методом тако што се полази од једног скупа линеарно независних вектора, којим се образује база. После тога се врши промена векторске базе на основу разрађених критеријума, све дотле док се не одреди најповољнији скуп вектора, који у том случају формирају оптималну базу. Simplex метода, којом се ефикасно решава задатак ЛП, заснива су на следећим претпостав-кама: ако се од m линеарно независних вектора , од матрице А, формира база , тада се вектор B изражава путем линеарне комбинације базичних вектора:

(46)                    

Небазични вектор  изражава се, такође, помоћу линеарне комбинације вектора, као:

(47)           

Ако се врши трансформација вектора базе , тако да један од базичних вектора  буде замењен небазичним вектором , мора да се уважи следећи услов, а то је да ако је базични вектор  за , тада мора да буде и да је . Претходни израз (47)   се сада формира као:

(48)                 

Претходна релација (48)  може да се реши по , на основу чега се добија:

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

(49)

Једначину (46):   можемо да напишемо исто на следећи начин:

(50)           или

Ако извршимо елиминацију базичног вектора , добијамо:

(51)                   , или

Дакле, вектор B се може изразити путем линеарне комбинације новог скупа базичних вектора  и вектора . Да би овај скуп образовао базично могуће решење потребно је да чланови у загради буду ненегативни, тј.

(52)                    и

Избор вектора који напушта базу се своди на тзв. “тета” критеријум, што у квантитативном облику износи:

(53)                      за

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

(54)                     

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

за ново (побољшано) базично решење ће тада бити: ,

односно заменом:

(55)  

За већ раније дефинисано: ,  уз означавање да је  вредност функције за вектор , следи да је:

(56)                      

Симплекс критеријум оптималног решења

Добијена релација  показује да се функција критеријума увећава за одређену вредност при промени векторске базе. Ако је небазични вектор , за  и  са најмање једним , тада је . Овај резултат је врло важан јер показује у ком смеру се може повећавати функција критеријума, сукцесивном променом векторске базе. Како је број база коначан, а узастопном итерацијом постижемо , уз непонављање ниједне базе више пута, најбоље решење, тј. највећу функцију циља добијамо у коначном броју итерација. У том смислу можемо поставити први симплекс критеријум за промену векторске базе.

1. Ако је , за један или више небазичних вектора, тада у базу треба увести онај вектор  са најмање једним , за који је пронађено:

(57)                                

2. Ако је , и ако су све вредности , за најмање један небазичан вектор, тада проблем нема коначног решења.

3. Ако је , за све небазичне векторе, решење је оптимално. При томе треба сматрати да је изузет случај дегенерисаног решења.

Критеријум напуштања тренутно егзистирајућег вектора базе одређујемо према већ изведеном критеријуму “тета”. Наиме, треба утврдити вредност:

(58)                            ,  за

Елиминација вектора следи након утврђивања најмањег количника за векторе B и . Ако је за i = u, количник одговарајућег решења најмањи, при чему је  (ненегативна), вектор  треба елиминисати из базе. Када смо постигли оптимално решење  и уколико је за небазични вектор , simplex критеријум , тада се уношењем тог вектора и елиминацијом једног од базичних вектора, постиже још једно оптимално решење, нпр. . Конвексном комбинацијом ових оптималних вектора постижемо ново оптимално решење као:

(59)         ,   где је скалар

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

(60)                      

Пример 10.

Примена simplex методе. За модел проблема ЛП (Примера 6.) потребно је одредити:

F(X)=8,5x₁+9x₂ ® max F(X)

уз ограничења:

2,5 × x₁ + 5,5 × x₂ £ 15
6 × x₁ + 3,5 × x₂ £ 21                 x_j ³ 0 (j = 1,2)

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

2,5 × x₁ + 5,5 × x₂ + x₃ = 15
6 × x₁ + 3,5 × x₂ + x₄ = 21                      x_j ³ 0 (j = 1,2)

и функције критеријума:     F(X)=8,5x₁+9x₂ + 0 × (x₃ + x₄)® max F(X)
Где су: x₃, x₄ допунске (изравнавајуће) променљиве. Претходни систем једначина може се написати у облику:  A×X = B. При томе су:

матрица тзв. техничких коефицијената:    ,

вектор непознатих вредности  ,  вектор ограничења  и вектор коефицијената функције критеријума C=[8,5, 9, 0, 0]. Вектори колона матрице А могу се изразити као:

                        ,  ,  и

тај начин се матрична једначина A×X = B може еквивалентно формулисати путем векторске једначине:

A^<1>×x₁ + A^<2>×x₂ + A^<3>×x₃ + A^<4>×x₄ = B

За усвојене почетне вредности реалних променљивих: x₁ = 0, x₂ = 0 можемо формулисати прво базичну једначину као:

A^<1>×0 + A^<2>×0 + A^<3>×15 + A^<4>×21 = B,

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

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

Дакле, почетну базу чине вектори:  Ab=[ A^<3>, A^<4>]. Небазни вектори A^<1>, A^<2> могу се изразити посредством базних, као:

са елементима: x₁₁ = 0, x₂₁ = 0, x₃₁ = 2,5 и x₄₁ = 6 и

са елементима:  x₁₂ = 0, x₂₂ = 0, x₃₂ = 5,5 и x₄₂ = 3,5.

Примена критеријума за улазак новог вектора у базу своди се на експлицитно одређивање најмање негативне вредности (F_j – c_j) небазних вектора. У том смислу, имамо следеће вредности:

            за вектор A^<1>:    F₁ – c₁ = (8,5×0 + 9×0 + 0×2,5 + 0×6) – 8,5 = – 8,5
            за вектор A^<2>:    F₂ – c₂ = (8,5×0 + 9×0 + 0×5,5 + 0×3,5) – 9 = – 9

Како је: min {(F₁ – c₁), (F₂ – c₂)}= F₂ – c₂ = – 9,  следи да у базу улази вектор A^<2>. Критеријум за излазак једног базног вектора A^<j> своди се на одређивање најмањег односа вредности тј. min {x_i/x_ij}, за изабрани улазни вектор.

Најмања вредност је:      и у том случају вектор A^<3> излази из базе. Формирање нове базе Ab’ се своди на измену изабраног вектора, што се симболички може представити као:

Претходни вектор A^<3> се може извести из израза (63), тако да добијамо:

(65)                  

Уврштавањем овог израза у изразе (62) и (64), респективно добијамо (66) и (67), с напоменом да се сви децимални бројеви у наредним итерацијама представљају у облику разломка, због прецизнијег приказа и могућности да корисник сам провери резултат:

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

Примена критеријума min (F_j – c_j) за улазак небазног вектора у базу.

Како је: min {(F₁ – c₁), (F₃ – c₃)}= F₁ – c₁ = – 97/22, следи да у базу улази вектор A^<1>. Критеријум за излазак једног базног вектора A^<i> своди се на одређивање најмањег односа вредности тј.  min {x_i/x_ij}, за изабрани улазни вектор. Најмања вредност је:  

и у том случају вектор A^<4> излази из базе. Формирање нове базе Ab² се може представити симболички изменом вектора:

Вектор A^<4> се може извести из израза (66), тако да добијамо:

(68)                   

Заменом вектора A^<4>  у (65) и (67), следе вектори:

(69)                  
(70)                  

показује да је нађено оптимално решење јер су све вредности F_j – c_j ³ 0, што је основни услов критеријума најбољег решења. Вектор оптималног решења на основу резултата

(70)  је сада:

При томе је функција критеријума максимална и износи:

,

Формирање simplex табеле

Simplex табелирање представља ефикасан начин да се слично претходним алгебарским релацијама на специфичан матрични (табеларан) начин структурирају сви елементи функција постављеног модела ЛП. Итеративним прорачунавањем трансформисани елементи тих функција (ограничења и циља), такође, се представљају у наредним simplex табелама, све док се не постигне оптимално решење. Основа сукцесивног прорачуна, на овај начин, еквивалентна је раније показаним матричним поступцима прорачунавања. Наиме, за формирани simplex модел проблема ЛП, нпр. типа максимума, из система једначина:

може се поставити (нулта)  simplex табела, у ознаци max ST-0 (Т-4). Део ознаке ST-0 симболички представља почетно решење, где је функција критеријума једнака нули, док се синтаксом маџ изражава карактер проблема који се решава.

  max ST-0                                                                                                                    (Т-4)

Поред тога остали симболи у  simplex табели имају следеће значење:

(73) 

Уз претпоставку да су допунске променљиве x_k+i (i = 1,... m) базичне променљиве, тада су остале променљиве једнаке x_j = 0 (j = 1,... k). У том смислу смо формирали прво базично могуће решење као:

(74)                , , ..... , , ..... ,

Функција критеријума при овој бази једнака је нули (аналогно са F(X) = 0 код почетног решења при примени графичке методе). Разлог томе је што су коефицијенти у функцији критеријума за ту базу једнаки нули, јер они физички не постоје. Измена базе иде у смеру увођења небазног вектора X_j (j = 1,..., k) (који узима адекватне позитивне вредности). У том смислу добијамо следећи израз:

                                   

За i-ту једначину, као што је познато у општем моделу ЛП могу се јавити случајеви да је a_ij{<, =, >} 0. Најинтересантнији резултат за анализу је случај када је a_ij > 0. Тада се може изабрати x_j, тако да једна од променљивих x_k+i постане једнака нули. Дакле, за:

(76)           x_k+i ³ 0  следи да је: b_i – a_ij × x_j ³ 0,  па је x_j £ b_i/a_ij  за a_ij > 0.

Претходна релација представља основу за формулисање критеријума елиминације једне базичне променљиве X_i (постављајући је као вектор). Наиме, да би услов x_j £ b_i/a_ij (a_ij > 0) био задовољен, потребно је између свих m количника пронаћи минималну вредност. Тај однос ће се обележити као и раније са “тета” и дат је у виду релације:

(77)             ,   (a_ij > 0)

Одабрану вредност индексирајмо са i = u, а затим  u-ти ред проглашавамо водећим редом (Т-5). Овај критеријум за излазак вектора из базе познат је, како је раније истакнуто, као први simplex критеријум. Други simplex критеријум за избор новог вектора X_j, који приступа бази, замењујући променљиву X_i, заснован је на одабиру најмање вредности (F_j – c_j) из скупа негативних:

(78)            ,   за вредности  F_j – c_j < 0 (j = 1,..., k)

Одабрана вредност ће бити обележена са (F_p – c_p), односно индекс одабране колоне са j = p. Очигледно да се исти резултат постиже на основу еквивалентне релације: . Може се закључити да се уз већу вредност c_j и актуализацијом одговарајућег вектора X_j у бази јавља нови ефекат који резултира, обично, повећању функције критеријума.

      max ST-0                                                                                                                   (Т-5)

Проширени критеријум, за избор вектора који приступа бази, примењује се у оним случајевима када се појављује већи број вредности F_j – c_j < 0 једнаких или блиских по величини. Његова примена може убрзати поступак налажења оптималног решења кроз смањење броја потребних итерација. Међутим, у једноставнијим моделима ЛП не јавља се такав ефекат, који се огледа у брзини конвергенције ка оптималном решењу, па проширени критеријум није потребно примењивати, већ се задржати само на основном. Напоменимо да се у фази испитивања q вредности не узимају у обзир негативне вредности односа q= b_i/a_ij, проузроковане негативношћу вредности a_ji. Поред тога, може се десити да количник b_i/a_ij буде исти по вредности за две или више “тета” вредности у анализираној колони. У том случају долази у питање примена првог simplex критеријума, јер није једнозначно утврђено који вектор напушта базу Аb. Овај случај познат је као случај дегенерисаног решења јер постоји више кандидата - базичних вектора за излазак из базе.

Итеративни прорачун елемената simplex табеле

Поступно, прорачунавање коефицијената унетих у табелу своди се на трансформацију сваког појединачног елемента матрице бројева [M] = [M]_{(m+1)´(k+m+1)} датих према (Т-6).

                                                                                                                                      (Т-6)

Приметимо да ова матрица садржи (m+1)´(k+m+1) елемената и потребно их је трансформисати при свакој новој итерацији. Овај поступак се реализује све дотле док се не постигне оптимално решење. Наредна simplex табела (Т-8) у односу на претходну (Т-7) садржи трансформисане вредности елемената матрице. Наиме, нове вредности рачунају се по одређеним правилима. Та правила су већ презентована у методама векторског прорачуна, док ће се овде изнети довољно упрошћено, за елементе текуће и наредне матрице.

          ST - текућа                   (Т-7)                          ST - наредна                  (Т-8)

Трансформација елемената ван водећег реда и ван водеће колоне (i ¹ u; j ¹ p) изводи се као:

(79)                  

Трансформација елемената у водећој колони, изузимајући водећи елемент (i ¹ u).

(80)                   

 

Трансформација елемената у водећем реду (i = u)

(81)                   

Трансформација водећег елемента (i = u; j = p)

(82)