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

Çok Amaçlı Doğrusal Programlama (ÇADP)

Ortaya koyan
Steuer, R. E.; Charnes, A.; Cooper, W. W.
Yıl
1955–1986
Tür
Mathematical optimization / vector optimization
Aile
Simulation / optimization

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

Yazı boyutu

Ne işe yarar?

Çok Amaçlı Doğrusal Programlama (ÇADP), klasik doğrusal programlamayı, doğrusal kısıtlamalarla tanımlanan bir uygun bölge üzerinde eş zamanlı olarak birden çok çelişkili doğrusal amaç fonksiyonunu işlemek üzere genişletir.

Tek bir optimal çözüm yerine, ÇADP, karar vericinin tercih edilen bir dengeyi seçtiği bir Pareto-etkin sınır üretir. Kaynak tahsisi, planlama ve rekabetçi hedeflere sahip tasarım problemleri için operasyon araştırması ve yönetim biliminin temelini oluşturur.

Yöntemin mantığı

Sıradan doğrusal programlamada tek bir maliyeti minimize eder veya tek bir kârı maksimize edersiniz, ancak gerçek kararlar neredeyse her zaman birden çok çelişkili hedefi içerir — hizmet seviyesini maksimize ederken maliyeti minimize etmek, emisyonları minimize ederken. ÇADP, tek bir çözümün tüm hedeflerde aynı anda en iyi olmadığını kabul eder. Bir hedefin iyileştirilmesinin zorunlu olarak diğerini kötüleştireceği baskın olmayan (Pareto-etkin) çözümlerin tam sınırını haritalandırır. Karar verici daha sonra bu sınırdan nihai bir çözüm seçmek için tercih bilgilerini — ağırlıklar, hedef seviyeler veya etkileşimli sorgular — kullanır, dengelemeleri gizli bir bileşik puan içine gizlemek yerine açık hale getirir.

Tarih

Çok amaçlı doğrusal programlamanın teorik temelleri, 1950'lerde Charnes ve Cooper'ın hedef programlama ve Koopmans'ın etkin üretim üzerine çalışmalarına dayanmaktadır. Steuer'in 1986 tarihli ders kitabı, bugün hala standart olan ağırlıklı toplam, epsilon-kısıtlama ve etkileşimli yöntemleri sistematikleştirerek alanı pekiştirmiştir. ÇADP artık dünya çapında operasyon araştırması müfredatlarının temel bir konusudur.

Ne zaman kullanılır?

Problemin birden çok çelişkili doğrusal hedefi ve doğrusal kısıtlamaları olduğu, verilerin sürekli ve kesin olarak bilindiği (veya deterministik olarak kabul edilebildiği) ve karar vericinin önceden toplanmış bir puana razı olmak yerine dengelemeleri açıkça anlaması gerektiği durumlarda ÇADP kullanın. Tipik ayarlar arasında üretim planlaması, portföy tahsisi, ulaşım rotalama ve kamu kaynağı bütçelemesi yer alır. Amaçlar veya kısıtlamalar doğrusal olmadığında (bunun yerine çok amaçlı doğrusal olmayan programlama veya meta-sezgisel yöntemler kullanın), veriler ayrık veya ikili olduğunda (çok amaçlı tamsayı programlaması kullanın), amaç sayısı beş veya altıyı aştığında (etkin sınır hesaplama açısından yönetilemez hale gelir) veya karar verici tekrarlayan tercih belirlemeye istekli olmadığında KULLANMAYIN.

Sınırlar ve dikkat edilmesi gerekenler

  • Yalnızca doğrusal amaç fonksiyonları ve doğrusal kısıtlamalarla sınırlıdır; gerçek dünya problemleri genellikle doğrusal değildir.
  • Etkin sınır, yüksek boyutlarda üstel olarak çok sayıda uç nokta içerebilir, bu da kapsamlı sayımı pratik olmaktan çıkarır.
  • Kesin sayısal veri gerektirir; katsayılardaki belirsizlik veya bulanıklık yerel olarak ele alınmaz.
  • Etkileşimli yöntemler, karar vericinin kullanılabilirliğine ve tercihlerini tutarlı bir şekilde ifade etme yeteneğine büyük ölçüde bağlıdır.

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

Güçlü yönleri

  • Karar vericilere dengelemelerin tam bir resmini veren tam Pareto-etkin sınırı üretir.
  • Basit tabanlı çözücüler aracılığıyla orta ölçekli problemler için hesaplama açısından elverişlidir.
  • Etkin sınırın her noktasının matematiksel optimalliğini garanti eder.
  • Olgun yazılımlar (CPLEX, Gurobi, açık kaynaklı alternatifler) tarafından iyi desteklenir.
  • Dengelemeler, opak bir bileşik endeks içine çökertilmek yerine açık hale getirilir.

Uygulama alanları

  • Maliyet, verim ve kaynak kullanımını dengeleyen üretim planlaması.
  • Getiri, risk ve likiditeyi dengeleyen portföy optimizasyonu.
  • Rekabetçi maliyet ve hizmet hedefleriyle ulaşım ve lojistik ağ tasarımı.
  • Maliyeti azaltırken emisyon ve güvenilirlik hedeflerini karşılayan enerji sistemi planlaması.
  • Eşitlik, verimlilik ve bütçe kısıtlamalarını dengeleyen sağlık kaynağı tahsisi.
  • Ekonomik ve ekolojik performansı eş zamanlı olarak optimize eden çevre yönetimi.

Nasıl çalışır?

Nasıl çalışır?

1

