Soru

Zorluk: OrtaYapay Değişkenli Yöntemler (Büyük-M ve İki Evreli)

Bir karar verici, aşağıdaki doğrusal programlama modelini Büyük-M (Çok Büyük Katsayılar) yöntemini kullanarak çözmek amacıyla standart forma dönüştürmek istemektedir:

Maks Z=2x1+4x2Maks \ Z = 2x_1 + 4x_2
Kısıtlar:
x1+x210x_1 + x_2 \geq 10
x1,x20x_1, x_2 \geq 0

MM çok büyük bir pozitif sayıyı temsil ettiğine göre; bu yönteme uygun olarak modele dahil edilmesi gereken ek değişkenler ve oluşturulacak yeni amaç fonksiyonu (ZyeniZ_{yeni}) aşağıdakilerin hangisinde doğru olarak verilmiştir?

  1. s1s_1 artık (surplus) ve a1a_1 yapay değişkenleri modele dahil edilir; Zyeni=2x1+4x2Ma1Z_{yeni} = 2x_1 + 4x_2 - Ma_1Cevap
  2. B
    s1s_1 dolgu (slack) ve a1a_1 yapay değişkenleri modele dahil edilir; Zyeni=2x1+4x2Ma1Z_{yeni} = 2x_1 + 4x_2 - Ma_1
  3. C
    s1s_1 artık (surplus) ve a1a_1 yapay değişkenleri modele dahil edilir; Zyeni=2x1+4x2+Ma1Z_{yeni} = 2x_1 + 4x_2 + Ma_1
  4. D
    Sadece s1s_1 dolgu (slack) değişkeni modele dahil edilir; Zyeni=2x1+4x2Z_{yeni} = 2x_1 + 4x_2
  5. E
    Sadece a1a_1 yapay değişkeni modele dahil edilir; Zyeni=2x1+4x2Ma1Z_{yeni} = 2x_1 + 4x_2 - Ma_1

Cevap

Modelde s1s_1 artık ve a1a_1 yapay değişkenleri kullanılmalı; amaç fonksiyonu Zyeni=2x1+4x2Ma1Z_{yeni} = 2x_1 + 4x_2 - Ma_1 şeklinde kurulmalıdır.
Doğru seçenek olan artık değişken çıkarma ve yapay değişken ekleme işlemi, 'büyük eşit' kısıtlarının standart formdaki temel gerekliliğidir. Maksimizasyon problemlerinde yapay değişkenlerin katsayısının -M olarak seçilmesi, optimal çözümde bu değişkenlerin değerinin sıfır olmasını zorlayan bir ceza mekanizmasıdır.

Adım Adım Çözüm

1
Kısıt yapısını analiz et.
x1+x210x_1 + x_2 \geq 10 kısıtı 'büyük eşit' tipindedir.
Yapay değişkenli yöntemler, başlangıçta uygun bir temel çözüm bulunamadığında (özellikle >= veya = kısıtlarında) kullanılır.
2
Kısıtı eşitlik haline getir.
x1+x2s1+a1=10x_1 + x_2 - s_1 + a_1 = 10
>= kısıtını dengelemek için bir artık (surplus) değişken (s1s_1) çıkarılır. Ancak başlangıçta orijin (0,00,0) uygun olmadığından bir yapay değişken (a1a_1) eklenerek başlangıç temeli oluşturulur.
3
Amaç fonksiyonunu ceza katsayısı ile güncelle.
Maksimizasyon için Ma1-Ma_1 eklenir.
Büyük-M yönteminde amaç, yapay değişkenleri mümkün olan en kısa sürede temelden çıkarmaktır. Maksimizasyon probleminde bunu sağlamak için yapay değişken çok küçük (negatif büyük) bir değerle çarpılır.

Anahtar Kavram

Büyük-M Yönteminde Değişken Dönüşümleri

Daha Fazla Pratik

İki evreli (Two-Phase) yöntemde birinci evrenin amaç fonksiyonunun nasıl kurulduğunu inceleyerek bu iki yöntemi karşılaştırabilirsiniz.
Tahmini Süre:1m 30s
Bu soruyu puanla