2. Modelowanie zależności

2.4. Zależności dualne

Każdy problem PL można przeformułować do symetrycznej postaci, odpowiadającej zadaniu dualnemu:

Problem prymalny ma odpowiadający mu problem dualny, taki że zmienne dualne odpowiadają ograniczenim prymalnym, i vice versa. Np. dla postaci standardowej pary te zapisujemy:
\( \min_{x\in \mathcal{R}^n} f(x) = \mathbf{c}^T x \qquad\Leftrightarrow\qquad \max_{\lambda\in \mathcal{R}^m} y(\lambda) = \mathbf{b}^T \lambda\\ \begin{eqnarray} \mathbf{A}x \geq& \mathbf{b}\;\perp\lambda\qquad\qquad\qquad& \qquad\mathbf{A}^T \lambda \leq \mathbf{c}\; \perp x \nonumber\\ x\geq& 0\qquad\qquad\nonumber &\qquad\qquad\lambda\geq 0\end{eqnarray} \)
Parę problemów prymalnego i odpowiadającego mu dualnego nazywamy problemami sprzężonymi.
W zapisie zadania PL oznaczamy zmienne dualne dla ograniczenia przy pomocy symbolu \(\mathbf{\perp }\). Oznaczenie pojawiające się za symbolem \(\perp \) (np. \(\perp\lambda\) powyżej) opisuje zmienną dualną, która jednak w sposób jawny nie jest definiowana w modelu. Wartości zmiennych dualnych (razem z wartościami prymalnych zmiennych decyzyjnych) są zwracane po obliczeniu optimum przez dowolny solwer zadań PL - jako wartość marginalna ograniczenia.
Ogólnie, dla innych postaci niż standardowa, mechanizm konstrukcji sformułowań prymalno-dualnych problemu optymalizacji liniowej można podsumować w następujący sposób:
  • Kierunek optymalizacji w problemie dualnym jest przeciwny, tj. problem dualny jest zadaniem maksymalizacji, gdy problem prymalny jest zadaniem minimalizacji; w przeciwnym przypadku problem dualny jest zadaniem minimalizacji dla maksymalizacji problemu prymalnego.
  • Ograniczenia typu równościowego implikują zmienne swobodne odpowiedniego sformułowania sprzężonego, i vice versa.
  • Ograniczenia typu \( \geq \) implikują zmienne nieujemne odpowiedniego sformułowania sprzężonego,  i vice versa.
  • Ograniczenia typu \( \leq \) implikują zmienne niedodatnie odpowiedniego sformułowania sprzężonego, i vice versa.
Z powyższego widać, że problem dualny do zadania dualnego jest zadaniem prymalnym.

Z dualnością wiążą się ważne twierdzenia, to jest twierdzenie o słabej i silnej dualności, oraz o warunku komplementarności.  Twierdzenia te są aplikacją warunków optymalności Karusha-Kuhna-Tuckera formułowanych dla funkcji nieliniowych, do specjalnego przypadku funkcji liniowych.

  1. Tw. o słabej dualności. Dla dowolnej pary rozwiązań dopuszczalnych \(x_0,\lambda_0\) zadań wzajemnie dualnych (przy \(\min c^Tx\))  zachodzi ogólna zależność, nazywana odstępem dualności (duality gap):

        \(c^Tx \geq b^T \lambda\)

  2. Tw. o silnej dualności. Jeśli jedno z zadań sprzężonych ma rozwiązanie optymalne, to ma je również drugie zadanie i zachodzi równość  wartości funkcji celu: \(c^T\hat{x_0} = b^T\hat{\lambda_0}\). Jeśli jedno z zadań wzajemnie dualnych jest sprzeczne (zbiór rozwiązań dopuszczalnych jest pusty), to zadanie dualne jest albo sprzeczne, albo nieograniczone.
  3. Warunek komplementarności. Zachodzi własność: \(x_s^T\lambda+\lambda_s^Tx=0\), gdzie \(x_s\) i \(\lambda_s\) są zmiennymi dopełniającymi dla ograniczeń nieaktywnych. W równoważnej wersji warunek ten ma postać: \(\lambda^T(Ax-b)=0\) oraz\((c^T-\lambda^TA)x=0\).   

