DOĞRUSAL PROGRAMLAMA
Yöneylem Araştırması modelleri, alternatifler, kısıtlar ve amaç fonksiyonu adı verilen temel elemanlardan oluşur. Karar problemlerinin alternatifleri genelde bilinmeyen değişkenler olarak ortaya çıkar. Bu değişkenler uygun bir matematik model oluşturmak üzere kısıtlar ve amaç fonksiyonu olarak düzenlenir. Modelin çözümü ile tüm kısıtları sağlayan, aynı zamanda da amaç fonksiyonunu optimum (maksimum veya minimum) yapan karar değişkenlerinin değerleri bulunur.
DP, sınırlı kaynakların kullanımını optimum yapmak için geliştirilmiş bir matematiksel modelleme yöntemidir. Bir optimizasyon tekniği olarak belirli ortak özellikleri bulunan problemlere uygulanır. Problemden kaynaklanan bazı özel durumlar dışında tüm DP modelleri üç temel özellik taşır:
Doğrusal amaç fonksiyonu
Doğrusal kısıtlar
Pozitiflik koşulu
Dogrusal amaç fonksiyonu
Tüm organizasyonların varmak istediği bir veya birden çok amaç vardır. Çoğu organizasyonlar kar maksimizasyonu ya da maliyet minimizasyonunu amaç olarak alırlar. DP modellerinde birçok değişkenin doğrusal fonksiyonundan oluşan bir “amaç fonksiyonu” bulunur. Bu fonksiyonu Z , değişkenleri x1 , x2 , ………., xn ve sabit katsayıları da c1 , c2 , ……… cn ile göstermek üzere;
Z = c1 * x1 + c2 * x2 + ......................... + cn * xn
Şeklinde yazılır. Problemin amacı Z ‘i maksimum veya minimum yapa x değerlerinin bulunmasıdır. Eğer kar maksimizasyonu amaçlanmışsa Z’i maksimum yapan, aksi durumda da maliyet minimizasyonu için Z’ i minimum yapan x değerleri aranır.
Doğrusal kısıtlar
Bütün doğrusal fonksiyonlar pozitif sonsuzda maksimum, negatif sonsuzda minimum değerini alırlar. Dolayısıyla doğrusal amaç fonksiyonlarının aynı maksimum ve minimuma sahip olduklarını söyleyebiliriz. Matematiksel olarak anlamsız olan bu sonuçtan kaçınmak için değişkenler üzerinde bazı kısıtlamalar yapılmalıdır. Zaten organizasyonların kaynaklarının da sonsuz olmadığı düşünülürse bu kısıtlamaların modelde yer alması normaldir. DP modellerinde kısıtlar, doğrusal eşitsizliklerden meydana gelir.
a11 , a12 , ........................., amn
ve
b1 , b2 , ..........................., bm
sabit sayılar olmak üzere kısıtlar :
a11 * x1 + a12 * x2 + …………………………+ a1n * xn <= b1
a21 * x1 + a22* x2 + …………………………+ a2n * xn < = b2
..............................................................
..............................................................
am1 * x1 + am2 * x2 + …………………………+ amn * xn <= bm
şeklinde gösterilir. Kısıtlar incelendiğinde şu özellikler göze çarpmaktadır:
Sistemin her satırı genellikle bir eşitsizliktir. Bazı durumlarda eşitlik de olabilir.
Eşitsizliklerin sol tarafları doğrusal fonksiyonlardır.
Kısıtların sayısı (m ) için bir sınırlama yoktur.
Kısıtları ifade eden eşitsizlikler , problemin çözümü olabilecek x değişkenlerinin içinde bulunduğu «çözüm bölgesini» belirler. Sonuçta tüm kısıtları sağlayan optimum(en uygun) çözüm bulunur.
Pozitiflik koşulu
DP ‘ nin gerçek problemlere uygulanmasını kolaylaştırmak amacı ile çözümde karar değişkenlerinin negatif değer alamayacağı koşulu getirilmiştir. Matematik olarak problem çözüldüğünde ;
x1 , x2 , ………., xn >= 0 olmalıdır.
DP modellerinin formülasyonu değişik şekillerde gösterilmektedir. En yaygın gösterim şekli aşağıda verildiği gibi matris notasyonu kullanılarak formüle etmektir.
Yöneylem Araştırması modelleri, alternatifler, kısıtlar ve amaç fonksiyonu adı verilen temel elemanlardan oluşur. Karar problemlerinin alternatifleri genelde bilinmeyen değişkenler olarak ortaya çıkar. Bu değişkenler uygun bir matematik model oluşturmak üzere kısıtlar ve amaç fonksiyonu olarak düzenlenir. Modelin çözümü ile tüm kısıtları sağlayan, aynı zamanda da amaç fonksiyonunu optimum (maksimum veya minimum) yapan karar değişkenlerinin değerleri bulunur.
DP, sınırlı kaynakların kullanımını optimum yapmak için geliştirilmiş bir matematiksel modelleme yöntemidir. Bir optimizasyon tekniği olarak belirli ortak özellikleri bulunan problemlere uygulanır. Problemden kaynaklanan bazı özel durumlar dışında tüm DP modelleri üç temel özellik taşır:
Doğrusal amaç fonksiyonu
Doğrusal kısıtlar
Pozitiflik koşulu
Dogrusal amaç fonksiyonu
Tüm organizasyonların varmak istediği bir veya birden çok amaç vardır. Çoğu organizasyonlar kar maksimizasyonu ya da maliyet minimizasyonunu amaç olarak alırlar. DP modellerinde birçok değişkenin doğrusal fonksiyonundan oluşan bir “amaç fonksiyonu” bulunur. Bu fonksiyonu Z , değişkenleri x1 , x2 , ………., xn ve sabit katsayıları da c1 , c2 , ……… cn ile göstermek üzere;
Z = c1 * x1 + c2 * x2 + ......................... + cn * xn
Şeklinde yazılır. Problemin amacı Z ‘i maksimum veya minimum yapa x değerlerinin bulunmasıdır. Eğer kar maksimizasyonu amaçlanmışsa Z’i maksimum yapan, aksi durumda da maliyet minimizasyonu için Z’ i minimum yapan x değerleri aranır.
Doğrusal kısıtlar
Bütün doğrusal fonksiyonlar pozitif sonsuzda maksimum, negatif sonsuzda minimum değerini alırlar. Dolayısıyla doğrusal amaç fonksiyonlarının aynı maksimum ve minimuma sahip olduklarını söyleyebiliriz. Matematiksel olarak anlamsız olan bu sonuçtan kaçınmak için değişkenler üzerinde bazı kısıtlamalar yapılmalıdır. Zaten organizasyonların kaynaklarının da sonsuz olmadığı düşünülürse bu kısıtlamaların modelde yer alması normaldir. DP modellerinde kısıtlar, doğrusal eşitsizliklerden meydana gelir.
a11 , a12 , ........................., amn
ve
b1 , b2 , ..........................., bm
sabit sayılar olmak üzere kısıtlar :
a11 * x1 + a12 * x2 + …………………………+ a1n * xn <= b1
a21 * x1 + a22* x2 + …………………………+ a2n * xn < = b2
..............................................................
..............................................................
am1 * x1 + am2 * x2 + …………………………+ amn * xn <= bm
şeklinde gösterilir. Kısıtlar incelendiğinde şu özellikler göze çarpmaktadır:
Sistemin her satırı genellikle bir eşitsizliktir. Bazı durumlarda eşitlik de olabilir.
Eşitsizliklerin sol tarafları doğrusal fonksiyonlardır.
Kısıtların sayısı (m ) için bir sınırlama yoktur.
Kısıtları ifade eden eşitsizlikler , problemin çözümü olabilecek x değişkenlerinin içinde bulunduğu «çözüm bölgesini» belirler. Sonuçta tüm kısıtları sağlayan optimum(en uygun) çözüm bulunur.
Pozitiflik koşulu
DP ‘ nin gerçek problemlere uygulanmasını kolaylaştırmak amacı ile çözümde karar değişkenlerinin negatif değer alamayacağı koşulu getirilmiştir. Matematik olarak problem çözüldüğünde ;
x1 , x2 , ………., xn >= 0 olmalıdır.
DP modellerinin formülasyonu değişik şekillerde gösterilmektedir. En yaygın gösterim şekli aşağıda verildiği gibi matris notasyonu kullanılarak formüle etmektir.
Örnek Problem : XX şirketi, H1 ve H2 hammaddelerinin karışımından iç ve dış duvar boyası üretmektedir. Aşağıdaki tabloda problemin temel verileri gösterilmektedir.
Şirketin yaptığı pazar araştırmasında, günlük iç boya talebinin en fazla 2 ton olduğu görülmüştür. Yine aynı araştırmada, günlük iç boya talebinin günlük dış boya talebinden fazla olduğu ve bu fazlalığın günde en çok 1 ton olduğu anlaşılmıştır. Sirket karını maksimum yapacak şekilde optimum üretim miktarını belirlemek istemektedir. Bu problem bir DP modeli olarak düşünüldüğünde 3 temel elemanı olacaktır:
1. karar değişkenleri
2. amaç fonksiyonu
3. kısıtlar
Modelin karar değişkenleri iç ve dış boya miktarlarıdır.
x1 --> dış boyanın günlük üretim miktarını( ton)
x2 --> iç boyanın günlük üretim miktarını( ton ) göstersin.
Şirket için en iyi amaç toplam karı maksimum yapmaktır. Z toplam karı göstermek üzere;
maksimum Z = 5 * x1 + 4 * x2
Şeklinde yazılabilir. Modelin son elemanı hammadde ve taleple ilgili sınırlamalardır.
H1 hammaddesinin kullanımı:
6 * x1 + 4 * x2 ton
H2 hammaddesinin kullanımı da:
1* x1 + 2 *x2 tondur.
Bu hammaddelerin günlük kullanımları sınırlı olduğu için kısıtları şu şekilde yazabiliriz:
6 * x1 + 4 * x2 < = 24 H1 hammaddesi için
1* x1 + 2 *x2 <= 6 H2 hammaddesi için
Ayrıca taleple ilgili sınırlamalar da vardır :
İç duvar boyası talebinin günde en çok 2 ton olması ;
x2 < = 2
İç boyanın günlük üretiminin dış boyanın üretiminden en çok 1 ton fazla olması;
x2 - x1 < = 1
Modelde yer alan değişkenlerin negatif olmama (pozitiflik koşulu) sınırlamasını da ekleyerek matematik modeli aşağıdaki gibi yazabiliriz :
amaç fonksiyonu :
maksimum Z = 5 * x1 + 4 * x2
kısıtlar :
6 * x1 + 4 * x2 < = 24
x1 + 2 *x2 <= 6
- x1 + x2 < = 1
x2 < = 2
pozitiflik koşulu :
x1 , x2 > = 0
Bu kısıtların tümünü sağlayan herhangi bir çözüm uygun çözüm adını alır.
Grafik çözüm
İki değişkenli bir DP modeli grafik olarak çözülebilir. Grafik yöntemin iki önemli adımı vardır:
Modelin tüm kısıtlarının sağlandığı uygun çözümleri içeren bir çözüm uzayının belirlenmesi,
Çözüm uzayındaki tüm noktalar arasından optimum çözümün bulunması.
Yukarıda verilen örneğin grafik çözümünü yapalım. Kısıtları bir koordinat sisteminde göstermenin en kolay yolu, eşitsizlikleri eşitlik şeklinde düşünerek bunlara ait doğruların çizilmesidir. Daha sonra eşitsizliğin işaretine göre doğrunun altında ya da üstünde kalan bölge çözüm bölgesi olarak seçilir. Birinci kısıtı ele alırsak;
6 * x1 + 4 * x2 < = 24 eşitsizliğini
6 * x1 + 4 * x2 = 24 şeklinde eşitlik olarak yazalım.
Bu doğruyu çizebilmek için iki nokta gerekir. x1 = 0 için x2 ‘yi, x2= 0 için de x1 ‘ i hesaplayabiliriz. x1 = 0 için x2= 6 , x2 = 0 için x1 = 4 bulunur. (0,6) ve (4,0) noktalarından geçen doğru aranılan doğrudur. Eşitsizliğin yönü (<= ) şeklinde olduğu için bu doğrunun altında kalan alan bu kısıtı sağlayan alandır. Tüm kısıtlara ait doğrular çizildikten sonra, çözüm uzayı belirlenir. Aslıda uygun çözüm bölgesi sonsuz sayıda uygun nokta içerdiği için , bunların arasından optimum noktayı bulmamız gerekir.
Optimum çözümün belirlenmesi için kar fonksiyonunun artış yönünün bilinmesi gerekir. Bu da Z’e keyfi değerler atayarak yapılabilir. Z’ e önce 10 sonra 15 değerleri verilerek;
5 * x1 + 4 * x2 = 10 ve
5 * x1 + 4 * x2 = 15 doğruları çizilir.
Amaç fonksiyonunun daha artırılması durumunda ABCDEF uygun çözüm uzayının dışına çıkılacaktır. Şekilden çözüm uzayının dışına C noktasından çıkıldığı görülmektedir. Dolayısıyla uygun çözümü içeren nokta C noktasıdır. C noktası 1 ve 2 numaralı kısıtların kesişim noktası olduğu için buradan x1 = 3 ve x2= 1.5 bulunur. Günlük üretimde 3 ton dış boya, 1.5 ton iç boya üretildiğinde günlük kar Z= 21000$ olacaktır. Optimum çözümün çözüm uzayının komşu köşe noktalarından birinde bulunması raslantı değildir. Amaç fonksiyonunun eğimi değiştirilse bile, yeni çözüm yine köşe noktalarından birinde olacaktır.
5 * x1 + 4 * x2 = 10 ve
5 * x1 + 4 * x2 = 15 doğruları çizilir.
Amaç fonksiyonunun daha artırılması durumunda ABCDEF uygun çözüm uzayının dışına çıkılacaktır. Şekilden çözüm uzayının dışına C noktasından çıkıldığı görülmektedir. Dolayısıyla uygun çözümü içeren nokta C noktasıdır. C noktası 1 ve 2 numaralı kısıtların kesişim noktası olduğu için buradan x1 = 3 ve x2= 1.5 bulunur. Günlük üretimde 3 ton dış boya, 1.5 ton iç boya üretildiğinde günlük kar Z= 21000$ olacaktır. Optimum çözümün çözüm uzayının komşu köşe noktalarından birinde bulunması raslantı değildir. Amaç fonksiyonunun eğimi değiştirilse bile, yeni çözüm yine köşe noktalarından birinde olacaktır.
Örnek problem: Bir çiftlikte günde en az 800 kg özel bir karışımla yapılan yem kullanılmaktadır. Bu karışım, aşağıdaki tabloda verilen maddelerin belirtilen miktarları kullanılarak elde edilmektedir.
Bu ürünün bileşiminde en az %30 protein ve en çok da % 5 lif bulunması zorunludur. Firma minimum maliyetle günlük yem karışımını belirlemek istemektedir. Önce probleme ait matematik modeli kuralım:
Karar değişkenleri:
x1 ---> karışımdaki mısır miktarı (kg)
x2 ---> karışımdaki soya unu miktarı(kg)
Amaç fonksiyonu:
Minimize Z = 0.3* x1 + 0.9 * x2
Kısıtlar:
x1 + x2 > = 800 ( günlük üretim)
0.09* x1 + 0.60* x2 > = 0.3 ( x1 + x2 ) (protein miktarı)
0.02 * x1 + 0.06 * x2 < = 0.05(x1 + x2 ) ( lif miktarı)
Kısıtları ve amaç fonksiyonunu yeniden yazalım:
Minimize Z = 0.3* x1 + 0.9 * x2
x1 + x2 > = 800
0.21* x1 - 0.30* x2 < = 0
0.03* x1 - 0.01 * x2 >= 0
x1 , x2 > = 0
optimum noktada değişkenlerin değerleri:
x1 = 470.59 kg
x2 = 329.42 kg
Amaç fonksiyonu: Z = 437.65 $
x1 = 470.59 kg
x2 = 329.42 kg
Amaç fonksiyonu: Z = 437.65 $
SİMPLEKS YÖNTEMİ
Bir doğrusal programlama modelini çözmek üzere geliştirilmiş , optimum çözümü iterasyon (ardışık yaklaşım) yoluyla bulan matematiksel bir yöntemdir. Probleme ait matematik model kurulduktan sonra, ilk adım modeli standart DP modeli şekline getirmektir. Standart bir DP modelinde eşitsizlikler eşitlik şekline dönüştürülmelidir.
Eşitsizliklerin eşitlik haline getirilmesi
Bir DP modelinde <= yönündeki bir kısıtı eşitlik haline getirmek için eşitsizliğin sol tarafına bir artık (slack) değişken eklenir.
x1 + 3* x2 <= 4
eşitsizliği,
x1 + 3* x2 + S1 = 4
eşitliği ile aynı anlamdadır. S1 >= 0 olup, artık değişken adını alır.
Eşitsizliğin yönü >= yönünde ise artık değişken eklemek yerine çıkarmak gerekir. Ancak bu durumda da değişkenin negatif olmasından ötürü başlangıç çözümünde yer alamaz. Bunun için bu tür kısıtlarda bir de yapay(artificial) değişken eklenir.
x1 + 2* x2 >= 6
eşitsizliği,
x1 + 2* x2 - S1 + A1 = 6
şeklinde eşitlik haline getirilir. Bazı modellerde de sadece = şeklinde kısıtlar da yer alabilir. Bu durumda da eşitsizliğin sol tarafına bir yapay değişken eklenir.
2*x1 + 3* x2 = 10
eşitsizliği,
2* x1 + 3* x2 + A1 = 10
eşitlik haline getirilir.
Bir eşitliğin sağ tarafı mutlaka negatif olmama koşuluna uygun olmalıdır. Gerekirse bu koşulu sağlamak için eşitsizliğin her iki tarafı –1 ile çarpılır ve eşitsizliğin yönü de değiştirilir.
Simpleks algoritması
Simpleks algoritması uygun bir temel çözümle başlar ve daha sonra amaç fonksiyonunun daha da iyileştirildiği başka uygun çözümlerle devam eder. İlk uygun çözüm için probleme eklenen artık ve yapay değişkenlerden yararlanılır. Problemin karar değişkenleri (x1 , x2 , ………., xn ) başlangıçta sıfır değerini alırken , artık (S ) ve yapay (A ) değişkenler sağ taraf değerlerine eşitlenir. Şimdi bir örnek problem ele alarak algoritmayı adım adım uygulayalım.
Örnek problem: Yüksek kaliteli cam ürünleri üreten bir firmanın üretimini gerçekleştirdiği 3 atölyesi mevcuttur.1. atölyede aliminyum çerçeve ve bağlantıları,2. atölyede ağaç çerçeve , 3. atölyede de cam üretilerek, kapı ve pencere ürünleri yapılmaktadır. Kazançlarındaki azalmadan dolayı üst kademe yönetimi üretim hattını yenilemek istemektedir. Kar getirmeyen bazı ürünler üretilmeyecek, buna karşılık talebi olan bir veya 2 yeni ürün, üretim kapasitesinin izin verdiği ölçüde üretilecektir.Yeni ürün olarak aliminyum çerçeveli kapı ve çift camlı ağaç çerçeveli pencere üretilmesi kararlaştırılıyor. Pazarlama departmanı elde mevcut kapasite ile üretilecek bu ürünlerin satılacağını garanti etmektedir. Atölyelerden elde edilen bilgiler aşağıdaki tabloda verilmektedir:
Bir doğrusal programlama modelini çözmek üzere geliştirilmiş , optimum çözümü iterasyon (ardışık yaklaşım) yoluyla bulan matematiksel bir yöntemdir. Probleme ait matematik model kurulduktan sonra, ilk adım modeli standart DP modeli şekline getirmektir. Standart bir DP modelinde eşitsizlikler eşitlik şekline dönüştürülmelidir.
Eşitsizliklerin eşitlik haline getirilmesi
Bir DP modelinde <= yönündeki bir kısıtı eşitlik haline getirmek için eşitsizliğin sol tarafına bir artık (slack) değişken eklenir.
x1 + 3* x2 <= 4
eşitsizliği,
x1 + 3* x2 + S1 = 4
eşitliği ile aynı anlamdadır. S1 >= 0 olup, artık değişken adını alır.
Eşitsizliğin yönü >= yönünde ise artık değişken eklemek yerine çıkarmak gerekir. Ancak bu durumda da değişkenin negatif olmasından ötürü başlangıç çözümünde yer alamaz. Bunun için bu tür kısıtlarda bir de yapay(artificial) değişken eklenir.
x1 + 2* x2 >= 6
eşitsizliği,
x1 + 2* x2 - S1 + A1 = 6
şeklinde eşitlik haline getirilir. Bazı modellerde de sadece = şeklinde kısıtlar da yer alabilir. Bu durumda da eşitsizliğin sol tarafına bir yapay değişken eklenir.
2*x1 + 3* x2 = 10
eşitsizliği,
2* x1 + 3* x2 + A1 = 10
eşitlik haline getirilir.
Bir eşitliğin sağ tarafı mutlaka negatif olmama koşuluna uygun olmalıdır. Gerekirse bu koşulu sağlamak için eşitsizliğin her iki tarafı –1 ile çarpılır ve eşitsizliğin yönü de değiştirilir.
Simpleks algoritması
Simpleks algoritması uygun bir temel çözümle başlar ve daha sonra amaç fonksiyonunun daha da iyileştirildiği başka uygun çözümlerle devam eder. İlk uygun çözüm için probleme eklenen artık ve yapay değişkenlerden yararlanılır. Problemin karar değişkenleri (x1 , x2 , ………., xn ) başlangıçta sıfır değerini alırken , artık (S ) ve yapay (A ) değişkenler sağ taraf değerlerine eşitlenir. Şimdi bir örnek problem ele alarak algoritmayı adım adım uygulayalım.
Örnek problem: Yüksek kaliteli cam ürünleri üreten bir firmanın üretimini gerçekleştirdiği 3 atölyesi mevcuttur.1. atölyede aliminyum çerçeve ve bağlantıları,2. atölyede ağaç çerçeve , 3. atölyede de cam üretilerek, kapı ve pencere ürünleri yapılmaktadır. Kazançlarındaki azalmadan dolayı üst kademe yönetimi üretim hattını yenilemek istemektedir. Kar getirmeyen bazı ürünler üretilmeyecek, buna karşılık talebi olan bir veya 2 yeni ürün, üretim kapasitesinin izin verdiği ölçüde üretilecektir.Yeni ürün olarak aliminyum çerçeveli kapı ve çift camlı ağaç çerçeveli pencere üretilmesi kararlaştırılıyor. Pazarlama departmanı elde mevcut kapasite ile üretilecek bu ürünlerin satılacağını garanti etmektedir. Atölyelerden elde edilen bilgiler aşağıdaki tabloda verilmektedir:
"http://enm.blogcu.com" dan alıntıdır emekleri için kendisine çok çok teşekkürler :)
Hiç yorum yok:
Yorum Gönder