Examkin

Tamsayılı Programlama

73 soru

Soru 61Soru →

Bir kamu hastanesi, laboratuvarlarında kullanılmak üzere özel bir dezenfektan çözeltisinin kendi tesislerinde üretimine geçip geçmeme kararı alacaktır.

- Hastane bu çözeltiyi üretmeye karar verirse, kimyasal reaksiyon stabilitesi gereği ayda en az 500500 litre, tesis kapasitesi gereği ise en fazla 20002000 litre üretim yapmak zorundadır.
- Üretim yapılmaması kararı alınırsa, üretim miktarı tam olarak sıfır olacaktır.

Dezenfektan çözeltisinin aylık üretim miktarını litre cinsinden xx sürekli değişkeni ile ve üretim yapma kararını yy sıfır-bir (ikili) değişkeni ile ifade ettiğimiz bir Karma Tamsayılı Programlama (MIP) modelinde, bu durumu doğru bir şekilde ifade eden kısıt seti aşağıdakilerden hangisidir?

Cevabı ve açıklamayı göster

Cevap: x−500y≥0x - 500y \geq 0 ; x−2000y≤0x - 2000y \leq 0 ; y∈{0,1}y \in \{0, 1\} ; x≥0x \geq 0

Cevap

Modeli doğru ifade eden kısıt seti: x−500y≥0x - 500y \geq 0 ; x−2000y≤0x - 2000y \leq 0 ; y∈{0,1}y \in \{0, 1\} ; x≥0x \geq 0 kısıtlarını içeren seçenektir.
Karma Tamsayılı Programlama (MIP) modellerinde 'ya belirtilen aralıkta değer al ya da sıfır ol' şeklindeki yarı-sürekli (semi-continuous) durumlar, sınır değerlerinin bir sıfır-bir değişkeni ile çarpılmasıyla modellenir. Doğru seçenekte yer alan x≥500yx \geq 500y (yani x−500y≥0x - 500y \geq 0) ve x≤2000yx \leq 2000y (yani x−2000y≤0x - 2000y \leq 0) eşitsizlikleri bu mantığı tam olarak karşılar. y=1y=1 iken 500≤x≤2000500 \leq x \leq 2000 aralığı geçerli olur, y=0y=0 iken ise 0≤x≤00 \leq x \leq 0 (dolayısıyla x=0x=0) durumu zorunlu kılınır.

Adım Adım Çözüm

1
Karar değişkenlerinin türlerini ve sınırlarını belirleme.
xx sürekli bir değişkendir (x≥0x \geq 0). yy ise evet/hayır kararını temsil ettiği için ikili (sıfır-bir) değişkendir (y∈{0,1}y \in \{0, 1\}).
Üretim miktarı kesirli olabilen bir sürekli değeri ifade ederken, üretime geçme kararı mantıksal bir seçimdir.
2
Üretim yapılması (y=1y=1) durumundaki kısıtları matematiksel olarak ifade etme.
Üretim varsa miktar 500500 ile 20002000 arasında olmalıdır: 500≤x≤2000500 \leq x \leq 2000.
Soruda belirtilen minimum reaksiyon stabilitesi ve maksimum tesis kapasitesi sınırlarıdır.
3
Üretim yapılmaması (y=0y=0) durumundaki kısıtı ifade etme.
Üretim yoksa miktar sıfır olmalıdır: x=0x = 0.
Karar verilmediğinde herhangi bir üretim gerçekleşemez.
4
İki durumu tek bir kısıt setinde birleştirmek için xx sınırlarını yy ile çarpma (Büyük-M tekniğinin yarı sürekli versiyonu).
Alt sınır için: x≥500yx \geq 500y. Üst sınır için: x≤2000yx \leq 2000y.
y=1y=1 iken 500≤x≤2000500 \leq x \leq 2000 olur. y=0y=0 iken 0≤x≤00 \leq x \leq 0 olur ki bu da doğrudan x=0x=0 eşitliğini sağlar.
5
Elde edilen eşitsizlikleri standart forma (değişkenler solda, sabitler sağda) dönüştürme.
x−500y≥0x - 500y \geq 0 ve x−2000y≤0x - 2000y \leq 0 denklemleri elde edilir.
Doğrusal ve tamsayılı programlama modellerinde kısıtlar genellikle standart formda yazılır.

Anahtar Kavram

Karma Tamsayılı Programlama Modellerinde Yarı Sürekli Değişken (Semi-continuous Variable) Modellemesi
Soru 62Soru →

Bir kamu kurumu, e-devlet veri tabanı altyapısını güçlendirmek amacıyla yüksek performanslı yeni bir bulut sunucu sistemine geçiş yapıp yapmamayı değerlendirmektedir. Sistemin aktif hale getirilmesi kararı verilirse 50.00050.000 TL tutarında sabit bir kurulum (lisans) maliyeti katlanılacaktır. Sistem kurulduktan sonra, bu sunucu üzerinden işlenen her bir terabayt (TB) veri için 1515 TL değişken işlem maliyeti oluşacaktır. Sistemin altyapısı gereği, kurulum yapıldığında bu sunucuda en fazla 10.00010.000 TB veri işlenebilmektedir. Kurulum yapılmazsa bu sunucuda herhangi bir veri işlenmesi mümkün değildir (işlenen veri miktarı sıfır olmalıdır).

Sistemin kurulup kurulmama kararını yy (y∈{0,1}y \in \{0, 1\}) ve işlenen veri miktarını TB cinsinden bir sürekli değişken olan xx (x≥0x \ge 0) ile gösteren, toplam maliyeti en küçüklemeyi amaçlayan karma tamsayılı programlama modeli aşağıdakilerden hangisinde doğru formüle edilmiştir?

Cevabı ve açıklamayı göster

Cevap: min⁡Z=15x+50000y\min Z = 15x + 50000y ; x−10000y≤0x - 10000y \le 0 ; x≥0x \ge 0 (sürekli), y∈{0,1}y \in \{0, 1\}

Cevap

Amaç fonksiyonunun sabit ve değişken maliyetleri doğru ağırlıklarla topladığı, kapasite ve ön koşul ilişkisinin x−10000y≤0x - 10000y \le 0 mantıksal kısıtıyla birbirine bağlandığı ve değişkenlerin türünün doğru (x sürekli, y ikili) ifade edildiği modeldir.
Doğru modelde maliyet maksimizasyonu önlenmiş (Min Z), x'in ancak y'nin 1 olması durumunda pozitif değer alabileceğini güvence altına alan bağlayıcı kısıt (x−10000y≤0x - 10000y \le 0) doğru yazılmış ve problemin doğası gereği değişkenlerden yalnızca birinin sıfır-bir kısıtına tabi olduğu, diğerinin sürekli bırakıldığı (Karma model prensibi) hatasız uygulanmıştır.

Adım Adım Çözüm

1
Amaç fonksiyonunu belirlemek.
Min Z = 15x + 50000y
Toplam maliyet, veri miktarı başına 15 TL ile sistemin kurulum kararını yansıtan 50.000 TL'nin toplamından oluşur.
2
Mantıksal ön koşul ve kapasite kısıtını oluşturmak.
x <= 10000y => x - 10000y <= 0
Sistem kurulmazsa (y=0) işlenen veri sıfır (x<=0) olmalı, kurulursa (y=1) veri miktarı en fazla 10.000 olmalıdır. Bu bağlantı eşitsizlikle ifade edilmelidir.
3
Değişkenlerin uzayını (türünü) tanımlamak.
x >= 0 (sürekli) ve y elemandır {0, 1} (ikili/kesikli)
İşlenen veri (TB) kesirli değerler alabilen sürekli bir miktar, sistemin kurulum kararı ise var/yok mantığıyla çalışan sıfır-bir tamsayı değeridir.

