Podwójny program liniowy - Dual linear program

Podwójnego danego programu liniowego (LP) jest inny PR, który uzyskiwany jest z pierwotnego (w jego pierwotnej ) LP w następujący sposób schematyczny:

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;
Cel obiektywny jest odwrotny - maksimum w pierwotnym staje się minimum w dualności i odwrotnie.

Twierdzenie o słabej dualności stwierdza, że obiektywna wartość dualnego LP w każdym wykonalnym rozwiązaniu jest zawsze związana z celem pierwotnego LP w jakimkolwiek wykonalnym 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ść ograniczająca zachowuje optymalne wartości podwójnych i pierwotnych LP.

Twierdzenie o silnej dualności stwierdza ponadto, że jeśli pierwotne ma optymalne rozwiązanie, to dual również ma optymalne rozwiązanie, a dwie optymalne 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 (przerwa między optimum pierwotnego i optymalnego dualności ) wynosi 0.

Budowa podwójnego LP

Biorąc pod uwagę pierwotny LP, do skonstruowania podwójnego LP można użyć następującego algorytmu. Podstawowy LP jest definiowany przez:

Zestaw n zmiennych . ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$
Dla każdej zmiennej , o ograniczenie znak - powinno to być nieujemne ( ) lub non-dodatnie ( ) lub nieograniczony ( ). ${\ displaystyle x_ {i}}$ ${\ displaystyle x_ {i} \ geq 0}$ ${\ displaystyle x_ {i} \ leq 0}$ ${\ displaystyle x_ {i} \ in \ mathbb {R}}$
Funkcja celu: ${\ displaystyle {\ text {maksymalizacja}} ~~~ c_ {1} x_ {1} + \ cdots + c_ {n} x_ {n}}$
Lista m ograniczeń. Każde ograniczenie j to: gdzie symbol przed symbolem może być albo albo albo . ${\ Displaystyle a_ {j1} x_ {1} + \ cdots + a_ {jn} x_ {n} \ lesseqqgtr b_ {j}}$ ${\ displaystyle b_ {j}}$ ${\ displaystyle \ geq}$ ${\ displaystyle \ leq}$ ${\ displaystyle =}$

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

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

Na podstawie tego algorytmu łatwo zauważyć, że dwoistość dualna jest pierwotna.

Formuły wektorowe

Jeżeli wszystkie ograniczenia mają ten sam znak, to powyższą recepturę można przedstawić w krótszy sposób za pomocą macierzy i wektorów. Poniższa tabela przedstawia relacje między różnymi rodzajami pierwiastków pierwotnych i dualnych.

Pierwotny	Podwójny	Uwaga
Maksymalizuj c ^T x z zastrzeżeniem A x ≤ b , x ≥ 0	Minimalizuj b ^T y z zastrzeżeniem A ^T y ≥ c , y ≥ 0	Nazywa się to „symetrycznym” problemem dualnym
Maksymalizuj c ^T x z zastrzeżeniem A x ≤ b	Minimalizuj b ^T y z zastrzeżeniem A ^T y = c , y ≥ 0	Nazywa się to „asymetrycznym” problemem dualnym
Maksymalizuj c ^T x z zastrzeżeniem A x = b , x ≥ 0	Minimalizuj b ^T y z zastrzeżeniem A ^T y ≥ c

Twierdzenia o dualności

Poniżej, załóżmy, że pierwotny LP to „maksymalizuj c ^T x podlegający [ograniczeniom]”, a podwójny LP to „minimalizuj b ^T y podlegający [ograniczeniom]”.

Słaba dwoistość

Twierdzenie o słabej dualności mówi, że dla każdego wykonalnego rozwiązania x pierwotnego i każdego wykonalnego y rozwiązania dualnego: c ^T x ≤ b ^T y . Innymi słowy, wartość obiektywna w każdym wykonalnym rozwiązaniu dualności jest górną granicą obiektywnej wartości pierwotnej, a obiektywna wartość w każdym wykonalnym rozwiązaniu pierwotnej jest dolną granicą obiektywnej wartości dualności. Oznacza to:

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

W szczególności, jeśli pierwotny jest nieograniczony (od góry), wtedy dual nie ma wykonalnego rozwiązania, a jeśli podwójny jest nieograniczony (od dołu), to pierwotny nie ma wykonalnego rozwiązania.