Dualność ma wiele ważnych zastosowań, w szczególności jest podstawą działania  algorytmu simplex  dualnego. W kontekście modelowania zależności liniowych niezwykle istotne jest zrozumienie znaczenia zmiennych dualnych, których wartość możemy odczytać rozwiązując dowolny problem optymalizacji liniowej w dowolnym solwerze. 

Zmienne dualne, nazywane też: cenami dualnymi, marginalnymi (ang. shadow prices, marginal prices) mają ważną interpretację ekonomiczną - ich wartości mogą być wskazówką, jak alokować ograniczone zasoby (pracownicy, materiały, maszyny, budżet) pomiędzy aktywności. W szczególności:
  • dla zadań maksymalizacji zysku zmienne dualne można interpretować jako koszty materiałowe (ograniczenie na materiały powoduje, że nie możemy zarobić więcej - ile warto zapłacić za ew. zwiększenie zasobów materiałowych?),
  • dla zadań minimalizacji kosztu zmienne dualne można intepretować jako zyski jednostkowe (ograniczenie na zapotrzebowanie powoduje, że nie możemy bardziej obniżyć kosztów - które z wymagań ma największy wpływ na ponoszone koszty, czyli powinno być dla nas najbardziej wartościowe?).
Rozważmy problem długoterminowego magazynowania ziaren zbóż w silosie o pojemności \(K\) ton. Ziarno może być kupowane raz w roku, w sierpniu, a sprzedaż może zachodzić raz w roku, w marcu. Jednostkowe ceny ziarna są prognozowane z dużą dokładnością w horyzoncie \(T\) lat, znany jest też jednostkowy koszt magazynowania ziarna w każdym roku. Firma zarządzająca silosem ma nieograniczone środki finansowe na zakup ziarna, przyjmujemy też, że popyt na ziarno jest znacząco większy od pojemności silosa, czyli można kupić i sprzedać dowolną ilość ziarna, a jedynym ograniczeniem jest pojemność silosa.
  • sformułuj zadanie maksymalizacji zysku, tj. różnicy między przychodem i kosztem;
  • czy można uzasadnić charakter zależności zysku od pojemności silosa?
W celu sformułowania zadania wprowadźmy następujące oznaczenia. Niech ilość ziarna przechowywanego w roku \(t\) będzie oznaczona jako \(I_t\). Jest ona równa ilości ziarna, która została w magazynie z poprzedniego roku \(I_{t-1}\) minus ilość ziarna sprzedana w poprzednim roku \(x_{t-1}\), po powiększeniu o ewentualny zakup w danym roku \(p_t\):

\( I_t = I_{t-1}-x_{t-1}+p_t,\qquad \forall t \in (1,\ldots, T),  \)

gdzie \(I_0=x_0=0\) (przyjmując, że silos jest pusty, gdy rozpoczynamy planowanie).
W każdym roku nie można sprzedać więcej ziarna, niż mamy w silosie. Ponadto, ilość ziarna w silosie nie może przekroczyć jego pojemności. Stąd ograniczenia:

\( x_t \leq I_t ,\qquad \forall t \in (1,\ldots, T),  \)
\( I_t\leq K, \forall t \in (1,\ldots, T).  \)

Zauważmy, że warunek \( x_t \leq I_t\) jest równoważny stwierdzeniu, że ilość ziarna w silosie nie może być mniejsza od zera, czyli wystarczy równoważny zapis tego ograniczenia \( I_t \geq 0\). Oznaczając przez \( c^s_t \) cenę ziarna w sierpniu, a przez \( c^m_t \) cenę ziarna w marcu, oraz przez \( h_t \) cenę magazynowania w roku \( t \), zapisujemy problem PL w postaci:

\(\max \sum_{t=1}^T \left( c^m_t x_t - c^s_t p_t - h_t I_t \right) \)

p.o.:

\( I_t = I_{t-1}-x_{t-1}+p_t,\qquad \forall t \in (1,\ldots, T),  \)

