Examkin

Soru

Zorluk: ZorDualite Kavramı ve Dual Model Kurulumu

Bir endüstri mühendisi, bir üretim sürecini optimize etmek amacıyla karar değişkenlerinden birinin miktar, diğerinin ise pozitif veya negatif değer alabilen bir kalite sapması olduğu aşağıdaki doğrusal programlama modelini kurmuştur:

Maksimum Z=12x1+8x2\text{Maksimum } Z = 12x_1 + 8x_2
Kısıtlar:
3x1+2x2≤243x_1 + 2x_2 \leq 24
4x1−x2≥104x_1 - x_2 \geq 10
x1≥0,x2 is¸aretsizx_1 \geq 0, x_2 \text{ işaretsiz}

Bu modelin duali alındığında, birinci kısıta karşılık gelen dual karar değişkeni y1y_1 ve ikinci kısıta karşılık gelen dual karar değişkeni y2y_2 olmak üzere, elde edilecek doğru dual model aşağıdakilerden hangisidir?

  1. Min W=24y1+10y2\text{Min } W = 24y_1 + 10y_2
    Kısıtlar:
    3y1+4y2≥123y_1 + 4y_2 \geq 12
    2y1−y2=82y_1 - y_2 = 8
    y1≥0,y2≤0y_1 \geq 0, y_2 \leq 0    Cevap
  2. B
    Min W=24y1+10y2\text{Min } W = 24y_1 + 10y_2
    Kısıtlar:
    3y1+4y2≥123y_1 + 4y_2 \geq 12
    2y1−y2≥82y_1 - y_2 \geq 8
    y1≥0,y2≥0y_1 \geq 0, y_2 \geq 0
  3. C
    Maks W=24y1+10y2\text{Maks } W = 24y_1 + 10y_2
    Kısıtlar:
    3y1+4y2≤123y_1 + 4y_2 \leq 12
    2y1−y2≤82y_1 - y_2 \leq 8
    y1≥0,y2≤0y_1 \geq 0, y_2 \leq 0
  4. D
    Min W=24y1+10y2\text{Min } W = 24y_1 + 10y_2
    Kısıtlar:
    3y1+4y2≤123y_1 + 4y_2 \leq 12
    2y1−y2=82y_1 - y_2 = 8
    y1 is¸aretsiz,y2≥0y_1 \text{ işaretsiz}, y_2 \geq 0
  5. E
    Min W=24y1+10y2\text{Min } W = 24y_1 + 10y_2
    Kısıtlar:
    3y1+4y2≥123y_1 + 4y_2 \geq 12
    2y1−y2≤82y_1 - y_2 \leq 8
    y1≥0,y2 is¸aretsizy_1 \geq 0, y_2 \text{ işaretsiz}

Cevap

Doğru dual model, amaç fonksiyonunun Minimum olduğu, birinci kısıt yönünden dolayı y1 >= 0 ve ikinci kısıt yönünden dolayı y2 <= 0 sınır koşullarına sahip, x2'nin işaretsiz olmasından dolayı da ikinci dual kısıtın eşitlik olduğu modeldir.
Primal model Maksimum yapısında olduğundan duali Minimum olur. Birinci kısıt ≤\leq yönünde olduğu için y1≥0y_1 \geq 0, ikinci kısıt ≥\geq yönünde olduğu için y2≤0y_2 \leq 0 sınır koşuluna sahiptir. Ayrıca primaldeki x2x_2 değişkeni işaretsiz (unrestricted) olduğundan, buna karşılık gelen ikinci dual kısıt bir eşitlik (==) olmalıdır. Doğru model, tüm bu simetrik dualite kurallarının eksiksiz uygulandığı modeldir.

Adım Adım Çözüm

1
Primal modelin amaç fonksiyonu ve kısıt yönleri incelenir.
Amaç fonksiyonu Maksimum olduğundan, dual model Minimum olmalıdır. Birinci kısıt (<=) ve ikinci kısıt (>=) yapısındadır.
Dualite kurallarına göre optimizasyon yönü değişir ve kısıt tipleri dual değişkenlerin işaret sınırlarını belirler.
2
Kısıt işaretlerine göre dual değişkenlerin sınır koşulları belirlenir.
1. kısıt (<=) Maksimum model için standart olduğundan y1≥0y_1 \geq 0 olur. 2. kısıt (>=) standart dışı olduğundan y2≤0y_2 \leq 0 olur.
Maksimum modelde standart kısıt yönü pozitif dual değişkene, ters kısıt yönü negatif dual değişkene karşılık gelir.
3
Primal değişkenlerin işaretlerine göre dual kısıtların yönleri belirlenir.
x1≥0x_1 \geq 0 olduğundan 1. dual kısıt (>=) olmalıdır (Minimum için standart). x2x_2 işaretsiz olduğundan 2. dual kısıt (=) eşitlik olmalıdır.
Primalde standart pozitif değişken standart kısıt yönü üretirken, işaretsiz değişken daima eşitlik kısıtı oluşturur.
4
Katsayılar transpoze edilerek model yazılır.
Amaç: Min W=24y1+10y2\text{Min } W = 24y_1 + 10y_2. 1. Kısıt: 3y1+4y2≥123y_1 + 4y_2 \geq 12. 2. Kısıt: 2y1−y2=82y_1 - y_2 = 8.
Sağ taraf sabitleri dualin amaç katsayılarını, amaç katsayıları ise dualin sağ taraf kısıt sınırlarını oluşturur.

Anahtar Kavram

Dualite Dönüşüm Kuralları ve İşaretsiz Değişkenler

Alternatif Yöntem

Primal modeldeki ikinci kısıtı eksi (-1) ile çarparak (−4x1+x2≤−10-4x_1 + x_2 \leq -10) tüm kısıtları Maksimum model için standart olan ≤\leq formuna getirebilirsiniz. Bu durumda dual değişken y2′≥0y_2' \geq 0 olur ve dual amaç fonksiyonu Min W=24y1−10y2′\text{Min } W = 24y_1 - 10y_2' şeklini alır. Bu yöntem, y2=−y2′y_2 = -y_2' dönüşümü yapıldığında, verilen doğru formülasyon ile tamamen aynıdır.
Tahmini Süre:2m 0s
Bu soruyu puanla

Konular

Dualite Kavramı ve Dual Model Kurulumu

Bu konudan daha fazla soru