YBS401U-YÖNEYLEM ARAŞTIRMASI
Ünite 7: Tamsayılı Programlama Modelleri
Tamsayılı Programlama Türleri
DP’nin varsayımlarını hatırlayacak olursak; bölünebilirlik varsayımına göre karar değişkenleri ondalıklı değerler alabilmektedir. Ancak, üretim ve reklam gibi alanlarda karar değişkenlerinin alacağı günlük 8.3 adet üretim miktarı veya bir adet reklam ile erişilecek 920.5 adet müşteri gibi değerler uygulamada mümkün değildir. Bu değerler tamsayı olmalıdır. Gerçek hayat problemlerinin bir kısmında da hangi üründen ne kadar üretileceği kararının yanı sıra, hangi ürünün üretileceği kararı da verilmektedir. Evet/hayır, üret/üretme gibi bu tarz kararların alındığı problemlerin karar değişkenleri de 0-1 tamsayı değerlerini almaktadır.
Karar değişkenlerinin tamsayı değer alması gereken karar problemleri Tamsayılı Programlama Problemi (TP) yerine bir DP problemi olarak ele alınırsa ele edilen ondalıklı değerleri tamsayı değere yuvarlayarak çözümü gerçekçi bir çözüm hâline getirebiliriz. Ancak saatte 8.3 adet bilgisayar üretme kararı 9 adet bilgisayar üretme kararına yuvarlandığında, bu tamsayı çözüm uygun çözüm alanı dışına çıkabilir, yani yuvarlanan çözüm probleme ait kısıtları sağlamayabilir.
TP’nin farklı türleri bulunmaktadır. Ancak, bir problemin TP olup olmadığını belirleyen ortak unsur, karar değişkenlerinin tamsayı değer alıp almamasıdır.
Bir tamsayılı programlama modeli parametreler yani amaç fonksiyonu katsayıları (cj), kısıtlarda yer alan teknik katsayılar (aij) ve sağ taraf sabitleri (bi) tamsayı olmak zorunda değildir. Aşağıda, bu duruma örnek olarak bir TP problemine ait matematiksel model verilmiştir.
(TP1): 3.8 x1 + 2x2 ≤ 10 6 x1 - x2 ≤ 19.3 x1, x2 ≥ 0 ve tamsayı k.a. Enb Z = 8.4 x1 + 4 x2
Örnekte de görüldüğü gibi, birinci kısıtta yer alan 3.8 teknik katsayısı, ikinci kısıtın sağ taraf sabiti olan 19.3 ve amaç fonksiyonunda birinci karar değişkeninin katsayısı olan 8.4 tamsayı değer değildir. Bu problemi tamsayılı programlama problemi yapan unsur, karar değişkenlerinin “tamsayı” olarak tanımlanmasıdır.
Saf Tamsayılı Programlama Problemleri
Karar değişkenlerinin tümünün alması gereken değerlerin tamsayı olduğu karar problemleridir. xj j. karar değişkeni olmak üzere, karar değişkenlerinin gösterimi izleyen şekildedir:
xj ≥ 0 ve tamsayı ,∀j (j = 1, 𝑛)
Üç farklı ürün üreten bir firmanın, önümüzdeki ay maliyetlerini en küçükleyecek üretim miktarlarını belirlemeyi amaçlayan bir TP’nin matematiksel modelinde, xj j. ürün üretim miktarı olmak üzere, karar değişkenleri x1, x2, x3 ≥ 0 ve tamsayı olarak tanımlanmalıdır.
(TP2) ile verilen matematiksel model, bir saf tamsayılı programlama problemine örnek olarak verilebilir.
(TP2): 3 x1 + 2 x2 ≤ 10 6 x1 – x2 ≤ 19 x1, x2 ≥ 0 ve tamsayı k.a. Enb Z = 4 x1 + 5 x2
Bir saf tamsayılı programlama probleminde karar değişkenlerinin alacağı değerlere bakacak olursak; örneğin, x1=2, x2 = 2 tamsayı değer olduğu için uygun bir çözüm iken x1=1, x2 = 2,78 kısıtları sağlasa bile ikinci karar değişkeni tamsayı bir değer almadığı için uygun çözüm olamaz. Bu problem türünde, karar değişkenlerinin alacağı değerlerin tamsayı olduğu bilinmelidir. Örneğin, gazlı içecekler üreten bir firmanın üretim miktarı 1.2 litre olabilir. Ancak üretim miktarı şişe adedi olarak belirlendiyse, 1.2 adet şişe üretilemeyeceği için geliştirilecek model mutlaka saf tamsayılı programlama problemi modeli olmalıdır.
0-1 Tamsayılı Programlama Problemleri
0-1 tamsayılı programlama problemleri, karar değişkenlerinin tümünün ya “0” ya da “1” değerlerini aldığı karar problemleridir. 0 veya 1 değerini alan değişkenler aynı zamanda ikili değişken olarak da adlandırılır. İkili değişkenler genellikle Evet/Hayır kararlarını formüle etmek ve mantıksal koşulları uygulamak için kullanılır. Üret/Üretme, Al/Alma, Kur/Kurma gibi kararlar Evet/Hayır kararlarına örnek olarak verilebilir. xj j. karar değişkeni olmak üzere, karar değişkenlerinin 0-1 tamsayılı programlama problemlerinde gösterimi izleyen şekildedir:
xj ∈ {0,1}, ∀j ( j = 1, 𝑛)
Bazı kaynaklarda xj = 0 veya 1 şeklindeki gösterim de kullanılmaktadır. Bir 0-1 tamsayılı programlama problemi için örneğin x1 = 1 uygun bir çözüm iken, x3 = 0,78 0 ya da 1 değeri almadığı için uygun çözüm olamaz.
Karma Tamsayılı Programlama Problemleri
Karar değişkenlerinin bir kısmının tamsayı, diğer kısmının da reel değer aldığı karar problemleridir. Örneğin, gazlı içecek üreten bir firma ilgili planlama döneminde en düşük maliyetle hangi içecek türünden, ne kadar miktarda üreteceğini araştırabilir. İlgili problemde hangi içecek türünün üretilip üretilmeyeceğini belirleyen karar değişkeni yj 0-1 ve üretim miktarını belirleten xj’de negatif olmayan karar değişkenidir. Bu örnekte, daha önce de değinildiği gibi, üretilen ürün sıvı bir ürün olduğu için, üretim miktarı sürekli bir değişken (3.5 ton vb.) olabilir. Karar değişkenlerinin TP modelinde gösterimi, problemde karar değişkenlerinin alabileceği değerlere bağlı olarak izleyen şekillerde olabilir.
y1, y2 ∈ {0,1} veya y1, y2 ≥ 0 ve tamsayı xj ≥ 0 xj ≥ 0
Bir karma tamsayılı programlama problemi için örneğin, x1=6,7 ve y1=1 hem reel hem de tamsayı değer alma kısıtı sağlandığı için uygun bir çözümdür.
Temel Tamsayılı Programlama Problemleri
Ürün Karması Belirleme Problemi
Hangi üründen ne kadar miktarda üretileceğinin belirlendiği ürün karması problemi bir saf tamsayılı programlama problemidir.
Örneğin bir mobilya firması hem çalışma masası hem de kitaplık üretmektedir. Bir çalışma masasının üretimi için 3 saat işçilik ve 6 m2 sunta plaka; bir kitaplık üretimi için de 4 saat işçilik ve 8 m2 sunta plaka gerekmektedir. Firmanın
mevcut durumdaki üretim kapasitesi haftada 60 saat işçilik ve 80 m2 sunta ile sınırlıdır. Firma, bir çalışma masası
satışından 400 lira kâr elde ederken, kitaplık satışından da 275 lira kâr elde etmektedir. Bu durumda, kârını en büyüklemek isteyen firmanın ürün karmasını belirleyecek matematiksel model ürün karması belirleme problemi olarak ele alınabilir.
Sermaye Bütçeleme Problemi
Firmalar belirlenen bir planlama dönemi boyunca bütçeleri sınırlı olduğu için, n tane aday projenin hepsini yatırım yapmak üzere seçememektedir. Dolayısıyla firma bütçesi aşılmayacak şekilde n tane projeden, toplam geliri en büyükleyecek olanların seçimi sermaye bütçeleme problemi olarak tanımlanır.
Tesis Yeri Seçimi Problemi
Birçok şirket düşük işçilik ve taşıma maliyetlerinden vb. yararlanmak için dünyanın ve/veya bulunduğu ülkenin çeşitli yerlerinde yeni tesisler açmaktadır. Yeni bir tesis için bir yer seçmeden önce, birçok potansiyel bölgenin analiz edilmesi ve karşılaştırılması gerekebilir. Potansiyel alanların her biri, “evet/hayır, aç/açma” kararını içerir. Birçok uygulamada da amaç, toplam maliyetleri en küçükleyecek yeni tesisleri açmaktır.
Tesis yeri seçimi problemi hem reel hem de 0-1 tamsayı değişkenlerin olduğu bir karma tamsayılı programlama problemi olarak ele alınabilir. Belirli bir bölgedeki n tane müşterisine ürün gönderen bir firma, ürün “taşıma maliyetlerini” azaltmak amacıyla dağıtım yapmak üzere ilgili bölgede olası m adet farklı lokasyonda depo açmak isteyebilir. Ancak, açacağı her bir depo için de bir “depo açma maliyetine” katlanmak zorunda olduğu unutulmamalıdır. Bu sebeple, aday lokasyonların her birinde depo açmak akıllıca bir karar olmayacaktır. Firmalar nihayetinde, depo açma maliyeti ve açılan depodan müşterilere ürün gönderme maliyetleri toplamlarını en küçüklemek ister.
Sırt Çantası Problemi
Sırt çantası problemi tek bir kısıt ve 0-1 karar değişkenlerinden oluşan bir TP problemidir. Problem ismini, yürüyüşçülerin sınırlı sayıda malzemeden hangilerini sırt çantalarına alacağını belirlediği karar
probleminden almıştır. Seçilebilecek her bir malzemenin yolculuğa katacağı bir fayda olduğundan, amaç seçilen malzemelerin toplam faydasını arttırmak olacaktır. Probleme ait tek kısıt, malzemelerin kapladığı alan/hacim veya getirdikleri ağırlığın, çanta kapasitesini aşmaması gerekliliği kısıtıdır.
Küme Kapsama Problemi
Birçok alanda uygulaması bulunan bu problemin en bilinen örneği, bir şehir için itfaiye istasyonlarının konumlarının belirlenmesi problemidir
Çizelgeleme Problemleri
Çizelgeleme, eğitim, hukuk, üretim, hastane, turizm ve otelcilik, havayolu ve çağrı merkezleri gibi birçok üretim ve hizmet sektöründe karşılaşılan bir karar verme sürecidir. Çizelgeleme problemleri, sınırlı sayıdaki faaliyetin sınırlı sayıdaki kaynak ve zaman dilimine atanması problemidir. Aslında, çizelgeleme problemleri birer atama problemidir. Zaman dilimine de atama yapıldığı için, çizelgeleme adını almaktadır. Hangi dersin hangi sınıf ve zamanda yapılacağının, hangi işin hangi makine ve zamanda başlayacağının, hangi davanın hangi mahkemede hangi gün ve saatte görüleceğinin, hangi tren seferinin hangi tren ile ne zamanda başlayacağının belirlenmesi problemleri çizelgeleme problemlerine örnek olarak verilebilir.
Tamsayılı Programlama Problemlerinde Özel Kısıtlar
Ya-Ya da Kısıtları
Ya-ya da kısıtları, matematiksel modelde verilen iki kısıttan sadece birinin sağlanmasını garantileyen kısıtlardır. Böylece, bir karar problemine ait matematiksel modelin kısıtları içinden verilmiş olan iki kısıt aynı anda sağlanmaz. Verilen iki kısıttan ya birinin ya da diğerinin modelde sağlanmasını garantilemek için modele yeni bir 0-1 tamsayılı karar değişkeni (y ∈ {0,1}) eklenir. Bu karar değişkeni, yardımcı karar değişkeni olarak da adlandırılır. 0-1 karar değişkenin tanımlanmasının ardından, çok büyük bir sayı M»0 ile çarpılarak verilen iki kısıttan birinin sağ taraf sabitine eklenir (+My). Diğer kısıtın sağ taraf sabitine de (+M(1–y)) olarak eklenir.
Farklı Değerler Alabilen Fonksiyonlar
Bazı durumlarda, ilgilenilen sisteme ait fonksiyonlardan (iş gücü, ham madde vb.) birden fazla değerden sadece birini almasını matematiksel modelde garantilemek gerekir.
Karar Probleminde Koşullar
Hangi projenin seçileceğini, hangi ürünlerin üretileceğini, hangi illerde depo açılacağını veya yeni tesis kurulacağını belirlediğimiz karar problemlerinde bütçe, hammadde ve işçilik gibi kısıtların yanında özel özel kısıtlar da olabilir. Örneğin, ürün karmasının belirlendiği bir problemde üretimine ve miktarına karar verilecek 10 ürün içinden en az 5 tanesi üretilsin, en fazla 4 tane üretilsin, ürün 2 üretiliyorsa ürün 5 üretilmesin gibi özel kısıtlar belirlenebilir.
Tamsayılı Programlama Problemleri Çözüm Yaklaşımları
DP çözüm yöntemi olan Simpleks Algoritması, eğer problemin bir en iyi çözümü varsa bunun uygun çözüm alanının bir köşe noktası olduğunu ispatlamaktadır. Ancak, TP problemlerinin uygun çözüm alanlarının köşe noktaları her zaman tamsayı değerler almaz. Bu sebeple, TP için Simpleks Algoritması tek başına bir çözüm yaklaşımı değildir.
Tamsayılı programlama problemlerinin çözümü için Doğrusal Gevşetme, Sayımlama, Dal-Sınır, Kesme Düzlemi gibi farklı yöntemler geliştirilmiştir.
Doğrusal gevşetme yönteminde, ele alınan TP probleminin amaç ve kısıtları aynı kalacak şekilde, bölünebilirlik varsayımı dahil edilir. Bir başka deyişle, amaç ve kısıtlar aynı kalır, işaret kısıtlarında tamsayı olma koşulu kaldırılır. Böylece, ilgili TP bir DP problemine dönüştürülür
Sayımlama yönteminde ise, uygun çözüm alanındaki tüm tamsayı çözümler tek tek ele alınır ve amaç fonksiyonları hesaplanır. En iyi amaç fonksiyonu değerini veren çözüm de en iyi tamsayı çözümü olarak belirlenir.
Dal-Sınır Algoritmasıdır. Çözümü aranan TP doğrusal gevşetme yöntemi ile çözülür. Elde edilen çözüm tamsayı değil ise, tamsayı olmayan karar değişkenlerinden biri seçilerek, en yakın alt ve üst tamsayılara yaklaştırılarak ana probleme yeni kısıt olarak eklenir. Böylece iki alt problem oluşturulur (dallandırma) yani doğrusal gevşetilerek çözülen ana problemin uygun çözüm alanı iki alt alana bölünerek, bu alanlarda tamsayı çözüm aranır. Bu adım, en iyi amaç fonksiyonunu veren tamsayı çözüm bulunana kadar devam eder.