PAKSA: LINEAR PROGRAMMING

GAWAIN 2.A. Paglutas ng problema sa linear programming graphical na pamamaraan

Pansin!

Ito ay isang TRIAL VERSION ng trabaho No. 2073, ang presyo ng orihinal ay 200 rubles. Dinisenyo sa programa ng Microsoft salita.

Pagbabayad. Mga contact.

Pagpipilian 7. Hanapin ang maximum at minimum na mga halagalinear functionФ = 2x 1 - 2 x 2may mga paghihigpit: x 1 + x 2 ≥ 4;

- x 1 + 2 x 2 ≤ 2;

x 1 + 2 x 2 ≤ 10;

x i ≥ 0, i = 1.2.

Solusyon:

Sa pamamagitan ng kondisyon na pagpapalit ng mga palatandaan ng hindi pagkakapantay-pantay ng mga palatandaan ng pagkakapantay-pantay, nakakakuha tayo ng isang sistema ng mga equation x1 + x2 = 4;

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

Bumuo tayo ng mga tuwid na linya gamit ang mga equation na ito, pagkatapos, alinsunod sa mga palatandaan ng hindi pagkakapantay-pantay, pipiliin natin ang kalahating eroplano at makuha ang kanilang karaniwang bahagi - ang rehiyon ng mga tinatanggap na solusyon ng ODR - ang quadrilateral MNPQ.

Pinakamababang halaga ng function

tions - sa puntong M(2; 2)

Ф min = 2·2 - 2·2 = 0.

Ang maximum na halaga ay naabot sa punto N (10; 0),

Ф max = 2·10 - 2·0 = 20.

Pagpipilian 8. Hanapin ang maximum at minimum na mga halaga

linear function Ф = x 1 + x 2

may mga paghihigpit: x 1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 ≥ 0;

x 1 + x 2 - 4 ≥ 0;

x i ≥ 0, i = 1.2.

Solusyon:

Sa pamamagitan ng kondisyon na pagpapalit ng mga palatandaan ng hindi pagkakapantay-pantay ng mga palatandaan ng pagkakapantay-pantay, nakakakuha tayo ng isang sistema ng mga equation x1 - 4 x2 = 4 ;

3 x1 - x2 = 0;

Bumuo tayo ng mga tuwid na linya gamit ang mga equation na ito, pagkatapos, alinsunod sa mga palatandaan ng hindi pagkakapantay-pantay, pipiliin natin ang kalahating eroplano at makuha ang kanilang karaniwang bahagi - ang rehiyon ng mga tinatanggap na solusyon ng ODR - ang walang limitasyong polygon MNPQ.

Pinakamababang halaga ng function

tions – sa direktang NP, halimbawa

sa puntong P(4; 0)

Ф min = 4 + 0 = 4.

Ang ODR ay hindi limitado mula sa itaas, samakatuwid, Ф max = + ∞.

Pagpipilian 10. Hanapin ang maximum at minimum na mga halaga

linear function Ф = 2 x 1 - 3 x 2

may mga paghihigpit: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 ≤ 16;

x 2 ≤ 5;

x i ≥ 0, i = 1.2.

Sa pamamagitan ng kondisyong pagpapalit ng mga palatandaan ng hindi pagkakapantay-pantay ng mga palatandaan ng pagkakapantay-pantay, nakakakuha tayo ng isang sistema ng mga equation

x 1 + 3 x 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4).

Bumuo tayo ng mga tuwid na linya gamit ang mga equation na ito, pagkatapos, alinsunod sa mga palatandaan ng hindi pagkakapantay-pantay, piliin ang kalahating eroplano at makuha ang kanilang karaniwang bahagi - ang rehiyon ng mga tinatanggap na solusyon ng ODR - ang MNPQRS polygon.

Buuin natin ang vector Г(2; -3) at gumuhit sa pinagmulan ng mga coordinate linya ng antas– tuwid.

Inilipat namin ang linya ng antas sa direksyon, ang halaga ng Ф ay tumataas. Sa puntong S(7; 0) ang layunin ng function ay umabot sa pinakamataas na Ф max =2·7–3·0= = 14. Inilipat namin ang linya ng antas sa direksyon, bumababa ang halaga ng Ф. Ang pinakamababang halaga ng function ay nasa punto N(0; 5)

Ф min = 2·0 – 3·5 = –15.

GAWAIN 2.B. Paglutas ng problema sa linear programming

analytical simplex na pamamaraan

Pagpipilian 7. I-minimize ang layunin ng function Ф = x 1 - x 2 + x 3 + x 4 + x 5 - x 6

may mga paghihigpit: x 1 + x 4 +6 x 6 = 9,

3 x 1 + x 2 – 4 x 3 + 2 x 6 = 2,

x 1 + 2 x 3 + x 5 + 2 x 6 = 6.

Solusyon:

Bilang ng mga hindi alam n=6, bilang ng mga equation m=3. Samakatuwid, ang r = n-m = 3 hindi alam ay maaaring kunin bilang libre. Piliin natin ang x 1, x 3 at x 6.

Ipinapahayag namin ang mga pangunahing variable x 2 , x 4 at x 5 sa mga tuntunin ng mga libre at binabawasan ang system sa isang yunit na batayan

x 2 = 2 – 3 x 1 + 4 x 3 – 2 x 6

x 4 = 9 – x 1 – 6 x 6 (*)

x 5 = 6 – x 1 – 2 x 3 – 2 x 6

Ang layunin ng function ay magiging ganito:

Ф = x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 – x 1 – 6 x 6 +6 – x 1 – 2 x 3 – 2 x 6 – x 6 =

13 + 2 x 1 – 5 x 3 – 7 x 6

Ilagay natin ang x 1 = x 3 = x 6 = 0, at ang mga pangunahing variable ay kukuha ng mga halaga x 2 = 2; x 4 = 9; x 5 = 6, iyon ay, ang unang magagawa na solusyon (0; 2; 0; 9; 6; 0), layunin function Ф 1 = 13.

Ang mga variable na x 3 at x 6 ay kasama sa layunin na pag-andar na may mga negatibong coefficient, samakatuwid, habang tumataas ang kanilang mga halaga, ang halaga ng Ф ay bababa. Kunin natin ang x 6 bilang halimbawa. Mula sa 1st equation ng system (*) ay malinaw na ang pagtaas sa halaga ng x 6 ay posible hanggang sa x 6 = 1 (habang x 2 ³ 0). Sa kasong ito, ang x 1 at x 3 ay nananatiling katumbas ng zero. Ngayon kunin namin ang x 4, x 5, x 6 bilang mga pangunahing variable, at x 1, x 2, x 3 bilang mga libreng variable. Ipahayag natin ang mga bagong pangunahing variable sa mga tuntunin ng mga bagong libre. Nakukuha namin

x 6 = 1 – 3/2 x 1 – 1/2 x 2 + 2 x 3

x 4 = 3 + 8 x 1 + 3 x 2 – 12 x 3

x 5 = 4 + 2 x 1 + x 2 – 6 x 3

Ф = 6 + 25/2 x 1 + 7/2 x 2 – 19 x 3

