Një metodë grafike për zgjidhjen e problemeve të programimit linear. Metoda grafike për zgjidhjen e problemeve të programimit linear: diagramë dhe shembuj

Teori e shkurtër

Programimi linear është një pjesë e programimit matematikor që përdoret në zhvillimin e metodave për gjetjen e ekstremit të funksioneve lineare të disa variablave me kufizime lineare shtesë të vendosura mbi variablat. Sipas llojit të detyrave që do të zgjidhen, metodat e tij ndahen në universale dhe të veçanta. Çdo problem i programimit linear (LPP) mund të zgjidhet duke përdorur metoda universale. Metodat e veçanta marrin parasysh veçoritë e modelit të problemit, funksionin e tij objektiv dhe sistemin e kufizimeve. Një tipar i problemeve të programimit linear është se funksioni objektiv arrin ekstremin e tij në kufirin e rajonit të zgjidhjeve të realizueshme.

Metoda grafike për zgjidhjen e problemeve të programimit linear bën të mundur vizualizimin e strukturës së tyre, identifikimin e veçorive dhe hapjen e mënyrave për të studiuar vetitë më komplekse. Një problem i programimit linear me dy ndryshore mund të zgjidhet gjithmonë grafikisht. Megjithatë, tashmë në hapësirën tredimensionale, një zgjidhje e tillë bëhet më e ndërlikuar, dhe në hapësirat dimensioni i të cilave është më shumë se tre, një zgjidhje grafike, në përgjithësi, është e pamundur. Rasti i dy variablave nuk ka ndonjë rëndësi të veçantë praktike, por shqyrtimi i tij sqaron vetitë e kufizimeve të LPP-së, shpie në idenë e zgjidhjes së tij, bën të qarta gjeometrikisht mënyrat e zgjidhjes dhe mënyrat e zbatimit praktik të tyre.

Nëse kufizimet dhe funksioni objektiv përmbajnë më shumë se dy ndryshore, atëherë është e nevojshme (ose me metodën e përmirësimit sekuencial të zgjidhjes) - është universale dhe mund të përdoret për të zgjidhur çdo LPP. Për disa probleme të programimit linear të aplikuar, si p.sh., janë zhvilluar metoda të veçanta zgjidhjeje.

Një shembull i zgjidhjes së problemit

Detyrë

Ndërmarrja prodhon dy lloje produktesh: produktin 1 dhe produktin 2. Për prodhimin e një njësie të produktit 1, kërkohet të shpenzohen kg lëndë të para të llojit të parë, kg lëndë e parë e llojit të dytë, kg lëndë e parë. materiale të llojit të tretë. Për prodhimin e një njësie të produktit 2, kërkohet të shpenzohen kg të llojit të parë, lëndëve të para të llojit të dytë, lëndëve të para të llojit të tretë. Prodhimi sigurohet me lëndë të parë të çdo lloji në sasi përkatësisht kg, kg, kg. Çmimi i tregut i një njësie të produktit 1 është mijë rubla, dhe një njësi e produktit 2 është mijë rubla.

Kërkohet:

• Ndërtoni një model matematikor të problemit.
• Hartoni një plan për prodhimin e produkteve që siguron të ardhurat maksimale nga shitja e tyre duke përdorur një metodë grafike për zgjidhjen e problemit të programimit linear.

Për ta bërë zgjidhjen e problemit të programimit linear sa më të saktë dhe të saktë që të jetë e mundur, shumë njerëz porosisin me çmim të lirë një test në këtë faqe. Mund të lexoni më shumë detaje (si të lini një kërkesë, çmimet, kushtet, mënyrat e pagesës) në testin Blini programimin linear ...

Zgjidhja e problemit

Ndërtimi i modelit

Nëpërmjet dhe ne shënojmë numrin e produkteve të prodhuara të llojit 1 dhe 2.

Atëherë kufijtë e burimeve janë:

Përveç kësaj, në kuptimin e problemit

Funksioni objektiv i modelit ekonomik dhe matematikor, duke shprehur të ardhurat e marra nga shitja:

Ne marrim modelin ekonomik dhe matematikor të mëposhtëm:

Ndërtimi i rajonit të zgjidhjeve të realizueshme

Le të zgjidhim grafikisht problemin e programimit linear që rezulton:

Për të ndërtuar rajonin e zgjidhjeve të realizueshme, ne ndërtojmë në sistemin e koordinatave vijat kufitare që korrespondojnë me këto kufizime të pabarazisë:

Le të gjejmë pikat nëpër të cilat kalojnë vijat:

Zgjidhja për çdo pabarazi të sistemit të kufizimeve të LPP-së është një gjysmë rrafshi që përmban vijën kufitare dhe ndodhet në njërën anë të saj.

Për të përcaktuar një gjysmëplan, merrni ndonjë pikë, për shembull, që nuk i përket vijës së drejtë (1), zëvendësoni koordinatat (0; 0) në pabarazinë përkatëse. Sepse pabarazia është e vërtetë:

Fusha e zgjidhjes së pabarazisë së parë korrespondon me gjysmërrafshin e majtë

Merrni ndonjë pikë, për shembull, që nuk i përket vijës së drejtë (2), zëvendësoni koordinatat (0; 0) në pabarazinë përkatëse. Sepse pabarazia është e vërtetë:

Merrni ndonjë pikë, për shembull, që nuk i përket vijës së drejtë (3), zëvendësoni koordinatat (0; 0) në pabarazinë përkatëse. Sepse pabarazia është e vërtetë:

Fusha e zgjidhjes së pabarazisë së dytë korresponduese i korrespondon gjysmërrafshit të majtë

Zona e zgjidhjeve të pranueshme është figura.

Gjetja e një zgjidhjeje për problemin LP

Ndërtojmë një vektor, koordinatat e të cilit janë proporcionale me koeficientët e funksionit objektiv. Këtu është koeficienti i proporcionalitetit.

Vizatoni një vijë të nivelit pingul me vektorin e ndërtuar.

Lëvizni vijën e nivelit në drejtim të vektorit në mënyrë që të prekë zonën e zgjidhjeve të realizueshme në pikën ekstreme. Zgjidhja në maksimum është pika, koordinatat e së cilës gjenden si pikëprerje e drejtëzave (2) dhe (1).

Përgjigju

Kështu, është e nevojshme të prodhohen 56 artikuj të llojit të parë dhe 64 artikuj të llojit të dytë. Në këtë rast, të ardhurat nga shitja e produkteve do të jenë maksimale dhe do të arrijnë në 5104 njësi monetare.

Metoda e zgjidhjes grafike, nëse një problem me dy ndryshore ka kufizime lineare dhe funksioni objektiv është kuadratik, diskutohet në detaje këtu.
Faqja detajon zgjidhjen e një problemi të programimit linear duke përdorur metodën simplex, përveç kësaj, tregon ndërtimin e një problemi të programimit të dyfishtë linear dhe gjetjen e zgjidhjes së tij duke zgjidhur një problem të drejtpërdrejtë.

Problemi i transportit dhe metoda e potencialeve
Problemi i transportit, modeli i tij matematikor dhe metodat e zgjidhjes shqyrtohen në detaje - gjetja e planit të referencës me metodën e elementit minimal dhe gjetja e zgjidhjes optimale me metodën potenciale.

Programim konveks – metodë grafike
Është paraqitur një shembull i zgjidhjes së problemit të programimit konveks kuadratik me metodën grafike.

