Dualność w programowaniu liniowym — zadanie prymalne, zadanie dualne i warunki komplementarności

Mgr inż.

Sebastian Dziarmaga-Działyński

Wirtualna kancelaria korepetytorska i konsultacyjna – wszechwiedza.pl

Wprowadzenie

Dualność w programowaniu liniowym jest jedną z najważniejszych idei w całej teorii optymalizacji liniowej. Każdemu zadaniu programowania liniowego można przyporządkować drugie zadanie, nazywane zadaniem dualnym. Co więcej, jeżeli do zadania dualnego ponownie utworzymy zadanie dualne, to wrócimy do zadania wyjściowego, czyli prymalnego. Oznacza to, że nie mamy tu do czynienia z jednostronną sztuczką rachunkową, lecz z parą ściśle powiązanych ze sobą problemów.

W tym artykule wyjaśnimy, jak tworzyć zadanie dualne, jak odczytywać zależność między zmiennymi i ograniczeniami, czym są ograniczenia typowe i nietypowe, a także jak wykorzystać warunki komplementarności do wyznaczania rozwiązania zadania prymalnego na podstawie rozwiązania zadania dualnego. Na końcu zobaczymy przykład, w którym zadanie z większą liczbą zmiennych można przeanalizować dzięki zadaniu dualnemu mającemu tylko dwie zmienne, a więc nadającemu się do rozwiązania metodą graficzną.

Czym jest dualność w programowaniu liniowym?

W klasycznym zadaniu programowania liniowego szukamy takiego rozwiązania, które spełnia wszystkie ograniczenia i jednocześnie daje najlepszą wartość funkcji celu. Jeżeli funkcję celu maksymalizujemy, szukamy największej możliwej wartości. Jeżeli ją minimalizujemy, szukamy wartości najmniejszej.

Zadanie, od którego wychodzimy, nazywamy zadaniem prymalnym, czyli pierwotnym. Do niego można utworzyć zadanie dualne. Oba zadania są ze sobą powiązane w bardzo konkretny sposób. Zmienne jednego zadania odpowiadają ograniczeniom drugiego, a ograniczenia jednego zadania odpowiadają zmiennym drugiego.

Można to ująć obrazowo tak: zadanie prymalne i dualne patrzą na ten sam problem z dwóch stron. W zadaniu prymalnym pytamy na przykład: ile produkować, przewozić, kupować albo alokować? W zadaniu dualnym pytamy raczej: jaką wartość mają ograniczone zasoby, które występują w zadaniu? Dlatego zmienne dualne często interpretuje się jako pewnego rodzaju ceny zasobów albo ceny cienia.

Istotne jest również to, że zadanie dualne do zadania dualnego jest znowu zadaniem prymalnym. Mówiąc mniej formalnie: jeżeli wykonamy przejście „na drugą stronę”, a potem jeszcze raz wykonamy takie samo przejście, wracamy do punktu wyjścia. Nie będziemy tutaj rozwijać języka relacji matematycznych, ale warto zapamiętać tę intuicję, bo dobrze pokazuje ona symetrię ukrytą w dualności.

Zadanie prymalne i zadanie dualne

Zacznijmy od najwygodniejszego przypadku. Rozważmy zadanie maksymalizacji, w którym wszystkie ograniczenia mają znak „mniejsze lub równe”, a wszystkie zmienne są nieujemne:

\[ \begin{aligned} \max \quad & Z = c_1x_1+c_2x_2+\ldots+c_nx_n \\ \text{przy warunkach} \quad & a_{11}x_1+a_{12}x_2+\ldots+a_{1n}x_n \le b_1, \\ & a_{21}x_1+a_{22}x_2+\ldots+a_{2n}x_n \le b_2, \\ & \ldots \\ & a_{m1}x_1+a_{m2}x_2+\ldots+a_{mn}x_n \le b_m, \\ & x_1,x_2,\ldots,x_n \ge 0. \end{aligned} \]

W zapisie macierzowym możemy to zapisać krócej:

\[ \begin{aligned} \max \quad & Z = c^T x \\ \text{przy warunkach} \quad & Ax \le b, \\ & x \ge 0. \end{aligned} \]

