Föreläsning 10

Question 1

Vad är linjär programmering?

Answer 1

Ett optimeringsproblem med målet att optimera värdet av ett linjärt uttryck givet att ett antal andra linjära samband håller.

Question 2

Vad är geometriskt känt om ett linjärt programmerings problem.

Answer 2

Lösningen är garanterad att finnas på kanten av lösningsrummet, som ingränsas av varje begränsande linjär funktion samt x/y-linjen.

Detta eftersom lösningsrummet alltid är konvext, och funktionen som ska maximeras har en konstant derivata.

Question 3

Vad vet vi om ett lokalt optimum inom linjär programmering?

Answer 3

Det är också ett globalt optimum

Question 4

Vad är en nonbasic variabel i linjär programmering?

Answer 4

Det är variablerna vi har kontroll över, x_1, x_2, etc.

Question 5

Vad är en basic variabel i linjär programmering?

Answer 5

Det är slack variablerna

Question 6

Hur fungerar simplex algoritmen?

Answer 6

1. Konvertera varje begränsning till slack form
2. Hitta en initial lösning, vid alla nonbasic variabler på 0
3. Testa den bästa grankanten
4. Om alla koefficienter är negativa i målfunktionen har vi en optimal lösning

Question 7

Hur fungerar Branch-and-bound algoritmen?

Answer 7

1. Vi söker efter lösning med simplex
2. Om heltalslösning hittas är vi klara. Detta är rekordhållaren
3. Om simplex säger att maxvärdet för denna branch är större än rekordhållaren prunar vi värdet
4. I annat fall om simplex ger ej heltalslösning updaterar vi begränsingarna i nya branches.

Detta görs till alla branches har kollats eller prunats.