Anahtar Kavram

Karma Tamsayılı (MIP) Modellerde Mantıksal (Sabit Maliyet) Kısıtlarının Formülasyonu
Soru 63Soru →

Bir büyükşehir belediyesi, kısıtlı bütçesiyle 5 farklı sosyal donatı projesini değerlendirmektedir. Projeler sırasıyla Kütüphane (x1x_1), Spor Salonu (x2x_2), Yüzme Havuzu (x3x_3), Gençlik Merkezi (x4x_4) ve Kreş (x5x_5) olarak belirlenmiş olup, her bir karar değişkeni xj∈{0,1}x_j \in \{0, 1\}'dir (j=1,2,3,4,5j=1,2,3,4,5).

Belediye meclisinin aldığı yatırım kararları şöyledir:
I. Kreş projesi hayata geçirilmezse, Kütüphane ve Spor Salonu projelerinin hiçbirisi yapılamaz.
II. Yüzme Havuzu projesi inşa edilmediği takdirde, Kütüphane ve Gençlik Merkezi projelerinden en fazla bir tanesi inşa edilebilir.

Buna göre, belediye meclisi kararlarını doğru bir şekilde ifade eden 0-1 tamsayılı programlama kısıtları aşağıdakilerden hangisinde birlikte verilmiştir?

Cevabı ve açıklamayı göster

Cevap: I. x1+x2≤2x5x_1 + x_2 \leq 2x_5
II. x1+x4−x3≤1x_1 + x_4 - x_3 \leq 1

Cevap

Birinci karar için x1+x2≤2x5x_1 + x_2 \leq 2x_5, ikinci karar için x1+x4−x3≤1x_1 + x_4 - x_3 \leq 1 eşitsizliklerini içeren seçenek doğrudur.
Doğru eşleşme, kısıtların x1+x2≤2x5x_1 + x_2 \leq 2x_5 ve x1+x4−x3≤1x_1 + x_4 - x_3 \leq 1 olarak verildiği seçenektir. Birinci ifadede x5=0x_5=0 (Kreş yok) olduğunda x1+x2≤0x_1+x_2 \leq 0 olur ve zorunlu olarak Kütüphane ile Spor Salonu yapılamaz (x1=0,x2=0x_1=0, x_2=0). İkinci ifadede x3=0x_3=0 (Havuz yok) olduğunda denklem x1+x4≤1x_1+x_4 \leq 1 halini alır ve en fazla birinin yapılabileceği şartını tam olarak sağlar.

Adım Adım Çözüm

1
Birinci kararı mantıksal olarak analiz edip eşitsizliğe dönüştürmek.
x1+x2≤2x5x_1 + x_2 \leq 2x_5 eşitsizliği elde edilir.
"Kreş (x5x_5) yapılmazsa (x5=0x_5=0), Kütüphane (x1x_1) ve Spor Salonu (x2x_2) yapılamaz" kuralı, x5=0x_5=0 için x1+x2≤0x_1+x_2 \leq 0 olmasını gerektirir. x5=1x_5=1 için herhangi bir engel olmadığından denklem x1+x2≤2x5x_1+x_2 \leq 2x_5 şeklinde veya x1≤x5x_1 \leq x_5 ve x2≤x5x_2 \leq x_5 olarak yazılabilir.
2
İkinci kararı mantıksal olarak analiz edip eşitsizliğe dönüştürmek.
x1+x4−x3≤1x_1 + x_4 - x_3 \leq 1 eşitsizliği elde edilir.
"Yüzme havuzu (x3x_3) yapılmazsa (x3=0x_3=0), Kütüphane (x1x_1) ve Gençlik Merkezi (x4x_4) en fazla 1 olabilir" kuralı, x3=0x_3=0 iken x1+x4≤1x_1+x_4 \leq 1 olmasını gerektirir. x3=1x_3=1 iken kısıtlama yoktur (x1+x4≤2x_1+x_4 \leq 2). Bu durum x1+x4≤1+x3x_1+x_4 \leq 1 + x_3 denklemi ile genel formda ifade edilir ve düzenlenirse x1+x4−x3≤1x_1 + x_4 - x_3 \leq 1 bulunur.

Anahtar Kavram

0-1 tamsayılı programlamada koşullu (önermeli) durumların kısıt denklemlerine dönüştürülmesi.
Soru 64Soru →

Bir kamu kurumunun tedarik zinciri ağında kullanılacak depo sayısını ve kapasitesini belirlemek amacıyla aşağıdaki saf tamsayılı maksimizasyon doğrusal programlama modeli kurulmuştur:

Maksimum Z=5x1+8x2\text{Maksimum } Z = 5x_1 + 8x_2
Kısıtlar:
x1+x2≤6x_1 + x_2 \leq 6
5x1+9x2≤455x_1 + 9x_2 \leq 45
x1,x2≥0 ve tamsayıx_1, x_2 \geq 0 \text{ ve tamsayı}

Bu model Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Başlangıç (kök) düğümünün doğrusal programlama gevşetmesi çözüldüğünde optimum çözüm x1=2.25x_1 = 2.25, x2=3.75x_2 = 3.75 ve amaç fonksiyonu değeri Z=41.25Z = 41.25 olarak bulunmuştur. Algoritmanın kuralı gereği, ilk dallanma işlemi kesirsel kısmı en büyük olan değişken üzerinden yapılacaktır.

İlk dallanma işlemi sonucunda elde edilen alt problemlerin (düğümlerin) çözülmesiyle birlikte, algoritmanın güncel durumu ve sınır (bound) değerleri hakkında aşağıdakilerden hangisi doğrudur?

Cevabı ve açıklamayı göster

Cevap: x2x_2 değişkeni üzerinden x2≤3x_2 \leq 3 ve x2≥4x_2 \geq 4 kısıtları ile iki alt düğüm oluşturulur; x2≤3x_2 \leq 3 kısıtlı düğümde Z=39Z=39 değerli tamsayılı çözüm bulunarak alt sınır (lower bound) 3939 olarak güncellenir, x2≥4x_2 \geq 4 kısıtlı düğüm ise Z=41Z=41 değerini verdiğinden incelenmeye devam edilir.

Cevap

İlk dallanma x2x_2 değişkeni üzerinden yapılarak x2≤3x_2 \leq 3 ve x2≥4x_2 \geq 4 alt problemleri oluşturulur. x2≤3x_2 \leq 3 düğümünde tamsayılı Z=39Z=39 çözümü bulunarak alt sınır (lower bound) güncellenir. x2≥4x_2 \geq 4 düğümü ise Z=41Z=41 (ve kesirli x1x_1) değerini verdiği için incelenmeye devam edilir.
Doğru yaklaşımda algoritma kesirsel değeri en yüksek olan değişkeni seçer (x2=3.75x_2=3.75). x2≤3x_2 \leq 3 ve x2≥4x_2 \geq 4 dalları oluşturulur. x2≤3x_2 \leq 3 eklendiğinde sistem çözülürse x1=3x_1=3 bulunur ve tamsayılı (3,3)(3,3) noktasında amaç fonksiyonu Z=39Z=39 çıkar. Bu maksimizasyon problemi için referans alt sınırı (LB) oluşturur. x2≥4x_2 \geq 4 dalı çözüldüğünde ise x1=1.8x_1=1.8 ile Z=41Z=41 üst sınır değeri (UB) üretilir. Çıkan 4141 değeri, tamsayılı en iyi çözümümüz olan 3939'dan büyük olduğu için algoritma bu dalın budanamayacağına (kapatılamayacağına) hükmeder ve incelemeye devam eder.

