Tentamen Optimalisering (WI2608)



Dovnload 48.28 Kb.
Datum17.08.2016
Grootte48.28 Kb.

Tentamen Optimalisering (WI2608)


Datum: 28 januari 2004, 9.00 – 12.00.

Docent: Dr. J.B.M. Melissen


Veel succes!

Meerkeuzevragen. Het kan zijn dat bij sommige vragen het aantal juiste mogelijkheden afwijkt van 1. Je moet dan alle juiste mogelijkheden geven. Een uitleg mag maar hoeft niet (en wordt nooit in je nadeel gebruikt). Voor elke meerkeuzevraag krijg je 3 punten.
M1. Een convexe functie

  1. heeft altijd precies één minimum.

  2. heeft mogelijk meer dan één, maar altijd eindig veel minima

  3. heeft mogelijk oneindig veel minima.

  4. heeft mogelijk geen minimum.

Normaal gesproken heeft een convexe functie een minimum. Dat hoeft niet uniek te zijn als de functie niet strikt convex is, bijvoorbeeld de nulfunctie. Er zijn ook convexe functies zonder minima, bijvoorbeeld f(x) = ex op R, of f(x) = x op het open interval (0,1).

Antwoord d is juist, maar c ook.
M2. De simplexmethode, toegepast op een begrensd LP probleem


  1. vindt altijd een locaal minimum.

  2. vindt altijd een globaal minimum.

  3. vindt altijd alle minima.

  4. vindt meestal een minimum

Een begrensd LP probleem heeft altijd een minimum (Dat hoeft geen globaal minimum te zijn, want er kunnen meer hoekpunten optimaal zijn). Afgezien van cycling vindt de simplexmethode dit minimum ook. Antwoord d.


M3. Het aantal minima van een LP probleem met 2 variabelen en k constraints is

  1. precies 1.

  2. hoogstens 1.

  3. hoogstens k.

  4. mogelijk oneindig

Antwoord d.


M4. Een probleem waarin 5 van 8 mogelijke personen moeten worden toegewezen aan 5 taken is te formuleren als een toewijzingsprobleem,

  1. punt.

  2. maar niet heus.

  3. na invoering van 3 dummytaken.

  4. door gebruik te maken van de Big M methode.

Antwoord c.


M5. Een optimaliseringsprobleem met een strikt convexe doelfunctie en lineaire constraints die een begrensd gebied definiëren heeft

  1. precies één optimum.

  2. hoogstens eindig veel optima.

  3. mogelijk oneindig veel optima, maar deze vormen altijd een convexe verzameling.

  4. mogelijk optima, maar die liggen altijd op de rand van het toegelaten gebied.

De lineaire constraints definiëren een begrensd en gesloten gebied. De functie heeft dus een minimum en een maximum. Die zijn uniek vanwege de strikte convexiteit. Er zijn dus precies twee optima. Antwoord b is het enig juiste.


M6. Een BIP probleem heeft

  1. altijd precies één optimale oplossing.

  2. altijd eindig veel optimale oplossingen.

  3. mogelijk oneindig veel optimale oplossingen als het toegelaten gebied onbegrensd is.

  4. altijd minder optimale oplossingen dan het gerelaxeerde LP probleem.

Het toegelaten gebied van een BIP probleem is altijd eindig (eindig veel variabelen met twee mogelijke waarden). Antwoord b is goed. Antwoord d niet:

Max x + y

z.d.d. x + 2y  2

en x, y  {0,1}

Het gerelaxeerde probleem heeft één optimale oplossing (1, ½), het BIP probleem heeft er twee (1,0) en (0,1).

Antwoord c is ook goed, omdat de voorwaarde “ als het toegelaten gebied onbegrensd is” nooit waar is.
M7. De schaduwprijzen van een LP probleem


  1. kunnen worden berekend uit de oplossing van het primale LP probleem.

  2. kunnen worden afgelezen uit de formulering van het duale LP probleem.

  3. vormen de oplossing van de eerste fase uit de twee-fasen simplexmethode.

  4. geven de marginale waarden van de grondstoffen in een productieprobleem.

