Tamsayılı Programlama Alıştırma Soruları — KPSS İstatistik — Sayfa 3

Soru 41Soru →

Bir kamu kurumu, vatandaşların kullanımı için yeni bir sosyal tesis alanı inşa etmeyi planlamaktadır. Tesisin kurulması kararı verildiğinde $20.000$ TL tutarında bir sabit hazırlık maliyeti ortaya çıkacaktır. Ayrıca tesisin kapalı alanındaki her bir metrekarelik ( $m^2$ ) düzenleme için $150$ TL değişken maliyet hesaplanmaktadır. Tesis için ayrılabilecek toplam alan en fazla $400$ $m^2$ olduğuna göre; toplam maliyeti minimize eden, $x$ değişkeninin kapalı alan miktarını (sürekli) ve $y$ değişkeninin tesisin kurulma kararını ( $0$ - $1$ ) temsil ettiği karma tamsayılı programlama modeli aşağıdakilerden hangisidir?

\min Z = 20.000y + 150x

;

x \leq 400y

;

x \geq 0, y \in \{0, 1\}

\min Z = 20.000x + 150y

;

x \leq 400y

;

x, y \geq 0

\min Z = 20.150(x + y)

;

x \leq 400

;

x \geq 0, y \in \{0, 1\}

\min Z = 20.000y + 150x

;

y \leq 400x

;

x \geq 0, y \text{ tamsayı}

\min Z = 20.000 + 150x

;

x \leq 400

;

x \geq 0

Cevabı ve açıklamayı göster

Cevap: $\min Z = 20.000y + 150x$ ; $x \leq 400y$ ; $x \geq 0, y \in \{0, 1\}$

Cevap

Toplam maliyeti minimize eden model

\min Z = 20.000y + 150x

amaç fonksiyonu ve

x \leq 400y

kısıtını içeren modeldir.

Modelde sabit maliyet (

20.000

) ancak tesisin inşasına karar verildiğinde (

y=1

) devreye girmekte, değişken maliyet ise inşa edilen alan (

x

) ile çarpılmaktadır.

x \leq 400y

kısıtı, hem kapasiteyi belirlemekte hem de tesis kurulmadan (

y=0

) alan kullanımının (

x>0

) imkansız olduğunu garanti etmektedir.

Adım Adım Çözüm

1

Karar değişkenlerini tanımla.

x

: Kapalı alan miktarı (

m^2

, sürekli);

y

: Tesis kurulma kararı (

0

veya

1

).

Karma tamsayılı modellerde bazı değişkenler sürekli, bazıları ise kesiklidir.

2

Amaç fonksiyonunu oluştur.

\min Z = 20.000y + 150x

Sabit maliyet sadece tesis kurulduğunda (

y=1

) oluşur, değişken maliyet ise alana bağlıdır.

3

Mantıksal kısıtı (Big-M mantığı) kur.

x \leq 400y

Eğer tesis kurulmazsa (

y=0

), kullanılan alan da

0

olmalıdır (

x \leq 0

); tesis kurulursa (

y=1

), alan kapasite (

400

) kadar olabilir.

Anahtar Kavram

Sabit hazırlık maliyeti içeren karma tamsayılı programlama modelleme mantığı.

Tahmini Süre:1m 0s

Soru 42Soru →

Bir yerel yönetim, yeni bir ek hizmet binası açmayı planlamaktadır. Binanın açılmasına karar verilmesi durumunda $150.000$ TL tutarında bir sabit kurulum maliyeti oluşacaktır. Ayrıca, bu binada sunulan hizmetin birim başına değişken maliyeti $40$ TL'dir. Binanın açılmaması durumunda ise herhangi bir maliyet ortaya çıkmayacaktır.

$y$ değişkeni binanın açılma durumunu ( $1$ : açılacak, $0$ : açılmayacak), $x$ ise sunulan hizmet miktarını (sürekli değişken) temsil ettiğine göre, toplam maliyeti ( $Z$ ) en küçüklemeyi (minimize etmeyi) amaçlayan fonksiyon aşağıdakilerden hangisidir?

\min Z = 150.000y + 40x

\min Z = 150.000x + 40y

\min Z = 150.040(x + y)

concepts

\min Z = 150.000 + 40x

\min Z = 40x

Cevabı ve açıklamayı göster

Cevap: $\min Z = 150.000y + 40x$

Cevap

Sabit maliyeti binanın açılma kararına (

y

), değişken maliyeti ise hizmet miktarına (

x

) bağlayan

\min Z = 150.000y + 40x

fonksiyonu doğrudur.

Karma tamsayılı programlama modellerinde, bir faaliyetin gerçekleştirilip gerçekleştirilmemesine bağlı olan sabit maliyetler

0-1

(binary) değişkenlerle çarpılırken, hacme bağlı değişken maliyetler sürekli değişkenlerle çarpılır. Bu soruda

150.000

TL sabit bir bedel olduğu için

y

ile,

40

TL birim başına olduğu için

x

ile çarpılmalıdır.

Adım Adım Çözüm

1

Sabit maliyetin hangi değişkene bağlı olduğunu belirleyin.

150.000

TL sabit maliyet, binanın açılıp açılmaması kararına (

y \in \{0, 1\}

) bağlıdır.

Sabit maliyetler sadece yatırım yapıldığında veya faaliyet başladığında ortaya çıkar.

2

Değişken maliyetin hangi değişkene bağlı olduğunu belirleyin.

Birim başına

40

TL olan değişken maliyet, sunulan hizmet miktarına (

x \geq 0

) bağlıdır.

Değişken maliyetler üretim veya hizmet hacmi ile doğru orantılı olarak artar.

3

Amaç fonksiyonunu oluşturun.

Z = (150.000 \times y) + (40 \times x)

Toplam maliyet, sabit ve değişken maliyet kalemlerinin toplamından oluşur.

Anahtar Kavram

Karma Tamsayılı Programlamada Sabit Hazırlık (Fixed-Charge) Maliyetlerinin Modellenmesi

Soru 43Soru →

Doğrusal gevşetmesi (LP relaxation) çözülmüş olan bir tam sayılı programlama modelinin optimal simpleks tablosundan alınan ve $x_2$ temel değişkenine ait olan satır denklemi aşağıda verilmiştir:

x_2 + \frac{2}{3}x_3 - \frac{3}{4}x_4 = \frac{7}{5}

Bu denklemde $x_3$ ve $x_4$ temel dışı değişkenlerdir. Problemin saf tam sayılı bir model olduğu bilindiğine göre, bu satırdan elde edilecek olan Gomory kısıtı (kesmesi) aşağıdakilerden hangisidir? ( $s_g$ : Gomory aylak değişkeni)

s_g - \frac{2}{3}x_3 - \frac{1}{4}x_4 = -\frac{2}{5}

s_g - \frac{2}{3}x_3 + \frac{3}{4}x_4 = -\frac{2}{5}

s_g - \frac{2}{3}x_3 - \frac{1}{4}x_4 = -\frac{3}{5}

s_g - \frac{2}{3}x_3 - \frac{3}{4}x_4 = -\frac{2}{5}

s_g + \frac{2}{3}x_3 + \frac{1}{4}x_4 = -\frac{2}{5}

Cevabı ve açıklamayı göster

Cevap: $s_g - \frac{2}{3}x_3 - \frac{1}{4}x_4 = -\frac{2}{5}$

Cevap

Gomory kısıtı

s_g - \frac{2}{3}x_3 - \frac{1}{4}x_4 = -\frac{2}{5}

şeklindedir.

Denklemin sağ tarafındaki

7/5

değerinin kesirsel kısmı

2/5

olup kısıtın sağ tarafı

-2/5

olmalıdır. Temel olmayan değişkenlerden

x_3

'ün katsayısı

2/3

pozitif olduğu için kesirsel kısmı doğrudan

2/3

olur.

x_4

'ün katsayısı

-3/4

negatif olduğu için kesirsel kısmı

-3/4 - (-1) = 1/4

olarak hesaplanır. Formüle yerleştirildiğinde doğru kısıt elde edilir.

Adım Adım Çözüm

1

Satır denklemindeki katsayıları ve sağ taraf değerini belirleyin.

a_{23} = \frac{2}{3}

,

a_{24} = -\frac{3}{4}

,

b_2 = \frac{7}{5}

Kesirsel kısımların hesaplanması için temel olmayan değişkenlerin katsayıları ve RHS değeri gereklidir.

2

Her bir değerin kesirsel kısmını (

f = a - \lfloor a \rfloor

) hesaplayın.

f_{20} = \frac{7}{5} - \lfloor \frac{7}{5} \rfloor = 1.4 - 1 = 0.4 = \frac{2}{5}

;

f_{23} = \frac{2}{3} - \lfloor \frac{2}{3} \rfloor = \frac{2}{3} - 0 = \frac{2}{3}

;

f_{24} = -\frac{3}{4} - \lfloor -\frac{3}{4} \rfloor = -0.75 - (-1) = 0.25 = \frac{1}{4}

Gomory algoritmasında negatif katsayılar için kesirsel kısım, sayının kendisinden kendisinden küçük en büyük tam sayının çıkarılmasıyla bulunur.

3

Bulunan değerleri

s_g - \sum f_{ij}x_j = -f_{i0}

formülünde yerine koyun.

s_g - (\frac{2}{3})x_3 - (\frac{1}{4})x_4 = -\frac{2}{5}

