1Dualizm w zagadnieniu programowania liniowego

Nasza ocena:

5
Pobrań: 7
Wyświetleń: 609
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
1Dualizm w zagadnieniu programowania liniowego - strona 1 1Dualizm w zagadnieniu programowania liniowego - strona 2 1Dualizm w zagadnieniu programowania liniowego - strona 3

Fragment notatki:


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)

Zaloguj się, aby dodać komentarz