Examkin

Soru

Zorluk: ZorSaf Tamsayılı Programlama Modelleri

Saf tamsayılı bir doğrusal programlama probleminin çözümünde Kesme Düzlemi (Gomory) algoritması kullanılmaktadır. Doğrusal programlama gevşetmesinin (LP relaxation) optimal simpleks tablosunda, temel değişkenlerden olan x2x_2'nin bulunduğu satır aşağıdaki denklemi vermektedir:

x2+75x3−34x4=176x_2 + \frac{7}{5}x_3 - \frac{3}{4}x_4 = \frac{17}{6}

Problemdeki tüm değişkenlerin (x1,x2,x3,x4x_1, x_2, x_3, x_4) negatif olmayan tamsayılar olması gerektiğine göre, bu satırdan elde edilecek Gomory kesme düzlemi (kesirli kesme) eşitsizliği aşağıdakilerden hangisidir?

  1. 25x3+14x4≥56\frac{2}{5}x_3 + \frac{1}{4}x_4 \ge \frac{5}{6}Cevap
  2. B
    25x3−34x4≥56\frac{2}{5}x_3 - \frac{3}{4}x_4 \ge \frac{5}{6}
  3. C
    25x3+34x4≥56\frac{2}{5}x_3 + \frac{3}{4}x_4 \ge \frac{5}{6}
  4. D
    75x3−34x4≥56\frac{7}{5}x_3 - \frac{3}{4}x_4 \ge \frac{5}{6}
  5. E
    25x3+14x4≤56\frac{2}{5}x_3 + \frac{1}{4}x_4 \le \frac{5}{6}

Cevap

Gomory kesme düzlemi algoritmasında kesirli kısımlar ayrıştırılarak elde edilen eşitsizlik 25x3+14x4≥56\frac{2}{5}x_3 + \frac{1}{4}x_4 \ge \frac{5}{6} olmalıdır.
Gomory kesme düzlemi oluşturulurken tüm katsayılar aij=⌊aij⌋+fija_{ij} = \lfloor a_{ij} \rfloor + f_{ij} şeklinde tam ve negatif olmayan kesirli kısımlarına ayrılır (0≤fij<10 \le f_{ij} < 1). Burada en çok hata yapılan nokta negatif sayıların kesirli kısmını bulmaktır. −3/4-3/4 sayısının bir alt tam kısmı −1-1'dir, dolayısıyla kesirli kısmı −3/4−(−1)=1/4-3/4 - (-1) = 1/4 olur. 7/57/5'in kesirli kısmı 2/52/5, sağ taraf sabiti olan 17/617/6'nın kesirli kısmı ise 5/65/6'dır. Standart Gomory kesmesi formülü ∑fijxj≥fi\sum f_{ij} x_j \ge f_i şeklindedir. Buna göre doğru eşitsizlik 25x3+14x4≥56\frac{2}{5}x_3 + \frac{1}{4}x_4 \ge \frac{5}{6} olarak bulunur.

Adım Adım Çözüm

1
Verilen denklemdeki katsayıların ve sağ taraf sabitinin kesirli (ff) kısımlarını belirlemek için a=⌊a⌋+fa = \lfloor a \rfloor + f kuralını uygula.
x3x_3 katsayısı: 75=1+25⇒f3=25\frac{7}{5} = 1 + \frac{2}{5} \Rightarrow f_3 = \frac{2}{5}
Gomory kesme düzlemi oluşturulurken değişken katsayıları, tam sayı ve pozitif kesirli kısımlarına ayrılmalıdır.
2
Negatif katsayılı terimin kesirli kısmını belirle.
x4x_4 katsayısı: −34=−1+14⇒f4=14-\frac{3}{4} = -1 + \frac{1}{4} \Rightarrow f_4 = \frac{1}{4}
Matematiksel olarak kesirli kısım daima pozitif olmalıdır (0≤f<10 \le f < 1). Bu nedenle negatif sayılar bir alt tamsayıya yuvarlanarak (burada −1-1) aradaki fark alınır.
3
Sağ taraf sabitinin kesirli kısmını belirle.
Sabit değer: 176=2+56⇒fb=56\frac{17}{6} = 2 + \frac{5}{6} \Rightarrow f_b = \frac{5}{6}
Eşitsizliğin sınır değerini oluşturmak için çözüm değerinin de tamsayı ve kesirli kısımları ayrılır.
4
Elde edilen kesirli kısımları standart Gomory eşitsizlik formülüne (∑fjxj≥fb\sum f_j x_j \ge f_b) yerleştir.
25x3+14x4≥56\frac{2}{5}x_3 + \frac{1}{4}x_4 \ge \frac{5}{6} eşitsizliği elde edilir.
Temel olmayan değişkenlerin kesirli kısımlarının toplamı, sağ taraf sabitinin kesirli kısmına eşit veya ondan büyük olmalıdır ki temel değişken tamsayı değerini alabilsin.

Anahtar Kavram

Gomory Kesme Düzlemi (Kesirli Kesme) Algoritması Formülasyonu
Bu soruyu puanla

Konular

Saf Tamsayılı Programlama Modelleri

Bu konudan daha fazla soru