Lektura 3. Simplex na mga talahanayan. Algorithm simplex na pamamaraan.

§ 3 SIMPLEX NA PARAAN

3.1. Pangkalahatang ideya ng simplex na pamamaraan. Geometric na interpretasyon

Ang graphical na paraan ay naaangkop sa isang napakakitid na klase ng mga problema linear programming: mabisa nitong malulutas ang mga problemang naglalaman ng hindi hihigit sa dalawang variable. Ang mga pangunahing theorems ng linear programming ay isinasaalang-alang, mula sa kung saan ito ay sumusunod na kung ang isang linear programming problema ay may isang pinakamainam na solusyon, pagkatapos ito ay tumutugma sa hindi bababa sa isang sulok na punto ng solusyon polyhedron at coincides, ayon sa kahit man lang, na may isa sa mga tinatanggap na pangunahing solusyon ng sistema ng mga hadlang. Ang isang paraan upang malutas ang anumang problema sa linear programming ay ipinahiwatig: upang mabilang ang isang tiyak na bilang ng mga magagawa na pangunahing solusyon ng sistema ng mga hadlang at piliin sa mga ito ang isa kung saan ang layunin na pag-andar ay gumagawa ng pinakamainam na solusyon. Geometrically, ito ay tumutugma sa enumerating lahat ng mga sulok na punto ng solusyon polyhedron. Ang ganitong kumpletong paghahanap ay hahantong sa isang pinakamainam na solusyon (kung mayroon man), ngunit ang praktikal na pagpapatupad nito ay nauugnay sa napakalaking kahirapan, dahil para sa mga tunay na problema ang bilang ng mga magagawa na pangunahing solusyon, kahit na may hangganan, ay maaaring maging napakalaki.

Ang bilang ng mga pinahihintulutang pangunahing solusyon na hahanapin ay maaaring mabawasan kung ang paghahanap ay hindi isinasagawa nang random, ngunit isinasaalang-alang ang mga pagbabago sa linear function, i.e. pagtiyak na ang lahat susunod na solusyon ay "mas mahusay" (o hindi bababa sa "walang mas masahol pa") kaysa sa nauna, ayon sa mga halaga ng linear function (tinataas ito kapag hinahanap ang maximum, binabawasan ito kapag hinahanap ang minimum
). Binibigyang-daan ka ng paghahanap na ito na bawasan ang bilang ng mga hakbang kapag hinahanap ang pinakamabuting kalagayan. Ipaliwanag natin ito gamit ang isang graphic na halimbawa.

Hayaang ang rehiyon ng mga magagawang solusyon ay kinakatawan ng isang polygon ABCDE. Ipagpalagay natin na ang sulok na punto nito A tumutugma sa orihinal na solusyon na posible na batayan. Ang isang random na paghahanap ay mangangailangan ng pagsubok ng limang posible na batayan na solusyon na tumutugma sa limang sulok na punto ng polygon. Gayunpaman, mula sa pagguhit ay malinaw na pagkatapos ng tuktok A ito ay kapaki-pakinabang upang lumipat sa isang kalapit na vertex SA, at pagkatapos ay sa pinakamainam na punto SA. Sa halip na lima, dumaan lang kami sa tatlong vertice, na patuloy na pinapabuti ang linear function.

Ang ideya ng sunud-sunod na pagpapabuti ng solusyon ay nabuo ang batayan ng isang unibersal na pamamaraan para sa paglutas ng mga problema sa linear programming - simplex na paraan o paraan ng sunud-sunod na pagpapabuti ng plano.

Ang geometric na kahulugan ng simplex na pamamaraan ay binubuo sa isang sequential transition mula sa isang vertex ng constraint polyhedron (tinatawag na paunang isa) sa kalapit na isa, kung saan linear function tumatagal ang pinakamahusay (hindi bababa sa hindi ang pinakamasama) halaga na may kaugnayan sa layunin ng gawain; hanggang sa matagpuan ang pinakamainam na solusyon - ang vertex kung saan pinakamainam na halaga function ng layunin (kung ang problema ay may pangwakas na pinakamabuting kalagayan).

Ang simplex method ay unang iminungkahi ng American scientist na si J. Danzig noong 1949, ngunit noong 1939 ang mga ideya ng pamamaraan ay binuo ng Russian scientist na si L.V. Kantorovich.

Ang simplex na paraan, na nagbibigay-daan sa paglutas ng anumang problema sa linear programming, ay pangkalahatan. Sa kasalukuyan, ito ay ginagamit para sa mga kalkulasyon ng computer, ngunit ang mga simpleng halimbawa gamit ang simplex na paraan ay maaaring malutas nang manu-mano.

Upang ipatupad ang simplex na paraan - sunud-sunod na pagpapabuti ng solusyon - ito ay kinakailangan upang makabisado tatlong pangunahing elemento:

isang paraan para sa pagtukoy ng anumang paunang magagawa na pangunahing solusyon sa isang problema;

ang panuntunan ng paglipat sa pinakamahusay (mas tiyak, hindi mas masahol pa) solusyon;

criterion para sa pagsuri sa pinakamainam ng solusyon na natagpuan.

Upang magamit ang simplex na paraan, ang problema sa linear programming ay dapat bawasan sa kanonikal na anyo, ibig sabihin. ang sistema ng mga hadlang ay dapat ipakita sa anyo ng mga equation.

Ang panitikan ay naglalarawan sa sapat na detalye: paghahanap ng paunang plano ng suporta (paunang tinatanggap na pangunahing solusyon), gamit din ang paraan ng artipisyal na batayan, paghahanap ng pinakamainam na plano ng suporta, paglutas ng mga problema gamit ang mga simplex na talahanayan.

3.2. Algorithm ng simplex na pamamaraan.

Isaalang-alang natin ang solusyon ng ZLP gamit ang simplex na paraan at ipakita ito kaugnay ng problema sa pag-maximize.

1. Batay sa mga kondisyon ng problema, ang modelo ng matematika nito ay pinagsama-sama.

2. Ang pinagsama-samang modelo ay na-convert sa kanonikal na anyo. Sa kasong ito, maaaring matukoy ang isang batayan na may paunang reference na plano.

3. Ang kanonikal na modelo ng problema ay nakasulat sa anyo ng isang simplex na talahanayan upang ang lahat ng mga libreng termino ay hindi negatibo. Kung napili ang paunang reference na plano, pagkatapos ay magpatuloy sa hakbang 5.

Simplex table: isang sistema ng mga constraint equation at isang layunin na function ay ipinasok sa anyo ng mga expression na nalutas na may kaugnayan sa paunang batayan. Ang linya na naglalaman ng mga coefficient layunin function
, tinawag
–string o target na function na string.

4. Hanapin ang paunang plano ng sanggunian sa pamamagitan ng pagsasagawa ng mga pagbabagong simplex na may positibong paglutas ng mga elemento na tumutugma sa pinakamababang relasyon ng simplex, at nang hindi isinasaalang-alang ang mga palatandaan ng mga elemento
– mga linya. Kung sa panahon ng mga pagbabagong-anyo ay nakatagpo ang isang 0-row, ang lahat ng mga elemento, maliban sa libreng termino, ay mga zero, kung gayon ang sistema ng mga equation ng pagpilit para sa problema ay hindi pare-pareho. Kung makakatagpo tayo ng 0-row kung saan, bukod sa libreng termino, walang iba pang positibong elemento, kung gayon ang sistema ng mga paghihigpit na equation ay walang mga di-negatibong solusyon.

Tatawagin natin ang pagbabawas ng system (2.55), (2.56) sa isang bagong batayan simplex na pagbabago . 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 Hakbang sa pag-aalis ng Jordan.

5. Ang nahanap na paunang plano ng suporta ay sinusuri para sa pinakamainam:

a) kung nasa
– walang negatibong elemento sa row (hindi binibilang ang libreng termino), kung gayon ang plano ay pinakamainam. Kung walang mga zero, pagkatapos ay mayroon lamang isang pinakamainam na plano; kung mayroong hindi bababa sa isang zero, pagkatapos ay mayroong isang walang katapusang bilang ng mga pinakamainam na plano;

b) kung c
– mayroong hindi bababa sa isang negatibong elemento sa row, na tumutugma sa isang column ng mga hindi positibong elemento, kung gayon
;

c) kung nasa
– ang row ay may kahit isang negatibong elemento, at ang column nito ay may kahit isang positibong elemento, pagkatapos ay maaari kang lumipat sa bago sangguniang plano, mas malapit sa pinakamainam. Upang gawin ito, ang tinukoy na column ay dapat italaga bilang isang column sa pagresolba, gamit ang pinakamababang ratio ng simplex, hanapin ang hilera ng paglutas at magsagawa ng pagbabagong simplex. Ang resultang reference plan ay muling susuriin para sa pinakamainam. Ang inilarawan na proseso ay paulit-ulit hanggang sa makuha ang isang pinakamainam na plano o hanggang sa hindi malutas ang problema ay maitatag.

Ang hanay ng mga coefficient para sa isang variable na kasama sa batayan ay tinatawag na paglutas. Kaya, ang pagpili ng isang variable na ipinasok sa batayan (o pagpili ng isang paglutas ng column) ng negatibong elemento
-strings, nagbibigay kami ng pagtaas ng function
.

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 ay hindi kasama sa batayan (o ang pagpili ng isang linya ng paglutas) ayon sa pinakamababang simplex na ugnayang mga garantiya, gaya ng naitatag na, ang pagiging positibo ng mga batayan na bahagi sa bagong reference plan.

Sa punto 3 ng algorithm, ipinapalagay na ang lahat ng elemento ng column ng mga libreng termino ay hindi negatibo. Ang kinakailangan na ito ay hindi kinakailangan, ngunit kung ito ay natutugunan, ang lahat ng kasunod na simplex na pagbabago ay isinasagawa lamang sa mga positibong elemento ng paglutas, na maginhawa para sa mga kalkulasyon. Kung may mga negatibong numero sa hanay ng mga libreng termino, pipiliin ang elemento ng pagresolba gaya ng sumusunod:

1) tingnan ang linya na tumutugma sa ilang negatibong libreng termino, halimbawa - isang hilera, at pumili ng anumang negatibong elemento sa loob nito, at ang kaukulang hanay ay kinuha bilang paglutas (ipinapalagay namin na ang mga hadlang ng problema ay pare-pareho);

2) bumubuo ng mga ugnayan ng mga elemento ng hanay ng mga libreng termino sa mga kaukulang elemento ng paglutas ng haligi na may parehong mga palatandaan (mga relasyon ng simplex);

