Ang paraan ng Gomori ay ginagamit upang makahanap ng mga integer na solusyon sa mga problema linear programming.
Hayaan itong matagpuan solusyon sa problema LP: . Ang solusyon L i ay magiging isang integer kung mga. . (βi) - praksyonal na bahagi non-integer optimal solution x i, (d i) ay ang fractional na bahagi ng mga di-basic na variable. Tinutukoy ng ratio na ito (tingnan ang figure).

Layunin ng serbisyo. Ang online na calculator ay ginagamit upang malutas ang mga problema sa integer linear programming gamit ang cutoff method. Sa panahon ng solusyon, ginagamit ang mga simplex na talahanayan. (tingnan ang halimbawa).

Mga tagubilin. Piliin ang bilang ng mga variable at bilang ng mga hilera (bilang ng mga hadlang), i-click ang Susunod. Ang nagresultang solusyon ay naka-imbak sa Word file(tingnan ang isang halimbawa ng solusyon gamit ang Gomori method). Bilang karagdagan, ang isang template ng solusyon ay nilikha sa format na Excel.

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

Kasabay nito, ang mga paghihigpit tulad ng x i ≥ 0 huwag mo itong isaalang-alang.

Mga uri ng algorithm ng Gomori

1. Ang unang algorithm ng Gomori para sa paglutas ng ganap na mga problema sa integer.
2. Ang pangalawang algorithm ng Gomori para sa mga problema sa bahagyang integer na linear programming.

Algoritmo ng Gomori para sa ganap na integer na mga problema ay kinabibilangan ng mga sumusunod na hakbang:

1. Ang problema ng linear programming ay nalutas nang hindi isinasaalang-alang ang integer.
2. Among mga fractional na numero pinipili at pinagsama-sama ang elementong may pinakamalaking bahaging praksyonal karagdagang paghihigpit.
3. Ang hindi pagkakapantay-pantay ay binago sa isang equation sa pamamagitan ng pagpapakilala ng karagdagang di-negatibong variable.
4. Ang resultang problema ay malulutas gamit ang dual simplex method.

Kung, sa panahon ng proseso ng solusyon, isang equation na may non-integer free terms b i at integer coefficients a ij ay lilitaw sa simplex table, kung gayon gawaing ito ay walang integer na pinakamainam na solusyon.

Halimbawa. Ang Strela Research and Production Association ay nakikibahagi sa paggawa ng mga bahagi para sa mga komplikadong negosyo ng militar-industriya. Sa paggawa ng mga produkto ng uri A at uri B, ang bakal at non-ferrous na mga metal ay ginagamit. Proseso kabilang din ang pagpoproseso ng mga produkto sa lathe at milling machine. Ayon sa mga teknolohikal na pamantayan, ang paggawa ng isang produkto ng uri A at isang produkto ng uri B ay nangangailangan ng isang tiyak na halaga ng mga hilaw na materyales at isang tiyak na halaga ng mga oras ng makina para sa pagproseso sa mga makina sa pagawaan. Ang teknolohikal na data ng proseso ng produksyon ay ibinibigay sa talahanayan.
Sa loob ng isang buwan, nagkaroon ng workshop ng NPO Strela limitadong mapagkukunan sa pamamagitan ng mga hilaw na materyales at sa oras ng trabaho sa mga tindahan ng produksyon (tingnan ang talahanayan). Ang kita mula sa pagbebenta ng isang produkto ng uri A ay 100 rubles, at mula sa isang yunit ng produkto ng uri B - 250 rubles.

	Mga hilaw na materyales		Magtrabaho sa workshop, machine-hour		Kita mula sa mga benta, kuskusin.
	Mga non-ferrous na metal	bakal	Mga gawaing pag-ikot	Paggiling trabaho
Produkto A	10	25	41	90	100
Produkto B	30	25	90	50	250
Mga mapagkukunan	4500	6250	14100	18000

Hanapin ang pinakamainam na plano sa produksyon para sa NPO Strela (dami ng uri ng produkto A at uri B - mga integer) na nagbibigay ng pinakamalaking kita.

Solusyon.
Pangkabuhayan modelo ng matematika mga gawain.
x 1 - plano ng produksyon para sa mga produkto ng uri A, x 2 - plano ng produksyon para sa mga produkto ng uri B,
Ang x 1, x 2 ay mga integer.
Mga Limitasyon sa Mapagkukunan
10x 1 + 30x 2 ≤ 4500
25x 1 + 25x 2 ≤ 6250
41x 1 + 90x 2 ≤ 14100
90x 1 + 50x 2 ≤ 18000
Layunin na pag-andar
100x 1 + 250x 2 → max

Lutasin natin ang isang direktang linear na problema sa programming gamit ang simplex na paraan. Bilang resulta, nakukuha namin ang sumusunod na pinakamainam na plano:

Batayan	B	x 1	x 2	x 3	x 4	x 5	x 6
x 2	1450 / 11	0	1	41 / 330	0	-1 / 33	0
x 4	17500 / 11	0	0	245 / 66	1	-50 / 33	0
x 1	600 / 11	1	0	-3 / 11	0	1 / 11	0
x 6	6500	0	0	55 / 3	0	-20 / 3	1
F(X3)	422500 / 11	0	0	125 / 33	0	50 / 33	0

x 1 = 54 6/11 , x 2 = 131 9/11
F(X) = 250 131 9 / 11 + 100 54 6 / 11 = 38409 1 / 11

Ang resultang pinakamainam na plano ay hindi integer, kaya ginagamit namin Pamamaraan ng Gomori. Ang pinakamalaking fractional na bahagi ay nasa pangalawang equation para sa variable na x 4 (10 / 11). Lumilikha kami ng karagdagang hadlang:
q 2 - q 21 x 1 - q 22 x 2 - q 23 x 3 - q 24 x 4 - q 25 x 5 - q 26 x 6 ≤0
q 2 = b 2 - = 1590 10 / 11 - 1590 = 10 / 11
q 2 1 = a 2 1 - = 0 - 0 = 0
q 2 2 = a 2 2 - = 0 - 0 = 0
q 2 3 = a 2 3 - = 3 47 / 66 - 3 = 47 / 66
q 2 4 = a 2 4 - = 1 - 1 = 0
q 2 5 = a 2 5 - = -1 17 / 33 + 2 = 16 / 33
q 2 6 = a 2 6 - = 0 - 0 = 0

10 / 11 - 47 / 66 x 3 - 16 / 33 x 5 ≤ 0

10 / 11 - 47 / 66 x 3 - 16 / 33 x 5 + x 7 = 0

kasi dual simplex na pamamaraan ginamit upang mahanap ang minimum ng layunin ng function, ginagawa namin ang pagbabagong F(x) = -F(X).

