Ang pinakamainam na halaga ng layunin ng function ay tinatawag. Paglutas ng mga problema sa linear programming gamit ang graphical na pamamaraan

Bumuo tayo sa eroplano ng isang hanay ng mga magagawang solusyon sa sistema ng mga linear na hindi pagkakapantay-pantay at geometrically hanapin ang pinakamababang halaga ng layunin ng function.

Bumubuo kami ng mga tuwid na linya sa x 1 x 2 coordinate system

Natagpuan namin ang kalahating eroplano na tinukoy ng system. Dahil ang mga hindi pagkakapantay-pantay ng sistema ay nasiyahan para sa anumang punto sa kaukulang kalahating eroplano, sapat na upang suriin ang mga ito para sa anumang isang punto. Ginagamit namin ang punto (0;0). Ipalit natin ang mga coordinate nito sa unang hindi pagkakapantay-pantay ng system. kasi , pagkatapos ay tinutukoy ng hindi pagkakapantay-pantay ang isang kalahating eroplano na hindi naglalaman ng punto (0;0). Pareho naming tinukoy ang natitirang kalahating eroplano. Nakita namin ang hanay ng mga magagawang solusyon bilang karaniwang bahagi ng mga nagresultang kalahating eroplano - ito ang may kulay na lugar.

Bumubuo kami ng isang vector at isang linya ng zero level na patayo dito.

Ang paglipat ng tuwid na linya (5) sa direksyon ng vector at nakikita natin na ang pinakamataas na punto ng rehiyon ay nasa punto A ng intersection ng tuwid na linya (3) at tuwid na linya (2). Nahanap namin ang solusyon sa sistema ng mga equation:

Nangangahulugan ito na nakuha namin ang punto (13;11) at.

Ang paglipat ng tuwid na linya (5) sa direksyon ng vector at makikita natin na ang pinakamababang punto ng rehiyon ay nasa punto B ng intersection ng tuwid na linya (1) at tuwid na linya (4). Nahanap namin ang solusyon sa sistema ng mga equation:

Nangangahulugan ito na nakuha namin ang punto (6;6) at.

2. Ang isang kumpanya ng muwebles ay gumagawa ng pinagsamang mga cabinet at computer table. Ang kanilang produksyon ay limitado sa pamamagitan ng pagkakaroon ng mga hilaw na materyales (mataas na kalidad na mga board, mga kabit) at ang oras ng pagpapatakbo ng mga makina na nagpoproseso sa kanila. Ang bawat cabinet ay nangangailangan ng 5 m2 ng mga board, para sa isang table - 2 m2. Ang mga fitting ay nagkakahalaga ng $10 para sa isang cabinet, at $8 para sa isang table. Maaaring makatanggap ang kumpanya mula sa mga supplier nito ng hanggang 600 m2 ng mga board bawat buwan at mga accessories na nagkakahalaga ng $2,000. Ang bawat cabinet ay nangangailangan ng 7 oras ng pagpapatakbo ng makina, at ang talahanayan ay nangangailangan ng 3 oras. May kabuuang 840 oras ng pagpapatakbo ng makina ang maaaring gamitin bawat buwan.

Ilang kumbinasyong cabinet at computer table ang dapat gawin ng isang kumpanya bawat buwan para mapakinabangan ang mga kita kung ang isang cabinet ay maghahatid ng $100 na tubo at ang bawat desk ay magdadala ng $50?

• 1. Gumawa matematikal na modelo problema at lutasin ito gamit ang simplex method.
• 2. Gumawa ng mathematical model ng dual problem, isulat ang solusyon nito batay sa solusyon sa orihinal.
• 3. Itatag ang antas ng kakulangan ng mga mapagkukunang ginamit at bigyang-katwiran ang kakayahang kumita ng pinakamainam na plano.
• 4. Tuklasin ang mga posibilidad ng karagdagang pagtaas ng output ng produksyon depende sa paggamit ng bawat uri ng mapagkukunan.
• 5. Tayahin ang pagiging posible ng pagpapakilala ng isang bagong uri ng produkto - mga istante, kung ang paggawa ng isang istante ay nagkakahalaga ng 1 m 2 ng mga board at accessories na nagkakahalaga ng $5, at kinakailangang gumastos ng 0.25 oras ng pagpapatakbo ng makina at ang kita mula sa pagbebenta ng ang isang istante ay $20.
• 1. Bumuo tayo ng mathematical model para sa problemang ito:

Tukuyin natin sa pamamagitan ng x 1 ang dami ng produksyon ng mga cabinet, at x 2 ang dami ng produksyon ng mga talahanayan. Gumawa tayo ng isang sistema ng mga paghihigpit at isang function ng layunin:

Malutas namin ang problema gamit ang simplex na pamamaraan. Isulat natin ito sa canonical form:

Isulat natin ang data ng gawain sa anyo ng isang talahanayan:

Talahanayan 1

kasi Ngayon ang lahat ng mga delta ay mas malaki kaysa sa zero, pagkatapos ay isang karagdagang pagtaas sa halaga ng function ng layunin f ay imposible at nakakuha kami ng isang pinakamainam na plano.

KONTROL ANG GAWAIN SA DISIPLINA:

