Diskret Optimering.

6. kursusgang, tirsdag den 21. september 12.30-16.15

Forelæsning i G5-109 ved LKJ:

12.30-13.00: Repetition.

14.55-16.15:

Maksimum strømnings problemet blev introduceret på side 23 i bogen. (Se eventuelt også definition 4.1 på side 92.)
Vi skal denne gang se på korteste vej problemet og maksimum strømnings problemet som lineære programeringsproblemer.
I afsnit 5.4, 5.5 og 5.6 ser vi primal-dual algoritmen anvendt på disse problemer.
I afsnit 6.1 beviser vi max-flow min-cut sætningen ved hjælp af dualitet.
Det er min plan at gennemgå resten af Kapitel 6 i løbet af ugen.

Opgaveregning:

Opgaver i Kapitel 3: 8, 13, 17, 21.
Opgave i Kapitel 5: 4.