İKİLİ DOĞRUSAL PROGRAMLAMA NEDİR? Yazdır

Metodunu ilk tahlil eden ve geliştiren iktisatçılar Von Neumann. D. Gale. H. V. W. Kuhn. A. W. Tucker. L. V. Kantoroviç. G. B. Dantzigve R. Dorfman'dır.

 

Doğrusal programlamada, her maksimizasyon probleminin yanında, ona bağlı bir de minimizasyon problemi vardır.

Bu iki problemden, esas olarak alınana primal denir. Diğeri ise duat problem olarak adlandırılır.

Maksimizasyon ve minimizasyon problemlerinden herhagi birinin primal problem olması mümkündür. Bu takdirde, öbürü duat problemin yerini alır.

Ansiklopedi'nin Doğrusal Programlama ve Simplex Çözüm maddelerinde verilmiş misalden, ikili Doğrusal Programlama'nın izahında da yararlanabiliriz.

iki çeşit input ile iki çeşit output yapan bir firma olsun. İnput'lar emek ve sermaye'dir. Emeğin kapasitesi 100 iş/saat ve sermayenin kapasitesi 50 makine/saat'tir. Firmanın faaliyet hedefi, mümkün olan en yüksek kâr miktarını elde etmektir.

Bu takdirde, primat problem, bir maksimizasyon problemidir.

Primal problem'i şöyle ifade edebiliriz.

PRİMAL PROBLEM

__________________