Magtalaga tayo ng mga zero na halaga sa mga libreng variable, iyon ay, x 1 = x 2 = x 3 = 0, habang x 6 = 1, x 4 = 3, x 5 = 4, iyon ay, ang ikatlong magagawa na solusyon (0 0; 3; Sa kasong ito Ф 3 = 6.

Ang variable na x 3 ay kasama sa layunin ng function na may negatibong koepisyent, samakatuwid ang pagtaas ng x 3 na may kaugnayan sa zero na halaga ay hahantong sa pagbaba sa F. Mula sa 2nd equation ay malinaw na ang x 3 ay maaaring tumaas sa 1/4 , mula sa 3rd equation - hanggang 2/3 . Ang pangalawang equation ay mas kritikal. I-convert natin ang variable na x 3 sa bilang ng mga basic, at x 4 sa bilang ng mga libre.

Ngayon kunin namin ang x 1, x 2 at x 4 bilang mga bagong libreng variable. Ipahayag natin sa pamamagitan nila ang mga bagong pangunahing variable x 3, x 5, x 6. Kunin natin ang sistema

x 3 = 1/4 + 2/3 x 1 + 1/4 x 2 – 1/12 x 4

x 5 = 5/2 – 2 x 1 – 1/2 x 2 + 1/2 x 4

x 6 = 3/2 – 1/6 x 1 – 1/6 x 4

Ang layunin ng function ay kukuha ng form

Ф = 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

Ang mga variable na x 1 at x 2 ay kasama sa layunin ng function na may mga negatibong coefficient, samakatuwid, habang tumataas ang kanilang mga halaga, bababa ang halaga ng Ф. Kunin natin ang x 2 bilang halimbawa. Mula sa 2nd equation ng system ay malinaw na ang pagtaas sa halaga ng x 2 ay posible hanggang sa x 2 = 5 (habang x 5 ³ 0). Sa kasong ito, ang x 1 at x 4 ay nananatiling zero, ang mga halaga ng iba pang mga variable ay katumbas ng x 3 = 3/2; x 5 = 0, x 6 = 3/2, iyon ay, ang ikaapat na magagawang solusyon (0; 5; 3/2; 0; 0; 3/2). Sa kasong ito Ф 4 = 5/4.

Ngayon kunin namin ang x 1, x 4 at x 5 bilang mga bagong libreng variable. Ipahayag natin sa pamamagitan nila ang mga bagong pangunahing variable x 2, x 3, x 6. Kunin natin ang sistema

x 2 = 5 – 4 x 1 + x 4 – 2 x 5

x 3 = 3/2 – 1/3 x 1 + 1/6 x 4 – 1/2 x 5

x 6 = 3/2 – 1/6 x 1 – 1/6 x 4

Ang layunin ng function ay kukuha ng form

Ф = - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

Ang mga coefficient para sa parehong mga variable sa expression para sa Ф ay positibo, samakatuwid, ang isang karagdagang pagbaba sa halaga ng Ф ay imposible.

Iyon ay, ang pinakamababang halaga ng Ф min = - 5, ang huling magagawa na solusyon (0; 5; 3/2; 0; 0; 3/2) ay pinakamainam.

Pagpipilian 8. I-maximize ang layunin ng function na Ф = 4 x 5 + 2 x 6

may mga paghihigpit: x 1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 = 30;

x 3 + x 5 - 2 x 6 = 6;

2 x 4 + 3 x 5 - 2 x 6 = 18;

Solusyon:

Ang bilang ng mga equation ay 4, ang bilang ng mga hindi alam ay 6. Samakatuwid, ang r = n – m = 6 – 4 = 2 na mga variable ay maaaring mapili bilang mga libreng variable, 4 na mga variable bilang mga pangunahing. Pinipili namin ang x 5 at x 6 bilang mga libre, at x 1 , x 2 , x 3 , x 4 bilang mga basic. Ipahayag natin ang mga pangunahing variable sa mga tuntunin ng mga libre at bawasan ang sistema ng mga equation sa isang yunit na batayan

x 1 = 12 - x 5 - x 6 ;

x 2 = 30 - 5 x 5 + x 6 ;

x 3 = 6 - x 5 + 2 x 6 ;

x 4 = 9 - 3/2 x 5 + x 6 ;

Isinulat namin ang layunin ng function sa form na Ф = 4 x 5 + 2 x 6. Magtalaga tayo ng mga zero na halaga sa mga libreng variable x 5 = x 6 = 0. Sa kasong ito, ang mga pangunahing variable ay kukuha ng mga halaga x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9 , iyon ay, nakukuha namin ang unang magagawa na solusyon (12, 30, 6, 9, 0,) at Ф 1 = 0.

Ang parehong mga libreng variable ay pumapasok sa layunin na function na may positibong coefficient, iyon ay, ang isang karagdagang pagtaas sa F ay posible. Mula sa equation (1) ay malinaw na ang x 1 = 0 sa x 5 = 12, sa (2) ÷ (4) x 6 ay kasama sa positive coefficients. Lumipat tayo sa isang bagong batayan: mga pangunahing variable - x 6, x 2, x 3, x 4, libre - x 1, x 5. Ipahayag natin ang mga bagong pangunahing variable sa mga tuntunin ng bagong libre

x 6 = 12 - x 1 - x 5;

x 2 = 42 - x 1 - 6 x 5;

x 3 = 30 - 2 x 1 - 3 x 5 ;

x 4 = 21 - x 1 - 5/2 x 5 ;

Ang layunin ng function ay kukuha ng form Ф = 24 - 2 x 1 + 2 x 5 ;

Magtalaga tayo ng mga zero na halaga sa mga libreng variable x 1 = x 5 = 0. Sa kasong ito, ang mga pangunahing variable ay kukuha ng mga halaga x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21 , iyon ay, nakukuha namin ang pangalawang magagawa na solusyon (0, 42, 30, 21, 0, 12) at Ф 2 = 24.

Ang target na function na x 5 ay kasama sa isang positibong koepisyent, iyon ay, ang isang karagdagang pagtaas sa F ay posible na lumipat sa isang bagong batayan: mga pangunahing variable - x 6, x 5, x 3, x 4, libre - x 1. , x 2. Ipahayag natin ang mga bagong pangunahing variable sa pamamagitan ng bagong libre

x 6 = 5 - 5/6 x 1 + 1/6 x 2;

x 5 = 7 - 1/6 x 1 - 1/6 x 2 ;

x 3 = 9 - 3/2 x 1 + 1/2 x 2 ;

x 4 = 7/2 - 7/12 x 1 + 5/12 x 5 ;

Ang layunin ng function ay kukuha ng form Ф = 38 – 7/2 x 1 – 1/3 x 2 ;

Magtalaga tayo ng mga zero na halaga sa mga libreng variable x 1 = x 2 = 0. Sa kasong ito, ang mga pangunahing variable ay kukuha ng mga halaga x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7 /2, ibig sabihin, nakukuha natin ang ikatlong magagawang solusyon X 3 = (0, 0, 9, 7/2, 7, 5) at Ф 3 = 38.

Ang parehong mga variable ay pumapasok sa layunin na pag-andar na may mga negatibong coefficient, iyon ay, ang isang karagdagang pagtaas sa Ф ay imposible.

Samakatuwid, ang huling magagawa na solusyon ay pinakamainam, iyon ay, X opt = (0, 0, 9, 7/2, 7, 5) at Ф max = 38.

Pagpipilian 10. I-maximize ang layunin ng function na Ф = x 2 + x 3

may mga paghihigpit: x 1 - x 2 + x 3 = 1,

x 2 - 2 x 3 + x 4 = 2.

Solusyon:

Ang sistema ng mga equation-constraints ay pare-pareho, dahil ang mga ranggo ng matrix ng sistema ng mga equation at ang pinalawig na matrix ay pareho at katumbas ng 2. Dahil dito, ang dalawang variable ay maaaring kunin bilang libre, ang iba pang dalawang variable - basic - maaari ipahayag nang linear sa pamamagitan ng dalawang libre.

Kunin natin ang x 2 at x 3 bilang mga libreng variable

x 1 = 1 + x 2 - x 3 ; (*)

x 4 = 2 - x 2 + 2 x 3 ;

Ang layunin ng function ay naipahayag na sa mga tuntunin ng x 2 at x 3, iyon ay, Ф = x 2 + x 3.

Para sa x 2 =0 at x 3 =0, ang mga pangunahing variable ay magiging katumbas ng x 1 = 1, x 4 = 2.

Mayroon kaming unang magagawa na solusyon X 1 = (1, 0, 0, 2), na may Ф 1 = 0.

Ang pagtaas sa Ф ay posible sa pamamagitan ng pagtaas, halimbawa, ang halaga ng x 3, na kasama sa expression para sa Ф na may positibong koepisyent (x 2 ay nananatiling katumbas ng zero). Ang unang equation ng system (*) ay nagpapakita na ang x 3 ay maaaring tumaas sa 1 (mula sa kundisyon x 1 ³0), iyon ay, ang equation na ito ay nagpapataw ng limitasyon sa pagtaas ng halaga ng x 3. Ang unang equation ng system (*) ay nireresolba. Batay sa equation na ito, lumipat kami sa isang bagong batayan, pinapalitan ang x 1 at x 3. Ngayon ang mga pangunahing variable ay magiging x 3 at x 4, at ang mga libreng variable ay magiging x 1 at x 2. Ipahayag natin ngayon ang x 3 at x 4 sa mga tuntunin ng x 1 at x 2.

Nakukuha namin ang: x 3 = 1 - x 1 + x 2 ; (**)

x 4 = 4 - 2 x 1 + x 2 ;

Ф = x 2 + 1 - x 1 + x 2 = 1 - x 1 + 2 x 2

Ang equating ng mga libreng variable sa zero, nakuha namin ang pangalawang tinatanggap na pangunahing solusyon X 2 = (0; 0; 1; 4), kung saan Ф 2 = 1.

Ang pagtaas sa Ф ay posible sa pagtaas ng x2. Ang pagtaas sa x 2, kung ihahambing sa huling sistema ng mga equation (**), ay hindi limitado. Dahil dito, ang Ф ay kukuha ng mas malalaking positibong halaga, iyon ay, Ф max = + ¥.

Kaya, ang layunin ng function na Ф ay hindi limitado mula sa itaas, samakatuwid walang pinakamainam na solusyon.

GAWAIN 2.D. Gumawa ng problemang dalawahan sa ibinigay

ang orihinal na gawain.

Pagpipilian 7. I-maximize ang layunin ng function Ф = 2× x 1 - x 4

may mga paghihigpit: x 1 + x 2 = 20,

x 2 + 2× x 4 ≥ 5,

x 1 + x 2 + x 3 ≤ 8,

x i ≥ 0 (i = 1, 2, 3, 4)

Solusyon:

Dalhin natin ang sistema ng mga paghihigpit sa isang solong, halimbawa, canonical form, sa pamamagitan ng pagpapasok ng mga karagdagang variable sa 2nd at 3rd equation

x 1 + x 2 = 20,

x 2 + 2 × x 4 – x 5 = 5,

- x 1 + x 2 + x 3 + x 6 = 8.

Nakakuha kami ng isang asymmetric na problema ng uri 2. Ang dalawahang problema ay magiging ganito:

I-minimize ang layunin ng function F = 20 × y 1 + 5 × y2+8 × y 3

sa y 1 - y 3 ≥ 2,

y 1 + y 2 + y 3 ≥ 0,

y 3 ≥ 0,

2× y 2 ≥ 1,

Y2 ≥ 0,

y 3 ≥ 0.

Pagpipilian 8. I-maximize ang layunin ng function na Ф = x 2 - x 4 - 3× x 5

may mga paghihigpit: x 1 + 2× x 2 - x 4 + x 5 = 1,

— 4 × x 2 + x 3 + 2× x 4 - x 5 = 2,

3 × x 2 + x 5 + x 6 = 5,

x i ≥ 0, (i = 1, 6)

Solusyon:

Mayroon kaming isang paunang problema sa pag-maximize sa isang sistema ng mga hadlang sa anyo ng mga equation, iyon ay, ang isang pares ng dalawahang problema ay may isang asymmetric type 2 na uri, ang modelo ng matematika kung saan sa anyo ng matrix ay may anyo:

Orihinal na problema: Dalawahang problema:

F = C × X max F = B T × Y min

sa A × X = B sa AT × Y ≥ C T

Sa orihinal na problema, ang matrix-row ng mga coefficient para sa mga variable sa layunin ng function ay may form na C = (0; 1; 0; -1; -3; 0),

ang matrix-column ng mga libreng termino at ang matrix ng mga coefficient para sa mga variable sa sistema ng mga paghihigpit ay may anyo

B = 2, A = 0 - 4 1 2 -1 0

Hanapin natin ang transposed matrix ng mga coefficient, isang row matrix ng mga coefficient para sa mga variable sa layunin ng function at isang column matrix ng mga libreng termino

0 1 0 0 V T = (1; 2; 5)

A T = -1 2 0 C T = -1

Ang dalawahang problema ay isusulat sa sumusunod na anyo:

hanapin ang pinakamababang halaga ng layunin ng function F = y 1 + 2 × y2+5 × y 3

sa ilalim ng mga paghihigpit y 1 ≥ 0,

2× y 1 - 4 × y2+3 × y 3 ≥ 1,

- y 1 + 2 × y 2 ≥ -1,

y 1 - y 2 + y 3 ≥ -3,

Pagpipilian 10. I-minimize ang function na Ф = x 1 + x 2 + x 3

may mga paghihigpit: 3× x 1 + 9× x 2 + 7× x 3 ≥ 2,

6 × x 1 + 4 x 2 + 5× x 3 ≥ 3,

8 × x 1 + 2 x 2 + 4× x 3 ≥ 4,

Solusyon:

Mayroon kaming paunang problema sa pag-minimize sa isang sistema ng mga hadlang sa anyo ng mga hindi pagkakapantay-pantay, iyon ay, ang isang pares ng dalawahang problema ay may simetriko na anyo ng ika-3 uri, ang modelo ng matematika kung saan sa anyo ng matrix ay may anyo:

Orihinal na problema Dual problem

F = C × X min F = B T × Ymax

sa A × X ≥ B at A T × Y ≤ S T

X ≥ 0 Y ≥ 0

Sa orihinal na problema, ang matrix-row ng mga coefficient para sa mga variable sa layunin ng function, ang matrix-column ng mga libreng termino at ang matrix ng coefficients para sa mga variable sa sistema ng mga hadlang ay may anyo

C = (1; 1; 1), B = 3, A = 6 4 5

Hanapin natin ang mga matrice ng dual problem

B T = (2; 3; 4) C T = 3 A T = 9 4 2

Ang dalawahang problema ay nabuo bilang:

I-maximize ang layunin ng function F = 2y 1 + 3y 2 + 4y 3

sa ilalim ng mga paghihigpit 3 × y 1 + 6 × y2+8 × y 3 ≤ 1,

9× y 1 + 4 × y2+2 × y 3 ≤ 1,

7× y 1 + 5 × y2+4 × y 3 ≤ 1,

y i ≥ 0 (i = 1, 2, 3)

GAWAIN 2.C. Paglutas ng problema sa linear programming gamit ang mga simplex na talahanayan.

Pagpipilian 7. I-maximize ang layunin ng function Ф = 2 x 1 - x 2 + 3 x 3 + 2 x 4

may mga paghihigpit: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,

4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.

Solusyon:

Dalhin natin ang sistema ng mga paghihigpit sa canonical form

2 x 1 + 3 x 2 – x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 +3 x 3 + x 4 + z 3 = 8. (3)

Mayroon kaming sistema ng 3 equation na may 7 hindi alam. Pumili tayo ng 3 variable x 1 , z 1 , z 3 bilang mga basic, x 2 , x 3 , x 4 , z 2 bilang mga libre, at ipahayag ang mga pangunahing variable sa pamamagitan ng mga ito.

Mula sa (2) mayroon tayong x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6

Ipalit sa (1) at (3), nakukuha natin

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

Ф - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 = 2.

Gumawa tayo ng simplex table

Pag-ulit ng Talahanayan 1

Basic AC	Kalayaan. AC
x 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z 1	2	0	7	-11		1	2	0	1/ 4	1/8
z 3	4	0	18	-17	13	0	4	1	4/13	13/8
F	2	0	— 3	7	— 8	0	— 2	0		1

X 1 = (1; 0; 0; 0; 2; 0; 4) Ф 1 = 2.

II pag-ulit Talahanayan 2

x 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x 4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z 3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
F	4	0	4	— 4	0	1	0	0		32/7

X 2 = (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 = 4.

III pag-ulit Talahanayan 3

x 1	1	1	— 6	0	0		-1	— 1		1/2
x 4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
x 3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
F	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

X 3 = (1; 0; 6/7; 10/7; 0; 0; 0) F 3 = 52/7.

IV pag-ulit Talahanayan 4

z 1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x 4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
x 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
F	149/14	45/14	15	0	0	0	3/14	19/14

X 4 = (0; 0; 25/14; 37/14; 1/2; 0; 0) F 4 = 149/14.

Walang huling talahanayan sa hilera ng index mga negatibong numero, iyon ay, sa expression para sa layunin ng function lahat Г i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Sagot: Ф m ax = 149/14,

pinakamainam na solusyon (0; 0; 25/14; 37/14; 1/2; 0; 0)

Pagpipilian 8. I-minimize ang layunin function na Ф = 5 x 1 - x 3

sa ilalim ng mga paghihigpit: x 1 + x 2 + 2 x 3 - x 4 = 3,

x 2 + 2 x 4 =1,

Solusyon:

Ang bilang ng mga variable ay 4, ang ranggo ng matrix ay 2, samakatuwid ang bilang ng mga libreng variable ay r = 4 - 2 = 2, ang bilang ng mga pangunahing variable ay 2 din. Kunin natin ang x 3, x 4 bilang mga libreng variable, ipahayag ang mga pangunahing variable x 1, x 2 sa mga tuntunin ng libre at Bawasan natin ang system sa isang yunit na batayan:

x 2 = 1 - 2 x 4,

x 1 = 3 - x 2 - 2 x 3 + x 4 = 3 - 1 + 2 x 4 - 2 x 3 + x 4 = 2 - 2 x 3 + 3 x 4

Ф = 5 x 1 - x 3 = 5 (2 - 2 x 3 + 3 x 4) - x 3 = 10 - 10 x 3 + 15 x 4 - x 3 = 10 - 11 x 3 + 15 x 4

Isulat natin ang sistema ng mga equation at ang layunin ng function sa isang form na maginhawa para sa simplex table, iyon ay, x 2 + 2 x 4 = 1,

x 1 +2 x 3 - 3 x 4 = 2

F + 11 x 3 - 15 x 4 = 10

Gawa tayo ng table

Pag-ulit ng Talahanayan 1

Basic AC	Kalayaan. AC
X 1	2	1	0		— 3		1/2
X 2	1	0	1	0	2
F	10	0	0	11	— 15		— 11/2

X 1 = (2; 1; 0; 0) Ф 1 = 10.

II pag-ulit Talahanayan 2

X 3	1	1/2	0	1	-3/2		3/4
X 2	1	0	1	0			1/2
F	— 1	— 11/2	0	0	3/2		— 3/4

X 2 = (0; 1; 1; 0) Ф 2 = -1.

III pag-ulit Talahanayan 3

X 3	7/4	1/2	3/4	1	0
X 4	1/2	0	1/2	0	1
F	— 7/4	— 11/2	— 3/4	0	0

X 3 = (0; 0; 7/4; 1/2) F 3 = -7/4.

Walang mga positibong numero sa hilera ng index ng huling talahanayan, iyon ay, sa expression para sa layunin ng function lahat Г i > 0. Mayroon kaming case I, samakatuwid, ang huling pangunahing solusyon ay pinakamainam.

Sagot: Ф min = -7/4, pinakamainam na solusyon (0; 0; 7/4; 1/2)

********************

Pagpipilian 10. I-minimize ang layunin ng function Ф = x 1 + x 2,

sa ilalim ng mga paghihigpit: x 1 –2 x 3 + x 4 = 2,

x 2 – x 3 + 2 x 4 = 1,

Solusyon:

Ang bilang ng mga variable ay 5, ang ranggo ng matrix ay 3, samakatuwid ang bilang ng mga libreng variable ay r = 6-3 = 2. Kunin natin ang x 3 at x 4 bilang mga libreng variable, at x 1 , x 2 , x 5 bilang mga pangunahing. Ang lahat ng mga equation ng system ay nabawasan na sa isang unit basis (ang mga pangunahing variable ay ipinahayag sa mga tuntunin ng mga libre), ngunit nakasulat sa isang form na hindi maginhawa para sa paggamit ng mga simplex na talahanayan. Isulat natin ang sistema ng mga equation sa anyo

x 1 - 2 x 3 + x 4 = 2

x 2 - x 3 +2 x 4 = 1

x 5 + x 3 – x 4 . = 5

Ipinapahayag namin ang layunin ng function sa mga tuntunin ng mga libreng variable at isulat ito sa form na Ф - 3 x 3 +3 x 4 = 3

Gawa tayo ng table

Pag-ulit ng Talahanayan 1

Basic AC	Kalayaan. AC
x 1	2	1	0	-2	1	0	2	-1/2
x 2	1	0	1	-1		0	1/2	1/2
x 5	5	0	0	1	-1	1		1/2
F	3	0	0	-3	3	0		-3/2

X 1 = (2; 3; 0; 0; 5) F 1 = 3.

talahanayan 2

x 1	3/2	1	-1/2	-3/2	0	0
x 4	1/2	0	1/2	-1/2	1	0
x 5	11/2	0	1/2	1/2	0	1
F	3/2	0	-3/2	-3/2	0	0

X 2 = (3/2; 0; 0; 1/2; 11/2) F 2 = 3/2.

Walang mga positibong numero sa hilera ng index ng huling talahanayan, iyon ay, sa expression para sa layunin ng function lahat Gi > 0. Mayroon kaming kaso 1, samakatuwid, ang huling pangunahing solusyon ay pinakamainam.

Sagot: Ф min = 3/2, pinakamainam na solusyon (3/2; 0; 0; 1/2; 11/2).

Pederal na Ahensya para sa Edukasyon

Badyet ng estado institusyong pang-edukasyon

mas mataas bokasyonal na edukasyon

"Omsk State Technical University"

PAGKUKULALA AT GRAPHIC WORK

sa pamamagitan ng disiplina"OPTIMAL CONTROL THEORY »

Naaayon sa paksa "MGA PARAAN NG OPTIMISATION AT PANANALIKSIK SA OPERASYON »

opsyon 7

Nakumpleto:

mag-aaral ng sulat

4th year group na ZA-419

Buong pangalan: Kuzhelev S. A.

Sinuri:

Devyaterikova M.V.

Omsk - 2012
^

Gawain 1. Graphical na pamamaraan para sa paglutas ng mga problema sa linear programming.

7) 7x 1 + 6x 2 → max 20x 1 + 6x 2 ≤ 15 16x 1 − 2x 2 ≤ 18 8x 1 + 4x 2 ≤ 20 13x 1 + 3x 2 ≤ 4 x 1 , x 2 ≥ 0.

Hakbang 1: Pagbuo ng Magagawang Rehiyon

Ang mga kondisyon para sa hindi negatibong mga variable at parisukat ay naglilimita sa saklaw ng kanilang mga pinahihintulutang halaga sa unang kuwadrante. Ang bawat isa sa natitirang apat na hindi pagkakapantay-pantay na mga hadlang ng modelo ay tumutugma sa isang tiyak na kalahating eroplano. Ang intersection ng mga kalahating eroplano na ito sa unang kuwadrante ay bumubuo ng hanay ng mga magagawang solusyon sa problema.

Ang unang hadlang ng modelo ay may anyo . Ang pagpapalit ng ≤ sign sa loob nito ng = sign, makuha namin ang equation . Sa Fig. 1.1 ito ay tumutukoy sa isang tuwid na linya (1), na naghahati sa eroplano sa dalawang kalahating eroplano, sa sa kasong ito sa itaas at sa ibaba ng linya. Upang piliin kung alin ang makakatugon sa hindi pagkakapantay-pantay , palitan dito ang mga coordinate ng anumang punto na hindi nakahiga sa isang naibigay na linya (halimbawa, ang pinagmulan X 1 = 0, X 2 = 0). Dahil nakuha namin ang tamang expression (20 0 + 6 0 = 0 ≤15), kung gayon ang kalahating eroplano na naglalaman ng pinagmulan ng mga coordinate (minarkahan ng isang arrow) ay nakakatugon sa hindi pagkakapantay-pantay. Kung hindi, isa pang kalahating eroplano.

Nagpapatuloy kami nang katulad sa natitirang mga hadlang ng problema. Ang intersection ng lahat ng constructed half-planes na may unang quadrant forms A B C D(tingnan ang Fig. 1). Ito ang posibleng lugar ng problema.

Hakbang 2. Pagguhit ng level line Level line Ang layunin ng function ay ang hanay ng mga punto sa eroplano kung saan ang layunin ng function ay tumatagal ng isang pare-parehong halaga. Ang nasabing set ay ibinibigay ng equation f ( x) = const. Ilagay natin, halimbawa, const = 0 at gumuhit ng linya sa antas f ( x) = 0, ibig sabihin. sa aming kaso tuwid na linya 7 x 1 + 6x 2 = 0.

Ang linyang ito ay dumadaan sa pinanggalingan at patayo sa vector. Ang vector na ito ay ang gradient ng layunin ng function sa punto (0,0). Ang gradient ng isang function ay isang vector ng mga halaga ng mga partial derivatives ng isang naibigay na function sa puntong pinag-uusapan. Sa kaso ng problema sa LP, ang mga partial derivatives ng layunin na function ay katumbas ng coefficients Cako, j = 1 , ..., n.

Ipinapakita ng gradient ang direksyon ng pinakamabilis na paglaki ng function. Paglipat ng linya ng antas ng layunin ng function f ( x) = const. patayo sa direksyon ng gradient, makikita natin ang huling punto kung saan ito nagsa-intersect sa rehiyon. Sa aming kaso, ito ang punto D, na magiging pinakamataas na punto ng layunin ng function (tingnan ang Fig. 2)

Ito ay nasa intersection ng mga linya (2) at (3) (tingnan ang Fig. 1) at tinutukoy ang pinakamainam na solusyon.

^ Tandaan na kung nais mong mahanap ang pinakamababang halaga ng layunin ng function, ang linya ng antas ay inilipat sa direksyon na kabaligtaran sa direksyon ng gradient.

^ Hakbang 3. Pagtukoy sa mga coordinate ng maximum (minimum) point at ang pinakamainam na halaga ng layunin ng function

Upang mahanap ang mga coordinate ng point C, kinakailangan upang malutas ang isang sistema na binubuo ng mga equation na naaayon sa mga tuwid na linya (sa kasong ito, equation 2 at 3):

16x 1 − 2x 2 ≤ 18

8x 1 + 4x 2 ≤ 20

Nakukuha namin ang pinakamainam na solusyon = 1.33.

^ Pinakamainam na halaga layunin function f * = f (X*) = 7 * 0 + 6 * 1,33 = 7,8

KONTROL ANG GAWAIN SA DISIPLINA:

"MGA PARAAN NG MGA OPTIMAL NA SOLUSYON"

Opsyon Blg. 8

1. Lutasin ang isang linear na problema sa programming sa graphical na paraan. Hanapin ang maximum at minimum ng function na may ibinigay na mga paghihigpit:

,

.

Solusyon

Ito ay kinakailangan upang mahanap ang pinakamababang halaga ng layunin ng pag-andar at ang maximum, sa ilalim ng sistema ng mga paghihigpit:

9x 1 +3x 2 ≥30, (1)

X 1 +x 2 ≤4, (2)

x 1 +x 2 ≤8, (3)

Bumuo tayo ng rehiyon ng mga magagawang solusyon, i.e. Solusyonan natin ang sistema ng mga hindi pagkakapantay-pantay nang grapiko. Upang gawin ito, itinatayo namin ang bawat tuwid na linya at tukuyin ang kalahating eroplano na tinukoy ng mga hindi pagkakapantay-pantay (ang kalahating eroplano ay ipinahiwatig ng isang prime).

Ang intersection ng mga kalahating eroplano ay magiging isang rehiyon na ang mga coordinate ng punto ay nakakatugon sa mga hindi pagkakapantay-pantay ng sistema ng mga hadlang ng problema. Tukuyin natin ang mga hangganan ng lugar ng polygon ng solusyon.

Bumuo tayo ng isang tuwid na linya na tumutugma sa halaga ng function F = 0: F = 2x 1 +3x 2 = 0. Ang gradient vector, na binubuo ng mga coefficient ng layunin function, ay nagpapahiwatig ng direksyon ng minimization ng F(X). Ang simula ng vector ay point (0; 0), ang dulo ay point (2; 3). Ililipat namin ang tuwid na linyang ito sa parallel na paraan. Dahil kami ay interesado sa minimal na solusyon, samakatuwid ay inililipat namin ang tuwid na linya hanggang sa una itong mahawakan ang itinalagang lugar. Sa graph, ang tuwid na linyang ito ay ipinapahiwatig ng isang tuldok na linya.

Diretso
nag-intersect sa rehiyon sa punto C. Dahil nakuha ang point C bilang resulta ng intersection ng mga linya (4) at (1), ang mga coordinate nito ay nakakatugon sa mga equation ng mga linyang ito:
.

Nang malutas ang sistema ng mga equation, nakukuha natin ang: x 1 = 3.3333, x 2 = 0.

Paano natin mahahanap ang pinakamababang halaga ng layunin ng function: .

Isaalang-alang natin ang layunin ng pag-andar ng problema.

Bumuo tayo ng isang tuwid na linya na tumutugma sa halaga ng function F = 0: F = 2x 1 +3x 2 = 0. Ang gradient vector, na binubuo ng mga coefficient ng layunin function, ay nagpapahiwatig ng direksyon ng pag-maximize ng F(X). Ang simula ng vector ay point (0; 0), ang dulo ay point (2; 3). Ililipat namin ang tuwid na linyang ito sa parallel na paraan. Dahil interesado kami sa maximum na solusyon, samakatuwid ay inililipat namin ang tuwid na linya hanggang sa huling pagpindot sa itinalagang lugar. Sa graph, ang tuwid na linyang ito ay ipinapahiwatig ng isang tuldok na linya.

Diretso
nag-intersect sa rehiyon sa punto B. Dahil nakuha ang punto B bilang resulta ng intersection ng mga linya (2) at (3), ang mga coordinate nito ay nakakatugon sa mga equation ng mga linyang ito:

.

Paano natin mahahanap ang pinakamataas na halaga ng layunin ng function: .

Sagot:
At
.

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

.

Solusyon

Lutasin natin ang isang direktang linear programming problem gamit ang simplex method, gamit ang simplex table.

Tukuyin natin ang pinakamababang halaga ng layunin ng function
sa ilalim ng mga sumusunod na kondisyon at paghihigpit:
.

Upang makabuo ng unang reference na plano, binabawasan namin ang sistema ng mga hindi pagkakapantay-pantay sa isang sistema ng mga equation sa pamamagitan ng pagpapakilala ng mga karagdagang variable.

Sa unang hindi pagkakapantay-pantay ng kahulugan (≥) ipinakilala namin ang pangunahing variable x 3 may minus sign. Sa ika-2 hindi pagkakapantay-pantay ng kahulugan (≤) ipinakilala namin ang pangunahing variable x 4 . Sa ika-3 hindi pagkakapantay-pantay ng kahulugan (≤) ipinakilala namin ang pangunahing variable x 5 .

Ipakilala natin ang mga artipisyal na variable : sa unang pagkakapantay-pantay ay ipinakilala namin ang isang variable x 6 ;

Upang itakda ang problema sa pinakamababa, isinusulat namin ang layunin ng function bilang mga sumusunod: .

Para sa paggamit ng mga artipisyal na variable na ipinakilala sa layunin ng pag-andar, isang tinatawag na parusa ng M ang ipinapataw, isang napakalaking positibong numero na karaniwang hindi tinukoy.

Ang resultang batayan ay tinatawag na artipisyal, at ang paraan ng solusyon ay tinatawag na paraan ng artipisyal na batayan.

Bukod dito, ang mga artipisyal na variable ay hindi nauugnay sa nilalaman ng problema, ngunit pinapayagan nila ang isa na bumuo ng isang panimulang punto, at pinipilit ng proseso ng pag-optimize ang mga variable na ito na kumuha ng mga zero na halaga at matiyak ang pagiging matanggap ng pinakamainam na solusyon.

Mula sa mga equation ay nagpapahayag kami ng mga artipisyal na variable: x 6 = 4-x 1 -x 2 +x 3, na pinapalitan namin sa layunin ng function: o.

Coefficient matrix
Ang sistemang ito ng mga equation ay may anyo:
.

Lutasin natin ang sistema ng mga equation para sa mga pangunahing variable: x 6 , x 4 , x 5.

Ipagpalagay na ang mga libreng variable ay katumbas ng 0, nakuha namin ang una sangguniang plano:

X1 = (0,0,0,2,10,4)

Ang isang pangunahing solusyon ay tinatawag na tinatanggap kung ito ay hindi negatibo.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Ang kasalukuyang reference plan ay hindi optimal dahil may mga positive coefficient sa index line. Bilang nangungunang column, pipiliin natin ang column na tumutugma sa variable x 2, dahil ito ang pinakamalaking coefficient. Kalkulahin natin ang mga halaga D i at mula sa kanila pipiliin namin ang pinakamaliit: min(4: 1, 2: 2, 10: 2) = 1.

Samakatuwid, ang 2nd line ang nangunguna.

Ang elemento ng paglutas ay katumbas ng (2) at matatagpuan sa intersection ng nangungunang column at ng nangungunang hilera.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Binubuo namin ang susunod na bahagi ng simplex table. Sa halip na variable x 4, isasama sa plan 1 ang variable x 2.

Ang row na tumutugma sa variable x 2 sa plan 1 ay nakukuha sa pamamagitan ng paghahati sa lahat ng elemento ng row x 4 ng plan 0 ng resolving element RE = 2. Sa lugar ng elemento ng paglutas ay nakakakuha tayo ng 1. Sa natitirang mga cell ng x 2 column ay nagsusulat tayo ng mga zero.

Kaya, sa bagong plano 1, napuno ang row x 2 at column x 2. Ang lahat ng iba pang elemento ng bagong plano 1, kabilang ang mga elemento ng index row, ay tinutukoy ng parihaba na panuntunan.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 2
x 5
		1 1/2 +1 1/2 M

Ang kasalukuyang reference plan ay hindi optimal dahil may mga positive coefficient sa index row. Bilang nangungunang column, pipiliin namin ang column na tumutugma sa variable x 1, dahil ito ang pinakamalaking coefficient. Kalkulahin natin ang mga halaga D i sa pamamagitan ng hilera bilang isang quotient ng dibisyon: at mula sa kanila pinipili namin ang pinakamaliit: min (3: 1 1 / 2, -, 8: 2) = 2.

Samakatuwid, ang unang linya ay ang nangunguna.

Ang elemento ng paglutas ay katumbas ng (1 1/2) at matatagpuan sa intersection ng nangungunang column at ng nangungunang hilera.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6		1 1 / 2
x 2
x 5
		-1 1 / 2 +1 1 / 2 M

Binubuo namin ang susunod na bahagi ng simplex table. Sa halip na variable x 6, isasama sa plan 2 ang variable x 1.

Kumuha kami ng bagong simplex table:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Walang mga positibong halaga sa mga halaga ng index string. Samakatuwid, tinutukoy ng talahanayang ito ang pinakamainam na plano para sa problema.

Ang huling bersyon ng simplex table:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Dahil walang mga artipisyal na variable sa pinakamainam na solusyon (ang mga ito ay katumbas ng zero), ang solusyon na ito ay tinatanggap.

Ang pinakamainam na plano ay maaaring isulat tulad ng sumusunod: x 1 = 2, x 2 = 2:.

Sagot:
,
.

3. Ang kumpanyang Three Fat Men ay naghahatid ng de-latang karne mula sa tatlong bodega na matatagpuan sa iba't ibang bahagi ng lungsod hanggang sa tatlong tindahan. Ang mga stock ng de-latang pagkain na makukuha sa mga bodega, pati na rin ang dami ng mga order sa tindahan at mga rate ng paghahatid (sa mga karaniwang yunit ng pananalapi) ay ipinakita sa talahanayan ng transportasyon.

Maghanap ng plano sa transportasyon na nagbibigay ng pinakamababang gastos sa pananalapi (gawin ang paunang plano sa transportasyon gamit ang paraan ng "northwest corner").

Solusyon

Suriin natin ang kinakailangan at sapat na kondisyon para sa pagkalutas ng problema:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Ang kondisyon ng balanse ay natutugunan. Nagbibigay ng pantay na pangangailangan. Samakatuwid, ang modelo ng problema sa transportasyon ay sarado.

Ipasok natin ang paunang data sa talahanayan ng pamamahagi.

Pangangailangan

Gamit ang paraan ng kanto sa hilagang-kanluran, bubuo kami ng unang sangguniang plano ng problema sa transportasyon.

Nagsisimulang punan ang plano mula sa kaliwang sulok sa itaas.

Ang kinakailangang elemento ay 4. Para sa elementong ito, ang mga imbentaryo ay 300, ang mga kinakailangan ay 250. Dahil ang minimum ay 250, ibinabawas namin ito: .

			300 - 250 = 50
250 - 250 = 0

Ang kinakailangang elemento ay katumbas ng 2. Para sa elementong ito, ang mga imbentaryo ay 50, ang mga kinakailangan ay 400. Dahil ang minimum ay 50, ibinabawas namin ito: .

			50 - 50 = 0
	400 - 50 = 350

Ang kinakailangang elemento ay 5. Para sa elementong ito, ang mga imbentaryo ay 300, ang mga kinakailangan ay 350. Dahil ang minimum ay 300, ibinabawas namin ito:

			300 - 300 = 0
	350 - 300 = 50

Ang elementong hinahanap mo ay 3. Para sa elementong ito, ang mga imbentaryo ay 200, ang mga kinakailangan ay 50. Dahil ang minimum ay 50, binabawasan namin ito:

			200 - 50 = 150
	50 - 50 = 0

Ang kinakailangang elemento ay 6. Para sa elementong ito, ang mga imbentaryo ay 150, ang mga kinakailangan ay 150. Dahil ang minimum ay 150, ibinabawas namin ito:

			150 - 150 = 0
		150 - 150 = 0

Pangangailangan

Panimula

Ang kasalukuyang yugto ng pag-unlad ng tao ay nakikilala sa pamamagitan ng katotohanan na ang edad ng enerhiya ay pinapalitan ng edad ng computer science. Mayroong masinsinang pagpapakilala ng mga bagong teknolohiya sa lahat ng larangan ng aktibidad ng tao. Mayroong isang tunay na problema ng paglipat sa isang lipunan ng impormasyon, kung saan ang pag-unlad ng edukasyon ay dapat maging isang priyoridad. Nagbabago rin ang istruktura ng kaalaman sa lipunan. Lalong nagiging mahalaga para sa praktikal na buhay makakuha ng pangunahing kaalaman na nakakatulong sa malikhaing pag-unlad ng indibidwal. Mahalaga rin ang constructiveness ng nakuhang kaalaman at ang kakayahang buuin ito alinsunod sa layunin. Batay sa kaalaman, nabubuo ang mga bago mapagkukunan ng impormasyon lipunan. Ang pagbuo at pagkuha ng bagong kaalaman ay dapat na nakabatay sa isang mahigpit na pamamaraan ng isang diskarte sa sistema, kung saan ang diskarte ng modelo ay sumasakop sa isang espesyal na lugar. Ang mga posibilidad ng diskarte sa modelo ay lubos na magkakaibang, kapwa sa mga tuntunin ng mga pormal na modelo na ginamit at sa mga pamamaraan ng pagpapatupad ng mga pamamaraan ng pagmomodelo. Ang pisikal na pagmomodelo ay nagpapahintulot sa isa na makakuha ng maaasahang mga resulta para sa medyo simpleng mga sistema.

Sa kasalukuyan, imposibleng pangalanan ang isang lugar ng aktibidad ng tao kung saan ang mga pamamaraan ng pagmomolde ay hindi gagamitin sa isang antas o iba pa. Ito ay totoo lalo na sa larangan ng pamamahala iba't ibang sistema, kung saan ang mga pangunahing proseso ay ang paggawa ng desisyon batay sa impormasyong natanggap.

1. Paglalahad ng suliranin

pinakamababang layunin ng pag-andar

Lutasin ang problema sa paghahanap ng pinakamaliit na layunin ng function para sa sistema ng mga hadlang na tinukoy ng solusyon polygon alinsunod sa opsyon No. 16 ng gawain. Ang solusyon polygon ay ipinapakita sa Figure 1:

Figure 1 - Polygon ng mga solusyon sa problema

Ang sistema ng mga hadlang at ang layunin ng pag-andar ng problema ay ipinakita sa ibaba:

Ito ay kinakailangan upang malutas ang problema gamit ang mga sumusunod na pamamaraan:

Graphical na paraan para sa paglutas ng mga problema sa LP;

Algebraic na pamamaraan para sa paglutas ng mga problema sa LP;

Simplex na paraan para sa paglutas ng mga problema sa LP;

Paraan para sa paghahanap ng tinatanggap na solusyon sa mga problema sa LP;

Solusyon sa dual LP na problema;

Paraan ng branch at bound para sa paglutas ng mga problema sa integer LP;

Pamamaraan ng Gomori para sa paglutas ng mga problema sa integer LP;

Paraan ng Balaz para sa paglutas ng mga problema sa Boolean LP.

Ihambing ang mga resulta ng solusyon iba't ibang pamamaraan gumawa ng angkop na konklusyon mula sa gawain.

2. Graphical na solusyon sa linear programming problem

Ang graphical na paraan para sa paglutas ng mga problema sa linear programming ay ginagamit sa mga kaso kung saan ang bilang ng mga hindi alam ay hindi lalampas sa tatlo. Maginhawa para sa husay na pananaliksik ng mga katangian ng mga solusyon at ginagamit kasabay ng iba pang mga pamamaraan (algebraic, branch at bound, atbp.). Ang ideya ng pamamaraan ay batay sa graphical na solusyon ng isang sistema ng mga linear na hindi pagkakapantay-pantay.

kanin. 2 Graphical na solusyon ng problema sa LP

Pinakamababang punto

Equation ng isang linya na dumadaan sa dalawang puntos na A1 at A2:

AB: (0;1); (3;3)

VS: (3;3); (4;1)

CD: (4;1); (3;0)

EA: (1;0); (0;1)

CF: (0;1); (5;2)

na may mga paghihigpit:

Paglutas ng linear programming problem gamit ang algebraic simplex method

Ang aplikasyon ng isang algebraic na pamamaraan para sa paglutas ng isang problema ay nangangailangan ng isang paglalahat ng representasyon ng problema sa LP. Ang orihinal na sistema ng mga paghihigpit, na tinukoy sa anyo ng mga hindi pagkakapantay-pantay, ay na-convert sa isang karaniwang notasyon kapag ang mga paghihigpit ay tinukoy sa anyo ng mga pagkakapantay-pantay. Pagbabago ng sistema ng pagpilit sa karaniwang view kasama ang mga sumusunod na hakbang:

Ibahin ang anyo ng mga hindi pagkakapantay-pantay upang mayroong mga variable at libreng termino sa kaliwa, at 0 sa kanan, i.e. sa kaliwang bahagi ay mas malaki sa o katumbas ng zero;

Ipakilala ang mga karagdagang variable, ang bilang nito ay katumbas ng bilang ng mga hindi pagkakapantay-pantay sa sistema ng mga hadlang;

Sa pamamagitan ng pagpapakilala ng mga karagdagang paghihigpit sa hindi negatibiti ng mga idinagdag na variable, palitan ang mga palatandaan ng hindi pagkakapantay-pantay ng mahigpit na mga palatandaan ng pagkakapantay-pantay.

Kapag nilulutas ang isang problema sa LP gamit ang algebraic na pamamaraan, ang isang kundisyon ay idinagdag: ang layunin ng function ay dapat na may pinakamababa. Kung ganitong kondisyon ay hindi nasiyahan, ito ay kinakailangan upang ibahin ang anyo ang layunin function na naaayon (multiply sa -1) at lutasin ang minimization problema. Matapos mahanap ang solusyon, palitan ang mga halaga ng mga variable sa orihinal na function at kalkulahin ang halaga nito.

Ang solusyon sa isang problema gamit ang algebraic na pamamaraan ay itinuturing na pinakamainam kapag ang mga halaga ng lahat ng mga pangunahing variable ay hindi negatibo, at ang mga koepisyent ng mga libreng variable sa layunin na equation ng function ay hindi rin negatibo. Kung ang mga kundisyong ito ay hindi natutugunan, kinakailangan na baguhin ang sistema ng mga hindi pagkakapantay-pantay, na nagpapahayag ng ilang mga variable sa mga tuntunin ng iba (pagbabago ng libre at pangunahing mga variable) upang makamit ang katuparan ng mga paghihigpit sa itaas. Ang halaga ng lahat ng mga libreng variable ay itinuturing na katumbas ng zero.

Ang algebraic na paraan para sa paglutas ng mga problema sa linear programming ay isa sa pinaka mabisang pamamaraan kapag manu-mano ang paglutas ng maliliit na problema dahil hindi nangangailangan ng malaking bilang ng mga kalkulasyon ng aritmetika. Ang pagpapatupad ng makina ng pamamaraang ito ay mas kumplikado kaysa, halimbawa, para sa simplex na paraan, dahil Ang algorithm ng solusyon na gumagamit ng algebraic na pamamaraan ay sa ilang lawak ay heuristic at ang bisa ng solusyon ay higit na nakasalalay sa personal na karanasan.

Libreng variable

St. lane - karagdagang kit

Ang mga kondisyon na hindi negatibo ay natutugunan, samakatuwid, ang pinakamainam na solusyon ay natagpuan.

3. Paglutas ng linear programming problem gamit ang simplex table

Solusyon: Dalhin natin ang problema sa isang karaniwang form para sa solusyon gamit ang isang simplex table.

Bawasan natin ang lahat ng equation ng system sa anyo:

Bumubuo kami ng isang simplex na talahanayan:

Sa itaas na sulok ng bawat cell ng talahanayan ipinasok namin ang mga coefficient mula sa sistema ng mga equation;

Pinipili namin ang maximum na positibong elemento sa row F, maliban na ito ang magiging pangkalahatang column;

Upang mahanap ang pangkalahatang elemento, bumuo kami ng isang relasyon para sa lahat ng positibo. 3/3; 9/1;- pinakamababang ratio sa linya x3. Samakatuwid - ang pangkalahatang string at =3 - ang pangkalahatang elemento.

Nahanap namin ang =1/=1/3. Dinadala namin ito sa ibabang sulok ng cell kung saan matatagpuan ang pangkalahatang elemento;

Sa lahat ng walang laman na mas mababang sulok ng pangkalahatang linya ipinapasok namin ang produkto ng halaga sa itaas na sulok ng cell sa pamamagitan ng;

Piliin ang itaas na sulok ng pangkalahatang linya;

Sa lahat ng mas mababang sulok ng pangkalahatang hanay ipinapasok namin ang produkto ng halaga sa itaas na sulok sa pamamagitan ng - at piliin ang mga resultang halaga;

Ang natitirang mga cell ng talahanayan ay napunan bilang mga produkto ng kaukulang mga napiling elemento;

Pagkatapos ay bumuo kami ng isang bagong talahanayan kung saan ang mga pagtatalaga ng mga cell ng mga elemento ng pangkalahatang haligi at hilera ay pinapalitan (x2 at x3);

Ang mga halaga na dati ay nasa ibabang sulok ay nakasulat sa itaas na sulok ng dating pangkalahatang hilera at haligi;

Ang kabuuan ng mga halaga ng itaas at ibabang sulok ng mga cell na ito sa nakaraang talahanayan ay nakasulat sa itaas na sulok ng natitirang mga cell

4. Paglutas ng problema sa linear programming sa pamamagitan ng paghahanap ng katanggap-tanggap na solusyon

Hayaang magbigay ng isang sistema ng mga linear algebraic equation:

Maaari nating ipagpalagay na ang lahat ay, kung hindi, i-multiply natin ang katumbas na equation sa -1.

Ipinakilala namin ang mga auxiliary variable:

Ipinakilala din namin ang isang pantulong na function

I-minimize namin ang system sa ilalim ng mga paghihigpit (2) at kundisyon.

PANUNTUNAN PARA SA PAGHAHANAP NG PINAPAYAGANG SOLUSYON: Upang makahanap ng katanggap-tanggap na solusyon sa system (1), pinapaliit namin ang form (3) sa ilalim ng mga paghihigpit (2), ang pagkuha ng xj bilang mga libreng hindi alam, at ang pagkuha ng xj bilang mga batayan.

Kapag nilulutas ang isang problema gamit ang simplex na pamamaraan, maaaring lumitaw ang dalawang kaso:

min f=0, kung gayon ang lahat ng i ay dapat na katumbas ng zero. At ang mga resultang halaga ng xj ay bubuo ng isang katanggap-tanggap na solusyon sa system (1).

min f>0, ibig sabihin. ang orihinal na sistema ay walang magagawang solusyon.

Source system:

Ginagamit ang kondisyon ng suliranin mula sa nakaraang paksa.

Ipakilala natin ang mga karagdagang variable:

Ang isang tinatanggap na solusyon sa orihinal na problema ay natagpuan: x1 = 3, x2 = 3, F = -12. Batay sa nakuhang feasible solution, makikita natin ang pinakamainam na solusyon sa orihinal na problema gamit ang simplex method. Upang gawin ito, bubuo kami ng isang bagong simplex na talahanayan mula sa talahanayan na nakuha sa itaas, aalisin ang hilera at ang hilera na may target na function ng auxiliary na problema:

Pagsusuri sa itinayong simplex na talahanayan, nakita namin na ang pinakamainam na solusyon para sa orihinal na problema ay natagpuan na (ang mga elemento sa hilera na naaayon sa layunin ng pag-andar ay negatibo). Kaya, ang magagawang solusyon na natagpuan kapag nilulutas ang pantulong na problema ay tumutugma sa pinakamainam na solusyon sa orihinal na problema:

6. Dual linear programming problema

Ang orihinal na sistema ng mga hadlang at ang layunin ng pag-andar ng problema ay ipinapakita sa figure sa ibaba.

na may mga paghihigpit:

Solusyon: Dalhin natin ang sistema ng mga paghihigpit sa karaniwang anyo:

Ang problemang dalawahan sa isang ito ay magkakaroon ng form:

Ang solusyon sa dalawahang problema ay isasagawa gamit ang isang simpleng paraan ng simplex.

Ibahin natin ang layunin ng function upang malutas ang problema sa minimization, at isulat ang sistema ng mga hadlang sa karaniwang anyo para sa paglutas gamit ang simplex na paraan.

y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??min

Bumuo tayo ng isang paunang simplex na talahanayan para sa paglutas ng problema sa dalawahang LP.

Ikalawang hakbang ng simplex method

Kaya, sa ikatlong hakbang ng simplex na paraan, ang pinakamainam na solusyon sa problema sa minimization ay natagpuan sa mga sumusunod na resulta: y2 = -7 /8, y1 = -11/8, Ф = 12. Upang mahanap ang halaga ng ang layunin ng pag-andar ng dalawahang problema, pinapalitan namin ang mga nahanap na halaga ng pangunahing at libreng mga variable sa pag-andar ng pag-maximize:

Фmax = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12

Dahil ang halaga ng layunin ng pag-andar ng direkta at dalawahang problema ay nagtutugma, ang solusyon sa direktang problema ay matatagpuan at katumbas ng 12.

Fmin = Фmax = -12

7. Paglutas ng problema sa integer linear programming gamit ang branch-and-bound na paraan

Ibahin natin ang orihinal na problema sa paraang hindi nasiyahan ang kundisyon ng integer kapag nalutas gamit ang mga tradisyonal na pamamaraan.

Paunang polygon ng mga solusyon sa isang problema sa integer programming.

Para sa binagong polygon ng mga solusyon na aming binuo bagong sistema mga paghihigpit.

Isulat natin ang sistema ng mga paghihigpit sa anyo ng mga pagkakapantay-pantay na lulutasin gamit ang algebraic method.

Bilang resulta ng solusyon, ang pinakamainam na plano para sa problema ay natagpuan: x1 = 9/4, x2 = 5/2, F = -41/4. Hindi natutugunan ng solusyong ito ang kundisyon ng integer na itinakda sa problema. Hatiin natin ang orihinal na solusyon polygon sa dalawang lugar, hindi kasama ang lugar 3 mula dito

Binagong solusyon sa problema polygon

Gumawa tayo ng mga bagong sistema ng mga paghihigpit para sa mga resultang lugar ng polygon ng solusyon. Ang kaliwang bahagi ay isang quadrilateral (trapezoid). Ang sistema ng mga paghihigpit para sa kaliwang rehiyon ng polygon ng solusyon ay ipinakita sa ibaba.

Sistema ng paghihigpit para sa kaliwang lugar

Ang tamang lugar ay kumakatawan sa punto C.

Ang sistema ng mga paghihigpit para sa tamang rehiyon ng desisyon ay ipinakita sa ibaba.

Ang mga bagong constraint system ay kumakatawan sa dalawang pantulong na problema na kailangang lutasin nang hiwalay sa isa't isa. Lutasin natin ang isang problema sa integer programming para sa kaliwang rehiyon ng polygon ng solusyon.

Bilang resulta ng solusyon, ang pinakamainam na plano para sa problema ay natagpuan: x1 = 3, x2 = 3, F = -12. Ang planong ito ay natutugunan ang kundisyon na ang mga variable sa problema ay integer at maaaring tanggapin bilang pinakamainam na reference plan para sa orihinal na integer linear programming problem. Walang punto sa paglutas para sa tamang rehiyon ng solusyon. Ang figure sa ibaba ay nagpapakita ng pag-unlad ng paglutas ng isang integer linear programming na problema sa anyo ng isang puno.

Pag-unlad ng paglutas ng isang integer linear programming problem gamit ang Gomori method.

Sa maraming praktikal na aplikasyon, isang problema sa integer programming kung saan ang isang sistema ng mga linear na hindi pagkakapantay-pantay at isang linear na anyo ay may malaking interes.

Kinakailangang maghanap ng integer na solusyon sa system (1), na nagpapaliit sa layunin ng function F, at lahat ng coefficient ay mga integer.

Ang isa sa mga pamamaraan para sa paglutas ng problema sa integer programming ay iminungkahi ni Gomori. Ang ideya ng pamamaraan ay ang paggamit ng tuluy-tuloy na mga pamamaraan ng linear programming, lalo na, ang simplex na pamamaraan.

1) Gamit ang simplex na paraan, ang solusyon sa problema (1), (2) ay tinutukoy, kung saan ang pangangailangan para sa isang integer na solusyon ay inalis; kung ang solusyon ay lumabas na integer, kung gayon ang nais na solusyon sa problema ng integer ay matatagpuan din;

