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

Sağlam Hedef Programlama — Belirsizlik Altında Birden Fazla Hedefe Ulaşma

Ortaya koyan
Charnes, A. & Cooper, W. W. (goal programming); Mulvey, J. M. et al. (robust optimization framework)
Yıl
1961 (GP); 1990s (robust extension)
Tür
Mathematical programming under uncertainty
Aile
Simulation / optimization

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

Yazı boyutu

Ne işe yarar?

Sağlam Hedef Programlama (RGP), klasik hedef programlamayı belirsiz veya muğlak model parametrelerini ele almak üzere genişletir.

Kesin hedeflerden sapmaları en aza indirmek yerine, makul senaryolar veya belirsiz veri gerçekleşmeleri yelpazesinde uygulanabilir ve optimuma yakın kalan çözümler arar. RGP, hedeflerin iddialı olduğu ve girdi verilerinin doğal değişkenlik veya tahmin hatası taşıdığı planlama problemlerinde özellikle değerlidir.

Yöntemin mantığı

Klasik hedef programlama şunu sorar: birden fazla hedefe aynı anda ne kadar yaklaşabiliriz? Sağlam hedef programlama kritik bir ikinci soruyu ekler: verilerimiz yanlış olduğunda veya koşullar değiştiğinde bu çözüm hala kabul edilebilir şekilde performans gösteriyor mu? Maliyetlerdeki, kaynak kullanılabilirlik veya hedef düzeylerindeki belirsizliği açıkça modelleyerek, RGP ideal koşullar altında biraz optimumdan fedakarlık eden, ancak gerçekçi senaryolar boyunca istikrar karşılığında bunu yapan planlar bulur. En kötü durum veya ortalama senaryo sapmasını, yalnızca nominal veri sapmasını değil, gerçek hedef olarak ele alır.

Tarih

Hedef programlama, 1961'de Charnes ve Cooper tarafından hedeflerden ağırlıklı sapmaları en aza indirerek birden fazla hedefi ele alma yolu olarak tanıtıldı. 1995'te Mulvey, Vanderbei ve Zenios tarafından biçimselleştirilen sağlam optimizasyon çerçevesi, senaryo tabanlı belirsizliği matematiksel programlara yerleştirmek için ilkeli bir yol sağladı. 1990'lar ve 2000'lerde araştırmacılar sağlam optimizasyon fikirlerini operasyon araştırmasındaki çok hedeflere yönelik planlama problemlerine uyguladıkça, sağlam hedef programlamaya entegrasyonları doğal olarak takip etti.

Ne zaman kullanılır?

Parametreler belirsiz olduğunda çok hedeflere sahip planlama ile karşılaştığınızda ve varsayılan koşullar altında değil, senaryolar boyunca güvenilir bir çözüm gerektirdiğinizde sağlam hedef programlamayı kullanın. Tedarik zinciri planlaması, portföy yönetimi, kamu politikası ve belirsiz bütçeler veya taleplerle kaynak tahsisi için idealdir. Tüm parametrelerin kesin olarak bilindiği durumlarda (standart GP yeterlidir), senaryo sayısı anlaşılabilir yeniden formülasyon olmadan astronomik derecede büyük olduğunda veya hedefler gerçekten ölçülemez olduğunda ve sapma tabanlı bir toplama anlamlı olmadığında KULLANMAYIN.

Sınırlar ve dikkat edilmesi gerekenler

  • Belirsizlik modelini (senaryo kümesi veya belirsizlik politopu) formüle etmek alan bilgisi gerektirir ve genellikle en zor kısımdır.
  • Sağlam formülasyonlar, deterministik GP'ye kıyasla problem boyutunu ve hesaplama maliyetini önemli ölçüde artırabilir.
  • Sağlamlık kriterinin (minimax, beklenen değer, varyans cezası) seçimi standartlaşmamıştır ve sonuçları önemli ölçüde etkiler.
  • Sağlam ayarlarda leksikografik öncelik, senaryolar boyunca doğru bir şekilde uygulanması karmaşık olabilir.

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

Güçlü yönleri

  • Birden fazla çelişkili hedefi aynı anda ele alırken parametre belirsizliğini açıkça hesaba katar.
  • Veri pertürbasyonları altında zarifçe azalan çözümler ürettiği için pratikte daha uygulanabilir çözümler üretir.
  • Esnek: hem senaryo tabanlı stokastik formülasyonları hem de aralık/polihedral belirsizlik kümelerini barındırır.
  • Öncelik yapısı (leksikografik veya ağırlıklı) hedef öneminin sezgisel kontrolünü sağlar.
  • Sağlamlık-optimumluk değiş tokuşu, lambda ceza parametresi aracılığıyla açık ve kontrol edilebilir.

Uygulama alanları

  • Belirsiz talep ve maliyetlerle tedarik zinciri ağı tasarımı
  • Bütçe değişkenliği altında birden fazla hizmet hedefini karşılayan sağlık kaynağı tahsisi
  • Piyasa belirsizliği altında getiri, risk ve likidite hedeflerini dengeleyen portföy optimizasyonu
  • Belirsiz gelecek gelirleri ve çok sektörlü harcama hedefleriyle kamu politikası planlaması
  • Belirsiz yenilenebilir çıktı ve birden fazla çevresel ve maliyet hedefleriyle enerji sistemi planlaması

