Tamsayılı Programlama
- FİGES AŞ
- MATLAB&Simulink
- Probleminizi Nasıl Çözeceğinizi Keşfedin
- 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;
- Problem-Based Mixed-Integer Linear Programming (4:31) – Video
- Getting Started with Integer Programming in MATLAB – Örnek
Kullanıcı Hikayeleri
- Operations, Logistics, and Supply Chain Management – Danışmanlık Hizmetleri
- PTTEP Optimizes Gas Field Production -Kullanıcı Hikayesi
- HUBER+SUHNER Optimizes Cable Manufacturing -Kullanıcı Hikayesi
Karışık Tamsayılı Doğrusal Programlama Örnekleri
- Traveling Salesman Problem – Örnek
- Supply Chain Optimization – Örnek
- Solve Sudoku Puzzles – Örnek
- Optimal Dispatch of Power Generators – Örnek
Karışık Tamsayılı Doğrusal Olmayan Programlama Örnekleri
- Mixed-Integer Quadratic Programming Portfolio Optimization – Örnek
- Portfolio Optimization with Semicontinuous and Cardinality Constraints – Örnek
- Solving an Engineering Design Problem Using the Genetic Algorithm – Örnek
- Circuit Design Using Surrogate Optimization – Örnek
Yazılım Referansı
- Problem-Based Optimization – Dokümantasyon
- Linear Programming and Mixed-Integer Linear Programming – Dokümantasyon
- Mixed-Integer Linear Programming Algorithms – Kavramlar
- Tuning Integer Linear Programming – Dokümantasyon
Ayrıca bkz: Optimization Toolbox, Global Optimization Toolbox, linear programming, quadratic programming, nonlinear programming, genetic algorithm, investment management, energy trading, prescriptive analytics, surrogate optimization, power system simulation and optimization