Diskret optimering - 4

4. kursusgang, torsdag den 14. september 8.15-12.00

8.15-8.45:

Eksempel på lineær programmering.
Mere fra afsnit 2.4.
Et LP-eksempel i Maple

10.40-12.00:

• Afsnit 2.4: Dualitetssætningen.
• Sætning 2.3 i afsnit 2.2.
• Afsnit 3.1 og 3.2. Tilbage til grafteori.
  

Opgaveregning:

1. (19) 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 (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.