optimeringsproblemets

Optimeringsproblemet är en matematisk modell där målet är att finna den bästa lösningen bland en mängd tillgängliga alternativ. Vanligtvis formuleras det som att maximera eller minimera en målfunktion f(x) över en mängd beslutvariabler x, under begränsningar som definierar vilka x som är tillåtna. Lösningar som uppfyller begränsningarna kallas feasibla lösningar och den bästa bland dem kallas optimal.

Den centrala strukturen består av tre delar: beslutvariablerna x, målfunktionen f(x) och begränsningar som skrivs som lika med eller ojämlikheter. Begränsningarna definierar en feasibel mängd F av tillåtna x. Problemtyp definieras av formen på f och begränsningarna; om de är linjära kallas det linjärt optimeringsproblem, annars är det icke-linjärt. Om variablerna är heltal talar man om heltals- eller kombinationsoptimering. Vidare skiljer man mellan konvexa och icke-konvexa problem samt mellan kontinuerliga och diskreta variabler eller blandade typer.

Metoderna för att lösa optimeringsproblem varierar. Analytiska metoder som Lagrange- eller Kuhn–Tucker-differensvillkor används för optimala lösningar i differentiabla problem. För linjära problem används algoritmen simplex eller mer moderna inre-punktmetoder. I icke-konvexa problem används ofta heuristiker eller metaheuristiker som genetiska algoritmer. För diskreta eller blandade problem används metoder som branch-and-bound. Dynamisk programmering är användbar för tidsberoende eller sekvensbaserade problem.

Resultatet av ett optimeringsproblem är vanligtvis en global eller lokal optimum beroende på problemets form och metod. Kvaliteten bedöms ofta utifrån objektivets värde och hur starkt det uppfyller begränsningarna. Dualitet, känslighelsanalys och robusthet är viktiga aspekter som hjälper till att tolka och tillämpa lösningen. Användningsområden är breda och sträcker sig från ekonomi och produktion till maskininlärning, logistik och teknik.