-
Notifications
You must be signed in to change notification settings - Fork 8
/
Copy path2.tex
138 lines (123 loc) · 5.95 KB
/
2.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
\skiptooddpage
\section[A lineáris programozás alapfeladata]{A lineáris programozás
alapfeladata, kétváltozós grafikus megoldás és Fourier-Motzkin elimináció}
Egy egyenlőtlenségrendszer megoldásai közül kiválasztani azt, amely valamilyen
célfüggvény szerint optimális:
\begin{displaymath}
max(cx: Ax \leq b).
\end{displaymath}
Az elemek méretei:
\begin{displaymath}
\begin{bmatrix} 1 & \cdots & n \end{bmatrix}
\begin{bmatrix} 1 \\ \vdots \\ n \end{bmatrix}
:
\begin{bmatrix} 1 & \cdots & n \\ \vdots & \ddots & \vdots \\ m & \cdots & 0 \end{bmatrix}
\begin{bmatrix} 1 \\ \vdots \\ n \end{bmatrix}
\leq
\begin{bmatrix} 1 \\ \vdots \\ m \end{bmatrix}.
\end{displaymath}
Ha az egyenletek, vagy a feladat más alakban van megadva átalakítható az
következő összefüggések alapján:
\begin{align*}
\alpha x \geq \beta \Rightarrow & -\alpha x \leq -\beta \\
\alpha x = \beta \Rightarrow & \begin{cases}
-\alpha x \leq-\beta \\
+\alpha x \leq+\beta \\
\end{cases} \\
min(cx:Ax \leq b) \Rightarrow & max((-c)x:Ax \leq b)
\end{align*}
A minimumos egyenlet megoldása a maximum egyenlet megoldásának az ellentéte
lesz. Ha olyan egyenletünk van, ahol szigorú egyenlőtlenség van ( $<$ vagy $>$)
akkor ezeket elhagyjuk, mert a valós számok halmazán nem tudunk hipersík közeli
értéket keresni. A kérdés amire keressük a válaszokat:
\begin{itemize}
\item Létezik e az $Ax \leq b$ egyenletnek megoldása?
\item $cx$ korlátos e a megoldáshalmazon?
\item Melyik $x$--re maximális a $cx$ kifejezés?
\end{itemize}
\subsection{Kétváltozós feladat grafikus megoldása}
$\alpha x \leq \beta$ egyenlet meghatároz egy félsíkot, amelyet $\alpha x = \beta$
határol. Ha a félsíkok metszete véges, egy konvex sokszöget alkotnak, amely megadja a
megoldás halmazt.
\begin{figure}[htbp]
\centering
\subfigure{\includegraphics[height=6cm]{./kepek/2valtozo_megoldas_rajz.png}
\quad
\subfigure{\includegraphics[height=6cm]{./kepek/2valtozo_megoldas_terulet.png} }}
\caption{Kétváltozós feladat grafikus megoldása} \label{fig:KetValtGraf}
\end{figure}
Ha a célfüggvényt különböző $x$--re felrajzoljuk, meghatározható az optimális
megoldás és az ehhez tartozó $x$ értékek. Egy alternativ megkőzelités, hogy
vesszük a célfügvény irányvektor normálját és ennek irányából pásztázunk végig a
meghatározott konvex sokszögben, a metszőpontok mentén. A megoldást az utolsó
megvizsgált metszőpont adja.
\subsection{Fourier-Motzkin elimináció}
Ennek segítségével megvizsgálhatjuk az egyenlet megoldhatóságát: $n$ változós
egyenletet visszavezetjük $n-1$ változóra, iteratívan, amíg egy egyváltozós
egyenletrendszert nem kapunk; erre könnyű megoldhatóságot vizsgálni. A folyamat:
\begin{enumerate}
\item Minden egyenlet $\alpha \in \mathbb{R}^+$ szorzással az alábbi alakra
hozható:
\begin{displaymath}
\begin{bmatrix}
1 & A_+ \\
-1 & A_- \\
0 & A_0
\end{bmatrix}
\begin{bmatrix}
x_1 &
x'
\end{bmatrix}
\leq
\begin{bmatrix}
b_+ \\
b_- \\
b_0
\end{bmatrix}.
\end{displaymath}
\item
\begin{itemize}
\item Ha $A_-$ üres ($=\emptyset$):
\begin{align*}
1 \cdot x_1 + A_+ x' & \leq b_+ \\
1 \cdot x_1 + \alpha x' & \leq \beta \\
x_1 & \leq \beta - \alpha x'
\end{align*}
Ekkor válasszuk úgy $x_1$--t, olyan kicsire hogy az összes sorra e feltétel
teljesüljön. Ezután $A_+$ teljes sorai elhagyhatóak, továbbá elég $A_0$
sorait vizsgálni, elhagyva a baloldalon található nulla oszlopot ($n-1$
változós eset).
Magyarul mivel nincs alsó korlát, mondhatjuk azt, hogy választunk egy nagyon
kicsi számot, ami biztos jó lesz, és innentől nem foglalkozunk az
egyenlettel.
\item Ha $A_+$ üres ($=\emptyset$):
\begin{align*}
-1 \cdot x_1 + \alpha x' & \leq \beta \\
x_1 & \geq \alpha x' - \beta
\end{align*}
Ekkor válasszuk úgy $x_1$--t, olyan nagyra hogy e feltétel teljesüljön.
Ezután $A_-$ elhagyható.
Az előzőhöz hasonlóan olyan nagyra választjuk, hogy ne kelljen foglalkozni
vele.
\item Ha $A_- \neq \emptyset$ és $A_+ \neq \emptyset$ akkor legyen
$i \in A_-$ egy sora, $j \in A_+$ egy sora, és képezzük az összes sorra az
alábbi összeget (ez exponenciális egyenlet szaporodást jelent, e miatt az
algoritmus futási ideje is exponenciális):
\[
\left( \alpha_i + \alpha_j \right) \cdot x' \leq b_i + b_j
\]
Ezzel visszavezettük a kérdést $n-1$ változós estre.
\end{itemize}
\item Ha $n=1$ és
\begin{align*}
\exists~b_0 < 0 & \Rightarrow \mbox{nem megoldható} \\
\not \exists~A_+ \mbox{ vagy} \not \exists~A_- < 0 & \Rightarrow \mbox{megoldható} \\
\mbox{másképp igaz, hogy } x_1 \leq \beta_+ \mbox{ és } x_1 \geq \beta_-
& \Rightarrow \mbox{megoldható ha } \mbox{max}(-\beta_-) \leq min(\beta_+)
\end{align*}
Magyarul ha az egyenletekben marad $0 x_1 \leq \beta$ $\beta < 0$ formájú,
akkor az egyenletnek nincs megoldása.
Ha $n \geq 1$ folytassuk a $2$--es lépéstől.
\end{enumerate}
A Gauss eliminációval szemben itt csak pozítiv skalárral szorozhatjuk be a sort,
az egyenlőtlenség miatt.