3) piliin ang pinakamaliit sa mga ugnayang simplex. Matutukoy nito ang pagpapagana ng string. Hayaan ito, halimbawa, r-linya;

4) sa intersection ng column at row sa pagresolba, matatagpuan ang isang elemento ng paglutas. Kung ang elemento ay permissive –strings, pagkatapos pagkatapos ng simplex transformation ang libreng termino ng string na ito ay magiging positibo. Kung hindi, sa susunod na hakbang ay babalik tayo muli sa -linya. Kung ang problema ay malulutas, pagkatapos ay pagkatapos ng isang tiyak na bilang ng mga hakbang ay walang mga negatibong elemento na natitira sa hanay ng mga libreng termino.

Kung ang isang tiyak na tunay na sitwasyon ng produksyon ay ipinahayag sa anyo ng isang PLP, kung gayon ang mga karagdagang variable na kailangang ipasok sa modelo sa proseso ng pag-convert nito sa canonical form ay palaging may tiyak na pang-ekonomiyang kahulugan.

Isa sa mga pamamaraan para sa paglutas ng mga problema sa pag-optimize ( karaniwang nauugnay sa paghahanap ng minimum o maximum) linear programming ay tinatawag na . Simplex na pamamaraan kabilang ang isang buong pangkat ng mga algorithm at pamamaraan para sa paglutas ng mga problema sa linear programming. Ang isa sa mga pamamaraang ito, na kinabibilangan ng pagtatala ng pinagmumulan ng data at muling pagkalkula sa mga ito sa isang espesyal na talahanayan, ay tinatawag paraan ng tabular simplex.

Isaalang-alang natin ang algorithm ng tabular simplex na paraan gamit ang halimbawa ng solusyon gawain sa produksyon, na bumababa sa paghahanap ng plano sa produksyon na nagsisiguro ng pinakamataas na kita.

Input ang data para sa problema ng simplex method

Gumagawa ang kumpanya ng 4 na uri ng mga produkto, pinoproseso ang mga ito sa 3 makina.

Ang mga pamantayan sa oras (min./piraso) para sa pagproseso ng mga produkto sa mga makina ay tinukoy ng matrix A:

Ang pondo sa oras ng pagpapatakbo ng makina (min.) ay tinukoy sa matrix B:

Ang kita mula sa pagbebenta ng bawat yunit ng produkto (RUB/piraso) ay ibinibigay ng matrix C:

Layunin ng gawain sa produksyon

Gumuhit ng isang plano sa produksyon na magpapalaki sa kita ng negosyo.

Paglutas ng problema gamit ang tabular simplex method

(1) Tukuyin natin sa pamamagitan ng X1, X2, X3, X4 ang nakaplanong bilang ng mga produkto ng bawat uri. Pagkatapos ang nais na plano: ( X1, X2, X3, X4)

(2) Isulat natin ang mga hadlang sa plano sa anyo ng isang sistema ng mga equation:

(3) Kung gayon ang target na kita ay:

Iyon ay, ang tubo mula sa pagtupad sa plano ng produksyon ay dapat na maximum.

(4) Upang malutas ang nagresultang conditional extremum na problema, pinapalitan namin ang sistema ng mga hindi pagkakapantay-pantay ng system mga linear na equation sa pamamagitan ng pagpapasok ng mga karagdagang di-negatibong variable dito ( X5, X6, X7).

(5) Tanggapin natin ang mga sumusunod sangguniang plano:

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) Ipasok natin ang data sa simpleng mesa:

Sa huling linya ipinapasok namin ang mga coefficient ng layunin ng function at ang halaga nito mismo kabaligtaran ng tanda;

(7) Pumili sa huling linya pinakadakila (modulo) ay isang negatibong numero.

Magkalkula tayo b = N / Items_of_the_selected_column

Kabilang sa mga kinakalkula na halaga ng b na pinili namin hindi bababa sa.

Ang intersection ng napiling column at row ay magbibigay sa amin ng elemento ng paglutas. Binago namin ang batayan sa isang variable na tumutugma sa elemento ng paglutas ( X5 hanggang X1).

• Ang mismong elemento ng paglutas ay nagiging 1.
• Para sa mga elemento ng linya ng resolusyon – a ij (*) = a ij / RE ( ibig sabihin, hinahati namin ang bawat elemento sa halaga ng elemento ng paglutas at kumuha ng bagong data).
• Para sa mga elemento ng column ng resolution, nire-reset lang ang mga ito sa zero.
• Muli naming kinakalkula ang natitirang mga elemento ng talahanayan gamit ang panuntunan ng parihaba.

a ij (*) = a ij – (A * B / RE)

Tulad ng nakikita mo, kinukuha namin ang kasalukuyang cell na muling kinakalkula at ang cell na may elemento ng paglutas. Bumubuo sila ng magkasalungat na sulok ng parihaba. Susunod, pinarami namin ang mga halaga mula sa mga cell ng iba pang 2 sulok ng parihaba na ito. Ang gawaing ito ( A * B) hatiin sa elemento ng paglutas ( RE). At ibawas mula sa kasalukuyang cell na muling kinakalkula ( isang ij) anong nangyari. Kumuha kami ng bagong halaga - isang ij (*).

(9) Suriin muli ang huling linya ( c) sa pagkakaroon ng mga negatibong numero. Kung wala sila doon, ang pinakamainam na plano ay natagpuan, pumunta sa huling yugto paglutas ng problema. Kung mayroon, ang plano ay hindi pa optimal, at ang simplex na talahanayan ay kailangang muling kalkulahin.

