11.4. DUAL SIMPLEX METODAS
Iš ankstesnių skyrių rezultatų matyti, kad norint gauti pirminės problemos sprendimą, galime pereiti prie dvejopos ir, naudodamiesi jo optimalaus dizaino įverčiais, nustatyti optimalų pradinės problemos sprendimą.
Perėjimas prie dvejopos problemos nėra būtinas, nes jei nagrinėsime pirmąją simplekso lentelę su vienetiniu papildomu pagrindu, tada nesunku pastebėti, kad stulpeliuose yra pirminė užduotis, o dviguba užduotis parašyta eilutėse.
Kaip buvo parodyta, sprendžiant tiesioginę problemą bet kuria iteracija, skirtumas, t.y. dydžio -koeficientas su kintamuoju, yra lygus skirtumui tarp atitinkamo dvigubo uždavinio apribojimo dešinės ir kairės pusės. Jei sprendžiant tiesioginę problemą su maksimalia tikslo funkcija, iteracija nesukelia optimalaus sprendimo, tai bent vienam kintamajam ir tik optimaliai visiems skirtumas.
Atsižvelgdami į šią sąlygą ir į dvilypumą, galime rašyti
.
Taigi, jei, tada. Tai reiškia, kad kai pirminės problemos sprendimas nėra optimalus, dvigubos problemos sprendimas yra negaliojantis. Iš kitos pusės 
adresu . Tai reiškia, kad optimalus pirminės problemos sprendimas atitinka leistiną dvigubos problemos sprendimą.
Tai leido sukurti naują linijinio programavimo problemų sprendimo metodą, kuris pirmiausia duoda nepriimtiną, bet „geresnį nei optimalų“ sprendimą (įprastu simplekso metodu pirmiausia randame priimtinas, bet neoptimalus sprendimas). Naujas metodas vadinamas dvigubas simplekso metodas, užtikrina sprendinio optimalumo sąlygos įvykdymą ir jos sistemingą „priartinimą“ į galimų sprendimų sritį. Kai gautas sprendimas yra priimtinas, iteracinis skaičiavimų procesas baigiasi, nes šis sprendimas taip pat yra optimalus.
Dvigubas simplekso metodas leidžia spręsti tiesinio programavimo uždavinius, kurių apribojimų sistemose, turinčios teigiamą pagrindą, yra laisvi bet kokio ženklo terminai. Šis metodas leidžia sumažinti suvaržymų sistemos transformacijų skaičių ir vienareikšmės lentelės dydį. Apsvarstykite dvigubo simplekso metodo taikymą naudodami pavyzdį.
Pavyzdys. Raskite funkcijos minimumą 
pagal apribojimus
.
Pereikime prie kanoninės formos:
pagal apribojimus
Pradinė simpleksinė lentelė turi formą
|
Pagrindinis kintamieji |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
Sprendimas |
|
x 3 x 4 x 5 |
–3 –4 |
–1 –3 |
–3 –6 |
|||
|
–2 |
–1 |
Pradinis pagrindinis sprendimasoptimalus, bet nepriimtinas.
Kaip ir įprastas simplekso metodas, nagrinėjamas sprendimo metodas yra pagrįstas priimtinumo ir optimalumo sąlygų taikymu.
Priimtinumo sąlyga. Išskirtuoju kintamuoju pasirenkamas didžiausias absoliučia reikšme neigiamas pagrindinis kintamasis (jei yra alternatyvų, pasirenkama savavališkai). Jei visi pagrindiniai kintamieji yra neneigiami, skaičiavimo procesas baigiasi, nes gautas sprendimas yra įmanomas ir optimalus.
Būklė optimalumas. Į pagrindą įtrauktas kintamasis parenkamas iš nepagrindinių kintamųjų taip. Apskaičiuojami kairiosios pusės koeficientų santykiai-lygtys su atitinkamais lygties, susijusios su neįtrauktu kintamuoju, koeficientais. Neatsižvelgiama į ryšius su teigiamais arba nuliniais vardikliais. Įvesties kintamojo minimizavimo uždavinyje turi atitikti mažiausias iš nurodytų koeficientų, o maksimizavimo uždavinyje santykis su mažiausia absoliučia reikšme (jei yra alternatyvų, pasirenkama savavališkai). Jei visų koeficientų vardikliai yra nuliniai arba teigiami, problema neturi įmanomų sprendimų.
Pasirinkus į bazę įtrauktinus ir neįtraukiamus kintamuosius, norint gauti kitą sprendinį, atliekama įprasta simpleksinės lentelės eilučių transformavimo operacija.
Šiame pavyzdyje neįtrauktas kintamasis yra. Santykiai, apskaičiuoti siekiant nustatyti naują bazinį kintamąjį, pateikti šioje lentelėje:
|
Kintamieji |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
Lygtis x 4 - lygtis |
–2 –4 |
–1 –3 |
|||
|
Požiūris |
Įtrauktinas kintamasis yra x 2. Vėlesnė eilutės konversija sukuria naują simplekso lentelę:
|
Pagrindinis kintamieji |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
Sprendimas |
|
x 3 x 2 x 5 |
–1 –1 |
|||||
Naujas sprendimas taip pat optimalus, bet vis tiek negalioja. Kaip naują neįtrauktą kintamąjį pasirenkame (savavališkai) x 3 . Apibrėžkime įtrauktą kintamąjį.
|
Kintamieji |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
Lygtis x 4 - lygtis |
|||||
|
požiūris |
Paprastas metodas - tai nuoseklaus perėjimo nuo vieno linijinio programavimo uždavinio apribojimų sistemos pagrindinio sprendinio (sprendinio daugiakampio viršūnės) prie kito pagrindinio sprendimo būdas, kol tikslo funkcija įgauna optimalią reikšmę (maksimali arba mažiausia).
Paprastasis metodas yra universalus metodas, galintis išspręsti bet kurį linijinio programavimo problema, o grafinis metodas tinka tik dviejų kintamųjų apribojimų sistemai.
Simpleksinį metodą pasiūlė amerikiečių matematikas R. Dantzigas 1947 m., nuo tada pramonės poreikiams šis metodas dažnai sprendžia linijinio programavimo problemas su tūkstančiais kintamųjų ir apribojimų.
Prieš pereinant prie simpleksinio metodo algoritmo, keli apibrėžimai.
Vadinamas bet koks neneigiamas apribojimų sistemos sprendimas priimtinas sprendimas .
Tegul būna sistema m apribojimai nuo n kintamieji ( m n).
Priimtinas pagrindinis sprendimas yra tirpalas, kurio sudėtyje yra m neneigiamas majoras (pagrindinis ) kintamieji ir n - m nepagrindinis . (nepagrindinis arba Laisvas ) kintamieji. Nebaziniai kintamieji pagrindiniame sprendime yra lygūs nuliui, o pagrindiniai kintamieji, kaip taisyklė, yra ne nulis, tai yra, jie yra teigiami skaičiai.
Bet koks m sistemos kintamieji m tiesines lygtis su n kintamieji vadinami pagrindinis , jei koeficientų determinantas prie jų skiriasi nuo nulio. Tada likusieji n - m kintamieji vadinami nepagrindinis (arba Laisvas ).
Simpleksinio metodo algoritmas
- 1 žingsnis. Perkelkite linijinio programavimo problemą į kanoninę formą. Norėdami tai padaryti, perkelkite laisvuosius terminus į dešinę pusę (jei tarp šių laisvųjų terminų yra neigiami, tada padauginkite atitinkamą lygtį arba nelygybę iš -1) ir į kiekvieną apribojimą įtraukite papildomus kintamuosius (su pliuso ženklu, jei pradinė nelygybė ženklas yra mažesnis arba lygus ", o su minuso ženklu, jei "didesnis arba lygus").
- 2 žingsnis. Jei susidariusioje sistemoje m tada lygtys m kintamuosius imti kaip pagrindinius, pagrindinius kintamuosius išreikšti nepagrindiniais ir rasti atitinkamą pagrindinį sprendimą. Jei rastas pagrindinis sprendimas yra priimtinas, pereikite prie leistino pagrindinio sprendimo.
- 3 veiksmas. Tikslo funkciją išreikškite įmanomo pagrindinio sprendimo nedideliais kintamaisiais. Jei rastas tiesinės formos maksimumas (minimalus) ir jos išraiškoje nėra nebazinių kintamųjų su neigiamais (teigiamais) koeficientais, tai optimalumo kriterijus tenkinamas ir gautas bazinis sprendimas yra optimalus – sprendimas baigtas. Jei, randant tiesinės formos maksimumą (minimumą), jos išraiškoje yra vienas ar keli nepagrindiniai kintamieji su neigiamais (teigiamais) koeficientais, pereikite prie naujo pagrindinio sprendimo.
- 4 veiksmas. Iš nebazinių kintamųjų, įtrauktų į tiesinę formą su neigiamais (teigiamais) koeficientais, pasirinkite tą, kuris atitinka didžiausią (modulio) koeficientą, ir perkelkite į pagrindinius. Eikite į 2 veiksmą.
Svarbios sąlygos
Kai kurie ypatingi atvejai aptariami atskiruose straipsniuose: kada maksimali tikslinė funkcija – begalybė, kada sistema neturi sprendimo, ir kada optimalus sprendimas nėra vienintelis .
Toliau analizuosime tipinį pavyzdį, kai apribojimų sistema yra nuosekli ir yra baigtinis optimalus, ir tik vienas. Simpleksinio metodo variantas yra paskirstymo būdas transporto problemai išspręsti .
Simplex metodas su simpleksinėmis lentelėmis
Konstruojant simpleksines lenteles daug lengviau išspręsti tiesinio programavimo uždavinį nei naudojant algebrines transformacijas, kurios parodytos kitoje pastraipoje. Paprastos lentelės yra labai vizualios. Yra keletas taisyklių, susijusių su darbu su simplex lentelėmis. Išanalizuosime taisyklę, kuri dažniausiai vadinama pirmaujančio stulpelio ir pirmaujančios eilutės taisykle.
Būtų naudinga naujame lange atidaryti vadovą Veiksmai su trupmenomis: jų užtenka, švelniai tariant, simplekso metodo uždaviniuose trupmenos.
Pavyzdys.
Pristatome papildomus neneigiamus kintamuosius ir sumažiname šią nelygybių sistemą iki lygiavertės lygčių sistemos
.
Tai buvo padaryta laikantis šios taisyklės: jei pradinio apribojimo ženklas yra "mažesnis arba lygus", tada reikia pridėti papildomą kintamąjį, o jei "didesnis arba lygus", tada papildomas kintamasis turi būti atimta.
Įvesti papildomi kintamieji laikomi pagrindiniais (pagrindiniais). Tada ir yra nebaziniai (laisvi) kintamieji.
Išreikšdami pagrindinius (pagrindinius) kintamuosius nepagrindiniais (laisvaisiais), gauname
Tikslo funkciją taip pat išreiškiame ne pagrindiniais (laisvais) kintamaisiais:
Iš kintamųjų (nežinomų) koeficientų sudarome pirmąją simplekso lentelę.
| 1 lentelė | ||||
| Pagrindiniai nežinomieji | Nemokami nariai | Nežinomieji | Pagalbiniai koeficientai | |
| X1 | X2 | |||
| X3 | -2 | 1 | -2 | |
| X4 | -4 | -1 | -1 | |
| X5 | 2 | 1 | -1 | |
| X6 | 6 | 0 | 1 | |
| F | 0 | -1 | -2 | |
Paskutinė lentelės eilutė, kurioje yra tikslo funkcija ir joje esančių laisvųjų kintamųjų koeficientai, bus vadinama indekso eilute.
Gautas sprendimas nėra optimalus, nes indekso eilutės laisvųjų kintamųjų koeficientai yra neigiami. Tai yra, optimalus sprendimas bus tas, kuriame indekso eilutės laisvųjų kintamųjų koeficientai bus didesni arba lygūs nuliui.
Norėdami pereiti prie kitos lentelės, raskite didžiausią (modulo) skaičių ir . Šis skaičius yra 2. Todėl pirmaujanti stulpelis yra stulpelis, kuriame jis parašytas
Norėdami nustatyti pirmaujančią eilutę, randame laisvųjų narių ir pirmaujančios stulpelio elementų santykio minimumą, o jei skaitiklis turi teigiamą skaičių, o vardiklis neigiamas, santykis laikomas lygiu begalybei.
.
Todėl pirmaujanti eilutė yra ta, kurioje ji parašyta
Taigi pagrindinis elementas yra -2.
Sudarome antrąją simplekso lentelę.
Pirmoje eilutėje įvedame naują pagrindinį elementą, o stulpelį, kuriame jis buvo, įvedame naują nemokamą kintamąjį
Užpildykite pirmąją eilutę. Norėdami tai padaryti, padalijame visus 1 lentelės priekinėje eilutėje esančius skaičius iš pirmaujančio elemento ir įrašome jį į atitinkamą pirmosios lentelės 2 eilutės stulpelį, išskyrus skaičių priekiniame stulpelyje, kur pirminio elemento atvirkštinė vertė parašytas elementas (ty vienas padalintas iš pagrindinio elemento).
Užpildykite pagalbinių koeficientų stulpelį. Šiam 1 lentelės priekinio stulpelio skaičiui, be pagrindinio elemento, 2 lentelės pagalbinių koeficientų stulpelyje rašome priešingus ženklus.
| 2 lentelė | ||||
| Pagrindiniai nežinomieji | Nemokami nariai | Nežinomieji | Pagalbiniai koeficientai | |
| X1 | X3 | |||
| X2 | 1 | -1/2 | -1/2 | |
| X4 | -3 | -3/2 | -1/2 | 1 |
| X5 | 3 | 1/2 | -1/2 | 1 |
| X6 | 5 | 1/2 | 1/2 | -1 |
| F | 2 | -2 | -1 | 2 |
Kas dar neatidarė rankinio Veiksmų su trupmenomis naujame lange, gali tai padaryti dabar, nes laikas.
Norint gauti likusias 2 lentelės eilutes, pirmoje šios lentelės eilutėje esantys skaičiai dauginami iš pagalbinio koeficiento pildomoje eilutėje ir prie rezultato pridedame skaičių iš 1 lentelės, kuri yra toje pačioje eilutėje su atitinkamą kintamąjį.
Pavyzdžiui, norėdami gauti laisvąjį antros eilutės narį, skaičių 1 padauginame iš 1 ir pridedame skaičių -4 iš 1 lentelės. Gauname -3. Antroje eilutėje randame koeficientą tokiu pačiu būdu: 
. Kadangi ankstesnėje lentelėje nėra stulpelio su nauju laisvu kintamuoju, naujojo laisvojo kintamojo stulpelio antros eilutės koeficientas bus 
(tai yra, iš 1 lentelės pridedame 0, nes 1 lentelėje nėra c stulpelio).
Rodyklės eilutė užpildoma taip pat:
Taip gautas sprendimas vėlgi nėra optimalus, nes laisvųjų kintamųjų koeficientai indekso eilutėje vėl yra neigiami.
Norėdami pereiti prie kitos simpleksinės lentelės, suraskime indekso eilutėje didžiausią skaičių (modulį) ir , tai yra, koeficientų modulius. Šis skaičius yra 2. Todėl pirmaujantis stulpelis yra stulpelis, kuriame yra .
Norėdami ieškoti pirmaujančios eilutės, suraskime minimalų laisvųjų narių ir pirmaujančios eilutės elementų santykį. Mes gauname:
.
Todėl pirmaujanti eilutė yra ta, kurioje parašyta, o pagrindinis elementas yra -3/2.
Trečiosios simpleksinės lentelės sudarymas
Pirmoje eilutėje rašome naują pagrindinį kintamąjį. Stulpelyje, kuriame jis buvo, įvedame naują nemokamą kintamąjį .
Pirma eilė:
Pagalbiniai koeficientai:
| 3 lentelė | ||||
| Pagrindiniai nežinomieji | Nemokami nariai | Nežinomieji | Pagalbiniai koeficientai | |
| X4 | X3 | |||
| X1 | 2 | -2/3 | 1/3 | |
| X2 | 2 | -1/3 | -1/3 | 1/2 |
| X5 | 2 | 1/3 | -2/3 | -1/2 |
| X6 | 4 | 1/3 | 1/3 | -1/2 |
| F | 6 | -4/3 | -1/3 | 2 |
Gautas sprendimas vėlgi nėra optimalus, nes laisvųjų nežinomųjų koeficientai indekso eilutėje vėl yra neigiami.
Norėdami pereiti prie ketvirtosios simpleksinės lentelės, suraskime didžiausią skaičių ir . Tai yra skaičius.
Todėl pirmaujanti stulpelis yra tas, kuriame yra .
Minimalus laisvųjų narių ryšių su pirmaujančios stulpelio elementais modulis:
.
Todėl pirmaujanti eilutė yra ta, kurioje parašyta, o pagrindinis elementas yra 1/3.
Ketvirtoje simpleksinėje lentelėje pirmoje eilutėje įrašome naują pagrindinį kintamąjį. Stulpelyje, kuriame jis buvo, rašome naują nemokamą kintamąjį .
Pirma eilė:
Pagalbiniai koeficientai:
| 4 lentelė | ||||
| Pagrindiniai nežinomieji | Nemokami nariai | Nežinomieji | Pagalbiniai koeficientai | |
| X5 | X3 | |||
| X4 | 6 | 3 | -2 | |
| X1 | 6 | 2 | -1 | 2/3 |
| X2 | 4 | 1 | -1 | 1/3 |
| X6 | 2 | -1 | 1 | -1/3 |
| F | 14 | 4 | -3 | 4/3 |
Likusių eilučių apskaičiavimas naudojant antros eilutės pavyzdį:
Gautas sprendimas taip pat nėra optimalus, bet jau geresnis už ankstesnius, nes vienas iš laisvųjų kintamųjų koeficientų indekso eilutėje yra neneigiamas.
Norėdami pagerinti planą, pereikime prie kitos simpleksinės lentelės.
Raskite didžiausią skaičių 4 ir . Šis skaičius yra 4. Todėl pirmaujanti stulpelis yra .
Norėdami rasti pirmaujančią eilutę, raskite
.
Todėl pirmaujanti eilutė yra ta, kurioje yra . Bet jie jau buvo kartu tarp laisvųjų kintamųjų. Todėl norėdami perkelti kitą kintamąjį iš laisvo į pagrindinį, pasirenkame kitą pagrindinį stulpelį - tą, kuriame parašyta.
Norėdami rasti pirmaujančią eilutę, raskite
.
Todėl pagrindinė eilutė yra ta, kurioje parašyta, o pagrindinis elementas yra 1.
Penktoje simpleksinėje lentelėje naujas pagrindinis kintamasis rašomas pirmoje eilutėje. Stulpelyje, kuriame jis buvo, rašome naują nemokamą kintamąjį .
Pirma eilė:
Pagalbiniai koeficientai:
| 5 lentelė | ||||
| Pagrindiniai nežinomieji | Nemokami nariai | Nežinomieji | Pagalbiniai koeficientai | |
| X5 | X6 | |||
| X3 | 2 | -1 | 1 | |
| X4 | 10 | 2 | ||
| X1 | 8 | 1 | ||
| X2 | 6 | 1 | ||
| F | 20 | 1 | 3 | 3 |
Pabandykime iš karto išsiaiškinti, ar sprendimas nėra optimalus. Todėl likusioms eilutėms skaičiuojame tik laisvuosius terminus (norėdami sužinoti pagrindinių kintamųjų reikšmes, kai laisvieji kintamieji lygūs nuliui) ir indekso eilutės laisvųjų kintamųjų koeficientus.
Nemokami nariai:
Antroje eilutėje;
Trečioje eilutėje;
Ketvirtoje eilutėje.
Indekso eilutė:
Žiūrime į simpleksinę lentelę 5. Matome, kad gautas optimalus sprendimas, kadangi indekso eilutėje laisvųjų nežinomųjų koeficientai yra neneigiami.
Paprastasis metodas su algebrinėmis transformacijomis
Išspręskime algebrinėmis transformacijomis tą patį pavyzdį, kaip ir ankstesnėje pastraipoje. Pažymėtina, kad sprendžiant tokio tipo simplekso metodą tikslo funkcijos formoje geriau nerašyti , nes ženkluose lengva susipainioti. Bet šiuo atveju algoritmo taškas, nustatantis optimalumo kriterijų, bus pakeistas taip.
Jei rastas tiesinės formos maksimumas (minimalus) ir jos išraiškoje nėra nebazinių kintamųjų su teigiamais (neigiamais) koeficientais, tai optimalumo kriterijus tenkinamas ir gautas bazinis sprendimas yra optimalus – sprendimas baigtas. Jei, randant tiesinės formos maksimumą (minimumą), jos išraiškoje yra vienas ar daugiau nepagrindinių kintamųjų su teigiamais (neigiamais) koeficientais, pereikite prie naujo pagrindinio sprendimo.
Pavyzdys. Raskite funkcijos maksimumą pagal apribojimus
I žingsnis. Įvedame papildomų neneigiamų kintamųjų ir šią nelygybių sistemą sumažiname iki ekvivalentinės lygčių sistemos
.
Įvesti papildomi kintamieji laikomi pagrindiniais, nes tokiu atveju nesunkiai randamas pagrindinis sistemos sprendimas. Tada ir yra nedideli kintamieji.
Išreikšdami pagrindinius kintamuosius nepagrindiniais, gauname
Vadinasi, toks kintamųjų skirstymas į pagrindinius ir nepagrindinius atitinka pagrindinį sprendimą 
, kuris yra neteisingas (du kintamieji yra neigiami), todėl nėra optimalus. Nuo šio pagrindinio sprendimo pereikime prie patobulinto.
Norėdami nuspręsti, kuris kintamasis turėtų būti konvertuojamas iš nepagrindinio į pagrindinį, apsvarstykite vieną iš dviejų galimų paskutinės sistemos lygčių su neigiamais laisvaisiais terminais, pavyzdžiui, antrąją. Tai rodo, kad ir gali būti verčiami į pagrindinius kintamuosius, nes šioje lygtyje jie turi teigiamus koeficientus (todėl jiems padidėjus, o tai atsitiks, jei kurį nors iš jų paverstume pagrindiniais kintamaisiais, kintamasis padidės).
Pabandykime išversti į pagrindinį kintamąjį . Norėdami nustatyti, kuris kintamasis turėtų būti perkeltas iš pagrindinio į nepagrindinį, randame mažiausio laisvųjų sistemos narių santykio su koeficientais absoliučią reikšmę. Mes turime . Jis gaunamas iš trečiosios lygties, kuri parodo, kad kintamasis turi būti konvertuojamas į nepagrindinius, o tai yra teigiama pirminiame pagrindiniame sprendime. Vadinasi, gautame baziniame sprendime, kaip ir pirminiame, yra du neigiami komponentai, t.y., perėjimas prie tokio pagrindinio sprendimo nepagerės.
Paprastas metodas− tai orientacinių planų užsakyto surašymo būdas (tvarką užtikrina monotoniškas tikslo funkcijos vertės pokytis pereinant prie kito plano). Šiuo atveju būtina laikytis principo: kiekvienas kitas žingsnis turi pagerinti arba, kraštutiniais atvejais, nepabloginti tikslo funkcijos vertės.
Norėdami išspręsti LLP simplekso metodas ji redukuojama į kanoninę formą, t.y. iš apribojimų – nelygybių reikia daryti apribojimus – lygybes. Norėdami tai padaryti, kiekvienas apribojimas papildomas papildomu neneigiamu balanso kintamasis su „+“ ženklu, jei nelygybės ženklas yra „£“, ir su „–“ ženklu, jei nelygybės ženklas yra „³“.
Tikslinėje funkcijoje šie papildomi kintamieji įvedami su nuliniais koeficientais, t.y. tikslinės funkcijos įrašas nepasikeis. Kiekvienas kintamasis, kuriam netaikoma neneigiamumo sąlyga, gali būti pavaizduotas kaip dviejų neneigiamų kintamųjų skirtumas: .
Jei užduoties apribojimai atspindi išteklių buvimą ir suvartojimą, tai papildomo kintamojo skaitinė reikšmė užduoties plane, įrašyta kanonine forma, yra lygi nepanaudoto resurso kiekiui.
Norėdami išspręsti problemą simplekso metodu, naudosime sutrumpintos tiesinių lygčių sistemos simpleksinės lentelės ir modifikuotas Jordano eliminacijos metodas.
1. Sudarome pirmąjį pagrindinį planą
Užduotis išlieka ta pati. Įveskime standartinę nelygybių sistemos formą (1) į kanoninę lygčių sistemos formą, įvesdami papildomus balanso kintamuosius x 3 , x 4 , x 5 ,x 6 .
Ekonomine prasme papildomų kintamųjų reikšmės x 3 , x 4 , x 5 nustatyti žaliavų likutį pardavus produkciją.
Gautos lygčių sistemos matrica yra tokia:
Tai matyti matricoje A 4 eilės bazinis minoras yra determinantas, sudarytas iš papildomų kintamųjų vienetų koeficientų x 3 , x 4 , x 5 ,x 6 , nes jis yra ne nulis ir lygus 1. Tai reiškia, kad šių kintamųjų stulpelių vektoriai yra tiesiškai nepriklausomi, t.y. forma pagrindu, ir atitinkamus kintamuosius x 3 , x 4 , x 5 ,x 6 yra pagrindinis(pagrindinis). Kintamieji x 1 , x 2 bus iškviestas Laisvas(nepilnametis).
Jei laisvi kintamieji x 1 ir x 2, norėdami nustatyti skirtingas reikšmes, tada, išspręsdami sistemą pagrindinių kintamųjų atžvilgiu, gauname begalinį konkrečių sprendimų rinkinį. Jei laisviesiems kintamiesiems nustatomos tik nulinės reikšmės, tada iš begalinio konkrečių sprendimų rinkinio, pagrindiniai sprendimai- pagrindiniai planai.
Norint išsiaiškinti, ar kintamieji gali būti pagrindiniai, reikia apskaičiuoti determinantą, susidedantį iš šių kintamųjų koeficientų. Jei šis determinantas nėra lygus nuliui, šie kintamieji gali būti pagrindiniai.
Pagrindinių sprendinių skaičius ir atitinkamas pagrindinių kintamųjų grupių skaičius gali būti ne didesnis kaip , kur n yra bendras kintamųjų skaičius, r yra pagrindinių kintamųjų skaičius, r≤ m≤ n.
Dėl mūsų užduoties r = 4; n= 6. Tada , t.y. Galimos 15 grupių po 4 pagrindinius kintamuosius (arba 15 pagrindinių sprendinių).
Išspręskime lygčių sistemą pagrindinių kintamųjų atžvilgiu x 3 , x 4 , x 5 ,x 6:
Darant prielaidą, kad laisvieji kintamieji x 1 = 0, x 2 = 0, gauname pagrindinių kintamųjų reikšmes: x 3 = 312; x 4 = 15; x 5 = 24;x 6 = -10, t.y. pagrindinis sprendimas bus = (0; 0; 312; 15; 24; -10).
Šis pagrindinis sprendimas yra nepriimtina, nes x 6 = –10 ≤ 0 ir pagal apribojimo sąlygą x 6 ≥ 0. Todėl vietoj kintamojo x 6 kaip pagrindą reikia paimti kitą kintamąjį iš nemokamų x 1 arba x 2 .
Tolesnį sprendimą atliksime naudodami sutrumpintas simpleksines lenteles, pirmosios lentelės eilutes užpildydami sistemos koeficientais (1 lentelė):
1 lentelė
F- vadinama styga indeksas. Jis užpildytas tikslo funkcijos koeficientais, paimtais priešingais ženklais, nes funkcijos lygtis gali būti pavaizduota kaip F = 0 – (– 4x 1 – 3x 2).
Laisvųjų narių stulpelyje b i yra neigiamas elementas b 4 = -10, t.y. sistemos sprendimas negalioja. Norint gauti tinkamą sprendimą (pagrindinį planą), elementas b 4 turi būti neneigiamas.
Pasirinkite x 6 – eilutė su neigiamu laisvuoju nariu. Šioje eilutėje yra neigiamų elementų. Pasirinkite bet kurį iš jų, pavyzdžiui, "-1" in x 1 -stulpelis ir x 1 - stulpelis priimti kaip leidimų stulpelis(jis nustatys, kad kintamasis x 1 iš nemokamo pereis į pagrindinį).
Dalinamės nemokamais nariais b i apie atitinkamus elementus a yra sprendžiant stulpelį, gauname vertinamieji santykiaiΘ i==(24, 15, 12, 10). Iš jų pasirenkame mažiausią teigiamą (minΘ i=10), kuris atitiks leidimo eilutė. Leidimų eilutė apibrėžia kintamąjį x j, kuri kitame žingsnyje išsikiša iš pagrindo ir tampa laisva. Štai kodėl x 6 eilutė yra leistinoji eilutė, o elementas "-1" yra įgalinantis elementas. Mes jį apskritime. Kintamieji x 1 ir x 6 yra sukeisti.
Apskaičiuoti santykiai Θ i kiekvienoje eilutėje nustatomos taisyklės:
1) Θ i= jei b i ir a yra turėti skirtingus ženklus;
2) Θ i= ∞ jei b i= 0 ir a yra < 0;
3) Θ i= ∞ jei a yra = 0;
4) Θ i= 0, jei b i= 0 ir a yra > 0;
5) Θ i= jei b i ir a yra turi tuos pačius ženklus.
Mes atliekame modifikuoto Jordanijos pašalinimo (MJJI) žingsnį su leidžiančiu elementu ir sudarome naują lentelę (2 lentelė) pagal šią taisyklę:
1) vietoje skiriamojo elemento (RE) nustatoma reikšmė, jos atvirkštinė, t.y. ;
2) leistinosios linijos elementai skirstomi į RE;
3) skiriamosios stulpelio elementai suskirstomi į RE ir keičiasi ženklas;
4) likę elementai randami pagal stačiakampio taisyklę:
Iš lentelės. 2 parodyta, kad laisvieji nariai b i-stulpeliai yra neneigiami, todėl gaunamas pradinis leistinas sprendimas - pirmasis bazinis planas= (10; 0; 182; 5; 4; 0). Šiuo atveju funkcijos reikšmė F() = 40. Geometriškai tai atitinka viršų F(10; 0) sprendinio daugiakampis (1 pav.).
2 lentelė
2. Patikriname plano optimalumą. Bazinis planas nėra optimalus, nes in F-eilutė turi neigiamą koeficientą "-4". Patobuliname planą.
3. Naujos bazinės linijos radimas
Mes pasirenkame leidžiantį elementą pagal taisyklę:
Mes pasirenkame mažiausią neigiamą koeficientą in F- eilutė "-4", kuri nustato įgalinimo stulpelį - x 6; kintamasis x 6 išversti į pagrindinį;
Randame santykius Θ i, tarp jų pasirenkame mažiausią teigiamą, atitinkančią leistinąją eilutę:
min Θ i = min(14, 5, 2, ∞) = 2, vadinasi x 5 - eilutė - leistinoji, kintamoji x 5 verčiame į laisvą (kintamieji x 5 ir x 6 yra sukeisti).
Leidžiamosios eilutės ir stulpelio sankirtoje yra leistinas elementas "2";
Atliekame žingsnį SHMZhI, statome lentelę. 3 pagal aukščiau pateiktą taisyklę ir gaukite naują atskaitos planą = (12; 0; 156; 3; 0; 2).
3 lentelė
4. Naujojo pagrindinio plano optimalumo patikrinimas
Bazinis planas taip pat nėra optimalus, nes in F-eilutė turi neigiamą koeficientą "-1". Funkcijos reikšmė F() = 48, kuris geometriškai atitinka viršų E(12; 0) sprendinio daugiakampis (1 pav.). Patobuliname planą.
5. Naujos bazinės linijos radimas
x 2 stulpeliai yra leistini, nes F- eilutėje yra mažiausias neigiamas koeficientas „-1“. x 2 stulpelis (Δ 2 = -1). Mažiausio Θ radimas i: min Θ i = min(≈ 9, 6, ∞, 24) = 6, vadinasi x 4 eilutė – leistinoji. Leidžiamasis elementas „1/2“. Kintamųjų keitimas x 2 ir x keturi . Atliekame žingsnį SHMZhI, statome lentelę. 4, gauname naują atskaitos planą = (9; 6; 51; 0; 0; 5).
6. Pagrindinio plano optimalumo patikrinimas
AT F-linija, visi koeficientai neneigiami, todėl atskaitos planas optimalus. Geometriškai atitinka tašką D(9;6) (žr. 1 pav.). Optimalus planas suteikia maksimalią tikslo funkcijos reikšmę c.u.
Pagrindinis simplekso metodo, skirto MVG sprendimui, idėja susideda iš nuoseklaus MVGP paramos sprendimų tobulinimo.
Yra keletas būdų, kaip parašyti simplekso metodą.
- Pagrindinė simplekso metodo forma;
- Simplekso metodas simpleksinės lentelės pavidalu;
- Modifikuotas simplekso metodas;
- Simpleksinis metodas stulpelio pavidalu;
- Paprastas metodas eilutės formoje.
Apibrėžkime maksimalią tikslo funkcijos reikšmę F(X) = 3x 1 +5x 2 +4x 3 tokiomis apribojimo sąlygomis.
0,1x1 +0,2x2 +0,4x3 ≤1100
0,05x1 +0,02x2 +0,02x3 ≤120
3x1 +x2 +2x3 ≤8000
Norėdami sudaryti pirmąjį atskaitos planą, nelygybių sistemą sumažiname į lygčių sistemą, įvesdami papildomus kintamuosius (perėjimas prie kanoninės formos).
0,1x1 + 0,2x2 + 0,4x3 + 1x4 + 0x5 + 0x6 = 1100
0,05x1 + 0,02x2 + 0,02x3 + 0x4 + 1x5 + 0x6 = 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000
Pagrindinis simplekso metodo žymėjimas
| Sprendimas atliekamas išreiškiant pagrindinius kintamuosius ne pagrindiniais: x0 = 3x1 +5x2 +4x3 x 4 = 1100-0,1x1 -0,2x2 -0,4x3 x 5 = 120-0,05x1 -0,02x2 -0,02x3 x 6 = 8000-3x 1 -x 2 -2x 3 |
Simplekso metodas simpleksinės lentelės pavidalu
Sprendimas atliekamas paprastos lentelės pavidalu. Forma skirta kompiuteriui skaičiuoti. Naudojant dirbtinį pagrindą, naudojamas specialus skaičius M (dažniausiai 10000).| Planuoti | Pagrindas | AT | x 1 | x2 | x 3 | x4 | x5 | x6 | min |
| 1 | x4 | 1100 | 0.1 | 0.2 | 0.4 | 1 | 0 | 0 | 5500 |
| x5 | 120 | 0.05 | 0.02 | 0.02 | 0 | 1 | 0 | 6000 | |
| x6 | 8000 | 3 | 1 | 2 | 0 | 0 | 1 | 8000 | |
| Indekso eilutė | F(X1) | 0 | -3 | -5 | -4 | 0 | 0 | 0 | 0 |
| 2 | x2 | 5500 | 0.5 | 1 | 2 | 5 | 0 | 0 | 11000 |
| x5 | 10 | 0.04 | 0 | -0.02 | -0.1 | 1 | 0 | 250 | |
| x6 | 2500 | 2.5 | 0 | 0 | -5 | 0 | 1 | 1000 | |
| Indekso eilutė | F(X2) | 27500 | -0.5 | 0 | 6 | 25 | 0 | 0 | 0 |
| 3 | x2 | 5375 | 0 | 1 | 2.25 | 6.25 | -12.5 | 0 | 11000 |
| x1 | 250 | 1 | 0 | -0.5 | -2.5 | 25 | 0 | 250 | |
| x6 | 1875 | 0 | 0 | 1.25 | 1.25 | -62.5 | 1 | 1000 | |
| Indekso eilutė | F(X3) | 27625 | 0 | 0 | 5.75 | 23.75 | 12.5 | 0 | 0 |
Modifikuotas simplekso metodas
| Koeficientų matrica A = a ij Matrica b. |
Paprastas metodas stulpelio pavidalu
| Mes pereiname prie simpleksinio metodo stulpelinės formos. Kiekvieną kintamąjį išreiškiame nebaziniais. x 0 = 0-3 (-x 1)-5 (-x 2)-4 (-x 3) + 0 (-x 4) + 0 (-x 5) + 0 (-x 6) x 1 = 0-1 (-x 1) + 0 (-x 2) + 0 (-x 3) + 0 (-x 4) + 0 (-x 5) + 0 (-x 6) x 2 = 0 + 0 (-x 1) - 1 (-x 2) + 0 (-x 3) + 0 (-x 4) + 0 (-x 5) + 0 (-x 6) x 3 = 0+0(-x 1)+0(-x 2)-1(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 4 = 1100 + 0,1 (-x 1) + 0,2 (-x 2) + 0,4 (-x 3) + 1 (-x 4) + 0 (-x 5) + 0 (-x 6) x 5 = 120 + 0,05 (-x 1) + 0,02 (-x 2) + 0,02 (-x 3) + 0 (-x 4) + 1 (-x 5) + 0 (-x 6) x 6 = 8000 + 3 (-x 1) + 1 (-x 2) + 2 (-x 3) + 0 (-x 4) + 0 (-x 5) + 1 (-x 6) Ši sistema atitinka lentelę T 0 .
|
Paprastas metodas eilutės forma
Kaip pradinę leistiną bazę galime paimti B 0 =<4, 5, 6>. Tai atitiks toliau pateiktą lentelę.
|
Matrica Q, sudaryta iš sistemos koeficientų, vadinama simplex stalas atitinkantis bazę B. Vadinamas simpleksas priimtinas, arba tiesiogiai priimtina, jei q i0 ≥ 0. Paprastosios lentelės Q paskutinės eilutės elementai q i0 vadinami santykiniai įverčiai.
Tirpalo formos dirbtinio pagrindo metodu
Naudojant dirbtinius kintamuosius, įvestus į tikslo funkciją, skiriama vadinamoji M bauda, labai didelis teigiamas skaičius, kuris dažniausiai nenurodomas.Gautas pagrindas vadinamas dirbtiniu, o sprendimo metodas vadinamas dirbtinio pagrindo metodu.
Be to, dirbtiniai kintamieji nėra susiję su užduoties turiniu, bet leidžia sukurti atskaitos tašką, o optimizavimo procesas verčia šiuos kintamuosius priimti nulines reikšmes ir užtikrinti optimalaus sprendimo priimtinumą.
Tirpalo formos dirbtinio pagrindo metodu:
- M metodas (simplex lentelė);
- dviejų pakopų arba dviejų fazių simplekso metodas (Pagrindinis žymėjimas, Modifikuotas simplekso metodas, Simpleksinis metodas stulpelio pavidalu, Simpleksinis metodas eilutės forma).
Jei uždavinio sąlygoje yra apribojimų su ženklu ≥, tai juos galima redukuoti iki formos ∑a ji b j, padauginus abi nelygybės dalis iš -1. Įvedame m papildomų kintamųjų x n+j ≥0(j =1,m ) ir paverčiame apribojimus lygybių forma
(2)
Tarkime, kad visi pradiniai uždavinio kintamieji x 1 , x 2 ,..., x n yra nebaziniai. Tada papildomi kintamieji bus pagrindiniai, o konkretus apribojimų sistemos sprendimas turi formą
x 1 = x 2 = ... = x n = 0, x n+ j = b j , j = 1, m . (3)
Kadangi šiuo atveju tikslo funkcijos reikšmė F 0 = 0, F(x) galime pavaizduoti taip:
F(x)=∑c i x i + F 0 =0 (4)
Pradinė simplekso lentelė (1 simplekso lentelė) sudaryta remiantis (2) ir (4) lygtimis. Jei prieš papildomus kintamuosius x n+j yra „+“ ženklas, kaip nurodyta (2), tai visi koeficientai prieš kintamuosius x i ir laisvąjį terminą b j į simpleksinę lentelę įrašomi be pokyčių. Tikslo funkcijos koeficientai jo maksimizavimo metu įvedami į apatinę simplekso lentelės eilutę su priešingais ženklais. Laisvieji nariai simpleksinėje lentelėje nustato problemos sprendimą.
Problemos sprendimo algoritmas yra toks:
1 žingsnis. Peržiūrimi nemokamų narių stulpelio elementai. Jei jie visi teigiami, tada rastas priimtinas pagrindinis sprendimas ir reikia pereiti prie 5 algoritmo žingsnio, kuris atitinka optimalaus sprendimo paiešką. Jei pradinėje simpleksinėje lentelėje yra neigiamų laisvųjų terminų, sprendimas negalioja ir turėtumėte pereiti prie 2 veiksmo.
2 žingsnis. Norint rasti įmanomą sprendimą, atliekama, kartu reikia nuspręsti, kurį iš nepagrindinių kintamųjų įtraukti į bazę, o kurį iš jo pašalinti.
1 lentelė.
| baziniai kintamieji | Laisviems nariams taikomi apribojimai | Nebaziniai kintamieji | |||||
| x 1 | x2 | ... | x l | ... | x n|||
| xn+1 | b 1 | a 11 | a 12 | ... | a 1l | ... | a 1n |
| xn+2 | b 2 | a 21 | a 22 | ... | a 2l | ... | a 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+r | b2 | a r1 | a r2 | ... | a rl | ... | a rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+m | b m | a m1 | m2 | ... | a ml | ... | amn |
| F(x)maks | F0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
Norėdami tai padaryti, pasirinkite bet kurį iš neigiamų laisvųjų narių stulpelio elementų (tebūnie b 2 pirmaujantis, arba leidžiantis. Jei eilutėje su neigiamu laisvuoju nariu nėra neigiamų elementų, tai apribojimų sistema yra nenuosekli ir problema neturi sprendimo.
Tuo pačiu metu kintamasis, kuris pirmasis pakeičia ženklą padidinus pasirinktą NP x l, neįtraukiamas į BP. Tai bus x n+r , kurio indeksas r nustatomas pagal sąlygą
tie. kintamasis, atitinkantis mažiausią laisvojo termino santykį su pasirinkto pirmaujančio stulpelio elementu. Šis ryšys vadinamas simpleksinis santykis. Reikėtų atsižvelgti tik į teigiamus simpleksinius ryšius.
Iškviečiama eilutė, atitinkanti kintamąjį x n+r vedantis arba leidžiantis. Paprastosios lentelės elementas a rl , esantis pirmaujančios eilutės ir pirmaujančios stulpelio sankirtoje, vadinamas pirmaujančiu arba skiriamuoju elementu. Surasus pagrindinį elementą, darbas baigiamas su kiekviena sekančia simplekso paveikslėliu.
3 žingsnis. Skaičiuojama nauja simplekso lentelė, kurios elementai perskaičiuojami iš ankstesnio žingsnio simplekso lentelės elementų ir pažymimi pirminiu, t.y. b" j , a" ji , c" i , F" 0 . Elementai perskaičiuojami pagal šias formules:
Pirma, eilutė ir stulpelis, kurie buvo pirmaujanti ankstesnėje vienareikšmėje lentelėje, bus užpildyti naujoje vienareikšmėje lentelėje. Išraiška (5) reiškia, kad elementas a "rl vietoje pirmaujančio elemento yra lygus ankstesnės simpleksinės lentelės elemento atvirkštiniam dydžiui. Eilutės a ri elementai dalijami iš pirmaujančio elemento, o stulpelis a jl taip pat dalijami iš pirmaujančio elemento, bet paimami su priešingu ženklu. Elementai b" r ir c" l apskaičiuojami pagal tą patį principą.
Likusias formules galima lengvai parašyti naudojant .
Stačiakampis statomas pagal senąją simplekso lentelę taip, kad vieną jo įstrižainę sudaro perskaičiuoti (a ji) ir pirmaujantys (a rl) elementai (1 pav.). Antroji įstrižainė yra vienareikšmiškai nustatyta. Norint rasti naują elementą a "ji, priešingos įstrižainės elementų sandauga, padalyta iš pirmaujančio elemento, atimama iš elemento a ji (tai rodomas ženklas" - "ląstelėje). Panašiai elementai b" j, (j≠r) ir c" i perskaičiuojami, (i≠l).
4-as žingsnis. Naujos simpleksinės lentelės analizė pradedama nuo 1-ojo algoritmo žingsnio. Veiksmas tęsiamas tol, kol randamas įmanomas pagrindinis sprendimas, t.y. visi laisvųjų narių stulpelio elementai turi būti teigiami.
5 žingsnis. Manome, kad buvo rastas priimtinas pagrindinis sprendimas. Žiūrime į tikslo funkcijos F(x) tiesės koeficientus. Simpleksinės lentelės optimalumo ženklas yra nebazinių kintamųjų koeficientų neneigiamumas F eilutėje.
Ryžiai. 1. Stačiakampio taisyklė
Jei tarp F eilutės koeficientų yra neigiamų (išskyrus laisvąjį terminą), tuomet reikia pereiti prie kito pagrindinio sprendimo. Maksimaliai padidinant tikslo funkciją, į pagrindą įtraukiamas nepagrindinių kintamųjų (pvz., x l) stulpelis, kurio stulpelis atitinka maksimalią absoliučią neigiamo koeficiento c l reikšmę simpleksinės lentelės apatinėje eilutėje. Tai leidžia pasirinkti kintamąjį, kurio padidinimas pagerina tikslo funkciją. Stulpelis, atitinkantis kintamąjį x l, vadinamas pirmaujančiu stulpeliu. Tuo pačiu į bazę neįtraukiamas tas kintamasis x n+r, kurio indeksas r nustatomas pagal minimalų simplekso santykį:
Eilutė, atitinkanti x n+r, vadinama pirmaujančia eilute, o simpleksinės lentelės elementas a rl , kuris yra pirmaujančios eilutės ir pirmaujančios stulpelio sankirtoje. vedantis elementas.
6-as žingsnis. pagal 3 žingsnyje nustatytas taisykles. Procedūra tęsiama tol, kol randamas optimalus sprendimas arba padaroma išvada, kad jo nėra.
Jei optimizuojant sprendimą priekiniame stulpelyje visi elementai yra neteigiami, tada priekinės eilutės pasirinkti negalima. Šiuo atveju funkcija leistinų problemos sprendimų srityje nėra ribojama iš viršaus ir F max ->&∞.
Jei kitame ekstremumo paieškos etape vienas iš pagrindinių kintamųjų tampa lygus nuliui, tada atitinkamas pagrindinis sprendimas vadinamas išsigimusiu. Tokiu atveju įvyksta vadinamasis kilpavimas, kuriam būdinga tai, kad tas pats BP derinys pradeda kartotis tam tikru dažniu (šiuo atveju išsaugoma funkcijos F reikšmė) ir įjungti neįmanoma. naujas priimtinas pagrindinis sprendimas. Kilpų sukūrimas yra vienas iš pagrindinių simpleksinio metodo trūkumų, tačiau jis yra gana retas. Praktikoje tokiais atvejais dažniausiai atsisakoma į bazę įvesti kintamąjį, kurio stulpelis atitinka maksimalią absoliučią neigiamo koeficiento reikšmę tikslo funkcijoje, ir atsitiktinai pasirenkamas naujas pagrindinis sprendimas.
1 pavyzdys. Išspręskite problemą
maks.(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)
Paprastasis metodas ir pateikti geometrinę sprendimo proceso interpretaciją.
Grafinis uždavinio sprendimo aiškinimas parodytas pav. 2. Maksimali tikslo funkcijos reikšmė pasiekiama ODZP viršuje su koordinatėmis . Išspręskime užduotį naudodami simplex lenteles. Antrąjį apribojimą padauginame iš (-1) ir įvedame papildomų kintamųjų, kad nelygybės būtų lygybės, tada
Pradiniai kintamieji x 1 ir x 2 laikomi nepagrindiniais, o papildomi x 3 , x 4 ir x 5 laikomi pagrindiniais ir sudarome simpleksinę lentelę (simpleksinė lentelė 2). Sprendimas, atitinkantis simplekso lentelę. 2, negalioja; pagrindinis elementas apibrėžiamas ir parenkamas pagal aukščiau pateikto algoritmo 2 veiksmą. Kitas simplekso skirtukas. 3 apibrėžia leistiną pagrindinį sprendimą; 2 Pagrindinis elementas apibrėžiamas ir parenkamas pagal 5 problemos sprendimo algoritmo žingsnį. Skirtukas. 4 atitinka optimalų uždavinio sprendimą, todėl: x 1 = x 5 = 0; x 2 \u003d 4; x 3 \u003d 3; x 4 = 8; F max = 20.
Ryžiai. 2. Grafinis uždavinio sprendimas
