Tabular na view ng PPP. Simplex - mga talahanayan.

SIMPLEX NA PARAAN PARA SA PAGSOLUSYON NG ZLP

3.1. Pangkalahatang katangian at ang mga pangunahing yugto ng paraan ng simplex

Ang mga tagapagtatag ng simplex na pamamaraan ay ang Sobyet na matematiko na si L.V. Kantorovich at Amerikanong matematiko na si J. Dantzig.

Gamit ang simplex na paraan, maaari mong lutasin ang anumang problema o matuklasan ang hindi malulutas nito. Maraming mga espesyal na klase ng mga problema ang maaaring malutas sa pamamagitan ng iba pang mga pamamaraan na mas epektibo para sa mga klase na ito. Gayunpaman, ang bentahe ng simplex na pamamaraan ay ang kakayahang magamit nito. Halos lahat ng mga computer ay binuo karaniwang mga programa upang malutas ZLP simplex- paraan.

Ilarawan natin pangkalahatang ideya simplex na pamamaraan.

Naniniwala kami na ang ZLP ay nakasulat sa canonical form at ang layunin ng function ay kailangang mabawasan. Tulad ng alam na natin, ang pinakamainam na plano ay dapat hanapin sa mga pangunahing plano ng ZLP. Ang simplex na paraan ay hindi dumaan sa lahat ng mga reference na plano (na kadalasang imposible dahil sa kanilang malaking bilang), ngunit, simula sa ilang paunang reference plan, ito ay sunud-sunod na lumilipat sa iba pang mga reference na plano na bumababa. layunin function. Ang simplex na paraan ay hihinto sa paggana kapag ang alinman sa pinakamainam na reference na plano ay natagpuan o ang unsolvability ng problema ay naitatag.

Kapag nagpapasya ZLP gamit ang simplex method Ang mga sumusunod na yugto ay maaaring makilala:

1) dinadala ang PAP sa kanonikal na anyo;

2) pagdadala ng isang sistema ng mga linear na equation sa anyo ng Jordan na may mga hindi negatibong kanang bahagi habang sabay na sinusuri ang hindi malulutas ng ZLP dahil sa hindi pagkakapare-pareho ng system linear na mga hadlang;

3) pag-aaral ng reference plan para sa pinakamainam;

4) pag-aaral ng ZLP para sa undecidability dahil sa unboundedness mula sa ibaba sa ODD ng layunin function;

5) paglipat sa isang bago, "mas mahusay" na reference na plano.

Upang bawasan at ayusin ang mga talaan kapag nilulutas ang ZLP gamit ang simplex na paraan, ginagamit ang tinatawag na simplex na mga talahanayan. Upang gumamit ng simplex na talahanayan, ang ZLP ay dapat i-convert sa tabular form. Ito ay ginawa tulad nito.

Hayaang maisulat ang ZLP sa canonical form (2.3-2.5). Upang gawing tabular na anyo ang ZLP, ang system (2.4) ay dapat munang bawasan sa anyo ng Jordan na may mga di-negatibong kanang bahagi. Ipagpalagay natin na ang anyo ng Jordan na ito ay may anyo (2.6). Ipahayag natin mula sa (2.6) ang mga pangunahing variable sa mga tuntunin ng mga libre:

Sa pamamagitan ng pagpapalit sa layunin ng function (2.3) sa halip ng mga pangunahing variable ng kanilang mga expression sa pamamagitan ng mga libreng variable ayon sa mga formula (3.1), sa gayon ay hindi namin isasama ang mga pangunahing variable mula sa layunin function. Ang layunin ng function ay kukuha ng form:

SA tabular na anyo ang layunin ng function ay nakasulat tulad ng sumusunod:

saan .

Tandaan sumusunod na mga tampok tabular na anyo ng PPP:

a) ang sistema ng mga linear na equation ay binawasan sa anyo ng Jordan na may mga di-negatibong kanang bahagi;

b) ang mga batayan na variable ay hindi kasama sa layunin ng function at ito ay nakasulat sa form (3.3).

Lumipat tayo ngayon sa paglalarawan ng simplex table. Hayaang maisulat ang ZLP sa anyong tabular:

(3.4)

Pagkatapos ang nakumpletong simplex na talahanayan ay ganito ang hitsura.

Simplex na pamamaraan para sa paglutas ng mga problema linear programming

Ang simplex na paraan ay pamamaraang analitikal Mga solusyon sa ZLP na nagpapatupad ng algorithm graphic na pamamaraan analytically, nang hindi gumuhit ng drawing.

Kaya ang punto ay simplex na pamamaraan binubuo ng isang nakadirekta na paghahanap ng mga magagawang solusyon, kung saan ang halaga ng layunin na pag-andar sa bawat hakbang ay mas mahusay kaysa sa nauna. Ang proseso ay paulit-ulit hanggang sa isang solusyon na pinakamainam sa mga tuntunin ng halaga ng layunin ng function ay nakuha.

Ang simplex na paraan ay maaaring gamitin upang malutas ang mga PLP sa anumang bilang ng mga hindi alam.

Ang teknikal na pagpapatupad ng simplex na pamamaraan ay nauugnay sa paglutas ng mga sistema ng mga linear na equation, kung saan ang Gauss method ay ginagamit, ang mga tabular form at mga panuntunan para sa pag-convert ng mga simplex na talahanayan ay binuo.

Simplex na pamamaraan na may natural na batayan nalalapat kung ang PIL ay tinukoy sa kanonikal na anyo records, at ang matrix sa KZLP ay naglalaman ng unit submatrix ng laki m'm. Para sa katiyakan, ipagpalagay natin na ang una m Ang mga vector matrice ng sistema ng mga equation ay bumubuo sa identity matrix. Pagkatapos ang paunang plano ay pinili tulad ng sumusunod:

Ang optimality ng reference plan ay sinusuri gamit ang optimality sign; ang paglipat sa ibang plano ay isinasagawa gamit ang Jordan-Gauss transformation gamit ang mathematical optimality sign. Ang nagreresultang reference plan ay muling sinusuri para sa optimality, atbp.

Ang mathematical criterion para sa optimality ay binubuo ng sumusunod na dalawang theorems:

1. Kung para sa lahat ng mga vectors A 1 , A 2 , … , A n ang kondisyon ay nasiyahan kung saan , kung gayon ang resultang reference plan ay pinakamainam. Sa kabuuan upang matukoy Z j lumahok m mga termino, iyon ay, hindi lahat ng mga coefficient ng layunin na function ay nakikilahok dito c j, ngunit may mga numero lamang na tumutugma sa mga numero ng kasalukuyang mga vector na batayan A i, ang bilang nito ay katumbas m .

2. Kung para sa ilang vector na hindi kasama sa batayan ang kondisyon ay nasiyahan , pagkatapos ay dapat kang maghanap ng bagong reference na plano kung saan ang halaga ng CF ay mas malaki kaysa sa kasalukuyang. Sa kasong ito, posible ang dalawang kaso:

a) kung ang lahat ng mga bahagi ng vector Isang k, na maipasok sa batayan, ay hindi positibo, pagkatapos ay ang LLP ay walang solusyon (walang pangwakas na pinakamabuting kalagayan);

b) kung ang vector ay may hindi bababa sa isang positibong bahagi Isang k, upang maipasok sa batayan, pagkatapos ay maaaring makuha ang isang bagong reference na plano.

Batay sa pinakamainam na pamantayan, ang isang vector ay ipinakilala sa batayan Isang k, na nagbigay ng pinakamababang negatibong halaga ng pagkakaiba ng simplex:

Upang masiyahan ang kondisyon ng di-negatibiti ng mga halaga ng plano ng sanggunian, ang vector ay nagmula sa batayan Isang r, na nagbibigay ng pinakamababang ratio ng positibong pagsusuri

Linya Isang r, kung saan matatagpuan ang lumang batayan ng vector, ay tinatawag na gabay, haligi Isang k at elemento isang rk- mga gabay.

Ang mga elemento ng linya ng gabay sa bagong simplex na talahanayan ay kinakalkula gamit ang mga formula:

at anumang iba pang elemento i ika-linya - ayon sa mga formula:

Ang mga halaga ng bagong reference plan ay kinakalkula gamit ang mga katulad na formula:

,

Ang proseso ay magpapatuloy hanggang sa makuha ang pinakamainam na plano o hanggang ang TF ay walang limitasyon. Kung kabilang sa mga pagkakaiba Δ j , j=1, 2, … , n ng pinakamainam na plano, ang mga pagkakaiba lamang na naaayon sa mga batayang vector ay zero, ito ay nagpapahiwatig ng pagiging natatangi ng pinakamainam na plano. Kung ang zero na pagtatantya ay tumutugma sa isang vector na hindi kasama sa batayan, kung gayon sa pangkalahatang kaso nangangahulugan ito na ang pinakamainam na plano ay hindi natatangi.

Halimbawa. Lutasin ang ZLP gamit ang modelo:

hanapin ,

sa ilalim ng mga paghihigpit

Ang ZLP na ito ay binawasan sa canonical form sa pamamagitan ng pagpapakilala ng mga karagdagang variable x 3 At x 4:

Ang KZLP ay may kinakailangang bilang (dalawa) ng mga zero column sa x 3 At x 4, ibig sabihin, mayroon itong malinaw na inisyal sangguniang plano (0,0,300,150).

Ang solusyon ay isinasagawa gamit ang simplex na pamamaraan na may natural na batayan na may mga kalkulasyon na na-format sa simplex na mga talahanayan:

Simplex na numero ng talahanayan	Batayan	kasama si j	kasama si j					Q
B	A 1	A 2	A 3	A 4
	←A 3
A 4
Δ	-		-2	-3			-
ako	→A 2			1/3		1/3
←A 4			2/3		-1/3
Δ	-		-1				-
II	A 2					1/2	-1/2	-
→A 1					-1/2	3/2	-
Δ	-				1/2	3/2	-

Isaalang-alang natin nang mas detalyado ang pagpuno sa mga talahanayan ng simplex at, nang naaayon, pagkuha ng solusyon sa KZLP.

SA nangungunang linya mga coefficient na kasama sa pangkalahatang talahanayan c j , j=1, 2, 3, 4 na may mga variable sa digital function. Ang unang dalawang row ng zero simplex table ay naglalaman ng mga column vectors B, A 1, A 2, A 3, A 4, naaayon sa vector form ng KZLP record. Dahil ang paunang batayan ay isang pares ng mga vector A 3 , A 4, kasama ang mga ito sa column na tinatawag na "Base" ng zero simplex table. Kasabay nito, A 3 ay kasama sa unang hilera, na tinutukoy ng unit bilang unang elemento ng vector na ito, at ang vector A 4- sa pangalawang linya, para sa vector na ito ang unit ay nasa pangalawang linya. Sa column na tinatawag na “ c i” ang mga coefficient ng layunin ng function na naaayon sa mga batayang vector ay ipinakilala A 3 , A 4, iyon ay c 3, c 4. Pareho silang katumbas ng zero. Susunod, ang mga halaga ng mga pagkakaiba Δ para sa mga vector ay kinakalkula B, A 1, A 2, A 3, A 4 at ipinasok sa ikatlong hilera ng zero table. Para sa vector A 1:

para sa vector:

Gayundin, .

Para sa vector B ang pagkalkula ng pagkakaiba ay medyo pinasimple dahil walang kaukulang coefficient c j , j=1, 2, 3, 4 sa CF:

Hindi para sa lahat ng mga vector A 1 , A 2 , A 3 , A 4 ang mga resultang pagkakaiba ay hindi negatibo, kaya ang reference plan na aming pinili ay hindi optimal. Kailangan nating maghanap ng bagong reference plan, at para dito kailangan nating palitan ang isa sa mga vector na kasama sa batayan A 3 , A 4.