Batayan	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
x 2	1450 / 11	0	1	41 / 330	0	-1 / 33	0	0
x 4	17500 / 11	0	0	245 / 66	1	-50 / 33	0	0
x 1	600 / 11	1	0	-3 / 11	0	1 / 11	0	0
x 6	6500	0	0	55 / 3	0	-20 / 3	1	0
x 7	-10 / 11	0	0	-47 / 66	0	-16 / 33	0	1
F(X0)	-422500 / 11	0	0	-125 / 33	0	-50 / 33	0	0

Unang pag-ulit ng Gomori. 1. Sinusuri ang pinakamainam na pamantayan. Ang plano sa isang simplex table ay isang pseudo-plan, kaya tinutukoy namin ang nangungunang row at column.
2. Kahulugan ng isang bagong libreng variable. Kabilang sa mga negatibong halaga ng mga pangunahing variable, pinipili namin ang pinakamalaking sa ganap na halaga. Ang nangungunang linya ay ang ikalimang linya, at ang variable na x 7 ay dapat na hango sa batayan.
3. Kahulugan ng isang bagong pangunahing variable. Pinakamababang halaga Ang θ ay tumutugma sa ikalimang hanay, i.e. ang variable x 5 ay dapat ipasok sa batayan. Sa intersection ng nangungunang hilera at haligi mayroong isang elemento ng paglutas (RE) na katumbas ng (-16 / 33).

Batayan	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
x 2	131 9 / 11	0	1	41 / 330	0	-1 / 33	0	0
x 4	1590 10 / 11	0	0	3 47 / 66	1	-1 17 / 33	0	0
x 1	54 6 / 11	1	0	-3 / 11	0	1 / 11	0	0
x 6	6500	0	0	18 1 / 3	0	-6 2 / 3	1	0
x 7	-10 / 11	0	0	-47 / 66	0	-16 / 33	0	1
F(X0)	-38409 1 / 11	0	0	-3 26 / 33	0	-1 17 / 33	0	0
θ		-	-	-3 26 / 33: (-47 / 66) = 5 15 / 47	-	-1 17 / 33: (-16 / 33) = 3 1 / 8	-	-

4. Muli naming kinakalkula ang simplex table gamit ang Jordano-Gauss method.

Batayan	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
x 2	1055 / 8	0	1	27 / 160	0	0	0	-1 / 16
x 4	6375 / 4	0	0	95 / 16	1	0	0	-25 / 8
x 1	435 / 8	1	0	-13 / 32	0	0	0	3 / 16
x 6	13025 / 2	0	0	225 / 8	0	0	1	-55 / 4
x 5	15 / 8	0	0	47 / 32	0	1	0	-33 / 16
F(X0)	-153625 / 4	0	0	-25 / 16	0	0	0	-25 / 8

Ang resultang pinakamainam na plano ay naglalaman ng mga fractional na numero. Gamit ang unang equation na may variable na x2, na nakatanggap ng hindi integer na halaga sa pinakamainam na plano na may pinakamalaking fractional na bahagi 7/8, gumawa kami ng karagdagang hadlang:
q 1 - q 11 x 1 - q 12 x 2 - q 13 x 3 - q 14 x 4 - q 15 x 5 - q 16 x 6 - q 17 x 7 ≤0
q 1 = b 1 - = 131 7 / 8 - 131 = 7 / 8


q 1 3 = a 1 3 - = 27 / 160 - 0 = 27 / 160



q 1 7 = a 1 7 - = -1 / 16 + 1 = 15 / 16
Ang isang karagdagang paghihigpit ay may anyo:
7 / 8 - 27 / 160 x 3 - 15 / 16 x 7 ≤ 0
Ibahin natin ang nagresultang hindi pagkakapantay-pantay sa equation:
7 / 8 - 27 / 160 x 3 - 15 / 16 x 7 + x 8 = 0
na ang mga coefficient ay ipinakilala namin karagdagang linya sa pinakamainam simpleng mesa.

Batayan	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
x 2	1055 / 8	0	1	27 / 160	0	0	0	-1 / 16	0
x 4	6375 / 4	0	0	95 / 16	1	0	0	-25 / 8	0
x 1	435 / 8	1	0	-13 / 32	0	0	0	3 / 16	0
x 6	13025 / 2	0	0	225 / 8	0	0	1	-55 / 4	0
x 5	15 / 8	0	0	47 / 32	0	1	0	-33 / 16	0
x 8	-7 / 8	0	0	-27 / 160	0	0	0	-15 / 16	1
F(X0)	-153625 / 4	0	0	-25 / 16	0	0	0	-25 / 8	0

Pangalawang pag-ulit ng Gomroya. 1. Sinusuri ang pinakamainam na pamantayan. Ang plano sa isang simplex table ay isang pseudo-plan, kaya tinutukoy namin ang nangungunang row at column.
2. Kahulugan ng isang bagong libreng variable. Kabilang sa mga negatibong halaga ng mga pangunahing variable, ang pinakamalaking sa ganap na halaga ay ang variable na x8. Dapat itong hango sa batayan.
3. Ang pinakamababang halaga ng θ ay tumutugma sa ikapitong hanay, i.e. ang variable x 7 ay dapat ipasok sa batayan.

Batayan	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
x 2	131 7 / 8	0	1	27 / 160	0	0	0	-1 / 16	0
x 4	1593 3 / 4	0	0	5 15 / 16	1	0	0	-3 1 / 8	0
x 1	54 3 / 8	1	0	-13 / 32	0	0	0	3 / 16	0
x 6	6512 1 / 2	0	0	28 1 / 8	0	0	1	-13 3 / 4	0
x 5	1 7 / 8	0	0	1 15 / 32	0	1	0	-2 1 / 16	0
x 8	-7 / 8	0	0	-27 / 160	0	0	0	-15 / 16	1
F(X0)	-38406 1 / 4	0	0	-1 9 / 16	0	0	0	-3 1 / 8	0
θ		-	-	-1 9 / 16: (-27 / 160) = 9 7 / 27	-	-	-	-3 1 / 8: (-15 / 16) = 3 1 / 3	-

4. Isagawa ang New Gomori cut transformation.

Batayan	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
x 2	1979 / 15	0	1	9 / 50	0	0	0	0	-1 / 15
x 4	4790 / 3	0	0	13 / 2	1	0	0	0	-10 / 3
x 1	271 / 5	1	0	-11 / 25	0	0	0	0	1 / 5
x 6	19576 / 3	0	0	153 / 5	0	0	1	0	-44 / 3
x 5	19 / 5	0	0	46 / 25	0	1	0	0	-11 / 5
x 7	14 / 15	0	0	9 / 50	0	0	0	1	-16 / 15
F(X0)	-115210 / 3	0	0	-1	0	0	0	0	-10 / 3

