Różnice

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

--- notatki:badania_operacyjne_teoria [2025/05/16 15:42] – utworzono administrator
+++ notatki:badania_operacyjne_teoria [2025/05/16 17:32] (aktualna) – administrator
@@ Linia 1: / Linia 1: @@
-====== Badania Operacyjne ======
+===== Badania operacyjne: Rozwiązywanie ZPL (zadań programowania liniowego) metodą graficzną =====
-===== Rozwiązywanie ZPL (zadań programowania liniowego) metodą graficzną =====
+Geogebra: {{ :notatki:zpl_graph.ggb |}}
 źródło: [[https://www.maslowski.pl/index.php?id=lekcja3|Malinowski.pl]]
@@ Linia 7: / Linia 7: @@
 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:
-z = 6x1 + 6x2 → max\\
+$$
-x1 + 3x2 ≤ 12\\
+\begin{align*}
-x1 + 2x2 ≤ 16\\
+\text{Maximize} \quad & z = 6x_1 + 6x_2 \\
-x1 ≥ 0, x2 ≥ 0\\
+\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*}
+$$
-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):
+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)
-{{:notatki:pasted:20250516-153357.gif}}
 Następnie numerujemy ograniczenia. Warto to robić, szczególnie w przypadku zadań, gdy liczba ograniczeń jest większa niż 2.
-) 2x1 + 3x2 ≤ 12\\
+$$
-) 4x1 + 2x2 ≤ 16\\
+\begin{align}
+\text{1) } 2x_1 + 3x_2 &\leq 12 \\
+\text{2) } 4x_1 + 2x_2 &\leq 16
+\end{align}
+$$
 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
-x1 + 3x2 = 12\\
+\[
+x_1 + 3x_2 = 12
+\]
 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:
- ≤ 12\\
+\[
+\leq 12
+\]
 Jest to zdanie prawdziwe, zatem punkt (0,0) należy do tej półpłaszczyzny. Półpłaszczyznę zaznaczamy strzałką.
@@ Linia 36: / Linia 49: @@
 Analogicznie sporządzamy wykres ograniczenia 2. Także rysujemy wykres prostej:
-x1 + 2x2 = 16
+\[
+x_1 + 2x_2 = 16
+\]
 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ę.
- ≤ 16
+\[
+ \leq 16
+\]
 Zatem punkt (0,0) należy do tej półpłaszczyzny. Podobnie jak w przypadku ograniczenia 1 półpłaszczyznę zaznaczamy strzałką.
@@ Linia 62: / Linia 81: @@
 Następnie należy narysować prostą prostopadłą do gradientu. Jest to warstwica funkcji celu. Ma ona równanie:
-x1 + 6x2 = c
+\[
+x_1 + 6x_2 = c
+\]
 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).
@@ Linia 70: / Linia 92: @@
 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ń:
-x1 + 3x2 = 12\\
+\[
-x1 + 2x2 = 16\\
+\begin{cases}
+x_1 + 3x_2 = 12 \\
+x_1 + 2x_2 = 16
+\end{cases}
+\]
 W wyniku rozwiązania powyższego układu równań otrzymujemy:
-x1 = 3, x2 = 2
+\[
+x_1 = 3, \quad x_2 = 2
+\]
 Zaznaczamy punkt optymalny na rysunku.
@@ Linia 83: / Linia 113: @@
 Należy jeszcze wyznaczyć wartość funkcji celu w punkcie optymalnym:
-z(3,2) = 3*6+2*6 = 30
+\[
+z(3,2) = 3 \times 6 + 2 \times 6 = 30
+\]
 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 = 2x1 + 6x2 → max
+\[
+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.

Kacper's Wiki

Narzędzia użytkownika

Narzędzia witryny

Różnice

Narzędzia strony