Upang matukoy ang vector na dapat nating ipasok, hinahanap natin ang vector kung saan ang halaga ng pagkakaiba ay minimal. Ito ang vector A 2, tumutugma dito pinakamababang halaga pagkakaiba: -3. Iyon ay, ang index k mula sa formula (8.4) ay katumbas ng 2. Upang matukoy ang vector na kakailanganin nating makuha mula sa batayan, kinakalkula natin ang mga halaga Q para sa bawat linya ayon sa formula (8.5) at ilagay ang mga ito sa huling column. SA sa kasong ito sa bawat linya kailangan namin ang halaga ng elemento ng vector B hatiin sa magnitude ng elemento ng vector A 2. Sa unang linya makakakuha tayo ng 300/3=100, sa pangalawa: 150/1=150. Ang ratio sa unang hilera ay mas maliit; A 3, samakatuwid, ang index r sa formula (8.5) ay katumbas ng 1, isang rk=3 (naka-highlight sa talahanayan na may isang frame), at kukunin namin ang vector mula sa batayan A 3(ipinahiwatig ng isang arrow sa talahanayan).

Dahil kabilang sa mga elemento ng vector A 2, na dapat ipasok sa batayan, mayroong mga positibo, pagkatapos ay isang bagong reference plan ay maaaring makuha at ang solusyon ay dapat ipagpatuloy.

Pagkatapos nito, ang pangalawang simplex na talahanayan ay napunan. Upang muling kalkulahin ang mga elemento ng vector B, A 1, A 2, A 3, A 4 ginagamit ang mga formula (8.6)-(8.8). Ang mga ito ay bahagyang naiiba para sa pagtukoy ng mga elemento ng linya ng gabay (sa aming kaso, ang una) at para sa pagtukoy ng mga elemento ng iba pang mga linya. Isulat natin ang mga kalkulasyon ng ilang elemento:

Ang iba pang mga elemento ng unang simplex table ay kinakalkula sa parehong paraan tulad ng ginawa namin para sa zero table. Dahil hindi lahat ng mga pagkakaiba sa unang simplex table ay hindi negatibo, ito ay nagiging kinakailangan upang ipagpatuloy ang mga kalkulasyon.

Tulad ng nakikita natin, bilang isang resulta ng mga kalkulasyon sa pangalawang simplex na talahanayan na may mga batayan ng vector A 2 , A 1 ang lahat ng mga pagkakaiba ay naging hindi negatibo, na nangangahulugang pagkamit ng pinakamainam na plano (75; 75; 0; 0). Simplex pagkakaiba para sa isang vector SA katumbas ng ninanais pinakamataas na halaga CF - 375.

Theorem (tungkol sa finiteness ng simplex algorithm).Kung mayroong isang pinakamainam desisyon ng PPP, pagkatapos ay mayroong isang pangunahing pinakamainam na solusyon. Ang huli ay palaging makukuha gamit ang simplex na paraan, at maaari kang magsimula sa anumang paunang batayan.

Ang isa sa mga pinaka-karaniwan at tanyag na problema sa pag-optimize sa logistik ay problema sa transportasyon . SA klasikong hitsura ito ay nagsasangkot ng paghahanap ng pinakamainam ( mga. nauugnay sa kaunting gastos ) plano sa transportasyon ng kargamento.

Halimbawa, mayroon kaming isang hanay ng mga retail na tindahan na nangangailangan ng isang tiyak na halaga ng mga kalakal. Mayroon ding isang bilang ng mga bodega ng tagapagtustos kung saan nakaimbak ang mga kinakailangang kalakal. Bukod dito, ang bawat bodega ay may iba't ibang halaga ng stock ng mga kalakal na ito. Bilang karagdagan, alam namin ang mga taripa - ang mga gastos sa pagdadala ng 1 produkto mula sa bawat bodega patungo sa bawat tindahan.

May pangangailangang bumuo ng plano sa transportasyon upang matanggap ng mga tindahan ang kinakailangang halaga ng mga kalakal na may pinakamababang gastos sa transportasyon. Ito ay tiyak sa mga ganitong kaso (at sa marami pang iba) na ang problema sa transportasyon ay kailangang lutasin.

Teoretikal na materyal sa problema sa transportasyon

(Problema ng Monge-Kantorovich) - problema sa matematika linear programming espesyal na uri tungkol sa paghahanap pinakamainam na pamamahagi mga homogenous na bagay mula sa baterya hanggang sa mga receiver habang pinapaliit ang mga gastos sa paglalakbay.

Para sa kadalian ng pag-unawa, ito ay itinuturing na isang problema sa pinakamainam na plano para sa transportasyon ng mga kalakal mula sa mga punto ng pag-alis ( halimbawa, mga bodega) sa mga punto ng pagkonsumo ( halimbawa, mga tindahan), na may kaunting kabuuang gastos sa transportasyon.

May sumusunod na anyo:

saan: Z- mga gastos sa transportasyon ng mga kalakal;
X- dami ng kargamento;
C- gastos (taripa) ng transportasyon ng isang yunit ng kargamento;
A- stock ng supplier;
B- kahilingan ng mamimili;
m- bilang ng mga supplier;
n- bilang ng mga mamimili.

Pangkalahatang plano para sa paglutas ng problema sa transportasyon gamit ang potensyal na paraan

Ang problema sa transportasyon ay maaaring malutas iba't ibang pamamaraan, simula sa simplex method at simpleng enumeration, at nagtatapos sa . Ang isa sa mga pinaka ginagamit at angkop na pamamaraan para sa karamihan ng mga kaso ay umuulit na pagpapabuti ng plano sa transportasyon.

Ang kakanyahan nito ay ang mga sumusunod: nakahanap kami ng isang tiyak na reference na plano at sinusuri ito pinakamainam (Z → min). Kung ang plano ay pinakamainam, ang isang solusyon ay natagpuan. Kung hindi, pinapabuti nito ang plano nang maraming beses hangga't kinakailangan hanggang sa matagpuan ang pinakamainam na plano.

Nasa ibaba ang algorithm para sa paglutas ng isang problema sa transportasyon sa pinaka-pangkalahatang anyo:

1. Pagbuo ng isang transport table.
2. Sinusuri ang problema para sa pagsasara.
3. Pagguhit ng isang pangunahing plano.
4. Sinusuri ang plano ng suporta para sa pagkabulok.
5. Pagkalkula ng mga potensyal para sa plano ng transportasyon.
6. Sinusuri ang reference na plano para sa pinakamainam.
7. Muling pamamahagi ng mga supply.
8. Kung ang pinakamainam na solusyon ay natagpuan, pumunta sa hakbang 9, kung hindi, pumunta sa hakbang 5.
9. Pagkalkula ng kabuuang gastos ng transportasyon ng mga kalakal.
10. Pagbuo ng isang graph ng transportasyon.

Mga detalyadong tagubilin para sa paglutas ng problema sa transportasyon

1. Pagbuo ng transport table

Bumubuo kami ng isang talahanayan kung saan ipinapahiwatig namin ang mga stock ng mga materyales na magagamit sa mga bodega ng mga supplier ( Ai), at ang mga pangangailangan ng mga pabrika ( Bj) sa mga materyales na ito.

Sa kanang ibabang sulok ng mga cell ng talahanayan ipinapasok namin ang halaga ng mga taripa para sa transportasyon ng kargamento ( Cij).

2. Sinusuri ang problema para sa pagsasara

Tukuyin natin ang kabuuang stock ng kargamento mula sa lahat ng mga supplier na may simbolo A, at ang kabuuang demand para sa kargamento para sa lahat ng mga mamimili ay sinasagisag B.

Ang problema sa transportasyon ay tinatawag sarado, Kung A=B. Kung A ≠ B, pagkatapos ay tinawag ang problema sa transportasyon bukas. Kung sakali saradong problema Ang lahat ng mga supply ng kargamento ay aalisin mula sa mga supplier, at lahat ng mga kahilingan ng consumer ay matutugunan. Kung sakali bukas na gawain Upang malutas ito, kailangan mong ipakilala ang mga fictitious na supplier o consumer.

Suriin natin ang gawain para sa pagsasara:

A = 10 + 20 + 30 = 60

B = 15 + 20 + 25 = 60

A = B, samakatuwid ang problema sa transportasyon ay sarado.

3. Pag-drawing ng isang reference plan

Binubuo ang paunang ( pagsuporta) plano sa transportasyon. Hindi ito kailangang maging pinakamainam. Ito ay isang uri lamang ng "draft", "sketch", pagpapabuti na unti-unti nating makakarating sa pinakamainam na plano.

Mayroong iba't ibang mga pamamaraan para sa paghahanap ng isang sanggunian na plano. Ang pinakakaraniwan ay ang mga sumusunod:

a) Paraan ng North-West Angle. Ipakita

Ang kakanyahan ng pamamaraan ay simple - ang mga cell ng talahanayan ng transportasyon ay sunud-sunod na puno ng pinakamataas na posibleng dami ng trapiko sa direksyon itaas pababa At mula kaliwa hanggang kanan. Iyon ay, ang tuktok na kaliwang cell ay napunan muna ( "northwest" cell), pagkatapos ay ang susunod sa kanan, atbp. Pagkatapos ay pumunta sa bagong linya at punan muli ito mula kaliwa hanggang kanan. At iba pa hanggang sa ganap na mapuno ang mesa.

Ang isang detalyadong paglalarawan ng pamamaraan at isang halimbawa ay matatagpuan.

b) Minimum na paraan ng elemento. Ipakita

Ang pamamaraan ay upang punan ang mga cell ng talahanayan ng transportasyon, pumili ng isang cell na may minimal halaga ng taripa. Pagkatapos ay pipiliin ang susunod na cell na may pinakamababang taripa at iba pa hanggang sa mapuno ang talahanayan ( lahat ng mga stock at pangangailangan ay ire-reset sa zero).

c) Vogel approximation. Ipakita

Ang batayan ng pamamaraan ay paghahanap pagkakaiba(modulo) sa pagitan ng isang pares pinakamababang taripa sa bawat hilera at hanay. Pagkatapos ay sa row o column na may pinakadakila ang pagkakaiba ay pumupuno sa cell ng ang pinakamaliit taripa. Pagkatapos ang lahat ng mga pagkilos na ito ay paulit-ulit na muli, tanging sa kasong ito ang mga napuno na mga cell ay hindi na isinasaalang-alang.
Ang isang detalyadong paglalarawan ng Vogel approximation at isang halimbawa ay matatagpuan

d) Paraan ng dobleng kagustuhan. Ipakita

Ang kakanyahan ng pamamaraan ay ang mga cell na may pinakamababang taripa ay minarkahan sa mga hilera at pagkatapos ay sa mga haligi. Pagkatapos ang mga cell ay napunan sa sumusunod na pagkakasunud-sunod: una ang mga cell na may dalawang marka, pagkatapos ay may isa, sa wakas ay walang marka.
Ang isang detalyadong paglalarawan ng pamamaraan at isang halimbawa ay matatagpuan

4. Sinusuri ang plano ng suporta para sa pagkabulok

Ang mga cell ng talahanayan kung saan ang mga transportasyon maliban sa zero ay naitala ay tinatawag basic, at ang natitira (walang laman) - libre.

Tinatawag ang plano mabulok, kung ang bilang ng mga pangunahing selula sa loob nito ay mas mababa sa m + n -1. Kung sa panahon ng solusyon ng problema ay nakuha ang isang degenerate na plano, pagkatapos ay dapat itong mapunan sa pamamagitan ng pagpasok ng zero na transportasyon sa nawawalang bilang ng mga cell at sa gayon ay gawing pangunahing mga cell ang mga ito ( ang kabuuang balanse at kabuuang halaga ng transportasyon ng plano ay hindi magbabago). Gayunpaman, imposibleng lagyang muli ang plano sa pamamagitan ng pagpili ng mga cell nang random. Dapat acyclic ang plano!

Ang isang plano ay tinatawag na acyclic kung ang mga base cell nito ay walang mga cycle. Ikot sa talahanayan ng transportasyon mayroong ilang mga cell na konektado sa pamamagitan ng isang saradong polyline upang ang dalawang katabing vertices ng polyline ay matatagpuan alinman sa parehong hilera o sa parehong haligi. Nasa ibaba ang halimbawa ng loop:

Ang isang putol na linya ay maaaring magkaroon ng mga self-intersection point, ngunit hindi sa mga cell ng cycle.

Bilang ng mga pangunahing cell = 5

m + n – 1 = 3 + 3 – 1 = 5

Dahil dito, ang orihinal na plano sa transportasyon ay hindi nasira.

5. Pagkalkula ng mga potensyal para sa plano ng transportasyon