Në këtë mësim do të njihemi me metodën grafike të zgjidhjes problemet e programimit linear, domethënë probleme të tilla në të cilat kërkohet të gjendet një zgjidhje për një sistem ekuacionesh lineare dhe (ose) pabarazish (një sistem kufizimesh) në të cilat funksioni i qëllimit - një funksion linear - merr vlerën optimale.

Për faktin se qartësia e zgjidhjes grafike arrihet vetëm në rrafsh, me paraqitjen grafike të problemit mund të njihemi vetëm në hapësirë ​​dydimensionale. Ky paraqitje është i përshtatshëm për një sistem kufizimesh pabarazie me dy ndryshore ose për sisteme ekuacionesh në të cilat numri i variablave është 2 më shumë se numri i ekuacioneve, domethënë, numri i ndryshoreve të lira është dy.

Prandaj, metoda grafike ka një fushë zbatimi aq të ngushtë sa nuk mund të flitet për të si një metodë e veçantë për zgjidhjen e problemeve të programimit linear.

Sidoqoftë, për zhvillimin e paraqitjeve vizuale të zgjidhjeve të problemeve të programimit linear, metoda grafike është me interes të caktuar. Përveç kësaj, ju lejon të konfirmoni gjeometrikisht vlefshmërinë e teorema të programimit linear .

Bazat teorike të metodës grafike

Pra, një problem i programimit linear. Kërkohet gjetja e vlerave jo negative të variablave dhe plotësimi i sistemit të pabarazive

në të cilën forma lineare merr vlerën optimale.

Shembulli 3.

Shembulli 4. Zgjidh grafikisht një problem të programimit linear në të cilin kërkohet të gjendet minimumi i një funksioni nën kufizime

Ne vazhdojmë t'i zgjidhim problemet grafikisht së bashku

Deri më tani, gjetjet janë bazuar në faktin se grupi i zgjidhjeve për një problem të programimit linear është konfiguruar në mënyrë që zgjidhja optimale të jetë e fundme dhe unike. Tani le të shohim shembujt kur shkelet ky kusht. Në këta shembuj, poligoni i vendimit është ndërtuar siç tregohet në shembujt e mëparshëm, por le të ndalemi në veçoritë që i dallojnë këta shembuj të jashtëzakonshëm.

Shembulli 5. Zgjidh grafikisht një problem të programimit linear në të cilin kërkohet të gjendet maksimumi i një funksioni nën kufizime

Zgjidhje. Figura tregon: një zonë shumëplanëshe të pakufizuar të zgjidhjeve të këtij sistemi kufizimesh, vijën e nivelit fillestar (e zezë), një vektor (burgundy) që tregon drejtimin e lëvizjes së vijës së nivelit fillestar për të gjetur maksimumin e funksionit objektiv.

Është e lehtë të shihet se funksioni F mund të rritet pafundësisht për një sistem të caktuar kufizimesh, kështu që ne mund ta shkruajmë atë me kusht.

Shembulli 6. Zgjidh grafikisht një problem të programimit linear në të cilin kërkohet të gjendet maksimumi i një funksioni nën kufizime

Metoda më e thjeshtë dhe më intuitive e programimit linear (LP) është metoda grafike. Përdoret për të zgjidhur problemet LP me dy variabla. Konsideroni problemin LP në formën standarde:

max f (x 1 , x 2, ..., x n) = ,

, i = 1, 2, ..., m,

x j 0, j = 1, 2,…, n.

Ne kemi vënë n = 2 dhe ne do ta shqyrtojmë problemin në aeroplan. Sistemi i pabarazive le të jetë konsistent (ka të paktën një zgjidhje).

Çdo pabarazi e këtij sistemi përcakton gjeometrikisht një gjysmëplan me vijën kufitare a i 1 x 1 + a i 2 x 2 = b i, i = 1, 2, …, m. Kushtet e jonegativitetit përcaktojnë gjysmërrafshe me vija kufitare x 1 = 0, x 2 = 0, përkatësisht. Sistemi është i pajtueshëm, pra, gjysmërrafshët, si grupe konvekse, të kryqëzuara, përbëjnë një pjesë të përbashkët, e cila është një bashkësi konvekse dhe është një koleksion pikash, ku koordinatat e secilës pikë janë zgjidhja e këtij sistemi. Mbledhja e këtyre pikave quhet shumëkëndëshi vendimtar. Mund të jetë një pikë, vijë, rreze, shumëkëndësh i kufizuar dhe i pakufizuar.

Kështu, gjeometrikisht, LPP është kërkimi i një pike të tillë të poligonit të zgjidhjes, koordinatat e së cilës japin vlerën maksimale (minimale) për funksionin linear të qëllimit dhe të gjitha pikat e poligonit të zgjidhjes janë zgjidhje të realizueshme.

Një ekuacion linear përshkruan një grup pikash që shtrihen në një vijë të drejtë. Pabarazia lineare përshkruan një zonë të caktuar në rrafsh. Le të përcaktojmë se cila pjesë e planit përshkruhet nga pabarazia 2x 1 + 3x 2 12.

Së pari, ndërtoni një rresht 2x 1 + Zx 2= 12. Kalon nëpër pikat (6; 0) dhe (0; 4). Për të përcaktuar se cili gjysmë rrafsh plotëson pabarazinë, është e nevojshme të zgjidhni çdo pikë në grafik që nuk i përket një drejtëze dhe të zëvendësoni koordinatat e saj në pabarazi. Nëse pabarazia qëndron, atëherë kjo pikë është një zgjidhje e realizueshme dhe gjysma e rrafshit që përmban pikën plotëson pabarazinë. Për zëvendësimin e pabarazisë, është e përshtatshme të përdoret pika e origjinës. Zëvendësojmë x 1 = x 2 = 0 në pabarazinë 2x 1 + 3x 2 12. Ne marrim 2x0 + 3x0 12. Ky pohim është i vërtetë, prandaj, pabarazia 2x 1 + 3x 2 12 korrespondon me gjysmëplanin e poshtëm që përmban pikën (0; 0). Kjo pasqyrohet në grafikun e paraqitur në Fig. 1.1.

Në mënyrë të ngjashme, ju mund të përshkruani grafikisht të gjitha kufizimet e problemit LP.

Zgjidhja për çdo pabarazi të sistemit të kufizimeve të LPP-së është një gjysmë rrafshi që përmban vijën kufitare dhe ndodhet në njërën anë të saj. Kryqëzimi i gjysmëplaneve, secila prej të cilave përcaktohet nga pabarazia përkatëse e sistemit, quhet rajoni i zgjidhjeve të realizueshme ose rajoni i përkufizimit. Duhet mbajtur mend se rajoni i zgjidhjeve të realizueshme plotëson kushtet e jonegativitetit ( x j 0, j = 1, 2, ..., n). Koordinatat e çdo pike që i përket fushës së përkufizimit janë një zgjidhje e mundshme për problemin.

Për të gjetur vlerën ekstreme të funksionit objektiv në zgjidhjen grafike të problemeve LP, përdoret një gradient vektorial, koordinatat e të cilit janë derivate të pjesshëm të funksionit objektiv, d.m.th.