Adım Adım Çözüm

1
Dallanma yapılacak değişkenin seçilmesi.
x1x_1'in kesirsel kısmı 0.250.25, x2x_2'nin kesirsel kısmı 0.750.75'tir. Kural gereği x2x_2 değişkeni seçilir.
Dal-Sınır algoritmasında daha hızlı yakınsama sağlamak için genellikle kesirsel kısmı 0.5'e en yakın veya en büyük olan değişken dallanma için seçilir.
2
Birinci alt problemin (x2≤3x_2 \leq 3) oluşturulması ve çözülmesi.
5x1+9(3)≤45⇒5x1≤18⇒x1≤3.65x_1 + 9(3) \leq 45 \Rightarrow 5x_1 \leq 18 \Rightarrow x_1 \leq 3.6 ve x1+3≤6⇒x1≤3x_1 + 3 \leq 6 \Rightarrow x_1 \leq 3. Maksimum x1x_1 değeri 33 olur. (3,3)(3, 3) noktasında Z=5(3)+8(3)=39Z = 5(3) + 8(3) = 39 bulunur.
Dallanan kısıt doğrusal programlama modeline eklenir ve maksimizasyon yönünde optimum köşe noktası hesaplanır.
3
Tamsayılı çözümün değerlendirilmesi.
(3,3)(3, 3) noktası tümüyle tamsayılıdır. Maksimizasyon probleminde geçerli bir tamsayılı çözüm bulunduğunda, bu değer mevcut alt sınır (Lower Bound) olarak kabul edilir. Yeni alt sınır: LB=39LB = 39.
Optimum tamsayılı çözüm en kötü ihtimalle bu değerde olacaktır.
4
İkinci alt problemin (x2≥4x_2 \geq 4) oluşturulması ve çözülmesi.
5x1+9(4)≤45⇒5x1≤9⇒x1≤1.85x_1 + 9(4) \leq 45 \Rightarrow 5x_1 \leq 9 \Rightarrow x_1 \leq 1.8. (1.8,4)(1.8, 4) noktasında Z=5(1.8)+8(4)=41Z = 5(1.8) + 8(4) = 41 bulunur.
Diğer dal incelenmeden optimum çözüm kesinleştirilemez.
5
Düğümlerin budanma (fathoming) durumunun kontrol edilmesi.
İkinci alt problemin amaç fonksiyonu değeri (Z=41Z=41), mevcut alt sınırdan (LB=39LB=39) daha büyük olduğu için budanamaz ve x1x_1 değişkeni kesirli (1.81.8) olduğu için dallanmaya bu düğümden devam edilir.
Eğer bir düğümün üst sınırı, mevcut en iyi tamsayılı çözümden küçük veya ona eşit olsaydı budanırdı. Ancak burada potansiyel olarak daha iyi bir çözüm barındırdığı için inceleme sürdürülmelidir.

Anahtar Kavram

Dal-Sınır algoritmasında maksimizasyon problemleri için düğüm oluşturma, doğrusal gevşetme çözümleriyle tamsayılı alt sınır (lower bound) bulma ve budama (fathoming) şartlarının analizi.
Soru 65Soru →

Bir kamu enerji şirketi, bir bölgeye güneş (SS) ve rüzgâr (WW) santralleri kurmayı planlamaktadır. Bu karar problemi için değişkenler şu şekilde tanımlanmıştır:

• ySy_S: Güneş santrali kurulursa 11, aksi halde 00 değerini alan ikili değişken,
• yWy_W: Rüzgâr santrali kurulursa 11, aksi halde 00 değerini alan ikili değişken,
• xSx_S: Güneş santralinden üretilecek enerji miktarı (MW),
• xWx_W: Rüzgâr santralinden üretilecek enerji miktarı (MW).

Sistemin kısıtlarına ilişkin kural ve gereksinimler şunlardır:
I. Güneş santralinin maksimum üretim kapasitesi 120120 MW, rüzgâr santralinin maksimum üretim kapasitesi ise 150150 MW'tır. Enerji üretimi ancak ilgili santralin kurulması durumunda gerçekleşebilir.
II. Bölgenin asgari 8080 MW olan toplam enerji talebi bu iki santral tarafından karşılanmak zorundadır.
III. Rüzgâr santrali, sadece güneş santrali kurulduğu takdirde inşa edilebilecektir (Güneş santrali olmadan rüzgâr santrali kurulamaz, ancak güneş santrali tek başına kurulabilir).

Buna göre, bu problemi tanımlayan karma tamsayılı programlama (MIP) modeline ait kısıt kümesi aşağıdakilerden hangisinde doğru ve eksiksiz olarak verilmiştir?

Cevabı ve açıklamayı göster

Cevap: xS≤120ySx_S \leq 120 y_S ; xW≤150yWx_W \leq 150 y_W ; yW≤ySy_W \leq y_S ; xS+xW≥80x_S + x_W \geq 80 ; yS,yW∈{0,1},xS,xW≥0y_S, y_W \in \{0, 1\}, x_S, x_W \geq 0

Cevap

Karma tamsayılı modelde, sürekli değişkenlerin ikili değişkenlerle kapasite sınırlarına doğru bağlandığı ve rüzgâr santralinin güneş santraline olan mantıksal ön koşulunun yW≤ySy_W \leq y_S şeklinde ifade edildiği kısıt kümesi doğru cevaptır.
Doğru formülasyonda; üretim miktarları, kurulum karar değişkenleri ile x≤M⋅yx \leq M \cdot y formatında doğru biçimde sınırlandırılmıştır (xS≤120ySx_S \leq 120 y_S ve xW≤150yWx_W \leq 150 y_W). Ayrıca 'rüzgâr sadece güneş kurulursa inşa edilebilir' mantıksal önermesi, yWy_W ikili değişkeninin ancak yS=1y_S=1 iken 11 olabileceğini şart koşan yW≤ySy_W \leq y_S eşitsizliği ile hatasız modellenmiştir. Talep kısıtı ve değişken tanımları da bütünüyle uygundur.

Adım Adım Çözüm

1
Sürekli ve ikili değişkenler arasındaki kapasite (bağlantı) kısıtlarının oluşturulması.
xS≤120ySx_S \leq 120 y_S ve xW≤150yWx_W \leq 150 y_W
Enerji üretiminin (xx) ancak o santral kurulduğunda (y=1y=1) gerçekleşebilmesi için, sürekli değişkenin üst sınırı ilgili ikili değişkenle çarpılmalıdır. y=0y=0 iken x=0x=0 olmaya zorlanır.
2
Ön koşul (mantıksal bağımlılık) kısıtının oluşturulması.
yW≤ySy_W \leq y_S
Rüzgâr santralinin (yWy_W) kurulabilmesi güneş santralinin (ySy_S) kurulmasına bağlıdır. Güneş santrali yoksa (yS=0y_S=0), rüzgâr santrali olamaz (yW=0y_W=0). Güneş santrali varsa (yS=1y_S=1), rüzgâr santrali olabilir veya olmayabilir (yW≤1y_W \le 1).
3
Talep kısıtının oluşturulması ve değişken yapılandırmasının tanımlanması.
xS+xW≥80x_S + x_W \geq 80 ve yS,yW∈{0,1},xS,xW≥0y_S, y_W \in \{0, 1\}, x_S, x_W \geq 0
Bölgenin toplam enerji ihtiyacı asgari 8080 MW olduğundan iki santralin üretim toplamı bu değere eşit veya büyük olmalıdır. Karar değişkenlerinin doğası gereği kurulumlar ikili, üretimler sürekli ve negatif olmayan değişkenlerdir.

