45497

Twierdzenia programów liniowych

1)    Zbiór rozwiązań dopuszczalnych MPL jest zbiorem wypukły. Jeśli weźmiemy 2 niezbedne punkty z rozwiązań I połączymy je to ten odcinek bedzie należał w całości do obszaru

2)    Jeśli istnieje optymalne rozwiązanie modelu programowania liniowego to jest nim 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.

**Określenia określające programowanie linowe:

1.    Rozwiązanie dopuszczalne - każdy wektor x =(xl; x2;x3...xn) spełniający warunki ograniczające i brzegowe rozwiązań dopuszczalnych jest nieskończenie wiele

2.    Rozwiązanie brzegowe - każdy wektor x=(xl; x2;x3...xn-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:    ^m

c* — ** — ^

Przykład: ^{2 2!(4_2)!}

X(l)= (xl; x2; 0; 0) X(2)= (xl; 0; x3; 0) X(3)= (xl; 0; 0; x4) X(4)= (0; x2; x3; 0)

X(5)= (0; x2; 0; x4) X(6)= (0; 0; x3; x4)

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)