Doğrusal Programlama — Doğrusal Kısıtlar Altında Doğrusal Amaç Fonksiyonlarının Optimizasyonu
Linear Programming (LP) · Ayrıca şöyle bilinir: LP, linear optimization, Doğrusal Programlama (LP)
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.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Yöntem haritası
İlişkili yöntemlerin komşuluğu — keşfetmek için bir düğüm seçin.
+1 tane daha
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.
Güçlü yönler & sınırlılıklar
- 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.
- 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.
SSS
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.
Kaynaklar
- Dantzig, G.B. (1963). Linear Programming and Extensions. Princeton University Press. ISBN: 9780691059136
- Vanderbei, R.J. (2014). Linear Programming: Foundations and Extensions. Springer. DOI: 10.1007/978-1-4614-7630-6 ↗
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 1). Linear Programming (LP). ScholarGate. https://scholargate.app/tr/optimization/linear-programming
Hangi yöntem?
Bu yöntemi en yakın akrabalarının yanına koyup yan yana okuyun — kütüphane kitapları masaya serer; seçim sizindir.
- Hedef ProgramlamaKarar verme↔ karşılaştır
- Tamsayı ProgramlamaOptimizasyon↔ karşılaştır
- Doğrusal Olmayan ProgramlamaOptimizasyon↔ karşılaştır
- Stokastik OptimizasyonOptimizasyon↔ karşılaştır