Do takiego zadania tworzymy zadanie dualne:

\[ \begin{aligned} \min \quad & W = b_1y_1+b_2y_2+\ldots+b_my_m \\ \text{przy warunkach} \quad & a_{11}y_1+a_{21}y_2+\ldots+a_{m1}y_m \ge c_1, \\ & a_{12}y_1+a_{22}y_2+\ldots+a_{m2}y_m \ge c_2, \\ & \ldots \\ & a_{1n}y_1+a_{2n}y_2+\ldots+a_{mn}y_m \ge c_n, \\ & y_1,y_2,\ldots,y_m \ge 0. \end{aligned} \]

W zapisie macierzowym:

\[ \begin{aligned} \min \quad & W = b^T y \\ \text{przy warunkach} \quad & A^T y \ge c, \\ & y \ge 0. \end{aligned} \]

Już z tego zapisu widać podstawową zasadę dualności. Współczynniki funkcji celu zadania prymalnego, czyli liczby \(c_1,c_2,\ldots,c_n\), stają się prawymi stronami ograniczeń w zadaniu dualnym. Natomiast prawe strony ograniczeń zadania prymalnego, czyli liczby \(b_1,b_2,\ldots,b_m\), stają się współczynnikami funkcji celu w zadaniu dualnym.

Odpowiedniość między elementami zadania prymalnego i dualnego

Najważniejsze zależności można zapamiętać w następujący sposób:

• każdemu ograniczeniu zadania prymalnego odpowiada jedna zmienna dualna,
• każdej zmiennej zadania prymalnego odpowiada jedno ograniczenie dualne,
• współczynniki funkcji celu zadania prymalnego przechodzą na prawe strony ograniczeń dualnych,
• prawe strony ograniczeń zadania prymalnego przechodzą do funkcji celu zadania dualnego,
• macierz współczynników ograniczeń zostaje transponowana, czyli wiersze przechodzą w kolumny.

Jeżeli zadanie prymalne ma \(n\) zmiennych oraz \(m\) ograniczeń, to zadanie dualne ma \(m\) zmiennych oraz \(n\) ograniczeń. To bardzo ważna obserwacja praktyczna. Czasem zadanie prymalne ma wiele zmiennych, ale niewiele ograniczeń. Wtedy zadanie dualne może mieć mało zmiennych i dać się rozwiązać znacznie prościej.

W najprostszym przypadku, gdy zadanie prymalne jest maksymalizacją z ograniczeniami typu \(\le\), zadanie dualne jest minimalizacją z ograniczeniami typu \(\ge\). Ten przypadek jest najbardziej przejrzysty i od niego najlepiej zaczynać naukę dualności.

Ograniczenia typowe, nietypowe i równościowe

W praktycznych zadaniach ograniczenia nie zawsze mają tak wygodną postać. Mogą występować nierówności w przeciwną stronę, równania, a także zmienne, które nie muszą być nieujemne. Dlatego przy tworzeniu zadania dualnego trzeba pilnować nie tylko współczynników, ale także znaków.

Dla zadania maksymalizacji typowym ograniczeniem jest ograniczenie typu:

\[ a_{i1}x_1+a_{i2}x_2+\ldots+a_{in}x_n \le b_i. \] 

Takie ograniczenie daje w zadaniu dualnym zmienną nieujemną:

\[ y_i \ge 0. \] 

Ograniczeniem nietypowym dla zadania maksymalizacji jest ograniczenie typu:

\[ a_{i1}x_1+a_{i2}x_2+\ldots+a_{in}x_n \ge b_i. \] 

Wtedy odpowiadająca mu zmienna dualna jest niedodatnia:

\[ y_i \le 0. \] 

Jeżeli natomiast w zadaniu prymalnym występuje ograniczenie równościowe:

\[ a_{i1}x_1+a_{i2}x_2+\ldots+a_{in}x_n = b_i, \] 

to odpowiadająca mu zmienna dualna jest zmienną nez nałożonych jakichkolwiek warunków brzegowych:

\[ y_i \in \mathbb{R}. \]

