1 Dualizm w zagadnieniu programowania liniowego n x m m x n Rozmiar Warunki ograniczające Warunki nieujemności min max Kryterium funkcji celu Funkcja celu yi , i = 1, …, m xj , j = 1, …, n Zmienne decyzyjne Dualne (lub pierwotne) Pierwotne (lub dualne) . , , 1 , 0 m i y i K = ≥ min 1 → = ∑ = m i i i y b z m i b x a i n j j ij ,..., 1 , 1 = ≤ ∑ = n j c y a j m i i ij ,..., 1 , 1 = ≥ ∑ = max 1 → = ∑ = n j j j x c z . , , 1 , 0 n j x j K = ≥ Zagadnienie dualne do dualnego jest zagadnieniem pierwotnym! Dla kaŜdego ZPL istnieje para problemów: ZP − pierwotne (prymalne) i ZD − dualne (dwoiste) 2 Twierdzenie dualne a) JeŜeli zagadnienia pierwotne (ZP) i dualne (ZD) mają rozwiązania dopuszczalne i , dla j = 1, 2, …, n, jest rozwiązaniem optymalnym ZP oraz , dla i = 1, 2, …, m, jest rozwiązaniem optymalnym zagadnienia dualnego, to: b) JeŜeli ZP (ZD) ma skończone rozwiązanie optymalne, to odpowiadające mu ZD (ZP) ma równieŜ rozwiązanie optymalne z tą samą wartością funkcji celu. Twierdzenia o rozwiązaniu ZP i ZD ∑ ∑ = = = m i i i n j j j y b x c 1 1 i y j x 3 WNIOSEK: JeŜeli któryś z warunków ograniczających ZP lub ZD spełniony jest z ostrą nierównością, to odpowiadająca mu zmienna w zagadnieniu sprzęŜonym jest równa zeru. Twierdzenia o rozwiązaniu ZP i ZD, cd. Twierdzenie o róŜnicach dopełniających Niech , dla j= 1, 2, …, n, oraz , dla i = 1,…, m, oznaczają odpowiednio rozwiązania dopuszczalne ZP i ZD. Rozwiązania te są rozwiązaniami optymalnymi i y j x . ,..., 2 , 1 , 0 , ,..., 2 , 1 , 0 1 1 n j c y a x m i b x a y j m i i ij j i n j j ij i = = − = = − ∑ ∑ = =
... zobacz całą notatkę
Komentarze użytkowników (0)