2) Kung hindi, kung ang ilang coordinate ay hindi isang integer, ang nagreresultang solusyon sa problema ay sinusuri para sa posibilidad ng pagkakaroon ng isang integer na solusyon (ang pagkakaroon ng mga integer na puntos sa isang tinatanggap na polyhedron):

kung sa anumang hilera na may isang fractional na libreng termino, ang lahat ng iba pang mga coefficient ay naging mga integer, kung gayon walang mga integer o puntos sa tinatanggap na polyhedron at ang problema sa integer programming ay walang solusyon;

Kung hindi man, ang isang karagdagang linear na hadlang ay ipinakilala, na pumutol sa isang bahagi ng tinatanggap na polyhedron na hindi naaasa para sa paghahanap ng solusyon sa problema sa integer programming;

3) Upang makabuo ng karagdagang linear constraint, piliin ang ika-1 hilera na may fractional free term at isulat ang karagdagang constraint

kung saan at ayon sa pagkakabanggit ay mga fractional na bahagi ng mga coefficient at libre

miyembro. Ipakilala natin ang isang auxiliary variable sa pagpilit (3):

Tukuyin natin ang mga coefficient at kasama sa pagpilit (4):

kung saan at ang pinakamalapit na integer mula sa ibaba para sa at ayon sa pagkakabanggit.

