Dualizm w liniowych problemach z programowaniem
Dualizm w problemach programowania liniowego!
Dla każdego problemu programowania liniowego istnieje odpowiedni unikalny problem obejmujący te same dane, a także opisuje pierwotny problem. Pierwotny problem nazywa się programem pierwotnym, a odpowiadający mu unikalny problem nazywa się Programem podwójnym. Oba programy są bardzo ściśle powiązane, a optymalne rozwiązanie dual daje pełne informacje o optymalnym rozwiązaniu pierwotnego i odwrotnie.
Różne użyteczne aspekty tej właściwości to:
(a) Jeśli pierwotny ma dużą liczbę stałych i małą liczbę zmiennych, obliczenia można znacznie zmniejszyć, przekształcając problem w Dual, a następnie rozwiązując go.
(b) Dualizm w programowaniu liniowym ma pewne daleko idące konsekwencje natury ekonomicznej. Może to pomóc menedżerom w odpowiadaniu na pytania dotyczące alternatywnych kierunków działań i ich względnych wartości.
(c) Obliczenie podwójnej kontroli dokładności pierwotnego rozwiązania.
(d) Dualizm w programowaniu liniowym pokazuje, że każdy program liniowy jest równoważny grze dwuosobowej o sumie zerowej. Wskazuje to na dość bliskie relacje między programowaniem liniowym a teorią gier.
1. Formowanie podwójne, gdy Primal jest w formie kanonicznej:
Z powyższych dwóch programów jasno wynikają następujące kwestie:
(i) Problem maksymalizacji w pierwotnym staje się problemem minimalizacji w systemie dualnym i vice versa.
(ii) Problem maksymalizacji ma () ograniczenia.
(iii) Jeśli pierwotny zawiera n zmiennych i m ograniczeń, dual będzie zawierać m zmiennych i n ograniczeń.
(iv) Stałe b 1 b 2, b 3 ......... b m w ograniczeniach pierwotnych pojawiają się w funkcji celu dwoistego.
(v) Stałe c 1, c 2, c 3 c n w funkcji celu pierwotnego pojawiają się w ograniczeniach dualu.
(vi) Zmienne w obu problemach są nieujemne.
Relacje więzów pierwotnych i podwójnych przedstawiono poniżej.
Przykład 1:
Zbuduj podwójny do pierwotnego problemu
Rozwiązanie:
Po pierwsze, ograniczenie ≥ jest przekształcane na ≤ ograniczenie przez pomnożenie obu stron przez -1.
Przykład 2:
Zbuduj podwójny do pierwotnego problemu
Rozwiązanie:
Niech Y 1, Y 2, V 3 i V 4 będą odpowiednimi podwójnymi zmiennymi, wtedy problem podwójny jest podany przez
Ponieważ problem podwójny ma mniejszą liczbę ograniczeń niż pierwotna (2 zamiast 4), wymaga mniejszej pracy i wysiłku, aby go rozwiązać. Wynika to z faktu, że trudności obliczeniowe w problemie programowania liniowego są związane głównie z liczbą ograniczeń, a nie liczbą zmiennych.
Przykład 3:
Zbuduj podwójny problem
Rozwiązanie:
Ponieważ problemem jest minimalizacja, wszystkie ograniczenia powinny być> typu. Mnożąc trzecie ograniczenie przez-1 po obu stronach otrzymujemy.
-8x 1 + 2x 2 + 2x 3 ≥ -10
Dwoistością danego problemu będzie
gdzie y 1, y 2, y 3, y 4 i y 5 są podwójnymi zmiennymi związanymi odpowiednio z pierwszym, drugim trzecim, czwartym i piątym ograniczeniem.
