İÇİNDEKİLER

İÇİNDEKİLER

1. TAMSAYILI PROGRAMLAMA PROBLEMİNİN ÇÖZÜMÜ *

2. TAMSAYILI PROGRAMLAMANIN BAZI UYGULAMALARI *

2.1. Sabit-Yüklü Problem *

2.2. Atölye Çizelgeleme Problemi *

2.3. İkiye Bölme *

3. TAMSAYILI PROGRAMLAMA METODLARI *

3.1. Kesme Algoritması (Cutting-Plane Algorithm) *

3.1.1. Kesirli ( Basit Tamsayılı ) Algoritma *

Kesme Metodlarında Kullanılan Hesaplamalar *

3.2. Dal ve Sınır Algoritması *

3.2.1. Dallara Ayırma *

3.2.2. Sınırlama *

Dal ve Sınır Algoritmasındaki Hesaplamalar *

3.3. Ya Bu- Ya O Tipi Kısıtlayıcılar (Zero-One İmplict Enumeration) *

1. TAMSAYILI PROGRAMLAMA PROBLEMİNİN ÇÖZÜMÜ

Çeşitli durumlar için çeşitli tamsayılı programlama model örnekleri söz konusudur. Bunlardan tamsayılı programlama olarak adlandırılanı bilinen lineer programlama problemine tamsayı olma şartının eklenmesiyle oluşmuştur. Bir tamsayılı programlama, bazı veya tüm değişkenlerin tamsayılı değer olması şeklinde sınırlanmasına göre karmaşık yada basit olarak adlandırılır. Eğer tamsayılı olma koşulu gözardı edildiğinde amaç fonksiyonu ve kısıtlar lineer ise, sonuç modeli tamsayılı lineer program olarak adlandırılır.

Her ne kadar birtakım sınırlı algoritma geliştirilmişse de hiçbir metod özellikle problemin boyutu arttığında hesaplama açısından tekbaşına etkili olamamıştır. Bu nedenle lineer programlamaların tersine, büyük çaplı problemlerin kabul edilebilir bir zaman içerisinde başarıyla çözülebilmesi tamsayılı algoritmalarda belirsiz bir performans sergiler.

Tamsayılı programlama hesaplamasındaki en önemli güçlüklerden bir tanesi de dijital hesap makinalarının tamsayılı programlama çözümlerindeki kaçınılmaz kullanımında rakamları yuvarlamanın yaratacağı etkidir.

Hesaplamalarda karşılaşılan güçlükler alternatif yolların bulunmasına yöneltmiştir. Genel bir yaklaşım, problemin devam eden kısmının çözülmesi ve sonra da sürekli optimumun en yakın olurlu (fizible) tamsayıya yuvarlanmasıdır. Yuvarlama burada yaklaşma anlamındadır. Örneğin; optimum değer makine sayısını gösteriyorsa ve bu 10.1 ise, bu yaklaşık olarak 10’a yuvarlanabilir. Yuvarlanan çözümün, kısıtları sağlama garantisi yoktur. Eğer orijinal problem lineer ve eşitliklerden oluşan kısıtlara sahipse, bu her zaman doğrudur. Lineer programlamanın teorisine göre yuvarlanmış çözüm olurlu olamaz çünkü, aynı kaynağın iki farklı çözümü olacağını gösterir.

Yuvarlamanın yarattığı olurlu olmayan durum, genellikle problemin tahmin edilen parametreleri kati olmadığından tolere edilebilir. Ancak, bazı tip eşitlik kısıtlarındaki parametreler katidir. Çok seçimli kısıtlar x₁ + x₂ +...+ x_n = 1 , x_j = (0,1) her j için buna bir örnektir. Bu tür durumlarda yuvarlama kullanılamaz ve kati (kesin) algoritma zorunlu hale gelir.

Yuvarlamanın genel olarak yetersizliğini vurgulamada şu dikkate alınmalıdır. Tamsayılı değişkenler birbirinden bağımsız miktardaki maddeler (makine, adam, yük) için kullanılsa da diğer tiptekiler bazı kodların miktarını göstermektedir. Bu nedenle, bir projeyi finanse edip etmeme kararında çift değişken kullanılır; x = 0 projenin reddedilmesi veya x = 1 kabul edilmesi. Bu durumda x’in kesirli değerleriyle uğraşmak saçma olacak ve yuvarlamak mantıken hatalı olacaktır.

Kodlanmış değişkenlerin kullanıldığı problemlerin önemini arttırmak için kullanılan uygulamalar bir sonraki bölümde ele alınacaktır. Bu aynı zamanda tamsayılı programlamanın genel olarak önemini vurgulamaya yarayacaktır.

2. TAMSAYILI PROGRAMLAMANIN BAZI UYGULAMALARI

