Solver Programowania Liniowego

O Solver Programowania Liniowego

Solver Programowania Liniowego to kalkulator online, który znajduje maksimum lub minimum liniowej funkcji celu podlegającej układowi liniowych nierówności lub równań. Wykorzystuje on metodę simpleks (wariant Big-M), dzięki czemu ograniczenia <=, >= oraz = mogą być dowolnie mieszane. W przypadku problemów z 2 zmiennymi narzędzie rysuje interaktywny wykres obszaru dopuszczalnego z wyróżnieniem każdego wierzchołka i punktu optymalnego.

Co to jest programowanie liniowe?

Problem programowania liniowego (LP) stawia pytanie:

Zbiór punktów spełniających każde ograniczenie nazywany jest obszarem dopuszczalnym, który jest wielościanem wypukłym. Podstawowe twierdzenie programowania liniowego mówi, że jeśli problem LP posiada skończone optimum, jest ono osiągane w wierzchołku (punkcie ekstremalnym) tego wielościanu. Dlatego metoda simpleks — która przemieszcza się od wierzchołka do wierzchołka — jest tak skuteczna.

Jak działa metoda simpleks

Zaczynając od wierzchołka dopuszczalnego, metoda simpleks wielokrotnie poprawia wartość funkcji celu, przechodząc do sąsiedniego wierzchołka o lepszej wartości. Mechanika procesu:

1. Postać standardowa: przekształcenie problemu do postaci max c^Tx przy Ax = b, x ≥ 0. Dla ograniczeń <= dodaje się zmienne swobodne (slack); dla >= odejmuje się nadwyżkę (surplus) i dodaje zmienną sztuczną z dużą karą −M; dla równości dodaje się zmienną sztuczną.
2. Tablica początkowa: baza składa się ze zmiennych swobodnych i sztucznych, co daje oczywisty wierzchołek startowy.
3. Zmienna wchodząca: wybór zmiennej niebazowej o największym dodatnim koszcie zredukowanym \( c_j - z_j \). Jeśli taka zmienna nie istnieje, bieżące rozwiązanie jest optymalne.
4. Zmienna wychodząca: dla kolumny wchodzącej wykonuje się test ilorazów — dzieli się RHS każdego wiersza przez jego dodatni element w kolumnie wchodzącej i wybiera wiersz z najmniejszym ilorazem. Jeśli brak dodatnich elementów, problem LP jest nieograniczony.
5. Obrót (piwot): użycie eliminacji Gaussa, aby kolumna wchodząca stała się wektorem jednostkowym z jedynką w wierszu wychodzącym.
6. Powtarzanie do momentu spełnienia kryterium stopu.

Jeśli po zakończeniu jakakolwiek zmienna sztuczna pozostaje w bazie z wartością dodatnią, pierwotny problem LP jest sprzeczny.

Metoda graficzna (dla 2 zmiennych)

Dla problemów z dwiema zmiennymi obszar dopuszczalny jest dwuwymiarowym wielokątem wypukłym. Ponieważ optimum zawsze znajduje się w wierzchołku, wyliczenie wszystkich wierzchołków i sprawdzenie w nich wartości funkcji celu wystarczy do rozwiązania problemu. Ten kalkulator dokonuje wyliczenia poprzez przecinanie każdej pary granic ograniczeń, zachowując tylko te punkty, które spełniają pozostałe warunki, i sortując je przeciwnie do ruchu wskazówek zegara na potrzeby wizualizacji.

Składnia wprowadzania danych

Wpisz funkcję celu w pierwszej linii, a następnie jedno ograniczenie na linię. Nazwy zmiennych mogą być dowolnymi identyfikatorami (x, y, x1, zysk…). Operatorzy to <=, >= oraz =. Warunek nieujemności można zapisać skrótem x, y >= 0.

Puste linie i komentarze zaczynające się od # są ignorowane. Solver akceptuje do 8 zmiennych decyzyjnych i 20 ograniczeń.

Przykład z rozwiązaniem

Rozważmy warsztat meblowy produkujący stoły i krzesła. Każdy stół daje 3 \$ zysku i wymaga 1 jednostki drewna oraz 2 jednostek pracy. Każde krzesło daje 5 \$ zysku i wymaga 1 jednostki drewna, 1 jednostki pracy i 3 jednostek lakieru. Dostępne zasoby: 10 drewna, 16 pracy, 18 lakieru. Przyjmując x = stoły i y = krzesła, problem LP to:

Obszar dopuszczalny jest pięciokątem. Obliczając Z w każdym wierzchołku:

Zatem warsztat powinien wyprodukować 6 stołów i 4 krzesła, aby osiągnąć maksymalny zysk wynoszący 38 $. Ograniczenia dotyczące drewna i pracy są aktywne (w optimum są równe dostępnym zasobom); lakier ma luz wynoszący 0 (również aktywny w tym przypadku), co oznacza wyczerpanie wszystkich trzech zasobów.

Typowe problemy i co wykrywa solver

Zastosowania

• Mieszanka produktów i planowanie produkcji — ile produktów każdego rodzaju wytworzyć, aby zmaksymalizować zysk przy ograniczonych zasobach.
• Problemy dietetyczne i mieszania — minimalizacja kosztu diety lub paszy przy zachowaniu minimalnych wartości odżywczych.
• Transport i przydział — minimalizacja kosztów wysyłki przy zrównoważeniu podaży i popytu.
• Optymalizacja portfela — maksymalizacja oczekiwanego zwrotu przy ograniczeniach ryzyka (zlinearyzowanych).
• Przepływy w sieciach — problemy maksymalnego przepływu i przepływu o minimalnym koszcie sprowadzają się do problemów LP.
• Harmonogramowanie — układanie grafików pracy z uwzględnieniem zapotrzebowania na zmiany i limitów godzinowych.

Jak korzystać z tego kalkulatora

1. Wpisz swój problem LP w polu tekstowym. Pierwsza linia musi zaczynać się od Maximize lub Minimize. Każda kolejna linia to jedno ograniczenie.
2. Użyj skrótu x, y >= 0, aby zadeklarować nieujemność dla wszystkich wymienionych zmiennych jednocześnie.
3. Kliknij Rozwiąż problem LP. Solver poda optymalną wartość Z, optymalne wartości każdej zmiennej decyzyjnej, listę aktywnych ograniczeń, a dla problemów z 2 zmiennymi wyświetli interaktywny wykres obszaru dopuszczalnego.
4. Najedź na wierzchołek na wykresie, aby zobaczyć jego współrzędne i wartość Z. Optimum jest oznaczone gwiazdką.
5. Przejrzyj tablice simpleksowe, aby zobaczyć każdy krok (obrót) i prześledzić, jak metoda poprawia wartość Z. Kolumna wchodząca jest podświetlona na bursztynowo, a wiersz wychodzący na czerwono.

Najczęściej zadawane pytania

Co to jest problem programowania liniowego?

Problem programowania liniowego (LP) polega na znalezieniu maksimum lub minimum liniowej funkcji celu na zbiorze zmiennych decyzyjnych spełniających układ liniowych nierówności lub równań. Zbiór dopuszczalny to wielościan wypukłym, a optimum zawsze znajduje się w jednym z jego wierzchołków — to kluczowy fakt wykorzystywany przez metodę simpleks.

Jak działa metoda simpleks?

Metoda simpleks przemieszcza się po wierzchołkach wielościanu dopuszczalnego. Każdy krok ("piwot") wymienia zmienną w bazie na inną, przechodząc do sąsiedniego wierzchołka o ściśle lepszej wartości funkcji celu. Algorytm kończy pracę, gdy żaden piwot nie może poprawić Z — bieżący wierzchołek jest wtedy optymalny. To narzędzie używa wariantu Big-M do obsługi ograniczeń <=, >= oraz =.

Co to jest obszar dopuszczalny?

Obszar dopuszczalny to zbiór wszystkich wartości zmiennych spełniających jednocześnie każde ograniczenie. Dla 2 zmiennych jest to dwuwymiarowy wielokąt wypukły; dla n zmiennych to n-wymiarowy wielościan. Pusty wielościan oznacza, że problem LP jest sprzeczny; wielościan rozciągający się w nieskończoność w kierunku poprawy oznacza, że problem jest nieograniczony.

Co oznacza "nieograniczony" w programowaniu liniowym?

Problem LP jest nieograniczony, gdy obszar dopuszczalny ciągnie się do nieskończoności w kierunku, w którym funkcja celu stale się poprawia. Na przykład Maximize x przy x ≥ 0 nie ma skończonego maksimum. W rzeczywistych problemach wynik ten zwykle sugeruje brakujące ograniczenie — często limit zasobów lub zmiennej.

Co oznacza "alternatywne optima"?

Alternatywne optima występują, gdy więcej niż jeden punkt osiąga tę samą, najlepszą wartość funkcji celu. Geometrycznie funkcja celu jest równoległa do krawędzi wielokąta, więc każdy punkt na tej krawędzi jest optymalny. Solver sygnalizuje to, gdy jakakolwiek zmienna niebazowa ma zerowy koszt zredukowany w rozwiązaniu końcowym.

Ile zmiennych i ograniczeń akceptuje solver?

Do 8 zmiennych decyzyjnych i 20 ograniczeń. Interaktywny wykres obszaru dopuszczalnego jest generowany tylko dla problemów z 2 zmiennymi; dla 3 i więcej zmiennych nadal otrzymasz pełne rozwiązanie numeryczne, tablice krok po kroku i raport ograniczeń.

Dalsza lektura

• Programowanie liniowe — Wikipedia
• Algorytm simpleks — Wikipedia
• Metoda Big-M — Wikipedia
• Dwoistość w optymalizacji — Wikipedia

Zaawansowane działania matematyczne:

• Kalkulator Antylogarytmów
• Kalkulator funkcji beta
• Kalkulator współczynnika dwumianu
• Kalkulator rozkładu dwumianowego
• Kalkulator Bitowy Polecane
• Kalkulator Twierdzenia Centralnego Granicznego
• Kalkulator kombinacji
• Komplementarny kalkulator funkcji błędu
• Kalkulator liczb zespolonych
• Kalkulator Entropii
• Kalkulator funkcji błędu
• Kalkulator rozkładu wykładniczego
• Kalkulator wzrostu wykładniczego - wysoka precyzja
• Kalkulator całki wykładniczej
• kalkulator-wykładników-wysoka-precyzja
• Kalkulator silni
• Kalkulator Funkcji Gamma
• Kalkulator złotego podziału
• Kalkulator półtrwania
• Kalkulator tempa wzrostu procentowego
• Kalkulator permutacji
• Kalkulator Rozkładu Poissona Polecane
• Kalkulator korzeni wielomianów ze szczegółowymi krokami
• Kalkulator prawdopodobieństwa
• Kalkulator rozkładu prawdopodobieństwa
• Kalkulator Proporcji
• Kalkulator Formuły Kwadratowej
• Kalkulator Naukowy
• Kalkulator notacji naukowej
• Kalkulator Cyfr Znaczących Nowy
• Kalkulator sumy sześcianów
• Kalkulator sumy kolejnych liczb
• Kalkulator sumy kwadratów
• Generator tablicy prawdy
• Kalkulator teorii zbiorów
• Generator Diagramu Venna (3 zbiory)
• Kalkulator chińskiego twierdzenia o resztach
• Kalkulator Funkcji Tocjenta Eulera
• Kalkulator rozszerzonego algorytmu Euklidesa
• Kalkulator modularnej odwrotności multiplikatywnej
• Kalkulator ułamków łańcuchowych
• Kalkulator Najkrótszej Ścieżki Dijkstry
• Kalkulator Minimalnego Drzewa Rozpinającego
• Walidator ciągu stopni grafu
• Kalkulator Nieporządków (Podfaktoriał)
• Kalkulator liczb Stirlinga
• Kalkulator Zasady Szufladkowej
• Kalkulator rozkładu stacjonarnego łańcucha Markowa
• Kalkulator Zaokrąglania Nowy
• Kalkulator Rozkładu Ujemnego Dwumianowego Nowy
• Kalkulator Permutacji z Powtórzeniami Nowy
• Kalkulator Potęgowania Modularnego Nowy
• Kalkulator Pierwiastka Pierwotnego
• Upraszczacz Algebry Boole’a Nowy
• Solver Tablicy Karnaugha (K-Map) Nowy
• Kalkulator Kolorowania Grafów Nowy
• Kalkulator Sortowania Topologicznego Nowy
• Kalkulator Macierzy Sąsiedztwa Nowy
• Kalkulator Włączeń i Wyłączeń Nowy
• Solver Programowania Liniowego Nowy
• Solver Problemu Komiwojażera (TSP) Nowy
• Sprawdzanie Ścieżki Hamiltona Nowy
• Walidator Grafu Planarnego Nowy
• Kalkulator Przepływu w Sieci (Maksymalny Przepływ) Nowy
• Solver Problemu Stabilnych Małżeństw Nowy
• Kalkulator Rzędu w Teorii Grup Nowy
• Kalkulator Pierścieni i Ciał Nowy