Zmienna taka może przyjmować wartości dodatnie, ujemne oraz zero. To częste źródło pomyłek, ponieważ w wielu prostych przykładach wszystkie zmienne są nieujemne i łatwo przyzwyczaić się do takiego schematu.

Tabela zasad dualności

Dla zadania prymalnego w postaci maksymalizacji najważniejsze reguły można zebrać w tabeli:

Dla zadania minimalizacji reguły są analogiczne, ale typowe znaki nierówności są odwrócone. W minimalizacji naturalne są ograniczenia typu \(\ge\), a zadanie dualne jest wtedy zadaniem maksymalizacji z ograniczeniami typu \(\le\).

Przykłady tworzenia zadania dualnego

Przykład 1. Klasyczne zadanie maksymalizacji

Rozważmy zadanie prymalne:

\[ \begin{aligned} \max \quad & Z = 40x_1+30x_2 \\ \text{przy warunkach} \quad & 2x_1+x_2 \le 100, \\ & x_1+x_2 \le 80, \\ & x_1+3x_2 \le 90, \\ & x_1,x_2 \ge 0. \end{aligned} \]

Zadanie ma trzy ograniczenia, więc zadanie dualne będzie miało trzy zmienne: \(y_1,y_2,y_3\). Zadanie prymalne ma dwie zmienne, więc zadanie dualne będzie miało dwa ograniczenia.

Prawe strony ograniczeń zadania prymalnego, czyli \(100,80,90\), przechodzą do funkcji celu zadania dualnego. Współczynniki funkcji celu zadania prymalnego, czyli \(40\) i \(30\), przechodzą na prawe strony ograniczeń dualnych.

Otrzymujemy:

\[ \begin{aligned} \min \quad & W = 100y_1+80y_2+90y_3 \\ \text{przy warunkach} \quad & 2y_1+y_2+y_3 \ge 40, \\ & y_1+y_2+3y_3 \ge 30, \\ & y_1,y_2,y_3 \ge 0. \end{aligned} \]

W pierwszym ograniczeniu dualnym pojawiły się współczynniki stojące przy \(x_1\) w zadaniu prymalnym: \(2,1,1\). W drugim ograniczeniu dualnym pojawiły się współczynniki stojące przy \(x_2\): \(1,1,3\). Jest to właśnie efekt transpozycji macierzy współczynników.

Przykład 2. Ograniczenie nietypowe

Rozważmy teraz zadanie:

\[ \begin{aligned} \max \quad & Z = 5x_1+4x_2 \\ \text{przy warunkach} \quad & 2x_1+x_2 \le 10, \\ & x_1+2x_2 \ge 8, \\ & x_1,x_2 \ge 0. \end{aligned} \]

Pierwsze ograniczenie jest typowe dla maksymalizacji, dlatego zmienna dualna \(y_1\) będzie nieujemna. Drugie ograniczenie jest nietypowe, ponieważ ma znak \(\ge\), dlatego odpowiadająca mu zmienna dualna \(y_2\) będzie niedodatnia.

Zadanie dualne ma postać:

\[ \begin{aligned} \min \quad & W = 10y_1+8y_2 \\ \text{przy warunkach} \quad & 2y_1+y_2 \ge 5, \\ & y_1+2y_2 \ge 4, \\ & y_1 \ge 0, \quad y_2 \le 0. \end{aligned} \]

Ten przykład pokazuje, że nie wystarczy mechanicznie przepisać współczynników. Trzeba jeszcze pilnować znaków nierówności oraz warunków nakładanych na zmienne dualne.

Przykład 3. Ograniczenie równościowe

Niech dane będzie zadanie:

\[ \begin{aligned} \max \quad & Z = 6x_1+2x_2 \\ \text{przy warunkach} \quad & x_1+x_2 = 12, \\ & 3x_1+x_2 \le 30, \\ & x_1,x_2 \ge 0. \end{aligned} \]

Pierwszemu ograniczeniu odpowiada zmienna dualna \(y_1\), ale ponieważ ograniczenie jest równościowe, zmienna \(y_1\) będzie swobodna. Drugiemu ograniczeniu odpowiada zmienna \(y_2\), a ponieważ jest to ograniczenie typu \(\le\), mamy \(y_2 \ge 0\).