“MGA PARAAN NG MGA OPTIMAL NA SOLUSYON”

Opsyon Blg. 8

1. Magpasya graphical na pamamaraan problema sa linear programming. Hanapin ang maximum at minimum ng function na may ibinigay na mga paghihigpit:

,

.

Solusyon

Ito ay kinakailangan upang mahanap ang pinakamababang halaga ng layunin ng pag-andar at ang maximum, sa ilalim ng sistema ng mga paghihigpit:

9x 1 +3x 2 ≥30, (1)

X 1 +x 2 ≤4, (2)

x 1 +x 2 ≤8, (3)

Bumuo tayo ng rehiyon ng mga magagawang solusyon, i.e. Solusyonan natin ang sistema ng mga hindi pagkakapantay-pantay nang grapiko. Upang gawin ito, itinatayo namin ang bawat tuwid na linya at tinukoy ang kalahating eroplano na tinukoy ng mga hindi pagkakapantay-pantay (ang kalahating eroplano ay ipinahiwatig ng isang prime).

Ang intersection ng mga kalahating eroplano ay magiging isang rehiyon na ang mga coordinate ng punto ay nakakatugon sa mga hindi pagkakapantay-pantay ng sistema ng mga hadlang ng problema. Tukuyin natin ang mga hangganan ng lugar ng polygon ng solusyon.

Bumuo tayo ng isang tuwid na linya na naaayon sa halaga ng function F = 0: F = 2x 1 +3x 2 = 0. Ang gradient vector, na binubuo ng mga coefficient ng objective function, ay nagpapahiwatig ng direksyon ng minimization ng F(X). Ang simula ng vector ay point (0; 0), ang dulo ay point (2; 3). Ililipat namin ang linyang ito sa parallel na paraan. Dahil kami ay interesado sa minimal na solusyon, samakatuwid ay inililipat namin ang tuwid na linya hanggang sa una itong mahawakan ang itinalagang lugar. Sa graph, ang tuwid na linyang ito ay ipinapahiwatig ng isang tuldok na linya.

Diretso
nag-intersect sa rehiyon sa punto C. Dahil nakuha ang point C bilang resulta ng intersection ng mga linya (4) at (1), ang mga coordinate nito ay nakakatugon sa mga equation ng mga linyang ito:
.

Nang malutas ang sistema ng mga equation, nakukuha natin ang: x 1 = 3.3333, x 2 = 0.

Paano natin mahahanap ang pinakamababang halaga ng layunin ng function: .

Isaalang-alang natin target na function mga gawain.

Bumuo tayo ng isang tuwid na linya na tumutugma sa halaga ng function F = 0: F = 2x 1 +3x 2 = 0. Ang gradient vector, na binubuo ng mga coefficient ng layunin function, ay nagpapahiwatig ng direksyon ng pag-maximize ng F(X). Ang simula ng vector ay point (0; 0), ang dulo ay point (2; 3). Ililipat namin ang tuwid na linyang ito sa parallel na paraan. Dahil interesado kami sa maximum na solusyon, samakatuwid ay inililipat namin ang tuwid na linya hanggang sa huling pagpindot sa itinalagang lugar. Sa graph, ang tuwid na linyang ito ay ipinapahiwatig ng isang tuldok na linya.

Diretso
nag-intersect sa rehiyon sa punto B. Dahil nakuha ang punto B bilang resulta ng intersection ng mga linya (2) at (3), ang mga coordinate nito ay nakakatugon sa mga equation ng mga linyang ito:

.

Paano natin mahahanap ang pinakamataas na halaga ng layunin ng function: .

Sagot:
At
.

2 . Lutasin ang isang linear programming problem gamit ang simplex method:

.

Solusyon

Lutasin natin ang isang direktang linear programming problem gamit ang simplex method, gamit ang simplex table.

Tukuyin natin ang pinakamababang halaga ng layunin ng function
sa ilalim ng mga sumusunod na kundisyon-paghihigpit:
.

Upang makabuo ng unang reference na plano, binabawasan namin ang sistema ng mga hindi pagkakapantay-pantay sa isang sistema ng mga equation sa pamamagitan ng pagpapakilala ng mga karagdagang variable.

Sa unang hindi pagkakapantay-pantay ng kahulugan (≥) ipinakilala namin ang pangunahing variable x 3 na may minus sign. Sa ika-2 hindi pagkakapantay-pantay ng kahulugan (≤) ipinakilala namin ang pangunahing variable x 4 . Sa ika-3 hindi pagkakapantay-pantay ng kahulugan (≤) ipinakilala namin ang pangunahing variable x 5 .

Ipakilala natin ang mga artipisyal na variable : sa unang pagkakapantay-pantay ay ipinakilala namin ang isang variable x 6 ;

Upang itakda ang problema sa pinakamababa, isinusulat namin ang layunin ng function bilang mga sumusunod: .

Para sa paggamit ng mga artipisyal na variable na ipinakilala sa layunin ng pag-andar, isang tinatawag na parusa ng M ang ipinapataw, isang napakalaking positibong numero na karaniwang hindi tinukoy.

Ang resultang batayan ay tinatawag na artipisyal, at ang paraan ng solusyon ay tinatawag na paraan ng artipisyal na batayan.

