Me metodën grafike për zgjidhjen e problemeve LP, ne në fakt zgjodhëm nga grupi i kulmeve që i përkasin kufirit të grupit të zgjidhjeve të sistemit të pabarazive një kulm të tillë në të cilin vlera e funksionit objektiv arriti maksimumin (minimumin). Në rastin e dy variablave, kjo metodë është plotësisht intuitive dhe ju lejon të gjeni shpejt një zgjidhje për problemin.
Nëse ka tre ose më shumë variabla në problem, dhe në problemet reale ekonomike kjo është pikërisht situata, është e vështirë të vizualizohet zona e zgjidhjeve për sistemin e kufizimeve. Detyra të tilla zgjidhen duke përdorur metodë simplex ose me metodën e përmirësimit të njëpasnjëshëm. Ideja e metodës është e thjeshtë dhe është si më poshtë.
Sipas një rregulli të caktuar, gjendet plani fillestar i referencës (një kulm i zonës së kufizimit). Kontrollohet nëse plani është optimal. Nëse po, atëherë problemi është zgjidhur. Nëse jo, atëherë shkoni në një plan tjetër të përmirësuar - në një kulm tjetër. vlera e funksionit objektiv në këtë plan (në këtë kulm) është dukshëm më e mirë se në atë të mëparshme. Algoritmi i tranzicionit kryhet duke përdorur një hap llogaritës, i cili shkruhet në mënyrë të përshtatshme në formën e tabelave, të quajtura tabela simplex ... Duke qenë se numri i kulmeve është i fundëm, atëherë në një numër të kufizuar hapash vijmë te zgjidhja optimale.
Le të shqyrtojmë metodën simplex duke përdorur një shembull specifik të problemit të hartimit të një plani.
Vini re përsëri se metoda simplex është e zbatueshme për zgjidhjen e problemeve kanonike LP të reduktuara në një formë të veçantë, d.m.th., duke pasur një bazë, anët pozitive të djathta dhe një funksion objektiv të shprehur në terma të variablave jo bazë. Nëse detyra nuk reduktohet në një formë të veçantë, atëherë nevojiten hapa shtesë, për të cilët do të flasim më vonë.
Le të shqyrtojmë problemin e një plani prodhimi, pasi kemi ndërtuar më parë një model dhe e kemi reduktuar atë në një formë të veçantë.
Detyrë.
Për prodhimin e produkteve A dhe V magazina mund të lëshojë jo më shumë se 80 njësi lëndë të parë. Për më tepër, për prodhimin e produktit A konsumohen dy njësi dhe produktet V- një njësi lëndësh të para. Kërkohet të planifikohet prodhimi në mënyrë që të sigurohet fitimi më i madh nëse produktet A kërkohet të bëhen jo më shumë se 50 copë, dhe produkte V- jo më shumë se 40 copë. Për më tepër, fitimi nga shitja e një produkti A- 5 rubla, dhe nga V- 3 rubla.
Le të ndërtojmë një model matematikor, duke treguar për X 1 numër i produkteve A në plan, për X 2 - numri i produkteve V... atëherë sistemi i kufizimeve do të duket si ky:
Le ta sjellim problemin në një formë kanonike duke futur variabla shtesë:
(3.10)
F = -5x 1 - 3x 2 → min.
Ky problem ka një formë të veçantë (me bazë, anët e djathta janë jo negative). Mund të zgjidhet duke përdorur metodën simplex.
Unëfazë. Shkrimi i një problemi në një tabelë Simplex. Ekziston një korrespondencë një-për-një midis sistemit të kufizimeve të problemit (3.10) dhe tabelës simplex. Ka aq rreshta në tabelë sa ka barazi në sistemin e kufizimeve dhe ka aq kolona sa ka variabla të lirë. Variablat bazë mbushin kolonën e parë, variablat e lira - rreshtin e sipërm të tabelës. Rreshti i fundit quhet vija e indeksit; ai përmban koeficientët e variablave në funksionin objektiv. Fillimisht 0 shkruhet në këndin e poshtëm djathtas nëse nuk ka term të lirë në funksion; nëse ka, atëherë e shkruajmë me shenjën e kundërt. Në këtë vend (në këndin e poshtëm djathtas) do të jetë vlera e funksionit objektiv, i cili, kur lëviz nga një tabelë në tjetrën, duhet të rritet në modul. Pra, sistemi ynë i kufizimeve korrespondon me tabelën 3.4, dhe ne mund të kalojmë në fazën II të zgjidhjes.
Tabela 3.4
|
bazë |
pa pagesë |
||
IIfazë... Kontrollimi i planit të mbështetjes për optimalitet.
Kjo tabelë 3.4 korrespondon me planin bazë të mëposhtëm:
(X 1 , X 2 , X 3 , X 4 , X 5) = (0, 0, 50, 40, 80).
Variabla të lira X 1 , X 2 janë të barabarta me 0; X 1 = 0, X 2 = 0. Dhe variablat bazë X 3 , X 4 , X 5 merr vlerat X 3 = 50, X 4 = 40, X 5 = 80 - nga kolona e anëtarëve të lirë. Vlera e funksionit objektiv:
-F = - 5X 1 - 3X 2 = -5 0 - 3 0 = 0.
Detyra jonë është të kontrollojmë nëse një plan bazë i dhënë është optimal. për këtë, ju duhet të shikoni vijën e indeksit - vijën e funksionit objektiv F.
Situata të ndryshme janë të mundshme.
1. Në indeks F-vargu nuk ka elemente negative. Kjo do të thotë që plani është optimal, ju mund të shkruani zgjidhjen e problemit. Funksioni objektiv ka arritur vlerën e tij optimale të barabartë me numrin në këndin e poshtëm djathtas të marrë me shenjën e kundërt. Kalojmë në fazën IV.
2. Rreshti i indeksit përmban të paktën një element negativ, kolona e të cilit nuk përmban elemente pozitive. Pastaj arrijmë në përfundimin se funksioni objektiv F→ ∞ zvogëlohet pa kufi.
3. Rreshti i indeksit përmban një element negativ me të paktën një element pozitiv në kolonën e tij. Më pas kalojmë në fazën tjetër III. rillogaritja e tabelës, përmirësimi i bazës.
IIIfazë... Përmirësimi i bazës.
Nga elementet e indeksit negativ F-Rreshtat zgjedhin më të madhin në modul, thirrni kolonën përkatëse zgjidhëse dhe shënoni "".
Për të zgjedhur rreshtin zgjidhës, është e nevojshme të llogariten raportet e elementeve të kolonës së anëtarit të lirë vetëm për të pozitive elementet lejuese të kolonës. Zgjidhni minimumin nga relacionet e marra. Elementi përkatës në të cilin arrihet minimumi quhet lejues. Do ta theksojmë me një katror.
Në shembullin tonë, 
, elementi 2 është lejues. Linja që i përgjigjet këtij elementi quhet gjithashtu zgjidhje (Tabela 3.5).
Tabela 3.5
Pasi kemi zgjedhur elementin zgjidhës, ne rillogaritim tabelën sipas rregullave:
1. Në tabelën e re me të njëjtat dimensione si më parë, ndryshohen variablat e rreshtit dhe kolonës zgjidhëse, gjë që korrespondon me kalimin në një bazë të re. Në shembullin tonë: X 1 është përfshirë në bazë, në vend të X 5, i cili lë bazën dhe tani është i lirë (Tabela 3.6).
Tabela 3.6
|
bazë |
pa pagesë |
||
2. Në vend të zgjidhjes së elementit 2, shkruani numrin e anasjelltë të tij.
3. Elementet e vijës zgjidhëse ndahen me elementin zgjidhës.
4. Elementet e kolonës zgjidhëse ndahen me elementin zgjidhës dhe shkruhen me shenjën e kundërt.
5. Për të plotësuar elementët e mbetur të tabelës 3.6, rillogaritemi sipas rregullit drejtkëndësh. Supozoni se duam të numërojmë elementin në pozicionin 50.
Ne e lidhim këtë element mendërisht me atë zgjidhës, gjejmë produktin, zbresim produktin e elementeve të vendosura në diagonalen tjetër të drejtkëndëshit që rezulton. Diferencën e ndajmë me elementin zgjidhës.
Kështu që, . Ne shkruajmë 10 në vendin ku ishte 50. Në mënyrë të ngjashme :
, 
, , 
.
Tabela 3.7
Kemi një tabelë të re 3.7, variablat bazë tani janë variablat (x 3, x 4, x 1). Vlera e funksionit objektiv u bë e barabartë me -200, d.m.th., u ul. Për të kontrolluar këtë zgjidhje bazë për optimalitet, është e nevojshme të kalojmë përsëri në fazën II. Procesi është padyshim i fundëm, kriteret e ndalimit janë pikat 1 dhe 2 të fazës II.
Zgjidhjen e problemit do ta çojmë deri në fund. Për ta bërë këtë, kontrolloni rreshtin e indeksit dhe, duke parë një element negativ në të, thirrni kolonën përkatëse zgjidhëse dhe, sipas fazës III, rillogaritni tabelën. Pasi kemi përpiluar relacionet dhe duke zgjedhur mes tyre minimumin = 40, kemi përcaktuar elementin zgjidhës 1. Tani kryejmë rillogaritjen sipas rregullave 2-5.
Tabela 3.8
|
bazë |
pa pagesë |
||
|
x 3 = 30, X 2 = 40, X 1 = 20. Variablat e lira janë 0, X 5 = 0, X 4 = 0. Funksioni objektiv merr vlerën e elementit të fundit të kolonës së anëtarëve të lirë me shenjën e kundërt: - F = -220 F = 220, në shembullin tonë funksioni u ekzaminua për min, dhe fillimisht F max, kështu që shenja në fakt ndryshoi dy herë. Kështu që, X* = (20, 40, 30, 0, 0), F* = 220. Përgjigjja e problemit: Është e nevojshme të përfshihen 20 produkte të llojit A, 40 produkte të tipit B, ndërsa fitimi do të jetë maksimal dhe do të jetë i barabartë me 220 rubla. Në fund të këtij seksioni, ne paraqesim një diagram bllok të algoritmit të metodës simplex, i cili përsërit saktësisht hapat, por, ndoshta, për disa lexues do të jetë më i përshtatshëm për t'u përdorur, pasi shigjetat tregojnë një drejtim të qartë veprimi. Lidhjet mbi drejtkëndëshat në grafikun e rrjedhës tregojnë se cilës faze ose nënklauzolë i përket grupi përkatës i transformimit. Rregulli për gjetjen e planit fillestar fillestar do të formulohet në pikën 3.7.
Pyetje për vetëkontroll 1. Si ndërtohet një tabelë simplex? 2. Si pasqyrohet ndryshimi i bazës në tabelë? 3. Formuloni një kriter ndalues për metodën simplex. 4. Si të organizohet rillogaritja e tabelës? 5. Nga cila linjë është e përshtatshme për të filluar rillogaritjen e tabelës? |
... Algoritmi i metodës së thjeshtë
Shembulli 5.1. Zgjidheni problemin e mëposhtëm të programimit linear duke përdorur metodën simplex:
Zgjidhja:
Unë përsëritje:
x3, x4, x5, x6 x1,x2... Le të shprehim variablat bazë në terma të atyre të lirë:
Le ta sjellim funksionin objektiv në formën e mëposhtme:
Bazuar në problemin e marrë, do të formojmë tabelën fillestare të Simpleksit:
Tabela 5.3
Tabela e burimit simplex
Marrëdhëniet e vlerësimit |
||||
Sipas përcaktimit të zgjidhjes bazë, ndryshoret e lira janë të barabarta me zero, dhe vlerat e variablave bazë janë të barabarta me vlerat përkatëse të numrave të lirë, d.m.th.
Faza 3: kontrollimi i përputhshmërisë së sistemit të kufizimit të LPP-së.
Në këtë përsëritje (në tabelën 5.3), shenja e papajtueshmërisë së sistemit të kufizimeve (shenja 1) nuk u identifikua (d.m.th., nuk ka asnjë rresht me një numër të lirë negativ (me përjashtim të vijës së funksionit objektiv), i cili bën të mos përmbajnë të paktën një element negativ (dmth. koeficient negativ në një variabël të lirë)).
Në këtë përsëritje (në tabelën 5.3), shenja e pakufizimit të funksionit objektiv (shenja 2) nuk u identifikua (d.m.th., nuk ka asnjë kolonë me një element negativ në vijën e funksionit objektiv (përveç kolonës së lirë numra), në të cilat nuk do të kishte të paktën një element pozitiv) ...
Meqenëse zgjidhja bazë e gjetur nuk përmban përbërës negativë, është e pranueshme.
Faza 6: kontrollimi i optimalitetit.
Zgjidhja bazë e gjetur nuk është optimale, pasi sipas kriterit të optimalitetit (veçoria 4), në vijën e funksionit objektiv nuk duhet të ketë elemente negative (numri i lirë i kësaj rreshti nuk merret parasysh kur merret parasysh kjo veçori). Prandaj, sipas algoritmit të metodës simplex kalojmë në fazën e 8-të.
Meqenëse zgjidhja bazë e gjetur është e pranueshme, kërkimi për kolonën zgjidhëse do të kryhet sipas skemës së mëposhtme: ne përcaktojmë kolonat me elemente negative në vijën e funksionit objektiv (përveç kolonës së numrave të lirë). Sipas tabelës 5.3, ekzistojnë dy kolona të tilla: kolona " x1"Dhe kolona" x2". Nga këto kolona zgjidhet ajo që përmban elementin më të vogël në vijën e funksionit objektiv. Ajo do të zgjidhet. folësi " x2"Përmban elementin më të vogël (–3) në krahasim me kolonën" x1
Për të përcaktuar vijën zgjidhëse, gjejmë raportet vlerësuese pozitive të numrave të lirë me elementët e kolonës zgjidhëse, linja, e cila korrespondon me raportin më të vogël vlerësues pozitiv, merret si e lejuar.
Tabela 5.4
Tabela e burimit simplex
Në tabelën 5.4, raporti më i vogël pozitiv i vlerësuar korrespondon me linjën " x5”, Prandaj do të zgjidhet.
Elementi që ndodhet në kryqëzimin e kolonës lejuese dhe vijës së lejimit pranohet si lejues. Në shembullin tonë, ky është një element i vendosur në kryqëzimin e linjës " x5"Dhe kolonat" x2».
Elementi zgjidhës tregon një variabël bazë dhe një variabël të lirë që duhet të ndërrohen në tabelën simplex në mënyrë që të kalohet në një zgjidhje të re bazë "të përmirësuar". Në këtë rast, këto janë variabla x5 dhe x2, në tabelën e re simplex (tabela 5.5) i ndërrojmë ato.
9.1. Transformimi i elementit të rezolucionit.
Elementi lejues i Tabelës 5.4 transformohet si më poshtë:
Ne e fusim rezultatin e marrë në një qelizë të ngjashme në Tabelën 5.5.
9.2. Konvertoni vargun e rezolucionit.
Ne i ndajmë elementet e vijës zgjidhëse të tabelës 5.4 me elementin zgjidhës të kësaj tabele simplex, rezultatet përshtaten në qeliza të ngjashme të tabelës së re simplex (Tabela 5.5). Transformimet e elementeve të vijës së rezolucionit janë dhënë në tabelën 5.5.
9.3. Konvertimi i kolonës së rezolucionit.
Elementet e kolonës zgjidhëse të tabelës 5.4 ndahen me elementin zgjidhës të tabelës së dhënë Simplex, dhe rezultati merret me shenjën e kundërt. Rezultatet e marra përshtaten në qeliza të ngjashme të tabelës së re Simplex (Tabela 5.5). Transformimet e elementeve të kolonës zgjidhëse janë paraqitur në tabelën 5.5.
9.4. Konvertoni pjesën tjetër të elementeve të tabelës Simplex.
Transformimi i elementeve të mbetur të tabelës simplex (d.m.th. elementet që nuk ndodhen në vijën e zgjidhjes dhe në kolonën e zgjidhjes) kryhet sipas rregullit "drejtkëndësh".
Për shembull, merrni parasysh transformimin e një elementi të vendosur në kryqëzimin e vargut " x3"Dhe kolona" ", ne do ta caktojmë në mënyrë konvencionale si" x3". Në tabelën 5.4, vizatoni mendërisht një drejtkëndësh, një kulm i të cilit ndodhet në qelizë, vlerën e së cilës e transformojmë (d.m.th. në qelizën " x3»), Dhe tjetra (kulmi diagonal) është në qelizën me elementin zgjidhës. Dy kulmet e tjera (diagonalja e dytë) përcaktohen në mënyrë unike. Pastaj vlera e transformuar e qelizës " x3"Do të jetë e barabartë me vlerën e mëparshme të kësaj qelize minus thyesën, në emëruesin e së cilës ka një element zgjidhës (nga tabela 5.4), dhe në numërues produktin e dy kulmeve të tjera të papërdorura, dmth:
« x3»: .
Vlerat e qelizave të tjera transformohen në mënyrë të ngjashme:
« x3 x1»: ;
« x4»: 
;
« x4 x1»: ;
« x6»: 
;
« x6 x1»: ;
«»: 
;
« x1»: 
.
Si rezultat i këtyre transformimeve, u përftua një tabelë e re simplex (tabela 5.5).
II përsëritje:
Faza 1: hartimi i një tabele simplex.
Tabela 5.5
Tabela e thjeshtëII përsëritjet
e vlerësuar marrëdhënie |
||||
| ||||
|
|
Faza 2: përcaktimi i zgjidhjes bazë.
Si rezultat i transformimeve të Simpleksit, u mor një zgjidhje e re bazë (Tabela 5.5):
Siç mund ta shihni, me këtë zgjidhje bazë, vlera e funksionit objektiv = 15, që është më shumë se me zgjidhjen bazë të mëparshme.
Mospërputhja e sistemit të kufizimeve në përputhje me atributin 1 në Tabelën 5.5 nuk u zbulua.
Faza 4: kontrollimi i kufizimit të funksionit objektiv.
Pakufishmëria e funksionit objektiv në përputhje me tiparin 2 në Tabelën 5.5 nuk u zbulua.
Faza 5: kontrollimi i pranueshmërisë së zgjidhjes bazë të gjetur.
Zgjidhja bazë e gjetur në përputhje me tiparin 4 nuk është optimale, pasi vija e funksionit objektiv të tabelës simplex (Tabela 5.5) përmban një element negativ: -2 (numri i lirë i kësaj rreshti nuk merret parasysh kur merret parasysh kjo veçori). Prandaj, shkojmë në fazën 8.
Faza 8: përcaktimi i elementit zgjidhës.
8.1. Përkufizimi i kolonës së rezolucionit.
Zgjidhja bazë e gjetur është e pranueshme, përcaktojmë kolonat me elemente negative në vijën e funksionit objektiv (përveç kolonës së numrave të lirë). Sipas tabelës 5.5, vetëm një kolonë është një kolonë e tillë: " x1". Prandaj, ne e pranojmë atë siç lejohet.
8.2. Përcaktimi i vargut të lejes.
Sipas vlerave të marra të raporteve vlerësuese pozitive në tabelën 5.6, minimumi është raporti që korrespondon me rreshtin " x3". Prandaj, ne e pranojmë atë siç lejohet.
Tabela 5.6
Tabela e thjeshtëII përsëritjet
e vlerësuar marrëdhënie |
||||
3/1 = 3 - min |
||||
Faza 9: transformimi i tabelës Simplex.
Transformimet e tabelave të thjeshta (tabelat 5.6) kryhen në të njëjtën mënyrë si në përsëritjen e mëparshme. Rezultatet e transformimeve të elementeve të një tabele simplex janë paraqitur në tabelën 5.7.
III përsëritje
Bazuar në rezultatet e transformimeve të Simpleksit të përsëritjes së mëparshme, ne përpilojmë një tabelë të re Simplex:
Tabela 5.7
Tabela e thjeshtëIII përsëritjet
e vlerësuar marrëdhënie |
||||
| ||||
|
|
Faza 2: përcaktimi i zgjidhjes bazë.
Si rezultat i transformimeve Simplex, u mor një zgjidhje e re bazë (Tabela 5.7):
Faza 3: kontrollimi i qëndrueshmërisë së sistemit të kufizimeve.
Mospërputhja e sistemit të kufizimeve në përputhje me atributin 1 në Tabelën 5.7 nuk u zbulua.
Faza 4: kontrollimi i kufizimit të funksionit objektiv.
Pakufishmëria e funksionit objektiv në përputhje me tiparin 2 në Tabelën 5.7 nuk u zbulua.
Faza 5: kontrollimi i pranueshmërisë së zgjidhjes bazë të gjetur.
Zgjidhja bazë e gjetur në përputhje me atributin 3 është e pranueshme, pasi nuk përmban përbërës negativë.
Faza 6: kontrollimi i optimalitetit të zgjidhjes bazë të gjetur.
Zgjidhja bazë e gjetur në përputhje me tiparin 4 nuk është optimale, pasi vija e funksionit objektiv të tabelës simplex (Tabela 5.7) përmban një element negativ: -3 (numri i lirë i kësaj rreshti nuk merret parasysh kur merret parasysh kjo veçori). Prandaj, shkojmë në fazën 8.
Faza 8: përcaktimi i elementit zgjidhës.
8.1. Përkufizimi i kolonës së rezolucionit.
Zgjidhja bazë e gjetur është e pranueshme, përcaktojmë kolonat me elemente negative në vijën e funksionit objektiv (përveç kolonës së numrave të lirë). Sipas tabelës 5.7, vetëm një kolonë është një kolonë e tillë: " x5". Prandaj, ne e pranojmë atë siç lejohet.
8.2. Përcaktimi i vargut të lejes.
Sipas vlerave të marra të raporteve vlerësuese pozitive në tabelën 5.8, minimumi është raporti që korrespondon me rreshtin " x4". Prandaj, ne e pranojmë atë siç lejohet.
Tabela 5.8
Tabela e thjeshtëIII përsëritjet
e vlerësuar marrëdhënie |
||||
5/5 = 1 - min |
||||
Faza 9: transformimi i tabelës Simplex.
Transformimet e tabelave të thjeshta (Tabela 5.8) kryhen në të njëjtën mënyrë si në përsëritjen e mëparshme. Rezultatet e transformimeve të elementeve të një tabele simplex janë paraqitur në tabelën 5.9.
IV përsëritje
Faza 1: ndërtimi i një tabele të re simplex.
Bazuar në rezultatet e transformimeve të Simpleksit të përsëritjes së mëparshme, ne përpilojmë një tabelë të re Simplex:
Tabela 5.9
Tabela e thjeshtëIV përsëritjet
e vlerësuar marrëdhënie |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
Faza 2: përcaktimi i zgjidhjes bazë.
Si rezultat i transformimeve Simplex, është marrë një zgjidhje e re bazë, sipas tabelës 5.9, zgjidhja është si më poshtë:
Faza 3: kontrollimi i qëndrueshmërisë së sistemit të kufizimeve.
Mospërputhja e sistemit të kufizimeve në përputhje me atributin 1 në Tabelën 5.9 nuk u zbulua.
Faza 4: kontrollimi i kufizimit të funksionit objektiv.
Pakufishmëria e funksionit objektiv në përputhje me tiparin 2 në Tabelën 5.9 nuk u zbulua.
Faza 5: kontrollimi i pranueshmërisë së zgjidhjes bazë të gjetur.
Zgjidhja bazë e gjetur në përputhje me atributin 3 është e pranueshme, pasi nuk përmban përbërës negativë.
Faza 6: kontrollimi i optimalitetit të zgjidhjes bazë të gjetur.
Zgjidhja bazë e gjetur në përputhje me tiparin 4 është optimale, pasi nuk ka elemente negative në vijën e funksionit objektiv të tabelës Simplex (Tabela 5.9) (numri i lirë i kësaj rreshti nuk merret parasysh kur merret parasysh kjo veçori) .
Faza 7: kontrollimi i alternativës së zgjidhjes.
Zgjidhja e gjetur është e vetmja, pasi nuk ka elemente zero në vijën e funksionit objektiv (Tabela 5.9) (numri i lirë i kësaj rreshti nuk merret parasysh kur merret parasysh kjo veçori).
Përgjigje: vlera optimale e funksionit objektiv të problemit të konsideruar = 24, e cila arrihet në.
Shembulli 5.2. Zgjidheni problemin e mësipërm të programimit linear me kusht që funksioni objektiv të minimizohet:
Zgjidhja:
Unë përsëritje:
Faza 1: formimi i tabelës fillestare të Simpleksit.
Problemi origjinal i programimit linear është dhënë në një formë standarde. Le ta sjellim atë në formën e tij kanonike duke futur një ndryshore shtesë jonegative në secilin prej kufizimeve të pabarazisë, d.m.th.
Në sistemin rezultues të ekuacioneve, marrim si variablat e lejuar (bazë). x3, x4, x5, x6, atëherë variablat e lirë do të jenë x1,x2... Le të shprehim variablat bazë në terma të atyre të lirë.
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| - | x 1 | + | x 2 | - | S 1 | + | R 1 | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | St. anëtar | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S 1 | + | S 2 | = | 12 | |||||||||
| - | x 1 | + | S 1 | + | S 3 | = | 3 |
| x 1 | x 2 | S 1 | S 2 | S 3 | St. anëtar | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F - 13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
Qëllimi i shërbimit... Shërbimi është krijuar për zgjidhjen në internet të problemeve të programimit linear (LPP) duke përdorur metodën simplex në format e mëposhtme të shënimeve:
- në formën e një tabele simplex (metoda e transformimeve të Jordanit); forma bazë e regjistrimit;
- metoda e modifikuar simplex; në formë kolone; në formë rreshti.
Udhëzim. Zgjidhni numrin e variablave dhe numrin e linjave (numrin e kufizimeve). Zgjidhja që rezulton ruhet në një skedar Word dhe Excel.
Në këtë rast, mos merrni parasysh kufizimet e tipit x i ≥ 0. Nëse në detyrën për disa x i nuk ka kufizime, atëherë LPP duhet të sillet në CLP, ose të përdoret ky shërbim. Zgjidhja zbulon automatikisht përdorimin e M-metoda(metodë e thjeshtë me bazë artificiale) dhe Metoda Simplex me dy hapa.Me këtë kalkulator përdoren gjithashtu sa më poshtë:
Metoda grafike për zgjidhjen e LPP
Zgjidhja e problemit të transportit
Zgjidhja e lojës me matricë
Duke përdorur shërbimin në internet, mund të përcaktoni çmimin e një loje matrice (kufijtë e poshtëm dhe të sipërm), të kontrolloni praninë e një pike shale, të gjeni një zgjidhje për një strategji të përzier duke përdorur metodat e mëposhtme: minimaks, metoda simplex, grafike (gjeometrike) metoda, metoda e Brown.
Ekstremumi i një funksioni të dy ndryshoreve
Probleme me programimin dinamik
Shpërndani 5 lote homogjene mallrash midis tre tregjeve në mënyrë që të merrni të ardhurat maksimale nga shitja e tyre. Të ardhurat nga shitjet në çdo treg G (X) varen nga numri i pjesëve të shitura të mallrave X dhe janë paraqitur në tabelë.
| Vëllimi i mallrave X (në lote) | Të ardhurat G (X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
Algoritmi i metodës së thjeshtë përfshin hapat e mëposhtëm:
- Hartimi i planit të parë bazë. Kalimi në formën kanonike të problemit të programimit linear duke futur variabla shtesë të balancës jonegative.
- Kontrollimi i planit për optimalitet... Nëse ka të paktën një koeficient të rreshtit të indeksit më pak se zero, atëherë plani nuk është optimal dhe duhet të përmirësohet.
- Përcaktimi i kolonës dhe rreshtit kryesor... Nga koeficientët negativ të rreshtit të indeksit, zgjidhet më i madhi në vlerë absolute. Pastaj elementet e kolonës së anëtarëve të lirë të tabelës simplex ndahen në elementë të së njëjtës shenjë të kolonës kryesore.
- Ndërtimi i një plani të ri referimi... Kalimi në një plan të ri kryhet si rezultat i rillogaritjes së tabelës simplex duke përdorur metodën Jordan-Gauss.
Nëse është e nevojshme të gjendet ekstremi i funksionit objektiv, atëherë po flasim për gjetjen e vlerës minimale (F (x) → min, shikoni shembullin e zgjidhjes së minimizimit të funksionit) dhe vlerës maksimale ((F (x) → max, shikoni shembullin e zgjidhjes së maksimizimit të funksionit)
Zgjidhja ekstreme arrihet në kufirin e rajonit të zgjidhjeve të realizueshme në një nga kulmet e pikave të këndit të poligonit, ose në segmentin midis dy pikave të këndit ngjitur.
Teorema themelore e programimit linear... Nëse funksioni objektiv i LPP-së arrin një vlerë ekstreme në një pikë në rajonin e zgjidhjeve të realizueshme, atëherë ai e merr këtë vlerë në pikën e këndit. Nëse funksioni objektiv i LPP-së arrin vlerën e tij ekstreme në më shumë se një pikë qoshe, atëherë ai merr të njëjtën vlerë në cilindo nga kombinimet lineare konveks të këtyre pikave.
Thelbi i metodës simplex... Lëvizja në pikën optimale kryhet duke lëvizur nga një pikë qoshe në atë fqinje, e cila është më afër dhe më e shpejtë me X opt. Një skemë e tillë për numërimin e pikave, quhet metoda simplex, sugjeruar nga R. Danzig.
Pikat e këndit karakterizohen nga m variabla bazë, prandaj kalimi nga një pikë qoshe në atë fqinje mund të kryhet duke ndryshuar në bazë vetëm një variabël bazë në një variabël nga jobaza.
Zbatimi i metodës simplex, për shkak të veçorive dhe formulimeve të ndryshme të problemeve LP, ka modifikime të ndryshme.
Ndërtimi i tabelave simplex vazhdon derisa të merret një zgjidhje optimale. Si të përdorim një tabelë Simplex për të përcaktuar se zgjidhja e një problemi të programimit linear është optimale?
Nëse rreshti i fundit (vlerat e funksionit objektiv) nuk përmban elemente negative, atëherë do të gjejë planin optimal.
Vërejtje 1. Nëse një nga variablat bazë është e barabartë me zero, atëherë pika ekstreme që i përgjigjet një zgjidhjeje të tillë bazë është e degjeneruar. Degjenerimi ndodh kur ka paqartësi në zgjedhjen e një udhëzuesi të linjës. Mund të mos e vini re fare degjenerimin e problemit nëse zgjidhni një linjë tjetër si udhëzues. Në rast paqartësie, zgjidhni rreshtin me indeksin më të ulët për të shmangur lakimin.
Vërejtje 2. Supozoni se në një pikë ekstreme të gjitha diferencat e simpleksit janë jonegative D k ³ 0 (k = 1..n + m), d.m.th. fitohet një zgjidhje optimale dhe ekziston një A k - vektor jo bazë për të cilin D k = 0. Atëherë maksimumi arrihet të paktën në dy pika, d.m.th. ekziston një optimum alternativ. Nëse e futim këtë ndryshore x k në bazë, vlera e funksionit objektiv nuk do të ndryshojë.
Vërejtje 3. Zgjidhja e problemit të dyfishtë gjendet në tabelën e fundit të Simpleksit. Komponentët m të fundit të vektorit të diferencave të simpleksit (në kolonat e variablave të balancës) janë zgjidhja optimale për problemin e dyfishtë. Vlerat e funksioneve objektive të problemeve të drejtpërdrejta dhe të dyfishta në pikat optimale përkojnë.
Vërejtje 4. Gjatë zgjidhjes së problemit të minimizimit, në bazë futet një vektor me diferencën më të madhe pozitive të Simpleksit. Më tej, i njëjti algoritëm zbatohet si për problemin e maksimizimit.
Nëse kushti "Është e nevojshme që lënda e parë e llojit III të konsumohet plotësisht", atëherë kushti përkatës është barazia.
Probleme të programimit linear. Është në një strukturë vijuese që karakterizon procesin në shqyrtim. Zgjidhja ndahet në tre faza kryesore: zgjedhja e variablave, ndërtimi i një sistemi kufizimesh dhe kërkimi i funksionit objektiv.
Bazuar në këtë ndarje, kushti problemor mund të riformulohet si vijon: ekstremi i funksionit objektiv Z (X) = f (x1, x2, ..., xn) → max (min) dhe ndryshoret përkatëse, nëse është dihet se ato plotësojnë sistemin e kufizimeve: Φ_i ( x1, x2,…, xn) = 0 për i = 1, 2,…, k; Φ_i (x1, x2,…, xn)) 0 për i = k + 1 , k + 2,…, m.
Sistemi i kufizimeve duhet të sillet në formën kanonike, d.m.th. në një sistem ekuacionesh lineare, ku numri i variablave është më i madh se numri i ekuacioneve (m> k). Në këtë sistem sigurisht që do të ketë variabla që mund të shprehen në terma të variablave të tjerë dhe nëse nuk është kështu, atëherë ato mund të futen artificialisht. Në këtë rast, të parët quhen bazë ose bazë artificiale, dhe të dytat quhen të lira.
Është më e përshtatshme të merret në konsideratë metoda simplex duke përdorur një shembull specifik. Le të jepet një funksion linear f (x) = 6x1 + 5x2 + 9x3 dhe një sistem kufizimesh: 5x1 + 2x2 + 3x3 ≤ 25; x1 + 6x2 + 2x3 ≤ 20; 4x1 + 3x3 ≤ 18. Kërkohet për të gjetur. vlera maksimale e funksionit f (x).
Zgjidhja Në fazën e parë, specifikoni zgjidhjen fillestare (mbështetëse) të sistemit të ekuacioneve në mënyrë absolutisht arbitrare, e cila duhet të plotësojë sistemin e caktuar të kufizimeve. Në këtë rast kërkohet futja e një artificiale, d.m.th. variablat bazë x4, x5 dhe x6 si më poshtë: 5x1 + 2x2 + 3x3 + x4 = 25; x1 + 6x2 + 2x3 + x5 = 20; 4x1 + 3x3 + x6 = 18.
Siç mund ta shihni, pabarazitë janë konvertuar në barazi falë variablave të shtuar x4, x5, x6, të cilat janë vlera jo negative. Kështu, ju e keni sjellë sistemin në formën kanonike. Ndryshorja x4 shfaqet në ekuacionin e parë me koeficient 1, dhe në dy - me koeficient 0, e njëjta gjë vlen edhe për variablat x5, x6 dhe ekuacionet përkatëse, që i përgjigjet përcaktimit të bazës.
Ju keni përgatitur sistemin dhe keni gjetur zgjidhjen fillestare të mbështetjes - X0 = (0, 0, 0, 25, 20, 18). Tani paraqitni koeficientët e variablave dhe termat e lirë të ekuacioneve (numrat në të djathtë të shenjës "=") në formën e një tabele për të optimizuar llogaritjet e mëtejshme (shih Fig.).
Thelbi i metodës simplex është ta sjellë këtë tabelë në një formë të tillë në të cilën të gjitha shifrat në rreshtin L do të jenë vlera jo negative. Nëse rezulton se kjo është e pamundur, atëherë sistemi nuk ka fare një zgjidhje optimale. Së pari, zgjidhni elementin më të vogël të kësaj rreshti, ky është -9. Numri është në kolonën e tretë. Shndërroni variablin përkatës x3 në atë bazë. Për ta bërë këtë, ndani rreshtin me 3 për të marrë 1 në qelizë.
Tani ju duhet që qelizat të kthehen në 0. Për ta bërë këtë, zbritni nga shifrat përkatëse të rreshtit të tretë me 3. Nga elementët e rreshtit të dytë - elementët e të tretës, shumëzuar me 2. Dhe, së fundi, nga elementet e vijës L - shumëzuar me (-9). Ju morët zgjidhjen e dytë të referencës: f (x) = L = 54 në x1 = (0, 0, 6, 7, 8, 0).
