İçeriğe atla
Arama sonuçlarına dön

Deterministik Lineer Programlama — Belirli Parametrelere Sahip Klasik LP

Ortaya koyan
George B. Dantzig
Yıl
1947
Tür
Deterministic mathematical optimization
Aile
Simulation / optimization

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

Deterministik Lineer Programlama (DLP), amaç fonksiyonu katsayılarının, kısıt katsayılarının ve sağ taraf değerlerinin tamamının kesinlikle bilindiği lineer programlamanın klasik biçimidir.

Doğrusal kısıtlamalara tabi doğrusal bir amacı maksimize etmek veya minimize etmek için kaynakların en uygun tahsisini bulur ve sabit, kesin veriler altında kesin, tekrarlanabilir bir çözüm sunar.

Yöntemin mantığı

Her biri bilinen maliyetlere ve getirilerine sahip projeler arasında sabit bir bütçeyi, tam olarak bildiğiniz kaynak limitlerine tabi olarak ayırdığınızı hayal edin. Deterministik LP bunu bir doğrusal eşitsizlik sistemi olarak kodlar ve bu kısıtlamalardan en fazla değeri elde eden köşe noktası çözümünü bulur. Her parametre kesin olduğundan — olasılık dağılımları, belirsizlik yok — çözücü, bir sonuç dağılımı yerine tek bir kesin optimal plan döndürür. Bu netlik, verilerin iyi ölçüldüğü ve belirsizliğin birincil endişe kaynağı olmadığı durumlarda DLP'yi doğal ilk tercih model haline getirir.

Tarih

Lineer programlama, George B. Dantzig tarafından 1947'de ABD Hava Kuvvetleri'nde çalışırken Simpleks algoritmasının geliştirilmesiyle biçimlendirilmiştir. Dantzig'in 1963 tarihli monografisi kanonik referans haline geldi. 'Deterministik' nitelemesi, stokastik LP varyantlarının tanıtılmasıyla (Dantzig ve Beale, 1950'ler-1960'lar) ortaya çıktı ve orijinal kesin parametre modelini olasılıksal uzantılarından ayırmak için kullanıldı.

Ne zaman kullanılır?

Karar problemi doğrusal bir amaç ve doğrusal kısıtlamalarla modellenebildiğinde ve tüm parametrelerin sabit sabitler olarak kabul edilmelerini haklı çıkaracak kadar kesinlikle bilindiği durumlarda Deterministik LP'yi kullanın. İdeal ortamlar arasında üretim planlaması, ulaşım ve lojistik, diyet ve harmanlama problemleri ve kararlı koşullar altında ağ akışı yer alır. Parametrelerin gerçekten belirsiz olduğu ve riskin önemli olduğu durumlarda DLP'yi KULLANMAYIN — bunun yerine Stokastik LP veya Sağlam LP'yi tercih edin. Amaç veya kısıtlamaların doğrusal olmadığı, değişkenlerin tamsayı olması gerektiği (MIP kullanın) veya birden fazla çelişkili amacın tek bir ağırlıklı toplama indirgenmeden dengelenmesi gerektiği (çok amaçlı LP veya hedef programlama kullanın) durumlarda DLP'den kaçının.

Sınırlar ve dikkat edilmesi gerekenler

  • Tüm ilişkilerin kesinlikle doğrusal olmasını gerektirir — doğrusal olmayan maliyet eğrileri veya azalan getiriler, yaklaştırma olmadan yakalanamaz.
  • Tüm parametreler bilinmeli ve sabit olmalıdır; model belirsizliği veya parametre tahmin hatasını ele almak için yerel bir mekanizma sağlamaz.
  • Optimum çözüm benzersiz olmayabilir (dejenere), bu da raporlama bazının seçimini ek kriterler olmadan belirsiz hale getirir.
  • Tamsayı veya kombinatoryal gereksinimler (örneğin, evet/hayır kararları) karışık tamsayılı programlamaya uzantı gerektirir, bu da hesaplama açısından daha zordur.
  • Yoğun kısıt matrislerine sahip büyük ölçekli problemler, modern çözücüler için bile bellek yoğun olabilir.

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Herhangi bir uygun, sınırlı LP örneği için dışbükeylik nedeniyle küresel optimum çözüm garanti edilir.
  • Yüksek ölçeklenebilirlik — modern çözücüler saniyeler içinde milyonlarca değişkeni ve kısıtı ele alır.
  • Dual değişkenler ve duyarlılık analizi, gölge fiyatları ve aralıkları hakkında zengin ekonomik yorumlar sağlar.
  • Şeffaf, denetlenebilir formülasyon: her varsayım kısıt matrisinde açıkça belirtilmiştir.
  • Olgun yazılım ekosistemi (CPLEX, Gurobi, HiGHS, GLPK) güvenilir, iyi test edilmiş uygulamalarla.
  • Net geçme/kalma uygunluk sinyali: uygunsuzluk, modelin yanlış belirtilmesini hemen ortaya çıkarır.