(X₁ ³ , X₂ ³ 0              olmak kaydile;

__________________

a₁₁ X₁+a₁₂X₂≤C₁

a₂₁ X₁+a₂₂X₂≤C₂          durumlarına göre;

__________________

P=p₁X₁+p₂X₂              nin maksimizasyonu'dur.

Primat problemde;

P                   ,kârdır.

X₁ ve X₂ , imal edilen mallar yahut output çeşitleridir.

C₁ ve C₂ , emeğin ve sermayenin kapasiteleridir.

p₁ ve p₂ , imal edilen iki çeşit maldan herbirinin ünite başına getireceği kârdır.

a₁₁ ve a₁₂ , imal edilen X₁ ve X₂ için, gölge fiyatı Y₁ olan emek /sporlarının miktarlarını her biri için ayrı ayrı göstermektedir.

a₂₁ ve a₂₂ , imal edilen X₁ ve X₂ için gölge fiyatı Y₂ olan sermaye inputlarının miktarlarını herbiri için ayrı ayrı göstermektedir.

Emek ve sermaye kapasiteleri sınırlı olduğuna göre Y₁ poflarının toplamı C₁ i aşamaz. Y₂ inputlarının azamî miktarı da, C₂ den fazla olamaz.

a_llX₁ + a_l2X₂ nin toplamı C₁ den ve a₂₁X₂ + a₂₂X₂ nin toplamı C₂ den küçük olduğunda, tam kapasite kullanılmıyor demektir.

Kullanılmayan kapasiteleri M₁ ve M₂ değişkenleriyle ifade edelim. M₁ ile kullanılmayan emek kapasitesini ve M₂ ile kullanılmayan sermaye kapasitesini gösterelim. M₁ ve M₂ değişkenlerini de ilâve ederek, primal problemin denklemlerini aşağıdaki şekilde yazalım.:

PRİMAL PROBLEM

_______________________

(X₁³0,X₂³0,M₁³0, M₂³0)          olmak kaydı ile:

___________________________

a₁₁X₁ + a₁₂X₂+ M₁ = C₁

a₂₁X₁ + a₂₂X ₂ + M₂ =C₂             durumlarına göre

____________________________

P = p₁X₁ + p₂X₂                         nin maksimizasyonu'dur.

Primat problemde  M₁ ve M₂ değişkenlerini denklemlerin sol yanına alalım:

PRİMAL PROBLEM

_____________________

M₁ = C₁ — a_1lX₁ — a₁₂X₂

M₂ = C₂ — a_2lX_l—a₂₂X₂                durumlarına göre:

_________________________

P = O + p₁X₁+p₂X₂                    nin maksimizasyonu'dur.

Ve bu denklemleri, matris şekline çevirelim :

		X1	X2
P	O	p1	p2
M1	C1	-a11	-a12
M2	C2	-a21	a-22

Şimdi, dual probleme geçelim.

Duat problemi şöyle ifade edebiliriz:

DUAL PROBLEM

_________________

(Y₁³0 , Y₂³0)              olmak kaydı ile;

____________________

A₁₁Y₁ + a₂₁Y₂³p₁

A_l2Y_l + a₂₂Y2³p₂        durumlarına göre:

____________________

V= C₁ Y₁ + C₂ Y₂ nin minimizasyonu'dur.

Dual problemde , V = C₁ Y₁ + C₂ Y₂ , «maliyet minimizasyonu» nu hedef tutan objective function, yahut maliyet minimizasyonu hedef fonksiyonudur.

V                firmanın kullanabileceği input değerlerinin toplamıdır.

Y_l ve Y₂ ,     input türlerinden herbirinin gölge fiyatlarıdır.

C₁ ve C₂ ,    gölge fiyatların katsayıları olup. primal problemdeki input kapasiteleridir.

Dual problemdeki an a₁₁ Y₁ + a_2l Y₂ ³ p₁ rı eşitsizliğinde; X₁ malından bir aded elde etmek için gerekli emek inputu ile bunun gölge tiyaıite çarpımına, gerekli sermaye inputu ile bunun gölge fiyatı ile çarpımı hasılası ilâve edilince, sonuç p_l den küçük bir rakam ise, maliyette bir şişkinlik yahut bir kâr kaybı var demektir. Gerçekleştirilememiş kârı yahut kâr kaybını L₁ değişkeni ile fiade edelim.

Aynı şekilde, a_l2Y₁ + a₂₂Y₂³0 eşitsizliğinde de, input değerlerile hedef tutulan kâr arasındaki boşluğu L₂ ile gösterelim.

L₁ ve L₂ değişkenlerini katarak, dual problemin eşitsizliklerini aşağıdaki denklemler haline getirelim:

DUAL PROBLEM

______________________

(Y₁³O , Y₂³O , L₁³O , L₂³O) olmak kaydile;

__________________________

A_1l Y₁ + a_2l Y₂ - L_l = p_l

a_l2 Y₁ + a₂₂ Y₂ – L₂ = p₂    durumlarına göre

__________________________

V = C₁ Y_l + C₂ Y₂      nin minimizasyonu'dur.

Dual problemde. L₁ ve L₂ değişkenlerini denklemlerin sol yanına alalım :

DUAL PROBLEM

L₁=p₁+a₁₁Y₁+ a₂₁ Y₂

L₂=p₂+a₁₂Y₁+ a₂₂ Y₂            durumlarınagöre

V = O + C₁ Y₁ + C_t Y_e         nin minimizasyonu'dur.

Ve dual problemin denklemlerini matris şekline çevirelim :

			Y2
V	0
L,	-TTl	au	a21
>-2	-T,	ai2	a22

Primal ve dual problemlerin matrisleri arasındaki ilişki, ilk bakışta belirgin bir niteliktedir. Dual problem matrisinin birinci sütunu, primat problem matrisinin hedef fonksiyon, yahut objective tunction'udur. Primal problem matrisinin birinci sütunu da, dual problem matrisinin hedef fonksiyonudur. Primat problem matrisinin ikinci sırası, eksi işaretleri dikkate alınmazsa, dual problem matrisinin ikinci sütunudur. Birinci matrisin satırlarını sırasile sütun haline çevirerek, dual matris elde edilmektedir.

Her iki matrisi birleştirerek bir kombine matris tertiplemek mümkündür:

(V)             -(L₁)        -(L₂)

İkili Doğrusal Programlamada, problemlerden herhangi biri için optimal çözüm varsa, diğeri için de optimal çözüm vardır. Primat problemin hedef fonksiyonunun maksimum değeri, dual problemin minimum değerine eşittir. Yani, P = V dır. Aynı zamanda, bir birirn üretmek üzere kullanılan kaynakların değeri, ürün birimi hasılâtından fazla ise o ürün optimal çözüm sisteminde yer almayacaktır, L₁ veya L₂ nin pozitif değer taşımaları halinde, ilişkin oldukları mal üretilmeyecektir.

Ansiklopedi'nin Simplex Çözüm maddesindeki örnekte gösterildiği gibi, primaI problemin gerçekleşen bir optimal çözümü, X, = 31.25 ve X2 = 62.5 tur. Primal problem matrisi'ndeki bu sonuç, kombine matris için de geçerlidir.

Dual problem'in çözümü, şudur:

		M2	M1	(L2)   (L1)
P	218.75		-1.25
X2   X1	62.5   31 25

 

Dual problemin çözümünde, L₁ ve L₂ gölge değişkenleri sıfır değerindedir ve bunlar kombine matrisin sağında gösterilmektedir.. Optimal temel çözüm. Y₂ = 0.6/032 ve = 1.25 tir. Y₁=1.25 tir. V = C₁Y₁+C₂Y₂ olarak ifade edilmiş dual hedef fonksiyonu şöyle rakamlandırılmaktadır:

V = 218.75 = 100 (1.25) + 50 (0.6/032)

Almancası : Duales Problem.

Fransızcası : probléme dual de la programmation linéaire.

İngilizcesi : dual linear programming.

(Bk; Doğrusal Programlama, Simplex Çözürn. Doğrusal ekonomiler).