Bu bölümde bazı tamsayılı programlama uygulamaları ele alınmıştır. Bu uygulamaların bazıları problemin doğrudan formülasyonuyla ilgilidir. Daha önemli bir katkı ise, tamsayılı programların matematiksel programlama modelindeki formata uygun olarak yanlış kurulmuş modellerin yeniden formülasyonunda kullanılmasıdır.

2.1. Sabit-Yüklü Problem

Tipik bir üretim planlama probleminde N tane mamulden, j mamulü için üretim maliyetleri; K_j üretilen miktardan bağımsız sabit maliyeti ve c_j birim başına değişken maliyeti mevcuttur. Bu durumda eğer x_j , j mamulünün üretim seviyesini gösteriyorsa, bunun üretim maliyeti fonksiyonu şöyle yazılabilir;

K_j+ c_jx_j x_j > 0

C_j(x_j) =

0 x_j = 0

Buradan amaç kriteri;

Min. z = ∑ c_j (x_j)

^{j = 1}

şeklini alır. Bu kriter orijinde devam etmediğinden x_j için lineer değildir. Bu da z’yi analitik açıdan izlenemez kılar. Problem, analitik açıdan yardımcı iki değişken eklenerek daha yönetilebilir hale gelebilir. Diyelim ki;

0 x_j = 0

1 x_j > 1

olsun. Bu durumda basit (lineer) kısıt şu şekilde gösterilir;

x_j ≤ M.y_j

M > 0 ve yeterince büyüktür. Böylece, x_j ≤ M üretim planlama problemindeki tüm aktif kısıtlar için gereksiz olmaktadır. Bu nedenle amaç kriteri şöyle yazılabilir;

Min. z = ∑ (c_jx_j + K_jy_j )

^{j =1}

Ş.k.g. 0 ≤ x_j ≤ M.y_j , her j için

y_j = 0 veya 1 , her j için

x_j ≤ M.y_j’nin uygun bir kısıt olduğunu göstermek için eğer, x_j > 0 ise, y_j = 1 ve sabit kuvvet K_j amaç fonksiyonuna eklenir. Eğer x_j = 0 ise, y_j 0 veya 1 olur. Ancak K_j > 0 ve z min. edildiğinde y_j 0 seviyesinde olmak zorundadır.

Orijinal sabit kuvvetli problemin tamsayılı programlamayla bir ilgisinin olması ilginçtir. “dönüşmüş” problem hala sıfır-bir karmaşık tamsayılı problem şeklindedir. Dönüşüm sadece analitik uygunluk için ortaya konur. Gerçekten de, eklenen çift değişkenler ikincildirler, dışarıdan eklenmiştirler. Dolayısıyla çözümle ilgili hiçbir yeni bilgi ortaya çıkarmazlar. Örneğin; optimum çözümdeki y_j= 1 zaten x_j > 0 şeklinde gösterilmektedir.

2.2. Atölye Çizelgeleme Problemi

Kuyruk probleminin tek makinayla en kısa zamanda tamamlanması gereken, n farklı işlemden oluştuğunu düşünelim. Her son mamul, siparişlerin gerçekleştirilmesi gerekli olan bir düzü operasyondan geçer. Ayrıca, son mamuller teslim tarihinde tamamlanmış olmalıdır.

Bu problemde üç tür kısıt vardır: sıralama, karışmama ve teslim tarihi. İkinci kısıt, iki operasyonun bir makinada aynı anda gerçekleştirilmesini engellemeyi sağlar. İlk kısıta bakarsak; x_j başlayacak olan j işleminin (sıfırdan başlamak üzere) zamanını göstersin, a_j ise j işleminin tamamlanması için gerekli üretim (işleme) zamanı olsun. Eğer i işlemi j’den bir önceki işlemse kuyruk kısıtının sonucu;

x_i + a_i ≤ x_j

Karışmama kısıtına bakarsak, i ve j işlemleri makinayı aynı anda meşgul etmemeli,

Ya x_i - x_j ≥ a_i yada x_j - x_i ≥ a_i ,

Optimum çözümde sırasıyla j’nin i’den önce veya i’nin j’den önce gelmesine bağlıdır.

Ya-yada kısıtının önceliği, model artık lineer programlama formatında olmadığından sorun oluşturur. Bu güçlük çift değişkenli y_ij tanımlanarak engellenir.

y_ij = 0 eğer j işlemi i’den önce geliyorsa

eğer i işlemi j’den önce geliyorsa

M yeterince büyük bir sayı iken “ ya-yada” kısıtı iki aşamalı kısıta denk gelir;

My_ij + (x_i + x_j ) ≥ a_j ve M ( 1 - y_ij ) + ( x_j- x_i ) ≥ a_i

Yeni dönüşümün önemi şudur, eğer optimum çözümde y_ij = 0 ise, ikinci kısıt gereksiz hale gelmektedir. Aynı zamanda birinci kısıt aktif kalmaktadır. Benzer şekilde eğer, y_ij = 1 ise, birinci değil ikinci kısıt aktif hale gelmektedir. y_ij çift değişkeni tanımlanırken bu kısıtları karmaşık tamsayılı programlamaya uygulanabilecek bir forma indirgemiştir.

