Programowanie liniowe — metoda simpleks i rozwiązanie graficzne

Programowanie liniowe to metoda znajdowania najlepszej wartości liniowej funkcji celu, takiej jak maksymalny zysk lub minimalny koszt, przy liniowych ograniczeniach. W zadaniu z dwiema zmiennymi rozwiązanie graficzne polega na wyznaczeniu obszaru dopuszczalnego i sprawdzeniu jego punktów wierzchołkowych. W większych problemach metoda simpleks wykorzystuje tę samą ideę punktów wierzchołkowych w sposób algebraiczny.

Programowanie liniowe stosuj tylko wtedy, gdy funkcja celu i ograniczenia są liniowe. Jeśli zależność się wygina, jest krzywoliniowa albo zależy od iloczynów takich jak $xy$, to model nie jest zadaniem programowania liniowego.

Definicja programowania liniowego

$$\text{maximize or minimize } z = c_1x_1 + c_2x_2 + \cdots + c_nx_n$$

przy ograniczeniach takich jak

$$a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \le b_1$$

oraz podobnych nierównościach liniowych, razem z warunkami typu $x_i \ge 0$, gdy wartości ujemne nie mają sensu.

Zbiór wszystkich punktów spełniających każde ograniczenie nazywa się obszarem dopuszczalnym. Programowanie liniowe pyta: który z tych dopuszczalnych punktów daje najlepszą wartość funkcji celu?

Jak działa metoda graficzna

Jeśli są tylko dwie zmienne decyzyjne, możesz narysować każde ograniczenie na płaszczyźnie $xy$. Część wspólna wszystkich dozwolonych obszarów to obszar dopuszczalny.

Każdy punkt w tym obszarze jest poprawnym rozwiązaniem. Funkcja celu przypisuje każdemu z nich pewną wartość.

W programowaniu liniowym kluczowy jest następujący fakt: jeśli istnieje rozwiązanie optymalne, to co najmniej jedno rozwiązanie optymalne występuje w punkcie wierzchołkowym obszaru dopuszczalnego. Dlatego metoda graficzna skupia się na wierzchołkach zamiast sprawdzać każdy punkt w zacieniowanym obszarze.

Przykład rozwiązany: rozwiąż zadanie programowania liniowego graficznie

Załóżmy, że zakład wytwarza dwa produkty, $A$ i $B$.

• Zysk z jednej jednostki $A$: $3$
• Zysk z jednej jednostki $B$: $5$
• Ograniczenie czasu pracy maszyny: każda jednostka $A$ zużywa $1$ godzinę, każda jednostka $B$ zużywa $2$ godziny, a dostępnych jest najwyżej $8$ godzin
• Ograniczenie montażu: każda jednostka $A$ zużywa $1$ godzinę, każda jednostka $B$ zużywa $1$ godzinę, a dostępnych jest najwyżej $5$ godzin

Niech $x$ oznacza liczbę jednostek $A$, a $y$ liczbę jednostek $B$.

Maksymalizuj

$$P = 3x + 5y$$

przy warunkach

$$x + 2y \le 8$$ $$x + y \le 5$$ $$x \ge 0,\quad y \ge 0$$

Wyznacz punkty wierzchołkowe

Z osi i prostych wyznaczonych przez ograniczenia wynika, że dopuszczalne punkty wierzchołkowe to

• $(0,0)$
• $(5,0)$
• $(0,4)$
• $(2,3)$

Punkt $(2,3)$ otrzymujemy, rozwiązując równania brzegowe

$$x + 2y = 8,\quad x + y = 5$$

Po odjęciu dostajemy $y = 3$, a następnie $x = 2$.

Sprawdź funkcję celu w każdym wierzchołku

Oblicz zysk w każdym punkcie wierzchołkowym:

• W $(0,0)$, $P = 0$
• W $(5,0)$, $P = 15$
• W $(0,4)$, $P = 20$
• W $(2,3)$, $P = 21$

Zatem maksymalny zysk wynosi

$$P = 21$$

dla

$$(x,y) = (2,3)$$

To właśnie metoda graficzna w jednym zdaniu: narysuj obszar dopuszczalny, znajdź punkty wierzchołkowe i oblicz w nich wartość funkcji celu.

Intuicja metody simpleks

Metoda graficzna jest praktyczna tylko wtedy, gdy są dwie zmienne, a czasem trzy, jeśli chcesz wyobrażać sobie obszar w 3D. Rzeczywiste problemy optymalizacyjne często mają wiele zmiennych, więc rysowanie obszaru dopuszczalnego przestaje być realistyczne.

Metoda simpleks zachowuje tę samą logikę punktów wierzchołkowych, ale realizuje ją algebraicznie. Ogólnie rzecz biorąc, przechodzi od jednego dopuszczalnego punktu wierzchołkowego do kolejnego, który poprawia wartość funkcji celu, i zatrzymuje się wtedy, gdy żaden sąsiedni ruch nie daje lepszej wartości.

Dobry model myślowy jest więc taki:

• Metoda graficzna: widzisz punkty wierzchołkowe
• Metoda simpleks: poruszasz się po punktach wierzchołkowych bez ich rysowania

Ten opis daje intuicję, a nie pełny algorytm. Właściwa procedura simpleks używa tablicy simpleksowej albo równoważnej postaci algebraicznej, aby zdecydować, która zmienna wchodzi i która wychodzi na każdym kroku.

Dlaczego punkty wierzchołkowe są ważne

Liniowe funkcje celu tworzą linie poziomu, takie jak

$$3x + 5y = k$$

dla różnych wartości $k$. Gdy przesuwasz tę prostą w kierunku większego zysku, ostatni punkt, w którym nadal styka się ona z obszarem dopuszczalnym, to miejsce, w którym występuje maksimum.

Na wielu rysunkach ten ostatni punkt styku przypada na pojedynczy wierzchołek. Jeśli prosta funkcji celu jest równoległa do krawędzi brzegu, wiele punktów na tej krawędzi może być jednocześnie optymalnych. W takim przypadku nadal istnieje co najmniej jeden optymalny punkt wierzchołkowy.

Typowe błędy

Mylenie rozwiązania dopuszczalnego z optymalnym

Punkt może spełniać wszystkie ograniczenia, a mimo to nie maksymalizować ani nie minimalizować funkcji celu. Dopuszczalny znaczy tylko tyle, że jest dozwolony.

Pomijanie warunków nieujemności

Jeśli $x$ i $y$ oznaczają ilości, które produkujesz albo wysyłasz, wartości ujemne zwykle nie mają sensu. Pominięcie warunku $x \ge 0$ lub $y \ge 0$ może zmienić całe zadanie.

Założenie, że każda odpowiedź musi być liczbą całkowitą

Zwykłe programowanie liniowe dopuszcza wartości ułamkowe. Jeśli zmienne muszą być liczbami całkowitymi, na przykład liczba ciężarówek albo liczba pracowników, potrzebujesz modelu programowania całkowitoliczbowego albo dodatkowego warunku całkowitości.

Założenie, że każde zadanie ma najlepsze rozwiązanie

Niektóre zadania programowania liniowego są niewykonalne, co oznacza, że żaden punkt nie spełnia wszystkich ograniczeń. Inne są nieograniczone, co oznacza, że wartość funkcji celu może poprawiać się bez ograniczeń. Skończone optimum istnieje tylko wtedy, gdy ograniczenia rzeczywiście wystarczająco zawężają problem.

Używanie metody graficznej przy zbyt wielu zmiennych

Gdy zmiennych jest dużo, rysowanie przestaje być właściwym narzędziem. Wtedy konieczna staje się metoda simpleks albo inne metody optymalizacji.

Kiedy stosuje się programowanie liniowe

Programowanie liniowe stosuje się wtedy, gdy decyzje konkurują o ograniczone zasoby, a zarówno cel, jak i ograniczenia można opisać liniowo. Typowe przykłady to planowanie produkcji, transport, obsada pracowników, mieszanie składników, harmonogramowanie i podział budżetu.

Model jest tylko tak dobry, jak jego założenia. Jeśli rzeczywista zależność nie jest w przybliżeniu liniowa albo jeśli zmienne muszą być całkowite, zwykły model programowania liniowego może być jedynie punktem wyjścia.

Spróbuj podobnego zadania

Weź krótkie zadanie tekstowe z dwoma produktami, dwoma ograniczeniami zasobów i funkcją zysku. Zapisz zmienne, narysuj ograniczenia i samodzielnie sprawdź punkty wierzchołkowe. Gdy zrozumiesz tę ideę, metoda simpleks stanie się dużo łatwiejsza, bo po prostu rozszerza tę samą logikę na wyższe wymiary.