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}$ Answer
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}$

Answer

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.

Step-by-Step Solution

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.

Key Concept

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

Question

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Topics

More questions from this topic