Bu formül, tamsayılı olmayan çözümü eleyen ve uygun tamsayılı bölgeyi daraltan yeni bir kısıt oluşturur.

Anahtar Kavram

Gomory kesme düzlemi oluşturulurken, katsayıların kesirsel kısımları her zaman negatif olmayan (

0 \leq f < 1

) değerler olmalıdır. Özellikle negatif katsayılarda

f = a - \text{floor}(a)

kuralına dikkat edilmelidir.

Soru 44Soru →

Balas'ın Kapalı Sayımlama (Additive) algoritması ile bir $0-1$ tamsayılı programlama problemi çözülürken, algoritmanın doğrudan uygulanabilmesi için problemin standart minimizasyon formundaki amaç fonksiyonu katsayıları ( $c_j$ ) ile ilgili temel gereklilik aşağıdakilerden hangisidir?

Tüm

c_j

katsayıları negatif olmayan (

c_j \geq 0

) değerler olmalıdır.

Tüm

c_j

katsayıları negatif (

c_j < 0

) değerler olmalıdır.

c_j

katsayıları sadece

0

veya

1

değerlerini almalıdır.

Katsayıların işaretleri kısıtların yönüne (

\leq

veya

\geq

) bağlı olarak değişmelidir.

En az bir

c_j

katsayısı negatif, diğerleri pozitif olmalıdır.

Cevabı ve açıklamayı göster

Cevap: Tüm $c_j$ katsayıları negatif olmayan ( $c_j \geq 0$ ) değerler olmalıdır.

Cevap

Balas algoritmasının standart minimizasyon formunda tüm amaç fonksiyonu katsayıları negatif olmayan (

c_j \geq 0

) değerler olmalıdır.

Balas'ın Kapalı Sayımlama algoritmasında, minimizasyon hedeflenirken amaç fonksiyonu katsayılarının negatif olmaması (

c_j \geq 0

) istenir. Bu durum, 'toplamsal' (additive) yapının korunmasını ve kısmi çözümlerde alt sınırların kolayca hesaplanarak uygun olmayan dalların budanmasını sağlar. Eğer katsayılarda negatif değer varsa, değişken dönüşümü (

x_j = 1 - y_j

) yapılarak bu şart sağlanmalıdır.

Adım Adım Çözüm

1

Algoritmanın temel yapısını analiz etme

Balas'ın Kapalı Sayımlama algoritması,

0-1

tamsayılı programlama problemlerini çözmek için kullanılan toplamsal (additive) bir algoritmadır.

Algoritmanın hangi model yapısı üzerinde çalıştığını anlamak için gereklidir.

2

Standart form gerekliliklerini belirleme

Algoritmanın doğrudan uygulanabilmesi için problemin minimizasyon formunda olması ve tüm amaç fonksiyonu katsayılarının (

c_j

) negatif olmaması şartı aranır.

Bu şart, değişkenlerin değerinin

0

'dan

1

'e çıkarılması durumunda amaç fonksiyonu değerinin (Z) asla azalmayacağını garanti eder.

3

Budama (Kapalı Sayımlama) mantığı ile ilişkilendirme

Eğer bir kısmi çözümde elde edilen Z değeri mevcut en iyi çözümden (

Z^*

) büyükse,

c_j \geq 0

olduğu sürece daha fazla değişkenin

1

yapılması Z'yi daha da artıracaktır; bu da o dalın budanabilmesini sağlar.

Katsayıların işareti, algoritmanın arama uzayını verimli bir şekilde daraltmasını sağlayan temel mekanizmadır.

Anahtar Kavram

Balas Algoritması Standart Formu

Daha Fazla Pratik

Balas algoritmasında kısıtların uygunluğunu kontrol etmek için kullanılan 'kısıt açığı' (slack) kavramını inceleyebilirsiniz.

Tahmini Süre:45s

Soru 45Soru →

Saf tam sayılı bir doğrusal programlama probleminin doğrusal gevşetilmesi (LP relaxation) simpleks yöntemi ile çözülmüş ve optimal simpleks tablosunda tam sayı değer alması gereken $x_2$ temel değişkenine ait satır aşağıdaki gibi elde edilmiştir:

x_2 + \frac{7}{4}s_1 - \frac{1}{3}s_2 = \frac{11}{5}

Buna göre, Gomory kesme düzlemi algoritması kullanılarak bu satırdan türetilecek olan yeni kısıt (kesme düzlemi) denklemi aşağıdakilerden hangisidir?

s_g - \frac{3}{4}s_1 - \frac{2}{3}s_2 = -\frac{1}{5}

s_g - \frac{3}{4}s_1 - \frac{1}{3}s_2 = -\frac{1}{5}

s_g - \frac{3}{4}s_1 - \frac{2}{3}s_2 = \frac{1}{5}

s_g - \frac{1}{4}s_1 - \frac{2}{3}s_2 = -\frac{1}{5}

s_g - \frac{7}{4}s_1 + \frac{1}{3}s_2 = -\frac{11}{5}

Cevabı ve açıklamayı göster

Cevap: $s_g - \frac{3}{4}s_1 - \frac{2}{3}s_2 = -\frac{1}{5}$

Cevap

Doğru cevap

s_g - \frac{3}{4}s_1 - \frac{2}{3}s_2 = -\frac{1}{5}

denklemi ile verilen seçenektir.

Kesme düzlemi oluşturulurken satırdaki her bir katsayının tam sayı kısmından sonra gelen pozitif kesirsel kısmı alınır.

11/5

için

1/5

,

7/4

için

3/4

ve

-1/3

için (

-1 + 2/3

olduğu için)

2/3

değerleri doğru şekilde seçilip

s_g - (\text{kesirsel katsayılar}) = -(\text{sağ taraf kesri})

kalıbına yerleştirildiğinde doğru sonuca ulaşılır.

Adım Adım Çözüm

1

Katsayıların ve sağ taraf değerinin kesirsel kısımlarını (

f_{ij}

) belirleyin.

\frac{11}{5} = 2 + \frac{1}{5} \rightarrow f_{20} = \frac{1}{5}

;

\frac{7}{4} = 1 + \frac{3}{4} \rightarrow f_{21} = \frac{3}{4}

.

Gomory kısıtı sadece katsayıların pozitif kesirsel kısımları üzerinden kurulur.

2

Negatif katsayının kesirsel kısmını

0 \leq f < 1

olacak şekilde hesaplayın.

-\frac{1}{3} = -1 + \frac{2}{3} \rightarrow f_{22} = \frac{2}{3}

.

Negatif sayıların kesirsel kısmı, kendisinden küçük olan en yakın tam sayıdan farkı alınarak bulunur.

3

Kesme düzlemi denklemini

s_g - \sum f_{ij} x_j = -f_{i0}

formunda yazın.

s_g - \frac{3}{4}s_1 - \frac{2}{3}s_2 = -\frac{1}{5}

Yeni eklenen aylak değişken (

s_g

) ile kısıt denkleme dönüştürülür.

Anahtar Kavram

Gomory Kesme Düzlemi kısıtı, optimal tablodaki tamsayı olmayan bir satırın tüm katsayılarının pozitif kesirsel kısımları (

f_{ij}

) kullanılarak

\sum f_{ij} x_j \geq f_{i0}

şeklinde oluşturulur.

Tahmini Süre:1m 30s

Soru 46Soru →

0-1 tamsayılı programlama problemlerinin çözümünde kullanılan Balas'ın Kapalı Sayımlama (Additive) algoritmasında, bir minimizasyon modeli ele alınmaktadır. Algoritma akışında bir düğümün (alt problemin) 'uygunsuzluk' (infeasibility) nedeniyle kapalı sayımlanmasına (budanmasına) karar verilebilmesi için aşağıdaki durumlardan hangisinin gerçekleşmesi gerekir?

Kısıtın sağlanması için gereken miktarın, serbest değişkenlerin o kısıta sağlayabileceği maksimum pozitif katkıdan daha büyük olması

Mevcut düğümde hesaplanan amaç fonksiyonu değerinin o ana kadar bulunan en iyi çözüm değerinden (Z*) daha yüksek olması

Henüz değer atanmamış tüm değişkenlerin 1 değerini alarak kısıtların tamamını sağlaması

Problemin amaç fonksiyonundaki tüm katsayıların negatif değerlerden oluşması

Değişkenlerden birinin çözüm sürecinde 0 veya 1 dışında bir tamsayı değeri alması

Cevabı ve açıklamayı göster

Cevap: Kısıtın sağlanması için gereken miktarın, serbest değişkenlerin o kısıta sağlayabileceği maksimum pozitif katkıdan daha büyük olması

Cevap

Balas algoritmasında bir düğüm, kısıtın sağlanması için gereken miktarın (zayiat/açık), serbest değişkenlerin kısıta yapabileceği maksimum pozitif katkıdan daha büyük olması durumunda uygunsuzluk nedeniyle budanır.

Doğru yanıt olan seçenek, Balas algoritmasındaki uygunsuzluk testini tanımlar. Eğer bir kısıttaki negatif sapma (açık), o kısıtta yer alan ve henüz değer atanmamış değişkenlerin kısıta katabileceği en büyük değerden daha büyükse, bu düğümün alt dallarında uygun bir çözüm bulunması matematiksel olarak imkansızdır. Bu nedenle düğüm 'uygunsuzluk' nedeniyle kapalı sayımlanır (budanır).

