Las leitakse üles probleemi lahendus LP: . Lahendus L i on täisarv, kui
need. 
. (βi) - murdosa mittetäisarvuline optimaalne lahendus x i, (d i) on mittepõhimuutujate murdosa. See suhe määrab (vt joonist). Teenuse eesmärk. Online-kalkulaatorit kasutatakse täisarvuliste lineaarsete programmeerimisülesannete lahendamiseks lõikemeetodi abil. Lahenduse käigus kasutatakse simplekstabeleid. (vt näidet).
Juhised. Valige muutujate arv ja ridade arv (piirangute arv), klõpsake nuppu Edasi. Saadud lahust hoitakse Wordi fail(vt Gomori meetodit kasutava lahenduse näidet). Lisaks luuakse lahendusmall Exceli vormingus.
Samas piirangud nagu x i ≥ 0ära arvesta sellega.Gomori algoritmi tüübid
- Gomori esimene algoritm täiesti täisarvuliste ülesannete lahendamiseks.
- Gomori teine algoritm osaliselt täisarvuliste lineaarsete programmeerimisprobleemide jaoks.
Gomori algoritm täisarvuliste probleemide puhul hõlmab järgmisi samme:
- Lineaarse programmeerimise probleem lahendatakse ilma täisarvu arvestamata.
- hulgas murdarvud valitakse ja koostatakse kõige suurema murdosaga element täiendav piirang.
- Ebavõrdsus teisendatakse võrrandiks, lisades täiendava mittenegatiivse muutuja.
- Tekkinud probleem lahendatakse dual simplex meetodi abil.
Näide. Teadus- ja tootmisühing Strela tegeleb komponentide valmistamisega sõjalis-tööstuskompleksi ettevõtetele. A- ja B-tüüpi toodete valmistamisel kasutatakse terast ja värvilisi metalle. Tehnoloogiline protsess hõlmab ka toodete töötlemist trei- ja freespinkidel. Vastavalt tehnoloogilistele standarditele on ühe A-tüüpi toote ja ühe B-tüüpi toote tootmiseks töökojas masinatel töötlemiseks vaja teatud kogust toorainet ja teatud masinatunde. Tootmisprotsessi tehnoloogilised andmed on toodud tabelis.
Kuu aja jooksul on MTÜ Strela töökoda piiratud ressursid tooraine ja tootmistsehhis töötamise aja järgi (vt tabel). Kasum ühe A-tüüpi toote müügist on 100 rubla ja B-tüüpi tooteühikult 250 rubla.
| Toored materjalid | Töö tsehhis, masinatund | Kasum müügist, hõõruda. | |||
| Värvilised metallid | Teras | Treimistööd | Freesitööd | ||
| Toode A | 10 | 25 | 41 | 90 | 100 |
| Toode B | 30 | 25 | 90 | 50 | 250 |
| Vahendid | 4500 | 6250 | 14100 | 18000 | |
Leidke NPO Strela jaoks optimaalne tootmisplaan (tootetüübi A ja tüübi B kogus – täisarvud), mis annab suurima kasumi.
Lahendus.
Majanduslik matemaatiline mudelülesandeid.
x 1 - A-tüüpi toodete tootmisplaan, x 2 - B-tüüpi toodete tootmisplaan,
x 1, x 2 on täisarvud.
Ressursi piirangud
10 x 1 + 30 x 2 ≤ 4500
25x1 + 25x2 ≤ 6250
41x1 + 90x2 ≤ 14100
90x1 + 50x2 ≤ 18000
Objektiivne funktsioon
100x1 + 250x2 → max
Lahendame sirgjoonelise programmeerimise ülesande, kasutades simpleksmeetodit. Selle tulemusena saame järgmise optimaalse plaani:
| Alus | 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
Saadud optimaalne plaan ei ole täisarv, seega kasutame Gomori meetod. Suurim murdosa on muutuja x 4 (10 / 11) teises võrrandis. Loome täiendava piirangu:
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
Kuna dual simplex meetod kasutatakse sihtfunktsiooni miinimumi leidmiseks, teeme teisenduse F(x) = -F(X).
| Alus | 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 |
Gomori esimene iteratsioon. 1. Optimaalsuse kriteeriumi kontrollimine. Plaan simplekstabelis on pseudoplaan, seega määrame juhtrea ja veeru.
2. Uue vaba muutuja definitsioon. Põhimuutujate negatiivsete väärtuste hulgast valime absoluutväärtuses suurima. Juhtrida on viies rida ja muutuja x 7 tuleks tuletada alusest.
3. Uue põhimuutuja definitsioon. Minimaalne väärtusθ vastab viiendale veerule, st. muutuja x 5 tuleb sisestada baasi. Juhtrea ja veeru ristumiskohas on lahutuselement (RE), mis on võrdne (-16 / 33).
| Alus | 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. Arvutame simplekstabeli ümber Jordano-Gaussi meetodil.
| Alus | 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 |
Saadud optimaalne plaan sisaldab murdarvusid. Kasutades esimest võrrandit muutujaga x2, mis sai optimaalses plaanis mittetäisarvulise väärtuse suurima murdosaga 7/8, loome täiendava piirangu:
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
Täiendav piirang on kujul:
7/8-27/160 x 3-15/16 x 7 ≤ 0
Teisendame saadud ebavõrdsuse võrrandiks:
7/8-27/160 x 3-15/16 x 7 + x 8 = 0
mille koefitsiendid võtame kasutusele lisarida optimaalseks simpleks laud.
| Alus | 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 |
Gomroya teine iteratsioon. 1. Optimaalsuse kriteeriumi kontrollimine. Plaan simplekstabelis on pseudoplaan, seega määrame juhtrea ja veeru.
2. Uue vaba muutuja definitsioon. Põhimuutujate negatiivsete väärtuste hulgas on absoluutväärtuses suurim muutuja x8. See tuleks tuletada alusest.
3. θ miinimumväärtus vastab seitsmendale veerule, s.o. muutuja x 7 tuleb sisestada baasi.
| Alus | 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. Tehke uue Gomori lõike teisendus.
| Alus | 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 |
Optimaalne plaan sisaldab murdarvu. Muutuja suurim murdosa on x 2 (14/15). Loome täiendava piirangu: 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
Täiendav piirang on kujul:
14/15-9/50 x 3-14/15 x 8 ≤ 0
Teisendame saadud ebavõrdsuse võrrandiks:
14/15-9/50 x 3-14/15 x 8 + x 9 = 0
mille koefitsiendid kantakse lisareana optimaalsesse simplekstabelisse.
| Alus | 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 |
Kolmas iteratsioon Gomori meetodil. Muutuja x 9 tuleks tuletada alusest. θ miinimumväärtus vastab kaheksandale veerule, st. muutuja x 8 tuleb sisestada baasi.
| Alus | 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. Tehke teisendus.
| Alus | 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 |
Lahendus osutus täisarvuks. Optimaalse täisarvu plaani saab kirjutada järgmiselt: x 1 = 54, x 2 = 132. F(X) = 38400
Probleemi majanduslik ja geomeetriline tõlgendus täisarvu programmeerimine. Äärmuslikku probleemi, mille muutujad võtavad ainult täisarvulisi väärtusi, nimetatakse täisarvu programmeerimise probleemiks.
Täisarvuülesande matemaatilises mudelis programmeerimine nii sihtfunktsioon kui ka funktsioonid piirangute süsteemis võivad olla lineaarsed, mittelineaarsed ja segatud. Piirdugem juhtumiga, kui objektiivne funktsioon ja ülesande piirangute süsteem on lineaarne.
Näide 20.
Ettevõtte töökotta otsustati paigaldada lisaseadmed, mille jaoks eraldati ruumi. Ettevõte võib seadmete ostmiseks kulutada 10 tuhat rubla ja osta kahte tüüpi seadmeid. I tüüpi seadmete komplekt maksab 1000 rubla ja II tüüpi 3000 rubla. Ühe I tüüpi seadmete komplekti ostmine võimaldab suurendada tootmisvõimsust vahetuse kohta 2 ühiku võrra ja ühe II tüüpi seadmete komplekti 4 ühiku võrra. Teades, et ühe I tüüpi seadmete komplekti paigaldamiseks on vaja 2 m 2 pinda ja II tüüpi seadmete jaoks 1 m 2 pinda, määrake selline lisaseadmete komplekt, mis võimaldab tootmisvõimsust maksimeerida.
Lahendus. Koostame ülesande matemaatilise mudeli. Oletame, et ettevõte ostab x 1 komplekti I tüüpi seadmeid ja II tüüpi seadmeid. Seejärel peavad muutujad x 1 ja vastama järgmistele ebavõrdsustele:
Kui ettevõte ostab kindlaksmääratud koguse seadmeid, siis kogutoodangu kasv on
Vastavalt oma majanduslikule sisule võivad muutujad x 1 ja võtta ainult mittenegatiivseid täisarvulisi väärtusi, s.o.
x 1 , – täisarvud. (73)
Seega jõuame järgmiseni matemaatika ülesanne: leia maksimaalne väärtus lineaarne funktsioon(71) kui tingimused (70), (72) ja (73) on täidetud. Kuna tundmatud saavad võtta ainult täisarvulisi väärtusi, on ülesanne (70) – (73) täisarvude programmeerimise probleem. Kuna ülesandes on tundmatute arv kaks, saab selle ülesande lahenduse leida selle geomeetrilise tõlgenduse abil. Selleks konstrueerime kõigepealt ülesande lahenduste hulknurga, mis koosneb lineaarfunktsiooni (71) maksimaalse väärtuse määramisest, kui tingimused (70) ja (72) on täidetud (joonis 11). Konstrueeritud lahendushulknurga kõigi punktide koordinaadid OAEVS süsteemi rahuldada lineaarsed ebavõrdsused(70) ja tingimus mittenegatiivsus muutujad (72). Samal ajal tingimus (73), st tingimus terviklikkus muutujad on rahuldatud ainult 12 punkti koordinaatidega, mis on märgitud joonisel fig. 11. Et leida punkt, mille koordinaadid määravad algülesande lahenduse, asenda hulknurk OABC hulknurk OKEMNF, mis sisaldab kõiki kehtivaid täisarvuliste koordinaatidega punkte ja nii, et iga tipu koordinaadid on täisarvud. See tähendab, et kui leiame funktsiooni maksimumpunkti (71) hulknurgalt OKEMNF, siis määravad selle punkti koordinaadid probleemi optimaalse plaani.
Selleks konstrueerime ka lahendushulknurka läbiva sirge OKEMNF(arv 12 on võetud meelevaldselt). Liigutame konstrueeritud sirget vektori suunas, kuni see läbib oma viimase ühispunkti antud hulknurgaga. Selle punkti koordinaadid määravad optimaalse plaani ja sihtfunktsiooni väärtus sellel on maksimaalne.
IN sel juhul vajalik punkt on E(1; 3), milles sihtfunktsioon võtab maksimaalse väärtuse C, seega punkti koordinaadid E määrata probleemi optimaalne plaan (70) – (73). Selle kava kohaselt peaks ettevõte ostma ühe komplekti 1. tüüpi seadmeid ja kolm komplekti II tüüpi seadmeid. See annab ettevõttele olemasolevad piirangud tootmispinnale ja rahalistele vahenditele maksimaalne suurendus tootmisvõimsus on võrdne 14 ühikuga. vahetuse kohta.
Näide 21.
Töö teostamiseks saab kasutada P mehhanismid. Esitus i-th mehhanism täitmisel j – th töö on võrdne . Eeldades, et iga mehhanismi saab kasutada ainult ühel tööl ja iga tööd saab teha ainult üks mehhanism, määrake mehhanismide määramine töödele, mis tagab maksimaalne jõudlus. Koostage probleemi matemaatiline mudel.
Lahendus. Toome täitmisel sisse muutuja x ij, mille väärtus on võrdne 1 if i-th kasutatud tööd j – mehhanismi ja vastasel juhul võrdub 0. Seejärel väljendatakse võrdsustega tingimusi iga mehhanismi kasutamiseks ainult ühel tööl
(74)
ja ainult ühe mehhanismiga töö tegemise tingimused - võrdsused
(75)
Seega on ülesandeks määrata sellised tundmatute väärtused 
, mis rahuldavad võrrandisüsteeme (74) ja (75) ning tingimust (76), mille korral saavutatakse funktsiooni maksimaalne väärtus
Sõnastatud probleem on täisarvulise programmeerimise probleem.
Täisarvulise programmeerimise ülesande optimaalse plaani määramine. Vaatleme täisarvulise programmeerimise ülesandeid, milles nii sihtfunktsioon kui ka funktsioonid piirangute süsteemis on lineaarsed. Sellega seoses sõnastame põhilise lineaarse programmeerimise probleemi, mille puhul muutujad saavad võtta ainult täisarvulisi väärtusi. Üldiselt saab selle ülesande kirjutada järgmiselt: leia funktsiooni maksimum
tingimustel
(79)
– terve (81)
Kui leiame probleemile lahenduse (78) – (81) simpleks meetod, siis võib see olla täisarv või mitte (näide, mille lahendus on alati täisarv, on transpordi probleem). Üldjuhul on probleemi (78) – (81) optimaalse plaani kindlaksmääramiseks vaja erimeetodeid. Praegu on selliseid meetodeid mitu, millest kõige kuulsam on Gomori meetod, mis põhineb ülalkirjeldatud simpleksmeetodil.
Gomori meetod. Täisarvulise programmeerimise ülesande lahenduse leidmine Gomori meetodil algab ülesande optimaalse plaani (78) – (80) määramisega simpleksmeetodil, arvestamata terviklikkus muutujad. Kui see plaan on leitud, vaadatakse selle komponendid üle. Kui komponentide hulgas pole murdarvu, siis on leitud plaan täisarvulise programmeerimise ülesande (78) – (81) jaoks optimaalne plaan. Kui ülesande (78) – (80) optimaalses plaanis võtab muutuja murdosa, siis lisatakse võrratus võrrandisüsteemi (79)
(82)
ja leida lahendus probleemile (78) – (80), (82).
Ebavõrdsuses (82) ja – teisendatud algsuurused ja mille väärtused on võetud viimasest simplekstabelist ja – arvude murdosad (teatud arvu murdosa a on väikseim mittenegatiivne arv b selline, et vahe A Ja b seal on tervik). Kui ülesande (78) – (80) optimaalses plaanis võtavad murdarvud mitu muutujat, siis määratakse täiendav ebavõrdsus (82). suurim murdosa osa.
Kui leitud ülesandeplaanis (78) – (80), (82) võtavad muutujad murdväärtusi, siis lisatakse uuesti üks lisapiirang ja arvutusprotsessi korratakse. Lõpliku arvu iteratsioonide läbiviimisel saadakse täisarvulise programmeerimise ülesande (78) – (81) jaoks optimaalne plaan või tuvastatakse selle lahendamatus.
Kui nõue terviklikkus(81) kehtib ainult mõne muutuja kohta, siis nimetatakse selliseid probleeme osaliselt täisarv. Nende lahendus leitakse ka ülesandeid järjestikku lahendades, millest igaüks saadakse eelnevast lisapiirangu sisseviimisega. Sel juhul on sellisel piirangul vorm
kus määratakse järgmistest seostest:
1) jaoks , mis võib võtta mittetäisarvulisi väärtusi,
(84)
2) jaoks , mis võib võtta ainult täisarvulisi väärtusi,
(85)
Eeltoodust järeldub, et täisarvulise programmeerimise probleemi optimaalse plaani määramise protsess Gomori meetodi abil hõlmab järgmist peamised etapid:
1. Kasutades simpleksmeetodit, leia lahendus ülesandele (78) – (80) ilma nõuet arvestamata terviklikkus muutujad.
2. Loo muutujale lisapiirang, mis ülesande (78) – (80) optimaalses plaanis on maksimaalne murdosa väärtus ja optimaalses plaanis peaks ülesanne (78) – (81) olema täisarv.
3. Kasutades duaali, leia lisapiirangu lisamise tulemusena ülesandest (78) – (80) tulenevale probleemile lahendus.
4. Vajadusel loo veel üks lisapiirang ja jätka iteratiivset protsessi, kuni saadakse probleemi (78) – (81) jaoks optimaalne plaan või tuvastatakse selle lahendamatus.
Näide 22.
Funktsiooni maksimaalse väärtuse leidmiseks kasutage Gomori meetodit
arvestades seda
(87)
– terve (89)
Lahendus. Probleemi (86) – (89) optimaalse plaani määramiseks leiame esmalt optimaalse plaani probleemi (86) – (88) jaoks (tabel 22).
Tabel 22
|
C b |
R 0 |
|||||||
Nagu tabelist näha. 22, leitud optimaalne plaan 
probleem (86) – (88) ei ole ülesande (86) – (89) jaoks optimaalne plaan, kuna kahel komponendil ja on mittetäisarvulised väärtused. Pealegi on nende arvude murdosad üksteisega võrdsed. Seetõttu koostatakse ühele neist muutujatest täiendav piirang. Teeme näiteks sellise piirangu muutujale Viimasest simplekstabelist (tabel 22) saame
Seega liidame ülesande (86) – (89) piirangute süsteemile ebavõrdsuse
või
Tabel 23
|
C b |
R 0 |
||||||||
Nüüd leiame funktsiooni (86) maksimaalse väärtuse, kui tingimused (87), (88) ja (90) on täidetud (tabel 23).
Tabelist 23 on näha, et algsel täisarvulise programmeerimise ülesandel on optimaalne plaan
P Selles plaanis on sihtfunktsiooni väärtus võrdne . Anname ülesande lahenduse geomeetrilise tõlgenduse. Ülesande (86) – (88) teostatavate lahenduste piirkond on hulknurk OABCD(joonis 12). Jooniselt fig. 12 on näha, et sihtfunktsioon võtab punktis oma maksimaalse väärtuse KOOS(19/2; 7/2), s.o. Mida X =(19/2; 7/2; 0; 0; 34) on optimaalne plaan. See ilmneb otseselt tabelist 22. Kuna X= (19/2; 7/2; 0; 0; 34) ei ole ülesande (86) – (89) jaoks optimaalne plaan (arvud ja on murdosa), siis võetakse kasutusele täiendav piirang. Jättes sellest välja ja asendades selle asemel vastavad väärtused piirangute süsteemi (87) võrranditest, saame hulknurgast piiri OABCD kolmnurk EFC.
Nagu näha jooniselt fig. 12 on saadud probleemi võimalike lahenduste piirkond hulknurk OABEFD. Punktis E(9; 4) sellest hulknurgast võtab selle ülesande sihtfunktsioon maksimaalse väärtuse. Kuna punkti koordinaadid E on täisarvud ja tundmatud ning võtavad väärtuste asendamisel ja võrrandisse (87) täisarvud, siis 
on probleemi optimaalne plaan (86) – (89). See tuleneb ka tabelist 23.
Näide 23.
Gomori meetodi abil leia lahendus funktsiooni maksimaalse väärtuse määramise ülesandele
tingimustel
- terve. (94)
Andke ülesande lahenduse geomeetriline tõlgendus.
Lahendus. Kirjutame sõnastatud ülesande ümber järgmiselt: leiame funktsiooni maksimaalse väärtuse
tingimustel
(96)
- terve. (98)
Ülesanne (95) – (98) on osaliselt täisarv, kuna muutujad ja võivad võtta mittetäisarvulisi väärtusi.
Simpleksmeetodil leiame ülesande (95) – (97) lahenduse (tabel 24).
Tabel 24
|
C b |
R 0 |
|||||||
|
C b |
R 0 |
|||||||
|
–1/3 ei ole ülesande (95) – (98) plaan, kuna muutuja |
Kärpimismeetodite olemus seisneb selles, et probleem lahendatakse esmalt ilma täisarvu tingimuseta. Kui saadud plaan on täisarv, on probleem lahendatud. Vastasel juhul lisatakse ülesande piirangutele uus piirang järgmiste omadustega:
See peaks olema lineaarne;
Peaks katkestama leitud optimaalse mittetäisarvulise plaani;
Ei tohiks kärpida ühtegi täisarvu plaani.
Täiendavat piirangut, millel on need omadused, nimetatakse õigeks piiriks.
Igaühe geomeetriline lisamine lineaarne piirang vastab sirgjoone (hüpertasapinna) tõmbamisele, mis lõikab sellest mingi osa lahenduspolügoonist (polühedrist) koos optimaalse punktiga mittetäisarvuliste koordinaatidega, kuid ei mõjuta ühtegi selle hulktahuka täisarvu punkti. Selle tulemusena sisaldab uus lahenduspolüheder kõiki algses lahenduspolüeedris sisalduvaid täisarvupunkte ja vastavalt sellele on selle hulktahukaga saadav optimaalne lahendus täisarv (joonis 8.1).
vajutades põhimuutujaid *1, *2, uued muutujad Xm+1, Xm+2, ..., Xm+1, lahendused
Xt läbi neo-x„optimaalne
| (8.5) |
mittetäisarvuline komponent. Sel juhul saab tõestada, et ebavõrdsus
(P, ) - (a," m+\)xm+1 ■ -~(at )Xn ^ 0, (* )
mis on moodustatud süsteemi (8.5) võrrandist /th, omab kõiki regulaarse piiri omadusi.
Täisarvulise lineaarse programmeerimise ülesande (8.1)-(8.4) lahendamiseks Gomori meetodil kasutatakse järgmist algoritmi:
1. Kasutades simpleksmeetodit, lahenda ülesanne (8.1)-(8.3) täisarvu tingimust arvestamata. Kui optimaalse plaani kõik komponendid on täisarvud, siis on see optimaalne täisarvulise programmeerimise ülesande (8.1)-(8.4) jaoks. Kui esimene probleem (8.1) -
(8.3) on lahendamatu (st tal puudub lõplik optimum või selle tingimused on vastuolulised), siis on ka teine ülesanne (8.1)-(8.4) lahendamatu.
2. Kui optimaalse lahenduse komponentide hulgas on mittetäisarvulisi, siis vali suurima täisarvulise osaga komponent ja moodusta süsteemi vastava võrrandi (8.5) abil õige piir (8.6).
3. Täiendava mittenegatiivse täisarvulise muutuja kasutuselevõtuga teisendage võrratus (8.6) samaväärseks võrrandiks
(P() - |a/ t+1 )*t+1- ■-(a|"l )xn + xn+1 > (®*^)
ja lisada see piirangute süsteemi (8.2).
4. Lahendage saadud laiendatud ülesanne, kasutades simpleksmeetodit. Kui leitud optimaalne plaan on täisarv,
siis on täisarvulise programmeerimise ülesanne (8.1)-(8.4) lahendatud. Vastasel juhul pöörduge tagasi algoritmi 2. sammu juurde.
Kui ülesanne on lahendatav täisarvudes, siis pärast lõplikku arvu samme (iteratsioone) leitakse optimaalne täisarvude plaan.
Kui lahendamise käigus tekib võrrand (väljendades põhimuutujat mittepõhilistena) mittetäisarvulise vaba liikme ja täisarvuliste järelejäänud koefitsientidega, siis vastaval võrrandil pole lahendust täisarvudes. Sel juhul pole sellel probleemil optimaalset täisarvulist lahendust.
^8.1. Teraviljasorteerimisseadmete ostmiseks eraldab talunik 34 den. ühikut Seadmed tuleb paigutada alale, mis ei ületa 60 ruutmeetrit. m Talunik saab tellida kahte tüüpi seadmeid: vähem võimsaid A-tüüpi masinaid, mille hind on 3 den. üksused, mis nõuavad tootmispinda 3 ruutmeetrit. m (koos läbipääsudega) ja tagavad tootlikkuse 2 tonni teravilja vahetuses ning võimsamad B-tüüpi masinad maksavad 4 den. üksused, mille pindala on 5 ruutmeetrit. m ja pakkudes tootlikkust 3 tonni kvaliteetset teravilja vahetuses.
Seadmete ostmiseks on vaja koostada optimaalne plaan, mis tagab maksimaalse üldise tootlikkuse, eeldusel, et põllumees saab osta mitte rohkem kui 8 B-tüüpi masinat.
Lahendus. Tähistame x\, x2-ga vastavalt A- ja B-tüüpi autode arvu Z-ga - Üldine jõudlus. Seejärel võtab ülesande matemaatiline mudel järgmisel kujul:
Joonisel fig. 8.2 OKM - probleemi võimalike lahenduste ala (8,1") - (8,3"), mis on piiratud sirgjoonte (1), (2), (3) ja koordinaattelgedega; />(2/3; 8) - ülesande optimaalse, kuid mittetäisarvulise lahenduse punkt (8,1") - (8,3"); (4) - selle mittetäisarvulise lahenduse lõikav sirgjoon; 0№М - laiendatud ülesande teostatavate lahenduste piirkond (8.1’) - (8.3’), (8.61); M2; 7) - optimaalse täisarvlahenduse punkt.
I samm. Peamised muutujad x3, x4, *5; mittepõhimuutujad X\, X2.
| x3 | = 60 - | Zh! - 5x2, |
| x4 | = 34 - | Zx) - 4x2, |
| x5 | = 8 | - *2> |
| Z = 2x) | + Zx2. |
Esimene põhilahend X\ = (0; 0; 60; 34; 8) on lubatud. Vastav lineaarse funktsiooni väärtus = 0.
Peamisteks muutujateks teisendame muutuja XI, mis sisaldub suurima positiivse koefitsiendiga lineaarfunktsiooni avaldises. Vastavate seoste miinimumi tingimusest leiame muutuja xi maksimaalse võimaliku väärtuse, mida piirangute süsteem “võimaldab” aktsepteerida:
Хг = 1ШП|т;т;Т| = 8,
need. Lahendatav (esiletõstetud) võrrand on kolmas. Kui *2 = 8 selles võrrandis X5 = 0 ja muutuja X5 muutub mittepõhiliseks.
II etapp. Peamised muutujad x2, x3, x*; mittepeamised muutujad Xx X5.
| { |
| (8.6) |
Täiendava täisarvulise muutuja x6 > O kasutuselevõtmisega saame võrrandi, mis on ekvivalentne ebavõrdsusega (8,6")
~1*5 + Xb = °" ^8"7 ^
Võrrand (8,7") tuleb kaasata algse kanoonilise ülesande piirangute süsteemi (8,5") ja seejärel korrata ülesande lahendamise protsessi, kasutades laiendatud ülesande suhtes simpleksmeetodit. Sel juhul on sammude (iteratsioonide) arvu vähendamiseks soovitatav ülesande lahendamise viimases etapis saadud süsteemi sisse viia lisavõrrand (8,7") (ilma täisarvu tingimuseta).
IV samm. Põhimuutujad X), *2, xs> *b‘> mittepõhimuutujad *1, *2-
X1 = z - 3*4 +
x3 = 18 + x4 +___ x5,
x6 - + ^x4 + z"x5-
Põhilahend X4 = (y; 8; 18; 0; 0; -y) on vastuvõetamatu. (Pange tähele, et pärast piirangusüsteemi õigele piirile vastava lisavõrrandi lisamist saadakse alati kehtetu baaslahendus.)
Lubatava põhilahenduse saamiseks on vaja teisendada põhimuutujaks, mis sisaldub positiivse koefitsiendiga võrrandis, milles vaba liige on negatiivne, s.t. *1 või x$ (praegus etapis me lineaarset funktsiooni ei käsitle). Tõlgime põhilisteks, näiteks muutuja X5.
V samm. Peamised muutujad X\, X2, X3, X5; mittepõhimuutujad R], X £
Pärast teisendusi saame:
LG| = 2 - x4 + 2x6,
*2 = 7 + 2х* ~ 2Х("
x3 = 19 + -x4 + -x6,
*5 = 1 - 2x* + 2x6'
2 = 25-|x4--|x6.
^5 =(2; 7; 19; 0; 1;0);^ = 25.
Kuna lineaarfunktsiooni avaldises puuduvad positiivsete koefitsientidega põhimuutujad, on X5 optimaalne lahendus.
Niisiis, optimaalsel juhul 2max = 25 täisarvuline lahendus X* - X$ =(2; 7; 19; 0; 1; 0), s.o. maksimaalse tootlikkuse 25 tonni kvaliteetset teravilja vahetuses saab ostes 2 A-tüüpi masinat ja 7 B-tüüpi masinat, samas kui ruumide vaba pindala on 19 ruutmeetrit. m, jääb Raha eraldatutest on 0, ostureservis - 1 B-tüüpi masin (kuuendal komponendil pole sisulist tähendust).
Kommenteeri. Lõike (8.6") geomeetriliseks tõlgendamiseks tasapinnal Ox\Xr (vt joonis 8.2) on vaja selles sisalduvaid muutujaid x4 ja x$ väljendada muutujate XI ja x2 kaudu. Saame (vt. piirangute süsteemi (8,5") 2. ja 3. võrrand):
y - y (34 - 3x, - 4x2) - y (8 - x 2) 0 naela või x, + 2x2 16 naela.
(vt lõikejoont (4) joonisel 8.2)>
^8.2. Neid on piisavalt suur hulk palgid pikkusega 3 m Palgid tuleks lõigata kahte tüüpi toorikuteks: 1,2 m pikkused ja 0,9 m pikkused ning igat tüüpi tuleks hankida vähemalt 50 tükki. ja 81 tk. vastavalt. Iga palki saab ettenähtud toorikuteks lõigata mitmel viisil: 1) kaheks 1,2-meetriseks toorikuks; 2) 1 tk 1,2 m ja 2 0,9 m tükki; 3) 3 tükki, igaüks 0,9 m, leidke palkide arv,
saetud iga meetodiga, nii et väikseimast arvust palkidest saab mis tahes tooriku.
Lahendus. Tähistame х\, хі, хм, vastavalt lõigatud palkide arv 1, 2 ja 3 meetodiga Nendest saate 2хі + *2 toorikut 1,2 m ja 2l\ + 3x2 toorikut, igaüks 0,9 m Olgu. me tähistame logide koguarvu I-ga. Siis saab ülesande matemaatiline mudel järgmise kuju:
I 2х, + x2 - x4 = 50, , ei ületa seda.
Under murdosa
mingi number A tähendab väikseimat mittenegatiivset arvu 
selline, et erinevus selle ja A Seal on [ a] – arvu täisarvuline osa).
Valitud baasmuutuja jaoks 
suurima murdosaga
leida murdosa 
see muutuja ja muutujate kõigi koefitsientide murdosad i piirangute süsteemi rida 
(tootmisliin).
Tähistame 
Ja 
arvude terved osad 
Ja 
. Murdväärtused 
Ja 
(
) on määratletud järgmiselt
Selleks kirjutatakse simplekstabeli genereerivast realt üles võrrand, eeldades, et esimene m muutujad on antud optimaalse plaani jaoks põhilised
või 
Liigutame kõik koefitsientide täisarvud ühes suunas, jättes kõik murdosad teise:
Sest 
<1,
то заменяя в правой части 
, saame range ebavõrdsuse
Kuna ebavõrdsuse vasak pool peab võtma täisarvulisi väärtusi, saab selle täisarvu jaoks vajaliku tingimuse kirjutada ainult järgmisel kujul:
Ebavõrdsus teisendatakse võrrandiks, lisades täiendava mittenegatiivse muutuja ja lisatakse optimaalsesse simplekstabelisse.
Lahendame ülesande dual simplex meetodi abil. Kui laiendatud ülesande uus optimaalne plaan on täisarv, on probleem lahendatud. Kui lahendus on mittetäisarv, peate kordama Gomori meetodi algoritmi, kuni saadakse täisarv.
Näide.
Gomori meetodi abil leidke lahendus täisarvulise programmeerimise probleemile, mis seisneb funktsiooni maksimaalse väärtuse määramises 
arvestades seda
Lahendus. Ebavõrdsuse tasandamine abimuutujate abil X 3 , X 4, saame lineaarse programmeerimise probleemi kanoonilisel kujul:
Lineaarse programmeerimise ülesande lahendame simpleksmeetodil, kasutades samm-sammult üleminekut ühelt aluselt teisele. Probleemi lahendamise käik ja sellest tulenev optimaalne lahendus on toodud tabelites.
|
KOOS B |
KOOS 2 =11 | |||||
|
| ||||||
|
∆ j =Z j - KOOS j | ||||||
|
KOOS B |
KOOS 2 =11 | |||||
|
| ||||||
|
|
|
| ||||
|
∆ j =Z j - KOOS j |
|
|
| |||
Leitud optimaalses plaanis muutuja väärtus X 2 on võrdne murdarvuga. Leiame selle murdosa ja muutujat sisaldava rea kõigi elementide murdosad X 2, nimelt:
Nüüd koostame murdosade leitud väärtuste jaoks Gomori ebavõrdsuse:
.
X 5, nihutame võrrandi vaba liikme paremale poole ja saame uue piirangu:
.
Lisame simplekstabelisse uut piirangut sisaldava rea ja uut muutujat sisaldava veeru ning jätkame ülesande lahendamist dual simplex meetodil, kuna pseudoplaan on nüüd tabelisse kirjutatud.
|
| |||||||
|
|
|
| |||||
|
|
|
| |||||
|
∆ j =Z j –KOOS j |
|
|
| ||||
|
KOOS B |
KOOS 2 =11 | ||||||
|
|
|
|
|||||
|
|
|
||||||
|
∆ j =Z j –KOOS j |
|
|
|||||
Saadud laiendatud ülesande optimaalne lahendus sisaldab muutuja mittetäisarvulist väärtust X 1, seega leiame selle rea jaoks kõigi mittetäisarvude murdosad, nimelt:
ja uuel Gomory ebavõrdsusel on vorm: 
Võrdsustame Gomori võrratuse uue abimuutuja abil X 6, nihutame võrrandi vaba liiget paremale ja saame uue piirangu: 
.
Lisame selle lahendatavale probleemile, joondame abimuutuja abil ja lahendame laiendatud ülesande
|
KOOS B |
KOOS 2 =11 | |||||||
|
|
|
| ||||||
|
|
| |||||||
|
|
|
| ||||||
|
∆ j =Z j –KOOS j |
|
| ||||||
|
KOOS B |
KOOS 2 =11 | |||||||
|
∆ j =Z j –KOOS j | ||||||||
Seega on täisarvulise programmeerimise probleemile leitud optimaalne lahendus: Z max=11 kl 
.
Märkmed :
Kui lahendusprotsessi käigus ilmub simplekstabelisse mittetäisarvulise komponendiga võrrand 
ja täisarvu koefitsiendid piirangute süsteemi vastaval real 
, siis sellel ülesandel pole täisarvulist lahendust.
Meetod põhineb simpleksmeetodil, mille abil leitakse optimaalne lahendus ilma täisarvu tingimusi arvestamata. Kui saadud plaan sisaldab vähemalt ühte murdosa, siis kehtestatakse täiendav piirang ja arvutused jätkuvad taas simpleksmeetodil.
Protsess jätkub, kuni kõik plaani komponendid on täisarvud või näidatakse, et ülesandel pole täisarvulist lahendust.
Olgu X* = (x1, x2, …, xm, …, xn) simpleksmeetodil leitud optimaalne plaan, kus aluseks on vektorid A1, A2,…, Am. Olgu xi murdarv (arv i-nda rea veerus B). Siis on võimalik, et i-ndal real:
1. kõik xij on täisarvud, see tähendab, et ülesandel ei ole täisarvulist lahendust
2. mõned xij on murdarvulised
Olgu [xi] ja [xij] arvude xi ja хij täisarvulised osad ning (xi) ja (хij) murdosad.
Tähistame qi = (хi) ja qij = (хij) ning koostame erinevused.
(qi1Х1+ qi1Х2+…+ qi1Хn) – qi ≥0
Teisendame võrratuse võrrandiks, korrutades selle (-1) ja lisades uue muutuja Xn+1 ning lisades simplekstabelisse (ja seega ka veergu) uue rea. Edasi lahendame dual simplex meetodil, kui leitud plaan ei ole täisarv, siis kordame simplekstabelisse uue muutuja, rea ja veeru lisamise protsessi.
Kui optimaalses plaanis on mitu mittetäisarvu komponenti, siis maksimaalsele qi-le loome täiendava piirangu.
Teid huvitava teabe leiate ka teaduslikust otsingumootorist Otvety.Online. Kasutage otsinguvormi:
Veel teemast 47 Gomori meetod: peamised ideed ja algoritmi lühikirjeldus. Täiendava piirangu kehtestamise majanduslik mõte:
- 25.Majandusjuhtimise meetodid, nende sihtotstarve. Majandusliku mõjutamise meetodite liigid ja põhisisu. Majandusmeetodite rakendamise lühikirjeldus ja tunnused
