Programowanie liniowe (PL) 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
x = LpVariable(name="lampy_stojace", lowBound=0, cat='Integer')
y = LpVariable(name="lampy_biurkowe", lowBound=0, cat='Integer')
 
# 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: 3.0
Lampy biurkowe: 4.0
Maksymalny zysk: 1360.0 zł