Është zhvilluar metoda e programimit linear. Teoria e programimit linear

2. Koncepti i programimit linear. Llojet e problemeve të programimit linear

Programimi linear (LP) është një nga seksionet e para dhe më të studiuara tërësisht të programimit matematik. Ishte programimi linear ai që ishte seksioni nga i cili filloi të zhvillohej vetë disiplina e "programimit matematikor". Termi "programim" në titullin e disiplinës nuk ka të bëjë fare me termin "programim (d.m.th., përpilimi i një programi) për një kompjuter" nuk ka asnjë lidhje me të, sepse Disiplina e "programimit linear" u ngrit edhe para kohës kur kompjuterët filluan të përdoren gjerësisht për të zgjidhur probleme matematikore, inxhinierike, ekonomike dhe të tjera.

Termi "programim linear" lindi si rezultat i një përkthimi të pasaktë të anglishtes "programim linear". Një nga kuptimet e fjalës "programim" është bërja e planeve, planifikimi. Prandaj, përkthimi i saktë i anglishtes "programim linear" nuk do të ishte "programim linear", por "planifikim linear", i cili pasqyron më saktë përmbajtjen e disiplinës. Megjithatë, termat programim linear, programim jolinear, programim matematikor etj. në letërsinë tonë janë bërë përgjithësisht të pranuara dhe për këtë arsye do të ruhen.

Pra, programimi linear lindi pas Luftës së Dytë Botërore dhe filloi të zhvillohet me shpejtësi, duke tërhequr vëmendjen e matematikanëve, ekonomistëve dhe inxhinierëve për shkak të mundësisë së zbatimit të gjerë praktik, si dhe harmonisë matematikore.

Mund të thuhet se programimi linear është i zbatueshëm për zgjidhjen e modeleve matematikore të atyre proceseve dhe sistemeve, të cilat mund të bazohen në hipotezën e një paraqitje lineare të botës reale.

Programimi linear përdoret në zgjidhjen e problemeve ekonomike, në probleme të tilla si menaxhimi dhe planifikimi i prodhimit; në detyrat e përcaktimit të vendosjes optimale të pajisjeve në anije, në punishte; në detyrat e përcaktimit të planit optimal për transportin e mallrave (problemi i transportit); në problemet e shpërndarjes optimale të personelit etj.

Problemi i programimit linear (LP), siç është tashmë e qartë nga ajo që u tha më lart, është gjetja e minimumit (ose maksimumit) të një funksioni linear nën kufizimet lineare.

Ekzistojnë disa metoda për zgjidhjen e problemeve të LP. Në këtë punim do të shqyrtohen disa prej tyre, në veçanti:

Metoda grafike për zgjidhjen e problemit LP;

Metoda Simplex;

Zgjidhja e problemit të LP duke përdorur tabelën e Excel;

3. Koncepti i programimit jolinear

Në shumicën e problemeve inxhinierike, ndërtimi i një modeli matematikor nuk mund të reduktohet në një problem programimi linear.

Modelet matematikore në problemet e projektimit të objekteve reale ose proceseve teknologjike duhet të pasqyrojnë proceset reale fizike dhe, si rregull, jolineare që ndodhin në to. Variablat e këtyre objekteve ose proceseve janë të ndërlidhura me ligje fizike jolineare, siç janë ligjet e ruajtjes së masës ose energjisë. Ato janë të kufizuara në intervale ekstreme që sigurojnë fizibilitetin fizik të një objekti ose procesi të caktuar. Si rezultat, shumica e problemeve të programimit matematikor që hasen në projektet kërkimore dhe problemet e projektimit janë probleme të programimit jolinear (NP).

Në këtë punim, ne do të konsiderojmë një metodë të tillë për zgjidhjen e problemeve NP si metodën e shumëzuesve të Lagranzhit.

Metoda e shumëzuesit të Lagranzhit ju lejon të gjeni maksimumin (ose minimumin) e një funksioni nën kufizimet e barazisë. Ideja kryesore e metodës është kalimi nga problemi i ekstremit të kushtëzuar në problemin e gjetjes së ekstremumit të pakushtëzuar të disa funksioneve të ndërtuara të Lagranzhit.

4. Programimi dinamik

Programimi dinamik është një aparat matematikor që ju lejon të gjeni shpejt zgjidhjen optimale në rastet kur situata e analizuar nuk përmban faktorë pasigurie, por ka një numër të madh sjelljesh që sjellin rezultate të ndryshme, ndër të cilat është e nevojshme të zgjidhni më të mirën. . Programimi dinamik i qaset zgjidhjes së një klase problemesh duke i zbërthyer në probleme më të vogla dhe më pak komplekse. Në parim, problemet e këtij lloji mund të zgjidhen duke numëruar të gjitha opsionet e mundshme dhe duke zgjedhur më të mirën mes tyre, por një numërim i tillë është shpesh shumë i vështirë. Në këto raste, procesi i marrjes së vendimit optimal mund të ndahet në hapa (faza) dhe të hetohet duke përdorur metodën e programimit dinamik.

Zgjidhja e problemeve me metoda dinamike të programimit kryhet në bazë të parimit të optimalitetit të formuluar nga R.E. Bellman: sjellja optimale ka vetinë që pavarësisht nga gjendja fillestare e sistemit dhe zgjidhja fillestare, zgjidhja pasuese duhet të përcaktojë sjelljen optimale në lidhje me gjendja e fituar si rezultat i zgjidhjes fillestare.

Kështu, planifikimi i çdo hapi duhet të kryhet duke marrë parasysh përfitimin e përgjithshëm të marrë në fund të të gjithë procesit, i cili lejon optimizimin e rezultatit përfundimtar sipas kriterit të zgjedhur.

Megjithatë, programimi dinamik nuk është një metodë zgjidhje universale. Pothuajse çdo problem i zgjidhur me këtë metodë karakterizohet nga karakteristikat e veta dhe kërkon kërkimin e grupit më të përshtatshëm të metodave për zgjidhjen e tij. Për më tepër, vëllimet e mëdha dhe kompleksiteti i zgjidhjes së problemeve me shumë hapa me shumë gjendje çojnë në nevojën për të zgjedhur probleme me dimensione të ulëta ose për të përdorur informacion të ngjeshur.

Programimi dinamik përdoret për zgjidhjen e problemeve të tilla si: shpërndarja e investimeve të pakta kapitale ndërmjet fushave të reja të përdorimit të tyre; zhvillimi i rregullave për menaxhimin e kërkesës dhe stoqeve; përgatitja e planeve kalendarike për riparimet aktuale dhe të mëdha të pajisjeve dhe zëvendësimi i tyre; kërkoni për distancat më të shkurtra në rrjetin e transportit, etj.

Le të ndahet procesi i optimizimit në n hapa. Në çdo hap, është e nevojshme të përcaktohen dy lloje të variablave - një variabël i gjendjes S dhe një ndryshore kontrolluese X. Ndryshorja S përcakton se në çfarë gjendje mund të jetë sistemi në hapin e dhënë k-të. Në varësi të S, në këtë hap mund të aplikohen disa kontrolle, të cilat karakterizohen nga ndryshorja X. Aplikimi i kontrollit X në hapin e kth sjell një rezultat Wk(S,Xk) dhe e vendos sistemin në një gjendje të re S"(S ,Xk) Për çdo gjendje të mundshme në hapin k-të, ndër të gjitha kontrollet e mundshme, kontrolli optimal X*k zgjidhet i tillë që rezultati që arrihet në hapa nga k-ti në n-të të dalë optimal. karakteristikë e këtij rezultati quhet funksioni Bellman Fk(S) dhe varet nga numri i hapit k dhe gjendja e sistemit S.

