Domän av tillåtna lösningar
I optimeringsteori är en genomförbar domän , genomförbar mängd , sökutrymme eller lösningsutrymme uppsättningen av alla möjliga punkter (värden av variabler) i ett optimeringsproblem som uppfyller begränsningarna för problemet. Dessa begränsningar kan inkludera ojämlikheter , likheter och kravet att lösningen ska vara heltal [1] [2] . Området för genomförbara lösningar är det första området för sökandet efter kandidater för att lösa problemet, och detta område kan minskas under sökningen.
Ta till exempel uppgiften
Minimera
med restriktioner för variabler och
och
I det här fallet är området för möjliga lösningar en uppsättning par ( x 1 , x 2 ) för vilka värdet x 1 inte är mindre än 1 och inte mer än 10, och värdet x 2 är inte mindre än 5 och inte mer än 12. Observera att uppsättningen av genomförbara lösningar betraktas separat från den objektiva funktionen, som bestämmer optimeringskriteriet och som i exemplet ovan är lika med
I många problem inkluderar det tillåtna lösningsintervallet begränsningen att en eller flera variabler måste vara icke-negativa. I problem med ren heltalsprogrammering består uppsättningen av möjliga lösningar av heltal (eller någon delmängd). I linjära programmeringsproblem är domänen av genomförbara lösningar en konvex polytop - en region i ett flerdimensionellt utrymme vars gränser bildas av hyperplan [1] .
Tillfredsställelse av begränsningar är processen att hitta en punkt i domänen av genomförbara lösningar.
Relaterade definitioner
Under olikhetsbegränsningar kan en punkt vara antingen en inre punkt (en giltig punkt), en gränspunkt (en giltig punkt) eller en extern punkt (en ogiltig punkt). En aktiv , eller bindande , begränsning är en som vid en given punkt förvandlas till jämlikhet [1] . Vissa algoritmer kan använda begreppet en aktiv begränsning för att bygga en mer effektiv algoritm (se variabelbasmetoden .
Om en giltig punkt inte finns för en uppgift, sägs uppgiften vara ogiltig .
Det villkorade optimum är ett lokalt optimum som ligger på gränsen till det tillåtna området [1] .
Konvex domän av genomförbara lösningar
En konvex domän av genomförbara lösningar är en uppsättning lösningar där segmentet som förbinder två genomförbara lösningar endast innehåller giltiga punkter och inte passerar genom någon ogiltig punkt. Den konvexa uppsättningen av möjliga lösningar uppstår i många typer av problem, inklusive linjära programmeringsproblem, och är av särskilt intresse, eftersom om problemet är att optimera en konvex objektivfunktion , i det allmänna fallet, är ett sådant problem lättare att lösa på en konvex uppsättning lösningar, och varje lokalt optimum kommer också att vara det globala optimum .
Brist på tillåtna lösningar
Om begränsningarna för optimeringsproblemet gemensamt är inkonsekventa, finns det ingen mening att uppfylla alla begränsningar, och då är domänen av genomförbara lösningar tom . I det här fallet har problemet inga lösningar och sägs vara oacceptabelt [1] .
Begränsade och obegränsade domäner av tillåtna lösningar
Uppsättningen av tillåtna lösningar kan vara begränsade eller obegränsade . Till exempel är uppsättningen av genomförbara lösningar som definieras av begränsningarna { x ≥ 0, y ≥ 0} obegränsad, eftersom man kan gå i oändlighet i vissa riktningar samtidigt som man förblir i domänen av genomförbara lösningar. Däremot är uppsättningen möjliga lösningar som bildas av begränsningarna { x ≥ 0, y ≥ 0, x + 2 y ≤ 4} begränsad, eftersom rörelse i vilken riktning som helst är begränsad. I linjära programmeringsproblem med n variabler är närvaron av minst n + 1 begränsningar ett nödvändigt men inte tillräckligt villkor för avgränsningen av domänen av genomförbara lösningar.
Om uppsättningen av genomförbara lösningar är obegränsad, kan den optimala lösningen existera eller inte, beroende på beteendet hos den objektiva funktionen. Till exempel, om mängden definieras av begränsningarna { x ≥ 0, y ≥ 0}, så har x + y -optimeringsproblemet inga lösningar, eftersom vilken kandidat som helst kan förbättras genom att öka x eller y , men x + y -minimeringen problemet har en optimal lösning (och nämligen vid punkten ( x , y ) = (0, 0)).