Pinatunayan ni Gomori na ang isang tiyak na bilang ng mga katulad na hakbang ay humahantong sa isang linear na problema sa programming na ang solusyon ay integer at, samakatuwid, ang nais.

Solusyon: Dalhin natin ang sistema ng mga linear na hadlang at ang layunin ng function sa canonical form:

Tukuyin natin ang pinakamainam na solusyon sa sistema ng mga linear na hadlang, pansamantalang itinatapon ang kundisyon ng integer. Ginagamit namin ang simplex na paraan para dito. Sa ibaba, sunud-sunod sa mga talahanayan, ang orihinal na solusyon ng problema ay ipinakita, at ang mga pagbabago sa orihinal na talahanayan ay ibinigay upang makuha ang pinakamainam na solusyon sa problema:

Paglutas ng mga problema sa Boolean LP gamit ang paraan ng Balazs.

Lumikha ng iyong sariling bersyon para sa isang problema sa integer linear programming na may mga Boolean variable, na isinasaalang-alang ang mga sumusunod na patakaran: ang problema ay gumagamit ng hindi bababa sa 5 variable, hindi bababa sa 4 na mga hadlang, ang mga coefficient ng mga hadlang at ang layunin ng function ay pinipili nang arbitraryo, ngunit sa ganoong isang paraan na ang sistema ng mga hadlang ay magkatugma. Ang gawain ay upang malutas ang LCLP na may Boolean variable gamit ang Balazs algorithm at matukoy ang pagbawas sa pagiging kumplikado ng mga kalkulasyon kaugnay sa paglutas ng problema gamit ang kumpletong paraan ng paghahanap.

