Kas see meeldis? Lisa järjehoidjate hulka

Ülesannete lahendamine simpleksmeetodil: veebinäited

Ülesanne 1. Ettevõte toodab vannitoariiuleid kahes suuruses - A ja B. Müügiesindajate hinnangul saab nädalas turule müüa kuni 550 riiulit. Iga A-tüüpi riiuli jaoks on vaja 2 m2 materjali ja iga B-tüüpi riiuli jaoks on vaja 3 m2 materjali. Nädalas saab ettevõte vastu võtta kuni 1200 m2 materjali. Ühe A-tüüpi riiuli valmistamiseks kulub 12 minutit masinaaega ja ühe B-tüüpi riiuli valmistamiseks 30 minutit; Masinat saab kasutada 160 tundi nädalas. Kui A-tüüpi riiulite müügist saadav kasum on 3 rahaühikut ja B-tüüpi riiulitelt - 4 rahaühikut. ühikut, siis mitu riiulit peaks igat tüüpi nädalas tootma?

2. ülesanne. Lahendage probleem lineaarne programmeerimine simpleks meetod.

3. ülesanne. Ettevõte toodab 3 tüüpi tooteid: A1, A2, A3, kasutades kahte tüüpi toorainet. Teada on iga tooraineliigi maksumus toodanguühiku kohta, planeerimisperioodi toorainevarud, samuti iga liigi tootmisühiku kasum.

1. Kui palju igat tüüpi eset tuleb kasumi maksimeerimiseks toota?
2. Määrake iga tooraine liigi staatus ja konkreetne väärtus.
3. Määrata iga tooraineliigi varude muutmise maksimaalne intervall, mille piires optimaalse plaani struktuur, s.o. Tootmisnomenklatuur ei muutu.
4. Määrake toodetud toodete kogus ja tootmisest saadav kasum, kui suurendate ühe defitsiitsete tooraineliikide laovarusid maksimaalse võimaliku (antud toodanguvahemiku piires) väärtuseni.
5. Määrake igat tüüpi toodanguühiku kasumi muutumise intervallid, mille korral saadakse optimaalne plaan ei muutu.

4. ülesanne. Lahendage lineaarse programmeerimise ülesanne simpleks meetod:

5. ülesanne. Lahendage lineaarse programmeerimise probleem, kasutades simpleksmeetodit:

6. ülesanne. Lahendage probleem simpleksmeetodi abil, pidades seda esialgseks võrdlusplaan, tingimuses antud plaan:

Ülesanne 7. Lahendage probleem modifitseeritud simpleksmeetodi abil.
Kahe tüüpi toodete A ja B tootmiseks kasutatakse kolme tüüpi tehnoloogilisi seadmeid. Toote A ühiku tootmiseks kasutavad esimest tüüpi seadmed a1=4 tundi, teist tüüpi seadmed a2=8 tundi ja kolmandat tüüpi seadmed a3=9 tundi. Toote B ühiku tootmiseks kasutavad esimest tüüpi seadmed b1=7 tundi, teist tüüpi seadmed b2=3 tundi ja kolmandat tüüpi seadmed b3=5 tundi.
Esimest tüüpi seadmed võivad nende toodete tootmiseks töötada mitte rohkem kui t1=49 tundi, teist tüüpi seadmed mitte rohkem kui t2=51 tundi, kolmandat tüüpi seadmed mitte rohkem kui t3=45 tundi.
Valmistoote A ühiku müügist saadav kasum on ALPHA = 6 rubla ja toode B on BETTA = 5 rubla.
Koostage toodete A ja B tootmisplaan, tagades nende müügist maksimaalse kasumi.

Ülesanne 8. Leia optimaalne lahendus, kasutades dual simplex meetodit

Vaadeldakse ülesande lahendamise näidet simpleksmeetodil, aga ka lahenduse näidet kahekordne probleem.

Probleemne seisund

Kolme kaubagrupi müügiks äriettevõte omab kolme tüüpi piiratud materiaalseid ja rahalisi ressursse summas b 1 = 240, b 2 = 200, b 3 = 160 ühikut. Samal ajal 1 kaubagrupi müügiks 1000 rubla eest. kaubakäibe korral tarbitakse esimest tüüpi ressurssi a 11 = 2 ühikut, teist tüüpi ressurssi a 21 = 4 ühikut, kolmandat tüüpi ressurssi summas 31 = 4 ühikut. 2 ja 3 kaubagrupi müügiks 1000 rubla eest. käivet tarbitakse vastavalt esimest tüüpi ressursile summas a 12 = 3, a 13 = 6 ühikut, teist tüüpi ressurssi summas a 22 = 2, a 23 = 4 ühikut, ressurssi kolmas tüüp summas a 32 = 6, a 33 = 8 ühikut . Kasum kolme kaubagrupi müügist 1 tuhande rubla eest. käive on vastavalt c 1 = 4, c 2 = 5, c 3 = 4 (tuhat rubla). Määrata kaubanduskäibe planeeritav maht ja struktuur nii, et kasum kaubandusettevõte oli maksimum.