Ky vektor tregon drejtimin e ndryshimit më të shpejtë në funksionin objektiv. Drejt me 1 x 1 + me 2 x 2 = f (x 0), pingul me vektorin e gradientit, është vija e nivelit të funksionit objektiv. Në çdo pikë të vijës së nivelit, funksioni objektiv merr të njëjtën vlerë. Le të barazojmë funksionin objektiv me një vlerë konstante "a"... Duke ndryshuar vlerën e "a", marrim një familje të drejtëzave paralele, secila prej të cilave është një vijë e nivelit të funksionit objektiv.

Një veti e rëndësishme e vijës së nivelit të një funksioni linear është se kur linja zhvendoset paralelisht në një drejtim, niveli vetëm rritet, dhe kur zhvendoset në drejtimin tjetër, ai vetëm zvogëlohet.

Nga pikëpamja gjeometrike, në një problem të programimit linear, kërkohet një pikë e tillë qoshe ose një grup pikash nga një grup zgjidhjesh të pranueshme, në të cilat arrihet vija e nivelit më të lartë (më të ulët), e vendosur më larg (më afër) se të tjerat në drejtim të rritjes më të shpejtë.

Metoda grafike për zgjidhjen e LPP-së përbëhet nga fazat në vijim.

1. Është ndërtuar rajoni poligonal i zgjidhjeve të realizueshme (ODS) të LPP-së.

2. Gradienti vektor i funksionit objektiv (CF) është ndërtuar në një pikë x 0 që i përket ODR:

3. Vija e nivelit c 1 x 1 + c 2 x 2 = a (a është një konstante) - një vijë e drejtë pingul me vektorin e gradientit - lëviz në drejtim të këtij vektori në rastin e maksimizimit të f (x 1, x 2) derisa të largohet nga kufijtë e ODR. Pika kufizuese (ose pikat) e zonës gjatë kësaj lëvizjeje është pika maksimale f (x 1, x 2).

4. Për të gjetur koordinatat e pikës maksimale, mjafton të zgjidhen dy ekuacione të drejtëzave të marra nga kufizimet përkatëse dhe duke dhënë pikën maksimale në kryqëzim. Vlera f (x 1, x 2) e gjetur në pikën që rezulton është maksimumi.

Kur minimizoni (maksimizoni) funksionin f (x 1, x 2), vija e nivelit lëviz në drejtim të kundërt me vektorin e gradientit. Nëse vija e drejtë që korrespondon me vijën e nivelit nuk largohet nga ODR gjatë lëvizjes së saj, atëherë minimumi (maksimumi) i funksionit f (x 1, x 2) nuk ekziston.

Nëse vija e nivelit është paralele me disa kufizime funksionale të problemit, atëherë vlera optimale e CF do të arrihet në çdo pikë të këtij kufizimi që shtrihet midis dy pikave optimale të këndit, dhe, në përputhje me rrethanat, secila prej këtyre pikave është zgjidhja optimale për LPP-së. Situatat e mundshme për zgjidhjen grafike të problemeve LP janë paraqitur në tabelë. 1.3.

Tabela 1.3

№	Lloji ODR	Lloji optimal i zgjidhjes	Shënime (redakto)
	Poligonal i mbyllur	Vetëm vendim
	Vetëm vendim
	Poligonale	ZF nuk kufizohet nga poshtë
	CF nuk kufizohet nga lart
	Poligonal i hapur	Vetëm vendim
	Një numër i pafund zgjidhjesh
	Seksioni	Vetëm vendim

Shqyrtoni zgjidhjen grafike të problemeve të programimit linear në shembullin e mëposhtëm.

Shembulli 1.1. Planifikimi i prodhimit të një ndërmarrje qepëse (problemi i kostumeve).

Është planifikuar të lëshohen dy lloje kostume - burra dhe gra. Një kostum femrash kërkon 1 m lesh, 2 m lavsan dhe 1 person / ditë punë. Për kostum mashkulli - 3,5 m lesh, 0,5 m lavsan dhe 1 person / ditë pune. Ka gjithsej 350 m lesh, 240 m lavsan dhe 150 njeri/dite kosto pune. Kërkohet të përcaktohet se sa kostume të secilit lloj duhet të qepen për të siguruar fitimin maksimal, nëse fitimi nga shitja e kostumit të grave është 10 njësi valutore, dhe nga kostumet e një burri - 20 njësi valutore. Duhet pasur parasysh se duhet të qepen të paktën 60 kostume për meshkuj.

Le të prezantojmë emërtimet e mëposhtme: x 1 - numri i kostumeve të grave; x 2 - numri i kostumeve për meshkuj. Fitimi nga shitja e kostumeve për femra është 10x1, kurse nga shitja e kostumeve për meshkuj - 20x2, d.m.th. është e nevojshme të maksimizohet funksioni objektiv:

10x1 + 20x2

Kufizimet e detyrës janë si më poshtë:

x 1 + x 2 150,

2 x 1 + 0,5x 2 240,

x 1 + 3,5x 2 350,

x 2 60,

x 1 0.

Kufizimi i parë i punës x 1 + x 2 150. Vija e drejtë x 1 + x 2 = 150 kalon nëpër pikat (150; 0) dhe (0; 150) (Fig. 1.2).

Kufizimi i dytë për lavsan është 2 x 1 + 0.5x 2 240. Vija e drejtë 2 x 1 + 0.5x 2 = 240 kalon nëpër pikat (120; 0) dhe (0; 480). Kufiri i tretë për leshin x 1 + 3,5 x 2 350. Le të shtojmë kufirin e katërt për numrin e kostumeve për meshkuj x 2 60. Zgjidhja e kësaj pabarazie është gjysmërrafshi i shtrirë mbi drejtëzën x 2 = 60. Në fig. 1.3 zona e zgjidhjeve të pranueshme është e hijezuar. Për të përcaktuar drejtimin e lëvizjes drejt optimumit, ndërtojmë një vektor gradient, koordinatat e të cilit janë derivate të pjesshëm të funksionit objektiv, d.m.th.

Për të ndërtuar një vektor të tillë, duhet të lidhni pikën (10; 20) me origjinën. Gjatë maksimizimit të funksionit objektiv, është e nevojshme të lëvizni në drejtim të vektorit të gradientit, dhe kur minimizoni, në drejtim të kundërt. Për lehtësi, mund të ndërtoni një vektor proporcional me vektorin. Pra, në fig. 1.4 tregon vektorin e gradientit (30; 60).

Për të përcaktuar drejtimin e lëvizjes drejt optimumit, ndërtojmë një vektor gradient, koordinatat e të cilit janë derivate të pjesshëm të funksionit objektiv, d.m.th.

Në rastin tonë, linja e nivelit do të lëvizë derisa të largohet nga zona e zgjidhjeve të pranueshme. Në pikën ekstreme, këndore, arrihet maksimumi i funksionit objektiv. Për të gjetur koordinatat e kësaj pike, mjafton të zgjidhen dy ekuacione të drejtëzave të marra nga kufizimet përkatëse dhe duke dhënë pikën maksimale në kryqëzim:

x 1 + 3,5x 2 = 350,

x 1 + x 2 = 150.

Nga këtu është e lehtë të shkruani zgjidhjen për LPP-në origjinale: max f (x)= 2300 dhe arrihet në x 1 = 70 dhe x 2 = 80 (shih Fig. 1.4).

1.3 TEKNOLOGJIA PËR ZGJIDHJEN E PROBLEMEVE TË PROGRAMIMIT LINEAR ME PËRDORIM RREGULLIMET KËRKONI NJË ZGJIDHJE NË MJEDISIN EXCEL