Pagpapatupad ng mga paghihigpit

halaga ng F

Limitasyon sa pag-filter:

Pagpapasiya ng pagbawas ng pagsusumikap sa computational

Ang solusyon sa problema gamit ang kumpletong paraan ng paghahanap ay 6*25=192 kalkuladong expression. Ang solusyon sa problema gamit ang paraan ng Balazs ay 3*6+(25-3)=47 mga kalkuladong expression. Ang kabuuang pagbawas sa pagiging kumplikado ng mga kalkulasyon na may kaugnayan sa paglutas ng problema gamit ang kumpletong paraan ng paghahanap ay:

Konklusyon

Ang proseso ng pagdidisenyo ng mga sistema ng impormasyon na nagpapatupad ng bagong teknolohiya ng impormasyon ay patuloy na pinagbubuti. Ang focus ng mga system engineer ay lalong nasa mga kumplikadong system, na nagpapahirap sa paggamit ng mga pisikal na modelo at pinapataas ang kahalagahan ng mga mathematical na modelo at machine simulation ng mga system. Ang machine simulation ay naging isang epektibong tool para sa pag-aaral at pagdidisenyo ng mga kumplikadong sistema. Ang kaugnayan ng mga modelo ng matematika ay patuloy na tumataas dahil sa kanilang flexibility, kasapatan sa mga tunay na proseso, at mababang halaga ng pagpapatupad batay sa mga modernong PC. Parami nang parami ang mga pagkakataon na ibinibigay sa gumagamit, ibig sabihin, isang espesyalista sa mga sistema ng pagmomodelo gamit ang teknolohiya ng computer. Ang paggamit ng pagmomodelo ay lalong epektibo sa mga unang yugto ng pagdidisenyo ng mga automated system, kapag ang halaga ng mga maling desisyon ay pinakamahalaga.

