Programowanie liniowe (eng. LP) to jedna z najważniejszych dziedzin optymalizacji matematycznej, której celem jest maksymalizacja lub minimalizacja funkcji liniowej przy spełnieniu określonych ograniczeń również w postaci równań lub nierówności liniowych. Metody programowania liniowego znajdują zastosowanie w wielu dziedzinach, takich jak logistyka, ekonomia, inżynieria, zarządzanie produkcją, analiza finansowa czy planowanie strategiczne.

Początki programowania liniowego sięgają lat 30. XX wieku, jednak jego dynamiczny rozwój rozpoczął się w czasie II wojny światowej. W 1947 roku amerykański matematyk George Dantzig opracował metodę simpleks, która zrewolucjonizowała sposób rozwiązywania problemów optymalizacyjnych i do dziś pozostaje jedną z najpopularniejszych metod rozwiązywania problemów PL.

Od tamtej pory programowanie liniowe stało się integralną częścią badań operacyjnych (ang. operations research) i zyskało szerokie uznanie w praktyce gospodarczej i naukowej.

Podstawowe elementy programowania liniowego to:

• Funkcja celu – funkcja liniowa, którą chcemy maksymalizować lub minimalizować (np. zysk, koszt, czas).
• Zmienna decyzyjna – wielkości, których wartości są poszukiwane i które mają wpływ na wartość funkcji celu.
• Ograniczenia (restrykcje) – warunki, jakie muszą być spełnione przez zmienne decyzyjne, zwykle w formie równań lub nierówności liniowych.
• Obszar dopuszczalny – zbiór wszystkich możliwych rozwiązań, które spełniają ograniczenia.
• Rozwiązanie optymalne – punkt w obszarze dopuszczalnym, dla którego funkcja celu osiąga wartość największą (maksimum) lub najmniejszą (minimum), zgodnie z założeniem problemu.

W kolejnych sekcjach tego artykułu przedstawione zostaną metody rozwiązywania problemów programowania liniowego oraz przykłady praktycznych zastosowań.

Rozważmy typowy problem produkcyjny, w którym celem jest maksymalizacja zysku przy ograniczonych zasobach czasu i materiałów.

Rzemieślnik produkuje dwa rodzaje lamp:

• Lampy stojące (duże) – wymagają 6 godzin pracy i 200 zł na materiały, zysk z jednej sztuki wynosi 240 zł.
• Lampy biurkowe (małe) – wymagają 5 godzin pracy i 100 zł na materiały, zysk z jednej sztuki wynosi 160 zł.

Rzemieślnik dysponuje tygodniowo:

• maksymalnie 40 godzinami pracy,
• maksymalnie 1000 zł na materiały.

Zadanie polega na określeniu, ile lamp każdego typu powinien produkować tygodniowo, aby zmaksymalizować swój zysk, nie przekraczając dostępnych zasobów.

Niech:

• $x$ – liczba lamp stojących produkowanych tygodniowo,
• $y$ – liczba lamp biurkowych produkowanych tygodniowo.

Chcemy zmaksymalizować zysk:

$$ Z = 240x + 160y $$

1. Czas pracy:

$$ 6x + 5y \leq 40 $$

2. Koszt materiałów:

$$ 200x + 100y \leq 1000 $$

3. Nieujemność zmiennych (nie można wyprodukować ujemnej liczby lamp):

$$ x \geq 0,\quad y \geq 0 $$

$$ \begin{cases} \text{Maksymalizuj } Z = 240x + 160y \\ \text{przy warunkach:} \\ 6x + 5y \leq 40 \\ 200x + 100y \leq 1000 \\ x \geq 0,\ y \geq 0 \end{cases} $$

W kolejnych krokach można ten model rozwiązać metodą graficzną (ponieważ są tylko dwie zmienne) lub zastosować metodę simpleks. Wynik da nam optymalną liczbę lamp każdego typu, które powinien produkować rzemieślnik, by osiągnąć maksymalny zysk.

