Diskret optimering

3. kursusgang, fredag den 9. oktober 8.15-12.00

8.15-8.40:

Lidt om lineær programmering og introduktion til dualitet, afsnit 2.4.

10.40-12.00:

• Afsnit 2.4: Dualitetssætningen.
• Sætning 2.3 i afsnit 2.2.
• Afsnit 3.1. Vi begynder på noget grafteori.

Opgaveregning:

1. (18) på side 14 er et heltals lineær programmerings problem.
   Ved at erstatte betingelserne x_i \in {0,1} med 0 <= x_i <= 1 fås et lineært programmerings problem.
   Løs dette (evtuelt ved hjælp af Maple) og undersøg om løsningen er heltallig.
2. Konstruer det duale LP til ovenstående.
3. Betragt et generelt LP. Sammenlign det duale af det duale LP med det oprindelige LP. Er dual² = identitet ?
4. Opgave 2.23.
5. Opgave 2.24.