Ang pinakamainam na plano ay naglalaman ng mga fractional na numero. Ang pinakamalaking fractional na bahagi ng variable ay x 2 (14 / 15). Gumagawa kami ng karagdagang hadlang: q 1 - q 11 x 1 - q 12 x 2 - q 13 x 3 - q 14 x 4 - q 15 x 5 - q 16 x 6 - q 17 x 7 - q 18 x 8 ≤0
q 1 = b 1 - = 131 14 / 15 - 131 = 14 / 15
q 1 1 = a 1 1 - = 0 - 0 = 0
q 1 2 = a 1 2 - = 1 - 1 = 0
q 1 3 = a 1 3 - = 9 / 50 - 0 = 9 / 50
q 1 4 = a 1 4 - = 0 - 0 = 0
q 1 5 = a 1 5 - = 0 - 0 = 0
q 1 6 = a 1 6 - = 0 - 0 = 0
q 1 7 = a 1 7 - = 0 - 0 = 0
q 1 8 = a 1 8 - = -1 / 15 + 1 = 14 / 15
Ang isang karagdagang paghihigpit ay may anyo:
14 / 15 - 9 / 50 x 3 - 14 / 15 x 8 ≤ 0
Ibahin natin ang nagresultang hindi pagkakapantay-pantay sa equation:
14 / 15 - 9 / 50 x 3 - 14 / 15 x 8 + x 9 = 0
ang mga coefficient nito ay ilalagay bilang karagdagang linya sa pinakamainam na simplex table.

Batayan	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
x 2	1979 / 15	0	1	9 / 50	0	0	0	0	-1 / 15	0
x 4	4790 / 3	0	0	13 / 2	1	0	0	0	-10 / 3	0
x 1	271 / 5	1	0	-11 / 25	0	0	0	0	1 / 5	0
x 6	19576 / 3	0	0	153 / 5	0	0	1	0	-44 / 3	0
x 5	19 / 5	0	0	46 / 25	0	1	0	0	-11 / 5	0
x 7	14 / 15	0	0	9 / 50	0	0	0	1	-16 / 15	0
x 9	-14 / 15	0	0	-9 / 50	0	0	0	0	-14 / 15	1
F(X0)	-115210 / 3	0	0	-1	0	0	0	0	-10 / 3	0

Pangatlong pag-ulit sa pamamagitan ng Gomori method. Ang variable na x 9 ay dapat na hango sa batayan. Ang pinakamababang halaga ng θ ay tumutugma sa ikawalong hanay, i.e. ang variable x 8 ay dapat ipasok sa batayan.

Batayan	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
x 2	131 14 / 15	0	1	9 / 50	0	0	0	0	-1 / 15	0
x 4	1596 2 / 3	0	0	6 1 / 2	1	0	0	0	-3 1 / 3	0
x 1	54 1 / 5	1	0	-11 / 25	0	0	0	0	1 / 5	0
x 6	6525 1 / 3	0	0	30 3 / 5	0	0	1	0	-14 2 / 3	0
x 5	3 4 / 5	0	0	1 21 / 25	0	1	0	0	-2 1 / 5	0
x 7	14 / 15	0	0	9 / 50	0	0	0	1	-1 1 / 15	0
x 9	-14 / 15	0	0	-9 / 50	0	0	0	0	-14 / 15	1
F(X0)	-38403 1 / 3	0	0	-1	0	0	0	0	-3 1 / 3	0
θ		-	-	-1: (-9 / 50) = 5 5 / 9	-	-	-	-	-3 1 / 3: (-14 / 15) = 3 4 / 7	-

4. Isagawa ang pagbabago.

Batayan	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
x 2	132	0	1	27 / 140	0	0	0	0	0	-1 / 14
x 4	1600	0	0	50 / 7	1	0	0	0	0	-25 / 7
x 1	54	1	0	-67 / 140	0	0	0	0	0	3 / 14
x 6	6540	0	0	234 / 7	0	0	1	0	0	-110 / 7
x 5	6	0	0	317 / 140	0	1	0	0	0	-33 / 14
x 7	2	0	0	27 / 70	0	0	0	1	0	-8 / 7
x 8	1	0	0	27 / 140	0	0	0	0	1	-15 / 14
F(X0)	-38400	0	0	-5 / 14	0	0	0	0	0	-25 / 7

Ang solusyon ay naging integer. Ang pinakamainam na integer plan ay maaaring isulat tulad ng sumusunod: x 1 = 54, x 2 = 132. F(X) = 38400

Pang-ekonomiya at geometriko na interpretasyon ng problema integer programming. Ang isang matinding problema na ang mga variable ay kumukuha lamang ng mga halaga ng integer ay tinatawag na problema sa integer programming.

Sa mathematical model ng integer problem programming ang layunin ng function at ang mga function sa sistema ng mga hadlang ay maaaring linear, nonlinear at halo-halong. Limitahan natin ang ating sarili sa kaso kung kailan layunin function at ang sistema ng mga hadlang ng problema ay linear.

Halimbawa 20.

Napagpasyahan na mag-install ng karagdagang kagamitan sa pagawaan ng negosyo, kung saan inilalaan ang puwang. Ang isang negosyo ay maaaring gumastos ng 10 libong rubles sa pagbili ng kagamitan, at maaari itong bumili ng dalawang uri ng kagamitan. Ang isang set ng type I na kagamitan ay nagkakahalaga ng 1,000 rubles, at type II - 3,000 rubles.

Solusyon. Ang pagbili ng isang set ng type I na kagamitan ay nagbibigay-daan sa iyo upang madagdagan ang output ng produksyon sa bawat shift ng 2 unit, at isang set ng type II na kagamitan - ​​sa pamamagitan ng 4 na unit. Ang pag-alam na ang pag-install ng isang set ng type I na kagamitan ay nangangailangan ng 2 m 2 ng lugar, at ang type II na kagamitan ay nangangailangan ng 1 m 2 ng lugar, tukuyin ang naturang set ng karagdagang kagamitan na ginagawang posible upang mapakinabangan ang produksyon na output

Gumawa tayo ng mathematical model ng problema.

Ipagpalagay natin na ang enterprise ay bibili ng x 1 set ng equipment ng type I at set ng equipment ng type II. Pagkatapos ang mga variable x 1 at dapat matugunan ang mga sumusunod na hindi pagkakapantay-pantay:

Kung ang negosyo ay bumili ng tinukoy na halaga ng kagamitan, kung gayon ang kabuuang pagtaas sa output ay magiging

