Podwójny program liniowy

Podwójny program liniowy (LP) to kolejny LP wyprowadzony z oryginalnego (pierwotnego ) LP w następujący schematyczny sposób:

• Każda zmienna w pierwotnym LP staje się ograniczeniem w podwójnym LP;
• Każde ograniczenie w pierwotnym LP staje się zmienną w podwójnym LP;
• Kierunek obiektywny jest odwrócony – maksimum w pierwotnym staje się minimalne w dualnym i odwrotnie.

Słabe twierdzenie o dualności stwierdza, że ​​​​celowa wartość podwójnego LP przy dowolnym możliwym rozwiązaniu jest zawsze ograniczona celem pierwotnego LP przy dowolnym możliwym rozwiązaniu (górna lub dolna granica, w zależności od tego, czy jest to problem maksymalizacji, czy minimalizacji). W rzeczywistości ta właściwość graniczna dotyczy optymalnych wartości podwójnych i pierwotnych LP.

Silne twierdzenie o dualności stwierdza ponadto, że jeśli pierwotna ma optymalne rozwiązanie, to dualna również ma optymalne rozwiązanie, a dwa optyma są równe .

Twierdzenia te należą do większej klasy twierdzeń o dualności w optymalizacji . Silne twierdzenie o dualności jest jednym z przypadków, w których luka dualności (luka między optimum pierwotnego a optimum dualnego) wynosi 0.

Forma podwójnego LP

Załóżmy, że mamy program liniowy:

Maksymalizuj c ^T x pod warunkiem, że A x ≤ b , x ≥ 0.

Chcielibyśmy skonstruować górną granicę rozwiązania. Tworzymy więc liniową kombinację ograniczeń o dodatnich współczynnikach, tak że współczynniki x w ograniczeniach wynoszą co najmniej c ^T . Ta liniowa kombinacja daje nam górną granicę celu. Zmienne y podwójnego LP są współczynnikami tej kombinacji liniowej. Podwójny LP próbuje znaleźć takie współczynniki, które minimalizują wynikową górną granicę. Daje to następujący LP:

Zminimalizuj b ^T y z zastrzeżeniem A ^T y ≥ c , y ≥ 0

Ten LP jest nazywany dualem oryginalnego LP.

Interpretacja

Twierdzenie o dualności ma interpretację ekonomiczną. Jeśli zinterpretujemy pierwotny LP jako klasyczny problem „alokacji zasobów”, jego podwójny LP można zinterpretować jako problem „wyceny zasobów”.

Rozważmy fabrykę, która planuje produkcję towarów. Niech ${\ displaystyle x}$ będzie jego harmonogramem produkcji (uczynić $,$$displaystyle$ ) niech będzie listą rynku $c \ geq 0$ ceny (jednostkę dobra $displaystyle$ sprzedać za $c_ {i}}$ ). Ograniczenia, które ma, to $negatywnych$ ) i ograniczenia surowcowe Niech $}$${$ będzie dostępnym surowcem i niech $jednostki$ macierzą kosztów materiałowych (wyprodukowanie jednej wymaga $} \ Displaystyle A_ {ji}}$ jednostek surowca ${\ Displaystyle j}$ ).

Wtedy ograniczona maksymalizacja przychodów jest pierwotnym LP:

Maksymalizuj c ^T x pod warunkiem, że A x ≤ b , x ≥ 0.

Rozważmy teraz inną fabrykę, która nie ma surowca i chce kupić cały zapas surowca z poprzedniej fabryki. Oferuje wektor ceny $}$$displaystyle$ \ y_ $}$ ). Aby oferta została przyjęta, powinno być tak $,$ że w przeciwnym razie fabryka mogłaby zarobić więcej gotówki na produkcji określonego materiał użyty do wytworzenia dobra. Powinno być również ${\ displaystyle y \ geq 0}$ , ponieważ fabryka nie sprzedawałaby żadnego surowca z ceną ujemną. Następnie problemem optymalizacji drugiej fabryki jest podwójny LP:

Zminimalizuj b ^T y z zastrzeżeniem A ^T y ≥ c , y ≥ 0

