nagustuhan mo ba? Idagdag sa mga bookmark

Paglutas ng mga problema gamit ang simplex na paraan: mga online na halimbawa

Gawain 1. Gumagawa ang kumpanya ng mga istante ng banyo sa dalawang laki - A at B. Tinatantya ng mga nagbebentang ahente na hanggang 550 istante ang maaaring ibenta sa merkado bawat linggo. Ang bawat uri ng istante ay nangangailangan ng 2 m2 ng materyal, at ang bawat uri ng istante ng B ay nangangailangan ng 3 m2 ng materyal. Ang kumpanya ay maaaring makatanggap ng hanggang 1200 m2 ng materyal bawat linggo. Upang gumawa ng isang istante ng uri A, 12 minuto ng oras ng makina ay kinakailangan, at upang gumawa ng isang istante ng uri B - 30 minuto; Ang makina ay maaaring gamitin ng 160 oras sa isang linggo. Kung ang kita mula sa pagbebenta ng mga istante ng uri A ay 3 mga yunit ng pananalapi, at mula sa mga istante ng uri ng B - 4 na mga yunit ng pananalapi. mga yunit, kung gaano karaming mga istante ng bawat uri ang dapat gawin bawat linggo?

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

Gawain 3. Gumagawa ang kumpanya ng 3 uri ng mga produkto: A1, A2, A3, gamit ang dalawang uri ng hilaw na materyales. Ang mga gastos ng bawat uri ng hilaw na materyales bawat yunit ng produksyon, ang mga reserba ng mga hilaw na materyales para sa panahon ng pagpaplano, pati na rin ang kita mula sa isang yunit ng produksyon ng bawat uri ay kilala.

1. Gaano karaming mga item ng bawat uri ang dapat gawin upang mapakinabangan ang kita?
2. Tukuyin ang katayuan ng bawat uri ng hilaw na materyal at ang tiyak na halaga nito.
3. Tukuyin ang maximum na agwat para sa mga pagbabago sa mga imbentaryo ng bawat uri ng hilaw na materyal, sa loob kung saan ang istraktura ng pinakamainam na plano, i.e. Hindi magbabago ang production nomenclature.
4. Tukuyin ang dami ng mga produktong ginawa at ang tubo mula sa produksyon kapag tinataasan ang stock ng isa sa mga kakaunting uri ng hilaw na materyales sa pinakamataas na posibleng halaga (sa loob ng ibinigay na hanay ng output).
5. Tukuyin ang mga pagitan ng pagbabago sa tubo mula sa isang yunit ng produksyon ng bawat uri kung saan ang resultang pinakamainam na plano ay hindi magbabago.

Gawain 4. Lutasin ang isang linear programming problem gamit ang simplex method:

Gawain 5. Lutasin ang isang linear programming problem gamit ang simplex method:

Gawain 6. Lutasin ang problema gamit ang simplex na paraan, na isinasaalang-alang bilang paunang reference plan ang planong ibinigay sa kondisyon:

Gawain 7. Lutasin ang problema gamit ang modified simplex method.
Upang makabuo ng dalawang uri ng mga produkto A at B, tatlong uri ng kagamitan sa teknolohiya ang ginagamit. Upang makagawa ng isang yunit ng produkto A, ang kagamitan ng unang uri ay gumagamit ng a1=4 na oras, kagamitan ng pangalawang uri a2=8 oras, at kagamitan ng ikatlong uri a3=9 na oras. Upang makagawa ng isang yunit ng produkto B, ang kagamitan ng unang uri ay gumagamit ng b1=7 oras, kagamitan ng pangalawang uri b2=3 oras, at kagamitan ng ikatlong uri b3=5 oras.
Ang mga kagamitan ng unang uri ay maaaring gumana para sa paggawa ng mga produktong ito nang hindi hihigit sa t1=49 na oras, kagamitan ng pangalawang uri nang hindi hihigit sa t2=51 na oras, kagamitan ng ikatlong uri nang hindi hihigit sa t3=45 na oras.
Ang kita mula sa pagbebenta ng isang yunit ng tapos na produkto A ay ALPHA = 6 rubles, at ang produkto B ay BETTA = 5 rubles.
Bumuo ng isang plano para sa produksyon ng mga produkto A at B, na tinitiyak ang pinakamataas na kita mula sa kanilang pagbebenta.

Gawain 8. Hanapin ang pinakamainam na solusyon gamit ang dual simplex method

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 ay mas malaki kaysa sa bilang ng 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 una ay tinatawag na isang batayan o isang artipisyal na batayan, at ang huli ay tinatawag na libre.

Ito ay mas maginhawa upang isaalang-alang ang simplex na paraan gamit ang isang tiyak na halimbawa. Hayaang magbigay ng linear function na f(x) = 6x1 + 5x2 + 9x3 at isang sistema ng mga hadlang: 5x1 + 2x2 + 3x3 ≤ 25; x1 + 6x2 + 2x3 ≤ 20; halaga ng function na 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 hadlang. 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 makikita 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 isang koepisyent ng 1, at sa pangalawa - na may isang koepisyent ng 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 imposible, kung gayon ang sistema ay walang pinakamainam na solusyon sa lahat. Una, piliin ang pinakamaliit na elemento ng linyang ito, na -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).

Isaalang-alang natin simplex na pamamaraan para sa paglutas ng mga problema sa linear programming (LP). Ito ay batay sa paglipat mula sa isang reference plan patungo sa isa pa, kung saan tumataas ang halaga ng layunin ng function.

Ang algorithm ng simplex method ay ang mga sumusunod:

1. Binabago namin ang orihinal na problema sa canonical form sa pamamagitan ng pagpapakilala ng mga karagdagang variable. Para sa mga hindi pagkakapantay-pantay ng form ≤, ang mga karagdagang variable ay ipinakilala na may isang senyas (+), ngunit kung sa form na ≥, pagkatapos ay may isang sign (-). Ang mga karagdagang variable ay ipinakilala sa layunin ng function na may kaukulang mga palatandaan na may isang koepisyent na katumbas ng 0 , dahil hindi dapat baguhin ng target na function ang pang-ekonomiyang kahulugan nito.
2. Ang mga vector ay nakasulat P i mula sa mga coefficient ng mga variable at column ng mga libreng termino. Tinutukoy ng pagkilos na ito ang bilang ng mga vector ng unit. Ang panuntunan ay dapat mayroong kasing dami ng mga vector ng yunit na may mga hindi pagkakapantay-pantay sa sistema ng mga hadlang.
3. Pagkatapos nito, ang source data ay ipinasok sa isang simplex table. Ang mga vector ng yunit ay ipinakilala sa batayan, at sa pamamagitan ng pagbubukod sa kanila mula sa batayan, ang pinakamainam na solusyon ay matatagpuan. Ang mga koepisyent ng layunin ng pag-andar ay nakasulat na may kabaligtaran na tanda.
4. Ang isang tanda ng optimality para sa isang problema sa LP ay ang solusyon ay pinakamainam kung nasa f– sa row lahat ng coefficient ay positibo. Panuntunan para sa paghahanap ng naka-enable na column - tiningnan f– isang string at kabilang sa mga negatibong elemento nito ang pinipili ang pinakamaliit. Vector P i nagiging permissive ang nilalaman nito. Ang panuntunan para sa pagpili ng isang elemento ng paglutas - ang mga ratio ng mga positibong elemento ng haligi ng paglutas sa mga elemento ng vector ay pinagsama-sama P 0 at ang bilang na nagbibigay ng pinakamaliit na ratio ay nagiging elemento ng paglutas kung saan muling kakalkulahin ang simplex table. Ang linyang naglalaman ng elementong ito ay tinatawag na enable line. Kung walang positibong elemento sa column ng resolusyon, walang solusyon ang problema. Matapos matukoy ang elemento ng paglutas, nagpapatuloy sila sa muling pagkalkula ng isang bagong talahanayan ng simplex.
5. Mga panuntunan para sa pagpuno ng bagong simplex table. Ang yunit ay inilalagay sa lugar ng paglutas ng elemento, at ang iba pang mga elemento ay ipinapalagay na pantay 0 . Ang paglutas ng vector ay idinagdag sa batayan, kung saan ang katumbas na zero vector ay hindi kasama, at ang natitirang mga batayan ng vector ay isinulat nang walang mga pagbabago. Ang mga elemento ng linya ng resolusyon ay hinati sa elemento ng resolusyon, at ang natitirang mga elemento ay muling kinakalkula ayon sa panuntunan ng parihaba.
6. Ginagawa ito hanggang sa f– lahat ng elemento ng string ay hindi magiging positibo.

