4. seminář:
Úlohy celočíselného programování, formulace problému, metoda větví a mezí
Příklad 1: Sestavte matematický model úlohy celočíselného programování a pomocí Řešitele nalezněte optimální řešení (nezapomeňte v Omezujících podmínkách přidat podmínky celočíselnosti):
a) Úloha o bramborách
Potravinářská firma se zabývá zpracováním brambor. Jejími produkty jsou bramborové lupínky, které prodává po 120 Kč/kg, a hranolky po 76 Kč/kg. Na výrobu 1 kg lupínků se spotřebuje 2 kg brambor a 0,4 1 oleje a na výrobu 1 kg hranolků 1,5 kg brambor a 0,2 1 oleje. Navrhněte výrobní program tak, aby byl při nákupních cenách surovin 12 Kč/kg brambor a 40 Kč/l oleje maximální ZISK (zanedbáme náklady na práci, energii, apod.) a přitom nebyla překročena kapacita dodavatele (100 kg brambor a 16 1 oleje). Jak se změní optimální řešení, je-li odběratel ochoten odebírat zboží pouze v baleních (lupínky á 3kg a hranolky á 15kg)?
b) Úloha o řezném plánu
Firma vyrábějící kovové součástky nakupuje v libovolném množství trubky o délce 65 cm. K výrobě součástek potřebuje alespoň 1200 ks trubek o délce 20 cm a alespoň 900 ks trubek o délce 15 cm. Jakým způsobem má firma rozřezat nakoupené trubky tak, aby spotřeba nakoupeného materiálu byla minimální?
c) Úloha o dopravě
Dopravní společnost v městě S zásobuje paletovaným zbožím 4 stejně vzdálená sousední města A, B, C a D. Dnes má rozvézt 110 palet do města A, 70 do B, 58 do C a 62 do D. Má dva typy nákladních aut s fixními cenami jízdy: 6 malých aut s kapacitou 33 palet a cenou jízdy 120 Kč a 4 velká auta s kapacitou 60 palet a cenou jízdy 190 Kč. Každé auto stihne za den jen jednu cestu. Která auta mají kam jet, aby cena dopravy byla minimální?
d) Úloha o pracovním rozvrhu služeb
Správa sbírkového fondu a provozní potřeba galerie vyžadují, aby v jednotlivých dnech byly v galerii ve službě tyto počty osob:
PO	UT	ST	ČT	PA	SO	NE
22	17	13	14	15	18	24
Pracující nastupují do zaměstnání tak, že odpracují vždy 5 po sobě jdoucích dní, po kterých následují dva dny volna. Nástupy se mohou uskutečnit kterýkoliv den v týdnu.
Úkolem je stanovit co nej menší počet zaměstnanců a rozvrhnout jejich nástupy do 5-denních pracovních cyklů tak, aby byly každý den v týdnu pokryty provozní potřeby.
e) Úloha o zakázkách
Podnik může převzít 6 různých zakázek, které se liší spotřebou času výrobního zařízení. Je znám zisk z jednotlivých zakázek a materiálová spotřeba. Zásoba materiálu a času je omezená. Parametry zakázek jsou shrnuty v tabulce:
č. zakázky		1	2	3	4	5	6	disponibilní kapacita
zisk		11	63	9	5	4	8	—> max.
spotřeba času	směny]	1	7	1	1	1	5	15 směn
spotřeba materiálu [kg]		15	70	10	5	3	2	lOOkg
Navrhněte, které zakázky má podnik realizovat, aby byl jeho zisk maximální.
Příklad 2: Aplikujte ručně metodu větví a mezí na následující modifikaci úlohy o batohu (použijte bivalentní proměnné a relaxace dílčích podúloh řešte bez pomoci simplexové metody):
Máme k dispozici sklad o celkové skladovací ploše 8400m2. O pronájem skladu má zájem 5 zájemců s různými požadavky na skladovou plochu a různými nabídkami za pronájem této plochy. Požadavky musí být splněny buď v plné výši nebo vůbec. V tabulce jsou uvedeny požadavky na plochu Pí a ceny za pronájem uvedené plochy q od každého zájemce i = 1,..., 5.
i	1	2	3	4	5
Pl[m2}	5000	1600	2800	6200	2200
Ci[Kč]	39000	9000	33000	63000	18000
Rozhodněte, kterým zájemcům poskytneme skladovací plochu, aby příjem z pronájmu byl co nejvyšší.