Diskret Optimering.

5. kursusgang, fredag den 17. september 8.15-12.00

Forelæsning i G5-109 ved LKJ:

8.15-8.45: Repetition.

10.40-12.00:

Afsnit 3.4: anvendelse af lineær programmering i forbindelse med korteste veje i grafer.
Afsnit 3.3: Farkas' lemma. Dette lemma bruges i andre bøger til at bevise sætning 3.1, men ikke i vores bog.
Afsnit 5.1 og 5.2 om primal-dual algoritmen.

Opgaver:

Bogen beskriver på side 28 tre måder man kan omskrive et LP:
1. erstat en ligning med to uligheder
2. erstat en ubegræset variabel med to variable, der er ikke-negative.
3. erstat en ulighed med en ligning ved indførelse af en surplus/slack variabel.
Betragt et LP på generel form og dets duale, som defineret i Definition 3.1.
For hver af de tre ovennævnte operationer: undersøg hvordan det duale LP påvirkes når operationen udføres det oprindelige LP.

Opgaver fra bogen:
Opgaver i Kapitel 3: 11, 14, 18.