Zadanie dualne:

\[ \begin{aligned} \min \quad & W = 12y_1+30y_2 \\ \text{przy warunkach} \quad & y_1+3y_2 \ge 6, \\ & y_1+y_2 \ge 2, \\ & y_1 \in \mathbb{R}, \quad y_2 \ge 0. \end{aligned} \]

Ograniczenia równościowe są więc szczególnie ważne, ponieważ powodują pojawienie się zmiennych swobodnych. W zadaniach egzaminacyjnych i ćwiczeniowych jest to jedno z miejsc, w których najłatwiej o błąd.

Interpretacja ekonomiczna zmiennych dualnych

Zmienne dualne często interpretuje się jako ceny dualne, ceny cienia albo wartości krańcowe zasobów. Jeżeli ograniczenie w zadaniu prymalnym oznacza dostępność pewnego zasobu, na przykład czasu pracy, surowca, powierzchni magazynowej albo budżetu, to odpowiadająca mu zmienna dualna informuje, jaką wartość ma dodatkowa jednostka tego zasobu z punktu widzenia funkcji celu.

Jeżeli dana zmienna dualna jest dodatnia, oznacza to zwykle, że odpowiadające jej ograniczenie jest aktywne, czyli zasób jest w pełni wykorzystany. Jeżeli zmienna dualna jest równa zero, oznacza to, że niewielkie zwiększenie dostępności tego zasobu nie poprawiłoby wartości funkcji celu, przynajmniej w pewnym zakresie.

Ta interpretacja jest bardzo użyteczna. Pozwala nie tylko odpowiedzieć na pytanie, jakie rozwiązanie jest optymalne, ale również zrozumieć, które ograniczenia naprawdę wpływają na wynik, a które w danym rozwiązaniu nie są wiążące.

Twierdzenie o dualności

Najważniejszy związek między zadaniem prymalnym i dualnym opisuje twierdzenie o dualności. W uproszczeniu: jeżeli zadanie prymalne jest zadaniem maksymalizacji, a zadanie dualne jest odpowiadającym mu zadaniem minimalizacji, to dla każdego rozwiązania dopuszczalnego zadania prymalnego i każdego rozwiązania dopuszczalnego zadania dualnego zachodzi nierówność:

\[ Z \le W. \] 

Oznacza to, że wartość funkcji celu w zadaniu prymalnym nie może przekroczyć wartości funkcji celu w zadaniu dualnym. Jeżeli uda się znaleźć takie rozwiązania dopuszczalne obu zadań, dla których:

\[ Z = W, \] 

to oba rozwiązania są optymalne. Zadanie dualne daje więc ograniczenie z góry dla zadania maksymalizacji. Gdy to ograniczenie zostanie osiągnięte, wiemy, że lepszego rozwiązania już nie ma.

W wersji silnej twierdzenie o dualności mówi, że jeżeli jedno z pary zadań ma rozwiązanie optymalne, to drugie również ma rozwiązanie optymalne, a optymalne wartości funkcji celu są sobie równe.

Warunki komplementarności

Bardzo ważnym narzędziem praktycznym są warunki komplementarności. Pozwalają one powiązać rozwiązanie zadania prymalnego z rozwiązaniem zadania dualnego.

Ich sens jest następujący: jeżeli pewna zmienna dualna jest dodatnia, to odpowiadające jej ograniczenie w zadaniu prymalnym musi być spełnione jako równość. Natomiast jeżeli ograniczenie prymalne nie jest aktywne, czyli pozostaje w nim pewien zapas, to odpowiadająca mu zmienna dualna musi być równa zero.

Dla zadania prymalnego:

\[ \max \quad Z=c^Tx, \quad Ax\le b, \quad x\ge 0, \] 

i odpowiadającego mu zadania dualnego:

\[ \min \quad W=b^Ty, \quad A^Ty\ge c, \quad y\ge 0, \] 

warunki komplementarności zapisujemy następująco:

\[ y_i\left(b_i-\sum_{j=1}^{n}a_{ij}x_j\right)=0 \quad \text{dla } i=1,2,\ldots,m, \]

