DOĞRUSAL PROGRAMLAMA MODELLERİNİN ÇÖZÜMÜ: GRAFİK ÇÖZÜM TEKNİĞİ

Bir doğrusal programlama modelinin tüm kısıtlarını sağlayan her X vektörüne,

X=[X1,X2, … Xj, … Xn] uygun çözüm denir.

Uygun çözümlerin oluşturduğu kümeye, Uygun Çözüm Alanı (UÇA) denir. Uygun Çözün Alanı={X | AX≤b, X≥0 }

Uygun Çözüm Alanı dışbükey(konveks) bir alandır. Dışbükey alanın temel özelliği, bu alan içinde iki nokta ele alınıp bir doğru parçasıyla birleştirildiğinde, birleştiren doğru parçasının tamamının alan kalmasıdır.

Amaç fonksiyonu maksimizasyon (en büyükleme) veya minimizasyon (en küçükleme) yönünde olan bir doğrusal programlama modelinin:

i. Eğer modelin optimum (en iyi) çözümü varsa, bu çözüm Uygun Çözüm Alanının bir köşe noktasındadır.

ii. Amaç fonksiyonu optimum (en iyi) değerini birden çok köşe noktasında alıyorsa, bu noktaların her dışbükey birleşimi de optimum(en iyi) çözümdür.

i. Her bir kısıt eşitlik olarak ele alınıp, karşı gelen doğrunun grafiği çizilerek, kısıtı sağlayan yönü (bölge) işaretlenir. Tüm kısıtları aynı anda sağlayan bölge taranarak “Uygun Çözüm Alanı(UÇA)” olarak belirlenir.

ii. Uygun Çözüm Alanının köşe noktalarında karar değişkenlerinin ve amaç fonksiyonunun değeri hesaplanarak amacı sağlayan köşe, optimum çözüm noktası olarak ilan edilir.

iii. Optimum çözüm seti (amaç fonksiyonu ve karar değişkenlerinin değeri) yazılarak çözüme ulaşılmış olur.

Doğrusal karar modelinin optimum çözümünü bulmak için öncelikle Uygun Çözüm Alanının(UÇA) belirlenmesi gerekmektedir. İlk adımda modelin kısıtlayıcıları olan doğrusal eşitsizliklerin grafiğini çizmek gerekir. Bütün doğrusal programlama modellerinde negatif olmama kısıtlayıcıları (X1, X2≥ 0) bulunduğundan, öncelikle bu kısıtların doyurulması ile başlamak gerekir. Koordinatlar ekseninde, uygun çözüm alanının hangi bölümde yer aldığı belirlenir. Örnek modeldeki X1(Ürün I’den üretilecek miktar) genellikle apsis (yatay) ekseninde, X2(Ürün II’den üretilecek miktar), ordinat (düşey) ekseninde gösterilir.

Uygun Çözüm Alanının sınırları, kısıtlayıcı doğrusal denklemlerle ifade edilen, çizilen doğrusal eşitsizliklerin grafiği ile belirlenir. Karar modelinin tüm kısıtlayıcıları aynı düzlemde(I. Bölge) çizilerek, her bir kısıtın uygun alanları taranırsa, Uygun Çözüm Alanı (UÇA) taranmış bölge olarak ortaya çıkar.

Köşe noktaların X1 ve X2 değerlerini bulmak için, o noktada kesişen doğru denklemleri çözülür. Matematikten hatırlanacağı üzere, iki bilinmeyenli iki denklem çözümü ile X1 ve X2 değerleri kolayca bulunabilir.

Bir doğrusal karar modelinin çözümü, grafik çözüm tekniği ile araştırılırken bazı özel durumlardan birisiyle karşılaşılabilir.

1. Uygun çözüm alanı boş(uygun çözüm bulunmama),

2. Sınırsız Çözüm(amaç fonksiyonu uygun çözüm alanında sınırsız),

3. Seçenekli(çoklu) optimal çözüm. 