Ang mga modernong kasangkapan sa pag-compute ay naging posible upang makabuluhang taasan ang pagiging kumplikado ng mga modelo na ginamit sa pag-aaral ng mga sistema naging posible na bumuo ng pinagsama, analytical at simulation na mga modelo na isinasaalang-alang ang buong iba't ibang mga kadahilanan na nangyayari sa mga tunay na sistema, i.e. , ang paggamit ng mga modelo na mas sapat sa mga phenomena na pinag-aaralan.

Panitikan:

1. Lyashchenko I.N. Linear at nonlinear programming / I.N. Lyashchenko, E.A Karagodova, N.V. Chernikova, N.Z. - K.: "Mataas na Paaralan", 1975, 372 p.

2. Mga tagubilin sa pamamaraan para sa pagkumpleto ng isang proyekto ng kurso sa disiplina na "Applied Mathematics" para sa mga mag-aaral ng specialty na "Computer Systems and Networks" ng full-time at part-time na mga anyo ng pag-aaral / Compiled by: I.A. Balakireva, A.V. SevNTU Publishing House , 2003. - 15 p.

3. Mga patnubay para sa pag-aaral ng disiplina na "Applied Mathematics", seksyong "Mga paraan ng pandaigdigang paghahanap at one-dimensional minimization" / Comp. A.V. Skatkov, I.A. Balakireva, L.A. Litvinova - Sevastopol: SevGTU Publishing House, 2000. - 31 p.

