|
|
Milan Hladík
|
Celočíselné programování - příklady
|
|
|
|
Nejprve uvedeme několik ilustračních příkládků v GAMSu:
První příklad.
Rozpis provozu výroby. Továrna vyrábí 3 typy aut: typ A, typ B a typ C. Výraba auta prochází jednotlivými provozy: slévárnou, úpravnou odlitků, lisovnou a montáží. Známe denní kapacity jednotlivých provozů, montáží a ceny jednotlivých typů aut. Kolik máme vyrábět jakých druhů aut, abychom maximalizovali výdělek?
| kapacita provozů jen pro daný typ | typ A | typ B | typ C |
| slévárna | 100 | 125 | 75 |
| úpravna odlitků | 150 | 125 | 100 |
| lisovna | 125 | 100 | 100 |
| montáž typu A | 75 | 0 | 0 |
| montáž typu B | 0 | 80 | 0 |
| montáž typu C | 0 | 0 | 80 |
| cena | 4500 | 4000 | 6000 |
Zdrojový soubor pro řešení v GAMSu je k dispozici zde, výsledek (jeho nejdůležitější část) pak zde. Z výsledku můžeme vyčíst, že GAMS jeho řešič použil BDMLP, výpočet trval 0.164s CPU, optimální řešení je: 1 auto typu A, 62 aut typu B a 37 typu C. Denní výdělek činí 474500 peněžních jednotek. Bez podmínek celočíselnosti by vyšel výsledek (0,62.5,37.5).
Druhý příklad
se týká dopravního problému s pevnými cenami. Máme optimalizovat převoz zboží mezi zdroji (kapacity v "a.dat") a spotřebiteli (kapacity v "b.dat") tak, aby cena převáženého zboží byla minimální. Na rozdíl od klasického doporavního problému se zde cena převozu zboží mezi zdrojem a spotřebitelem počítá jako přímá úměra převáženého zboží (koeficienty v "c.dat") plus nějaká základní sazba za to, že se něco převáží (sazby v "d.dat"). Zdrojový soubor (s přípodou ".gms") a soubory se vstupními daty:
Výsledek program ukládá do souboru s příponou ".lst", zde uvádíme část výpisu řešení naší úlohy. Dozvíme se tam optimální řešení, otimální hodnotu účelové funkce (=9929.5), doba tvrání 0.35s CPU. Použitý řešič byl CPLEX, protože jsme si ho ve zdrojovém kodu vyžádali. Jinak by se použit defaultně BDMLP a trvalo by mu to podstatně déle (145s CPU).
Třetí příklad
Tentokrát na nelineární celočíselné programování. Úloha má název: Optimální rozmístění zařízení kuchyně. V kuchyni máme na m míst umístit m kusů zařízení. Máme k dispozici tabulku d(i,j) vzdáleností mezi jednotlivými místy a f(k,l) frekvencí přechodů mezi zařízeními k a l. Úkolem je rozmístit zařízení po kuchyni tak, abychom se co nejméně nachodili. Zdrojové řešení v GAMSu pro určité konkrétní hodnoty je zde, výsledek je zde. GAMS použil řešič DICOPT a po 1.578s CPU vydal výsledek (na místě 1, 2 resp. 3 bude 1., 3. resp. 2. zařízení).
Další příklady (v angličtině) najdete zde.
A nyní úkoly pro vás:
Úloha 1.
Průvodčí vykonávají 8-hodinové služby s nástupem buď v 0, 4, 8, 12, 16 nebo 20 hodin. Určete minimální počet průvodčích, jestli počet průvodčích nutný na provoz dané směny je dán následovně
| směna | nutný počet průvodčích |
| 0-4 hodin | 3 |
| 4-8 hodin | 8 |
| 8-12 hodin | 10 |
| 12-16 hodin | 8 |
| 16-20 hodin | 4 |
| 20-0 hodin | 5 |
Úloha 2.
Optimální dělení materiálu. Pro stavbu je potřeba 640 kusů ocelových prutů o délce 70cm, 500 kusů o délce 130cm a 200 kusů o délce 260cm. K dispozici máme pouze ocelové pruty o délce 4m. Kolik minimálně je zapotřebí těchto čtyřmetrových prutů, abychom po jejich rozřezání získali požadované díly?
Příklady z oblasti grafů:
Úloha 3.
Určete maximální nezávislou množinu v grafu G=(V,E). Maximální nezávislá množina je maximální (co do počtu vrchlů) množina vrcholů takových, že žádné dva nejsou spojeny hranou. Zadané hodnoty:
V={1,...,8}, E={(1,3),(1,5),(1,6),(1,8),(2,3),(2,4),(2,6),(3,6),(3,7),(4,5),(4,7),(5,8),(6,7),(6,8)}.
Úloha 4.
Určete maximální párování ve váženém úplném bipartitním grafu (V1,V2) (tj. hrany vedou právě mezi vrcholy z V1 a V2), kde
V1={1,...,5}, V2={1,...,7} a hrany jsou váženy takto (matice vah mezi V1 a V2):
| 12 | 3 | 8 | 26 | 4 | 16 | 2 |
| 30 | 25 | 9 | 3 | 0 | 17 | 5 |
| 0 | 14 | 28 | 20 | 7 | 22 | 34 |
| 40 | 35 | 0 | 33 | 13 | 25 | 35 |
| 11 | 53 | 19 | 0 | 31 | 20 | 13 |
Úloha 5.
Určete maximální kliku (tj. maximální úplný podgraf) G=(V,E). Zadané hodnoty:
V={1,...,9}, E={(1,2),(1,5),(1,6),(1,9),(2,3),(2,4),(2,8),(3,5),(3,7),(4,6),(4,7),(5,8),(6,7),(6,9),(8,9)}.
Úloha 6.
Určete barevnost v grafu G=(V,E). Barevností rozumíme nejmenší počet barev nutných k obarvení vrcholů tak, aby vrcholy spojené barvou neměly stejnou barvu. Zadané hodnoty:
V={1,...,8}, E={(1,3),(1,4),(1,5),(1,8),(2,3),(2,6),(2,8),(3,5),(3,8),(4,6),(5,7),(5,8),(6,8),(7,8)}.
Úloha 7.
Varianta obchodního cestujícího: máme n=6 měst, musíme vyjí z města 1 a vrátit se do něj zpátky, ale nemusíme navštívit všechna města. Za návštěvu města i máme profit f(i), cesta mezi městy i,j má náklady C(i,j). Řešením je uzavřená cesta s maximálním ziskem. Řešte pro data
| 0 | 2 | 8 | 16 | 3 | 4 |
| 2 | 0 | 6 | 4 | 3 | 8 |
| 8 | 6 | 0 | 10 | 12 | 9 |
| 16 | 4 | 10 | 0 | 5 | 7 |
| 3 | 3 | 12 | 5 | 0 | 13 |
| 4 | 8 | 9 | 7 | 13 | 0 |
f=(0,19,13,1,8,12), C=
|