Tam Sayılı Programlama

Tam sayılı programlama (TSP; İng. integer programming, IP) — bazı veya tüm değişkenlerin yalnızca tam sayı değerleri alması gereken problemleri inceleyen matematiksel optimizasyon dalıdır.

En çok çalışılmış özel durum, amaç fonksiyonu ve kısıtların doğrusal olduğu tam sayılı doğrusal programlamadır (TSDP; İng. integer linear programming, ILP). Değişkenlerin herhangi bir gerçel değer alabileceği doğrusal programlamanın aksine, tam sayılılık koşulu TSP problemlerini çözmeyi önemli ölçüde güçleştirmektedir.

Tam sayılı programlama; değişkenlerin doğası gereği ayrık olduğu (örneğin üretilen birim sayısı veya çalışan sayısı gibi) ekonomi, lojistik, üretim planlaması ve diğer alanlarda geniş uygulama alanı bulmaktadır.

Tanım ve Terminoloji

Tam sayılı doğrusal programlamanın genel problemi şu şekilde yazılabilir:

$x$ vektörünü bul; bu vektör:

$c^{T}x$'yi maksimize (veya minimize) eder

kısıtlar altında:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{Z}}^n$ ($x$ vektörünün tüm bileşenleri tam sayıdır)

burada $x$ — değişkenler vektörü, $c$ ve $b$ — vektörler, $A$ ise katsayılar matrisidir.

Değişkenlere yönelik gereksinimlere bağlı olarak şu problem türleri ayırt edilir:

• Tamamen tam sayılı programlama: tüm değişkenler tam sayı olmak zorundadır.
• Karma tam sayılı programlama (İng. mixed-integer programming, MIP): yalnızca değişkenlerin bir kısmı tam sayı olmak zorundadır.
• İkili (0-1) programlama: değişkenler yalnızca 0 veya 1 değerini alır; bu durum "evet/hayır" türündeki mantıksal kararların modellenmesine olanak tanır.

Temel Özellikler ve Karmaşıklık

Hesaplama Karmaşıklığı

Tam sayılı doğrusal programlama problemi genel durumda NP-zordur. Bu, herhangi bir TSP problemi için polinom zamanda kesin optimal çözüm bulabilen bilinen bir algoritmanın mevcut olmadığı anlamına gelir. Karmaşıklık, problemin kombinatoryal doğasından kaynaklanmaktadır; zira olası tam sayılı çözümlerin sayısı, değişken sayısındaki artışla birlikte üstel olarak büyüyebilir.

Doğrusal Programlama ile İlişki (DP-Gevşemesi)

Herhangi bir TSP problemi için, değişkenlerin tam sayılılık koşulunun kaldırıldığı doğrusal gevşemesi — yani bir doğrusal programlama (DP) problemi — oluşturulabilir. DP-gevşemesinin çözümünün iki önemli özelliği vardır:

1. Çok daha hızlı (polinom zamanda) bulunabilir.
2. DP-gevşemesinin optimal amaç fonksiyonu değeri, orijinal tam sayılı problemin optimal değeri için bir sınır (maksimizasyon problemi için üst sınır, minimizasyon için alt sınır) sağlar.

Ancak DP-gevşemesinin kesirli çözümünün en yakın tam sayılara yuvarlanması, kural olarak, tam sayılı problemin optimal hatta uygun bir çözümüne ulaşmayı sağlamaz.

Tam Ünimodülerlik Özelliği

TSDP problemlerinin, DP-gevşemeleri kadar kolay çözülebilen önemli bir sınıfı vardır. Bunlar, kısıt matrisinin $A$ tamamen ünimodüler olduğu problemlerdir (yani herhangi bir kare alt matrisinin determinantı 0, +1 veya −1'e eşittir). Eğer $A$ matrisi tamamen ünimodüler ve $b$ vektörü tam sayıysa, DP-gevşemesinin uygun çözüm çokyüzlüsünün tüm köşe noktaları otomatik olarak tam sayılı olacaktır. Dolayısıyla simpleks yöntemi ile bulunan çözüm tam sayılı olacaktır. Bu tür problemlere örnek olarak ulaştırma problemi ve atama problemi gösterilebilir.

Çözüm Yöntemleri

Tam ünimodülerlik özelliğine sahip olmayan genel TSP problemlerinin çözümü için örtük sıralama fikrine dayalı kesin yöntemler geliştirilmiştir.

• Dal ve sınır yöntemi (İng. Branch and Bound) — uygun çözümler kümesinin sistematik olarak alt kümelere bölünmesine (dallanma) ve optimal çözümü kesinlikle içermeyen alt kümelerin elenmesine dayanan temel kesin yöntemdir. Alt kümelerin umut vaat edip etmediğini değerlendirmek için DP-gevşemesi kullanılır.

• Kesme düzlemleri yöntemi (Gomory yöntemi; İng. Cutting Plane Method) — probleme sıralı olarak yeni doğrusal kısıtlar ("kesimler") ekleyen yinelemeli bir yaklaşımdır. Bu kesimler, DP-gevşemesinin kesirli çözümlerini "keserken" uygun tam sayılı çözümlerin hiçbirini etkilemez ve DP-gevşemesinin uygun çözüm bölgesini kademeli olarak tam sayılı çözümlerin konveks zarfına yaklaştırır.

Modern çözücüler genellikle her iki yaklaşımın avantajlarını birleştiren dal ve kesme yöntemi (İng. Branch and Cut) gibi hibrit algoritmalar kullanır.

Örnekler ve Uygulama Alanları

Tam sayılı programlama, kombinatoryal optimizasyonun pek çok klasik problemini modellemeye olanak tanır.

• Sırt çantası problemi: toplam ağırlık kısıtını aşmadan maksimum toplam değere sahip eşya setini seçmenin amaçlandığı klasik bir 0-1 programlama problemidir.
• Gezgin satıcı problemi: belirli bir şehirler kümesinden geçen en kısa rotanın bulunması problemidir. Değişkenlerin grafın kenarlarının nihai rotaya dahil edilip edilmediğini temsil ettiği bir tam sayılı programlama problemi olarak formüle edilebilir.

Esnekliği sayesinde TSP, yöneylem araştırmasının en çok talep edilen araçlarından biri olup şu alanlarda uygulama bulmaktadır:

• Lojistik ve tedarik zinciri yönetimi: taşıma rotalarının optimizasyonu, depo yerleşimi, stok yönetimi.
• Üretim planlaması: üretim çizelgeleri oluşturma, kaynak dağılımı, ekipman yüklemesi.
• Finans ve ekonomi: yatırım portföyü oluşturma, sermaye bütçelemesi.
• Telekomünikasyon ve enerji: iletişim ağı tasarımı, enerji ünitelerinin çalışma planlaması.

Ayrıca bakınız

• Doğrusal programlama
• Dal ve sınır yöntemi

Notlar

</references>