Optymalizacja wypukła - programowanie liniowe
Metodologia
Programowanie liniowe, zwane także optymalizacją liniową, jest techniką używaną do rozwiązywania problemów matematycznych, w których zależności mają charakter liniowy. podstawową naturą programowania liniowego jest maksymalizacja lub minimalizacjaobjective function z zastrzeżeniem niektórych constraints. Funkcja celu jest funkcją liniową uzyskaną z matematycznego modelu problemu. Więzy to warunki, które są nałożone na model i są również liniowe.
- Na podstawie zadanego pytania znajdź funkcję celu.
- znaleźć ograniczenia.
- Narysuj ograniczenia na wykresie.
- znajdź wykonalny region, który jest utworzony przez przecięcie wszystkich ograniczeń.
- znajdź wierzchołki wykonalnego regionu.
- znajdź wartość funkcji celu w tych wierzchołkach.
- Wierzchołek, który maksymalizuje lub minimalizuje funkcję celu (zgodnie z pytaniem) jest odpowiedzią.
Przykłady
Step 1 - Maksymalizuj 5 $ x + 3 lata z zastrzeżeniem
$ x + y \ leq 2 $,
$ 3x + y \ leq 3 $,
$ x \ geq 0 \: i \: y \ geq 0 $
Solution -
Pierwszym krokiem jest znalezienie odpowiedniego regionu na wykresie.
Wyraźnie z wykresu wynika, że wierzchołki możliwego obszaru są
$ \ left (0, 0 \ right) \ left (0, 2 \ right) \ left (1, 0 \ right) \ left (\ frac {1} {2}, \ frac {3} {2} \ right ) $
Niech $ f \ left (x, y \ right) = 5x + 3y $
Umieszczając te wartości w funkcji celu, otrzymujemy -
$ f \ left (0, 0 \ right) $ = 0
$ f \ left (0, 2 \ right) $ = 6
$ f \ left (1, 0 \ right) $ = 5
$ f \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $ = 7
Dlatego funkcja maksymalizuje w $ \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $
Step 2- Firma zegarmistrzowska produkuje zegarek cyfrowy i mechaniczny. Prognozy długoterminowe wskazują na spodziewane zapotrzebowanie na co najmniej 100 zegarków cyfrowych i 80 zegarków mechanicznych każdego dnia. Ze względu na ograniczenia zdolności produkcyjnej dziennie można wyprodukować nie więcej niż 200 zegarków cyfrowych i 170 mechanicznych. Aby spełnić warunki umowy wysyłkowej, każdego dnia wysyłanych jest co najmniej 200 zegarków.
Jeżeli każdy sprzedany zegarek cyfrowy przynosi 2 $ \ $ straty, ale każdy zegarek mechaniczny przynosi 5 $ \ $ zysku, ile każdego typu zegarka należy robić codziennie, aby zmaksymalizować zysk netto?
Solution -
Niech x $ będzie liczbą wyprodukowanych zegarków cyfrowych
$ y $ to liczba wyprodukowanych zegarków mechanicznych
Zgodnie z pytaniem, co najmniej 100 zegarków cyfrowych ma być wykonywanych dziennie i można wykonać maksymalnie 200 zegarków cyfrowych.
$ \ Rightarrow 100 \ leq \: x \ leq 200 $
Podobnie, co najmniej 80 zegarków mechanicznych ma być wytwarzanych dziennie, a maksymalnie 170 zegarków mechanicznych.
$ \ Rightarrow 80 \ leq \: y \ leq 170 $
Ponieważ każdego dnia ma być produkowanych co najmniej 200 zegarków.
$ \ Rightarrow x + y \ leq 200 $
Ponieważ każdy sprzedany zegarek cyfrowy przynosi 2 $ \ $ straty, ale każdy zegarek mechaniczny przynosi 5 $ \ $ zysku,
Całkowity zysk można obliczyć jako
Zysk $ = -2x + 5y $
I musimy maksymalizować zysk, dlatego pytanie można sformułować jako -
Maksymalizuj -2 x + 5 $ z zastrzeżeniem
100 $ \: \ leq x \: \ leq 200 $
80 $ \: \ leq y \: \ leq 170 $
$ x + y \: \ leq 200 $
Przedstawiając powyższe równania na wykresie, otrzymujemy:
Wierzchołki obszaru wykonalnego to
$ \ left (100, 170 \ right) \ left (200, 170 \ right) \ left (200, 180 \ right) \ left (120, 80 \ right) and \ left (100, 100 \ right) $
Maksymalną wartość funkcji celu uzyskuje się na poziomie $ \ left (100, 170 \ right) $. Zatem, aby zmaksymalizować zysk netto, należy wyprodukować 100 jednostek zegarków cyfrowych i 170 jednostek zegarków mechanicznych.