Programowanie liniowe to nie tylko abstrakcyjna matematyka. Jest motorem logistyki, łańcucha dostaw i zarządzania zasobami. Opiera się na metodzie simplex. Ta standardowa metoda znajduje najlepszy możliwy wynik w systemie określonym przez ograniczenia i funkcję celu.
Wyobraź sobie to w ten sposób. Masz cel. Na przykład maksymalizacja zysków lub minimalizacja kosztów. Ty też masz ograniczenia. Godziny pracy sprzętu. Surowce. Praca. Metoda simpleks przechodzi przez te ograniczenia, aby znaleźć maksymalną wydajność. Nie domyśla się. Oblicza.
Dlaczego potrzebujemy systematycznego podejścia
Być może myślisz, że możesz po prostu wykreślić dwie zmienne i zobaczyć, gdzie się przecinają. Działa to w przypadku prostych zadań. Fabryka produkuje dwa produkty. Rysujesz linie. Znajdujesz kąt, pod którym zysk jest maksymalny. To jest jasne. To intuicyjne.
Ale rzeczywistość rzadko jest dwuwymiarowa. Problemy występujące w świecie rzeczywistym obejmują setki równań i tysiące zmiennych. Liczba potencjalnych rozwiązań staje się astronomiczna. Nie da się wykreślić wykresu dla tysięcy zmiennych. Potrzebne byłyby pomiary, których nie jesteś w stanie dostrzec.
George Dantzig rozwiązał ten problem w 1947 roku. Pracował jako konsultant matematyczny dla Sił Powietrznych USA. Wojsko miało ogromne problemy logistyczne. Musieli zoptymalizować trasy dostaw i alokację zasobów. Danzig opracował metodę simpleksową w celu odcięcia nadmiaru.
Metoda ogranicza liczbę punktów ekstremalnych wymagających sprawdzenia. Zamienia niemożliwe zadanie w wykonalne. Do dziś pozostaje standardowym algorytmem w komputerach. Jedno z najbardziej przydatnych narzędzi, jakie kiedykolwiek wynaleziono.
Jak krok po kroku działa metoda simplex
Proces jest systematyczny. Przechodzi od jednej opcji do drugiej. Oto jak to działa w praktyce.
Po pierwsze, zakłada się, że masz punkt wyjścia. Skrajny punkt. Jeśli go nie masz, opcja o nazwie Etap I znajduje prawidłowy punkt wyjścia lub określa, że nie istnieje żadne rozwiązanie.
Następnie metoda sprawdza ten punkt. Czy jest to optymalne? Sprawdzenie to przeprowadza specyfikacja problemu algebraicznego. Jeżeli test zakończy się niepowodzeniem, algorytm przechodzi do sąsiedniego skrajnego punktu. Porusza się wzdłuż krawędzi. Wybiera kierunek, w którym funkcja celu rośnie najszybciej.
Czasami funkcja rośnie w nieskończoność. Procedura zatrzymuje się i wyznacza krawędź, przy której wartość zbliża się do dodatniej nieskończoności. Znalazłeś nieograniczone rozwiązanie.
Jeśli tak się nie stanie, osiągniesz nowy ekstremalny punkt. Wartość ta jest co najmniej tak wysoka, jak poprzednia. Sekwencja się powtarza. Trwa to aż do znalezienia optymalnego punktu lub ujawnienia nieskończoności.
Teoretycznie liczba kroków może rosnąć wykładniczo wraz z liczbą skrajnych punktów. W praktyce zbieżność następuje szybko. Zwykle wymagana jest tylko niewielka wielokrotność skrajnych punktów.
Studium przypadku: maksymalizacja zysków fabryki
Spójrzmy na konkretny przypadek. Fabryka produkuje dwa produkty. Nazwijmy je x1 i x2. Zysk z drugiego rodzaju jest dwukrotnie większy niż z pierwszego. Całkowity zysk przedstawia równanie:
x1 + 2×2
To jest twoja funkcja celu. Chcesz to zmaksymalizować.
Naturalnie chciałbyś wyprodukować tylko x2. Zarabia więcej na jednostkę. Ale są ograniczenia. Nie można produkować w nieskończoność.
Oto rzeczywiste ograniczenia:
- Surowce dla x2 ograniczają produkcję do pięciu jednostek na partię (x2 ≤ 5).
- Surowce dla x1 ograniczają produkcję do ośmiu sztuk na partię (x1 ≤ 8).
- Czas pracy maszyn pozwala na wyprodukowanie łącznie maksymalnie dziesięciu sztuk (x1 + x2 ≤ 10).
- Nie można przedstawić ilości ujemnych (x1 ≥ 0 i x2 ≥ 0).
Metoda simplex znajduje wartości x1 i x2, które maksymalizują zysk w tych granicach. Każde rozwiązanie to para liczb (x1, x2). Na przykład utworzenie trzech jednostek x1 i sześciu jednostek x2 jest prawidłowym punktem (3, 6).
Po naniesieniu na wykres ograniczenia te tworzą obszar wielokątny. Jest to zbiór możliwych rozwiązań. Punkty spoza tego obszaru naruszają jedno lub więcej ograniczeń.
Aby zobaczyć, jak metoda simpleks wyznacza optymalny wierzchołek, rozważ funkcję celu x1 + 2×2 = k. Jeśli ustawisz k na 4, otrzymasz linię na wykresie. Gdy k wzrasta, otrzymujesz linie równoległe. Największą wartością k, która nadal mieści się w obszarze rozwiązań dopuszczalnych, jest maksymalny możliwy zysk.
W tym przykładzie linia dla k = 15 dotyka obszaru w punkcie (5, 5). Jeśli k jest większe, linia znajduje się poza dozwolonym zbiorem. Optymalnym rozwiązaniem jest wyprodukowanie równych ilości każdego dobra.
Dlaczego wierzchołki są ważne w programowaniu liniowym
Wynik nie jest dziełem przypadku. W problemach liniowych optymalne rozwiązanie zawsze osiąga się w wierzchołku. W skrajnym punkcie.
Jest to podstawowa właściwość programowania liniowego. Funkcja jest liniowa. Ograniczenia są liniowe. Kształt jest wypukłym wielokątem (lub wielościanem w większych wymiarach). Szczyt funkcji liniowej na zbiorze wypukłym znajduje się zawsze w narożniku.
Nie musisz sprawdzać każdego punktu w przestrzeni możliwych rozwiązań. Musisz tylko sprawdzić wierzchołki. Metoda simplex właśnie to robi. Skacze ze szczytu na szczyt. Wspina się po powierzchni obszaru możliwych rozwiązań. Zatrzymuje się, gdy nie może wznieść się wyżej.
Czasami optymalne nie jest jedyne. Wszystkie krawędzie mogą dawać tę samą wartość maksymalną. Ale metoda simplex nadal znajdzie jeden z tych optymalnych punktów. Daje konkretną odpowiedź. Dane, które można wykorzystać.
Dla studentów i profesjonalistów zrozumienie tego mechanizmu jest kluczowe. Nie chodzi tylko o rozwiązywanie równań. Chodzi o wiedzę, jak poruszać się po złożonych systemach przy ograniczonych zasobach. Metoda simplex zapewnia ścieżkę.
Metoda simplex nie tylko zgaduje odpowiedzi. Porusza się wzdłuż krawędzi obszaru możliwych rozwiązań, sprawdzając wierzchołki, aż znajdzie najlepsze. Po pierwsze, upraszcza matematyczne sformułowanie problemu. Bierzesz te kłopotliwe nierówności liniowe i zamieniasz je w zgrabne równości. W tym celu wprowadza się „zmienne luzu” (zmienne odchylenia).
Pomyśl o luzie jako o pozostałej mocy. Jeśli masz ograniczenie w postaci $x_1 \le 8$, dodajesz zmienną $x_3$ tak, że $x_1 + x_3 = 8$. I pamiętaj, że $x_3$ musi być większe lub równe zero. Robisz to dla każdego ograniczenia.
- $x_1 + x_3 = 8 $ (przy $x_3 \ge 0$)
- $x_2 + x_4 = 5 $ (przy $x_4 \ge 0$)
- $x_1 + x_2 + x_5 = 10 $ (przy $x_5 \ge 0 $)
Potrzebujesz także zmiennej dla samej funkcji docelowej. Nazwijmy to $x_0$. Jeśli Twoim celem jest maksymalizacja $x_0 = x_1 + 2x_2$, przepisz to jako $x_1 + 2x_2 – x_0 = 0$.
Teraz zadanie stało się łatwiejsze. Znajdź wartości nieujemne dla $x_1$ do $x_5$. Zwiększ kwotę $x_0$ tak dużą, jak to możliwe.
Pochodzenie w miejscu pochodzenia
Gdzie zacząć? Najprostszym punktem jest pochodzenie. Ustaw wszystkie zmienne decyzyjne na zero. $x_1 = 0 $. $x_2 = 0 $.
To jest prawidłowe rozwiązanie. To jest skrajny punkt. W rzeczywistości jest to szczyt początkowy. Wartość funkcji celu $x_0$ również wynosi zero. Niezbyt dobrze, ale jest to działanie zgodne z prawem.
Czy możemy zrobić lepiej? Tak. Jeśli zwiększysz jedną ze zmiennych od zera, pozostawiając drugą równą zero, wartość $x_0$ wzrośnie. Pytanie brzmi, która zmienna zapewni Ci największy zwrot z każdej wydanej złotówki.
Spójrz na równanie funkcji celu: $x_1 + 2x_2 – x_0 = 0$. Wyrażając $x_0$, otrzymujemy $x_0 = x_1 + 2x_2$.
Zwiększenie $x_1$ dodaje 1 do całkowitej wartości. Zwiększenie $x_2$ dodaje 2. $x_2$ jest wyraźnym zwycięzcą. Daje największy wzrost $x_0$ na zmianę jednostkową. Wybierasz więc $x_2$ i zwiększasz.
Napotkanie pierwszego ograniczenia
Nie możesz zwiększać $x_2$ w nieskończoność. Zmienne muszą pozostać nieujemne. Jeśli zwiększysz $x_2$ powyżej 5, coś pójdzie nie tak. W szczególności spójrz na drugie ograniczenie: $x_2 + x_4 = 5 $.
Jeśli $x_2 = 6$, wówczas $x_4$ stanie się -1. Jest to zabronione. Wymóg nieujemności działa jak twarde ograniczenie. Limit wynosi 5.
Więc ustawiasz $x_2 = 5$. Jak wygląda teraz rozwiązanie?
- $x_2 = 5 $
- $x_1 = 0 $ (wciąż zero)
- $x_4 = 0$ (ta zmienna osiągnęła swój limit, więc teraz wynosi zero)
- $x_3 = 8 $ (ponieważ 0 $ + 8 = 8 $)
*$
