Table of Contents

Grafik Yöntemi

Örnek 1:

Amaç fonksiyonu:

z=3x_1+2x_2

Kısıt denklemleri:

x_1+2x_2\geq0\\ x_1+3x_2\leq6

Kısıt denklemlerini koordinat düzleminde gösterelim

İki doğru arasında kalan ve 1. bölgeden kalan taralı bölge bizim çözüm kümemizi verir. Bu alanın köşe noktalarından 1 tanesi maksimumum çözümü vermekte, başka bir köşe noktası ise minimum çözümü vermektedir.

(0,0) noktası minimum çözümü
(6,0) noktası maksimum çözümü verecektir.

Örnek 2

Amaç fonksiyonu:

z=x_1+2x_2\ \ max

Kısıt denklemleri:

x_1+3x_2\leq3\\ 2x_1+x_2\leq2\\ 3x_1+x_2\leq3\\

Kısıt denklemlerinin taradığı alan

Yukarıdaki taralı alanın köşelerinden 1 tane maksimumu 1 tanesi ise minimum değeri verir.

Ödev

Grafik yöntemi gerçekleştiren bir program yazınız. Bir adet lineer programlama denklem setini kodun içerisinde tanımlamanız yeterlidir. Ancak çözümünüz genel olmalıdır. Koordinat sistemi, doğrular, doğrular arasında kalan taralı bölgeyi göstermeniz gereklidir. Programınız olası tüm çözüm noktalarını bulmalı ve denklem sistemini minimum ve maksimum yapan noktaları da göstermelidir. İstenilen platformda yapılabilir. Ancak MATLAB(vb. program) kullanılmayacaktır.

Teslim Tarihi: 23 Kasım 2020

Simplex Yöntemi

Çözüm için öncelikle tüm eşitsizlikler, eşitlik haline dönüştürülür.

Kısıt denklemleri küçük eşittir ise:

z=c_1x_1+c_2x_2+c_3x_3

a_{11}x_1+a_{12}x_2+a_{13}x_3\leq b_1\\ a_{21}x_1+a_{22}x_2+a_{23}x_3\leq b_2\\ a_{31}x_1+a_{32}x_2+a_{33}x_3\leq b_3\\

\begin{align*} &a_{11}x_1+a_{12}x_2+a_{13}x_3+x_4~~~~~~~~~~~~= b_1\\ &a_{21}x_1+a_{22}x_2+a_{23}x_3+x_5= b_2\\ &a_{31}x_1+a_{32}x_2+a_{33}x_3+~~~~~~~~~~~~x_6 = b_3\\ \end{align*}

z=c_1x_1+c_2x_2+c_3x_3+0x_4+0x_5+0x_6

Kısıt denklemleri büyük eşittir ise:

z=c_1x_1+c_2x_2+c_3x_3

a_{11}x_1+a_{12}x_2+a_{13}x_3\geq b_1\\ a_{21}x_1+a_{22}x_2+a_{23}x_3\geq b_2\\ a_{31}x_1+a_{32}x_2+a_{33}x_3\geq b_3\\

\begin{align*} &a_{11}x_1+a_{12}x_2+a_{13}x_3-x_4~~~~~~~~~~~~+x_7~~~~~~~~~~~~= b_1\\ &a_{21}x_1+a_{22}x_2+a_{23}x_3~~~~~~-x_5~~~~~~~~~~~~+x_8~~~~~~= b_2\\ &a_{31}x_1+a_{32}x_2+a_{33}x_3~~~~~~~~~~~~-x_6~~~~~~~~~~~~+x_9 = b_3\\ \end{align*}

z=c_1x_1+c_2x_2+c_3x_3+0x_4+0x_5+0x_6+\omega x_7+\omega x_8+\omega x_9

💡 Denklemleri eşitlik haline getirmek için eklediğimiz değişkenlerin katsayıları 0’dır. Birim matrix oluşturmak için eklediğimiz değişkenlerin katsayıları omega’dır.

