Metinde verilen örnek bir maksimizasyon modelinde, tamsayı kısıtları gevşetildiğinde elde edilen doğrusal programlama modelinin optimal amaç fonksiyonu değeri 888,9 olarak bulunmuştur. Aynı model saf tamsayılı olarak çözüldüğünde ise optimal amaç fonksiyonu değeri 888'e düşmüştür. Bu durum, gevşetilmiş modelin optimal değerinin tamsayılı model için her zaman bir üst sınır oluşturduğunu somut olarak kanıtlamaktadır.
Dal-sınır algoritmasının ilk adımı, tamsayılılık kısıtlarını tamamen göz ardı ederek problemi standart doğrusal programlama yöntemleriyle çözmektir. Eğer bu ilk çözümde tüm değişkenler tamsayı çıkarsa algoritma doğrudan sonlandırılır. Metindeki örnekte, gevşetilmiş modelin ilk çözümü x1 = 15/4 ve x2 = 9/4 olarak kesirli bulunmuş, bu nedenle dallandırma işlemine geçilmiştir.
Sayımlama yöntemi, özellikle 0-1 tamsayılı programlama problemlerinde kesin çözümü garanti etmesine rağmen yüksek işlem yükü nedeniyle tercih edilmez. Değişken sayısı doğrusal arttıkça, incelenmesi gereken olası çözüm noktası sayısı üssel olarak artmaktadır. Bu durum, yöntemin çok değişkenli gerçek işletme problemlerinde bilgisayar yazılımlarıyla bile uygulanmasını zorlaştırır.
Yuvarlama yöntemi, gevşetilmiş doğrusal programlama çözümündeki kesirli değerleri en yakın tamsayıya yuvarlar. Ancak bu işlem sonucunda elde edilen yeni tamsayı koordinatları, problemin kısıt sınırlarını aşarak uygun çözüm bölgesinin dışına çıkabilir. Bu durum, yuvarlama yönteminin her zaman güvenilir ve uygulanabilir sonuçlar vermediğini gösterir.
Gezgin satıcı probleminde (TSP) her noktaya sadece bir noktadan gelinebilmesi ve gelinen her noktadan sadece tek bir başka noktaya geçilebilmesi kısıtı bulunur. Ayrıca, gezginin tüm noktaları dolaşmadan kendi içinde kapalı döngüler oluşturmasını (alt turları) önleyici özel matematiksel kısıtlar modele eklenmek zorundadır.
En kısa yol problemi sadece coğrafi mesafeleri en küçüklemek için kullanılmaz. Bir işletmenin üretim makinelerini en düşük toplam maliyetle yenileyebilmesi için zaman içerisindeki bakım, onarım ve yenileme planlarını oluşturması problemi de matematiksel olarak bir en kısa yol problemine dönüştürülerek çözülebilmektedir.
Sırt çantası problemlerinin sadece tek bir kapasite kısıtı barındırmayan, birden fazla kısıtlayıcı kaynağın (örneğin hem bütçe, hem hacim, hem de işçilik süresi kısıtlarının) aynı anda yer aldığı daha karmaşık türlerine 'çok boyutlu sırt çantası problemleri' adı verilmektedir.
Bir havayolu işletmesinde hafta sonu uçuşlarına kabin amiri atanması problemi küme örtme modeline dayanır. Tüm uçuşlara en az bir kabin amiri atanması zorunluyken, şirketin amacı hafta sonu çalışan toplam kabin amiri sayısını minimumda tutarak tüm uçuşların kapsanmasını sağlamaktır.
Metindeki örnek dal-sınır uygulamasında, DP-4 alt modelinin kısıtları altında hiçbir uygun çözüm bulunamamıştır. Çözümü olmayan bu dal algoritma gereği doğrudan budanmış ve bu koldan ilerleme durdurularak diğer dallardaki çözümlere odaklanılmıştır.
Dallandırma işlemine başlarken hangi kesirli değişkenin seçileceğine karar vermek için çeşitli kurallar uygulanır. Bunlar arasında; gevşetilmiş çözümde en büyük kesirli kısma sahip olan değişkeni seçmek, amaç fonksiyonundaki katsayısı en büyük olan değişkene öncelik vermek veya en küçük indise sahip değişkenden başlamak yer alır.
Doğrusal karar problemlerinde uygun çözüm alanının dışbükey (convex) bir küme olması ve en iyi çözümün uç noktalarda yer alması çözümü kolaylaştırır. Ancak doğrusal olmayan (non-lineer) ve tamsayılı modellerde genel bir çözüm yöntemi bulunmayıp, probleme özel farklı algoritmaların kullanılması gerekir.
Şirket, yeni fabrikasını Adana (AOSB) veya Kayseri (KOSB) Organize Sanayi Bölgesinde kurmayı planlamaktadır. Toplam 21 milyon TL sermaye bütçesiyle, en fazla bir depo inşa etme ve depoyu sadece fabrikanın kurulduğu bölgeye yapma kısıtları altında, net bugünkü değeri 22 milyon TL olarak maksimize eden optimal çözüme ulaşılmıştır.
Boyahane, ev tekstili, cep astarı dokuma ve cep astarı dikim atölyesi olmak üzere dört yatırım alternatifi bulunmaktadır. Şirket, elindeki 6.900 TL nakit bütçesini aşmayacak şekilde, toplam net bugünkü değerini 44.200.000 TL'ye ulaştıran optimal yatırım kombinasyonunu 0-1 sırt çantası modeliyle belirlemiştir.
Bir kargo uçağı, her uçuş için 20.000 kg'lık maksimum taşıma kapasitesine sahiptir. Model, uçuş başına toplam karı maksimize etmek amacıyla, ağırlıkları 1.000 kg ile 4.000 kg arasında değişen dört farklı kargo kaleminin uçağa yüklenip yüklenmeyeceğini 0-1 tamsayılı programlama formülasyonu ile belirler.
Metindeki örnek problemde, tamsayı kısıtları gevşetildiğinde elde edilen doğrusal programlama çözümü Max Z = 888,9 olarak bulunmuştur. Aynı problemin saf tamsayılı çözümü ise Max Z = 888 değerini alarak, gevşetilmiş modelin tamsayılı model için bir üst sınır oluşturduğunu somut bir şekilde kanıtlamıştır.
Bir havayolu işletmesinde, hafta sonu uçuşlarının tamamına en az bir kabin amiri atanması zorunluluğu vardır. Bu problem, tüm uçuşların en az sayıda kabin amiri görevlendirilerek kapsanmasını hedefleyen klasik bir Küme Örtme Problemi uygulamasıdır.
Bir işletmenin makinelerini en düşük toplam maliyetle yenileyebilmesi için zaman içerisindeki bakım planını oluşturması problemi, fiziki bir yol bulma problemi olmamasına rağmen En Kısa Yol Problemi algoritması kullanılarak çözülebilmektedir.
Süha Şirketi örneğinde, firmanın en fazla bir depo inşa etmek istemesi durumu modelde 'x3 + x4 <= 1' kısıtı ile temsil edilmiştir. Bu kısıt, iki seçenekten sadece birinin seçilebileceğini veya hiçbirinin seçilemeyeceğini garanti eder.
Deponun sadece fabrikanın kurulduğu bölgeye yapılabilmesi koşulu, modelde 'x3 - x1 <= 0' ve 'x4 - x2 <= 0' kısıtları ile formüle edilmiştir. Bu sayede fabrika kurulmazsa (x1=0), deponun kurulması da (x3=1) engellenmiş olur.
Sandalye, masa ve tabure üretimi yapan bir atölyede, 360 m3 ahşap malzeme ve 130 saat işçilik kapasitesi bulunmaktadır. Aylık toplam satış karını en çoklamak amacıyla kurulan model, tüm değişkenlerin tamsayı olmasını gerektiren bütünüyle tamsayılı bir programlama modelidir.
Metindeki iki değişkenli örnek problemde, gevşetilmiş doğrusal programlama modelinin ilk çözümü köşe noktalarından C noktasında x1 = 15/4 ve x2 = 9/4 olarak bulunmuş ve amaç fonksiyonu üst sınırı Z = 165/4 (41.25) olarak hesaplanmıştır.
Dallandırma aşamasında x1 <= 3 kısıtı eklenerek çözülen DP-3 alt modelinde, her iki karar değişkeni de tamsayı değer alarak (x1 = 3, x2 = 3) çözülmüş ve Z = 39 değeriyle problemin ilk geçerli alt sınırını oluşturmuştur.
Dallandırma sürecinde x1 >= 4 ve x2 >= 2 kısıtları eklenerek oluşturulan DP-4 alt modelinin uygun çözüm bölgesinin boş olduğu (çözümünün olmadığı) grafik yöntemle tespit edilmiş ve bu dal daha fazla ilerletilmeden sonlandırılmıştır.
DP-7 alt modelinin çözülmesiyle elde edilen x1 = 5 ve x2 = 0 tamsayılı çözümü, Z = 40 değerini üreterek önceki alt sınır olan 39'u aşmış ve tüm dallar tamamlandığı için problemin kesin optimal çözümü olarak belirlenmiştir.
İki değişkenli örnek problemde tamsayı noktaları içeren çözüm kümesinde (S) toplam 25 farklı nokta bulunmaktadır. Değişken sayısı arttıkça bu kombinasyon sayısı üssel olarak arttığı için sayımlama yöntemi büyük modellerde kullanılamaz.
Bir işletmenin elindeki sınırlı sermayeyi aşmayacak şekilde, her birinin maliyeti ve getirisi bilinen yatırım projeleri arasından seçim yapması, çok boyutlu veya tek boyutlu sırt çantası probleminin en yaygın finansal uygulama alanıdır.