Programowanie matematyczne i programowanie liniowe — modele, metody i zastosowania

Mgr inż.

Sebastian Dziarmaga-Działyński

Wirtualna kancelaria korepetytorska i konsultacyjna – wszechwiedza.pl

Programowanie matematyczne to dział optymalizacji, który pomaga podejmować najlepsze decyzje w warunkach ograniczonych zasobów. Programowanie liniowe jest jego klasycznym i bardzo ważnym przypadkiem: opisuje sytuacje, w których funkcja celu oraz warunki ograniczające mają postać liniową. Dzięki takim modelom można planować produkcję, transport, przydziały, wykorzystanie zasobów, strukturę kosztów i wiele innych procesów decyzyjnych.

Spis treści

Czym jest programowanie matematyczne?
Krótka historia programowania liniowego
Czym jest programowanie liniowe?
Podstawowe elementy modelu
Ogólny model programowania liniowego
Założenia programowania liniowego
Rodzaje warunków ograniczających
Zbiór rozwiązań dopuszczalnych i optimum
Postać ogólna, kanoniczna i standardowa
Zapis macierzowy
Metody rozwiązywania programów liniowych
Szczególne modele programowania liniowego
Dualność w programowaniu liniowym
Co znajduje się poza programowaniem liniowym?
Praktyczny schemat budowy modelu
Podsumowanie

Czym jest programowanie matematyczne?

Programowanie matematyczne jest działem matematyki stosowanej i badań operacyjnych, którego celem jest znalezienie najlepszego wariantu decyzji spośród wielu wariantów dopuszczalnych. Słowo „programowanie” nie oznacza tutaj pisania kodu komputerowego. Chodzi o planowanie działań, dobór decyzji i optymalne wykorzystanie dostępnych zasobów.

W typowym problemie decyzyjnym mamy ograniczone zasoby: czas pracy, materiały, budżet, powierzchnię magazynową, liczbę pojazdów, moc produkcyjną albo liczbę dostępnych pracowników. Jednocześnie chcemy osiągnąć określony cel, na przykład:

maksymalizować zysk, przychód lub efektywność,
minimalizować koszt, czas, zużycie paliwa albo emisję,
ograniczać liczbę opóźnień, braków lub niewykorzystanych zasobów,
znaleźć najlepszy podział dostępnych środków między różne działania,
zaplanować produkcję przy ograniczonej dostępności materiałów i maszyn.

Model programowania matematycznego przekłada problem praktyczny na język matematyki. Najpierw określamy decyzje, które należy podjąć. Następnie zapisujemy cel oraz ograniczenia. Na końcu korzystamy z odpowiedniej metody rozwiązania, aby wskazać wariant najlepszy.

Istota optymalizacji

Nie wystarczy wskazać rozwiązanie, które „wydaje się dobre”. Programowanie matematyczne ma prowadzić do rozwiązania najlepszego według przyjętego kryterium, przy jednoczesnym spełnieniu wszystkich warunków ograniczających.

Krótka historia programowania liniowego

Korzenie programowania matematycznego sięgają wcześniejszych badań nad optymalizacją, geometrią wypukłą oraz teorią nierówności. Dynamiczny rozwój programowania liniowego nastąpił jednak w pierwszej połowie XX wieku, zwłaszcza w związku z problemami planowania gospodarczego, logistyki i wykorzystania zasobów.

Ważną postacią był Leonid Kantorowicz, który już pod koniec lat trzydziestych XX wieku analizował problemy racjonalnego wykorzystania zasobów produkcyjnych. Po II wojnie światowej potrzeby planowania transportu, zaopatrzenia, produkcji i działań wojskowych przyczyniły się do intensywnego rozwoju metod optymalizacyjnych.

Kluczowym momentem było opracowanie przez George’a Dantziga metody simpleks w 1947 roku. Metoda ta umożliwiła skuteczne rozwiązywanie dużych modeli liniowych i stała się jednym z fundamentów nowoczesnych badań operacyjnych. Rozwój komputerów sprawił później, że programowanie liniowe przestało być wyłącznie narzędziem teoretycznym i znalazło zastosowanie w przedsiębiorstwach, administracji, logistyce, finansach, energetyce i wielu innych dziedzinach.