4. Mga patnubay para sa pag-aaral ng disiplina na "Applied Mathematics" para sa mga mag-aaral ng specialty na "Computer Systems and Networks" Seksyon "Paglutas ng mga problema sa integer linear programming" para sa full-time at part-time na edukasyon / Compiled by: I.A. Balakireva, A.V : Publishing House ng SevNTU, 2000. - 13 p.

5. Akulich I.L. Mathematical programming sa mga halimbawa at problema:

6. Teksbuk allowance para sa mga mag-aaral sa ekonomiya. espesyalista. unibersidad.-M.: Mas mataas. paaralan, 1986.- 319 p., may sakit.

7. Andronov S.A. Pinakamainam na paraan ng disenyo: Teksto ng mga lektura / SPbSUAP. St. Petersburg, 2001. 169 p.: may sakit.

Mga katulad na dokumento

Algorithm para sa paglutas ng mga problema sa linear programming gamit ang simplex na pamamaraan. Konstruksyon ng isang mathematical model ng isang linear programming problem. Paglutas ng problema sa linear programming sa Excel. Paghahanap ng tubo at pinakamainam na plano sa produksyon.

course work, idinagdag 03/21/2012


Graphic na paglutas ng problema. Pagguhit ng isang mathematical model. Pagtukoy sa pinakamataas na halaga ng layunin ng function. Solusyon sa pamamagitan ng simplex method na may artipisyal na batayan ng canonical linear programming problem. Sinusuri ang pinakamainam ng solusyon.

