Besliskunde 1/ Optimalisering (6 EC punten), 2013
Technische Wiskunde (TUD), Wiskunde (Leiden)
Algemeen
Besliskunde 1/Optimalisering gaat over optimalisatie van lineaire functies op R^n of Z^n, onder lineaire randvoorwaarden. Het vak valt onder de verantwoordelijkheid van Prof. K.I. Aardal, TUD. Vervolgvakken binnen de Besliskunde in Leiden zijn Besliskunde 2 (Speltheorie en Stochastische Besliskunde) en Besliskunde 3 (Grafentheorie, Lineaire Modellen, Netwerkoptimalisatie, Combinatoriek en Enumeratie, Semi-definite Programmering of Robuuste Optimalisering). Voor BK2 is BK1 niet noodzakelijk, maar een enkele keer wel handig. BK3 is wel gedeeltelijk een vervolg op BK1. Nadere informatie is te vinden op de respectievelijke sub-pagina's BK2.html en BK3.html.

Docent en assistenten

Hoorcollege: Dr. Floske Spieksma, spieksma@math.leidenuniv.nl, kr. 228
Werkcollege Leiden, contactpersoon huiswerk: Herman Blok, blokh1@math.leidenuniv.nl, kr. 217
Werkcollege Delft, contactpersoon huiswerk: Pieter van den Berg, P.L.vandenberg@tudelft.nl, kamer HB 04.130

Werkvorm
De hoorcolleges zijn op de woensdag in Leiden:

13.45-15.30 Snellius B1 (laatste college in Snellius 405

De werkcolleges zijn op de vrijdag:

in Leiden : 9-10.45 zaal 412

In tegenstelling tot wat in het rooster staat, zal er geen vragenuurtje zijn voor de Delftse studenten met een dubbele Bachelor. Dezen kunnen in plaats daarvan op afspraak langskomen bij Pieter.

Literatuur

Christos H. Papadimitriou, Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity,
Dover Publications, Inc. Mineola, NY, 1998, Paperback.
Extra materiaal bestaande uit college aantekeningen van Prof. Aardal (eerste 7 colleges) en dictaat van Dr. Spieksma (resterende colleges) (zie programma).
Aantekeningen Prof. Aardal met materiaal gerelateerd aan colleges 8-13 zijn hier verkrijgbaar: extra1,extra2, extra3, extra4, extra5, extra6, TPprobleem.
Op college besproken stof
Naslagwerk en extra opgaven zijn te vinden in het oude Besliskunde 1 dictaat, Hoofdstukken 1 en 4, zie hier.

Toetsing
Het vak wordt getoetst via 4 verplichte inleveropgaven, en een schriftelijk tentamen.

Het cijfer voor het huiswerk is het gewogen gemiddelde van de vier opgaven.
Voor huiswerk en tentamen moet minstens een 6 gehaald zijn
Het eindcijfer wordt berekend via de formule
max{tentamencijfer, 0,65 x tentamencijfer + 0,35 x huiswerkcijfer}

Het huiswerkcijfer blijft geldig tot en met het hertentamen in april 2014.

Manier van inleveren van huiswerk
Handgeschreven uitwerkingen zijn toegestaan mits goed leesbaar!

Huiswerk wordt bij voorkeur in koppels ingeleverd, maar elke student moet in staat zijn zijn ingeleverde huiswerk goed te kunnen uitleggen en te verdedigen. Overschrijven van elkaar is niet toegestaan.
Bewaar zelf een kopie van hetgeen je inlevert.
De uitwerkingen moeten duidelijk zijn; motiveer de gemaakte stappen, voer de notatie op een duidelijke manier in.
Schrijf naam en studentnummer op alle ingeleverde vellen.
Huiswerk moeten worden ingeleverd in hardcopy in het postvak van je assistent (4de verd. in Delft, 2de verd. in Leiden) of electronisch als 1 pdf-bestand per email naar je assistent.
Inleverdata staan in het programma, het uiterste tijdstip is 23.59 van de betreffende dag.

Uitslagen van huiswerk en tentamen kun je hier: Delft en Leiden vinden.

Weekprogramma
Het weekprogramma (te behandelen stof en te maken opgaven) wordt in de loop van het college wekelijks bekend gemaakt. Hieronder staat een voorlopig programma, inclusief de huiswerkinleverdata, links naar de huiswerkopgaven, en naar de collegeaantekeningen, zodra deze bschikbaar zijn gesteld.


Week	Datum	Activiteit	Stof	Onderwerp
Wk 1	04/09	HC	P&S: 1, App. A2 aant-C1 N.B. info op eerste 2 slides klopt niet!! grafische uitwerking LP	Introductie
	06/09	WC	E1	Opgaven: P&S: 1.1a, 1.5 (alleen N_2(t)), 1.6, 1.7, 1.11, (1.15). E1: 2.
Wk 2	11/09 13.30 in C3	HC	P&S: 2.1-2.3 aant-C2	LP in standaardvorm, basisoplossing, polyeder, polytoop, relatie hoekpunt polyeder en bfs.
	13/09	WC	2, E2	Geometrie van LP Opgaven: 2.1, 2.3, E2.
Wk 3	18/09 13.45 in C3	HC	P&S: 2.4-2.6, 2.8 aant-C3	Simplexalgoritme
	20/09	HC	2.5, 2.7, uitgewerkte simplexopgaven, E3	Simplex: tableauvorm, cycling Opgaven: E3
Wk 4	25/09 13.45 in C3	HC	P&S: 3.1 aant-C4	Dualiteit
	26/09	Huiswerk	HW1	Oplossingen inleveren!
	27/09	WC	P&S 3, E4	Opgaven: 3.11, E4
Wk 5	Collegevrij TUD+UL
Wk 6	9/10 13.45 in C3	HC	P&S: 3.2-3.6 aant-C5	Farkas' Lemma, Complementary Slackness (toepassing: Kortste paden), duale simplex
	11/10	WC	3, E5	Opgaven: 3.6*, 3.14, 3.19, E5.
Wk 7	16/10 13.45 in C3	HC	6.1-6.3 aant-C6(a), aant-C6(b), Ford-Fulkerson algoritme	Max flow, min cut; Ford-Fulkerson en Dijkstra
	18/10	WC	6.3, 6.4, E6	Ford-Fulkerson en Dijkstra vervolg Opgaven: E6
Wk 8	23/10 13.45 in B1 (Snellius!!!)	HC	81-8.5, aant-C7 (Blok)	Analyse van algoritmen
	24/10	Huiswerk	HW2	Oplossingen inleveren!
	25/10	WC	8.6, E7	Simplex is niet polynomiaal Opgaven: 8.3, 8.6a, 8.7, E7.
Wk 9	30/10 13.45 in B1	HC	12.1, 12.3, 12.4 en BK1-C8.pdf: Algoritmes 1.7, 1.8, 1.9 incl correctheidsbewijs en complexiteit Huiswerk 3 is beschikbaar	Opspannende bomen en matroiden
	1/11	WC	12.2 12, BK1-C8.pdf	Een O(\|E\| log\|V\|) greedy algoritme voor MST 12.1, en de opgaven 1.5, 1.15, 1.16, 1.17 uit BK1-C8.pdf
Wk10	Collegevrij TUD+UL		Aantekeningen van Prof. Aardal zijn vanaf college 8 supplementair
Wk11	13/11 13.45 in B1	HC	13.1-13.2 en BK1-C9.pdf	Geheeltallige optimalisering, totale unimodulariteit, transportprobleem (begin)
	15/11	WC	13, E9	13.1 Example 13.1 Nonlinearities Opgaven: 13.1, 13.9, E9
Wk12	20/11 13.45 in B1	HC	BK1-C9.pdf (vervolg)	Transportprobleem vervolg
	22/11	WC		Opgaven: (i) restant (13.1, 13.9, E9) vorige week (ii) Transportprobleem BK1-C9.pdf: Opgave 7.3, Vraag 7.3, Vraag 7.4
Wk13	27/11 13.45 in B1	HC	BK1-C10-13.pdf Hoofdstuk 1, paragraaf 1.2 tot stelling 1.4 15.1-15.6	Complexiteit
	28/11	Huiswerk	HW3	Oplossingen inleveren!
	29/11	WC		BK1-C10-13.pdf: Vragen 1.4, 1.5, Opgaven 1.3, 1.4
Wk14	4/12 13.45 in B1	HC	BK1-C10-13.pdf Hoofdstuk 1, 3-SAT zit in NPC, Hoofdstuk 2,paragrafen 2.1-2.3 18.1, 14.1 Huiswerk 4 is beschikbaar	Branch-and-Bound (B&B)
	6/12	WC	E12	Duale simplex, E12: Opgave 2 BK1-C10-13.pdf: Opgaven 2.3, 2.5, 2.6, 2.7
Wk15	11/12 13.45 in 405	HC	14.1 BK1-C10-13.pdf Hoofdstuk 2.3.1	Gomory fractiesnede algoritme `Normaal'test
	13/12	WC	E13	Opgave in E13 BK1-C10-13.pdf Opgave 2.8, vraag 2.6 (zonder condities op keuze bronrij en pivotkolom) restant vorige week en eventueel HW3 uitleg
Wk17	24/12	Huiswerk	HW4 Hint voor opgave 7.6 van BK1-C9.pdf: Je mag zelf een startoplossing kiezen. Als je een standaardregel toepast, moet je eerst een volledige bipartiete graaf maken, en per toegevoegde tak `hoge' kosten toevoegen.	Oplossingen inleveren!
2014	8/1, 11-14 h 401	Vragenuurtje
	10/1 10-13 in Delft en Leiden!!	Tentamen	Oplossingen van `vragen' in dictaten Overzicht tentamenstof oefenopgaven transportprobleem
	15/4 14-17 in Delft en Leiden!	Hertentamen