k adet doğrusal amaç fonksiyonunu f1(x) ile fk(x) arasında ve doğrusal eşitsizlik ve eşitlik kısıtlamalarıyla (Ax <= b, x >= 0) tanımlanan uygun bir bölge X formüle edin. Hangi hedeflerin minimize edileceğini ve hangilerinin maksimize edileceğini belirleyin. Tüm amaç fonksiyonlarının ve kısıtlamaların karar değişkenlerinde doğrusal olduğundan emin olun.

Formül
\min_{x \in X} \mathbf{f}(x) = (f_1(x), f_2(x), \ldots, f_k(x))^T \text{ s.t. } Ax \leq b,\; x \geq 0
2

Pareto-etkin (baskın olmayan) çözümler kümesini oluşturun. Yaygın yaklaşımlar arasında ağırlıklı toplam yöntemi (simplex boyunca değişen ağırlıklar), epsilon-kısıtlama yöntemi (diğerlerini sınırlarken bir hedefi optimize etme) ve Chebyshev yöntemi bulunur. Her yaklaşım, etkin sınırın bir kısmını veya tamamını izler.

3

Vektör problemini bir dizi tek amaçlı LP'ye dönüştürmek için bir ölçeklendirme tekniği uygulayın. Ağırlıklı toplam yaklaşımında, sistematik olarak değiştirilmiş ağırlık vektörleri için min sum(wi * fi(x)) çözün. Amaç uzayının her etkin uç noktasını kaydedin.

Formül
\min_{x \in X} \sum_{i=1}^{k} w_i f_i(x), \quad w_i \geq 0, \; \sum w_i = 1
4

Pareto sınırını karakterize etmek için etkin uç noktalarını ve bunları birbirine bağlayan kenarları toplayın. Dengelemelerin büyüklüğünü anlamak için sınır boyunca her hedefin aralığını analiz edin. Sınırı karar vericiye tablolar veya iki amaçlı grafikler aracılığıyla sunun.

5

Tercih edilen bir çözümü etkin kümeden seçmek için karar vericiyi dahil edin. Etkileşimli yöntemler (STEM, NIMBUS), çözümleri sunmak ve karar vericiden tercihini ifade etmesini istemek arasında gidip gelerek, önceliklerini en iyi yansıtan nihai bir seçime yakınsar.

Sık yapılan hatalar

  • Ağırlıklı toplam ölçeklendirmesinde sabit ağırlıklar kullanmak ve yalnızca bir çözüm raporlamak, sınırı gizler ve ÇADP'nin amacını boşa çıkarır.
  • Pareto etkinliğini optimalite ile karıştırmak: sınırın her noktası etkindir, ancak hiçbiri tercih bilgisi olmadan küresel olarak 'en iyi' değildir.
  • Uygun bölgenin sınırlı olup olmadığını kontrol etmemek: sınırsız bir problem, sonlu bir etkin küme üretmez.
  • ÇADP'yi karar vericiyi seçim sürecine dahil etmeden bir kara kutu olarak ele almak, keyfi nihai seçimlere yol açar.
  • ÇADP'yi doğası gereği tamsayı problemlerine, çok amaçlı tamsayı programlamasına geçiş yapmadan uygulamak, bütünlüğü ihlal eden çözümler üretir.

Sık sorulan sorular

ÇADP, hedef programlamadan nasıl farklıdır?

Hedef programlama, bir özel durum veya varyanttır: her hedefi bir hedef seviyeye dönüştürür ve ardından bu hedeflerden sapmaları minimize ederek tek bir çözüm üretir. Genel biçimindeki ÇADP, hedef seviyeleri önceden belirlemeden tam etkin sınırı karakterize etmeyi amaçlar, bu da karar vericiye daha fazla esneklik sağlar.

ÇADP birden fazla hedefi işleyebilir mi?

Evet, ancak Pareto sınırı iki veya üç hedefi aştığında görselleştirmesi zorlaşır ve etkin uç noktalarının sayısı üstel olarak artabilir. Dört veya daha fazla hedef için etkileşimli yöntemler ve temsili alt küme teknikleri önerilir.

Verilerim belirsizse ne olur?

Standart ÇADP deterministik katsayıları varsayar. Belirsizlik, stokastik çok amaçlı doğrusal programlamaya (şans kısıtlamaları, senaryo tabanlı yaklaşımlar) veya ayrı yöntemler olan sağlam çok amaçlı optimizasyona genişleterek ele alınabilir.

ÇADP, çok amaçlı optimizasyon ile aynı şey midir?

ÇADP, tüm amaçların ve kısıtlamaların doğrusal olduğu çok amaçlı optimizasyonun özel bir durumudur. Çok amaçlı optimizasyon, doğrusal olmayan, tamsayı ve birleştirme varyantlarını da içeren daha geniş alandır.

Hangi ölçeklendirme yöntemi kullanılmalı?

Ağırlıklı toplam yöntemi basittir ancak sınırın dışbükey olmayan kısımlarını kaçırır. Epsilon-kısıtlama yöntemi, dışbükey olmayan bölgeler için bile tam sınırı kurtarabilir ve genellikle kapsamlı analiz için tercih edilir. Karar verici katılımı mümkün olduğunda etkileşimli yöntemler en iyisidir.

İlgili yöntemler

Kaynaklar

  1. Steuer, R. E. (1986). Multiple Criteria Optimization: Theory, Computation, and Application. John Wiley & Sons, New York.

    ISBN: 9780471888468
    Kopyalandı.
  2. Chankong, V., Haimes, Y. Y. (1983). Multiobjective Decision Making: Theory and Methodology. North-Holland, New York.

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