Bukod dito, ang mga artipisyal na variable ay hindi nauugnay sa nilalaman ng problema, ngunit ginagawang posible na bumuo ng isang panimulang punto, at ang proseso ng pag-optimize ay pinipilit ang mga variable na ito na kumuha ng mga zero na halaga at matiyak ang pagiging matanggap ng pinakamainam na solusyon.

Mula sa mga equation ay nagpapahayag kami ng mga artipisyal na variable: x 6 = 4-x 1 -x 2 +x 3, na pinapalitan namin sa layunin ng function: o.

Coefficient matrix
Ang sistemang ito ng mga equation ay may anyo:
.

Lutasin natin ang sistema ng mga equation para sa mga pangunahing variable: x 6 , x 4 , x 5.

Ipagpalagay na ang mga libreng variable ay katumbas ng 0, nakuha namin ang una sangguniang plano:

X1 = (0,0,0,2,10,4)

Ang pangunahing solusyon ay tinatawag na tinatanggap kung ito ay hindi negatibo.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Ang kasalukuyang reference plan ay hindi optimal dahil may mga positive coefficient sa index line. Bilang nangungunang column, pipiliin namin ang column na tumutugma sa variable x 2, dahil ito ang pinakamalaking coefficient. Kalkulahin natin ang mga halaga D i at mula sa kanila pipiliin namin ang pinakamaliit: min(4: 1, 2: 2, 10: 2) = 1.

Samakatuwid, ang 2nd line ang nangunguna.

Ang elemento ng paglutas ay katumbas ng (2) at matatagpuan sa intersection ng nangungunang column at ng nangungunang hilera.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Binubuo namin ang susunod na bahagi ng simplex table. Sa halip na variable x 4, isasama sa plan 1 ang variable x 2.

Ang row na tumutugma sa variable x 2 sa plan 1 ay nakukuha sa pamamagitan ng paghahati sa lahat ng elemento ng row x 4 ng plan 0 ng resolving element RE = 2. Sa lugar ng elemento ng paglutas ay nakakakuha tayo ng 1. Sa natitirang mga cell ng x 2 column ay nagsusulat tayo ng mga zero.

Kaya, sa bagong plano 1, napuno ang row x 2 at column x 2. Ang lahat ng iba pang elemento ng bagong plano 1, kabilang ang mga elemento ng index row, ay tinutukoy ng parihaba na panuntunan.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 2
x 5
		1 1/2 +1 1/2 M

Ang kasalukuyang reference plan ay hindi optimal dahil may mga positive coefficient sa index row. Bilang nangungunang column, pipiliin namin ang column na tumutugma sa variable x 1, dahil ito ang pinakamalaking coefficient. Kalkulahin natin ang mga halaga D i sa pamamagitan ng hilera bilang isang quotient ng dibisyon: at mula sa kanila pinipili namin ang pinakamaliit: min (3: 1 1 / 2, -, 8: 2) = 2.

Samakatuwid, ang unang linya ay ang nangunguna.

Ang elemento ng paglutas ay katumbas ng (1 1/2) at matatagpuan sa intersection ng nangungunang column at ng nangungunang hilera.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6		1 1 / 2
x 2
x 5
		-1 1 / 2 +1 1 / 2 M

Binubuo namin ang susunod na bahagi ng simplex table. Sa halip na ang variable na x 6, ang plan 2 ay isasama ang variable na x 1.

Kumuha kami ng bagong simplex table:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Walang mga positibong halaga sa mga halaga ng index string. Samakatuwid, tinutukoy ng talahanayang ito ang pinakamainam na plano para sa problema.

Ang huling bersyon ng simplex table:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Dahil walang mga artipisyal na variable sa pinakamainam na solusyon (ang mga ito ay katumbas ng zero), ang solusyon na ito ay tinatanggap.

Ang pinakamainam na plano ay maaaring isulat tulad ng sumusunod: x 1 = 2, x 2 = 2:.

Sagot:
,
.

3. Ang kumpanyang Three Fat Men ay naghahatid ng de-latang karne mula sa tatlong bodega na matatagpuan sa iba't ibang bahagi ng lungsod hanggang sa tatlong tindahan. Ang mga stock ng de-latang pagkain na makukuha sa mga bodega, pati na rin ang dami ng mga order sa tindahan at mga rate ng paghahatid (sa maginoo na mga yunit ng pananalapi) ay ipinakita sa talahanayan ng transportasyon.

Maghanap ng plano sa transportasyon na nagbibigay ng pinakamababang halaga ng pera (gawin ang paunang plano sa transportasyon gamit ang paraan ng "northwest corner").

Solusyon

Suriin natin ang kinakailangan at sapat na kondisyon para sa pagkalutas ng problema:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Ang kondisyon ng balanse ay natutugunan. Nagbibigay ng pantay na pangangailangan. Samakatuwid, ang modelo problema sa transportasyon ay sarado.

Ipasok natin ang paunang data sa talahanayan ng pamamahagi.

Pangangailangan

Gamit ang paraan ng kanto sa hilagang-kanluran, bubuo kami ng unang sangguniang plano ng problema sa transportasyon.

Nagsisimulang punan ang plano mula sa kaliwang sulok sa itaas.