Obecnie klasyczne algorytmy programowania liniowego są wbudowane w liczne systemy optymalizacyjne. Użytkownik często nie musi sam wykonywać wszystkich rachunków, ale nadal musi poprawnie sformułować model, zinterpretować wynik i ocenić, czy przyjęte założenia odpowiadają rzeczywistości.

Czym jest programowanie liniowe?

Programowanie liniowe jest szczególnym przypadkiem programowania matematycznego. W modelu liniowym zarówno funkcja celu, jak i warunki ograniczające są funkcjami liniowymi zmiennych decyzyjnych.

Oznacza to, że w modelu nie pojawiają się między innymi iloczyny zmiennych decyzyjnych, ich potęgi większe od pierwszej, pierwiastki, funkcje trygonometryczne ani inne zależności nieliniowe. Dopuszczalne są natomiast stałe współczynniki przy zmiennych oraz sumy i różnice zmiennych.

\[ Z=12x_1+8x_2+15x_3 \]

Powyższa funkcja celu jest liniowa. Zmienna \(x_1\), \(x_2\) albo \(x_3\) występuje tylko w pierwszej potędze, a jej współczynnik jest stały.

\[ Z=12x_1+8x_2^2 \]

Taka funkcja nie jest liniowa, ponieważ występuje w niej kwadrat zmiennej \(x_2\). Podobnie nieliniowy byłby wyraz \(x_1x_2\), ponieważ oznacza iloczyn dwóch zmiennych decyzyjnych.

Modele liniowe są szczególnie ważne, ponieważ mają przejrzystą interpretację ekonomiczną i techniczną, a jednocześnie można je efektywnie rozwiązywać nawet przy bardzo dużej liczbie zmiennych i ograniczeń.

Podstawowe elementy modelu

Każdy model programowania liniowego składa się z kilku podstawowych części. Ich poprawne rozróżnienie jest najważniejszym etapem budowy modelu.

Elementy modelu programowania liniowego
Element	Znaczenie	Przykład interpretacji
Zmienne decyzyjne	Wielkości, których wartości mają zostać wyznaczone.	Liczba wyprodukowanych wyrobów, liczba kursów, ilość surowca przeznaczonego do danego procesu.
Funkcja celu	Wyraża cel decydenta: maksymalizację albo minimalizację określonej wielkości.	Maksymalizacja zysku albo minimalizacja kosztu transportu.
Warunki ograniczające	Opisują zasoby, wymagania, limity oraz zależności między decyzjami.	Zużycie materiału nie może przekroczyć zapasu.
Warunki brzegowe	Określają dopuszczalny zakres wartości zmiennych.	\(x_j\geq0\), \(x_j\leq U_j\), \(x_j\in\mathbb{Z}\).
Parametry modelu	Dane wejściowe, które uznajemy za znane przy budowie modelu.	Cena jednostkowa, dostępny czas pracy, zapas materiału, koszt przewozu.

Zmienne decyzyjne

Zmienne decyzyjne opisują wybory, których wartości nie są znane przed rozwiązaniem modelu. Jeżeli przedsiębiorstwo produkuje dwa wyroby, możemy przyjąć:

\[ x_1=\text{liczba jednostek wyrobu A} \]

\[ x_2=\text{liczba jednostek wyrobu B} \]

Po rozwiązaniu modelu wartości \(x_1\) i \(x_2\) powiedzą, ile jednostek każdego wyrobu należy zaplanować.

Funkcja celu

Funkcja celu opisuje wielkość, którą chcemy maksymalizować albo minimalizować. Jeżeli zysk jednostkowy ze sprzedaży wyrobu A wynosi 30 zł, a wyrobu B wynosi 20 zł, funkcję celu można zapisać następująco:

\[ \max Z=30x_1+20x_2 \]

Model nie mówi jeszcze, jakie wartości powinny przyjąć \(x_1\) i \(x_2\). Określa jedynie, według jakiego kryterium oceniane będą warianty decyzji.

Warunki ograniczające

Warunki ograniczające opisują ograniczenia rzeczywistego problemu. Mogą wynikać z dostępności surowców, czasu pracy, mocy maszyn, zapotrzebowania odbiorców, wymogów technologicznych, limitów budżetowych albo warunków prawnych.

Jeżeli wytworzenie jednostki A wymaga 2 godzin pracy maszyny, a jednostki B wymaga 3 godzin, przy dostępności 120 godzin, otrzymujemy ograniczenie:

\[ 2x_1+3x_2\leq120 \]

Wyrażenie po lewej stronie oznacza całkowite zużycie czasu maszyny. Nie może ono przekroczyć liczby godzin dostępnych po prawej stronie.

Ogólny model programowania liniowego

Ogólny model programowania liniowego można zapisać w postaci maksymalizacyjnej albo minimalizacyjnej.

\[ \max\ \text{lub}\ \min\quad Z=c_1x_1+c_2x_2+\dots+c_nx_n \]

przy warunkach:

\[ a_{i1}x_1+a_{i2}x_2+\dots+a_{in}x_n \begin{cases} \leq\\ =\\ \geq \end{cases} b_i \qquad \text{dla } i=1,2,\dots,m \]

oraz warunkach brzegowych, na przykład:

\[ x_j\geq0 \qquad \text{dla } j=1,2,\dots,n \]

W tym zapisie:

\(x_j\) oznacza \(j\)-tą zmienną decyzyjną,
\(c_j\) oznacza współczynnik funkcji celu przy zmiennej \(x_j\),
\(a_{ij}\) oznacza współczynnik przy zmiennej \(x_j\) w \(i\)-tym ograniczeniu,
\(b_i\) oznacza prawą stronę \(i\)-tego ograniczenia,
\(m\) oznacza liczbę ograniczeń,
\(n\) oznacza liczbę zmiennych decyzyjnych.

Co oznacza współczynnik \(a_{ij}\)?

Współczynnik \(a_{ij}\) pokazuje, w jakim stopniu realizacja jednej jednostki decyzji \(x_j\) wpływa na \(i\)-te ograniczenie. Może oznaczać na przykład zużycie konkretnego materiału, czas pracy maszyny, koszt jednostkowy albo zapotrzebowanie na energię.

Założenia programowania liniowego

Model liniowy jest użyteczny wtedy, gdy przyjęte uproszczenia są rozsądne w odniesieniu do analizowanego problemu. Klasyczne programowanie liniowe opiera się na kilku ważnych założeniach.

Najważniejsze założenia klasycznego programu liniowego
Założenie	Znaczenie praktyczne
Proporcjonalność	Wkład każdej zmiennej do funkcji celu i ograniczeń jest proporcjonalny do jej wartości. Dwukrotnie większa produkcja oznacza dwukrotnie większe zużycie danego zasobu.
Addytywność	Łączny efekt jest sumą efektów poszczególnych decyzji. Nie występują dodatkowe interakcje typu „produkcja A zmienia koszt jednostkowy produkcji B”.
Podzielność	Zmienne mogą przyjmować wartości ułamkowe, chyba że model wyraźnie wymaga wartości całkowitych.
Pewność parametrów	Współczynniki modelu uznaje się za znane i stałe w rozpatrywanym okresie.
Nieujemność	W wielu zastosowaniach wartości zmiennych nie mogą być ujemne, na przykład liczba produktów lub liczba kursów.

Założenia te nie oznaczają, że model zawsze idealnie odwzorowuje rzeczywistość. Model jest celowym uproszczeniem. Jego wartość zależy od tego, czy uproszczenie pozwala podejmować lepsze decyzje niż działanie wyłącznie intuicyjne.

Jeżeli decyzje muszą mieć charakter całkowity, na przykład liczba pojazdów, osób albo maszyn, klasyczne programowanie liniowe należy rozszerzyć o warunki całkowitoliczbowości. Wtedy otrzymujemy model programowania całkowitoliczbowego albo mieszanego.

Rodzaje warunków ograniczających

Warunki ograniczające nie zawsze oznaczają wyłącznie niedobór zasobów. Mogą opisywać również wymagania minimalne, równowagę przepływów, zależności technologiczne i limity poszczególnych decyzji.

Najczęściej spotykane typy ograniczeń
Typ ograniczenia	Postać	Przykładowa interpretacja
Zasobowe	\(2x_1+3x_2\leq120\)	Łączne zużycie czasu maszyny nie może przekroczyć 120 godzin.
Minimalnego wymogu	\(x_1+x_2\geq500\)	Łączna produkcja musi wynieść co najmniej 500 jednostek.
Bilansowe	\(x_1+x_2=x_3\)	Łączny dopływ musi być równy odpływowi albo produkcja musi pokryć zapotrzebowanie.
Górnego limitu	\(x_1\leq80\)	Produkcja wyrobu A nie może przekroczyć zdolności sprzedażowej lub technicznej.
Dolnego limitu	\(x_2\geq20\)	Należy utrzymać minimalny poziom realizacji danego działania.
Proporcji	\(x_1\leq2x_2\)	Produkcja A nie może być większa niż dwukrotność produkcji B.

