TAMSAYILI PROGRAMLAMA

Tüm değişkenlerin tamsayı olması gereken durumlar bütünüyle tamsayılı programlamaya örnektir. 

Bazı değişkenlerin tamsayı bazılarının sürekli olabildiği durumlarda karma tamsayılı programlama
sözkonusudur.

Bir deponun açılıp açılmaması, bir tezgahın kullanımına bir işçinin atanıp atanmaması gibi bir kararın verilip verilmemesi durumlarının sözkonusu olduğu problemlerde de 0-1 tamsayılı değişken kullanılmaktadır.

Bulunduğu noktadan başlayarak, belirli sayıda noktaya birer defa uğrayan, sonunda başladığı noktaya dönen ve bu güzergah boyunca katettiği toplam mesafeyi enküçüklemek isteyen bir gezginin uğrayacağı noktaların sırasının belirlenmesi problemi gezgin satıcı problemi olarak tanımlanır. Problemin basit anlamda kısıtları; her noktaya sadece bir noktadan gelinebileceği, gelinen her noktadan ise sadece tek bir başka noktaya geçilebileceği şeklindedir.

Küme örtme, verilen herhangi bir kümenin her üyesinin, diğer bir kümenin kabul edilebilir bir üyesince örtülmesi (kapsanması) problemidir. Amaç, kapsanan kümenin, kapsayan kümenin olabildiğince az elemanıyla örtülmesidir

Küme örtme probleminin kullanımına başka bir örnek olarak, örneğin, bir havayolu işletmesinde, hafta sonuna çizelgelenen uçuşlara, pilotların atanması problemini düşünelim. Tüm uçuşlara mutlaka en az bir pilotun atanması gerekmektedir. Öte yandan, mümkünse tüm pilotlara hafta sonu uçuşu atamadan uçuşların kapsanması tercih edilmektedir. Bu durumda problem, tüm uçuşların en az sayıda pilot görevlendirerek çizelgelenmesi şeklinde bir küme örtme problemidir.

Problemin basit anlamda kısıtları; her noktaya sadece bir noktadan gelinebileceği, gelinen her noktadan ise sadece tek bir başka noktaya geçilebileceği şeklindedir. Ayrıca bir yere, gidilen yerden tekrar gelinmesini önleyici kısıta da ihtiyaç vardır.

Lojistik faaliyetlerinde, ürünlerin dağıtımında, uğranması gereken boşaltım noktalarının sırasına karar verirken karşılaşılan problem, bir çeşit gezgin satıcı problemi gibi düşünülebilir.

Örneğin bir işletmenin makinalarını, en küçük toplam maliyetle yenileyebilmesi için, zaman içerisindeki yenileme ve bakım planını oluşturma problemi bir en kısa yol problemine benzetilebilir.

Birim kapasite kullanım miktarları ve seçilmeleri halinde ortaya çıkacak birim katkıları bilinen belirli
sayıda nesneden hangilerinin, eldeki kapasiteyi aşmadan ve toplam katkıyı enbüyükleyecek şekilde,
seçilmeleri gerektiğine dönük problemler, sırt çantası problemleri olarak bilinirler.

Bir işletmenin, ilgilendiği belirli sayıda yatırım aracı olsun. Her bir yatırımın birim getirisi ayrıca yatırım maliyeti bilinmektedir. Yatırıma ayrılabilecek belirli bir sermaye söz konusu iken, toplam yatırım harcamasının sermayeyi aşmamasına dikkat ederek, gerçekleştirilecek yatırımlara ve miktarlarına karar vermek bir sırt çantası problemi olarak tanımlanabilir. Problemin, birden fazla kapasite kısıtının yer aldığı, çok boyutlu sırt çantası türleri de bulunmaktadır.

Simpleks Algoritması, doğrusal karar problemlerinin çözümü için geliştirilmiş olup pek çok problemin
çözümünde kullanılabilmektedir. Doğrusal olmayan karar problemlerinin çözümü için ise, genel bir
çözüm yöntemi bulunmamakta, bunun yerine, farklı problemler için farklı çözüm yaklaşımları
kullanılmaktadır.

Tamsayılı programlama problemlerinin çözüm yöntemlerinden biri yuvarlama yöntemidir. Bu yöntemde problem, tamsayı koşulu yokmuş gibi çözülür. Elde edilen çözümün tamsayı olmaması durumunda, değişkenlerin aldığı değerler en yakın iki (alt ve üst) tamsayıya yuvarlanır.

Olası tüm çözüm seçeneklerinin türetilmesi, içlerinden, varsa, uygun çözüm olanlarının
belirlenmesi ve daha sonra amaç fonksiyonu değerini eniyileyen çözümün seçilmesidir.

Dal sınır algoritması, tamsayılı programlama problemlerinin çözümü için kullanılan, sayımlama
temelinde bir yöntemdir.

Yöntemin sakıncası, yuvarlama işlemi sonucunda, değişkenlerin aldığı değerlerin, problemin kısıtlarını sağlamayabileceği bir başka deyişle elde edilen çözümün uygun çözüm alanının içinde olmayabileceğidir.

Sayımlama yöntemi, yukarıda görüldüğü gibi, az sayıda değişken için bile iş yükü getirmekte,
yanı sıra, uygun çözüm olmadığı halde, bazı noktaların bulunmasını ve kısıtları sağlayıp sağlamadığının incelenmesini gerektirmektedir. Çok sayıda değişkenin olduğu durumlarda oldukça yoğun bir iş yükü getireceğinden, kesin çözümü vermekle birlikte, önerilen bir yöntem değildir.

Dal-sınır algoritmasında esas olan, problemi, her seferinde yeni bir kısıt ekleyerek ve tamsayı koşulu
gözardı edilerek, doğrusal bir karar modeli olarak çözmektir.

Bu durumda, eğer varsa, tamsayı koşulu gözardı edildiğinde bulunan çözümün amaç fonksiyonu
değeri, tamsayılı problem için alt sınır olarak kabul edilir. Uygun çözüm alanından, alt sınırdan daha
büyük bir amaç fonksiyonu değeri veren bir nokta için amaç fonksiyonu değeri ise üst sınır kabul edilir. Tamsayılı çözüm elde edildikçe, mevcut üst sınırdan daha küçük bir amaç fonksiyonu değeri de varsa, üst sınır güncellenir. Üst sınırın, sabit değere sahip olan alt sınıra olabildiğince yaklaşması istenir.

Tamsayı değer alması gereken karar değişkenlerinin tanımlanması için değil, bazı durumlarda, iki grup kısıttan birisinin sağlanması, belirli sayıda projenin, uygulamaya alınacak olan ve olmayanlarına karar verilmesi gibi çeşitli amaçlarla da tamsayılı değişkenler kullanılabilir.