Dahil mayroon kaming mga negatibong numero sa huling linya, magsisimula kami ng bagong pag-ulit ng mga kalkulasyon.

(10) Dahil walang negatibong elemento sa huling linya, nangangahulugan ito na natagpuan namin ang pinakamainam na plano sa produksyon! Namely: gagawa kami ng mga produktong iyon na lumipat sa column na "Basis" - X1 at X2. Alam natin ang tubo mula sa produksyon ng bawat yunit ng output ( matris C). Ito ay nananatiling upang i-multiply ang nahanap na dami ng produksyon ng mga produkto 1 at 2 na may tubo bawat 1 piraso, nakuha namin ang pangwakas ( maximum! ) tubo para sa isang ibinigay na plano ng produksyon.

SAGOT:

X1 = 32 pcs., X2 = 20 pcs., X3 = 0 pcs., X4 = 0 pcs.

P = 48 * 32 + 33 * 20 = 2,196 kuskusin.

Galyaudinov R.R.

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

. Simplex method algorithm

Halimbawa 5.1. Lutasin ang sumusunod na linear programming problem gamit ang simplex method:

Solusyon:

ako pag-ulit:

x3, x4, x5, x6 x1,x2. Ipahayag natin ang mga pangunahing variable sa mga tuntunin ng mga libre:

Bawasan natin ang target na function sa susunod na view:

Batay sa nakuhang problema, bubuo tayo ng paunang simplex na talahanayan:

Talahanayan 5.3

Orihinal na simplex na talahanayan

				Mga Relasyon sa Pagsusuri

Ayon sa kahulugan ng pangunahing solusyon, ang mga libreng variable ay katumbas ng zero, at ang mga halaga ng mga pangunahing variable ay katumbas ng kaukulang mga halaga ng mga libreng numero, i.e.:

Stage 3: pagsuri sa compatibility ng PAP restrictions system.

Sa pag-ulit na ito (sa Talahanayan 5.3), ang tanda ng hindi pagkakapare-pareho ng sistema ng pagpilit (sign 1) ay hindi natukoy (ibig sabihin, walang linya na may negatibong libreng numero (maliban sa linya ng layunin ng function) kung saan hindi maging kahit isang negatibong elemento (i.e. negatibong koepisyent para sa isang libreng variable)).

Sa pag-ulit na ito (sa Talahanayan 5.3), hindi natukoy ang senyales ng unboundedness ng objective function (sign 2) (ibig sabihin, walang column na may negatibong elemento sa row ng objective function (maliban sa column ng mga libreng numero. ) kung saan hindi magkakaroon ng kahit isang positibong elemento) .

Dahil ang nahanap na pangunahing solusyon ay hindi naglalaman ng mga negatibong sangkap, ito ay tinatanggap.

Stage 6: pagsusuri ng pinakamainam.

Ang nahanap na pangunahing solusyon ay hindi pinakamainam, dahil ayon sa pinakamainam na pamantayan (sign 4) ay hindi dapat magkaroon ng mga negatibong elemento sa linya ng layunin ng pag-andar ( libreng numero ang linyang ito ay hindi isinasaalang-alang kapag isinasaalang-alang ang katangiang ito). Samakatuwid, ayon sa algorithm ng simplex na pamamaraan, lumipat kami sa yugto 8.

Dahil tinatanggap ang nahanap na pangunahing solusyon, hahanapin namin ang column ng paglutas ayon sa sumusunod na scheme: tinutukoy namin ang mga column na may mga negatibong elemento sa hilera ng layunin na function (maliban sa column ng mga libreng numero). Ayon sa Talahanayan 5.3, mayroong dalawang ganoong column: column “ x1"at column" x2" Mula sa naturang mga column, pipiliin ang isa na naglalaman ng pinakamaliit na elemento sa row ng target na function. Siya ang magiging permissive. Column" x2" naglalaman ng pinakamaliit na elemento (–3) kumpara sa column " x1

Upang matukoy ang linya ng paglutas, nakita namin ang mga positibong tinantyang ratio ng mga libreng numero sa mga elemento ng column ng paglutas ng linya na tumutugma sa pinakamaliit na positibong ratio ng pagsusuri ay tinatanggap bilang nalutas.

Talahanayan 5.4

Orihinal na simplex na talahanayan

Sa Talahanayan 5.4, ang pinakamaliit na positibong evaluative na relasyon ay tumutugma sa linyang " x5", samakatuwid, ito ay magiging permissive.

Ang elementong matatagpuan sa intersection ng column na nagpapagana at ang row na nagpapagana ay tinatanggap bilang pagpapagana. Sa aming halimbawa, ito ang elemento na matatagpuan sa intersection ng linya " x5"at mga hanay" x2».

Ang elemento ng paglutas ay nagpapakita ng isang batayan at isang libreng variable na dapat ipagpalit sa simplex table upang lumipat sa isang bagong "pinahusay" na batayan na solusyon. SA sa kasong ito ito ay mga variable x5 At x2, sa bagong simplex na talahanayan (Talahanayan 5.5) pinapalitan namin ang mga ito.

9.1. Pagbabago ng elemento ng paglutas.

Ang elemento ng resolusyon ng Talahanayan 5.4 ay kino-convert bilang sumusunod:

Ipinasok namin ang resultang resulta sa isang katulad na cell sa Talahanayan 5.5.

9.2. Resolution string conversion.

Hinahati namin ang mga elemento ng row ng paglutas ng talahanayan 5.4 sa pamamagitan ng elemento ng paglutas ng talahanayan ng simplex na ito, ang mga resulta ay magkasya sa mga katulad na mga cell ng bagong talahanayan ng simplex (talahanayan 5.5). Ang mga pagbabago sa mga elemento ng string ng resolusyon ay ibinibigay sa Talahanayan 5.5.

9.3. Pag-convert ng column ng resolution.

Hinahati namin ang mga elemento ng column ng resolution ng Table 5.4 sa elemento ng resolution ng simplex table na ito, at ang resulta ay kinuha gamit ang kabaligtaran na sign. Ang mga resulta na nakuha ay umaangkop sa mga katulad na mga cell ng bagong simplex na talahanayan (Talahanayan 5.5). Ang mga pagbabagong-anyo ng mga elemento ng hanay ng resolusyon ay ibinibigay sa Talahanayan 5.5.

9.4. Pagbabago ng natitirang mga elemento ng simplex table.

Ang pagbabagong-anyo ng natitirang mga elemento ng simplex table (i.e., mga elemento na hindi matatagpuan sa paglutas ng row at paglutas ng column) ay isinasagawa ayon sa panuntunang "rektanggulo".

Halimbawa, isaalang-alang ang pagbabago ng isang elemento na matatagpuan sa intersection ng linya " x3" at mga hanay "", kundisyon naming tukuyin ito " x3" Sa Talahanayan 5.4, gumuhit tayo ng isang parihaba, isang vertex na matatagpuan sa cell na ang halaga ay binabago natin (i.e. sa cell " x3"), at ang isa pa (diagonal vertex) ay nasa isang cell na may elemento ng paglutas. Ang iba pang dalawang vertices (ng pangalawang dayagonal) ay natatanging tinutukoy. Pagkatapos ay ang binagong halaga ng cell " x3" ay magiging katumbas ng nakaraang halaga ng cell na ito na binawasan ang fraction, sa denominator na kung saan ay ang paglutas ng elemento (mula sa Talahanayan 5.4), at sa numerator ay ang produkto ng dalawang iba pang hindi nagamit na vertices, i.e.:

« x3»: .

Ang mga halaga ng iba pang mga cell ay na-convert nang katulad:

« x3 x1»: ;

« x4»: ;

« x4 x1»: ;

« x6»: ;

« x6 x1»: ;

«»: ;

« x1»: .

Bilang resulta ng mga pagbabagong ito, nakatanggap kami ng bago simpleng mesa(Talahanayan 5.5).

II pag-ulit:

Stage 1: pagguhit ng simplex table.

Talahanayan 5.5

Simplex na talahanayanII mga pag-ulit

				Tinatantya relasyon

Stage 2: pagpapasiya ng pangunahing solusyon.

Bilang resulta ng mga pagbabagong simplex, isang bagong pangunahing solusyon ang nakuha (Talahanayan 5.5):

Tulad ng nakikita mo, sa pangunahing solusyon na ito ang halaga ng layunin ng function = 15, na mas malaki kaysa sa nakaraang pangunahing solusyon.

Ang hindi pagkakapare-pareho ng sistema ng mga paghihigpit alinsunod sa tampok 1 sa Talahanayan 5.5 ay hindi natukoy.

Stage 4: pagsuri sa boundedness ng layunin function.

Ang unboundedness ng layunin function alinsunod sa criterion 2 sa Table 5.5 ay hindi ipinahayag.

Stage 5: pagsuri sa admissibility ng nahanap na pangunahing solusyon.

Ang nahanap na pangunahing solusyon alinsunod sa criterion 4 ay hindi optimal, dahil ang linya ng layunin ng function ng simplex table (Talahanayan 5.5) ay naglalaman ng negatibong elemento: –2 (ang libreng numero ng linyang ito ay hindi isinasaalang-alang kapag isinasaalang-alang ito katangian). Samakatuwid, lumipat tayo sa ika-8 yugto.

Stage 8: pagpapasiya ng elemento ng paglutas.

8.1. Kahulugan ng hanay ng resolusyon.

Ang nahanap na pangunahing solusyon ay katanggap-tanggap; tinutukoy namin ang mga haligi na may mga negatibong elemento sa hilera ng layunin na pag-andar (maliban sa hanay ng mga libreng numero). Ayon sa Talahanayan 5.5, mayroon lamang isang kolum: " x1" Samakatuwid, tinatanggap namin ito bilang pinahihintulutan.

8.2. Kahulugan ng isang enable string.

Ayon sa nakuha na mga halaga ng positibong evaluative na relasyon sa Talahanayan 5.6, ang pinakamababa ay ang kaugnayan na naaayon sa linya " x3" Samakatuwid, tinatanggap namin ito bilang pinahihintulutan.

Talahanayan 5.6

Simplex na talahanayanII mga pag-ulit

				Tinatantya relasyon
				3/1=3 – min

Stage 9: pagbabago ng simplex table.

Ang mga pagbabago sa simplex table (Talahanayan 5.6) ay ginaganap sa parehong paraan tulad ng sa nakaraang pag-ulit. Ang mga resulta ng mga pagbabagong-anyo ng mga elemento ng simplex na talahanayan ay ibinibigay sa Talahanayan 5.7.