W praktyce poprawne sformułowanie ograniczeń bywa trudniejsze niż samo rozwiązanie modelu. Należy pilnować, aby lewa i prawa strona nierówności opisywały wielkości porównywalne, wyrażone w zgodnych jednostkach.

Zbiór rozwiązań dopuszczalnych i rozwiązanie optymalne

Rozwiązaniem dopuszczalnym nazywamy taki zestaw wartości zmiennych decyzyjnych, który spełnia wszystkie warunki ograniczające oraz warunki brzegowe. Zbiór wszystkich rozwiązań dopuszczalnych tworzy obszar, w którym możemy poszukiwać optimum.

W programowaniu liniowym zbiór rozwiązań dopuszczalnych ma postać zbioru wypukłego. W przypadku dwóch zmiennych można go przedstawić na płaszczyźnie jako wielokąt lub obszar nieograniczony. Właśnie na tej własności opiera się metoda graficzna programowania liniowego.

W klasycznym problemie liniowym, jeśli istnieje rozwiązanie optymalne i zbiór rozwiązań jest ograniczony, optimum można znaleźć w jednym z wierzchołków zbioru dopuszczalnego. Metoda simpleks wykorzystuje tę własność, przechodząc od jednego rozwiązania bazowego do kolejnego w taki sposób, aby poprawiać wartość funkcji celu.

Możliwe sytuacje w programowaniu liniowym
Sytuacja	Znaczenie
Jedno rozwiązanie optymalne	Istnieje jeden najlepszy wariant decyzji.
Wiele rozwiązań optymalnych	Różne rozwiązania dopuszczalne dają tę samą najlepszą wartość funkcji celu.
Brak rozwiązania dopuszczalnego	Ograniczenia są ze sobą sprzeczne i nie istnieje wariant spełniający wszystkie warunki.
Funkcja celu nieograniczona	Można poprawiać wartość celu bez końca, nie naruszając ograniczeń.
Rozwiązanie zdegenerowane	Jedno lub więcej zmiennych bazowych przyjmuje wartość zero; może to wymagać ostrożności podczas obliczeń metodą simpleks.

Postać ogólna, kanoniczna i standardowa

W podręcznikach można spotkać nieco różne definicje postaci ogólnej, kanonicznej i standardowej. Warto więc przede wszystkim rozumieć sens przekształceń, a nie zapamiętywać wyłącznie nazwę używaną przez konkretnego autora.

Postać ogólna

W postaci ogólnej model może zawierać zarówno nierówności \(\leq\), jak i \(\geq\), równości oraz różne warunki brzegowe. Jest to forma najbliższa opisowi rzeczywistego problemu.

\[ \max Z=5x_1+4x_2 \]

\[ \begin{aligned} 2x_1+x_2 &\leq 20\\ x_1+3x_2 &\geq 15\\ x_1-x_2 &= 2\\ x_1,x_2 &\geq0 \end{aligned} \]

Przekształcanie nierówności \(\leq\)

Do nierówności typu \(\leq\) dodaje się zmienną luzu. Pokazuje ona niewykorzystaną część danego zasobu.

\[ 2x_1+x_2\leq20 \]

Po dodaniu zmiennej luzu \(s_1\geq0\):

\[ 2x_1+x_2+s_1=20 \]

Jeżeli rozwiązanie końcowe daje \(s_1=4\), oznacza to, że z dostępnych 20 jednostek zasobu wykorzystano tylko 16.

Przekształcanie nierówności \(\geq\)

Od nierówności typu \(\geq\) odejmuje się zmienną nadwyżki. Sama zmienna nadwyżki zwykle nie tworzy jednak wygodnej bazy początkowej dla metody simpleks, dlatego często pojawia się również zmienna sztuczna.

\[ x_1+3x_2\geq15 \]

Po odjęciu zmiennej nadwyżki \(s_2\geq0\):

