Proeftentamen 2009-2010
Combinatorial Optimisation (FEB22002X)
Erasmus Universiteit Rotterdam
Aanbevolen voor jou
Reacties
Gerelateerde documenten
Gerelateerde Studylists
Combinatorisch OptimaliserenPreview tekst
Proeftentamen Combinatorisch Optimaliseren
Opgave 1 (6 + 3 punten)
Een bedrijf maakt ́e ́en product en wil een productieplan maken voor de opeenvolgende perioden 1, 2 ,... , T. De vraag naar het product is in elke periode bekend en wordt voor periodetaangegeven metdt. Aan de vraag in een bepaalde periode kan op de volgende twee manieren worden voldaan (combinaties zijn toegestaan):
door productie in de periode zelf,
door in eerdere perioden te produceren en dan te leveren uit de opgebouwde voor- raad.
Aangenomen mag worden dat productie altijd aan het begin van een periode plaatsvindt en dat de productietijd verwaarloosbaar is. Er zijn capaciteitsrestricties die de grootte van de productie beperken: in periodet kunnen niet meer dancteenheden worden geproduceerd. Verder geldt er ook een restrictie op de minimale productiehoeveelheid. Als er in een periodetproductie plaatsvindt, dan moeten ten minsteℓteenheden geproduceerd worden. We nemen aan dat 0≤ℓt ≤ct voort= 1,... , T. (De capaciteiten en minimale productiehoeveelheden kunnen dus per periode verschillen, maar zijn wel steeds bekend.) Het bedrijf heeft de volgende kostenstructuur. De productiekosten in periodetbedra- gen pt per eenheid geproduceerd in die periode. Daarnaast zijn er nog opstartkosten (setup-kosten)st die gemaakt worden zodra er in periodetgeproduceerd wordt; deze kosten hangen niet af van het niveau van de productie in periodet. De voorraadkosten in periodetbedragenhtper eenheid in voorraad aan het eind van de periode. De doelstelling is om een toegelaten productieplan voor deT perioden te bepalen zodanig dat aan alle vraag wordt voldaan en het totaal van de boven genoemde kosten minimaal is. Aangenomen wordt dat er voor aanvang van periode 1 geen voorraad aanwezig is.
(a)Formuleer het probleem als een (gemengd) geheeltallig lineair programmeringspro- bleem ((mixed) integer linear programming problem). Geef een duidelijke toelichting op de gebruikte variabelen en restricties.
Beschouw een (algemeen) geheeltallig lineair programmeringsprobleem
min{c⊤x:Ax≤b,x∈Nn}, (IP)
waarbijA,bencde juiste dimensies hebben enN= { 0 , 1 , 2 ,.. .}. Stel datP 1 enP 2 formuleringen zijn voor het toegelaten gebied van probleem (IP) en stel datP 1 ⊆P 2.
(b)Stel verder dat we de twee formuleringen willen gebruiken om probleem (IP) op te lossen met behulp van Branch-and-Bound. Welke formulering heeft uw voorkeur? Leg uit waarom.
Opgave 2 (3 + 5 + 3 + 4 punten)
Beschouw het probleem waarbij erntaken zijn enmmachines. Elke taak moet aan een machine worden toegekend. Verder heeft machineieen capaciteit vanri,i= 1,... , m. Als taakj op machineiwordt uitgevoerd, dan wordenaij eenheden van de capaciteit gebruikt met kostencij. Het doel is om de taken z ́o aan de machines toe te kennen dat de kosten minimaal zijn en de capaciteit van de machines niet overschreden wordt. Het probleem kan als volgt geformuleerd worden:
min
∑m i=
∑n j=1cijxij s.
∑m ∑in=1xij= 1 j= 1,... , n j=1aijxij≤ri i= 1,... , m xij∈{ 0 , 1 } i= 1,... , m;j= 1,... , n.
(a)Geef een duidelijke interpretatie van de gebruikte beslissingsvariabelen, de doel- stellingsfunctie en de restricties.
(b)Stel dat we Lagrange relaxatie toepassen en de restricties
∑n j=1aijxij ≤ ri, i= 1 ,... , m, in de doelstellingsfunctie opnemen met Lagrange multipliersλ 1 ,... , λm. Geef de Lagrange functie en los deze op voor een gegeven vectorλ. Formuleer tevens het Lagrange duale probleem.
(c)Is het eenvoudig om uit een oplossing van het Lagrange probleem een toegelaten oplossing voor het primale probleem te construeren? Zo ja, geef een Lagrange heuristiek. Zo nee, leg uit waarom niet.
(d)Stel dat we Lagrange relaxatie toepassen en de restricties
∑m i=1xij= 1,j= 1,... , n, in de doelstellingsfunctie willen opnemen met Lagrange multipliersμ 1 ,... , μn. Geef de uitdrukking voor de Lagrange functieθ(μ) (los hem niet op). Laat zien dat we de Lagrange functieθ(μ) kunnen oplossen door voor elke machine apart een probleem op te lossen. Wat is de naam van het probleem dat u voor elke machine moet oplossen?
Figuur 2: Graaf met koppeling bij Opgave 4 Figuur 3: Graaf bij Opgave 4 4
Proeftentamen 2009-2010
Vak: Combinatorial Optimisation (FEB22002X)
Universiteit: Erasmus Universiteit Rotterdam