Upang pag-aralan ang mga nagresultang plano at ang kanilang kasunod na pagpapabuti, ito ay maginhawang pumasok karagdagang mga katangian mga punto ng pinagmulan at destinasyon, na tinatawag na potensyal.

Ang pamamaraang ito ng pagpapabuti ng mga plano sa transportasyon ay tinatawag potensyal na pamamaraan . Mayroong iba pang mga pamamaraan para sa paulit-ulit na pagpapabuti ng plano sa transportasyon, ngunit hindi namin isasaalang-alang ang mga ito dito.

Kaya, ihambing natin ang bawat supplier na si Ai at ang bawat consumer na si Bj sa mga halaga Ui At Vj nang naaayon, upang para sa lahat ng pangunahing mga cell ng plano ang sumusunod na kaugnayan ay nasiyahan:

Ui + Vj = Cij

Idagdag sa transport table dagdag na linya at isang column para sa Ui at Vj.

Ipagpalagay natin na U1 = 0.

Pagkatapos ay mahahanap natin ang V3 = C13 – U1 = 1 – 0 = 1.

Alam ang V3, mahahanap na natin ngayon ang U3:

Sa pamamagitan ng pagkakatulad, kinakalkula namin ang lahat ng natitirang potensyal:

6. Sinusuri ang plano para sa pinakamainam gamit ang potensyal na pamamaraan

Para sa bawat libreng cell ng plano, kinakalkula namin ang mga pagkakaiba

ΔCij = Cij – (Ui + Vj)

at isulat ang mga nagresultang halaga sa ibabang kaliwang sulok ng kaukulang mga cell.

Ang plano ay pinakamainam, kung ang lahat ng pagkakaiba ΔCij ≥ 0.

Sa kasong ito, ang plano ay suboptimal(ΔC22< 0), и его следует улучшить путем перераспределения поставок.

7. Muling pamamahagi ng mga supply

Hanapin natin ang cell na may pinakamalaking ganap na halaga negatibong pagkakaiba ΔCij at bumuo ng isang cycle kung saan, maliban sa cell na ito, lahat ng iba ay basic. Ang ganyang cycle palaging umiiral at natatangi.

Markahan natin ang cell ng negatibong pagkakaiba ΔCij na may “+” sign, ang susunod ay may “-” sign, at iba pa, isa-isa.

Pagkatapos ay nakita namin ang pinakamababang halaga ng pag-load sa mga cell ng cycle na may "-" sign (narito ito ay 5) at ipasok ito sa libreng cell na may "+" sign. Pagkatapos ay sunud-sunod kaming dumaan sa lahat ng mga cell ng cycle, halili na pagbabawas at pagdaragdag ng pinakamababang halaga sa kanila (alinsunod sa mga palatandaan kung saan minarkahan ang mga cell na ito: kung saan ang minus ay binabawasan, kung saan ang plus ay idinagdag).

Nakukuha namin bagong reference plan transportasyon:

Dahil mayroong mas maraming pangunahing mga cell kaysa sa m + n - 1, pagkatapos ay isang pangunahing cell na may zero na halaga gawin itong libre:

Muli naming kinakalkula ang mga potensyal na halaga at ang pagkakaiba ΔCij:

Sa pagkakataong ito ang lahat ng mga pagkakaiba ΔCij ng mga selula ay positibo, samakatuwid, natagpuan ang pinakamainam na solusyon.

8. Kung ang pinakamainam na solusyon ay natagpuan, pumunta sa hakbang 9, kung hindi, pumunta sa hakbang 5.

Natagpuan namin ang pinakamainam na solusyon, kaya magpatuloy sa punto 9.

9. Pagkalkula ng kabuuang gastos sa pagdadala ng mga kalakal

Magkalkula tayo kabuuang gastos sa pagpapadala kargamento ( Z), na tumutugma sa pinakamainam na plano na aming nakita, ayon sa formula:

Zmin = 10 ∙ 1 + 15 ∙ 3 + 5 ∙ 2 + 15 ∙ 1 + 15 ∙ 2 = 110 den. mga yunit

Kabuuang mga gastos sa pagpapadala para sa lahat ng mga produkto, para sa pinakamainam na solusyon, make up 110 den. mga yunit

10. Paggawa ng isang graph ng transportasyon

Ang pagkakaroon ng natagpuan ang pinakamainam na plano sa transportasyon, kami ay gagawa. Ang mga vertex ng graph ay magiging "mga bodega" at "mga tindahan". Sa vertices ipinapahiwatig namin ang kaukulang dami ng mga reserba at pangangailangan. Ang mga arko na nagkokonekta sa mga vertice ng graph ay tumutugma sa mga hindi zero na transportasyon. Pipirmahan namin ang bawat naturang arko, na nagpapahiwatig ng dami ng kargamento na dinadala.

Ang resulta ay magiging isang graph na katulad ng ipinapakita sa ibaba:

Iyon lang, nalutas ang problema sa transportasyon. Binabati kita!

Praktikal na aplikasyon ng problema sa transportasyon

Ang problema sa transportasyon ay ginagamit sa maraming kaso. Ito ay ang pag-optimize ng supply ng mga hilaw na materyales at mga supply sa mga negosyo sa pagmamanupaktura. Ito ang pag-optimize ng paghahatid ng mga kalakal mula sa mga bodega hanggang sa mga retail na tindahan. Ito ang pag-optimize ng transportasyon ng pasahero, at marami pa.

Galyaudinov R.R.

© Ang pagkopya ng materyal ay pinahihintulutan lamang kung ang isang direktang hyperlink sa

Tanda ng pagiging mahusay ng reference plan

Kung sa isang simplex na talahanayan na naglalaman ng isang partikular na plano ng suporta, ang lahat ng mga elemento ng f-row (maliban sa libreng termino) ay hindi negatibo, kung gayon ang plano ng suporta na ito ay pinakamainam.. Ipasok ang f-row ng talahanayan. 2.b 0j > (i=1, ..., n m). Sa reference plan x 0 na nakapaloob sa talahanayang ito, ang mga halaga ng lahat ng libreng variable x m+j ay katumbas ng zero at f(x 0) =b 00. Kung tataasan mo ang alinman sa mga libreng variable na x m+ j, kung gayon, tulad ng makikita sa pagkakapantay-pantay (2.5), dahil sa hindi negatibiti ng b 0j, magsisimulang bumaba ang halaga ng f(x). Dahil dito, sa x o ang function na f(x) ay umabot sa pinakamalaking halaga nito, na nangangahulugan na ang x 0 ay talagang ang pinakamainam na reference plan.