Anahtar Kavram

Karma Tamsayılı Modellerde Mantıksal ve Kapasite Kısıtlarının Kurulması
Soru 66Soru →

Bir üretim planlaması için oluşturulan iki değişkenli saf tamsayılı maksimizasyon problemi aşağıda verilmiştir:

Maksimum Z=3x1+4x2\text{Maksimum } Z = 3x_1 + 4x_2
Kısıtlar:\text{Kısıtlar:}
2x1+x2≤62x_1 + x_2 \leq 6
2x1+3x2≤92x_1 + 3x_2 \leq 9
x1,x2≥0 ve tamsayıx_1, x_2 \geq 0 \text{ ve tamsayı}

Bu problem Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Başlangıç (kök) düğümünde tamsayı kısıtları gevşetilerek çözülen doğrusal programlama modelinin optimal çözümü x1=2,25x_1 = 2,25, x2=1,5x_2 = 1,5 ve amaç fonksiyonu değeri Z=12,75Z = 12,75 olarak bulunmuştur.
Algoritmanın standart işleyişine göre, tamsayı olmayan değişkenler arasından en büyük kesirli kısma sahip olan değişken seçilerek ilk dallanma yapılacaktır.

Buna göre, kök düğümden yapılan bu dallanma işlemi sonucunda elde edilecek iki yeni alt düğümün gevşetilmiş (relaxed) amaç fonksiyonu (ZZ) değerleri aşağıdakilerden hangisinde doğru olarak verilmiştir?

Cevabı ve açıklamayı göster

Cevap: x2≤1x_2 \leq 1 dalı için Z=11,5Z = 11,5 ve x2≥2x_2 \geq 2 dalı için Z=12,5Z = 12,5

Cevap

Doğru değerler x2≤1x_2 \leq 1 dalı için Z=11,5Z = 11,5 ve x2≥2x_2 \geq 2 dalı için Z=12,5Z = 12,5'tir.
Doğru dallanma kuralı uygulanarak en büyük kesirli kısma sahip olan x2x_2 değişkeni seçilmiş ve x2≤1x_2 \leq 1 ile x2≥2x_2 \geq 2 dalları oluşturulmuştur. Her iki dal için doğrusal programlama modeli yeni kısıtlarla yeniden çözüldüğünde sırasıyla Z=11,5Z=11,5 ve Z=12,5Z=12,5 değerlerine ulaşılır.

Adım Adım Çözüm

1
Dallanma değişkenini belirleme
x1x_1'in kesirli kısmı 0,250,25 ve x2x_2'nin kesirli kısmı 0,500,50'dir.
Algoritma kuralı gereği en büyük kesirli kısma sahip olan değişken (x2x_2) üzerinden dallanma yapılır.
2
Dallanma kısıtlarını oluşturma
İki yeni alt düğüm için x2≤1x_2 \leq 1 ve x2≥2x_2 \geq 2 kısıtları elde edilir.
x2=1,5x_2=1,5 tamsayı olmadığı için bir alt tamsayıya yuvarlanarak sol dal, bir üst tamsayıya yuvarlanarak sağ dal oluşturulur.
3
x2≤1x_2 \leq 1 dalı için problemi çözme
Mevcut kısıtlarda x2=1x_2=1 alındığında dar kısıt 2x1+1≤6⇒x1≤2,52x_1 + 1 \leq 6 \Rightarrow x_1 \leq 2,5 olur. Bu dal için Z=3(2,5)+4(1)=11,5Z = 3(2,5) + 4(1) = 11,5 bulunur.
Amaç fonksiyonunu maksimize etmek için kısıtların izin verdiği en büyük değerler olan x1=2,5x_1=2,5 ve x2=1x_2=1 seçilir.
4
x2≥2x_2 \geq 2 dalı için problemi çözme
Mevcut kısıtlarda x2=2x_2=2 alındığında dar kısıt 2x1+6≤9⇒x1≤1,52x_1 + 6 \leq 9 \Rightarrow x_1 \leq 1,5 olur. Bu dal için Z=3(1,5)+4(2)=12,5Z = 3(1,5) + 4(2) = 12,5 bulunur.
Tüm kısıtları aynı anda sağlayan en uygun değerler olan x1=1,5x_1=1,5 ve x2=2x_2=2 belirlenir.

Anahtar Kavram

Dal-Sınır Algoritmasında Düğüm Değerlendirme
Soru 67Soru →

Bir mobilya atölyesi, masa (xx) ve sandalye (yy) üretiminden elde edeceği toplam kârı en çoklamak istemektedir. Üretim sürecindeki işçilik ve hammadde kısıtları göz önüne alınarak problemin matematiksel modeli şu şekilde oluşturulmuştur:

Amaç Fonksiyonu:
MaksZ=8x+5yMaks \quad Z = 8x + 5y
Kısıtlayıcı Fonksiyonlar:
x+y≤6x + y \leq 6
9x+5y≤459x + 5y \leq 45
x,y≥0 ve tamsayıx, y \geq 0 \text{ ve tamsayı}

Buna göre, problemin grafik yöntem kullanılarak çözülmesi durumunda bulunacak en uygun (optimum) ZZ değeri kaçtır?

Cevabı ve açıklamayı göster

Cevap: 40

Cevap

Problemin tamsayı kısıtları altındaki optimum çözümü (5,0)(5, 0) noktasında gerçekleşir ve elde edilecek maksimum ZZ değeri 4040'tır.
Doğrusal programlama gevşetmesinin optimum noktası (3,75;2,25)(3,75 ; 2,25) olup amaç fonksiyonu değeri 41,2541,25'tir. Ancak değişkenlerin tamsayı olması gerektiğinden, bu noktanın etrafındaki uygun tamsayı koordinatları incelenmelidir. Standart yuvarlama işlemi ile ulaşılan (4,2)(4, 2) noktası 9(4)+5(2)=46>459(4)+5(2)=46 > 45 olduğundan kısıtı ihlal eder ve uygun çözüm bölgesinde değildir. Bölge içindeki (3,3)(3, 3) noktası için Z=8(3)+5(3)=39Z = 8(3)+5(3)=39 bulunurken, uygun alanın sağ alt köşesindeki (5,0)(5, 0) noktasında kısıtlar sağlanır (5+0≤65+0 \leq 6 ve 9(5)+0≤459(5)+0 \leq 45) ve Z=8(5)+5(0)=40Z = 8(5)+5(0)=40 değeri elde edilir. Maksimum tamsayı değeri 4040'tır.

Adım Adım Çözüm

1
Kısıt doğrularının kesişim noktasının (LP gevşetme optimumunun) bulunması
İki denklem (x+y=6x+y=6 ve 9x+5y=459x+5y=45) ortak çözülerek x=3,75x=3,75 ve y=2,25y=2,25 bulunur.
Grafik çözümünde amaç fonksiyonu doğrusunun en dışa itildiği köşe noktası belirlenir.
2
Bulunan kesirli noktanın tamsayıya yuvarlanarak uygunluğunun test edilmesi
En yakın tamsayı olan (4,2)(4, 2) noktası denendiğinde 9(4)+5(2)=46≤459(4) + 5(2) = 46 \leq 45 eşitsizliğini sağlamadığı, yani çözüm alanının dışında kaldığı görülür.
Tamsayılı programlamada en yakın tamsayıya yuvarlamak her zaman uygun ve optimum çözümü vermez.
3
Uygun çözüm alanındaki alternatif tamsayı noktalarının değerlendirilmesi
(3,3)(3, 3) noktası için Z=39Z=39, (4,1)(4, 1) noktası için Z=37Z=37 ve (5,0)(5, 0) noktası için Z=40Z=40 hesaplanır.
Amaç fonksiyonunu (Z=8x+5yZ=8x+5y) en çoklayan ve tüm kısıtları sağlayan en iyi tamsayı kombinasyonunun bulunması gerekir.

