Nëse keni nevojë të zgjidhni një problem të programimit linear duke përdorur tabela simplex, atëherë shërbimi ynë online do t'ju ndihmojë shumë. Metoda simplex nënkupton një numërim sekuencial të të gjitha kulmeve të diapazonit të vlerave të pranueshme për të gjetur kulmin ku funksioni merr një vlerë ekstreme. Në fazën e parë, gjendet një zgjidhje, e cila përmirësohet në çdo hap pasues. Kjo zgjidhje quhet bazë. Këtu është një sekuencë veprimesh kur zgjidhni një problem të programimit linear duke përdorur metodën simplex:
Hapi i parë. Në tabelën e përpiluar, para së gjithash, duhet të shikoni kolonën me anëtarë të lirë. Nëse ka elemente negative në të, atëherë është e nevojshme të vazhdohet në hapin e dytë, nëse jo, atëherë në të pestin.
Hapi i dytë. Në hapin e dytë, është e nevojshme të vendoset se cila variabël të përjashtohet nga baza dhe cila të përfshihet, në mënyrë që të rillogaritet tabela simplex. Për ta bërë këtë, shikoni nëpër kolonën me anëtarë të lirë dhe gjeni një element negativ në të. Vija me element negativ do të quhet vija kryesore. Në të gjejmë elementin maksimal negativ në vlerë absolute, kolonën përkatëse - ndjekësin. Nëse ka vlera negative midis anëtarëve të lirë, por jo në rreshtin përkatës, atëherë një tabelë e tillë nuk do të ketë zgjidhje. Duke ndryshuar në rreshtin kryesor, ai në kolonën e anëtarit të lirë përjashtohet nga baza dhe ndryshorja që korrespondon me kolonën kryesore përfshihet në bazë.
Tabela 1.
| variablat bazë | Anëtarë të lirë në kufizime | Variabla pa bazë | |||||
| x 1 | x 2 | ... | x l | ... | x n | ||
| x n + 1 | b 1 | një 11 | një 12 | ... | një 1l | ... | një 1n |
| x n + 2 | b 2 | një 21 | një 22 | ... | një 2l | ... | një 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n + r | b2 | një r1 | një r2 | ... | një rl | ... | një rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n + m | b m | një m1 | një m2 | ... | një ml | ... | një mn |
| F (x) max | F 0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
Hapi i tretë. Në hapin e tretë, ne rillogaritim të gjithë tabelën Simplex duke përdorur formula të veçanta, këto formula mund të shihen duke përdorur.
Hapi i katërt. Nëse, pas rillogaritjes, elementet negative mbeten në kolonën e anëtarëve të lirë, atëherë shkoni në hapin e parë, nëse nuk ka të tillë, atëherë në të pestin.
Hapi i pestë. Nëse keni arritur në hapin e pestë, atëherë keni gjetur një zgjidhje që është e pranueshme. Megjithatë, kjo nuk do të thotë se është optimale. Do të jetë optimale vetëm nëse të gjithë elementët në rreshtin F janë pozitivë. Nëse nuk është kështu, atëherë është e nevojshme të përmirësohet zgjidhja, për të cilën gjejmë rreshtin dhe kolonën kryesore për rillogaritjen e radhës sipas algoritmit të mëposhtëm. Fillimisht, ne gjejmë numrin minimal negativ në rreshtin F, duke përjashtuar vlerën e funksionit. Kolona me këtë numër do të jetë ajo kryesore. Për të gjetur rreshtin kryesor, gjejmë raportin e anëtarit të lirë përkatës dhe elementit nga kolona kryesore, me kusht që ato të jenë pozitive. Marrëdhënia minimale do t'ju lejojë të përcaktoni rreshtin kryesor. Ne rillogaritim tabelën përsëri duke përdorur formulat, d.m.th. shkoni në hapin 3.
Metoda grafike është mjaft e thjeshtë dhe intuitive për zgjidhjen e problemeve LP me dy variabla. Ajo bazohet në gjeometrike përfaqësimi i zgjidhjeve të realizueshme dhe CF e problemit.
Secila nga pabarazitë e problemit LP përcaktohet në planin koordinativ (NS 1 ,NS 2 ) disa gjysmë rrafsh (Fig. 1), dhe sistemi i pabarazive në tërësi është kryqëzimi i rrafsheve përkatëse. Bashkësia e pikave të kryqëzimit të këtyre gjysmërrafsheve quhet zona e lejuarvendimet(ODR). SDT përfaqëson gjithmonë konveks figura, d.m.th. e cila ka vetinë e mëposhtme: nëse kësaj figure i përkasin dy pika A dhe B, atëherë i takon i gjithë segmenti AB. ODR mund të përfaqësohet grafikisht nga një shumëkëndësh konveks, një rajon poligonal konveks i pakufizuar, një segment, një rreze, një pikë. Në rastin e mospërputhjes së sistemit të kufizimeve, problemi SDT është një grup bosh.
shënim № 1. E gjithë sa më sipër vlen edhe për rastin kur sistemi i kufizimeve (1.1) përfshin barazitë, pasi çdo barazi
a il x 1 + a i 2 x 2 = b
mund të përfaqësohet si një sistem i dy pabarazive (Fig. 1)
A dhe 2 x 2<Ь 1э +a i 2 x 2 >bj.
CF L (x) = c1x1 + c2x2 me një vlerë fikse L (x) = L përcakton një vijë të drejtë c1x1 në plan + c2x2 = L. Duke ndryshuar vlerat e L, marrim një familje të drejtëzave paralele, të quajtur linjat e nivelit.
Kjo për faktin se një ndryshim në vlerën e L do të sjellë një ndryshim vetëm në gjatësinë e segmentit të prerë nga vija e nivelit në boshtin x2 (ordinata fillestare), dhe pjerrësia e vijës së drejtë tgа = - do të mbetet konstante (Fig. 1).
Prandaj, për ta zgjidhur atë, do të mjaftojë të ndërtoni një nga linjat e nivelit, duke zgjedhur në mënyrë arbitrare vlerën e L.
Vektori C = (c1; c2) me koordinata nga koeficientët CF në x1 dhe x2 është pingul me secilën prej vijave të nivelit (shih Fig. 1). Drejtimivektori С përkon me drejtim rritet CF, e cila është një pikë e rëndësishme për zgjidhjen e problemeve. Drejtimi duke u pakësuar CF e kundërtadrejtimi i vektorit C.
Thelbi i metodës grafike është si më poshtë. Në drejtimin (kundër drejtimit) të vektorit C në ODR, kërkimi për pikën optimale X = (x1; x2 ). Pika optimale është pika nëpër të cilën kalon linja e nivelit L max (L min), që i përgjigjet vlerës më të madhe (më të vogël) të funksionit L (x). Zgjidhja optimale gjendet gjithmonë në kufirin e ODR, për shembull, në kulmin e fundit të poligonit ODR nëpër të cilin kalon vija e synuar, ose në të gjithë anën e saj.
Kur kërkoni një zgjidhje optimale për problemet e LP, situatat e mëposhtme janë të mundshme: ekziston një zgjidhje unike për problemin; ka një numër të pafund zgjidhjesh (optium alternativ); CF nuk është i kufizuar; zona e zgjidhjeve të pranueshme është pika e vetme; detyra nuk ka zgjidhje.
Zona e vlefshme - gjysmë rrafsh
Foto 1
1.2. Metodologjia e zgjidhjes së problemeve të LP me metodën grafike
I. Në kufizimet e problemës zëvendësoni shenjat e pabarazive me shenjat e barazive ekzakte dhe ndërtoni vijat përkatëse.
II. Gjeni dhe ngjyrosni gjysmërrafshet e zgjidhura nga secili prej kufizimeve të pabarazisë në problem. Për ta bërë këtë, zëvendësoni koordinatat e një pike [për shembull, (0; 0)] në një pabarazi specifike dhe kontrolloni vërtetësinë e pabarazisë që rezulton.
Nëse pabarazia është e vërtetë, pastaj është e nevojshme të hijezohet gjysma e rrafshit që përmban pikën e dhënë; ndryshe (pabarazia është e rreme) është e nevojshme të hijezohet gjysmërrafshi që nuk përmban pikën e dhënë.
Që nga x1 dhe x2 duhet të jetë jo negative, atëherë vlerat e tyre të lejuara do të jenë gjithmonë mbi boshtin x 1 dhe në të djathtë të boshtit x2, d.m.th. në kuadratin e 1-rë.
Kufizimet e barazisë lejojnë vetëm ato pika që shtrihen në vijën përkatëse, kështu që zgjidhni linja të tilla në grafik.
Përcaktoni një IDD si pjesë të avionit që i përket të gjitha zonave të lejuara në të njëjtën kohë dhe zgjidhni atë. Në mungesë të një IDT, detyra jo ka zgjidhje, për të cilat nxjerrin përfundimin e duhur.
Nëse ODR nuk është një grup bosh, atëherë ndërtoni linjën e synuar, d.m.th. ndonjë nga linjat e nivelit me 1 x 1 + me 2 x 2 = L, ku L është një numër arbitrar, për shembull, një shumëfish i 1 dhe me 2, d.m.th. i përshtatshëm për të bërë llogaritjet. Metoda e ndërtimit është e ngjashme me ndërtimin e kufizimeve të drejtpërdrejta.
V. Ndërtoni një vektor C = (c 1, c 2), i cili fillon në pikën (0; 0), përfundon në pikën (c 1, c 2). Nëse vija e synuar dhe vektori C janë ndërtuar në mënyrë korrekte, atëherë ato do të jenë pingul.
Vi. Kur kërkoni për max DF, lëvizni vijën e synuar në drejtim vektor C, kur kërkoni për min CF - kundër drejtimit vektor C. E fundit përgjatë lëvizjes, maja e ODR do të jetë pika maksimale ose min e CF. Nëse një pikë (pika) e tillë nuk ekziston, atëherë nxirrni një përfundim rreth pakufizimi i CF mbi shumë plane lart (kur kërkoni për kontroll) ose më poshtë (kur kërkoni për min).
Përcaktoni koordinatat e pikës max (min) DF X = (x1 *; x2 * ) dhe llogaritni vlerën e CF l (x *). Për të llogaritur koordinatat e pikës optimale X *, zgjidhni sistemin e ekuacioneve të drejtëzave në kryqëzimin e të cilave ndodhet X *.
Problemi 1
Le të gjejmë zgjidhjen optimale të problemit, modeli matematik i së cilës ka formën
L (X) = 3x 1 + 2x 2 → max
x 1 + 2 x 2< 6, (1)
2x 1 + x 2< 8, (2)
X 1 + x 2<1, (3)
x 2< 2, (4)
x 1> 0, x 2> 0.
Le të ndërtojmë vija kufizimesh, për të cilat llogarisim koordinatat e pikave të kryqëzimit të këtyre drejtëzave me boshtet koordinative (Fig. 2).
x 1 + 2x 2 = 6, (1)
2x1 + x2 = 8, (2)
(1) x1 = 0, x1 = 6, x2 = 3, x2 = 0,
(2) x1 = 0, x1 = 4, x2 = 8, x2 = 0,
(3) x1 = 0, x1 = -1, x2 = 1, x2 = 0,
Vija e drejtë (4) kalon nëpër pikën x 2 = 2 paralel me boshtin L (X).
Oriz. 2. Zgjidhja grafike e problemës
Le të përcaktojmë ODR. Për shembull, zëvendësoni pikën (0; 0) në kufizimin origjinal (3), marrim 0< 1, что является истинным неравенством, поэтому стрелкой (или штрихованием) обозначим полуплоскость, që përmban pika (0; 0), d.m.th. ndodhet djathtas dhe poshtë vijës së drejtë (3). Në mënyrë të ngjashme, ne përcaktojmë gjysmë-rrafshët e pranueshëm për kufizimet e mbetura dhe i tregojmë ato me shigjeta në kufizimet e drejtpërdrejta përkatëse (Fig. 2). Një zonë e përbashkët e lejuar nga të gjitha kufizimet, d.m.th. ODR është shumëkëndëshi ABCDEF.
Vija e synuar mund të vizatohet sipas ekuacionit
Ndërtojmë vektorin C nga pika (0; 0) deri në pikën (3; 2). Pika E është kulmi i fundit i poligonit të zgjidhjeve të realizueshme ABCDEF, nëpër të cilin kalon vija e synuar, duke lëvizur drejt vektori C. Prandaj, E është pika maksimale e CF. Le të përcaktojmë koordinatat e pikës E nga sistemi i ekuacioneve të kufizimeve të drejtpërdrejta (1) dhe (2)
X1 + 2x 2 = 6, (1) x1 = 10/3 = 3 1/3, x2 = 4/3 = 1 1/3
2 X1 + x 2 = 8, (2) E 3 1/3; 1 1/3
Vlera maksimale e CF është L (E) = 3 * 10/3 + 2 * 4/3 = 12 2/3
Le të shqyrtojmë fillimisht rastin më të thjeshtë, kur saktësisht dy variabla janë përfshirë në LPP:
Secila nga pabarazitë (a) - (b) të sistemit të kufizimeve të problemës (3.8) përcakton gjeometrikisht një gjysmërrafsh me vija kufitare, përkatësisht X 1 = 0 dhe X 2 = 0. Secila prej vijave kufitare e ndan rrafshin x 1 Ox 2 në dy gjysmërrafshe. Të gjitha zgjidhjet e pabarazisë fillestare qëndrojnë në një nga gjysmërrafshët e formuar (të gjitha pikat e gjysmëplanit) dhe, për rrjedhojë, kur koordinatat e ndonjë prej pikave të saj zëvendësohen në pabarazinë përkatëse, ai e kthen atë në një identitet të vërtetë. . Duke marrë parasysh këtë, përcaktohet gjysëm rrafshi në të cilin qëndrojnë zgjidhjet e pabarazisë, d.m.th. duke zgjedhur çdo pikë nga çdo gjysmë rrafsh dhe duke zëvendësuar koordinatat e saj në pabarazinë përkatëse. Nëse pabarazia vlen për një pikë të caktuar, atëherë ajo vlen për çdo pikë tjetër nga i njëjti gjysmëplan. Përndryshe, zgjidhjet e pabarazisë qëndrojnë në një gjysmë rrafsh tjetër.
Nëse sistemi i pabarazive (a) - (b) është i qëndrueshëm, atëherë domeni i zgjidhjeve të tij është grupi i pikave që u përkasin të gjithë gjysmërrafsheve të treguara. Meqenëse grupi i pikave të kryqëzimit të këtyre gjysmëplanëve është konveks, fusha e zgjidhjeve të realizueshme të problemit (3.8) është një grup konveks, i cili quhet poligon i zgjidhjeve (termi i paraqitur më parë "politop i zgjidhjeve" përdoret zakonisht nëse n 3). Brinjët e këtij shumëkëndëshi shtrihen në vija të drejta, ekuacionet e të cilave janë marrë nga sistemi origjinal i kufizimeve duke zëvendësuar shenjat e pabarazisë me shenja të barazive ekzakte.
Kështu, LPP fillestare konsiston në gjetjen e një pike të poligonit vendimtar në të cilën funksioni objektiv F merr vlerën maksimale (minimale).
Kjo pikë ekziston kur shumëkëndëshi i zgjidhjes nuk është bosh dhe funksioni objektiv është i kufizuar nga lart mbi të. Në këto kushte, në një nga kulmet e poligonit vendimtar, funksioni objektiv merr vlerën e tij maksimale. Për të përcaktuar këtë kulm, ndërtohet një vijë e nivelit L: c 1 x 1 + c 2 x 2 = h (ku h është një farë konstante), pingul me vektorin e gradientit dhe kalon nëpër poligonin e zgjidhjes dhe lëvizë atë paralelisht përgjatë gradientit. vektor derisa, derisa të kalojë nëpër pikën e tij të fundit të përbashkët të kryqëzimit me shumëkëndëshin e zgjidhjeve (kur ndërtohet një vektor gradient, një pikë lihet jashtë (c 1; c 2) në rrafshin x 1 Ox 2 dhe vizatohet një segment i drejtuar tek ajo nga origjina e koordinatave). Koordinatat e pikës së specifikuar përcaktojnë planin optimal për këtë detyrë.
Duke përmbledhur të gjitha sa më sipër, ne paraqesim një algoritëm për metodën grafike për zgjidhjen e LPP.
Algoritmi i metodës grafike për zgjidhjen e LPP
1. Ndërtoni një shumëkëndësh zgjidhjesh të dhëna nga sistemi i kufizimeve të LPP-së origjinale.
2. Nëse shumëkëndëshi i ndërtuar i zgjidhjeve është një grup bosh, atëherë LPP-ja origjinale nuk ka zgjidhje. Përndryshe, ndërtoni një gradient-vektor dhe vizatoni një vijë arbitrare të nivelit L, duke lëvizur e cila, kur e zgjidh problemin në maksimum në drejtim të vektorit (ose në drejtim të kundërt për problemin me minimumin), përcakton pikën ekstreme. të shumëkëndëshit të zgjidhjeve, ku arrihet maksimumi (minimumi) i funksionit objektiv të problemës ...
3. Njehsoni koordinatat e pikës optimale të gjetur duke zgjidhur sistemin e ekuacioneve të dy vijave kufitare që priten në të.
4. Zëvendësimi i zgjidhjes optimale të gjetur në funksionin objektiv të problemit, llogaritet vlera optimale e saj, dmth.
Kur ndërtohet grafikisht grupi i zgjidhjeve të pranueshme të LPP (poligoni i zgjidhjes), situatat e mëposhtme janë të mundshme.
Modelimi matematik në kërkimin e operacioneve është, nga njëra anë, një proces shumë i rëndësishëm dhe kompleks, dhe nga ana tjetër, praktikisht nuk i nënshtrohet formalizimit shkencor. Vini re se përpjekjet e përsëritura për të theksuar parimet e përgjithshme të krijimit të modeleve matematikore çuan ose në shpalljen e rekomandimeve të një natyre shumë të përgjithshme që janë të vështira për t'u zbatuar për zgjidhjen e problemeve specifike, ose, anasjelltas, në shfaqjen e recetave që janë në të vërtetë të zbatueshme vetëm. në një gamë të ngushtë problemesh. Prandaj, njohja me teknikën e modelimit matematik në shembuj specifik duket të jetë më e dobishme.
Problemet e programimit linear mund të zgjidhen me metodat e mëposhtme:
algoritmi i Floydit;
Algoritmi i Dijkstra-s mbi grafikë;
metoda grafike;
metoda e tabelës simplex etj.
Algoritmi për zgjidhjen e problemeve të programimit linear me metodën e Dijkstra-s në grafikë.
Në zbatimin më të thjeshtë, mund të përdorni një grup numrash për të ruajtur numrat d [i] dhe një grup variablash Boolean për të ruajtur përkatësinë e një elementi në grupin U.
Në fillim të algoritmit, distanca për kulmin fillestar vendoset e barabartë me zero, dhe të gjitha distancat e tjera plotësohen me një numër të madh pozitiv (më i madh se shtegu maksimal i mundshëm në grafik). Vargu i flamujve është i mbushur me zero. Pastaj fillon cikli kryesor.
Në çdo hap të ciklit, është e nevojshme të gjendet kulmi U me distancën minimale dhe flamurin e barabartë me zero. Më pas duhet të vendosim flamurin në të në 1 dhe të kontrollojmë të gjitha kulmet U ngjitur me të. Nëse distanca është më e madhe se shuma e distancës nga kulmi aktual dhe gjatësia e skajit, atëherë është e nevojshme ta zvogëlojmë atë. . Cikli përfundon kur flamujt e të gjitha kulmeve bëhen të barabartë me 1, ose kur të gjitha kulmet kanë një flamur 0. Rasti i fundit është i mundur nëse dhe vetëm nëse grafiku G nuk është i lidhur.
Një metodë për zgjidhjen e problemeve të programimit linear duke përdorur një metodë grafike.
Metoda grafike për zgjidhjen e problemeve të programimit linear bazohet në interpretimin gjeometrik të problemeve të programimit linear dhe përdoret kryesisht në zgjidhjen e problemeve në hapësirën dydimensionale dhe vetëm disa problemeve në hapësirën tredimensionale, pasi është mjaft e vështirë të ndërtohet një poliedron i zgjidhje, e cila formohet si rezultat i kryqëzimit të gjysmëhapësirave. Në përgjithësi është e pamundur të përshkruhet grafikisht problemi i një hapësire me dimensione më të mëdha se tre.
Lëreni problemin e programimit linear të jepet në një hapësirë dy-dimensionale, domethënë, kufizimet përmbajnë dy ndryshore.
Vlera minimale e funksionit përcaktohet me formulën (1).
(1)
Kufizimet përfaqësohen nga formula (2) dhe (3).
(2)
(3)
Le të jetë konsistent sistemi (2) në kushtin (3). Secila nga pabarazitë nga sistemet (2) dhe (3) përcakton një gjysmëplan me vija kufitare të përfaqësuara me formulën (4):
Funksioni linear (1) në vlera fikse të Z është ekuacioni i një vije të drejtë: 
Është e nevojshme të ndërtohet shumëkëndëshi i zgjidhjeve të sistemit të kufizimeve (2) dhe grafiku i funksionit linear (1) në Z = 0. Atëherë problemi i caktuar i programimit linear mund të interpretohet si më poshtë:
Gjeni pikën e shumëkëndëshit të zgjidhjes në të cilën është drejtëza 
referenca një dhe funksioni Z në të njëjtën kohë arrin një minimum.
vlerat 
ulje në drejtim të vektorit 
, pra, drejtëza Z = 0 duhet të zhvendoset paralelisht me vetveten në drejtim të vektorit N.
Nëse shumëkëndëshi i zgjidhjes është i kufizuar, atëherë vija e drejtë bëhet vijë mbështetëse dy herë në lidhje me shumëkëndëshin e zgjidhjes (në pikat B dhe E), me vlerën minimale në pikën E. Koordinatat e pikës 
duhet gjetur duke zgjidhur sistemin e ekuacioneve për drejtëzat DE dhe EF.
Nëse shumëkëndëshi i zgjidhjes është një rajon shumëkëndor i pakufizuar, atëherë janë të mundshme dy raste.
Rasti 1. Direkt 
duke lëvizur në drejtim të vektorit N ose të kundërt me të, e pret vazhdimisht shumëkëndëshin zgjidhje dhe në asnjë moment nuk ka referencë për të. Në këtë rast, funksioni linear nuk kufizohet në poligonin e zgjidhjes as nga lart as nga poshtë.
Rasti 2. Një vijë e drejtë, që lëviz përreth, megjithatë bëhet një mbështetje në lidhje me shumëkëndëshin zgjidhje. Pastaj, në varësi të llojit të rajonit, funksioni linear mund të kufizohet nga lart dhe i pakufizuar nga poshtë, i kufizuar nga poshtë dhe i pakufishëm nga lart, ose i kufizuar nga poshtë dhe nga lart.
Për zgjidhjen e këtij problemi u zgjodh metoda më e njohur dhe më e përdorur në praktikë për zgjidhjen e problemeve të programimit linear është metoda Simplex. Pavarësisht se metoda Simplex është një algoritëm mjaft efektiv që ka treguar rezultate të mira në zgjidhjen e problemeve të programimit linear të aplikuar, ai është një algoritëm me kompleksitet eksponencial.
Metoda simplex e problemeve të programimit linear bazohet në kalimin nga një plan bazë në tjetrin, në të cilin vlera e funksionit objektiv rritet ose zvogëlohet.
Përpara përpilimit të një tabele simplex, detyra duhet të transformohet, sistemi i kufizimeve të sillet në një formë bazë të pranueshme, me ndihmën e së cilës variablat bazë duhet të përjashtohen nga funksioni objektiv, siç tregohet në figurën 1.
Figura 1 - Transformimi fillestar i sistemit të kufizimeve
Këtu, për saktësinë e shënimit, supozohet se variablat X1, X2, ..., Xr mund të merren si variabla bazë dhe se b1, b2, ..., br ≥ 0 (zgjidhja bazë përkatëse është referenca një).
Për të përpiluar një tabelë simplex në të gjitha barazitë në deklaratën e problemit, termat që përmbajnë variablat transferohen në anën e majtë, ato të lira lihen në të djathtë, d.m.th. problemi është shkruar në formën e një sistemi barazish siç tregohet në figurën 2.
Figura 2 - Transformimi i sistemit të pabarazive
Algoritmi për kalimin në tabelën tjetër është si më poshtë:
skanohet rreshti i fundit i tabelës (indeksit) dhe ndër koeficientët e këtij rreshti (duke përjashtuar kolonën e anëtarëve të lirë) zgjidhet numri më i vogël negativ kur gjendet max, ose numri më i madh pozitiv kur gjendet min. Nëse nuk ka asnjë, atëherë zgjidhja bazë origjinale është optimale dhe kjo tabelë është e fundit;
kolona e tabelës skanohet që korrespondon me koeficientin e zgjedhur negativ (pozitiv) në rreshtin e fundit - kolona kryesore, dhe koeficientët pozitivë janë zgjedhur në këtë kolonë. Nëse nuk ka asnjë, atëherë funksioni objektiv është i pakufizuar në gamën e vlerave të pranueshme të variablave dhe problemi nuk ka zgjidhje;
ndër koeficientët e përzgjedhur të kolonës zgjidhet ai për të cilin vlera absolute e raportit të anëtarit të lirë përkatës (që ndodhet në kolonën e anëtarëve të lirë) me këtë element është minimale. Ky koeficient quhet zgjidhës dhe vija në të cilën ndodhet është kyçe;
në të ardhmen, ndryshorja bazë që korrespondon me rreshtin e elementit lejues duhet të shndërrohet në kategorinë e atyre të lira dhe ndryshorja e lirë që korrespondon me kolonën e elementit lejues duhet të futet në numrin e atyre bazë. Është ndërtuar një tabelë e re që përmban emrat e rinj të variablave bazë:
ne do të ndajmë çdo element të linjës kryesore (duke përjashtuar kolonën e anëtarëve të lirë) në një element zgjidhës dhe do t'i shkruajmë vlerat e marra në rreshtin me variablin bazë të ndryshuar të tabelës së re Simplex.
rreshti i elementit zgjidhës ndahet me këtë element dhe vargu që rezulton shkruhet në tabelën e re në të njëjtin vend.
në tabelën e re, të gjithë elementët e kolonës kryesore = 0, përveç kolonës së prerjes, është gjithmonë e barabartë me 1.
kolona me 0 në rreshtin kyç do të jetë e njëjtë në tabelën e re.
një rresht që ka një 0 në kolonën kryesore do të jetë i njëjtë në tabelën e re.
në pjesën tjetër të qelizave të tabelës së re, shkruhet rezultati i transformimit të elementeve të tabelës së vjetër, siç tregohet në figurën 3.
Figura 3 - Hartimi i një elementi të ri në një tabelë simplex
Si rezultat, fitohet një tabelë e re simplex që korrespondon me zgjidhjen e re bazë.
Tani duhet të shikoni përmes vijës së funksionit objektiv (indeksi), nëse ai nuk përmban vlera negative (në problemin e gjetjes së vlerës maksimale), ose pozitive (në problemin e gjetjes së vlerës minimale), me përjashtim të ajo që qëndron ende (kolona e lirë), atëherë do të thotë se është marrë zgjidhja optimale. Përndryshe, shkoni te një tabelë e re simplex duke përdorur algoritmin e përshkruar më sipër.
Për të zgjidhur problemin e punës së kësaj lënde, u zgjodh drejtimi i problemit për shpërndarjen optimale të fondeve në ndërmarrje. Plani optimal ose zgjidhja optimale për një problem të programimit linear është një plan në të cilin vlera e synuar do të rritet (zvogëlohet).
Pas analizimit të informacionit të grumbulluar, u hartua një detyrë programimi linear për punëtorinë nr.8 në NefAZ OJSC, në transportuesin e bojës, mbi të cilin janë lyer pjesët. Është e nevojshme të pikturohet numri optimal i pjesëve për ndërrim të punës për të maksimizuar fitimin.
Për të zgjidhur më tej problemin, është e nevojshme të formulohet problema dhe modeli matematikor i problemës.
Programimi linear përdor një metodë grafike për të përcaktuar grupe konvekse (polyedron zgjidhje). Nëse problemi kryesor i programimit linear ka një dizajn optimal, atëherë funksioni objektiv merr një vlerë në një nga kulmet e poliedrit vendimtar (shih figurën).
Qëllimi i shërbimit... Me ndihmën e këtij shërbimi është e mundur të zgjidhet problemi i programimit linear me metodën gjeometrike në modalitetin online, si dhe të merret një zgjidhje për problemin e dyfishtë (për të vlerësuar optimalitetin e përdorimit të burimeve). Për më tepër, një shabllon zgjidhje është krijuar në Excel.
Udhëzim. Zgjidhni numrin e rreshtave (numrin e kufizimeve). Nëse numri i variablave është më shumë se dy, është e nevojshme ta çoni sistemin në SZLP (shih gjithashtu shembullin nr. 2). Nëse kufizimi është dyfish, për shembull, 1 ≤ x 1 ≤ 4, atëherë ndahet në dy: x 1 ≥ 1, x 1 ≤ 4 (d.m.th. numri i rreshtave rritet me 1).
Ju gjithashtu mund të ndërtoni një rajon të zgjidhjes së mundshme (ADR) duke përdorur këtë shërbim.
Me këtë kalkulator përdoren gjithashtu sa më poshtë:
Metoda e thjeshtë për zgjidhjen e LPP
Zgjidhja e problemit të transportit
Zgjidhja e lojës me matricë
Duke përdorur shërbimin në internet, ju 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
Llogaritja e kufijve
Zgjidhja e problemit të programimit linear me metodën grafike përfshin hapat e mëposhtëm:
- Linjat e drejta vizatohen në rrafshin X 1 0X 2.
- Përcaktohen gjysmë rrafshe.
- Përcaktoni shumëkëndëshin zgjidhje;
- Ndërtoni një vektor N (c 1, c 2), i cili tregon drejtimin e funksionit objektiv;
- Zhvendos funksionin e objektivit të drejtpërdrejtë c 1 x 2 + c 2 x 2= 0 në drejtim të vektorit N në pikën ekstreme të shumëkëndëshit zgjidhje.
- Llogariten koordinatat e pikës dhe vlera e funksionit objektiv në këtë pikë.
Nje shembull. Kompania prodhon dy lloje produktesh - P1 dhe P2. Për prodhimin e produkteve, përdoren dy lloje të lëndëve të para - C1 dhe C2. Çmimi me shumicë i një njësie prodhimi është i barabartë me: 5 NJM. për P1 dhe 4 njësi për P2. Konsumi i lëndëve të para për njësi prodhimi të tipit P1 dhe tipit P2 është dhënë në tabelë.
Tabela - Konsumi i lëndëve të para për prodhim
Kërkohet të përcaktohet:
Sa produkte të secilit lloj duhet të prodhojë kompania në mënyrë që të maksimizojë të ardhurat nga shitja e produkteve?
- Formuloni një model matematikor të një problemi të programimit linear.
- Zgjidhja e problemit të programimit linear në mënyrë grafike (për dy ndryshore).
Le të formulojmë një model matematikor të problemit të programimit linear.
x 1 - prodhimi i produkteve P1, njësi.
x 2 - prodhimi i produkteve P2, njësi.
x 1, x 2 ≥ 0
Kufijtë e burimeve
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6
Kufizimet e kërkesës
x 1 +1 ≥ x 2
x 2 ≤ 2
Funksioni objektiv
5x 1 + 4x 2 → maksimumi
Pastaj marrim LPP-në e mëposhtme:
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6
x 2 - x 1 ≤ 1
x 2 ≤ 2
x 1, x 2 ≥ 0
5x 1 + 4x 2 → maksimumi
Nëse numri i variablave në një problem të programimit linear është më shumë se dy, atëherë problemi reduktohet paraprakisht në një LPP standard.
→ maksimumi sipas kufizimeve:
x 1 + x 2 + x 3 = 12
2x 1 - x 2 + x 4 = 8
- 2x 1 + 2x 2 + x 5 = 10
F (X) = 3x 1 - 2x 2 + 5x 3 - 4x 5
Kalimi në SZLP.
| 1 | 1 | 1 | 0 | 0 | 12 |
| 2 | -1 | 0 | 1 | 0 | 8 |
| -2 | 2 | 0 | 0 | 1 | 10 |
Le ta reduktojmë sistemin në matricën e njësive me metodën e transformimeve të Jordanit.
x 1 + x 2 + x 3 = 12
2x 1 - x 2 + x 4 = 8
- 2x 1 + 2x 2 + x 5 = 10
x 3 = - x 1 - x 2 +12
x 4 = - 2x 1 + x 2 +8
x 5 = 2x 1 - 2x 2 +10
ose
Sistemi i pabarazive:
- x 1 - x 2 +12 ≥ 0
- 2x 1 + x 2 +8 ≥ 0
2x 1 - 2x 2 +10 ≥ 0
x 1 + x 2 ≤ 12
2x 1 - x 2 ≤ 8
- 2x 1 + 2x 2 ≤ 10
Karakteristikat e zgjidhjes së problemeve të programimit linear duke përdorur një metodë grafike
Shembulli # 1. Shkruani problemin në një formë standarde dhe zgjidheni atë grafikisht.f = x 1 + 13x 2 -x 3 + 2x 4 + 3x 5
-x 2 + x 3 -x 5 = -3
x 1 -4x 2 + 3x 3 -x 4 + 2x 5 = 3
4x 2 -x 3 + x 4 -x 5 = 6
Nga ekuacioni i parë shprehim x 5:
x 5 = -x 2 + x 3 +3
f = x 1 + 13x 2 -x 3 + 2x 4 +3 (-x 2 + x 3 +3)
x 1 -4x 2 + 3x 3 -x 4 +2 (-x 2 + x 3 +3) = 3
4x 2 -x 3 + x 4 - (- x 2 + x 3 +3) = 6
ose
f = x 1 + 10x 2 + 2x 3 + 2x 4 +9
x 1 -6x 2 + 5x 3 -x 4 = -3
5x 2 -2x 3 + x 4 = 9
Nga ekuacioni i dytë shprehim x 4:
x 4 = 9-5x 2 + 2x 3
dhe zëvendëso në të gjitha shprehjet:
f = x 1 + 6x 3 +27
x 1 -x 2 + 3x 3 = 6
Ne e marrim variablin x 2 si një variabël shtesë dhe e zëvendësojmë me shenjën "≥":
f = x 1 + 6x 3 + 27
x 1 + 3x 3 ≥6
Shembulli nr. 2
x 1 + x 2 + x 3 = 12
2x 1 - x 2 + x 4 = 8
- 2x 1 + 2x 2 + x 5 = 10
F (X) = 3x 1 - 2x 2 + 5x 3 - 4x 5
Kalimi në SZLP.
Matrica e zgjeruar e sistemit të kufizimeve-barazive të këtij problemi:
| 1 | 1 | 1 | 0 | 0 | 12 |
| 2 | -1 | 0 | 1 | 0 | 8 |
| -2 | 2 | 0 | 0 | 1 | 10 |
1. Ju mund të zgjidhni x 3 si variabël bazë.
2. Ju mund të zgjidhni x 4 si variabël bazë.
3. Ju mund të zgjidhni x 5 si variabël bazë.
Meqenëse sistemi ka një matricë njësi, ne marrim X = (3,4,5) si variabla bazë.
Ekuacionet përkatëse janë:
x 1 + x 2 + x 3 = 12
2x 1 - x 2 + x 4 = 8
- 2x 1 + 2x 2 + x 5 = 10
Le të shprehim variablat bazë në lidhje me pjesën tjetër:
x 3 = - x 1 - x 2 +12
x 4 = - 2x 1 + x 2 +8
x 5 = 2x 1 - 2x 2 +10
Le t'i zëvendësojmë ato në funksionin objektiv:
F (X) = 3x 1 - 2x 2 + 5 (- x 1 - x 2 +12) - 4 (2x 1 - 2x 2 +10)
ose
F (X) = - 10x 1 + x 2 +20 → max
Sistemi i pabarazive:
- x 1 - x 2 +12 ≥ 0
- 2x 1 + x 2 +8 ≥ 0
2x 1 - 2x 2 +10 ≥ 0
Ne e sjellim sistemin e pabarazive në formën e mëposhtme:
x 1 + x 2 ≤ 12
2x 1 - x 2 ≤ 8
- 2x 1 + 2x 2 ≤ 10
F (X) = - 10x 1 + x 2 +20 → max
Shembulli nr. 3. Krijoni një model matematikor të një problemi të programimit linear dhe gjeni një zgjidhje në mënyrë gjeometrike.
- Hartoni një sistem varësish (pabarazish) matematikore dhe një funksion objektiv.
- Vizatoni një interpretim gjeometrik të problemit.
- Gjeni zgjidhjen optimale.
- Kontroll analitik.
- Përcaktoni burimet thelbësore dhe jo thelbësore dhe tepricat e tyre.
- Përcaktoni vlerën e funksionit objektiv.
- Llogaritni vlerësimet e përcaktuara objektivisht.
- Hartoni raportin e qëndrueshmërisë.