\(\qquad 0\leq I_t\leq K, \qquad \forall t \in (1,\ldots, T).  \qquad  \perp \lambda_t\)

Rozważmy teraz dualne sformułowanie powyższego problemu. Jedynym ograniczeniem, które ma niezerowy współczynnik prawej strony jest ograniczenie na pojemność silosa. Stąd funkcja celu zadania dualnego będzie postaci: \(\min \sum_{t=1}^T K\lambda_t\). Ponieważ \( K \) jest stałą, nie ma ona wpływu na optymalne wartości zmiennych decyzyjnych dualnego problemu, czyli wystarczy minimalizować \(\sum_{t=1}^T \lambda_t\). Oznacza to, że optymalny zysk jest liniowo zależny od pojemności silosa.
Zmienne dualne są też ściśle związane z teorią równowagi rynku, gdyż ich wartość w odniesieniu do równania bilansu popytu i podaży odpowiada wartości ceny rynkowej. Cena rynkowa określa rynkową wartość towaru, pozwalając na jednolitą wycenę i porównanie ofert kupna i sprzedaży. Oferty niekonkurencyjne, czyli o zbyt wysokich cenach w przypadku sprzedaży, lub o zbyt niskich cenach w przypadku kupna, nie powinny brać udziału w obrocie. Natomiast oferty konkurencyjne, przyczyniające się do zwiększenia ogólnego dobrobytu rynkowego powinny uczestniczyć w wymianie rynkowej. 
Rozważmy problem optymalizacji obrotu pojedynczego towaru, na rynku skupiającym \( S \) sprzedających i \( K \) kupujących. W ramach pojedynczej sesji notowań każdy uczestnik zgłasza ofertę kupna lub sprzedaży, która zawiera maksymalny wolumen towaru, jaki uczestnik jest chętny kupić lub sprzedać, po cenie nie gorszej niż ta, którą oferuje.
Oferty uczestników rynku można opisać następującymi parametrami:
  • \( d^{\max}_k \) maksymalna ilość towaru, którą chce nabyć kupujący \( k\); 
  • \( p^{\max}_s \) maksymalna ilość towaru, którą chce zbyć sprzedający \(s \);
  • \( e_k \) maksymalna cenę jednostkową, którą jest skłonny zapłacić kupujący \( k \);
  • \( c_s \) minimalna cenę jednostkową, którą jest skłonny zaakceptować sprzedający \( s \).
Optymalizacja w obrocie giełdowym polega na podjeciu decyzji o wolumenach zawartych transakcji. Przy tym nie ma znaczenia, pomiędzy którą konkretnie parą (lub większą liczbą) uczestników rynku dochodzi do wymiany - ważne jest, aby określić: \(d_k\) ilość zakupionego towaru według \(k\)-tej oferty kupna, oraz \(p_s\) ilość sprzedanego towaru według oferty sprzedazy \(s\); tak, aby sumarycznie ilości kupionego i sprzedanego towaru się zgadzały i żeby dobrobyt z przeprowadzonej wymiany był jak największy.
Odpowiednie zadanie optymalizacji ma prostą strukturę:

 \( \max \sum_{k \in K} e_kd_k - \sum_{s \in S} c_sp_s \) 

przy ograniczeniach:
\( \begin{eqnarray} \sum_{k \in K} d_k &= &\sum_{s \in S} p_s,\\ d_k &\leq &d^{\max}_k,\;\;\forall k\in K\\ p_s &\leq &p^{\max}_s,\;\;\forall s\in S,\\ d_k , p_s &\geq &0.\\ \end{eqnarray} \)
Rozwiązaniem optymalnym powyższego zadania jest wielkość wolumenów wybranych do realizacji ofert kupna i sprzedazy, oraz jednolita cena rynkowa, która nie pojawia się jawnie w modelu, ale jest ceną dualną równania bilansu przepływu towarów.
Czy optymalny dobrobyt rynkowy, osiągany w wyniku wymiany towarami między kupującymi a sprzedającymi na rynku jak w poprzednim przykładzie, zależy od wysokości rynkowej ceny towaru? Czy cena rynkowa zależy od wielkości dobrobytu? Odpowiedź uzasadnić.