Datalogisk Institut
Københavns Universitet

Introduktion til Optimering og Operationsanalyse, blok 2, 2005

[Meddelelser] [Opgaver] [Litteratur] [Pensum] [SIS]

Meddelelser

[6 feb] Information om reeksamen findes her (incl. eksamensspørgsmål)
[30 jan] Karakterliste er ophængt overfor DIKU's studieadministration.
[27 jan] Eksamenssæt 2006 (sidste 10 spørgsmål): pdf, vejl. løsning pdf.
[23 jan] Jakob's "Snydeark" findes her
[23 jan] Der er tilsyneladende studerende som er blevet afmeldt fra eksamen, selv om de opfylder kravet om at have fået godkendt begge projektopgaver. Skulle du være en af de uheldige, så kontakt Steen Brandt (email: steen@diku.dk, tlf: 35 32 14 40, kontor: S220) for at få rettet informationen. Jeg beklager meget de problemer det må have afstedkommet, og ønsker alle held og lykke ved eksamen - David.
[22 jan] Der er flere studerende som efterlyser deres projektopgaver. Jeg har i bunkerne i studieadministrationen fundet følgende rapporter (fødselsdato i parantes): OPT-P2 hold 2 (300383,100283,130884) godkendt
OPT-P2 hold 5 (160884,190482,160384) godkendt
OPT-P2 hold 7 (050676,010375,300682) godkendt
OPT-P2 hold 8 (250879,010380,060679) godkendt
OPT-P2 hold 11 (291177,280976,290979) godkendt
OPT-P2 hold 12 (150979,060575) godkendt
OPT-P2 hold 20 (221082) godkendt
OPT-P2 hold 22 (081080,2203082,290272) godkendt
Rapporterne kan afhentes i studieadministrationen. Jeg vil ikke udelukke at der findes yderligere rapporter som er lagt i en forkert bunke. - David.
[17 jan] Alle forfattere til "problematiske" projektopgaver har fået direkte besked pr. email. Så hvis du ikke har modtaget nogen besked kan du gå ud fra at opgaven er godkendt.
[13 jan] Skitse til løsning for projektopgave 2 vil være tilgængelig på nettet mandag 15 januar her
[13 jan] Projektopgave 2 kan hentes i studieadministrationen.
[10 jan] Løsning til "Written exam, 27 January 2006" (Q1-Q10) vil kunne hentes i kursets dueslag (samme sted som de hidtil uddelte noter) umiddelbart efter eksaminens afslutning.
[16. dec] Grundet en fejl har der i nogle få timer været adgang til en vejledende løsning fra hjemmesiden. Det betragtes som eksamenssnyd at benytte den vejledende løsning.
[16. dec] Mindre præcisering af opgave 8 i projektopgave 2. Den nye tekst findes nedenfor.
[6. dec] Projektopgave 2 er tilgængelig her. Forbehold for mindre rettelser.
Forside til P2 er findes her.
[28. nov] Her er en elektronisk forside til P1 pdf.
[15. nov] Øvelserne onsdag d. 16 nov for hold 3 rykkes til mandag d. 21 kl. 8.00 - 10.00. Dvs der er 4 timers øvelser for hold 3 på mandag og ingen imorgen onsdag.
[14. nov] Der er ingen øvelser første øvelsesgang i uge 46.
[14. nov] Der er oprettet 3 øvelseshold, se længere nede.

Forudsætninger

Videregående algoritmik (VA) - kan evt. følges sideløbende

Formål

Operationsanalyse (OR) blev introduceret i England i slutningen af trediverne med det overordnede formål at bistå beslutningstagere med at finde gode løsninger til realistiske problemer. Optimering udgør den vigtigste bestanddel af OR-værktøjet. Fra et anvendelsessynspunkt handler optimering typisk om bedst mulige udnyttelse af knappe ressourcer. Fra at teknisk synspunkt er det centrale spørgsmål at bestemme ekstreme værdier for funktioner af mange variable, hvor disse tillige skal tilfredsstille et antal begrænsninger. Kurset vil først beskæftige sig med Lineær Programmering (LP), hvor såvel den funktion, der skal maksimeres eller minimeres, som begrænsningerne er lineære funktioner af de variable. Under overskriften "Network flow problems" fortsættes med en række specielt strukturerede LP-problemer samt dertil hørende algoritmer. Kurset afsluttes med Kombinatorisk Optimering, som især omhandler LP-problemer med det ekstra krav at nogle eller alle variable kun må antage heltallige værdier.

Forelæsning og øvelser

Undervisere: Jakob Krarup (JK), David Pisinger (DP)

Forlæsninger: tirsdag 10:00-12:00 og fredag 10:00-12:00 i Auditorium 3, HCØ

Øvelser:

Hold 1 tirsdag og fredag 08:00-10:00 i N022, Niels Peter Milthers
Hold 2 tirsdag og fredag 08:00-10:00 i N026, Thomas Friis Antonsen
Hold 3 mandag og onsdag 10:00-12:00 i N018, Alima Saidi

Elektronisk materiale

Liste over rettelser til Wolsey findes her
IP-opgaver pdf
"Snydearket" pdf

Jakob's "snydeark"

Ved den afsluttende forelæsning (13.01) glædede det David Pisinger (og dermed også undertegnede) at høre om almindelig tilfredshed med kursus- forløbet. En enkelt studerende efterlyste dog et "snydeark", der rede- gjorde for forskelle i Tahas terminologi og den af mig anvendte. Jeg har gennemgået mine udleverede noter og sammenholdt dem med Tahas fremstilling. Afvigelserne er kun ganske få. Taha definerer "reduced cost" som z_j_ - c_j_ , hvor z_j_ = cost of consumed resources per unit of activity j og c_j_ = profit per unit of activity j I lighed med flertallet af lærebogsforfattere finder jeg det mere lo- gisk at vende fortegnet: "reduced cost" = c_j_ - z_j_, dvs. den oprin- delige "cost" _reduceres_ med beløbet z_j_. I de viste simplex-tabeller (mine noter) hvori "reduced costs" sty- rer dele af algoritmens forløb er Tahas "objektfunktionsrække" skrevet øverst, og min - hvis den er med - står nederst. Nogen navneforvirring kan desuden opstå af Tahas foretrukne "unit worth of a resource" som han alligevel vælger at kalde "dual price". I andre fortolkninger af samme begreb tales om "shadow prices" eller "sim- plex multipliers". Der henvises i øvrigt til diskussionen (Taha, siderne 35 og 135). God fornøjelse den 27. januar! Som det vil fremgå af eksamenssættets forside er det tilladt at bruge blyant, blot man skriver tydeligt. Jakob Krarup

Pensum

OPT-E05: Pensum, første kursusafsnit (15.11.05 - 02.12.05) ---------------------------------------------------------- H.A. Taha: Kap. 1-7 inklusive, med følgende bemærkninger: Afsnit 2.4: kun eksempel 2.4-1 Afsnit 2.5: overspringes Afsnit 3.4: kan erstattes af "The initial basic feasible solution" (se JK notesæt 4) Afsnit 5.5: overspringes Afsnit 4.4.2: overspringes Kapitel 6: Kun afsnittene 6.3 og 6.4 læses. Alle algoritmer kan ignoreres; flertallet er enten gennemgået ved AD+VA. Kapitel 7: Kun afsnittene 7.1 (uden 7.1.2) og 7.5 læses. Generelt: Af Taha's mange "examples", "problems sets" og "comprehensive problems" kræves kun kendskab til de eksempler, der måtte være nævnt under fore- læsningerne (og i så fald med udleverede kopier af viste transparenter) og de opgaver, der er udvalgt til øvelserne. Alt stof om specifikke pro- grampakker (TORA, Excel, LINGO, AMPL) kan overspringes. Da VA (Videregående Algoritmik) er en forudsætning for at følge OPT, antages begreber som "Complementary Slackness Condition" og "unimodular- ity" kendte. ............................................................ Der har under kursusafsnittet været lejlighed til at stifte bekendtskab med flere tidligere eksamens- og projektopgaver. Det kan forventes, at opgaven til skriftlig eksamen, 27. januar 2006, vil blive "et eller andet" i samme stil, og at alle hjælpemidler i form af bøger og noter men _ikke_ lommeregner vil være tilladte. Med bogen ved hånden vil man således ikke blive krævet til regnskab med hensyn til eksempelvis lange korrrekthedsbeviser for diverse algoritmer. Hvis et spørgsmål lyder: "gør dette eller hint" og der _ikke_ stilles krav om en specifik fremgangsmåde, er man frit stillet i valg af denne. Bedes der explicit om brug af simplex algoritmen, er man ligeledes frit stillet i valg mellem slackformen eller tableauformatet. Det vides ikke i skrivende stund, om det vil være tilladt at bruge blyant (og viskelæder) ved den skriftlige eksamen. Nævnes det ikke tid- ligere på kursets hjemmeside, vil det i hvert fald fremgå af opgavesæt- tets forside.

Undervisningsplan

Foreløbig plan for kurset. Forbehold for ændringer.