Ang kinakailangang elemento ay 4. Para sa elementong ito, ang mga imbentaryo ay 300, ang mga kinakailangan ay 250. Dahil ang minimum ay 250, ibinabawas namin ito: .

			300 - 250 = 50
250 - 250 = 0

Ang kinakailangang elemento ay katumbas ng 2. Para sa elementong ito, ang mga imbentaryo ay 50, ang mga kinakailangan ay 400. Dahil ang minimum ay 50, ibinabawas namin ito: .

			50 - 50 = 0
	400 - 50 = 350

Ang kinakailangang elemento ay 5. Para sa elementong ito, ang mga imbentaryo ay 300, ang mga kinakailangan ay 350. Dahil ang minimum ay 300, ibinabawas namin ito:

			300 - 300 = 0
	350 - 300 = 50

Ang kinakailangang elemento ay 3. Para sa elementong ito, ang mga imbentaryo ay 200, ang mga kinakailangan ay 50. Dahil ang minimum ay 50, ibinabawas namin ito:

			200 - 50 = 150
	50 - 50 = 0

Ang kinakailangang elemento ay 6. Para sa elementong ito, ang mga imbentaryo ay 150, ang mga kinakailangan ay 150. Dahil ang minimum ay 150, ibinabawas namin ito:

			150 - 150 = 0
		150 - 150 = 0

Pangangailangan

Laboratory work No. 1. Paglutas ng mga problema sa linear programming

Layunin ng trabaho Pagkakaroon ng mga kasanayan sa paglutas ng mga problema sa linear programming gamit ang mga graphical, simplex at Excel na mga pamamaraan.

Ang problema ng linear programming ay ang pag-aaral ng mga paraan upang mahanap ang maximum o minimum na mga halaga ng isang linear function sa pagkakaroon ng mga linear na hadlang. Ang layunin ng function ay isang function na ang maximum o minimum na halaga ay natagpuan. Ang hanay ng mga halaga ng mga variable kung saan ang maximum o minimum na mga halaga ay nakamit ay tinatawag na isang pinakamainam na solusyon (pinakamainam na plano), ang anumang iba pang hanay ng mga halaga na nakakatugon sa mga paghihigpit ay tinatawag na isang tinatanggap na solusyon (tinatanggap na plano).

Geometric na paraan ng solusyon ako Tingnan natin ang mga problema sa linear programming gamit ang isang halimbawa.

Halimbawa. Hanapin ang pinakamataas na halaga ng layunin ng function L=2x 1 +2x 2 sa ilalim ng ibinigay na mga paghihigpit

Solusyon. Buuin natin ang domain ng solusyon ng sistema ng mga hadlang, binabago ang mga palatandaan ng hindi pagkakapantay-pantay sa eksaktong mga palatandaan ng pagkakapantay-pantay:

l 1: 3x 1 -2x 2 +6=0,

l 2: 3x 1 +x 2 -3=0,

l 3:x 1 -3=0.

DSA

2 0 1 3 X 1

(l 1) (l 3)

Diretso l 1 ang naghahati sa eroplano X TUNGKOL SA sa sa dalawang kalahating eroplano, kung saan kailangan mong pumili ng isa na nakakatugon sa unang hindi pagkakapantay-pantay sa system (3). Upang gawin ito, kunin natin ang t. TUNGKOL SA(0; 0) at palitan ito ng hindi pagkakapantay-pantay. Kung ito ay totoo, pagkatapos ay kailangan mong lilim ang kalahating eroplano mula sa tuwid na linya kung saan matatagpuan ang tinatawag. TUNGKOL SA(0; 0). Gawin ang parehong sa mga tuwid na linya. l 2 at l 3. Ang domain ng mga solusyon sa hindi pagkakapantay-pantay (3) ay isang polygon ABCD. Para sa bawat punto sa eroplano ang function L tumatagal ng isang nakapirming halaga L=L 1 . Ang hanay ng lahat ng kasalukuyang mga punto ay isang tuwid na linya L=c 1 x 1 +c 2 x 2 (sa aming kaso L=2x 1 +2x 2), patayo sa vector SA(Sa 1 ;Sa 2) (SA(2; 2)), nagmula sa pinanggalingan. Kung ang linyang ito ay inilipat sa positibong direksyon ng vector Sa, pagkatapos ay ang layunin function L tataas, kung hindi ay bababa ito. Kaya, sa aming kaso, ang tuwid na linya sa exit mula sa polygon ABCD ang mga desisyon ay dadaan sa tinatawag na SA(3; 7.5), at samakatuwid ay kasama. SA ang layunin ng function ay tumatagal ng pinakamataas na halaga, i.e. L max =2ּ3+2ּ7.5=21. Katulad nito, tinutukoy na ang pinakamababang halaga na kinukuha ng function ay D(1; 0) at L min =2ּ1+2ּ0=2.

Ang algorithm ng simplex na paraan para sa paglutas ng isang linear na problema sa programming ay ang mga sumusunod.

1. Pangkalahatang gawain Ang linear programming ay binabawasan sa isang kanonikal na problema (ang mga hadlang ay naglalaman ng pantay na mga senyales) sa pamamagitan ng pagpapakilala ng maraming auxiliary na mga variable dahil may mga hindi pagkakapantay-pantay sa sistema ng mga hadlang.