Uygulama alanları

  • Sabit kaynak kapasiteleri ve bilinen talep ile üretim ve imalat planlaması.
  • Ulaşım ve lojistik: bir ağ üzerinden minimum maliyetli nakliye rotalarını bulma.
  • Diyet ve harmanlama problemleri: bileşim kısıtlamalarını karşılayan en az maliyetli besin veya kimyasal karışımları formüle etme.
  • Doğrusal getiri ve bütçe kısıtlamaları altında finansal portföy optimizasyonu.
  • Bilinen maliyetler ve kapasitelerle güç üretim birimlerinin optimum sevkiyatı ile enerji sistemleri planlaması.
  • Talep ve teslim sürelerinin bilinen sabitler olarak kabul edildiği durumlarda tedarik zinciri ağ tasarımı.

Nasıl çalışır?

Nasıl çalışır?

1

Karar değişkenlerini x (örneğin, üretim miktarları, akış miktarları), minimize etmek veya maksimize etmek için amaç fonksiyonunu c^T x ve kısıt kümesini Ax <= b, x >= 0 ile tanımlayın. c, A ve b'deki tüm katsayılar kesin, bilinen sabitler olarak kabul edilir — bu, modeli deterministik yapan şeydir. Standart formdaki LP'yi yazın: min c^T x, Ax = b, x >= 0 koşullarına bağlı olarak.

Formül
\min_{x} \; c^\top x \quad \text{s.t.} \quad Ax \leq b, \; x \geq 0
2

Optimizasyondan önce, uygun bölgenin boş olmadığını (kısıt kümesinin en az bir çözümü olduğunu) ve amacın sınırlı olduğunu doğrulayın. Uygun bölge boşsa problem uygunsuzdur; amaç sınırsızsa model yanlış belirtilmiştir. Bu kontroller çözücüler tarafından otomatik olarak yapılır ancak formülasyon hatalarını yakalamak için analist tarafından yorumlanmalıdır.

3

LP'yi Simpleks algoritması (dışbükey politopun kenarları boyunca optimum köşeye doğru kaydırma) veya iç nokta yöntemi (uygun bölgenin içinden bir yol izleyerek) kullanarak çözün. Her iki yaklaşım da uygun kümenin dışbükeyliğini ve amacın doğrusalını kullanır ve herhangi bir yerel optimumun küresel olmasını garanti eder. Modern çözücüler (CPLEX, Gurobi, HiGHS) milyonlarca değişkeni ve kısıtı verimli bir şekilde ele alır.

4

Çözücü, optimum karar vektörünü x* ve optimum amaç değerini c^T x* döndürür. Uygun bölge dışbükey bir politop ve amaç doğrusal olduğundan, optimum her zaman bir köşede (temel uygun çözüm) elde edilir. x*'ı kaydedin ve tüm kısıtlamaları sağladığını doğrulayın, ardından bunu tekrar yönetimsel terimlere çevirin (örneğin, üretilecek birimler, kullanılacak rotalar).

Formül
x^* = \arg\min \{ c^\top x : Ax \leq b,\; x \geq 0 \}
5

x*'ı elde ettikten sonra, mevcut bazın — ve dolayısıyla optimum çözümün — değişmeden önce c veya b'deki her katsayının ne kadar değişebileceğini belirlemek için duyarlılık (optimum sonrası) analizi yapın. Gölge fiyatları (dual değişkenler), her kısıtın gevşetilmesinin marjinal değerini ölçer. Model deterministik olsa da, duyarlılık analizi deterministik çerçeveden ayrılmadan çözümün parametre tahmin hatalarına karşı sağlamlığını ortaya koyar.

Sık yapılan hatalar

  • Belirsiz parametreleri, sonraki duyarlılık analizi olmadan sabit nokta tahminleri olarak ele almak, kağıt üzerinde optimum ancak pratikte kırılgan çözümler üretebilir.
  • Negatif olmama kısıtlamalarını veya mantıksal sınırları dahil etmeyi unutmak, matematiksel olarak optimum ancak operasyonel olarak uygunsuz çözümler üretebilir (örneğin, negatif üretim miktarları).
  • Gölge fiyatlarını, aralık analiziyle belirlenen geçerlilik aralığının dışında kalan garantili marjinal değerler olarak yanlış yorumlamak.
  • Gerçek problem tamsayı yapısına sahip olduğunda (örneğin, kamyon sayısı) ve LP çözümlerini yuvarladığında DLP kullanmak — bu, kısıtlamaları ihlal edebilir veya gerçek optimumları kaçırabilir.
  • Tek bir ağırlıklı toplama indirgenen birden fazla amacı, ağırlıkların paydaş tercihlerini doğru bir şekilde yansıttığını doğrulamadan aşırı toplamak, önemli ödünleşimleri gizler.

Sık sorulan sorular

LP'yi 'stokastik' yerine 'deterministik' yapan nedir?

Deterministik LP'de amaç fonksiyonundaki, kısıt matrisindeki ve sağ taraf vektöründeki her katsayı bilinen bir sabittir. Buna karşılık, Stokastik LP bu katsayıların bazılarını veya tamamını olasılık dağılımlarına sahip rastgele değişkenler olarak ele alır ve senaryolar boyunca iyi performans gösteren veya yüksek olasılıkla iyi performans gösteren çözümler arar.

Simpleks algoritması her zaman verimli midir?

Pratikte evet — Simpleks yöntemi gerçek dünya LP'lerinin neredeyse tamamını son derece hızlı çözer. Teorik olarak en kötü durumda üssel zaman alabilir (Klee–Minty örnekleri), ancak iç nokta yöntemleri (örneğin, Karmarkar algoritması) polinom zamanda çalışır ve çok büyük örnekler için rekabetçidir.

Bazı karar değişkenlerimin tam sayı olması gerekiyorsa DLP'yi kullanabilir miyim?

Hayır. Değişkenlerin tamsayı olması gerekiyorsa (örneğin, satın alınacak makine sayısı), model karışık tamsayılı veya saf tamsayılı bir program haline gelir. LP gevşetmesini çözüp yuvarlamak kısıtlamaları ihlal edebilir veya gerçek tamsayı optimumunu kaçırabilir; bunun yerine özel bir MIP çözücüsü kullanın.

Çözdükten sonra gölge fiyatları nasıl yardımcı olur?

Bir kısıtın gölge fiyatı (dual değişkeni), geçerli aralık dahilinde, o kısıtın sağ tarafı bir birim gevşetilirse amaç değerinin ne kadar iyileşeceğini söyler. Bu, maliyet etkin bir şekilde kapasiteyi genişletmek için nereye yatırım yapılacağına dair kararları yönlendirir.

DLP'den Sağlam veya Stokastik LP'ye ne zaman yükseltmeliyim?

Parametre belirsizliği önemsiz olmadığında ve gerçekleşen parametre değerleri altında uygunsuz veya kötü bir çözümün maliyeti önemli olduğunda yükseltin. Önemli bir katsayıda %10-20'lik bir sapma, hangi çözümün tercih edildiğini değiştirirse veya kısıt ihlaline neden olursa, deterministik LP'nin kesinlik varsayımı çok güçlüdür.

İlgili yöntemler

Kaynaklar

  1. Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press, Princeton, NJ.

    ISBN: 9780691059136
    Kopyalandı.
  2. Linear programming. Wikipedia.

    Yayın kaynağını aç
    Kopyalandı.