Adım Adım Çözüm

1

Düğümdeki kısıt açığını (slack) belirle

s_i < 0 ise kısıt henüz sağlanmamıştır.

Budama kriterini kontrol etmek için kısıtın ne kadar uzağında olduğumuzu bilmemiz gerekir.

2

Serbest değişkenlerin kısıta yapabileceği maksimum katkıyı hesapla

Pozitif katsayılı serbest değişkenlerin katsayıları toplanır.

En iyi ihtimalle (tüm serbest değişkenler 1 olduğunda) kısıtın ne kadar iyileşebileceğini bulmak için gereklidir.

3

İhtiyaç ile maksimum katkıyı karşılaştır

Açık miktarı > Maksimum katkı ise durum uygunsuzdur.

En iyi senaryoda bile kısıt sağlanamıyorsa, bu daldan devam etmenin bir anlamı yoktur.

Anahtar Kavram

Uygunsuzluk Nedeniyle Budama (Fathoming by Infeasibility)

Soru 47Soru →

Saf tamsayılı bir doğrusal programlama problemi Dal-Sınır (Branch and Bound) algoritması ile çözülmektedir. Bir çözüm adımında, gevşetilmiş (relaxed) çözümden elde edilen sonuçlarda $x_1 = 4,6$ değeri bulunmuştur. Algoritma gereği bu değişken üzerinden yapılacak olan ilk dallandırma (branching) işleminde modele eklenecek yeni kısıtlar aşağıdakilerden hangisidir?

x_1 \leq 4

ve

x_1 \geq 5

x_1 < 4

ve

x_1 > 5

x_1 \geq 4

ve

x_1 \leq 5

x_1 \leq 3

ve

x_1 \geq 5

x_1 \leq 4

ve

x_1 \geq 6

Cevabı ve açıklamayı göster

Cevap: $x_1 \leq 4$ ve $x_1 \geq 5$

Cevap

Dallandırma kuralına göre eklenecek kısıtlar

x_1 \leq 4

ve

x_1 \geq 5

şeklinde olmalıdır.

Dal-Sınır algoritmasında, bir değişken

v

gibi kesirli bir değer aldığında, mevcut çözüm bölgesini tamsayı olmayan kısmı (

\lfloor v \rfloor < x < \lceil v \rceil

) dışarıda bırakacak şekilde ikiye bölmemiz gerekir.

x_1 = 4,6

için alt tamsayı sınırı 4, üst tamsayı sınırı ise 5'tir. Bu nedenle

x_1 \leq 4

ve

x_1 \geq 5

kısıtları eklenerek iki yeni alt problem oluşturulur.

Adım Adım Çözüm

1

Tamsayılı olması gereken ancak kesirli sonuç veren değişkenin belirlenmesi

x_1 = 4,6

Dal-Sınır algoritmasında dallandırma, tamsayı kısıtını sağlamayan değişkenler üzerinden yapılır.

2

Değişken değerini çevreleyen ardışık tamsayıların bulunması

\lfloor 4,6 \rfloor = 4

ve

\lceil 4,6 \rceil = 5

Değişkenin alabileceği olası tamsayı değerleri kesirli kısmın hemen altındaki ve üstündeki değerlerdir.

3

Kesirli bölgeyi dışarıda bırakacak eşitsizliklerin yazılması

x_1 \leq 4

ve

x_1 \geq 5

Bu iki kısıt,

4 < x_1 < 5

aralığındaki uygun olmayan tüm kesirli değerleri (4,6 dahil) çözüm kümesinden çıkarırken tamsayı noktaları korur.

Anahtar Kavram

Dal-Sınır Algoritmasında Dallandırma Kuralı

Tahmini Süre:45s

Soru 48Soru →

Bir üretim atölyesi, sınırlı kaynaklarını kullanarak $x_1$ ve $x_2$ ürünlerinden üretmeyi planlamaktadır. Her iki ürünün de üretim miktarlarının tam sayı olması zorunludur. Modele ait amaç fonksiyonu ve kapasite kısıtı şu şekildedir:

\text{Maks } Z = 60x_1 + 80x_2

\text{Kısıt: } x_1 + x_2 \leq 2,2

x_1, x_2 \in \{0, 1, 2, \dots\}

Buna göre, bu saf tamsayılı programlama modelinin en iyi (optimal) amaç fonksiyonu değeri kaçtır?

160

176

140

120

132

Cevabı ve açıklamayı göster

Cevap: 160

Cevap

En iyi amaç fonksiyonu değeri 160'tır.

Verilen modelde

x_1 + x_2 \leq 2,2

kısıtı ve tam sayı olma zorunluluğu altında, değişkenlerin toplamı en fazla 2 olabilir. En yüksek katsayıya sahip değişken olan

x_2

değerini maksimuma çıkardığımızda (

x_2=2, x_1=0

), amaç fonksiyonu

80 \times 2 = 160

değerine ulaşır ve bu, kısıtlar dahilindeki en yüksek tam sayılı değerdir.

Adım Adım Çözüm

1

Modelin kısıtını ve değişken yapısını inceleme

Tüm karar değişkenlerinin (

x_1, x_2

) tam sayı olması gerektiği saptanmıştır.

Soruda 'saf tamsayılı programlama modeli' ifadesi kullanıldığı ve değişkenlerin tam sayı kümesine ait olduğu belirtildiği için.

2

Kısıtı sağlayan uygun tam sayılı noktaları (çözüm kümesini) belirleme

x_1 + x_2 \leq 2,2

kısıtını sağlayan tam sayı çiftleri:

(0,0), (1,0), (2,0), (0,1), (0,2), (1,1)

noktalarıdır.

Karar değişkenleri negatif olamaz ve toplamları 2,2'yi aşmamalıdır.

3

Uygun noktalar için amaç fonksiyonu (

Z = 60x_1 + 80x_2

) değerlerini hesaplama

(2,0) \rightarrow Z = 120

;

(0,2) \rightarrow Z = 160

;

(1,1) \rightarrow Z = 140

olarak hesaplanır.

Hangi tam sayılı kombinasyonun en yüksek karı verdiğini belirlemek için.

4

Optimal çözümü seçme

En büyük

Z

değeri

x_1=0, x_2=2

noktasında 160 olarak bulunur.

Maksimizasyon probleminde en büyük amaç fonksiyonu değeri en iyi çözümü temsil eder.

Anahtar Kavram

Saf tamsayılı modellerde çözüm uzayı sadece tam sayılı noktalardan oluşur ve çözüm aranırken tamsayılılık kısıtı asla ihlal edilmemelidir.

İpuçları

1

Değişkenlerin tam sayı olması gerektiğini unutmayın; yani toplam üretim 2,2 olamaz, en fazla 2 olabilir.

Daha Fazla Pratik

Kısıtın

x_1 + x_2 \leq 2,8

ve katsayıların

100x_1 + 90x_2

olduğu bir durumda optimal çözümün nasıl değişeceğini inceleyebilirsiniz.

Tahmini Süre:45s

Soru 49Soru →

Balas’ın Kapalı Sayımlama (Additive) algoritması ile bir $0-1$ tamsayılı programlama problemi çözülmektedir. Problemin amaç fonksiyonu aşağıda verilmiştir:

min Z = 8x_1 + 5x_2 + 12x_3

Algoritmanın belirli bir adımında $x_2$ değişkenine $1$ değeri atanmış, $x_1$ ve $x_3$ değişkenleri ise henüz atanmamış (serbest) durumdadır.

Buna göre, bu aşamada ilgili düğüm (node) için hesaplanan mevcut amaç fonksiyonu değeri kaçtır?

0

5

8

12

25

Cevabı ve açıklamayı göster

Cevap: 5

Cevap

İlgili düğümde hesaplanan amaç fonksiyonu değeri 5'tir.

Balas'ın Kapalı Sayımlama algoritmasında, bir düğümdeki amaç fonksiyonu değeri hesaplanırken, o düğümde 1 değeri alan (atanmış) değişkenlerin katsayıları toplanır. Henüz atanmamış (serbest) değişkenler ise 0 kabul edilir. Soruda sadece

x_2

değişkenine 1 değeri atandığı için

Z

değeri

5 \times 1 = 5

olarak bulunur.

Adım Adım Çözüm

1

Modeldeki amaç fonksiyonunu ve değişken durumlarını belirle.

min Z = 8x_1 + 5x_2 + 12x_3

fonksiyonunda

x_2 = 1

olarak sabitlenmiş,

x_1

ve

x_3

serbesttir.

Balas algoritmasında mevcut çözüm değeri, o ana kadar değer atanmış değişkenler üzerinden hesaplanır.

2

Serbest değişkenlere varsayılan değerleri ata.

x_1 = 0

ve

x_3 = 0

olarak alınır.

Balas algoritmasında bir düğümdeki alt sınır (veya mevcut değer), serbest değişkenlerin en küçük değeri olan 0 kabul edilmesiyle bulunur.

3

Değerleri amaç fonksiyonunda yerine koyarak hesaplama yap.

Z = 8(0) + 5(1) + 12(0) = 5

Düğümün maliyetini belirlemek için sabitlenen değişkenin katkısı hesaplanır.

Anahtar Kavram

Balas algoritmasında bir kısmi çözümün amaç fonksiyonu değeri, atanan değişkenlerin katsayıları ile değerlerinin çarpım toplamıdır.

Daha Fazla Pratik