\[ x_j\left(\sum_{i=1}^{m}a_{ij}y_i-c_j\right)=0 \quad \text{dla } j=1,2,\ldots,n. \]

Pierwszy warunek dotyczy ograniczeń zadania prymalnego. Wyrażenie:

\[ b_i-\sum_{j=1}^{n}a_{ij}x_j \]

oznacza zapas w \(i\)-tym ograniczeniu. Jeżeli zapas jest dodatni, to zmienna dualna \(y_i\) musi być równa zero. Jeżeli natomiast \(y_i>0\), to zapas musi być równy zero, czyli ograniczenie jest aktywne.

Drugi warunek działa analogicznie po stronie ograniczeń dualnych. Jeżeli zmienna prymalna \(x_j\) jest dodatnia, to odpowiadające jej ograniczenie dualne musi być spełnione jako równość. Jeżeli ograniczenie dualne jest spełnione z nadwyżką, to odpowiadająca mu zmienna prymalna musi być równa zero.

Rozwiązanie zadania prymalnego przez zadanie dualne

Jednym z praktycznych zastosowań dualności jest sytuacja, w której zadanie prymalne ma wiele zmiennych, ale tylko dwa ograniczenia. Zadania z czterema, pięcioma czy większą liczbą zmiennych nie da się bezpośrednio rozwiązać metodą graficzną. Jeżeli jednak ma ono tylko dwa ograniczenia, to zadanie dualne będzie miało tylko dwie zmienne. A takie zadanie można już przedstawić na płaszczyźnie.

Rozważmy zadanie prymalne:

\[ \begin{aligned} \max \quad & Z = 4x_1+3x_2+5x_3+2x_4 \\ \text{przy warunkach} \quad & x_1+x_2+2x_3+x_4 \le 10, \\ & 2x_1+x_2+x_3+3x_4 \le 12, \\ & x_1,x_2,x_3,x_4 \ge 0. \end{aligned} \]

Zadanie ma cztery zmienne, ale tylko dwa ograniczenia. Tworzymy więc zadanie dualne z dwiema zmiennymi:

\[ \begin{aligned} \min \quad & W = 10y_1+12y_2 \\ \text{przy warunkach} \quad & y_1+2y_2 \ge 4, \\ & y_1+y_2 \ge 3, \\ & 2y_1+y_2 \ge 5, \\ & y_1+3y_2 \ge 2, \\ & y_1,y_2 \ge 0. \end{aligned} \]

To zadanie dualne można rozwiązać metodą graficzną. Każde ograniczenie odpowiada jednej zmiennej prymalnej:

• ograniczenie \(y_1+2y_2\ge 4\) odpowiada zmiennej \(x_1\),
• ograniczenie \(y_1+y_2\ge 3\) odpowiada zmiennej \(x_2\),
• ograniczenie \(2y_1+y_2\ge 5\) odpowiada zmiennej \(x_3\),
• ograniczenie \(y_1+3y_2\ge 2\) odpowiada zmiennej \(x_4\).

Rozwiązaniem optymalnym zadania dualnego jest punkt:

\[ y_1=2, \quad y_2=1. \]

Wartość funkcji celu zadania dualnego wynosi:

\[ W=10\cdot 2+12\cdot 1=32. \]

Z twierdzenia o dualności wynika, że optymalna wartość funkcji celu zadania prymalnego również wynosi:

\[ Z=32. \]

Sprawdźmy teraz warunki komplementarności. Dla \(y_1=2\), \(y_2=1\) ograniczenia dualne przyjmują wartości:

\[ y_1+2y_2=2+2\cdot 1=4, \]

\[ y_1+y_2=2+1=3, \]

\[ 2y_1+y_2=2\cdot 2+1=5, \]

\[ y_1+3y_2=2+3\cdot 1=5>2. \]

Pierwsze trzy ograniczenia dualne są aktywne, natomiast czwarte jest spełnione z nadwyżką. Oznacza to, że zmienna odpowiadająca czwartemu ograniczeniu, czyli \(x_4\), musi być równa zero:

\[ x_4=0. \]

Ponieważ \(y_1>0\) oraz \(y_2>0\), oba ograniczenia prymalne muszą być aktywne:

\[ x_1+x_2+2x_3+x_4=10, \]

