Intuicyjny / nieformalny dowód na LP Duality?

Jaki byłby dobry nieformalny / intuicyjny dowód na „trafienie w sedno” na temat dualności LP? Jak najlepiej wykazać, że zminimalizowana funkcja celu jest rzeczywiście minimalna, z intuicyjnym sposobem rozumienia granicy?

Sposób, w jaki mnie uczono, doprowadził do tego, że DUŻO ludzi, które znam, podziela jedno zrozumienie: jestem pewien, że dla każdego odpowiedniego problemu minimalizacji istnieje równoważny problem maksymalizacji, który można uzyskać poprzez odwrócenie ograniczeń nierówności. Kropka. Ten „wniosek” dualności jest tym, co wydaje się trzymać, ale nie „dlaczego tak jest” (tj. W jaki sposób / dlaczego wiąże się optymalne rozwiązanie).

Czy istnieje sposób na grę z nierównościami, aby po prostu „pokazać” dolną / górną granicę optimum, która może być motywacją do udowodnienia?

Przejrzałem książkę Chvatala, a także kilka innych, ale nie znalazłem nic, co mogłoby być zrozumiane przez absolutne nooby dla LP. Najbliższa mi była książka Vazirani na temat algorytmów, w której mówi on o „pomnożeniu nierówności przez niektóre magiczne liczby, które pokazują granicę” - nie jestem pewien, jak odtworzyć efekt dla dowolnego LP.

Na życzenie OP, oto odpowiedź matematyczna, do której odsyłam w powyższym komentarzu.

---

Może warto omówić, skąd bierze się dualność, na przykładowym problemie. To potrwa chwilę, ale mam nadzieję, że dualność nie będzie wydawać się tak tajemnicza, kiedy skończymy.

Załóżmy, że mamy pierwotny problem w następujący sposób.

$$Primal =\begin{Bmatrix} \max \ \ \ \ 5x_1 - 6x_2 \\ \ \ \ s.t. \ \ \ \ 2x_1 -x_2 = 1\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 +3x_2 \leq9\\ \ \ \ \ x_1 \geq 0\\ \end{Bmatrix}$$

---

Załóżmy teraz, że chcemy wykorzystać ograniczenia pierwotne jako sposób na znalezienie górnej granicy optymalnej wartości pierwotnej. Jeśli pomnożymy pierwsze ograniczenie przez , drugie ograniczenie przez 1 i dodamy je razem, otrzymamy 9 ( 2 x 1 - x 2 ) + 1 ( x 1 + 3 x 2 ) dla lewej strony i 9 ( 1 ) + 1 ( 9 ) po prawej stronie. Ponieważ pierwsze ograniczenie jest równością, a drugie nierównością, oznacza to$9$$1$$9(2x_1 - x_2) + 1(x_1 +3 x_2)$$9(1) + 1(9)$ Ale ponieważ x 1 ≥ 0 , to jest również prawdą, że 5 x 1 ≤ 19 x 1 , a więc 5 x 1 - 6 x 2 ≤ 19 x 1 - 6 x 2 ≤ 18. Zatem , 18 jest związany z górnym na wartość optymalną do pierwotnego problemu. $$19x_1 - 6x_2 \leq 18.$$ $x_1 \geq 0$$5x_1 \leq 19x_1$ $$5x_1 - 6x_2 \leq 19x_1 - 6x_2 \leq 18.$$ $18$

Z pewnością możemy zrobić to lepiej. Zamiast zgadywać i 1 jako mnożniki, pozwólmy im być zmiennymi. Dlatego szukamy mnożników y 1 i y 2, aby wymusić 5 x 1 - 6 x 2 ≤ y 1 ( 2 x 1 - x 2 ) + y 2 ( x 1 + 3 x 2 ) ≤ y 1 ( 1 ) + y $9$$1$$y_1$$y_2$

$$5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9).$$

Teraz, aby utrzymać tę parę nierówności, co musi być prawdą o i y 2 ? Weźmy dwie nierówności pojedynczo.$y_1$$y_2$

---

Pierwszy nierówność : $5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2)$

$x_1$$x_2$$x_1$$5$$5$$x_1 \geq 0$$5$$x_1$$2y_1 + y_2 \geq 5$

$x_2$$x_2$$-6$$x_2$$-6$$x_2$$-6$$x_2$$x_2$ .$-y_1 + 3y_2 = -6$

---

Druga nierówność : $y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9)$

$y_1$$y_2$$y_1$$y_1$$y_1$$y_2$$y_2$$y_2 \geq 0$

$y_1 + 9y_2$

---

$y_1$$y_2$

$$\begin{align*} \text{Minimize }\:\:\:\:\: y_1 + 9y_2& \\ \text{subject to }\:\:\:\:\: 2y_1 + y_2& \geq 5 \\ -y_1 + 3y_2& = -6\\ y_2 & \geq 0. \end{align*}$$

I to jest podwójne.

---

Prawdopodobnie warto podsumować implikacje tego argumentu dla wszystkich możliwych form pierwotnych i podwójnych. Poniższa tabela pochodzi z p. 214 Wstępu do badań operacyjnych , 8. edycja, Hillier i Lieberman. Odnoszą się do tego jako do metody SOB, gdzie SOB oznacza Sensible, Odd lub Bizarre, w zależności od prawdopodobieństwa znalezienia tego konkretnego ograniczenia lub ograniczenia zmiennej w problemie maksymalizacji lub minimalizacji.

             Primal Problem                           Dual Problem
             (or Dual Problem)                        (or Primal Problem)

             Maximization                             Minimization

Sensible     <= constraint            paired with     nonnegative variable
Odd          =  constraint            paired with     unconstrained variable
Bizarre      >= constraint            paired with     nonpositive variable

Sensible     nonnegative variable     paired with     >= constraint
Odd          unconstrained variable   paired with     = constraint
Bizarre      nonpositive variable     paired with     <= constraint

$x$$x = B$$x$$x \leq C$$C$$B \leq \min C$$B$$B = \min C$$B$$B$

$f$$f$$S,O$$f(S) \geq (1-1/e) f(O)$$f$$f$$f(O) = 1$$f(S)$$\min f(S) = 1-1/e$$1-1/e$$f(S) \geq 1-1/e$

To pozostawia otwarte pytanie, dlaczego tak naprawdę utrzymuje się silna dualność. Istnieją dwa dowody na to, że dotyczy programowania liniowego, jeden dotyczy algorytmu simpleks, drugi lemat Farkasa. Lemat Farkasa jest prawdopodobnie „poprawnym” sposobem na zrozumienie sytuacji, sprowadzając wszystko do intuicyjnego faktu geometrycznego. Przyznaję jednak, że ta intuicja przechodzi mi przez głowę.

W bardziej ogólnych sytuacjach (powiedzmy programowanie półfinałowe), musisz użyć bardziej ogólnych warunków Karush-Kuhn-Tucker (forma mnożników Lagrange'a), aby uzyskać dualność i warunki silnego dwoistości. Jest to traktowane w tekstach o optymalizacji nieliniowej lub wypukłej.