Doğrusal Programlama - SIMPLEKS YÖNTEMİNDE ÖZEL DURUMLAR VE DUALİTE

SIMPLEKS YÖNTEMİNDE ÖZEL DURUMLAR
1. Alternatif Çözümler
2. Sınırsız DP
3. Çözümsüzlük
4. Dejenerasyon

Alternatif Optimal Çözümler :

• DP’nin birden fazla optimal çözümü olması durumudur.

• Genellikle eşdeğer doğrusunun sınırlayıcı kısıtlardan birine ait doğru parçası ile kesişmesi sonucu meydana gelir.

Zmaks= 8X1+ 5X2
8/5X1+ X2≤8
X1+ 5/4X2≤6
X1, X2≥0
 

Simpleks tabloda alternatif çözüm durumu Cj-Zjsatırı ve temel sütun araştırılarak anlaşılabilir.Eğer çözümde olmayan bir değişkenin Cj-Zjdeğeri 0 ise, alternatif optimal çözümler vardır.

Zmaks= 8X1+ 5X2 + 0S1+0 S2
8/5X1+ X2 + S1 = 8
X1+ 5/4X2 + S2 = 6
X1, X2 ,S1, S2 ≥0
Başlangıç Simpleks Tablo

İkinci Simpleks Tablo ve Üçüncü Simpleks Tablo :

Sınırsız Çözüm Alanı

• Kimi DP problemlerinde, amaç fonksiyonu maksimizasyon ise amaç fonksiyonu değerinin sonsuza dek arttırılması, minimizasyon problemi ise eksi sonsuza dek azaltılması mümkündür. Bu tip problemlerde uygun çözüm alanı da, amaç fonksiyonu değeri de sınırsızdır.

• Sınırsız çözüm yalnız bir şeyi ifade eder: Model yanlış kurulmuştur. Bunun sebebi varsayımların doğru kurulmaması, kimi kısıtların eksikliği veya model parametrelerinin yanlış tahminlenmesi olabilir(Taha, 1997 pp.103-104).

Zmax= X1 + 2X2
X1 + X2 ≥1
X2 ≤4
X1, X2 ≥0

Sınırsız çözüm simpleks tabloda, çözümden çıkacak değişken belirlenirken farkedilebilir.
Başlangıç Simpleks Tablo

İkinci Simpleks Tablo ve Üçüncü Simpleks Tablo:

Yukarıdaki tabloda görüleceği gibi, optimal çözüme ulaşılmamış olmasına rağmen, çözümden çıkacak değişkeni belirlemek mümkün değildir. Sağ taraf testinde tüm değerler tanımsız veya <0 olduğu için problem sınırsızdır.

Çözümsüzlük

• DP problemlerinde çözümsüzlük uygun çözüm alanının bulunmaması sonucu oluşur.

• Genellikle problemin doğru modellenmemesi sonucu meydana gelir.

Zmaks=3X1 + 2X2
2X1 + X2 ≤2
3X1 + 4X2 ≥12
X1 , X2 ≥0

Çözümsüzlüğün amaç fonksiyonu ile ilgisi yoktur ve simpleks tablo üzerinde temel değişkenler sütunu kontrol edilerek anlaşılabilir. Optimal simpleks tabloda eğer bir yapay değişkenin değeri sıfırdan farklı ise, problem çözümsüzdür.
Zmax= 3X1+ 2X2+ 0S1 +0E1 -MA1
2X1+ X2+ S1 =2
3X1+ 4X2 -E1 + A1 =12
X1, X2 ,E1, A1 , S1≥0
Başlangıç Simpleks:

İkinci tablo:

Çözümsüzlük durumu, genellikle birbiri ile çelişen kısıtların varlığında oluşur.

Dejenerasyon (Bozulma)

• Simpleks çözüm tekniği uygulanırken optimal çözümde temelde yeraland eğişkenlerden en az birinin değerinin 0 olması sonucu ortaya çıkar.

• Genellikle gereksiz bir kısıtın modelde bulunması sonucu meydana gelir.