1.3.1. Informacione të përgjithshme rreth punës me një procesor të fletëllogaritjes Excel

Le të shqyrtojmë disa aspekte të punës me një procesor Excel, i cili do të thjeshtojë llogaritjet e nevojshme për të zgjidhur problemet e optimizimit. Një spreadsheet është një produkt softuerësh i krijuar për të automatizuar përpunimin e të dhënave tabelare.

Elementet e ekranit Excel. Pas fillimit të Excel, në ekran shfaqet një tabelë, pamja e së cilës është paraqitur në figurën 1.5.

Ky imazh quhet fletë pune. Është një rrjet rreshtash dhe kolonash, kryqëzimet e të cilave formojnë drejtkëndësha të quajtur qeliza. Fletët e punës janë të destinuara për futjen e të dhënave, llogaritjet, organizimin e bazës së informacionit, etj. Dritarja e Excel shfaq elementet kryesore të programit: shiriti i titullit, shiriti i menusë, shiriti i statusit, butonat e kontrollit të dritares.

Puna me formula. Në programet e fletëllogaritjeve, formulat përdoren për të kryer një shumëllojshmëri të gjerë llogaritjesh. Me Excel, ju mund të krijoni shpejt një formulë. Formula ka tre pjesë kryesore:

1) një shenjë e barabartë;

2) një grup vlerash ose referencash në qelizat me të cilat kryhen llogaritjet;

3) operatorët.

4) Nëse nuk ka shenjë të barabartë, atëherë Excel i interpreton të dhënat jo si formulë, por si hyrje të të dhënave në një qelizë. Formulat mund të futen direkt në një qelizë ose në shiritin e formulave - ose tekst ose numra. Në këtë rast, duhet të bëni sa më poshtë:

· Zgjidhni qelizën që duhet të përmbajë formulën dhe vendosni shenjën (=);

· Futni një operator ose një shenjë veprimi;

· Zgjidhni një qelizë tjetër që do të përfshihet në formulë;

· Shtypni tastin Enter.

Formula e futur shfaqet në shiritin e formulës dhe rezultati i llogaritjes shfaqet në qelizë.

Përdorimi i funksioneve në formula. Ju mund të përdorni funksionet e Excel për ta bërë më të lehtë futjen e formulave. Funksionet janë formula të integruara në Excel. Excel përmban shumë formula. Ato grupohen në lloje të ndryshme: logjike, matematikore, inxhinierike, statistikore etj.

Për të aktivizuar një formulë të caktuar, shtypni butonat Fut, Funksionet. Dritarja Function Wizard që shfaqet në të majtë përmban një listë të llojeve të funksioneve. Pas zgjedhjes së llojit, një listë e vetë funksioneve do të vendoset në të djathtë. Funksioni zgjidhet duke klikuar mbi emrin përkatës.

Funksione të ndryshme kryejnë lloje të ndryshme llogaritjesh sipas rregullave specifike. Kur një funksion është një objekt i vetëm në një qelizë të një flete pune, ai fillon me një shenjë (=), e ndjekur nga emri i funksionit dhe më pas argumentet e funksionit, të mbyllura në kllapa.

Gjetja e një zgjidhjeje është një shtesë Excel që ju lejon të zgjidhni problemet e optimizimit. Nëse komanda Gjeni një zgjidhje mungon në menynë e Veglave, atëherë duhet të ngarkoni këtë shtesë. Zgjidhni Tools => Add-Ins dhe aktivizoni shtesën Find Solution. Nëse kjo shtesë nuk është në kutinë e dialogut të Shtesave, atëherë duhet të shkoni te Paneli i Kontrollit të Windows, të klikoni ikonën Shto ose Hiq Programet dhe të përdorni programin e konfigurimit të Excel (ose Office) për të instaluar shtesën Gjeni një zgjidhje. -në.

Pasi të keni zgjedhur Mjetet => Gjeni zgjidhjen, shfaqet kutia e dialogut Gjeni zgjidhje.

Ekzistojnë tre opsione kryesore në kutinë e dialogut Gjeni zgjidhje;

Cakto qelizën e synuar.

Me ndryshimin e qelizave.

Kufizimet.

Së pari, duhet të plotësoni fushën Set Target Cell. Në të gjitha detyrat për mjetin Solver, rezultati në një nga qelizat e fletës së punës është i optimizuar. Qeliza e synuar është e lidhur me qelizat e tjera në këtë fletë pune duke përdorur formula. Solution Finder përdor formula që prodhojnë një rezultat në qelizën e synuar për të testuar zgjidhjet e mundshme. Mund të zgjidhni të kërkoni për vlerën më të vogël ose më të madhe për qelizën e synuar, ose të vendosni një vlerë specifike.

Parametri i dytë i rëndësishëm i mjetit Solver është parametri Modify Cells. Këtu specifikoni qelizat, vlerat në të cilat do të ndryshojnë për të optimizuar rezultatin në qelizën e synuar. Mund të specifikoni deri në 200 qeliza të ndryshueshme për të kërkuar një zgjidhje. Ekzistojnë dy kërkesa kryesore për këto qeliza: ato nuk duhet të përmbajnë formula dhe ndryshimet në vlerat e tyre duhet të reflektohen në ndryshimin e rezultatit në qelizën e synuar. Me fjalë të tjera, qeliza e synuar varet nga qelizat që do të ndryshohen.

Parametri i tretë që duhet të futet në skedën Zgjidh është kufizimet.

Për të zgjidhur problemin, duhet:

1) tregoni adresat e qelizave në të cilat do të vendoset rezultati i zgjidhjes (qeliza të ndryshueshme);

2) shkruani të dhënat fillestare;

3) futja e një varësie për funksionin objektiv;

4) futni varësi për të kufizuar,

5) ekzekutoni komandën Kërko për zgjidhje;

6) caktoni një qelizë në funksionin e synuar (vendosni qelizën e synuar);

7) vendos kufizime;

8) shkruani parametrat për zgjidhjen e LPP-së.

Merrni parasysh teknologjinë e zgjidhjes duke përdorur kushtet e Shembullit 1.1 (problemi i kostumit).

Modeli ekonomik dhe matematikor i problemit

Le të jetë x 1 numri i kostumeve të grave; x 2 - numri i kostumeve për meshkuj,

10 x x 1 + 20 x x 2 maksimum

Kufizimet e detyrës janë si më poshtë:

x 1 + x 2 150 - kufizimet e punës;

2 x x 1 + 0,5 x NS 2 240 - kufizim në lavsan;

x 1 + 3,5 x x 2 350 - kufizim në lesh;

x 2 60 - kufizim në kostumet e meshkujve;

x 1 0 - kufizim në kostumet e grave.

1. Përcaktoni adresat e qelizave në të cilat do të vendoset rezultati i zgjidhjes (qelizat e modifikuara).

Etiketa x 1, x 2 për numrin e kostumeve të çdo lloji. Në problemin tonë, vlerat optimale të vektorit = (x 1, x 2) do të vendosen në qelizat A2: B2, vlera optimale e funksionit objektiv - në qelizën C3.

2. Futni të dhënat fillestare.

Futni të dhënat fillestare të detyrës, siç tregohet në Fig. 1.6.

3. Prezantoni varësinë për funksionin objektiv.

· Vendosni kursorin në qelizën "NW", qeliza do të theksohet.

· Vendoseni kursorin në butonin Function Wizard që ndodhet në shiritin e veglave.

· Futni Enter. Në ekran shfaqet kutia e dialogut Function Wizard Hapi 1 nga 2.

· Në dritaren Funksionet zgjidhni linjën SUMPRODUCT (Fig. 1.7). Në ekran

· Shfaqet kutia e dialogut SUMPRODUCT (Fig. 1.8).

Në rreshtin Array 1 futni A2: B2.

· Në rreshtin Array 2 shkruani AZ: VZ.

Vargu 1 do të përdoret kur injektoni varësi nga kufizimet, kështu që ju duhet të bëni një referencë absolute për këtë grup. Në fig. 1.9 tregon se një funksion është futur në qelizën СЗ.

5. Prezantoni varësitë për kufizimet (Figura 1.10).

· Vendosni kursorin në qelizën SZ.

· Në shiritin e veglave, butoni Copy to clipboard.

· Vendosni kursorin në qelizën C4.

· Vendosni kursorin në qelizën C5.

· Në shiritin e veglave, butoni Paste from clipboard.

· Vendosni kursorin në qelizën Sat.

· Në shiritin e veglave, butoni Paste from clipboard.

· Vendosni kursorin në qelizën C7.

· Në shiritin e veglave, klikoni butonin Paste from clipboard. (Përmbajtja e qelizave C4-C7 duhet të kontrollohet. Ato duhet të përmbajnë informacion, siç tregohet për shembullin në figurën 1.11; përmbajtja e qelizës C5 tregohet si shembull.)

· Në shiritin e menysë, vendosni treguesin e miut në shërbim. Në menynë e zgjeruar, zgjidhni komandën Gjej zgjidhje. Shfaqet kutia e dialogut Kërko për zgjidhje (Fig. 1.12).

5. Ekzekutoni komandën Gjej zgjidhje.

6. Caktoni një qelizë për funksionin objektiv (caktoni qelizën e synuar), specifikoni adresat e qelizave që do të ndryshohen.

· Vendosni kursorin në rreshtin Set target qelizë.

· Futni adresën e qelizës $ C $ 3.

· Futni llojin e funksionit objektiv në varësi të kushteve të problemit tuaj. Për ta bërë këtë, shënoni nëse funksioni objektiv është i barabartë me vlerën maksimale ose vlerën minimale.

· Vendosni kursorin në një rresht Duke ndryshuar qelizat.

· Futni adresat e variablave të kërkuar A $ 2: B $ 2 (Fig. 1.13).

7. Futja e kufizimeve.

· Lëvizni treguesin e miut mbi butonin Shto. Shfaqet kutia e dialogut Add Constraint.

· Prezantoni një shenjë kufizuese.

· Në rreshtin Restriction, vendosni adresën $ D $ 4 (Fig. 1.14).

· Lëvizni treguesin e miut mbi butonin Shto. Kutia e dialogut Add Constraint rishfaqet në ekran.

· Prezantoni pjesën tjetër të kufizimeve të problemit sipas algoritmit të mësipërm.

· Pasi të jetë futur kufizimi i fundit, klikoni në butonin OK. Në ekran do të shfaqet dialog box-i Search for a zgjidhje me kushtet e futura (Fig. 1.15).

8. Shkruani parametrat për zgjidhjen e problemit të programimit linear.

· Në kutinë e dialogut, vendosni treguesin e miut në butonin Options. Në ekran do të shfaqet kutia e dialogut të parametrave të kërkimit të zgjidhjes (Fig. 1.16).

· Vendosni kutitë e kontrollit në kutitë Model linear (kjo do të sigurojë aplikimin e metodës simplex) dhe vlerat jo negative.

· Lëvizni treguesin e miut mbi butonin OK. Shfaqet kutia e dialogut Gjeni zgjidhjen.

· Vendosni treguesin e miut në butonin Run.

Pas një kohe të shkurtër, do të shfaqet kutia e dialogut e rezultateve të kërkimit të zgjidhjes dhe tabela origjinale me qelizat AZ të mbushura: VZ për vlerat x i dhe qeliza C3 me vlerën maksimale të funksionit objektiv (Fig. 1.17).

Nëse specifikoni llojin e raportit Stabilitet, atëherë mund të merrni informacion shtesë për zgjidhjen optimale (Fig. 1.18).

Si rezultat i zgjidhjes së problemit, u mor përgjigja: është e nevojshme të qepni 70 copë. kostume femrash dhe 80 copë. kostume për meshkuj për të marrë fitimin maksimal prej 2300 USD.

1.4. DUALITET NË PROBLEMET E PROGRAMIMIT LINEAR. ANALIZA E ZGJIDHJEVE OPTIMALE TË PËRFITURA

Në vitin 1975, bashkatdhetari ynë L.V. Kantorovich iu dha Çmimi Nobel në Ekonomi (së bashku me ekonomistin amerikan T. Koopmans) për zhvillimin e teorisë së përdorimit optimal të burimeve (shih Shtojcën 1).

I lidhur ngushtë me çdo problem të programimit linear është një problem tjetër linear, i quajtur i dyfishtë; detyra fillestare quhet fillestare, ose e drejtpërdrejtë. Lidhja midis problemeve origjinale dhe të dyfishta qëndron, veçanërisht, në faktin se zgjidhja e njërës prej tyre mund të merret drejtpërdrejt nga zgjidhja për tjetrën.

Variablat e problemit të dyfishtë y i quhen vlerësime të përcaktuara objektivisht, ose vlerësime të dyfishta, ose "çmime" të burimeve, ose çmime hije.

Secila nga problemet e çiftit të dyfishtë është në fakt një problem i pavarur i programimit linear dhe mund të zgjidhet në mënyrë të pavarur nga tjetra.

Problemi i dyfishtë në lidhje me origjinalin përpilohet sipas rregullave të mëposhtme:

1) funksioni objektiv i problemit origjinal është formuluar për maksimumin, dhe funksioni objektiv i problemit të dyfishtë - për minimumin, ndërsa në problemin për maksimumin të gjitha pabarazitë në kufizimet funksionale kanë formën (), në problem për minimumin - formularin ( );

2) matrica A, e përbërë nga koeficientët në kufizime të panjohura në sistemin e problemit origjinal, dhe një matricë e ngjashme A T në problemin e dyfishtë, merren nga njëri-tjetri me transpozim;

3) numri i variablave në problemin e dyfishtë është i barabartë me numrin e kufizimeve funksionale të problemit origjinal, dhe numri i kufizimeve në sistemin e problemit të dyfishtë është i barabartë me numrin e variablave në atë origjinal;

4) koeficientët për të panjohurat në funksionin objektiv të problemit të dyfishtë janë terma të lirë në sistemin e kufizimeve të problemit origjinal, dhe anët e djathta në kufizimet e problemit të dyfishtë janë koeficientët për të panjohurat në funksionin objektiv të origjinale; j 0.

Këto dy probleme formojnë një çift problemesh të dyfishta simetrike. Deklaratat kryesore për problemet reciproke të dyfishta përmbahen në dy teoremat e ardhshme.

Teorema e parë e dualitetit. Për detyrat reciproke të dyfishta, ndodh një nga rastet reciprokisht ekskluzive.

1. Problemet e drejtpërdrejta dhe të dyfishta kanë zgjidhje optimale,
në këtë rast, vlerat e objektivit funksionojnë në zgjidhjet optimale
ndeshje

2. Në problemin e drejtpërdrejtë, grupi i pranueshëm nuk është bosh dhe funksioni objektiv në këtë grup nuk kufizohet më sipër. Në këtë rast, problemi i dyfishtë do të ketë një grup bosh të pranueshëm.

3. Në problemin e dyfishtë, grupi i pranueshëm nuk është bosh dhe funksioni objektiv në këtë grup nuk është i kufizuar nga poshtë. Në këtë rast, grupi i pranueshëm i problemit të drejtpërdrejtë rezulton të jetë bosh.

4. Të dyja problemet në shqyrtim kanë grupe boshe të pranueshme.

Teorema e dytë e dualitetit (teorema plotësuese e plogëtisë). Le = ( x 1, x 2, ..., xn) është një zgjidhje e pranueshme e problemit të drejtpërdrejtë, a = (y 1, y 2,…, y m) është një zgjidhje e pranueshme e problemit të dyfishtë. Që ato të jenë zgjidhje optimale të problemeve të drejtpërdrejta dhe të dyfishta, është e nevojshme dhe e mjaftueshme që të mbahen këto marrëdhënie:

(1.4)

(1.5)

Kushtet (1.4) dhe (1.5) lejojnë, duke ditur zgjidhjen optimale të një prej problemeve reciproke të dyfishta, të gjejmë zgjidhjen optimale për një problem tjetër.

Shqyrtoni një teoremë tjetër, përfundimet e së cilës do të përdoren në vijim.

Teorema e vlerësimit. Vlerat e variablave y i në zgjidhjen optimale të problemit të dyfishtë janë vlerësime të ndikimit të termave të lirë b i të sistemit të kufizimeve (pabarazive) të problemit të drejtpërdrejtë në vlerë.

Duke zgjidhur LPP-në duke përdorur metodën simplex, ne zgjidhim njëkohësisht LPP-në e dyfishtë. Variablat e problemit të dyfishtë y i quhen vlerësime të përcaktuara objektivisht.

Le të shqyrtojmë interpretimin ekonomik të problemit të dyfishtë duke përdorur shembullin e problemit të tapetit.

Shembulli 1 .2. Duke përdorur deklaratën e problemit të qilimit, plotësoni detyrat e mëposhtme.

1. Formuloni një model ekonomik dhe matematikor të problemit të qilimave për koston totale maksimale të prodhimit, duke përdorur të dhënat në tabelë. 1.1.

2. Duke përdorur Kërkimin e Zgjidhjeve, gjeni një plan prodhimi që maksimizon koston totale të prodhimit.

3. Formuloni një model ekonomik dhe matematikor të problemit të dyfishtë ndaj problemit të qilimave.

4. Gjeni planin optimal të problemit të dyfishtë, duke përdorur teoremën e dualitetit, shpjegoni barazinë në zero të X 1 dhe X 4.

5. Duke përdorur protokollet e kërkimit për një zgjidhje, analizoni zgjidhjen optimale të marrë për problemin origjinal.

6. Përcaktoni se si do të ndryshojë kostoja totale dhe plani i prodhimit me një rritje të rezervës së burimit të tubacionit me 12 njësi.

1. Le të formulojmë një model ekonomik dhe matematikor të problemit.

Le të caktojmë përmes X 1, X 2, X 3, X 4 numrin e tapeteve të secilit lloj. Funksioni objektiv ka formën

F (X) = ZX 1 + 4X 2 + ZX 3 + X 4 max,

dhe kufizimet e burimeve

7X 1 + 2X 2 + 2X 3 + 6X 4 80,

5X 1 + 8X 2 + 4 X 3 + ZX 4 480,

2X 1 + 4 X 2 + X 3 + 8X 4 130,

X 1, X 2, X 3, X 4 0.

2. Gjetja e planit optimal të lëshimit.

Ne do ta zgjidhim problemin duke përdorur shtesën Excel në Kërko për një zgjidhje. Teknologjia për zgjidhjen e problemit u diskutua në detaje në problemin për kostumet. Në problemin tonë, vlerat optimale të vektorit X = (X 1, X 2, X 3, X 4) do të vendosen në qelizat ВЗ: ЕЗ, vlera optimale e funksionit objektiv - në qelizë F4.

Le të fusim të dhënat fillestare. Së pari, ne përshkruajmë funksionin objektiv duke përdorur funksionin - SUMPRODUCT (Fig. 1.19). Dhe pastaj do të futim të dhëna për anën e majtë të kufizimeve. Në kërkimin e një zgjidhjeje, ne prezantojmë drejtimin e funksionit objektiv, adresat e variablave të kërkuar dhe shtojmë kufizime. Në ekran do të shfaqet dialog box-i Search for a zgjidhje me kushtet e futura (Fig. 1.20).

Pasi të keni futur parametrat për zgjidhjen e LPP, klikoni butonin Ekzekutoni. Në ekran do të shfaqet një mesazh se zgjidhja është gjetur (Fig. 1.21).

Zgjidhja që rezulton do të thotë që të ardhurat maksimale janë 150 mijë rubla. Fabrika mund të marrë 30 qilima të tipit të dytë dhe 10 qilima të tipit të tretë pas lëshimit. Në këtë rast, burimet "punë" dhe "pajisje" do të përdoren plotësisht dhe do të përdoren 280 kg prej 480 kg fije (burimi "i papërpunuar").

Gjenerimi i një raporti bazuar në rezultatet e kërkimit për një zgjidhje. Excel ju lejon të paraqisni rezultatet e kërkimit për një zgjidhje në formën e një raporti (Tabela 1.4). Ekzistojnë tre lloje të raporteve të tilla:

· Rezultatet (Përgjigje). Raporti përfshin vlerat e burimit dhe destinacionit të objektivit dhe qelizave të modifikuara, dhe më shumë informacion rreth kufizimeve.

· Stabiliteti (Ndjeshmëria). Një raport që ofron informacion në lidhje me ndjeshmërinë e një zgjidhjeje ndaj ndryshimeve të vogla në qelizat që ndryshohen ose në formulat e kufizimeve.

· Kufijtë. Përveç vlerave të burimit dhe objektivit të qelizave të modifikuara dhe të synuara, raporti përfshin kufijtë e sipërm dhe të poshtëm të vlerave që qelizat ndikuese mund të marrin, në varësi të kufizimeve.

Nëse ka vetëm dy variabla në një problem të programimit linear, atëherë ai mund të zgjidhet grafikisht.

Konsideroni një problem të programimit linear me dy ndryshore dhe:
(1.1) ;
(1.2)
Këtu, ka numra arbitrar. Detyra mund të jetë si për të gjetur maksimumin (maksimum) ashtu edhe për të gjetur minimumin (min). Në sistemin e kufizimeve mund të jenë të pranishme edhe shenjat edhe shenjat.

Ndërtimi i rajonit të zgjidhjeve të realizueshme

Metoda grafike për zgjidhjen e problemit (1) është si më poshtë.
Së pari, vizatojmë boshtet e koordinatave dhe zgjedhim shkallën. Secila nga pabarazitë e sistemit të kufizimeve (1.2) përcakton një gjysmëplan të kufizuar nga vija përkatëse.