Aby rozwiązać problem programowania liniowego w Excelu, można skorzystać z wbudowanego narzędzia Solver:

1. Wprowadź dane do arkusza:

2. Wprowadź zmienne decyzji (np. komórki B5 i C5) – to będą liczby lamp.

3. Oblicz łączny zysk: W komórce D1 wpisz formułę: =240*B5 + 160*C5

4. Oblicz zużycie zasobów:

• Łączny czas pracy: `=6*B5 + 5*C5`
• Łączny koszt materiałów: `=200*B5 + 100*C5`

5. Otwórz Solver:

• `Dane > Solver`
• Ustaw „Maksymalizuj”: komórka z całkowitym zyskiem
• Zmieniane komórki: `B5:C5`

Ograniczenia:

• czas pracy ≤ 40
• koszt materiałów ≤ 1000
• B5 ≥ 0, C5 ≥ 0

6. Wybierz Simplex LP jako metodę rozwiązywania.

7. Kliknij Rozwiąż.

Python oferuje bibliotekę `PuLP`, która umożliwia tworzenie i rozwiązywanie problemów programowania liniowego.

from pulp import LpMaximize, LpProblem, LpVariable
 
# Definiowanie problemu
model = LpProblem(name="lamp-production", sense=LpMaximize)
 
# Zmienne decyzyjne (rzeczywiste)
x = LpVariable(name="lampy_stojace", lowBound=0)
y = LpVariable(name="lampy_biurkowe", lowBound=0)
 
# Funkcja celu
model += 240 * x + 160 * y, "Zysk"
 
# Ograniczenia
model += (6 * x + 5 * y <= 40, "Czas_pracy")
model += (200 * x + 100 * y <= 1000, "Koszt_materialow")
 
# Rozwiązanie
model.solve()
 
# Wynik
print(f"Lampy stojące: {x.value()}")
print(f"Lampy biurkowe: {y.value()}")
print(f"Maksymalny zysk: {model.objective.value()} zł")

Lampy stojące: 2.5
Lampy biurkowe: 5.0
Maksymalny zysk: 1400.0 zł

Rozważmy problem optymalizacji produkcji w zakładzie wytwarzającym dwa rodzaje rajstop: cienkie i grube. Celem jest maksymalizacja utargu, przy ograniczonych zasobach surowców.

Zakład produkuje:

• Rajstopy cienkie – wymagają: 10 g przędzy elastycznej i 10 g bawełnianej,
• Rajstopy grube – wymagają: 20 g przędzy elastycznej i 25 g bawełnianej.

Stan magazynowy:

• 200 kg przędzy elastycznej = 200 000 g,
• 500 kg przędzy bawełnianej = 500 000 g.

Ceny sprzedaży:

• Rajstopy cienkie: 1,50 zł / para,
• Rajstopy grube: 4,00 zł / para.

\

Niech:

• $x$ – liczba par rajstop cienkich,
• $y$ – liczba par rajstop grubych.

Zakład chce zmaksymalizować utarg (czyli całkowity przychód):

$$ Z = 1.5x + 4y $$

1. Zużycie przędzy elastycznej:

$$ 10x + 20y \leq 200\,000 $$

2. Zużycie przędzy bawełnianej:

$$ 10x + 25y \leq 500\,000 $$

3. Nieujemność zmiennych:

$$ x \geq 0,\quad y \geq 0 $$

$$ \begin{cases} \text{Maksymalizuj } Z = 1.5x + 4y \\ \text{przy warunkach:} \\ 10x + 20y \leq 200\,000 \\ 10x + 25y \leq 500\,000 \\ x \geq 0,\ y \geq 0 \end{cases} $$

Model ten można rozwiązać w Excelu (przy pomocy dodatku Solver) lub w Pythonie, np. za pomocą biblioteki `PuLP`. Wynikiem będzie liczba par rajstop cienkich i grubych, które zakład powinien wyprodukować, aby osiągnąć jak największy przychód, nie przekraczając dostępnych zapasów przędzy.

