LABORATIONSINFORMATION, LAB 1

TMA945 Tillämpad optimeringslära

Michael Patriksson

11 februari 2002

Förberedelser

Vi rekommenderar varmt att Ni formulerar samtliga problem på standardform före laborationen. Dessutom finns det en del dualer vilka är bra att ha formulerat i förväg. Tänk på att simplexmetoden kräver likhetsvillkor och ickenegativa variabler.

Redovisning

Deadline för inlämnande av laborationen är 18/2, 24.00! Vad vi vill ha är svar på samtliga uppgifter samt motivering till samtliga svar utom uppgift 1 och 4. Inlämning sker via en textfil. Denna fil skall heta lab1.txt och ligga under roten på ert labbkonto (där ni hamnar när ni loggar in). Denna fil kommer vi att kopiera vid inlämningsdags. Filen skall (längst upp) innehålla gruppnummer samt namn på gruppens deltagare. Även om ni föredrar att jobba hemma vill vi att ni lägger in filen på labbkontona här på mc. Ett tips till er som gärna jobbar hemma är att lägga en fil som heter .forward i labbkontot, i vilken ni skriver er ordinarie mailadress. Mail kommer då att skickas vidare till er vanliga adress. Godkännande och eventuella returer kommer att mailas till labbkontona. En eventuell returinlämning läggs sedan på samma sätt på samma ställe fast med namn lab1_retur1.txt. Anledningen till detta (något bökiga) sätt att lämna in och ut labbar är att någon förra året slängde en omgång returer vi lade ut, och orsakade mycket strul när vi trodde att studenterna fått returer, medans studenterna trodde ingen retur=godkänt.

Simplexmetoden

I denna laboration ska Ni lösa några små LP-problem med simplexmetoden genom att använda programsystemet Matlab. Laborationen syftar till att öka förståelsen för linjärprogrammering, dualitet och känslighetsanalys samt att ge träning på simplexmetoden. En trevlig extra-uppgift består i att lösa det berömda diet-problemet med hjälp av ett interaktivt program-paket på internet.

Först beskrivs hur Matlab-systemet kan användas för att lösa LP-problem och därefter anges de uppgifter som ska lösas.

Matlab-systemet