Teslim tarihleri aşağıdaki kısıtlar eklenerek sağlanabilir. Diyelim ki j işlemi d_j zamanda tamamlanmak zorunda olsun. Buradan;

x_j+ a_i ≤ d_j

olur. Eğer t, toplam n adet işlemin bitirilmesi için gerekli zamanı gösterirse problem;

min. z = t

Ş.k.g. x_j+ a_i ≤ t j = 1,2,...,n

Sıralama, karışmama ve teslim tarihi kısıtlarının tümü bu şekilde geliştirilmiş olur.

2.3. İkiye Bölme

Belirli bir durumda m kısıttan herhangi k tanesinin aktif olduğunu düşünelim. Ancak, verilmesi gereken belirli kısıtlar başta bilinmemektedir. Bu durumu şöyle gösterebiliriz. Diyelim ki m kısıt formdan olsun;

g_i (x₁ + x₂ +...+ x_n) ≤ b_i i = 1,2,...,m

y_i = 0 eğer i. kısıt aktifse

1 eğer i. kısıt aktif değilse

şeklinde belirlersek, eğer M yeterince büyükse, m kısıttan herhangi k tanesinin aktif olduğu kesindir.

g_i (x₁ + x₂ +...+ x_n) ≤ b_i + My_i i = 1,2,...,m

ve y₁ + y₂ +...+ y_m = m-k

her i için y_i = 0 veya 1’dir. Bu, m-k adet kısıtın b_i + M biçiminde olduğunu gösterir. Bu da kısıtı gereksiz kılar. Burada dikkat edilmesi gereken şey yukarıdaki formülasyonun en iyi amaç değerini sağlayacak aktif seti belirleyeceğinin bilinmesidir.

3. TAMSAYILI PROGRAMLAMA METODLARI

Bu tip tamsayılı programlama modellerinin iki türlü çözümü vardır: kesme metodları ve araştırma metodları. Birincisi, öncelikle tamsayılı lineer problemler için geliştirilmiştir ve sürekli bir optimumla başlar. Sistematik olarak bütünlüğün sağlanması için gerekli olan şartları göstermeye yarayan “ikincil” özel kısıtların eklenmesiyle sürekli çözüm alanı kademe kademe düşürülerek sürekli optimumun tamsayı koşulunu sağlayacağı en üst noktaya ulaşıncaya kadar devam eder. “Kesme Metodu” ismi, “ikincil” kısıtların çözüm alanındaki olurlu tamsayı noktalarını içermeyen parçaların kesilmesi (veya elimine edilmesi) nedeniyle verilmiştir. Simplex metoduna dayanır. İkiden fazla değişken olduğunda kullanılır. Problem Simplex metoduyla çözülür, daha sonra tam sayılı sonuç elde edilinceye kadar yeni kısıtlar eklenir.

Araştırma metodlarının temeli, tüm olurlu tamsayı noktalarının doğrudan numaralandırılması düşüncesine dayanır. Temel düşünce, sadece (küçük) bir parça olurlu tamsayıları açıkça diğerlerini dolaylı olarak otomatik hesaplayarak “akıllı” testlerin geliştirilmesidir. En yaygın olarak ortay çıkan dal ve sınır algoritması (branch and bound technique) dır. İki değişkenli problemlerin grafik çözüm şeklidir. Bu teknik de sürekli optimumla başlar ancak, sistematik olarak olurlu tamsayı noktalarını içermeyen parçaları eleyerek çözüm alanını alt problemlere “bölme” şeklinde gelişir.

Araştırma metodunda tüm tamsayı değerlerinin çift değişken olması durumunda özel bir durum ortaya çıkar. Değişkenlerin ikili özelliği araştırma prosedürünü oldukça basitleştirir.

Burada ele alınan lineer tamsayılı problemlerden kesme metodları R. E. Gomory tarafından geliştirilmiştir. Bunlar basit tamsayılı problemlere uygulanan kesirli algoritma ve karmaşık tamsayılı problemler için oluşturulmuş karmaşık algoritmadır. Dal ve sınır algoritması esas olarak A.H.Land ve A.G.Doig tarafından geliştirilmiştir. Ancak, R.J.Dankin’in yaptığı dönüştürme büyük hesaplama avantajı yarattığından burada buna değinilmiştir. Üçüncü algoritma eklemeli algoritma (additive algorithm) basit sıfır-bir problemine uygulanmaktadır.

3.1. Kesme Algoritması (Cutting-Plane Algorithm)

Bu algoritmayı bir örnek üzerinde açıklamak daha uygun olacaktır. Aşağıdaki tamsayılı lineer programlama problemini ele alalım.

Min. z = 7x₁ + 9x₂

Ş.k.g. -x₁ + 3x₂ ≤ 6

