Zasady tworzenia zadania dualnego:
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:
• Współczynniki funkcji celu zadania pierwotnego są wyrazami wolnymi układu nierówności zadania dualnego
• Wyrazy wolne układu nierówności zadania pierwotnego są współczynnikami funkcji celu zadania dualnego
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) Odwrotny kierunek optymalizacji
Znak nierówności w warunku ograniczającym ↔ warunek znakowy zmiennej decyzyjnej:
• JeŜeli 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Ŝeli w ZP i-ty warunek jest równością to odpowiadająca mu zmienna yi nie ma ograniczeń
• JeŜeli w ZP i-ty warunek jest nietypową nierównością to odpowiadająca mu zmienna yi≤0
• JeŜeli w ZP zmienna xj≥0 to j-ty warunek ZD jest typową nierównością
• JeŜeli w ZP na zmienną xj nie nałoŜono ograniczeń to j-ty warunek ZD jest równością
• JeŜeli w ZP zmienna xj≤0 to j-ty warunek ZD jest nietypową nierównością Zadaniem dualnym dla zadania dualnego (ZD) jest zadanie pierwotne (ZP)
Przykład tworzenia zadania dualnego:
zadanie pierwotne:
zadanie dualne:
funkcja celu: 15y1+5y2+12y3→min
funkcja celu: 2x1+1x2-5x3+7x4→max
warunek 1: 4y1+5y2+9y3≤2
warunek 1: 4x1+6x2+2x3+1x4≤15
warunek 2: 6y1+0y2+1y3=1
warunek 2: 5x1 -8x3+2x4≥5
warunek 3: 2y1-8y2+4y3≥-5
warunek 3: 9x1+1x2+4x3-5x4=12
warunek 4: 1y1+2y2-5y3≥7
warunki znakowe: x1≤0, x2-dowolne, x3 ,x4≥0
warunki znakowe: y1≥0, y2≤0, y3-dowolne
Interpretacja ekonomiczna: wartość zmiennej dualnej yi mówi nam o ile zmieni się wartość funkcji celu zadania pierwotnego jeŜeli wartość wyrazu wolnego bi wzrośnie o 1 (w określonym przedziale).
Wartość zmiennej dualnej yi nazywana jest takŜe wyceną i-tego środka produkcji. Zakupienie jednostki danego środka produkcji zwiększa nam wartość funkcji celu o yi (przynosi dodatkową korzyść w tej wysokości), zatem tyle ten środek jest dla nas wart. Jeśli chcielibyśmy go dokupić to opłaca nam się to zrobić po cenie niŜszej od yi (wtedy osiągniemy jednostkową korzyść netto wynoszącą yi minus koszt zakupu jednostki środka produkcji).