nagustuhan mo ba? Idagdag sa mga bookmark

Paglutas ng mga problema gamit ang simplex na paraan: online na mga 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 problema linear programming simplex na pamamaraan.

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 nagreresulta pinakamainam na plano hindi magbabago.

Gawain 4. Lutasin ang isang linear programming problem simplex na pamamaraan:

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

Gawain 6. Lutasin ang problema gamit ang simplex method, na isinasaalang-alang bilang inisyal sangguniang plano, 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.
Gumuhit 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

Ang isang halimbawa ng paglutas ng isang problema gamit ang simplex na pamamaraan ay isinasaalang-alang, pati na rin ang isang halimbawa ng isang solusyon dalawahang problema.

Kondisyon ng problema

Para sa pagbebenta ng tatlong pangkat ng mga kalakal komersyal na negosyo 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 halagang 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 direkta 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;

. Simplex na paraan ng 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 hilera ng paglutas ng talahanayan 5.4 sa pamamagitan ng elemento ng paglutas ng talahanayang simplex na ito, ang mga resulta ay magkasya sa mga katulad na selula 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 talahanayan 5.4 sa elemento ng resolution ng simplex table na ito, at ang resulta ay kinuha mula sa kabaligtaran ng tanda. 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 nating tukuyin ito " x3" Sa Talahanayan 5.4, gumuhit tayo ng isang parihaba sa isip, ang isang vertex ay 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: pag-compile 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 string ng pahintulot.

Ayon sa nakuha na mga halaga ng positibong ebalwasyon na mga 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 kolum: “ x5" Samakatuwid, tinatanggap namin ito bilang pinahihintulutan.

8.2. Kahulugan ng string ng pahintulot.

Ayon sa nakuha na mga halaga ng positibong ebalwasyon na relasyon sa Talahanayan 5.8, ang pinakamababa ay ang kaugnayan na naaayon sa linyang " 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 pagbabago sa simplex na talahanayan (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: pinakamainam na halaga 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 kanonikal na anyo sa pamamagitan ng pagpapasok sa bawat isa sa hindi pagkakapantay-pantay na mga hadlang sa isang karagdagang di-negatibong variable, 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.

Simplex na pamamaraan ay isang umuulit na proseso ng nakadirekta na solusyon ng isang sistema ng mga equation na hakbang-hakbang, na nagsisimula sa isang reference na solusyon at sa paghahanap ng pinakamahusay na pagpipilian gumagalaw sa kahabaan ng mga sulok na punto ng lugar ng posible na solusyon, na pinapabuti ang halaga ng layunin ng layunin hanggang sa maabot ng layunin ang pinakamainam na halaga.

Layunin ng serbisyo. Ang serbisyo ay inilaan para sa mga online na solusyon Mga problema sa linear programming (LPP) gamit ang simplex na pamamaraan sa sumusunod na mga form mga entry:

• sa anyo ng isang simplex table (paraan ng pagbabago ng Jordan); pangunahing anyo mga talaan;
• 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 nagresultang solusyon ay naka-imbak sa Word file at Excel.

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. Awtomatikong tinutukoy ng solusyon 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 paraan para sa paglutas ng ZLP
Solusyon sa problema sa transportasyon
Paglutas ng isang matrix na laro
Gamit ang serbisyo sa online mode maaari mong matukoy ang presyo ng isang matrix game (lower at upper bounds), suriin ang pagkakaroon ng saddle point, maghanap ng solusyon sa isang halo-halong diskarte gamit ang mga sumusunod na pamamaraan: minimax, simplex method, graphical (geometric) method, Brown's method .
Extremum ng isang function ng dalawang variable
Mga problema sa dinamikong programming
Ipamahagi ang 5 magkakatulad na maraming kalakal sa pagitan ng tatlong pamilihan upang makakuha 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. Pumunta sa canonical form mga problema sa linear programming sa pamamagitan ng pagpapakilala ng mga di-negatibong karagdagang mga 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. Sa mga negatibong coefficient ng linya ng index, ang pinakamalaking isa ay napili ganap na halaga. 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 ito ay kinakailangan upang mahanap ang extremum ng layunin function, pagkatapos pinag-uusapan natin tungkol sa paghahanap pinakamababang halaga(F(x) → min , tingnan ang halimbawa ng paglutas ng function minimization) at pinakamataas na halaga((F(x) → max , tingnan ang halimbawa ng paglutas ng pag-maximize ng 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 matambok linear na kumbinasyon 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.
Pagpapatupad ng simplex na pamamaraan sa puwersa iba't ibang katangian at mga pahayag ng problema, ang LP ay may iba't ibang 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 tulad na A k - isang di-batayan na vector kung saan D k = 0. Pagkatapos ay ang maximum ay nakamit sa pamamagitan ng kahit man lang sa dalawang punto, i.e. mayroong isang alternatibong pinakamabuting kalagayan. Kung ipinakilala namin 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 na 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.

Ang pamamaraang ito ay isang paraan ng may layuning enumeration ng mga reference na solusyon sa isang linear programming problem. Nagbibigay-daan ito, sa isang limitadong bilang ng mga hakbang, alinman sa paghahanap ng pinakamainam na solusyon o upang maitatag na walang pinakamainam na solusyon.

Ang pangunahing nilalaman ng simplex na pamamaraan ay ang mga sumusunod:

1. Magpahiwatig ng isang paraan para sa paghahanap ng pinakamainam na reference na solusyon
2. Ipahiwatig ang paraan ng paglipat mula sa isang reference na solusyon patungo sa isa pa, kung saan ang halaga ng layunin ng function ay magiging mas malapit sa pinakamainam, i.e. magpahiwatig ng isang paraan upang mapabuti ang reference na solusyon
3. Magtakda ng mga pamantayan na nagbibigay-daan sa iyo na agad na huminto sa paghahanap ng mga solusyon sa suporta sa pinakamainam na solusyon o gumawa ng konklusyon tungkol sa kawalan ng pinakamainam na solusyon.

Algorithm ng simplex na pamamaraan para sa paglutas ng mga problema sa linear programming

Upang malutas ang isang problema gamit ang simplex na pamamaraan, dapat mong gawin ang mga sumusunod:

1. Dalhin ang problema sa canonical form
2. Hanapin ang paunang solusyon sa suporta na may "batay sa yunit" (kung walang solusyon sa suporta, kung gayon ang problema ay walang solusyon dahil sa hindi pagkakatugma ng sistema ng mga hadlang)
3. Kalkulahin ang mga pagtatantya ng mga pagkabulok ng vector batay sa reference na solusyon at punan ang talahanayan ng simplex na paraan
4. Kung ang criterion para sa pagiging natatangi ng pinakamainam na solusyon ay nasiyahan, pagkatapos ay ang solusyon ng problema ay nagtatapos
5. Kung ang kondisyon para sa pagkakaroon ng isang hanay ng mga pinakamainam na solusyon ay natutugunan, kung gayon ang lahat ng pinakamainam na solusyon ay matatagpuan sa pamamagitan ng simpleng enumeration

Isang halimbawa ng paglutas ng problema gamit ang simplex method

Halimbawa 26.1

Lutasin ang problema gamit ang simplex method:

Solusyon:

Dinadala namin ang problema sa canonical form.

Para sa layuning ito sa kaliwang bahagi Para sa unang hadlang sa hindi pagkakapantay-pantay, nagpapakilala kami ng karagdagang variable x 6 na may coefficient na +1. Ang variable na x 6 ay kasama sa layunin ng function na may koepisyent na zero (ibig sabihin, hindi ito kasama).

Nakukuha namin:

Nahanap namin ang paunang solusyon sa suporta. Upang gawin ito, itinutumbas namin ang mga libreng (hindi nalutas) na mga variable sa zero x1 = x2 = x3 = 0.

Nakukuha namin sangguniang solusyon X1 = (0,0,0,24,30,6) na may unit na batayan B1 = (A4, A5, A6).

Kinakalkula namin mga pagtatantya ng mga vector decomposition mga kondisyon batay sa reference na solusyon ayon sa formula:

Δ k = C b X k - c k

• C b = (c 1, c 2, ..., c m) - vector ng mga coefficient ng layunin ng function para sa mga pangunahing variable
• X k = (x 1k, x 2k, ..., x mk) - vector ng pagpapalawak ng kaukulang vector A k ayon sa batayan ng reference na solusyon
• Ang C k ay ang koepisyent ng layunin ng function para sa variable na x k.

Ang mga pagtatantya ng mga vector na kasama sa batayan ay palaging katumbas ng zero. Ang reference solution, expansion coefficient at mga pagtatantya ng pagpapalawak ng condition vectors batay sa reference solution ay nakasulat sa simpleng mesa:

Sa tuktok ng talahanayan, para sa kaginhawaan ng pagkalkula ng mga pagtatantya, ang mga coefficient ng layunin ng function ay nakasulat. Sa unang hanay na "B" ang mga vector na kasama sa batayan ng reference na solusyon ay nakasulat. Ang pagkakasunud-sunod kung saan isinulat ang mga vector na ito ay tumutugma sa mga bilang ng mga pinapayagang hindi alam sa mga equation ng pagpilit. Sa pangalawang hanay ng talahanayan na "C b" ang mga coefficient ng layunin ng function para sa mga pangunahing variable ay nakasulat sa parehong pagkakasunud-sunod. Sa tamang lokasyon Ang mga coefficient ng layunin ng function sa column na "C b" ng pagtatantya ng mga unit vectors na kasama sa batayan ay palaging katumbas ng zero.

SA huling linya mga talahanayan na may mga pagtatantya Δ k sa hanay na "A 0" ang mga halaga ng layunin ng function sa reference na solusyon Z(X 1) ay nakasulat.

Ang paunang solusyon sa suporta ay hindi pinakamainam, dahil sa pinakamataas na problema ang mga pagtatantya Δ 1 = -2, Δ 3 = -9 para sa mga vectors A 1 at A 3 ay negatibo.

Ayon sa theorem sa pagpapabuti ng solusyon sa suporta, kung sa isang maximum na problema, ang hindi bababa sa isang vector ay may negatibong pagtatantya, pagkatapos ay makakahanap ka ng isang bagong solusyon sa suporta kung saan ang halaga ng layunin ng function ay magiging mas malaki.

Alamin natin kung alin sa dalawang vector ang hahantong sa mas malaking pagtaas sa layunin ng function.

Ang pagtaas ng layunin ng function ay matatagpuan sa pamamagitan ng formula: .

Kinakalkula namin ang mga halaga ng parameter θ 01 para sa una at pangatlong haligi gamit ang formula:

Nakukuha namin ang θ 01 = 6 para sa l = 1, θ 03 = 3 para sa l = 1 (Talahanayan 26.1).

Nakikita namin ang pagtaas ng layunin ng function kapag ipinakilala sa batayan ang unang vector ΔZ 1 = - 6*(- 2) = 12, at ang ikatlong vector ΔZ 3 = - 3*(- 9) = 27.

Dahil dito, para sa isang mas mabilis na diskarte sa pinakamainam na solusyon, kinakailangan na ipakilala ang vector A3 sa batayan ng reference na solusyon sa halip na ang unang vector ng batayan A6, dahil ang minimum ng parameter na θ 03 ay nakamit sa unang hilera ( l = 1).

Ginagawa namin ang pagbabagong-anyo ng Jordan na may elementong X13 = 2, nakuha namin ang pangalawang sanggunian na solusyon X2 = (0,0,3,21,42,0) na may batayan B2 = (A3, A4, A5). (Talahanayan 26.2)

Ang solusyon na ito ay hindi pinakamainam, dahil ang vector A2 ay may negatibong pagtatantya Δ2 = - 6. Upang mapabuti ang solusyon, kinakailangang ipasok ang vector A2 sa batayan ng reference na solusyon.

Tinutukoy namin ang bilang ng vector na nagmula sa batayan. Upang gawin ito, kinakalkula namin ang parameter θ 02 para sa pangalawang haligi, ito ay katumbas ng 7 para sa l = 2. Dahil dito, nakukuha namin ang pangalawang batayan na vector A4 mula sa batayan. Isinasagawa namin ang pagbabagong-anyo ng Jordan na may elementong x 22 = 3, nakuha namin ang ikatlong sanggunian na solusyon X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Talahanayan 26.3).

Ang solusyon na ito ay ang pinakamainam lamang, dahil para sa lahat ng mga vector na hindi kasama sa batayan ang mga pagtatantya ay positibo

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

Sagot: max Z(X) = 201 sa X = (0.7,10,0.63).

Linear programming method sa economic analysis

Pamamaraan ng linear programming ginagawang posible na bigyang-katwiran ang pinakamainam desisyon sa ekonomiya sa ilalim ng mga kondisyon ng matinding paghihigpit na may kaugnayan sa mga mapagkukunang ginagamit sa produksyon (fixed asset, materyales, labor resources). Ang paggamit ng pamamaraang ito sa pagsusuri sa ekonomiya ay ginagawang posible upang malutas ang mga problema na pangunahing nauugnay sa pagpaplano ng mga aktibidad ng isang organisasyon. Ang pamamaraang ito ay nakakatulong na matukoy ang pinakamainam na antas ng output, pati na rin ang mga direksyon para sa karamihan mabisang paggamit mga mapagkukunan ng produksyon na magagamit ng organisasyon.

Gamit ang pamamaraang ito, malulutas ang tinatawag na matinding mga problema, na binubuo sa paghahanap ng mga matinding halaga, iyon ay, ang maximum at minimum na mga pag-andar mga variable.

Ang panahong ito ay batay sa paglutas ng isang sistema ng mga linear na equation sa mga kaso kung saan ang nasuri na mga pang-ekonomiyang phenomena ay konektado nang linearly, mahigpit na functional dependence. Ang linear programming method ay ginagamit upang pag-aralan ang mga variable sa pagkakaroon ng ilang mga salik na naglilimita.

Ang isang napaka-karaniwang solusyon ay ang tinatawag na problema sa transportasyon gamit ang linear programming method. Ang nilalaman ng gawaing ito ay upang mabawasan ang mga gastos na natamo kaugnay ng pagpapatakbo ng mga sasakyan sa ilalim ng umiiral na mga paghihigpit tungkol sa bilang ng mga sasakyan, ang kanilang kapasidad sa pagdadala, ang tagal ng kanilang operasyon, kung may pangangailangan para sa pagpapanatili maximum na dami mga customer.

Bukod dito, ang pamamaraang ito ay malawakang ginagamit sa paglutas ng mga problema sa pag-iiskedyul. Ang gawaing ito ay binubuo ng gayong pamamahagi ng oras ng pagpapatakbo para sa mga tauhan ng isang partikular na organisasyon na magiging pinakakatanggap-tanggap kapwa para sa mga miyembro ng tauhan na ito at para sa mga kliyente ng organisasyon.

Ang gawaing ito ay upang i-maximize ang bilang ng mga kliyenteng pinaglilingkuran sa ilalim ng mga kundisyon ng mga limitasyon sa bilang ng magagamit na mga miyembro ng kawani, pati na rin ang pondo sa oras ng pagtatrabaho.

Kaya, ang linear programming method ay medyo karaniwan sa placement at usage analysis. iba't ibang uri mga mapagkukunan, pati na rin sa proseso ng pagpaplano at pagtataya ng mga aktibidad ng mga organisasyon.

Gayunpaman, ang mathematical programming ay maaari ding ilapat sa mga pang-ekonomiyang phenomena, ang relasyon sa pagitan nito ay hindi linear. Para sa layuning ito, maaaring gamitin ang mga nonlinear, dynamic at convex na pamamaraan ng programming.

Ang nonlinear programming ay umaasa sa hindi linear na katangian ng layunin ng function o mga hadlang, o pareho. Ang mga anyo ng layunin ng pag-andar at hindi pagkakapantay-pantay na mga hadlang sa mga kundisyong ito ay maaaring magkaiba.

Ang nonlinear programming ay ginagamit sa pagsusuri sa ekonomiya, lalo na, kapag nagtatatag ng ugnayan sa pagitan ng mga tagapagpahiwatig na nagpapahayag ng kahusayan ng mga aktibidad ng isang organisasyon at ang dami ng aktibidad na ito, ang istraktura ng mga gastos sa produksyon, mga kondisyon ng merkado, atbp.

Ang dinamikong programming ay batay sa pagbuo ng isang puno ng desisyon. Ang bawat baitang ng punong ito ay nagsisilbing yugto para matukoy ang mga kahihinatnan nakaraang desisyon at upang alisin ang hindi epektibong mga opsyon para sa solusyon na ito. kaya, dynamic na programming ay may multi-step, multi-stage na kalikasan. Ang ganitong uri ng programming ay ginagamit sa pagsusuri ng ekonomiya upang mahanap pinakamainam na pagpipilian pag-unlad ng organisasyon ngayon at sa hinaharap.

Ang convex programming ay isang uri ng nonlinear programming. Ang ganitong uri ng programming ay nagpapahayag ng hindi linear na katangian ng relasyon sa pagitan ng mga resulta ng mga aktibidad ng isang organisasyon at mga gastos nito. Sinusuri ng convex (aka concave) programming ang convex layunin ng mga function at matambok na sistema ng mga paghihigpit (puntos mga katanggap-tanggap na halaga). Ginagamit ang convex programming sa pagsusuri ng mga aktibidad na pang-ekonomiya na may layuning mabawasan ang mga gastos, at malukong programming na may layuning i-maximize ang kita sa ilalim ng umiiral na mga paghihigpit sa pagkilos ng mga salik na nakakaimpluwensya sa nasuri na mga tagapagpahiwatig sa kabaligtaran na paraan. Dahil dito, sa mga uri ng programming na isinasaalang-alang, ang mga convex na layunin ng function ay pinaliit, at ang mga concave na layunin ng mga function ay na-maximize.