7x₁ + x₂ ≤ 35

x₁ , x₂ negatif olmayan tamsayıdır.

Şekil 1

Optimal çözüm, bütünlük koşulu dikkate alınmadığında, grafik olarak Şakil 1’de gösterilmiştir. Bu, z =63 , x₁ = 9/2 ve x₂ = 7/2 şeklindedir.

Kesme algoritmasına göre amaç, dışbükey çözüm alanını değiştirmek, böylece uygun en üst noktayı tamsayı yapmaktır. Çözüm algoritmasının sınırlarındaki bu değişiklikler yine dışbükey halinde olmalıdır. Ayrıca bu değişiklik, orijinal problemdeki hiçbir olurlu tamsayı çözümün çıkarılmasına izin vermemelidir. Şekilde, tamsayılı optimal çözüm sağlayan (4,3) değeri ile keyfi seçilen iki tane ikincil kısıtın probleme nasıl eklendiği gösterilmektedir. Burada çıkarılan alanın tamsayılı çözüm içermediği dikkate alınmalıdır. Aşağıdaki analiz, ikincil kısıtların sistematik olarak basit ve karmaşık tamsayılı problemler için nasıl geliştirildiği anlatılmaktadır.

3.1.1. Kesirli ( Basit Tamsayılı ) Algoritma

Bu algoritmanın uygulanmasında tüm katsayıların ve denklemin sağ tarafındaki sabitin tamsayı olması gerekmektedir. Örneğin;

x₁ + 1/3 x₂ ≤ 13/2 kısıtı,

6x₁ + 2x₂ ≤ 39

şekline dönüştürülmelidir. İkinci kısıt her iki tarafın en küçük ortak çarpanla genişletilmesiyle elde edilmiştir.

Yukarıdaki ihtiyaç zorunludur. Çünkü, basit tamsayılı algoritma kurallı ve aylak değişkenler için farklı değildir, tümü tamsayı olmalıdır. Bu nedenle, başlangıçtaki kesirli katsayılar, aylak değişkenlerin tamsayılı olduklarını farz edemez. Bu durumda, kesirli algoritma problemin aylak olmayan değişkenleri cinsinden olurlu tamsayı çözümü olduğu halde hiçbir olurlu çözümün olmadığını gösterebilir.

Öncelikle, problem bütünlük kuralına uymadan kurallı lineer programlama problemi şeklinde çözülür ve eğer optimum çözüm tamsayı çıkarsa yapılması gereken bir şey kalmaz. Çözüme ulaşılmıştır. Aksi taktirde, ikincil kısıtlar çözümü tamsayı olma yönünde etkileyecektir. Bu durum aşağıdaki şekilde geliştirilir. Son optimal tablo aşağıdaki gibi iken;

Temel	x₁	x_i	x_m	w₁	w_j	w_n	Çözüm
z	0	0	0	c₁	c_j	c_n	β₀
x₁	1	0	0	α	α	α	β₁
x_i	0	1	0	α	α	α	β_i
x_m	0	0	1	α	α	α	β_m

Değişkenlerden x_i (i = 1,2,...,m) temel değişkenleri, w_j ise ( j = 1,2,...,n) temel olmayan değişkenleri göstermektedir. Bu değişkenlerin uygun hale gelmesi için şöyle düzenlenir.

i. denklemdeki temel değişkenin x_i , tamsayı olmayan bir değere sahip olduğunu düşünelim;

_{n j}

x_i = β_i - ∑ α w_j , β_i tamsayı değildir

^{j =1 i}

Kesirli algoritmanın iki dezavantajından bahsedilebilir:

Otomatik hesaplamalar sonucu oluşan yuvarlama hataları yanlış optimal tamsayılı çözüm verebilir. Bu sorun, farklı kesirlerin pay ve paydalarının ayrı yerlerde tutularak çözülebilse de bu yöntemle ortaya çıkacak sayıların boyutu bilgisayar kapasitesinin çok üstünde olabilir.

Optimal tamsayılı çözüme ulaşılıncaya kadar herhangi bir tamsayılı çözümün bulunamaması halinde problemin çözümü olursuz kalacaktır. Bu da optimal tamsayılı çözüme ulaşılıncaya kadar herhangi bir iyi tamsayılı çözümün bulunamaması anlamına gelir.

İlk zorluk, tüm-tamsayılı tamsayı algoritması (all-integer integer algorithm) geliştirilerek çözülebilir. Bu algoritma ilk olarak çift simplex algoritmasının uygulanmasına olanak veren tüm-tamsayı tablosu ile başlar. Daha sonra tüm katsayıların bütünlüğünü korumaya yönelik özel kesimler bu tabloya eklenir. Yine de, optimal tamsayılı çözüme ulaşılıncaya kadar çözümün olursuz kalması dezavantajı sürdürmektedir.