Twierdzenie o dualności stwierdza, że ​​​​luka dualności między dwoma problemami LP wynosi co najmniej zero. Z ekonomicznego punktu widzenia oznacza to, że jeśli pierwsza fabryka otrzyma ofertę zakupu całego zapasu surowca po cenie jednostkowej y , takiej że A ^T y ≥ c , y ≥ 0, to powinna przyjąć ofertę. Osiągnie co najmniej tyle dochodów, ile mógłby produkować wyroby gotowe.

Silne twierdzenie o dualności stwierdza ponadto, że różnica w dualności wynosi zero. Przy silnej dualności rozwiązanie dualne $,$ z ekonomicznego punktu widzenia, „ceną równowagi” (patrz cena ) dla surowca, który fabryka z macierzą produkcyjną i ${\ displaystyle A}$$rynkową$ surowców zaakceptowałyby surowiec, biorąc pod uwagę cenę $gotowych$ . ( $unikalny$ , że może nie być , więc cena równowagi może nie być w pełni określona przez i za { $displaystyle A}$ , ${\ displaystyle b}$ i ${\ displaystyle c$ .)

$}$ , zastanów się, czy ceny surowców są takie, że $($$\ Displaystyle (A ^ {T} y) _ {i}<c_$$}$ dla niektórych $ponieważ$ kupiłaby więcej surowca, aby wyprodukować więcej dobra ceny są „zbyt niskie”. $I odwrotnie,$${T} y}$ surowców spełniają nie minimalizują , to fabryka zarobiłaby więcej, sprzedając swój surowiec niż produkując towary, ponieważ ceny są „zbyt wysokie”. Przy cenie równowagi $zakup lub$ surowca.

Twierdzenie o dualności ma również fizyczną interpretację.

Konstruowanie podwójnego LP

Ogólnie rzecz biorąc, biorąc pod uwagę pierwotny LP, można zastosować następujący algorytm do skonstruowania jego podwójnego LP. Pierwotny LP jest zdefiniowany przez:

• Zbiór n zmiennych: ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$ .
• Dla każdej zmiennej $Displaystyle$ - powinno być albo nieujemne ( ( $x_ {i} \ geq 0}$ ) lub nie dodatnie ( ${\ Displaystyle x_ {i} \ równoważnik 0}$ ) lub nieograniczony ( ${\ Displaystyle x_ {i} \ in \ mathbb {R}}$ ).
• Funkcja celu: ${\ Displaystyle {\ tekst {maksymalizuj}} ~~~ c_ {1} x_ {1} + \ cdots + c_ {n} x_ {n}}$
• Lista m ograniczeń. Każde ograniczenie j to: $\ Displaystyle a_ {j1} x_ {1} + \ cdots + a_ {jn} x_ {n} \ lesseqqgtr b_ {j} }$ gdzie symbol przed ${\ displaystyle b_ {j}}$ może być jednym z ${\ displaystyle \ geq}$ lub ${\ displaystyle \ leq}$ lub ${\ displaystyle =}$ .

Podwójny LP jest skonstruowany w następujący sposób.

• Każde ograniczenie pierwotne staje się zmienną dualną. Jest więc m zmiennych: ${\ Displaystyle y_ {1}, \ ldots, y_ {m}}$ .
• Ograniczenie znaku każdej zmiennej dualnej jest „przeciwne” do znaku jego ograniczenia pierwotnego. Więc " ${\ Displaystyle \ geq b_ {j}}$ " staje się ${\ Displaystyle y_ {j} \ równoważnik 0}$ i " ${\ Displaystyle \ leq b_ {j}}$ " staje się ${\ Displaystyle y_ {j} \ geq 0}$ i " ${\ Displaystyle = b_ {j}}$ " staje się ${\ Displaystyle y_ {j} \ in \ mathbb {R}}$ .
• Funkcja podwójnego celu to ${\ Displaystyle {\ tekst {minimalizuj}} ~ ~ ~ b_ {1} y_ {1} + \ cdots + b_ {m} y_ {m} }$
• Każda zmienna pierwotna staje się podwójnym ograniczeniem. Jest więc n ograniczeń. Współczynnik zmiennej dualnej w ograniczeniu podwójnym jest współczynnikiem jej zmiennej pierwotnej w jej ograniczeniu pierwotnym. Więc każde ograniczenie i to: ${\ Displaystyle a_ {1i} y_ {1} + \ cdots + a_ {mi} y_ {m} \ lesseqqgtr c_ {i }}$ , gdzie symbol przed $podobny$ ograniczenia znaku na zmiennej i w pierwotnym LP. Więc $0}$$"$ staje się " ${\ Displaystyle \ równoważnik c_ {i}}$ i się " ${\ Displaystyle \ geq c_ {i}}$ " i ${\ Displaystyle x_ {i} \ in \ mathbb {R}}$ staje się " $\ Displaystyle = c_ {i}}$ ".

Z tego algorytmu łatwo zauważyć, że liczba podwójna liczby podwójnej jest liczbą podstawową.

Formuły wektorowe

Jeżeli wszystkie więzy mają ten sam znak, to można przedstawić powyższy przepis w krótszy sposób za pomocą macierzy i wektorów. Poniższa tabela przedstawia relacje między różnymi rodzajami pierwotnych i podwójnych.

Pierwotny	Podwójny	Notatka
Maksymalizuj c T x pod warunkiem, że A x ≤ b , x ≥ 0	Zminimalizuj b T y z zastrzeżeniem A T y ≥ c , y ≥ 0	Nazywa się to „symetrycznym” problemem dualnym
Maksymalizuj c T x pod warunkiem, że A x ≤ b	Zminimalizuj b T y z zastrzeżeniem A T y = c , y ≥ 0	Nazywa się to „asymetrycznym” problemem dualnym
Maksymalizuj c T x pod warunkiem, że A x = b , x ≥ 0	Zminimalizuj b T y z zastrzeżeniem A T y ≥ c

Twierdzenia o dualności

Poniżej załóżmy, że pierwotnym LP jest „maksymalizacja c ^T x podlegająca [ograniczeniom]”, a podwójna LP to „minimalizacja b ^T y podlegająca [ograniczeniom]”.

Słaby dualizm

Słabe twierdzenie o dualności mówi, że dla każdego możliwego rozwiązania x prymitywu i każdego możliwego rozwiązania y dualizmu: c ^T x ≤ b ^T y . Innymi słowy, wartość obiektywna w każdym wykonalnym rozwiązaniu dualizmu jest górną granicą obiektywnej wartości pierwiastka pierwotnego, a wartość obiektywna w każdym wykonalnym rozwiązaniu prymitywu jest dolną granicą obiektywnej wartości dualizmu. Oto dowód dla pierwotnego LP „Maksymalizuj c ^T x z zastrzeżeniem A x ≤ b , x ≥ 0”:

• c ^Tx _
• = x ^T c [ponieważ to tylko iloczyn skalarny dwóch wektorów]
• ≤ x ^T ( A ^T y ) [ponieważ A ^T y ≥ c przez podwójne ograniczenia i x ≥ 0]
• = ( x ^T A ^T ) y [przez łączność]
• = ( Ax ) ^T y [przez właściwości transpozycji]
• ≤ b ^T y [ponieważ A x ≤ b przez ograniczenia pierwotne]

Słaba dwoistość implikuje:

max _x c ^T x ≤ min _y b ^T y

W szczególności, jeśli liczba pierwotna jest nieograniczona (z góry), to liczba podwójna nie ma wykonalnego rozwiązania, a jeśli liczba podwójna jest nieograniczona (od dołu), to liczba pierwotna nie ma wykonalnego rozwiązania.

Silna dwoistość

Twierdzenie o silnej dualności mówi, że jeśli jeden z dwóch problemów ma rozwiązanie optymalne, to drugie ma rozwiązanie optymalne, a granice wyznaczone przez słabe twierdzenie o dualności są ścisłe, tj.:

max _x c ^T x = min _y b ^T y

Mocne twierdzenie o dualności jest trudniejsze do udowodnienia; dowody zwykle wykorzystują słabe twierdzenie o dualności jako podprogram.

Jeden dowód wykorzystuje algorytm simpleks i opiera się na dowodzie, że przy odpowiedniej regule obrotu zapewnia prawidłowe rozwiązanie. Dowód pokazuje, że gdy algorytm simpleks zakończy się rozwiązaniem pierwotnego LP, możliwe jest odczytanie z końcowego obrazu rozwiązania podwójnego LP. Tak więc, uruchamiając algorytm simplex, uzyskujemy rozwiązania zarówno dla liczby pierwotnej, jak i liczby podwójnej jednocześnie.

