YÖNEYLEM ARAŞTIRMASI I

Bunun yanında X1≥ 0, yatay eksenin(apsis) üst tarafını, X2≥ 0 dikey eksenin (ordinat) sağ tarafını işaret eder ki, bu da koordinat ekseninin I. Bölgesidir.

Uygun çözümlerin oluşturduğu kümeye, Uygun Çözüm Alanı (UÇA) denir.

Uygun Çözüm Alanı dışbükey(konveks) bir alandır.

Grafik çözümde: amaç fonksiyonu ve kısıtlayıcı denklemler birinci dereceden fonksiyonlar olmalıdır.

Değişken ve kısıtlayıcı sayısı itibariyle büyük hacimli modellerin çözümünde etkin teknik olan Simpleks Çözüm Tekniği bir sonraki bölümde ele alınmalıdır.

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.

X1, ve X2 değişkenlerinin çözüm değerlerinin anlamlı olabilmesi için, negatif olmayan değer almaları gerekir.

Karar modelinin kısıtlarının grafiği çizildiğinde, uygun çözüm alanı oluşmuyor (boş) ise, problemin çözümü yoktur denir.

Grafik çözüm tekniği ile genellikle iki karar değişkenli modellerin çözümü mümkün olur. Problemde iki karar değişkeni var ise, grafik çözümle tüm olası durumlar görülebilmekte ve analizler yapılabilmektedir. Uygulamada karşılaşılan problemlerde karar değişkeni ve kısıtlayıcı sayısı ikiden daha çoktur. Özellikle değişken sayısı ikiden çok olduğunda, grafik çözüm etkin bir analiz tekniği olmaz.

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.

Bu sorunun cevabı, A şıkkında verilmiştir. Bir doğrusal karar modeli doğrusal amaç fonksiyonu, doğrusal eşitlik veya eşitsizliklerle verilmiş kısıt fonksiyonları ve karar değişkenleri için olası kısıtlardan oluşuyor.

Soruda verilmiş küme sonsuz bir doğruyu belirtir. Bir doğru, üzerindeki her hangi iki noktayı birleştiren doğru parçasını da içerdiğinden, dışbükey bir kümedir.

Soruda verilen küme, iki boyutlu Kartezyen koordinat sisteminde birinci bölgede yerleşmektedir. Küme, (0, 1/3), (1/2, 0) ve (0,0) noktalarını birleştiren doğru parçalarının sınırladığı bir üçgen olup, dışbükey bir kümedir ve bu noktalar da üçgenin tepe noktaları ve aynı zamanda da uç noktalarıdır.

Doğrusal programlama probleminin uygun çözüm alanı her zaman kapalı (veya açık) yarı uzayların kesişimi şeklinde verildiğinden, ve bu yarı uzaylar her zaman dışbükey küme olduklarından, onların kesişimi de dışbükeydir. a şıkkındaki cevap her zaman doğru olmayabilir, zira bir doğrusal programlama probleminin en iyi çözümler kümesi, iki uç noktayı birleştiren doğru parçası üzerindeki sonsuz sayıda noktayı içerebilir ve bu noktalar da uç nokta olamayabilir. Ayrıca, uygun çözüm alanı boş küme iken hiç bir uç nokta içermez.

Soruda tarif edilen küme, tepe noktaları (-1, 0), (0, 1) ve (1, 0) noktalarında olan bir üçgeni belirtir. Tepe noktaları aynı zamanda bu kümenin uç noktaları olacaktır.

Soruda verilen küme grafik olarak gösterildiğinde, bir tanesi (1, 0) ve (0, 1) noktalarından, diğeri de (-1, 0) ve (0, 1) noktalarından geçen doğruların alt taraflarında kalan yarı uzayların kesişmesinden oluştuğu görülmektedir. Bu yarı uzayların her biri dışbükey olduklarından, onların kesişimi de dışbükey bir küme olacaktır. Bu doğrular tek bir noktada kesiştiğine göre doğal olarak, bu kesişme noktası da bu kümenin tek uç noktası olacaktır.

Bu problemin amaç fonksiyonunu belirleyen z=x1 + x2 doğruları, uygun çözüm alanının bir kenarını belirleyen x1 + x2 =1 doğrusuna paralel olduğundan bu doğrunun uygun çözüm alanı içinde kalan parçasının tamamı bize en iyi çözümler kümesini verecektir. Bu durumda problem sonsuz sayıda optimum çözüme sahip olup, bu çözümler kümesi (0, 1) ve (1, 0) noktalarını birleştiren doğru parçasıdır.

Bu problemin amaç fonksiyonunu tanımlayan x1 + x2 = z doğru denklemlerinin sağ tarafı, uygun çözüm alanı sınırsız bir küme olduğundan, uygun çözüm alanında sınırsız olarak artmaktadır. Bu yüzden problem en iyi çözüme sahip olmamaktadır.

Problemin amaç fonksiyonunu belirleyen x1 + x2 =z doğruları her bir z değeri için, uygun çözüm alanını alttan sınırlayan x1 + x2 = 1 doğrusuna paraleldir. Amaç fonksiyonu minimizasyon şeklinde talep edildiğinden bu doğrunun uygun çözüm alanı içinde kalan parçası, yani (1, 0) ve (0, 1) noktalarını birleştiren doğru parçası üzerindeki bütün noktalar optimum çözümlerdir.

Problemin amaç fonksiyonu minimizasyon şeklinde verildiğinden, bu fonksiyonu belirleyen doğruyu, amaç fonksiyonunun normal vektörü olan (1, 2) vektörünün tersi yönünde, uygun çözüm alanını terk edinceye kadar kaydırırsak, bu doğru uygun çözüm alanını (1, 0) noktasında terk eder.