Pra, pabarazia e parë
(1.2.1)
përcakton një gjysmë rrafsh të kufizuar nga një vijë e drejtë. Në njërën anë të kësaj vije të drejtë, dhe në anën tjetër. Në vijën më të drejtë. Për të zbuluar se nga cila anë qëndron pabarazia (1.2.1), ne zgjedhim një pikë arbitrare që nuk shtrihet në një vijë të drejtë. Më pas, ne zëvendësojmë koordinatat e kësaj pike në (1.2.1). Nëse pabarazia qëndron, atëherë gjysma e rrafshit përmban pikën e zgjedhur. Nëse pabarazia nuk plotësohet, atëherë gjysma e rrafshit ndodhet në anën tjetër (nuk përmban pikën e zgjedhur). Hijezim i gjysmërrafshit për të cilin vlen pabarazia (1.2.1).

Ne kryejmë të njëjtën gjë për pabarazitë e mbetura të sistemit (1.2). Kjo do të na japë gjysmë-rrafshët me hije. Pikat e rajonit të zgjidhjeve të realizueshme plotësojnë të gjitha pabarazitë (1.2). Prandaj, grafikisht, rajoni i zgjidhjeve të realizueshme (ADS) është kryqëzimi i të gjithë gjysmëplanëve të ndërtuar. Hijezim ODT. Është një shumëkëndësh konveks, faqet e të cilit i përkasin drejtëzave të ndërtuara. Gjithashtu, ODR mund të jetë një formë konveks e pakufizuar, segment vije, rreze ose vijë e drejtë.

Mund të lindë një rast që gjysmërrafshët nuk përmbajnë pika të përbashkëta. Atëherë domeni i zgjidhjeve të realizueshme është grupi bosh. Ky problem nuk ka zgjidhje.

Metoda mund të thjeshtohet. Ju nuk keni pse të hijeni çdo gjysmë rrafsh, por së pari ndërtoni të gjitha linjat e drejta
(2)
Më pas, zgjidhni një pikë arbitrare që nuk i përket asnjërës prej këtyre rreshtave. Zëvendësoni koordinatat e kësaj pike në sistemin e pabarazive (1.2). Nëse plotësohen të gjitha pabarazitë, atëherë rajoni i zgjidhjeve të realizueshme kufizohet nga vijat e drejta të ndërtuara dhe përfshin pikën e zgjedhur. Ne e hijezojmë rajonin e zgjidhjeve të realizueshme përgjatë kufijve të vijave të drejta në mënyrë që të përfshijë pikën e zgjedhur.

Nëse të paktën një pabarazi nuk plotësohet, atëherë zgjedhim një pikë tjetër. Dhe kështu me radhë, derisa të gjendet një pikë, koordinatat e së cilës plotësojnë sistemin (1.2).

Gjetja e ekstremit të funksionit objektiv

Pra, kemi zonën e hijezuar të zgjidhjeve të realizueshme (ODS). Ai kufizohet nga një polivijë e përbërë nga segmente dhe rreze që u përkasin vijave të drejta të ndërtuara (2). ODR është gjithmonë një grup konveks. Mund të jetë ose një grup i kufizuar ose jo i kufizuar përgjatë disa drejtimeve.

Tani mund të kërkojmë ekstremin e funksionit objektiv
(1.1) .

Për ta bërë këtë, zgjidhni çdo numër dhe ndërtoni një vijë të drejtë
(3) .
Për lehtësinë e prezantimit të mëtejshëm, supozojmë se kjo linjë kalon përmes ODR. Në këtë linjë, funksioni objektiv është konstant dhe i barabartë. një vijë e tillë e drejtë quhet vijë e nivelit të funksionit. Kjo vijë e drejtë e ndan aeroplanin në dy gjysmërrafshe. Në një gjysmë aeroplan
.
Në gjysmë rrafshin tjetër
.
Kjo do të thotë, në njërën anë të vijës së drejtë (3), funksioni objektiv rritet. Dhe sa më shumë ta largojmë pikën nga vija e drejtë (3), aq më e madhe do të jetë vlera. Në anën tjetër të vijës së drejtë (3), funksioni objektiv zvogëlohet. Dhe sa më tej ta lëvizim pikën nga vija e drejtë (3) në anën tjetër, aq më e ulët do të jetë vlera. Nëse vizatojmë një drejtëz paralele me drejtëzën (3), atëherë drejtëza e re do të jetë edhe drejtëza e nivelit të funksionit objektiv, por me vlerë të ndryshme.

Kështu, për të gjetur vlerën maksimale të funksionit objektiv, është e nevojshme të vizatoni një vijë të drejtë paralele me vijën e drejtë (3), më e largët prej saj në drejtim të rritjes së vlerave dhe duke kaluar nga të paktën një pikë. të ODR. Për të gjetur vlerën minimale të funksionit objektiv, është e nevojshme të vizatoni një vijë të drejtë paralele me vijën e drejtë (3) dhe më të largëtin prej saj në drejtim të zvogëlimit të vlerave dhe duke kaluar nga të paktën një pikë e ODR.

Nëse RDGJ është e pakufishme, atëherë mund të lindë një rast kur një vijë e tillë e drejtë nuk mund të vizatohet. Kjo do të thotë, pavarësisht se si e heqim vijën e drejtë nga vija e nivelit (3) në drejtim të rritjes (zvogëlimit), vija e drejtë do të kalojë gjithmonë përmes ODR. Në këtë rast, mund të jetë arbitrarisht i madh (i vogël). Prandaj, nuk ka vlerë maksimale (minimale). Problemi nuk ka zgjidhje.

Merrni parasysh rastin kur një vijë e drejtë ekstreme paralele me një vijë të drejtë arbitrare të formës (3) kalon nëpër një kulm të shumëkëndëshit ODR. Nga grafiku përcaktojmë koordinatat e këtij kulmi. Pastaj vlera maksimale (minimale) e funksionit objektiv përcaktohet nga formula:
.
Zgjidhja e problemit është
.

Mund të ketë gjithashtu një rast kur një vijë e drejtë është paralele me një nga faqet e ODR. Pastaj vija kalon nëpër dy kulme të poligonit ODR. Përcaktoni koordinatat e këtyre kulmeve. Për të përcaktuar vlerën maksimale (minimale) të funksionit objektiv, mund të përdorni koordinatat e ndonjë prej këtyre kulmeve:
.
Problemi ka pafundësisht shumë zgjidhje. Zgjidhja është çdo pikë e vendosur në segmentin midis pikave dhe, duke përfshirë pikat dhe veten e tyre.

Një shembull i zgjidhjes së një problemi të programimit linear duke përdorur një metodë grafike

Detyrë

Kompania prodhon fustane të dy modeleve A dhe B. Në këtë rast përdoren tre lloje pëlhure. Prodhimi i një fustani të modelit A kërkon 2 m pëlhurë të llojit të parë, 1 m pëlhurë të llojit të dytë dhe 2 m pëlhurë të llojit të tretë. Prodhimi i një fustani të modelit B kërkon 3 m pëlhurë të llojit të parë, 1 m pëlhurë të tipit të dytë, 2 m pëlhurë të tipit të tretë. Rezervat e llojit të parë të pëlhurës janë 21 m, të tipit të dytë - 10 m, të tipit të tretë - 16 m. Lëshimi i një produkti të llojit A sjell të ardhura prej 400 denarë. njësi, një produkt i tipit B - 300 den. njësi

Hartoni një plan prodhimi që i siguron kompanisë të ardhurat më të larta. Zgjidheni problemin në mënyrë grafike.

Zgjidhje

