Podstawowe określenia i twierdzenia dotyczące programów liniowych (liczba rozwiązań ) DWIE POSTACIE PROGRAMÓW LINIOWYCH 1,Postać standardowa
2,Postać kanoniczna - jest to przekształcona postać standardowa, przekształcenie polega na zamianie warunków w równaniu: L(x) = 50x 1 +80x 2 +0x 3 +0x 4 5x 1 +3x 2 +1x 3 +0x 4 =15 4x 1 +6x 2 +0x 3 +1x 4 =24x 1 ; x 2 ; x 3 ; x 4 ≥0 Określenia określające programowanie linowe: 1,Rozwiązanie dopuszczalne - każdy wektor x =(x 1 ; x 2 ;x 3 …x n ) spełniający warunki ograniczające i brzegowe rozwiązań dopuszczalnych jest nieskończenie wiele 2,Rozwiązanie brzegowe - każdy wektor x=(x 1 ; x 2 ;x 3 …x n-0 ,…0), rozwiązanie otrzymamy poprzez porównanie n-m zmiennych dla zera i rozwiązanie układu rozwiązań względem m zmiennych. Liczba rozwiązań jest równa: Przykład: X(1)= (x 1 ; x 2 ; 0; 0) X(2)= (x 1 ; 0; x 3 ; 0) X(3)= (x 1 ; 0; 0; x 4 )
X(4)= (0; x 2 ; x 3 ; 0) X(5)= (0; x 2 ; 0; x 4 ) X(6)= (0; 0; x 3 ; x 4 )
3,Bazowe rozwiązanie dopuszczalne (wierzchołkowe) - to takie rozwiązania bazowe, które spełniają warunki brzegowe. Maksymalna liczba rozwiązań wskazuje pierwszy wzór, ale na ogół jest ich więcej 4,Rozwiązanie optymalne - to takie, które spełnia funkcje celu. Rozwiązanie może być jedna, nieskończenie wiele lub 0 - (kiedy zadanie będzie sprzeczne)
TWIERDZENIA:
5,ZBIÓR ROZWIĄZAŃ DOPUSZCZALNYCH MPL - jest zbiorem wypukłym. Jeśli weźmiemy dwa niezbędne punkty 2 rozwiązań i połączymy je, to ten odcinek będzie zależał w całości od obszaru. 6,Jeżeli istnieje optymalne rozwiązanie modelu programowanie liniowego to jest m. in. przynajmniej jedno z bazowych rozwiązań dopuszczalnych. Wynika z niego, że należy znaleźć wszystkie rozwiązania bazowe, sprawdzić które z nich są rozwiązaniami wierzchołkowymi dla n - wierzchołkowych należy wyznaczyć wartość funkcji celu tam gdzie wartość będzie największa, będzie rozwiązanie optymalne.
... zobacz całą notatkę
Komentarze użytkowników (0)