Zmaks= 3X1+ 9X2
X1+ 4X2≤8
X1+ 2X2≤4
X1, X2≥0

Simpleks yöntemi uygulanırken çözümden çıkacak değişkenin seçiminde minimum  oran kuralında eşitlik olabilir. Birden fazla aynı minimum orana sahip değer varsa çıkan değişken,  bu eşit oranlardan birinin rasgele seçilmesiyle belirlenir.
Problemde böyle bir durum  gerçekleştiğinde bir sonraki iterasyonda bir yada birden fazla taban değişken sıfır değerini alarak tabloda kalacaktır. Bu yeni çözümede jenere çözüm adı verilmektedir. Modelin çözümünün bu şekilde çıkması çok önemli değildir. Kısıtlardan en az birinin fazla olduğu yorumu yapılabilir.
Bozulma hali bazan bir dalgalanma durumuna yol açtığından optimal çözüme ulaşılamaz ve tekrarlamalar olabilir

Standart form:
Zmaks= 3X1+ 9X2 + 0S1+0 S2
X1+ 4X2 + S1 = 8
X1 + 2X2 + S2 = 4
X1, X2 ,S1, S2 ≥0

Başlangıç Simpleks Tablo:

İkinci Simpleks Tablo:

Çözümde olan:x2=2, S2=0
Çözümde olmayan: x1=S1=0
Z=18

Üçüncü Simpleks Tablo:

Çözümde olan:x2=2, x1=0
Çözümde olmayan: S2=S1=0Z=18

DUALİTE

Herhangi bir DP ile ilişkisi olan bir diğer DP dual (eşters) olarak isimlendirilir.  Dual bilgisi ekonomik ve duyarlılık analizi ile ilgili ilginç açıklamalar sağlar. Duali alınan DP primal olarak isimlendirilir. Primal model en büyükleme sorunu ise dual en küçükleme sorunu olur. Bu kuralın tam terside doğrudur.

Bir DP’nin Dualini Bulma

• Normal en büyükleme probleminin duali normal en küçükleme problemidir.

• Normal enbüyüklemeproblemi tümdeğişkenlerin0 veya0’danbüyükolduğuvetümkısıtların≤ olduğubirproblemdir.

• Normal en küçükleme problemi tüm değişkenlerin 0 veya 0’dan büyük olduğuve tüm kısıtların ≥ olduğu bir problemdir.

• Benzer şekilde, normal en küçükleme probleminin dualide normal en büyükleme problemidir

Normal En büyükleme Probleminin Dualini Bulma

Normal En küçükleme Probleminin Dualini Bulma

Normal Olmayan En büyükleme Probleminin Dualini Bulma :

• Eğeri. primal kısıt> kısıtsa, ilgilidual değişkenyi< 0 şeklinde olmalıdır.

• Eğeri. primal kısıt eşitlikse, ilgili dual değişken yi “serbest" (unrestricted in sign -urs) değişkendir.

• Eğeri. primal değişken serbest ise, i. dual kısıt eşitliktir.

Normal En küçükleme Probleminin Dualini Bulma

• Eğeri. primal kısıt ≤ kısıtsa, ilgili dual değişken xi ≤ 0 şeklinde olmalıdır

• Eğeri. primal kısıt eşitlikse, ilgili dual değişken xi “serbest" (urs) değişkendir.

• Eğeri. primal değişken serbest ise, i. dual kısıt eşitliktir

Örnek

• Zmaks= 4x1+ 6x2

2x1+ 4x2=100
4x1–x2≥ 120
3x1+x2≤300
x1serbest, x2≥ 0

• Zmin=2y1+ 5y2 + 8y3

y1+2y2+y3≥ 8
y1 –y3≥ 4
2y1+ 4y3= 160
2y1+y2≤ 40

Ekonomik Yorum

• Primal ve dualin en iyi amaç fonksiyon değerleri eşittir.

• Primal normal en büyükleme sorunu olduğunda, dual değişkenler karar vericiye sağlanabilecek kaynakların değeri ile ilgili olur. Bu yüzden dual değişkenlerden çoğu kez kaynak gölge fiyatları olarak söz edilir