Inny dowód wykorzystuje lemat Farkasa .

Implikacje teoretyczne

1. Słabe twierdzenie o dualności implikuje, że znalezienie jednego wykonalnego rozwiązania jest tak samo trudne, jak znalezienie optymalnego wykonalnego rozwiązania. Załóżmy, że mamy wyrocznię, która, biorąc pod uwagę LP, znajduje dowolne wykonalne rozwiązanie (jeśli takie istnieje). Biorąc pod uwagę LP „Maksymalizuj c ^T x z zastrzeżeniem A x ≤ b , x ≥ 0”, możemy skonstruować inny LP, łącząc ten LP z jego dualnością. Połączone LP ma zarówno x , jak i y jako zmienne:

Maksymalizuj 1

pod warunkiem A x ≤ b , A ^T y ≥ c , c ^T x ≥ b ^T y , x ≥ 0, y ≥ 0

Jeśli złożony LP ma wykonalne rozwiązanie ( x , y ), to przez słabą dualność c ^T x = b ^T y . Zatem x musi być rozwiązaniem maksymalnym pierwotnego LP, a y musi być rozwiązaniem minimalnym dualnego LP. Jeśli połączony LP nie ma wykonalnego rozwiązania, to pierwotny LP również nie ma wykonalnego rozwiązania.

2. Mocne twierdzenie o dualności zapewnia „dobrą charakterystykę” optymalnej wartości LP, ponieważ pozwala nam łatwo udowodnić, że pewna wartość t jest optymalna dla pewnego LP. Dowód przebiega w dwóch krokach:

• Pokaż wykonalne rozwiązanie pierwotnego LP o wartości t ; dowodzi to, że optymalna jest co najmniej t .
• Pokaż wykonalne rozwiązanie podwójnego LP o wartości t ; dowodzi to, że optymalna jest co najwyżej t .

Przykłady

Malutki przykład

Rozważmy pierwotny LP z dwiema zmiennymi i jednym ograniczeniem:

${\ Displaystyle {\ rozpocząć {wyrównane} {\ tekst {maksymalizuj}} i 3x_ {1} + 4x_ {2 }\\{\text{podlega }}&5x_{1}+6x_{2}=7\\&x_{1}\geq 0,x_{2}\geq 0\end{wyrównane}}}$

Zastosowanie powyższego przepisu daje następujący podwójny LP, z jedną zmienną i dwoma ograniczeniami:

${\ Displaystyle {\ rozpocząć {wyrównane} {\ tekst {minimalizuj}} i 7y_ {1} \\ {\ tekst {z zastrzeżeniem}} &5y_{1}\geq 3\\&6y_{1}\geq 4\\&y_{1}\w \mathbb {R} \end{wyrównane}}}$

Łatwo zauważyć, że maksimum pierwotnego LP jest osiągane, gdy x ₁ jest minimalizowane do dolnej granicy (0), a x ₂ jest maksymalizowane do górnej granicy przy ograniczeniu (7/6). Maksimum to 4 · 7/6 = 14/3.

Podobnie, minimum podwójnego LP jest osiągane, gdy y ₁ jest minimalizowane do dolnej granicy w ramach ograniczeń: pierwsze ograniczenie daje dolną granicę 3/5, podczas gdy drugie ograniczenie daje bardziej rygorystyczną dolną granicę 4/6, więc rzeczywista dolna granica to 4/6, a minimalna to 7 · 4/6 = 14/3.

Zgodnie z silnym twierdzeniem o dwoistości, maksimum prymitywu równa się minimum dwoistości.

Użyjemy tego przykładu, aby zilustrować dowód słabego twierdzenia o dualności. Załóżmy, że w pierwotnym LP chcemy uzyskać górną granicę celu ${\ Displaystyle 3x_ {1} + 4x_ {2}}$ . Możemy użyć ograniczenia pomnożonego przez jakiś współczynnik, powiedzmy ${\ displaystyle y_ {1}}$ . ${\ Displaystyle y_ {1}}$ otrzymujemy : ${\ Displaystyle y_ {1} \ cdot (5x_ {1} + 6x_ {2} )=7y_{1}}$ . Teraz, jeśli ${\ Displaystyle y_ {1} \ cdot 5x_ {1} \ geq 3x_ {1}}$ i ${\ Displaystyle y_ {1 } \ cdot 6x_ {2} \ geq 4x_ {2}}$ , a następnie ${\ Displaystyle y_ {1} \ cdot (5x_ {1} + 6x_ {2}} \ geq 3x_ {1}+4x_ {2}}$ , więc ${\ Displaystyle 7y_ {1} \ geq 3x_ {1} + 4x_ {2}}$ . Stąd cel podwójnego LP jest górną granicą celu pierwotnego LP.

Przykład rolnika

Rozważmy rolnika, który może uprawiać pszenicę i jęczmień, mając ustalone zapasy ziemi L , nawozów F i pestycydów P. $pestycydów$ wyhodować jedną jednostkę pszenicy, należy użyć jednej jednostki $jednostek$ i . Podobnie, aby wyhodować $jedną$ jednostkę jęczmienia, należy użyć jednej jednostki , $nawozu$ pestycydów

$sprzedaży$ , ile pszenicy ( ) i jęczmienia ( ) uprawiać, jeśli ich ceny $displaystyle$$S_ {1}}$ i na jednostkę ${\ displaystyle S_ {2}}$ .

Maksymalizuj: ${\ Displaystyle S_ {1} \ cdot x_ {1} + S_ {2} \ cdot x_ {2}}$		(maksymalizacja przychodów z produkcji pszenicy i jęczmienia)
podlega:	${\ Displaystyle x_ {1} + x_ {2} \ równoważnik L}$	(nie można użyć więcej gruntów niż jest dostępne)
	${\ Displaystyle F_ {1} \ cdot x_ {1} + F_ {2} \ cdot x_ {2} \ równoważnik F}$	(nie można użyć więcej nawozu niż jest dostępne)
	${\ Displaystyle P_ {1} \ cdot x_ {1} + P_ {2} \ cdot x_ {2} \ równoważnik P}$	(nie można użyć większej ilości pestycydów niż jest dostępna)
	${\ Displaystyle x_ {1}, x_ {2} \ geq 0}$	(nie może produkować ujemnych ilości pszenicy lub jęczmienia).

W postaci macierzowej staje się to:

maksymalizuj: ${\ Displaystyle {\ rozpocząć {bmatrix} S_ {1} i S_ {2} \ koniec {bmatrix}} {\ rozpocząć {bmatrix} x_ {1} \\ x_ {2} \ koniec {bmatrix}}}$

z zastrzeżeniem: ${\ Displaystyle {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\ end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix} }\geq 0.}$

W przypadku problemu dualnego załóżmy, że ceny jednostkowe y dla każdego z tych środków produkcji (nakładów) są ustalane przez radę planistyczną. Zadaniem rady planowania jest zminimalizowanie całkowitego kosztu pozyskania ustalonych ilości środków produkcji, przy jednoczesnym zapewnieniu rolnikowi dolnego poziomu ceny jednostkowej każdej z jego upraw (produktów wyjściowych), S 1 dla pszenicy i _S 2 dla _jęczmienia . Odpowiada to następującemu LP:

Zminimalizuj: ${\ Displaystyle L \ cdot y_ {L} + F \ cdot y_ {F} + P \ cdot y_ {P}}$		(minimalizacja całkowitego kosztu środków produkcji jako „funkcja celu”)
podlega:	${\ Displaystyle y_ {L} + F_ {1} \ cdot y_ {F} + P_ {1} \ cdot y_ {P} \ geq S_ { 1}}$	(rolnik musi otrzymać nie mniej niż S 1 za swoją pszenicę)
	${\ Displaystyle y_ {L} + F_ {2} \ cdot y_ {F} + P_ {2} \ cdot y_ {P} \ geq S_ { 2}}$	(rolnik musi otrzymać nie mniej niż S 2 za swój jęczmień)
	${\ Displaystyle y_ {L}, y_ {F}, y_ {P} \ geq 0}$	(ceny nie mogą być ujemne).

W postaci macierzowej staje się to:

Zminimalizuj: ${\ Displaystyle {\ rozpocząć {bmatrix} L & F i P \ koniec {bmatrix}} {\ rozpocząć {bmatrix} y_ {L} \\ y_ {F} \\ y_ {P}\end{bmacierz}}}$

podlega: ${\ Displaystyle {\ rozpocząć {bmatrix} 1 & F_ {1} i P_ {1} \\ 1 & F_ {2} i P_ {2} \ koniec {bmatrix}} {\ rozpocząć {bmatrix} y_ {L} \\ y_ {F }\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L} \\y_{F}\\y_{P}\end{bmatrix}}\geq 0.}$

Podstawowy problem dotyczy wielkości fizycznych. Biorąc pod uwagę wszystkie nakłady dostępne w ograniczonych ilościach i zakładając, że ceny jednostkowe wszystkich produktów są znane, jakie ilości produktów należy wyprodukować, aby zmaksymalizować całkowity dochód? Podwójny problem dotyczy wartości ekonomicznych. Mając gwarancje minimalne dla wszystkich jednostkowych cen produkcji i zakładając, że znana jest dostępna ilość wszystkich nakładów, jaki schemat ustalania cen jednostkowych nakładów, aby zminimalizować łączne wydatki?

Każdej zmiennej w przestrzeni pierwotnej odpowiada nierówność do spełnienia w przestrzeni dualnej, obie indeksowane według typu danych wyjściowych. Każdej nierówności do spełnienia w przestrzeni pierwotnej odpowiada zmienna w przestrzeni dualnej, obie indeksowane według typu danych wejściowych.

Współczynniki ograniczające nierówności w przestrzeni pierwotnej są używane do obliczenia celu w przestrzeni dualnej, w tym przykładzie wielkości wejściowe. Współczynniki użyte do obliczenia celu w przestrzeni pierwotnej ograniczają nierówności w przestrzeni dualnej, w tym przykładzie wyjściowe ceny jednostkowe.

Zarówno problem pierwotny, jak i dualny wykorzystują tę samą macierz. W przestrzeni pierwotnej macierz ta wyraża zużycie fizycznych ilości nakładów niezbędnych do wytworzenia określonych ilości wyjść. W przestrzeni dualnej wyraża tworzenie wartości ekonomicznych związanych z wyjściami z ustalonych wejściowych cen jednostkowych.

Ponieważ każdą nierówność można zastąpić zmienną równości i luzu, oznacza to, że każda zmienna pierwotna odpowiada podwójnej zmiennej luzu, a każda zmienna dualna odpowiada pierwotnej zmiennej luzu. Relacja ta pozwala mówić o luzie komplementarnym.

Niewykonalny program

LP może być również nieograniczone lub niewykonalne. Teoria dualności mówi nam, że:

• Jeśli pierwotne jest nieograniczone, to podwójne jest niewykonalne;
• Jeśli dwoistość jest nieograniczona, to pierwotna jest niewykonalna.

Jednak możliwe jest, aby zarówno dualność, jak i pierwotność były niewykonalne. Oto przykład:

Maksymalizuj: ${\ Displaystyle 2x_ {1} -x_ {2}}$
Z zastrzeżeniem:	${\ Displaystyle x_ {1} -x_ {2} \ równoważnik 1}$
	${\ Displaystyle -x_ {1} + x_ {2} \ równoważnik -2}$
	${\ Displaystyle x_ {1}, x_ {2} \ geq 0 .}$

Aplikacje

Twierdzenie o maksymalnym przepływie i minimalnym cięciu jest szczególnym przypadkiem silnego twierdzenia o dualności: maksymalizacja przepływu jest pierwotnym LP, a minimalizacja cięcia jest podwójnym LP. Zobacz twierdzenie o maksymalnym przepływie min-cut # Sformułowanie programu liniowego .

Inne twierdzenia związane z grafami można udowodnić za pomocą silnego twierdzenia o dualności, w szczególności twierdzenia Koniga .

Twierdzenie Minimax dla gier o sumie zerowej można udowodnić za pomocą twierdzenia o silnej dualności.

Algorytm alternatywny

Czasami może się wydawać, że bardziej intuicyjne jest uzyskanie podwójnego programu bez patrzenia na macierz programów. Rozważ następujący program liniowy:

Zminimalizować	${\ Displaystyle \ suma _ {i = 1} ^ {m} c_ {i} x_ {i} + \ suma _ {j = 1 }^{n}d_{j}t_{j}}$
z zastrzeżeniem	${\ Displaystyle \ suma _ {i = 1} ^ {m} a_ {ij} x_ {i} + e_ {j} t_ {$		${\ Displaystyle 1 \ równoważnik j \ równoważnik n}$
	${\ Displaystyle f_ {i} x_ {i} + \ suma _ {j = 1} ^ {n} b_ {ij} t_ {j }\geq h_{i},}$		${\ Displaystyle 1 \ równoważnik ja \ równoważnik m}$
	${\ Displaystyle x_ {i} \ geq 0, \, t_ {j} \ geq 0,}$		${\ Displaystyle 1 \ równoważnik ja \ równoważnik m, 1 \ równoważnik j \ równoważnik n}$

Mamy m + n warunków i wszystkie zmienne są nieujemne. Zdefiniujemy m + n zmiennych dualnych: y _j oraz s _i . Otrzymujemy:

Zminimalizować	${\ Displaystyle \ suma _ {i = 1} ^ {m} c_ {i} x_ {i} + \ suma _ {j = 1 }^{n}d_{j}t_{j}}$
z zastrzeżeniem	$\ Displaystyle \ suma _ {i = 1} ^ {m} a_ {ij} x_ {i }\cdot y_{j}+e_{j}t_{j}\cdot y_{j}\geq g_{j}\cdot y_{j},}$		${\ Displaystyle 1 \ równoważnik j \ równoważnik n}$
	${\ Displaystyle f_ {i} x_ {i} \ cdot s_ {i} + \ suma _ { j=1}^{n}b_{ij}t_{j}\cdot s_{i}\geq h_{i}\cdot s_{i},}$		${\ Displaystyle 1 \ równoważnik ja \ równoważnik m}$
	${\ Displaystyle x_ {i} \ geq 0, \, t_ {j} \ geq 0,}$		${\ Displaystyle 1 \ równoważnik ja \ równoważnik m, 1 \ równoważnik j \ równoważnik n}$
	${\ Displaystyle y_ {j} \ geq 0, \, s_ {i} \ geq 0,}$		${\ Displaystyle 1 \ równoważnik j \ równoważnik n, 1 \ równoważnik ja \ równoważnik m}$

Ponieważ jest to problem minimalizacji, chcielibyśmy otrzymać program dualny, który jest dolną granicą pierwotnej. Innymi słowy, chcielibyśmy, aby suma wszystkich prawych stron ograniczeń była maksymalna pod warunkiem, że dla każdej zmiennej pierwotnej suma jej współczynników nie przekracza jej współczynnika w funkcji liniowej. Na przykład x ₁ pojawia się w ograniczeniach n + 1. Jeśli zsumujemy współczynniki jego ograniczeń, otrzymamy a _1,1 y ₁ + a _1,2 y ₂ + ... + a _1,;;n;; y _n + fa ₁ s ₁ . Suma ta musi wynosić co najwyżej c ₁ . W rezultacie otrzymujemy:

Wyolbrzymiać	$\ Displaystyle \ suma _ {j = 1} ^ {n} g_ {j} y_ {j} + \ suma _ {i = 1 }^{m}h_{i}s_{i}}$
z zastrzeżeniem	$j} + f_ {i} s_ {i }\równik c_{i},}$		${\ Displaystyle 1 \ równoważnik ja \ równoważnik m}$
	${\ Displaystyle e_ {j} y_ {j} + \ suma _ {i = 1} ^ {m} b_ {ij} s_ {$		${\ Displaystyle 1 \ równoważnik j \ równoważnik n}$
	${\ Displaystyle y_ {j} \ geq 0, \, s_ {i} \ geq 0,}$		${\ Displaystyle 1 \ równoważnik j \ równoważnik n, 1 \ równoważnik ja \ równoważnik m}$

Zauważmy, że w naszych krokach obliczeniowych zakładamy, że program jest w postaci standardowej. Jednak dowolny program liniowy można przekształcić do postaci standardowej i dlatego nie jest to czynnik ograniczający.