Zostavenie ďalšej reštrikčnej metódy gomori. Celočíselné modely lineárneho programovania

Ekonomická a geometrická interpretácia problému celočíselné programovanie. Extrémny problém, ktorého premenné nadobúdajú iba celočíselné hodnoty, sa nazýva problém celočíselného programovania.

V matematickom modeli celočíselnej úlohy programovanie cieľová funkcia aj funkcie v systéme obmedzení môžu byť lineárne, nelineárne a zmiešané. Obmedzíme sa na prípad, keď cieľová funkcia a systém obmedzení problému sú lineárne.

Príklad 20.

V dielni podniku sa rozhodlo o inštalácii dodatočného vybavenia, pre ktoré bol pridelený priestor. Podnik môže minúť 10 000 rubľov na nákup vybavenia, zatiaľ čo si môže kúpiť dva typy zariadení. Sada zariadení typu I stojí 1 000 rubľov a typu II - 3 000 rubľov. Nákup jednej sady zariadení typu I vám umožňuje zvýšiť výkon za zmenu o 2 jednotky a jednej sady zariadení typu II - o 4 jednotky. S vedomím, že inštalácia jednej sady zariadení typu I vyžaduje 2 m 2 plochy a zariadenia typu II - 1 m 2 plochy, určte takú sadu doplnkových zariadení, ktorá umožňuje maximalizovať výkon.

Riešenie. Poďme skladať matematický modelúlohy. Predpokladajme, že spoločnosť nakúpi x 1 súprav zariadení typu I a súpravy zariadení typu II. Potom premenné x 1 a musia spĺňať nasledujúce nerovnosti:

Ak podnik získa špecifikované množstvo zariadení, celkový nárast produkcie bude

Premenné x 1 a môžu podľa ekonomického obsahu nadobúdať len celočíselné nezáporné hodnoty, t.j.

x 1 sú celé čísla. (73)

Dostávame sa teda k ďalšiemu matematický problém: nájsť maximálna hodnota lineárna funkcia (71) za podmienok (70), (72) a (73). Keďže neznáme môžu nadobúdať iba celočíselné hodnoty, problém (70) - (73) je problém celočíselného programovania. Keďže počet neznámych v úlohe je dva, riešenie tejto úlohy možno nájsť pomocou jej geometrickej interpretácie. Na to najskôr zostrojíme mnohouholník riešení úlohy, ktorý spočíva v určení maximálnej hodnoty lineárnej funkcie (71) za podmienok (70) a (72) (obr. 11). Súradnice všetkých bodov polygónu zostrojeného riešenia OAEMU uspokojiť systém lineárne nerovnosti(70) a podmienka nezápornosť premenné (72). Zároveň podmienka (73), teda podmienka celé čísla premenné spĺňajú súradnice len 12 bodov označených na obr. 11. Aby sme našli bod, ktorého súradnice určujú riešenie pôvodnej úlohy, nahradíme mnohouholník OABC mnohouholník OKEMNF, ktorá obsahuje všetky platné body s celočíselnými súradnicami a také, že súradnice každého z vrcholov sú celé čísla. Ak teda nájdeme maximálny bod funkcie (71) na polygóne OKEMNF, potom súradnice tohto bodu určia optimálny plán problému.

Na tento účel zostrojíme aj priamku prechádzajúcu polygónom riešenia OKEMNF(číslo 12 sa berie ľubovoľne). Zostrojenú čiaru posúvame v smere vektora, kým neprejde cez poslednú spoločný bod to s daným polygónom. Súradnice tohto bodu určujú optimálny plán a hodnotu objektívna funkcia v ňom je maximum.

IN tento prípad požadovaný bod je E(1; 3), v ktorom má účelová funkcia maximálnu hodnotu С Preto súradnice bodu E určiť optimálny plán problému (70) - (73). V súlade s týmto plánom by mal podnik zakúpiť jednu sadu zariadení typu 1 a tri sady zariadení typu II. To poskytne podniku existujúce obmedzenia týkajúce sa výrobných oblastí a hotovosť maximálne zväčšenie výstup rovný 14 jednotkám. v smene.

Príklad 21.

Dá sa použiť na prácu P mechanizmov. Výkon i-tý mechanizmus pri vykonávaní j – práca sa rovná . Za predpokladu, že každý stroj je možné použiť iba v jednej úlohe a každú úlohu môže vykonávať iba jeden stroj, určite priradenie strojov k úlohám, ktoré zaisťujú maximálnu produktivitu. Zostavte matematický model problému.

Riešenie. Zavedme premennú x ij , ktorej hodnota sa rovná 1, ak počas vykonávania i-tý použitá práca j – mechanizmus a inak je 0. Potom sú podmienky pre použitie každého mechanizmu len na jednej úlohe vyjadrené rovnosťami

(74)

a podmienky výkonu práce len jedným mechanizmom - rovnosťami

(75)

Problémom je teda určiť takéto hodnoty neznámych splnenie sústavy rovníc (74) a (75) a podmienky (76), pri ktorých je maximálna hodnota funkcie

Formulovaný problém je problém celočíselného programovania.