Të gjitha zgjidhjet e problemit ndahen në dy faza. Në fazën e parë, që quhet optimizim i kushtëzuar, funksioni Bellman dhe kontrollet optimale gjenden për të gjitha gjendjet e mundshme në çdo hap, duke filluar nga ai i fundit.

Pasi të gjenden funksioni Bellman dhe kontrollet optimale përkatëse për të gjithë hapat nga n-ja në të parën, kryhet faza e dytë e zgjidhjes së problemit, e cila quhet optimizim i pakushtëzuar.

Në përgjithësi, problemi i programimit dinamik formulohet si më poshtë: kërkohet të përcaktohet një kontroll i tillë X* që transferon sistemin nga gjendja fillestare S0 në gjendjen përfundimtare Sn, në të cilën funksioni objektiv F(S0,X*) merr. vlera më e madhe (më e vogël).

Karakteristikat e modelit matematikor të programimit dinamik janë si më poshtë:

problemi i optimizimit formulohet si një proces kontrolli përfundimtar me shumë hapa;

funksioni objektiv është shtues dhe është i barabartë me shumën e funksioneve objektive të çdo hapi

zgjedhja e kontrollit Xk në çdo hap varet vetëm nga gjendja e sistemit nga ky hap Sk-1 dhe nuk ndikon në hapat e mëparshëm (pa reagime);

gjendja e sistemit Sk pas çdo hapi kontrolli varet vetëm nga gjendja e mëparshme e sistemit Sk-1 dhe nga ky veprim i kontrollit Xk (pa efekt të mëvonshëm) dhe mund të shkruhet si një ekuacion i gjendjes:

në çdo hap, kontrolli Xk varet nga një numër i kufizuar variablash kontrolli, dhe gjendja e sistemit Sk varet nga një numër i kufizuar variablash;

kontrolli optimal X* është një vektor i përcaktuar nga sekuenca e kontrolleve optimale hap pas hapi:

X*=(X*1, X*2, …, X*k, …, X*n),

numri i të cilave përcakton numrin e hapave të detyrës.

Optimizimi i kushtëzuar. Siç u përmend më lart, në këtë fazë, funksioni Bellman dhe kontrollet optimale gjenden për të gjitha gjendjet e mundshme në çdo hap, duke filluar nga ai i fundit, në përputhje me algoritmin e pasme. Në hapin e fundit të n-të, gjetja e kontrollit optimal X*n dhe vlera e funksionit Bellman Fn(S) nuk është e vështirë, pasi

Fn(S)=max(Wn(S, Xn)),

ku kërkohet maksimumi mbi të gjitha vlerat e mundshme të Xn.

Llogaritjet e mëtejshme kryhen sipas relacionit rekurziv që lidh funksionin Bellman në çdo hap me të njëjtin funksion, por të llogaritur në hapin e mëparshëm:

Fk(S)=max(Wk(S,Xk)+Fk+1(S"(S,Xk))). (1)

Kjo maksimum (ose minimum) përcaktohet nga të gjitha vlerat e mundshme të ndryshores së kontrollit X për k dhe S.

Optimizimi i pakushtëzuar. Pasi të gjenden funksioni Bellman dhe kontrollet optimale përkatëse për të gjithë hapat nga n-të në të parën (në hapin e parë k=1, gjendja e sistemit është e barabartë me gjendjen fillestare S0), faza e dytë e zgjidhjes së problemit. kryhet. Kontrolli optimal gjendet në hapin e parë X1, aplikimi i të cilit do ta sjellë sistemin në gjendjen S1(S,x1*), duke ditur që, duke përdorur rezultatet e optimizimit të kushtëzuar, mund të gjejmë kontrollin optimal në hapin e dytë. , dhe kështu me radhë deri në hapin e 9-të të fundit.

Laboratori #1 (Problemi i Programimit Linear)

Për një formulim të caktuar matematikor të problemit LP, duke supozuar kushtin shtesë të jonegativitetit të variablave, kryeni veprimet e mëposhtme:

Zgjidhja e problemit në mënyrë grafike;

Sillni problemin në shënimin kanonik;

Bëni një tabelë simplex;

Zgjidheni problemin me metodën simplex me dorë ose duke përdorur një kompjuter;

Për të kryer formulimin e problemit të dyfishtë LP;

Merrni një zgjidhje për problemin e dyfishtë nga tabela e Simpleksit të marrë më parë dhe analizoni rezultatet e marra;

Kontrolloni rezultatet e zgjidhjes në një spreadsheet Excel;

Përgatitni një raport me rezultatet për çdo artikull.

Burimet	Stoqet	Produktet
		P1	R2
S1	18	0.2	3
S2	13.1	0.7	2
MV	23	2.3	2
Fitimi nga një njësi prodhimi në U.U.		3	4

Metoda grafike. Për të ndërtuar një shumëkëndësh zgjidhje, ne transformojmë sistemin origjinal

, marrim

vizatoni vijat kufitare.

Funksioni linear F=f(x) është ekuacioni i drejtëzës c1x1 + c2x2 = konst. Le të vizatojmë funksionin e synuar për f(x)=0. për të ndërtuar një vijë të drejtë 3x1 + 4x2 = 0, ndërtojmë vektorin e rrezes N = (3; 4) dhe vizatojmë një vijë pingul me të përmes pikës 0. Drejtëzën e ndërtuar F=0 e lëvizim paralel me vetveten në drejtim të vektorit N.

Figura 1 - Metoda grafike

Nga Figura 1 rezulton se kjo drejtëzë bëhet vija referuese në raport me poligonin e ndërtuar të zgjidhjeve në pikën B, ku funksioni F merr vlerën e tij maksimale. Pika B shtrihet në kryqëzimin e drejtëzave 0,7x1 + 2x2 ≤ 13,1 dhe 2,3x1 + 2x2 = 23/ Për të përcaktuar koordinatat e saj, zgjidhim sistemin e ekuacioneve:

Plani optimal i detyrave: x1 = 6,187; х2 = 4.38, duke zëvendësuar vlerat x1 dhe х2 në funksionin objektiv, marrim Fmax= 3*6.187+4*4.38=36.08.

Kështu, për të marrë fitimin maksimal prej 36,06 dollarë, duhet të planifikoni prodhimin e 6 njësive. produktet P1 dhe 4 njësi. produktet P2.

Forma kanonike e problemit LP. Le të shkruajmë problemin e alokimit të burimeve në formë kanonike. Duke shtuar variabla jonegative x3 ≥ 0, x4 ≥ 0, x5 ≥ 0 në sistemin origjinal të kufizimeve, kemi:

Tabela Simplex LP. Në rastin e variablave bazë (x3, x4, x5), tabela fillestare simplex do të duket si kjo:

Tabela 1.

	-x1	-x2
x3 =	0,2	3	18
x4 =	0,7	2	13,1
x5 =	2,3	2	23
f(x) =	3	4

Ajo tashmë korrespondon me planin bazë x(0) = T (kolona e anëtarëve të lirë).

Ndër problemet e optimizimit në teorinë e vendimeve, më të njohurat janë problemet e programimit linear në të cilat funksioni i maksimizuar F(X) është linear dhe kufizimet A jepen nga pabarazitë lineare. Le të fillojmë me një shembull (shih).

detyrë prodhimi. Punëtoria mund të prodhojë karrige dhe tavolina. Duhen 5 njësi materiali për të prodhuar një karrige dhe 20 njësi (këmbë sofër) për të prodhuar një tavolinë. Një karrige kërkon 10 orë pune, një tavolinë 15. Janë 400 copë material dhe 450 orë pune. Fitimi në prodhimin e një karrige - 45 USD, në prodhimin e një tavoline - 80 USD. Sa karrige dhe tavolina duhet të bëni për të marrë fitimin maksimal?

Le të shënojmë: X 1 - numrin e karrigeve të bëra, X 2 - numrin e tavolinave të bëra. Problemi i optimizimit ka formën:

45 X 1 + 80 X 2 → maksimumi,

5 X 1 + 20 X 2 ≤ 400,

10 X 1 + 15 X 2 ≤ 450,

Rreshti i parë përmban funksionin e synuar - fitimin në prodhimin e X 1 karrige dhe X 2 tavolina. Duhet të maksimizohet duke zgjedhur vlerat optimale të variablave X 1 dhe X 2 . Në këtë rast, kufizimet në material (vija e dytë) duhet të respektohen - nuk janë shpenzuar më shumë se 400 këmbë sofër. Si dhe kufizimet e punës (linja e tretë) - jo më shumë se 450 orë të shpenzuara. Përveç kësaj, nuk duhet të harrojmë se numri i tavolinave dhe numri i karrigeve janë jonegativë. Nëse X 1 \u003d 0, atëherë kjo do të thotë që karriget nuk janë të disponueshme. Nëse është bërë të paktën një karrige, atëherë X 1 është pozitiv. Por është e pamundur të imagjinohet një prodhim negativ - X 1 nuk mund të jetë negativ nga pikëpamja ekonomike, megjithëse një kufizim i tillë nuk mund të shihet nga pikëpamja matematikore. Në rreshtin e katërt dhe të pestë të problemës dhe thuhet se variablat janë jonegativë.

Kushtet e detyrës së prodhimit mund të përshkruhen në planin koordinativ. Ne do të vizatojmë vlerat X 1 përgjatë boshtit horizontal të abshisës dhe vlerat X 2 përgjatë boshtit vertikal të ordinatave. Pastaj kufizimet në material dhe dy rreshtat e fundit të problemit të optimizimit nxjerrin në pah vlerat e mundshme (Х 1 , Х 2) të vëllimeve të daljes në formën e një trekëndëshi (Fig. 1).

Kështu, kufizimet materiale përshkruhen si një shumëkëndësh konveks, veçanërisht një trekëndësh. Ky trekëndësh përftohet duke prerë zonën ngjitur me origjinën nga kuadrati i parë. Prerja kryhet nga një vijë e drejtë që korrespondon me vijën e dytë të problemit origjinal, me pabarazinë e zëvendësuar nga barazia. Vija e drejtë pret boshtin X 1 që korrespondon me karriget në pikën (80.0). Kjo do të thotë se nëse i gjithë materiali përdoret për të bërë karrige, atëherë do të bëhen 80 karrige. E njëjta drejtëz pret boshtin X 2 që i korrespondon tabelave në pikën (0.20). Kjo do të thotë që nëse i gjithë materiali përdoret për të bërë tabela, atëherë do të bëhen 20 tabela. Për të gjitha pikat brenda trekëndëshit, pabarazia, jo barazia, është e kënaqur - materiali do të mbetet.

Kufizimet e punës mund të përshkruhen në mënyrë të ngjashme (Fig. 2).

Kështu, kufizimet e punës përshkruhen gjithashtu si një trekëndësh. Ky trekëndësh fitohet gjithashtu duke prerë zonën ngjitur me origjinën nga kuadrati i parë. Prerja kryhet nga një vijë e drejtë që korrespondon me vijën e tretë të problemit origjinal, me pabarazinë e zëvendësuar nga barazia. Vija e drejtë pret boshtin X 1 që korrespondon me karriget në pikën (45.0). Kjo do të thotë se nëse të gjitha burimet e punës përdoren për të bërë karrige, atëherë do të bëhen 45 karrige. E njëjta drejtëz pret boshtin X 2 që i korrespondon tabelave në pikën (0.30). Kjo do të thotë se nëse të gjithë punëtorët caktohen për të bërë tabela, atëherë do të bëhen 30 tabela. Për të gjitha pikat brenda trekëndëshit, pabarazia është e kënaqur, jo barazia - disa nga punëtorët do të jenë boshe.

Ne shohim se nuk ka zgjidhje të dukshme - për prodhimin e 80 karrigeve ka material, por nuk ka punëtorë të mjaftueshëm, dhe për prodhimin e 30 tavolinave ka fuqi punëtore, por nuk ka material. Pra, duhet të bëj të dyja. Por në çfarë raporti?

Për t'iu përgjigjur kësaj pyetjeje, është e nevojshme të "kombinohen" Fig. 1 dhe Fig. 2, duke marrë sipërfaqen e zgjidhjeve të mundshme, dhe më pas të gjurmoni se çfarë vlerash merr funksioni objektiv në këtë grup (Fig. 3).

Kështu, grupi i vlerave të mundshme të vëllimeve të prodhimit të karrigeve dhe tavolinave (X 1 , X 2), ose, në terma të tjerë, grupi A, i cili vendos kufizimet në parametrin e kontrollit në problemin e përgjithshëm të optimizimit, është kryqëzimi i dy trekëndëshave, d.m.th. katërkëndëshi konveks i paraqitur në Fig.3. Tre kulmet e tij janë të dukshme - ato janë (0.0), (45.0) dhe (0.20). E katërta është kryqëzimi i dy vijave të drejta - kufijtë e trekëndëshave në figurën 1 dhe figurën 2, d.m.th. zgjidhje e një sistemi ekuacionesh

5 X 1 + 20 X 2 \u003d 400,

10 X 1 + 15 X 2 \u003d 450.

Nga ekuacioni i parë: 5 X 1 \u003d 400 - 20 X 2, X 1 \u003d 80 - 4 X 2. Zëvendësoni në ekuacionin e dytë: 10 (80 - 4 X 2) + 15 X 2 \u003d 800 - 40X 2 + 15 X 2 \u003d 800 - 25 X 2 \u003d 450, pra, 25 X 2 \u003d \u003d 14, nga ku X 1 \u003d 80 - 4 x 14 \u003d 80 -56 \u003d 24. Pra, kulmi i katërt i katërkëndëshit është (24, 14).

Ne duhet të gjejmë maksimumin e një funksioni linear në një shumëkëndësh konveks. (Në rastin e përgjithshëm të programimit linear, maksimumi i një funksioni linear në një shumëkëndësh konveks të shtrirë në një hapësirë ​​lineare me dimensione të fundme.) Ideja themelore e programimit linear është që maksimumi të arrihet në kulmet e poligonit. Në rastin e përgjithshëm - në një kulm, dhe kjo është pika e vetme maksimale. Në mënyrë private - në dy, dhe më pas segmenti që i lidh ato përbëhet gjithashtu nga pikë maksimale.

Funksioni objektiv 45 X 1 + 80 X 2 merr një vlerë minimale prej 0 në krye (0,0). Me rritjen e argumenteve, ky funksion rritet. Në kulmin (24.14), ajo merr vlerën 2200. Në këtë rast, vija e drejtë 45 X 1 + 80 X 2 \u003d 2200 kalon midis vijave të drejta të kufizimeve 5 X 1 + 20 X 2 \u003d 400 dhe 10 X 1 + 15 X 2 \u003d 450, që kryqëzohen në të njëjtën pikë. Nga këtu, si dhe nga një kontroll i drejtpërdrejtë i dy kulmeve të mbetura, rezulton se maksimumi i funksionit objektiv, i barabartë me 2200, arrihet në kulmin (24,14).

Kështu, prodhimi optimal është si më poshtë: 24 karrige dhe 14 tavolina. Kjo përdor të gjitha burimet materiale dhe të punës, dhe fitimi është 2200 dollarë amerikanë.

Problem i dyfishtë. Çdo problem i programimit linear korrespondon me të ashtuquajturin problem të dyfishtë. Në të, krahasuar me problemin origjinal, rreshtat kthehen në kolona, ​​pabarazitë ndryshojnë shenjën, kërkohet një minimum në vend të një maksimumi (ose anasjelltas, në vend të një minimumi, kërkohet një maksimum). Detyra e dyfishtë ndaj asaj të dyfishtë është vetë detyra origjinale. Le të krahasojmë problemin origjinal (në të majtë) dhe problemin e tij të dyfishtë (në të djathtë):

45 X 1 + 80 X 2 → maksimumi, 400 W 1 + 450 W 2 → min,

5 X 1 + 20 X 2 ≤ 400, 5 W 1 + 10 W 2 ≥ 45,

10 X 1 + 15 X 2 ≤ 450, 20 W 1 + 15 W 2 ≥ 80,

X 1 ≥ 0, W 1 ≥ 0,

X 2 ≥ 0. W2 ≥ 0.

Pse është kaq e rëndësishme detyra e dyfishtë? Mund të vërtetohet se vlerat optimale të funksioneve objektive në problemin origjinal dhe të dyfishtë janë të njëjta (d.m.th., maksimumi në problemin origjinal përkon me minimumin në problemin e dyfishtë). Në këtë rast, vlerat optimale të W 1 dhe W 2 tregojnë koston e materialit dhe punës, përkatësisht, nëse ato vlerësohen nga kontributi i tyre në funksionin objektiv. Për të mos u ngatërruar me çmimet e tregut të këtyre faktorëve të prodhimit, W 1 dhe W 2 quhen "vlerësime të përcaktuara objektivisht" të lëndëve të para dhe të punës.

Programimi linear si disiplinë shkencore dhe praktike. Nga të gjitha problemet e optimizimit, problemet e programimit linear dallohen nga fakti se kufizimet e tyre janë sisteme të pabarazive ose barazive lineare. Kufizimet përcaktojnë poliedra lineare konvekse në një hapësirë ​​lineare të fundme. Funksionet objektive janë gjithashtu lineare.

Për herë të parë probleme të tilla u zgjidhën nga matematikani sovjetik L.V. Kantorovich (1912-1986) në vitet 1930 si detyrat e menaxhimit të prodhimit për të optimizuar organizimin e proceseve të prodhimit dhe prodhimit, për shembull, proceset e ngarkimit të makinerive dhe prerjes së fletëve të materialeve. Pas Luftës së Dytë Botërore, detyra të ngjashme u morën në Shtetet e Bashkuara. Në vitin 1975, T. Koopmans (1910-1985, lindur në Holandë, punoi kryesisht në SHBA) dhe Akademiku i Akademisë së Shkencave të BRSS L.V. Kantorovich iu dha Çmimi Nobel në Ekonomi.

Shqyrtoni disa probleme të programimit linear.

Problemi i optimizimit të përzierjes (versioni i thjeshtuar). Në një fabrikë kimike, për të optimizuar procesin teknologjik, është e nevojshme të bëhet përzierja më e lirë që përmban sasinë e nevojshme të substancave të caktuara (le t'i shënojmë ato si T dhe H). Vlera energjetike e përzierjes (në kalori) duhet të jetë së paku e specifikuar. Le të, për thjeshtësi, përzierja të përbëhet nga dy përbërës - K dhe C. Sa prej tyre duhet marrë për t'u përfshirë në përzierje? Të dhënat fillestare për llogaritjet janë dhënë në tabelën 3.

Tabela 3. Të dhënat fillestare në problemin e optimizimit të përzierjes.

3,8 K + 4,2 C → min,

0,10 K + 0,25 C ≥ 1,00,

1,00 K + 0,25 C ≥ 5,00,

110,00 K + 120,00 C ≥ 400,00 ,

Zgjidhja grafike e tij është paraqitur në Fig.4.

Fig.4. Zgjidhja grafike e problemit të optimizimit të përzierjes.

Në figurën 4, për hir të lehtësisë së perceptimit, katër vija të drejta janë shënuar me numrat (1) - (4). Vija e drejtë (1) është një vijë e drejtë 1.00K + 0.25C = 5.00 (kufizimi i substancës H). Ai kalon, siç tregohet në figurë, nëpër pikat (5.0) në boshtin x dhe (0.20) në boshtin y. Ju lutemi vini re se vlerat e lejuara të parametrave (K, C) qëndrojnë mbi vijën e drejtë (1), në kontrast me rastet e konsideruara më parë në problemin e mëparshëm të prodhimit.

Linja (2) është një linjë 110.00 K + 120.00 C = 400.00 (kufizimi i kalorive). Le të theksojmë se në rajonin e С jo-negative ndodhet kudo nën vijën (1). Në të vërtetë, kjo është e vërtetë për K=0, drejtëza (1) kalon nëpër pikën (0.20), dhe drejtëza (2) kalon nëpër pikën (0, 400/120). Pika e prerjes së dy drejtëzave gjendet kur zgjidhet sistemi i ekuacioneve

1,00 K + 0,25 C \u003d 5,00,

110,00 K + 120,00 C = 400,00.

Nga ekuacioni i parë K \u003d 5 - 0,25 C. Zëvendësojeni në të dytin: 110 (5-0,25 C) + 120 C \u003d 400, nga ku 550 - 27,5 C + 120 C \u003d 400. Prandaj, 1003d \u 92 .5 C, d.m.th. zgjidhja arrihet për C negative. Kjo do të thotë se për të gjithë C-në pozitive, rreshti (2) qëndron poshtë vijës (1). Pra, nëse plotësohet kufizimi në H, atëherë domosdoshmërisht plotësohet edhe kufizimi i kalorive. Jemi përballë një fenomeni të ri - disa kufizime nga pikëpamja matematikore mund të jenë të tepërta. Nga pikëpamja ekonomike, ato janë të nevojshme, ato pasqyrojnë tiparet thelbësore të deklaratës së problemit, por në këtë rast, struktura e brendshme e problemit doli të jetë e tillë që kufizimi i kalorive nuk merr pjesë në formimin e të lejuarit. gamën e parametrave dhe gjetjen e një zgjidhjeje.

Vija e drejtë (4) është një vijë e drejtë 0,1 K + 0,25 C \u003d 1 (kufizim në substancën T). Ai kalon, siç tregohet në figurë, nëpër pikat (10.0) në boshtin e abshisës dhe (0.4) në boshtin e ordinatave. Ju lutemi vini re se vlerat e lejuara të parametrave (K, C) qëndrojnë mbi vijën (4), si dhe për rreshtin (1).

Rrjedhimisht, diapazoni i vlerave të pranueshme të parametrave (К, С) është i pakufizuar nga lart. Nga i gjithë rrafshi dallohet nga boshtet koordinative (shtrihet në kuadrantin e parë) dhe drejtëzat (1) dhe (4) (shtrihet mbi këto vija). Gama e vlerave të lejuara të parametrave (K, C) mund të quhet "poligoni i pakufizuar". Funksioni objektiv minimal prej 3,8 K + 4,2 C mund të arrihet vetëm në kulmet e këtij "poligoni". Ka vetëm tre maja. Këto janë kryqëzimet me boshtet e abshisave (10.0) dhe ordinatave (0.20) të vijave (1) dhe (4) (në secilin rast nga të dy kryqëzimet merret ai që plotëson të dy kufizimet). Kulmi i tretë është pika e kryqëzimit të drejtëzave (1) dhe (4), koordinatat e të cilave gjenden gjatë zgjidhjes së sistemit të ekuacioneve.

0,10 K + 0,25 C \u003d 1,00,

1,00 K + 0,25 C = 5,00.

Nga ekuacioni i dytë K \u003d 5 - 0,25 C, nga i pari 0,10 (5 - 0,25 C) + 0,25 C \u003d 0,5 - 0,025 C + 0,25 C \u003d 0,5 + 0,225 C \u003d = 1,5 C \u003d. = 20/9 dhe K = 5 - 5/9 = 40/9. Pra A = (40/9; 20/9).

Rreshti (3) në figurën 4 është një vijë që i korrespondon funksionit objektiv 3.8 K + 4.2 C. Ai kalon midis rreshtave (1) dhe (4), të cilat vendosin kufijtë, dhe minimumi arrihet në pikën A, përmes së cilës dhe vija e drejtë (3) kalon. Prandaj, minimumi është 3.8x40/9 + 4.2x20/9 = 236/9. Problemi i optimizimit të përzierjes është zgjidhur plotësisht.

Problemi i dyfishtë, i ndërtuar sipas rregullave të përshkruara më sipër, ka formën e mëposhtme (ne përsërisim këtu problemin origjinal të optimizimit të përzierjes për të demonstruar qartë teknologjinë për ndërtimin e problemit të dyfishtë):

3,8 K + 4,2 C → min, W 1 + 5 W 2 + 400 W 3 → max,

0,10 K + 0,25 C ≥ 1,00, 0,1 W 1 + 1,10 W 2 + 110 W 3 ≤ 3,8,

1,00 K + 0,25 C ≥ 5,00, 0,25 W 1 + 0,25 W 2 + 120 W 3 ≤ 4,2,

110,00 K + 120,00 C ≥ 400,00, W 1 ≥ 0,

K ≥ 0, W 2 ≥ 0,

C ≥ 0. W3 ≥ 0.

Vlera minimale në problemin e drejtpërdrejtë, siç duhet, është e barabartë me vlerën maksimale në problemin e dyfishtë, d.m.th. të dy numrat janë 236/9. Interpretimi i variablave të dyfishtë: W 1 është "kostoja" e një njësie të substancës T dhe W 2 është "kostoja" e një njësie të substancës H, e matur "nga kontributi i tyre" në funksionin objektiv. Në këtë rast, W 3 = 0, pasi kufizimi i numrit të kalorive nuk merr pjesë në asnjë mënyrë në formimin e zgjidhjes optimale. Pra, W 1, W 2, W 3 - kjo është e ashtuquajtura. vlerësime të kushtëzuara objektivisht (sipas L.V. Kantorovich) të burimeve (substancat T dhe H, kalori).

Planifikimi i nomenklaturës dhe vëllimeve të lëshimit. Le të kthehemi te organizimi i prodhimit. Ndërmarrja mund të prodhojë kuzhina automatike (lloji tepsi), aparate kafeje dhe samovare. Tabela 4 tregon të dhënat për kapacitetet prodhuese të disponueshme në ndërmarrje (në pjesë të produkteve).

Tabela 4. Kapaciteti prodhues (në copë.)

		Kafebërësit	Samovarët
Stampimi
Vëllimi i botimit
Fitimi specifik (për produkt)

Në këtë rast, vulosja dhe përfundimi kryhen në të njëjtat pajisje. Kjo ju lejon të vulosni në një kohë të caktuar ose 20,000 kuzhina, ose 30,000 aparate kafeje, ose të dyja, dhe jo më pak. Por montimi kryhet në zona të veçanta.

Problemi i programimit linear ka formën:

X 1 ≥ 0, X 2 ≥ 0, X 3 ≥ 0, (0)

X 1 / 200 + X 2 / 300 + X 3 / 120 ≤ 100 , (1)

X 1 / 300 + X 2 / 100 + X 3 / 100 ≤ 100 , (2)

Х 1 / 200 ≤ 100 , (3)

Х 2 / 120 ≤ 100 , (4)

Х 3 / 80 ≤ 100 , (5)

F \u003d 15 X 1 + 12 X 2 + 14 X 3 → maksimum.

Këtu:
(0) është kushti i zakonshëm në ekonomi për mosnegativitetin e variablave,
(1) - kufizim në mundësitë e vulosjes (i shprehur për lehtësinë e perceptimit si përqindje),
(2) - kufizim në mundësitë e përfundimit,
(3) - kufiri i montimit për kuzhina,
(4) - e njëjta gjë për mulli kafeje,
(5) - e njëjta gjë për samovaret (siç është përmendur tashmë, të tre llojet e produkteve janë mbledhur në linja të veçanta).

Së fundi, funksioni objektiv F është fitimi total i ndërmarrjes.

Vini re se pabarazia (3) vjen nga pabarazia (1), dhe pabarazia (4) vjen nga (2). Prandaj, pabarazitë (3) dhe (4) mund të hidhen menjëherë.

Le të vërejmë menjëherë një fakt interesant. Siç do të përcaktohet, në planin optimal, X 3 = 0, d.m.th. është e padobishme të prodhosh samovare.

E mëparshme

Në lidhje me zhvillimin e teknologjisë, rritja e prodhimit industrial, detyrat e gjetjes së zgjidhjeve optimale në sfera të ndryshme të veprimtarisë njerëzore luajnë një rol gjithnjë e më të rëndësishëm. Mjeti kryesor në zgjidhjen e këtyre problemeve ishte modelimi matematik - një përshkrim formal i fenomenit në studim dhe hulumtim duke përdorur aparate matematikore.

Çdo model i një procesi real presupozon idealizim dhe abstragim, por ato nuk duhet të shkojnë shumë larg nga përmbajtja e problemit, në mënyrë që modeli i ndërtuar të mos humbasë tiparet thelbësore të objektit të modeluar, d.m.th., të jetë adekuat për të. Nga ana tjetër, nëse ndërtoni një model kompleks që merr parasysh të gjitha tiparet më të mira të procesit në studim, atëherë kjo mund të cenojë kuptimin e modelimit, një nga qëllimet e të cilit është të thjeshtojë formulimin e problemit në mënyrë që është më e lehtë për ta studiuar atë (një model shumë kompleks, si rregull, nuk mund të analizohet).

Në një numër të madh rastesh, shkalla e parë e përafrimit me realitetin është një model në të cilin të gjitha varësitë midis variablave që karakterizojnë gjendjen e një objekti supozohen të jenë lineare. Këtu ekziston një analogji e plotë me atë se sa informacion shumë i rëndësishëm dhe shpesh shterues për sjelljen e një funksioni arbitrar merret në bazë të studimit të derivatit të tij - ky funksion zëvendësohet në fqinjësinë e secilës pikë me një varësi lineare. Një numër i konsiderueshëm i proceseve ekonomike, teknike dhe të tjera janë përshkruar mjaft mirë dhe plotësisht nga modelet lineare. Sa më sipër përcakton rëndësinë e rolit të luajtur nga programimi linear - një metodë për të gjetur një ekstrem të kushtëzuar të një funksioni linear në një grup të specifikuar duke përdorur marrëdhënie lineare si barazitë dhe pabarazitë (kufizimet lineare).

Kushtet për zbatueshmërinë e modelit linear

Pjesëtueshmëria. Nëse metoda zbatohet me intensitetet a dhe b (a< b), то его можно применять с любой интенсивностью x .

Kjo gjendje nuk është e parëndësishme. Nëse, për shembull, intensiteti i kryerjes së punës matet me numrin e punonjësve të caktuar për të, atëherë lejohen vetëm vlerat e plota të intensitetit. Nëse intensiteti matet me numrin e orëve të punës në ditë, atëherë parimi i pjesëtueshmërisë, me sa duket, është përmbushur.

proporcionaliteti. Kostot, rezultatet dhe dobia e prodhuar nga secila metodë janë proporcionale me intensitetin e saj.

Ky është një kusht i kthimeve të vazhdueshme (në çdo kuptim), mungesë e ekonomive të shkallës. Vëmendje e veçantë duhet t'i kushtohet identifikimit të gamës së intensitetit të metodës teknologjike, në të cilën kjo metodë plotëson kushtin e proporcionalitetit. Për shembull, nëse një saldator saldon një enë në 6 orë, atëherë dy saldatorë ndoshta mund ta bëjnë punën në 3 orë. Por gjashtë - në një orë - nuk do të bashkojnë enën.

Aditiviteti. Shërbimet dhe - për çdo përbërës - kostot dhe rezultatet e prodhuara nga të gjitha metodat janë përmbledhur.

Parimi i aditivitetit kërkon një përshkrim të saktë dhe të qëndrueshëm të nomenklaturës së përfshirë në model: metodat teknologjike, përbërësit, shërbimet.

Format e shkrimit të problemave të programimit linear

Në formën e tij më të përgjithshme, problemi LP shkruhet si më poshtë:

• 2 (2)
• 3 (3)

• 4 (4)
• 5 (5)

Përkufizimi 1. Matrica quhet matrica e problemit (1) - (5). ?

Një paraqitje më e unifikuar e problemit LP është forma standarde:

për i (1,…, m), x 0.

Karakteristikat e formës standarde: të gjitha variablat janë jonegative (n1 = n), nuk ka kufizime barazie (m1 = 0). Nëse filtri dixhital është maksimizuar, atëherë m2 = 0 dhe nuk ka kufizime të formës (3); përndryshe m2 = m dhe nuk ka kufizime të formës (4). Duke supozuar dhe, forma standarde mund të shkruhet si më poshtë:

6c x max (min) në Ax () b, x 0. (6)

Por forma më e thjeshtë është forma kanonike e shkrimit të problemeve LP.

Përkufizimi 2. Problemi (1) - (4) paraqitet në formë kanonike nëse të gjitha kufizimet, përveç kushteve të jonegativitetit të ndryshoreve, janë barazi (m1 = m) dhe të gjitha variablat janë jonegative (n1 = n) . ?

Problemi LP në formë kanonike pra ka formën

• 7c x max (min) në Ax = b, x 0. (7)
• 1.2 Bazat e metodës simplex

Konsideroni problemin LP në formë kanonike:

• 9 (9)
• 10x 0 (10)

Le të jenë, përkatësisht, rreshti i dhe kolona j e matricës A0. Supozojmë se rreshtat e matricës janë linearisht të pavarura.

Çdo problem LP mund të reduktohet në një formë kanonike; nëse problemi është i zgjidhshëm në formë kanonike, atëherë midis zgjidhjeve të tij ekziston të paktën një pikë ekstreme e grupit të zgjidhjeve të realizueshme; Pikat ekstreme të grupit të zgjidhjeve të pranueshme të problemit LP në formën kanonike përkojnë me BDD.

Bazuar në faktet e mësipërme, mund të imagjinojmë procedurën e mëposhtme për zgjidhjen e problemit. Le të kontrollojmë në një farë mënyre nëse problemi ka një zgjidhje dhe, nëse po, ta reduktojmë atë në formën kanonike. Le të ketë matrica A0 e formës kanonike dimension m × n dhe renditje m. Ne ndërtojmë të gjitha nënmatricat m × m të matricës A0, duke hedhur poshtë nënmatricat e degjeneruara, ndërsa nënmatricat e mbetura korrespondojnë me bazat e matricës A0. Ne zgjedhim bazat e pranueshme prej tyre dhe ndërtojmë BDD-të përkatëse. Le të zgjedhim BDD që jep maksimumin e funksionit objektiv.

Por një algoritëm i tillë nuk mund të zbatohet në praktikë, pasi numri i BDD-ve rritet në mënyrë eksponenciale me rritjen e dimensionit të problemit (numri i variablave dhe/ose kufizimet). Procedura mund të përshpejtohet nëse organizohet në atë mënyrë që vlera e filtrit dixhital të mos ulet në procesin e numërimit të BDR (përmirësimi i njëpasnjëshëm i planit). Kjo është ideja origjinale e metodës simplex, e cila zbatohet si më poshtë.

1. 3 tabela të thjeshta

optimizimi i programimit linear Simplex

Transformimet e problemit LP në formën kanonike të kryera me metodën Simplex mund të përfaqësohen lehtësisht si transformime të tabelave Simplex. Pamja e përgjithshme e tabelës simplex, e cila korrespondon me përsëritjen aktuale të metodës simplex, është tabela 1.

Rreshti i sipërm përmban: titullin e kolonës së parë, identifikuesit e të gjitha variablave (kryesore, shtesë, ndihmëse, etj.) të detyrës dhe titullin e kolonës së fundit. Rreshtat m vijues përshkruajnë ekuacionet e problemit në formën:

që kanë në fillim të përsëritjes. Së pari, specifikohet identifikuesi i ndryshores bazë (në bazën aktuale) për ekuacionin përkatës. Më pas vijojnë koeficientët e variablave (në rendin në të cilin janë shkruar variablat në rreshtin e parë). Elementi i fundit i vargut është ana e djathtë e kufizimit.

Rreshti i fundit korrespondon me ekuacionin

12, ku i. (12)

që përfaqëson CF. Ndryshorja z luan rolin e një ndryshoreje bazë në të (ka koeficient 1 dhe nuk përfshihet në ekuacione të tjera); numri F është ana e djathtë e ekuacionit (12), vlera e filtrit dixhital në zgjidhjen bazë aktuale.

Tabela 1. Pamje e përgjithshme e tabelës simplex

Koment. Tabela përshkruan sistemin e ekuacioneve (11), kështu që BDD aktuale mund të merret duke supozuar se ndryshoret bazë janë të barabarta me elementët përkatës të kolonës së fundit, dhe variablat jo-bazë janë të barabartë me zero. ?

Në përsëritjen e konsideruar, ndodh sa vijon.

Nëse nuk ka elemente negative në rreshtin z, në kolonat që korrespondojnë me variablat, atëherë BDR aktuale është optimale dhe variablat e bazës optimale shkruhen në kolonën e parë të tabelës. Përndryshe, kolona e ndryshores xs për të cilën s< 0, становится направляющим.

Nëse të gjithë elementët e kolonës udhëzuese janë jopozitive, atëherë problemi është i pakufizuar. Përndryshe, ne llogarisim raportin e elementeve të kolonës së fundit dhe asaj kryesore për të gjitha rreshtat që kanë një element pozitiv në kolonën kryesore. Rreshti r, për të cilin ky raport është minimal, bëhet udhëzues. Në kolonën e parë të tabelës së thjeshtë të ardhshme, xs do të zërë vendin e xj(r).

Tani ars është një element aktivizues. Elementet e tabelës së thjeshtë të mëposhtme llogariten me formula:

13 për i r (13)

• 14 (14)
• 15 (15)

Konsideroni j = j(k). Nga (11) dhe (12) rrjedh se kolona j (bazë) ka një njësi në rreshtin k dhe zero në rreshtat e tjerë: j = 0, aij = 1 për i = k, përndryshe aij = 0. Le të jetë k r (kolona j ruhet në bazën e re). Atëherë ari = 0 dhe nga (13), (14), (16) rrjedh se për të gjitha i dhe. Duke marrë parasysh këtë, ne formulojmë rregullat për transformimin e një tabele simplex kur kalojmë në një bazë të re:

• · në titullin e vijës drejtuese vendosim titullin e kolonës drejtuese;
• Ndani të gjithë numrat e vijës udhëzuese me elementin zgjidhës;
• · kolona kryesore bëhet e vetme, me njësinë në rreshtin e parë;
• · kolonat e bazës aktuale me numra të ndryshëm nga j(r) nuk ndryshojnë;
• · Të gjithë numrat e tjerë të tabelës (përfshirë elementët e rreshtit të poshtëm dhe kolonës së fundit) rillogariten sipas formulave (13) - (15), (16).

Programimi linear

Programimi linear- një disiplinë matematikore kushtuar teorisë dhe metodave për zgjidhjen e problemeve ekstreme në bashkësitë e hapësirës vektoriale -dimensionale, të dhëna nga sistemet e ekuacioneve lineare dhe pabarazive.

Programimi linear është një rast i veçantë i programimit konveks, i cili nga ana tjetër është një rast i veçantë i programimit matematik. Në të njëjtën kohë, ajo është baza e disa metodave për zgjidhjen e problemeve të programimit me numra të plotë dhe jolinear. Një përgjithësim i programimit linear është programimi linear i pjesshëm.

Shumë veti të problemeve të programimit linear mund të interpretohen gjithashtu si veti të poliedrave dhe kështu mund të formulohen dhe vërtetohen gjeometrikisht.

Histori

Metoda e pikës së brendshme u përmend për herë të parë nga I. I. Dikin në 1967.

Detyrat

Problemi kryesor (standard) i programimit linear quhet problemi i gjetjes së minimumit të një funksioni objektiv linear (formë lineare) të formës:

sipas kushteve

, .

Problemi i programimit linear do të ketë pamje kanonike , nëse në problemin kryesor në vend të sistemit të parë të pabarazive ekziston një sistem ekuacionesh:

,

Problemi kryesor mund të reduktohet në një kanonik duke futur variabla shtesë.

Problemet e programimit linear të formës më të përgjithshme (probleme me kufizime të përziera: barazi dhe pabarazi, prania e variablave pa kufizime) mund të reduktohen në ekuivalente (që kanë të njëjtin grup zgjidhjesh) ndryshime të variablave dhe zëvendësim të barazive me një palë pabarazitë.

Është e lehtë të shihet se problemi i gjetjes së maksimumit mund të zëvendësohet me problemin e gjetjes së minimumit duke marrë koeficientët me shenjën e kundërt.

Shembuj detyrash

Përputhja maksimale

Merrni parasysh problemin maksimal të përputhjes në një grafik dypalësh: ka disa djem dhe vajza, dhe për çdo djalë dhe vajzë dihet nëse i pëlqen njëri-tjetri. Është e nevojshme të martohen me numrin maksimal të çifteve me simpati reciproke.

Le të prezantojmë variabla që korrespondojnë me një çift nga - ai djalë dhe - ajo vajzë dhe plotësojnë kufizimet:

me funksion objektiv. Mund të tregohet se ndër zgjidhjet optimale të këtij problemi ekziston një zgjidhje me numër të plotë. Variablat e barabartë me 1 do të korrespondojnë me çiftet që duhet të martohen.

Rrjedha maksimale

Le të ketë një grafik (me skaje të drejtuara) në të cilin për secilën skaj tregohet kapaciteti i tij. Dhe jepen dy kulme: një lavaman dhe një burim. Është e nevojshme të specifikohet për secilën skaj se sa lëng do të rrjedhë nëpër të (jo më shumë se kapaciteti i tij) në mënyrë që të maksimizohet rrjedha totale nga burimi në lavaman (lëngu nuk mund të shfaqet ose të zhduket në të gjitha kulmet, përveç lavamanit dhe burimit).

Le të marrim si variabla - sasinë e lëngut që rrjedh nëpër skajin i-të. Pastaj

,

ku është kapaciteti i skajit të i-të. Këto pabarazi duhet të plotësohen nga barazia e sasisë së lëngut hyrës dhe dalës për çdo kulm, me përjashtim të lavamanit dhe burimit. Si funksion, është e natyrshme të merret diferenca midis sasisë së lëngut dalës dhe atij që hyn në burim.

Një përgjithësim i problemit të mëparshëm është fluksi maksimal i kostos minimale. Në këtë problem jepen kostot për çdo skaj dhe është e nevojshme të zgjidhet midis prurjeve maksimale fluksi me kosto minimale. Kjo detyrë reduktohet në dy probleme të programimit linear: së pari, ju duhet të zgjidhni problemin e rrjedhës maksimale, dhe më pas t'i shtoni këtij problemi kufizimin , ku është vlera e fluksit maksimal dhe ta zgjidhni problemin me një funksion të ri - kostoja e rrjedhës.

Këto probleme mund të zgjidhen më shpejt sesa me algoritme të përgjithshme për zgjidhjen e problemeve të programimit linear për shkak të strukturës së veçantë të ekuacioneve dhe pabarazive.

Detyra e transportit

Ekziston një ngarkesë e caktuar homogjene që duhet të transferohet nga magazinat në fabrika. Për çdo magazinë dihet se sa ngarkesë ka në të dhe për çdo fabrikë dihet nevoja e saj për ngarkesë. Kostoja e transportit është në përpjesëtim me distancën nga magazina në uzinë (të gjitha distancat nga magazina e -të deri tek impianti - dihen). Kërkohet të hartohet plani më i lirë i transportit.

Variablat vendimtare në këtë rast janë - sasia e ngarkesës së transportuar nga magazina e -të në impiantin -të. Ata plotësojnë kufizimet:

Funksioni objektiv ka formën: , i cili duhet të minimizohet.

Lojë me shumën zero

Ekziston një matricë madhësie. Lojtari i parë zgjedh një numër nga 1 në , i dyti - nga 1 në . Pastaj ata krahasojnë numrat dhe lojtari i parë merr pikë, dhe i dyti merr pikë ( - numri i zgjedhur nga lojtari i parë, - i dyti). Duhet të gjejmë strategjinë optimale për lojtarin e parë.

Lëreni në strategjinë optimale, për shembull, lojtarin e parë, numri duhet të zgjidhet me probabilitet . Atëherë strategjia optimale është një zgjidhje për problemin e mëposhtëm të programimit linear:

, , (),

në të cilin funksioni duhet të maksimizohet. Vlera në zgjidhjen optimale do të jetë pritshmëria në rastin më të keq të fitimit të lojtarit të parë.

Algoritmet e zgjidhjes

Më e famshmja dhe e përdorur gjerësisht në praktikë për zgjidhjen e problemit të përgjithshëm të programimit linear (LP) është metoda simplex. Pavarësisht se metoda Simplex është një algoritëm mjaft efikas që ka treguar rezultate të mira në zgjidhjen e problemeve të aplikuara LP, është një algoritëm me kompleksitet eksponencial. Arsyeja për këtë është natyra kombinuese e metodës simplex, e cila numëron në mënyrë të njëpasnjëshme kulmet e poliedrit të zgjidhjeve të pranueshme gjatë kërkimit të zgjidhjes optimale.

Algoritmi i parë polinomial, metoda elipsoid, u propozua në vitin 1979 nga matematikani sovjetik L. Khachiyan, duke zgjidhur kështu një problem që kishte mbetur i pazgjidhur për një kohë të gjatë. Metoda elipsoid ka një natyrë krejtësisht të ndryshme, jokombinatore nga metoda simplex. Sidoqoftë, në terma llogaritës, kjo metodë doli të ishte jopremtuese. Sidoqoftë, vetë fakti i kompleksitetit polinomial të problemeve çoi në krijimin e një klase të tërë të algoritmeve efikase LP - Metodat e pikës së brendshme, i pari prej të cilit ishte algoritmi i N. Karmarkar i propozuar në vitin 1984. Algoritmet e këtij lloji përdorin një interpretim të vazhdueshëm të problemit LP, kur në vend që të numërohen kulmet e politopit të zgjidhjeve të problemit LP, bëhet një kërkim përgjatë trajektoreve në hapësirën e ndryshoreve të problemit që nuk kalojnë nëpër kulme. të politopit. Metoda e pikës së brendshme, e cila, ndryshe nga metoda simplex, anashkalon pikat nga pjesa e brendshme e diapazonit të tolerancës, përdor metoda të funksionit të barrierës logaritmike të programimit jolinear të zhvilluara në vitet 1960 nga Fiacco dhe McCormick.

Shiko gjithashtu

• Metoda grafike për zgjidhjen e problemit të programimit linear

Shënime

Letërsia

• Thomas H. Kormen etj. Kapitulli 29. Programimi Linear // Algoritmet: Ndërtimi dhe Analiza = HYRJE NË ALGORITME. - Ed. 2. - M .: "Williams", 2006. - S. 1296. - ISBN 5-8459-0857-4
• Akulich I.L. Kapitulli 1. Probleme të programimit linear, Kapitulli 2. Probleme të veçanta të programimit linear // Programimi matematikor në shembuj dhe problema. - M .: Shkolla e Lartë, 1986. - 319 f. - ISBN 5-06-002663-9
• Karmanov V. G. Programim matematikor. - Botimi i 3-të. - M .: Nauka, 1986. - 288 f.
• Danzig George Bernard "Kujtimet e fillimit të programimit linear"

Lidhjet

• - Paketa e optimizimit falas e krijuar për të zgjidhur problemet e programimit linear, me numra të plotë dhe të synuar.
• Vershik A. M. "Për L. V. Kantorovich dhe programimin linear"
• Bolshakova I. V., Kuralenko M. V. "Programimi linear. Manual edukativo-metodik për punën e kontrollit”.
• Barsov A. S. "Çfarë është programimi linear", Leksione popullore në matematikë, Gostekhizdat, 1959.
• M. N. Vyaly Pabarazitë lineare dhe kombinatorika. - MTsNMO, 2003.

Fondacioni Wikimedia. 2010 .

• Salten, Feliks
• Glagov, Martina

Shihni se çfarë është "Programimi linear" në fjalorë të tjerë:

programimi linear- - programimi linear Fusha e programimit matematikor kushtuar teorisë dhe metodave për zgjidhjen e problemeve ekstreme të karakterizuara nga një marrëdhënie lineare midis ... ... Manuali Teknik i Përkthyesit

Programimi linear

Programimi linear- fusha e programimit matematikor, kushtuar teorisë dhe metodave për zgjidhjen e problemeve ekstreme, e karakterizuar nga një marrëdhënie lineare midis variablave. Në formën më të përgjithshme, L.p. mund të shkruhet kështu. Janë dhënë… … Fjalor Ekonomik dhe Matematik

Programimi linear është një nga degët më të rëndësishme të matematikës që studion teoritë dhe metodat për zgjidhjen e problemeve të caktuara. Kjo disiplinë matematikore është përdorur gjerësisht vitet e fundit në fusha të ndryshme të ekonomisë, teknologjisë dhe çështjeve ushtarake, ku planifikimi matematikor dhe përdorimi i kompjuterëve dixhitalë automatikë luajnë një rol të rëndësishëm në zhvillimin e tyre. Kjo degë e shkencës studion modelet lineare të optimizimit. Me fjalë të tjera, programimi linear ka të bëjë me numrat.

Termi "programim linear" u propozua për herë të parë nga ekonomisti amerikan T. Koopmans në 1951. Në vitin 1975. Matematikani rus L.V. Kantorovich dhe T. Koopmans u nderuan me Çmimin Nobel në Shkencat Ekonomike për kontributin e tyre në teorinë e shpërndarjes optimale të burimeve. T.Kupmans promovoi metodat e programimit linear dhe mbrojti prioritetet e L.V.Kantorovich, i cili zbuloi këto metoda.

Historia e programimit linear në SHBA shkon prapa në vitin 1947, kur J. Dantzig shkroi për të në veprën e tij. L.V. Kantorovich studioi mundësinë e aplikimit të matematikës në çështjet e planifikimit, mbi bazën e së cilës u botua monografia e tij "Metodat matematikore të organizimit dhe planifikimit të prodhimit" në 1939. Gjetja (zbulimi) më i rëndësishëm i L.V. Kantorovich ishte mundësia për të formuluar qartë matematikisht problemet më të rëndësishme të prodhimit, gjë që bën të mundur gjetjen e një qasjeje sasiore ndaj këtyre problemeve, si dhe zgjidhjen e tyre me metoda numerike.

Nëse veprat e para të L.V. Kantorovich do të ishin vlerësuar siç duhet në kohën e tyre, atëherë do të kishte një probabilitet të lartë për përparim edhe më të madh në programimin linear në kohën e tanishme. Fatkeqësisht, puna e tij mbeti në hije si në Bashkimin Sovjetik ashtu edhe më gjerë, dhe, siç vëren Dantzig: "...dhe gjatë kësaj kohe, programimi linear u bë një art i vërtetë".

Plani optimal i çdo programi linear duhet të shoqërohet automatikisht me çmimet optimale ose, sipas L.V. Kantorovich, me "vlerësime të përcaktuara objektivisht". Ky grumbull fjalësh kishte për qëllim të rriste "stabilitetin kritik" të termit. Thelbi i zbulimit ekonomik të L.V. Kantorovich qëndron në marrëdhënien midis zgjidhjeve optimale dhe çmimeve optimale.

Metodat e programimit linear

Me ndihmën e metodave të programimit linear zgjidhen një numër i madh problemesh ekstremale që lidhen me ekonominë. Në këto raste, gjenden vlerat ekstreme (maksimale dhe minimale) të disa funksioneve të variablave.

Baza e programimit linear është zgjidhja e një sistemi ekuacionesh lineare, të cilat shndërrohen në ekuacione dhe pabarazi. Karakterizohet nga një shprehje matematikore e variablave, një renditje e caktuar, një sekuencë llogaritjesh, një analizë logjike. Ai zbatohet:

• në prani të sigurisë matematikore dhe kufizimit sasior ndërmjet variablave dhe faktorëve të studiuar;
• me këmbyeshmërinë e faktorëve për shkak të sekuencës së llogaritjeve;
• në rastin e kombinimit të logjikës matematikore me kuptimin e thelbit të dukurive që studiohen.

Në prodhimin industrial, kjo metodë ndihmon në llogaritjen e produktivitetit të përgjithshëm optimal të makinerive, njësive, linjave të prodhimit (nëse jepet gama e produktit dhe vlerat përkatëse), si dhe zgjidhjen e problemit të përdorimit racional të materialeve (me numri më i favorshëm i boshllëqeve).

Në bujqësi, kjo metodë përdoret për të përcaktuar koston minimale të racioneve të ushqimit, duke marrë parasysh një sasi të caktuar ushqimi (bazuar në llojet dhe lëndët ushqyese që përmbajnë).

Në shkritore, kjo metodë ndihmon për të zgjidhur problemin e përzierjeve që përbëjnë ngarkesën metalurgjike. E njëjta metodë lejon zgjidhjen e problemit të transportit, problemin e lidhjes më optimale të ndërmarrjeve konsumuese me ndërmarrjet që prodhojnë produkte.

Një tipar dallues i të gjitha problemeve ekonomike që mund të zgjidhen duke përdorur metodat e programimit linear është zgjedhja e zgjidhjeve, si dhe disa kushte kufizuese. Zgjidhja e një problemi të tillë do të thotë të zgjedhësh opsionin më optimal nga të gjitha opsionet alternative.

Vlera thelbësore e aplikimit të metodave të programimit linear në ekonomi është zgjedhja e opsionit më optimal nga një numër i madh i të gjitha opsioneve të realizueshme. Në mënyra të tjera, është pothuajse e pamundur të zgjidhen probleme të tilla për të gjetur shkallën e racionalitetit në përdorimin e burimeve në prodhim.

Një nga problemet kryesore që zgjidhet me ndihmën e programimit linear është problemi i transportit, i cili synon të minimizojë qarkullimin e mallrave të konsumit kur ato dorëzohen nga prodhuesi te konsumatori.