Isaalang-alang natin ang paglutas ng problema gamit ang algorithm na tinalakay sa itaas.
Ibinigay:

Dinadala namin ang problema sa canonical form:

Binubuo namin ang mga vectors:

Punan ang simplex table:

:
Recalculate natin ang unang elemento ng vector P 0, kung saan gumawa kami ng isang parihaba ng mga numero: at nakukuha namin: .

Nagsasagawa kami ng mga katulad na kalkulasyon para sa lahat ng iba pang elemento ng simplex table:

Sa natanggap na plano f– ang linya ay naglalaman ng isang negatibong elemento – (-5/3), vector P 1. Naglalaman ito sa column nito ng isang positibong elemento, na magiging elementong magpapagana. Muli nating kalkulahin ang talahanayan tungkol sa elementong ito:

Walang negatibong elemento sa f– ang ibig sabihin ng linya ay natagpuan pinakamainam na plano:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).

• Ashmanov S. A. Linear programming, M: Nauka, 1998,
• Ventzel E.S. Pananaliksik sa Operasyon, M: Radio ng Sobyet, 2001,
• Kuznetsov Yu.N., Kuzubov V.I., Voloshenko A.B. Mathematical programming, M: Higher School, 1986.

Pasadyang Linear Programming Solution

Maaari kang mag-order ng anumang mga takdang-aralin sa disiplinang ito sa aming website. Maaari kang mag-attach ng mga file at tukuyin ang mga deadline sa

Narito ang manu-manong (hindi applet) na solusyon ng dalawang problema gamit ang simplex na paraan (katulad ng applet solution) na may mga detalyadong paliwanag upang maunawaan ang algorithm para sa paglutas ng mga problema gamit ang simplex na paraan. Ang unang problema ay naglalaman ng mga palatandaan ng hindi pagkakapantay-pantay lamang na "≤" (problema sa isang paunang batayan), ang pangalawa ay maaaring maglaman ng mga palatandaan na "≥", "≤" o "=" (problema sa isang artipisyal na batayan), ang mga ito ay nalutas sa ibang paraan.

Simplex na pamamaraan, paglutas ng isang problema na may paunang batayan

1)Simplex na pamamaraan para sa isang problema na may paunang batayan (lahat ng mga palatandaan ng hindi pagkakapantay-pantay na mga hadlang " ≤ ").

Isulat natin ang problema sa kanonikal anyo, i.e. isinulat muli namin ang mga paghihigpit sa hindi pagkakapantay-pantay sa anyo ng mga pagkakapantay-pantay, pagdaragdag balanse sheet mga variable:

Ang sistemang ito ay isang sistema na may batayan (basis s 1, s 2, s 3, bawat isa sa kanila ay kasama lamang sa isang equation ng system na may koepisyent na 1), x 1 at x 2 ay mga libreng variable. Ang mga problemang lutasin gamit ang simplex na pamamaraan ay dapat magkaroon ng sumusunod na dalawang katangian: - ang sistema ng mga hadlang ay dapat na isang sistema ng mga equation na may batayan; -Ang mga libreng termino ng lahat ng mga equation sa system ay dapat na hindi negatibo.

Ang resultang sistema ay isang sistemang may batayan at ang mga libreng tuntunin nito ay hindi negatibo, kaya maaari tayong mag-apply simplex na pamamaraan. Gumawa tayo ng unang simplex na talahanayan (Iterasyon 0) upang malutas ang problema sa simplex na pamamaraan, ibig sabihin. isang talahanayan ng mga coefficient ng layunin ng function at isang sistema ng mga equation para sa kaukulang mga variable. Dito ang ibig sabihin ng "BP" ay ang column ng mga pangunahing variable, ang "Solusyon" ay ang column ng kanang bahagi ng mga equation ng system. Ang solusyon ay hindi pinakamainam, dahil may mga negatibong coefficient sa z-row.

simplex method iteration 0

							Saloobin

Upang mapabuti ang solusyon, magpatuloy tayo sa susunod na pag-ulit simplex na pamamaraan, nakukuha namin ang sumusunod na simplex table. Upang gawin ito kailangan mong pumili paganahin ang hanay, ibig sabihin. isang variable na isasama sa batayan sa susunod na pag-ulit ng simplex na paraan. Ito ay pinili ng pinakamalaking ganap na negatibong koepisyent sa z-row (sa pinakamataas na problema) - sa paunang pag-ulit ng simplex na paraan ito ay column x 2 (coefficient -6).

Pagkatapos ay piliin paganahin ang string, ibig sabihin. isang variable na mag-iiwan ng batayan sa susunod na pag-ulit ng simplex na paraan. Pinipili ito ng pinakamaliit na ratio ng column na "Desisyon" sa mga kaukulang positibong elemento ng column ng resolution (column "Ratio") - sa paunang pag-ulit ito ay row s 3 (coefficient 20).

Permissive na elemento ay nasa intersection ng resolving column at ang resolving row, ang cell nito ay naka-highlight sa kulay, ito ay katumbas ng 1. Samakatuwid, sa susunod na pag-ulit ng simplex method, ang variable na x 2 ay papalitan ng s 1 sa batayan. Tandaan na hindi hinahanap ang relasyon sa z-string; Kung mayroong magkatulad na minimal na relasyon, kung gayon ang alinman sa mga ito ay napili. Kung ang lahat ng mga coefficient sa column ng resolusyon ay mas mababa sa o katumbas ng 0, kung gayon ang solusyon sa problema ay walang hanggan.

Punan natin ang sumusunod na talahanayan na “Iterasyon 1”. Makukuha namin ito mula sa talahanayan ng "Iterasyon 0". Ang layunin ng karagdagang pagbabago ay gawing column ng unit ang column ng x2 resolution (na may isa sa halip na elemento ng resolution at mga zero sa halip na ang natitirang mga elemento).

1) Kalkulahin ang row x 2 ng table na “Iteration 1”. Una, hinahati namin ang lahat ng mga miyembro ng row s 3 ng paglutas ng talahanayan ng "Iteration 0" sa pamamagitan ng elemento ng paglutas (ito ay katumbas ng 1 sa kasong ito) ng talahanayang ito, nakukuha namin ang row x 2 sa talahanayan ng "Iteration 1". . kasi ang elemento ng paglutas sa kasong ito ay katumbas ng 1, pagkatapos ay ang row s 3 ng talahanayang "Iteration 0" ay magkakasabay sa row x 2 ng talahanayan ng "Iteration 1". Ang Row x 2 ng Iteration 1 table ay nakakuha kami ng 0 1 0 0 1 20, ang natitirang mga row ng Iteration 1 table ay makukuha mula sa row na ito at ang mga row ng Iteration 0 table ay ang mga sumusunod:

2) Pagkalkula ng z-row ng talahanayan na "Iteration 1". Sa halip na -6 sa unang row (z-row) sa x2 column ng Iteration 0 table, dapat mayroong 0 sa unang row ng Iteration 1 table. Upang gawin ito, i-multiply ang lahat ng elemento ng row x 2 ng table na "Iteration 1" 0 1 0 0 1 20 by 6, kumuha ng 0 6 0 0 6 120 at idagdag ang row na ito sa unang row (z - row) ng talahanayan "Iteration 0" -4 -6 0 0 0 0, nakukuha namin -4 0 0 0 6 120. Ang isang zero 0 ay lilitaw sa x 2 column, ang layunin ay nakamit. Ang mga elemento ng column ng resolution x 2 ay naka-highlight sa pula.