Určenie optimálneho plánu pre problém celočíselného programovania. Zvážte problémy celočíselného programovania, v ktorých sú cieľová funkcia aj funkcie v systéme obmedzení lineárne. V tejto súvislosti formulujeme hlavný problém lineárne programovanie, v ktorom premenné môžu nadobúdať iba celočíselné hodnoty. Vo všeobecnosti možno tento problém napísať takto: nájdite maximum funkcie

za podmienok

(79)

- celé (81)

Ak sa nájde riešenie problému (78) – (81) simplexná metóda, potom to môže alebo nemusí byť celé číslo (príklad , ktorého riešenie je vždy celé číslo, je dopravná úloha). Vo všeobecnom prípade sú na určenie optimálneho plánu pre problém (78) - (81) potrebné špeciálne metódy. V súčasnosti existuje niekoľko takýchto metód, z ktorých najznámejšia je Gomoryho metóda, ktorý je založený na simplexnej metóde opísanej vyššie.

Gomoryho metóda. Hľadanie riešenia problému celočíselného programovania metódou Gomory začína určením optimálneho plánu problému (78) - (80) simplexovou metódou bez zohľadnenia celé čísla premenné. Po nájdení tohto plánu sa zobrazia jeho komponenty. Ak medzi komponentmi nie sú žiadne zlomkové čísla, nájdený plán je optimálnym plánom pre problém celočíselného programovania (78) - (81). Ak v optimálnom pláne úlohy (78) - (80) premenná nadobúda zlomkovú hodnotu, potom sa nerovnosť pridá do systému rovníc (79)

(82)

a nájdite riešenie problému (78) – (80), (82).

V nerovnosti (82) a – transformované počiatočné veličiny a ktorých hodnoty sú prevzaté z poslednej simplexnej tabuľky a a – zlomkové časti čísel (zlomková časť nejakého čísla a sa chápe ako najmenšie nezáporné číslo b taký, že rozdiel medzi ale A b je celé číslo). Ak v optimálnom pláne problému (78) - (80) zlomkové hodnoty obsahujú niekoľko premenných, potom sa určí dodatočná nerovnosť (82) najväčší zlomkovýčasť.

Ak v pláne nájdeného problému (78) - (80), (82) premenné nadobúdajú zlomkové hodnoty, potom sa opäť pridá jedno ďalšie obmedzenie a proces výpočtu sa zopakuje. Uskutočnením konečného počtu iterácií sa buď získa optimálny plán úlohy celočíselného programovania (78) - (81), alebo sa zistí jej neriešiteľnosť.

Ak požiadavka celé čísla(81) platí len pre niektoré premenné, vtedy sa takéto problémy nazývajú čiastočne celé číslo. Ich riešenie sa tiež nachádza sekvenčným riešením problémov, z ktorých každý sa získa z predchádzajúceho zavedením dodatočného obmedzenia. V tomto prípade má toto obmedzenie tvar

kde sú určené z nasledujúcich vzťahov:

1) pre , ktorý môže mať iné ako celočíselné hodnoty,

(84)

2) pre , ktorý môže nadobúdať iba celočíselné hodnoty,

(85)

Z uvedeného vyplýva, že proces určenia optimálneho plánu pre problém celočíselného programovania metódou Gomory zahŕňa nasledovné hlavné etapy:

1. Pomocou simplexovej metódy nájdite riešenie problému (78) - (80) bez zohľadnenia požiadavky celé čísla premenné.

2. Zostavte dodatočné obmedzenie pre premennú, ktorá má v optimálnom pláne problému (78) - (80) maximálne zlomkové a v optimálnom pláne problému (78) - (81) by mali byť celé čísla.

3. Pomocou dual nájdite riešenie problému získaného z úlohy (78) - (80) ako výsledok pridania dodatočného obmedzenia.

4. Ak je to potrebné, vytvorte ešte jedno dodatočné obmedzenie a pokračujte v iteračnom procese, kým sa nezíska optimálny plán pre problém (78) - (81) alebo kým sa nezistí jeho neriešiteľnosť.

Príklad 22.

Pomocou Gomoriho metódy nájdete maximálnu hodnotu funkcie

za podmienky

(87)

– celé (89)

Riešenie. Na určenie optimálneho plánu pre problém (86) - (89) najskôr nájdeme optimálny plán pre problém (86) - (88) (tabuľka 22).

Tabuľka 22

		C b	R 0

Ako je možné vidieť z tabuľky. 22, našiel optimálny plán problém (86) - (88) nie je optimálnym plánom pre úlohu (86) - (89), pretože tieto dve zložky a majú neceločíselné hodnoty. V tomto prípade sa zlomkové časti týchto čísel navzájom rovnajú. Preto je pre jednu z týchto premenných vytvorené ďalšie obmedzenie. Zostavme si napríklad také obmedzenie pre premennú Z poslednej simplexovej tabuľky (tabuľka 22) máme

K systému obmedzení problému (86) – (89) teda pridáme nerovnosť

alebo

Tabuľka 23

		C b	R 0

Teraz nájdeme maximálnu hodnotu funkcie (86) pri podmienkach (87), (88) a (90) (tabuľka 23).