Anahtar Kavram

Tamsayılı Programlama Modellerinde Grafik Çözüm ve LP Gevşetmesi Optimizasyonu

Alternatif Yöntem

Grafik çizmek yerine, kısıtları sağlayan tüm makul tamsayı ikililerini (x, y) sınır koşullarına göre (örneğin x=0'dan 5'e kadar) tek tek deneyerek Z değerini hesaplamak (tam sayımlama yaklaşımı).
Tahmini Süre:2m 0s
Soru 68Soru →

Bir kamu kurumunun bütçe kısıtları altındaki yatırım projelerinin seçimi için oluşturulan ve Balas'ın Kapalı Sayımlama (Additive) algoritması ile çözülen bir 0−10-1 tamsayılı minimizasyon modelinde, çözüm ağacının belirli bir düğümünde 1. ve 5. projelere onay verilmiş (x1=1x_1 = 1 ve x5=1x_5 = 1), 2., 3. ve 4. projelerin durumu ise henüz karara bağlanmamıştır (x2,x3,x4x_2, x_3, x_4 serbest değişkendir).

Modelin kaynak kullanım kısıtlarından birinin matematiksel ifadesi şöyledir:
4x1−3x2+5x3−2x4+2x5≤−44x_1 - 3x_2 + 5x_3 - 2x_4 + 2x_5 \le -4

Buna göre, Balas algoritmasının bu kısıtı değerlendirmesi ve ilgili düğüm için vereceği algoritmik karar aşağıdakilerden hangisidir?

Cevabı ve açıklamayı göster

Cevap: Serbest değişkenlerin alabileceği en elverişli değerler dahi kısıt eşitsizliğini sağlamaya yetmediğinden, bu düğüm uygunsuzluk (infeasibility) gerekçesiyle budanır.

Cevap

Serbest değişkenlerin alabileceği en elverişli değerler dahi kısıt eşitsizliğini sağlamaya yetmediğinden, bu düğüm uygunsuzluk (infeasibility) gerekçesiyle budanır.
Balas algoritmasında (Kapalı Sayımlama) bir düğümün uygun bir çözüm üretip üretemeyeceği, serbest değişkenlere eşitsizliği en elverişli hale getirecek değerler verilerek test edilir. 4x1−3x2+5x3−2x4+2x5≤−44x_1 - 3x_2 + 5x_3 - 2x_4 + 2x_5 \le -4 kısıtında x1=1x_1 = 1 ve x5=1x_5 = 1 atandığında, eşitsizlik −3x2+5x3−2x4≤−10-3x_2 + 5x_3 - 2x_4 \le -10 halini alır. Eşitsizlik yönü ≤\le olduğu için sol tarafı en küçük yapmak hedeflenir. Negatif katsayılı olanlara 11 (x2=1,x4=1x_2=1, x_4=1), pozitif katsayılı olana 00 (x3=0x_3=0) verdiğimizde sol tarafın alabileceği en küçük değer −5-5 olur. −5-5 değeri −10-10'dan küçük veya eşit olmadığı için, bu kısıt serbest değişkenlerin alacağı hiçbir değerle sağlanamaz. Kesin kısıt ihlali söz konusu olduğundan düğüm uygunsuzluk (infeasibility) gerekçesiyle algoritmada derhal budanır.

Adım Adım Çözüm

1
Mevcut atamaları kısıt denkleminde yerine koyun.
4(1)−3x2+5x3−2x4+2(1)≤−44(1) - 3x_2 + 5x_3 - 2x_4 + 2(1) \le -4 işlemi yapılarak 6−3x2+5x3−2x4≤−46 - 3x_2 + 5x_3 - 2x_4 \le -4 elde edilir.
Serbest değişkenlerin sağlaması gereken kalan eşitsizliği bulmak için sabitlenmiş değerler denkleme yansıtılır.
2
Eşitsizliği sadeleştirin.
Sabit olan 66 karşı tarafa atıldığında −3x2+5x3−2x4≤−10-3x_2 + 5x_3 - 2x_4 \le -10 eşitsizliğine ulaşılır.
Serbest değişkenlerin hedef eşik değerini tam olarak görmek için matematiksel sadeleştirme yapılır.
3
Sol tarafı minimize edecek en elverişli 0−10-1 atamalarını belirleyin.
Sol tarafın en küçük değeri alabilmesi için katsayısı negatif olan değişkenlere 11 (x2=1,x4=1x_2 = 1, x_4 = 1), katsayısı pozitif olan değişkenlere 00 (x3=0x_3 = 0) atanır. Bu durumda sol taraf: −3(1)+5(0)−2(1)=−5-3(1) + 5(0) - 2(1) = -5 olur.
Bir düğümün uygun bir çözüm üretme ihtimalini test etmek için, "küçük eşittir" (≤\le) kısıt yönüne göre sol taraf matematiksel olarak elde edilebilecek en küçük değere çekilir.
4
Elde edilen minimum değeri eşitsizliğin sağ tarafı ile karşılaştırın.
Bulunan en küçük değer olan −5-5, eşitsizliğin sağ tarafındaki −10-10 değerinden küçük veya eşit değildir (−5≰−10-5 \not\le -10).
Serbest değişkenler kullanılarak kısıtı sağlamak adına yapılabilecek en iyi atama bile eşitsizliği sağlayamıyorsa, bu düğümden türetilecek hiçbir çözüm uygun (feasible) olamaz ve düğüm uygunsuzluktan dolayı budanır.

Anahtar Kavram

Balas Algoritmasında Uygunsuzluk (Infeasibility) Budama Kriteri
Soru 69Soru →

Bir teknoloji firması, akıllı ev sistemleri için A ve B olmak üzere iki farklı model güvenlik kamerası üretmektedir. Üretim sürecinde bu kameralar optik montaj ve yazılım testi olmak üzere iki aşamadan geçmektedir. Firmanın günlük kârını en çoklamak amacıyla kurduğu tamsayılı doğrusal programlama modeli aşağıda verilmiştir:

MaksimumZ=4x1+5x2Maksimum \quad Z = 4x_1 + 5x_2
Kısıtlar:
3x1+2x2≤143x_1 + 2x_2 \leq 14
x1+4x2≤15x_1 + 4x_2 \leq 15
x1,x2≥0 ve tamsayıx_1, x_2 \geq 0 \text{ ve tamsayı}

(Burada x1x_1 ve x2x_2 sırasıyla A ve B model kameraların günlük üretim miktarlarını temsil etmektedir.)

Buna göre, bu problemin tamsayılı grafik çözüm yöntemi ile incelenmesi sonucunda elde edilecek maksimum ZZ (kâr) değeri aşağıdakilerden hangisidir?

Cevabı ve açıklamayı göster

Cevap: 23

Cevap