3) Pagkalkula ng row s 1 ng table na "Iteration 1". Sa halip na 1 sa s 1 na hilera ng talahanayang “Iteration 0” ay dapat mayroong 0 sa talahanayang “Iteration 1”. Upang gawin ito, i-multiply ang lahat ng elemento ng row x 2 ng table na "Iteration 1" 0 1 0 0 1 20 by -1, kumuha ng 0 -1 0 0 -1 -20 at idagdag ang row na ito na may s 1 - row ng talahanayan "Iteration 0" 2 1 1 0 0 64, nakukuha namin ang row 2 0 1 0 -1 44. Sa x 2 column ay nakukuha namin ang kinakailangang 0.

4) Kalkulahin ang hilera s 2 ng talahanayan ng "Iterasyon 1". Sa lugar na 3 sa s 2 na hilera ng talahanayan na "Iteration 0" dapat mayroong 0 sa talahanayan na "Iteration 1". Upang gawin ito, i-multiply ang lahat ng elemento ng row x 2 ng table na “Iteration 1” 0 1 0 0 1 20 by -3, kumuha ng 0 -3 0 0 -3 -60 at idagdag ang row na ito ng s 1 - row ng table “Iteration 0” 1 3 0 1 0 72, makuha natin ang row 1 0 0 1 -3 12. Sa column na x 2, ang kinakailangang 0 ay nakuha Ang x 2 column sa table na “Iteration 1” ay naging unit , naglalaman ito ng isa 1 at ang natitira ay 0.

Ang mga hilera ng talahanayan na "Iterasyon 1" ay nakuha ayon sa sumusunod na panuntunan:

Bagong row = Old row – (Old row resolution column coefficient)*(Bagong resolution row).

Halimbawa, para sa isang z-string mayroon kami:

Lumang z-string (-4 -6 0 0 0 0) -(-6)*Bagong resolving string -(0 -6 0 0 -6 -120) =Bagong z-string (-4 0 0 0 6 120).

Para sa mga sumusunod na talahanayan, ang muling pagkalkula ng mga elemento ng talahanayan ay ginagawa sa katulad na paraan, kaya tinanggal namin ito.

simplex method na pag-ulit 1

							Saloobin

Ang paglutas ng column x 1, ang paglutas ng row s 2, s 2 ay umalis sa batayan, x 1 ang pumapasok sa batayan. Sa eksaktong parehong paraan, nakukuha namin ang natitirang mga talahanayan ng simplex hanggang sa makuha namin ang isang talahanayan na may lahat ng positibong coefficient sa z-row. Ito ay isang tanda ng isang pinakamainam na talahanayan.

simplex method na pag-ulit 2

							Saloobin

Ang paglutas ng column s 3, paglutas ng row s 1, s 1 ay umalis sa batayan, s 3 ay pumapasok sa batayan.

simplex method na pag-ulit 3

							Saloobin

Sa z-row, ang lahat ng mga coefficient ay hindi negatibo, samakatuwid, ang pinakamainam na solusyon x 1 = 24, x 2 = 16, z max = 192 ay nakuha.

Simplex na pamamaraan ay isang umuulit na proseso ng nakadirekta na solusyon ng isang sistema ng mga equation sa mga hakbang, na nagsisimula sa isang sanggunian na solusyon at, sa paghahanap ng pinakamahusay na opsyon, gumagalaw sa mga sulok na punto ng lugar ng posible na solusyon, pagpapabuti ng halaga ng layunin ng pag-andar hanggang sa ang layunin ng function ay umabot sa pinakamainam na halaga.

