Doğrusal Programlama
Doğrusal programlama, doğrusal eşitlik ve eşitsizlik kısıtlamalarına tabi doğrusal bir amacı optimize eden, optimizasyon problemlerinin en yaygın uygulanan sınıfıdır.
Tanım
Doğrusal bir program, doğrusal kısıtlamalara tabi karar değişkenlerinin doğrusal bir fonksiyonunu minimize veya maksimize eder; uygun bölgesi dışbükey bir çokyüzlüdür ve eğer mevcutsa, bir optimum bir köşede elde edilir.
Kapsam
Bu konu, doğrusal bir programın standart formunu, uygun çokyüzlülerin ve köşelerinin geometrisini, simpleks yöntemini, doğrusal programlama dualitesini ve tamamlayıcı gevşekliği, duyarlılık analizini ve büyük ölçekli problemler için iç nokta yöntemlerini kapsamaktadır.
Temel sorular
- Pratik bir kaynak problemi doğrusal bir program olarak nasıl formüle edilir?
- Bir optimum neden uygun çokyüzlünün bir köşesinde meydana gelir?
- Dual doğrusal program, primal hakkında bize ne anlatır?
- Hangi algoritmalar büyük doğrusal programları verimli bir şekilde çözer?
Temel kuramlar
- Doğrusal programlamanın temel teoremi
- Eğer bir doğrusal programın optimal bir çözümü varsa, bir optimum uygun çokyüzlünün bir köşesinde elde edilir ve bu da aramayı sonlu sayıda aday noktaya indirger.
- Dualite ve tamamlayıcı gevşeklik
- Her doğrusal programın, optimal değeri primalinkine eşit olan bir duali vardır ve tamamlayıcı gevşeklik, aktif kısıtlamaları sıfır olmayan dual değişkenlere bağlayarak optimallik sertifikaları ve ekonomik yorumlar sağlar.
- Simpleks ve iç nokta yöntemleri
- Simpleks yöntemi, amacı iyileştirmek için köşeler arasında hareket ederken, iç nokta yöntemleri iç kısmı kateder ve doğrusal programları kanıtlanabilir polinom zamanda çözer.
Klinik önem
Doğrusal programlama, yöneylem araştırmasının temel taşlarından biridir; üretim planlaması, ulaşım ve lojistik, çizelgeleme, diyet ve karıştırma problemleri ile ağ akışları için kullanılmakta olup, tam sayı ve doğrusal olmayan optimizasyon içinde bir alt yordam olarak hizmet vermektedir.
Tarihçe
Kantorovich, 1939'da üretim planlaması için doğrusal optimizasyonu tanıtmış, Dantzig ise 1947'de genel problemi ve simpleks yöntemini formüle etmiştir. Von Neumann, oyun teorisi ile dualiteyi tanımış, Khachiyan'ın elipsoid yöntemi ve Karmarkar'ın iç nokta yöntemi ise daha sonra polinom zamanlı çözülebilirliği ortaya koymuştur.
Öne çıkan isimler
- George Dantzig
- Leonid Kantorovich
- John von Neumann
- Narendra Karmarkar
İlgili konular
Temel eserler
- dantzig1963
- luenberger2008
Sıkça sorulan sorular
- Optimum neden bir köşede yer alır?
- Doğrusal bir amaç, sabit bir yönde en hızlı şekilde artar, bu nedenle dışbükey bir çokyüzlü üzerinde en iyi değeri sınıra ve nihayetinde bir köşeye itilir. Amaç, bir kenar veya yüz boyunca sabit olmadığı sürece, optimum bir köşede elde edilir.
- Simpleks yöntemi her zaman hızlı mıdır?
- Pratikte simpleks yöntemi oldukça verimlidir, ancak en kötü durum örnekleri, üstel sayıda adım atmasına neden olabilmektedir. İç nokta yöntemleri polinom zamanlı bir garanti sunar ve modern çözücüler probleme bağlı olarak her ikisini de kullanmaktadır.