Tamsayılı Programlama

Tamsayılı Programlama Nedir?

Tamsayı kısıtlamalarıyla optimizasyon problemlerini çözün

Tamsayı programlama algoritmaları, eşitlik, eşitsizlik ve tamsayı kısıtlamalarına tabi bir işlevi en aza indirir veya en üst düzeye çıkarır. Tamsayı kısıtlamaları, optimizasyon problemindeki değişkenlerin bir kısmını veya tamamını yalnızca tamsayı değerleri alacak şekilde kısıtlar. Bu, ayrı miktarları (bir stoğun veya bir bataryadaki hücrelerin payları gibi) veya evet / hayır kararlarını içeren problemlerin doğru bir şekilde modellenmesini sağlar. Değişkenlerin yalnızca bazılarında tamsayı kısıtlamaları olduğunda, soruna karma tamsayılı program (MIP) adı verilir. Örnek tamsayı programlama problemleri arasında finansta portföy optimizasyonu, enerji üretiminde üretim birimlerinin optimal dağıtımı (birim taahhüdü), mühendislikte tasarım optimizasyonu veya ulaşım, tedarik zinciri uygulamalarında çizelgeleme ve yönlendirme yer alır.

Tamsayı programlama, işlevi en aza indiren bir vektör x bulmanın matematiksel problemidir:

minx f(x)

Kısıtlamalara tabi olarak:

g(x) ≤ 0 (inequality constraint)

h(x) = 0 (equality constraint)

xi ∈ Z (integer constraint)

Bu, tamsayı programlamanın en genel biçimidir ve karışık tamsayılı doğrusal olmayan program (MINLP) olarak adlandırılır.

Pek çok problem sadece doğrusal hedefler ve kısıtlamalar ile formüle edilebilir. Bu durumda, tamsayılı programa karışık tamsayılı doğrusal program (MILP) adı verilir ve şu şekilde yazılır:

minx {fT x}

Kısıtlamalara tabi olarak:

Ax ≤ b (inequality constraint)

Aeqx = beq (equality constraint)

lb ≤ x ≤ ub (bound constraint)

xi ∈ Z (integer constraint)

MATLAB’de Karışık Tamsayılı Doğrusal Programlama

Tamsayı programlama algoritmaları, MATLAB® gibi yazılımlarda uygulanabilir. MILP’leri çözmek, tipik olarak, çözüm uzayını daraltmak, tamsayı uygulanabilir çözümler bulmak ve çözüm uzayının daha iyi tamsayı uygulanabilir çözümler içermeyen kısımlarını atmak için tekniklerin bir kombinasyonunu kullanmayı gerektirir. Tamsayı programlama için yaygın teknikler şunları içerir:

Kesme düzlemleri: Probleme, arama alanını azaltan ek kısıtlamalar ekleyin.
Sezgisel: Tamsayı uygulanabilir çözümler arayın.
Dal ve sınır: En uygun çözümü sistematik olarak arayın. Algoritma, tamsayı değişkenlerinin sınırlı olası değer aralıklarıyla doğrusal programlama gevşetmelerini çözer.

Optimization Toolbox™ içindeki MILP çözücü bu teknikleri uygular.

MATLAB’de Karma Tamsayılı Doğrusal Olmayan Programlama

Bazı MINLP’ler, bu tamsayı programlama tekniklerini doğrusal olmayan fonksiyonlara uyarlayarak veya doğrusal olmayan fonksiyonları doğrusallaştırarak ve bir MILP dizisi üzerinde işlemler yaparak çözülebilir. Doğrusal olmayan fonksiyonlar yalnızca integral noktalarda değerlendirilebildiği durumlarda başka tekniklere de ihtiyaç duyarlar. Bu tür tamsayı programlarına uygulanabilen iki algoritma, Global Optimization Toolbox’ta kullanılmaktadır.

Genetik algoritmalar: İntegral değerlerle sınırlı bireysel çözümlerden oluşan bir popülasyonu tekrar tekrar değiştiren bir doğal seçilim sürecini taklit eder.
Temsili optimizasyon: Sorunun gevşetilebilen ve daha sonra MILP tekniklerinin MINLP’ye uyarlanmasıyla çözülebilen vekil, geçici bir modelini otomatik olarak oluşturur.

Tamsayı programlama hakkında daha fazla bilgi için bkz. Optimization Toolbox ve Global Optimization Toolbox.

Örnekler;