W kolejnych sekcjach można przedstawić konkretne rozwiązanie (metodą graficzną, w Excelu lub Pythonie) i analizę wyniku.

Python oferuje bibliotekę `PuLP`, która umożliwia tworzenie i rozwiązywanie problemów programowania liniowego.

from pulp import LpMaximize, LpProblem, LpVariable
 
# Tworzymy problem maksymalizacji
model = LpProblem(name="produkcja-rajstop", sense=LpMaximize)
 
# Zmienne decyzyjne (liczba par rajstop)
x = LpVariable(name="rajstopy_cienkie", lowBound=0)
y = LpVariable(name="rajstopy_grube", lowBound=0)
 
# Funkcja celu – maksymalizacja utargu
model += 1.5 * x + 4 * y, "Utarg"
 
# Ograniczenia zużycia przędzy (gramy)
model += (10 * x + 20 * y <= 200_000, "Przędza_elastyczna")
model += (10 * x + 25 * y <= 500_000, "Przędza_bawełniana")
 
# Rozwiązanie
model.solve()
 
# Wyniki
print("Plan produkcji maksymalizujący utarg:")
print(f"Rajstopy cienkie: {x.value()} par")
print(f"Rajstopy grube: {y.value()} par")
print(f"Maksymalny utarg: {model.objective.value()} zł")

Plan produkcji maksymalizujący utarg:
Rajstopy cienkie: 0.0 par
Rajstopy grube: 10000.0 par
Maksymalny utarg: 40000.0 zł

Zakład produkcyjny wytwarza trzy rodzaje tkanin:

• Pościelowe
• Sukienkowe
• Dekoracyjne

Proces produkcji każdej tkaniny przebiega w trzech wydziałach:

• Przędzalnia
• Tkalnia
• Wykończalnia

Dla każdego rodzaju tkaniny określono:

• Jednostkowe zużycie czasu pracy maszyn (w minutach na 1 mb – metr bieżący),
• Jednostkowy zysk (w złotówkach na 1 mb).

Maksymalny czas pracy maszyn w każdym z wydziałów jest ograniczony – wartości te podano w godzinach, co należy przeliczyć na minuty (1 godzina = 60 minut).

Niech:

• $x$ – liczba metrów bieżących tkanin pościelowych,
• $y$ – liczba metrów bieżących tkanin sukienkowych,
• $z$ – liczba metrów bieżących tkanin dekoracyjnych.

Celem jest maksymalizacja zysku:

$$ Z = 5x + 4.5y + 6z $$

1. Przędzalnia:

$$ 2x + 1y + 2z \leq 144000 $$

2. Tkalnia:

$$ 1x + 2y + 2z \leq 180000 $$

3. Wykończalnia:

$$ 2x + 2y + 1z \leq 156000 $$

4. Nieujemność zmiennych:

$$ x \geq 0,\quad y \geq 0,\quad z \geq 0 $$

$$ \begin{cases} \text{Maksymalizuj } Z = 5x + 4.5y + 6z \\ \text{przy warunkach:} \\ 2x + 1y + 2z \leq 144000 \\ 1x + 2y + 2z \leq 180000 \\ 2x + 2y + 1z \leq 156000 \\ x, y, z \geq 0 \end{cases} $$

Wyznaczyć optymalny plan produkcji tkanin, czyli wartości $x$, $y$, $z$, które maksymalizują zysk zakładu, nie przekraczając dostępnych limitów czasu pracy maszyn w każdym dziale produkcyjnym.

Python oferuje bibliotekę `PuLP`, która umożliwia tworzenie i rozwiązywanie problemów programowania liniowego.

from pulp import LpMaximize, LpProblem, LpVariable
 
# Tworzymy model
model = LpProblem(name="produkcja-tkanin", sense=LpMaximize)
 