Ayon sa kanilang pang-ekonomiyang nilalaman, ang mga variable x 1 at maaari lamang kumuha ng mga hindi negatibong halaga ng integer, i.e. x 1 , – mga integer.(73) Kaya, dumating tayo sa sumusunod problema sa matematika: hanapin pinakamataas na halaga linear function (71) kapag natugunan ang mga kundisyon (70), (72), at (73). Dahil ang mga hindi alam ay maaari lamang kumuha ng mga halaga ng integer, ang problema (70) – (73) ay isang problema sa integer programming. Dahil ang bilang ng mga hindi alam sa problema ay dalawa, ang solusyon sa problemang ito ay matatagpuan gamit ang geometric na interpretasyon nito. Upang gawin ito, una sa lahat, gagawa kami ng polygon ng mga solusyon sa problema na binubuo ng pagtukoy sa pinakamataas na halaga ng linear function (71) kapag natugunan ang mga kondisyon (70) at (72) (Fig. 11). Mga coordinate ng lahat ng mga punto ng itinayong polygon na solusyon OAEVS masiyahan ang sistema mga linear na hindi pagkakapantay-pantay (70) at kundisyon hindi negatibiti mga variable (72). Kasabay nito, kondisyon (73), ibig sabihin, kundisyon integridad ang mga variable ay nasiyahan sa pamamagitan ng mga coordinate ng 12 puntos lamang na minarkahan sa Fig. 11. Upang mahanap ang punto kung saan ang mga coordinate ay tumutukoy sa solusyon sa orihinal na problema, palitan ang polygon, na naglalaman ng lahat ng wastong puntos na may mga integer na coordinate at ang mga coordinate ng bawat isa sa mga vertices ay mga integer na numero. Nangangahulugan ito na kung makikita natin ang pinakamataas na punto ng function (71) sa polygon ang mga variable ay nasiyahan sa pamamagitan ng mga coordinate ng 12 puntos lamang na minarkahan sa Fig. 11. Upang mahanap ang punto kung saan ang mga coordinate ay tumutukoy sa solusyon sa orihinal na problema, palitan ang polygon, kung gayon ang mga coordinate ng puntong ito ay tutukuyin ang pinakamainam na plano para sa problema.

Upang gawin ito, gagawa din kami ng isang tuwid na linya na dumadaan sa polygon ng solusyon ang mga variable ay nasiyahan sa pamamagitan ng mga coordinate ng 12 puntos lamang na minarkahan sa Fig. 11. Upang mahanap ang punto kung saan ang mga coordinate ay tumutukoy sa solusyon sa orihinal na problema, palitan ang polygon(ang numero 12 ay kinukuha nang arbitraryo). Inilipat namin ang itinayong linya sa direksyon ng vector hanggang sa ito ay dumaan sa huling karaniwang punto nito kasama ang ibinigay na polygon. Tinutukoy ng mga coordinate ng puntong ito ang pinakamainam na plano, at ang halaga ng layunin ng function dito ay ang pinakamataas.

SA sa kasong ito ang kinakailangang punto ay E(1; 3), kung saan ang layunin ng function ay tumatagal ng pinakamataas na halaga C, samakatuwid, ang mga coordinate ng punto E tukuyin ang pinakamainam na plano para sa problema (70) – (73). Alinsunod sa planong ito, dapat bumili ang enterprise ng isang set ng type 1 equipment at tatlong set ng type II equipment. Bibigyan nito ang negosyo ng mga kasalukuyang paghihigpit nito sa espasyo at pondo ng produksyon maximum na pagpapalaki

output ng produksyon na katumbas ng 14 na yunit. bawat shift.

Halimbawa 21. Upang maisagawa ang gawain ay maaaring gamitin n mga mekanismo. Pagganap i -ika mekanismo kapag nagsasagawa – j ang gawain ay katumbas ng . Ipagpalagay na ang bawat mekanismo ay magagamit lamang sa isang trabaho at ang bawat trabaho ay maaaring gawin sa pamamagitan lamang ng isang mekanismo, tukuyin ang pagtatalaga ng mga mekanismo sa mga trabaho na nagsisiguro pinakamataas na pagganap

Solusyon.. Bumuo ng isang mathematical model ng problema. Ipakilala natin ang isang variable na x ij na ang halaga ay 1 kung, kapag nagpapatupad -ika mekanismo kapag nagsasagawa – i-th

(74)

gawaing ginamit

(75)

ika mekanismo, at katumbas ng 0 kung hindi man. Pagkatapos ang mga kondisyon para sa paggamit ng bawat mekanismo sa isang trabaho lamang ay ipinahayag ng mga pagkakapantay-pantay at ang mga kondisyon para sa pagsasagawa ng trabaho sa pamamagitan lamang ng isang mekanismo - pagkakapantay-pantay

Kaya, ang gawain ay upang matukoy ang mga naturang halaga ng mga hindi alam

, kasiya-siyang sistema ng mga equation (74) at (75) at kundisyon (76), kung saan nakamit ang pinakamataas na halaga ng function Isaalang-alang natin ang mga problema sa integer programming kung saan ang layunin ng function at ang mga function sa system ng mga hadlang ay linear. Kaugnay nito, binubuo namin ang pangunahing problema sa linear programming kung saan ang mga variable ay maaari lamang kumuha ng mga halaga ng integer. Sa pangkalahatan, ang problemang ito ay maaaring isulat bilang mga sumusunod: hanapin ang maximum ng function

sa ilalim ng mga kondisyon

(79)

– buo (81)

Kung makakahanap tayo ng solusyon sa problema (78) – (81) simplex na pamamaraan, kung gayon ito ay maaaring o hindi maaaring integer (isang halimbawa, ang solusyon kung saan ay palaging integer, ay problema sa transportasyon). Sa pangkalahatang kaso, upang matukoy ang pinakamainam na plano para sa problema (78) – (81) kinakailangan ang mga espesyal na pamamaraan. Sa kasalukuyan, mayroong ilang mga naturang pamamaraan, kung saan ang pinakasikat ay Pamamaraan ng Gomori, na batay sa simplex na pamamaraan na inilarawan sa itaas.

Pamamaraan ng Gomori. Ang paghahanap ng solusyon sa problema sa integer programming gamit ang Gomori method ay nagsisimula sa pagtukoy ng pinakamainam na plano ng problema (78) – (80) gamit ang simplex method, nang hindi isinasaalang-alang (70) at kundisyon mga variable. Kapag nahanap na ang planong ito, susuriin ang mga bahagi nito. Kung walang mga fractional na numero sa mga bahagi, kung gayon ang nahanap na plano ay ang pinakamainam na plano para sa problema sa integer programming (78) – (81). Kung sa pinakamainam na plano ng problema (78) - (80) ang variable ay tumatagal ng isang fractional na halaga, pagkatapos ay ang hindi pagkakapantay-pantay ay idinagdag sa sistema ng mga equation (79)

(82)

at humanap ng solusyon sa problema (78) – (80), (82).

Sa hindi pagkakapantay-pantay (82) at – binago ang mga paunang dami at ang mga halaga ay kinuha mula sa huling talahanayan ng simplex, at – fractional na bahagi ng mga numero (ang fractional na bahagi ng isang tiyak na numero a ay ang pinakamaliit na hindi negatibong numero b tulad na ang pagkakaiba sa pagitan A At b may buo). Kung sa pinakamainam na plano ng problema (78) - (80) ang mga fractional na halaga ay tumatagal sa ilang mga variable, pagkatapos ay ang karagdagang hindi pagkakapantay-pantay (82) ay tinutukoy pinakamalaking fraction

