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

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 simplex na talahanayan

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. Sa kasong ito, ang pinakamataas na kita ay 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;

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

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 mga ito mula sa batayan, ang pinakamainam na solusyon ay matatagpuan. Ang mga coefficient ng layunin ng function ay isinulat 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 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:

Bawasan namin ang problema sa kanonikal na anyo:

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

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 simplex na talahanayan:

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 solusyon ng sistema mga linear na equation sa mga kaso kung saan ang nasuri na pang-ekonomiyang phenomena ay konektado nang linearly, mahigpit functional dependence. Ang linear programming method ay ginagamit upang pag-aralan ang mga variable sa pagkakaroon ng ilang mga salik na naglilimita.

Ito ay napaka-pangkaraniwan upang malutas 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 operasyon mga sasakyan sa ilalim ng umiiral na mga paghihigpit hinggil 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 mga convex objective function at convex constraint system (mga 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.

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. Hayaan itong ibigay linear function f(x) = 6x1 + 5x2 + 9x3 at ang sistema ng mga paghihigpit: 5x1 + 2x2 + 3x3 ≤ 25; x1 + 6x2 + 2x3 ≤ 20; 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 sa kasong ito ang pagpapakilala ng artipisyal ay kinakailangan, 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 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. 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).

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 pamamaraan gamit ang halimbawa ng solusyon gawain sa produksyon, na bumababa sa paghahanap ng plano sa produksyon na nagsisiguro pinakamataas na kita.

Mag-input ng 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 isang sistema ng mga linear equation sa pamamagitan ng pagpasok 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 ipinasok namin ang mga coefficient ng layunin ng function at ang halaga nito mismo na may kabaligtaran na 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. Binabago 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)

Gaya 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 rektanggulo. 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