Saf tam sayılı bir programlama modelinin doğrusal gevşetmesi çözüldüğünde elde edilen opti… — KPSS İstatistik

Saf tam sayılı bir programlama modelinin doğrusal gevşetmesi çözüldüğünde elde edilen optimal simpleks tablosunda $x_1$ temel değişkeninin yer aldığı satır şu şekildedir:

Temel Değişken	$x_1$	$x_2$	$s_1$	$s_2$	Sağ Taraf
$x_1$	$1$	$0$	$7/4$	$-1/2$	$11/4$

Buna göre, Gomory kesme düzlemi algoritması kullanılarak bu satırdan elde edilecek olan kesme kısıtı aşağıdakilerden hangisidir?

$\frac{3}{4} s_1 + \frac{1}{2} s_2 \geq \frac{3}{4}$ Cevap
B
$\frac{3}{4} s_1 - \frac{1}{2} s_2 \geq \frac{3}{4}$
C
$\frac{3}{4} s_1 + \frac{1}{2} s_2 \leq \frac{3}{4}$
D
$\frac{1}{4} s_1 + \frac{1}{2} s_2 \geq \frac{3}{4}$
E
$\frac{3}{4} s_1 + \frac{1}{2} s_2 \geq \frac{1}{4}$

Cevap

Gomory kesme kısıtı

\frac{3}{4} s_1 + \frac{1}{2} s_2 \geq \frac{3}{4}

şeklindedir.

Doğru cevap olan seçenekte,

7/4

katsayısı

1 + 3/4

olarak,

-1/2

katsayısı

-1 + 1/2

olarak ve

11/4

sağ taraf sabiti

2 + 3/4

olarak doğru ayrıştırılmıştır. Gomory kuralına göre

\sum f_j x_j \geq f_0

yapısı uygulandığında

\frac{3}{4} s_1 + \frac{1}{2} s_2 \geq \frac{3}{4}

ifadesine ulaşılır.

Adım Adım Çözüm

Değişken katsayılarını ve sağ taraf sabitini tam sayı (

I

) ve pozitif kesirsel (

f

) kısımlarına ayırın.

7/4 = 1 + 3/4 \rightarrow f_{s1} = 3/4

-1/2 = -1 + 1/2 \rightarrow f_{s2} = 1/2

11/4 = 2 + 3/4 \rightarrow f_{RHS} = 3/4

Gomory kısıtı, denklemin kesirsel kısımlarının toplamının sağ tarafın kesirsel kısmından büyük veya eşit olması kuralına dayanır.

Elde edilen kesirsel kısımları kullanarak kısıt denklemini oluşturun.

3/4 s_1 + 1/2 s_2 \geq 3/4

Değişkenlerin katsayılarının kesirsel kısımları ile çarpımlarının toplamı, sağ tarafın kesirsel kısmına eşit veya ondan büyük olmalıdır.

Anahtar Kavram

Gomory kesme düzlemi algoritmasında kesme kısıtı oluşturulurken, negatif katsayıların kesirsel kısmı belirlenirken katsayıdan küçük veya eşit olan en büyük tam sayı (taban değer) çıkarılmalıdır (

f = a - \lfloor a \rfloor

Soru

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Konular

Bu konudan daha fazla soru