bahagi.

Kung sa nahanap na plano ng problema (78) - (80), (82) ang mga variable ay kumukuha ng mga fractional na halaga, pagkatapos ay isang karagdagang hadlang ay idinagdag muli at ang proseso ng pagkalkula ay paulit-ulit. Ang pagsasagawa ng isang may hangganang bilang ng mga pag-ulit, maaaring makuha ng isa ang pinakamainam na plano para sa problema sa integer programming (78) – (81) o itatag ang hindi malutas nito. (70) at kundisyon Kung ang kinakailangan (81) ay nalalapat lamang sa ilang mga variable, pagkatapos ay ang mga naturang problema ay tinatawag bahagyang integer. Ang kanilang solusyon ay matatagpuan din sa pamamagitan ng sunud-sunod na paglutas ng mga problema, ang bawat isa ay nakuha mula sa nauna sa pamamagitan ng pagpapakilala ng karagdagang hadlang.

kung saan natutukoy mula sa mga sumusunod na relasyon:

1) para sa , na maaaring kumuha ng mga hindi integer na halaga,

(84)

2) para sa , na maaari lamang kumuha ng mga halaga ng integer,

(85)

Mula sa itaas ay sumusunod na ang proseso ng pagtukoy ng pinakamainam na plano para sa isang problema sa integer programming gamit ang Gomori method ay kinabibilangan ng mga sumusunod pangunahing yugto:

1. Gamit ang simplex method, humanap ng solusyon sa problema (78) – (80) nang hindi isinasaalang-alang ang pangangailangan (70) at kundisyon mga variable.

2. Lumikha ng karagdagang hadlang para sa variable, na sa pinakamainam na plano ng problema (78) – (80) ay may maximum fractional halaga, at sa pinakamainam na plano, ang problema (78) – (81) ay dapat na integer.

3. Gamit ang dalawahan , humanap ng solusyon sa problemang bunga ng problema (78) – (80) bilang resulta ng pagdaragdag ng karagdagang hadlang.

4. Kung kinakailangan, lumikha ng isa pang karagdagang hadlang at ipagpatuloy ang umuulit na proseso hanggang sa makuha ang pinakamainam na plano para sa problema (78) – (81) o ang hindi pagkalutas nito ay maitatag.

Halimbawa 22.

Gamitin ang Gomori method upang mahanap ang maximum na halaga ng function

ibinigay na

(87)

– buo (89)

Solusyon. Upang matukoy ang pinakamainam na plano para sa problema (86) – (89), hahanapin muna natin ang pinakamainam na plano para sa problema (86) – (88) (Talahanayan 22).

Talahanayan 22

		C b	R 0

Tulad ng makikita mula sa talahanayan. 22, nakita ang pinakamainam na plano problema (86) – (88) ay hindi isang pinakamainam na plano para sa problema (86) – (89), dahil dalawang bahagi at may mga non-integer na halaga. Bukod dito, ang mga fractional na bahagi ng mga numerong ito ay katumbas ng bawat isa. Samakatuwid, ang isang karagdagang hadlang ay iginuhit para sa isa sa mga variable na ito. Gumawa tayo, halimbawa, tulad ng isang hadlang para sa variable Mula sa huling talahanayan ng simplex (Talahanayan 22) mayroon tayong

Kaya, sa sistema ng mga hadlang ng problema (86) - (89) idinaragdag namin ang hindi pagkakapantay-pantay

o

Talahanayan 23

		C b	R 0

Nahanap na natin ngayon ang pinakamataas na halaga ng function (86) kapag natugunan ang mga kondisyon (87), (88) at (90) (Talahanayan 23).

Mula sa Talahanayan 23 makikita na ang orihinal na problema sa programming ng integer ay may pinakamainam na plano P Sa planong ito, ang halaga ng layunin ng function ay katumbas ng . Magbigay tayo ng geometric na interpretasyon ng solusyon sa problema. Ang rehiyon ng mga magagawang solusyon sa problema (86) – (88) ay isang polygon OABCD (Larawan 12). Mula sa Fig. 12 makikita na ang layunin ng function ay tumatagal ng pinakamataas na halaga nito sa punto SA(19/2; 7/2), ibig sabihin. Ano X == (19/2; 7/2; 0; 0; 34) ay hindi ang pinakamainam na plano para sa problema (86) – (89) (mga numero at fractional), pagkatapos ay ipinakilala ang isang karagdagang hadlang. Hindi kasama dito at sa halip ay pinapalitan ang kaukulang mga halaga mula sa mga equation ng sistema ng mga hadlang (87), nakakakuha kami ng cutoff mula sa polygon Magbigay tayo ng geometric na interpretasyon ng solusyon sa problema. Ang rehiyon ng mga magagawang solusyon sa problema (86) – (88) ay isang polygon tatsulok EFC.

Tulad ng makikita mula sa Fig. 12, ang rehiyon ng mga magagawang solusyon sa nagresultang problema ay isang polygon OABEFD. Sa punto E(9; 4) ng polygon na ito, ang layunin ng pag-andar ng problemang ito ay tumatagal ng pinakamataas na halaga. Dahil ang mga coordinate ng punto E ay mga integer na numero at hindi alam, at kumukuha ng mga integer na halaga kapag pinapalitan ang mga halaga at sa equation (87), pagkatapos ay ang pinakamainam na plano para sa problema (86) – (89). Kasunod din ito mula sa Talahanayan 23.

Halimbawa 23.

Gamit ang Gomori method, humanap ng solusyon sa problema ng pagtukoy sa pinakamataas na halaga ng isang function

sa ilalim ng mga kondisyon

- buo.

(94)

Solusyon. Magbigay ng geometric na interpretasyon ng solusyon sa problema.

sa ilalim ng mga kondisyon

(96)

Isulat muli natin ang nabuong problema tulad ng sumusunod: hanapin ang pinakamataas na halaga ng function

- buo.

(98)

Problema (95) – (98) ay bahagyang integer, dahil ang mga variable at maaaring kumuha ng mga non-integer na halaga.

		C b	R 0
		C b	R 0
							Gamit ang simplex na paraan, hinahanap natin ang solusyon sa problema (95) – (97) (Talahanayan 24).

Talahanayan 24

–1/3 ay hindi isang plano para sa problema (95) – (98), dahil ang variable

Ang kakanyahan ng mga pamamaraan ng pruning ay ang problema ay unang nalutas nang walang kondisyon ng integer. Kung ang resultang plano ay integer, malulutas ang problema. Kung hindi, may idaragdag na bagong hadlang sa mga hadlang sa gawain na may mga sumusunod na katangian:

Dapat itong maging linear;