Kakayahang lumipat mula sa isang reference plan patungo sa isa pa

Tulad ng nabanggit sa itaas, ang kakanyahan ng simplex na pamamaraan ay nasa proseso ng pagpapatunay sa sumusunod na pamantayan: kung sa f-row ng isang simplex table na naglalaman ng ilang reference plan, mayroong hindi bababa sa isang negatibong elemento (hindi binibilang ang libreng termino), na tumutugma sa isang column na may hindi bababa sa isang positibong elemento, pagkatapos ay maaari mong, sa pamamagitan ng pagbabago ng batayan, lumipat sa isa pang reference na plano na may mas malaking halaga ng layunin na function.

Patunayan natin ang sign na ito. Itatag natin ang mga panuntunan para sa pagpili ng mga variable para sa naturang pagbabago ng inisyal na batayan B o na may reference plan x 0 sa bagong batayan B 1 na may reference plan x 1 kung saan; tumataas ang halaga ng function na f, ibig sabihin, f(x i)>f(x 0). Pagkatapos, ayon sa panuntunan para sa muling pagkalkula ng mga elemento mula sa simplex table, binabago namin ang mga ito sa isang bagong batayan, na magbibigay-daan sa amin upang mahanap ang mga bahagi ng bagong reference plan.

Ipagpalagay natin na nasa talahanayan. 2.1, halimbawa, b 0s<0, а среди элементов b is s-го столбца есть хотя бы один положительный. Полагая в равенстве (2.5) все свободные переменные х m+j кроме x m+s , равными нулю, получаем f = b oo -- b os xm+s . Из этого равенства видно, что при увеличении x m+s значение f тоже возрастает. Таким образом, при указанных в признаке условиях действительно есть возможность увеличить f(x), переходя к планам, в которых x m+s принимает положительные значения, а все остальные компоненты x m+j по-прежнему равны нулю. Покажем, что среди таких планов существует и опорный. Тем самым будет найден путь направленного преобразования базиса Б о в новый базис Б 1 . В самом деле, если переменная x m+s принимает положительное значение в некотором опорном плане, значит, она является в нем базисной компонентой (в опорном плане x о она была свободной компонентой и равнялась нулю). Поэтому прежний базис следует преобразовать за счет включения в него переменной x m+s . Но здесь предстоит решить два вопроса:

1) kung alin sa mga variable ang dapat alisin sa naunang batayan upang magkaroon ng puwang para sa variable na x m+s;

2) anong halaga ang dapat kunin ng bagong basic variable x m+s sa bagong reference plan.

Upang malutas ang mga tanong na ibinigay, ipagpalagay natin na sa mga pagkakapantay-pantay (2.4) lahat ng x m+j, maliban sa x m+s, ay katumbas ng zero. Pagkatapos

x i = b io -b ay x m+s (i=l, ..., m)

Mula sa mga pagkakapantay-pantay na ito ay malinaw na sa pagtaas ng x m+s ang mga halaga ng mga pangunahing variable na x i kung saan ang mga coefficient b ay<0, тоже будут расти, оставаясь положительными. Значит, на отрицательные коэффициенты b is можно внимания не обращать, так как они не влияют на знак базисных переменных. Иначе обстоит дело с базисными переменными, у которых b is >0. Habang tumataas ang x m+s, magsisimulang bumaba ang mga halaga ng mga variable na ito, at darating ang isang sandali kung saan kukuha sila ng mga negatibong halaga at hindi na masisiyahan ang kundisyon (2.3). Hindi ito maaaring payagan. Samakatuwid, alamin natin kung anong limitasyon ng halaga x m+s ang maaaring dagdagan nang hindi nilalabag ang kondisyon ng hindi negatibo ng mga pangunahing variable. Para sa layuning ito, isinusulat namin mula sa system (2.6) ang mga pagkakapantay-pantay kung saan ang b ay >0. Ipagpalagay natin na may kinalaman ito sa mga pagkakapantay-pantay sa mga numerong i=d,…,k,…,p:

x d =b do -- b ds x m+s ,

…………………..

x k =b k0 - b ks x m+s ,

………………….

x p =b p0 - b ps x m+s .

Ang mga pangunahing variable na x d, ..., x k, ..., x p ay mananatiling hindi negatibo hangga't ang x m+s ay nakakatugon sa sistema ng hindi pagkakapantay-pantay.

b gawin - b ds x m+s >0, x m+s

……………… ………………

b k0 - b ks x m +s >0 o x m+s< b ko /b ks

……………… ………………

b p0 - b ps x m+s >0 x m+s< b po /b ps

ibig sabihin, sa x m+s

Hayaang ang pinakamaliit sa mga fraction b io /b ay tumutugma sa i = k, i.e.

min ( b io /b is )= b k0 /b ks .

Pagkatapos ay maaari nating sabihin na hangga't ang x m+s ay hindi lalampas sa halaga b k0 /b ks , ibig sabihin, x m+s 0, pagkatapos ang variable na x k ay magiging katumbas ng bullet: x k = b k0 -- b ks b ko /b ks =0, at sa gayon ang batayan ay mababago B o = (x 1 ; ...; x k ; . . Kasabay nito, ang lahat ng iba pang mga libreng variable ay katumbas pa rin ng zero, at ang natitirang mga pangunahing variable ay positibo pa rin. Dahil dito, ang pangunahing plano x 1 sa bagong batayan B 1 = (x 1 ; ...; x m+s ; ...; x m ) ay magkakaroon ng m positibong bahagi at m-n zero ones. Sa x 1 na plano, ang ilang mga pangunahing variable ay maaaring tumagal sa mga zero na halaga sa dalawang kaso:

1) kapag sa plan x 0 mayroong mga pangunahing variable na katumbas ng zero;

