Yöneylem Araştırması #14 | Dual Çözüm Tabloda Hazır: Ters Matris ve Optimal Dual Çözüm
Dualite Teorisi ve SonuçlarıEğitmen: Dr. Süleyman Burak ÇELİK
Optimal tablo elinizde; dual modelin optimal çözümünü bulup dual amacın z'ye eşit olduğunu gösterin. Çoğu kişi dual modeli baştan simpleksle çözmeye girişir ya da sayıları tablonun rastgele bir sütunundan okur; oysa dual çözüm tabloda hazırdır ve doğru sütunlar başlangıçta temelde olanlardır. Yöneylem Araştırması serisinin bu dersinde primal–dual ilişkilerini, ters matrisi ve optimal dual çözümü iki yolla bir sınav sorusuyla, her işlemi tek tek yaparak öğreniyoruz. Bu derste: - Sezgi (birim matris ters matris olur): başlangıç tablosunda s1, s2, s3 sütunları birim matristir ve z satırında sıfırdır. Simpleks her adımda bütün sütunlara aynı satır işlemlerini uygular; bu işlemlerin kaydı o üç sütunda birikir: gövdede ters matris, z satırında dual çözüm. - İki yol: Yöntem 1, y = başlangıç temel değişkeninin optimal z katsayısı + özgün amaç katsayısı (gevşekte + 0, yapay değişkende + (−M)). Yöntem 2, y = c_B × ters matris; c_B optimal temel değişkenlerin özgün katkıları, Temel sütunundaki sırayla. En büyüklemede uygun her primal–dual çift için z ≤ w; optimumda z = w. - Örnek 1 (sınav sorusu, a–e): kova x1, kasa x2, sepet x3; en büyük z = 5 x1 + 7 x2 + 8 x3; kalıplama 3 x1 + 2 x2 + 2 x3 ≤ 600, montaj x1 + 2 x3 ≤ 580, paketleme 3 x1 + x2 + 2 x3 ≤ 520; optimal tabloda kasa 80, sepet 220, s2 = 140, z = 2320. (a) Dual model: y1, y2, y3 (lira/dakika); en küçük w = 600 y1 + 580 y2 + 520 y3; 3 y1 + y2 + 3 y3 ≥ 5; 2 y1 + y3 ≥ 7; 2 y1 + 2 y2 + 2 y3 ≥ 8; y1, y2, y3 ≥ 0. (b) Ters matris başlangıç temel değişkenlerinin (s1, s2, s3) sütunlarından okunur; satır sırası kasa, sepet, s2: kasa 1, 0, −1; sepet −1 ÷ 2, 0, 1; s2 1, 1, −2. (c) Yöntem 1: z satırında s1 3, s2 0, s3 1; özgün katsayı 0 olduğundan y = (3, 0, 1) lira/dakika (montajda 140 dakika boş, gölge fiyatı 0). (d) Yöntem 2: c_B = (7, 8, 0). y1 = 7 × 1 + 8 × (−1 ÷ 2) + 0 × 1 = 7 − 4 + 0 = 3; y2 = 7 × 0 + 8 × 0 + 0 × 1 = 0; y3 = 7 × (−1) + 8 × 1 + 0 × (−2) = −7 + 8 + 0 = 1; aynı (3, 0, 1). Sıra (8, 7, 0) karışırsa y1 = 9 ÷ 2 çıkar, yanlış. (e) Kova 3 × 3 + 1 × 0 + 3 × 1 = 12 ≥ 5 (12 − 5 = 7, tablodaki kova katsayısı); kasa 2 × 3 + 0 × 0 + 1 × 1 = 7 ≥ 7; sepet 2 × 3 + 2 × 0 + 2 × 1 = 8 ≥ 8; y ≥ 0, dual uygun. w = 600 × 3 + 580 × 0 + 520 × 1 = 1800 + 0 + 520 = 2320 = z. - Örnek 2 (şimdi siz deneyin): en büyük z = 6 x1 + 2 x2; şeker 2 x1 + x2 ≤ 80, sipariş x1 + x2 ≥ 50; s1 gevşek, e2 fazla, R yapay (Büyük M, amaç katsayısı −M). Optimal tabloda x1 = 30, x2 = 20, z satırı s1 4, e2 2, R −2 + M, z = 220. (a) Başlangıç temel değişkenleri s1 ve R (e2 değil): y1 = 4 + 0 = 4; y2 = (−2 + M) + (−M) = −2; fazla sütunu 2, işareti çevrilince yine −2; negatif değer en büyüklemede ≥ kısıtın dual değişkeni için olağandır. (b) Ters matris [1 −1; −1 2], c_B = (6, 2): y1 = 6 × 1 + 2 × (−1) = 4; y2 = 6 × (−1) + 2 × 2 = −2; w = 80 × 4 + 50 × (−2) = 320 − 100 = 220 = z. - Tuzaklar: ters matrisi optimal temel değişkenlerin (kasa, sepet) sütunlarından okumak; temel katkı satırını yanlış sırayla yazmak (8, 7, 0 ile y1 = 9 ÷ 2); yapay değişkende −M düzeltmesini unutmak ya da negatif dual değeri hata sanmak. Optimum dışındaki uygun çiftte z ≤ w olağandır; eşitlik yalnız optimumda. - Kural: optimal tabloda dual çözüm hazırdır: başlangıç temel sütunlarının z katsayısına özgün katsayıyı ekle ya da temel katkı satırını ters matrisle çarp. Bölümler: 0:00 Önceki ders, bugünün konusu ve sınav sorusu: dual çözümü baştan çözmeden bulun 1:03 Tablo düzeni: başlangıçtaki birim matris sonda ters matris olur 1:51 İki yöntem ve amaç değerleri kuralı: z ≤ w, optimumda eşit 2:43 Örnek 1: plastik atölyesi, optimal tablo ve beş adımlı prosedür 3:45 (a) Dual modeli kurmak 4:47 (b) Ters matrisi başlangıç temel sütunlarından okumak 5:28 (c) Yöntem 1: z satırından y = (3, 0, 1) 6:14 (d) Yöntem 2: c_B × ters matris, sıra tuzağı 7:22 (e) Dual kısıtlar ve w = z = 2320 8:25 Sağlama: z doğrudan, 2080 ≤ 2320 ≤ 2400 9:32 Örnek 2: şekerleme atölyesi, büyük eşit kısıt ve Büyük M 10:38 Örnek 2 çözümü: yapay düzeltmesi, y = (4, −2), w = 220 12:11 Üç sık hata 12:55 Ne yaptık? Yöntem geri sayımı 13:55 Kural ve sıradaki ders Sıradaki ders: ters matrisle tablo hesabı ve dual kısıtların yorumu. Kaynak kitap: Hamdy A. Taha, Operations Research: An Introduction, 10. baskı (Pearson, 2017), Bölüm 4 (§4.2.1–4.2.3, primal–dual ilişkileri: tablo düzeni, ters matris ve optimal dual çözüm). Konu sırası, tanımlar ve kurallar kitaptan alındı; örnekler ve sayılar özgündür. Endüstri Mühendisliği öğrencileri için Yöneylem Araştırması serisinin on dördüncü dersi. Ön koşul: serinin önceki dersleri (doğrusal programlama modeli, simpleks tablosu, dual modelin kurulması, gölge fiyat ve duyarlılık analizi).
Bu videoyu izlemek için Premium üyelik gerekir.