To ukazuje tabuľka 23 počiatočná úloha celočíselné programovanie má optimálny plán P V tomto pláne sa hodnota účelovej funkcie rovná . Uveďme geometrickú interpretáciu riešenia úlohy. Oblasťou realizovateľných riešení úlohy (86) - (88) je mnohouholník OABCD(obr. 12). Z obr. 12 ukazuje, že účelová funkcia nadobúda maximálnu hodnotu v bode OD(19/2; 7/2), zväzok e. čo X =(19/2; 7/2; 0; 0; 34) je optimálny plán. Je to priamo zrejmé z tabuľky 22. Od r X= (19/2; 7/2; 0; 0; 34) nie je optimálny plán pre problém (86) - (89) (čísla a sú zlomkové), potom sa zavedie ďalšie obmedzenie. Vylúčením z nej a nahradením zodpovedajúcich hodnôt z rovníc systému obmedzení (87) získame medzu z polygónu. OABCD trojuholník EFC.

Ako je možné vidieť na obr. 12 je oblasťou možných riešení získaného problému mnohouholník OABEFD. V bode E(9; 4) tohto mnohouholníka má účelová funkcia tohto problému maximálnu hodnotu. Od súradníc bodu E sú celé čísla a neznáme a nadobudnú celočíselné hodnoty, keď sa hodnoty a dosadia do rovnice (87), potom je optimálny plán pre problém (86) – (89). Vyplýva to z tabuľky 23.

Príklad 23.

Pomocou Gomoryho metódy nájdite riešenie problému, ktoré spočíva v určení maximálnej hodnoty funkcie

za podmienok

- celý. (94)

Uveďte geometrickú interpretáciu riešenia problému.

Riešenie. Sformulovaný problém prepíšeme takto: nájdite maximálnu hodnotu funkcie

za podmienok

(96)

- celý. (98)

Problém (95) - (98) je čiastočne celý, pretože premenné a môžu nadobúdať neceločíselné hodnoty.

Simplexovou metódou nájdeme riešenie úloh (95) - (97) (tabuľka 24).

Tabuľka 24

		C b	R 0
		C b	R 0
							–1/3 nie je plán úloh (95) – (98), keďže premenná

Podstatou metód rezania je, že problém sa najskôr vyrieši bez celočíselnej podmienky. Ak je výsledný plán celé číslo, problém je vyriešený. V opačnom prípade sa k obmedzeniam úlohy pridá nové obmedzenie s nasledujúcimi vlastnosťami:

Musí byť lineárny

· musí odrezať nájdený optimálny neceločíselný plán;

· by nemal prerušiť žiadny celočíselný plán.

Ďalšie obmedzenie, ktoré má tieto vlastnosti, sa nazýva správne orezanie.

Geometricky pridanie každého lineárneho obmedzenia zodpovedá nakresleniu priamky (nadroviny), ktorá odreže určitú časť polygónu riešenia (mnohosten) spolu s neceločíselnými súradnicami, ale neovplyvní žiadny z celočíselných bodov tohto mnohostenu. Výsledkom je, že nový rozhodovací mnohosten obsahuje všetky celočíselné body obsiahnuté v pôvodnom rozhodovacom mnohostene a teda optimálne riešenie získané s týmto mnohostenom bude celočíselné (obr. 6.24).

Jeden z algoritmov na riešenie problému lineárneho celočíselného programovania (6.59)…(6.62), navrhnutý Gomorym, je založený na simplexovej metóde a používa pomerne jednoduchý spôsob na zostrojenie správneho rezu.

Ryža. 6.18. Grafické znázornenie celočíselné riešenie

Nech má úloha lineárneho programovania (6.52)…(6.55) konečné optimum a posledný krok jeho riešením simplexovou metódou sa získajú nasledujúce rovnice vyjadrujúce hlavné premenné prostredníctvom neprimárnych premenných optimálne riešenie

(6.56)

takže optimálne riešenie úlohy (6.52)…(6.55) je , kde napr. i je neceločíselná zložka. V tomto prípade možno dokázať, že nerovnosť

tvorený i rovnica systému (6.56), má všetky vlastnosti správneho rezania.

V nerovnosti (6.57) je symbol označujúci zlomkovú časť čísla. číslo ale sa nazýva kongruentné s číslom v(označené ) vtedy a len vtedy, ak je rozdiel ale- v− celé číslo.

celá časť čísla ale sa nazýva najväčšie celé číslo nepresahujúce ale. Zlomková časť čísla je definovaná ako rozdiel medzi týmto číslom a jeho číslom celá časť, t.j. . Napríklad pre = 2, ; pre = -3 a .

Na vyriešenie problému celočíselného lineárneho programovania (6.52)…(6.55) Gomoryho metódou sa používa nasledujúci algoritmus:

1. Použite simplexovú metódu na vyriešenie úlohy (6.52)…(6.55) bez zohľadnenia podmienky celistvosti. Ak sú všetky zložky optimálneho plánu celočíselné, potom je optimálny aj pre problém celočíselného programovania (6.52)…(6.55). Ak je prvá úloha (6.52)…(6.54) neriešiteľná (teda nemá konečné optimum alebo sú jej podmienky protichodné), potom je neriešiteľná aj druhá úloha (6.52)…(6.55).

2. Ak sú medzi zložkami optimálneho riešenia neceločíselné zložky, vyberte zložku s najväčšou integrálnou časťou a pomocou zodpovedajúcej rovnice sústavy (6.56) vytvorte správnu hranicu (6.57).

3. Nerovnosť (6.57) zavedením ďalšej nezápornej celočíselnej premennej sa transformuje na ekvivalentnú rovnicu

a zahrnúť ho do systému obmedzení (6.53).

4. Vyriešte výsledný rozšírený problém pomocou simplexnej metódy. Ak je nájdený optimálny plán celé číslo, potom je problém celočíselného programovania (6.52)…(6.55) vyriešený. V opačnom prípade sa vráťte na krok 2 algoritmu.

Ak je problém riešiteľný v celých číslach, potom sa po konečnom počte krokov (iterácií) nájde optimálny celočíselný plán.

Ak sa v procese riešenia objaví rovnica (vyjadrujúca hlavnú premennú z hľadiska nebázických) s neceločíselným voľným členom a celými inými koeficientmi, potom zodpovedajúca rovnica nemá riešenie v celých číslach. V tomto prípade a zadanú úlohu nemá celočíselné optimálne riešenie.

Nevýhodou Gomoriho metódy je požiadavka celých čísel pre všetky premenné – ako hlavné (vyjadrujúce napr. v probléme využitia zdrojov produkčnej jednotky), tak aj doplnkové premenné (vyjadrujúce množstvo nevyužitých zdrojov, ktoré môže byť zlomkové).

Všimnite si, že prechod na kanonická forma v plne celočíselnom probléme lineárneho programovania, ktorý obsahuje obmedzenia − nerovnice

nevedie, všeobecne povedané, k úplne celočíselnému problému v kanonickej forme, pretože v transformovaných obmedzeniach (6.59)

pomocné premenné x n + i nepodliehajú požiadavke na celé číslo.

Ak však všetky koeficienty aij, b i v (6.59) sú celé čísla, potom môže byť podmienka celého čísla rozšírená na x n + i ako pri riešení príkladu 6.10.

Úplný celočíselný problém v kanonickom tvare možno získať aj vtedy, ak v (6.59) aij, b i− racionálne čísla. Za týmto účelom vynásobte (6,59) spoločným násobkom menovateľov koeficientov − aij, b i(t. j. prejdite na celočíselné koeficienty v (6.59)) a až potom zaveďte pomocné premenné .

Príklad 6.20. Vyriešte problém úplného celočíselného programovania

pod obmedzeniami

Riešenie. Prenesme problém do kanonickej formy zavedením ďalších nezáporných premenných . Dostávame systém obmedzení:

Úlohu riešime simplexnou metódou. Pre názornosť riešenie znázorníme graficky (obr. 6.19).

Ryža. 6.19. Grafické znázornenie riešenia problému