Karar modelinin kısıtlarının grafiği çizildiğinde, uygun çözüm alanı oluşmuyor (boş) ise, problemin çözümü yoktur denir. Uygun çözüm bulunmaması, problemin yapısından kaynaklanabileceği gibi, modelleme hataları da (bir kısıtlayıcının yönünün ters olması gibi) uygun çözüm alanının boş olmasına neden olabilmektedir. 

Bazı doğrusal programlama modellerinin amaç fonksiyonu değeri, uygun çözüm alanı üzerinde istenen yönde sonlu değilse, optimum değeri bulunamayacağından, sınırsız çözüm vardır denir. Bu durum karar vericiye hiçbir öneri getiremez. Sınırsız çözümün varlığı, grafik çözümde, grafik üzerinde kolaylıkla görülebilir.

Doğrusal programlama problemleri birden çok optimum çözüme sahip olabilir. Karar modelinin amaç fonksiyonunun optimum değeri, uygun çözüm alanında iki ayrı noktada aynı değeri alıyorsa, modelin seçenekli (alternatif) çözümü vardır denir.

Bir doğrusal programlama problemini matematiksel modelle ifade etmek, en iyi çözümün araştırılmasının yanı sıra, problemin yapısında veya parametrelerde meydana gelebilecek değişiklikleri analiz etme imkanı da sağlar. Problemde iki karar değişkeni var ise, grafik çözümle tüm olası durumlar görülebilmekte ve analizler yapılabilmektedir.

Uygun Çözüm Alanı üzerinde Xj’lere göre, amaç fonksiyonunun maksimum (en büyük) veya minimum (en küçük) değerini aldığı Xj’lere optimum (en iyi) çözüm seti, amaç fonksiyonuna karşı gelen değerine optimum (en iyi) değer denir.

Dışbükey alanın temel özelliği, bu alan içinde iki nokta ele alınıp bir doğru parçasıyla birleştirildiğinde, birleştiren doğru parçasının tamamının alan kalmasıdır. Bir anlamda Uygun Çözüm Alanı kümesindeki herhangi iki nokta çiftini birleştiren doğru parçası, tamamen Uygun Çözüm Alanı kümesinde ise, uygun çözüm alanı dışbükey bir kümedir. Söz konusu doğru parçasının bir kısmını içine almayan küme ise, içbükey (konkav) kümedir.

Uç(köşe) Nokta Teoremi: Grafik üzerinde Uygun Çözüm Alanının (UÇA) farklı iki noktasının dışbükey birleşimi olarak yazılamayan noktası varsa, buna uç nokta veya köşe nokta denir. Düzlemde bir üçgenin, bir karenin köşeleri uç (köşe) noktadır. Şu halde, amaç fonksiyonu maksimizasyon (en büyükleme) veya minimizasyon (en küçükleme) yönünde olan bir doğrusal programlama modelinin:

i. Eğer modelin optimum (en iyi) çözümü varsa, bu çözüm Uygun Çözüm Alanının bir köşe noktasındadır.

ii. Amaç fonksiyonu optimum (en iyi) değerini birden çok köşe noktasında alıyorsa, bu noktaların her dışbükey birleşimi de optimum(en iyi) çözümdür.

X1 + 2X2 ≤ 6

2X1 + X2 ≤ 8

X1 ≥ 7

ve X1, X2 ≥ 0

Grafik çözümde Uygun Çözüm Alanı koordinat sisteminin I. bölgesinde yer alır. 

X1, ve X2 değişkenlerinin çözüm değerlerinin anlamlı olabilmesi için, negatif olmayan değer almaları gerekir. Yani X1≥0 ve X2≥0 koşulları sağlanmalıdır. İlgili üründen üretilecek ise, X1 pozitif bir değer alır; üretilmeyecek ise sıfır değerini alacak demektir. İlgili üründen üretilecek ise, X2 pozitif bir değer alır; üretilmeyecek ise sıfır değerini alacak demektir. Bunun yanında X1≥ 0, yatay eksenin(apsis) üst tarafını, X2≥ 0 düşey eksenin (ordinat) sağ tarafını işaret eder ki, bu da koordinat ekseninin I.Bölgesidir.