\[ 2x_1+x_2+x_3+3x_4=12. \]

Po podstawieniu \(x_4=0\) otrzymujemy:

\[ x_1+x_2+2x_3=10, \]

\[ 2x_1+x_2+x_3=12. \]

Odejmując pierwsze równanie od drugiego, dostajemy:

\[ x_1-x_3=2, \]

czyli:

\[ x_1=x_3+2. \]

Podstawiamy to do pierwszego równania:

\[ (x_3+2)+x_2+2x_3=10, \]

\[ x_2=8-3x_3. \]

Z warunków nieujemności mamy:

\[ x_3\ge 0, \quad x_2=8-3x_3\ge 0. \] 

Stąd:

\[ 0\le x_3\le \frac{8}{3}. \]

Rodzina rozwiązań optymalnych zadania prymalnego ma więc postać:

\[ x_1=t+2, \quad x_2=8-3t, \quad x_3=t, \quad x_4=0, \quad 0\le t\le \frac{8}{3}. \]

Dla każdego takiego rozwiązania wartość funkcji celu wynosi:

\[ Z=4(t+2)+3(8-3t)+5t=32. \]

Widzimy więc, że rozwiązując graficznie zadanie dualne z dwiema zmiennymi, możemy uzyskać ważne informacje o zadaniu prymalnym z czterema zmiennymi. To jedna z praktycznych zalet dualności: czasem trudniejsze zadanie można zastąpić zadaniem prostszym geometrycznie.

Najczęstsze błędy przy tworzeniu zadania dualnego

Przy pierwszym kontakcie z dualnością najczęściej pojawiają się następujące błędy:

• pominięcie transpozycji macierzy współczynników,
• pomylenie współczynników funkcji celu z prawymi stronami ograniczeń,
• nieuwzględnienie ograniczeń nietypowych,
• zapomnienie, że ograniczenie równościowe daje zmienną swobodną,
• zapomnienie, że zmienna swobodna daje ograniczenie równościowe,
• mechaniczne rozwiązywanie zadania dualnego bez sprawdzenia warunków komplementarności.

Najbezpieczniej jest zawsze rozpisać sobie odpowiedniości: ograniczenia prymalne — zmienne dualne, zmienne prymalne — ograniczenia dualne. Dopiero potem warto przepisywać współczynniki.

Podsumowanie

Dualność w programowaniu liniowym polega na tym, że każdemu zadaniu liniowemu można przyporządkować drugie zadanie, ściśle z nim powiązane. Zadanie wyjściowe nazywamy prymalnym, a powiązane z nim zadanie — dualnym. Jeżeli do zadania dualnego utworzymy ponownie zadanie dualne, wracamy do zadania wyjściowego.

Najważniejsza odpowiedniość polega na tym, że ograniczeniom jednego zadania odpowiadają zmienne drugiego zadania, a zmiennym jednego zadania odpowiadają ograniczenia drugiego. Współczynniki funkcji celu przechodzą na prawe strony ograniczeń, prawe strony ograniczeń przechodzą do funkcji celu, a macierz współczynników zostaje transponowana.

Warunki komplementarności pozwalają powiązać rozwiązania obu zadań. Pokazują, które ograniczenia są aktywne, które zmienne muszą być zerowe i jak na podstawie rozwiązania zadania dualnego można odtworzyć informacje o rozwiązaniu zadania prymalnego.

W praktyce dualność jest nie tylko elegancką teorią, ale także użytecznym narzędziem rachunkowym. Szczególnie wtedy, gdy zadanie prymalne ma wiele zmiennych, ale niewiele ograniczeń, przejście do zadania dualnego może znacznie uprościć analizę.

Utworzono: 18.05.2026

Powiązane artykuły

• Programowanie liniowe – metoda graficzna 
• Metoda simpleks — algorytm rozwiązywania zadań programowania liniowego 

Masz problem z tym tematem?

Wszechwiedza.pl pomaga zrozumieć matematykę, statystykę, ekonometrię, badania operacyjne, analizę danych, mechanikę i wiele innych przedmiotów — spokojnie, konkretnie i krok po kroku. 

Zapytaj o pomoc