Diskret
Optimering.
18. kursusgang, tirsdag den 23. november 12.30-16.15
Forelæsning i G5-109:
12.30-13.00 (LKJ): Repetition.
14.55-16.15 (LDA):
Gennemgang af afsnit 13.1 og 13.2
Opgaveregning:
A: Nedenfor er vist to grafer hver med kantmængde E={1, ...
, 8}. Lad M og N være de grafiske matroider af disse grafer.
Benyt algoritmen i afsnit 12.5 til at finde maximum delmængde af
E, der er uafhængig i begge disse matroider. Start med
mængden {4, 5}.
B: Opgave 14 i Kapitel 12 (undtagen spørgsmålet om
matching matroids).
C: Opgave 21 i Kapitel 12.
Afleveringsopgave:
Der er givet n jobs som er numereret 1, ... , n og en maskine, der kan
udføre hvert job på 1 time.
Udførelse af job nr. j giver en fortjeneste cj
forudsat at det er udført når der er gået dj
timer efter et starttidspunkt.
Betragt følgende familie af delmængder af {1, ... , n}
I = { J |
alle jobs i mængden J kan udføres af maskinen sådan
at tidsfristerne overholdes }.
Problemet er at finde en mængde J i I som giver størst
mulig samlet fortjeneste.
1. Argumenter for at hvis J er i I og alle jobs bliver
udført i rækkefølge bestemt ved voksende dj
så bliver alle tidsfrister overholdt.
2. Argumenter for at I
opfylder betingelsen i Definition 12.1 og betingelse 2 i Sætning
12.5 og ({1, ... ,n}, I)
dermed er en matroide. Foreslå en algoritme til løsning af
problemet.
3. Løs problemet med følgende værdier af cj
og dj.
Job nr. j
|
cj
|
dj
|
1
|
20
|
3
|
2
|
10
|
1
|
3
|
3
|
2
|
4
|
2
|
5
|
5
|
1
|
5
|
6
|
4
|
2
|
7
|
6
|
4
|
8
|
10
|
4
|