Dapat putulin ang nahanap na pinakamainam na non-integer na plano;

Hindi dapat putulin ang anumang integer plan. Ang isang karagdagang hadlang na may ganitong mga katangian ay tinatawag na tamang cutoff. Geometrically pagdaragdag ng bawat isa

linear na hadlang

tumutugma sa pagguhit ng isang tuwid na linya (hyperplane) na pumutol sa ilang bahagi nito mula sa solusyon polygon (polyhedron) kasama ang pinakamainam na punto na may mga non-integer na coordinate, ngunit hindi nakakaapekto sa alinman sa mga integer na punto ng polyhedron na ito. Bilang resulta, ang bagong solusyon na polyhedron ay naglalaman ng lahat ng mga integer na puntos na nakapaloob sa orihinal na solusyon na polyhedron at, nang naaayon, ang pinakamainam na solusyon na nakuha sa polyhedron na ito ay magiging integer (Fig. 8.1).

(8.5)

pagpindot sa mga pangunahing variable *1, *2, mga bagong variable Xm+1, Xm+2, ..., Xm+1, mga solusyon

Xt hanggang neo-x„optimal

na nabuo ng /th equation ng system (8.5), ay mayroong lahat ng mga katangian ng isang regular na cutoff.

Upang malutas ang problema sa integer linear programming (8.1)-(8.4) gamit ang Gomori method, ang sumusunod na algorithm ay ginagamit:

1. Gamit ang simplex method, lutasin ang problema (8.1)-(8.3) nang hindi isinasaalang-alang ang integer condition. Kung ang lahat ng bahagi ng pinakamainam na plano ay mga integer, kung gayon ito ay pinakamainam din para sa problema sa integer programming (8.1)-(8.4). Kung ang unang problema (8.1) -

(8.3) ay hindi malulutas (iyon ay, wala itong pangwakas na pinakamabuting kalagayan o ang mga kondisyon nito ay magkasalungat), at ang pangalawang problema (8.1)-(8.4) ay hindi rin malulutas.

2. Kung kabilang sa mga bahagi ng pinakamainam na solusyon ay may mga non-integer, pagkatapos ay piliin ang bahagi na may pinakamalaking bahagi ng integer at, gamit ang kaukulang equation ng system (8.5), bumuo ng tamang cut-off (8.6).

3. Sa pamamagitan ng pagpapakilala ng karagdagang non-negative integer variable, ibahin ang hindi pagkakapantay-pantay (8.6) sa isang katumbas na equation

(P() - |a/ t+1 )*t+1- ■-(a|"l )xn + xn+1 > (®*^)

at isama ito sa sistema ng mga paghihigpit (8.2).

4. Lutasin ang resultang pinahabang problema gamit ang simplex method. Kung ang pinakamainam na plano na natagpuan ay integer,

pagkatapos ay ang problema sa integer programming (8.1)-(8.4) ay malulutas. Kung hindi, bumalik sa hakbang 2 ng algorithm.

Kung ang problema ay malulutas sa mga integer, pagkatapos ay pagkatapos ng isang tiyak na bilang ng mga hakbang (mga pag-ulit) ang pinakamainam na integer plan ay makikita.

Kung sa proseso ng paglutas ng isang equation ay lilitaw (nagpapahayag ng pangunahing variable sa mga tuntunin ng mga di-basic) na may isang non-integer na libreng term at integer na natitirang mga coefficient, kung gayon ang kaukulang equation ay walang solusyon sa mga integer. Sa kasong ito, ang problemang ito ay walang integer na pinakamainam na solusyon.

^8.1. Para makabili ng mga kagamitan sa pag-uuri ng butil, naglalaan ang magsasaka ng 34 den. mga yunit Ang kagamitan ay dapat ilagay sa isang lugar na hindi hihigit sa 60 metro kuwadrado. m. Ang magsasaka ay maaaring mag-order ng dalawang uri ng kagamitan: hindi gaanong makapangyarihang uri A na makina na nagkakahalaga ng 3 den. mga yunit na nangangailangan ng isang lugar ng produksyon na 3 sq. m (kabilang ang mga pass) at nagbibigay ng produktibidad na 2 toneladang butil bawat shift, at mas makapangyarihang type B machine na nagkakahalaga ng 4 den. mga yunit na sumasakop sa isang lugar na 5 sq. m at nagbibigay ng produktibidad ng 3 tonelada ng mataas na kalidad na butil bawat shift.

Kinakailangan na gumuhit ng isang pinakamainam na plano para sa pagbili ng mga kagamitan na nagsisiguro ng pinakamataas na pangkalahatang produktibo, sa kondisyon na ang magsasaka ay maaaring bumili ng hindi hihigit sa 8 uri ng B machine.

Solusyon. Tukuyin natin sa pamamagitan ng x\, x2 ang bilang ng mga sasakyan ng uri A at B, ayon sa pagkakabanggit, ng Z - pangkalahatang pagganap. Pagkatapos ang modelo ng matematika ng problema ay kukuha ng anyo:

Sa Fig. 8.2 OKM - lugar ng mga magagawang solusyon sa problema (8.1") - (8.3"), limitado ng mga tuwid na linya (1), (2), (3) at coordinate axes; />(2/3; 8) - ang punto ng pinakamainam, ngunit hindi integer na solusyon sa problema (8.1") - (8.3"); (4) - isang tuwid na linya na pinuputol ang non-integer na solusyon; 0№М - lugar ng mga magagawang solusyon ng pinahabang problema (8.1') - (8.3'), (8.61); M2; 7) - punto ng pinakamainam na integer na solusyon.

Hakbang I. Mga pangunahing variable x3, x4, *5; mga di-basic na variable X\, X2.

x3	= 60 -	Zh! - 5x2,
x4	= 34 -	Zx) - 4x2,
x5	= 8	- *2>
	Z = 2x)	+ Zx2.

Ang unang pangunahing solusyon X\ = (0; 0; 60; 34; 8) ay tinatanggap. Ang katumbas na linear function na value = 0.

Isinasalin namin sa pangunahing mga variable ang variable na XI, na kasama sa pagpapahayag ng linear function na may pinakamalaking positibong koepisyent. Nahanap namin ang pinakamataas na posibleng halaga ng variable xi, na "pinapayagan" ng sistema ng mga paghihigpit, mula sa kondisyon ng minimum ng kaukulang mga relasyon:

Хг = 1ШП|т;т;Т| = 8,

mga. ang paglutas (naka-highlight) equation ay ang pangatlo. Kapag ang *2 = 8 sa equation na ito X5 = 0, at ang variable na X5 ay naging non-basic.

Hakbang II. Mga pangunahing variable x2, x3, x*; hindi pangunahing mga variable Xx X5.

