Doğrusal Programlama Problemlerinde Dualite

Doğrusal Programlama Problemlerinde Dualite!

Her Doğrusal programlama Problemi için, aynı verileri içeren ilgili eşsiz bir problem vardır ve aynı zamanda orijinal problemi tarif eder. Orijinal problem primal program, karşılık gelen benzersiz problem ise Dual program olarak adlandırılır. İki program birbiriyle çok yakından ilgilidir ve optimalin dual çözümü, primal'in optimal çözümü hakkında tam bilgi verir.

Bu özelliğin farklı faydalı yönleri şunlardır:

(a) Eğer primalde çok sayıda sınır ve az sayıda değişken varsa, hesaplama problemi Dual'e çevirip sonra çözerek önemli ölçüde azaltılabilir.

(b) Doğrusal programlamadaki dualite, ekonomik doğanın kesin sonuçlarına ulaşır. Bu, yöneticilerin alternatif eylem kursları ve göreceli değerleri hakkındaki soruları cevaplamasına yardımcı olabilir.

(d) Doğrusal programlamadaki dualite, her doğrusal programın iki kişilik sıfır toplamlı bir oyuna eşdeğer olduğunu göstermektedir. Bu, doğrusal programlama ve oyun teorisi arasında oldukça yakın ilişkilerin olduğunu gösterir.

1. Primal Kanonik Formdayken İkili Şekillendirme:

Yukarıdaki iki programdan, aşağıdaki noktalar açıktır:

(i) Primerde maksimizasyon problemi, ikilide minimizasyon problemi olur ve bunun tersi de geçerlidir.

(ii) En üst düzeye çıkarma probleminin () kısıtlamaları vardır.

(iii) Eğer primal n değişkenleri ve m kısıtlamaları içeriyorsa, dual m değişkenleri ve n kısıtlamaları içerecektir.

(iv) Primalin kısıtlamalarında b ₁ b ₂, b ₃ ……… b _m sabitleri çiftin nesnel işlevinde ortaya çıkar.

(v) Primalin nesnel işlevindeki c ₁, c ₂, c ₃ c _n sabitleri çiftin sınırlarında belirir.

(vi) Her iki problemdeki değişkenler negatif değildir.

Primal ve dualin kısıtlayıcı ilişkileri aşağıda gösterilmiştir.

Örnek 1:

Primer problemin dualini oluşturur

Çözüm:

Öncelikle ≥ kısıtı, her iki tarafın da -1 ile çarpılmasıyla ≤ kısıtına dönüştürülür.

Örnek 2:

Primer problemin dualini oluşturur

Çözüm:

Y1, Y2, V3 ve V4'ün karşılık gelen ikili değişkenler olmasını sağlayın;

İkili problemin, ilkelden daha az sayıda kısıtlaması olduğundan (4 yerine 2 yerine), sorunu çözmek için daha az çalışma ve çaba gerektirir. Bu, doğrusal programlama problemindeki hesaplama zorluğunun temelde değişken sayısından ziyade kısıtlama sayısı ile ilişkili olduğu gerçeğinden kaynaklanmaktadır.

Örnek 3:

Sorunun ikilisini kur