Antwoord d.


M8. In een minimaal kostenstromingsprobleem op een netwerk hebben alle opgelegde beperkingen op de takken gehele waarden.

  1. Er is dan altijd een gehele optimale oplossing.

  2. Er is dan altijd een gehele optimale oplossing als ook alle opgelegde in- en uitvoerwaarden geheel zijn.

  3. Er is alleen een gehele optimale oplossing als de som van de invoerwaarden gelijk is aan de som van alle uitvoerwaarden.

  4. Er zijn altijd gehele optimale oplossingen, maar eventuele convexe combinaties hiervan zijn meestal niet geheel.

De beperkingen en de opgelegde stromen moeten allemaal geheel zijn om aan de geheeltalligheidseigenschap te voldoen. Antwoord b.


M9. De uitvoering van de Brach-and-Bound methode voor het oplossen van een IP probleem kan worden versneld door

  1. het verscherpen van de constraints.

  2. het toevoegen van extra constraints.

  3. het weglaten van constraints.

  4. het verscherpen van de doelfunctie.

Antwoord a, b, c.


M10. De gulden-snede-methode is geschikt voor het vinden van

  1. het nulpunt van een ééndimensionale functie.

  2. het optimum van een ééndimensionale functie.

  3. het optimum van een convex optimaliseringsprobleem.

  4. een benaderend optimum van een ééndimensionale functie.

De gulden-snede-methode benadert het optimum van een een ééndimensionale functie, dus strikt gesproken klopt alleen d, maar in de praktijk natuurlijk ook b.



O1. Zoals je weet luiden de Karush-Kuhn-Tucker voorwaarden waaronder een punt x* een locaal optimale oplossing kan zijn van het optimaliseringsprobleem

Max f(x)


z.d.d. gi(x) £ bi voor alle i = 1, …, m

en xi ³ 0 voor alle i = 1, …, n

als volgt: er moeten Lagrangemultiplicatoren u1, …, um zijn zodat aan de volgende zes voorwaarden is voldaan:

1.

2. voor alle j = 1, …, n

3. gi(x*) £ bi voor alle i = 1, …, m

4. ui(gi(x*)-bi) = 0 voor alle i = 1, ..., m

5. x* ³ 0.

6. ui ³ 0.

a. (5 punten) Leid hieruit af dat voor het volgende probleem

Max f(x,y)

z.d.d. g(x,y) = b

en x, y  0

een punt (x*,y*) met x*,y* > 0 optimaal kan zijn als er een Lagrangemultiplicator R is zodat aan de volgende voorwaarden is voldaan:

1.

2.

3.


De voorwaarde g(x,y) = 0 kun je in de goede vorm voor KKT schrijven door hem te vervangen door de volgende twee ongelijkheden: g(x,y)  b en –g(x,y)  -b. Uitschrijven van de KKT voorwaarden levert:

1a.

1b.

2a.

2b.

3. g(x*,y*)  b en –g(x*,y*)  -b.

4. u1(g(x*,y*) – b) = 0, u2(-g(x*,y*) + b) = 0

5. x, y  0

6. u1, u2  0
Vervang nu := u1 – u2, dan volgt er:

1a.

1b.

2a. en 2b. impliceren 1, want x, y > 0

3. g(x*,y*) = b

4. u1(g(x*,y*) – b) = 0, u2(-g(x*,y*) + b) = 0

5. x, y  0

6. u1, u2  0 impliceert R


b. (3 punten) Een voorwerp dat op afstand v vóór een lens staat geeft een scherp beeld op een afstand b achter de lens. Als de brandpuntsafstand van de lens f is dan geldt de volgende relatie tussen v, b en f (de lenzenformule):