III pag-ulit

Batay sa mga resulta ng mga pagbabagong simplex ng nakaraang pag-ulit, nag-compile kami ng bagong talahanayan ng simplex:

Talahanayan 5.7

Simplex na talahanayanIII mga pag-ulit

				Tinatantya relasyon

Stage 2: pagpapasiya ng pangunahing solusyon.

Bilang resulta ng mga pagbabagong simplex, isang bagong pangunahing solusyon ang nakuha (Talahanayan 5.7):

Stage 3: suriin ang pagiging tugma ng sistema ng mga paghihigpit.

Ang hindi pagkakapare-pareho ng sistema ng mga paghihigpit alinsunod sa tampok 1 sa Talahanayan 5.7 ay hindi natukoy.

Stage 4: pagsuri sa boundedness ng layunin function.

Ang unboundedness ng layunin function alinsunod sa criterion 2 sa Table 5.7 ay hindi ipinahayag.

Stage 5: pagsuri sa admissibility ng nahanap na pangunahing solusyon.

Ang nahanap na pangunahing solusyon alinsunod sa criterion 3 ay tinatanggap, dahil hindi ito naglalaman ng mga negatibong sangkap.

Stage 6: pagsuri sa pinakamainam ng nahanap na pangunahing solusyon.

Ang nahanap na pangunahing solusyon alinsunod sa criterion 4 ay hindi optimal, dahil ang linya ng layunin ng function ng simplex table (Talahanayan 5.7) ay naglalaman ng negatibong elemento: –3 (ang libreng numero ng linyang ito ay hindi isinasaalang-alang kapag isinasaalang-alang ito. katangian). Samakatuwid, lumipat tayo sa ika-8 yugto.

Stage 8: pagpapasiya ng elemento ng paglutas.

8.1. Kahulugan ng hanay ng resolusyon.

Ang nahanap na pangunahing solusyon ay katanggap-tanggap; tinutukoy namin ang mga haligi na may mga negatibong elemento sa hilera ng layunin na pag-andar (maliban sa hanay ng mga libreng numero). Ayon sa Talahanayan 5.7, mayroon lamang isang ganoong column: “ x5" Samakatuwid, tinatanggap namin ito bilang pinahihintulutan.

8.2. Kahulugan ng isang enable string.

Ayon sa nakuha na mga halaga ng positibong ebalwasyon na mga relasyon sa Talahanayan 5.8, ang pinakamababa ay ang kaugnayan na naaayon sa linya " x4" Samakatuwid, tinatanggap namin ito bilang pinahihintulutan.

Talahanayan 5.8

Simplex na talahanayanIII mga pag-ulit

				Tinatantya relasyon
				5/5=1 – min

Stage 9: pagbabago ng simplex table.

Ang mga pagbabagong-anyo ng simplex table (Talahanayan 5.8) ay ginaganap sa parehong paraan tulad ng sa nakaraang pag-ulit. Ang mga resulta ng mga pagbabagong-anyo ng mga elemento ng simplex na talahanayan ay ibinibigay sa Talahanayan 5.9.

IV pag-ulit

Stage 1: pagbuo ng bagong simplex table.

Batay sa mga resulta ng mga pagbabagong simplex ng nakaraang pag-ulit, nag-compile kami ng bagong talahanayan ng simplex:

Talahanayan 5.9

Simplex na talahanayanIV mga pag-ulit

				Tinatantya relasyon
			–(–3/5)=3/5
			–(1/5)=–1/5
			–(9/5)=–9/5
			–(–3/5)=3/5

Stage 2: pagpapasiya ng pangunahing solusyon.

Bilang resulta ng mga pagbabagong simplex, isang bagong pangunahing solusyon ang nakuha ayon sa Talahanayan 5.9, ang solusyon ay ang mga sumusunod:

Stage 3: suriin ang pagiging tugma ng sistema ng mga paghihigpit.

Ang hindi pagkakapare-pareho ng sistema ng mga paghihigpit alinsunod sa tampok 1 sa Talahanayan 5.9 ay hindi natukoy.

Stage 4: pagsuri sa boundedness ng layunin function.

Ang unboundedness ng layunin function alinsunod sa criterion 2 sa Table 5.9 ay hindi ipinahayag.

Stage 5: pagsuri sa admissibility ng nahanap na pangunahing solusyon.

Ang nahanap na pangunahing solusyon alinsunod sa criterion 3 ay tinatanggap, dahil hindi ito naglalaman ng mga negatibong sangkap.

Stage 6: pagsuri sa pinakamainam ng nahanap na pangunahing solusyon.

Ang nahanap na pangunahing solusyon alinsunod sa tampok 4 ay pinakamainam, dahil walang mga negatibong elemento sa linya ng layunin ng function ng simplex table (Talahanayan 5.9) (ang libreng numero ng linyang ito ay hindi isinasaalang-alang kapag isinasaalang-alang ang tampok na ito) .

Stage 7: pagsuri sa kahalili ng solusyon.

Ang solusyon na natagpuan ay natatangi, dahil ang linya ng layunin ng function (Talahanayan 5.9) ay hindi naglalaman zero elemento(ang libreng numero ng linyang ito ay hindi isinasaalang-alang kapag isinasaalang-alang ang katangiang ito).

Sagot: ang pinakamainam na halaga ng layunin ng pag-andar ng problemang isinasaalang-alang =24, na nakamit sa.

