Chalmers/GU Matematiska institutionen TENTAMEN

TMA946/MAN280 TILLÄMPAD OPTIMERINGSLÄRA

Datum:  01–03–05
Tid:  14^{15}–19^{15}
Hjälpmedel:  Typgodkänd räknedosa
Antal uppgifter:  7; för godkänd uppgift krävs 2 poäng av 3.

Uppgifterna är inte ordnade efter svårighetsgrad.

För godkänt krävs 10 poäng och tre godkända uppgifter.

Examinator:  Michael Patriksson
Jourhavande lärare:  Erik Svensson, tel. 0740-459022
Resultat anslås senast: 01–03–19

Kortfattade lösningsförslag anslås vid skrivningstidens slut på anslagstavlan för optimeringslära vid matematiska institutionen.

Tentamensinstruktioner

När Du löser uppgifterna

Redovisa lösningsmetodik och beräkningar. Använd generellt giltiga metoder, t.ex. de som genomgåtts i kursen.

Skriv endast på ena sidan av lösningsbladen. Använd inte rödpenna. Behandla ej fler än en huvuduppgift på varje blad.

Vid skrivningens slut

Sortera Dina lösningsblad i uppgiftsordning. Markera på omslaget de uppgifter Du behandlat. Kontrollräkna antalet inlämnade blad och fyll i antalet på omslaget.

TENTAMEN

Uppgift 1

(Linjärprogrammering)

Betrakta följande LP-problem:

minimera z = cx_{1} + 2x_{2}
då  2x_{1} + x_{2} ≥ 1,
x_{1} − x_{2} ≤ 1,
x_{1} , x_{2} ≥ 0.

(2p) a) Lös problemet med simplexmetoden (fax I och fas II), givet att konstanten c har värdet c = −1.

(1p) b) Tag fram det intervall a ≤ c ≤ b där den erhållna basen i föregående deluppgift är optimal.

Nedan står listat några matrisinverser vilka kan vara till hjälp vid lösandet.

\begin{aligned}[\begin{matrix}2 & 1 \\ 1 & −1 \end{matrix}]^{−1} & = & \frac{1}{3} [\begin{matrix}1 & 1 \\ 1 & −2 \end{matrix}] & ; & [\begin{matrix}2 & −1 \\ 1 & 0 \end{matrix}]^{−1} & = & [\begin{matrix}0 & 1 \\ −1 & 2 \end{matrix}] & ; & [\begin{matrix}2 & 0 \\ 1 & 1 \end{matrix}]^{−1} & = & \frac{1}{2} [\begin{matrix}1 & 0 \\ −1 & 1 \end{matrix}] \\ [\begin{matrix}2 & 1 \\ 1 & 0 \end{matrix}]^{−1} & = & [\begin{matrix}0 & 1 \\ 1 & −2 \end{matrix}] & ; & [\begin{matrix}1 & −1 \\ −1 & 0 \end{matrix}]^{−1} & = & [\begin{matrix}0 & −1 \\ −1 & −1 \end{matrix}] & ; & [\begin{matrix}1 & 0 \\ −1 & 1 \end{matrix}]^{−1} & = & [\begin{matrix}1 & 0 \\ 1 & 1 \end{matrix}] \\ [\begin{matrix}1 & 1 \\ −1 & 0 \end{matrix}]^{−1} & = & [\begin{matrix}0 & −1 \\ 1 & 1 \end{matrix}] & ; & [\begin{matrix}−1 & 0 \\ 0 & 1 \end{matrix}]^{−1} & = & [\begin{matrix}−1 & 0 \\ 0 & 1 \end{matrix}] & ; & [\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}]^{−1} & = & [\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}] \end{aligned}

Uppgift 2

(Obegränsad optimering)

Betrakta det obegränsade optimeringsproblemet

minimera f(x),
då x ∈ ℜ^{n},

där f är en reellvärd funktion.

(1p) a) Ange de nödvändiga villkoren för att x ska vara ett lokalt minimum i det fall då f är kontinuerligt differentierbar.

(1p) b) Ange de nödvändiga villkoren för att x ska vara ett lokalt minimum i det fall då f är två gånger kontinuerligt differentierbar.

(1p) c) Bevisa att ovanstående villkor verkligen är nödvändiga.

Uppgift 3

(Linjär optimering)

(2p) a) Antag att den optimala lösningen till ett LP-problem inte är unik. (Detta upptäcker vi genom att den reducerade kostnaden är 0 för någon eller några icke-basvariabler i en optimal baslösning, och att någon av dessa kan inkluderas i basen med ett värde som är större än noll.) Exempelvis gäller detta i optimallösningen till LPproblemet som modellerar Mexicos stålproduktion, där det finns flera alternativa sätt att transportera råvaror och färdiga produkter till samma kostnad. I detta problem var målet att minimera den totala kostnaden. På grund av att det finns flera optimala lösningar kan vi emellertid välja, bland dem, så att ett annat mål optimeras, till exempel så att den totala transportsträckan minimeras. För ett allmänt LP-problem (formulerat som i uppgiften nedan) med multipla optimallösningar, hur skulle Du göra för att utföra denna “sekundära” optimering? Låt den sekundära målfunktionen vara att minimera d^{T} x.

(1p) b) Ange och motivera med ett bevis de nödvändiga och tillräckliga villkoren för att x ska vara en optimallösning i ett LP-problem på formen

minimera c^{T} x,
då Ax ≥ b,
x ≥ 0^{n}.

(3p) Uppgift 4

(Lagrangedualitet)

Betrakta problemet

minimera z = 2x_{1} + x_{2}
då  x_{1} + x_{2} ≥ 5,
x_{1}  ≤ 4,
x_{2} ≤ 4,
x_{1} , x_{2} ≥ 0, heltal.

Lagrangerelaxera det övergripande bivillkoret. Beskriv Lagrangefunktionen och ge ett uttryck för den Lagrangeduala funktionen och det duala problemet. Beräkna den Lagrangeduala funktionen i följande fyra punkter: λ = 0, 1, 2, 3. Ange den bästa övre och den bästa undre gränsen för det optimala målfunktionsvärdet till det ursprungliga problemet som Du finner.

(3p) Uppgift 5

(Modellering)

Mejeribolaget Mula har just fått ett kontrakt från lågpriskedjan Öca om att förse samtliga Öcas M butiker med mejeriprodukter av tre olika kategorier (mjölk, ost och övrigt). Butik m behöver b_{mi} ton varor av kategori i varje dag. För att genomföra leveranserna så måste Mula bygga upp ett nät av distributionscentraler över den svenska landsbygden. Byggandet underlättas av att Mula har utarbetat K olika standardcentraler vilka dagligen kan leverera c_{ki} ton av produkt i. Att bygga en central av typ k kostar d_{k} kronor. Mula har även letat upp N lämpliga platser att placera sina centraler på, och man kan bygga maximalt en central per plats. Kostnaden för att förse en kund m med varor av typ k från central n är uppdelad i två delar: p_{mnk} är en fast kostnad för att över huvud taget skicka ut en bil till kunden och q_{mnk} är kostnaden per ton.

Enligt kontraktet är det även möjligt att ej förse en butik med den mängd de önskar. Om vi gör detta så måste vi betala ett straff om t kronor per butik som ej får vad de behöver, samt s kronor per ton behov som ej tillfredställs.

Formulera ett linjrt heltalsproblem som skall lösas för att minimera Mulas kostnader för att uppfylla kontraktet.

(3p) Uppgift 6

(Frank–Wolfe)

Betrakta optimeringsproblemet

minimera f(x) := 2x_{1}^{2} + 2x_{2}^{2} − 24x_{1} − 20x_{2},
då x_{1} + x_{2} ≤ 8,
6 ≥ x_{1} ≥ 0, 6 ≥ x_{2} ≥ 0.

Starta i punkten x^{0} = (0, 0)^{T} och genomför två iterationer med Frank–Wolfealgoritmen. Redovisa och motivera de övre och undre gränser för det optimala målfunktionsvärdet som algoritmen genererar under beräkningarnas gång. Om du finner optimum, motivera då att det är ett optimum.

Uppgift 7

