mgr inż. Magdalena Mytkowska. Ćwiczenia Badania operacyjne. Dualność.

Z relacji zachodzących między zadaniem pierwotnym a zadaniem dualnym wynika, że:

Zmienne decyzyjne ↔ warunki ograniczające:

· W zadaniu dualnym jest tyle zmiennych ile warunków ograniczających w zadaniu pierwotnym;

· W zadaniu dualnym jest tyle warunków ograniczających ile zmiennych w zadaniu pierwotnym;

Współczynniki (wagi) funkcji celu ↔ wyrazy wolne układu nierówności:

· Wyrazy wolne zadania pierwotnego są wagami funkcji celu w zadaniu dualnym;

· Wagi funkcji celu zadania pierwotnego są wyrazami wolnymi w zadaniu dualnym;

Odwrotny kierunek optymalizacji:

· Jeśli zadanie pierwotne jest na maksimum to zadanie dualne jest na minimum i odwrotnie;

Transpozycja współczynników w układzie nierówności:

· Współczynniki układu nierówności w programie dualnym powstają z transpozycji współczynników układu nierówności w zadaniu pierwotnym (i odwrotnie);

Znak nierówności w warunku ograniczającym « warunek znakowy zmiennej decyzyjnej:

· Jeśli w ZP i-ty warunek jest typową nierównością (odwrotną do kierunku optymalizacji tego zadania,

tzn. ≤ dla max i ≥ dla min) to odpowiadająca mu zmienna yi≥0 (typowy warunek znakowy);

· Jeśli w ZP i-ty warunek jest równością to odpowiadająca mu zmienna yi nie ma ograniczeń;

· Jeśli w ZP i-ty warunek jest nietypową nierównością to odpowiadająca mu zmienna yi≤0;

· Jeśli w ZP zmienna xj≥0 to j-ty warunek ZD jest typową nierównością;

· Jeśli w ZP na zmienną xj nie nałożono ograniczeń to j-ty warunek ZD jest równością;

· Jeśli w ZP zmienna xj≤0 to j-ty warunek ZD jest nietypową nierównością;

Typowość/ nietypowość zwrotu nierówności w zależności od kierunku optymalizacji.

Przykład tworzenia zadania dualnego:

zadanie pierwotne (ZP): zadanie dualne (ZD):

funkcja celu: 2x₁+1x₂-5x₃+7x₄→max funkcja celu: 15y₁+5y₂+12y₃→min

warunek 1: 4x₁+6x₂+2x₃+1x₄≤15 warunek 1: 4y₁+5y₂+9y₃≤2

warunek 2: 5x₁ -8x₃+2x₄≥5 warunek 2: 6y₁+0y₂+1y₃=1

warunek 3: 9x₁+1x₂+4x₃-5x₄=12 warunek 3: 2y₁-8y₂+4y₃≥-5

warunek 4: 1y₁+2y₂-5y₃≥7

warunki znakowe: x₁≤0, x₂-dowolne, x₃ ,x₄≥0 warunki znakowe: y₁≥0, y₂≤0, y₃-dowolne

---