{

(8.6)

Sa pamamagitan ng pagpapakilala ng karagdagang integer variable x6 > O, nakukuha namin ang equation na katumbas ng inequality (8.6")

~1*5 + Xb = °" ^8"7 ^

Ang equation (8.7") ay dapat isama sa sistema ng mga hadlang (8.5") ng orihinal na canonical na problema, at pagkatapos ay ulitin ang proseso ng paglutas ng problema gamit ang simplex na paraan kaugnay ng pinalawig na problema. Sa kasong ito, upang bawasan ang bilang ng mga hakbang (mga pag-ulit), inirerekumenda na magpasok ng karagdagang equation (8.7") sa sistema na nakuha sa huling hakbang ng paglutas ng problema (nang walang kondisyon ng integer).

IV hakbang. Mga pangunahing variable X), *2, xs> *b‘> mga hindi pangunahing variable *1, *2-

X1 = z - 3*4 +

x3 = 18 + x4 +___ x5,

x6 - + ^x4 + z"x5-

Ang pangunahing solusyon X4 = (y; 8; 18; 0; 0; -y) ay hindi katanggap-tanggap. (Tandaan na pagkatapos magsama ng karagdagang equation na naaayon sa tamang cutoff sa constraint system, palaging makukuha ang isang di-wastong batayan na solusyon.)

Upang makakuha ng isang katanggap-tanggap na pangunahing solusyon, kinakailangan na i-convert sa pangunahing variable, na kasama ng isang positibong koepisyent sa equation kung saan ang libreng termino ay negatibo, i.e. *1 o x$ (sa yugtong ito hindi namin isinasaalang-alang ang isang linear function). Isinasalin namin sa mga pangunahing, halimbawa, ang variable na X5.

V hakbang. Mga pangunahing variable X\, X2, X3, X5; mga di-basic na variable R], X £

Pagkatapos ng mga pagbabago, nakukuha namin ang:

LG| = 2 - x4 + 2x6,

*2 = 7 + 2х* ~ 2Х("

x3 = 19 + -x4 + -x6,

*5 = 1 - 2х* + 2Х6’

2 = 25-|x4--|x6.

^5 =(2; 7; 19; 0; 1;0);^ = 25.

Dahil walang pangunahing mga variable na may mga positibong coefficient sa pagpapahayag ng isang linear function, ang X5 ay ang pinakamainam na solusyon.

Kaya, 2max = 25 sa pinakamainam integer na solusyon X* - X$ =(2; 7; 19; 0; 1; 0), ibig sabihin. ang maximum na produktibidad na 25 tonelada ng mataas na kalidad na butil bawat shift ay maaaring makuha sa pamamagitan ng pagbili ng 2 makina ng uri A at 7 makina ng uri B\ habang ang walang tao na lugar ng lugar ay magiging 19 sq. m. m, nananatili cash sa mga inilalaan ay katumbas ng 0, sa reserba para sa pagbili - 1 makina ng uri B (ang ikaanim na bahagi ay walang makabuluhang kahulugan).

Magkomento. Para sa isang geometric na interpretasyon sa eroplanong Ox\Xr (tingnan ang Fig. 8.2) ng cutoff (8.6"), kinakailangang ipahayag ang mga variable na x4 at x$ na kasama dito sa pamamagitan ng mga variable XI at x2. Nakukuha namin (tingnan ang 2nd at 3rd equation ng system of constraints (8.5")):

y - y (34 - 3x, - 4x2) - y (8 - x2) £ 0 o x, + 2x2 £ 16.

(tingnan ang clipping line (4) sa Fig. 8.2)>

^8.2. May sapat na malaking bilang Ang mga troso na 3 m ang haba ay dapat gupitin sa dalawang uri ng mga blangko: 1.2 m ang haba at 0.9 m ang haba, at hindi bababa sa 50 piraso ng bawat uri ay dapat makuha. at 81 pcs. ayon sa pagkakabanggit. Ang bawat log ay maaaring i-cut sa tinukoy na mga piraso sa ilang mga paraan: 1) sa 2 piraso ng 1.2 m bawat isa; 2) para sa 1 piraso ng 1.2 m bawat isa at 2 piraso ng 0.9 m bawat isa; 3) para sa 3 piraso ng 0.9 m bawat isa Hanapin ang bilang ng mga log,

sawn sa pamamagitan ng bawat paraan, upang ang anumang uri ng workpiece ay maaaring makuha mula sa pinakamaliit na bilang ng mga log.

Solusyon. Tukuyin natin sa pamamagitan ng х\, хі, хм, ang bilang ng mga log na pinutol nang naaayon sa 1, 2 at 3 na paraan mula sa kanila ay makakakuha ka ng 2хі + *2 blangko ng 1.2 m bawat isa at 2l\ + 3x2 blangko ng 0.9 m bawat Hayaan. tinutukoy namin ang kabuuang bilang ng mga log sa pamamagitan ng I. Pagkatapos ang modelo ng matematika ng problema ay kukuha ng anyo:

I 2х, + x2 - x4 = 50, , hindi hihigit dito.

Sa ilalim praksyonal na bahagi ilang numero A nangangahulugang ang pinakamaliit na hindi negatibong numero
na ang pagkakaiba sa pagitan nito at A may [ a] – integer na bahagi ng numero).

Para sa napiling variable na batayan na may pinakamalaking fractional na bahagi hanapin ang fractional na bahagi
ang variable na ito at ang mga fractional na bahagi ng lahat ng coefficient para sa mga variable mga mekanismo. Pagganap ika-linya ng sistema ng mga paghihigpit
(linya ng paggawa).

Tukuyin natin
At
buong bahagi ng mga numero At . Mga fractional na halaga
At
(
) ay tinukoy bilang mga sumusunod

Upang gawin ito, ang isang equation ay isinulat mula sa pagbuo ng row ng simplex table, sa pag-aakalang ang unang m pangunahing mga variable para sa isang naibigay na pinakamainam na plano

o

Inililipat namin ang lahat ng integer na bahagi ng mga coefficient sa isang direksyon, na iniiwan ang lahat ng fractional na bahagi sa kabilang direksyon:

kasi
<1, то заменяя в правой части
, nakukuha natin ang mahigpit na hindi pagkakapantay-pantay

Dahil ang kaliwang bahagi ng hindi pagkakapantay-pantay ay dapat kumuha ng mga halaga ng integer, samakatuwid, ang kinakailangang kundisyon para sa integerity nito ay maaari lamang isulat sa sumusunod na anyo:

Ang hindi pagkakapantay-pantay ay na-convert sa isang equation sa pamamagitan ng pagpapakilala ng karagdagang di-negatibong variable at kasama sa pinakamainam na simplex table.

Malutas namin ang problema gamit ang dual simplex na pamamaraan. Kung ang bagong pinakamainam na plano para sa pinalawig na problema ay integer, pagkatapos ay malulutas ang problema. Kung ang solusyon ay hindi integer, kailangan mong ulitin ang Gomori method algorithm hanggang sa makuha ang integer solution.

