Doğrusal Programlama — Doğrusal Kısıtlar Altında Doğrusal Amaç Fonksiyonlarının Optimizasyonu
- Ortaya koyan
- George B. Dantzig
- Yıl
- 1947
- Tür
- Mathematical programming / continuous optimization
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
George B. Dantzig tarafından 1947'de öncülüğü yapılan doğrusal programlama (DP), doğrusal eşitsizlik ve eşitlik kısıtlamaları kümesine tabi olarak, doğrusal bir amaç fonksiyonunun — maliyet minimizasyonu veya kâr maksimizasyonu gibi — en iyi değerini bulmak için kullanılan matematiksel bir yöntemdir.
Operasyon araştırmasının temel tekniğidir ve üretim planlaması, kaynak tahsisi, lojistik, diyet problemleri ve mühendislik, ekonomi ve doğa bilimleri genelindeki sayısız diğer karar verme senaryolarının temelini oluşturur.
Yöntemin mantığı
İki ürün üreten küçük bir fabrikanız olduğunu hayal edin. Her ürün size belirli bir kâr kazandırır, ancak üretimi sınırlı hammadde ve makine zamanı tüketir. Doğrusal programlama, sabit kaynaklarınızdan en fazla kârı elde etmek — herhangi bir fiziksel veya sözleşmesel sınırı ihlal etmeden — için ürünlerin tam karışımını bulur. 'Doğrusal' kısmı, kârın ve kaynak tüketiminin ürettiğiniz miktarlarla doğru orantılı bir ilişki içinde ölçeklendiği anlamına gelir. Mümkün olan seçimler iki boyutta bir poligon (çokgen) ve daha yüksek boyutlarda bir polihedron (çok yüzlü) oluşturur ve optimal cevap her zaman köşelerinden birinde yer alır.
Tarih
Doğrusal programlamanın sistematik gelişimi, George B. Dantzig'in ABD Hava Kuvvetleri'nde çalışırken askeri lojistik planlamasını otomatikleştirmek için Simpleks algoritmasını icat ettiği 1947'de başladı. Dantzig, temel teoriyi 1963 tarihli monografisinde yayınladı ve bu eser hala temel referans niteliğindedir. Sovyetler Birliği'nde Leonid Kantorovich'in bağımsız ve paralel çalışmaları (1939), benzer matematiksel fikirler kullanarak üretim planlamasını ele aldı ve Kantorovich, kısmen bu katkısı nedeniyle 1975'te Ekonomi alanında Nobel Ödülü'ne layık görüldü. Polinom zamanlı çözülebilirlik sorunu, Khachian'ın elipsoid yöntemi (1979) ve daha sonra büyük ölçekli problemler için pratik olarak hızlı olduğu kanıtlanan Karmarkar'ın iç nokta yöntemi (1984) ile çözüldü. Günümüzde, ticari ve açık kaynaklı DP çözücüleri dünya çapında kurumsal kaynak planlama, havayolu çizelgeleme ve enerji sistemlerine entegre edilmiştir.
Ne zaman kullanılır?
Amacınız doğrusal değişkenler kümesine doğrusal olarak bağlı bir miktarı optimize etmek ve tüm kısıtlamalar da doğrusal olduğunda doğrusal programlama uygundur. Dağılımsal varsayım veya minimum örneklem boyutu gerektirmez — istatistiksel bir tahminci değil, deterministik bir matematiksel modeldir. Yöntem, karar değişkenleri sürekli olduğunda (kesirli değerler anlamlıdır) uygulanır; değişkenler tam sayılar veya ikili değerler olmak zorundaysa, bunun yerine tamsayı programlama gereklidir. DP, üretim çizelgeleme, tedarik zinciri lojistiği, diyet ve harmanlama problemleri, finansal portföy optimizasyonu, ulaşım ve atama problemleri ve enerji sevkiyatında yaygın olarak kullanılır.
Sınırlar ve dikkat edilmesi gerekenler
- Doğrusallık gereksinimi: amaç fonksiyonu veya herhangi bir kısıtlama doğrusal değilse, DP modeli yanlış belirtilmiştir ve çözüm yanlış veya mümkün olmayabilir.
- Yalnızca sürekli değişkenler: karar değişkenleri tam sayı veya ikili değerler almak zorundaysa, DP gevşetmesi bir alt sınır verir ancak geçerli bir çözüm vermez; bunun yerine tamsayı programlama kullanılmalıdır.
- Deterministik: DP parametrelerdeki belirsizliği modellemez; veri belirsiz olduğunda stokastik programlama veya sağlam optimizasyon gereklidir.
- Dejenerasyon ve döngü: nadir durumlarda Simpleks yöntemi, yakınsama olmadan dejeneratif tabanlar arasında döngüye girebilir, ancak döngü önleyici kurallar (örneğin, Bland kuralı) bunu çözer.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Garantili global optimum: mümkün bölge dışbükey bir polihedron olduğundan, herhangi bir yerel optimum aynı zamanda global bir optimumdur, alt-optimal bir çözüme takılma riski yoktur.
- Yüksek ölçeklenebilirlik: modern çözücüler (HiGHS, Gurobi, CPLEX) saniyeler içinde milyonlarca değişken ve kısıtlamaya sahip modelleri işler.
- Zengin çözüm sonrası bilgi: gölge fiyatlar ve hassasiyet aralıkları, ek çalıştırmalar olmadan kaynak değeri ve çözüm sağlamlığı hakkında eyleme geçirilebilir içgörüler sunar.
- Dağılımsal varsayım yok: DP tamamen cebirsel bir modeldir, bu nedenle normallik veya verilerin herhangi bir istatistiksel özelliğini gerektirmez.
Uygulama alanları
- Üretim planlaması: makine kapasitesi ve hammadde limitlerine saygı göstererek kârı maksimize eden optimal ürün karışımını bulmak.
- Tedarik zinciri ve ulaşım lojistiği: depolar ve müşteriler ağı boyunca nakliye maliyetlerini en aza indirmek.
- Diyet ve harmanlama problemleri: minimum maliyetle beslenme gereksinimlerini karşılayan bileşen miktarlarını seçmek.
- Finansal portföy optimizasyonu: risk ve düzenleyici kısıtlamalara tabi olarak beklenen getiriyi maksimize etmek için sermayeyi varlıklar arasında tahsis etmek.
- Enerji sevkiyatı ve güç şebekesi çizelgelemesi: elektrik talebini ve jeneratör kapasitesi limitlerini karşılarken yakıt maliyetini en aza indirmek.
- Personel ve işgücü çizelgelemesi: minimum işgücü maliyetiyle talebi karşılamak için işçilere vardiya atamak.
Nasıl çalışır?
Nasıl çalışır?
Gerçek dünya karar problemi matematiksel sembollere çevrilir. Karar değişkenlerini (kontrol edebileceğiniz miktarlar) belirlersiniz, amaç fonksiyonunu (maksimize etmek veya minimize etmek istediğiniz şeyi) bu değişkenlerin doğrusal bir kombinasyonu olarak yazarsınız ve her kısıtlamayı — kaynak limitleri, kapasite sınırları, talep gereksinimleri — doğrusal bir eşitsizlik veya eşitlik olarak yazarsınız. İyi tanımlanmış bir DP, net bir amaca, açık değişken sınırlamalarına ve doğrusal olarak ifade edilen her yapısal kısıtlamaya sahiptir.
Model, bir çözücünün işleyebileceği kanonik veya standart forma getirilir. Eşitsizlikler, negatif olmayan gevşeklik (slack) veya fazlalık (surplus) değişkenleri eklenerek eşitliklere dönüştürülür ve sınırsız herhangi bir değişken, iki negatif olmayan değişkenin farkıyla değiştirilir. Bu mekanik adım, algoritmanın üzerinde çalıştığı tablo veya matris temsilini üretir ve problemi değiştirmez — yalnızca hesaplama için yeniden şekillendirir.
Bir çözücü, mümkün polihedronu optimal köşe için arar. Klasik Simpleks yöntemi, polihedronun kenarları boyunca köşeden köşeye hareket ederek, her zaman amacı iyileştirerek (veya koruyarak), iyileştiren bir komşu kalmayana kadar devam eder. İç nokta (bariyer) yöntemleri bunun yerine mümkün bölgenin içinden merkezi bir yol boyunca seyahat eder, bu da özellikle çok büyük modeller için verimlidir. Mümkün bölge dışbükey olduğu için, her iki aile de bir global optimum varsa onu bulmayı garanti eder.
Çözücü, karar değişkenlerinin optimal değerlerini ve optimal amaç değerini, ikincil değişkenler (gölge fiyatlar) ve hassasiyet aralıkları ile birlikte döndürür. Gölge fiyatlar, bağlayıcı bir kısıtlama birim başına gevşetildiğinde amacın ne kadar iyileşeceğini ölçer — karar vericiye ek kaynakların nerede en değerli olacağını doğrudan söyler. Hassasiyet analizi, mevcut taban optimal olmaktan çıkmadan önce bir maliyet katsayısının veya sağ taraf değerinin ne kadar değişebileceğini belirler.
Sık yapılan hatalar
- Kısıtlamalar veya amaç fonksiyonu doğrusal olmadığında DP uygulamak — çözüm yanlış olacaktır veya çözücü modeli reddedecektir.
- Bütünlük gereksinimlerini göz ardı etmek: sürekli bir DP çözümünü tamsayılara yuvarlamak genel olarak geçerli veya optimal bir tamsayı çözümü vermez; bunun yerine tamsayı programlama kullanın.
- Mümkün olmayan veya sınırsız modeller: mümkün bölge boşsa (çelişkili kısıtlamalar) veya amaç fonksiyonu sınırsızsa (eksik sınır kısıtlamaları), çözücü başarısızlık bildirecektir — çalıştırmadan önce her zaman model yapısını kontrol edin.
- DP çıktısını hassasiyet analizi olmadan bir tavsiye olarak ele almak: teknik olarak optimal olan bir çözüm, verilerdeki küçük bir değişikliğin tavsiyeyi değiştirdiği ince bir kenarda oturabilir — hassasiyet aralıkları her zaman incelenmelidir.
Sık sorulan sorular
Bir problemi DP amaçları için 'doğrusal' yapan nedir?
Hem amaç fonksiyonu hem de her kısıtlama doğrusal olmalıdır — yani her terim, tek bir karar değişkeniyle çarpılan bir sabittir, değişkenlerin çarpımları, üsler ve doğrusal olmayan fonksiyonlar yoktur. Eğer tek bir kısıtlama veya amaç fonksiyonu bile örneğin x çarpı y veya x kare içeriyorsa, standart DP artık geçerli olmaz ve doğrusal olmayan veya karesel programlama çözücüsü gerekir.
Optimal çözüm neden her zaman mümkün bölgenin bir köşesinde yer alır?
Doğrusal kısıtlamalarla tanımlanan mümkün bölge, dışbükey bir polihedrondur (veya politoptur). Doğrusal bir amaç fonksiyonu kendi başına doğrusaldır, bu nedenle dışbükey bir kümenin içine doğru 'çekilemez' — ekstrem değerini her zaman sınırda ve özellikle bir köşe noktasında elde eder. Bu, Simpleks yönteminin köşeden köşeye stratejisinin altında yatan geometrik sezgidir.
Ne zaman DP yerine tamsayı programlamayı kullanmalıyım?
Bir veya daha fazla karar değişkeninin tam sayı veya ikili (0/1) değerler alması gerektiğinde — örneğin, bir tesisin açılıp açılmayacağı (evet/hayır), kaç kamyon gönderileceği (tam sayılar) veya bir seçime hangi öğelerin dahil edileceği gibi. Sürekli DP çözümünü çözüp tamsayılara yuvarlamak genel olarak güvenilir değildir: yuvarlanmış çözümler mümkün olmayabilir veya optimalden uzak olabilir. Tamsayı programlama, daha yüksek hesaplama maliyetiyle bütünlüğü doğru bir şekilde ele alır.
Gölge fiyatlar bana ne anlatır?
Bağlayıcı bir kısıtlama için bir gölge fiyat (ikincil değişken), diğer her şey sabit tutulduğunda, kısıtlamanın sağ tarafı bir birim gevşetildiğinde optimal amaç değerinin ne kadar iyileşeceğini gösterir. Örneğin, bir işgücü saati kısıtlaması üzerindeki 3'lük bir gölge fiyat, bir saat daha fazla işgücü eklemenin amacı 3 birim iyileştireceği anlamına gelir. Bağlayıcı olmayan kısıtlamaların gölge fiyatı sıfırdır — mevcut optimumu sınırlamazlar.
İlgili yöntemler
Kaynaklar
Dantzig, G.B. (1963). Linear Programming and Extensions. Princeton University Press.
ISBN: 9780691059136Kopyalandı.Vanderbei, R.J. (2014). Linear Programming: Foundations and Extensions. Springer.
DOI kaynağını açKopyalandı.