İkinci zorluk, tamsayılı başlayan ve olurlu olan ancak optimal olmayan kesme algoritmaların geliştirilmesiyle çözülür. İterasyonlar optimum çözüme ulaşıncaya kadar olurlu ve bütünlük içinde kalmaya devam edecektir. Böylece bu algoritma Gomory’nin algoritmasıyla karşılaştırıldığında öncelikli olurlu olarak tanımlanabilir.

Bunu örnek üzerinde daha kolay anlayabiliriz.

ÖRNEK: Optimum sürekli çözüm aşağıdaki gibidir.

Temel

x₁

x₂

x₃

x₄

Çözüm

z

0

0

28/11

15/11

63

x₂

0

1

7/22

1/22

7/2

x₁

1

0

-1/22

3/22

9/2

Çözüm tamsayı olmadığından kesirli bir kesme tabloya eklenir.

x₂ + 7/22 x₃ + 1/22 x₄= 7/2

Bu denklemin kesirli kesmesi aşağıdaki gibi olur.

S₁ - 7/22 x₃ - 1/22 x₄= -1/2

Buradan yeni tablo şu şekli alır;

Temel	x₁	x₂	x₃	x₄	S₁	Çözüm
z	0	0	28/11	15/11	0	63
x₂	0	1	7/22	1/22	0	7/2
x₁	1	0	-1/22	3/22	0	9/2
S₁	0	0	-7/22	-1/22	1	-1/2

Çift simplex metodu devreye girer;

Temel	x₁	x₂	x₃	x₄	S₁	Çözüm
z	0	0	0	1	8	59
x₂	0	1	0	0	1	73
x₁	1	0	0	1/7	-1/7	32/7
x₁	0	0	1	1/7	-22/7	11/7

Çözüm hala tamsayılı olmadığından yeni bir kesme oluşturulur. x₁ denklemi şu şekilde yazılır;

x₁ + ( 0 + 1/7 ) x₄ + ( -1 + 6/7 ) S₁ = ( 4 + 4/7 )

Buradan da kesme şu şekilde ortaya çıkar;

S₂ – 1/7 x₄ – 6/7 S₁ = -4/7

Bu kısıtı son tabloya eklersek;

Temel

x₁

x₂

x₃

x₄

S₁

S₂

Çözüm

z

0

0

0

1

8

0

59

x₂

0

1

0

0

1

0

3

x₁

1

0

0

1/7

-1/7

0

32/7

x₃
0

0

1

1/7

-22/7

0

11/7

S₂

0

0

0

-1/7

-6/7

1

-4/7

Bunun sonucu da şöyledir;

Temel

x₁

x₂

x₃

x₄

S₁

S₂

Çözüm

z

0

0

0

0

2

7

55

x₂

0

1

0

0

1

0

3

x₁

1

0

0

0

-1

1

4

x₃

0

0

1

0

-4

1

1

x₄

0

0

0

1

6

-7

4

Bu da optimum tamsayılı sonuç olan, z = 55 , x₁ = 4 , x₂ = 3 ’ ü verir.

Yukarıdaki kesmelerin eklenmesi ile çözüm alanı gözönüne alınışı grafik üzerinde de gözlenebilir. İlk kesme;

S₁ - 7/22 x₃ - 1/22 x₄= -1/2

x₁ ve x₂ cinsinden ifade edilirse uygun çözüm aşağıdaki gibi olacaktır;

S₁ - 7/22 ( 6 + x₁– 3x₂ ) - 1/22 ( 35 - 7x₁ – x₂ )= -1/2

veya

S₁ + x₂ = 3

olur.

Bu da; x₂ ≤ 3 ’e denktir.

Benzer şekilde;

S₂ – 1/7 x₄ – 6/7 S₁ = -4/7

Kesmesi x₁ ve x₂ cinsinden ifade edilirse;

x₁ + x₂ ≤ 7

olur. Bu iki kısıtın eklenmesiyle grafikte yeni optimal üst noktanın (4,3) olduğu görülür.

Kesme Metodlarında Kullanılan Hesaplamalar

Geliştirilen çeşitli Kesme yöntemlerinden her biri diğerleriyle ilişkili olarak yeni hesaplama güçlükleri getirmektedir. Bununla beraber, tek başına hiçbir kesme yöntemi hesaplama açısından diğerlerinden üstün olduğu söylenemez.

Her ne kadar bazı özel oluşturulmuş problem çözümlerinde bu yöntemler etkili olmuşlarsa da uygulayıcılar arasındaki genel kanı , kesme yöntemlerinin tamsayılı

problemlerin çözümünde güvenilir olmadığıdır. Deneyler, daha ufak problemlerin bu yöntemle çözüme ulaştırılamayacağını göstermiştir. Pek çok durumda kısıtların sıralamasındaki herhangi bir değişiklik hesaplama yönünden kolay bir problemi oldukça zorlaştırabilmektedir.