Layunin ng serbisyo. Ang serbisyo ay idinisenyo para sa online na paglutas ng mga problema sa linear programming (LPP) gamit ang simplex na paraan sa mga sumusunod na notation form:

• sa anyo ng isang simplex table (paraan ng pagbabago ng Jordan); pangunahing form ng pag-record;
• binagong paraan ng simplex; sa anyo ng hanay; sa line form.

Mga tagubilin. Piliin ang bilang ng mga variable at ang bilang ng mga hilera (bilang ng mga hadlang). Ang resultang solusyon ay nai-save sa isang Word at Excel file.

Bilang ng mga variable 2 3 4 5 6 7 8 9 10
Bilang ng mga hilera (bilang ng mga paghihigpit) 1 2 3 4 5 6 7 8 9 10

Sa kasong ito, huwag isaalang-alang ang mga paghihigpit tulad ng x i ≥ 0. Kung walang mga paghihigpit sa gawain para sa ilang x i, dapat na i-convert ang ZLP sa KZLP, o gamitin ang serbisyong ito. Kapag nag-solve, awtomatikong tinutukoy ang paggamit M-paraan(simplex na paraan na may artipisyal na batayan) at dalawang yugto na simplex na pamamaraan.

Ang mga sumusunod ay ginagamit din sa calculator na ito:
Graphical na pamamaraan para sa paglutas ng ZLP
Solusyon sa problema sa transportasyon
Paglutas ng isang matrix na laro
Gamit ang online na serbisyo, maaari mong matukoy ang presyo ng isang laro ng matrix (mas mababa at itaas na mga hangganan), suriin para sa pagkakaroon ng isang saddle point, maghanap ng solusyon sa isang halo-halong diskarte gamit ang mga sumusunod na pamamaraan: minimax, simplex na pamamaraan, graphical (geometric ) paraan, pamamaraan ni Brown.
Extremum ng isang function ng dalawang variable
Mga problema sa dinamikong programming
Ipamahagi ang 5 homogenous lots ng mga kalakal sa pagitan ng tatlong pamilihan upang makakuha ng pinakamataas na kita mula sa kanilang pagbebenta. Ang kita mula sa mga benta sa bawat market G(X) ay depende sa bilang ng mga naibentang batch ng produkto X at ipinakita sa talahanayan.

Dami ng produkto X (sa lot)	Kita G(X)
	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

Simplex method algorithm kasama ang mga sumusunod na hakbang:

1. Pagguhit ng unang pangunahing plano. Transition sa canonical form ng linear programming problem sa pamamagitan ng pagpapakilala ng mga hindi negatibong karagdagang variable ng balanse.
2. Sinusuri ang plano para sa pinakamainam. Kung mayroong hindi bababa sa isang index line coefficient na mas mababa sa zero, kung gayon ang plano ay hindi optimal at kailangang pagbutihin.
3. Pagtukoy sa nangungunang column at row. Mula sa mga negatibong coefficient ng linya ng index, ang pinakamalaki sa ganap na halaga ay pinili. Pagkatapos ang mga elemento ng libreng miyembro na column ng simplex table ay nahahati sa mga elemento ng parehong tanda ng nangungunang column.
4. Pagbuo ng bagong reference plan. Ang paglipat sa isang bagong plano ay isinasagawa bilang isang resulta ng muling pagkalkula ng talahanayan ng simplex gamit ang pamamaraang Jordan-Gauss.

Kung kinakailangan upang mahanap ang extremum ng layunin function, pagkatapos ay pinag-uusapan natin ang tungkol sa paghahanap ng pinakamababang halaga (F(x) → min, tingnan ang halimbawa ng isang solusyon sa pagliit ng isang function) at ang maximum na halaga ((F(x) ) → max, tingnan ang halimbawa ng isang solusyon sa pag-maximize ng isang function)

Ang isang matinding solusyon ay nakakamit sa hangganan ng rehiyon ng mga magagawang solusyon sa isa sa mga vertices ng mga sulok na punto ng polygon, o sa segment sa pagitan ng dalawang katabing punto ng sulok.

