Domæne af tilladte løsninger
I optimeringsteori er et gennemførligt domæne , gennemførligt sæt , søgerum eller løsningsrum mængden af alle mulige punkter (værdier af variabler af et optimeringsproblem, der opfylder problemets begrænsninger . Disse begrænsninger kan omfatte uligheder , ligheder og kravet om at løsningen skal være heltal [1] [2] . Området med gennemførlige løsninger er det indledende område af søgningen efter kandidater til at løse problemet, og dette område kan indsnævres under søgningen.
Tag for eksempel opgaven
Minimer
med restriktioner på variable og
og
I dette tilfælde er området med mulige løsninger et sæt af par ( x 1 , x 2 ), for hvilke værdien x 1 er ikke mindre end 1 og ikke mere end 10, og værdien x 2 er ikke mindre end 5 og ikke mere end 12. Bemærk, at sættet af mulige løsninger betragtes separat fra den objektive funktion, som bestemmer optimeringskriteriet, og som i ovenstående eksempel er lig med
I mange problemer inkluderer det tilladte løsningsområde begrænsningen, at en eller flere variable skal være ikke-negative. I problemer med ren heltalsprogrammering består sættet af gennemførlige løsninger af heltal (eller en delmængde). I lineære programmeringsproblemer er domænet for mulige løsninger en konveks polytop - et område i et multidimensionelt rum, hvis grænser er dannet af hyperplaner [1] .
Begrænsningstilfredshed er processen med at finde et punkt i domænet af gennemførlige løsninger.
Relaterede definitioner
Under ulighedsbegrænsninger kan et punkt enten være et indre punkt (et gyldigt punkt), et grænsepunkt (et gyldigt punkt) eller et eksternt punkt (et ugyldigt punkt). En aktiv , eller bindende , begrænsning er en, der på et givet tidspunkt bliver til lighed [1] . Nogle algoritmer kan bruge begrebet en aktiv begrænsning til at bygge en mere effektiv algoritme (se variabel basismetoden .
Hvis der ikke findes et gyldigt punkt for en opgave, siges opgaven at være ugyldig .
Det betingede optimum er et lokalt optimum, der ligger på grænsen af det tilladte område [1] .
Konveks domæne af mulige løsninger
Et konveks domæne af mulige løsninger er et sæt af løsninger, hvor segmentet, der forbinder to mulige løsninger, kun indeholder gyldige punkter og ikke passerer gennem noget ugyldigt punkt. Det konvekse sæt af gennemførlige løsninger opstår i mange typer problemer, herunder lineære programmeringsproblemer, og er af særlig interesse, fordi hvis problemet er at optimere en konveks objektivfunktion , i det generelle tilfælde, er et sådant problem lettere at løse på en konveks sæt af løsninger, og ethvert lokalt optimum vil også være det globale optimum .
Mangel på acceptable løsninger
Hvis begrænsningerne af optimeringsproblemet tilsammen er inkonsistente, er der ingen mening, der opfylder alle begrænsningerne, og så er domænet af gennemførlige løsninger tomt . I dette tilfælde har problemet ingen løsninger og siges at være uacceptabelt [1] .
Afgrænsede og ubegrænsede domæner af tilladte løsninger
Sættet af tilladte løsninger kan være begrænset eller ubegrænset . For eksempel er sættet af mulige løsninger defineret af begrænsningerne { x ≥ 0, y ≥ 0} ubegrænset, da man kan gå i det uendelige i nogle retninger, mens man forbliver i domænet af mulige løsninger. I modsætning hertil er sættet af mulige løsninger dannet af begrænsningerne { x ≥ 0, y ≥ 0, x + 2 y ≤ 4} afgrænset, da bevægelse i enhver retning er begrænset. I lineære programmeringsproblemer med n variable er en nødvendig, men ikke tilstrækkelig betingelse for afgrænsningen af domænet af mulige løsninger, tilstedeværelsen af mindst n + 1 begrænsninger.
Hvis sættet af mulige løsninger er ubegrænset, kan den optimale løsning eksistere eller ikke eksistere, afhængigt af den objektive funktions adfærd. For eksempel, hvis mængden er defineret af begrænsningerne { x ≥ 0, y ≥ 0}, så har x + y optimeringsproblemet ingen løsninger, da enhver kandidat kan forbedres ved at øge x eller y , men x + y minimeringen problem har en optimal løsning (og nemlig ved punktet ( x , y ) = (0, 0)).