2. Ang layunin function ay ipinahayag sa pamamagitan ng mga pangunahing at auxiliary variable.

3. Ang unang simplex table ay pinagsama-sama. Ang mga variable na may kaugnayan sa kung saan ang sistema ng mga paghihigpit ay pinahihintulutan ay nakasulat sa batayan (pinakamainam na kumuha ng mga auxiliary variable bilang mga batayan). Inililista ng unang hilera ng talahanayan ang lahat ng mga variable at nagbibigay ng column para sa mga libreng termino. Ang mga coefficient ng function ng layunin na may kabaligtaran na mga palatandaan ay nakasulat sa huling hilera ng talahanayan.

4. Ang bawat simplex table ay nagbibigay ng solusyon sa isang linear na problema sa programming: ang mga libreng variable ay katumbas ng zero, ang mga pangunahing variable ay katumbas ng mga libreng termino, ayon sa pagkakabanggit.

5. Ang pinakamainam na pamantayan ay ang kawalan ng mga negatibong elemento sa huling hilera ng talahanayan para sa paglutas ng maximum na problema at positibong elemento para sa minimum.

6. Upang mapabuti ang solusyon, kinakailangan na lumipat mula sa isang simplex na talahanayan patungo sa isa pa. Upang gawin ito, maghanap ng pangunahing column sa nakaraang talahanayan na tumutugma sa pinakamaliit na negatibong elemento sa huling hilera ng talahanayan sa maximum na problema at ang pinakamalaking positive coefficient sa pinakamababang problema. Pagkatapos ay matatagpuan ang isang pangunahing hilera na tumutugma sa pinakamababang ratio ng mga libreng termino sa mga katumbas na positibong elemento ng pangunahing hanay. Sa intersection ng isang key column at isang key row ay ang pangunahing elemento.

7. Sinimulan naming punan ang sumusunod na talahanayan ng simplex sa pamamagitan ng pagpuno sa batayan: ang variable na naaayon sa key row ay hinango mula sa batayan, at ang variable na naaayon sa key column ay ipinasok sa lugar nito. Ang mga elemento ng dating key string ay nakukuha sa pamamagitan ng paghahati ng dating elemento sa key one. Ang mga elemento ng dating key column ay nagiging mga zero, maliban sa pangunahing elemento, na isa. Ang lahat ng iba pang elemento ay kinakalkula gamit ang parihaba na panuntunan:

8. Ang pagbabago ng mga simplex na talahanayan ay isinasagawa hanggang sa makuha ang isang pinakamainam na plano.

Halimbawa. Hanapin ang maximum na halaga ng isang function
, kung mga variable
matugunan ang sistema ng mga paghihigpit:

Solusyon. 1. Ipakilala ang mga bagong variable
, sa tulong kung saan binabago natin ang mga hindi pagkakapantay-pantay ng system sa mga equation:

Binabago namin ang tanda ng mga coefficient ng layunin ng function o isulat ito sa form
. Pinupunan namin ang unang simplex table, sa zero line na isinusulat namin X 1 ,X 2 at (libreng logro). Sa zero column - X 3 ,X 4 ,X 5 at F. Pinupunan namin ang talahanayang ito gamit ang nagresultang sistema ng mga equation at ang binagong layunin na function.

Sinusuri namin ang pamantayan ng optimality upang mahanap ang maximum na halaga: sa huling linya, dapat na positibo ang lahat ng coefficient. Hindi natutugunan ang pamantayang ito, kaya nagpapatuloy kami sa pag-compile ng pangalawang talahanayan.

2. Hanapin ang elemento ng paglutas ng unang talahanayan tulad ng sumusunod. Kabilang sa mga elemento ng huling hilera, pipiliin namin ang pinakamalaking negatibong koepisyent sa magnitude (ito ay -3) at kunin ang pangalawang hanay bilang paglutas. Kung ang lahat ng mga coefficient ng column ay hindi positibo, kung gayon
.

Upang matukoy ang hilera ng paglutas, hinahati namin ang mga libreng coefficient sa mga kaukulang elemento ng column ng paglutas at piliin ang pinakamababang ratio, habang hindi kami kumukuha ng mga negatibong coefficient. Meron kami
, ang pangalawang linya ay pinahihintulutan. Ang intersection ng resolving row at column ay nagbibigay ng resolving element - ito ay 3.

3. Punan ang pangalawang simplex table. Ang mga variable sa intersection kung saan nakuha namin ang isang elemento ng paglutas ay pinapalitan, i.e. At . Pinapalitan namin ang elemento ng paglutas ng kabaligtaran nito, i.e. sa. Ang mga elemento ng row at column sa paglutas (maliban sa elemento ng paglutas) ay nahahati sa elemento ng paglutas. Sa kasong ito, binabago namin ang tanda ng mga coefficient ng column ng resolution.

Ang natitirang mga elemento ng pangalawang talahanayan ay nakuha gamit ang parihaba na panuntunan mula sa mga elemento ng unang talahanayan. Para mapuno ang cell at ang cell na may elemento ng paglutas, gumawa kami ng isang parihaba. Pagkatapos, mula sa elemento para sa cell na mapunan, ibinabawas namin ang produkto ng mga elemento ng iba pang dalawang vertices, na hinati sa paglutas ng elemento. Ipakita natin ang mga kalkulasyon gamit ang panuntunang ito upang punan ang unang hilera ng pangalawang talahanayan:

.

Patuloy naming pinupunan ang mga talahanayan ayon sa mga panuntunang ito hanggang sa matugunan ang pamantayan. Mayroon pa kaming dalawang mesa para sa aming gawain.

	X 1	X 4					X 3	X 2
X 3						X 1
X 2						X 2
X 5						X 5

4. Ang resulta ng pagpapatupad ng algorithm na ito ay nakasulat bilang mga sumusunod. Sa huling talahanayan, ang elemento sa intersection ng row
at kolum b, ay nagbibigay ng pinakamataas na halaga ng layunin ng function. Sa kaso natin
. Ang mga halaga ng mga variable ng row ay katumbas ng mga libreng coefficient. Para sa problema natin meron tayo
.

Mayroong iba pang mga paraan upang mag-compile at punan ang mga simplex na talahanayan. Halimbawa, para sa yugto 1, ang lahat ng mga variable at libreng coefficient ay naitala sa zero line ng talahanayan. Matapos mahanap ang elemento ng paglutas gamit ang parehong mga panuntunan sa sumusunod na talahanayan, pinapalitan namin ang variable sa zero na column, ngunit hindi sa row. Hinahati namin ang lahat ng elemento ng allowing line sa pamamagitan ng allowing element at isulat ang mga ito sa isang bagong table. Para sa natitirang mga elemento ng hanay ng resolusyon nagsusulat kami ng mga zero. Susunod, ginagawa namin ang tinukoy na algorithm na isinasaalang-alang ang mga panuntunang ito.

Kapag nilulutas ang isang linear na problema sa programming para sa isang minimum, ang pinakamalaking positibong koepisyent ay pinili sa huling linya, at ang tinukoy na algorithm ay isinasagawa hanggang sa walang mga positibong koepisyent sa huling linya.

Ang paglutas ng mga problema sa linear programming gamit ang Excel ay isinasagawa bilang mga sumusunod.

Upang malutas ang mga problema sa linear programming, gamitin ang add-on sa Solution Search. Una kailangan mong tiyakin na ang add-in na ito ay naroroon sa tab na Data sa pangkat ng Pagsusuri (para sa 2003, tingnan ang Mga Tool). Kung nawawala ang command na Find a Solution o ang Analysis group, dapat mong i-download ang add-in na ito.

Upang gawin ito, i-click ang Microsoft Office File (2010), pagkatapos ay i-click ang Excel Options button. Sa lalabas na window ng Excel Options, piliin ang Add-in box sa kaliwa. Sa kanang bahagi ng window, ang halaga ng Control na field ay dapat itakda sa Excel Add-in, i-click ang "Go" na buton, na matatagpuan sa tabi ng field na ito. Sa window ng Add-Ins, piliin ang checkbox sa tabi ng Find a solution at i-click ang OK. Pagkatapos ay maaari kang magtrabaho kasama ang naka-install na Search for Solutions add-on.

Bago tumawag sa Search for a Solution, kailangan mong maghanda ng data para sa paglutas ng isang linear programming problem (mula sa isang mathematical model) sa isang worksheet:

1) Tukuyin ang mga cell kung saan ilalagay ang resulta ng solusyon para dito sa unang linya na ipinasok namin ang mga variable at ang layunin na pag-andar. Hindi namin pinupunan ang pangalawang linya (nababagong mga cell) sa mga cell na ito ang pinakamainam na resulta ay makukuha. Ipasok ang data para sa layunin ng function sa susunod na linya, at ang sistema ng mga paghihigpit (coefficients para sa mga hindi alam) sa susunod na mga linya. Kanang bahagi ang mga paghihigpit (libreng coefficients) ay ipinakilala, na nag-iiwan ng isang libreng cell pagkatapos i-record ang mga coefficient ng sistema ng mga paghihigpit.

2) Ipakilala ang isang dependence sa variable na mga cell para sa layunin ng function at isang dependence sa variable na mga cell para sa kaliwang bahagi ng constraint system sa natitirang libreng mga cell. Upang ipakilala ang mga formula ng dependency, maginhawang gamitin ang mathematical function na SUMPRODUCT.

Susunod, kailangan mong gamitin ang Search for a solution add-on. Sa tab na Data, sa pangkat ng Pagsusuri, piliin ang Maghanap ng Solusyon. Lalabas ang dialog box ng Search for Solution, na dapat kumpletuhin gaya ng sumusunod:

1) Tukuyin ang cell na naglalaman ng objective function sa field na "Optimize objective function" (dapat maglaman ang cell na ito ng formula para sa objective na function). Piliin ang opsyon para sa pag-optimize ng halaga ng target na cell (pagmaximize, pagliit):

2) Sa field na "Pagbabago ng mga variable na cell," ilagay ang mga cell upang baguhin. Sa susunod na patlang na "Alinsunod sa mga paghihigpit", ipasok ang tinukoy na mga paghihigpit gamit ang pindutang "Idagdag". Sa lalabas na window, ipasok ang mga cell na naglalaman ng mga formula ng constraint system, piliin ang constraint sign at ang constraint value (libreng koepisyent):

