TelekryptoLinjär och Kombinatorisk Optimering, LP1 VT 2005.

Omtenta-2005 :

6 september - 16 september, hämtas här. Meddela i förväg (tom 5 september) om du planerar att tentera. Om ingen meddelar att vill tentera blir omtenta i januari (alt. juni).

Sista Tentamen - (juni 2005):

  • pdf.

    Kursen i Linjär och Kombinatorisk optimering ges under lp1 våren 2005. Nedanstående information är delvis tagen från läsåret 1999. Mycket av informationen kommer att uppdateras under kursens gång. Hör av dig till kursledaren ufn@maths.lth.se om du har några frågor.

    Föreläsningar:

    Onsdagarna 8-10, MH:333; Fredagarna 13-15, MH:332A.

    Godkända i Lab och Inlämningsuppgifter:

  • pdf.

    Utdelat material och kortfattade komihåg.


    Vad händer sen?

    För er som är intresserade av att lära mer om optimering och närliggande ämnen kan jag rekommendera följande evenemang:

    Litteratur:

    Dessutom har jag när jag förberett lektionerna inhämtat material från:

    Matlab:

    För er som vill ha mer information om och kring matlab, kan jag rekommendera. För studenter finns matlab att få via UB. För en liten avgift kan man hämta hem senaste versionen till PC och Mac. Se även denna länk.

    Laborationer

    I kursen ingår två obligatoriska laborationer.
    1. Simplexmetoden för att lösa linjärprogrammeringsproblem.
    2. Transportproblemet, maximalt-flöde-minsta-snitt, algoritimer för kombinatorisk optimering.

    Övningsförslag ur kursboken

    1. 1.1: 4.
    2. 1.3: 33, 37.
    3. 1.5: 1, 6.
    4. 2.1: 1, 9, 19, 21.
    5. 2.3: 3, 20.
    6. 3.1: 1, 3, 7.
    7. 3.2: 1, 5, 9, 11.
    8. 3.3: 1.
    9. 3.4: 1, 9.
    10. 3.5: 1, 3, 10, 11, 12.
    11. 3.6: 1, 5.
    12. 4.1: 1.
    13. 4.2: 1, 3, 5.
    14. 4.3: 1, 3.
    15. 5.1: 9, 11, 15.
    16. 5.3: 1, 5.
    17. 5.4: 1, 3, 7.

    Föreläsningssprogram

    on 19/1 Grundläggande begrepp
    Kombinatorisk optimering
    Linjärprogrammering (Kapitel 1)
    fr 21/1 Simplexmetoden (Kapitel 2)
    on 26/1 Dualitet (Kapitel 3)
    fr 28/1 Dualitet (Kapitel 3)
    on 2/2 Heltalsprogrammering (Kapitel 4)
    fr 4/2 Heltalsprogrammering (Kapitel 4)
    `Branch and Bound'
    on 9/2 Maximalflödesproblemet (Kapitel 5.3, 5.4)
    Transportproblemet (Kapitel 5.1)
    Tillordningsproblemet (Kapitel 5.2)
    fr 11/2 Algoritmkomplexitet
    Karmarkars algoritm
    Ellipsoidmetoden
    on 16/2 Konvex Optimering
    Dinamisk programmering
    fr 18/2 Simulerad Stelning
    on 23/2 Genetiska Algoritmer
    fr 25/2 Neurala Nätverk
    on 2/3 Tabusökning. Voting methods.
    fr 4/3 Repetition

    Examination

    Examination på kursen bygger på fyra moment:

    1. 4 inlämningsuppgifter.
    2. 2 laborationer.
    3. En hemtenta. Vi diskuterar senare i kursen tider för denna.
    4. Om hemtentan är godkänd bestäms en tid för diskussion av tentamen.
    För slutbetyg på kursen krävs godkänt på inlämningsuppgifter, laborationer och hemtentamen samt godkänd tentamensdiskussion.

    Gamla tentor

  • 2003.
  • 2004.

    Länkar till hemsidor om linjär och kombinatorisk optimering

    1. Global Optimering.
    2. Vanliga frågor om linjärprogrammering.
    3. Boyd's research group index. Stephen Boyd är en av experterna inom området konvex optimering. Han har många värdefulla referenser, bland annat till fritt tillängliga lösare för Linjär programmerings problem och vissa utvidgningar av LP, (kvadratisk programmering, semidefinit programmering, etc.).
    4. The SDPpack Home Page Ett paket för semidefinit programmering.
    5. SDPSOL En del av samma paket.
    6. PCx Linear Programming Code En effektiv LP-lösare.
    7. Handelsresandeoptimering med genetiska algoritmer.
    8. Myror i optimering
    9. Dopplertomografi med lokalsökning.

    Här kan man läsa om dagens matematiker och om populära matematiska konstanter.


    Victor Ufnarovski
    Department of Mathematics (LTH)
    Lund Institute of Technology / Lund University
    Box 118, 221 00 LUND

    Room: 426
    Direct Phone: +46 46 22 245 48
    Dept. Phone: +46 46 22 285 37
    Fax: +46 46 22 240 10
    e-mail: ufn@maths.lth.se
    www: http://www.maths.lth.se/matematiklth/personal/ufn/