Optimal lösning (optimering)

Optimal lösning — inom operationsanalys, optimering och beslutsteori avses en tillåten lösning (dvs. en lösning som uppfyller alla uppgiftens begränsningar) som ger ett extremalt (maximalt eller minimalt, beroende på uppgiftens formulering) värde av målfunktionen.

Att söka efter den optimala lösningen är huvudmålet vid lösning av de flesta optimeringsuppgifter.

Väsen och egenskaper

En optimal lösning har två grundläggande egenskaper:

1. Tillåtlighet: Den måste uppfylla alla begränsningar som ställts på modellens variabler. Med andra ord tillhör den optimala lösningen alltid det tillåtna lösningsområdet (TLO). 2. Extremalitet avseende målfunktionen: Bland alla tillåtna lösningar ger den det bästa (maximala eller minimala) värdet av målfunktionen, som formaliserar optimalitetskriteriet.

Inte varje tillåten lösning är optimal, men varje optimal lösning måste nödvändigtvis vara tillåten.

Samband med det tillåtna lösningsområdet

Det tillåtna lösningsområdet (TLO) utgörs av mängden av alla alternativ (uppsättningar av variabelvärden) som uppfyller uppgiftens begränsningar. Den optimala lösningen är den punkt (eller de punkter) i detta område där målfunktionen når sitt extremvärde. Om TLO är tomt saknar uppgiften både tillåtna och, följaktligen, optimala lösningar.

Målfunktionens och begränsningarnas roll

• Begränsningarna definierar mängden av möjliga lösningar (TLO).
• Målfunktionen avgör vilken av dessa möjliga lösningar som är bäst (optimal).

Utan en målfunktion är det omöjligt att avgöra vilken av de tillåtna lösningarna som är optimal. Utan begränsningar kan uppgiften vara trivial eller sakna en ändlig optimal lösning (till exempel maximering av en linjär funktion utan begränsningar).

Den optimala lösningens unikhet

Den optimala lösningen är inte alltid unik. I vissa uppgifter (till exempel inom linjär programmering, om målfunktionen är parallell med en av de aktiva begränsningarna) kan det finnas oändligt många optimala lösningar med samma värde på målfunktionen. Däremot är värdet av målfunktionen i optimumpunkten (eller optimumpunkterna) alltid unikt (om optimum existerar).

Metoder för att hitta lösningar

För att söka optimala lösningar inom operationsanalys används olika matematiska metoder, beroende på modelltyp:

• Simplexmetoden (för linjär programmering)
• Gradientnedstigningsmetoder och andra numeriska metoder (för icke-linjär programmering)
• Gren-och-gräns-metoden, avskärningsmetoder (för heltalsplanering)
• Metoder för dynamisk programmering

Modellberoende

Det är viktigt att förstå att en lösning är optimal endast inom ramen för den antagna matematiska modellen. Om modellen inte återspeglar den verkliga situationen på ett adekvat sätt (om målfunktionen valts felaktigt, om viktiga begränsningar eller samband inte beaktats) kan den formellt funna optimala lösningen visa sig vara ineffektiv eller till och med felaktig i praktiken.

Optimalitet i flerkriterieproblem

I uppgifter med flera målfunktioner (flerkriterieoptimerng) ersätts begreppet unik optimal lösning ofta av begreppet Pareto-optimalitet. En Pareto-optimal lösning är en tillåten lösning för vilken det är omöjligt att förbättra värdet av en målfunktion utan att försämra värdet av åtminstone en annan.

Litteratur

• Вентцель Е. С. Исследование операций: задачи, принципы, методология. — М.: Наука, 1988.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

Se även

• Operationsanalys
• Optimering
• Matematisk modell
• Målfunktion
• Begränsningar
• Tillåtet lösningsområde
• Tillåten lösning
• Kriterium
• Beslutsteori
• Flerkriterieoptimering
• Pareto-optimalitet
• Extremvärde