(KKT och Wardrops princip i transportplanering)

För att kunna planera för framtida investeringar i innerstadstrafiknätet behöver Göteborgs lokaltrafikkontor ha information om hur resvanorna i staden ser ut och hur trafikflöden skulle förändras av en förändring i infrastrukturen, t.ex. av en utbyggnad av en vägsträcka eller införandet av fler spårvagnslinjer. Matematiska prognosmodeller används för att undersöka detta. Det underliggande beteendeantagandet i prognosmodellerna är att alla som reser mellan en given startplats och ett mål väljer färdmedel och väg så att den totala resekostnaden minimeras. Om alla väljer på detta sätt och observerar var det är “billigast” att färdas, så kommer över tiden en jämvikt att nås, där samtliga resor som görs mellan ett givet par av start och mål vid en viss tidpunkt kostar ungefär lika mycket och är minst lika billiga som alla outnyttjade alternativ, eftersom det annars skulle finnas en resrutt som vore billigare och som någon skulle upptäcka och välja i stället. Denna princip kallas Wardrops användaroptimala princip.

I matematisk notation kan vi skriva detta på följande sätt. Antag att (p, q) ∈ C är ett par av noder p och q, var emellan folk reser. Låt oss anta att vi vet att under en viss tidsperiod det finns d_{pq} enheter (bilar, låt säga) som färdas mellan nod p och q. Om vi räknar upp alla möjliga vägar mellan p och q får vi en mängd som vi kan kalla R_{pq}. Låt flödet på väg r ∈ R_{pq} vara h_{r}. När alla har valt resesätt fås en kostnad c_{r} för varje väg, som beror på hur många som reser. Att vi har nått en jämvikt där alla vägar som används har samma och minimala kostnad kan då uttryckas som att för varje par (p, q) ∈ C det finns ett värde π_{pq} så att

h_{r} ≥ 0, r ∈ R_{pq}; ∑_{r∈R_{pq}} h_{r} = d_{pq},  (p, q) ∈ C,  (1)

och

h_{r} > 0 ⟹ c_{r}(h) = π_{pq},  r ∈ R_{pq},  (2a)
h_{r} = 0 ⟹ c_{r}(h) ≥ π_{pq},  r ∈ R_{pq}.  (2b)

När restiden mäts på en båge (eller länk som man brukar kalla det) används en restidsfunktion, t_{a}(f_{a}), som är en positiv, strikt växande och kontinuerlig funktion. Denna funktion mäter hur lång restiden är längs bågen a ∈ A, där A är mängden av bågar i nätverket, som en funktion av hur många som reser där under en viss tidsperiod. Antalet resenärer per tidsenhet, f_{a}, på en båge är relaterat till flödena på vägarna genom sambandet

f_{a} = ∑_{(p,q)∈C} ∑_{r∈R_{pq}} δ_{ra}h_{r}, a ∈ A,

dvs. på varje båge a ges det totala flödet av summan av flödet av alla vägar som passerar den bågen (konstanten δ_{ra} har värdet 1 om väg r passerar båge a och är 0 annars).

Att beräkna ett jämviktsflöde betyder att man på något sätt måste finna ett flöde h som uppfyller efterfrågan, dvs. (1) och jämviktsvillkoren (2). Hur gör man det på ett effektivt sätt? Jo, man sätter upp följande optimeringsproblem:

minimera T (f) := ∫_{0}^{f_{a}} t_{a}(s) ds,  (3a)

då

∑_{(p,q)∈C} ∑_{r∈R_{pq}} δ_{ra}h_{r} − f_{a} = 0,  a ∈ A,  (3b)
∑_{r∈R_{pq}} h_{r} = d_{pq},  (p, q) ∈ C,  (3c)
h_{r} ≥ 0,  r ∈ R_{pq}, (p, q) ∈ C.  (3d)

(1p) a) Visa att optimeringsproblemet (3) är konvext.

(2p) b) Visa att KKT-villkoren för problemet (3) precis är att vi uppfyller (1) och jämviktsvillkoren (2). Vad drar vi för slutsats av det för möjligheten att beräkna ett jämviktsflöde?

Lycka till!