Różnice

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

--- notatki:badania_operacyjne_teoria [2025/05/16 15:05] – utworzono administrator
+++ notatki:badania_operacyjne_teoria [2025/05/16 17:32] (aktualna) – administrator
@@ Linia 1: / Linia 1: @@
-====== Badania operacyjne: teoria ======
+===== Badania operacyjne: Rozwiązywanie ZPL (zadań programowania liniowego) metodą graficzną =====
-====== Wprowadzenie do badań operacyjnych ======
+Geogebra: {{ :notatki:zpl_graph.ggb |}}
-Badania operacyjne (ang. *Operations Research*) to interdyscyplinarna dziedzina nauki zajmująca się tworzeniem i analizą modeli matematycznych wspomagających podejmowanie optymalnych decyzji w złożonych systemach. Powstała w odpowiedzi na potrzeby efektywnego zarządzania zasobami i procesami, zwłaszcza w kontekście militarnym podczas II wojny światowej, a obecnie znajduje zastosowanie w wielu obszarach, takich jak przemysł, logistyka, ekonomia czy zarządzanie.
+źródło: [[https://www.maslowski.pl/index.php?id=lekcja3|Malinowski.pl]]
-Celem badań operacyjnych jest dostarczenie narzędzi umożliwiających:
+Metoda graficzna służy do rozwiązywania tylko takich zadań programowania liniowego, które mają maksymalnie 2 zmienne, gdyż tylko takie można przedstawić w układzie współrzędnych. Oto przykład takiego zadania:
-  * identyfikację i precyzyjne sformułowanie problemów decyzyjnych,
+$$
-  * opracowanie modeli matematycznych odzwierciedlających rzeczywiste sytuacje,
+\begin{align*}
-  * analizę tych modeli w celu znalezienia optymalnych lub zadowalających rozwiązań,
+\text{Maximize} \quad & z = 6x_1 + 6x_2 \\
-  * wdrożenie i monitorowanie wybranych rozwiązań w praktyce.([sylabus.uj.edu.pl][1])
+\text{subject to} \quad
+& 2x_1 + 3x_2 \leq 12 \\
+& 4x_1 + 2x_2 \leq 16 \\
+& x_1 \geq 0,\ x_2 \geq 0
+\end{align*}
+$$
-==== Podstawowe pojęcia ====
+Należy rozpocząć od zaznaczenia w układzie współrzędnych obszaru danego za pomocą ograniczeń. W pierwszym kroku rysujemy układ współrzędnych (należy pamiętać o opisaniu osi oraz o zaznaczeniu skali)
-**Model matematyczny** – uproszczony opis rzeczywistego systemu lub procesu, wyrażony za pomocą równań, nierówności i funkcji celu. Modele te pozwalają na analizę i optymalizację zachowań systemów.
+Następnie numerujemy ograniczenia. Warto to robić, szczególnie w przypadku zadań, gdy liczba ograniczeń jest większa niż 2.
-**Zmienna decyzyjna** – wielkość, której wartość jest ustalana w procesie podejmowania decyzji, np. ilość produkowanych jednostek produktu.
+$$
+\begin{align}
+\text{1) } 2x_1 + 3x_2 &\leq 12 \\
+\text{2) } 4x_1 + 2x_2 &\leq 16
+\end{align}
+$$
-**Funkcja celu** – matematyczne wyrażenie opisujące cel optymalizacji, którym może być maksymalizacja zysku, minimalizacja kosztów, czasu czy ryzyka.
+Rysujemy pierwsze ograniczenie. Obrazem graficznym ograniczenia 1 jest półpłaszczyzna, którą należy narysować następująco:
+Najpierw należy sporządzić wykres prostej
-**Ograniczenia (warunki brzegowe)** – zbiór równań lub nierówności, które określają dopuszczalne wartości zmiennych decyzyjnych, wynikające z dostępnych zasobów, technologii czy innych uwarunkowań.
+\[
+x_1 + 3x_2 = 12
+\]
-**Rozwiązanie dopuszczalne** – zestaw wartości zmiennych decyzyjnych spełniających wszystkie ograniczenia modelu.
-**Rozwiązanie optymalne** – rozwiązanie dopuszczalne, które prowadzi do najlepszego możliwego wyniku funkcji celu.
+Prosta ta przechodzi przez punkty (0,4) i (6,0). Następnie należy zdecydować, po której stronie narysowanej prostej jest właściwa półpłaszczyzna. Decyduje o tym kierunek nierówności. Należy wstawić współrzędne dowolnego punktu do równania półpłaszczyzny i sprawdzić, czy współrzędne tego punktu spełniąją dane ograniczenie. Najprościej jest wstawić współrzędne punktu (0,0). Otrzymujemy wtedy:
-==== Etapy badań operacyjnych ====
+\[
+\leq 12
+\]
-. **Definicja problemu** – dokładne określenie celu analizy i identyfikacja kluczowych elementów systemu.
-. **Budowa modelu** – przekształcenie problemu rzeczywistego w model matematyczny, uwzględniający zmienne decyzyjne, funkcję celu i ograniczenia.
+Jest to zdanie prawdziwe, zatem punkt (0,0) należy do tej półpłaszczyzny. Półpłaszczyznę zaznaczamy strzałką.
-. **Rozwiązanie modelu** – zastosowanie odpowiednich metod matematycznych do znalezienia rozwiązania optymalnego.
+{{:notatki:pasted:20250516-153414.gif}}
-. **Weryfikacja modelu** – sprawdzenie, czy model adekwatnie odzwierciedla rzeczywistość i czy rozwiązanie jest praktycznie wykonalne.
+Analogicznie sporządzamy wykres ograniczenia 2. Także rysujemy wykres prostej:
-. **Implementacja rozwiązania** – wdrożenie wybranego rozwiązania w praktyce i monitorowanie jego efektywności.
+\[
+x_1 + 2x_2 = 16
+\]
-==== Zastosowania badań operacyjnych ====
-Badania operacyjne znajdują zastosowanie w wielu dziedzinach, takich jak:
+Przechodzi ona przez punkty (0,8) i (4,0). Następnie wstawiając do ograniczenia drugiego współrzędne punktu (0,0) znajdujemy właściwą półpłaszczyznę.
-  * **Logistyka i transport** – optymalizacja tras, zarządzanie flotą, planowanie dostaw.
+\[
-  * **Produkcja** – planowanie produkcji, zarządzanie zapasami, harmonogramowanie zadań.
+\leq 16
-  * **Finanse** – optymalizacja portfela inwestycyjnego, zarządzanie ryzykiem.
+\]
-  * **Służba zdrowia** – alokacja zasobów, planowanie personelu, optymalizacja procesów medycznych.
-  * **Zarządzanie projektami** – harmonogramowanie, alokacja zasobów, analiza ścieżki krytycznej.
-==== Literatura ====
-. Węglarz, J. (2009). *Badania operacyjne*. Politechnika Poznańska.([sirius.cs.put.poznan.pl][2])
+Zatem punkt (0,0) należy do tej półpłaszczyzny. Podobnie jak w przypadku ograniczenia 1 półpłaszczyznę zaznaczamy strzałką.
-. Krawczyk, S. (1996). *Badania operacyjne dla menedżerów*. Wydawnictwo Akademii Ekonomicznej we Wrocławiu.([logistyka.net.pl][3])
+{{:notatki:pasted:20250516-153452.gif}}
-. Wikipedia. (n.d.). *Badania operacyjne*. Retrieved from [https://pl.wikipedia.org/wiki/Badania\_operacyjne](https://pl.wikipedia.org/wiki/Badania_operacyjne)
+Pamiętając o ograniczeniach brzegowych, tj. x1 ≥ 0, x2 ≥ 0, zaznaczamy część wspólną wszystkich narysowanych obszarów.
-====== Symbole i wzory matematyczne w badaniach operacyjnych ======
+{{:notatki:pasted:20250516-153518.gif}}
-Badania operacyjne opierają się na precyzyjnym języku matematycznym, który umożliwia modelowanie złożonych problemów decyzyjnych. Poniżej przedstawiono najważniejsze symbole i wzory, które są niezbędne do formułowania i analizowania modeli optymalizacyjnych.
+Zaznaczony obszar nosi nazwę "obszaru rozwiązań dopuszczalnych" (w skrócie "obszaru dopuszczalnego"). Zadanie polega na znalezieniu takiego punktu należącego do tego obszaru, którego współrzędne dają największą wartość funkcji celu. Jest twierdzenie, które mówi, że jeżeli zadanie programowania liniowego ma rozwiązanie skończone, to leży ono w wierzchołku obszaru dopuszczalnego. Zatem, w analizowanym zadaniu, mamy 4 punkty (wierzchołki obszaru dopuszczalnego), w których może być rozwiązanie zadania. Aby uniknąć wyznaczania współrzędnych wszystkich wierzchołków (metoda kłopotliwa szczególnie w zadaniach, w których obszar dopuszczalny ma wiele wierzchołków), należy wyznaczyć gradient funkcji celu.
-==== Symbole podstawowe ====
+Gradient jest to wektor, który wskazuje kierunek najszybszego wzrostu funkcji. Wyznacza się go jako pochodne cząstkowe funkcji po wszystkich współrzędnych. W naszym zadaniu gradient funkcji celu będzie miał następującą postać:
-  * **Zmienne decyzyjne**: \$x\_i\$, \$y\_j\$ – reprezentują ilości, które należy określić w procesie decyzyjnym, np. liczba produktów do wyprodukowania.
+gradz=[6,6]
-  * **Parametry**: \$a\_{ij}\$, \$b\_i\$, \$c\_j\$ – stałe wartości określające cechy modelu, takie jak zużycie zasobów, dostępność czy zyski jednostkowe.
+Wyznaczony gradient, czyli wektor [6,6] należy zaznaczyć na rysunku.
-  * **Funkcja celu**: \$Z\$ – wartość, którą chcemy maksymalizować lub minimalizować, np. zysk, koszt, czas.
+{{:notatki:pasted:20250516-153537.gif}}
-  * **Ograniczenia**: wyrażone w postaci równań lub nierówności, np. \$a\_{11}x\_1 + a\_{12}x\_2 \leq b\_1\$, które definiują dopuszczalny obszar rozwiązań.
+Następnie należy narysować prostą prostopadłą do gradientu. Jest to warstwica funkcji celu. Ma ona równanie:
-==== Operatory matematyczne ====
+\[
+x_1 + 6x_2 = c
+\]
-  * **Dodawanie**: \$+\$ – suma dwóch wyrażeń.
-  * **Odejmowanie**: \$-\$ – różnica między dwoma wyrażeniami.
+gdzie c jest stałą. W zależności od tej stałej możemy przesuwać równolegle warstwicę po rysunku. Aby odnaleźć punkt optymalny, którego współrzędne dają nam największą wartość funkcji celu, należy warstwicę przesuwać równolegle, zgodnie z kierunkiem gradientu, aż do momentu, gdy ta warstwica będzie miała po raz ostatni punkt wspólny z obszarem rozwiązań dopuszczalnych (tak jak na poniższym rysunku).
-  * **Mnożenie**: \$\cdot\$ lub brak symbolu – iloczyn dwóch wyrażeń.([BYJU'S][1])
+{{:notatki:pasted:20250516-153552.gif}}
-  * **Dzielenie**: \$/\$ lub \$\div\$ – iloraz dwóch wyrażeń.
+Przesuwana prosta prostopadła do gradientu (warstwica) ma ostatni raz punkt wspólny z obszarem dopuszczalnym w punkcie przecięcia się prostych 1 i 2. Tam też leży rozwiązanie zadania - punkt optymalny. Znajdujemy go poprzez rozwiązanie następującego układu równań:
-  * **Równość**: \$=\$ – oba wyrażenia mają tę samą wartość.([zssio.com.pl][2])
+\[
+\begin{cases}
+x_1 + 3x_2 = 12 \\
+x_1 + 2x_2 = 16
+\end{cases}
+\]
-  * **Nierówności**: \$\leq\$, \$\geq\$, \$<\$, \$>\$ – relacje porządku między wyrażeniami.
-  * **Suma**: \$\sum\$ – operator sumowania, np. \$\sum\_{i=1}^{n} x\_i\$ oznacza sumę wszystkich \$x\_i\$ od \$i=1\$ do \$n\$.([zssio.com.pl][3], [math.uni.wroc.pl][4])
+W wyniku rozwiązania powyższego układu równań otrzymujemy:
-  * **Iloczyn**: \$\prod\$ – operator mnożenia, np. \$\prod\_{i=1}^{n} x\_i\$ oznacza iloczyn wszystkich \$x\_i\$ od \$i=1\$ do \$n\$.([Smartick][5])
+\[
+x_1 = 3, \quad x_2 = 2
+\]
-\==== Notacja indeksowa ====
-W modelach matematycznych często stosuje się indeksy do oznaczania elementów zbiorów:
-  * \$x\_i\$ – \$i\$-ta zmienna decyzyjna.
-  * \$a\_{ij}\$ – wartość parametru dla \$i\$-tego ograniczenia i \$j\$-tej zmiennej.
-  * \$b\_i\$ – dostępność zasobu w \$i\$-tym ograniczeniu.
-  * \$c\_j\$ – współczynnik funkcji celu dla \$j\$-tej zmiennej.
-\==== Przykładowy model programowania liniowego ====
-**Cel**: Maksymalizacja funkcji celu \$Z\$ przy danych ograniczeniach.
-$$
-\begin{align*}
-\text{Maksymalizuj } & Z = \sum_{j=1}^{n} c_j x_j \\
-\text{przy warunkach: } & \sum_{j=1}^{n} a_{ij} x_j \leq b_i, \quad i = 1, 2, \ldots, m \\
-& x_j \geq 0, \quad j = 1, 2, \ldots, n
-\end{align*}
-$$
-Gdzie:([Medium][6])
-  * \$x\_j\$ – zmienne decyzyjne.
-  * \$c\_j\$ – współczynniki funkcji celu.
-  * \$a\_{ij}\$ – współczynniki ograniczeń.
-  * \$b\_i\$ – dostępne zasoby.
-==== Przykład zastosowania ====
-**Problem**: Firma produkuje dwa produkty: A i B. Zysk jednostkowy wynosi odpowiednio 40 zł i 30 zł. Produkcja jednego produktu A wymaga 2 godzin pracy i 3 jednostek surowca, a produktu B – 1 godziny pracy i 2 jednostek surowca. Dostępne zasoby to 100 godzin pracy i 120 jednostek surowca.
-**Model matematyczny**:([GeeksforGeeks][7])
-$$
-\begin{align*}
-\text{Maksymalizuj } & Z = 40x_1 + 30x_2 \\
-\text{przy warunkach: } & 2x_1 + x_2 \leq 100 \quad \text{(czas pracy)} \\
-& 3x_1 + 2x_2 \leq 120 \quad \text{(surowiec)} \\
-& x_1, x_2 \geq 0
-\end{align*}
-$$
-**Interpretacja**: \$x\_1\$ i \$x\_2\$ oznaczają liczbę wyprodukowanych jednostek produktów A i B. Celem jest maksymalizacja zysku przy ograniczeniach zasobów.
+Zaznaczamy punkt optymalny na rysunku.
-==== Literatura ====
+{{:notatki:pasted:20250516-153612.gif}}
-  * Węglarz, J. (2009). *Badania operacyjne*. Politechnika Poznańska.([mimuw.edu.pl][8])
+Należy jeszcze wyznaczyć wartość funkcji celu w punkcie optymalnym:
-  * Krawczyk, S. (1996). *Badania operacyjne dla menedżerów*. Wydawnictwo Akademii Ekonomicznej we Wrocławiu.
+\[
+z(3,2) = 3 \times 6 + 2 \times 6 = 30
+\]
-  * Wikipedia. (n.d.). *Badania operacyjne*. Retrieved from [https://pl.wikipedia.org/wiki/Badania\_operacyjne](https://pl.wikipedia.org/wiki/Badania_operacyjne)
+Podsumowjąc, pamiętajmy, aby rysunek wykonywać bardzo precyzyjnie, aby "trzymać" skalę, oraz aby za każdym razem rysować gradient i przesuwać prostą prostopadłą do gradientu - warstwicę (nie wolno ulegać optycznym złudzeniom :)). Należy zwrócić uwagę, że to gdzie leży punkt optymalny, zależy od nachylenia gradientu. Dla przykładu, gdyby funkcja celu miała postać:
+\[
+z = 2x_1 + 6x_2 \to \max
+\]
+to gradient byłby wektorem [2,6], a punkt optymalny znalazłby się w punkcie (0,4). Sytuacja taka została przedstawiona na rysunku poniżej.
+{{:notatki:pasted:20250516-153632.gif}}

Kacper's Wiki

Narzędzia użytkownika

Narzędzia witryny

Różnice

Narzędzia strony