Diskret optimering

1. kursusgang, onsdag den 23. september 8.15-12.00

8.15-8.40:

Introduktion til kurset. Introduktion til lineær programmering (LP).
LP betyder: find maximum af lineær funktion i et område afgrænset af hyperplaner.

10.40-12.00:

Kapitel 2 handler om lineær programmering og forudsætninger for LP.

• Afsnit 2.1: Hyperplaner og konvekse mængder i Rⁿ.
• Afsnit 2.2: Polytoper og polyedre, områder afgrænset af hyperplaner.
• Afsnit 2.3.  (Hvis vi når det fortsætter vi med dette afsnit, ellers er det her vi starter i næste uge.)
  

Opgaveregning:

1. Løs følgende LP-problemer grafisk:
   
   • max{2x₁+3x₂ |  x₁+x₂<=5, 2x₁+x₂<=7, x₁>=0, x₂>=0}
   • max{2x₁+5x₂ |  -2x₁+3x₂<=6, 7x₁-2x₂<=14, x₁+x₂<=5, x₁>=0, x₂>=0}
2. Undersøg hvilke funktioner i Maple pakkerne "simplex" og "Optimization" der kan løse ovenstående LP-problemer.
3. Gennemgå Application 1.2. Forklar hvorfor metoden løser problemet.
4. Opgave 1.1.