Eğer amaç fonksiyonunda katsayılar negatif olsaydı, Balas algoritmasını uygulamadan önce yapılacak dönüşümleri inceleyebilirsiniz.

Tahmini Süre:45s

Soru 50Soru →

Bir karar verici, iki değişkenli bir tamsayılı programlama problemini grafik yöntemle çözmek istemektedir. Probleme ait matematiksel model aşağıda verilmiştir:

Maksimum \quad Z = 4x_1 + 3x_2

Kısıtlar:

2x_1 + x_2 \leq 7

x_1 + 2x_2 \leq 7

x_1, x_2 \geq 0 \quad \text{ve tamsayı}

Buna göre, bu tamsayılı programlama modelinin optimum amaç fonksiyonu ( $Z$ ) değeri aşağıdakilerden hangisidir?

14

15

16,33

18

21

Cevabı ve açıklamayı göster

Cevap: 15

Cevap

Optimum tamsayılı amaç fonksiyonu değeri 15'tir.

Verilen modelde doğrusal gevşetme noktası

(2,33; 2,33)

olup amaç değeri

16,33

'dür. Ancak tamsayı kısıtı nedeniyle bu çözüm geçerli değildir. Bölge içindeki en yakın tamsayı noktaları test edildiğinde

(3,1)

noktası hem birinci kısıtı (

2(3)+1=7 \leq 7

) hem de ikinci kısıtı (

3+2(1)=5 \leq 7

) sağlamaktadır. Bu noktadaki amaç değeri olan 15, diğer tüm uygun tamsayı noktalarından daha büyüktür.

Adım Adım Çözüm

1

Doğrusal programlama gevşetmesinin (tamsayı kısıtı olmadan) çözümünü bulun.

x_1 = 2,33

ve

x_2 = 2,33

noktası elde edilir. Bu noktada

Z = 16,33

olur.

Tamsayılı çözümün üst sınırını belirlemek ve grafik üzerinde araştırma yapılacak bölgeyi daraltmak için gereklidir.

2

Uygun çözüm bölgesi içerisindeki tamsayı koordinatlı noktaları belirleyin.

Bölge içindeki uç tamsayı noktaları

(3,1)

,

(2,2)

ve

(1,3)

'tür.

Tamsayılı modellerde grafik çözüm, uygun bölge içindeki tam koordinatlı noktalardan birinde gerçekleşir.

3

Belirlenen noktaları amaç fonksiyonunda yerine koyarak en büyük değeri seçin.

Z(3,1) = 4(3) + 3(1) = 15

,

Z(2,2) = 14

ve

Z(1,3) = 13

. En büyük değer 15'tir.

Maksimizasyon probleminde en yüksek amaç fonksiyonu değerini veren uygun tamsayı noktası optimum çözümdür.

Anahtar Kavram

Tamsayılı programlamada grafik çözüm yöntemi, doğrusal gevşetme çözümünün yakınındaki uygun tamsayı noktalarının araştırılmasına dayanır.

İpuçları

1

Önce tamsayı kısıtı yokmuş gibi kısıt doğrularının kesişim noktasını bulun.

2

Kesişim noktası olan (2,33; 2,33) çevresindeki (3,1), (2,2), (1,3) gibi tamsayı koordinatları kısıtlarda yerine koyun.

Tahmini Süre:1m 30s

Soru 51Soru →

Bir mobilya fabrikası, yeni bir koltuk modeli üretmek için $5.000$ TL sabit hazırlık (setup) maliyeti ve üretilen her bir koltuk için $10$ TL değişken maliyet öngörmektedir. Fabrikanın bu model için toplam üretim kapasitesi en fazla $1.000$ adettir. Üretim miktarı $x$ (sürekli değişken) ve üretim kararı $y$ (üretimin yapılması durumunda $1$ , aksi halde $0$ değerini alan tamsayı değişken) ile gösterildiğine göre, toplam maliyeti minimize etmeyi amaçlayan uygun karma tamsayılı programlama modeli aşağıdakilerden hangisidir?

\min Z = 5000y + 10x

;

x \leq 1000y

,

x \geq 0, y \in \{0, 1\}

\min Z = 5000y + 10x

;

x \leq 1000

,

x \geq 0, y \in \{0, 1\}

\min Z = 5010(x + y)

;

x \leq 1000

,

x \geq 0, y \geq 0

\min Z = 5000x + 10y

;

y \leq 1000x

,

x \geq 0, y \in \{0, 1\}

\min Z = 5000y + 10x

;

x \geq 1000y

,

x \geq 0, y \in \{0, 1\}

Cevabı ve açıklamayı göster

Cevap: $\min Z = 5000y + 10x$ ; $x \leq 1000y$ , $x \geq 0, y \in \{0, 1\}$

Cevap

Toplam maliyet fonksiyonunun

\min Z = 5000y + 10x

ve kapasite kısıtının

x \leq 1000y

(

y \in \{0, 1\}

) şeklinde kurgulandığı model doğrudur.

Karma tamsayılı programlama modellerinde sabit maliyetlerin devreye girmesi için binary bir karar değişkeni (

y

) kullanılır. Doğru modelde, maliyet fonksiyonu sabit ve değişken maliyetleri doğru değişkenlerle eşleştirirken, kapasite kısıtı da üretimin ancak karar değişkeni aktif olduğunda yapılabileceğini garantiler.

Adım Adım Çözüm

1

Amaç fonksiyonunu oluşturun.

Z = 5000y + 10x

Sabit maliyet (

5.000

) sadece üretim yapıldığında (

y=1

) maliyete eklenmelidir. Değişken maliyet (

10

) ise her birim üretim (

x

) başına eklenir.

2

Mantıksal kapasite kısıtını kurun.

x \leq 1000y

Eğer üretim yapılmazsa (

y=0

), üst sınır

0

olur ve

x=0

zorunluluğu doğar. Eğer üretim yapılırsa (

y=1

), üretim miktarı kapasite sınırı olan

1.000

birimi aşamaz.

Anahtar Kavram

Sabit Maliyetli (Fixed Charge) Karma Tamsayılı Programlama Modellemesi

Tahmini Süre:50s

Soru 52Soru →

Bir kamu kurumu, tesis güvenliğini artırmak amacıyla 4 farklı elektronik güvenlik sistemi ( $x_1, x_2, x_3, x_4$ ) yatırımını değerlendirmektedir. Değerlendirme komisyonu, bütçe ve uyumluluk kriterleri doğrultusunda yatırımlarla ilgili şu kuralı belirlemiştir:

'Eğer 1. sistem ( $x_1$ ) kurulursa, 2. sistem ( $x_2$ ) ve 3. sistemden ( $x_3$ ) en fazla biri kurulabilir. Ancak 1. sistem kurulmazsa, 2. ve 3. sistemlerin kurulumunda herhangi bir kısıtlama aranmayacaktır.'

Sistemlerin kurulması durumunda karar değişkenleri 1, aksi halde 0 değerini almaktadır.

Buna göre, komisyonun belirlediği bu koşulu sağlayan matematiksel model kısıtı aşağıdakilerden hangisidir?

x_1 + x_2 + x_3 \leq 2

x_1 + x_2 + x_3 \leq 1

x_2 + x_3 \leq x_1

x_1 \leq x_2 + x_3

x_1 + x_2 + x_3 \geq 2

Cevabı ve açıklamayı göster

Cevap: $x_1 + x_2 + x_3 \leq 2$

Cevap

Komisyonun belirlediği koşulu sağlayan model kısıtı

x_1 + x_2 + x_3 \leq 2

'dir.

Verilen mantıksal yapı bir 'eğer-ise' koşuludur. Modelin,

x_1=1

olduğunda

x_2+x_3 \leq 1

sonucunu,

x_1=0

olduğunda ise

x_2+x_3 \leq 2

(yani hiçbir kısıtlayıcılığı olmayan, serbest) sonucunu vermesi gerekir. Doğru seçenek incelendiğinde;

x_1=1

konulduğunda

1 + x_2 + x_3 \leq 2 \Rightarrow x_2 + x_3 \leq 1

eşitsizliğine dönüşerek koşulu tam olarak sağlar.

x_1=0

konulduğunda ise

0 + x_2 + x_3 \leq 2 \Rightarrow x_2 + x_3 \leq 2

olur, 0-1 değişkenlerin toplamı zaten en fazla 2 olabileceği için sistemi hiçbir şekilde kısıtlamaz. Dolayısıyla mantıksal koşulu kusursuz olarak temsil eden eşitsizlik budur.

Adım Adım Çözüm

1

Mantıksal koşulu matematiksel eşitsizliğe çevirmek için durum analizi yapın.

1. Durum:

x_1 = 1

ise

x_2 + x_3 \leq 1

olmalıdır. 2. Durum:

x_1 = 0

ise

x_2 + x_3 \leq 2

olmalıdır (iki değişkenin toplamı en fazla 2 olabileceği için kısıtlama yoktur).

Sıfır-bir tamsayılı programlamada 'eğer-ise' (if-then) yapılarının alabileceği tüm olası durumları belirlemek, doğru denklemi kurmanın ilk adımıdır.

2

Bu iki durumu tek bir kısıt altında birleştirmek için Büyük-M (Big-M) tekniği mantığını kullanın.

x_2 + x_3 \leq 1 + M(1 - x_1)

denklemini kurun.

Koşullu kısıtlarda sağ taraf sabiti, koşulun gerçekleşip gerçekleşmemesine göre esneklik kazanmalıdır.