Halimbawa. Gamit ang Gomori method, humanap ng solusyon sa isang integer programming problem na binubuo ng pagtukoy sa maximum value ng isang function.
ibinigay na

Solusyon. Pag-level ng mga Di-pagkakapantay-pantay gamit ang mga Auxiliary Variable X 3 , X 4, nakuha namin ang linear programming problem sa canonical form:

Malutas namin ang problema sa linear programming gamit ang simplex na paraan, gamit ang sunud-sunod na paglipat mula sa isang batayan patungo sa isa pa. Ang pag-unlad ng paglutas ng problema at ang resultang pinakamainam na solusyon ay ipinakita sa mga talahanayan.

	(Larawan 12). B			(Larawan 12). 2 =11
∆ -ika mekanismo kapag nagsasagawa =Z -ika mekanismo kapag nagsasagawa -SA -ika mekanismo kapag nagsasagawa

	(Larawan 12). B			(Larawan 12). 2 =11
∆ -ika mekanismo kapag nagsasagawa =Z -ika mekanismo kapag nagsasagawa -SA -ika mekanismo kapag nagsasagawa

Sa nahanap na pinakamainam na plano, ang halaga ng variable X Ang 2 ay katumbas ng isang fractional number. Nakita namin ang fractional na bahagi nito at ang mga fractional na bahagi ng lahat ng elemento ng linya na naglalaman ng variable X 2, ibig sabihin:

Ngayon binubuo namin ang hindi pagkakapantay-pantay ng Gomori para sa mga nahanap na halaga ng mga fractional na bahagi:

.

X 5, inililipat namin ang libreng termino ng equation sa kanang bahagi at kumuha ng bagong hadlang:

.

Nagdagdag kami ng row na naglalaman ng bagong constraint at column na naglalaman ng bagong variable sa simplex table, at patuloy na lutasin ang problema gamit ang dual simplex method, dahil nakasulat na ngayon ang pseudoplan sa table.

∆ -ika mekanismo kapag nagsasagawa =Z -ika mekanismo kapag nagsasagawa –(Larawan 12). -ika mekanismo kapag nagsasagawa

	(Larawan 12). B			(Larawan 12). 2 =11
∆ -ika mekanismo kapag nagsasagawa =Z -ika mekanismo kapag nagsasagawa –(Larawan 12). -ika mekanismo kapag nagsasagawa

Ang resultang pinakamainam na solusyon sa pinahabang problema ay naglalaman ng isang hindi-integer na halaga ng variable X 1, kaya nahanap namin para sa linyang ito ang mga fractional na bahagi ng lahat ng hindi integer na numero, katulad:

at ang bagong hindi pagkakapantay-pantay ng Gomory ay may anyo:

Tinutumbasan namin ang hindi pagkakapantay-pantay ni Gomori gamit ang isang bagong auxiliary variable X 6, inililipat namin ang libreng termino ng equation sa kanang bahagi at kumuha ng bagong hadlang:
.

Idinaragdag namin ito sa problemang nilulutas, ihanay ito gamit ang isang auxiliary variable at lutasin ang pinalawig na problema

	(Larawan 12). B			(Larawan 12). 2 =11
∆ -ika mekanismo kapag nagsasagawa =Z -ika mekanismo kapag nagsasagawa –(Larawan 12). -ika mekanismo kapag nagsasagawa

	(Larawan 12). B			(Larawan 12). 2 =11
∆ -ika mekanismo kapag nagsasagawa =Z -ika mekanismo kapag nagsasagawa –(Larawan 12). -ika mekanismo kapag nagsasagawa

Kaya, ang pinakamainam na solusyon sa problema sa integer programming ay natagpuan: Z max=11 sa
.

Mga Tala :

Kung, sa panahon ng proseso ng solusyon, ang isang equation na may non-integer na bahagi ay lilitaw sa simplex table at mga integer coefficient sa kaukulang linya ng sistema ng mga paghihigpit
, kung gayon ang problemang ito ay walang integer na solusyon.

Ang pamamaraan ay batay sa simplex na pamamaraan, na ginagamit upang mahanap ang pinakamainam na solusyon nang hindi isinasaalang-alang ang mga kondisyon ng integer. Kung ang resultang plano ay naglalaman ng hindi bababa sa isang fractional na bahagi, pagkatapos ay isang karagdagang pagpilit ay ipapataw at ang mga kalkulasyon ay muling magpapatuloy sa paggamit ng simplex na paraan.

Ang proseso ay nagpapatuloy hanggang ang lahat ng bahagi ng plano ay integer, o ito ay ipinapakita na ang problema ay walang integer na solusyon.

Hayaang X* = (x1, x2, …, xm, …, xn) ang pinakamainam na plano na natagpuan gamit ang simplex method, kung saan ang batayan ay ang mga vectors A1, A2,…, Am. Hayaang ang xi ay isang fractional number (ang numero sa column B sa i-th row). Pagkatapos ay posible na sa i-th na linya:

1. lahat ng xij ay mga integer, nangangahulugan ito na ang problema ay walang integer na solusyon

2. ilang xij ay fractional

Hayaang ang [xi] at [xij] ay mga bahaging integer ng mga numerong xi at хij, at ang (xi) at (хij) ay mga bahaging fractional.

Ipahiwatig natin ang qi = (хi) at qij = (хij) at buuin ang mga pagkakaiba.

(qi1Х1+ qi1Х2+…+ qi1Хn)- qi ≥0

Ibahin natin ang hindi pagkakapantay-pantay sa isang equation sa pamamagitan ng pagpaparami nito sa (-1) at pagdaragdag ng bagong variable Xn+1 at pagdaragdag ng bagong row sa simplex table (at samakatuwid ay isang column). Mas lutasin namin ang paggamit ng dual simplex na paraan kung ang nahanap na plano ay hindi integer, pagkatapos ay ulitin namin ang proseso ng pagdaragdag ng bagong variable, row at column sa simplex table.

Kung ang pinakamainam na plano ay may ilang mga non-integer na bahagi, pagkatapos ay gumawa kami ng karagdagang hadlang para sa maximum na qi.

Maaari mo ring mahanap ang impormasyong interesado ka sa siyentipikong search engine na Otvety.Online. Gamitin ang form sa paghahanap:

Higit pa sa paksa 47 Gomori method: pangunahing ideya at maikling paglalarawan ng algorithm. Ang pang-ekonomiyang kahulugan ng pagpapakilala ng karagdagang paghihigpit:

1. 25. Mga pamamaraan ng pamamahala sa ekonomiya, ang kanilang nilalayon na layunin. Mga uri at pangunahing nilalaman ng mga pamamaraan ng impluwensyang pang-ekonomiya. Maikling paglalarawan at mga tampok ng aplikasyon ng mga pamamaraang pang-ekonomiya