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.