Örnek 3:
z=x_1+2x_2+3x_3-x_4~~max\\ \downarrow\\ z=-x_1-2x_2-3x_3+x_4~~min
~~x_1+2x_2+3x_3+~~~~~~=15\\ 2x_1+~~x_2+5x_3+~~~~~~=20\\ ~~x_1+2x_2+~~x_3+x_4=10\\
z=-x1-2x_2-3x_3+x_4+\omega x_5+\omega x_6~~~~min
\begin{align*}
x_1+2x_2+3x_3+~~~~~~x_5~~~~~~=15\\
2x_1+~~x_2+5x_3+~~~~~~~~~~~~x_6=20\\
x_1+2x_2+~~x_3+x_4~~~~~~~~~~~~=10\\
\end{align*}
P_3 değişkeni P_6 yerine çözüme giriyor. Bu durumda geçice değişken olan P_6 çözümden çıkıyor.
P_5 değişkeni yerine P_2 değişkeni çözüme giriyor. P_5 değişkeni çözümden çıkıyor.
x_1=5/2\\ x_2=3/2\\ x_3=5/2
x_4=0\\x_5=0\\x_6=0
z=13
Dualite
Her bir lineer programlama probleminin duali olarak ifade edilen bir hâli mevcuttur. Eğer asıl problem maksimum ise duali minimum, asıl problem minimum ise de dualie maksimum olur. Biz simetrik dualle ilgileneceğiz.
💡 Kısıt denklemlerinin hepsi aynı yönde olmalı. Küçük eşitse hepsi küçük eşit olmalı; büyük eşitse hepsi büyük eşit olmalı.
Örnek 1:
z=x_2-3x_3+2x_5~~~~min\\ \downarrow\\ z=0x_1+x_2-3x_3+0x_4+2x_5+0x_6~~~~min
\begin{align*} x_1+3x_2-x_3+2x_5\leq~~7\\ -2x_2+4x_3+x_4\leq12\\ -4x_2+3x_3+8x_5+x_6\leq10\\ \end{align*} kısıt denklemlerini daha düzgün bir biçimde yazalım:
\begin{align*} 1x_1+3x_2-1x_3 +0x_4+2x_5+0x_6\leq~~7\\ 0x_1-2x_2+4x_3 +1x_4+0x_5+0x_6\leq12\\ 0x_1-4x_2+3x_3 +0x_4+8x_5+1x_6\leq10\\ \end{align*}Duali:
\begin{bmatrix}
1 & ~~~3 &-1 & 0 & 2 & 0\\
0 &-2 &~~~4 & 1 & 0 & 0\\
0 &-4 &~~~ 3 & 0 & 8 & 1
\end{bmatrix}^T=
\begin{bmatrix}
~~~1 & ~~~0 & ~~~0\\
~~~3 & -2 & -4\\
-1 & ~~~4 & ~~~3\\
~~~0 & ~~~1 & ~~~0\\
~~~2 & ~~~0 & ~~~8\\
~~~0 & ~~~0 & ~~~1
\end{bmatrix}Amaç fonksiyonumuz katsayıları, daha önceki kısıt denklemlerindeki eşitliğin sağındaki sayılar oldu
g=7y_1+12y_2+10y_3~~~~max
Kısıt fonksiyonlarımız sol tarafı trospozu alınmış matrisin katsayılarından oluşur. eşitsizliğin sağ tarafı ise daha önce z fonksiyonumuzun katsayılarından oluşur.
\begin{align*}
y_1~~~~~~~~~~~~~~~~~~~~~\geq~~~0\\
3y_1-2y_2-4y_3\geq~~~1\\
-y_1+4y_2+3y_3\geq-3\\
y_2~~~~~~~~~~~\geq~~~0\\
2y_1~~~~~~+~~~~~8y_3\geq~~~2\\
y_3\geq~~~0\\
\end{align*}
Leave a Reply