Examkin

Soru

Zorluk: OrtaKesme Düzlemi (Gomory) Algoritması

Tam sayılı bir programlama probleminin doğrusal gevşetilmiş (LP relaxation) hali simpleks yöntemiyle çözülmüş ve optimal tablo şu şekilde elde edilmiştir:

Temelx1x_1x2x_2s1s_1s2s_2Çözüm
ZZ001220
x1x_110−5/4-5/41/21/211/411/4
x2x_2013/43/41/41/49/49/4

Bu problemde tüm değişkenlerin tam sayı olması gerektiği bilindiğine göre, tablodaki x1x_1 satırı kullanılarak oluşturulacak Gomory kesme kısıtı (cut constraint) aşağıdakilerden hangisidir? (sgs_g yeni eklenen aylak değişkendir.)

  1. sg−34s1−12s2=−34s_g - \frac{3}{4} s_1 - \frac{1}{2} s_2 = -\frac{3}{4}Cevap
  2. B
    sg+14s1−12s2=−34s_g + \frac{1}{4} s_1 - \frac{1}{2} s_2 = -\frac{3}{4}
  3. C
    sg−34s1−12s2=34s_g - \frac{3}{4} s_1 - \frac{1}{2} s_2 = \frac{3}{4}
  4. D
    sg−54s1+12s2=−114s_g - \frac{5}{4} s_1 + \frac{1}{2} s_2 = -\frac{11}{4}
  5. E
    sg−14s1−12s2=−14s_g - \frac{1}{4} s_1 - \frac{1}{2} s_2 = -\frac{1}{4}

Cevap

sg−34s1−12s2=−34s_g - \frac{3}{4} s_1 - \frac{1}{2} s_2 = -\frac{3}{4} kısıtı doğrudur.
Kesme kısıtı oluşturulurken kullanılan katsayıların [0,1)[0, 1) aralığındaki kesirli kısımları doğru şekilde tespit edilmiştir. −54-\frac{5}{4} değeri −2+34-2 + \frac{3}{4} şeklinde yazıldığında kesirli kısım 34\frac{3}{4} olur. Benzer şekilde 114\frac{11}{4} için 34\frac{3}{4} ve 12\frac{1}{2} için 12\frac{1}{2} değerleri kullanılarak standart formdaki denklem elde edilmiştir.

Adım Adım Çözüm

1
x1x_1 temel değişkeninin bulunduğu satır denklemi yazılır.
x1−54s1+12s2=114x_1 - \frac{5}{4} s_1 + \frac{1}{2} s_2 = \frac{11}{4}
Kesme kısıtı oluşturulacak kaynak satırı belirlemek.
2
Katsayılar ve sağ yan değer, tam sayı (kk) ve 0≤f<10 \leq f < 1 olacak şekilde kesirli kısım (ff) toplamı olarak ayrıştırılır.
RHS: 114=2+34\frac{11}{4} = 2 + \frac{3}{4} (f0=34f_0 = \frac{3}{4}); s1s_1 katsayısı: −54=−2+34-\frac{5}{4} = -2 + \frac{3}{4} (f1=34f_1 = \frac{3}{4}); s2s_2 katsayısı: 12=0+12\frac{1}{2} = 0 + \frac{1}{2} (f2=12f_2 = \frac{1}{2}).
Gomory kesmesi için katsayıların kesirli kısımlarını elde etmek.
3
Gomory kesme eşitsizliği ∑fjxj≥f0\sum f_j x_j \geq f_0 formunda oluşturulur.
34s1+12s2≥34\frac{3}{4} s_1 + \frac{1}{2} s_2 \geq \frac{3}{4}
Temel değişkenin tamsayılık kısıtını ihlal eden bölgeyi budamak.
4
Eşitsizlik, yeni bir aylak değişken (sgs_g) eklenerek standart forma dönüştürülür.
sg−34s1−12s2=−34s_g - \frac{3}{4} s_1 - \frac{1}{2} s_2 = -\frac{3}{4}
Tabloya yeni kısıtı ekleyip Dual Simpleks yöntemiyle çözüme devam etmek.

Anahtar Kavram

Gomory kesme düzlemi algoritmasında, kesirli kısımlar her zaman negatif olmayan (0≤f<10 \leq f < 1) değerler olarak tanımlanır.
Tahmini Süre:2m 0s
Bu soruyu puanla

Konular

Kesme Düzlemi (Gomory) Algoritması

Bu konudan daha fazla soru