Innan Ni kör igång, se till att Ni står i det bibliotek där Era Matlab-filer finns lagrade. (Matlabfilerna hämtas enligt instruktionen på kursens hemsida,

http://www.md.chalmers.se/~mipat/TOkurs.html.)

Packa upp filerna med kommandot tar -xvf lab1_swe.tar. Ni har nu fått ett bibliotek vid namn LP. Gå ned i detta med kommandot cd LP och starta Matlab med kommandot matlab.

Programmet för labben startas med kommandot simplex när ni är inne i Matlab.

Probleminmatning

Problemet som skall matas in måste vara på standardform, dvs alla villkor ska vara likhetsvillkor och alla högerled ickenegativa (slackvariabler och eventuella artificiella variabler måste alltså adderas). Detta görs lämpligen som förberedelseuppgift.

Programmet ber er om storleken på problemet när det startas, därefter trycker man på Editera och matar in alla uppgifter direkt i tabellen. Alla fält som kan ändras är svagt rosa. Man kan hoppa mellan fält m.h.a Tab. Efter inmatning trycker man Editera igen för att avsluta inmatningen. Fält som lämnats tomma kommer att fyllas med värdet 0.

Lösning av LP-problemen mha Simplexmetoden

Efter inmatningen ska man först välja en startbas. Detta görs genom att klicka på de variabler som skall ingå samt klicka Ange bas . Nu kommer programmet att lista basmatrisen, dess invers, de reducerade kostnaderna (c − c_{B}^{T}B^{−1}A), värdet på basvariablerna samt målfunktionsvärdet. Välj nu inkommande variabel genom att markera motsvarande variabel ovan den reducerade kostnaden och klicka på Ange inkommande . Programmet kommer nu att beräkna B^{−1}A^{j}. Ni väljer utgående genom att markera rätt rad till höger om basvariablernas värde och klicka på Byt bas . Fortsätt på detta sätt tills en optimal lösning nås.

Lösning av ett LP-problem mha Fas I och Fas II

Om problemet är sådant att en tillåten baslösning inte kan hittas direkt, måste Fas I metoden användas. Detta görs genom att ange fas-I målfunktionen och lösa till optimalitet. Därefter ändrar man målfunktionen och anger den bas man kom fram till i fas-I.

Tillägg av variabel Om man behöver en extra kolumn klickar man på Ny kolumn . Detta lägger till en extra kolumn och ställer programmet i editeringsläge.

Borttagning av variabel Välj vilken variabel som skall tas bort genom att klicka på knapparna ovan matrisen (samma som vi val av bas), samt klicka på Tag bort kolumn .

Tillägg av villkor Ett nytt villkor kräver en ny rad och oftast också en ny variabel (kolumn) för slack. Tillägg av rader fungerar på samma sätt som tillägg av kolumner, men efter tillägg av en rad måste en ny bas väljas.

Borttagning av villkor Välj vilket villkor som skall tas bort genom att klicka på knapparna till höger om basvariablernas värde (samma som vid val av utgående) och klicka på Tag bort rad .

Ändring av koefficienter Detta görs genom att trycka på Editera och ändra i tabellen.

Sammanfattning av kommandon

Följande kommandon finns:

Ange bas  - Anger en ny bas m.h.a. knappar ovanför kolumnerna
Byt bas  - Anger utgående variabel och byter bas.
Ny kolumn  - Skapar en ny kolumn och sätter programmet i editerings-läge
Editera  - Sättet programmet i editerings läge eller avslutar editering.

Spara - Sparar problemet under det namn som angetts under Filnamn. Om inget filnamn finns så sparas problemet under namnet default. Filformatet är Matlabs eget .mat.

Ny rad  - Skapar en ny rad i matrisen och sätter programmet i editerings-läge.

Hämta - Hämtar ett problem från den fil som anges av fältet filnamn. Om filen vid namn “filnamn” saknas så hämtas filen default.

Tag bort kolumn - Tar bort de kolumner vilka indikeras med radioknappar ovan matrisen.

Tag bort rad - Tar bort de rader vilka indikeras av radioknappar till höger om basvariablernas värde.

Avsluta  - Avslutar programmet.

Workspace

I matlabs workspace finns hela tiden matrisen (A), kostnaden (c), högerledet (b), basen (B), dess invers (invB), den reducerade kostnaden (rc), basen (basindex), b̄ (Bb) samt Ā^{j} (col).

Uppgifter

1. Lös problemet

max z = 2x_{1} + 4x_{2} + 3x_{3}
då x_{1} + 3x_{2} + 2x_{3} ≤ 30
x_{1} + x_{2} + x_{3} ≤ 24
3x_{1} + 5x_{2} + 3x_{3} ≤ 60
x_{1}, x_{2}, x_{3} ≥ 0

2. Lös problemet

min z = x_{1} + 3x_{2} + 2x_{3}
då 2x_{1} + x_{2} + x_{3} ≤ 30
x_{1} + 2x_{2} + x_{3} ≥ 10
−x_{1} + 2x_{2} + 3x_{3} ≤ 40
x_{1}, x_{2}, x_{3} ≥ 0

Använd simplexmetodens båda faser.

3. Lös problemet

min z = 4x_{1} + 10x_{2} − 4x_{3}
då −2x_{1} + x_{2} + x_{3} ≤ 2
−3x_{1}  + x_{3} ≥ 1
x_{2} − x_{3} ≥ 1
x_{1}, x_{2}, x_{3} ≥ 0

4. Formulera och lös dualen till problemet i uppgift 3. Kontrollera att svaret är konsistent med uppgift 3

5. Lös problemet

max z = 6x_{1} + 4x_{2} + 7x_{3}
då x_{1} + 2x_{2} + 3x_{3} ≤ 8
2x_{1} + x_{2} + 2x_{3} ≤ 5
3x_{1} + 3x_{2} + 4x_{3} ≤ 10
x_{1}, x_{2}, x_{3} ≥ 0

6. Lägg till en ny variabel med målfunktionskoefficient 2 och bivillkorskolumn (3 0 1). Ange nya variabelns reducerade kostnad i den bas som var optimal för problem 5. Optimera om problemet, ange den nya lösningen och kommentera resultatet.

7. Givet optimala basen i uppgift 6, bestäm skuggpriset för bivillkor 2. Vad bör det nya målfunktionsvärdet bli om högerledskoefficienten till bivillkor 2 ändras till 6? Kontrollera med Matlab. Kommentera resultatet.

Diet-problemet (Redovisas ej, mest på kul).

Diet-problemet är en av de allra första kända applikationerna av linjär-programmering. Problemet beskriver hur man på billigast möjliga sätt tillgodoser ett dagligt behov av diverse nödvändiga näringsämnen (vitaminer, kolhydrater, …) givet ett antal möjliga födoämnen. (Problemet kan lösas t.ex. för att bestämma en optimal utfodring av boskap, eller amerikanska soldater, vilket var det ursprungliga problemet.)

På adressen

http://www.mcs.anl.gov/home/otc/Guide/CaseStudies/diet/index.html

hittar Ni ett interaktivt program i vilket Ni kan välja ett antal möjliga födoämnen (typiska amerikanska maträtter bland annat), och bland dessa väljer sedan ett LP-paket den billigaste dieten som satisfierar alla kost-krav (om möjligt). Optimal-lösningen kan sedan analyseras med avseende på bidraget till kostnaden och intaget av vitaminer, etc., från vardera födoämne; Ni kan alltså använda programmet också för att studera kostlära! Vid lösningen av uppgifterna, använd Er gärna av den kost- och pristabell som finns på hemsidan.

Ni kan även läsa om problemets historia, och söka vidare för mer information om linjär-program-mering på hemsidan. En förträfflig hemsida att utgå från om ni vill söka Er fram på nätet efter mer information om optimeringslära är INFORMS (INstitute For Operations Research and the Management Sciences)

http://www.informs.org/Resources/