3) Lagyan ng check ang checkbox na "Gawing hindi negatibo ang mga variable na walang limitasyon." Piliin ang paraan ng solusyon na "Paghahanap ng mga solusyon sa mga linear na problema gamit ang simplex na paraan." Pagkatapos i-click ang pindutang "Hanapin ang solusyon", magsisimula ang proseso ng paglutas ng problema. Bilang resulta, ang dialog box na "Mga Resulta sa Paghahanap ng Solusyon" at ang paunang talahanayan na may mga punong cell para sa mga variable na halaga at ang pinakamainam na halaga ng layunin ng function.

Halimbawa. Lutasin ang isang linear programming problem gamit ang Excel Solution Add-in: hanapin ang maximum na halaga ng isang function
sa ilalim ng mga paghihigpit

,

;

,
.

Solusyon. Upang malutas ang aming problema, isagawa natin ang tinukoy na algorithm sa isang worksheet ng Excel. Ipasok ang paunang data sa anyo ng isang talahanayan

Ipinakilala namin ang mga dependency para sa layunin na pag-andar at ang sistema ng mga hadlang. Upang gawin ito, ilagay ang formula =SUMPRODUCT(A2:B2;A3:B3) sa cell C2. Sa mga cell C4 at C5, ayon sa pagkakabanggit, ang mga formula ay: =SUMPRODUCT(A2:B2,A4:B4) at =SUMPRODUCT(A2:B2,A5:B5). Bilang resulta, nakakakuha kami ng isang mesa.

Patakbuhin ang command na "Search for a solution" at punan ang Search for a solution window na lalabas tulad ng sumusunod. Sa field na "I-optimize ang layunin ng function," ilagay ang cell C2. Piliin ang pag-optimize ng target na halaga ng cell na "Maximum".

Sa field na "Pagbabago ng mga variable na cell," ilagay ang mga nagbabagong cell A2:B2. Sa field na "Alinsunod sa mga paghihigpit", ipasok ang tinukoy na mga paghihigpit gamit ang pindutang "Magdagdag". Mga sanggunian sa cell $C$4:$C$5 Mga sanggunian sa mga paghihigpit =$D$4:$D$5 sa pagitan nila sign<= затем кнопку «ОК».

Lagyan ng check ang checkbox na "Gawing hindi negatibo ang mga variable na walang limitasyon." Piliin ang paraan ng solusyon na "Paghahanap ng mga solusyon sa mga linear na problema gamit ang simplex na paraan."

Ang pag-click sa pindutang "Hanapin ang solusyon" ay magsisimula sa proseso ng paglutas ng problema. Bilang resulta, ang dialog box na "Mga Resulta sa Paghahanap ng Solusyon" at ang orihinal na talahanayan na may mga punong cell para sa mga variable na halaga at ang pinakamainam na halaga ng layunin ng function ay lilitaw.

Sa dialog box na "Mga Resulta sa Paghahanap ng Solusyon," i-save ang resulta x1=0.75, x2=0.75, F=1.5 - katumbas ng maximum na halaga ng layunin ng function.

Mga gawain para sa malayang gawain

Ehersisyo 1. Gamit ang mga graphical, simplex na pamamaraan at Excel tool, hanapin ang maximum at minimum na halaga ng isang function F(x) sa ilalim ng isang ibinigay na sistema ng mga paghihigpit.

1. F(x)=10x 1 +5x 2 2. F(x)=3x 1 -2x 2

3. F(x)=3x 1 +5x 2 4. F(x)=3x 1 +3x 2

5. F(x)=4x 1 -3x 2 6. F(x)=2x 1 -x 2

7. F(x)=-2x 1 +4x 2 8. F(x)=4x 1 -3x 2

9. F(x)=5x 1 +10x 2 10. F(x)=2x 1 +x 2

11. F(x)=x 1 +x 2 12. F(x)=3x 1 +x 2

13. F(x)=4x 1 +5x 2 14. F(x)=3x 1 +2x 2

15. F(x)=-x 1 -x 2 16. F(x)=-3x 1 -5x 2

17. F(x)=2x 1 +3x 2 18. F(x)=4x 1 +3x 2

19. F(x)=-3x 1 -2x 2 20. F(x)=-3x 1 +4x 2

21. F(x)=5x 1 -2x 2 22. F(x)=-2x 1 +3x 3

23. F(x)=2x 1 +3x 2 24. F(x)=4x 1 +3x 2

25. F(x)=-3x 1 -2x 2 26. F(x)=-3x 1 +4x 2

27. F(x)=-2x 1 +4x 2 28. F(x)=4x 1 -3x 2

29. F(x)=-x 1 -x 2 30. F(x)=-3x 1 -5x 2

Kontrolin ang mga tanong.

1. Anong mga problema ang tinatawag na mga problema sa linear programming?

2. Magbigay ng mga halimbawa ng mga problema sa linear programming.

3. Paano nalulutas ang problema sa linear programming gamit ang graphical na pamamaraan?

4. Ilarawan ang algorithm ng simplex na paraan para sa paglutas ng mga problema sa linear programming.

5. Ilarawan ang isang algorithm para sa paglutas ng mga problema sa linear programming gamit ang Excel.

Pederal na Ahensya para sa Edukasyon

Institusyong pang-edukasyon sa badyet ng estado

mas mataas na propesyonal na edukasyon

"Omsk State Technical University"

PAGKUKULALA AT GRAPHIC WORK

sa pamamagitan ng disiplina"OPTIMAL CONTROL THEORY »

Naaayon sa paksa "MGA PARAAN NG OPTIMISATION AT PANANALIKSIK SA OPERASYON »

opsyon 7

Nakumpleto:

mag-aaral ng sulat

4th year group na ZA-419

Buong pangalan: Kuzhelev S. A.

Sinuri:

Devyaterikova M.V.

Omsk - 2012
^

Gawain 1. Graphical na paraan para sa paglutas ng mga problema sa linear programming.

7) 7x 1 + 6x 2 → max 20x 1 + 6x 2 ≤ 15 16x 1 − 2x 2 ≤ 18 8x 1 + 4x 2 ≤ 20 13x 1 + 3x 2 ≤ 4 x 1 , x 2 ≥ 0.

Hakbang 1: Pagbuo ng Magagawang Rehiyon

Ang mga kondisyon para sa hindi negatibong mga variable at parisukat ay naglilimita sa saklaw ng kanilang mga pinahihintulutang halaga sa unang kuwadrante. Ang bawat isa sa natitirang apat na hindi pagkakapantay-pantay na mga hadlang ng modelo ay tumutugma sa isang tiyak na kalahating eroplano. Ang intersection ng mga kalahating eroplano na ito sa unang kuwadrante ay bumubuo ng hanay ng mga magagawang solusyon sa problema.

Ang unang hadlang ng modelo ay may anyo . Ang pagpapalit ng ≤ sign sa loob nito ng = sign, makuha namin ang equation . Sa Fig. 1.1 Tinutukoy nito ang isang tuwid na linya (1), na naghahati sa eroplano sa dalawang kalahating eroplano, sa kasong ito sa itaas ng linya at sa ibaba nito. Upang piliin kung alin ang makakatugon sa hindi pagkakapantay-pantay , palitan dito ang mga coordinate ng anumang punto na hindi nakahiga sa isang naibigay na linya (halimbawa, ang pinagmulan X 1 = 0, X 2 = 0). Dahil nakuha namin ang tamang expression (20 0 + 6 0 = 0 ≤15), kung gayon ang kalahating eroplano na naglalaman ng pinagmulan ng mga coordinate (minarkahan ng isang arrow) ay nakakatugon sa hindi pagkakapantay-pantay. Kung hindi, isa pang kalahating eroplano.

Nagpapatuloy kami nang katulad sa natitirang mga hadlang ng problema. Ang intersection ng lahat ng constructed half-planes na may unang quadrant forms A B C D(tingnan ang Fig. 1). Ito ang posibleng lugar ng problema.

Hakbang 2. Pagguhit ng level line Level line Ang layunin ng function ay ang hanay ng mga punto sa eroplano kung saan ang layunin ng function ay tumatagal ng isang pare-parehong halaga. Ang nasabing set ay ibinibigay ng equation f ( x) = const. Ilagay natin, halimbawa, const = 0 at gumuhit ng linya sa antas f ( x) = 0, ibig sabihin. sa aming kaso tuwid na linya 7 x 1 + 6x 2 = 0.

Ang linyang ito ay dumadaan sa pinanggalingan at patayo sa vector. Ang vector na ito ay ang gradient ng layunin ng function sa punto (0,0). Ang gradient ng isang function ay isang vector ng mga halaga ng mga partial derivatives ng isang naibigay na function sa puntong pinag-uusapan. Sa kaso ng problema sa LP, ang mga partial derivatives ng layunin na function ay katumbas ng coefficients Cako, j = 1 , ..., n.

Ipinapakita ng gradient ang direksyon ng pinakamabilis na paglaki ng function. Paglipat ng linya ng antas ng layunin ng function f ( x) = const. patayo sa direksyon ng gradient, makikita natin ang huling punto kung saan ito nagsa-intersect sa rehiyon. Sa aming kaso, ito ang punto D, na magiging pinakamataas na punto ng layunin ng function (tingnan ang Fig. 2)

Ito ay nasa intersection ng mga linya (2) at (3) (tingnan ang Fig. 1) at tinutukoy ang pinakamainam na solusyon.

^ Tandaan na kung nais mong mahanap ang pinakamababang halaga ng layunin ng function, ang linya ng antas ay inilipat sa direksyon na kabaligtaran sa direksyon ng gradient.

^ Hakbang 3. Pagtukoy sa mga coordinate ng maximum (minimum) point at ang pinakamainam na halaga ng layunin ng function

Upang mahanap ang mga coordinate ng point C, kinakailangan upang malutas ang isang sistema na binubuo ng kaukulang mga direktang equation (sa kasong ito, equation 2 at 3):

16x 1 − 2x 2 ≤ 18

8x 1 + 4x 2 ≤ 20

Nakukuha namin ang pinakamainam na solusyon = 1.33.

^ Pinakamainam na halaga ng layunin ng function f * = f (X*) = 7 * 0 + 6 * 1,33 = 7,8