Özel Durumlar (Sınırsızlık, Çoklu Çözüm, Uygunsuzluk, Dejenerelik)

11 soru

Bir maksimizasyon problemi için oluşturulan başlangıç Simpleks tablosu aşağıda verilmiştir:

Temel Değişkenler	$x_1$	$x_2$	$s_1$	$s_2$	Çözüm ( $RHS$ )
$s_1$	$2$	$-3$	$1$	$0$	$10$
$s_2$	$1$	$-1$	$0$	$1$	$20$
$Z_j - C_j$	$-2$	$-5$	$0$	$0$	$0$

Bu tabloya göre, söz konusu doğrusal programlama modelinin çözüm süreci ve sonucu ile ilgili aşağıdakilerden hangisi söylenebilir?

Modelin sınırsız (unbounded) çözümü vardır.

Modelin birden fazla (çoklu) optimal çözümü mevcuttur.

Modelin uygun bir çözüm kümesi yoktur (uygunsuzluk).

Modelde dejenere (yozlaşmış) bir çözüm oluşmuştur.

Tablo optimaldir ve amaç fonksiyonu değeri 0'dır.

Cevabı ve açıklamayı göster

Cevap: Modelin sınırsız (unbounded) çözümü vardır.

Cevap

Modelin sınırsız (unbounded) çözümü vardır; çünkü temele girecek değişkenin katsayıları oran testi yapılmasına izin vermeyecek şekilde negatif değerlerden oluşmaktadır.

Verilen Simpleks tablosunda amaç satırındaki en negatif değer

-5

olup

x_2

değişkenine aittir.

x_2

sütunundaki kısıt katsayıları ise

-3

-1

şeklindedir. Bir maksimizasyon probleminde, temele girmesi gereken bir değişkenin sütununda hiç pozitif katsayı bulunmaması, o değişkenin değerinin sonsuza kadar artırılabileceği ve dolayısıyla amaç fonksiyonunun da sınırsızca büyüyeceği anlamına gelir. Bu durum 'sınırsız çözüm' (unboundedness) olarak tanımlanır.

Adım Adım Çözüm

Temele girecek (anahtar sütun) değişkenin belirlenmesi

x_2

değişkeni temele girmelidir.

Maksimizasyon problemlerinde amaç satırındaki (

Z_j - C_j

) en küçük negatif değer (

-5

) temele girecek değişkeni belirler.

Çıkan değişkenin (anahtar satır) belirlenmesi için oran testi yapılması

