MAI - Matematiska institutionen

TAOP33 Kombinatorisk optimering gk

Information om distansundervisning

(Detta gällde 2020 och 2021.) Att läsa kursen på distans kräver betydande eget ansvar. Nedan följer en detaljerad lista på hur man kan göra för att lära sig stoffet i kursen på distans.

På kurshemsidan finns mycket material, bl.a. alla föreläsningsbilder, i flera varianter, dels några för utskrift, med fyra bilder på varje sida, inte riktigt fullständig, och dels precis de bilder som visas på föreläsningen. Ni ska ladda ner de senare, och titta på den med en pdf-visare som visar en sida i taget. Bilderna är nämligen gjorda så att en rad i taget kommer fram. Skriv inte ut! Bläddra inte igenom bilderna för snabbt, utan fundera på vad som står, innan ni går vidare till nästa bild.

Det finns också filmer, dels lite äldre, gjorde för några år sedan, med exempellösning från föreläsningarna, och dels nya, gjorda för denna variant av kursen, för valda delar av föreläsningarna.

Nedanstående rekommenderade tillvägagångssätt för föreläsningarna innehåller följande delar: Bläddra igenom föreläsningsanteckningar, dvs. kör en föreläsning hemma själv. Se filmer (och hör mig föreläsa). Läs avsnitt i boken, för att få den kompletta bilden. Dessa tre delar täcker samma stoff, men kompletterar varandra till ett fullt inlärande.

Lektioner planeras i nuläget att göras med ett interaktivt vertyg, Teams, på de tider som anges i schemat.

Frågor till Kaj skickas lämpligtvis in med email, till kaj.holmberg@liu.se. Notera möjligheten att skicka med en bild på anteckningar eller datorskärm. Jag har lagt in schemalagd tid i nedastående lista, som hållpunkter för när i tiden saker bör göras. Om schemat i TimeEdit och denna sida visar olika tider, är det TimeEdit som gäller. Nedan anges vilka sidor i föreläsningsbilderna man ska stega igenom. Vissa pdf-visare räknar sidor mer "generöst", de siffrorna anges inom parantes.

Denna sida kan uppdateras ofta. Det som ligger långt fram i tiden kan vara fel.

Förändring från 2020: Föreläsning 2 och 3 har slagits ihop, så simplexmetoden och LP-dualitet behandlas tillsammans. (Tyvärr har jag inte hunnit numrera om filmer mm.)

1. Fö 1: Introduktion: Tis v 35 2021-08-31 10:15 - 12:00
   Se film fö 1-1: Kursintroduktion.
   Stega igenom fö 1, sid 1-9 (1-92).
   Se film fö 1-2: Några kända exempel.
   Stega igenom fö 1, sid 10-16 (93-101).
   Se film fö 1-3: Är handelsresandeproblemet svårt?
   Stega igenom fö 1, sid 17-20 (102-146).
   Se film fö 1-4: Ett första exempel.
   Stega igenom fö 1, sid 21-29 (147-195).
   Läs bok kap 1.
   Stega igenom fö 1, sid 30-33 (196-214).
   Se film fö 1-5: Tillämpningar.
   Stega igenom fö 1, sid 34-110 (215-314)
   
2. Le 1: Ons v 35 2021-09-01 13:15 - 15:00
   3.2 (film), 2.2, 3.3, 3.9a.
