proeftentamen

Combinatorisch Optimaliseren (FEB22002), 2011-2012
Proeftentamen
Opgave 1
Handelsreizigersprobleem (2 + 5 + 2 + 3 punten)
Gegeven zijn n steden en hun onderlinge afstanden. De afstand van stad i naar stad j geven
we aan met cij, i, j {1, 2, . . . , n}. In het Handelsreizigersprobleem (Engels: Traveling
Salesman Problem) wil men de tour (= rondrit langs alle steden zodanig dat elke stad
precies een keer wordt aangedaan) bepalen, waarvan de totaal afgelegde afstand minimaal
is. Stel dat we een formulering P hebben waarbij we uitsluitend gebruik maken van de
volgende binaire variabelen
1 als stad j direct na stad i wordt bezocht
xij =
0 anders.
waarbij i, j {1, 2, . . . , n}.
a. Laat zien dat de onderstaande formulering Q een relaxatie is van het Handels-
reizigersprobleem:
min
n
n
c
i=1
j=1 ij xij
s.t.
n
j=1 xij = 1
1 i n
(Q)
n
x
i=1
ij = 1
1 j n
xij {0, 1}
1 i, j n.
Stel dat we een formulering voor het Handelsreizigersprobleem willen maken met een
polynomiaal aantal restricties. Naast de variabelen xij maken we daarom gebruik van de
variabelen
1 als stad i als p-de stad wordt bezocht in the tour
yip =
0 anders
waarbij i, j {1, 2, . . . , n}.
b. Geef een formulering van het Handelsreizigersprobleem (met een polynomiaal aantal
restricties) waarbij u uitsluitend gebruik maakt van de variabelen xij en yip. Geef
een duidelijke toelichting op uw formulering.
In de onderstaande onderdelen zijn p, q, r, s, t, u {1, 2, . . . , n} zes gegeven steden. Het
is in deze onderdelen in principe niet de bedoeling dat u behalve de xij-variabelen ook
1

---

andere variabelen gebruikt. Lukt het u echter niet om zo tot een correcte formulering te
komen, geef dan een formulering met extra variabelen. Bij een correcte formulering zal het
onderdeel dan gedeeltelijk goed worden gerekend. (Merk op dat u bij de beantwoording
van de onderstaande onderdelen het vorige onderdeel niet nodig heeft.)
c. Stel dat als extra restrictie geldt dat q niet direct na p mag worden bezocht als s
direct na r wordt bezocht. Modeleer dit als lineaire restrictie.
d. Stel nu dat als extra restrictie geldt dat q direct na p moet worden bezocht als
s direct na r wordt bezocht of als t direct na u wordt bezocht. Modeleer dit als
lineaire restrictie.
Opgave 2
Uncapacitated facility location (2 + 5 + 3 + 2 punten)
Het uncapacitated facility location (UFL) probleem kan als volgt beschreven worden. Een
bedrijf wil een aantal nieuwe fabrieken openen om de vraag van klanten M = {1, ..., m} te
voldoen. De mogelijke locaties voor de fabrieken bestaan uit de verzameling N = {1, ..., n}.
De vraag van elke klant moet worden voldaan door precies een fabriek. De transportkosten
voor het voorzien van de vraag van klant i M vanuit fabriek j N is gelijk aan cij 0.
Verder zijn de kosten voor het openen van een fabriek op locatie j N gelijk aan fj 0.
Het doel van het bedrijf is om te bepalen op welke plaatsen er fabrieken moeten worden
geopend zodanig dat de vraag van de klanten voldaan wordt en de totale kosten (transport-
en openingskosten) minimaal zijn. Het UFL probleem kan dan als volgt geformuleerd
worden:
min
m
n
c
f
i=1
j=1 ij xij +
n
j=1 j yj
s.t.
n
j=1 xij = 1
1 i m
xij yj
1 i m, 1 j n
xij {0, 1}
1 i m, 1 j n
yj {0, 1}
1 j 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 xij yj (1 i m, 1
j n) in de doelstellingsfunctie opnemen met de Lagrange multipliers ij (1 i
m, 1 j n). Geef de Lagrange functie en los deze op voor gegeven multipliers
ij (1 i m, 1 j n). Formuleer tevens het Lagrange duale probleem.
c. Leg uit wat een Lagrange heuristiek is. Geef vervolgens een Lagrange heuristiek
voor de in onderdeel b voorgestelde Lagrange relaxatie.
d. Is de in onderdeel b voorgestelde Lagrange relaxatie sterker dan de LP relaxatie?
Verklaar uw antwoord.
2

---

Opgave 3
Maximum stroom en Minimum snede (4 + 4 + 4 punten)
Beschouw het netwerk in Figuur 1 met bron s en put t. Op elke pijl is de capaciteit
weergegeven door het linkse getal en de stroom door het rechtse getal. De stroomsterkte
in het netwerk is dus 11.
a. Breid de stroom uit naar een maximum s, t-stroom en teken deze in Figuur 2 (geef
op elke pijl aan wat de stroom is).
b. Vind een minimum snede (B, P ) met s B en t P in het netwerk en leg uit hoe
u de minimum snede gevonden heeft. Omcirkel de punten in B en geef ook aan in
Figuur 2 welke pijlen er tussen B en P liggen.
c. Zij N = (V, A, c) een samenhangend netwerk met een bron s en een put t. Geef een
lineaire programmerings formulering voor het minimum snede probleem. Geef een
duidelijke uitleg van de gebruikte variabelen en restricties.
Opgave 4
Optimaal goederen vervoer m.b.v. DP (3 + 2 + 4 punten)
Een vrachtvliegtuig vervoert goederen en deze goederen hebben elk een bepaald gewicht
en een bepaald volume. Het totale volume van het vrachtvliegtuig wordt gegeven door
V kubieke meters en het totale laadgewicht door W ton. Er worden n goederen aangeboden
met vi en wi respectievelijk het volume in kubieke meters en het gewicht in ton van
transportgoed i, 1 i n. Bovendien is van ieder goed i de winst ri bekend. Het doel
van de vervoerder is om een selectie van de goederen te maken, zodanig dat de gewichts-
en volumerestrictie niet wordt overschreden en de winst maximaal is.
a. Geef een geheeltallige lineaire programmerings formulering voor het bepalen van
de optimale laadcombinatie. Geef een duidelijk uitleg bij de gebruikte beslissings-
variabelen en restricties.
Neem aan dat alle gewichten en volumes geheeltallig zijn. We willen nu bovenstaand
probleem met dynamisch programmeren (DP) oplossen. Daarvoor maken we gebruik van
k(v, w) : maximale winst voor goederen 1, . . . , k met beschikbaar volume v en beschik-
baar gewicht w,
waarbij k = 1, . . . , n, v = 0, . . . , V en w = 0, . . . , W .
b. Geef de initialisatie van het DP algoritme.
c. Geef de recurrente betrekking van het DP algoritme samen met een duidelijke
uitleg.
3

---

2, 2
-

6
3, 2
7, 5
7, 5
2, 1
3, 2
1, 1
2, 2
1, 1
2, 2
s
-?

R
R
- t
6

2, 1
6, 4
1, 1
1, 0
6, 4
3, 2
R?
R
-
3, 3
Figuur 1: Netwerk met stroomsterkte 11 bij Opgave 3
2,
-

6
3,
7,
7,
2,
3,
1,
2,
1,
2,
s
-?

R
R
- t
6

2,
6,
1,
1,
6,
3,
R?
R
-
3,
Figuur 2: Netwerk bij Opgave 3.a en 3.b
4

---