Lërini variablat dhe shënoni numrin e fustaneve të prodhuara të modeleve A dhe B, respektivisht. Atëherë sasia e pëlhurës së konsumuar të llojit të parë do të jetë:
(m)
Sasia e pëlhurës së konsumuar të llojit të dytë do të jetë:
(m)
Sasia e pëlhurës së konsumuar të llojit të tretë do të jetë:
(m)
Meqenëse numri i fustaneve të prodhuar nuk mund të jetë negativ, atëherë
dhe .
Të ardhurat nga fustanet e prodhuara do të jenë:
(njësi monetare)

Atëherë modeli ekonomik dhe matematikor i problemit ka formën:

E zgjidhim grafikisht.
Vizatojmë boshtet e koordinatave dhe.

Ne ndërtojmë një vijë të drejtë.
Në .
Në .
Vizatoni një vijë të drejtë përmes pikave (0; 7) dhe (10.5; 0).

Ne ndërtojmë një vijë të drejtë.
Në .
Në .
Vizatoni një vijë të drejtë nëpër pikat (0; 10) dhe (10; 0).

Ne ndërtojmë një vijë të drejtë.
Në .
Në .
Vizatoni një vijë të drejtë përmes pikave (0; 8) dhe (8; 0).

Hijezojeni zonën në mënyrë që pika (2; 2) të bjerë në pjesën e hijezuar. Marrim një OABC katërkëndësh.

(A1.1) .
Në .
Në .
Vizatoni një vijë të drejtë nëpër pikat (0; 4) dhe (3; 0).

Më tej, vërejmë se meqenëse koeficientët në dhe të funksionit objektiv janë pozitivë (400 dhe 300), atëherë ai rritet me rritjen dhe. Ne tërheqim një vijë të drejtë paralele me vijën e drejtë (A1.1), më e largëta prej saj në drejtimin ngjitës dhe që kalon nëpër të paktën një pikë të katërkëndëshit OABC. Një drejtëz e tillë kalon në pikën C. Nga konstruksioni përcaktojmë koordinatat e saj.
.

Zgjidhja e problemit: ;

Përgjigju

.
Domethënë, për të marrë të ardhurat më të larta, duhet të bëhen 8 fustane të modelit A. Në këtë rast të ardhurat do të jenë 3200 denarë. njësi

Shembulli 2

Detyrë

Zgjidhja e një problemi të programimit linear duke përdorur një metodë grafike.

Zgjidhje

E zgjidhim grafikisht.
Vizatojmë boshtet e koordinatave dhe.

Ne ndërtojmë një vijë të drejtë.
Në .
Në .
Vizatoni një vijë të drejtë përmes pikave (0; 6) dhe (6; 0).

Ne ndërtojmë një vijë të drejtë.
Nga këtu.
Në .
Në .
Vizatoni një vijë të drejtë përmes pikave (3; 0) dhe (7; 2).

Ne ndërtojmë një vijë të drejtë.
Ndërtojmë një vijë të drejtë (bosht abshisash).

Rajoni i zgjidhjeve të realizueshme (ODD) është i kufizuar nga vijat e drejta të ndërtuara. Për të zbuluar se nga cila anë, vërejmë se pika i përket ODR, pasi plotëson sistemin e pabarazive:

Ne e hijezojmë zonën përgjatë kufijve të vijave të ndërtuara në mënyrë që pika (4; 1) të bjerë në pjesën e hijezuar. Marrim një trekëndësh ABC.

Ne ndërtojmë një linjë arbitrare të nivelit të funksionit objektiv, për shembull,
.
Në .
Në .
Ne tërheqim një vijë të drejtë të nivelit përmes pikave (0; 6) dhe (4; 0).
Meqenëse funksioni objektiv rritet me rritjen dhe, atëherë vizatojmë një vijë të drejtë, paralele me vijën e nivelit dhe sa më larg që të jetë e mundur prej saj në drejtim të rritjes dhe duke kaluar të paktën në një pikë të trekëndëshit ABC. Një drejtëz e tillë kalon në pikën C. Nga konstruksioni përcaktojmë koordinatat e saj.
.

Zgjidhja e problemit: ;

Përgjigju

Një shembull pa zgjidhje

Detyrë

Zgjidhja grafike e një problemi të programimit linear. Gjeni vlerën maksimale dhe minimale të funksionit objektiv.

Zgjidhje

Ne e zgjidhim problemin grafikisht.
Vizatojmë boshtet e koordinatave dhe.

Ne ndërtojmë një vijë të drejtë.
Në .
Në .
Vizatoni një vijë të drejtë nëpër pikat (0; 8) dhe (2,667; 0).

Ne ndërtojmë një vijë të drejtë.
Në .
Në .
Vizatoni një vijë të drejtë nëpër pikat (0; 3) dhe (6; 0).

Ne ndërtojmë një vijë të drejtë.
Në .
Në .
Vizatoni një vijë të drejtë përmes pikave (3; 0) dhe (6; 3).

Vijat e drejta janë boshtet koordinative.

Zona e zgjidhjeve të pranueshme (ODS) është e kufizuar nga vijat e drejta të ndërtuara dhe akset koordinative. Për të zbuluar se nga cila anë, vërejmë se pika i përket ODR, pasi plotëson sistemin e pabarazive:

Ne e hijezojmë zonën në mënyrë që pika (3; 3) të bjerë në pjesën e hijezuar. Marrim një zonë të pakufizuar të kufizuar nga polivija ABCDE.

Ne ndërtojmë një linjë arbitrare të nivelit të funksionit objektiv, për shembull,
(A3.1) .
Në .
Në .
Vizatoni një vijë të drejtë përmes pikave (0; 7) dhe (7; 0).
Meqenëse koeficientët në dhe janë pozitivë, ai rritet me rritjen dhe.

Për të gjetur maksimumin, duhet të vizatoni një vijë të drejtë paralele, sa më shumë që të jetë e mundur në drejtimin ngjitës, dhe duke kaluar nga të paktën një pikë e zonës ABCDE. Megjithatë, duke qenë se rajoni është i pakufizuar nga ana e vlerave të mëdha të dhe, një vijë e tillë e drejtë nuk mund të vizatohet. Pavarësisht se çfarë vije të drejtë të tërheqim, gjithmonë do të ketë pika të rajonit që janë më të largëta në drejtim të rritjes dhe. Prandaj, nuk ka maksimum. mund të bëhen në mënyrë arbitrare të mëdha.

Ne po kërkojmë një minimum. Vizatojmë një vijë të drejtë paralele me vijën e drejtë (A3.1) dhe më të largëtin prej saj në drejtim të zvogëlimit dhe që kalon nga të paktën një pikë e zonës ABCDE. Një drejtëz e tillë kalon në pikën C. Nga konstruksioni përcaktojmë koordinatat e saj.
.
Vlera minimale e funksionit objektiv:

Përgjigju

Nuk ka vlerë maksimale.
Vlera minimale
.

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 shenjat e sakta të barazisë.

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 , pasi ka zgjidhur sistemin e ekuacioneve të dy vijave kufitare që kryqëzohen në të.

4. Duke zëvendësuar zgjidhjen optimale të gjetur në funksionin objektiv të problemit, llogaritni vlerën e saj optimale, dmth. .

Kur ndërtohet grafikisht grupi i zgjidhjeve të pranueshme të LPP (poligoni i zgjidhjes), situatat e mëposhtme janë të mundshme.