Różnice

Różnice między wybraną wersją a wersją aktualną.

--- notatki:programowanie_liniowe [2025/05/16 14:10] – administrator
+++ notatki:programowanie_liniowe [2025/05/16 19:26] (aktualna) – administrator
@@ Linia 1: / Linia 1: @@
-====== Programowanie Liniowe: ćwiczenia======
+====== Badania operacyjne: Programowanie Liniowe ćwiczenia======
 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.
@@ Linia 193: / Linia 193: @@
   * Rajstopy grube: **4,00 zł / para**.
-\==== Zmienna decyzyjna ====
+==== Zmienna decyzyjna ====
 Niech:
@@ Linia 539: / Linia 539: @@
 </code>
+====== Przykład problemu produkcyjnego – Pani Zuzia ======
+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.
+==== Treść zadania ====
+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
+==== Zmienna decyzyjna ====
+Niech:
+  * $x$ – liczba dań typu **Maxi**,
+  * $y$ – liczba dań typu **Mini**.
+==== Funkcja celu ====
+Celem jest **maksymalizacja przychodu**:
+$$
+Z = 19x + 11y
+$$
+==== Ograniczenia zasobów ====
+. **Mięso**:
+$$
+.07x + 0.04y \leq 1.3
+$$
+. **Kapusta**:
+$$
+.10x + 0.07y \leq 2.0
+$$
+. **Nieujemność zmiennych**:
+$$
+x \geq 0,\quad y \geq 0
+$$
+==== Model matematyczny ====
+$$
+\begin{cases}
+\text{Maksymalizuj } Z = 19x + 11y \\
+\text{przy warunkach:} \\
+.07x + 0.04y \leq 1.3 \\
+.10x + 0.07y \leq 2.0 \\
+x, y \geq 0
+\end{cases}
+$$
+==== Cel zadania ====
+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.
+==== Rozwiązanie w Pythonie (biblioteka `PuLP`) ====
+Python oferuje bibliotekę `PuLP`, która umożliwia tworzenie i rozwiązywanie problemów programowania liniowego.
+=== Przykładowy kod: ===
+<code python>
+from pulp import LpMaximize, LpProblem, LpVariable, LpInteger
+# Tworzymy model optymalizacji
+model = LpProblem(name="produkcja-dan-pani-zuzia", sense=LpMaximize)
+# Zmienne decyzyjne jako liczby całkowite
+x = LpVariable(name="danie_maxi", lowBound=0, cat=LpInteger)
+y = LpVariable(name="danie_mini", lowBound=0, cat=LpInteger)
+# Funkcja celu: maksymalizacja przychodu
+model += 19 * x + 11 * y, "Przychod"
+# Ograniczenia surowcó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 problemu
+model.solve()
+# Wyniki
+print("Optymalny plan produkcji (liczby całkowite):")
+print(f"Dania Maxi: {int(x.value())} szt.")
+print(f"Dania Mini: {int(y.value())} szt.")
+print(f"Maksymalny przychód: {model.objective.value():.2f} zł")
+</code>
+=== Wynik: ===
+<code>
+Optymalny plan produkcji (liczby całkowite):
+Dania Maxi: 14 szt.
+Dania Mini: 8 szt.
+Maksymalny przychód: 354.00 zł
+</code>
+====== Przykład Minimalizacyjny Ogrzewanie pomieszczeń ======
+Do ogrzania dwóch pomieszczeń o początkowej temperaturze 0°C można używać dwóch źródeł ciepła: węgla i koksu. Każde z tych paliw wpływa inaczej na temperaturę w pomieszczeniach, a ich ceny również się różnią.
+===== Dane wejściowe =====
+Początkowa temperatura w obu pomieszczeniach: 0°C
+Minimalne wymagane temperatury:
+    * Pomieszczenie 1: co najmniej 180°C
+    * Pomieszczenie 2: co najmniej 200°C
+fekt spalania:
+**1 kg węgla**:
+      * Pomieszczenie 1: +30°C
+      * Pomieszczenie 2: +20°C
+**1 kg koksu**:
+      * Pomieszczenie 1: +10°C
+      * Pomieszczenie 2: +20°C
+Koszty:
+    * 1 tona węgla: 500 zł → 1 kg = 0,50 zł
+    * 1 tona koksu: 300 zł → 1 kg = 0,30 zł
+===== Zmienne decyzyjne =====
+  * $ x $ – liczba **kg węgla** do spalenia
+  * $ y $ – liczba **kg koksu** do spalenia
+===== Funkcja celu =====
+Minimalizacja łącznego kosztu ogrzewania:
+$$
+\min Z = 0.50x + 0.30y
+$$
+===== Ograniczenia =====
+Temperatury muszą być osiągnięte lub przekroczone:
+  * Dla pierwszego pomieszczenia:
+$$
+x + 10y \geq 180
+$$
+  * Dla drugiego pomieszczenia:
+$$
+x + 20y \geq 200
+$$
+  * Dodatkowo, nie możemy spalać ujemnych ilości paliwa:
+$$
+x \geq 0,\quad y \geq 0
+$$
+===== Cel =====
+Wyznaczyć minimalne ilości węgla $ x $ i koksu $ y $, które pozwolą uzyskać wymaganą temperaturę w obu pomieszczeniach przy **najniższym koszcie ogrzewania**.
+===== Rozwiązanie =====
+Rozwiązanie można uzyskać za pomocą:
+  * arkusza kalkulacyjnego (Excel: dodając Solver),
+  * programowania liniowego w Pythonie (np. z użyciem biblioteki PuLP),
+  * metody graficznej (jeśli szukamy wizualnego zrozumienia dla 2 zmiennych).
+==== Rozwiązanie w Pythonie (biblioteka `PuLP`) ====
+Python oferuje bibliotekę `PuLP`, która umożliwia tworzenie i rozwiązywanie problemów programowania liniowego.
+=== Przykładowy kod: ===
+<code python>
+from pulp import LpProblem, LpVariable, LpMinimize, LpStatus, value
+# Tworzenie modelu
+model = LpProblem("ogrzewanie_pomieszczen", LpMinimize)
+# Zmienne decyzyjne: kg węgla (x), kg koksu (y)
+x = LpVariable("wegiel_kg", lowBound=0)
+y = LpVariable("koks_kg", lowBound=0)
+# Funkcja celu: minimalizacja kosztów
+model += 0.50 * x + 0.30 * y, "Koszt_ogrzewania"
+# Ograniczenia temperatury
+model += 30 * x + 10 * y >= 180, "Temp_pomieszczenie_1"
+model += 20 * x + 20 * y >= 200, "Temp_pomieszczenie_2"
+# Rozwiązanie
+model.solve()
+# Wyniki
+print("Status:", LpStatus[model.status])
+print("Węgiel (kg):", round(x.value(), 2))
+print("Koks (kg):", round(y.value(), 2))
+print("Minimalny koszt (zł):", round(value(model.objective), 2))
+</code>
+=== Wynik: ===
+<code>
+Status: Optimal
+Węgiel (kg): 4.0
+Koks (kg): 6.0
+Minimalny koszt (zł): 3.8
+</code>
+====== Problem transportowy - Transport mieszanki soli i piasku ======
+Miasto musi w okresie zimowym dostarczyć mieszankę soli i piasku z dwóch składnic do czterech dzielnic. Celem jest ustalenie takiego planu transportu, który **zaspokoi zapotrzebowanie wszystkich dzielnic** przy **najniższym możliwym koszcie transportu**.
+===== Dane wejściowe =====
+  * Miasto dysponuje **dwiema składnicami** materiału.
+  * Materiał musi być rozwieziony do **czterech dzielnic**.
+  * Każda dzielnica ma określone **zapotrzebowanie na mieszankę (w tonach)**.
+  * Każda składnica ma ograniczoną **maksymalną ilość materiału, jaką może dostarczyć**.
+  * Koszty transportu (w zł/t) różnią się w zależności od trasy (składnica–dzielnica).
+==== Tabela kosztów transportu i zapotrzebowań ====
+^ Dzielnica ^ Składnica 1 (zł/t) ^ Składnica 2 (zł/t) ^ Zapotrzebowanie (t) ^
+| 1         | 2.00              | 4.00              | 300                 |
+| 2         | 3.00              | 3.50              | 450                 |
+| 3         | 1.50              | 2.50              | 500                 |
+| 4         | 2.50              | 3.00              | 350                 |
+==== Pojemności składnic ====
+  * Składnica 1: **900 ton**
+  * Składnica 2: **750 ton**
+===== Zmienne decyzyjne =====
+Niech:
+$x_{ij}$ – ilość ton mieszanki przetransportowanej ze składnicy $i$ do dzielnicy $j$,
+gdzie $i \in \{1, 2\}$ i $j \in \{1, 2, 3, 4\}$.
+===== Funkcja celu =====
+Minimalizacja całkowitego kosztu transportu:
+$$
+Z = \min \sum_{i=1}^{2} \sum_{j=1}^{4} c_{ij} \cdot x_{ij}
+$$
+Gdzie $c_{ij}$ to koszt transportu 1 tony ze składnicy $i$ do dzielnicy $j$.
+===== Ograniczenia =====
+**Pojemności składnic:**
+$$
+x_{11} + x_{12} + x_{13} + x_{14} \leq 900 \\
+x_{21} + x_{22} + x_{23} + x_{24} \leq 750
+$$
+**Zapotrzebowanie dzielnic:**
+$$
+x_{11} + x_{21} = 300 \\
+x_{12} + x_{22} = 450 \\
+x_{13} + x_{23} = 500 \\
+x_{14} + x_{24} = 350
+$$
+**Nieujemność zmiennych:**
+$$
+x_{ij} \geq 0 \quad \text{dla każdego } i, j
+$$
+===== Cel =====
+Wyznaczyć optymalne wartości $x_{ij}$, aby **całkowity koszt transportu był jak najmniejszy**, a jednocześnie spełnione zostały ograniczenia zapotrzebowania i pojemności.
+===== Uwagi =====
+To klasyczny przykład tzw. **problemu transportowego** w programowaniu liniowym. Rozwiązanie można znaleźć m.in. za pomocą:
+  * metody potencjałów (ręcznie lub w arkuszu kalkulacyjnym),
+  * programowania liniowego w Pythonie (np. `PuLP`, `scipy.optimize`),
+  * narzędzi takich jak Excel Solver.
+==== Rozwiązanie w Pythonie (biblioteka `PuLP`) ====
+Python oferuje bibliotekę `PuLP`, która umożliwia tworzenie i rozwiązywanie problemów programowania liniowego.
+=== Przykładowy kod: ===
+<code python>
+import pulp
+# Tworzymy problem minimalizacji kosztów
+problem = pulp.LpProblem("Transport_soli_i_piasku", pulp.LpMinimize)
+# Składnice i dzielnice
+skladnice = [1, 2]
+dzielnice = [1, 2, 3, 4]
+# Koszty transportu c_ij (słownik)
+koszty = {
+    (1, 1): 2.00, (1, 2): 3.00, (1, 3): 1.50, (1, 4): 2.50,
+    (2, 1): 4.00, (2, 2): 3.50, (2, 3): 2.50, (2, 4): 3.00
+}
+# Zapotrzebowania dzielnic
+zapotrzebowanie = {1: 300, 2: 450, 3: 500, 4: 350}
+# Pojemności składnic
+pojemnosc = {1: 900, 2: 750}
+# Zmienne decyzyjne x_ij: ilość materiału z i-tej składnicy do j-tej dzielnicy
+x = pulp.LpVariable.dicts("x", [(i, j) for i in skladnice for j in dzielnice],
+                          lowBound=0, cat='Continuous')
+# Funkcja celu: minimalizacja kosztu transportu
+problem += pulp.lpSum(koszty[i, j] * x[i, j] for i in skladnice for j in dzielnice), "Koszt_calkowity"
+# Ograniczenia pojemności składnic
+for i in skladnice:
+    problem += pulp.lpSum(x[i, j] for j in dzielnice) <= pojemnosc[i], f"Pojemnosc_skladnicy_{i}"
+# Ograniczenia zapotrzebowania dzielnic
+for j in dzielnice:
+    problem += pulp.lpSum(x[i, j] for i in skladnice) == zapotrzebowanie[j], f"Zapotrzebowanie_dzielnicy_{j}"
+# Rozwiązanie problemu
+problem.solve()
+# Wyniki
+print("Status:", pulp.LpStatus[problem.status])
+print("Minimalny koszt transportu:", pulp.value(problem.objective), "zł")
+for i in skladnice:
+    for j in dzielnice:
+        print(f"x({i},{j}) = {x[i, j].varValue} t")
+</code>
+=== Wynik ===
+<code>
+Status: Optimal
+Minimalny koszt transportu: 3925.0 zł
+x(1,1) = 300.0 t
+x(1,2) = 0.0 t
+x(1,3) = 500.0 t
+x(1,4) = 100.0 t
+x(2,1) = 0.0 t
+x(2,2) = 450.0 t
+x(2,3) = 0.0 t
+x(2,4) = 250.0 t
+</code>
+====== Transport truskawek ======
+W sezonie letnim truskawki zbierane przez plantatorów muszą być dostarczone do punktów skupu. Każdy z plantatorów dysponuje określoną ilością truskawek (w tonach), a każdy punkt skupu ma sprecyzowane zapotrzebowanie. Celem jest tak zaplanować transport, aby **pokryć zapotrzebowanie punktów skupu przy minimalnych kosztach transportu**.
+===== Dane wejściowe =====
+**Dostępność truskawek u plantatorów:**
+  * Plantator I: 12 tony
+  * Plantator II: 30 ton
+  * Plantator III: 6 ton
+**Zapotrzebowanie punktów skupu:**
+  * Punkt A: 18 ton
+  * Punkt B: 12 ton
+  * Punkt C: 18 ton
+==== Tabela kosztów transportu (w zł za 1 tonę) ====
+^ Plantator ↓ / Punkt → ^ A  ^ B   ^ C   ^
+| I                     | 80 | 160 | 160 |
+| II                    |240 | 320 |  80 |
+| III                   | 32 | 160 |  32 |
+===== Zmienne decyzyjne =====
+Niech:
+  * $x_{ij}$ – ilość ton truskawek transportowana od plantatora $i$ do punktu skupu $j$
+  gdzie $i \in \{1,2,3\}$ (plantatorzy) i $j \in \{A,B,C\}$ (punkty skupu)
+===== Funkcja celu =====
+Minimalizacja całkowitego kosztu transportu:
+$$
+Z = \min \sum_{i=1}^{3} \sum_{j \in \{A,B,C\}} c_{ij} \cdot x_{ij}
+$$
+Gdzie $c_{ij}$ to koszt transportu 1 tony z plantatora $i$ do punktu skupu $j$.
+===== Ograniczenia =====
+**Dostępność u plantatorów:**
+$$
+x_{1A} + x_{1B} + x_{1C} \leq 24 \\
+x_{2A} + x_{2B} + x_{2C} \leq 30 \\
+x_{3A} + x_{3B} + x_{3C} \leq 6
+$$
+**Zapotrzebowanie punktów skupu:**
+$$
+x_{1A} + x_{2A} + x_{3A} = 18 \\
+x_{1B} + x_{2B} + x_{3B} = 12 \\
+x_{1C} + x_{2C} + x_{3C} = 18
+$$
+**Nieujemność zmiennych:**
+$$
+x_{ij} \geq 0 \quad \text{dla każdego } i,j
+$$
+===== Cel =====
+Wyznaczyć optymalne wartości zmiennych $x_{ij}$, aby:
+  * Całkowity koszt transportu był **najniższy**
+  * Spełnione zostały ograniczenia dostępności i zapotrzebowania
+===== Uwagi =====
+To klasyczny **problem transportowy** możliwy do rozwiązania z użyciem:
+  * **Python + PuLP**
+  * **Excel Solver**
+  * **Metody północno-zachodniego narożnika + metoda potencjałów** (dla zadań ręcznych)
+=== Kod ===
+<code python>
+from pulp import LpProblem, LpVariable, LpMinimize, LpStatus, lpSum, value
+# Model
+model = LpProblem("transport_truskawek", LpMinimize)
+# Plantatorzy i punkty skupu
+plantatorzy = ['P1', 'P2', 'P3']
+punkty_skupu = ['A', 'B', 'C']
+# Koszty transportu (zł/t)
+koszty = {
+    ('P1', 'A'): 80,   ('P1', 'B'): 160, ('P1', 'C'): 160,
+    ('P2', 'A'): 240,  ('P2', 'B'): 320, ('P2', 'C'): 80,
+    ('P3', 'A'): 32,   ('P3', 'B'): 160, ('P3', 'C'): 32
+}
+# Ilość dostępnych truskawek (t)
+dostawy = {'P1': 12, 'P2': 30, 'P3': 6}
+# Zapotrzebowanie punktów skupu (t)
+zapotrzebowanie = {'A': 18, 'B': 12, 'C': 18}
+# Zmienne decyzyjne
+x = {
+    (p, s): LpVariable(f"x_{p}_{s}", lowBound=0)
+    for p in plantatorzy for s in punkty_skupu
+}
+# Funkcja celu: minimalizacja kosztów transportu
+model += lpSum(koszty[p, s] * x[p, s] for p in plantatorzy for s in punkty_skupu), "Koszt_calkowity"
+# Ograniczenia dostępności plantatorów
+for p in plantatorzy:
+    model += lpSum(x[p, s] for s in punkty_skupu) <= dostawy[p], f"Dostawa_{p}"
+# Ograniczenia zapotrzebowania punktów skupu
+for s in punkty_skupu:
+    model += lpSum(x[p, s] for p in plantatorzy) == zapotrzebowanie[s], f"Zapotrzebowanie_{s}"
+# Rozwiązanie
+model.solve()
+# Wyniki
+print("Status:", LpStatus[model.status])
+print("Minimalny koszt transportu (zł):", round(value(model.objective), 2))
+print("\nWielkości dostaw (t):")
+for p in plantatorzy:
+    for s in punkty_skupu:
+        print(f"{p} -> {s}: {round(x[p, s].value(), 2)} t")
+</code>
+=== Wynik: ===
+<code>
+Status: Optimal
+Minimalny koszt transportu (zł): 6432.0
+Wielkości dostaw (t):
+P1 -> A: 0.0 t
+P1 -> B: 12.0 t
+P1 -> C: 0.0 t
+P2 -> A: 12.0 t
+P2 -> B: 0.0 t
+P2 -> C: 18.0 t
+P3 -> A: 6.0 t
+P3 -> B: 0.0 t
+P3 -> C: 0.0 t
+</code>

Kacper's Wiki

Narzędzia użytkownika

Narzędzia witryny

Różnice

Narzędzia strony