Na obr. 6,19 0 KLM je oblasť prípustných riešení problému ohraničené priamkami (1), (2), (3) a súradnicovými osami; L(2/3;8) – bod optimálneho, ale neceločíselného riešenia úlohy ; (4) je priamka, ktorá oddeľuje toto neceločíselné riešenie; 0 KNM je doménou prípustných riešení rozšíreného problému (6.64") N(2; 7) je bod optimálneho celočíselného riešenia.

krokujem

	X 1	X 2
X 3
X 4
X 5

Prvé základné riešenie X 1 = (0;0;60;34;8) - platné. Zodpovedajúca hodnota lineárnej funkcie f 1 = 0.

Premennú preložíme na hlavné premenné X 2, ktorý je zahrnutý vo vyjadrení lineárnej funkcie s najväčším kladným koeficientom. Nájdenie maximálnej možnej hodnoty premennej X 2, ktorý nám umožňuje prijať systém obmedzení, z podmienky minima zodpovedajúcich pomerov:

,

tie. tretia rovnica je riešenie (zvýraznené). o X 2 = 8 v tejto rovnici X 5 = 0 a prechádza do nezákladných premenných X 5 .

II krok. Základné premenné ; vedľajšie premenné.

	X 1	X 5
X 3		-5
X 4		-4
X 2
		-3	-24

X 2 = (0;8;20;2;0); f= 24. Preveďte na hlavné premenné X 1 , a v malom X 4 .

W krok. Základné premenné ; vedľajšie premenné. Po transformáciách dostaneme:

	X 4	X 5				X 4	X 5
X 3	-3	-3		X 3	-1	-1
X 1		-4		X 1	1/3	-4/3	2/3
X 2				X 2
	-2	-1	-76		-2/3	-1/3	-76/3

Základné riešenie X 3 je pre danú úlohu optimálna , keďže vo vyjadrení lineárnej funkcie neexistujú žiadne nebázické premenné s kladnými koeficientmi.

Avšak rozhodnutie X 3 nespĺňa podmienku celého čísla (6,55"). Podľa prvej rovnice s premennou X 1 , ktorý v optimálnom riešení (2/3) dostal neceločíselnou hodnotu, vytvoríme dodatočné obmedzenie (6.57):

Upozorňujeme na skutočnosť, že podľa (6.56) a (6.57) berieme zlomkovú časť voľného člena s rovnakým znamienkom, aký má v rovnici, a zlomkové časti koeficientov pre nebázické premenné X 4 a X 5 - s opačnými znamienkami.

Vzhľadom k tomu, zlomkové časti

potom zapíšeme poslednú nerovnosť do tvaru

Zavedením ďalšej celočíselnej premennej X 6 ≥ 0, dostaneme rovnicu ekvivalentnú nerovnosti (6,57")

Rovnica (6.58) musí byť zahrnutá do systému obmedzení (6.56") originálu kanonický problém a potom zopakujte postup riešenia úlohy simplexovou metódou vo vzťahu k rozšírenému problému. V tomto prípade, aby sa znížil počet krokov (iterácií), sa odporúča zaviesť do systému získanom v poslednom kroku riešenia úlohy dodatočnú rovnicu (6,58") (bez celočíselnej podmienky).

IV krok. Základné premenné ; vedľajšie premenné.

	X 4	X 5
X 1	1/3	-4/3	2/3
X 2
X 3	-1	-1
X 6	-1/3	-2/3	-2/3
	-2/3	-1/3	-76/3

Základné riešenie − neprijateľné. Všimnite si, že po zahrnutí ďalšej rovnice zodpovedajúcej správnej hranici do systému obmedzení sa vždy získa neplatné základné riešenie.

Na získanie prijateľného základného riešenia je potrebné previesť na hlavnú premennú, ktorá vstupuje do rovnice s kladným koeficientom, v ktorej je voľný člen záporný, t.j. X 4 resp X 5 (v tomto štádiu sa lineárna funkcia neuvažuje). Prekladáme do hlavných, napríklad premennú X 5 .

V krok. Základné premenné ; vedľajšie premenné. Po transformáciách dostaneme:

	X 4	X 6				X 4	X 6
X 1	-6/9	4/3	-12/9	X 1		-2
X 2	1/3	-1	-14/3	X 2	-1/2	3/2
X 3	1/3		38/3	X 3	-1/2	-3/2
X 5	-1/3		-2/3	X 5	1/2	-3/2
	3/9	1/3	150/9		-1/2	-1/2	-25

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

Keďže vo vyjadrení lineárnej funkcie nie sú žiadne hlavné premenné s kladnými koeficientmi, potom X 5 je optimálne riešenie.

takze f max = 25 pre optimálne celočíselné riešenie Šiesta zložka nemá žiadny zmysluplný význam.

Pre geometrickú interpretáciu v rovine 0 X 1 X 2 (pozri obr. 6.19) orezanie (6,57") vyžaduje premenné, ktoré obsahuje X 4 a X 5 vyjadrovať z hľadiska premenných X 1 a X 2. Dostaneme (pozri 2. a 3. rovnicu systému obmedzení (6.56“):

(pozri odrezanie priamky (4) na obr. 6.19).

Nech je optimálny plán získaný simplexovou metódou pre úlohu (5.1)-(5.3) nasledujúci: a získaný na základe
Potom má posledná simplexná tabuľka nasledujúci tvar:

Tabuľka 5.1

Redukované na základné simplexné tablo pre problém celočíselného programovania

Predstierajme to
zlomkové; potom nejaké
aj zlomkové (inak úloha nemá celočíselné riešenie). Označiť podľa
A
celé časti čísel A , t.j. najväčšie celé čísla nepresahujúce čísla A . Potom hodnoty zlomkových častí A čísla A sú definované ako rozdiely:

kde A

Napríklad,

.

Keďže podľa stavu
sú nezáporné celé čísla, potom je rozdiel tiež nezáporné celé číslo.

Transformácia tejto nerovnosti na rovnicu, odčítaním od jej ľavej strany celočíselnej nezápornej dodatočnej premennej
rovnicu vynásobíme –1, pridáme k poslednému simplexovému tablo a pomocou simplexovej metódy (najlepšie duálnej) nájdeme nový plán. Ak to nie je celé číslo, potom vytvoríme nové dodatočné obmedzenie na poslednej simplexnej tabuľke.

Ak je v optimálnom pláne problému (5.1)-(5.3) niekoľko zlomkových
potom je dodatočné obmedzenie pre max . To urýchľuje proces získania optimálneho celočíselného riešenia.

Zvážte geometrický význam zavedenia dodatočného obmedzenia (pozri obr. 5.2). Nech v bode A roztokový mnohosten Q funkciu Z dosiahne maximálnu hodnotu Z(A)=max, ale súradnice bodu A- zlomkový. Potom sa zaviedli obmedzenia na celé číslo I a II z regiónu Q odrezaná oblasť s rohovým hrotom
, ktorého súradnice sú celé a v ktorom lineárna funkcia dosiahne svoju maximálnu hodnotu.

Obr.5.2. Geometrický význam Gomoryho obmedzenia

Zvážte Gomoryho metódu pomocou príkladu nasledujúceho problému.

Príklad 5.1. Nájdite maximálnu hodnotu funkcie

za podmienok

Uveďte geometrickú interpretáciu riešenia problému.

Riešenie. Aby sme určili optimálny plán pre problém (5.5)-(5.8), najprv nájdeme optimálny plán pre problém (5.5)-(5.7):

Tabuľka 5.2

základ
plánovať
- suboptimálny
.

Tabuľka 5.3

Simplexné tablo zredukované na základ

,
– neoptimálny, základ
,
.

Tabuľka 5.4

Simplexné tablo zredukované na základ

Optimálny plán
, základ
. Tento optimálny plán nie je optimálnym plánom pre problém (5.5)-(5.8), pretože ide o dve zložky A majú neceločíselné hodnoty. V tomto prípade ide o zlomkové časti týchto čísel
sú si navzájom rovné. Preto je pre jednu z týchto premenných vytvorené ďalšie obmedzenie. Zostavme si napríklad takéto obmedzenie pre premennú (častejšie berte prvý riadok). Z poslednej simplexnej tabuľky máme:

.

Pridáme teda nerovnosť

Teraz nájdeme maximálnu hodnotu funkcie (5.5) za podmienok (5.6), (5.7) a (5.9). V podmienke (5.9) zavedieme ďalšiu premennú:

Tabuľka 5.5

Zadanie ďalšej premennej do simplexnej tabuľky

Poďme si vybrať .
základ.

Tabuľka 5.6

Redukcia simplexného tabla na základ

Základ
.
.

Napíšeme optimálny plán pre pôvodný problém:
V tomto pláne sa hodnota účelovej funkcie rovná
.

Geometrická interpretácia riešenia problému.

Obr.5.3. Geometrická interpretácia riešenia problému

Oblasťou prípustných riešení úlohy (5.5)-(5.7) je mnohouholník OABCD(obr. 5.3). Z obrázku je vidieť, že účelová funkcia nadobúda v bode svoju maximálnu hodnotu
tie.
je optimálny plán. Keďže tento plán nie je optimálnym plánom pre problém (5.5)-(5.8) (čísla A – zlomkové), potom sa zavedie ďalšie obmedzenie

Odstránenie tejto nerovnosti A ak namiesto nich nahradíme zodpovedajúce hodnoty z rovníc systému obmedzení (5.6), dostaneme
.

.

Táto nerovnosť zodpovedá polrovine ohraničenej priamkou
odrezaný polygón OABCD trojuholník EFC.

Ako je zrejmé z obrázku, oblasť prípustných riešení získaného problému je mnohouholník OABEFD. V bode E(9;4) tohto mnohouholníka, objektívna funkcia tohto problému nadobúda maximálnu hodnotu. Od súradníc bodu E- celé čísla a neznáme
A vezmite celočíselné hodnoty pri dosadzovaní hodnôt do rovníc (5.6).
A
potom
je optimálny plán pre problém (5.5)-(5.8). Vyplýva to aj z tabuľky simplexnej metódy.

Poznámka k použitiu Gomoryho metódy: ak počiatočný základ problému zahŕňal umelé vektory, potom pri zostavovaní dodatočného obmedzenia je potrebné umelé premenné vynechať.

Otázky na samovyšetrenie

Oblasti použitia celočíselného programovania.

Vyjadrenie problému celočíselného programovania.

Grafický spôsob riešenia problému celočíselného programovania.

Algoritmus Gomoriho metódy.

Pravidlo na zostavenie dodatočného obmedzenia (sekcie Gomory).

Geometrický význam úvodu sekcie Gomory.

Gomoryho metóda sa používa na nájdenie celočíselného riešenia v úlohách lineárneho programovania.
Nech sa nájde riešenie úlohy LP: . Riešenie L i bude celé číslo, ak tie. . (β i) - zlomková časť neceločíselné optimálne riešenie x i , (d i ) - zlomková časť nebázických premenných. Tento pomer určuje (pozri obrázok).

Pridelenie služby. Online kalkulačka sa používa na riešenie problémov celočíselného lineárneho programovania pomocou metódy cutoff. Pri riešení sa používajú simplexné tabuľky. (pozri príklad).

Poučenie. Vyberte počet premenných a počet riadkov (počet obmedzení), kliknite na Ďalej. Výsledný roztok je uložený v Súbor programu Word(pozri príklad riešenia Gomoryho metódou). Okrem toho sa vytvorí šablóna riešenia vo formáte Excel.

Počet premenných 2 3 4 5 6 7 8 9 10
Počet riadkov (počet obmedzení) 2 3 4 5 6 7 8 9 10

V tomto prípade obmedzenia typu x i ≥ 0 neberú do úvahy.

Typy Gomoryho algoritmu

1. Gomoryho prvý algoritmus na riešenie úplne celočíselných problémov.
2. Gomoryho druhý algoritmus pre problémy čiastočne celočíselného lineárneho programovania.

Gomoriho algoritmus pre celočíselné problémy zahŕňa nasledujúce kroky:

1. Problém lineárneho programovania je vyriešený bez zohľadnenia celých čísel.
2. Medzi zlomkovými číslami sa vyberie prvok s najväčšou zlomkovou časťou a urobí sa ďalšie obmedzenie.
3. Nerovnosť sa prevedie na rovnicu zavedením ďalšej nezápornej premennej.
4. Výsledný problém je riešený duálnou simplexovou metódou.

Ak sa v procese riešenia rovnice s neceločíselným voľným členom b i a celočíselnými koeficientmi a ij objaví v simplexovej tabuľke, potom táto úloha nemá celočíselné optimálne riešenie.

Príklad. Výskumné a výrobné združenie "Strela" sa zaoberá výrobou komponentov pre podniky vojensko-priemyselného komplexu. Pri výrobe výrobkov typu A a typu B sa používa oceľ a neželezné kovy. Technologický proces zahŕňa aj spracovanie výrobkov na sústružení a frézky. Podľa technologických noriem na výrobu jedného výrobku typu A a jedného výrobku typu B sa vyžaduje určité množstvo suroviny a určitý počet strojových hodín na spracovanie na strojoch v dielni. Technologické údaje proces produkcie sú uvedené v tabuľke.
Počas mesiaca workshopu má NPO Strela obmedzené zdroje, pokiaľ ide o suroviny a čas strávený vo výrobných dielňach (pozri tabuľku). Zisk z predaja jedného výrobku typu A je 100 rubľov a z jednotky výrobku typu B - 250 rubľov.

	Surový materiál		Práca v obchode, hodinová		Zisk z predaja, rub.
	Neželezné kovy	Oceľ	Sústruženie funguje	Frézovacie práce
Produkt A	10	25	41	90	100
Produkt B	30	25	90	50	250
Zdroje	4500	6250	14100	18000

Nájdite optimálny plán výroby pre NPO "Strela" (počet produktov typu A a typu B - celé čísla), ktorý dáva najväčší zisk.

Riešenie.
Ekonomicko-matematický model problému.
x 1 - plán výroby výrobkov typu A, x 2 - plán výroby výrobkov typu B,
x 1, x 2 sú celé čísla.
Limity zdrojov
10x1 + 30x2 ≤ 4500
25x1 + 25x2 ≤ 6250
41x1 + 90x2 ≤ 14100
90x1 + 50x2 ≤ 18 000
objektívna funkcia
100x1 + 250x2 → max

Vyriešme priamy problém lineárneho programovania simplexovou metódou. V dôsledku toho získame nasledujúci optimálny plán:

Základ	B	x 1	x2	x 3	x4	x5	x6
x2	1450 / 11	0	1	41 / 330	0	-1 / 33	0
x4	17500 / 11	0	0	245 / 66	1	-50 / 33	0
x 1	600 / 11	1	0	-3 / 11	0	1 / 11	0
x6	6500	0	0	55 / 3	0	-20 / 3	1
F(X3)	422500 / 11	0	0	125 / 33	0	50 / 33	0

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

Výsledný optimálny plán nie je celočíselný, preto aplikujeme Gomoryho metóda. Najväčšia zlomková časť je v druhej rovnici pre premennú x 4 (10 / 11). Vytvárame ďalšie obmedzenie:
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 \u003d b 2 - \u003d 1590 10/11 - 1590 \u003d 10/11
q 2 1 = a 2 1 - = 0 - 0 = 0
q 2 2 = a 2 2 - = 0 - 0 = 0
q 2 3 \u003d a 2 3 - \u003d 3 47 / 66 - 3 \u003d 47 / 66
q 2 4 = a 2 4 - = 1 - 1 = 0
q 2 5 \u003d a 2 5 - \u003d -1 17 / 33 + 2 \u003d 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

Pokiaľ ide o duálna simplexná metóda sa používa na nájdenie minima účelovej funkcie, vykonáme transformáciu F(x) = -F(X).

Základ	B	x 1	x2	x 3	x4	x5	x6	x 7
x2	1450 / 11	0	1	41 / 330	0	-1 / 33	0	0
x4	17500 / 11	0	0	245 / 66	1	-50 / 33	0	0
x 1	600 / 11	1	0	-3 / 11	0	1 / 11	0	0
x6	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

Prvá iterácia Gomoryho. 1. Kontrola kritéria optimality. Plán v simplexnej tabuľke je pseudoplán, takže definujeme vodiaci riadok a stĺpec.
2. Definícia novej voľnej premennej. Spomedzi záporných hodnôt základných premenných vyberáme najväčšie modulo. Piaty riadok bude vedúci a premenná x 7 by mala byť vyňatá zo základu.
3. Definícia novej základnej premennej. Minimálna hodnotaθ zodpovedá piatemu stĺpcu, t.j. do základu treba zadať premennú x 5. Na priesečníku vedúceho riadku a stĺpca je rozlišovací prvok (RE) rovný (-16 / 33).

Základ	B	x 1	x2	x 3	x4	x5	x6	x 7
x2	131 9 / 11	0	1	41 / 330	0	-1 / 33	0	0
x4	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
x6	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. Simplexnú tabuľku prepočítame Jordanovou-Gaussovou metódou.

Základ	B	x 1	x2	x 3	x4	x5	x6	x 7
x2	1055 / 8	0	1	27 / 160	0	0	0	-1 / 16
x4	6375 / 4	0	0	95 / 16	1	0	0	-25 / 8
x 1	435 / 8	1	0	-13 / 32	0	0	0	3 / 16
x6	13025 / 2	0	0	225 / 8	0	0	1	-55 / 4
x5	15 / 8	0	0	47 / 32	0	1	0	-33 / 16
F(X0)	-153625 / 4	0	0	-25 / 16	0	0	0	-25 / 8

Vo výslednom optimálnom pláne sú zlomkové čísla. Podľa prvej rovnice s premennou x 2 , ktorá v optimálnom pláne s najväčšou zlomkovou časťou 7/8 získala neceločíselnou hodnotu, zostavíme ďalšie obmedzenie:
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 \u003d b 1 - \u003d 131 7/8 - 131 \u003d 7/8


q 1 3 \u003d a 1 3 - \u003d 27 / 160 - 0 \u003d 27 / 160



q 1 7 \u003d a 1 7 - \u003d -1/16 + 1 \u003d 15/16
Ďalšie obmedzenie vyzerá takto:
7 / 8 - 27 / 160 x 3 - 15 / 16 x 7 ≤ 0
Výslednú nerovnosť transformujeme na rovnicu:
7/8 – 27/160 x 3 – 15/16 x 7 + x 8 = 0
ktorých koeficienty budú zavedené dodatočným riadkom v optimálnom simplexný stôl.

Základ	B	x 1	x2	x 3	x4	x5	x6	x 7	x 8
x2	1055 / 8	0	1	27 / 160	0	0	0	-1 / 16	0
x4	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
x6	13025 / 2	0	0	225 / 8	0	0	1	-55 / 4	0
x5	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

Druhá iterácia Gomroya. 1. Kontrola kritéria optimality. Plán v simplexnej tabuľke je pseudoplán, takže definujeme vodiaci riadok a stĺpec.
2. Definícia novej voľnej premennej. Spomedzi záporných hodnôt základných premenných je najväčším modulom premenná x 8 . Treba to vyňať zo základu.
3. Minimálna hodnota θ zodpovedá siedmemu stĺpcu, t.j. do základu treba zadať premennú x 7.

Základ	B	x 1	x2	x 3	x4	x5	x6	x 7	x 8
x2	131 7 / 8	0	1	27 / 160	0	0	0	-1 / 16	0
x4	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
x6	6512 1 / 2	0	0	28 1 / 8	0	0	1	-13 3 / 4	0
x5	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. Transformácia New Gomory Cuts.

Základ	B	x 1	x2	x 3	x4	x5	x6	x 7	x 8
x2	1979 / 15	0	1	9 / 50	0	0	0	0	-1 / 15
x4	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
x6	19576 / 3	0	0	153 / 5	0	0	1	0	-44 / 3
x5	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

V optimálnom pláne sú zlomkové čísla. Najväčšia zlomková časť premennej x 2 (14 / 15). Robíme dodatočné obmedzenie: 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 \u003d b 1 - \u003d 131 14/15 - 131 \u003d 14/15
q 1 1 = a 1 1 - = 0 - 0 = 0
q 1 2 = a 1 2 - = 1 - 1 = 0
q 1 3 \u003d a 1 3 - \u003d 9/50 - 0 \u003d 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 \u003d a 1 8 - \u003d -1/15 + 1 \u003d 14/15
Ďalšie obmedzenie vyzerá takto:
14/15 - 9 / 50 x 3 - 14 / 15 x 8 ≤ 0
Výslednú nerovnosť transformujeme na rovnicu:
14/15 - 9 / 50 x 3 - 14 / 15 x 8 + x 9 = 0
ktorých koeficienty budú zavedené ako doplnkový riadok v optimálnom simplexovom tablo.

Základ	B	x 1	x2	x 3	x4	x5	x6	x 7	x 8	x9
x2	1979 / 15	0	1	9 / 50	0	0	0	0	-1 / 15	0
x4	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
x6	19576 / 3	0	0	153 / 5	0	0	1	0	-44 / 3	0
x5	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
x9	-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

Tretia iterácia metódou Gomory. Premenná x 9 by sa mala vyňať zo základu. Minimálna hodnota θ zodpovedá ôsmemu stĺpcu, t.j. do základu treba zadať premennú x 8.

Základ	B	x 1	x2	x 3	x4	x5	x6	x 7	x 8	x9
x2	131 14 / 15	0	1	9 / 50	0	0	0	0	-1 / 15	0
x4	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
x6	6525 1 / 3	0	0	30 3 / 5	0	0	1	0	-14 2 / 3	0
x5	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
x9	-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. Vykonajte transformáciu.

Základ	B	x 1	x2	x 3	x4	x5	x6	x 7	x 8	x9
x2	132	0	1	27 / 140	0	0	0	0	0	-1 / 14
x4	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
x6	6540	0	0	234 / 7	0	0	1	0	0	-110 / 7
x5	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

Riešenie sa ukázalo ako celé číslo. Optimálny celočíselný plán možno napísať takto: x 1 \u003d 54, x 2 \u003d 132. F (X) \u003d 38400