Bu yöntemle ilgili genel kanı bunların tek başlarına tamsayılı problemlerin çözümünde güvenilir biçimde kullanılamayacağıdır. Bununla beraber, diğer tekniklerde bu yöntemlerden faydalanılabilmektedir.

3.2. Dal ve Sınır Algoritması

Herhangi bir tam sayılı programın çözümüne yaklaşık bir değer, tamsayı olma mecburiyetini ihmal etmekle meydana gelen lineer programlamanın bilinen çözüm metodlarından birisiyle elde edilir. Eğer çözüm tesadüfen tamsayı çıkarsa o zaman bu çözüm, orijinal tamsayılı programlamanın da optimal çözümüdür.

3.2.1. Dallara Ayırma

Eğer bir yaklaşık değer x_j^* gibi tamsayı olmayan bir değişken içerirse o zaman i₁< x_j^* < i₂ olur. i₁ ve i₂ birbirini takip eden, negatif olmayan tamsayılardır. Orijinal yeni ilk tamsayılı program ya x_j ≤ i₁ yada x_j≥ i₂ kısıtı ile çoğaltılarak iki yeni tamsayılı program eklenebilir. Bu işlem, x_j için mevcut, yani en son tamsayılı olmayan çözümü tekrar değerlendirmeden elimine eder. Fakat orijinal veya ilk probleme ait bütün mümkün tamsayılı çözümleri ihtiva eder.

3.2.2. Sınırlama

Amaç fonksiyonu maksimize edildiğinde dallanma, tamsayı çözüm elde edilinceye kadar devam eder. Bu ilk tamsayı çözüm için amaç fonksiyonunun değeri, problem için bir alt sınır olur ve tamsayı olsun yada olmasın birinci yaklaşık değeri bu alt sınırdan daha küçük amaç fonksiyonunu veren diğer programların hiçbirisi gözönüne alınmazlar. Dallanma, amaç fonksiyonunun değeri alt sınırdan daha büyük olan ancak tamsayı olmayan bir yaklaşık

değere sahip programdan devam eder. Eğer işlem sırasında mevcut alt sınırdan daha büyük bir amaç fonksiyonuna sahip bir çözüm çıkartılırsa, bu değer yeni alt sınır olur. İlk alt sınır elimine edilir. Dallanma prosesi, inceleme altında tamsayı olmayan birinci yaklaşık değerli hiçbir program kalmayıncaya kadar devam eder. Bu noktada mevcut alt sınır çözüm, orijinal (ilk) tamsayılı programın optimal çözümüdür. Eğer amaç fonksiyonunun minimize edilmesi gerekiyorsa, aynı prosedürde bu sefer üst sınırlar kullanılır. Yani birinci tamsayılı çözümün değeri, problem için bir üst sınır olur ve birinci yaklaşık z değeri üst sınırdan büyük olanlar elimine edilir.

Bu algoritmada, optimale en yakın programdan dallanılır. Birçok seçenek varsa, amaç fonksiyonunun maksimizasyonu için en büyük değerli z, amaç fonksiyonunun minimizasyonu için ise, en küçük değerli z değeri seçilir.

Eğer birinci yaklaşık değer, birden fazla tamsayı olmayan değişkeni içeriyorsa, yeni kısıtlar tamsayı olmaktan en uzak değişkene (0.5’e en yakın ondalıklıya) empoze edilir. Eşitlik durumunda değişkenlerden herhangi biri keyfi seçilir. Bir tamsayılı program için birden fazla optimum çözüm bulmak mümkündür. Her iki durumda da çözümlerden birisini optimum çözüm olarak kabul ederiz.

ÖRNEK: Verilen tamsayılı programlama probleminin optimum çözümünü Datson algoritmasıyla çözün.

Max. z = 3x₁+ 4x₂

Ş.k.g. 2x₁ + x₂ ≤ 6

2x₁ + 3x₂ ≤ 9

x₁, x₂ ≥ 0 ve tamsayı

ÇÖZÜM: 2x₁ + x₂ = 6 x₁= 0 x₂ = 6

x₁= 3 x₂ = 0

2x₁ + 3x₂ = 9 x₁= 0 x₂ = 3

x₁= 4,5 x₂ = 0

Optimum noktanın (C) hesaplanması;

2x₁ + x₂ = 6

2x₁ + 3x₂ = 9

x₂^* = 1,5 x₁^* = 2,25

max. z = 3*2,25 + 4*1,5 = 12,75

x₂^* dan dallanılır. Yani kısıtlar; x₂ ≤ 1 ve x₂ ≥ 2

Prg. 2 : max. z = 3x₁+ 4x₂max. z = 3x₁+ 4x₂

Ş.k.g. 2x₁ + x₂ ≤ 6 Ş.k.g. 2x₁ + x₂ ≤ 6

2x₁ + 3x₂ ≤ 9 2x₁ + 3x₂ ≤ 9

x₂ ≤ 1 x₂ ≥ 2

