Kacper's Wiki

Narzędzia użytkownika

Narzędzia witryny

Ślad:
notatki:programowanie_liniowe

Różnice

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

Odnośnik do tego porównania

Poprzednia rewizja po obu stronachPoprzednia wersja
Nowa wersja		Poprzednia wersja
notatki:programowanie_liniowe [2025/05/16 13:34] – administratornotatki:programowanie_liniowe [2025/05/16 19:26] (aktualna) – administrator
Linia 1: Linia 1:
-====== Programowanie Liniowe: ćwiczenia======+====== Badania operacyjne: Programowanie Liniowe ćwiczenia======
  
-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.+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.
  
 ==== Krótka historia ==== ==== Krótka historia ====
Linia 172: Linia 172:
 </code> </code>
  
 +====== Przykład problemu produkcyjnego – Rajstopy ======
  
 +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.
 +
 +==== Treść zadania ====
 +
 +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**.
 +
 +==== Zmienna decyzyjna ====
 +
 +Niech:
 +
 +  * $x$ – liczba par rajstop cienkich,
 +  * $y$ – liczba par rajstop grubych.
 +
 +==== Funkcja celu ====
 +
 +Zakład chce **zmaksymalizować utarg** (czyli całkowity przychód):
 +
 +$$
 +Z = 1.5x + 4y
 +$$
 +
 +==== Ograniczenia ====
 +
 +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
 +$$
 +
 +==== Model matematyczny ====
 +
 +$$
 +\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}
 +$$
 +
 +==== Komentarz ====
 +
 +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.
 +
 +==== 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
 +
 +# 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ł")
 +</code>
 +
 +=== Nagłówek ===
 +
 +<code>
 +Plan produkcji maksymalizujący utarg:
 +Rajstopy cienkie: 0.0 par
 +Rajstopy grube: 10000.0 par
 +Maksymalny utarg: 40000.0 zł
 +</code>
 +
 +====== Przykład problemu produkcyjnego – "Lampy" ======
 +
 +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).
 +
 +==== Dane wejściowe ====
 +
 +^ Tkaniny       ^ Przędzalnia [min] ^ Tkalnia [min] ^ Wykończalnia [min] ^ Zysk jednostkowy [zł] ^
 +| Pościelowe    | 2                 | 1             | 2                   | 5                    |
 +| Sukienkowe    | 1                 | 2             | 2                   | 4.5                  |
 +| Dekoracyjne   | 2                 | 2             | 1                   | 6                    |
 +^ Maksymalny czas pracy maszyn (w godz.) ^ 2400     ^ 3000         ^ 2600               ^                          ^
 +^ Po przeliczeniu na minuty              ^ 144000   ^ 180000       ^ 156000             ^                          ^
 +
 +
 +==== Zmienna decyzyjna ====
 +
 +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**.
 +
 +==== Funkcja celu ====
 +
 +Celem jest **maksymalizacja zysku**:
 +
 +$$
 +Z = 5x + 4.5y + 6z
 +$$
 +
 +==== Ograniczenia czasowe (przeliczone na minuty) ====
 +
 +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
 +$$
 +
 +==== Model matematyczny ====
 +
 +$$
 +\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}
 +$$
 +
 +==== Cel zadania ====
 +
 +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.
 +
 +==== 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
 +
 +# 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ł")
 +</code>
 +
 +=== Wynik ===
 +
 +<code>
 +Optymalny plan produkcji:
 +Tkanina pościelowa:    12000.00 mb
 +Tkanina sukienkowa:    48000.00 mb
 +Tkanina dekoracyjna:   36000.00 mb
 +Maksymalny zysk:       492000.00 zł
 +</code>
 +
 +====== Przykład problemu produkcyjnego – kapelusze ======
 +
 +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ł).
 +
 +==== Treść zadania ====
 +
 +  * **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.**
 +
 +==== Zmienna decyzyjna ====
 +
 +Niech:
 +
 +  * $x$ – liczba produkowanych kapeluszy miesięcznie,
 +  * $y$ – liczba produkowanych beretów miesięcznie.
 +
 +==== Funkcja celu ====
 +
 +Celem jest **maksymalizacja zysku**:
 +
 +$$
 +Z = 3x + 2y
 +$$
 +
 +==== Ograniczenia ====
 +
 +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
 +$$
 +
 +==== Model matematyczny ====
 +
 +$$
 +\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}
 +$$
 +
 +==== Cel zadania ====
 +
 +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.
 +
 +==== 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
 +
 +# 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ł")
 +
 +</code>
 +
 +=== Wynik: ===
 +
 +<code>
 +Optymalny plan produkcji:
 +Kapelusze: 1000 szt.
 +Berety:    900 szt.
 +Maksymalny zysk: 4800.00 zł
 +</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 ====
 +
 +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
 +$$
 +
 +==== Model matematyczny ====
 +
 +$$
 +\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}
 +$$
 +
 +==== 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:
 +$$
 +30x + 10y \geq 180
 +$$
 +
 +  * Dla drugiego pomieszczenia:
 +$$
 +20x + 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>
notatki/programowanie_liniowe.1747395286.txt.gz · ostatnio zmienione: 2025/05/16 13:34 przez administrator

Narzędzia strony

Wszystkie treści w tym wiki, którym nie przyporządkowano licencji, podlegają licencji: GNU Free Documentation License 1.3
GNU Free Documentation License 1.3 Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki