Rozwiązanie problemów optymalizacji sterowania metodą programowania liniowego
Poprzednio opisałem jak podejmowanie decyzji z ograniczającymi czynnikami . Celem takich decyzji jest określenie asortymentu produktów (plan produkcji), który maksymalizuje zysk firmy. Rozwiązaniem było przydzielenie zasobów między produktami według krańcowego zysku na jednostkę ograniczonych zasobów, z zastrzeżeniem wszelkich innych ograniczeń, takich jak maksymalne lub minimalne zapotrzebowanie na niektóre rodzaje produktów. [1]
Jeśli istnieje jeden czynnik ograniczający (na przykład wadliwa maszyna), rozwiązanie można znaleźć za pomocą prostych formuł (patrz link na początku artykułu). Jeśli istnieje kilka czynników ograniczających, stosowana jest metoda programowania liniowego.
Programowanie liniowe to nazwa kombinacji narzędzi stosowanych w naukach o zarządzaniu. Ta metoda rozwiązuje problem przydzielania ograniczonych zasobów między konkurencyjne działania w celu zmaksymalizowania lub zminimalizowania pewnych wartości liczbowych, takich jak krańcowe zyski lub wydatki. W biznesie można go wykorzystywać w takich obszarach, jak planowanie produkcji w celu maksymalizacji zysków, wybór komponentów w celu zminimalizowania kosztów, wybór portfela inwestycyjnego w celu maksymalizacji rentowności, optymalizacja transportu towarów w celu zmniejszenia odległości, przydzielenie personelu w celu maksymalizacji wydajności pracy i harmonogramowania zaoszczędzić czas.
Pobierz notatkę w formacie Słowo , zdjęcia w formacie Excel
Programowanie liniowe obejmuje budowę modelu matematycznego danego problemu. Następnie rozwiązanie można znaleźć graficznie (omówiono poniżej), korzystając z programu Excel (do rozważenia oddzielnie) lub specjalistycznych programów komputerowych. [2]
Być może konstrukcja modelu matematycznego jest najtrudniejszą częścią programowania liniowego, wymagającą przetłumaczenia danego problemu na system zmiennych, równań i nierówności - proces, który ostatecznie zależy od umiejętności, doświadczenia, umiejętności i intuicji kompilatora modelu.
Rozważmy przykład konstruowania matematycznego modelu programowania liniowego.
Nikołaj Kuzniecow zarządza małym zakładem mechanicznym. W przyszłym miesiącu planuje wyprodukować dwa produkty (A i B), dla których konkretny zysk krańcowy szacuje się odpowiednio na 2500 i 3500 rubli.
Produkcja obu produktów wymaga kosztów obróbki maszynowej, surowców i robocizny (rys. 1). W celu wytworzenia każdej jednostki produktu A podaje się 3 godziny obróbki maszynowej, 16 jednostek surowców i 6 jednostek pracy. Odpowiednie wymagania dla jednostki produktu B wynoszą 10, 4 i 6. Nikolay przewiduje, że w przyszłym miesiącu może zapewnić 330 godzin obróbki maszynowej, 400 jednostek surowców i 240 jednostek pracy. Technologia procesu produkcyjnego jest taka, że co najmniej 12 jednostek produktu B musi być wytwarzanych w każdym miesiącu.
Rys. 1. Użytkowanie i udostępnianie zasobów
Nikolai chce zbudować model w celu określenia liczby jednostek produktów A i B, które ma wyprodukować w przyszłym miesiącu, aby zmaksymalizować marżę zysku.
Model liniowy można zbudować w czterech etapach.
Etap 1. Definicja zmiennych
Istnieje zmienna docelowa (oznaczona przez Z), która musi zostać zoptymalizowana, czyli zmaksymalizowana lub zminimalizowana (na przykład zysk, przychód lub wydatki). Nikolai dąży do maksymalizacji marginalnego zysku, a więc zmiennej docelowej:
Z = całkowita marża zysku (w rublach) otrzymana w następnym miesiącu w wyniku produkcji produktów A i B.
Istnieje pewna liczba nieznanych pożądanych zmiennych (oznaczamy je jako x1, x2, x3 itd.), Których wartości należy określić w celu uzyskania optymalnej wartości funkcji celu, która w naszym przypadku jest całkowitym marginalnym zyskiem. Ten marginalny zysk zależy od ilości produktów A i B. Wartości tych wielkości muszą być obliczone, a zatem są to pożądane zmienne w modelu. Oznacza to:
x1 = liczba jednostek produktu A wyprodukowanych w przyszłym miesiącu.
x2 = liczba jednostek produktu B wyprodukowanych w przyszłym miesiącu.
Bardzo ważne jest jasne zdefiniowanie wszystkich zmiennych; Zwróć szczególną uwagę na jednostki miary i okres, do którego należą zmienne.
Etap. 2. Konstrukcja funkcji celu
Funkcja celu jest równaniem liniowym, które musi być zmaksymalizowane lub zminimalizowane. Zawiera zmienną docelową wyrażoną za pomocą pożądanych zmiennych, to znaczy Z wyrażoną w x1, x2 ... jako równanie liniowe.
W naszym przykładzie każdy wyprodukowany produkt A przynosi 2500 rubli. marginalny zysk, a przy wytwarzaniu x1 jednostek produktu A, krańcowy zysk wyniesie 2500 * x1. Podobnie krańcowy zysk z produkcji jednostek x2 produktu B wyniesie 3500 * x2. Zatem całkowity zysk krańcowy otrzymany w następnym miesiącu z powodu produkcji x1 jednostek produktu A i jednostek x2 produktu B, czyli zmiennej docelowej Z będzie:
Z = 2500 * x1 + 3500 * x2
Nikołaj stara się zmaksymalizować tę liczbę. Tak więc funkcja celu w naszym modelu:
Maksymalizuj Z = 2500 * x1 + 3500 * x2
Etap. 3. Definicja ograniczeń
Ograniczenia to system równań liniowych i / lub nierówności, które ograniczają wartości pożądanych zmiennych. Matematycznie odzwierciedlają dostępność zasobów, czynników technologicznych, warunków marketingowych i innych wymagań. Ograniczenia mogą mieć trzy typy: „mniejszy lub równy”, „większy niż lub równy”, „ściśle równy”.
W naszym przykładzie produkcja produktów A i B wymaga czasu przetwarzania maszyn, surowców i robocizny, a dostępność tych zasobów jest ograniczona. Wielkość produkcji tych dwóch produktów (tj. Wartości x1 i 2) będzie zatem ograniczona faktem, że ilość zasobów wymaganych w procesie produkcji nie może przekroczyć dostępnych. Rozważ sytuację z czasem przetwarzania maszyny. Wytwarzanie każdej jednostki produktu A wymaga trzech godzin obróbki maszynowej, a jeśli zostanie wykonane x1, jednostki, a następnie 3 * x1 godziny zostaną wykorzystane, godziny tego zasobu. Wytwarzanie każdej jednostki produktu B wymaga 10 godzin, a zatem, jeśli wytwarzane są produkty x2, zajmie to 10 * x2 godzin. Zatem całkowita ilość czasu maszynowego wymagana do wytworzenia x1 jednostek produktu A i jednostek x2 produktu B wynosi 3 * x1 + 10 * x2. Ten całkowity czas komputera nie może przekroczyć 330 godzin. Matematycznie jest to napisane w następujący sposób:
3 * x1 + 10 * x2 ≤ 330
Podobne rozważania dotyczą surowców i robocizny, co pozwala nam napisać dwa dodatkowe ograniczenia:
16 * x1 + 4 * x2 ≤ 400
6 * x1 + 6 * x2 ≤ 240
Na koniec należy zauważyć, że istnieje warunek, zgodnie z którym należy wyprodukować co najmniej 12 jednostek produktu B:
x2 ≥ 12
Krok 4. Zapisz warunki nieujemności
Żądane zmienne nie mogą być liczbami ujemnymi, które muszą być zapisane w postaci nierówności x1 ≥ 0 i x2 ≥ 0. W naszym przykładzie drugi warunek jest zbędny, ponieważ został określony powyżej, że x2 nie może być mniejszy niż 12.
Pełny model programowania liniowego dla problemu produkcyjnego Nikołaja można zapisać jako:
Maksymalizuj: Z = 2500 * x1 + 3500 * x2
Pod warunkiem, że: 3 * x1 + 10 * x2 ≤ 330
16 * x1 + 4 * x2 ≤ 400
6 * x1 + 6 * x2 ≤ 240
x2 ≥ 12
x1 ≥ 0
Rozważmy graficzną metodę rozwiązywania problemu programowania liniowego.
Ta metoda nadaje się tylko do zadań z dwiema pożądanymi zmiennymi. Model skonstruowany powyżej zostanie użyty do zademonstrowania metody.
Osie na wykresie to dwie pożądane zmienne (rys. 2). Nie ma znaczenia, którą zmienną umieścić wzdłuż której osi. Ważne jest, aby wybrać skalę, która ostatecznie pozwala zbudować wykres wizualny. Ponieważ obie zmienne muszą być nieujemne, rysowany jest tylko I-ty kwadrant.
Rys. 2. Osie grafiki programowania liniowego
Rozważmy na przykład pierwsze ograniczenie: 3 * x1 + 10 * x2 ≤ 330. Ta nierówność opisuje region leżący poniżej linii prostej: 3 * x1 + 10 * x2 = 330. Ta linia prosta przecina oś x1 dla x2 = 0, to znaczy równanie wygląda tak: 3 * x1 + 10 * 0 = 330, a jego rozwiązanie: x1 = 330/3 = 110
Podobnie obliczamy punkty przecięcia z osiami x1 i x2 dla wszystkich warunków:
Zakres dopuszczalnych wartości Granica dopuszczalnych wartości Przecięcie z osią x1 Przecięcie z osią x2 3 * x1 + 10 * x2 ≤ 330 3 * x1 + 10 * x2 = 330 x1 = 110; x2 = 0 x1 = 0; x2 = 33 16 * x1 + 4 * x2 ≤ 400 16 * x1 + 4 * x2 = 400 x1 = 25; x2 = 0 x1 = 0; x2 = 100 6 * x1 + 6 * x2 ≤ 240 6 * x1 + 6 * x2 = 240 x1 = 40; x2 = 0 x1 = 0; x2 = 40 x2 ≥ 12 x2 = 12 nie przecina się; biegnie równolegle do osi x1 x1 = 0; x2 = 12
Graficznie pierwsze ograniczenie przedstawiono na rys. 3
Rys. 3. Skonstruowanie domeny możliwych rozwiązań dla pierwszego ograniczenia
Każdy punkt w wybranym trójkącie lub na jego granicach spełni to ograniczenie. Takie punkty nazywane są dopuszczalnymi, a punkty poza trójkątem nazywane są nieważnymi.
Podobnie przedstawiamy na wykresie pozostałe ograniczenia (rys. 4). Wartości x1 i x2 na lub w zakreskowanym obszarze ABCDE będą zgodne ze wszystkimi ograniczeniami modelu. Obszar ten nazywany jest domeną możliwych rozwiązań.
Rys. 4. Zakres możliwych rozwiązań dla modelu jako całości
Teraz, w dziedzinie możliwych rozwiązań, konieczne jest określenie wartości x1 i x2, które maksymalizują Z. Aby to zrobić, w równaniu funkcji celu:
Z = 2500 * x1 + 3500 * x2
podzielić (lub pomnożyć) współczynniki przed x1 i x2 przez tę samą liczbę, tak aby uzyskane wartości spadły do zakresu odzwierciedlonego na wykresie; w naszym przypadku zakres ten wynosi od 0 do 120; dlatego współczynniki można podzielić przez 100 (lub 50):
Z = 25x1 + 35x2
następnie przypisujemy wartość Z równą iloczynowi współczynników przed x1 i x2 (25 * 35 = 875):
875 = 25x1 + 35x2
i wreszcie znajdujemy punkty przecięcia linii z osiami x1 i x2:
Równanie funkcji celu Przecięcie z przecięciem osi x1 z osią x2 875 = 25x1 + 35x2 x1 = 35; x2 = 0 x1 = 0; x2 = 25
Zastosuj to równanie celu do wykresu w taki sam sposób jak ograniczenia (rys. 5):
Rys. 5. Zastosowanie funkcji celu (czarna linia przerywana) do regionu możliwych rozwiązań.
Wartość Z jest stała w całej docelowej linii funkcyjnej. Aby znaleźć wartości x1 i x2, które maksymalizują Z, musisz równolegle przenieść linię funkcji celu do takiego punktu w granicach regionu możliwych rozwiązań, który znajduje się w maksymalnej odległości od pierwotnej linii funkcji celu w górę iw prawo, to jest do punktu C (rys. 6) .
Rys. 6. Linia funkcji celu osiągnęła maksimum w zakresie możliwych rozwiązań (w punkcie C)
Można stwierdzić, że optymalne rozwiązanie będzie w jednym z ekstremalnych punktów obszaru decyzyjnego. W którym zależeć będzie od kąta funkcji celu i od tego, który problem rozwiązujemy: maksymalizować lub minimalizować. W związku z tym nie jest konieczne rysowanie funkcji celu - wystarczy określić wartości x1 i x2 w każdym z ekstremalnych punktów, odczytując z diagramu lub rozwiązując odpowiednią parę równań. Uzyskane wartości x1 i x2 są następnie zastępowane w funkcji celu w celu obliczenia odpowiedniej wartości Z. Optymalnym rozwiązaniem jest to, w którym maksymalna wartość Z jest uzyskiwana przy rozwiązywaniu problemu maksymalizacji, a minimalna przy rozwiązywaniu problemu minimalizacji.
Definiujemy, na przykład, wartości x1 i x2 w punkcie C. Zauważ, że punkt C znajduje się na przecięciu linii: 3x1 + 10x2 = 330 i 6x1 + 6x2 = 240. Rozwiązanie tego układu równań daje: x1 = 10, x2 = 30. Wyniki obliczeń dla wszystkie wierzchołki regionu dopuszczalnych rozwiązań podano w tabeli:
Punkt Wartość x1 Wartość x2 Z = 2500x1 + 3500x2 A 22 12 97 000 V 20 20 120 000 C 10 30 130 000 D 0 33 115 500 E 0 12 42 000
Tak więc Nikołaj Kuznets musi zaplanować na następny miesiąc produkcję 10 produktów A i 30 produktów B, co pozwoli mu uzyskać marżę zysku w wysokości 130 tysięcy rubli.
W skrócie, istotę graficznej metody rozwiązywania problemów programowania liniowego można podsumować następująco:
- Narysuj na wykresie dwie osie reprezentujące dwa parametry rozwiązania; narysuj tylko i-ty kwadrant.
- Wyznacz współrzędne punktów przecięcia wszystkich warunków brzegowych z osiami, zastępując na przemian wartości x1 = 0 i x2 = 0 równaniami warunków brzegowych.
- Umieść linie ograniczeń modelu na wykresie.
- Określ obszar na wykresie (zwany ważnym obszarem decyzyjnym), który spełnia wszystkie ograniczenia. Jeśli nie ma takiego obszaru, model nie ma rozwiązania.
- Określ wartości pożądanych zmiennych w skrajnych punktach obszaru decyzyjnego, aw każdym przypadku oblicz odpowiednią wartość zmiennej docelowej Z.
- W przypadku problemów z maksymalizacją rozwiązaniem jest punkt, w którym Z jest maksymalne, w przypadku problemów z minimalizacją rozwiązaniem jest punkt, w którym Z jest minimalny.
[1] Niniejsza notatka jest oparta na materiałach. CIMA .
[2] Zobacz na przykład tutaj .