Pozitif bir oran elde edilememiştir (

10/(-3)

20/(-1)

Çıkan değişkeni belirlemek için

RHS

değerleri, anahtar sütundaki pozitif katsayılara bölünmelidir. Sütundaki tüm katsayılar

\leq 0

ise bu test yapılamaz.

Özel durumun teşhis edilmesi

Sınırsızlık (Unboundedness) durumu teşhis edilmiştir.

Bir değişken amaç fonksiyonunu iyileştirmek için temele girmek istiyor ancak kısıtlar bu değişkenin artışını sınırlamıyorsa çözüm sınırsızdır.

Anahtar Kavram

Simpleks yönteminde sınırsızlık durumu, temele girmesi beklenen bir değişkenin kısıt sütunundaki tüm değerlerin sıfır veya negatif olmasıyla belirlenir.

Soru 2Soru →

Bir doğrusal programlama modelinin Simpleks algoritması ile çözümü sırasında elde edilen optimal tablo aşağıda verilmiştir. Tabloda $x_1$ ve $x_2$ karar değişkenlerini, $s_1$ ve $s_2$ ise dolgu değişkenlerini temsil etmektedir.

Temel Değişkenler	$x_1$	$x_2$	$s_1$	$s_2$	Çözüm (RHS)
$Z$	$0$	$0$	$0$	$4$	$120$
$x_1$	$1$	$0$	$2$	$-1$	$20$
$x_2$	$0$	$1$	$1$	$3$	$30$

Bu tabloya göre, problemin çözüm kümesinin karakteristiği hakkında aşağıdakilerden hangisi söylenebilir?

Modelin çözüm kümesi boş olup uygun çözüm yoktur.

Amaç fonksiyonu değeri sonsuza gittiği için çözüm sınırsızdır.

Modelin tek bir optimal çözüm noktası bulunmaktadır.

Modelin sonsuz sayıda optimal çözüm noktası mevcuttur.

Sağ taraf değerlerinden biri sıfır olduğu için dejenerelik durumu vardır.

Cevabı ve açıklamayı göster

Cevap: Modelin sonsuz sayıda optimal çözüm noktası mevcuttur.

Cevap

Modelin amaç satırında, temel dışı bir değişken olan dolgu değişkeninin katsayısı sıfır olduğu için modelin sonsuz sayıda optimal çözüm noktası mevcuttur.

Verilen Simpleks tablosunda amaç satırı (

Z

) incelendiğinde, temelde bulunmayan

s_1

dolgu değişkeninin katsayısının

0

olduğu görülmektedir. Optimal bir tabloda (tüm katsayılar

\geq 0

iken) temel dışı bir değişkenin katsayısının sıfır olması, bu değişkenin temele alınabileceğini ancak amaç fonksiyonu değerini (

120

) değiştirmeyeceğini gösterir. Bu durum, modelin tek bir noktada değil, bir doğru parçası veya bölge üzerinde sonsuz sayıda optimal çözüme sahip olduğu anlamına gelir.

Adım Adım Çözüm

Tablodaki temel ve temel dışı değişkenleri belirleme

Temel Değişkenler:

x_1, x_2

; Temel Dışı Değişkenler:

s_1, s_2

Tablonun çözüm yapısını anlamak için hangi değişkenlerin temelde olduğunu saptamak gerekir.

Optimallik kontrolü ve temel dışı değişkenlerin amaç satırı (

Z

) katsayılarını inceleme

Z

satırında

s_1

değişkeninin katsayısı

0

s_2

değişkeninin katsayısı ise

4

'tür.

Optimal bir tabloda, eğer temel dışı bir değişkenin katsayısı

0

ise, bu durum çözümün tek olmadığını gösterir.

Özel durumu teşhis etme

Çoklu Optimal Çözüm (Multiple Optima)

Temel dışı

s_1

değişkeninin

Z

satırındaki katsayısının

0

olması, bu değişkenin temele girmesi durumunda amaç fonksiyonu değerinin değişmeyeceğini, yani başka optimal noktaların da olduğunu gösterir.

Anahtar Kavram

Çoklu Optimal Çözüm Koşulu

Tahmini Süre:1m 30s

Soru 3Soru →

Bir minimizasyon (en küçükleme) problemi için Simpleks algoritması kullanılarak elde edilen ve optimalite koşullarını sağlayan son tablo aşağıda verilmiştir:

Temel Değişkenler	$x_1$	$x_2$	$s_1$	$s_2$	Sağ Yan ( $RHS$ )
$Z$ (Amaç)	$0$	$0$	$-4$	$0$	$120$
$x_1$	$1$	$2$	$0,5$	$0$	$10$
$s_2$	$0$	$1$	$-1$	$1$	$5$

Tablodaki $x_1$ ve $x_2$ karar değişkenlerini, $s_1$ ve $s_2$ ise dolgu/artık değişkenleri temsil etmektedir. Bu tabloya göre, söz konusu doğrusal programlama modelinin çözüm kümesi hakkında aşağıdakilerden hangisi söylenebilir?

Modelin birden fazla (alternatif) optimal çözümü vardır.

Modelin çözüm kümesi sınırsızdır (unbounded).

Modelin uygun bir çözüm kümesi yoktur (uygunsuzluk).

Modelde dejenerelik (yozlaşma) durumu mevcuttur.

Modelin tek bir optimal çözüm noktası vardır.

Cevabı ve açıklamayı göster

Cevap: Modelin birden fazla (alternatif) optimal çözümü vardır.

Cevap

Modelin birden fazla (alternatif) optimal çözümü bulunmaktadır.

Verilen optimal Simpleks tablosunda, temelde yer almayan (non-basic)

x_2

değişkeninin amaç fonksiyonu satırındaki (

Z_j - C_j

) katsayısı

0

olarak görülmektedir. Bir minimizasyon probleminde optimalite sağlandıktan sonra temel dışı bir değişkenin katsayısının

0

olması, o değişkenin çözüme dahil edilmesi durumunda amaç fonksiyonu değerinin değişmeyeceğini ancak değişken değerlerinin değişeceğini gösterir. Bu durum, problemin birden fazla optimal çözüme (alternatif optima) sahip olduğu anlamına gelir.

Adım Adım Çözüm

Problemin tipini ve optimalite durumunu kontrol et.

Problem bir minimizasyon problemidir ve amaç satırındaki (

Z_j - C_j

) tüm değerler

\leq 0

olduğundan tablo optimaldir.

Minimizasyon problemlerinde optimalite için amaç satırı katsayılarının pozitif olmaması gerekir.

Temel ve temel dışı değişkenleri belirle.

Temel değişkenler:

x_1

s_2

. Temel dışı değişkenler:

x_2

s_1

Birim matris sütunlarına sahip olan değişkenler temelde yer alır.

Temel dışı değişkenlerin amaç satırı katsayılarını incele.

Temel dışı olan

x_2

değişkeninin amaç satırındaki katsayısı

0

'dır.

Optimal bir tabloda temel dışı bir değişkenin amaç satırı katsayısının

0

olması, bu değişkenin temele girmesi durumunda amaç fonksiyonu değerinin (Z=120) değişmeyeceğini, dolayısıyla başka bir optimal noktanın daha var olduğunu gösterir.

Anahtar Kavram

Simpleks Yönteminde Çoklu (Alternatif) Optimal Çözüm Analizi

Daha Fazla Pratik

Grafik yöntemde alternatif optimal çözümlerin, amaç fonksiyonu doğrusunun bir kısıt doğrusu ile çakışması (paralel olması) durumunda ortaya çıktığını hatırlayınız.

Tahmini Süre:1m 30s

Soru 4Soru →

Bir kamu kurumunun kaynak tahsis problemini çözmek amacıyla kurulan maksimizasyon (en büyükleme) yönlü doğrusal programlama modelinde, Simpleks algoritmasının bir adımında aşağıdaki ara tablo elde edilmiştir:

Temel Değişkenler	$x_1$	$x_2$	$s_1$	$s_2$	Çözüm (Sağ Yan Değerler)
$s_1$	2	1	1	0	10
$s_2$	4	3	0	1	20
$Z_j - C_j$	-8	-5	0	0	0

Bu tabloda, en yüksek iyileştirme potansiyeline sahip olan $x_1$ değişkeninin temele girmesine karar verilmiştir. Bu seçime bağlı olarak gerçekleştirilecek olan pivot işlemi sonucunda ortaya çıkacak özel durum aşağıdakilerden hangisidir?

Dejenerelik

Sınırsızlık

Uygunsuzluk (Çözümün olmaması)

Çoklu optimal çözüm

Gereksiz (Atıl) kısıt bulunmaması

Cevabı ve açıklamayı göster

Cevap: Dejenerelik

Cevap

Minimum oran testinde eşitlik (bağ) oluştuğu için bir sonraki iterasyonda dejenerelik durumu ortaya çıkar.

Doğrusal programlamada Simpleks yöntemi uygulanırken, temelden çıkacak değişkeni belirlemek için yapılan minimum oran testinde birden fazla satırda aynı minimum değer elde edilirse, bir sonraki iterasyonda temel değişkenlerden biri sıfır değerini alır. Temel değişkenlerden en az birinin sıfır olması durumu 'dejenerelik' (degeneracy) olarak tanımlanır.

Adım Adım Çözüm

Temele girecek değişkenin belirlenmesi

x_1

değişkeni temele girer.

Maksimizasyon probleminde

Z_j - C_j

satırındaki en küçük (en negatif) değer -8'dir.

Temelden çıkacak değişken için minimum oran testinin uygulanması

s_1

için

10 / 2 = 5

;

s_2

için

20 / 4 = 5

Çözüm sütunundaki değerler, temele girecek değişkenin sütunundaki pozitif katsayılara bölünür.

Oran sonuçlarının yorumlanması

Oranlar birbirine eşittir (5 = 5).

Minimum oran testinde bir bağ (tie) olması, bir sonraki çözümde temel değişkenlerden birinin değerinin sıfıra düşeceğini gösterir.

Anahtar Kavram

Dejenerelik (Degeneracy)

Tahmini Süre:1m 30s

Soru 5Soru →

Bir maksimizasyon (en büyükleme) probleminin Simpleks yöntemi ile çözümü sırasında elde edilen bir ara tablo aşağıda verilmiştir:

Temel Değişkenler	$x_1$	$x_2$	$s_1$	$s_2$	Çözüm
$Z$	$-5$	$0$	$3$	$0$	$50$
$x_2$	$-2$	$1$	$1$	$0$	$10$
$s_2$	$-4$	$0$	$2$	$1$	$20$

Bu tabloya göre, modelin çözümüne ilişkin aşağıdakilerden hangisi söylenebilir?

Modelin çözüm kümesi sınırsızdır.

Modelde dejenerelik (yozlaşma) durumu mevcuttur.

Modelin birden fazla (alternatif) optimal çözümü vardır.

Modelin uygun bir çözüm kümesi yoktur (uygunsuzluk).

Mevcut tablo optimal çözümü vermektedir ve

Z

değeri

50

'dir.

Cevabı ve açıklamayı göster

Cevap: Modelin çözüm kümesi sınırsızdır.

Cevap

Modelin çözüm kümesi sınırsızdır çünkü temele girmeye aday değişkenin sütununda pozitif bir katsayı bulunmamaktadır.

Verilen tabloda maksimizasyon yönlü bir problemde

x_1

değişkeninin amaç satırı katsayısı

-5

olduğundan bu değişken temele girmeye adaydır. Ancak

x_1

sütunundaki tüm kısıt katsayıları (

-2

-4

) negatif veya sıfırdır. Bu durum,

x_1

değişkeni artırıldıkça kısıtların daralmak yerine esnediğini ve değişkenin değerinin sonsuza kadar artırılabileceğini gösterir. Dolayısıyla amaç fonksiyonu değeri de sınırsız olarak artacaktır.

Adım Adım Çözüm

Amaç satırındaki katsayıları incele

x_1

değişkeninin katsayısı

-5

olarak belirlenir.

Maksimizasyon probleminde amaç satırında (Z satırı) negatif katsayıya sahip değişkenler, amaç fonksiyonu değerini artırmak için temele girmeye adaydır.

Girecek değişkenin sütun katsayılarını kontrol et

x_1

sütunundaki katsayılar

\{-2, -4\}

'tür.

Temele girecek değişkenin kısıtları ne ölçüde daralttığını belirlemek için katsayıların pozitif olması gerekir.

Oran testini uygula

Pozitif katsayı bulunmadığından oran testi yapılamaz.

Simpleks algoritmasında çıkacak değişkeni belirlemek için yapılan oran testi (Çözüm / Pozitif Katsayı) paydadaki değerlerin

\leq 0

olması durumunda sonuçsuz kalır.

Sonucu yorumla

Sınırsızlık (Unboundedness) durumu teşhis edilir.

Bir değişken amaç fonksiyonunu sonsuza kadar iyileştirebiliyor ve hiçbir kısıt tarafından durdurulamıyorsa (oran testi yapılamıyorsa), çözüm sınırsızdır.

Anahtar Kavram

Simpleks Yönteminde Sınırsızlık Koşulu

Tahmini Süre:1m 30s

Soru 6Soru →

Bir kamu kurumunda hizmet birim maliyetlerini en küçüklemek (minimizasyon) amacıyla oluşturulan doğrusal programlama modelinin Simpleks yöntemi ile çözümünde elde edilen optimal tablo aşağıda sunulmuştur:

Temel Değişkenler	$x_1$	$x_2$	$s_1$	$s_2$	Çözüm ( $b$ )
$x_2$	0	1	2	-1	40
$x_1$	1	0	-1	3	25
$z_j - c_j$	0	0	-6	0	350

Tabloda $x_1, x_2$ karar değişkenlerini; $s_1, s_2$ ise dolgu veya artık değişkenleri ifade etmektedir.

Buna göre, bu tabloya dayalı olarak modelin çözümü hakkında yapılabilecek en doğru değerlendirme aşağıdakilerden hangisidir?

Modelin tek bir optimal çözüm noktası vardır ve amaç fonksiyonunun minimum değeri 350'dir.

Temel dışı olan

s_2

değişkeninin amaç fonksiyonu satırındaki katsayısı sıfır olduğu için modelin alternatif optimal çözümleri mevcuttur.

Çözüm sütunundaki (

b

) tüm değerler pozitif olduğundan, modelde dejenerelik (yozlaşma) durumu söz konusudur.

Amaç fonksiyonu satırındaki katsayıların tamamı sıfır veya negatif olduğu için çözüm kümesi sınırsızdır.

Tabloda yapay değişkenler yer almadığı için modelin başlangıçta uygun bir çözümü bulunmamaktadır.

Cevabı ve açıklamayı göster

Cevap: Temel dışı olan $s_2$ değişkeninin amaç fonksiyonu satırındaki katsayısı sıfır olduğu için modelin alternatif optimal çözümleri mevcuttur.

Cevap

Modelin temel dışı bir değişkeninin (

s_2

) amaç fonksiyonu satırındaki katsayısının sıfır olması nedeniyle alternatif (birden fazla) optimal çözümü bulunmaktadır.

Doğrusal programlama modellerinde, optimal tabloya ulaşıldığında (minimizasyon için

z_j - c_j \leq 0

durumu), eğer temel dışı değişkenlerden en az birinin amaç fonksiyonu satırındaki katsayısı sıfır ise, bu durum modelin alternatif (birden fazla) optimal çözümü olduğunu gösterir. Verilen tabloda temel dışı

s_2

değişkeninin katsayısı 0 olduğundan bu kriter sağlanmaktadır.

Adım Adım Çözüm

Tablodaki temel ve temel dışı değişkenleri belirleyin.

Temel değişkenler

x_1

x_2

; temel dışı değişkenler ise

s_1

s_2

olarak görülmektedir.

Değişkenlerin çözüm üzerindeki etkisini analiz etmek için temel durumlarını bilmek gerekir.

Minimizasyon problemi için optimalite kontrolü yapın.

z_j - c_j

satırındaki tüm değerler 0 veya negatif (0, 0, -6, 0) olduğu için optimalite koşulu sağlanmıştır.

En küçükleme problemlerinde optimal tabloya tüm

z_j - c_j \leq 0

olduğunda ulaşılır.

Özel durumları (alternatif çözüm, dejenerelik vb.) inceleyin.

Temel dışı değişken olan

s_2

için

z_s2 - c_s2 = 0

olduğu görülmektedir. Ayrıca

s_2

sütununda pozitif bir değer (3) olduğu için bu değişken temele girebilir.

Optimal tabloda temel dışı bir değişkenin katsayısının sıfır olması, amaç fonksiyonu değerini bozmadan başka bir köşe noktasına gidilebileceğini (alternatif çözüm) gösterir.

Anahtar Kavram

Alternatif Optimal Çözüm (Multiple Optima)

Daha Fazla Pratik

Dejenerelik durumunu test etmek için çözüm (

b

) sütunundaki değerlerin sıfır olup olmadığını kontrol etmeyi unutmayın.

Tahmini Süre:1m 30s

Soru 7Soru →

Bir maksimizasyon (en büyükleme) problemi için Simpleks algoritması uygulanırken elde edilen bir ara tablo aşağıda verilmiştir:

Temel Değişkenler	$x_1$	$x_2$	$s_1$	$s_2$	Çözüm ( $b$ )
$s_1$	$2$	$-3$	$1$	$0$	$10$
$s_2$	$4$	$-1$	$0$	$1$	$20$
$Z_j - C_j$	$-2$	$-6$	$0$	$0$	$100$

Bu tabloya göre, modelin çözüm süreci ve sonucuyla ilgili aşağıdakilerden hangisi doğrudur?

Modelin sınırsız çözümü (unbounded) vardır.

Modelin çoklu optimal çözümü vardır.

Modelin uygun çözümü yoktur (infeasible).

Modelde dejenere (degenerate) bir çözüm elde edilmiştir.

Mevcut tablo optimaldir ve tek bir çözüm sunar.

Cevabı ve açıklamayı göster

Cevap: Modelin sınırsız çözümü (unbounded) vardır.

Cevap

Modelin sınırsız çözümü (unbounded) vardır çünkü temele girecek değişkenin sütununda sınırlayıcı pozitif bir katsayı bulunmamaktadır.

Maksimizasyon probleminde

Z_j - C_j

satırında en negatif değer olan

-6

değişkeninin (

x_2

) temele girmesi gerekir. Ancak

x_2

sütunundaki tüm katsayılar (

-3

-1

) negatif olduğu için bu değişken kısıtları ihlal etmeden sonsuza kadar artırılabilir. Bu durum, amaç fonksiyonunun da sınırsız artmasına neden olur.

Adım Adım Çözüm

Temele girecek değişkenin belirlenmesi

x_2

değişkeni seçilir.

Maksimizasyon probleminde

Z_j - C_j

satırındaki en küçük (en negatif) değer temele girecek değişkeni belirler (

-6

Oran testinin (

b_i / a_{ij}

) uygulanması

Oran testi yapılamaz.

Anahtar sütun olan

x_2

sütunundaki değerler (

-3

-1

) negatif veya sıfırdır. Oran testi sadece pozitif katsayılar için geçerlidir.

Sonucun yorumlanması

Sınırsız çözüm teşhisi konulur.

Temele girmesi gereken değişkenin artışını sınırlayacak hiçbir kısıt bulunmadığı için amaç fonksiyonu sonsuza gidebilir.

Anahtar Kavram

Sınırsızlık (Unboundedness) Durumu

Tahmini Süre:1m 30s

Soru 8Soru →

Doğrusal programlama problemlerinin Simpleks yöntemi ile çözümünde, optimal tabloya ulaşıldığında temel dışı (karar) değişkenlerinden en az birinin amaç fonksiyonu satırındaki ( $Z_j - C_j$ ) katsayısının sıfır olması durumu aşağıdakilerden hangisini ifade eder?

Problemin birden fazla (çoklu) optimal çözümünün olduğunu

Problemin çözüm kümesinin sınırsız (unbounded) olduğunu

Problemin uygun bir çözümünün bulunmadığını (uygunsuzluk)

Problemin dejenereliğe (bozulmaya) uğradığını

Problemin tek bir benzersiz optimal çözüme sahip olduğunu

Cevabı ve açıklamayı göster

Cevap: Problemin birden fazla (çoklu) optimal çözümünün olduğunu

Cevap

Optimal tabloda temel dışı bir değişkenin amaç fonksiyonu satırı katsayısının sıfır olması, problemin birden fazla (çoklu) optimal çözüme sahip olduğu anlamına gelir.

Optimal tabloda temel değişken olmayan bir değişkenin amaç satırındaki maliyet farkı (

Z_j - C_j

) sıfır ise, bu değişken çözüme dahil edildiğinde amaç fonksiyonunun değeri değişmez ancak değişkenlerin aldığı değerler değişir. Bu durum, problemin sonsuz sayıda optimal çözümü (çoklu çözüm) olduğunu gösterir.

Adım Adım Çözüm

Optimal tablo koşulunu kontrol et.

Tüm

Z_j - C_j \geq 0

(maksimizasyon için) sağlandığında optimal çözüme ulaşılmıştır.

Simpleks yönteminde iyileştirme yapılamayacak noktaya gelindiğini doğrulamak gerekir.

Temel dışı değişkenlerin katsayılarını analiz et.

Temel dışı bir

x_i

değişkeni için

Z_i - C_i = 0

olduğu belirlenmiştir.

Bu durum, bu değişken temele girdiğinde amaç fonksiyonu değerinin (

Z

) değişmeyeceğini gösterir.

Sonucu yorumla.

Değişken değerleri değiştiği halde amaç değeri sabit kalıyorsa, çözüm uzayında aynı optimal değere sahip farklı noktalar mevcuttur.

Bu durumun tanımı çoklu optimal çözümdür.

Anahtar Kavram

Doğrusal programlamada çoklu optimal çözüm, amaç fonksiyonu doğrusunun (veya düzleminin) sınırlandırıcı kısıtlardan biriyle çakışması (paralel olması) durumunda ortaya çıkar.

Daha Fazla Pratik

Dejenerelik durumunda Simpleks algoritmasının sonsuz döngüye (cycling) girme riskini inceleyebilirsiniz.

Tahmini Süre:45s

Soru 9Soru →

Simpleks algoritması kullanılarak çözülen bir doğrusal programlama modelinde, iterasyonlar sırasında ulaşılan bir temel çözümde en az bir temel değişkenin değerinin sıfıra ( $0$ ) eşit olması durumu aşağıdakilerden hangisi ile ifade edilir?

Dejenerelik (Bozulma)

Sınırsızlık (Unboundedness)

Uygunsuzluk (Infeasibility)

Çoklu Optimal Çözüm

Artıklık (Redundancy)

Cevabı ve açıklamayı göster

Cevap: Dejenerelik (Bozulma)

Cevap

Temel değişkenlerden en az birinin değerinin sıfır olması durumu dejenerelik (bozulma) olarak adlandırılır.

Doğrusal programlamada bir temel çözümde yer alan temel değişkenlerden bir veya daha fazlasının sıfır değerini alması durumuna dejenerelik (bozulma) denir. Bu durum genellikle Simpleks yönteminde anahtar satır seçimi için yapılan oran testinde en küçük değerin birden fazla satırda çıkması (beraberlik) sonucu oluşur.

Adım Adım Çözüm

Simpleks tablosundaki temel çözüm değerlerini (sağ taraf sabitlerini) incelemek.

Temel değişkenler sütununda yer alan bir değişkenin karşısındaki çözüm değerinin

0

olduğu tespit edilir.

Özel durumların tespiti için çözüm değerlerinin ve amaç fonksiyonu katsayılarının analizi gereklidir.

Elde edilen bulguyu doğrusal programlama özel durum tanımlarıyla eşleştirmek.

Temel çözümde sıfır değerli değişken bulunması 'Dejenerelik' tanımına karşılık gelir.

Dejenerelik, pivot seçimi sırasında oran testinde bir bağ (eşitlik) oluşması sonucu ortaya çıkan yapısal bir durumdur.

Anahtar Kavram

Dejenerelik (Bozulma) Durumu

Daha Fazla Pratik

Dejenerelik durumunun Simpleks algoritmasında döngüye (cycling) neden olup olmayacağını araştırınız.

Alternatif Yöntem

Grafik yöntemde dejenerelik, ikiden fazla kısıt doğrusunun aynı uç noktada (köşede) kesişmesi olarak gözlemlenebilir.

Tahmini Süre:45s

Soru 10Soru →

Doğrusal programlama problemlerinin Simpleks algoritması ile çözümü sürecinde, bir iterasyondan diğerine geçişte anahtar satırın belirlenmesi amacıyla yapılan oran testi ( $min \{ b_i / a_{ij} \mid a_{ij} > 0 \}$ ) sonucunda, en küçük oran değerinin birden fazla kısıt satırı için aynı olduğu saptanmıştır. Bu durum, bir sonraki iterasyonda elde edilecek temel uygun çözüm ile ilgili aşağıdakilerden hangisine neden olur?

Problemin uygun bir çözümünün bulunmamasına (Uygunsuzluk)

Temel değişkenlerden en az birinin değerinin sıfıra eşit olmasına (Dejenerelik)

Amaç fonksiyonu değerinin sonsuza gitmesine (Sınırsızlık)

Problemin birden fazla alternatif optimal çözüme sahip olmasına

Algoritmanın çözüm sürecinin sonlanarak optimal tabloya ulaşılmasına

Cevabı ve açıklamayı göster

Cevap: Temel değişkenlerden en az birinin değerinin sıfıra eşit olmasına (Dejenerelik)

Cevap

Oran testindeki eşitlik durumu, bir sonraki çözümde en az bir temel değişkenin değerinin sıfır olmasına (dejenerelik) neden olur.

Simpleks yönteminde anahtar satır seçimi için yapılan oran testinde birden fazla satırın aynı minimum değeri vermesi, bir sonraki iterasyonda temel değişkenlerden en az birinin sıfır değerini alacağını gösterir. Bu durum literatürde 'dejenerelik' veya 'bozulma' (degeneracy) olarak adlandırılır.

Adım Adım Çözüm

Oran testinin amacını değerlendir

Oran testi, çözüm kümesinin (uygun bölge) sınırları dışına çıkmadan temelden ayrılacak olan değişkeni (anahtar satır) belirler.

Anahtar satır, uygun çözüm bölgesinin sınırlarını belirleyen kısıtları temsil eder.

Eşitlik (tie) durumunun etkisini incele

Birden fazla satırda aynı minimum oran çıktığında, giren değişken tabana girdiğinde bu satırlardaki tüm değişkenler aynı anda sıfıra ulaşır.

Değişkenlerin değişim hızları (katsayıları) ve mevcut değerleri arasındaki oran aynı olduğu için aynı anda sınır değerine ulaşırlar.

Sonuç aşamasını belirle

Yalnızca bir değişken temelden çıkabilirken, sıfıra düşen diğer değişkenler temel değişken olarak kalmaya devam eder (dejenerelik oluşur).

Temel çözümde sıfır değerli bir değişkenin bulunması, problemin dejenereliğe (bozulmaya) uğradığını tanımlar.

Anahtar Kavram

Simpleks Oran Testi ve Dejenerelik (Bozulma)

Tahmini Süre:45s

Soru 11Soru →

Bir kamu kurumunun lojistik ağındaki dağıtım maliyetlerini en küçükleme (minimizasyon) amacıyla kurduğu doğrusal programlama modelinin Simpleks algoritması ile çözümünde nihai (optimal) tabloya ulaşılmıştır.

Tabloda incelenen değerlere göre şu iki durum tespit edilmiştir:
I. Temel dışı (non-basic) bir karar değişkeninin net değerlendirme satırındaki ( $Z_j - C_j$ ) değeri tam olarak sıfırdır.
II. İlgili temel dışı değişkenin sütununda yer alan tüm yer değiştirme (teknolojik) katsayıları sıfır veya negatiftir ( $\leq 0$ ).

Buna göre, modellenen problem ve elde edilen çözüm durumu hakkında aşağıdakilerden hangisi kesinlikle doğrudur?

Problemin uygun çözüm alanı sınırsızdır, ancak amaç fonksiyonu değeri sınırlıdır ve birbirine eşit amaç fonksiyonu değeri veren sonsuz sayıda alternatif optimal çözüm bulunur.

Problemde amaç fonksiyonunu eksi sonsuza götüren bir sınırsızlık durumu vardır ve problemin herhangi bir optimal çözümü bulunamaz.

Simpleks algoritmasının önceki adımlarında en küçük oran testinde eşitlik çıkmış olup, çözüm dejenereliğe (bozulmaya) uğradığı için iterasyonlar tıkanmıştır.

Kurulan modeldeki kısıtlar birbiriyle çelişmektedir, bu nedenle problemin uygun çözüm alanı boştur ve yapay değişkenler temelden çıkmamıştır.

Uygun çözüm alanı her yönden kapalı (sınırlı) bir dışbükey çokgendir ve problemin yalnızca tek bir köşede gerçekleşen benzersiz (unique) bir optimal çözümü vardır.

Cevabı ve açıklamayı göster

Cevap: Problemin uygun çözüm alanı sınırsızdır, ancak amaç fonksiyonu değeri sınırlıdır ve birbirine eşit amaç fonksiyonu değeri veren sonsuz sayıda alternatif optimal çözüm bulunur.

Cevap

Problemin uygun çözüm alanı sınırsızdır, ancak amaç fonksiyonu değeri sınırlıdır ve birbirine eşit amaç fonksiyonu değeri veren sonsuz sayıda alternatif optimal çözüm bulunur.

Verilen iki durumun birleşimi, yöneylem araştırmasında özel ve ileri düzey bir senaryoyu tanımlar. Optimal bir tabloda temel dışı bir karar değişkeninin net değerlendirme (fırsat maliyeti) değerinin sıfır olması, bu problemin çoklu (alternatif) optimal çözüme sahip olduğunu kanıtlar. Bu değişken temele sokulmak istendiğinde, sütunundaki tüm teknolojik katsayıların sıfır veya negatif olması ise oran testi yapılamayacağını, dolayısıyla o eksen boyunca çözüm alanının sınırsız (açık) olduğunu gösterir. Ancak değişken temele girse bile amaç fonksiyonuna net katkısı sıfır olduğundan, çözüm alanı sonsuza gitmesine rağmen amaç fonksiyonu değeri bozulmaz ve sabit kalır. Matematiksel ve grafiksel olarak bu durum; sınırsız bir uygun çözüm bölgesi üzerinde, amaç fonksiyonu doğrusuna paralel olan ve sonsuza uzanan bir optimal çözümler ışını (ray) elde edildiğini kesin olarak doğrular.

Adım Adım Çözüm

Birinci öncülün (Temel dışı değişken için

Z_j - C_j = 0

) analiz edilmesi.

Problemin alternatif (çoklu) optimal çözümü olduğu tespit edilir.

Optimal bir tabloda temel dışı bir değişkenin amaca katkısının sıfır olması, bu değişkenin temele girmesi halinde amaç fonksiyonu değerinin değişmeyeceğini (mevcut optimal değerin korunacağını) gösterir.

İkinci öncülün (Sütundaki katsayıların

\leq 0

olması) analiz edilmesi.

Uygun çözüm alanının o değişken yönünde sınırsız olduğu tespit edilir.

Temele girecek değişkenin sütununda hiç pozitif katsayı olmaması, Simpleks oran testinin yapılamayacağı ve değişkenin mevcut kısıtları ihlal etmeden sonsuza kadar artırılabileceği anlamına gelir.

İki bilginin sentezlenerek çözümün genel yorumunun yapılması.

Uygun çözüm alanının sınırsız olduğu, ancak bu yönde ilerlerken amaç fonksiyonu değerinin değişmemesi sebebiyle amaç fonksiyonunun sınırlı kaldığı sonucuna varılır.

Değişken sonsuza giderken amaç fonksiyonuna katkısı sıfır olduğundan, amaç değeri sonsuza gitmez. Bu durum, sınırsız bir uygun çözüm alanı içinde, amaç fonksiyonu ile çakışan ve sonsuza uzanan bir 'alternatif optimal çözümler ışını' (ray) oluşturur.

Anahtar Kavram

Özel Durumlarda Çoklu Çözüm ve Sınırsız Alan İlişkisi

Özel Durumlar (Sınırsızlık, Çoklu Çözüm, Uygunsuzluk, Dejenerelik)

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Daha Fazla Pratik

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Daha Fazla Pratik

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Daha Fazla Pratik

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Daha Fazla Pratik

Alternatif Yöntem

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar