Den Lagrangian-avslapningen er en avspenningsteknikk som innebærer å fjerne begrensninger i den vanskelige integrasjonen i den objektive funksjonen i det ugunstige hvis disse begrensningene ikke blir oppfylt.
Gitt et lineært optimaliseringsproblem og i følgende form:
maks | ||
sc | ||
Hvis vi skiller begrensningene i , med og slik at vi kan omskrive systemet i form:
maks | ||
sc | ||
(1) | ||
(2) |
Anta at begrensningene (2) er vanskelige, vi introduserer dem i den objektive funksjonen:
maks | ||
St. | ||
(1) |
Hvis det er positive straffer, blir vi straffet dersom begrensningen (2) blir brutt. På den annen side, hvis vi ønsker å beholde en lineær objektivfunksjon, blir vi belønnet hvis vi følger den objektive funksjonen strengt. Ovennevnte system kalles den lagrangiske avslapningen av problemet.
Vi vil deretter søke å løse det dobbelte av denne avslapningen ved forskjellige metoder, for eksempel strålemetoden, generering av kolonner eller den mest brukte, nedstigningen av undergradienten og dens variasjoner.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">