Bepaal met het bovenstaande criterium de kortst mogelijke afstand tussen voorwerp en beeld voor een lens met gegeven brandpuntsafstand f > 0 (Hint: elimineer )


De afstand tussen voorwerp en beeld is f(v,b) = v + b. De voorwaarden in a leveren:

1 - (-1/v2)=0

1 - (-1/b2)=0

Hieruit volgt dat  = v2 = b2, dus v = b = 2f en v + b = 4f


c. (2 punten) Los het voorgaande probleem ook op door met behulp van de constraint één variabele te elimineren.

Elimineer b = fv/(v-f), dan is v+b = v2/(v-f). De afgeleide naar v is 0 als v = 2f, dus v+b = 4f.



O2. Een vertrouwelijke boodschap moet door vijf mensen worden gelezen. Als de boodschap van persoon i aan persoon j wordt gegeven kan deze worden onderschept met een kans pij. Er geldt dat p­ij = pji. De kansen worden gegeven in de volgende tabel:




1

2

3

4

5

1

-

0,05

0,07

0,03

0,08

2




-

0,09

0,04

0,05

3







-

0,07

0,04

4










-

0,06




  1. (6 punten) Hoe moet de boodschap worden gecirculeerd onder deze vijf mensen zodat de kans op onderschepping zo klein mogelijk is? De boodschap wordt aan een persoon naar keuze gegeven en hoeft niet terug te komen.

Door de kansen te vervangen door log(1-pij) wordt het een kortste pad probleem dat met Dijkstra kan worden opgelost. Dit levert 1 – 4 – 2 – 5 – 3.




  1. (4 punten) Verandert de aanpak als de personen kopieën van de boodschap mogen houden, en zo ja, wat is dan de beste oplossing?

De aanpak verandert omdat een persoon het bericht nu aan meer anderen zou kunnen doorgeven. Je moet nu niet het kortste pad hebben, maar de minimale opspannende boom. In dit geval blijft het antwoord gelijk.



O3a. (5 punten) Laat D = {xR2 | |x|  1} de eenheidscirkelschijf in het vlak zijn. De functie f: D  R is convex en de functie g: D  R is niet-negatief. Definieer nu de functie h: D  R door

h(x) = f(x) + g(x) als |x| = 1

h(x) = f(x) elders