2) kapag ang pinakamaliit sa mga fraction na b io /b ay ay tumutugma sa dalawa o higit pang mga numero i Sa aming kaso, ito ay tumutugma lamang sa i = k.

Ang variable na isasama sa batayan ay tinutukoy ng negatibong elemento ng f-string. Mula sa pagkakapantay-pantay f =b oo - b os x m+s malinaw na kapag b 0s<0 и фиксированном x m+s >0, ang halaga ng f(x) ay nakasalalay sa absolute value ng coefficient b 0s: mas malaki |b 0s |, mas malaki ang value na matatanggap ng f(x) sa bagong batayan. Ngunit mula sa pagkakapantay-pantay na ito ay malinaw din na ang halaga ng layunin ng pag-andar sa bagong batayan ay nakasalalay din sa halaga na kinuha ng bagong variable na batayan x m+s. Pipili kami ng isang variable na ipinakilala sa batayan, na nakatuon lamang sa mga negatibong elemento ng f-row. Samakatuwid, kapag mayroong ilang negatibong elemento sa f-row, ipakikilala natin sa batayan ang variable na x m+j na naaayon sa negatibong elemento na may pinakamalaking ganap na halaga. Ang hanay ng mga coefficient para sa isang variable na kasama sa batayan ay tinatawag na paglutas. Kaya, sa pamamagitan ng pagpili ng variable na ipinakilala sa batayan (o pagpili ng isang column sa pagresolba) batay sa negatibong elemento ng f-row, tinitiyak namin na tumataas ang function na f.

Medyo mas mahirap matukoy ang variable na ibubukod sa batayan. Upang gawin ito, binubuo nila ang mga ratio ng mga libreng termino sa mga positibong elemento ng haligi ng paglutas (ang mga ganitong relasyon ay tinatawag na simplex) at hanapin ang pinakamaliit sa kanila, na tumutukoy sa hilera (paglutas) na naglalaman ng hindi kasamang variable. Ang pagpili ng isang variable na ibinukod mula sa batayan (o ang pagpili ng isang linya ng paglutas) ayon sa pinakamababang simplex na ugnayan ay ginagarantiyahan ang pagiging positibo ng mga batayan na bahagi sa bagong reference na plano.

Kaya, napatunayan namin na sa ilalim ng mga kundisyong tinukoy sa sign ay posible talagang lumipat mula sa isang reference plan patungo sa isa pa na may malaking halaga ng layunin na function f(x).

Tandaan na alam na natin ang halaga ng bagong basis variable x m+s sa bagong reference plan: ito ay katumbas ng b ko /b ks . Tulad ng para sa mga numerical na halaga ng natitirang pangunahing mga variable sa bagong reference plan at ang katumbas na halaga ng f(x), sila ay matatagpuan lamang pagkatapos ng binagong sistema ng mga pangunahing variable x 1 ;..., x m+s ; ...,x m ay ipahahayag sa pamamagitan ng isang binagong sistema ng mga libreng variable x m+1,…,x k,…, x n. Upang gawin ito, itakda natin; mga tuntunin kung saan ang mga kondisyon ng isang problema ay binago mula sa isang batayan patungo sa isa pa.

Ang coefficient b ks = 0 sa x m+s sa equation na ito ay tinatawag na resolving element. Sa pagkakapantay-pantay (2.7), ang bagong pangunahing variable x m+s ay ipinahayag sa mga tuntunin ng mga libreng variable, kung saan matatagpuan ang dating pangunahing variable x k. Kaya, ang mga variable na x m+s at x k ay nagpalit ng mga tungkulin.

Ipahayag natin ang mga natitirang pangunahing variable sa pamamagitan ng isang bagong hanay ng mga libreng variable. Para sa layuning ito, pinapalitan namin ang halaga x m+s mula sa natitirang mga pagkakapantay-pantay (tinutukoy namin ang f sa x 0, pagkatapos ay isasama ang pagkakapantay-pantay sa sistema sa i = 0)

Ang pagdadala ng isang sistema sa isang bagong batayan ay tinatawag na simplex transformation. Kung ang simplex na pagbabago ay itinuturing bilang isang pormal na algebraic na operasyon, kung gayon mapapansin ng isa na bilang resulta ng operasyong ito, ang mga tungkulin ay muling ipinamamahagi sa pagitan ng dalawang variable na kasama sa isang tiyak na sistema ng mga linear na function: ang isang variable ay napupunta mula sa umaasa hanggang sa independyente, at ang isa pa. , sa kabaligtaran, mula sa independyente hanggang umaasa . Ang operasyong ito ay kilala sa algebra bilang ang Jordan elimination step.

123 mga pahina (Word file)

Tingnan ang lahat ng pahina

Fragment ng teksto ng akda

Ang paglipat mula sa isang reference na plano patungo sa isa pa, ang halaga ng layunin na pag-andar kung saan ay mas malaki kaysa sa nauna.

3. Sinusuri ang pinakamainam ng resultang plano, na nagbibigay-daan sa iyong ihinto kaagad ang paghahanap para sa mga reference na plano o gumawa ng konklusyon na walang pinakamainam na plano.

Ang simplex na paraan ay batay sa mga sumusunod na theorems, na ibinigay nang walang patunay.

Theorem 1.2 (sa pagkakaroon ng isang plano ng suporta)

Kung ang isang linear na anyo ay nakatali mula sa itaas sa isang di-walang laman na set D, kung gayon ang LLP ay malulutas, iyon ay, mayroong isang punto na .

Theorem 1.3 (pagsubok para sa pinakamainam ng plano ng suporta)

Batayang plano ang problema (1.18) ay pinakamainam kung para sa lahat j , ay nasiyahan, kung saan ang dami

(1.21)

tinawag simplex - pagkakaiba o pagtatasa.

Theorem 1.4 (pagsubok para sa kawalan ng pinakamainam na plano)

Kung para sa ilang k at kabilang sa mga numero , walang mga positibo, i.e. lahat, ang layunin ng pag-andar ng problema ay hindi limitado sa hanay ng mga magagawang solusyon at walang pangwakas na solusyon.

Theorem 1.5 (pagsubok para sa pagkakaroon ng isang mas mahusay na plano ng suporta)