1-x_1

ifadesi,

x_1=1

olduğunda 0,

x_1=0

olduğunda 1 değerini üreterek anahtarlama görevi görür.

3

M

değerini belirleyerek denklemi sadeleştirin.

x_1 = 0

iken kısıtın

x_2 + x_3 \leq 1 + M

olması ve

x_2 + x_3

'ün alabileceği maksimum değerin 2 olması nedeniyle

1 + M \geq 2

, yani en dar sınırla

M=1

seçilir. Denklem

x_2 + x_3 \leq 1 + 1(1 - x_1) \Rightarrow x_2 + x_3 \leq 2 - x_1 \Rightarrow x_1 + x_2 + x_3 \leq 2

olarak elde edilir.

M değeri kısıtı geçersiz kılacak kadar büyük, ancak çözüm uzayını gereksiz genişletmeyecek kadar küçük (sıkı) seçilmelidir.

Anahtar Kavram

Sıfır-Bir (0-1) Tamsayılı Programlamada Mantıksal Kısıtların Modellenmesi

Tahmini Süre:1m 15s

Soru 53Soru →

Ulusal bir lojistik şirketi, 5 farklı bölgeye (sırasıyla $x_1, x_2, x_3, x_4$ ve $x_5$ ) yeni dağıtım merkezleri kurmayı planlamaktadır. Merkezlerin açılıp açılmama durumları sıfır-bir (0-1) tamsayılı değişkenler ile modellenecektir ( $x_i = 1$ ise $i$ . merkez açılır, $x_i = 0$ ise açılmaz).

Yönetimin belirlediği stratejik kurallar şunlardır:
I. 1 numaralı veya 2 numaralı dağıtım merkezinden en az biri kesinlikle açılmalıdır.
II. 3 numaralı dağıtım merkezin açılabilmesi için, 4 ve 5 numaralı merkezlerin her ikisinin birden açılmış olması zorunludur.
III. 2 numaralı merkezin açılması durumunda, 4 numaralı merkez açılamaz.

Buna göre, bu kuralları tam ve doğru olarak yansıtan doğrusal kısıtlar aşağıdakilerden hangisidir?

x_1 + x_2 \geq 1

,

\quad 2x_3 \leq x_4 + x_5

,

\quad x_2 + x_4 \leq 1

x_1 + x_2 \geq 1

,

\quad x_3 \leq x_4 + x_5

,

\quad x_2 + x_4 \leq 1

x_1 + x_2 \leq 1

,

\quad 2x_3 \leq x_4 + x_5

,

\quad x_2 - x_4 \leq 0

x_1 + x_2 \geq 1

,

\quad x_4 + x_5 \leq 2x_3

,

\quad x_2 + x_4 \leq 1

x_1 + x_2 = 1

,

\quad x_3 \leq x_4 + x_5

,

\quad x_2 + x_4 \geq 1

Cevabı ve açıklamayı göster

Cevap: $x_1 + x_2 \geq 1$ , $\quad 2x_3 \leq x_4 + x_5$ , $\quad x_2 + x_4 \leq 1$

Cevap

Birinci kural için

x_1 + x_2 \geq 1

, ikinci kural için

2x_3 \leq x_4 + x_5

, üçüncü kural için

x_2 + x_4 \leq 1

eşitsizliklerini içeren seçenektir.

Doğru kısıt modellemesinde; birinci kural 'en az biri' şartını karşılayacak şekilde

x_1 + x_2 \geq 1

olarak ifade edilmiştir. İkinci kural, 3 numaralı merkezin açılmasını (

x_3=1

) ancak 4 ve 5'in her ikisinin birden açılmasına (

x_4+x_5=2

) bağlayabilmek için

2x_3 \leq x_4 + x_5

eşitsizliği ile hatasız modellenmiştir. Üçüncü kural olan karşılıklı dışlama (biri varsa diğeri yok) şartı ise toplamların en fazla 1 olması gerektiğinden

x_2 + x_4 \leq 1

olarak doğru şekilde yazılmıştır.

Adım Adım Çözüm

1

Birinci stratejik kuralı matematiksel kısıta dönüştürme.

x_1 + x_2 \geq 1

'En az biri kesinlikle açılmalıdır' ifadesi, bu iki değişkenin toplamının 1'e eşit veya 1'den büyük olmasını gerektirir.

2

İkinci stratejik kuralı matematiksel kısıta dönüştürme.

2x_3 \leq x_4 + x_5

(veya eşdeğer olarak

x_3 \leq x_4

ve

x_3 \leq x_5

)

3'ün açılması (

x_3=1

), 4 ve 5'in her ikisinin de açılmasına bağlıdır. Formülde

x_3

yerine 1 konduğunda, eşitsizliğin sağlanması için karşı tarafın en az 2 olması gerekir ki bu da

x_4=1

ve

x_5=1

olmasını zorunlu kılar.

3

Üçüncü stratejik kuralı matematiksel kısıta dönüştürme.

x_2 + x_4 \leq 1

Karşılıklı dışlayan (mutually exclusive) olaylardır. Biri açılırsa diğeri açılamayacağı için ikisinin aynı anda 1 değerini alamaması, toplamlarının en fazla 1 olabileceği şeklinde modellenir.

Anahtar Kavram

Sıfır-Bir (0-1) Tamsayılı Programlama Modellerinde Mantıksal Kısıtlar

Soru 54Soru →

Bir araştırma enstitüsü, altyapı geliştirme programı kapsamında 5 farklı ileri düzey laboratuvarın ( $x_1, x_2, x_3, x_4, x_5$ ) kurulumunu değerlendirmektedir. Kurulum kararları sıfır-bir (0-1) tamsayılı değişkenler ile tanımlanmıştır ( $i = 1, 2, 3, 4, 5$ için laboratuvar kurulursa $x_i = 1$ , kurulmazsa $x_i = 0$ ).

Yönetim kurulunun laboratuvar kurulumlarına ilişkin belirlediği stratejik kurallar şunlardır:
I. Eğer 1. laboratuvar kurulacaksa, 2. ve 3. laboratuvarlardan en az biri mutlaka kurulmalıdır.
II. 4. ve 5. laboratuvarlar aynı anda kurulamaz; ancak her ikisinin de kurulmaması mümkündür.
III. Eğer 2. laboratuvar kurulursa, 4. laboratuvarın da kurulması zorunludur.

Buna göre, yönetim kurulunun belirlediği bu kuralları doğru şekilde modelleyen matematiksel kısıt seti aşağıdakilerden hangisidir?

x_1 - x_2 - x_3 \leq 0

,

\quad x_4 + x_5 \leq 1

,

\quad x_2 - x_4 \leq 0

x_1 - x_2 - x_3 \geq 0

,

\quad x_4 + x_5 \geq 1

,

\quad x_2 - x_4 \geq 0

x_1 - x_2 - x_3 \leq 0

,

\quad x_4 + x_5 = 1

,

\quad x_2 + x_4 \leq 1

x_2 + x_3 - x_1 \leq 0

,

\quad x_4 + x_5 \leq 1

,

\quad x_4 - x_2 \leq 0

x_1 + x_2 + x_3 \geq 1

,

\quad x_4 + x_5 \leq 1

,

\quad x_2 - x_4 = 0

Cevabı ve açıklamayı göster

Cevap: $x_1 - x_2 - x_3 \leq 0$ , $\quad x_4 + x_5 \leq 1$ , $\quad x_2 - x_4 \leq 0$

Cevap

Doğru kısıt seti:

x_1 - x_2 - x_3 \leq 0

,

\quad x_4 + x_5 \leq 1

,

\quad x_2 - x_4 \leq 0

ifadelerini içeren seçenektir.

Verilen kurallar analiz edildiğinde: I. kural için

x_1 \leq x_2 + x_3

, II. kural için

x_4 + x_5 \leq 1

ve III. kural için

x_2 \leq x_4

eşitsizlikleri gereklidir. Eşitsizliklerdeki değişkenler eşitsizliğin sol tarafına toplandığında, doğru modellemeyi veren eşitsizlik sistemi elde edilir.

Adım Adım Çözüm

1

I. Kuralın matematiksel olarak modellenmesi

x_1 \leq x_2 + x_3 \Rightarrow x_1 - x_2 - x_3 \leq 0

Eğer 1. laboratuvar kurulacaksa (

x_1=1

), 2. ve 3. laboratuvarlardan en az biri (

x_2+x_3 \geq 1

) kurulmalıdır. Eğer kurulmazsa (

x_1=0

), sağ taraf için bir kısıtlama olmaz. Değişkenler aynı tarafa toplanarak eşitsizlik elde edilir.

2

II. Kuralın matematiksel olarak modellenmesi

x_4 + x_5 \leq 1

4 ve 5 aynı anda kurulamaz (dışlayan kısıt). Toplamları maksimum 1 olabilir. İkisi birden 0 da olabileceği için küçük eşit işareti kullanılır.

3

III. Kuralın matematiksel olarak modellenmesi

x_2 \leq x_4 \Rightarrow x_2 - x_4 \leq 0

2. laboratuvar kurulursa (

x_2=1

), 4. laboratuvar da kurulmak zorundadır (

x_4=1

). Ancak 4 tek başına kurulabilir. Değişkenler aynı tarafa toplandığında

x_2 - x_4 \leq 0

eşitsizliğine ulaşılır.

