Voorbeeld van herschrijven als transportprobleem Het water van 3 rivieren moet worden verdeeld over 4 steden. Daar zijn kosten aan verbonden per eenheid water (zie tabel). De steden hebben minimumbehoeften en maximale capaciteit Colombo River Sacron River Calorie River min. nodig maximale cap.
Berdoo 16 14 19 30 50
Los Devils 13 13 20 70 70
San Go 22 19 23 0 30
Hollyglass 17 15 10 ∞
Aanvoer 50 60 50
Schrijf eerst het probleem op zonder minimale eis: Colombo River Sacron River Calorie River Dummy vraag
Berdoo 16 14 19 0 50
Los Devils 13 13 20 0 70
San Go 22 19 23 0 30
Hollyglass 17 15 M 0 60
Aanvoer 50 60 50 50
De totale aanvoer is 160, dus Hollyglass krijgt maximaal 160 – (30 + 70 + 0) = 60 Voeg een dummyrivier toe die water aanvult tot maximale capaciteit. Dit water wordt in werkelijkheid niet geleverd.
Minimale behoefte krijg je door steden te splitsen. Het minimale deel mag niet uit de dummyrivier komen.
Colombo R. Sacron River Calorie River Dummy vraag
Berdoo min 16 14 19 M 30
Berdoo rest 16 14 19 0 20
Los Devils 13 13 20 M 70
San Go
Hollyg.
22 19 23 0 30
17 15 M 0 60
50 60 50 50 210
Berdoo-min en Los Devils mogen niets uit de dummyrivier krijgen. Hollyglass hoeft niet gesplitst te worden in dit voorbeeld, want krijgt al minimaal 160 - (50 + 70 + 30) = 10.
Toewijzingsproblemen (3.5.2) Toewijzingsprobleem: Elk van n oorsprongknopen moet 1-1 worden gekoppeld aan één van n bestemmingsknopen. De kosten van elk paar koppelingen is bekend. Vind een toewijzing met minimale kosten. Dit is een speciaal geval van een transportprobleem: Voorraad = 1, vraag = 1, aantal leveranciers = aantal afnemers. Simplex op het gerelaxeerde probleem vindt dan automatisch een binaire oplossing. Voorbeeld: Welke machine op welke locatie? KOSTEN Locatie → 1 machine↓ 1 13 2 15 3 5
2 16 7
3 12 20 10
4 11 13 6
KOSTEN Locatie → 1 machine↓ 1 13 2 15 3 5 dummy1 0
2 16 M 7 0
3 12 20 10 0
4 11 13 6 0
Toewijzingen die niet mogen krijgen als kosten M. Als aantallen niet kloppen: voeg dummies toe met kosten 0. Die worden uiteindelijk niet toegewezen. Oplossing: 1→3, 2→4, 3→1, dummy1→2.
Kosten = 30
Hongaarse methode voor toewijzingsprobleem Het volgende algoritme (H.W. Kuhn, 1955) lost het toewijzingsprobleem op als de vierkante kostenmatrix gegeven is met kosten ≥ 0:
1. Trek in elke kolom het kleinste getal van elk getal in die kolom af 2. Trek in elke rij het kleinste getal van elk getal in die rij af 3. Streep alle nullen weg met een minimaal aantal horizontale en/of verticale strepen Als aantal strepen = aantal rijen ga naar 5, anders 4 4. Trek kleinste getal dat niet weggestreept is af van elk niet weggestreept getal. Tel het getal op bij elk getal op het kruispunt van strepen. Ga naar 3 5. Wijs elke rij aan een kolom toe zodat die kolom 0 heeft in die rij, en elke kolom één keer wordt toegewezen Het aftrekken van een getal van elk getal in een rij of een kolom verandert de optimale oplossing niet want vanwege n
∑x i =1
ij
=1
n
en
∑x j =1
ij
=1
wordt alleen een getal van de doelfunctie afgetrokken. De gereduceerde kosten blijven ≥ 0 en een oplossing met gereduceerde kosten = 0 is dus optimaal.
Voorbeeld: 13 16 12 11 15 M 20 13 5 7 10 6 0 0 0 0 Kostenmatrix
2 5 1 0 2 M-13 7 0 0 2 5 1 0 0 0 0 Na stap 1 en 2
2 2 0 0
2 4 0 0 2 M-14 6 0 0 1 4 1 1 0 0 1 Stap 4
5
1 M-13 7 2 5 0 0 Stap 3
0 0 1 0
0
0 0
0 0 0 Stap 3 lukt niet met 3 strepen
0 0 0 0 Stap 5
Toewijzing: 1→3, 2→4, 3→1, 4→2.
0 0
Dynamisch programmeren (H 5) Dynamisch programmeren is een “verdeel en heers” methode voor het oplossen van discrete optimaliseringsproblemen waarin een aantal opeenvolgende beslissingen moeten worden genomen, zodat de doelfunctie voor volgende beslissingen niet meer afhangt van vorige beslissingen. De doelfunctie moet recursief worden uitgerekend, maar hoeft niet lineair te zijn.
Voorbeeld: NASA ontwikkelt een nieuwe satelliet. Drie teams werken parallel aan verschillende technologieën. Het project is geslaagd als minstens één van de teams slaagt. Twee extra wetenschappers kunnen aan de teams worden toegevoegd. Ze beïnvloeden de slaagkans van de teams als volgt:
Aantal 0 1 2
team 1 0.4 0.2 0.15
Faalkans team 2 0.6 0.4 0.2
team 3 0.8 0.5 0.3
De faalkans zonder extra wetenschappers is de kans dat alledrie de teams falen: 0.4 × 0.6 × 0.8 = 0.192 In fase n bepaal je hoeveel wetenschappers team n krijgt. sn is het aantal wetenschappers dat daarvoor nog beschikbaar is. De faalkans vanaf fase n is de faalkans vanaf fase n+1 maal de faalkans van team n. Dit geeft de recursie die voor dynamisch programmeren nodig is. In formule: fn(sn, xn) = pn(xn) fn+1*(sn – xn) fn*(sn) = min {fn(sn, xn) | xn}
Tabel van fase 3: f3*(s3) 0.8 0.5 0.3
s3 0 1 2
x3* 0 1 2
Tabel van fase 2: x2 0 0.48 0.3 0.18
s2 0 1 2
1
2
0.32 0.2
0.16
f2*(s2) 0.48 0.3 0.16
x2* 0 0 2
Bijvoorbeeld: s1 = 1, x2 = 0 betekent: je hebt één wetenschapper over, je geeft er géén aan team 2. Faalkans is faalkans van team 2 zonder extra hulp (0.6) maal kleinste faalkans van de rest van het project, waarbij je nog één wetenschapper te verdelen hebt (vorige tabel, s3 = s2 – x2 = 1 – 0 = 1 (kans 0.5). 0.6 × 0.5 = 0.3 komt in de tabel. Onder f2*(s2) komt de minimale waarde van de rij daarvoor. Onder x2* komt de waarde van x2 waar het minimum wordt aangenomen. Tabel van fase 1:
x1 s1 2
0 0.064
1 0.06
2 0.072
f1*(s1) 0.06
x1* 1
Je begint met twee wetenschappers dus alleen s1 = 2 is mogelijk. Oplossing: x1* = 1 (tabel fase 1), dus s2 = s1 – x1* = 2 – 1 = 1, dus (tabel fase 2) x2* = 0, dus s3 = s2 – x2* = 1 – 0 = 1 en x2* = 1 (tabel fase 3) Gevolg: team 1 en 3 krijgen elk één wetenschapper. Faalkans is nu 0.06. In dit simpele voorbeeld kun je trouwens alle mogelijke verdelingen van wetenschappers over de teams opschrijven: Team 1 2 1 1 0
Team 2 0 1 0 2
Team 3 0 0 1 0
Faalkans 0.072 0.064 0.06 0.064
0 0
1 0
1 2
0.08 0.072
Een LP maximaliseringsprobleem in 250 variabelen heeft 200 lineaire begrenzingen. Welke uitspraak is waar? a. De simplexmethode vindt in hooguit 250 stappen een maximum. ⎛ 250 ⎞ ⎟⎟ stappen een maximum. ⎝ 200 ⎠
b. De simplexmethode vindt in hooguit ⎜⎜
c. De simplexmethode is niet toepasbaar op een maximaliseringsprobleem. d. De simplexmethode vindt zeer waarschijnlijk geen maximum voor dit probleem. e. De bovenstaande antwoorden zijn allemaal onjuist. Oplossing: In het algemeen heeft een lineair optimaliseringsprobleem meer begrenzingen dan variabelen. Voor het eenvoudigste gebiedje in n variabelen, de simplex, heb je al n+1 begrenzingen nodig. Als er minder begrenzingen zijn dan variabelen, zoals hier, dan is het toegelaten gebied onbegrensd. Er kan dan wel een maximum zijn, maar dat hoeft niet. De simplexmethode zal dus niet voor al dit soort problemen gegarandeerd een maximum vinden. Het aantal variabelen is hier een stuk groter dan het aantal begrenzingen, dus de kans is groot dat er geen maximum bestaat. Antwoord d.
Gegeven is een transportprobleem met 5 leveranciers, die totaal 415 producten leveren aan 8 afnemers. Met behulp van LP-technieken wordt nu een optimale oplossing bepaald. Afnemer A vraagt 48 producten en krijgt deze ook. Afnemer A komt er achter dat hij eigenlijk 52 producten wil hebben en spreekt met afnemer B, die in de optimale oplossing 29 producten kreeg, af dat B ook met 25 producten tevreden is. Men laat dit probleem opnieuw doorrekenen. De gegevens van alle andere afnemers en leveranciers blijven daarbij gelijk. a. Afnemer A krijgt nog steeds 48 producten. b. Afnemer A krijgt nu 52 producten. c. Afnemer A krijgt minimaal 48 en maximaal 52 producten. d. Afnemer A krijgt 52 producten, óf het probleem heeft geen toelaatbare oplossing. e. Er kan nu geen toelaatbare oplossing meer zijn. f. Dit probleem is niet meer als een transportprobleem te formuleren. Oplossing: In een transportprobleem wordt elk geleverd product ook afgenomen. Omdat A meer wil en B minder, kan het zijn dat dit lukt, maar dat is niet gegarandeerd. Als de producten voor A alleen maar kunnen komen van één leverancier die precies 48 producten levert, dan zal A niet meer kunnen krijgen en is er dus geen toelaatbare oplossing. Antwoord d. (Antwoord b is ook goed, als er in de formulering van het transportprobleem geen Big-M is gebruikt om een niet-volledige transportnetwerk te beschrijven)
Welke uitspraken zijn waar? (meer antwoorden mogelijk) a. Het aantal CPF oplossingen in een LP probleem is eindig. b. Het aantal CPF oplossingen in een LP probleem is minstens 1. c. Het aantal CPF oplossingen in een LP probleem is minimaal n+1, als n het aantal variabelen is. d. Een oplossing op het lijnstuk tussen twee CPF oplossingen is altijd toelaatbaar. Oplossing a en d zijn waar. Een LP probleem heeft eindig veel begrenzingen, er zijn dus eindig veel snijpunten van n bijbehorende lineaire gelijkheden, dus eindig veel hoekpunten. Het toelaatbare gebied is convex, dus alle punten op het verbindingslijnstuk tussen twee punten daaruit (bijvoorbeeld CPF oplossingen) zijn toelaatbaar. Er zijn problemen zonder CPF oplossingen (bijvoorbeeld: maximaliseer x2 met x2≤0, heeft als toelaatbaar gebied een halfvlak zonder hoekpunten).
Welke uitspraken zijn ONjuist? (meer antwoorden mogelijk) a. Elk BIP probleem is te formuleren als een IP probleem. b. Elk IP probleem is te formuleren als een BIP probleem. c. Elk LP probleem is te formuleren als een MIP probleem. d. Elk IP probleem heeft eindig veel toelaatbare oplossingen. e. Elk BIP probleem heeft eindig veel toelaatbare oplossingen Oplossing Een BIP probleem met n variabelen heeft maximaal 2n oplossingen, maar een IP probleem kan er makkelijk oneindig veel hebben. Uitspraak d is onjuist.
Gegeven is een situatie met 5 leveranciers, die totaal 738 producten leveren aan 6 afnemers, die bij elkaar 715 producten nodig hebben. Men wil dit probleem formuleren als een transportprobleem. Dit kan a. door invoering van een dummy afnemer. b. door invoering van een dummy leverancier. c. door invoering van een dummy leveranciers en een dummy afnemer. d. door toepassing van de Big M methode. e. niet. Oplossing: Er wordt meer geleverd dan afgenomen, er is dus een dummy afnemer nodig, die het teveel geproduceerde opneemt en het probleem in balans brengt. Antwoord a.
Twee fabrieken, F1 en F2 leveren elk 50 producten per dag. De producten worden allemaal afgenomen door twee afnemers A1 en A2. Afnemer A1 wil minstens 20 producten afnemen, en A2 kan maximaal 60 producten afnemen. De transportkosten per product van fabriek naar afnemer staan in de tabel:
F1 F2
A1 A2 c11 c12 a. Formuleer dit probleem als een transportprobleem en geef de bijbehorende transporttabel. c21 c22 b. Geef een LP formulering van dit probleem met zo weinig
mogelijk variabelen (dus niet noodzakelijk als transportprobleem). c. Een mogelijke oplossing is dat fabriek 1 40 producten aan A1 levert, en dat fabriek 2 geen producten aan A1 levert. Leidt (grafisch) een voorwaarde voor de kostencoëfficiënten af waaronder deze oplossing optimaal is. a. In een transportprobleem nemen de afnemers vastgestelde hoeveelheden af, maar dat is hier niet het geval. We moeten daar eerst met een paar trucks voor zorgen. Afnemer A2 neemt maximaal 60 producten af. Omdat alle producten worden afgenomen betekent dit dat A1 minimaal 40 producten afneemt. We splitsen A1 in twee afnemers: A1min en A1plus. A1min neemt precies 40 producten af (het minimum, en A1plus neemt maximaal 100 - 40 = 60 producten af. Hij hoeft ze echter niet allemaal af te nemen, dus we voeren een dummyleverancier D in die alles levert wat A1plus minder dan 60 afneemt. De kosten voor afname van deze leverancier zijn 0 voor A1plus (want het kost in het echt niets als hij minder afneemt) en M voor A1min (want het minimum moet worden afgenomen, en niet minder). A2 laten we 60 producten afnemen, waarvan er een aantal uit de dummybron mogen komen met kosten 0, want minder afnemen kost in het echt ook niets. Totaal is de behoefte nu 40+60+60 = 160. Dat betekent dat de dummy 160-50-50 = 60 producten moet leveren. A1min A1plus A2 F1 c11 c11 c12 50 F2 c21 c21 c22 50 D M 0 0 60 40 60 60 160
b. Noem xij het aantal producten van fabriek i naar afnemer j dan hebben we vier variabelen en de volgende LP formulering: min c11x11 + c12x12 + c21x21 + c22x22 z.d.d. x11 + x12 = 50 x21 + x22 = 50 x11 + x21 ≥ 20 x12 + x22 ≤ 60 xij ≥ 0 Met de eerste twee gelijkheden kunnen we x12 en x22 elimineren: min (c11- c12) x11 + (c21- c22) x21 + 50(c12+ c22) z.d.d. x11 + x21 ≥ 20 50-x11 + 50-x21 ≤ 60 ⇒ x11 + x21 ≥ 40 x11 ≥ 0, x21 ≥ 0, x11 ≤ 50, x21 ≤ 50 Er blijft dus over: min (c11- c12) x11 + (c21- c22) x21 + 50(c12+ c22) z.d.d. x11 + x21 ≥ 40 x11 ≥ 0, x21 ≥ 0, x11 ≤ 50, x21 ≤ 50 c. Het toelaatbare gebied van de bovenstaande formulering is een vierkant [0,50] × [0,50], waaruit linksonder een driehoek ((0,0) – (40,0) – (0,40)) is weggeknipt. Het hoekpunt (40,0) is optimaal als de richtingsvector van de ⎛ c11 − c12 ⎞ ⎟⎟ recht naar beneden wijst, of maximaal over een hoek ⎝ c 21 − c 22 ⎠
doelfunctie ⎜⎜
van 45o naar links wordt gedraaid. Dat levert de volgende ongelijkheden: c21 – c22 ≤ c11 – c22 ≤ 0.
Mike Phoney woont op de Long Street nr 312 en hij werkt voor een telefoonmaatschappij. Nu ligt Long Street in een achterstandswijk en het komt regelmatig voor dat er wanbetalers moeten worden afgesloten. Het is de taak van Mike om dit in Long Street te verzorgen. Elke ochtend om 8.00 uur krijgt hij de huisnummers doorgebeld die moeten worden afgesloten en gaat hij op pad om dit te doen. Zijn strategie is om eerst linksaf te slaan en achtereenvolgens alle lagere huisnummers van zijn lijstje af te sluiten. Bij het laagste nummer keert hij om en gaat terug langs zijn eigen huis om alle hogere nummers af te werken. Hiermee loopt hij meteen de kortst mogelijke route. De telefoonmaatschappij legt echter andere criteria aan. Zij willen dat de gemiddelde afsluittijd zo klein mogelijk is. De afsluittijd is de tijd waarop Mike een bepaalde woning afsluit. Omdat het afsluiten alleen neerkomt op het omdraaien van een schakelaar, is de afsluittijd evenredig met de totale lengte van de route die Mike tot die woning heeft afgelegd. Het komt er dus op neer dat de som van de afsluittijden van alle af te sluiten woningen minimaal moet worden. Dit kan betekenen dat Mike niet meer de kortst mogelijke route loopt. De telefoonmaatschappij stuurt Mike op een cursus dynamisch programmeren, zodat hij elke ochtend zelf de beste route kan bepalen, en jij geeft tot je grote verrassing deze cursus. Leg aan Mike uit hoe hij met behulp van dynamisch programmeren de beste route bepaalt in het geval dat de volgende huisnummers moeten worden afgesloten: 118, 372, 394 en 739. De afstand tussen twee huisnummers is evenredig met het verschil van de nummers. Hint: Mike hanteert de volgende werkwijze: na elke afsluiting heeft hij bepaald of hij links- of rechtsaf moet gaan en sluit hij het eerstvolgende nummer van zijn lijstje in die richting af, die hij nog niet heeft gehad. In het algemeen kan hij dus een zigzagroute volgen, waarbij hij bepaalde woningen meerdere malen passeert. Oplossing: We moeten eerst een aantal fasen onderscheiden. Fase 0 is de start op nummer 312, fase 1 is het eerste huisnummer dat hij aandoet, fase 2 het tweede, etc. tot en met fase 4, waarin het laatste adres wordt bezocht. De objectfunctie is de som van alle afgelegde wegen tot de adressen (de som van de bezorgtijden), dus de afgelegde weg van nr 312 naar het eerste huis plus de afgelegde weg (niet de kortste weg) van 312 tot het tweede huis. Deze som is gemakkelijk uit te drukken in de weg die tussen de fasen wordt afgelegd. De weg tussen fase 3 en 4 (van het éénna-laatste huis naar het laatste) wordt erbij opgeteld. De weg van fase 2 naar fase 3 wordt er tweemaal bij opgeteld (want dat stuk geldt voor de route naar het één-na-laatste huis, maar ook naar het laatste), de route van 1 naar twee wordt er driemaal bij opgeteld en de route van 0 naar 1 viermaal. In formule geldt voor de objectfunctie in fase n: fn(s,xn) = (5n)|s-xn| + fn-1*(xn) Hierin is s de toestand (adres) waarin je je bevindt en xn het volgende adres, |s-xn| is de afstand tussen de adressen en 5-n is de factor waarmee deze afstand meetelt: éénmaal voor fase 4, tweemaal voor fase 3, etc.,
fn-1*(xn) is de optimale som van de bezorgafstanden tot en met adres xn. Omdat het hier om maar vier adressen gaat kun je nog eenvoudig alle mogelijkheden opschrijven: 312 – 118 – 372 – 394 – 739 \ 372 – 118 – 394 – 739 \ 394 – 118 – 739 \ 739 – 118 Je begint nu in fase 4, het laatste adres. Dit kan alleen zijn: 118, of 739, want de tussenliggende adressen moet je inmiddels gepasseerd zijn. Je kunt in 118 alleen komen via 739 (bijdrage 739-118 = 621), in 739 kom je via 394 (bijdrage 345) of via 118. Voor fase 4 kun je de volgende tabel maken. Hierin staan de mogelijke laatste routes (van s naar x4) met hun bijdrage aan de som van de servicetijden. x4 s 118 739 f4*(s) x4* 118 621 621 739 394 345 345 739 739 621 621 118 De tabel van fase 3, vervolgens is als volgt opgebouwd: de route van 394 naar 118 (afstand 394-118 = 276) geeft een bijdrage 2×276. De kleinste bijdrage vanaf 118 lees je uit de vorige tabel: 621. De totale bijdrage van 394 naar 118 is dus: 2×276 + 621 = 1173, etc. x3 s 118 394 739 f3*(s) x3* 118 897 897 394 372 389 389 394 394 1173 1311 1173 118 Fase 2: x2 s 118 118 372 1659
372 1151 -
394 1239
f2*(s) 1151 1239
Tenslotte fase 1: x1 s 118 372 312 1927 1479
f1*(s) 1479
x1* 372
x2* 372 394
Uit deze tabellen lees je af dat de beste route is: 312 – 372 – 394 – 118 – 739. De som van de servicetijden is 1497 (60 + 82 + 358 + 979). Merk op dat dit niet de kortste route is.
René heeft via een internetveiling goedkoop een CD gekocht van een aanbieder uit Duitsland. Voor € 1,50 heeft hij de CD toegeslagen gekregen. Hij moet hiervoor, inclusief porto, een bedrag van € 3,50 betalen, een koopje dus. Tot zijn schrik komt hij er achter dat de Postgiro voor overboeken naar een buitenlandse bank € 5,- vraagt, terwijl ook de bank van de Duitse CD-eigenaar nog eens € 3,50 aan kosten in rekening brengt. Dit zou de totale prijs op € 12 brengen. René besluit om het geld per brief op te sturen. Hij vraagt zich af met welke combinatie van munten hij het kleinste gewicht kan realiseren, om zodoende portokosten te besparen. In de tabel staat het gewicht van elke munt aangegeven. (2 pt.) Formuleer dit probleem als een geheeltallig € gewicht lineair optimaliseringsprobleem. (gram) (2 pt.) Beredeneer dat in de optimale oplossing elke 0,01 2,3 munt hoogstens éénmaal voorkomt. 0,02 3,0 (2 pt.) Betekent dit dat je de eis van geheeltalligheid in 0,05 3,9 de formulering van onderdeel a kunt vervangen door 0,10 4,1 een binaire eis? Waarom? 0,20 5,7 (7 pt.) Vind met behulp van Branch and Bound de 0,50 7,8 beste oplossing. Hint: vind eerst door proberen de 1,00 7,5 (waarschijnlijk) beste oplossing. Het is het handigst 2,00 8,5 om met Branch and Bound bij de hoogste munt te beginnen. Zoek telkens een bovengrens van de gerelaxeerde problemen zonder ze expliciet op te lossen, of laat zien dat ze niet toelaatbaar zijn (tenzij je lol hebt in simplexproblemen met zeven variabelen). (2 pt.) René realiseert zich dat hij zijn probleem gewicht tarief eigenlijk niet goed heeft geformuleerd. Het gaat (gr) (€) immers niet om een zo laag mogelijk gewicht, maar om 0-20 0,54 minimale kosten. Hij maakt gebruik van de 20-50 1,08 portotarieven van PTT Post uit de tabel hiernaast. Een 50-500 1,62 envelop weegt 3 gram. Is de oplossing die je in d. hebt gevonden ook onder de nieuwe voorwaarden de beste? Waarom? Oplossing: Voer geheeltallige variabelen x1, …, x8 in die aangeven hoeveel centen, dubbeltjes (= 2 cent), stuivers, etc. René moet opsturen. De formulering van het probleem is dan: Min 2,3x1 + 3x2 + 3,9x3 + 4,1x4 + 5,7x5 + 7,8x6 + 7,5x7 + 8,5x8 z.d.d. en
x1 + 2x2 + 5x3 + 10x4 + 20x5 + 50x6 + 100x7 + 200x8 = 350 0 ≤ xj ∈ Z voor 1≤j≤8.
Als een muntstuk van 1, 5, 10, 50, 100 cent dubbel voorkomt, dan kun je dat vervangen door een muntstuk met de dubbele waarde en minder gewicht. Als er vervolgens een munt van 2 cent tweemaal voorkomt, dan moet er ook één cent voorkomen, of er zijn meteen vijf munten van twee cent (anders kun je namelijk niet op een tienvoud uitkomen). In beide gevallen kun je munten vervangen door een kleiner aantal met minder gewicht (2+2+1 = 5, 2+2+2+2+2 = 10). Een soortgelijk argument geldt voor de 20 cent munt. De munt van € 2 kan hoogstens éénmaal voorkomen omdat je anders boven het bedrag van € 3,50 uitkomt. Ja, je weet nu namelijk dat de optimale oplossing binair is dus de eis van binair zijn sluit geen van die mogelijkheden uit. De beste oplossing is € 0,50 + 1,00 + 2,00 met een gewicht van 7,8 + 7,5 + 8,5 = 23,8 gram. Deze oplossing ligt erg voor de hand, en is waarschijnlijk de eerste die je zou proberen. Elke oplossing die boven de 23,8 gram uitkomt kun je dus schrappen. Begin bij x8, het aantal € 2 munten. We weten dat x8 0 of 1 is. Als x8 = 0, dan wordt de constraint: x1 + 2x2 + 5x3 + 10x4 + 20x5 + 50x6 + 100x7 = 350. Deze is niet toelaatbaar (de maximaal bereikbare waarde links is 188), conclusie: x8 = 1 (ofwel: de hele tak met x8 = 0 valt af.) De constraint is nu x1 + 2x2 + 5x3 + 10x4 + 20x5 + 50x6 + 100x7 = 150. Stel dat x7 = 0, dan moet x1 + 2x2 + 5x3 + 10x4 + 20x5 + 50x6 = 150. Ook deze is niet toelaatbaar, omdat het linkerlid maximaal 88 kan zijn, gevolg: x7 = 1. De constraint wordt: x1 + 2x2 + 5x3 + 10x4 + 20x5 + 50x6 = 50. Stel dat x6 = 0, dan moet x1 + 2x2 + 5x3 + 10x4 + 20x5 = 50. Ook dit kan niet, dus x6 = 1. De constraint is dan: x1 + 2x2 + 5x3 + 10x4 = 0. Dit kan alleen als x1 = x2 = x3 = x4 = 0. Het totale gewicht is dan 23,8 gram. Bij de oplossing uit d. moet je 23,8 (munten) + 3 (envelop) gram versturen. Het versturen kost dus € 3,50 + 1,08 = € 4,58. Dit is niet de beste oplossing. Dat komt omdat de eis, dat het te verzenden bedrag gelijk is aan € 3,50, kan worden vervangen door de eis dat er minstens € 3,50 moet worden verstuurd. Dat lijkt flauw, want waarom zou je teveel sturen? Als je echter twee munten van € 2 verstuurt in een envelop is het totale gewicht 2×8,5 + 3 = 20 gram. Dit gaat tegen een tarief van € 0,54, dus de totale kosten voor René zijn € 4,54. Dat is 4 cent goedkoper, terwijl de ontvanger 50 cent extra ontvangt. In werkelijkheid kwam René er pas ná het overmaken van € 3,50 achter dat dit hem € 5 extra kostte, en dat de Duitse bank de € 3,50 bij de ontvanger bijschreef. De CD kostte René uiteindelijk € 3,50 + 5,00 + 4,54 = € 13,04, in plaats van de € 3,50 die het leek te kosten.