Kung ang sangguniang plano ang problema (1.18) ay hindi bumababa para sa ilang k, ngunit kabilang sa mga numero , mayroong hindi bababa sa isang positibo, i.e. hindi lahat, tapos may reference plan , kung saan ang layunin ng function ay kumukuha ng halaga na hindi bababa sa naunang plano: .

Simplex method algorithm

1. Ang problema ay dapat na bawasan sa canonical form. Ang sistema ng mga paghihigpit ay binabawasan sa isang yunit na batayan, i.e. ay nalutas na may paggalang sa ilang mga pangunahing baryabol (nang walang pagkawala ng pangkalahatan, ipapalagay natin na may kinalaman sa mga unang m variable) gamit ang pamamaraang Jordan-Gauss (system (1.19)). Ang kaukulang paunang reference na solusyon ay nakuha.

2. Para sa kadalian ng mga kalkulasyon, isinusulat namin ang lahat sa isang simplex na talahanayan (Talahanayan 1.1). Ang hanay ng Batayan ay naglalaman ng isang listahan ng mga variable na batayan; ang susunod na hanay na "c j na batayan" ay naglalaman ng mga coefficient ng layunin ng function para sa mga variable na batayan; ang mga sumusunod na hanay ay naglalaman ng mga coefficient ng sistema ng mga paghihigpit para sa kaukulang mga variable; Ang column na “b i” ay isang column ng mga libreng miyembro ng system of restrictions. Ang huling linya ay naglalaman ng simplex - mga pagkakaiba na kinakalkula gamit ang formula (1.21) at ang huling cell ay naglalaman ng halaga ng layunin na function =. Tandaan na ang simplex - ang mga pagkakaiba ng mga pangunahing variable - ay palaging katumbas ng zero.

Talahanayan 1.1

		c j batayan

3. Kung ang lahat ay simplex, ang mga pagkakaiba ay hindi negatibo, i.e. , kung gayon ang reference na plano ay pinakamainam.

4. Kung hindi bababa sa isang simplex - pagkakaiba ay negatibo, , at walang mga positibong elemento sa kaukulang hanay, kung gayon ang problema ay walang pinakamainam na solusyon, i.e. .

5. Kung kahit isang simplex - pagkakaiba ay negatibo, , at sa bawat column na may negatibong marka ay mayroong kahit isang positibong elemento, kung gayon ang resultang reference plan ay maaaring mapabuti.

6. Pumili paganahin ang hanay"p", na tumutugma sa pinakamaliit na negatibong marka.

7. Pumili string ng pahintulot"k", na tumutugma sa pinakamaliit sa mga ratio ng kanang panig sa kaukulang positibong elemento ng column ng resolusyon. Tinatawag ang elemento sa intersection ng column ng resolution at row ng resolution permissive element.

8. Lumipat kami sa isang bagong talahanayan ng simplex, kung saan magkakaroon ng bagong batayan: ang pangunahing variable sa lugar na "k" sa lumang batayan ay binago sa isang bagong variable. Ang kaukulang vector ng bagong variable na batayan ay dapat gawing unit one. Upang gawin ito, hatiin ang linya ng resolution upang lumitaw ang isang yunit sa lugar ng elemento ng resolution. Sa pamamagitan ng pagpaparami ng linya ng resolution sa mga angkop na numero at pagdaragdag nito sa natitirang mga linya, nakakakuha tayo ng mga zero sa column ng resolution. Pagkatapos nito, nagsusulat kami ng bagong reference na plano at muling kinakalkula ang linya ng mga pagtatantya. Pumunta tayo sa point 3.

Isang tala tungkol sa alternatibong plano.

Kung ang lahat ng mga pagtatantya ng mga libreng variable sa huling simplex na talahanayan ay lumabas na mahigpit na mas malaki kaysa sa zero, kung gayon ang pinakamainam na plano ay natatangi. Kung ang hindi bababa sa isang pagtatantya para sa isang libreng variable ay katumbas ng zero, kung gayon mayroong isang alternatibong pinakamabuting kalagayan (isang hanay ng mga pinakamainam na plano). Upang makahanap ng alternatibong solusyon, kinakailangan na gumawa ng isang hakbang ng simplex na paraan, pagpili bilang paglutas ng haligi ng libreng variable, na tumutugma sa isang zero na marka.

Sa kasong ito, ang hanay ng lahat ng pinakamainam na plano ay maaaring katawanin bilang isang convex linear na kumbinasyon ng pagsuporta sa pinakamainam na mga plano: , Saan .

Halimbawa 5. Lutasin ang ZLP gamit ang simplex na paraan:

(1.22)

Binabawasan namin ang sistema ng mga linear inequalities (1.22) sa canonical form sa pamamagitan ng paglalagay ng karagdagang hindi-negatibong variable sa bawat hindi pagkakapantay-pantay. Kumuha kami ng isang sistema ng mga linear na equation:

(1.23)

Ang layunin ng function ay magkakaroon ng form

Lumilikha kami ng isang simplex na talahanayan:

Talahanayan 1.2

		c j batayan

Batayang plano ay hindi optimal, dahil sa linya ng mga rating mayroong mga negatibong elemento = - 3 at = - 2. Pinipili namin ang column ng paglutas - ang una, dahil ito ay tumutugma sa minimum ng mga negatibong pagtatantya = - 3. Para sa lahat ng positibong elemento ng unang hanay, kinakalkula namin ang ratio . Nakita namin ang pinakamababa sa mga ratio na ito: . Tumutugma ito sa pangalawang linya, samakatuwid ito ay magiging permissive. Kaya, ipinapakita ng elemento ng paglutas na ang variable x 4 ay hinango mula sa batayan, at sa halip ay magkakaroon ng variable x 1 sa batayan. Pinupuno namin ang isang bagong talahanayan ng simplex (Talahanayan 1.3). Upang gawin ito, ginagawa namin ang unang column sa isang solong column. I-multiply namin ang pangalawang linya sa pamamagitan ng (-1/2) at idagdag ito sa una, isulat ang resulta sa unang linya ng bagong simplex table; katulad nito, i-multiply ang pangalawang linya sa (1/2) at idagdag ito sa pangatlo; hatiin ang linya ng resolusyon sa 2; Sinusulat namin muli ang pang-apat nang walang mga pagbabago.