# Zmienne decyzyjne: ilość mb tkanin
x = LpVariable(name="tkanina_poscielowa", lowBound=0)
y = LpVariable(name="tkanina_sukienkowa", lowBound=0)
z = LpVariable(name="tkanina_dekoracyjna", lowBound=0)
 
# Funkcja celu: maksymalizacja zysku
model += 5 * x + 4.5 * y + 6 * z, "Zysk"
 
# Ograniczenia czasowe – przeliczone na minuty
model += 2 * x + 1 * y + 2 * z <= 144_000, "Przędzalnia"
model += 1 * x + 2 * y + 2 * z <= 180_000, "Tkalnia"
model += 2 * x + 2 * y + 1 * z <= 156_000, "Wykończalnia"
 
# Rozwiązanie
model.solve()
 
# Wyniki
print("Optymalny plan produkcji:")
print(f"Tkanina pościelowa:    {x.value():.2f} mb")
print(f"Tkanina sukienkowa:    {y.value():.2f} mb")
print(f"Tkanina dekoracyjna:   {z.value():.2f} mb")
print(f"Maksymalny zysk:       {model.objective.value():.2f} zł")

Optymalny plan produkcji:
Tkanina pościelowa:    12000.00 mb
Tkanina sukienkowa:    48000.00 mb
Tkanina dekoracyjna:   36000.00 mb
Maksymalny zysk:       492000.00 zł

Pracownia specjalizująca się w produkcji męskich kapeluszy i beretów dysponuje ograniczonymi zasobami surowca oraz stoi wobec ograniczonego popytu rynkowego. Celem jest opracowanie takiego planu produkcji, który zmaksymalizuje całkowity zysk w miesiącach jesienno-zimowych (I i IV kwartał).

• Surowiec: podstawowym materiałem do produkcji obu wyrobów jest filc.
• Na jeden kapelusz potrzeba: 0,6 m² filcu.
• Na jeden beret potrzeba: 0,4 m² filcu.
• Łączny miesięczny limit zakupu filcu: 960 m².
• Popyt rynkowy: nie więcej niż 1000 sztuk każdego produktu miesięcznie.

Zysk jednostkowy:

• Kapelusz: 3 zł/szt.
• Beret: 2 zł/szt.

Niech:

• $x$ – liczba produkowanych kapeluszy miesięcznie,
• $y$ – liczba produkowanych beretów miesięcznie.

Celem jest maksymalizacja zysku:

$$ Z = 3x + 2y $$

1. Zużycie filcu:

$$ 0.6x + 0.4y \leq 960 $$

2. Ograniczenia popytowe (sprzedażowe):

$$ x \leq 1000 \\ y \leq 1000 $$

3. Nieujemność zmiennych:

$$ x \geq 0,\quad y \geq 0 $$

$$ \begin{cases} \text{Maksymalizuj } Z = 3x + 2y \\ \text{przy warunkach:} \\ 0.6x + 0.4y \leq 960 \\ x \leq 1000 \\ y \leq 1000 \\ x, y \geq 0 \end{cases} $$

Wyznaczyć liczbę kapeluszy i beretów, jaką pracownia powinna produkować w miesiącach jesienno-zimowych, aby osiągnąć maksymalny zysk, przy uwzględnieniu ograniczeń materiałowych oraz popytowych.

Python oferuje bibliotekę `PuLP`, która umożliwia tworzenie i rozwiązywanie problemów programowania liniowego.

from pulp import LpMaximize, LpProblem, LpVariable
 
# Tworzymy model maksymalizacji zysku
model = LpProblem(name="produkcja-kapeluszy-i-beretow", sense=LpMaximize)
 
# Zmienne decyzyjne: liczba kapeluszy i beretów
x = LpVariable(name="kapelusze", lowBound=0)
y = LpVariable(name="berety", lowBound=0)
 
# Funkcja celu: maksymalizacja zysku
model += 3 * x + 2 * y, "Zysk"
 