Bewijs dat h convex is op D (Aanwijzing: gebruik de definitie en onderscheid de gevallen dat 0, 1 of 2 eindpunten van het segment op de rand van D liggen.


Kies een x, y in D en  (0,1), dan geldt dat x + (1-)y in D ligt, maar niet op de rand. Dan is

h(x + (1-)y) = f(x + (1-)y)   f(x) + (1-)f(y)   h(x) + (1-)h(y),

want h(z)  f(z) voor alle z in D. Voor  = 0,1 is de ongelijkheid altijd waar.


  1. (5 punten) Bewijs dat de functie f(x,y) = x2 + ey strict convex is.

De tweede afgeleide is en deze matrix is positief definiet, want de twee eigenwaarden 2 en ey zijn positief. f is dus strikt convex.



O4. Bekijk het volgende LP probleem:
Max Z = x1 + 2x2 + 3x3 – 4x4

z.d.d. x1 + x2 + x3 + x4  8

x1 + x4  8,

x2 – 2x4  4

en x1, x2, x3  0


  1. (3 punten) Herschrijf dit LP probleem in de standaardvorm voor de simplexmethode

  2. (7 punten) Los het probleem op met de simplexmethode (één echte iteratie is voldoende)


O5. Vier vrachtwagens zijn beschikbaar om goederen vanuit een magazijn te leveren aan zeven klanten. De gewichtscapaciteiten van de vier vrachtwagens 1, 2, 3 en 4 zijn respectievelijk 9, 12, 15 en 11 ton. De gewichten van de goederen die aan klant 1 t/m 7 moeten worden afgeleverd zijn respectievelijk 6, 3, 5, 2, 4, 5 en 3 ton. Elke klant kan slechts door één vrachtwagen bevoorraad worden, maar elke vrachtwagen kan meer klanten bezoeken. De operationele kosten van vrachtwagen 1, 2, 3 en 4 zijn respectievelijk 125, 150, 170 en 135 euro.

  1. (10 punten) Formuleer een optimaliseringsmodel dat het bevoorradingsschema oplevert met minimale kosten

Introduceer de volgende variabelen: xij = 0, 1 naar gelang vrachtwagen i niet of wel levert aan klant j. Variabele yi = 0,1 naar gelang vrachtwagen i niet of wel wordt gebruikt

Minimaliseer 125y1 + 150y2 + 170y3 + 135y4

zodat 6x11 + 3x12 + 5x13 + 2x14 + 4x15 + 5x16 + 3x17  9 capaciteit wagen 1

6x21 + 3x22 + 5x23 + 2x24 + 4x25 + 5x26 + 3x27  12 capaciteit wagen 2

6x31 + 3x32 + 5x33 + 2x34 + 4x35 + 5x36 + 3x37  15 capaciteit wagen 3

6x41 + 3x42 + 5x43 + 2x44 + 4x45 + 5x46 + 3x47  11 capaciteit wagen 4

x11 + x21 + x31 + x41  1 klant 1 wordt beleverd

x12 + x22 + x32 + x42  1 klant 2 wordt beleverd

x13 + x23 + x33 + x43  1 klant 3 wordt beleverd

x14 + x24 + x34 + x44  1 klant 4 wordt beleverd

x15 + x25 + x35 + x45  1 klant 5 wordt beleverd

x16 + x26 + x36 + x46  1 klant 6 wordt beleverd

x17 + x27 + x37 + x47  1 klant 7 wordt beleverd

y1  (x11 + x12 + x13 + x14 + x15 + x16 + x17) wordt wagen 1 ingezet?

y1  (x21 + x22 + x23 + x24 + x25 + x26 + x27) wordt wagen 2 ingezet?

y1  (x31 + x32 + x33 + x34 + x35 + x36 + x37) wordt wagen 3 ingezet?

y1  (x41 + x42 + x43 + x44 + x45 + x46 + x47) wordt wagen 4 ingezet?

Alle variabelen binair.


  1. (10 bonuspunten) Vind een optimaal bevoorradingsschema.

Vrachtwagen 1 levert aan klant 1 en 2. Vrachtwagen 2 levert aan klant 3, 4 en 5. Vrachtwagen 4 levert aan klant 6 en 7. kosten €410.



O6. (10 punten) Pas twee iteraties van het sequentieel lineair benaderingsalgoritme van Frank-Wolfe toe op het volgende probleem:
Max x2 + 3xy + 2y2

z.d.d. 3x + y  4

en x, y  0
Los de optredende LP problemen grafisch op en doe de line-search exact.

Spiekbriefje: Frank-Wolfe: Vervang de objectfunctie door de lineaire benadering in het startpunt. Vind een oplossing van het ontstane LP probleem. Vind tussen startpunt en LP oplossing met een line-search een optimum voor het originele probleem. Dit is het startpunt voor de nieuwe iteratie.


De gradiënt van f is . Als je start in (0,0) is de gradiënt de nulvector en het bijbehorende probleem:
max 0

zodat 3x + y  4

en x, y  0
maar dat schiet natuurlijk niet op. Neem als startpunt (4/3,0), dan is het LP probleem
max 8/3x + 4y

zodat 3x + y  4



en x, y  0
LP oplossing is (0,4). Zoek nu een oplossing tussen (4/3,0) en (0,4): (4/3,4(1-)). De functiewaarde is daar 17 8/92 - 48 + 32. De maximale waarde is  = 1. Dit levert ook meteen de optiamle oplossing (0,4).



De database wordt beschermd door het auteursrecht ©opleid.info 2017
stuur bericht

    Hoofdpagina