Twierdzenie o słabej dualności jest stosunkowo łatwe do udowodnienia. Załóżmy, że podstawowym LP jest „Maksymalizuj c ^T x z zastrzeżeniem A x ≤ b , x ≥ 0”. Załóżmy, że utworzenie liniowej kombinacji z ograniczeniami, z pozytywnymi współczynników w taki sposób, że współczynniki X w ograniczeń są przynajmniej C ^T . Ta liniowa kombinacja daje nam górną granicę celu. Zmienne y podwójnego LP są współczynnikami tej liniowej kombinacji. Podwójny LP próbuje znaleźć takie współczynniki, które minimalizują wynikową górną granicę. Daje to LP „Minimalizuj b ^T y podlega A ^T y ≥ c , y ≥ 0”. Zobacz mały przykład poniżej.

Silna dwoistość

Twierdzenie o silnej dualności mówi, że jeśli jeden z dwóch problemów ma optymalne rozwiązanie, tak samo jest z drugim i że granice podane przez twierdzenie o słabej dualności są ciasne, tj .:

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

Silne twierdzenie o dwoistości jest trudniejsze do udowodnienia; dowody zwykle używają słabego twierdzenia o dwoistości jako podprogramu.

Jeden dowód wykorzystuje algorytm simplex i opiera się na dowodzie, że wraz z odpowiednią regułą obrotu zapewnia prawidłowe rozwiązanie. Dowód ustala, że gdy algorytm simplex zakończy rozwiązanie dla pierwotnego LP, możliwe jest odczytanie z końcowego tableau rozwiązania podwójnego LP. Tak więc, uruchamiając algorytm simplex, otrzymujemy jednocześnie rozwiązania zarówno dla pierwotnego, jak i podwójnego.

Inny dowód wykorzystuje lemat Farkasa .

Implikacje teoretyczne

1. Twierdzenie o słabej dualności oznacza, że znalezienie jednego wykonalnego rozwiązania jest tak trudne, jak znalezienie optymalnego wykonalnego rozwiązania. Załóżmy, że mamy wyrocznię, która mając LP, znajduje dowolne możliwe rozwiązanie (jeśli takie istnieje). Mając 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łączony LP ma zarówno x, jak i y jako zmienne:

Maksymalizuj 1

podlega A x ≤ b , A ^T y ≥ c , c ^T x ≥ b ^T y , x ≥ 0, y ≥ 0

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

2. Twierdzenie o silnej dualności zapewnia „dobrą charakterystykę” optymalnej wartości LP, ponieważ pozwala nam łatwo udowodnić, że pewna wartość t jest optimum dla jakiegoś LP. Dowód przebiega w dwóch etapach:

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

Przykłady

Mały przykład

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

{\ Displaystyle {\ rozpocząć {wyrównane} {\ tekst {maksymalizacja}} i 3x_ {1} + 4x_ {2} \\ {\ tekst {temat}} i 5x_ {1} + 6x_ {2} = 7 \\ & x_ { 1} \ geq 0, x_ {2} \ geq 0 \ end {aligned}}}

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

{\ Displaystyle {\ rozpocząć {wyrównane} {\ tekst {zminimalizować}} i 7y_ {1} \\ {\ tekst {temat do}} i 5y_ {1} \ geq 3 \\ & 6y_ {1} \ geq 4 \\ & y_ { 1} \ in \ mathbb {R} \ end {aligned}}}

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

Podobnie, minimum podwójnego LP jest osiągane, gdy y ₁ jest zminimalizowane do dolnej granicy pod ograniczeniami: 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 twierdzeniem o silnej dualności, maksimum pierwotnej równa się minimum dualności.

Użyjemy tego przykładu, aby zilustrować dowód twierdzenia o słabej dualności. Załóżmy, że w pierwotnym LP chcemy uzyskać górną granicę celu . Możemy użyć ograniczenia pomnożonego przez jakiś współczynnik, powiedzmy . Dla każdego otrzymujemy: . Teraz, jeśli i wtedy tak . W związku z tym celem podwójnego LP jest górna granica celu pierwotnego LP. ${\ displaystyle 3x_ {1} + 4x_ {2}}$ ${\ displaystyle y_ {1}}$ ${\ displaystyle y_ {1}}$ ${\ Displaystyle y_ {1} \ cdot (5x_ {1} + 6x_ {2}) = 7y_ {1}}$ ${\ Displaystyle y_ {1} \ cdot 5x_ {1} \ geq 3x_ {1}}$ ${\ Displaystyle y_ {1} \ cdot 6x_ {2} \ geq 4x_ {2}}$ ${\ Displaystyle y_ {1} \ cdot (5x_ {1} + 6x_ {2}) \ geq 3x_ {1} + 4x_ {2}}$ ${\ displaystyle 7y_ {1} \ geq 3x_ {1} + 4x_ {2}}$

Przykład rolnika