pagsubok, idinagdag noong 04/05/2016


Teoretikal na batayan ng linear programming. Mga problema sa linear programming, mga pamamaraan ng solusyon. Pagsusuri ng pinakamainam na solusyon. Solusyon ng isang single-index linear programming problem. Pahayag ng problema at data entry. Mga yugto ng pagbuo ng modelo at solusyon.

course work, idinagdag noong 12/09/2008


Konstruksyon ng isang mathematical model. Pagpili, pagbibigay-katwiran at paglalarawan ng pamamaraan para sa paglutas ng isang direktang linear na problema sa programming gamit ang simplex na paraan, gamit ang isang simplex table. Pagbubuo at solusyon ng dalawahang problema. Pagsusuri ng pagiging sensitibo ng modelo.

course work, idinagdag 10/31/2014


Ang pagtatayo ng isang modelo ng matematika upang makakuha ng pinakamataas na kita para sa negosyo, graphical na solusyon ng problema. Paglutas ng problema gamit ang SOLVER add-on. Pagsusuri ng mga pagbabago sa mga reserbang mapagkukunan. Pagtukoy sa mga limitasyon para sa pagbabago ng mga coefficient ng layunin ng function.

course work, idinagdag noong 12/17/2014


Pagprograma ng matematika. Linear programming. Mga problema sa linear programming. Graphical na pamamaraan para sa paglutas ng mga problema sa linear programming. Economic formulation ng linear programming problem. Konstruksyon ng isang mathematical model.

course work, idinagdag noong 10/13/2008


Paglutas ng problema sa linear programming sa pamamagitan ng graphical na pamamaraan, pagsuri nito sa MS Excel. Pagsusuri ng panloob na istraktura ng paglutas ng isang problema sa isang programa. Pag-optimize ng plano ng produksyon. Paglutas ng problema gamit ang simplex method. Multichannel queuing system.

pagsubok, idinagdag noong 05/02/2012


Paglutas ng isang linear na problema sa programming gamit ang simplex na pamamaraan: pahayag ng problema, pagbuo ng isang modelong pang-ekonomiya at matematika. Paglutas ng problema sa transportasyon gamit ang potensyal na paraan: pagbuo ng paunang reference plan, pagtukoy sa pinakamainam na halaga nito.

pagsubok, idinagdag noong 04/11/2012


Pahayag ng problema sa nonlinear programming. Pagpapasiya ng mga nakatigil na puntos at ang kanilang uri. Pagbuo ng mga linya ng antas, tatlong-dimensional na graph ng layunin na pag-andar at mga hadlang. Graphic at analytical na solusyon ng problema. Manual ng gumagamit at algorithm diagram.

course work, idinagdag noong 12/17/2012


Pagsusuri ng solusyon sa isang linear programming problem. Simplex method gamit ang simplex tables. Pagmomodelo at paglutas ng mga problema sa LP sa isang computer. Pang-ekonomiyang interpretasyon ng pinakamainam na solusyon sa problema. Ang pagbabalangkas ng matematika ng problema sa transportasyon.