Örnek
Zmaks= 6x1+8x2
30x1+ 20x2≤ 300 (Tahta kısıtı)
5x1+ 10x2≤ 110 (Montajkısıtı)
x1,x2≥ 0
Wmin= 300y1+ 110y2
30y1+ 5y2≥ 6 (Sırakısıtı)
20y1+ 10y2≥ 8 (Masa kısıtı)
y1,y2≥ 0

Çözüm

"http://enm.blogcu.com" dan alıntıdır emek veren elleri dert görmesin :)

Doğrusal Programlama

DOĞRUSAL PROGRAMLAMA


Yöneylem Araştırması modelleri, alternatifler, kısıtlar ve amaç fonksiyonu adı verilen temel elemanlardan oluşur. Karar problemlerinin alternatifleri genelde bilinmeyen değişkenler olarak ortaya çıkar. Bu değişkenler uygun bir matematik model oluşturmak üzere kısıtlar ve amaç fonksiyonu olarak düzenlenir.  Modelin çözümü ile tüm kısıtları sağlayan, aynı zamanda  da amaç  fonksiyonunu optimum (maksimum veya minimum) yapan karar değişkenlerinin değerleri bulunur.
DP, sınırlı kaynakların kullanımını optimum yapmak için geliştirilmiş bir matematiksel modelleme yöntemidir. Bir optimizasyon tekniği olarak belirli ortak özellikleri bulunan problemlere uygulanır. Problemden kaynaklanan bazı özel durumlar dışında tüm DP modelleri üç temel özellik taşır:

Doğrusal amaç fonksiyonu
Doğrusal kısıtlar
Pozitiflik koşulu




Dogrusal amaç fonksiyonu

Tüm organizasyonların varmak istediği bir veya birden çok  amaç vardır. Çoğu organizasyonlar kar maksimizasyonu ya da maliyet minimizasyonunu amaç olarak alırlar. DP modellerinde birçok değişkenin doğrusal fonksiyonundan oluşan bir “amaç fonksiyonu” bulunur.  Bu fonksiyonu Z , değişkenleri x1 , x2 , ………., xn  ve sabit katsayıları da c1 , c2 , ……… cn  ile göstermek üzere;

                             Z =  c1 * x1  + c2 * x2  + ......................... + cn * xn

Şeklinde yazılır. Problemin amacı Z ‘i maksimum veya minimum yapa x değerlerinin bulunmasıdır. Eğer kar maksimizasyonu amaçlanmışsa Z’i maksimum yapan, aksi durumda da maliyet minimizasyonu için Z’ i minimum yapan x değerleri  aranır.

Doğrusal kısıtlar

Bütün doğrusal fonksiyonlar pozitif sonsuzda maksimum, negatif sonsuzda minimum değerini alırlar. Dolayısıyla doğrusal amaç fonksiyonlarının aynı maksimum ve minimuma sahip olduklarını söyleyebiliriz. Matematiksel olarak anlamsız olan bu sonuçtan kaçınmak için değişkenler üzerinde bazı kısıtlamalar yapılmalıdır. Zaten organizasyonların kaynaklarının da sonsuz olmadığı düşünülürse bu kısıtlamaların modelde yer alması normaldir. DP modellerinde kısıtlar, doğrusal eşitsizliklerden meydana gelir.
                       a11 , a12 , ........................., amn 
                        ve
                       b1 , b2 , ..........................., bm 

sabit sayılar olmak üzere kısıtlar :

                       a11 *  x1   +  a12 * x2 + …………………………+   a1n * xn  <=  b1
                                 a21 *  x1     +  a22* x2  + …………………………+ a2n * xn   < = b2
                        ..............................................................
                        .............................................................. 
                      
                       am1 *  x1   +  am2 * x2 + …………………………+   amn * xn  <=  bm 

şeklinde gösterilir. Kısıtlar incelendiğinde şu özellikler göze çarpmaktadır:

Sistemin her satırı genellikle bir eşitsizliktir. Bazı durumlarda eşitlik de olabilir. 
Eşitsizliklerin sol tarafları doğrusal fonksiyonlardır.
Kısıtların sayısı (m ) için bir sınırlama yoktur. 

Kısıtları ifade eden eşitsizlikler , problemin çözümü olabilecek x değişkenlerinin içinde bulunduğu  «çözüm bölgesini» belirler. Sonuçta tüm kısıtları sağlayan optimum(en uygun) çözüm bulunur. 



Pozitiflik koşulu

DP ‘ nin gerçek problemlere uygulanmasını kolaylaştırmak amacı ile çözümde karar değişkenlerinin negatif değer alamayacağı koşulu getirilmiştir. Matematik olarak problem çözüldüğünde  ; 

             x1 , x2 , ………., xn   >= 0 olmalıdır.  




 DP modellerinin formülasyonu değişik şekillerde gösterilmektedir. En yaygın gösterim şekli aşağıda verildiği gibi matris notasyonu kullanılarak formüle etmektir.

Örnek Problem :  XX şirketi, H1 ve H2 hammaddelerinin karışımından iç ve dış duvar boyası üretmektedir. Aşağıdaki tabloda problemin temel verileri gösterilmektedir.

Şirketin yaptığı pazar araştırmasında, günlük iç boya talebinin en fazla 2 ton olduğu görülmüştür. Yine aynı araştırmada, günlük iç boya talebinin günlük dış boya talebinden fazla olduğu ve bu fazlalığın günde en çok 1 ton olduğu anlaşılmıştır. Sirket karını maksimum yapacak şekilde optimum üretim miktarını belirlemek istemektedir. Bu problem bir DP modeli olarak düşünüldüğünde 3 temel elemanı olacaktır:
1. karar değişkenleri
2. amaç fonksiyonu
3. kısıtlar
Modelin  karar değişkenleri iç ve dış boya miktarlarıdır.

x1     -->    dış boyanın günlük üretim miktarını( ton) 
 x2   -->    iç boyanın günlük üretim miktarını( ton )    göstersin. 

Şirket için en iyi amaç toplam karı maksimum yapmaktır. Z toplam karı göstermek üzere;

                               maksimum   Z = 5 * x1   +  4 * x2  
 
Şeklinde yazılabilir.  Modelin son elemanı hammadde ve taleple ilgili sınırlamalardır.
     
                            H1 hammaddesinin kullanımı:

                               6 * x1  + 4 * x2  ton 

                           H2 hammaddesinin kullanımı da: 

                               1* x1  + 2 *x2   tondur.   

Bu hammaddelerin günlük kullanımları sınırlı olduğu için kısıtları şu şekilde yazabiliriz:
                               
                            6 * x1  + 4 * x2   < = 24            H1  hammaddesi için

                            1* x1  + 2 *x2     <=   6             H2 hammaddesi için 



Ayrıca  taleple ilgili sınırlamalar da vardır : 
İç duvar boyası talebinin günde en çok 2 ton olması ;
                                 x2   < =  2
İç boyanın günlük üretiminin dış boyanın üretiminden en çok 1 ton fazla olması;
                                 x2    -    x1    < = 1 
 Modelde yer alan  değişkenlerin negatif olmama (pozitiflik koşulu) sınırlamasını da ekleyerek matematik modeli aşağıdaki gibi yazabiliriz : 
              amaç fonksiyonu :

                         maksimum   Z = 5 * x1   +  4 * x2  

               kısıtlar :
                             6 * x1  + 4 * x2   < = 24
                                   x1  + 2 *x2     <=   6 
                                 -  x1    + x2             < =  1 
                                            x2              < =  2 
              pozitiflik koşulu : 
                                            x1 , x2    > = 0 

Bu kısıtların tümünü sağlayan herhangi bir çözüm uygun çözüm adını alır. 

Grafik çözüm

İki değişkenli bir DP modeli grafik olarak çözülebilir. Grafik yöntemin iki önemli adımı vardır:
Modelin tüm kısıtlarının sağlandığı uygun çözümleri içeren bir çözüm uzayının belirlenmesi,
Çözüm uzayındaki tüm noktalar arasından  optimum çözümün  bulunması.

Yukarıda verilen örneğin  grafik çözümünü yapalım. Kısıtları bir koordinat sisteminde göstermenin en kolay yolu, eşitsizlikleri eşitlik şeklinde düşünerek bunlara ait doğruların çizilmesidir. Daha sonra eşitsizliğin işaretine göre doğrunun altında ya da üstünde kalan bölge çözüm bölgesi olarak seçilir. Birinci kısıtı ele alırsak; 

          6 * x1  + 4 * x2   < = 24   eşitsizliğini 
          6 * x1  + 4 * x2    = 24     şeklinde eşitlik olarak yazalım. 

 Bu doğruyu çizebilmek için iki nokta gerekir.   x1  = 0  için  x2 ‘yi,  x2= 0  için de x1  ‘ i hesaplayabiliriz.  x1  = 0  için    x2= 6 ,  x2  = 0  için    x1 = 4 bulunur. (0,6) ve (4,0) noktalarından geçen doğru aranılan doğrudur. Eşitsizliğin yönü (<= ) şeklinde olduğu için bu doğrunun altında kalan alan bu kısıtı sağlayan alandır.   Tüm kısıtlara ait doğrular çizildikten sonra, çözüm uzayı belirlenir. Aslıda uygun çözüm bölgesi sonsuz sayıda  uygun nokta içerdiği için , bunların arasından optimum noktayı bulmamız gerekir.  
 

Optimum çözümün belirlenmesi için kar fonksiyonunun artış yönünün bilinmesi gerekir.  Bu da Z’e  keyfi değerler atayarak yapılabilir. Z’ e önce 10 sonra 15 değerleri verilerek;

           5 * x1   +  4 * x2     = 10    ve
            5 * x1   +  4 * x2        = 15  doğruları çizilir.

Amaç fonksiyonunun daha artırılması durumunda ABCDEF uygun çözüm uzayının dışına çıkılacaktır. Şekilden çözüm uzayının dışına C noktasından çıkıldığı görülmektedir. Dolayısıyla uygun çözümü içeren nokta C noktasıdır. C noktası 1 ve 2 numaralı kısıtların kesişim noktası olduğu için buradan  x1  = 3 ve  x2= 1.5 bulunur.  Günlük üretimde 3 ton dış boya, 1.5 ton iç boya üretildiğinde günlük kar Z= 21000$ olacaktır.  Optimum çözümün çözüm uzayının komşu köşe noktalarından birinde bulunması raslantı değildir. Amaç fonksiyonunun eğimi değiştirilse bile, yeni çözüm yine köşe noktalarından birinde olacaktır.

Örnek problem: Bir çiftlikte günde en az 800 kg özel bir karışımla yapılan  yem kullanılmaktadır.  Bu karışım, aşağıdaki tabloda verilen maddelerin belirtilen miktarları kullanılarak elde edilmektedir.

Bu ürünün bileşiminde en az %30 protein ve en çok da % 5 lif bulunması zorunludur. Firma minimum maliyetle günlük yem karışımını belirlemek istemektedir. Önce probleme ait matematik modeli kuralım:

Karar değişkenleri:
                                            x1   --->    karışımdaki mısır miktarı (kg)
                                                                    x2    --->    karışımdaki soya unu miktarı(kg) 

           Amaç fonksiyonu:
                                       Minimize  Z = 0.3* x1   + 0.9 * x2    

Kısıtlar:

                                     x1   +   x2  > =  800 ( günlük üretim)   
                                   
                      0.09* x1  + 0.60* x2    > = 0.3 ( x1 +  x2  )   (protein miktarı)

                      0.02 * x1  + 0.06 * x2  < = 0.05(x1 + x2 )    ( lif miktarı)

Kısıtları ve amaç fonksiyonunu yeniden yazalım:

                                       Minimize  Z = 0.3* x1   + 0.9 * x2    
                                    x1   +   x2  > =  800                                        
                      0.21* x1  - 0.30* x2    < = 0
                      0.03* x1  - 0.01 * x2   >=  0 
                                            x1 , x2    > = 0    
 

optimum noktada değişkenlerin değerleri:

x1    = 470.59 kg
x2   = 329.42 kg   
Amaç fonksiyonu: Z = 437.65 $

SİMPLEKS YÖNTEMİ

Bir doğrusal programlama modelini çözmek üzere geliştirilmiş , optimum çözümü iterasyon (ardışık yaklaşım) yoluyla bulan matematiksel bir yöntemdir. Probleme ait matematik model kurulduktan sonra, ilk  adım modeli standart DP modeli şekline getirmektir. Standart bir DP modelinde eşitsizlikler eşitlik şekline dönüştürülmelidir.

Eşitsizliklerin eşitlik haline getirilmesi

Bir DP modelinde <= yönündeki bir kısıtı eşitlik haline getirmek için eşitsizliğin sol tarafına bir artık (slack) değişken eklenir. 
                            x1   + 3* x2    <= 4
eşitsizliği,
                             x1   + 3* x2  + S1  = 4
eşitliği ile aynı anlamdadır.  S1  >= 0 olup, artık değişken adını alır.
Eşitsizliğin yönü >= yönünde ise  artık değişken eklemek yerine çıkarmak gerekir. Ancak bu durumda da değişkenin negatif olmasından ötürü başlangıç çözümünde yer alamaz. Bunun için bu tür  kısıtlarda bir de yapay(artificial) değişken eklenir.
                            x1   + 2* x2    >= 6
eşitsizliği,
                            x1   + 2* x2  - S1  + A1    = 6
şeklinde eşitlik haline getirilir. Bazı modellerde  de sadece = şeklinde kısıtlar da yer alabilir. Bu durumda da eşitsizliğin sol tarafına bir yapay değişken eklenir.
            
                             2*x1    + 3* x2    = 10
eşitsizliği,
                             2* x1   + 3* x2   + A1    = 10
eşitlik haline getirilir.

Bir eşitliğin sağ tarafı mutlaka negatif olmama koşuluna uygun olmalıdır. Gerekirse bu koşulu sağlamak için eşitsizliğin her iki tarafı  –1 ile çarpılır ve eşitsizliğin yönü de değiştirilir.

Simpleks algoritması  

Simpleks algoritması uygun bir temel çözümle başlar ve daha sonra amaç fonksiyonunun daha da iyileştirildiği başka uygun çözümlerle devam eder. İlk uygun çözüm için probleme eklenen artık ve yapay değişkenlerden yararlanılır. Problemin karar değişkenleri (x1 , x2 , ………., xn  )   başlangıçta sıfır değerini alırken , artık (S ) ve yapay (A ) değişkenler sağ taraf değerlerine eşitlenir. Şimdi bir örnek problem ele alarak algoritmayı adım adım uygulayalım.

Örnek problem: Yüksek kaliteli cam ürünleri üreten bir firmanın üretimini gerçekleştirdiği 3 atölyesi mevcuttur.1. atölyede aliminyum çerçeve ve bağlantıları,2. atölyede ağaç çerçeve , 3. atölyede de cam üretilerek, kapı ve pencere    ürünleri yapılmaktadır. Kazançlarındaki azalmadan dolayı üst kademe yönetimi üretim hattını yenilemek istemektedir. Kar getirmeyen bazı ürünler üretilmeyecek, buna karşılık talebi olan bir veya 2 yeni ürün, üretim kapasitesinin izin verdiği ölçüde üretilecektir.Yeni ürün olarak aliminyum çerçeveli kapı ve çift camlı ağaç çerçeveli pencere üretilmesi kararlaştırılıyor. Pazarlama departmanı elde mevcut kapasite ile üretilecek bu ürünlerin satılacağını garanti etmektedir. Atölyelerden elde edilen bilgiler aşağıdaki tabloda verilmektedir:

"http://enm.blogcu.com" dan alıntıdır emekleri için kendisine çok çok teşekkürler :)