Sadece tamsayı değerler alabilen karar değişkenleriyle kurulan bir doğrusal programlama mo… — KPSS İstatistik

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 ( $Z$ satırı katsayıları) sırasıyla $x_3$ için $2$ , $x_4$ için $3$ ve $x_5$ için $0,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 $x_2$ 'nin satır denklemi aşağıda verilmiştir:

x_2 + 1,5x_3 - 0,8x_4 + 2,1x_5 = 4,6

Çözümün tamsayılı olabilmesi için $x_2$ satırı üzerinden Gomory kesme düzlemi (fractional cut) oluşturulacak ve modele yeni bir kısıt (yeni bir $S_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?

A
$S_g$ temelden çıkar, $x_4$ temele girer.
B
$x_2$ temelden çıkar, $x_3$ temele girer.
$S_g$ temelden çıkar, $x_3$ temele girer.Answer
D
$S_g$ temelden çıkar, $x_5$ temele girer.
E
$x_2$ temelden çıkar, $x_4$ temele girer.

Answer

Çö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.

Step-by-Step Solution

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.

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.

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.

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.

Key Concept

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).

Alternative Method

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.

Estimated Time:2m 0s

Question

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Alternative Method

Topics

More questions from this topic