45503

Podstawowe określenia i twierdzenia dotyczące programem 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) = 50xi+80x₂+0x3+0x45xi+3x2+1x3⁺0x4=15 4xi+6x2+0x3+1x4=24xi; X2; X3j X4>0

Określenia określające pro&ramowąme linpwę;

1, Rozwiązanie dopuszczalne - każdy wektor x =(xi; X2;x3...x„) spełniający waninki ograniczające i brzegowe rozwiązań dopuszczalnych jest nieskończenie wiele

2, Rozwiązanie brzegowe - każdy wektor x=(xi; X2;x3...Xn.o,...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(l)= (x,; x₂; 0; 0) X(2)= (x,; 0; x₃; 0) X(3)= (x,; 0; 0; x₄)

X(4)= (0; x₂; x₃; 0) X(5)= (0; _Xz; 0; x₄) X(6)= (0; 0; x₃; x₄)

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.

Wtynika 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.