3. Fö 2: Simplexmetoden och LP-dualitet: Tis v 36 2021-09-07 10:15 - 12:00
   Läs bok kap 2.
   Se film fö 2-0: Konvexitet och polyeder.
   Se film fö 2-1: Simplexmetoden.
   Stega igenom fö 2a, sid 1-7 (1-60).
   Stega igenom fö 2a, baslösningar, sid 8-12 (61-82).
   Stega igenom fö 2a, byta bas, sid 13-14 (83-106).
   Stega igenom fö 2a, matrisbeteckningar, sid 15 (107-116).
   Stega igenom fö 2a, metoden, sid 16-22 (117-169).
   Stega igenom fö 2a, sid 23-28 (170-203).
   Läs bok kap 6 (ej 6.4).
   Se film: Simplexmetoden: Exempel.
   Se film fö 2-2: Sammanfattning av LP-dualitet.
   Se film fö 2-3: LP-dualitet.
   Stega igenom fö 2b, sid 1-11 (1-53).
   Stega igenom fö 2b, sid 12-13 (54-64).
   Stega igenom fö 2b, sid 14-20 (65-113).
   Läs bok kap 7.1 - 7.5.
   Se film: LP-dualitet: Exempel.
   Stega igenom fö 2b, sid 21-33 (114-183).
   Läs bok kap 7.7.
   Stega igenom fö 2b, sid 34 (184-185).
   
4. Le 2: Ons v 36 2021-09-08 13:15 - 15:00
   6.5 (film), 6.12, 6.16, 6.20.
   7.1 (film), 7.10, 7.4, 7.18d,e, 7.17.
   
5. Läs instruktioner till lab 1, läs på om Vileopt, och förbered labben.
   Se film om Vileopt.
6. Lab 1: Simplexmetoden och LP-dualitet
   Fre v 36 2021-09-10 08:15 - 10:00
   
7. Läs instruktioner till lab 3, läs ev. på om Python/Matlab, och förbered labben.
   
8. Lab 3: Formulering och lösning med programvara
   Mån v 37 2021-09-13 08:15 - 10:00
   
9. Fö 3: Grafer, träd, cykler: Tis v 37 2021-09-14 10:15 - 12:00
   Se film: Sammanfattning av föreläsningen.
   Se film: Grafintro.
   Stega igenom fö 3, sid 1-14 (1-70).
   Läs bok kap 10.1.
   Läs bok kap 10.2.
   Se film: Billigaste uppspännande träd, formulering.
   Se film: Billigaste uppspännande träd, exempel.
   Stega igenom fö 3, sid 15-21 (71-122).
   Läs bok kap 10.3.
   Se film: Handelsresandeproblemet.
   Se film: Handelsresandeproblemet, exempel.
   Stega igenom fö 3, sid 22-45 (123-248).
   Se film: Matchningsproblemet.
   Stega igenom fö 3, sid 46-57 (249-341).
   Stega igenom fö 3, sid 58-65 (342-385).
   Läs bok kap 10.4 - 10.7.
   Se film: Kinesiska brevbärarproblemet: Exempel.
10. Le 3: Ons v 37 2021-09-15 13:15 - 15:00
    10.16 (film), 10.9d (film), 10.8, 10.1, 10.4, 10.12, 10.13, 10.21.
    
11. Fö 4: Vägar och flöde: Tis v 38 2021-09-21 10:15 - 12:00
    Se film: Intro billigaste väg.
    Se film: Sammanfattning av fö.
    Stega igenom fö 4, sid 1-14 (1-53).
    Stega igenom fö 4, Ford, sid 15-18 (54-92).
    Se film: Korrekt Dijkstra-algoritm.
    Stega igenom fö 4, Dijkstra, sid 19-21 (93-132).
    Stega igenom fö 4, sid 22-25 (133-153).
    Läs bok kap 11.1, 11.2.
    Se film: Billigaste väg: Exempel.
    Stega igenom fö 4, flöde, formulering, sid 26-31 (154-189).
    Stega igenom fö 4, maxflöde, sid 32-35 (190-225).
    Läs bok kap 12.2.
    Se film: Maxflödesproblemet.
    Stega igenom fö 4, dynp, sid 36-40 (226-255).
    Läs bok kap 11.3.
    Se film: Dynamisk programmering för kappsäcksproblemet.
