Examkin

Soru

Zorluk: ZorKesme Düzlemi (Gomory) Algoritması

Sadece tamsayı değerler alabilen karar değişkenleriyle kurulan bir doğrusal programlama modelinde, maksimizasyon yönlü amaç fonksiyonu hedeflenmektedir. Bu modelin doğrusal gevşetme (LP relaxation) analizi sonucunda ulaşılan optimal tablosunda, temel dışı değişkenlerin indirgenmiş maliyetleri (ZZ satırı katsayıları) sırasıyla x3x_3 için 22, x4x_4 için 33 ve x5x_5 için 0,50,5 olarak hesaplanmıştır.

Optimal tabloda, tamsayılık koşulunu ihlal eden ve en büyük kesirsel kısma sahip olan temel değişken x2x_2'nin satır denklemi aşağıda verilmiştir:

x2+1,5x3−0,8x4+2,1x5=4,6x_2 + 1,5x_3 - 0,8x_4 + 2,1x_5 = 4,6

Çözümün tamsayılı olabilmesi için x2x_2 satırı üzerinden Gomory kesme düzlemi (fractional cut) oluşturulacak ve modele yeni bir kısıt (yeni bir SgS_g aylak değişkeni ile) eklenecektir.

Buna göre, yeni kısıt eklendikten sonra optimum tamsayılı çözüme ulaşmak amacıyla başlatılacak dual simpleks yönteminin ilk adımında, sırasıyla temelden çıkacak ve temele girecek değişkenler hangileridir?

  1. A
    SgS_g temelden çıkar, x4x_4 temele girer.
  2. B
    x2x_2 temelden çıkar, x3x_3 temele girer.
  3. SgS_g temelden çıkar, x3x_3 temele girer.Cevap
  4. D
    SgS_g temelden çıkar, x5x_5 temele girer.
  5. E
    x2x_2 temelden çıkar, x4x_4 temele girer.

Cevap

Çözüm sürecinde temelden çıkacak değişken S_g, temele girecek değişken ise x_3 olmalıdır.
Verilen denklemdeki katsayıların kesirsel kısımları doğru bir şekilde ayrıştırıldığında; -0,8'in kesirsel kısmı 0,2 olarak bulunur. Diğer kesirsel kısımlar 0,5 (x_3 için), 0,1 (x_5 için) ve 0,6 (sağ taraf sabiti) şeklindedir. Kesme düzlemi eşitliğe çevrildiğinde yeni satır 'S_g - 0,5x_3 - 0,2x_4 - 0,1x_5 = -0,6' halini alır. Bu durumda değeri -0,6 olan S_g değişkeni temelden çıkmak zorundadır. Girecek değişkeni bulmak için Z satırı katsayıları ile yeni satırın negatif katsayıları oranlanır (2/0,5=4, 3/0,2=15, 0,5/0,1=5). En küçük oran olan 4, x_3 değişkenine ait olduğu için x_3 temele girer.

Adım Adım Çözüm

1
Verilen denklemdeki tüm katsayıların ve sağ taraf sabitinin kesirsel kısımlarını (f = a - ⌊a⌋) hesapla.
4,6'nın kesirsel kısmı: 0,6
1,5'in kesirsel kısmı: 0,5
-0,8'in kesirsel kısmı: -0,8 - (-1) = 0,2
2,1'in kesirsel kısmı: 0,1
Gomory kesme düzlemi kısıtını oluşturmak için denklemdeki elemanların yalnızca pozitif kesirsel kısımlarına ihtiyaç vardır.
2
Bulunan kesirsel kısımlarla Gomory kısıtını (∑ f_j x_j ≥ f_0) kur ve S_g aylak değişkenini ekleyerek eşitliğe dönüştür.
0,5x_3 + 0,2x_4 + 0,1x_5 ≥ 0,6 eşitsizliği -0,5x_3 - 0,2x_4 - 0,1x_5 ≤ -0,6 formuna getirilir. S_g eklenince: S_g - 0,5x_3 - 0,2x_4 - 0,1x_5 = -0,6 elde edilir.
Dual simpleks yöntemini işletebilmek için kısıtın eşitlik formunda olması ve sağ taraf sabitinin (fizibilite ihlalini göstermek üzere) negatif kalması gerekir.
3
Yeni satır üzerinden temelden çıkacak değişkeni belirle.
S_g değişkeninin aldığı değer -0,6'dır ve negatiflik koşulunu ihlal ettiği için temelden çıkacak değişken S_g olarak belirlenir.
Dual simpleks yönteminde çözüme sağ taraf sabiti negatif olan (fizibil olmayan) temel değişken temelden çıkarılarak başlanır.
4
Temele girecek değişkeni bulmak için negatif katsayılı (a_rj < 0) karar değişkenleri üzerinden oran testini |Z_j / a_rj| uygula.
x_3 oranı: |2 / -0,5| = 4
x_4 oranı: |3 / -0,2| = 15
x_5 oranı: |0,5 / -0,1| = 5
En küçük oran 4 olduğundan temele girecek değişken x_3 olur.
Dual simpleks iterasyonunda amaç fonksiyonunun optimallik koşulunu bozmamak adına oran testi sonucu en küçük olan değişken temele alınır.

Anahtar Kavram

Gomory Kesme Düzlemi kısıtının doğru oluşturulması ve ardından Dual Simpleks Yönteminde pivot eleman seçimi (oran testi).

Alternatif Yöntem

Negatif sayıların kesirsel kısmını zihinden pratik olarak bulmak için, sayının ondalık kısmını 1'e tamamlayan değeri düşünebilirsiniz. Örneğin -0,8 sayısında 0,8'i 1'e tamamlayan değer 0,2'dir. Bu yöntem işlem hızınızı ve doğruluğunuzu artırır.
Tahmini Süre:2m 0s
Bu soruyu puanla

Konular

Kesme Düzlemi (Gomory) Algoritması

Bu konudan daha fazla soru