Gjennomførbar region - Feasible region

Et problem med fem lineære begrensninger (i blått, inkludert begrensningene for ikke-negativitet). I fravær av heltalsbegrensninger er det mulige settet hele regionen avgrenset av blått, men med heltalsbegrensninger er det settet med røde prikker.

En lukket mulig region av et lineært programmeringsproblem med tre variabler er en konveks polyhedron .

I matematisk optimalisering er et gjennomførbart område , gjennomførbart sett , søkeområde eller løsningsrom settet med alle mulige punkter (sett med verdier av valgvariablene) for et optimaliseringsproblem som tilfredsstiller problemets begrensninger , potensielt inkludert ulikheter , likheter og heltalsbegrensninger . Dette er det første settet med kandidatløsninger på problemet, før kandidatsettet har blitt begrenset.

Tenk for eksempel på problemet

Minimer ${\ displaystyle x ^ {2} + y ^ {4}}$

med hensyn til variablene og${\ displaystyle x}$${\ displaystyle y,}$

underlagt

${\ displaystyle 1 \ leq x \ leq 10}$

og

${\ displaystyle 5 \ leq y \ leq 12. \,}$

Her er det mulige settet settet med par ( x , y ) der verdien av x er minst 1 og maksimalt 10 og verdien av y er minst 5 og maksimalt 12. Merk at det mulige settet til problemet er atskilt fra den objektive funksjonen , som angir kriteriet som skal optimaliseres og som i eksemplet ovenfor er${\ displaystyle x ^ {2} + y ^ {4}.}$

I mange problemer gjenspeiler det mulige settet en begrensning om at en eller flere variabler må være ikke-negative. I rene heltallsprogrammeringsproblemer er det mulige settet settet med heltall (eller noe delsett derav). I lineære programmeringsproblemer er det mulige settet en konveks polytop : en region i flerdimensjonalt rom hvis grenser er dannet av hyperplan og hvis hjørner er hjørner .

Begrensningstilfredshet er prosessen med å finne et punkt i den gjennomførbare regionen.

Konveks gjennomførbart sett

I et lineært programmeringsproblem produserer en serie lineære begrensninger en konveks mulig region med mulige verdier for disse variablene. I det to-variable tilfellet er denne regionen i form av en konveks enkel polygon .

Et konveks gjennomførbart sett er et der et linjesegment som forbinder to mulige punkter, bare går gjennom andre mulige punkter, og ikke gjennom noen punkter utenfor det mulige settet. Konvekse mulige sett oppstår i mange typer problemer, inkludert lineære programmeringsproblemer, og de er av spesiell interesse fordi, hvis problemet har en konveks objektiv funksjon som skal maksimeres, vil det generelt være lettere å løse i nærvær av en konveks mulig sett og ethvert lokalt optimalt vil også være et globalt optimalt .

Ikke noe mulig sett

Hvis begrensningene for et optimaliseringsproblem er motstridende med hverandre, er det ingen punkter som tilfredsstiller alle begrensningene, og dermed er det mulige området null sett . I dette tilfellet er problemet ikke har noen løsning, og sies å være umulig .

Avgrensede og ubegrensede mulige sett

Et begrenset mulig sett (øverst) og et ubegrenset mulig sett (nederst). Settet nederst fortsetter for alltid mot høyre.

Mulige sett kan være avgrenset eller ubegrenset . For eksempel er det mulige settet definert av begrensningssettet { x ≥ 0, y ≥ 0} ubegrenset fordi det i noen retninger ikke er noen grense for hvor langt man kan gå og fremdeles være i det mulige området. Derimot er det mulige settet dannet av begrensningssettet { x ≥ 0, y ≥ 0, x + 2 y ≤ 4} avgrenset fordi omfanget av bevegelse i hvilken som helst retning er begrenset av begrensningene.

I lineære programmeringsproblemer med n variabler, er en nødvendig, men utilstrekkelig forutsetning for at det mulige settet skal avgrenses, at antall begrensninger er minst n + 1 (som illustrert av eksemplet ovenfor).

Hvis det mulige settet er ubegrenset, kan det være eller ikke være et optimalt, avhengig av detaljene til den objektive funksjonen. For eksempel, hvis det mulige området er definert av begrensningssettet { x ≥ 0, y ≥ 0}, har problemet med å maksimere x + y ikke noe optimalt siden en hvilken som helst kandidatløsning kan forbedres ved å øke x eller y ; Likevel, hvis problemet er å minimere x + y , er det et optimalt (spesifikt ved ( x , y ) = (0, 0)).

Kandidatløsning

I optimalisering og andre grener av matematikken , og i søkealgoritmer (et emne i informatikk ), en kandidat løsning er et medlem av settet av mulige løsninger i mulighetsområdet for et gitt problem. En kandidatløsning trenger ikke å være en sannsynlig eller rimelig løsning på problemet - det er ganske enkelt i settet som tilfredsstiller alle begrensninger ; det vil si at det er i settet med gjennomførbare løsninger . Algoritmer for å løse ulike typer optimaliseringsproblemer begrenser ofte settet med kandidatløsninger ned til en delmengde av mulige løsninger, hvis poeng forblir som kandidatløsninger mens de andre mulige løsningene fremover er ekskludert som kandidater.

Plassen til alle kandidatløsninger, før noen mulige punkter er ekskludert, kalles mulige regioner, mulige sett, søkerom eller løsningsrom. Dette er settet med alle mulige løsninger som tilfredsstiller problemets begrensninger. Begrensningstilfredshet er prosessen med å finne et poeng i det gjennomførbare settet.

Genetisk algoritme

Når det gjelder den genetiske algoritmen , er kandidatløsningene individene i befolkningen som utvikles av algoritmen.

Kalkulus

I kalkulator søkes det etter en optimal løsning ved hjelp av den første derivattesten : det første derivatet av funksjonen som blir optimalisert, tilsvares null, og alle verdier av valgvariablene som tilfredsstiller denne ligningen blir sett på som kandidatløsninger (mens de som ikke utelukkes som kandidater). Det er flere måter som en kandidatløsning kanskje ikke er en faktisk løsning på. For det første kan det gi et minimum når man søker et maksimum (eller omvendt), og for det andre kan det verken gi et minimum eller et maksimum, men snarere et sadelpunkt eller et bøyepunkt , hvor en midlertidig pause i den lokale økningen eller fall av funksjonen oppstår. Slike kandidatløsninger kan være i stand til å utelukkes ved bruk av den andre derivatprøven , hvis tilfredshet er tilstrekkelig for at kandidatløsningen skal være i det minste lokalt optimal. For det tredje kan en kandidatløsning være et lokalt optimalt, men ikke et globalt optimalt .

Ved å ta primitiv funksjon av monomials på formen kandidaten oppløsning ved bruk av Cavalieri kvadraturformel ville være Denne kandidaten løsning er faktisk riktig unntatt når${\ displaystyle x ^ {n},}$${\ displaystyle {\ tfrac {1} {n + 1}} x ^ {n + 1} + C.}$${\ displaystyle n = -1.}$

Lineær programmering

En serie med lineære programmeringsbegrensninger på to variabler produserer en region med mulige verdier for disse variablene. Løsbare problemer med to variabler vil ha en gjennomførbar region i form av en konveks enkel polygon hvis den er avgrenset. I en algoritme som tester mulige punkter sekvensielt, er hvert testet punkt i sin tur en kandidatløsning.

I simpleksmetoden for å løse lineære programmeringsproblemer blir et toppunkt av den mulige polytopen valgt som den første kandidatløsningen og testet for optimalitet; hvis det blir avvist som det optimale, betraktes et tilstøtende toppunkt som den neste kandidatløsningen. Denne prosessen fortsetter til en kandidatløsning er funnet å være den optimale.

Referanser