Käibe planeerimise otsesele probleemile lahendatakse simpleksmeetodil, koostada kahekordne probleem lineaarne programmeerimine.
Installige muutujate konjugeeritud paarid otsesed ja topeltprobleemid.
Muutujate konjugeeritud paaride järgi saame otsese ülesande lahendusest topeltprobleemi lahendus, milles seda toodetakse ressursside hindamine, kulutatud kaupade müügile.

Probleemi lahendamine simpleksmeetodi abil

Olgu x 1, x 2, x 3 müüdud kaupade arv tuhandetes rublades, vastavalt 1, 2, 3 rühmas. Siis matemaatiline mudelülesandel on vorm:

F = 4 x 1 + 5 x 2 + 4 x 3 -> max

0)))(~)" title="delim(lbrace)(maatriks(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

Lahendame simpleksmeetodi.

Toome sisse täiendavad muutujad x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, et muuta võrratused võrdsusteks.

Võtame aluseks x 4 = 240; x 5 = 200; x 6 = 160.

Sisestame andmed sisse simpleks laud

Simplex tabel nr 1

Objektiivne funktsioon:

0 240 + 0 200 + 0 160 = 0

Arvutame hinnangud järgmise valemi abil:

Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0

Kuna on negatiivseid hinnanguid, pole plaan optimaalne. Madalaim punktisumma:

Toome baasi sisse muutuja x 2.

Defineerime baasist lähtuva muutuja. Selleks leiame x2 veeru jaoks väikseima mittenegatiivse suhte.

= 26.667

Väikseim mittenegatiivne: Q 3 = 26,667. Muutuja x 6 tuletame baasist

Jagage kolmas rida 6-ga.
1. realt lahutage 3. rida, korrutatuna 3-ga
2. realt lahutage 3. rida, korrutatuna 2-ga

Arvutame:

Me saame uus laud:

Simplex tabel nr 2

Objektiivne funktsioon:

0 160 + 0 440/3 + 5 80/3 = 400/3

Arvutame hinnangud järgmise valemi abil:

Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6

Kuna on negatiivne hinnang Δ 1 = - 2/3, ei ole plaan optimaalne.

Toome baasi sisse muutuja x 1.

Defineerime baasist lähtuva muutuja. Selleks leiame veeru x 1 väikseima mittenegatiivse suhte.

Väikseim mittenegatiivne: Q 3 = 40. Muutuja x 2 tuletame baasist

Jagage 3. rida 2/3-ga.
2. realt lahutage 3. rida, korrutatuna 8/3-ga

Arvutame:

Saame uue tabeli:

Simplex tabel nr 3

Objektiivne funktsioon:

0 160 + 0 40 + 4 40 = 160

Arvutame hinnangud järgmise valemi abil:

Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1

Kuna negatiivseid hinnanguid pole, on plaan optimaalne.

Probleemi lahendus:

Vastus

x 1 = 40; x2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x6 = 0; F max = 160

See tähendab, et on vaja müüa esimest tüüpi kaupu 40 tuhande rubla ulatuses. 2. ja 3. tüüpi tooteid ei ole vaja müüa. Samal ajal maksimaalne kasum on F max = 160 tuhat rubla.

Topeltprobleemi lahendus

Kahekordsel probleemil on vorm:

Z = 240 a 1 + 200 a 2 + 160 a 3 -> min

Title="delim(lbrace)(maatriks(4)(1)((2a_1 + 4a_2 + 4a_3>=4) (3a_1 + 2a_2 + 6a_3>=5) (6a_1 + 4a_2 + 8a_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}

Toome sisse täiendavad muutujad y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0, et muuta võrratused võrdsusteks.

Otsese ja duaalse probleemi muutujate konjugeeritud paarid on järgmisel kujul:

Otsese ülesande viimasest simplekstabelist nr 3 leiame lahenduse duaalülesandele:

Z min = Fmax = 160;
y1 = A4 = 0; y2 = A5 = 0; y3 = A6 = 1; y4 = Δ1 = 0; y5 = A2 = 1; y6 = A3 = 4;

. Simpleksmeetodi algoritm

Näide 5.1. Lahendage simpleksmeetodi abil järgmine lineaarse programmeerimise probleem:

Lahendus:

I iteratsioon:

x3, x4, x5, x6 x1,x2. Väljendame põhimuutujaid vabadena:

Vähendame sihtfunktsiooni järgmine vaade:

Saadud ülesande põhjal moodustame esialgse simplekstabeli:

Tabel 5.3

Originaal simplekslaud

				Hindavad suhted

Põhilahenduse definitsiooni kohaselt on vabad muutujad võrdsed nulliga ja põhimuutujate väärtused on võrdsed vabade arvude vastavate väärtustega, st:

3. etapp: PAP piirangute süsteemi ühilduvuse kontrollimine.

Sellel iteratsioonil (tabelis 5.3) ei tuvastata piirangusüsteemi mittevastavuse märki (märk 1) (st ei ole negatiivse vaba arvuga rida (v.a sihtfunktsiooni rida), milles seda poleks olema vähemalt üks negatiivne element (st vaba muutuja negatiivne koefitsient)).

Sellel iteratsioonil (tabelis 5.3) sihtfunktsiooni piiramatuse märki (märk 2) ei tuvastatud (st sihtfunktsiooni real ei ole negatiivse elemendiga veergu (v.a vabade arvude veerg). ), milles poleks vähemalt üht positiivset elementi) .

Kuna leitud põhilahendus ei sisalda negatiivseid komponente, on see lubatav.

6. etapp: optimaalsuse kontroll.

Leitud põhilahendus ei ole optimaalne, kuna optimaalsuse kriteeriumi (märk 4) järgi ei tohiks sihtfunktsiooni real olla negatiivseid elemente ( tasuta number seda joont ei võeta selle tunnuse arvestamisel arvesse). Seetõttu liigume vastavalt simpleksmeetodi algoritmile 8. etappi.

Kuna leitud põhilahend on lubatav, siis otsime lahendavat veergu järgmise skeemi järgi: määrame sihtfunktsiooni real negatiivsete elementidega veerud (v.a vabade arvude veerg). Tabeli 5.3 kohaselt on kaks sellist veergu: veerg “ x1" ja veerg " x2" Sellistest veergudest valitakse see, mis sisaldab sihtfunktsiooni rea väikseimat elementi. Temast saab lubaja. veerg " x2" sisaldab väikseimat elementi (–3) võrreldes veeruga " x1

Lahutusjoone määramiseks leiame vabade arvude positiivsed hinnangulised suhted lahutusveeru elementidega, mis võetakse lahendatuks.

Tabel 5.4

Originaal simplekslaud

Tabelis 5.4 vastab väikseim positiivne hinnanguline seos reale “ x5"Seepärast on see lubatav.

Lubava veeru ja lubamisrea ristumiskohas asuv element loetakse lubavaks. Meie näites on see element, mis asub joone " ristumiskohas x5" ja veerud " x2».

Lahenduselement näitab ühte alust ja ühte vaba muutujat, mis tuleb simplekstabelis vahetada, et liikuda uuele "täiustatud" baaslahendusele. IN antud juhul need on muutujad x5 Ja x2, uues simplekstabelis (tabel 5.5) vahetame need ära.

9.1. Lahutava elemendi transformatsioon.

Tabeli 5.4 eraldusvõime element teisendatakse järgmiselt:

Saadud tulemuse sisestame sarnasesse lahtrisse tabelis 5.5.

9.2. Eraldusvõime stringi teisendamine.

Jagame tabeli 5.4 lahutusrea elemendid selle simplekstabeli lahutuselemendiga, tulemused mahuvad uue simplekstabeli (tabel 5.5) sarnastesse lahtritesse. Resolutsioonistringi elementide teisendused on toodud tabelis 5.5.

9.3. Eraldusvõime veeru teisendamine.

Jagame tabeli 5.4 eraldusvõime veeru elemendid selle simplekstabeli eraldusvõime elemendiga ja tulemus võetakse vastupidine märk. Saadud tulemused sobivad uue simplekstabeli sarnastesse lahtritesse (tabel 5.5). Eraldusvõime veeru elementide teisendused on toodud tabelis 5.5.

9.4. Simplekstabeli ülejäänud elementide teisendus.

Ülejäänud simplekstabeli elementide (st elemendid, mis ei asu lahutusreas ja lahutusveerus) teisendamine toimub ristküliku reegli järgi.

Näiteks kaaluge joone ristumiskohas asuva elemendi teisendamist x3" ja veerud "", tähistame seda tingimuslikult " x3" Tabelis 5.4 joonistame mõtteliselt ristküliku, mille üks tipp asub lahtris, mille väärtust me teisendame (st lahtris " x3") ja teine ​​(diagonaaltipp) on lahutuselemendiga lahtris. Ülejäänud kaks tippu (teise diagonaali) on üheselt määratud. Seejärel lahtri teisendatud väärtus " x3" on võrdne selle lahtri eelmise väärtusega, millest on lahutatud murdosa, mille nimetajas on lahutuselement (tabelist 5.4) ja lugejas on kahe teise kasutamata tipu korrutis, st:

« x3»: .

Teiste lahtrite väärtused teisendatakse sarnaselt:

« x 3 x 1»: ;

« x4»: ;

« x4x1»: ;

« x6»: ;

« x 6 x 1»: ;

«»: ;

« x1»: .

Nende ümberkujundamiste tulemusena saime uue simpleks laud(Tabel 5.5).

II iteratsioon:

1. etapp: simplekstabeli koostamine.

Tabel 5.5

Simplex tabelII iteratsioonid

				Hinnanguline suhe

2. etapp: põhilahuse määramine.

Simpleksteisenduste tulemusena saadi uus aluseline lahendus (tabel 5.5):

Nagu näete, on selle põhilahenduse korral sihtfunktsiooni väärtus 15, mis on suurem kui eelmise põhilahenduse puhul.

Tabeli 5.5 tunnuse 1 kohase piirangute süsteemi vastuolu ei ole tuvastatud.

4. etapp: sihtfunktsiooni piirituse kontrollimine.

Tabeli 5.5 kriteeriumi 2 kohase sihtfunktsiooni piiramatust ei selgu.

5. etapp: leitud põhilahenduse vastuvõetavuse kontrollimine.

Kriteeriumile 4 vastav leitud põhilahend ei ole optimaalne, kuna simplekstabeli (tabel 5.5) eesmärkfunktsiooni rida sisaldab negatiivset elementi: –2 (selle rea vaba arvu selle arvestamisel arvesse ei võeta iseloomulik). Seetõttu liigume edasi 8. etapi juurde.

8. etapp: lahutuselemendi määramine.

8.1. Eraldusvõime veeru määratlus.

Leitud põhilahendus on vastuvõetav, määrame sihtfunktsiooni real negatiivsete elementidega veerud (va vabade arvude veerg). Tabeli 5.5 kohaselt on ainult üks selline veerg: “ x1" Seetõttu aktsepteerime seda lubatud kujul.

8.2. Lubamisstringi definitsioon.

Tabelis 5.6 saadud positiivsete hindamissuhete väärtuste järgi on miinimumiks reale " vastav seos. x3" Seetõttu aktsepteerime seda lubatud kujul.

Tabel 5.6

Simplex tabelII iteratsioonid

				Hinnanguline suhe
				3/1=3 – min

9. etapp: simplekstabeli teisendus.

Simplekstabeli (tabel 5.6) teisendused sooritatakse samamoodi nagu eelmises iteratsioonis. Simplekstabeli elementide teisenduste tulemused on toodud tabelis 5.7.

III iteratsioon

Eelmise iteratsiooni simpleksteisenduste tulemuste põhjal koostame uue simplekstabeli:

Tabel 5.7

Simplex tabelIII iteratsioonid

				Hinnanguline suhe

2. etapp: põhilahuse määramine.

Simpleksteisenduste tulemusena saadi uus aluseline lahendus (tabel 5.7):

3. etapp: piirangute süsteemi ühilduvuse kontrollimine.

Tabeli 5.7 tunnuse 1 kohase piirangute süsteemi vastuolu ei ole tuvastatud.

4. etapp: sihtfunktsiooni piirituse kontrollimine.

Tabeli 5.7 kriteeriumi 2 kohase sihtfunktsiooni piiramatust ei selgu.

5. etapp: leitud põhilahenduse vastuvõetavuse kontrollimine.

Leitud põhilahendus vastavalt kriteeriumile 3 on vastuvõetav, kuna see ei sisalda negatiivseid komponente.

6. etapp: leitud põhilahenduse optimaalsuse kontrollimine.

Kriteeriumile 4 vastav leitud põhilahend ei ole optimaalne, kuna simplekstabeli (tabel 5.7) sihtfunktsiooni rida sisaldab negatiivset elementi: –3 (selle rea vaba arvu selle arvestamisel arvesse ei võeta iseloomulik). Seetõttu liigume edasi 8. etapi juurde.

8. etapp: lahutuselemendi määramine.

8.1. Eraldusvõime veeru määratlus.

Leitud põhilahendus on vastuvõetav, määrame sihtfunktsiooni real negatiivsete elementidega veerud (va vabade arvude veerg). Tabeli 5.7 kohaselt on ainult üks selline veerg: “ x5" Seetõttu aktsepteerime seda lubatud kujul.

8.2. Lubamisstringi definitsioon.

Vastavalt tabelis 5.8 saadud positiivsete hindamissuhete väärtustele on miinimumiks reale " vastav seos. x4" Seetõttu aktsepteerime seda lubatud kujul.

Tabel 5.8

Simplex tabelIII iteratsioonid

				Hinnanguline suhe
				5/5=1 – min

9. etapp: simplekstabeli teisendus.

Simplekstabeli (tabel 5.8) teisendused sooritatakse samamoodi nagu eelmises iteratsioonis. Simplekstabeli elementide teisenduste tulemused on toodud tabelis 5.9.

IV iteratsioon

1. etapp: uue simplekslaua ehitamine.

Eelmise iteratsiooni simpleksteisenduste tulemuste põhjal koostame uue simplekstabeli:

Tabel 5.9

Simplex tabelIV iteratsioonid

				Hinnanguline suhe
			–(–3/5)=3/5
			–(1/5)=–1/5
			–(9/5)=–9/5
			–(–3/5)=3/5

2. etapp: põhilahuse määramine.

Simpleksteisenduste tulemusena saadi uus põhilahend vastavalt tabelile 5.9, lahend on järgmine:

3. etapp: piirangute süsteemi ühilduvuse kontrollimine.

Tabeli 5.9 tunnuse 1 kohase piirangute süsteemi vastuolu ei ole tuvastatud.

4. etapp: sihtfunktsiooni piirituse kontrollimine.

Tabeli 5.9 kriteeriumi 2 kohase sihtfunktsiooni piiramatust ei selgu.

5. etapp: leitud põhilahenduse vastuvõetavuse kontrollimine.

Leitud põhilahendus vastavalt kriteeriumile 3 on vastuvõetav, kuna see ei sisalda negatiivseid komponente.

6. etapp: leitud põhilahenduse optimaalsuse kontrollimine.

Leitud põhilahendus vastavalt tunnusele 4 on optimaalne, kuna simplekstabeli (tabel 5.9) sihtfunktsiooni real ei ole negatiivseid elemente (selle tunnuse arvestamisel selle rea vaba arvu ei võeta arvesse) .

7. etapp: lahenduse alternatiivsuse kontrollimine.

Leitud lahendus on unikaalne, kuna sihtfunktsiooni rida (tabel 5.9) ei sisalda null elementi(selle tunnuse arvestamisel selle rea vaba numbrit ei võeta arvesse).

Vastus: optimaalne väärtus vaadeldava probleemi eesmärkfunktsioon =24, mis saavutatakse juures.

Näide 5.2. Lahendage ülaltoodud lineaarse programmeerimise probleem tingimusel, et sihtfunktsioon on minimeeritud:

Lahendus:

I iteratsioon:

1. etapp: algse simplekstabeli moodustamine.

Algne probleem lineaarne programmeerimine on määratletud standardvorm. Toome selle juurde kanooniline vorm lisades igasse ebavõrdsuse piirangusse täiendava mittenegatiivse muutuja, s.o.

Saadud võrrandisüsteemis võtame lubatud (põhi)muutujad x3, x4, x5, x6, siis on vabad muutujad x1,x2. Väljendame põhimuutujaid vabadena.

Lihtne meetod on iteratiivne protsess võrrandisüsteemi samm-sammult suunatud lahendamiseks, mis algab võrdluslahendusest ja otsib parim variant liigub mööda teostatava lahendusala nurgapunkte, parandades sihtfunktsiooni väärtust, kuni sihtfunktsioon saavutab optimaalse väärtuse.

Teenuse eesmärk. Teenus on mõeldud võrgulahendused Lineaarse programmeerimise probleemid (LPP), kasutades simpleksmeetodit järgmised vormid sissekanded:

• simplekstabeli kujul (Jordaania teisendusmeetod); põhivorm rekordid;
• modifitseeritud simpleksmeetod; veeru kujul; rea kujul.

Juhised. Valige muutujate arv ja ridade arv (piirangute arv). Saadud lahust hoitakse Wordi fail ja Excel.

Muutujate arv 2 3 4 5 6 7 8 9 10
Ridade arv (piirangute arv) 1 2 3 4 5 6 7 8 9 10

Sel juhul ärge võtke arvesse selliseid piiranguid nagu x i ≥ 0. Kui mõne x i ülesandes pole piiranguid, tuleb ZLP teisendada KZLP-ks või kasutada seda teenust. Lahendamisel määratakse kasutus automaatselt M-meetod(lihtmeetod kunstlikul alusel) ja kaheastmeline simpleksmeetod.

Selle kalkulaatoriga kasutatakse ka järgmist:
Graafiline meetod ZLP lahendamiseks
Transpordiprobleemi lahendus
Maatriksmängu lahendamine
Teenuse kasutamine sisse võrgurežiim saab määrata maatriksmängu hinda (alumine ja ülemine piir), kontrollida sadulapunkti olemasolu, leida lahendus segastrateegiale järgmiste meetoditega: minimax, simplex meetod, graafiline (geomeetriline) meetod, Browni meetod .
Kahe muutuja funktsiooni ekstreemum
Dünaamilise programmeerimise probleemid
Jagage 5 homogeenset kaubapartii kolme turu vahel, et saada maksimaalne sissetulek nende müügist. Müügitulu igal turul G(X) sõltub toote X müüdud partiide arvust ja on esitatud tabelis.

Toote maht X (partiidena)	Tulu G(X)
	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

Simpleksmeetodi algoritm sisaldab järgmisi samme:

1. Esimese põhiplaani koostamine. Mine aadressile kanooniline vorm lineaarse programmeerimise probleemid mittenegatiivsete lisabilansi muutujate kasutuselevõtuga.
2. Plaani optimaalsuse kontrollimine. Kui on vähemalt üks indeksjoone koefitsient väiksem kui null, siis pole plaan optimaalne ja vajab täiustamist.
3. Juhtveeru ja rea ​​määramine. Indeksirea negatiivsetest koefitsientidest valitakse suurim absoluutväärtus. Seejärel jagatakse simplekstabeli vabaliikme veeru elemendid juhtveeru sama märgi elementideks.
4. Uue võrdlusplaani koostamine. Uuele plaanile üleminek toimub simplekstabeli ümberarvutamise tulemusena Jordani-Gaussi meetodi abil.

Kui on vaja leida sihtfunktsiooni ekstreemum, siis me räägime otsingu kohta minimaalne väärtus(F(x) → min , vt funktsiooni minimeerimise lahendamise näide) ja maksimaalne väärtus((F(x) → max , vaata funktsiooni maksimeerimise lahendamise näidet)

Äärmuslik lahendus saavutatakse teostatavate lahenduste piirkonna piiril polügooni nurgapunktide ühes tipus või kahe külgneva nurgapunkti vahelisel lõigul.

Lineaarse programmeerimise alusteoreem. Kui ZLP eesmärgifunktsioon saavutab teostatavate lahenduste piirkonnas mingil hetkel äärmusliku väärtuse, võtab see selle väärtuse nurgapunktis. Kui ZLP eesmärgifunktsioon saavutab äärmusliku väärtuse rohkem kui ühes nurgapunktis, võtab see sama väärtuse mis tahes kumeras lineaarne kombinatsioon need punktid.

Simpleksmeetodi olemus. Liikumine optimaalsesse punkti toimub liikudes ühest nurgapunktist naaberpunkti, mis toob X optile lähemale ja kiiremini. Selline punktide loendamise skeem, nimetatakse simpleksmeetodiks, soovitas R. Danzig.
Nurgapunkte iseloomustavad m põhimuutujat, seega saab ülemineku ühest nurgapunktist külgnevasse, muutes ainult ühe baasis oleva põhimuutuja mittealuseliseks muutujaks.
Kehtiva simpleksmeetodi rakendamine erinevaid funktsioone ja probleemiavaldused, LP-l on mitmesuguseid modifikatsioone.

Simplekslaudade ehitamine jätkub kuni optimaalse lahenduse saamiseni. Kuidas saate simplekstabeli abil kindlaks teha, kas lineaarse programmeerimise probleemi lahendus on optimaalne?
Kui viimane rida (sihtfunktsiooni väärtused) ei sisalda negatiivseid elemente, leiab see optimaalse plaani.

Märkus 1. Kui üks põhimuutujatest on võrdne nulliga, siis sellisele põhilahendusele vastav äärmuspunkt on degenereerunud. Degeneratsioon tekib siis, kui juhtjoone valikul on ebaselgust. Kui valite juhiseks mõne muu rea, ei pruugi te probleemi degeneratsiooni üldse märgata. Ebaselguse korral tuleks silmuse vältimiseks valida madalaima indeksiga rida.

Märkus 2. Olgu mingis äärmuslikus punktis kõik simplekserinevused mittenegatiivsed D k ³ 0 (k = 1..n+m), s.o. saadakse optimaalne lahendus ja on olemas selline A k - mittebaasvektor, mille puhul D k ​​= 0. Siis saavutatakse maksimum vähemalt kahes punktis, s.o. on olemas alternatiivne optimum. Kui sisestame selle muutuja x k baasi, siis sihtfunktsiooni väärtus ei muutu.

Märkus 3. Duaalülesande lahendus on viimases simplekstabelis. Simpleksierinevuste vektori viimast m komponenti (bilansimuutujate veergudes) on duaalülesande optimaalne lahendus. Otseste ja topeltprobleemide sihtfunktsioonide väärtused optimaalsetes punktides langevad kokku.

Märkus 4. Minimeerimisülesande lahendamisel sisestatakse baasi suurima positiivse simpleksi erinevusega vektor. Järgmisena rakendatakse sama algoritmi nagu maksimeerimisprobleemi puhul.

Kui on märgitud tingimus “III tüüpi tooraine on vaja täielikult ära tarbida”, siis on vastav tingimus võrdsus.

See meetod on meetod lineaarse programmeerimisprobleemi viitelahenduste sihipäraseks loendamiseks. See võimaldab piiratud arvu sammudega kas leida optimaalse lahenduse või tuvastada, et optimaalset lahendust pole.

Simpleksmeetodi põhisisu on järgmine:

1. Märkige meetod optimaalse võrdluslahenduse leidmiseks
2. Märkige ühelt etalonlahenduselt teisele ülemineku meetod, mille korral on sihtfunktsiooni väärtus optimaalsele lähemal, s.t. näidata viisi, kuidas võrdluslahendust parandada
3. Määrake kriteeriumid, mis võimaldavad teil koheselt lõpetada tugilahenduste otsimise optimaalse lahenduse juures või teha järelduse optimaalse lahenduse puudumise kohta.

Lineaarse programmeerimise ülesannete lahendamise simpleksmeetodi algoritm

Probleemi lahendamiseks simpleksmeetodi abil peate tegema järgmist.

1. Viige probleem kanoonilisse vormi
2. Leia esialgne tugilahendus “ühikupõhiselt” (kui tugilahendus puudub, siis pole probleemil lahendust piirangute süsteemi sobimatuse tõttu)
3. Arvutage võrdluslahenduse põhjal vektorite lagunemiste hinnangud ja täitke simpleksmeetodi tabel
4. Kui optimaalse lahenduse unikaalsuse kriteerium on täidetud, siis ülesande lahendamine lõpeb
5. Kui optimaalsete lahenduste hulga olemasolu tingimus on täidetud, siis leitakse kõik optimaalsed lahendused lihtsa loendamise teel

Näide ülesande lahendamisest simpleksmeetodil

Näide 26.1

Lahendage probleem simpleksmeetodi abil:

Lahendus:

Toome probleemi kanoonilisse vormi.

Sel eesmärgil sisse vasak pool Esimese ebavõrdsuse piirangu jaoks võtame kasutusele täiendava muutuja x 6 koefitsiendiga +1. Muutuja x 6 on kaasatud sihtfunktsiooni koefitsiendiga null (st seda ei kaasata).

Saame:

Leiame esmase tugilahenduse. Selleks võrdsustame vabad (lahendamata) muutujad nulliga x1 = x2 = x3 = 0.

Me saame võrdluslahus X1 = (0,0,0,24,30,6) ühiku baasiga B1 = (A4, A5, A6).

Me arvutame vektorite lagunemise hinnangud tingimused võrdluslahuse alusel vastavalt valemile:

Δ k = C b X k - c k

• C b = (c 1, c 2, ..., c m) - põhimuutujate sihtfunktsiooni koefitsientide vektor
• X k = (x 1k, x 2k, ..., x mk) - vastava vektori A k laienemise vektor võrdluslahenduse alusel
• C k on muutuja x k sihtfunktsiooni koefitsient.

Aluses sisalduvate vektorite hinnangud on alati võrdsed nulliga. Võrdluslahendus, laienduste koefitsiendid ja tingimuste vektorite laienduste hinnangud võrdluslahenduse alusel on kirjas simpleks laud:

Tabeli ülaossa on hinnangute arvutamise mugavuse huvides kirjas sihtfunktsiooni koefitsiendid. Esimesse veergu "B" kirjutatakse võrdluslahenduse alusesse kuuluvad vektorid. Nende vektorite kirjutamise järjekord vastab piiranguvõrrandites lubatud tundmatute arvule. Tabeli "C b" teise veergu kirjutatakse põhimuutujate sihtfunktsiooni koefitsiendid samas järjekorras. Kell õige asukoht Alusesse kuuluvate ühikvektorite hinnangu veerus "C b" olevad sihtfunktsiooni koefitsiendid on alati võrdsed nulliga.

IN viimane rida tabelites hinnangutega Δ k veerus “A 0” on kirjas sihtfunktsiooni väärtused võrdluslahendil Z(X 1).

Algne tugilahendus ei ole optimaalne, kuna maksimumülesandes on vektorite A 1 ja A 3 hinnangud Δ 1 = -2, Δ 3 = -9 negatiivsed.

Tugilahenduse parendamise teoreemi kohaselt, kui maksimaalses ülesandes on vähemalt ühe vektori hinnang negatiivne, siis saab leida uue tugilahenduse, millel on sihtfunktsiooni väärtus suurem.

Teeme kindlaks, milline kahest vektorist toob kaasa sihtfunktsiooni suurema tõusu.

Sihtfunktsiooni juurdekasv leitakse valemiga: .

Arvutame parameetri θ 01 väärtused esimese ja kolmanda veeru jaoks järgmise valemi abil:

Saame θ 01 = 6, kui l = 1, θ 03 = 3, kui l = 1 (tabel 26.1).

Sihtfunktsiooni juurdekasvu leiame, kui sisestame baasi esimese vektori ΔZ 1 = - 6*(- 2) = 12 ja kolmanda vektori ΔZ 3 = - 3*(- 9) = 27.

Järelikult on optimaalse lahenduse kiiremaks lähenemiseks vaja aluse A6 esimese vektori asemel etalonlahenduse baasi sisestada vektor A3, kuna esimeses reas saavutatakse parameetri θ 03 miinimum ( l = 1).

Jordani teisenduse teostame elemendiga X13 = 2, teise võrdluslahendi X2 = (0,0,3,21,42,0) saame alusega B2 = (A3, A4, A5). (Tabel 26.2)

See lahendus ei ole optimaalne, kuna vektoril A2 on negatiivne hinnang Δ2 = - 6. Lahenduse parandamiseks on vaja viia vektor A2 võrdluslahenduse baasi.

Määrame baasist tuletatud vektori arvu. Selleks arvutame teise veeru jaoks parameetri θ 02, see on 7, kui l = 2. Sellest tulenevalt tuletame baasist teise baasvektori A4. Jordani teisenduse teostame elemendiga x 22 = 3, saame kolmanda võrdluslahendi X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (tabel 26.3).

See lahendus on ainuke optimaalne, kuna kõikide vektorite puhul, mis ei sisaldu baasis, on hinnangud positiivsed

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Vastus: max Z(X) = 201 at X = (0,7, 10, 0,63).

Lineaarne programmeerimismeetod majandusanalüüsis

Lineaarne programmeerimismeetod võimaldab põhjendada kõige optimaalsemat majanduslik otsus rangete piirangute tingimustes, mis on seotud tootmises kasutatavate ressurssidega (põhivara, materjalid, tööjõuressursid). Selle meetodi kasutamine majandusanalüüsis võimaldab lahendada peamiselt organisatsiooni tegevuse planeerimisega seotud probleeme. See meetod aitab määrata optimaalseid väljundtasemeid ja kõige rohkem juhiseid tõhus kasutamine organisatsiooni käsutuses olevad tootmisressursid.

Selle meetodi abil lahendatakse nn äärmuslikud probleemid, mis seisneb äärmuslike väärtuste ehk funktsioonide maksimumi ja miinimumi leidmises. muutujad.

See periood põhineb lineaarsete võrrandite süsteemi lahendamisel juhtudel, kui analüüsitavad majandusnähtused on seotud lineaarselt, rangelt funktsionaalne sõltuvus. Lineaarse programmeerimise meetodit kasutatakse muutujate analüüsimiseks teatud piiravate tegurite olemasolul.

Väga levinud lahendus on nn transpordi probleem kasutades lineaarse programmeerimise meetodit. Selle ülesande sisuks on hooldusvajaduse korral minimeerida kulusid, mis tekivad seoses sõidukite käitamisega olemasolevate sõidukite arvu, kandevõime, ekspluatatsiooni kestuse piirangute juures. maksimaalne kogus klientidele.

Peale selle, seda meetodit kasutatakse laialdaselt ajastamisprobleemide lahendamisel. See ülesanne seisneb sellises tegevusaja jagamises antud organisatsiooni personalile, mis oleks kõige vastuvõetavam nii selle personali liikmetele kui ka organisatsiooni klientidele.

Selle ülesande eesmärk on maksimeerida teenindatavate klientide arvu, kui töötajate arv ja tööajafond on piiratud.

Seega on lineaarne programmeerimismeetod paigutuse ja kasutuse analüüsimisel üsna levinud. erinevat tüüpi ressursse, samuti organisatsioonide tegevuse planeerimise ja prognoosimise protsessis.

Sellegipoolest saab matemaatilist programmeerimist rakendada ka nende majandusnähtuste puhul, mille vaheline seos ei ole lineaarne. Sel eesmärgil saab kasutada mittelineaarseid, dünaamilisi ja kumeraid programmeerimismeetodeid.

Mittelineaarne programmeerimine tugineb eesmärgifunktsiooni või piirangute või mõlema mittelineaarsele olemusele. Nendes tingimustes võivad sihtfunktsiooni ja ebavõrdsuse piirangute vormid olla erinevad.

Mittelineaarset programmeerimist kasutatakse majandusanalüüsis, eelkõige organisatsiooni tegevuse tõhusust väljendavate näitajate ja selle tegevuse mahu, tootmiskulude struktuuri, turutingimuste jms vahelise seose kindlakstegemisel.

Dünaamiline programmeerimine põhineb otsustuspuu koostamisel. Selle puu iga tasand toimib tagajärgede kindlaksmääramise etapina eelmine otsus ja kõrvaldada selle lahenduse ebatõhusad võimalused. Seega dünaamiline programmeerimine on mitmeastmeline, mitmeastmeline. Seda tüüpi programmeerimist kasutatakse leidmiseks majandusanalüüsis optimaalsed võimalused organisatsiooni arengut nii praegu kui ka tulevikus.

Kumer programmeerimine on mittelineaarse programmeerimise tüüp. Seda tüüpi programmeerimine väljendab organisatsiooni tegevuse tulemuste ja selle kulude vahelise seose mittelineaarset olemust. Kumer (aka nõgus) programmeerimine analüüsib kumerat objektiivsed funktsioonid ja kumerad piirangute süsteemid (punktid vastuvõetavad väärtused). Kumerprogrammeerimist kasutatakse majandustegevuse analüüsimisel eesmärgiga minimeerida kulusid ja nõgusat programmeerimist eesmärgiga maksimeerida tulu olemasolevate piirangute korral analüüsitavaid näitajaid vastupidiselt mõjutavate tegurite mõjul. Järelikult on vaadeldavate programmeerimistüüpide puhul kumerad eesmärgifunktsioonid minimeeritud ja nõgusad eesmärgifunktsioonid maksimeeritud.