Nasıl çalışır?

Nasıl çalışır?

1

Karar değişkenlerini, her hedef için iddialı hedef düzeylerini (örneğin, kâr >= T1, atık <= T2) ve öncelik yapısını (leksikografik veya ağırlıklı) belirleyin. Her hedefin aşırı ve eksik gerçekleştirilmesini ölçen pozitif ve negatif sapma değişkenleri d+ ve d- tanımlayın.

2

Belirsizlik kaynaklarını belirtin: belirsiz sağ taraf hedefleri, kısıt katsayıları veya amaç ağırlıkları. Belirsizliği olasılıkları ps olan sonlu bir senaryo kümesi S = {s1, ..., sK} olarak veya sağlam optimizasyon formülasyonları için aralık/polihedral belirsizlik kümeleri olarak temsil edin.

3

Senaryo-indeksli sapma değişkenlerini dahil ederek ve sağlamlık cezası terimleri ekleyerek sağlam modeli oluşturun. Yaygın bir formülasyon, çözüm kalitesi ile istikrarı dengeleyerek, beklenen sapma artı senaryolar boyunca varyansın (veya en kötü durum sapmasının) lambda katını cezalandırmayı en aza indirir.

4

Ortaya çıkan deterministik eşdeğer modeli çözün — seçilen sağlamlık kriterine bağlı olarak tipik olarak bir kuadratik veya lineer program. Leksikografik öncelik, hedef düzeyleri üzerinde sıralı optimizasyon ile ele alınabilir.

5

Çözümü tüm senaryolar üzerinden değerlendirin: ortalama, en kötü durum ve en iyi durum hedef gerçekleştirme oranlarını raporlayın. Optimum ile istikrar arasındaki verimlilik sınırını ortaya çıkarmak için sağlamlık değiş tokuş parametresi lambda üzerinde duyarlılık analizi yapın.

Sık yapılan hatalar

  • Sağlam GP'yi stokastik GP ile karıştırmak: sağlam GP genellikle en kötü durum veya varyans cezalı performansı hedeflerken, stokastik GP beklenen sapmayı en aza indirir — seçim hem modeli hem de yorumu değiştirir.
  • Aşırı muhafazakarlık: belirsizlik kümesini kalibre etmeden en kötü durum sağlamlığını kullanmak, tipik senaryolarda optimumdan uzak, aşırı temkinli çözümler üretebilir.
  • Senaryo olasılıklarını veya belirsizlik sınırlarını gerçek verilere karşı doğrulama yapmayı ihmal etmek, sağlamlık analizini yanıltıcı hale getirir.
  • Lambda cezasını gerçek değiş tokuş eğrisini keşfetmek yerine sabit bir sabit olarak ele almak, sağlamlığın gerçek maliyetini gizler.

Sık sorulan sorular

Sağlam hedef programlama, stokastik hedef programlamadan nasıl farklıdır?

Stokastik GP, senaryolar boyunca olasılıkla ağırlıklandırılmış beklenen (ortalama) sapmaları en aza indirir. Sağlam GP tipik olarak değişkenliği veya en kötü durum sonuçlarını da cezalandırır — daha muhafazakardır ancak tüm senaryolar boyunca, düşük olasılıklı olanlar dahil, daha tutarlı performans gösteren çözümler üretir.

Aralık belirsizliğini senaryolar yerine kullanabilir miyim?

Evet. Parametreler aralıklara veya politoplara düştüğünde, sağlam bir karşılık formülasyonu (Ben-Tal ve Nemirovski'nin yaklaşımını izleyerek) türetilebilir ve belirsiz GP'yi standart LP veya SOCP çözücüler tarafından çözülebilen deterministik bir programa dönüştürebilir.

Lambda parametresi neyi kontrol eder?

Lambda, nominal performans ile sağlamlık arasındaki değiş tokuşu yönetir. Sıfır lambda beklenen değer GP'sini geri kazanır; lambda'yı artırmak varyansı veya en kötü durum sapmasını daha ağır bir şekilde cezalandırır, daha sağlam ancak potansiyel olarak daha az optimum (beklenen değerde) çözümler üretir.

Sağlam hedef programlama için yazılım mevcut mu?

Standart formülasyonlar herhangi bir LP/QP çözücü (CPLEX, Gurobi, GLPK) ile çözülebilir. Stokastik uzantılar, senaryo numaralandırması ile GAMS, SPiNE veya PuLP ve Pyomo gibi Python kütüphanelerini kullanabilir.

Normal GP üzerinde basit duyarlılık analizine göre ne zaman sağlam GP'yi tercih etmeliyim?

Açıkça istikrarı optimize eden tek bir uygulanabilir plan gerektirdiğinizde, sadece seçilmiş bir GP çözümünün parametre değişikliklerine ne kadar duyarlı olduğunu anlamak istediğinizde değil, sağlam GP'yi tercih edin.

İlgili yöntemler

Kaynaklar

  1. Charnes, A., Cooper, W. W. (1961). Management Models and Industrial Applications of Linear Programming. Wiley, New York.

    ISBN: 9780471155041
    Kopyalandı.
  2. Mulvey, J. M., Vanderbei, R. J., Zenios, S. A. (1995). Robust optimization of large-scale systems. Operations Research, 43(2), 264-281.

    DOI kaynağını aç
    Kopyalandı.