\[ x_1+3x_2-s_2=15 \]

W metodzie simpleks można wtedy użyć zmiennych sztucznych oraz metody dwóch faz albo metody wielkiej kary. Te techniki pozwalają rozpocząć obliczenia od dopuszczalnego rozwiązania bazowego.

Zmienne bez ograniczenia znaku

Jeżeli zmienna może przyjmować wartości dodatnie i ujemne, można zapisać ją jako różnicę dwóch zmiennych nieujemnych:

\[ x_j=x_j^{+}-x_j^{-} \]

przy czym:

\[ x_j^{+}\geq0, \qquad x_j^{-}\geq0 \]

Takie przekształcenie pozwala zapisać model w formie wygodnej dla standardowych algorytmów liniowych.

Dlaczego stosuje się postać standardową?

Algorytmy takie jak metoda simpleks działają najwygodniej, gdy ograniczenia mają postać równań, a zmienne spełniają warunek nieujemności. Przekształcenia nie zmieniają sensu ekonomicznego modelu, lecz przygotowują go do rozwiązania określoną metodą.

Zapis macierzowy modelu

W większych modelach zapis rozwinięty byłby nieczytelny. Dlatego programowanie liniowe często zapisuje się z wykorzystaniem macierzy i wektorów.

Niech:

\[ x= \begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{bmatrix}, \qquad c= \begin{bmatrix} c_1\\ c_2\\ \vdots\\ c_n \end{bmatrix}, \qquad b= \begin{bmatrix} b_1\\ b_2\\ \vdots\\ b_m \end{bmatrix} \]

oraz niech \(A\) będzie macierzą współczynników ograniczeń:

\[ A= \begin{bmatrix} a_{11} & a_{12} & \dots & a_{1n}\\ a_{21} & a_{22} & \dots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{m1} & a_{m2} & \dots & a_{mn} \end{bmatrix} \]

Wtedy typowy model maksymalizacyjny można zapisać zwięźle:

\[ \max\ c^Tx \]

przy ograniczeniach:

\[ Ax\leq b, \qquad x\geq0 \]

W postaci standardowej ograniczenia zapisuje się zwykle jako:

\[ Ax=b, \qquad x\geq0 \]

Zapis macierzowy jest szczególnie przydatny przy analizie dualności, metodach numerycznych, implementacji komputerowej oraz opisie dużych modeli logistycznych i produkcyjnych.

Metody rozwiązywania programów liniowych

Wybór metody zależy przede wszystkim od wielkości modelu, jego struktury i celu analizy. Dla bardzo prostych modeli można wykonać obliczenia ręcznie. Dla modeli rzeczywistych, obejmujących setki lub tysiące zmiennych, stosuje się oprogramowanie optymalizacyjne.

Podstawowe metody rozwiązywania modeli liniowych
Metoda	Zastosowanie	Charakterystyka
Metoda graficzna	Modele z dwiema zmiennymi decyzyjnymi.	Pozwala zobaczyć zbiór rozwiązań dopuszczalnych, wierzchołki i kierunek poprawy funkcji celu.
Metoda simpleks	Ogólne modele liniowe.	Przechodzi między rozwiązaniami bazowymi, poprawiając wartość funkcji celu.
Metoda dwóch faz	Modele z ograniczeniami \(\geq\) i równościami.	Umożliwia znalezienie dopuszczalnej bazy początkowej z wykorzystaniem zmiennych sztucznych.
Metoda wielkiej kary	Modele wymagające zmiennych sztucznych.	Wprowadza wysoką karę za pozostawienie zmiennej sztucznej w rozwiązaniu końcowym.
Metody punktów wewnętrznych	Duże modele komputerowe.	Poszukują rozwiązania przez wnętrze zbioru dopuszczalnego, a nie wyłącznie przez jego wierzchołki.
Solvery i pakiety optymalizacyjne	Modele praktyczne.	Automatyzują obliczenia, ale wymagają poprawnego sformułowania i interpretacji modelu.

Dla modeli z dwiema zmiennymi warto poznać metodę graficzną. Pozwala ona intuicyjnie zrozumieć pojęcie zbioru dopuszczalnego, wierzchołka i rozwiązania optymalnego.

Najważniejszą klasyczną metodą ogólną jest metoda simpleks. Jest ona podstawą wielu podręcznikowych obliczeń i pozwala rozwiązywać modele o dowolnej liczbie zmiennych decyzyjnych.

Szczególne modele programowania liniowego

Niektóre klasy problemów mają tak charakterystyczną strukturę, że opracowano dla nich wyspecjalizowane algorytmy. Są one nadal modelami liniowymi albo ściśle związanymi z programowaniem liniowym, ale ich szczególna budowa pozwala rozwiązywać je sprawniej niż za pomocą całkowicie ogólnego podejścia.

Zagadnienie transportowe

Zagadnienie transportowe służy do wyznaczania optymalnego planu przewozu dóbr od dostawców do odbiorców. Celem jest zwykle minimalizacja łącznego kosztu transportu przy zachowaniu podaży każdego dostawcy i popytu każdego odbiorcy.

Model transportowy ma strukturę macierzową: dostawcy są zwykle zapisywani w wierszach, odbiorcy w kolumnach, a komórki opisują wielkości przewozów. Szczegółowe omówienie metod początkowych i metody potencjałów w zagadnieniu transportowym znajduje się w osobnym artykule.

Zagadnienie przydziału

Zagadnienie przydziału polega na przypisaniu wykonawców do zadań w taki sposób, aby każdy wykonawca otrzymał jedno zadanie, każde zadanie zostało wykonane przez jednego wykonawcę, a łączny koszt był minimalny albo łączna korzyść maksymalna.

Jest ono szczególnym przypadkiem zagadnienia transportowego, w którym podaż każdego wykonawcy i popyt każdego zadania wynoszą 1. Do jego rozwiązywania stosuje się między innymi algorytm węgierski dla zagadnienia przydziału.

Problemy mieszanki i planowania produkcji

W problemach mieszanki określa się, ile składników należy wykorzystać, aby osiągnąć wymagane parametry produktu przy minimalnym koszcie. W planowaniu produkcji wyznacza się natomiast wielkości produkcji poszczególnych wyrobów przy ograniczonych zasobach materiałowych, maszynowych i kadrowych.

Takie modele są klasycznymi przykładami programowania liniowego: zmienne decyzyjne opisują ilości produktów albo składników, funkcja celu wyraża zysk lub koszt, a ograniczenia wynikają z dostępnych zasobów i wymagań jakościowych.

Przepływy w sieciach

Modele sieciowe opisują przepływ dóbr, informacji, osób lub energii przez sieć połączeń. Mogą dotyczyć minimalnego kosztu przepływu, maksymalnego przepływu, najkrótszej ścieżki albo planowania tras. Wiele z nich można traktować jako szczególne przypadki programowania liniowego, wykorzystujące strukturę grafu.

Dualność w programowaniu liniowym

Każdemu programowi liniowemu można przypisać drugi, powiązany z nim model: zadanie dualne. Pierwotny model nazywa się zadaniem prymalnym. Dualność pozwala spojrzeć na ten sam problem z dwóch stron: na przykład z perspektywy planu produkcyjnego oraz z perspektywy wyceny zasobów.

W wielu zastosowaniach zmienne dualne interpretuje się jako ceny dualne lub ceny cienia. Pokazują one, jak zmieniłaby się optymalna wartość funkcji celu po niewielkim zwiększeniu dostępności danego zasobu.

Temat ten ma duże znaczenie teoretyczne i praktyczne. Szczegółowo omawia go artykuł Dualność w programowaniu liniowym — zadanie prymalne, zadanie dualne i warunki komplementarności.

Dlaczego dualność jest użyteczna?

Dualność nie jest tylko formalnym przekształceniem wzorów. Pozwala interpretować wartość ograniczonych zasobów, analizować wrażliwość rozwiązania oraz lepiej rozumieć strukturę problemu decyzyjnego.

Co znajduje się poza programowaniem liniowym?

Programowanie liniowe jest bardzo ważne, ale nie obejmuje wszystkich problemów optymalizacyjnych. Rzeczywiste decyzje mogą wymagać dodatkowych ograniczeń lub uwzględnienia niepewności, nieliniowości albo kolejności decyzji w czasie.