Rozważmy rolnika, który może rosnąć pszenicę i jęczmień z ustawionym świadczenia pewnym L gruntu, F nawozów i P pestycydu. Aby wyhodować jedną jednostkę pszenicy, należy użyć jednej jednostki ziemi, jednostek nawozu i pestycydów. Podobnie, aby wyhodować jedną jednostkę jęczmienia, należy użyć jednej jednostki gruntu, jednostki nawozu i jednostki pestycydu. ${\ displaystyle F_ {1}}$ ${\ displaystyle P_ {1}}$ ${\ displaystyle F_ {2}}$ ${\ displaystyle P_ {2}}$

Podstawowym problemem byłby rolnik decydujący o tym, ile pszenicy ( ) i jęczmienia ( ) mają rosnąć, jeśli ich ceny sprzedaży są i na jednostkę. ${\ displaystyle x_ {1}}$ ${\ displaystyle x_ {2}}$ ${\ Displaystyle S_ {1}}$ ${\ Displaystyle S_ {2}}$

Wyolbrzymiać: ${\ Displaystyle S_ {1} \ cdot x_ {1} + S_ {2} \ cdot x_ {2}}$		(zmaksymalizuj przychody z produkcji pszenicy i jęczmienia)
z zastrzeżeniem:	${\ displaystyle x_ {1} + x_ {2} \ równoważnik L}$	(nie można użyć więcej ziemi niż jest dostępna)
	${\ 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} \ leq P}$	(nie można użyć więcej pestycydów niż jest dostępne)
	${\ displaystyle x_ {1}, x_ {2} \ geq 0}$	(nie może produkować ujemnych ilości pszenicy lub jęczmienia).

W postaci macierzy staje się to:

Wyolbrzymiać:

{\ displaystyle {\ begin {bmatrix} S_ {1} i S_ {2} \ end {bmatrix}} {\ begin {bmatrix} x_ {1} \\ x_ {2} \ end {bmatrix}}}

z zastrzeżeniem:

{\ displaystyle {\ begin {bmatrix} 1 i 1 \\ F_ {1} i F_ {2} \\ P_ {1} i 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 podwójnego załóżmy, że ceny jednostkowe y dla każdego z tych środków produkcji (nakładów) są ustalane przez tablicę planistyczną. Zadaniem rady planistycznej jest zminimalizowanie całkowitego kosztu pozyskania określonej ilości nakładów, przy jednoczesnym zapewnieniu rolnikowi minimalnej ceny jednostkowej każdej z jego upraw (produkcji), S ₁ dla pszenicy i S ₂ dla jęczmienia. Odpowiada to następującemu LP:

Zminimalizować: ${\ Displaystyle L \ cdot y_ {L} + F \ cdot y_ {F} + P \ cdot y_ {P}}$		(zminimalizować całkowity koszt środków produkcji jako „funkcja celu”)
z zastrzeżeniem:	${\ Displaystyle y_ {L} + F_ {1} \ cdot y_ {F} + P_ {1} \ cdot y_ {P} \ geq S_ {1}}$	(rolnik musi otrzymać nie mniej niż S ₁ 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 ₂ za swój jęczmień)
	${\ displaystyle y_ {L}, y_ {F}, y_ {P} \ geq 0}$	(ceny nie mogą być ujemne).

W postaci macierzy staje się to:

Zminimalizować:

{\ displaystyle {\ begin {bmatrix} L & F i P \ end {bmatrix}} {\ begin {bmatrix} y_ {L} \\ y_ {F} \\ y_ {P} \ end {bmatrix}}}

z zastrzeżeniem:

{\ displaystyle {\ begin {bmatrix} 1 & F_ {1} & P_ {1} \\ 1 & F_ {2} & P_ {2} \ end {bmatrix}} {\ begin {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.}

Pierwotny problem dotyczy wielkości fizycznych. Przy wszystkich nakładach dostępnych w ograniczonych ilościach i przy założeniu, że ceny jednostkowe wszystkich produktów są znane, jakie ilości produkcji należy wyprodukować, aby zmaksymalizować całkowity dochód? Podwójny problem dotyczy wartości ekonomicznych. Przy gwarancjach dolnego progu dla wszystkich wyjściowych cen jednostkowych i przy założeniu, że dostępna ilość wszystkich nakładów jest znana, jaki schemat cen jednostkowych nakładów należy ustalić, aby zminimalizować całkowite wydatki?

Każdej zmiennej w przestrzeni pierwotnej odpowiada nierówność, którą należy spełnić w przestrzeni podwójnej, obie indeksowane według typu danych wyjściowych. Każdej nierówności do spełnienia w przestrzeni pierwotnej odpowiada zmienna w przestrzeni podwójnej, obie indeksowane według typu danych wejściowych.

Współczynniki, które ograniczają nierówności w przestrzeni pierwotnej, są używane do obliczenia celu w przestrzeni podwójnej, 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, czyli wyjściowe ceny jednostkowe w tym przykładzie.

Zarówno pierwotne, jak i podwójne problemy 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 produktów. W przestrzeni dualnej wyraża tworzenie wartości ekonomicznych związanych z wynikami z ustalonych cen jednostkowych nakładów.

Ponieważ każdą nierówność można zastąpić zmienną równości i luzu, oznacza to, że każda zmienna podstawowa odpowiada podwójnej zmiennej zapasu, a każda zmienna podwójna odpowiada pierwotnej zmiennej zapasu. Ta relacja pozwala mówić o komplementarnej luźności.

Niewykonalny program

LP może być również nieograniczony lub niewykonalny. Teoria dualizmu mówi nam, że:

Jeśli pierwotność jest nieograniczona, to dualność jest niewykonalna;
Jeśli dualność jest nieograniczona, to pierwotność jest niewykonalna.

Jednak możliwe jest, że zarówno to, co podwójne, jak i to, co pierwotne, będzie niewykonalne. Oto przykład:

Wyolbrzymiać: ${\ Displaystyle 2x_ {1} -x_ {2}}$
Z zastrzeżeniem:	${\ displaystyle x_ {1} -x_ {2} \ leq 1}$
	${\ Displaystyle -x_ {1} + X_ {2} \ równoważnik -2}$
	${\ Displaystyle x_ {1}, x_ {2} \ geq 0.}$

Aplikacje

Twierdzenie max-flow min-cut jest szczególnym przypadkiem twierdzenia o silnej dualności: maksymalizacja przepływu to pierwotny LP, a minimalizacja przecięcia to podwójny LP. Zobacz twierdzenie o maksymalnym przepływie i minimalnym cięciu # Liniowe formułowanie programu .

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

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

Alternatywny algorytm

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

Zminimalizować	${\ Displaystyle \ sum _ {i = 1} ^ {m} c_ {i} x_ {i} + \ sum _ {j = 1} ^ {n} d_ {j} t_ {j}}$
z zastrzeżeniem	${\ Displaystyle \ sum _ {i = 1} ^ {m} a_ {ij} x_ {i} + e_ {j} t_ {j} \ geq g_ {j},}$	${\ Displaystyle 1 \ równoważnik j \ równoważnik n}$
	${\ displaystyle f_ {i} x_ {i} + \ sum _ {j = 1} ^ {n} b_ {ij} t_ {j} \ geq h_ {i},}$	${\ Displaystyle 1 \ równoważnik i \ 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 zmienne dualne m + n : y _j oraz s _i . Otrzymujemy:

Zminimalizować	${\ Displaystyle \ sum _ {i = 1} ^ {m} c_ {i} x_ {i} + \ sum _ {j = 1} ^ {n} d_ {j} t_ {j}}$
z zastrzeżeniem	${\ Displaystyle \ sum _ {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} + \ sum _ {j = 1} ^ {n} b_ {ij} t_ {j} \ cdot s_ {i} \ geq h_ {i} \ cdot s_ {i},}$	${\ Displaystyle 1 \ równoważnik i \ 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ć podwójny program, który jest dolną granicą pierwotnego. Innymi słowy, chcielibyśmy, aby suma wszystkich ograniczeń po prawej stronie 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 + f ₁ s ₁ . Suma ta nie może przekraczać c ₁ . W efekcie otrzymujemy:

Wyolbrzymiać	${\ Displaystyle \ sum _ {j = 1} ^ {n} g_ {j} y_ {j} + \ sum _ {i = 1} ^ {m} h_ {i} s_ {i}}$
z zastrzeżeniem	${\ displaystyle \ sum _ {j = 1} ^ {n} a_ {ij} y_ {j} + f_ {i} s_ {i} \ równoważnik c_ {i},}$	${\ Displaystyle 1 \ równoważnik i \ równoważnik m}$
	${\ displaystyle e_ {j} y_ {j} + \ sum _ {i = 1} ^ {m} b_ {ij} s_ {i} \ leq d_ {j},}$	${\ 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ż, że w naszych krokach obliczeniowych zakładamy, że program jest w standardowej formie. Jednak każdy program liniowy może zostać przekształcony do postaci standardowej i dlatego nie jest czynnikiem ograniczającym.

Interpretacje z życia wzięte

Twierdzenie o dualności ma interpretację ekonomiczną. Jeśli zinterpretujemy pierwotny LP jako klasyczny problem „alokacji zasobów”, jego podwójny LP może być zinterpretowany jako problem „wyceny zasobów”. Zobacz także Cena cienia .

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

Languages

In other projects