Lagrange'a relaks jest technika relaksacji , które polega na usunięciu ograniczeń w trudnej integracji z funkcji celu w niekorzystne jeśli te ograniczenia nie są spełnione.
Biorąc pod uwagę problem optymalizacji liniowej iw następującej postaci:
max | ||
sc | ||
Gdybyśmy oddzielenia ograniczeń w , ze i tak, że możemy przepisać systemu w formie:
max | ||
sc | ||
(1) | ||
(2) |
Załóżmy, że ograniczenia (2) są trudne, wprowadzamy je w funkcji celu:
max | ||
św | ||
(1) |
Jeśli są kary pozytywne, jeden jest karany, jeśli zostanie naruszone ograniczenie (2). Z drugiej strony, jeśli chcemy zachować liniową funkcję celu, jesteśmy nagradzani, jeśli ściśle przestrzegamy funkcji celu. Powyższy system nazywany jest Lagrange'a relaksacją problemu.
Następnie będziemy starać się rozwiązać podwójną tę relaksację różnymi metodami, takimi jak metoda wiązki, generowanie kolumn lub najczęściej stosowana metoda opadania podgradienta i jego wariacje.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">