Pangunahing Teorama ng Linear Programming. Kung ang layunin ng ZLP na function ay umabot sa isang matinding halaga sa isang punto sa rehiyon ng mga magagawang solusyon, kung gayon ito ay kukuha ng halagang ito sa sulok na punto. Kung ang layunin ng ZLP na function ay umabot sa isang matinding halaga sa higit sa isang sulok na punto, pagkatapos ay kukuha ito ng parehong halaga sa alinman sa mga convex linear na kumbinasyon ng mga puntong ito.

Ang kakanyahan ng simplex na pamamaraan. Ang paglipat sa pinakamainam na punto ay isinasagawa sa pamamagitan ng paglipat mula sa isang sulok na punto patungo sa kalapit na punto, na naghahatid ng mas malapit at mas mabilis sa X opt. Ang gayong pamamaraan para sa pagbilang ng mga puntos, tinatawag na simplex method, iminungkahi ni R. Danzig.
Ang mga sulok na punto ay nailalarawan sa pamamagitan ng m pangunahing mga variable, kaya ang paglipat mula sa isang sulok na punto patungo sa isang katabi ay maaaring magawa sa pamamagitan ng pagpapalit lamang ng isang pangunahing variable sa batayan sa isang variable mula sa isang hindi batayan.
Ang pagpapatupad ng simplex na paraan, dahil sa iba't ibang mga tampok at formulations ng mga problema sa LP, ay may iba't ibang mga pagbabago.

Ang pagtatayo ng mga simplex na talahanayan ay nagpapatuloy hanggang sa makuha ang pinakamainam na solusyon. Paano mo magagamit ang isang simplex na talahanayan upang matukoy na ang solusyon sa isang linear na problema sa programming ay pinakamainam?
Kung ang huling linya (mga halaga ng layunin ng pag-andar) ay hindi naglalaman ng mga negatibong elemento, samakatuwid, mahahanap nito ang pinakamainam na plano.

Puna 1. Kung ang isa sa mga pangunahing variable ay katumbas ng zero, kung gayon ang matinding punto na tumutugma sa naturang pangunahing solusyon ay bumababa. Ang pagkabulok ay nangyayari kapag may kalabuan sa pagpili ng linya ng gabay. Maaaring hindi mo mapansin ang pagkabulok ng problema kung pipili ka ng isa pang linya bilang gabay. Sa kaso ng kalabuan, dapat piliin ang row na may pinakamababang index upang maiwasan ang pag-loop.

Puna 2. Hayaan sa ilang matinding punto na ang lahat ng simplex differences ay hindi negatibo D k ³ 0 (k = 1..n+m), i.e. ang isang pinakamainam na solusyon ay nakuha at mayroong A k - isang di-batayan na vector kung saan D k = 0. Pagkatapos ang maximum ay nakamit ng hindi bababa sa dalawang puntos, i.e. mayroong isang alternatibong pinakamabuting kalagayan. Kung ipinakilala natin ang variable na ito x k sa batayan, ang halaga ng layunin ng function ay hindi magbabago.

Puna 3. Ang solusyon sa dual problem ay nasa huling simplex table. Ang huling m bahagi ng vector ng mga pagkakaiba ng simplex (sa mga hanay ng mga variable ng balanse) ay ang pinakamainam na solusyon sa dalawahang problema. Ang mga halaga ng mga layunin na pag-andar ng direkta at dalawahang mga problema sa pinakamainam na mga punto ay nag-tutugma.

Puna 4. Kapag nilulutas ang problema sa pag-minimize, ang vector na may pinakamalaking pagkakaiba sa positibong simplex ay ipinakilala sa batayan. Susunod, ang parehong algorithm ay inilapat tulad ng para sa problema sa pag-maximize.

Kung ang kondisyon na "Kailangan na ang uri III na hilaw na materyales ay ganap na maubos" ay tinukoy, kung gayon ang kaukulang kondisyon ay isang pagkakapantay-pantay.