Teori + formler Flashcards
Standardform
Alla bivillkor utryckta som likhetsvillkor, alla variabler är icke-negativa variabler. Detta kallas standardform. Detta ger en fördel till simplexmetoden.
Skuggpris
Förväntade förändring av målfunktionen. Kallas även dualvärde/ dualpris.
v^T=C^T*B^-1
Slackvariabel
För att göra om ett olikhets bivillkor till ett likhetsvillkor adderar man eller subtraherar en så kallas slackvariabel. Denna utrycker skillnaden mellan vänster och högerled.
Baslösning
En baslösning är ett sätt att beskriva hörnpunkter på ett matematiskt sätt. Vi utrycker dessa till LP-problemets standardform. En baslösning till ekvationssystemet Ax=b erhålls om n-m variabler sätts till 0 och resterande variabler får unika värden som erhålls då det kvarvarande mxm ekvationssystemet löses.
Existerar under förutsättning att kolumnerna i den kvarvarande mxm matrisen är linjärt oberoende.
Tillåten lösning
Om baslösningen uppfyller alla icke-negativitetsvillkor så är den tillåten.
Degenererad baslösning
En baslösning där en eller flera basvariabler är 0 kallas degenererad.
Linjesökningsmetod
Finna optimala steglängden i en riktning i sökutrymmet
Vad är en heuristisk optimeringsalgoritm?
Hitta tillåten lösning snabbt
Nämn (beskriv) 3 heuristiska optimeringsalgoritmer
Obegränsad lösning
Om ingen komponent i riktningen d är negativ kan vi obegränsat öka värdet på den inkommande variabeln utan att någon basvariabel minskar i värde och begränsas av icke-negativitetsvillkor.
Steglängden blir obegränsad och vi kan få ett godtyckligt stort värde på målfunktionen. Alltså obegränsad lösning.
Konvexa höljet
Det konvexa höljet till en mängd punkter x^k, består av alla möjliga konvexkombinatigner av dessa.
Vilken egenskap har det duala problemet då det primala har flera lösningar?
alternativa lösningar
Trädsökning
Billigaste uppspännande träd
Globalt maximum