12. Fö 5: Flöde i nätverk: Ons v 38 2021-09-22 13:15 - 15:00
    Se film: Sammanfattning av fö.
    Stega igenom fö 5, sid 1-7 (1-38).
    Se film: Lösningsmetod för minkostnadsflödesproblem
    Stega igenom fö 5, sid 8-13 (39-124).
    Se film: Simplexmetoden för minkostnadsflödesproblemet: Exempel.
    Stega igenom fö 5, sid 14 (125-130).
    Läs bok 12.1, 12.3.
    Se film: Ungerska metoden för tillordningsproblemet.
    Stega igenom fö 5, sid 15-22 (131-208).
    Läs bok 12.4.
    Stega igenom fö 5, sid 23-28 (209-214)
    
13. Le 4: Ons v 38 2021-09-22 15:15 - 17:00
    11.1 (film), 11.12, 12.2 (film), 12.1, 11.9, 11.11.
    
14. Le 5: Fre v 38 2021-09-24 08:15 - 10:00
    12.5 (film), 12.7, 12.18 (film), 12.24.
    
15. Läs instruktioner för lab 2, införskaffa en problemtext, läs på om Vineopt, och förbered lab 2 genom att formulera nätverket.
    Se film om Vineopt.
16. Lab 2: Vineopt, minkostnadsflödesproblem
    Mån v 39 2021-09-27 08:15 - 10:00
    
17. Fö 6: Heltal: Tis v 39 2021-09-28 10:15 - 12:00
    Se film: Heltalsoptimering.
    Stega igenom fö 6, sid 1-16 (1-77).
    Läs bok kap 3.
    Se film: Litet heltalsexempel.
    Stega igenom fö 6, sid 17-20 (78-101).
    Stega igenom fö 6, sid 21-30 (102-194).
    Läs bok kap 13.1, 13.2.
    Se film: Land-Doig-Dakins metod för linjära heltalsproblem.
    Stega igenom fö 10, fö 6, Balas, sid 31-47 (195-278).
    Stega igenom fö 10, fö 6, TSP, sid 38-43 (279-323).
    Läs bok kap 13.3.
    Stega igenom fö 10, fö 6, plansnittning, sid 44-48 (324-365).
    Läs bok kap 14.
    
18. Le 6: Ons v 39 2021-09-29 08:15 - 10:00
    (film)13.10, 14.3 (film), 13.9, 13.15, 13.7a,b,d.
    
19. Läs instruktioner för lab 4 (och 5) och förbered labben.
    
20. Lab 4: Heltal
    Fre v 39 2021-10-01 08:15 - 10:00
    
21. Fö 7: Komplexitet, heuristiker: Tis v 40 2021-10-05 10:15 - 12:00
    Se film: Komplexitet.
    Stega igenom fö 7, komplexitet, sid 1-13 (1-92).
    Läs bok kap 15.
    Se film: Heuristiker.
    Stega igenom fö 7, heur, sid 14-34 (93-282).
    Se film: Exempel på olika heuristiker.
    Läs bok kap 16.1 - 16.3.
    Se film: Lokalsökning och utvidgningar.
    Stega igenom fö 7, sid 35-46 (283-396).
    Läs bok kap 16.4 - 16.5.
    Se film: Grön optimering.
    
22. Le 7: 16.1a,c, 16.4 (film), 16.12, 16.13, 16.17.
    
23. Läs instruktioner för lab 5 och förbered labben, genom att konstruera en girig heuristik för lokaliseringsproblemet.
    
24. Lab 5: Heuristik
    Ons v 40 2021-10-06 13:15 - 15:00
    

25. Se film: Sammanfatting av olika problemstrukturer.
    Se film: Sammanfattning av kursen.
    (Dessa sammanfattningsfilmer är gjorda för en lite större kurs, men om man bortser från allt olinjärt passar de för TAOP33 också.)

Sidansvarig: Kaj Holmberg
Senast uppdaterad: 2022-08-30