Last Update: 24‐1‐2010, Cliff Voetelink
Aanvullende Opgaven Inleiding Besliskunde II 2010‐2011 Aanvullende Opgave 1: Routeringsprobleem (ILP) Dit is een aangepaste versie van opgave 2.3 uit het boek van Tijms. Vrachtwagens 1,..., M zijn beschikbaar om goederen te leveren aan klanten 1,..., N met M < N . De gewichtscapaciteit van vrachtwagen i is bi ton [ i = 1,..., M ]. Het gewicht van het goed voor klant j bedraagt a j ton [ j = 1,..., N ] . Elke klant kan slechts door één vrachtwagen bevoorraad worden, maar dezelfde vrachtwagen kan meerdere klanten bevoorraden. Verder wordt geëist dat de vrachtwagen die een klant belevert dit niet over meerdere ritten mag doen. Een vrachtwagen maakt hoogstens 1 rit. De operationale kosten van vrachtwagen i bedragen ci euro. We zijn geïnteresseerd in het bevoorradingsschema dat de totale kosten minimaliseert. Formuleer dit probleem als geheeltallig programmeringsprobleem.
Aanvullende Opgave 2: Jones Chemical (ILP) Dit is een aangepaste versie van opgave 2.9 uit het boek van Tijms. Het bedrijf Jones Chemical heeft een contract gesloten om een speciaal soort zwavelzuur af te leveren in de komende N maanden. De overeenkomst behelst de levering ai ton aan het begin van maand i [i = 1,..., N ] . De productie van het zwavelzuur vereist enkele speciale maatregelen . De productiemanager heeft daarom besloten dat het zwavelzuur alleen geproduceerd kan worden aan het begin van elke maand. Elke productie neemt een verwaarloosbare hoeveelheid tijd in beslag. De vaste opstartkosten van een productie bedragen d euro. De variabele productiekosten van zwavelzuur bedragen c euro per ton. Iedere keer kan elke gewenste hoeveelheid van het zwavelzuur geproduceerd worden. Het bedrijf heeft voldoende opslagcapaciteit voor het zwavelzuur, maar voor elke ton zwavelzuur in voorraad bedragen de voorraad kosten r euro per maand. Op dit moment is er geen voorraad aanwezig. We zijn geïnteresseerd in het optimale productieschema. 2A) Formuleer dit probleem als een gemengd geheeltallig lineair programmeringsprobleem. 2B) Welke constraint moet worden toegevoegd indien er een extra eis is dat de productie in een maand j [ j vast gekozen] tenminste b ton moet zijn als besloten zou worden in maand j te produceren. 2C) Welke constraint moet men toevoegen indien er een extra eis is dat er maximaal 3 productierondes zijn. 2D) Welke constraint moet men toevoegen indien er een extra eis is dat in maanden 2 en 3 geen productierondes mogelijk zijn als er in maand 1 geproduceerd wordt.
Aanvullende Opgave 3: De Cocaïnesom (DP) Afkomstig uit het tentamen Inleiding OR 13 Januari 1999, door dr. R.D. Nobel. Cocaïnekoning dr. C. Snuif moet zijn kostbare lading in 5 etappes van zijn plantage ‘De Wilde Papaver’ naar de eindbestemming Amsterdam vervoeren. Voor elke etappe heeft ‘de Snuifmeister’ de keuze uit drie typen vervoer: vrachtwagen (1), trein (2) of schip (3). Vervoersvorm i kost voor etappe j een bedrag vij (i = 1, 2,3; j = 1, 2,3, 4,5) . In totaal is voor het vervoer een bedrag B beschikbaar. Verder is op etappe j met vervoersvorm i hoogstens een tonnage tij te vervoeren. Snuif vraagt zich af hoeveel ton cocaïne hij maximaal in één zending [welke dus bestaat uit 5 etappes] van ‘De Wilde Papaver’ naar Amsterdam kan vervoeren. Ook wil hij weten welke vervoersvormen op de verschillende etappes gebruikt moeten worden. Formuleer dit probleem als een dynamisch programmeringsprobleem.
Aanvullende Opgave 4: De Boekensom (DP) Afkomstig uit het tentamen Inleiding OR 10 Januari 2000, door dr. R.D. Nobel. [Aangepaste versie]. N studenten gaan op studiereis naar Zimbabwe en worden geacht gezamenlijk M studieboeken mee te nemen. Student j heeft hiervoor in zijn/haar rugzak nog plaats voor een gewicht van W j kilo
( j = 1,..., N ) . Boek i weegt gi kilo (i = 1,..., M ) en het totale gewicht van de boeken is groter dan M
het totale nog beschikbare gewicht in de rugzakken van de studenten, d.w.z.:
N
∑ g >∑ W i =1
i
j =1
j
. Omdat
men de boeken beslist wil meenemen zal een aantal studenten een overgewicht moeten meetorsen. Om de ‘pijn’ zo eerlijk mogelijk te verdelen besluit men de boeken zó te verdelen dat het grootste individuele overgewicht minimaal is. 4A) Formuleer dit probleem als een dynamisch programmeringsprobleem. Aangekomen op de luchthaven blijkt overgewicht niet toegestaan te zijn. Men zal daarom noodgedwongen een aantal boeken thuis moeten laten. Omdat elk boek voor de studiereis een bepaalde waarde heeft, zeg vi voor boek i , wil men nu de boeken zodanig herverdelen dat de totale waarde van de meegenomen boeken maximaal is, onder de voorwaarde dat geen enkele student meer een overgewicht meetorst. De vraag is nu welke boeken mee te nemen en wie welke boeken in zijn/haar rugzak meedraagt. 4B) Formuleer dit probleem als een dynamisch programmeringsprobleem. Vlak voor de aankomst op de luchthaven heeft iedere student nog een dictaat gekregen. Het dictaat is een soort samenvatting van alle studieboeken en heeft een waarde u . Op het vliegveld wordt er besloten het grootste deel van de dictaten daar achter te laten. Alleen wanneer de rugzak van een student te weinig ruimte heeft om überhaupt één boek mee te nemen, zal hij/zij één dictaat mee moeten nemen. Het dictaat past in iedere rugzak en heeft een verwaarloosbaar gewicht. Opnieuw worden de boeken verdeeld zodanig dat de totale waarde van de meegenomen boeken/dictaten maximaal is en er geen enkele student een overgewicht meetorst. 4C) Pas de recursievergelijkingen van vraag 4B aan op dit aangepaste probleem.
⎧1 als ..... geldt anders ⎩0
Hint: Gebruik de indicatorfunctie: 1{......} = ⎨
Aanvullende Opgave 5: Branch & Bound max 4 y1 + 3 y2 + 4 y3 onder: 4 y1 + 2 y2 + 3 y3 ≤ 15
y1 , y2 , y3 ≥ 0 én geheel. Los het bovenstaande knapzak probleem op met behulp van branch en bound.
Aanvullende Opgave 6: Brandstoftanks (ILP) Dit is een aangepaste versie van opgave 3 afkomstig van het hertentamen Inleiding Besliskunde II 2008‐2009. Benzinemaatschappij Overakker moet tijdelijk drie verschillende soorten brandstof opslaan. Op het terrein zijn daarvoor 4 opslaglocaties beschikbaar. Opslaglocaties 1, 2 en 3 zijn tanks en hierin kan slechts één type brandstof tegelijk worden opgeslagen. Alles wat niet in de tanks kan worden opgeslagen, wordt opgeslagen op opslaglocatie 4. De hoeveelheid ton van brandstoftype i die moet worden opgeslagen bedraagt bi [i = 1, 2, 3] . Het kost een bedrag cij om 1 ton van brandstoftype i in opslaglocatie j op te slaan
[i = 1, 2, 3; j = 1,..., 4] . De opslagkosten per ton op opslaglocatie 4 zijn echter nogal hoog, precies gezegd: ci 4 >>> cik i = 1, 2, 3; k ≠ 4 . Op deze locatie kun je wel verschillende soorten brandstof tegelijk opslaan maar dit is dus een stuk duurder wanneer je brandstof in een normale tank opslaat. Tank j heeft een opslagcapaciteit van m j ton [ j = 1, 2,3] . Op opslaglocatie 4 is er geen beperking qua capaciteit. Het doel is de brandstoffen tegen zo laag mogelijke kosten op te slaan. N.B.: Het is mogelijk dat je [verschillende hoeveelheden van] 1 type brandstof opslaat in twee verschillende tanks! Maar het is dus niet om meerdere verschillende brandstoffen in 1 tank op te slaan! 6A) Om dit probleem te formuleren als een gemengd geheeltallig lineair programmeringsprobleem, introduceren we continue beslissingsvariabelen xij en binaire beslissingsvariabelen yij . Geef nu duidelijk de betekenis van deze beslissingsvariabelen aan. 6B) Formuleer het bovenstaande probleem nu als een gemengd lineair programmeringsprobleem. 6C) Welke restrictie(s) moet je toevoegen als je maximaal 2 tanks mag toewijzen voor het opslaan van brandstoftype 3? Welke restrictie(s) moet je toevoegen wanneer tank 2 niet gebruikt mag worden om brandstoftype 1 in op te slaan als zowel tank 1 als tank 3 gebruikt worden voor het opslaan van brandstoftype 3?
Aanvullende Opgave 7: Klussen (ILP) Dit is een aangepaste versie van opgave 3 afkomstig van het tentamen Inleiding Besliskunde II 2008‐ 2009. Het bedrijf Dwars & Los heeft vorige week M klussen binnengesleept die zo snel mogelijk moeten worden uitgevoerd door de N werknemers (met M >> N ). Een klus kan slechts één keer worden geklaard en door slechts door één werknemer. Helaas is er te weinig tijd beschikbaar om alle klussen deze week te klaren. Het doel is nu om een werkrooster voor deze week te maken en de totale opbrengst van deze week te maximaliseren: als klus i uitgevoerd wordt, dan levert dat het bedrijf het bedrag ci euro op [i = 1,..., M ] . Als klus i gedaan wordt door werknemer j , dan neemt dit een tijd tij uur in beslag.
[i = 1,..., M , j = 1,..., N ] . Ook is het zo dat niet iedereen full‐time bij het bedrijf werkt en zo komt het dat iedere werknemer deze week slechts een bepaald aantal uren beschikbaar is. Precies gezegd: werknemer j is precies T j uur beschikbaar deze week. Een werknemer mag echter meerdere klussen in de week uitvoeren. Wel is er vereist dat iedere werknemer minstens één klus klaart en dat elke werknemer onder het werk nog minstens b uur vrije tijd (= beschikbare tijd – tijd besteed aan klussen) overhoudt. Tenslotte kan klus 3 om technische redenen niet worden uitgevoerd als klussen 1 of 2 (of beiden) deze week worden geklaard. Directeuren Peter D. en David L. willen graag het werkrooster van deze week hebben waarbij de totale opbrengst zo groot mogelijk is. Formuleer dit probleem als een geheeltallig lineair programmeringsprobleem. Geef duidelijk de betekenis van uw gekozen beslissingsvariabelen aan!
Aanvullende Opgave 8: Kortste Pad / Goedkoopste Pad (ILP)
Beschouw een gerichte graaf G = ( X , E ) waarbij X de verzameling steden is in het netwerk: X = {1,..., N } . Een pijl van stad i naar stad j wordt genoteerd met (i, j ) . Laat E ⊂ X × X (Cartesisch Product) de verzameling pijlen zijn waarover het mogelijk is om over te reizen. Laat het niet‐negatieve getal cij met (i, j ) ∈ E de afstand zijn om van stad i rechtstreeks naar stad j te gaan. Formuleer nu het algemene kortste pad probleem als een geheeltallig lineair programmerings‐ probleem zodat het kortste pad berekend wordt van stad 1 naar stad N . Geef duidelijk de betekenis van de beslissingsvariabelen aan en geef een korte toelichting op de constraints.
Aanvullende Opgave 9: Computer Samenstellen (ILP) Daan H. wil op een zo goedkoop mogelijke manier een computer aanschaffen door alle onderdelen los te kopen. Er zijn in totaal M verschillende onderdelen nodig [van elk onderdeel precies één], aangegeven met nummers 1 t/m M , die te koop zijn in N verschillende (internet)winkels. Onderdeel i kost in winkel j een bedrag cij [i = 1,..., M ; j = 1,..., N ] . Als Daan in winkel j één of meerdere onderdelen koopt moet hij sowieso een bedrag v j betalen [ j = 1,..., N ] (bijvoorbeeld voor verzendkosten). Daan vraagt zich af in welke winkels hij de M onderdelen moet aanschaffen ten einde de totale aanschafkosten zo laag mogelijk te laten zijn. 9A) Om dit probleem te formuleren als een geheeltallig lineair programmeringsprobleem, introduceren we binaire beslissingsvariabelen xij en y j . Geef nu duidelijk de betekenis van de gekozen beslissingsvariabelen aan.
9B) Formuleer dit probleem als een geheeltallig lineair programmeringsprobleem. 9C) Welke restrictie(s) moet(en) worden toegevoegd als Daan bij winkel N hoogstens k onderdelen mag aanschaffen? Welke restrictie(s) moet(en) worden toegevoegd als Daan bij hoogstens R winkels onderdelen mag aanschaffen [met R een gegeven waarde en R < N ]? Welke restrictie(s) moet(en) worden toegevoegd als Daan onderdelen 3 en 4 bij winkel 6 wil [moet] aanschaffen indien Daan onderdeel M niet bij winkel 2 aanschaft? 9D) Welke restrictie(s) moet(en) worden toegevoegd als Daan bij tenminste 3 verschillende winkels maximaal voor een bedrag van b per winkel aan onderdelen wil kopen?
Aanvullende Opgave 10: Computer Samenstellen (DP). Daan H. wil op een zo goedkoop mogelijke manier een computer aanscha_en door alle onderdelen los te kopen. Er zijn in totaal M verschillende onderdelen nodig [van elk onderdeel precies één], aangegeven met nummers 1 t/m M , die te koop zijn in N verschillende (internet)winkels. Onderdeel i kost in winkel j een bedrag cij [i = 1,..., M ; j = 1,..., N ] . Als Daan in winkel j één of meerdere onderdelen koopt moet hij sowieso een bedrag v j betalen [ j = 1,..., N ] (bijvoorbeeld voor verzendkosten). Daan vraagt zich af in welke winkels hij de M onderdelen moet aanschaffen ten einde de totale aanschafkosten zo laag mogelijk te laten zijn. 10A) Formuleer dit problem al seen dynamisch programmeringsprobleem. Beschrijf daarvoor in ieder geval de toestand, de interpretatie van de waardefunctie in woorden, de recursierelatie, de start‐ recursie en wat je moet berekenen in termen van de waardefunctie. Aanwijzing 1: Ga 1 voor 1 de winkels langs! Beschrijf nu eerst stadium j . Aanwijzing 2: Gebruik in je recursierelatie een indicatorfunctie en bedenk wat er op de plek van de … hoort te staan.
⎧1 als {...} geldt 1{...} = ⎨ anders ⎩0
10B) Formuleer het bovenstaande probleem opnieuw als een dynamisch programmeringsprobleem wanneer er de extra eis is dat er bij hoogstens R winkels onderdelen mogen worden aangeschaft. Beschrijf daarvoor in ieder geval de toestand, de interpretatie van de waardefunctie in woorden, de recursierelatie, de start‐recursie en wat je moet berekenen in termen van de waardefunctie. Aanwijzing: Gebruik de gelijkheid min{g ( S \ A)} = min{ min {g ( S \ A)}, g ( S )} A⊆ S
A⊆ S , A≠∅
Aanvullende Opgave 11 Vakkenpakket Samenstellen. (ILP) De calculerende Marloes B. moet voor volgende periode nog een keuze maken uit een collectie van N keuzevakken (genummerd van 1 tot en met N ). Elk vak vereist een bepaalde voorbereidingstijd, levert een aantal studiepunten op en heeft een gegeven moeilijkheidsgraad. Precies geformuleerd: vak j kost Marloes een tijd t j in uren aan voorbereiding, levert haar p j studie punten op en wordt door stafleden beoordeeld als een categorie c j vak, waarbij c j een geheel getal is tussen 1 en 10 [1 = zeer eenvoudig;.... ; 10 = heel moeilijk]. Volgens het studieprogramma moet Marloes nog minstens Q studiepunten halen. Marloes wil aan alle vakken tezamen niet meer dan T uur aan voorbereiding besteden. We gaan er vanuit dat Marloes voor elk vak slaagt. Omdat Marloes een mooie lijst vakken op haar CV wil kunnen presenteren stelt zij haarzelf eerst de vraag, welke vakken zij in de volgende
periode moet opnemen om te bereiken dat de som van de moeilijkheidsgraden van de gekozen vakken maximaal is. 11A) Formuleer dit probleem als een geheeltallig lineair programmeringsprobleem. Geef duidelijk de betekenis van uw gekozen beslissingsvariabelen aan! 11B) Welke restrictie(s) moet Marloes toevoegen als ze vakken 1, 2 en 3 niet mag opnemen in haar vakkenpakket wanneer vak N wordt opgenomen in haar vakkenpakket. Welke restrictie(s) moet je toevoegen als zij precies k vakken van vakken 1 t/m 10 moet volgen (met k vast en k < 10 )? Welke restricties moet Marloes toevoegen voor het geval dat wanneer Marloes 5 of meer keuzevakken gaat volgen, dat zij dan ook minstens 2Q studiepunten uit het samengestelde vakkenpakket moet halen? Hint: introduceer voor de laatste restricties een nieuwe binaire beslissingsvariabele! Veronderstel nu dat Marloes kan kiezen aan welke universiteit zij een bepaald vak volgt: elk keuzevak is te volgen op alle M verschillende universiteiten in Nederland. Het aantal college‐uren verschilt echter, op universiteit i neemt vak j een tijd tij uren aan colleges in beslag. Aangezien Marloes vanaf nu altijd naar colleges gaat en ze zoveel mogelijk van afwisseling houdt wil ze nu haar vakken zodanig kiezen dat de grootste tijd, die zij aan colleges kwijt is op eenzelfde universiteit, wordt geminimaliseerd. Het aantal studiepunten en de moeilijkheidsgraden bij elk vak blijven hetzelfde maar er moet nu voldaan worden aan het feit dat de som van de moeilijkheidsgraden van alle vakken die zij volgt minstens C is. Uiteraard moet zij nog steeds minstens Q studiepunten halen en wil zij aan alle vakken tezamen niet meer dan T uur besteden, de totale tijd die zij kwijt is aan vak j is nu de totale voorbereidingstijd voor vak j plus de totale tijd die zij aan colleges kwijt is voor vak j . Verder zal zij de colleges van een bepaald vak slechts aan 1 universiteit volgen, mocht zij besluiten dit vak op te nemen in haar vakkenpakket. Tenslotte wil zij aan minstens R verschillende universiteiten college volgen. 11C) Formuleer dit probleem als een (gemengd) geheeltallig lineair programmeringsprobleem. Geef duidelijk de betekenis van uw gekozen beslissingsvariabelen aan!
Aanvullende Opgave 12: Teams Samenstellen. (DP) De afdeling BWI besluit een N teams van k studenten te sturen naar een landelijke Operations Research olympiade. Er zijn M studenten die zich hebben aangemeld met ( M >> N ). De intelligentie van een student in dit vakgebied wordt gemeten op basis van een open‐boek toelatingstentamen, dat iedere (aangemelde) student heeft afgelegd. Het cijfer van student i van deze toets bedraagt bi [i = 1,..., M ] . Verder zijn er zoveel aanmeldingen dat lang niet iedere (aangemelde) student mee kan doen. Michiel V. wordt gevraagd om de teams in te delen en hij besluit de teams zodanig in te delen dat het laagste cijfergemiddelde per team zo hoog mogelijk is. Formuleer dit probleem als een dynamisch programmeringsprobleem. Beschrijf daarvoor in ieder geval: de toestand, de interpretatie van de waardefunctie in woorden, de recursierelatie, de start‐ recursie en wat je moet berekenen in termen van de waardefunctie. Hint: Je zal dus N keer een team moeten samen te stellen. Beschrijf nu eerst stadium j .
Aanvullende Opgave 13: De Bakker. (DP) Voor de komende N weken wil diepvriesbakker Marten W. een optimale bakstrategie vastleggen die zijn totale kosten minimaliseert. Hij weet dat in week j de vraag naar gebak exact D j stuks zal bedragen [ j = 1,..., N ] . Gebak gebakken in week j wordt ingevroren en is pas voor de verkoop beschikbaar in week j + 1 . Het in voorraad houden van gebak kost een bedrag h per stuk gebak per week aan invrieskosten, te betalen over de totale voorraad aanwezig aan het eind van de week. De vraag naar gebak waaraan niet direct voldaan kan worden, gaat voor de verkoop verloren en brengt boetekosten p met zich mee voor elk stuk gebak dat wel gevraagd maar niet geleverd wordt. De bakkosten per stuk gebak bedragen c j in week j en in week 1 zijn Q stuks ingevroren gebak in voorraad. Het ingevroren gebak is onbeperkt houdbaar. Formuleer dit probleem als een dynamisch programmeringsprobleem. Beschrijf daarvoor in ieder geval: de toestand, de interpretatie van de waardefunctie in woorden, de recursierelatie, de start‐ recursie en wat je moet berekenen in termen van de waardefunctie. Hint: Ga 1 voor 1 de weken af, beschrijf eerst stadium j .
Aanvullende Opgave 14: Sacred Heart. (DP) Het ziekenhuis Sacred Heart heeft N chirurgen in dienst. Elke chirurg heeft een eigen werkrooster. Deze week is het echter een zeer drukke week: er zijn namelijk M nieuwe patiënten aangekomen die allemaal geopereerd moeten worden. Chirurg j heeft nog tijd van t j uur beschikbaar in zijn/haar rooster voordat er overwerk plaatsvindt [ j = 1,..., N ] . De operatie van patiënt i neemt een tijd van Ti uur in beslag [i = 1,..., M ] . Het problem is echter dat
∑
M
T >∑ j =1 t j dus de totale N
i =1 i
tijd die de operaties van de M nieuwe patiënten bij elkaar in beslag nemen is veel groter dan het totaal aantal nog beschikbare uren van de chirurgen. Omdat alle operaties moeten plaatsvinden, zullen een aantal chirurgen moeten overwerken. Om de 'pijn' zo eerlijk mogelijk te verdelen besluit men de overuren zó te verdelen dat het grootste individuele aantal overuren minimaal is. Hoe moeten de patiënten op basis van dit criterium verdeeld worden over de verschillende chirurgen? Overigens is het mogelijk dat één chirurg meerdere patiënten onder zijn/haar hoede neemt maar een patient kan slechts aan één chirurg gekoppeld worden. Formuleer dit probleem als een dynamisch programmeringsprobleem. Beschrijf daarvoor in ieder geval: de toestand, de interpretatie van de waardefunctie in woorden, de recursierelatie, de start‐ recursie en wat je moet berekenen in termen van de waardefunctie.
Aanvullende Opgave 15: Docenten en Studenten (DP)
Bij de vakgroep BWI van de VU werken N docenten en er zijn M studenten met [ M >> N ]. Elke student moet precies één docent toegewezen krijgen als begeleider voor zijn/haar masterscriptie. Omdat alle studenten inmiddels hun onderwerp gekozen hebben kan men een goede inschatting maken van de tijd die het begeleiden van een student zal kosten. Deze tijd is mede afhankelijk van de docent. Precies gezegd, voor een optimale begeleiding zal student i van docent j een tijd tij [weken] voor zijn/haar begeleiding vergen. Elke docent heeft aangegeven hoeveel tijd hij voor scriptie‐begeleiding beschikbaar heeft: voor docent j is dit T j weken [ j = 1,..., N ] . Nu blijkt de totale minimale tijd die de studenten nodig hebben, i.e. totale tijd die de docenten beschikbaar hebben, i.e.
∑
∑
N j =1
M i =1
min j =1,..., N {tij } groter te zijn dan de
T j . Omdat alle studenten beslist een
optimale begeleiding willen, zullen sommige docenten meer dan hun als beschikbaar opgegeven tijd aan scriptiebegeleidingen moeten besteden. Beschouw nu het volgende criterium: de studenten moeten zodanig over de docenten verdeeld worden, zodat de grootste overschrijding van de tijden die de docenten bereid zijn aan de begeleiding te besteden, minimaal is. 15A) Formuleer dit probleem als een dynamisch programmeringsprobleem. Beschrijf daarvoor in ieder geval de toestand, de interpretatie van de waardefunctie in woorden, de recursierelatie, de start‐recursie en wat je moet berekenen in termen van de waardefunctie. Hint: het is handig om eerst op te schrijven wat stadium j voorstelt! De oplossing van het bovenstaande probleem leidt tot grote ontevredenheid onder de docenten. De vakgroepvoorzitter Prof. C. Ten Hoope stelt nu voor om docent j een bedrag b j extra salaris te geven voor elke week scriptiebegeleiding die de beschikbare tijd van docent j , T j , te boven gaat. Prof. ten Hoope streeft er nu naar om het totale bedrag dat zij zal moeten besteden aan de extra salarisuitgaven te minimaliseren. Hoe moeten de studenten volgens dit criterium verdeeld worden over docenten? 15B) Formuleer dit nieuwe probleem als een dynamisch programmeringsprobleem. Beschrijf daarvoor in ieder geval de toestand, de interpretatie van de waardefunctie in woorden, de recursierelatie, de start‐recursie en wat je moet berekenen in termen van de waardefunctie. Hint: het is handig om eerst op te schrijven wat stadium j voorstelt!
Aanvullende Opgave 16: Vrachtwagens en Routes. (DP) Een bedrijf moet voor N verschillende vrachtwagens beslissen welke routes ze moeten rijden. Het kost vrachtwagen j een bedrag cij om route i te rijden [i = 1,..., M ] , verder mag vrachtwagen j alleen routes rijden uit de verzameling V j [ j = 1,..., N ] . Er zijn minder routes dan vrachtwagens maar alle routes moeten gereden worden, als een vrachtwagen geen route rijdt, dan rijdt hij route 0, let op: 0 ∉ V j . Verder kost het een bedrag q j als vrachtwagen j geen route rijdt en mag een vrachtauto slechts 1 route rijden. 16A) Welke vrachtwagens moeten welke routes rijden opdat de totale kosten minimaal zijn? 16B) Vrachtwagen j bevindt zich op dij kilometer van het startpunt van route i af. Als vrachtwagen
j zich op meer dan c kilometer van zijn toegewezen route bevindt, wordt hij b j euro extra uitbetaald voor elke kilometer die hij meer dan deze c kilometer moet afleggen om bij het startpunt van zijn toegewezen route te komen. Hoe moet de formulering nu aangepast worden als we hiermee rekening houden?
