Solver Programowania Liniowego

Rozwiąż zadania programowania liniowego metodą sympleks. Obsługuje maksymalizację lub minimalizację celu, mieszane ograniczenia i do ośmiu zmiennych decyzyjnych, a dla dwóch zmiennych rysuje obszar dopuszczalny z zaznaczonym optimum.

BezpłatneBez rejestracjiNatychmiastowe wyniki

Solver Programowania LiniowegoWypróbuj teraz — za darmo ▼

Embed Solver Programowania Liniowego Widget

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:

Maksymalizuj (lub minimalizuj): Z = c₁ x₁ + c₂ x₂ + … + c_n x_n przy ograniczeniach: a₁₁ x₁ + … + a_1n x_n (≤, ≥, lub =) b₁ a₂₁ x₁ + … + a_2n x_n (≤, ≥, lub =) b₂ … a_m1 x₁ + … + a_mn x_n (≤, ≥, lub =) b_m x₁, x₂, …, x_n ≥ 0

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:

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ą.
Tablica początkowa: baza składa się ze zmiennych swobodnych i sztucznych, co daje oczywisty wierzchołek startowy.
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.
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.
Obrót (piwot): użycie eliminacji Gaussa, aby kolumna wchodząca stała się wektorem jednostkowym z jedynką w wierszu wychodzącym.
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.

Maximize 3x + 5y x + y <= 10 2x + y <= 16 x + 3y <= 18 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:

Maximize Z = 3x + 5y x + y <= 10 (drewno) 2x + y <= 16 (praca) x + 3y <= 18 (lakier) x, y >= 0

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

Wierzchołek (x, y)	Z = 3x + 5y	Dopuszczalny?
(0, 0)	0	Tak
(8, 0)	24	Tak
(6, 4)	38 ← optimum	Tak
(0, 6)	30	Tak

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

Sytuacja	Objaw	Jak naprawić
Nieograniczony problem LP	Solver zgłasza "Nieograniczony"	Dodaj brakujące ograniczenie górne. Funkcja celu może rosnąć bez końca, ponieważ obszar dopuszczalny jest otwarty w kierunku poprawy.
Sprzeczny problem LP	Solver zgłasza "Sprzeczny"	Ograniczenia wykluczają się wzajemnie (np. `x >= 10` i `x <= 5`). Przejrzyj wszystkie pary warunków.
Alternatywne optima	Odznaka ostrzegawcza; wierzchołek optymalny jest unikalny, ale Z jest osiągane wzdłuż krawędzi	Dzieje się tak, gdy wektor funkcji celu jest równoległy do aktywnej krawędzi. Dowolna kombinacja wypukła dwóch wierzchołków na tej krawędzi również jest optymalna.
Degeneracja / cykle	Simpleks wykonuje iteracje bez poprawy Z	Rzadkie w problemach akademickich; można rozwiązać regułą Blanda. Ten solver ogranicza liczbę iteracji, aby uniknąć pętli nieskończonych.

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

Wpisz swój problem LP w polu tekstowym. Pierwsza linia musi zaczynać się od Maximize lub Minimize. Każda kolejna linia to jedno ograniczenie.
Użyj skrótu x, y >= 0, aby zadeklarować nieujemność dla wszystkich wymienionych zmiennych jednocześnie.
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.
Najedź na wierzchołek na wykresie, aby zobaczyć jego współrzędne i wartość Z. Optimum jest oznaczone gwiazdką.
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

Cytuj ten materiał, stronę lub narzędzie w następujący sposób:

"Solver Programowania Liniowego" na https://MiniWebtool.com/pl/solver-programowania-liniowego/ z MiniWebtool, https://MiniWebtool.com/

przez zespół miniwebtool. Aktualizacja: 21 kwietnia 2026

Dostępne API dla deweloperów: Uruchom to narzędzie z aplikacji, automatyzacji lub agenta za pomocą jednego żądania HTTP JSON. Zobacz dokumentację API

Możesz także wypróbować nasz AI Rozwiązywacz Matematyczny GPT, aby rozwiązywać swoje problemy matematyczne poprzez pytania i odpowiedzi w języku naturalnym.