Doğru değer 23'tür.
Tamsayılı grafik çözüm yönteminde amaç, kısıtların oluşturduğu uygun poligon içindeki en yüksek amaç fonksiyonu (Z) değerini veren tamsayı koordinatlarını bulmaktır. Kesirli kesişim noktası (2.6, 3.1)'e komşu tamsayı noktalar incelendiğinde, (3, 3) noktası kısıtları ihlal ederken (2, 3) noktası alanı ihlal etmez ve Z değerini 23 yapar. Kısıtları sağlayan diğer tamsayı noktalarında (örneğin (3, 2) için Z=22) daha yüksek bir kâr elde edilememektedir.

Adım Adım Çözüm

1
Doğrusal programlama (LP) gevşetmesinin optimum noktasını bulmak için kısıtların kesişim noktasını hesapla.
3x_1 + 2x_2 = 14 ve x_1 + 4x_2 = 15 denklemleri ortak çözüldüğünde x_1 = 2.6 ve x_2 = 3.1 elde edilir.
Grafik çözüm yönteminde tamsayılı noktalar, sürekli (kesirli) çözümün etrafındaki uygun alanda aranır.
2
LP gevşetmesi için Z değerini hesapla.
Z = 4(2.6) + 5(3.1) = 10.4 + 15.5 = 25.9
Tamsayı kısıtı olduğu için 25.9 değeri doğrudan alınamaz, ancak optimum tamsayı çözümünün bu değerden küçük veya buna eşit olacağı bir üst sınır (bound) olarak bilinir.
3
Kesişim noktası (2.6, 3.1) etrafındaki tamsayılı noktaların uygun çözüm alanında (kısıtları sağlayıp sağlamadığı) olup olmadığını kontrol et.
Yuvarlama sonucu oluşan (3, 3) noktası 1. kısıtı (3*3 + 2*3 = 15 > 14) ihlal eder. Alt yuvarlama olan (2, 3) noktası 1. kısıtı (12 <= 14) ve 2. kısıtı (14 <= 15) sağlar. (3, 2) noktası da her iki kısıtı sağlar.
Tamsayılı programlamada sadece kısıt doğrusunun altında kalan uygun poligon alanı içindeki tamsayı koordinatları geçerlidir.
4
Uygun tamsayılı noktalar için amaç fonksiyonu (Z) değerlerini karşılaştır.
(2, 3) noktası için Z = 4(2) + 5(3) = 23. (3, 2) noktası için Z = 4(3) + 5(2) = 22.
En büyük (maksimum) Z değerini veren uygun tamsayı noktası, problemin kesin çözümüdür.

Anahtar Kavram

Tamsayılı Modellerde Grafik Çözüm Yöntemi
Soru 70Soru →

Afet yönetimi alanında faaliyet gösteren bir STK, kısıtlı kaynaklarını en verimli şekilde değerlendirebilmek amacıyla karar değişkenleri x1x_1 (arama-kurtarma ekibi) ve x2x_2 (sağlık destek aracı) olan bir saf tamsayılı doğrusal programlama modeli tasarlamıştır.

Kurulan modelin amaç fonksiyonu Maksimum Z=7x1+5x2\text{Maksimum } Z = 7x_1 + 5x_2 şeklindedir ve kısıtlar şöyledir:
4x1+3x2≤254x_1 + 3x_2 \leq 25
2x1+x2≤102x_1 + x_2 \leq 10
x1,x2≥0x_1, x_2 \geq 0 ve tamsayı.

Modelin tamsayı kısıtları gevşetildiğinde kök düğümün (root node) optimum çözümü x1=2.5x_1 = 2.5, x2=5x_2 = 5 ve Z=42.5Z = 42.5 olarak bulunmuştur.
Bu problemi Dal-Sınır (Branch and Bound) algoritmasıyla çözerken, algoritmanın ilk aşamasında modele x1≥3x_1 \geq 3 kısıtı eklenerek yeni bir alt düğüm oluşturulmuştur.

Buna göre, oluşturulan bu yeni alt düğümün doğrusal programlama problemi çözüldüğünde elde edilecek çözümün durumu ve amaç fonksiyonu (ZZ) değeri aşağıdakilerden hangisidir?

Cevabı ve açıklamayı göster

Cevap: Tamsayılı bir çözüm bulunur ve bu dal budanır (fathomed), Z=41Z = 41

Cevap

Eklenen x1≥3x_1 \geq 3 kısıtı altında model çözüldüğünde en iyi tamsayılı çözüm olan (3,4)(3, 4) noktası elde edilir ve dal budanır, Z=41Z = 41 olur.
Düğümün modeli çözülürken x1≥3x_1 \geq 3 bölgesi incelendiğinde, maksimizasyon problemi olduğundan x1x_1'in 33 sınırında x2x_2'nin alabileceği maksimum değer aranır. 2x1+x2≤102x_1 + x_2 \leq 10 kısıtı x2≤4x_2 \leq 4 sınırını, 4x1+3x2≤254x_1 + 3x_2 \leq 25 kısıtı ise x2≤13/3x_2 \leq 13/3 sınırını getirir. En kısıtlayıcı sınır x2≤4x_2 \leq 4 olduğundan optimum nokta x1=3x_1=3, x2=4x_2=4 olur. Bu değerlerin ikisi de tamsayı olduğundan algoritma bu dalı 'tamsayılı çözüm bulundu' diyerek budar ve Z=41 adayı kaydedilir.

Adım Adım Çözüm

1
Oluşturulan yeni alt düğümün (node) modelini tanımla.
Maksimum Z=7x1+5x2Z = 7x_1 + 5x_2
Kısıtlar: 4x1+3x2≤254x_1 + 3x_2 \leq 25, 2x1+x2≤102x_1 + x_2 \leq 10, ve eklenen yeni kısıt x1≥3x_1 \geq 3.
Dal-Sınır algoritmasında her yeni düğüm, bir önceki düğümün kısıtlarına dallanma kısıtının eklenmesiyle oluşur.
2
Amaç fonksiyonunu maksimize etmek için x1x_1'in alabileceği en küçük sınır değeri olan x1=3x_1 = 3 değerini mevcut kısıtlarda yerine koyarak x2x_2 için üst sınırları hesapla.
1. Kısıt için: 4(3)+3x2≤25⇒12+3x2≤25⇒3x2≤13⇒x2≤4.334(3) + 3x_2 \leq 25 \Rightarrow 12 + 3x_2 \leq 25 \Rightarrow 3x_2 \leq 13 \Rightarrow x_2 \leq 4.33
2. Kısıt için: 2(3)+x2≤10⇒6+x2≤10⇒x2≤42(3) + x_2 \leq 10 \Rightarrow 6 + x_2 \leq 10 \Rightarrow x_2 \leq 4
x1x_1 artarken x2x_2'nin kapasite kısıtları nedeniyle alabileceği maksimum değeri bulmak gereklidir.
3
Elde edilen x2x_2 sınırlarından en kısıtlayıcı olanı seçerek düğümün optimum noktasını belirle.
x2≤4x_2 \leq 4 eşitsizliği daha kısıtlayıcıdır. Maksimum Z için x1=3x_1 = 3 ve x2=4x_2 = 4 seçilir.
Tüm kısıtların aynı anda sağlanması (uygun çözüm bölgesi) için en dar sınırın (minimum üst sınırın) geçerli olması gerekir.
4
Bulunan (3,4)(3, 4) noktasında amaç fonksiyonu değerini hesapla ve düğümün durumunu (tamsayılılık kontrolü) değerlendir.
Z=7(3)+5(4)=21+20=41Z = 7(3) + 5(4) = 21 + 20 = 41. Hem x1x_1 hem de x2x_2 tamsayı olduğu için dal 'tamsayılılık' gerekçesiyle budanır (fathomed).
Dal-sınır yönteminde, çözümü tamsayı çıkan düğümler dallandırılmaya devam edilmez; bunlar olası optimum çözüm (incumbent) adayı olarak kaydedilir.