Wybrane dziedziny programowania matematycznego
Rodzaj modelu	Charakterystyka	Przykład
Programowanie całkowitoliczbowe	Niektóre lub wszystkie zmienne muszą przyjmować wartości całkowite.	Liczba samochodów, pracowników, maszyn lub otwartych magazynów.
Programowanie binarne	Zmienne przyjmują wyłącznie wartości 0 albo 1.	Wybór projektu, otwarcie lokalizacji, przydział zadania.
Programowanie mieszane	Część zmiennych jest ciągła, a część całkowita lub binarna.	Plan produkcji z decyzją o uruchomieniu maszyny.
Programowanie nieliniowe	Funkcja celu lub ograniczenia zawierają zależności nieliniowe.	Modele z efektami skali, funkcjami ryzyka lub iloczynami zmiennych.
Programowanie stochastyczne	Uwzględnia niepewność parametrów, scenariusze i ryzyko.	Planowanie zapasów przy niepewnym popycie.
Programowanie dynamiczne	Opisuje decyzje podejmowane w kolejnych okresach.	Planowanie zapasów, trasy wieloetapowe, harmonogram inwestycji.

W ramach badań operacyjnych analizuje się również zagadnienia, które nie są klasycznymi programami liniowymi. Należą do nich między innymi modele zapasów, symulacja, analiza sieciowa i teoria kolejek. Przykładem jest teoria kolejek i modele obsługi masowej, które pomagają analizować średni czas oczekiwania, liczbę klientów w kolejce oraz wykorzystanie stanowisk obsługi.

Praktyczny schemat budowy modelu

Rozwiązanie rachunkowe ma sens tylko wtedy, gdy model poprawnie opisuje problem. Dlatego budowę programu liniowego warto prowadzić według uporządkowanego schematu.

Jak zbudować model programowania liniowego?

Określ problem decyzyjny. Ustal, co ma zostać zaplanowane lub wybrane.
Zdefiniuj zmienne decyzyjne. Opisz każdą zmienną słowami i podaj jej jednostkę.
Wybierz funkcję celu. Zdecyduj, czy maksymalizujesz, czy minimalizujesz określoną wielkość.
Wypisz ograniczenia. Uwzględnij zasoby, wymagania minimalne, limity oraz zależności technologiczne.
Dodaj warunki brzegowe. Określ nieujemność, całkowitoliczbowość albo inne ograniczenia zakresu zmiennych.
Sprawdź jednostki. Wszystkie składniki pojedynczego równania lub nierówności muszą być porównywalne.
Dobierz metodę rozwiązania. Dla dwóch zmiennych można użyć metody graficznej, dla większych modeli simpleksu lub solvera.
Zinterpretuj wynik. Przełóż wartości zmiennych i funkcji celu na konkretne decyzje praktyczne.
Wykonaj analizę wrażliwości. Sprawdź, jak zmiana cen, zasobów lub limitów wpływa na rozwiązanie.

Warto pamiętać, że wynik modelu nie zastępuje decyzji człowieka. Jest narzędziem wspierającym decyzję. Trzeba jeszcze ocenić, czy dane są wiarygodne, czy model nie pomija ważnych ograniczeń oraz czy rozwiązanie można realnie wdrożyć.

Podsumowanie

Programowanie matematyczne służy do podejmowania najlepszych decyzji w warunkach ograniczonych zasobów. Programowanie liniowe jest jego podstawowym przypadkiem, w którym funkcja celu i warunki ograniczające mają postać liniową.

Każdy model liniowy składa się ze zmiennych decyzyjnych, funkcji celu, ograniczeń i warunków brzegowych. Po prawidłowym sformułowaniu model można rozwiązać metodą graficzną, metodą simpleks, metodami komputerowymi albo algorytmami wyspecjalizowanymi dla określonych klas problemów.

Programowanie liniowe stanowi fundament wielu modeli badań operacyjnych: planowania produkcji, transportu, przydziału zadań, przepływów sieciowych i optymalizacji wykorzystania zasobów. Zrozumienie jego podstaw ułatwia naukę kolejnych metod, takich jak simpleks, dualność, zagadnienie transportowe czy algorytm węgierski.

Powiązane artykuły

Masz problem z tym tematem?

Wszechwiedza.pl pomaga zrozumieć matematykę, statystykę, ekonometrię, badania operacyjne, analizę danych, mechanikę, rachunkowość i wiele innych przedmiotów — spokojnie, konkretnie i krok po kroku.

Zapytaj o pomoc