Halimbawa 5.2. Lutasin ang problema sa linear programming sa itaas sa kondisyon na ang layunin ng function ay pinaliit:

Solusyon:

ako pag-ulit:

Stage 1: pagbuo ng paunang simplex table.

Orihinal na problema linear programming ay tinukoy sa karaniwang anyo. Dalhin natin ito sa canonical form sa pamamagitan ng paglalagay ng karagdagang di-negatibong variable sa bawat isa sa mga hadlang sa hindi pagkakapantay-pantay, i.e.

Sa nagresultang sistema ng mga equation ay kinukuha namin bilang pinapayagan (basic) na mga variable x3, x4, x5, x6, kung gayon ang mga libreng variable ay magiging x1,x2. Ipahayag natin ang mga pangunahing variable sa mga tuntunin ng mga libre.

Para sa pagbebenta ng tatlong pangkat ng mga kalakal komersyal na negosyo ay may tatlong uri ng limitadong materyal at pera na mapagkukunan sa halagang b 1 = 240, b 2 = 200, b 3 = 160 na yunit. Kasabay nito, para sa pagbebenta ng 1 pangkat ng mga kalakal para sa 1 libong rubles. turnover ng kalakal, ang mapagkukunan ng unang uri ay natupok sa halaga ng isang 11 = 2 yunit, ang mapagkukunan ng pangalawang uri sa halaga ng isang 21 = 4 na yunit, ang mapagkukunan ng ikatlong uri sa halaga ng isang 31 = 4 na yunit. Para sa pagbebenta ng 2 at 3 grupo ng mga kalakal para sa 1 libong rubles. Ang turnover ay natupok ayon sa mapagkukunan ng unang uri sa halaga ng isang 12 = 3, isang 13 = 6 na yunit, ang mapagkukunan ng pangalawang uri sa halaga ng isang 22 = 2, isang 23 = 4 na yunit, ang mapagkukunan ng ang pangatlong uri sa halaga ng isang 32 = 6, isang 33 = 8 na yunit . Ang kita mula sa pagbebenta ng tatlong grupo ng mga kalakal para sa 1 libong rubles. ang turnover ay ayon sa pagkakabanggit c 1 = 4, c 2 = 5, c 3 = 4 (libong rubles). Tukuyin ang nakaplanong dami at istraktura ng turnover ng kalakalan upang kumita negosyong pangangalakal ay ang maximum.

Sa direktang problema ng pagpaplano ng turnover, nalutas sa pamamagitan ng simplex na pamamaraan, sumulat dalawahang problema linear programming.
I-install conjugate pares ng variables tuwid at dalawahang problema.
Ayon sa mga pares ng conjugate ng mga variable, mula sa solusyon ng direktang problema na nakukuha natin solusyon sa dalawahang problema, kung saan ito ginawa pagtatasa ng mapagkukunan, ginugol sa pagbebenta ng mga kalakal.

Paglutas ng problema gamit ang simplex method

Hayaang x 1, x 2, x 3 ang bilang ng mga kalakal na naibenta, sa libong rubles, 1, 2, 3 na grupo, ayon sa pagkakabanggit. Pagkatapos modelo ng matematika ang gawain ay may anyo:

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

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

Nalulutas namin ang simplex na paraan.

Ipinakilala namin ang mga karagdagang variable x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 upang baguhin ang mga hindi pagkakapantay-pantay sa mga pagkakapantay-pantay.

Kunin natin ang x 4 = 240 bilang batayan; x 5 = 200; x 6 = 160.

Ipinasok namin ang data sa simpleng mesa

Simplex talahanayan No. 1

Layunin ng function:

0 240 + 0 200 + 0 160 = 0

Kinakalkula namin ang mga pagtatantya gamit ang formula:

Δ 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

Dahil may mga negatibong pagtatantya, hindi optimal ang plano. Pinakamababang marka:

Ipinakilala namin ang variable x 2 sa batayan.

Tinutukoy namin ang isang variable na umuusbong mula sa batayan. Upang gawin ito, nakita namin ang pinakamaliit na hindi negatibong ratio para sa x2 column.

= 26.667

Pinakamaliit na hindi negatibo: Q 3 = 26.667. Nakukuha namin ang variable x 6 mula sa batayan

Hatiin ang ika-3 linya ng 6.
Mula sa 1st line, ibawas ang 3rd line, multiplied sa 3
Mula sa 2nd line, ibawas ang 3rd line, multiplied sa 2

Kinakalkula namin:

Nakukuha namin bagong mesa:

Simplex talahanayan No. 2

Layunin ng function:

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

Kinakalkula namin ang mga pagtatantya gamit ang formula:

Δ 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

Dahil may negatibong pagtatantya Δ 1 = - 2/3, hindi optimal ang plano.

Ipinakilala namin ang variable x 1 sa batayan.

Tinutukoy namin ang isang variable na umuusbong mula sa batayan. Upang gawin ito, nakita namin ang pinakamaliit na hindi negatibong ratio para sa column x 1.

Pinakamaliit na hindi negatibo: Q 3 = 40. Nakukuha namin ang variable na x 2 mula sa batayan

Hatiin ang ika-3 linya ng 2/3.
Mula sa ika-2 linya, ibawas ang ika-3 linya, na i-multiply sa 8/3

Kinakalkula namin:

Kumuha kami ng bagong talahanayan:

Simplex talahanayan No. 3

Layunin ng function:

0 160 + 0 40 + 4 40 = 160

Kinakalkula namin ang mga pagtatantya gamit ang formula:

Δ 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

Dahil walang negatibong rating, pinakamainam ang plano.

Solusyon sa problema:

Sagot

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

Iyon ay, kinakailangang ibenta ang unang uri ng mga kalakal sa halagang 40 libong rubles. Hindi na kailangang magbenta ng mga kalakal ng mga uri 2 at 3. Kasabay nito pinakamataas na kita magiging F max = 160 libong rubles.

Solusyon sa dalawahang problema

Ang dalawahang problema ay may anyo:

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

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

Ipinakilala namin ang mga karagdagang variable y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 upang baguhin ang mga hindi pagkakapantay-pantay sa mga pagkakapantay-pantay.

Ang mga pares ng conjugate ng mga variable ng direkta at dalawahang problema ay may anyo:

Mula sa huling simplex na talahanayan No. 3 ng direktang problema, nakita namin ang solusyon sa dalawahang problema:

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;

Mga problema sa linear programming. Ito ay nasa isang sunud-sunod na konstruksiyon na nagpapakilala sa prosesong isinasaalang-alang. Ang solusyon ay nahahati sa tatlong pangunahing yugto: pagpili ng mga variable, pagbuo ng isang sistema ng mga hadlang at paghahanap para sa isang layunin na function.

Batay sa dibisyong ito, ang kondisyon ng problema ay maaaring i-rephrase tulad ng sumusunod: extremum ng layunin ng function Z(X) = f(x1, x2, … ,xn) → max (min) at ang kaukulang mga variable, kung alam na sila matugunan ang sistema ng mga hadlang: Φ_i ( x1, x2, … ,xn) = 0 para sa i = 1, 2, …, k;Φ_i (x1, x2, … ,xn)) 0 para sa i = k+1, k+ 2, …, m.

Ang sistema ng mga paghihigpit ay dapat dalhin sa isang canonical form, i.e. sa isang sistema ng mga linear equation, kung saan ang bilang ng mga variable mas maraming numero mga equation (m > k). Sa sistemang ito ay tiyak na magkakaroon ng mga variable na maaaring ipahayag sa pamamagitan ng iba pang mga variable, at kung hindi ito ang kaso, maaari silang ipakilala sa artipisyal na paraan. Sa kasong ito, ang mga una ay tinatawag na batayan o artipisyal na batayan, at ang pangalawa ay libre.

Ito ay mas maginhawa upang isaalang-alang ang simplex na paraan sa tiyak na halimbawa. Hayaang magbigay ng linear function na f(x) = 6x1 + 5x2 + 9x3 at isang sistema ng mga hadlang: 5x1 + 2x2 + 3x3 ≤ 25; pinakamataas na halaga mga function f(x).

Solusyon Sa unang yugto, tukuyin ang paunang (reference) na solusyon ng sistema ng mga equation sa isang ganap na arbitrary na paraan, na dapat matugunan ang ibinigay na sistema ng mga paghihigpit. Sa kasong ito, kinakailangan ang pagpapakilala ng artipisyal, i.e. mga pangunahing variable na x4, x5 at x6 tulad ng sumusunod: 5x1 + 2x2 + 3x3 + x4 = 25;

Tulad ng nakikita mo, ang mga hindi pagkakapantay-pantay ay nabago sa mga pagkakapantay-pantay salamat sa mga idinagdag na variable na x4, x5, x6, na mga hindi negatibong dami. Kaya, dinala mo ang sistema sa canonical form nito. Ang variable na x4 ay kasama sa unang equation na may coefficient na 1, at sa pangalawang equation na may coefficient na 0, ang parehong ay totoo para sa mga variable na x5, x6 at ang kaukulang mga equation, na tumutugma sa kahulugan ng batayan.

Naihanda mo na ang system at natagpuan ang paunang reference na solusyon – X0 = (0, 0, 0, 25, 20, 18). Ngayon ipakita ang mga coefficient ng mga variable at ang mga libreng termino ng mga equation (ang mga numero sa kanan ng "=" sign) sa anyo ng isang talahanayan upang ma-optimize ang karagdagang mga kalkulasyon (tingnan ang figure).

Ang kakanyahan ng paraan ng simplex ay upang dalhin ang talahanayang ito sa isang form kung saan ang lahat ng mga numero sa row L ay magiging mga hindi negatibong halaga. Kung ito ay lumabas na ito ay imposible, kung gayon ang sistema ay walang pinakamainam na solusyon. Upang magsimula, piliin ang pinaka pinakamababang elemento ng linyang ito, ito ay -9. Ang numero ay nasa ikatlong hanay. I-convert ang kaukulang x3 variable sa isang batayang variable. Upang gawin ito, hatiin ang linya ng 3 upang ang cell ay magtatapos sa 1.

Ngayon ay kailangan mo ang mga cell at lumiko sa 0. Upang gawin ito, ibawas mula sa kaukulang mga numero ng ikatlong hilera ng 3. Mula sa mga elemento ng pangalawang hilera - ang mga elemento ng pangatlo, pinarami ng 2. At, sa wakas, mula sa ang mga elemento ng L row - pinarami ng (-9). Nakuha mo ang pangalawang reference na solusyon: f(x) = L = 54 na may x1 = (0, 0, 6, 7, 8, 0).