💡 Birim matrix oluşturmak için eklediğimiz değişkenler geçici değişkenlerdir ve geçici değişkenler simplex yönteminde çözüm esnasında çözümden çıkartılır.

z=c_1x_1+c_2x_2+c_3x_3

a_{11}x_1+a_{12}x_2+a_{13}x_3\leq b_1\\ a_{21}x_1+a_{22}x_2+a_{23}x_3\geq b_2\\ a_{31}x_1+a_{32}x_2+a_{33}x_3= b_3\\

\begin{align*} &a_{11}x_1+a_{12}x_2+a_{13}x_3+x_4~~~~~~~~~~~~~~~~~~~~~~~~= b_1\\ &a_{21}x_1+a_{22}x_2+a_{23}x_3~~~~~~-x_5+x_6~~~~~~~~~= b_2\\ &a_{31}x_1+a_{32}x_2+a_{33}x_3~~~~~~~~~~~~~~~~~~~~~~~~+x_7= b_3\\ \end{align*}

z=c_1x_1+c_2x_2+c_3x_3+0x_4+0x_5+\omega x_6+\omega x_7

Örnek 1:

z=2x_1+3x_2~~~~min

4x_1+2x_2\leq5\\ 3x_1+~~x_2\leq7

Çözüm:

Öncelikle eşitsizlikleri, eşitliğe çeviriyoruz

4x_1+2x_2+x_3~~~~~~=5\\ 3x_1+x_2~~~~+x_4=7

yukarıdaki kısıt denklemlerini şu şekilde de yazabilirdik

4x_1+2x_2+1x_3+0x_4=5\\ 3x_1+1x_2+0x_3+1x_4=7

Amaç fonksiyonumuzu yeniden yazalım:

z=2x_1+3x_2+0x_3+0x_4~~~~min

Şimdi elimizdeki bu verilerden tablo oluşturacağız:

En üsteki satır z denkleminin katsayılarıdır.
$P_0$ Kısıt denklemlerinin sonuçlarıdır. (denklemin sağ tarafı)
$P_1, P_2, P_3, P_4$ Kısıt denklemlerinin katsayılarıdır.
Baz olarak birim matrisi oluşturan $P_3, P_4$ seçtik.
$C_{Baz}$ sütunu $P_3$ ve $P_4$ ün z denklemindeki katsayıları.

Sonuç satırını hesaplamak için $C_{Baz}$ sütunu ile sırasıyla $P_1, P_2, P_3, P_4$ sütunlarını çarpıp z’nin katsayılarından çıkartıyoruz.

\begin{align*} &0*4+0*3-2=-2\\ &0*2+0*1-3=-2\\ &0*1+0*0-0=0\\ &0*0+0*1-0=0 \end{align*}

Sonuç satırının tümü 0 dan küçük veya 0’a eşit ise çözüm optimaldir. Böyle bir durumda Baz sütununda hangi değişkenler varsa o değişkenlerin katsayıları bellidir ve $P_0$ a eşittir. Bu durumda

x_3=5\\ x_4=7

💡 Geride kalan değişkenleri 0 kabul ediyoruz.

x_1=0\\x_2=0

Bu durumda amaç fonksiyonumuzun sonucu:

z=0

Örnek 2:

z=2x_1+3x_2~~max

4x_1+2x_2\leq5\\ 3x_1+x_2\leq7

💡 Simplex yönteminde amaç fonksiyonumuz max ise min’e çeviririz.

z=2x_1+3x_2~~max\\\downarrow\\z=-2x_1-3x_2~~min

Yeni durumda:

z=-2x_1-3x_2+0x_3+0x_4~~min

4x_1+2x_2+x_3~~~~~~=5\\ 3x_1+~~x_2+~~~~~~x_4=7

Elimizdeki bu denklemlerden tablo oluşturursak.

Sonuç satırımızdaki tüm değerler ≤0 olmadığından dolayı bu çözüm optimal değildir. Böyle bir durumda sonuç satırındaki en yüksek değere sahip olan sütünu seçiyoruz.