Anahtar Kavram

Dal-Sınır Algoritmasında Alt Düğüm (Node) Değerlendirmesi ve Budama

Alternatif Yöntem

Grafik çözüm yöntemi kullanılarak da bu sonuca ulaşılabilir. Koordinat sisteminde kısıtlar çizilip x1=3x_1 = 3 doğrusunun sağında kalan uygun çözüm bölgesinin köşeleri incelendiğinde, (3,4)(3,4) noktasının bölgedeki en iyi tamsayılı köşe olduğu kolayca görülebilir.
Tahmini Süre:2m 0s
Soru 71Soru →

Amaç fonksiyonu katsayılarının tamamı tamsayı olan maksimizasyon yönlü saf tamsayılı bir doğrusal programlama problemi, Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Sadece tek bir optimum çözümün bulunmasının hedeflendiği bu problemde, algoritmanın belirli bir aşamasında mevcut en iyi tamsayılı çözümün (alt sınır) amaç fonksiyonu değeri Z=125Z = 125 olarak belirlenmiştir.

Aynı aşamada, henüz dallandırılmamış olan üç farklı aktif düğümün (X, Y ve Z) doğrusal programlama gevşetmesi (LP relaxation) çözülmüş ve aşağıdaki amaç fonksiyonu değerleri elde edilmiştir:

• Düğüm X: ZX=127.4Z_X = 127.4 (En az bir değişken kesirli)
• Düğüm Y: ZY=125.8Z_Y = 125.8 (En az bir değişken kesirli)
• Düğüm Z: ZZ=124.6Z_Z = 124.6 (En az bir değişken kesirli)

Buna göre, algoritmanın karar kuralları işletildiğinde düğümlerin durumu ile ilgili aşağıdaki ifadelerden hangisi kesinlikle doğrudur?

Cevabı ve açıklamayı göster

Cevap: Düğüm Y'nin üretebileceği herhangi bir tamsayılı çözümün amaç fonksiyonu değeri en fazla 125125 olabileceğinden ve bu değer mevcut alt sınırdan daha iyi bir sonuç vermeyeceğinden Düğüm Y budanmalıdır.

Cevap

Düğüm Y'nin üretebileceği herhangi bir tamsayılı çözümün amaç fonksiyonu değeri en fazla 125 olabileceğinden ve bu değer mevcut alt sınırdan daha iyi bir sonuç vermeyeceğinden Düğüm Y budanmalıdır.
Maksimizasyon yönlü ve katsayıları tamsayı olan bir saf tamsayılı programlama probleminde, herhangi bir tamsayılı çözümün ZZ değeri de mutlaka tamsayı olmak zorundadır. Doğrusal programlama gevşetmesi, o düğümden elde edilebilecek tüm çözümler için aşılmaz bir üst sınır (upper bound) verir. Düğüm Y için bu üst sınır 125.8125.8'dir. Değişkenler tamsayıya zorlandığında, bu daldan elde edilebilecek en büyük ZZ değeri aşağı yuvarlanarak en fazla 125125 olabilir. Algoritma zaten Z=125Z = 125 değerini veren geçerli bir tamsayılı çözüme (mevcut alt sınır) sahiptir. Problemde tek bir optimum çözüm arandığı için, Düğüm Y'den daha iyi bir sonuç (Z≥126Z \ge 126) elde etme olasılığı sıfırdır. Bu yüzden Düğüm Y budanarak (kapatılarak) elenir.

Adım Adım Çözüm

1
Maksimizasyon probleminde Dal-Sınır algoritmasının temel budama (fathoming) kurallarını belirleme.
Bir düğümün budanması için doğrusal programlama gevşetmesi (üst sınır) değerinin, mevcut en iyi tamsayılı çözümden (alt sınır) daha kötü veya ona eşit olması gerekir.
Algoritmanın amacı, yalnızca elimizdeki mevcut en iyi çözümden daha üstün (daha iyi) çözümler aramaktır.
2
Saf tamsayılı modelde amaç fonksiyonu katsayılarının tamsayı olmasının matematiksel etkisini analiz etme.
Hem karar değişkenleri hem de amaç fonksiyonu katsayıları tamsayı olduğundan, amaç fonksiyonu ZZ yalnızca tamsayı değerler alabilir.
Tamsayıların doğrusal kombinasyonu her zaman bir tamsayıdır.
3
Düğüm Y'nin üretebileceği maksimum tamsayı değerini hesaplama.
ZY=125.8Z_Y = 125.8 olduğuna göre, değişkenler tamsayı olmaya zorlandığında bu daldan elde edilebilecek en yüksek ZZ değeri ⌊125.8⌋=125\lfloor 125.8 \rfloor = 125'tir.
Doğrusal programlama gevşetmesi, ilgili daldaki tüm olası tamsayılı çözümler için kesin bir üst sınır (upper bound) sağlar.
4
Elde edilen bu üst sınırı mevcut alt sınır ile karşılaştırma.
Düğüm Y'nin üretebileceği maksimum değer (125125), halihazırda elimizde bulunan mevcut en iyi çözüme (Z=125Z = 125) eşittir. Tek bir optimum çözüm arandığı için daha iyi bir çözüm çıkma ihtimali yoktur.
Bu nedenle Düğüm Y dallandırılmadan budanır (kapatılır). Düğüm Z (124.6<125124.6 < 125) zaten budanır. Sadece Düğüm X (⌊127.4⌋=127>125\lfloor 127.4 \rfloor = 127 > 125) dallandırılmaya devam edilir.

Anahtar Kavram

Saf Tamsayılı Programlamada Dal-Sınır Algoritması ve Budama Kuralları
Soru 72Soru →

Bir kamu kurumu, personel atama ve araç tahsis süreçlerini optimize etmek amacıyla saf tamsayılı bir doğrusal programlama modeli kurmuştur. Modelin doğrusal programlama gevşetmesi (LP relaxation) çözüldükten sonra elde edilen nihai simpleks tablosunda, tamsayı değer alması gereken temel değişkenlerden x2x_2'ye ait satır denklemi aşağıda verilmiştir:

x2+25x4−56x5+94x6=235x_2 + \frac{2}{5}x_4 - \frac{5}{6}x_5 + \frac{9}{4}x_6 = \frac{23}{5}

Gomory kesirli kesme (fractional cut) algoritması kullanılarak, bu optimal tablodaki kesirli çözümü ortadan kaldırmak için yeni bir kısıt (kesme düzlemi) üretilecektir.

Buna göre, modele eklenmesi gereken geçerli kesme kısıtı aşağıdakilerden hangisidir?

Cevabı ve açıklamayı göster

Cevap: 25x4+16x5+14x6≥35\frac{2}{5}x_4 + \frac{1}{6}x_5 + \frac{1}{4}x_6 \geq \frac{3}{5}

Cevap