Dato	Lærer	Indhold/Emne	Projektopgave	Litteratur	Plancher	Opgaver
ti:15/11 fr:18/11	JK	Modelbygning			udleveres ved forelæsningen	Til 2. øvelsesgang: TAHA 3.1A 1, 2 TAHA 3.2A 2 TAHA 3.3B 2(a,b) TAHA 3.3C 1 (Løs LP problemet i hånden og vha. Cplex TAHA 3.4A 3, 5 (Kun a og b) TAHA 3.4B 3 (Kun a og b) TAHA 3.5A 2 (Løs a i hånden og b med cplex) TAHA 3.5B 1 TAHA 3.5C 2
ti:22/11 fr:25/11	JK	Post-optimal analyse	P1 stilles 25/11		udleveres ved forelæsningen	Til 1. øvelsesgang: TAHA 4.1A 4,6 TAHA 4.2C 2,6 TAHA 4.2D 3,4 Skriftlig eksamen 4. januar 2005, S1-S10, (udleveret i notesæt 2) Til 2. øvelsesgang: Skriftlig eksamen 10. juni 2003
ti:29/11 fr:2/12	JK	Flow problemer			udleveres ved forelæsningen	Skriftlig eksamen 18. december 1997
ti:6/12 fr:9/12	DP	ti:Modelbygning fr:Branch-and-bound	P1 afleveres 9/12	ti:Williams 9,10 (fotokopi i dueslag) fr:Wolsey 7	ti:pdf fr:pdf	Til 1. øvelsesgang: Skriftlig eksamen 17. december 2003 Til 2. øvelsesgang: IP-opgaver: 4, 5, 6, 24. Eksamenssæt 1998: Q17, Q18. Eksamenssæt 2001: Q20.
ti:13/12 fr:16/12	DP	ti:Snitplan metoder fr:Snitplan metoder	P2 stilles 13/12	ti:Wolsey 8 fr:Wolsey 8,9	ti:pdf fr:pdf	Til 1. øvelsesgang: IP-opgaver: 7, 8, 9, 25. Eksamenssæt 2000: Q19. Eksamenssæt 1999; Q11, Q12. Til 2. øvelsesgang: IP-opgaver: 11, 14, 15. Eksamenssæt 1998: Q11, Q12, Q13. Eksamenssæt 1999: Q15, Q16, Q17.
ti:3/1 fr:6/1	DP	ti:Stærke lovlige uligheder fr:Grænseværdier		ti:Wolsey 9 fr:Wolsey 10	ti:pdf fr:pdf	Til 1. øvelsesgang: IP-opgaver: 10,16,17. Eksamenssæt 2000: Q11, Q20, Q16, Q17, Q18. Til 2. øvelsesgang: Eksamenssæt 1999: Q13, Q14. Eksamenssæt 2000: Q13. Eksamenssæt dec2003: Q17, Q18, Q19, Q20. Projektopgave 2 (diskussion)
ti:10/1 fr:13/1	DP	ti:Grænseværdier fr:Dantzig-Wolfe dekomponering	P2 afleveres 10/1	ti:Wolsey 10 fr:Wolsey 11	ti:pdf fr:pdf	Til 1. øvelsesgang: IP-opgaver: 21, 22, 23 Eksamenssæt 1999: Q19, Q20. Eksamenssæt 2000: Q14, Q15 Til 2. øvelsesgang: Eksamenssæt juni2003 (alt), Eksamenssæt juni2004 (alt)

Eksamen

Eksamen 27. januar 2006
Reeksamen 21. april 2006

Opgaver

Eksamenssæt 1998 (sidste 10 spørgsmål) pdf
Eksamenssæt 1999 (sidste 10 spørgsmål) pdf
Eksamenssæt 2000 (sidste 10 spørgsmål) pdf
Eksamenssæt 2001 (sidste 10 spørgsmål) pdf
Eksamenssæt juni2003 pdf (1.6Mb),
Eksamenssæt dec2003 (sidste 10 spørgsmål) pdf
Eksamenssæt juni2004 (sidste 10 spørgsmål) pdf
Eksamenssæt jan2005 (sidste 10 spørgsmål) pdf

Løsninger til opgaver gennemgået ved øvelserne

Den bedste gennemgang af opgaverne finder sted ved øvelserne, men skulle du have været syg findes her forslag til besvarelser:

IP-opgaver

Opgave 1	Opgave 2	Opgave 3	Opgave 4	Opgave 5	Output 5
Opgave 6	Output 6	Opgave 7	Output 7	Opgave 8	Output 8
Opgave 9	Opgave 10	Opgave 11	Opgave 14	Opgave 15	Output 15
Opgave 16	Output 16	Opgave 17	Opgave 24	Opgave 25

Gamle eksamenssæt

dec 1998 dec 1999 dec 2000 dec 2001 juni2003 dec 2003 juni 2004 jan 2005

Litteratur

H.A. Taha "Operations Research", 7th. Edition, Prentice Hall(Pearson Education International), 2003
(ISBN 0-13-048808-9)
L.A. Wolsey, "Integer Programming", Wiley 1998
H. P. Williams, "Model Building in Mathematical Programming", Wiley 1990 (Fotokopier findes i dueslaget)

[ Upwards | DIKU Home ]