x₁, x₂ ≥ 0 ve ts. x₁, x₂ ≥ 0 ve ts.

E ( x₁^* = 2,5 x₂^* = 1 ) z =11,5

G ( x₁^* = 1,5 x₂^* = 2 ) z =12,5 z’si büyük olan alınır.

Prg. 3 : x₁ ≤ 1 ve x₁ ≥ 2

Prg. 4 : max. z = 3x₁+ 4x₂max. z = 3x₁+ 4x₂

Ş.k.g. 2x₁ + x₂ ≤ 6 Ş.k.g. 2x₁ + x₂ ≤ 6

2x₁ + 3x₂ ≤ 9 2x₁ + 3x₂ ≤ 9

x₂ ≥ 2 x₂ ≥ 2

x₁ ≤ 1 x₁ ≥ 2

x₁, x₂ ≥ 0 ve ts. x₁, x₂ ≥ 0 ve ts.

L optimum noktadır. Fizibil çözüm yok.

L (x₁^* = 1 x₂^* = 7/3 )

Max. z = 12,33

2 < x₂^* < 3 x₂ ≤ 2 x₂ ≥ 3

Prg. 6 : max. z = 3x₁+ 4x₂Prg. 7 : max. z = 3x₁+ 4x₂

Ş.k.g. 2x₁ + x₂ ≤ 6 Ş.k.g. 2x₁ + x₂ ≤ 6

2x₁ + 3x₂ ≤ 9 2x₁ + 3x₂ ≤ 9

x₂ ≥ 2 x₂ ≥ 2

x₁ ≤ 1 x₁ ≤ 1

x₂ ≤ 2 x₂ ≥ 3

x₁, x₂ ≥ 0 ve ts. x₁, x₂ ≥ 0 ve ts.

Fizibil doğru parçası var HK . Fizibil nokta var D .

x₁^* = 1 x₂^* = 2 z^* = 11 x₁^* = 0 x₂^* = 3 z^* = 12

6. ve 7. programlar tamsayılı sonuç vermiştir. Ancak, program 7’nin sonucu, bu problemin optimum çözümü olarak kabul edilir. Dallanılabilecek tek program, program 2’dir. Ancak, bunun z^* değeri (11,5) , alt sınırdan (12) küçük olduğundan, bu programdan dallanmaya gerek kalmamaktadır.

Problemin ağaç diyagramı ise şu şekildedir;

z^* = 11,5 z^* = 11

x₂ ≤ 1 x₂ ≤ 2

z =12 z^* = 12,33

x₁ ≤ 1

z^* = 12,5 x₂ ≥ 3 z^* = 12

x₂ ≥ 2

x₁ ≥ 2

Dal ve Sınır Algoritmasındaki Hesaplamalar

Dal ve sınır tekniğinde kullanılan bilgisayar kodları daha önce bahsedilen tekniklerden dallanma değişkenleri ve alt problemlerin sıralanması yönünden farlılık göstermektedir. Bu kurallar, deneyler sonucu geliştirilen tahminlere dayanmaktadır.

Daha önceki yöntemlerde her düğümde lineer programı tümünün yeniden çözülmesi temel dezavantajdır. Bu, daha geniş problemlerde önemli zaman kayıplarına yol açmaktadır. Bu sorun, iyi bir sınır belirlenebilirse pek çok düğümün devre dışı bırakılabileceğinin farkedilmesiyle ortadan kaldırılmıştır.

Bu gelişme, bir ağaç diyagramında tüm alt problemlerin çözülme gerekliliğini ortadan kaldırmıştır. Buradaki esas fikir, bir maksimizasyon problemindeki gibi her düğümdeki optimum hedef değeri için bir üstsınır tahmininde bulunmaktır. Eğer bu üst sınır, eldeki tamsayılı çözümlerin en iyisinden küçük kalıyorsa bu düğüm devre dışı bırakılır. Temel avantaj, üst sınırların kolaylıkla tahmin edilebilir olmasıdır.

Buradaki genel fikir x_k ≤ [β_k] ve x_k ≤ [β_k]+1 şartlarını yürüterek, ortaya çıkan cezaların tahminine dayanır. Bu da bu kısıtların her birinin düğümdeki optimum tablo seviyesine çıkartılmasıyla başarılabilir. Temelde bir değişiklik olmaması varsayımıyla bulunmak istenen ceza direkt olarak amaç fonksiyonu katsayılarından çıkartılabilir.

Bu cezaların hesaplanması kolay olmakla beraber eksikliği, amaç değerlerindeki gerçek sapmalarla orantılı olmak zorunda değildir. Bu eksikliği gidermek için yapılan çalışmalardan en ilginç olanı kesme metodlarının kullanıldığı yöntemdir. Yine de bu yöntemlere rağmen tam olarak giderilemediğinden ceza yöntemi özellikle problemin büyüklüğü arttığında etkisiz kalmaktadır.