Anahtar Kavram

Sıfır-Bir (0-1) Tamsayılı Modellerde Mantıksal Kısıtlar

Soru 55Soru →

Maksimizasyon amaçlı saf tam sayılı bir doğrusal programlama probleminin doğrusal gevşetilmesi (LP relaxation) simpleks yöntemiyle çözülmüş ve optimal tabloya ulaşılmıştır. Bu tabloda amaç fonksiyonu satırı ( $Z$ ) ile $x_2$ temel değişkenine ait satır denklemleri aşağıda verilmiştir:

Z + 3x_3 + 4x_4 = 40

x_2 - \frac{3}{5}x_3 + \frac{7}{4}x_4 = \frac{13}{3}

(Burada $x_3$ ve $x_4$ temel olmayan değişkenlerdir.)

Bu probleme $x_2$ satırı temel alınarak bir Kesme Düzlemi (Gomory) kısıtı ( $s_g$ aylak değişkeni ile) üretilip optimal tabloya eklenmiştir.

Buna göre, yeni kısıt eklendikten sonra optimalliği yeniden sağlamak için uygulanacak dual simpleks algoritmasının ilk adımında, temelden çıkacak ve temele girecek değişkenler sırasıyla aşağıdakilerden hangisidir?

Temelden çıkacak:

s_g

, Temele girecek:

x_4

Temelden çıkacak:

s_g

, Temele girecek:

x_3

Temelden çıkacak:

x_2

, Temele girecek:

x_4

Temelden çıkacak:

x_2

, Temele girecek:

x_3

Yeni kısıt eklendiğinde tablo primal olarak uygun kaldığından dual simpleks uygulanmaz, çözüm tamamlanmıştır.

Cevabı ve açıklamayı göster

Cevap: Temelden çıkacak: $s_g$ , Temele girecek: $x_4$

Cevap

Temelden çıkacak olan değişken

s_g

, temele girecek olan değişken ise

x_4

'tür.

Kesme düzlemi (Gomory) algoritmasında,

a_{ij}

katsayılarının kesirsel kısımları

f_{ij} = a_{ij} - \lfloor a_{ij} \rfloor

ile hesaplanır.

13/3

'ün kesri

1/3

;

-3/5

'in kesri

2/5

ve

7/4

'ün kesri

3/4

'tür. Oluşturulan kısıt

s_g - \frac{2}{5}x_3 - \frac{3}{4}x_4 = -\frac{1}{3}

şeklindedir. Sağ tarafı negatif olan

s_g

temelden çıkar. Giren değişken ise

Z

satırı katsayıları ile kesme düzleminin negatif katsayıları arasındaki oran testinden (

\min(3/0.4, 4/0.75) = \min(7.5, 5.33)

) minimum değeri veren

x_4

'tür.

Adım Adım Çözüm

1

x_2

satırındaki sabit değerin ve değişken katsayılarının kesirsel kısımlarını (

f

) hesaplayın.

Sabit değer

13/3

:

13/3 = 4 + 1/3 \implies f_0 = 1/3

x_3

katsayısı

-3/5

:

\lfloor -3/5 \rfloor = -1 \implies f_3 = -3/5 - (-1) = 2/5

x_4

katsayısı

7/4

:

\lfloor 7/4 \rfloor = 1 \implies f_4 = 7/4 - 1 = 3/4

Gomory kesme düzlemi oluşturulurken, katsayıların formülü

a_{ij} = \lfloor a_{ij} \rfloor + f_{ij}

şeklindedir. Negatif katsayıların kesirsel kısımları bulunurken alt tamsayıya yuvarlama kuralına dikkat edilmelidir.

2

Kesme düzlemi kısıtını oluşturun ve

s_g

aylak değişkenini ekleyerek tablo formatına getirin.

Gomory kısıtı formülü:

\sum f_{ij} x_j \ge f_0

\frac{2}{5}x_3 + \frac{3}{4}x_4 \ge \frac{1}{3}

Bunu

\le

formatına çevirip aylak değişken (

s_g

) eklersek:

-\frac{2}{5}x_3 - \frac{3}{4}x_4 + s_g = -\frac{1}{3}

Simpleks tablosuna eklenebilmesi için eşitsizliğin denklem haline getirilmesi ve bir temel değişken (

s_g

) barındırması gerekir.

3

Dual simpleks yöntemiyle temelden çıkacak değişkeni belirleyin.

Temelden çıkacak değişken

s_g

'dir.

Yeni kısıt eklendiğinde

s_g

değişkeninin çözüm değeri

-1/3

olmuştur. Dual simplekste sağ taraf sabiti en negatif olan temel değişken, çözümden çıkarılır.

4

Dual simpleks oran testini uygulayarak temele girecek değişkeni belirleyin.

Oranlar

\min \{ \frac{c_j}{|a_{gj}|} \}

formülüyle (

a_{gj} < 0

için) hesaplanır.

x_3

için oran:

\frac{3}{|-2/5|} = \frac{3}{0.4} = 7.5

x_4

için oran:

\frac{4}{|-3/4|} = \frac{4}{0.75} = 5.33

Minimum oran

x_4

'e (

5.33

) aittir.

Dual simpleks yönteminde, amaç fonksiyonundaki optimalliğin bozulmaması için Z satırı katsayılarının, temelden çıkacak satırdaki negatif katsayıların mutlak değerlerine oranı hesaplanır ve en küçük oranı veren değişken temele sokulur.

Anahtar Kavram

Gomory Kesme Düzlemi Üretimi ve Dual Simpleks Algoritması

Soru 56Soru →

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 $x_2$ 'nin bulunduğu satır aşağıdaki denklemi vermektedir:

x_2 + \frac{7}{5}x_3 - \frac{3}{4}x_4 = \frac{17}{6}

Problemdeki tüm değişkenlerin ( $x_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?

\frac{2}{5}x_3 + \frac{1}{4}x_4 \ge \frac{5}{6}

\frac{2}{5}x_3 - \frac{3}{4}x_4 \ge \frac{5}{6}

\frac{2}{5}x_3 + \frac{3}{4}x_4 \ge \frac{5}{6}

\frac{7}{5}x_3 - \frac{3}{4}x_4 \ge \frac{5}{6}

\frac{2}{5}x_3 + \frac{1}{4}x_4 \le \frac{5}{6}

Cevabı ve açıklamayı göster

Cevap: $\frac{2}{5}x_3 + \frac{1}{4}x_4 \ge \frac{5}{6}$

Cevap

Gomory kesme düzlemi algoritmasında kesirli kısımlar ayrıştırılarak elde edilen eşitsizlik

\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

a_{ij} = \lfloor a_{ij} \rfloor + f_{ij}

şeklinde tam ve negatif olmayan kesirli kısımlarına ayrılır (

0 \le f_{ij} < 1

). Burada en çok hata yapılan nokta negatif sayıların kesirli kısmını bulmaktır.

-3/4

sayısının bir alt tam kısmı

-1

'dir, dolayısıyla kesirli kısmı

-3/4 - (-1) = 1/4

olur.

7/5

'in kesirli kısmı

2/5

, sağ taraf sabiti olan

17/6

'nın kesirli kısmı ise

5/6

'dır. Standart Gomory kesmesi formülü

\sum f_{ij} x_j \ge f_i

şeklindedir. Buna göre doğru eşitsizlik

\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 (

f

) kısımlarını belirlemek için

a = \lfloor a \rfloor + f

kuralını uygula.

x_3

katsayısı:

\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.

x_4

katsayısı:

-\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 \le f < 1

). Bu nedenle negatif sayılar bir alt tamsayıya yuvarlanarak (burada

-1

) aradaki fark alınır.

3

Sağ taraf sabitinin kesirli kısmını belirle.

Sabit değer:

\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 (

\sum f_j x_j \ge f_b

) yerleştir.

\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

Soru 57Soru →

İki karar değişkenli ( $x_1, x_2 \geq 0$ ) bir saf tamsayılı maksimizasyon problemi, Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Kök düğümde (P0) doğrusal programlama gevşetmesinin optimum çözümü $x_1 = 4,5$ , $x_2 = 5,5$ ve amaç fonksiyonu değeri $Z = 144,5$ olarak hesaplanmıştır.

Algoritmanın ilerleyen adımlarında sırasıyla aşağıdaki düğümler ve çözümler elde edilmiştir:

- P1 Düğümü (P0'dan $x_1 \leq 4$ dalı): $x_1 = 4$ , $x_2 = 5,8$ ve $Z = 142,8$
- P2 Düğümü (P0'dan $x_1 \geq 5$ dalı): $x_1 = 5$ , $x_2 = 4$ ve $Z = 140$
- P3 Düğümü (P1'den $x_2 \leq 5$ dalı): $x_1 = 3,5$ , $x_2 = 5$ ve $Z = 138,5$
- P4 Düğümü (P1'den $x_2 \geq 6$ dalı): Uygun çözüm alanına sahip değildir.

Bu bilgilere göre, algoritmanın güncel durumu ve P3 düğümü için verilecek karar aşağıdakilerden hangisinde doğru olarak ifade edilmiştir?

P2 düğümünde ilk tamsayılı çözüm elde edildiği için algoritma anında sonlandırılır ve diğer düğümlerin durumuna bakılmaksızın

Z=140

değeri optimum kabul edilir.

P3 düğümünün amaç fonksiyonu değeri (

Z=138,5

), mevcut en iyi tamsayılı çözümden (

Z=140

) küçük olduğu için budanır; incelenecek aktif düğüm kalmadığından

Z=140

kesin optimum olur.

P3 düğümü tamsayılı çözüm vermediğinden algoritma devam etmeli ve

x_1 = 3,5

değeri için kısıtlar

x_1 < 3

ve

x_1 > 4

şeklinde tanımlanarak yeni dallandırma yapılmalıdır.

P2 düğümündeki çözüm, kök düğümün gevşetilmiş üst sınır değerine (

Z=144,5

) ulaşamadığı için budanır ve P3 düğümünden standart dallandırma işlemlerine devam edilir.

Kök düğümde (P0) elde edilen gevşetilmiş çözüm değerlerinin en yakın tamsayıya yuvarlanmasıyla elde edilecek sonuç optimum kabul edileceği için, algoritma dallandırma yapmadan P0 üzerinden sonlanır.

Cevabı ve açıklamayı göster

Cevap: P3 düğümünün amaç fonksiyonu değeri ( $Z=138,5$ ), mevcut en iyi tamsayılı çözümden ( $Z=140$ ) küçük olduğu için budanır; incelenecek aktif düğüm kalmadığından $Z=140$ kesin optimum olur.

Cevap

P3 düğümünün amaç fonksiyonu değeri (

Z=138,5

), mevcut en iyi tamsayılı çözümden (

Z=140

) küçük olduğu için budanır; incelenecek aktif düğüm kalmadığından

Z=140

kesin optimum olur.

Maksimizasyon problemlerinde Dal-Sınır algoritması, bulduğu her tamsayılı çözümü (P2 düğümündeki

Z=140

) bir alt sınır olarak kabul eder. Aktif düğümlerden elde edilen gevşetilmiş Z değeri bu alt sınırdan küçük veya eşitse (P3 düğümündeki

138,5 < 140

), o dalın daha iyi bir çözüm üretme ihtimali kalmadığı için dallandırma durdurulur ve budanır. Tüm açık dallar kapandığında (P4 uygunsuz, P3 bound yedi, P2 zaten tamsayı), algoritma iterasyonu tamamlar ve elimizdeki en iyi tamsayılı çözüm (

Z=140

) global optimum olur.

Adım Adım Çözüm

1

Algoritmadaki mevcut en iyi tamsayılı çözümü (alt sınırı) belirle.

P2 düğümünde

x_1=5, x_2=4

tamsayı değerleri elde edilmiştir ve

Z=140

olmuştur. Maksimizasyon probleminde ilk tamsayılı çözüm bir alt sınır (Lower Bound) oluşturur: LB = 140.

Mevcut en iyi tamsayılı çözüm, diğer düğümlerin dallandırılıp dallandırılmayacağına karar vermek için bir eşik değeri görevi görür.

2

P4 düğümünün durumunu değerlendir.

P4 düğümünde uygun çözüm olmadığı (infeasible) belirtilmiştir. Bu nedenle bu dal tamamen kapatılır (budanır).

Uygun çözüm alanı olmayan bir düğümden tamsayılı çözüm elde edilemez.

3

P3 düğümünün durumunu sınırlandırma (bound) kuralı ile değerlendir.

P3 düğümünde

Z = 138,5

'tir. Maksimizasyon probleminde bu daldan elde edilebilecek maksimum tamsayılı çözüm en fazla 138,5 (hatta ondan küçük) olabilir. Ancak elimizde zaten

Z=140

veren bir çözüm vardır.

138,5 < 140

olduğundan P3 düğümü dallandırılmaz ve budanır.

Bir düğümün amacı, mevcut en iyi tamsayılı çözümden daha iyi bir sonuç potansiyeli taşımaması durumunda sınırlandırma (fathoming by bound) kuralıyla elenmesidir.

4

Algoritmanın genel durumunu kontrol et.

P0'ın dalları olan P1 ve P2 incelenmiştir. P2 tamsayılıdır. P1'in dalları olan P3 (sınır nedeniyle) ve P4 (uygunsuzluk nedeniyle) budanmıştır. Açıkta (aktif) dallandırılacak hiçbir düğüm kalmamıştır.

Tüm aktif düğümler budandığında veya tamsayılı optimum çözüme ulaştığında algoritma sonlanır.

Anahtar Kavram

Dal-Sınır (Branch and Bound) Algoritmasında Budama Kuralları ve Optimum Çözüm Koşulu

Tahmini Süre:3m 0s

Soru 58Soru →

Sadece tamsayı değerler alabilen karar değişkenleriyle kurulan bir doğrusal programlama modelinde, maksimizasyon yönlü amaç fonksiyonu hedeflenmektedir. Bu modelin doğrusal gevşetme (LP relaxation) analizi sonucunda ulaşılan optimal tablosunda, temel dışı değişkenlerin indirgenmiş maliyetleri ( $Z$ satırı katsayıları) sırasıyla $x_3$ için $2$ , $x_4$ için $3$ ve $x_5$ için $0,5$ olarak hesaplanmıştır.

Optimal tabloda, tamsayılık koşulunu ihlal eden ve en büyük kesirsel kısma sahip olan temel değişken $x_2$ 'nin satır denklemi aşağıda verilmiştir:

x_2 + 1,5x_3 - 0,8x_4 + 2,1x_5 = 4,6

Çözümün tamsayılı olabilmesi için $x_2$ satırı üzerinden Gomory kesme düzlemi (fractional cut) oluşturulacak ve modele yeni bir kısıt (yeni bir $S_g$ aylak değişkeni ile) eklenecektir.

Buna göre, yeni kısıt eklendikten sonra optimum tamsayılı çözüme ulaşmak amacıyla başlatılacak dual simpleks yönteminin ilk adımında, sırasıyla temelden çıkacak ve temele girecek değişkenler hangileridir?

S_g

temelden çıkar,

x_4

temele girer.

x_2

temelden çıkar,

x_3

temele girer.

S_g

temelden çıkar,

x_3

temele girer.

S_g

temelden çıkar,

x_5

temele girer.

x_2

temelden çıkar,

x_4

temele girer.

Cevabı ve açıklamayı göster

Cevap: $S_g$ temelden çıkar, $x_3$ temele girer.

Cevap

Çözüm sürecinde temelden çıkacak değişken S_g, temele girecek değişken ise x_3 olmalıdır.

Verilen denklemdeki katsayıların kesirsel kısımları doğru bir şekilde ayrıştırıldığında; -0,8'in kesirsel kısmı 0,2 olarak bulunur. Diğer kesirsel kısımlar 0,5 (x_3 için), 0,1 (x_5 için) ve 0,6 (sağ taraf sabiti) şeklindedir. Kesme düzlemi eşitliğe çevrildiğinde yeni satır 'S_g - 0,5x_3 - 0,2x_4 - 0,1x_5 = -0,6' halini alır. Bu durumda değeri -0,6 olan S_g değişkeni temelden çıkmak zorundadır. Girecek değişkeni bulmak için Z satırı katsayıları ile yeni satırın negatif katsayıları oranlanır (2/0,5=4, 3/0,2=15, 0,5/0,1=5). En küçük oran olan 4, x_3 değişkenine ait olduğu için x_3 temele girer.

Adım Adım Çözüm

1

Verilen denklemdeki tüm katsayıların ve sağ taraf sabitinin kesirsel kısımlarını (f = a - ⌊a⌋) hesapla.

4,6'nın kesirsel kısmı: 0,6
1,5'in kesirsel kısmı: 0,5
-0,8'in kesirsel kısmı: -0,8 - (-1) = 0,2
2,1'in kesirsel kısmı: 0,1

Gomory kesme düzlemi kısıtını oluşturmak için denklemdeki elemanların yalnızca pozitif kesirsel kısımlarına ihtiyaç vardır.

2

Bulunan kesirsel kısımlarla Gomory kısıtını (∑ f_j x_j ≥ f_0) kur ve S_g aylak değişkenini ekleyerek eşitliğe dönüştür.

0,5x_3 + 0,2x_4 + 0,1x_5 ≥ 0,6 eşitsizliği -0,5x_3 - 0,2x_4 - 0,1x_5 ≤ -0,6 formuna getirilir. S_g eklenince: S_g - 0,5x_3 - 0,2x_4 - 0,1x_5 = -0,6 elde edilir.

Dual simpleks yöntemini işletebilmek için kısıtın eşitlik formunda olması ve sağ taraf sabitinin (fizibilite ihlalini göstermek üzere) negatif kalması gerekir.

3

Yeni satır üzerinden temelden çıkacak değişkeni belirle.

S_g değişkeninin aldığı değer -0,6'dır ve negatiflik koşulunu ihlal ettiği için temelden çıkacak değişken S_g olarak belirlenir.

Dual simpleks yönteminde çözüme sağ taraf sabiti negatif olan (fizibil olmayan) temel değişken temelden çıkarılarak başlanır.

4

Temele girecek değişkeni bulmak için negatif katsayılı (a_rj < 0) karar değişkenleri üzerinden oran testini |Z_j / a_rj| uygula.

x_3 oranı: |2 / -0,5| = 4
x_4 oranı: |3 / -0,2| = 15
x_5 oranı: |0,5 / -0,1| = 5
En küçük oran 4 olduğundan temele girecek değişken x_3 olur.

Dual simpleks iterasyonunda amaç fonksiyonunun optimallik koşulunu bozmamak adına oran testi sonucu en küçük olan değişken temele alınır.

Anahtar Kavram

Gomory Kesme Düzlemi kısıtının doğru oluşturulması ve ardından Dual Simpleks Yönteminde pivot eleman seçimi (oran testi).

Alternatif Yöntem

Negatif sayıların kesirsel kısmını zihinden pratik olarak bulmak için, sayının ondalık kısmını 1'e tamamlayan değeri düşünebilirsiniz. Örneğin -0,8 sayısında 0,8'i 1'e tamamlayan değer 0,2'dir. Bu yöntem işlem hızınızı ve doğruluğunuzu artırır.

Tahmini Süre:2m 0s

Soru 59Soru →

Bir lojistik firması, araç filosu için iki farklı tipte (A ve B) yeni taşıma aracı almayı planlamaktadır. Firmanın bu alımlar için garaj kapasitesi ve bütçe sınırları bulunmaktadır. A tipi araç sayısını $x_1$ ve B tipi araç sayısını $x_2$ ile gösteren ve günlük taşıma kapasitesini maksimize etmeyi amaçlayan tamsayılı programlama modeli aşağıda formüle edilmiştir:

Maksimum \quad Z = 3x_1 + 4x_2

Kısıtlar:

2x_1 + 4x_2 \leq 17 \quad \text{(Bütçe kısıtı)}

4x_1 + 2x_2 \leq 19 \quad \text{(Garaj kısıtı)}

x_1, x_2 \geq 0 \text{ ve tamsayı}

Bu problemin grafik çözüm yöntemi ile elde edilen tamsayılı optimum çözümünde amaç fonksiyonu ( $Z$ ) değeri kaçtır?

17

18

20

20.5

24

Cevabı ve açıklamayı göster

Cevap: 18

Cevap

Tamsayılı optimum çözüm değeri 18'dir.

Tamsayılı programlama modellerinde grafik çözüm uygulanırken, doğrusal programlama bölgesinin içindeki tamsayı noktaları araştırılır. Bu problemde doğrusal programlamanın kesişim noktası (3.5, 2.5) olup Z=20.5 değerini verir. Ancak değişkenler tamsayı olmalıdır. Bu noktaya yakın tamsayı koordinatları test edildiğinde; (4, 2) ve (3, 3) noktalarının kısıtları ihlal ettiği görülür. Uygun çözüm alanı içinde kalan tamsayı noktalarından (3, 2) noktasında Z=17, (2, 3) noktasında ise Z=18 değeri elde edilir. Amaç maksimizasyon olduğu için en iyi tamsayılı çözüm Z=18'dir.

Adım Adım Çözüm

1

Problemin tamsayı kısıtları göz ardı edilerek doğrusal programlama (DP) gevşetmesinin optimum noktasını hesapla.

2x_1 + 4x_2 = 17

ve

4x_1 + 2x_2 = 19

denklemlerinin ortak çözümünden

x_1 = 3.5

ve

x_2 = 2.5

bulunur. Bu noktada

Z = 20.5

'tir.

Grafik yöntemde tamsayılı çözümü ararken, öncelikle sürekli (kesirli) çözüm alanının tepe noktasını bulmak, hangi tamsayı noktalarını incelememiz gerektiği konusunda yön gösterir.

2

DP optimumuna (3.5, 2.5) yakın olan ve kısıtları sağlayan (uygun) tamsayı noktalarını belirle.

(3, 2)

noktası kısıtları sağlar (

14 \leq 17

ve

16 \leq 19

).

(2, 3)

noktası kısıtları sağlar (

16 \leq 17

ve

14 \leq 19

). Yuvarlama ile elde edilebilecek

(4, 2)

ve

(3, 3)

gibi diğer noktalar ise kısıtları sağlamaz (uygun değildir).

Tamsayılı programlamada çözüm, uygun bölgenin içindeki veya sınırındaki tamsayı koordinatlı noktalarda aranmalıdır. Kesirli çözümü basitçe yuvarlamak genellikle kısıtları ihlal eder.

3

Belirlenen uygun tamsayı noktalarında amaç fonksiyonu (

Z

) değerlerini karşılaştırarak maksimum olanı seç.

(3, 2)

noktası için

Z = 3(3) + 4(2) = 17

.

(2, 3)

noktası için

Z = 3(2) + 4(3) = 18

. Maksimum değer 18'dir.

Mümkün olan tüm uygun tamsayı çözümleri arasından, amaç fonksiyonunu en çoklaştıran değer optimum tamsayılı çözümdür.

Anahtar Kavram

Tamsayılı Programlamada Grafik Çözüm ve Yuvarlama Hataları

Soru 60Soru →

Sanayi ve Teknoloji Bakanlığı, bölgesel teşvik programı kapsamında 5 farklı ihtisas organize sanayi bölgesi (OSB) projesini ( $x_1, x_2, x_3, x_4, x_5$ ) değerlendirmektedir. Her bir $x_i$ karar değişkeni, $i$ . projenin yatırım programına alınması durumunda $1$ , aksi halde $0$ değerini almaktadır.

Bölgesel kalkınma dengelerini gözetmekle görevli planlama komisyonu şu stratejik kuralı belirlemiştir:

'Kuzey bölgesinde planlanan 1, 2 ve 3 numaralı OSB projelerinden hiçbiri yatırım programına alınmazsa, Güney bölgesindeki 4 ve 5 numaralı OSB projelerinin her ikisinin de kesinlikle yatırım programına alınması zorunludur. Ancak Kuzey bölgesindeki projelerden en az biri onaylanırsa, Güney bölgesindeki projelerin seçimi tamamen serbest bırakılacaktır.'

Buna göre, komisyonun bu stratejik kararını tek başına ve eksiksiz olarak ifade eden en uygun sıfır-bir (0-1) tamsayılı programlama kısıtı aşağıdakilerden hangisidir?

2x_1 + 2x_2 + 2x_3 + x_4 + x_5 \geq 2

x_1 + x_2 + x_3 + x_4 + x_5 \geq 2

x_4 + x_5 \leq 2x_1 + 2x_2 + 2x_3

x_4 + x_5 - 2x_1 - 2x_2 - 2x_3 \geq 0

x_1 + x_2 + x_3 + 2x_4 + 2x_5 \geq 4

Cevabı ve açıklamayı göster

Cevap: $2x_1 + 2x_2 + 2x_3 + x_4 + x_5 \geq 2$

Cevap

İstenen stratejik durumu sağlayan doğru eşitsizlik

2x_1 + 2x_2 + 2x_3 + x_4 + x_5 \geq 2

kısıtıdır.

Mantıksal modellemelerde 'A durumu gerçekleşmezse B durumu olmalıdır' koşulu, değişkenler arasına cezalandırıcı (veya dengeleyici) bir katsayı eklenerek çözülür. Doğru kısıtta (

2x_1 + 2x_2 + 2x_3 + x_4 + x_5 \geq 2

), Kuzey projelerinin toplamı

0

olduğunda eşitsizlik

x_4 + x_5 \geq 2

halini alarak

4

ve

5

numaralı projeleri zorunlu kılar. Kuzey projelerinden herhangi biri

1

değerini aldığında ise sol taraftaki toplam en az

2

olacağından,

x_4

ve

x_5

değişkenleri sıfır dahi olsa eşitsizlik (

2+0+0 \geq 2

) sağlanır ve böylece Güney projelerinin seçimi serbest kalmış olur.

Adım Adım Çözüm

1

Koşulun bağlayıcı olduğu durumu matematiksel olarak ifade et.

Kuzey projelerinden hiçbiri seçilmezse durumu:

x_1 + x_2 + x_3 = 0

.

Bu durumda Güney projelerinin ikisi de zorunludur:

x_4 = 1

ve

x_5 = 1

, yani

x_4 + x_5 \geq 2

olmalıdır.

2

Koşulun serbest bıraktığı durumu analiz et.

Kuzey projelerinden en az biri seçilirse durumu:

x_1 + x_2 + x_3 \geq 1

.

Bu durumda

x_4

ve

x_5

için hiçbir kısıtlama (zorunluluk) olmamalıdır, yani eşitsizliğin sağladığı minimum değer

x_4 + x_5 \geq 0

(veya daha küçük bir sayı) olmalıdır.

3

İki durumu tek bir 'Big-M' benzeri mantıksal eşitsizlikte birleştir.

Genel form:

x_4 + x_5 \geq 2 - M(x_1 + x_2 + x_3)

.

Buradaki

M

katsayısı,

x_1+x_2+x_3 \geq 1

olduğunda eşitsizliğin sağ tarafını

0

veya altına düşürecek kadar büyük olmalıdır.

4

En uygun

M

katsayısını belirle ve denklemi düzenle.

M=2

seçilirse:

x_4 + x_5 \geq 2 - 2(x_1 + x_2 + x_3)

.

Terimleri aynı tarafa topladığımızda doğru kısıt olan

2x_1 + 2x_2 + 2x_3 + x_4 + x_5 \geq 2

elde edilir.

Anahtar Kavram

Sıfır-Bir Tamsayılı Modellerde Şartlı (Mantıksal) Kısıtların Modellenmesi

Tahmini Süre:2m 0s

Tamsayılı Programlama

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Daha Fazla Pratik

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

İpuçları

Daha Fazla Pratik

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Daha Fazla Pratik

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

İpuçları

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Alternatif Yöntem

Cevap