Modelden elde edilecek doğru Gomory kesme kısıtı 25x4+16x5+14x6≥35\frac{2}{5}x_4 + \frac{1}{6}x_5 + \frac{1}{4}x_6 \geq \frac{3}{5} olmalıdır.
Gomory kesirli kesme (fractional cut) algoritmasında, her katsayı aij=⌊aij⌋+fija_{ij} = \lfloor a_{ij} \rfloor + f_{ij} kuralıyla kendisinden küçük en büyük tamsayı (floor) ve pozitif kesirli kısmına (fijf_{ij}) ayrılır. Kesme kısıtı ∑fijxj≥fi\sum f_{ij} x_j \geq f_i temel formülü ile oluşturulur. Denklemdeki x4x_4 katsayısının kesirli kısmı 25\frac{2}{5}'tir. Negatif olan x5x_5 katsayısı −56-\frac{5}{6} için; ⌊−56⌋=−1\lfloor -\frac{5}{6} \rfloor = -1 işlemiyle kesirli kısım −56−(−1)=16-\frac{5}{6} - (-1) = \frac{1}{6} bulunur. x6x_6 katsayısı 94=2+14\frac{9}{4} = 2 + \frac{1}{4} olduğundan kesirli kısmı 14\frac{1}{4}'tür. Eşitliğin sağ tarafı 235=4+35\frac{23}{5} = 4 + \frac{3}{5} yapılarak fi=35f_i = \frac{3}{5} olarak belirlenir. Tüm kesirli bileşenler ∑fijxj≥fi\sum f_{ij} x_j \geq f_i denklemine yerleştirildiğinde doğru kısıt 25x4+16x5+14x6≥35\frac{2}{5}x_4 + \frac{1}{6}x_5 + \frac{1}{4}x_6 \geq \frac{3}{5} olarak çıkar.

Adım Adım Çözüm

1
Kesme düzleminde kullanılmak üzere denklemdeki her bir değişkenin katsayısının pozitif kesirli kısmını (fijf_{ij}) belirleme
x4x_4 katsayısı 25\frac{2}{5} için f4=25f_4 = \frac{2}{5}, x5x_5 katsayısı −56-\frac{5}{6} için ⌊−56⌋=−1\lfloor -\frac{5}{6} \rfloor = -1 olduğundan f5=−56−(−1)=16f_5 = -\frac{5}{6} - (-1) = \frac{1}{6}, x6x_6 katsayısı 94\frac{9}{4} için ⌊94⌋=2\lfloor \frac{9}{4} \rfloor = 2 olduğundan f6=94−2=14f_6 = \frac{9}{4} - 2 = \frac{1}{4} olarak hesaplanır.
Gomory algoritması, değişkenlerin katsayılarını en büyük alt tamsayı ile arasındaki pozitif farka (aij=⌊aij⌋+fija_{ij} = \lfloor a_{ij} \rfloor + f_{ij}) ayırarak yeni bir kısıt üretir.
2
Eşitliğin sağ tarafındaki sabit değerin pozitif kesirli kısmını (fif_i) belirleme
Sağ taraf değeri 235=4.6\frac{23}{5} = 4.6 olduğundan ⌊4.6⌋=4\lfloor 4.6 \rfloor = 4 bulunur ve kesirli kısım fi=235−4=35f_i = \frac{23}{5} - 4 = \frac{3}{5} olarak elde edilir.
Kesme kısıtının sağ tarafı (RHS), optimal simpleks tablosundaki mevcut çözüm değerinin kesirli kısmından oluşturulmalıdır.
3
Gomory kesirli kesme kısıtı formülünü (∑fijxj≥fi\sum f_{ij} x_j \geq f_i) uygulama
Bulunan fijf_{ij} ve fif_i değerleri formüle yerleştirildiğinde 25x4+16x5+14x6≥35\frac{2}{5}x_4 + \frac{1}{6}x_5 + \frac{1}{4}x_6 \geq \frac{3}{5} kısıtı türetilir.
Bu eşitsizlik, mevcut LP gevşetmesinin optimal çözüm alanını daraltırken tamsayılı uygun çözüm bölgesini tamamen koruyan geçerli bir kesme düzlemidir.

Anahtar Kavram

Gomory Kesirli Kesme Algoritması
Tahmini Süre:2m 0s
Soru 73Soru →

Bir tamsayılı programlama problemi Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Problemin doğrusal programlama gevşetmesi (LP Relaxation) sonucunda elde edilen ilk çözümde x1=2,25x_1 = 2,25 ve x2=1,60x_2 = 1,60 değerleri bulunmuştur. Algoritma gereği x2x_2 değişkeni üzerinden dallandırma yapılmasına karar verilmiştir.

Buna göre, bu çözüm düğümünden (P0P_0) türetilecek olan iki yeni alt probleme eklenmesi gereken kısıtlar aşağıdakilerden hangisidir?

Cevabı ve açıklamayı göster

Cevap: x2≤1x_2 \leq 1 ve x2≥2x_2 \geq 2

Cevap

Dallandırma kısıtları, tamsayı olmayan değişken değerini kapsayan ardışık iki tamsayı kullanılarak x2≤1x_2 \leq 1 ve x2≥2x_2 \geq 2 şeklinde oluşturulmalıdır.
Dal-Sınır algoritmasında, tamsayı olması gereken bir değişkenin gevşetilmiş çözümdeki değeri vv ise, dallandırma işlemi bu değeri dışarıda bırakacak şekilde x≤⌊v⌋x \leq \lfloor v \rfloor ve x≥⌈v⌉x \geq \lceil v \rceil kısıtlarının eklenmesiyle gerçekleştirilir. x2=1,60x_2 = 1,60 için bu sınırlar 11 ve 22 olduğundan, doğru kısıtlar x2≤1x_2 \leq 1 ve x2≥2x_2 \geq 2 olur.

Adım Adım Çözüm

1
Dallandırma yapılacak değişkenin gevşetilmiş değerini belirleme
x2=1,60x_2 = 1,60
Soruda dallandırmanın x2x_2 değişkeni üzerinden yapılacağı belirtilmiştir.
2
Değerin alt ve üst tamsayı sınırlarını hesaplama
Alt tamsayı: ⌊1,60⌋=1\lfloor 1,60 \rfloor = 1; Üst tamsayı: ⌈1,60⌉=2\lceil 1,60 \rceil = 2
Dal-Sınır algoritması, tamsayı olmayan bölgeyi çözüm dışı bırakmak için değişkenin değerini çevreleyen tamsayıları kullanır.
3
Yeni kısıtları formüle etme
x2≤1x_2 \leq 1 ve x2≥2x_2 \geq 2
Mevcut uygun çözüm bölgesini ikiye bölerek tamsayı olmayan 1,601,60 değerini ortadan kaldırmak için bu iki kısıt alt problemlere eklenir.

Anahtar Kavram

Dal-Sınır (Branch and Bound) Algoritmasında Dallandırma Kuralı

İpuçları

1
Dallandırma işlemi, değişkenin tamsayı olmayan değerini içine alan tamsayı aralığını (1<1,60<21 < 1,60 < 2) bölmeyi hedefler.
2
Değişkenin değerini (1,601,60) bir altındaki tamsayıya yuvarlayarak üst sınırı, bir üstündeki tamsayıya yuvarlayarak alt sınırı oluşturmalısınız.
3
Elde edilen 1,601,60 değeri için eklenmesi gereken kısıtlar x2≤As¸ag˘ı Yuvarla(1,60)x_2 \leq \text{Aşağı Yuvarla}(1,60) ve x2≥Yukarı Yuvarla(1,60)x_2 \geq \text{Yukarı Yuvarla}(1,60) şeklindedir.

Daha Fazla Pratik

Dallandırma yapıldıktan sonra alt problemlerde elde edilen ZZ değerlerinin, ana problemin ZZ değerinden daha büyük olamayacağını (maksimizasyon için) hatırlayınız.
Tahmini Süre:1m 30s
ÖncekiSayfa 4 / 4
Tamsayılı Programlama Alıştırma Soruları — KPSS İstatistik — Sayfa 4 | Examkin