# Ograniczenie zużycia filcu
model += 0.6 * x + 0.4 * y <= 960, "Filc"
 
# Ograniczenia popytowe
model += x <= 1000, "Max_kapelusze"
model += y <= 1000, "Max_berety"
 
# Rozwiązanie
model.solve()
 
# Wyniki
print("Optymalny plan produkcji:")
print(f"Kapelusze: {x.value():.0f} szt.")
print(f"Berety:    {y.value():.0f} szt.")
print(f"Maksymalny zysk: {model.objective.value():.2f} zł")

Optymalny plan produkcji:
Kapelusze: 1000 szt.
Berety:    900 szt.
Maksymalny zysk: 4800.00 zł

Pani Zuzia prowadzi małą firmę gastronomiczną, w której przygotowuje dwa rodzaje dań: Maxi i Mini. Oba dania różnią się wielkością porcji, zużyciem składników oraz ceną sprzedaży. Celem jest ustalenie takiej liczby dań każdego typu, aby zmaksymalizować dzienny przychód z ich sprzedaży – zakładamy, że wszystko, co zostanie przygotowane, zostanie również sprzedane.

* Dania oferowane:

• Maxi – cena: 19 zł
• Mini – cena: 11 zł

* Składniki potrzebne do przygotowania:

• Mięso:

• Maxi: 7 dag (0,07 kg)
• Mini: 4 dag (0,04 kg)
• Kapusta:

• Maxi: 10 dag (0,10 kg)
• Mini: 7 dag (0,07 kg)

* Dzienne zapasy:

• Mięso: 1,3 kg
• Kapusta: 2,0 kg

Niech:

• $x$ – liczba dań typu Maxi,
• $y$ – liczba dań typu Mini.

Celem jest maksymalizacja przychodu:

$$ Z = 19x + 11y $$

1. Mięso:

$$ 0.07x + 0.04y \leq 1.3 $$

2. Kapusta:

$$ 0.10x + 0.07y \leq 2.0 $$

3. Nieujemność zmiennych:

$$ x \geq 0,\quad y \geq 0 $$

$$ \begin{cases} \text{Maksymalizuj } Z = 19x + 11y \\ \text{przy warunkach:} \\ 0.07x + 0.04y \leq 1.3 \\ 0.10x + 0.07y \leq 2.0 \\ x, y \geq 0 \end{cases} $$

Wyznaczyć ile dań typu Maxi oraz Mini powinna przygotowywać Pani Zuzia dziennie, aby osiągnąć maksymalny możliwy przychód, przy ograniczonych zasobach mięsa i kapusty.

Python oferuje bibliotekę `PuLP`, która umożliwia tworzenie i rozwiązywanie problemów programowania liniowego.

from pulp import LpMaximize, LpProblem, LpVariable
 
# Tworzenie modelu
model = LpProblem(name="produkcja-dan-pani-zuzia", sense=LpMaximize)
 
# Zmienne decyzyjne: liczba dań Maxi (x) i Mini (y)
x = LpVariable(name="danie_maxi", lowBound=0)
y = LpVariable(name="danie_mini", lowBound=0)
 
# Funkcja celu: maksymalizacja przychodu
model += 19 * x + 11 * y, "Przychod"
 
# Ograniczenia zasobów
model += 0.07 * x + 0.04 * y <= 1.3, "Ograniczenie_miesa"
model += 0.10 * x + 0.07 * y <= 2.0, "Ograniczenie_kapusty"
 
# Rozwiązanie modelu
model.solve()
 
# Wyniki
print("Optymalny plan produkcji dań:")
print(f"Dania Maxi: {x.value():.2f} szt.")
print(f"Dania Mini: {y.value():.2f} szt.")
print(f"Maksymalny przychód: {model.objective.value():.2f} zł")

Optymalny plan produkcji dań:
Dania Maxi: 12.22 szt.
Dania Mini: 11.11 szt.
Maksymalny przychód: 354.44 zł