Dal sınır metodunun eksikliğine rağmen bu yöntemin normal büyüklükteki tamsayılı programların çözümünde en etkin yöntem olduğu söylenebilir.

3.3. Ya Bu- Ya O Tipi Kısıtlayıcılar (Zero-One İmplict Enumeration)

Her tamsayılı değişken belirli sayıdaki 0 veya 1 şeklindeki (çift) değişken cinsinden tanımlanabilir. Bunun en kolay yolu şöyledir.

0 ≤ x ≤ n eşitsizliğinde x bir tamsayılı değişken ve n de bir tamsayılı üst sınırdır. Buna göre, y₁ , y₂ ,..., y_n sıfır-bir değişkenleridir.

x = y₁ + y₂ +...+ y_n

yukarıdaki denklem x’in tüm olurlu değerlerini gösteren ikili bir ifadedir. İkili değişkenlerin n’den daha küçük olduğu durumlarda kullanılan bir diğer gösterim şekli de aşağıdaki gibidir.

x = y₀ + 2y₁ + 2²y₂ +...+ 2^k y_k

Bu denklemdeki k değişkeni 2^k+1 –1 ≥ n şartını sağlayan en küçük tamsayıdır.

Her tamsayılı problemin sıfır-bir değişkeniyle hesaplanmasındaki kolaylıktan ötürü ikili forma dönüştürülmesi fikri bu özellikleri etkili bir algoritma geliştirmek üzere kullanmaya yol açmıştır.

Eklemeli algoritma (additive algorithm) yöntemi de aslında genişletilmiş bir dal-sınır algoritması uygulamasından farklı değildir. Burada orijinal algoritma hiçbir zaman lineer programlama çözümünü içermez. Aslında, buradaki tek aritmetik işlem çıkartma ve toplamalardır. Bu nedenle sıfır-bir algoritması bazı uygulamalarda eklemeli algoritma halini almaktadır.

Dal-sınır algoritmasında bu yöntemden bahsedildiğinden iki yöntem arasındaki ilişkinin anlaşılması daha kolay anlaşılacaktır.

Eklemeli algoritmanın temel fikri, 2ⁿ olası çözümün numaralandırılmasıdır. Bununla beraber, bu yöntem bazı çözümlerin dikkatli incelenmesine gerek kalmadan elenmesine de olanak verir. Böylece, son analizde 2ⁿ çözümün bir bölümünün dikkatli incelenmesi gerekmektedir.

YA f₁(x₁,.....,x_n) ≤ 0 YA DA f₂(x₁,......,x_n) ≤ 0

f₁(x₁,.....,x_n) ≤ M.y
f₂(x₁,......,x_n) ≤ M(1-y)

y = 0 à Sadece (1) aktif

y = 1 à Sadece (2) aktif

Örnek : Üç değişik model araba üretilecektir. Ekonomik nedenlerle herhangi bir model üretilecekse en az bin adet üretilmesi gerekiyor.

Model 1 Model 2 Model 3 Kısıtlama

ÇELİK 1,5 T 3 T 5 T 6000 T

İŞ GÜCÜ 30 S 25 S 40 S 60000S

KAR 2000$ 3000$ 4000$

Karar Değişkenleri x_İ = i model araba üretim miktarı i = 1,2,3...

Max 2x₁ + 3x₂ + 4x₃

Kısıtlayıcılar : (1) YA x₁ ≤ 0 VEYA x₁ ≥ 1000

(2) YA x₂ ≤ 0 VEYA x₂ ≥ 1000

(3) YA x₃ ≤ 0 VEYA x₃ ≥ 1000

(4) ÜRETİMDE EN FAZLA ÇELİK KULLANIMI 6000 T

(5) ÜRETİMDE EN FAZLA İŞ GÜCÜ KULLANIMI 60000 S

(1) KISITLAYICI x₁ ≤ M₁y₁ M₁ = min{6000/1.5 60000/30 }

1000 – x₁ ≤ M₁y₁ = min{4000 , 2000} = 2000

y₁ = 0 VEYA 1

y₁ = 1 à x₁ ≥ 1000

y₁ = 0 à x₁ ≤ 0

Max. z = 2x₁ + 3x₂ + 4x₃

x₁ ≤ 2000 y₁

1000 - x₁ ≤ 2000 (1 – y₁)

x₂ ≤ 2000 y₂

1000 – x₂ ≤ 2000 (1 – y₂)

x₃ ≤ 1200 y₂

1000 – x₃ ≤ 1200 (1 – y₂)

1.5 x₁ + 3 x₂ + 5 x₃ ≤ 6000

30 x₁ + 25 x₂ + 40 x₃ ≤ 60000

x₁, x₂, x₃ ≥ 0 ; x₁, x₂, x₃ T/S

y₁, y₂, y₃ = 0 veya 1

Optimal Çözüm : Z = 6000

X₂=2000 , Y₂ = 1

Y₁=Y₃=X₁=X₃=0