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

Simpleks Yöntemi

Ortaya koyan
George Dantzig
Yıl
1947
Tür
algorithm
Aile
Optimization

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

Yazı boyutu

Ne işe yarar?

George Dantzig tarafından 1947'de geliştirilen Simpleks Yöntemi, doğrusal programlama problemlerini çözmek için temel bir algoritmadır.

Kısıtlamalara tabi olarak amaç fonksiyonunun maksimize edildiği veya minimize edildiği en uygun çözümü bulmak için uygun bölgenin köşe noktalarını sistematik olarak inceler.

Yöntemin mantığı

Yöntem, doğrusal kısıtlamalarla tanımlanan uygun bölgenin bir köşe noktasından başlayarak, amaç fonksiyonu değerini iyileştiren komşu köşe noktalarına hareket eder. Daha fazla iyileştirme sunan komşu bir köşe noktasına ulaşılana kadar devam eder ve bu da optimalliği garanti eder. Algoritma, doğrusal programların en uygun çözümlerinin kısıt kısıt politopunun köşe noktalarında bulunduğunu geometrik özelliğinden yararlanır.

Tarih

George Dantzig, 1947'de simpleks yöntemini tanıttı, operasyon araştırmalarında devrim yarattı ve on yıllarca doğrusal programlama için standart algoritma haline geldi. Klee ve Minty (1972), en kötü durum üstel karmaşıklığını gösterdi, ancak ampirik olarak yöntem hızlı kaldı. 1980'lerde alternatif olarak iç nokta yöntemlerinin geliştirilmesi görüldü, ancak simpleks yöntemi, sağlamlığı ve modern uygulamaların karmaşıklığı nedeniyle birçok pratik uygulama için baskın kaldı.

Ne zaman kullanılır?

Uygun bölgenin sınırlı olduğu ve amaç fonksiyonunun doğrusal olduğu doğrusal programlama problemlerini çözerken simpleks yöntemini uygulayın. Özellikle yüzlerce veya binlerce değişken ve kısıtlamaya sahip problemler için etkilidir. Doğrusal olmayan veya sınırsız problemler için kullanmaktan kaçının. Çok büyük ölçekli problemler için iç nokta yöntemleri tercih edilebilir.

Sınırlar ve dikkat edilmesi gerekenler

  • Üstel en kötü durum zaman karmaşıklığı (pratikte nadir olsa da)
  • Yüksek derecede dejeneratif problemler üzerinde kötü performans gösterebilir
  • Çok büyük ölçekli problemler üzerinde iç nokta yöntemlerinden daha az rekabetçidir
  • Problemlerin standart formda ve açık kısıt yönetimi ile olmasını gerektirir

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

Güçlü yönleri

  • Doğrusal programlar için sonlu sürede optimal çözümü bulmayı garanti eder
  • Dikkatli uygulama ve dejenerasyon yönetimi ile pratikte verimlidir
  • Yaygın olarak uygulanmış ve olgun optimizasyon kütüphaneleri tarafından desteklenmektedir
  • Daha gelişmiş optimizasyon algoritmalarını anlamak için temel oluşturur

Uygulama alanları

  • Üretim planlaması: talep kısıtlamalarını karşılarken maliyetleri en aza indirmek için üretim miktarlarını optimize etme
  • Nakliye ve lojistik: depolar ve dağıtım merkezleri arasındaki optimal nakliye rotalarını ve miktarlarını belirleme
  • Portföy optimizasyonu: risk ve bütçe kısıtlamalarına tabi olarak getirileri maksimize etmek için varlıklar arasında sermaye tahsisi
  • Kaynak tahsisi: organizasyonel çıktıyı maksimize etmek için işgücü ve malzeme gibi sınırlı kaynakları dağıtma
  • Karıştırma problemleri: kalite spesifikasyonlarını karşılamak ve maliyeti en aza indirmek için ham maddeleri optimal oranlarda karıştırma
  • İşgücü çizelgeleme: talebi karşılarken işgücü maliyetlerini en aza indirmek için işçileri vardiyalara atama

Nasıl çalışır?

Nasıl çalışır?

1

Doğrusal programı, gevşek değişkenlerle standart forma dönüştürün ve başlangıçta temel uygun bir çözüm belirleyin (genellikle uygunsa orijin).

2

Simpleks tablosu üzerinde pivot işlemleri gerçekleştirin: negatif indirgenmiş maliyete sahip bir giren değişken seçin, minimum oran testi ile çıkan değişkeni belirleyin ve temeli güncelleyin.

3

İndirgenmiş maliyetleri kullanarak optimallik koşullarını kontrol edin; maksimizasyon için tüm indirgenmiş maliyetler negatif değilse, mevcut çözüm optimaldir; aksi takdirde pivot adımına geri dönün.

Sık yapılan hatalar

  • Dejenere tabanlarla karşılaşıldığında döngüyü düzgün bir şekilde ele alamama (Bland kuralını veya pertürbasyon yöntemlerini kullanın)
  • Yanlış pivot seçimi veya tablo güncellemelerindeki aritmetik hatalar sayısal kararsızlığa yol açabilir
  • Algoritmayı başlatmadan önce sınırsızlığı veya uygunsuzluğu kontrol etmeme

Sık sorulan sorular

Simpleks yöntemi neden 'simpleks' olarak adlandırılır?

Simpleks terimi, herhangi bir boyuttaki bir politopun en basit biçimini ifade eder. Algoritma, kısıtlamalarla tanımlanan politopun kenarları ve köşe noktaları boyunca hareket ederek çalışır.

Simpleks yöntemi ile iç nokta yöntemi arasındaki fark nedir?

Simpleks yöntemi uygun bölgenin sınırında köşe noktalarında kalırken, iç nokta yöntemleri iç kısımdan geçer. İç nokta yöntemlerinin en kötü durum karmaşıklığı daha iyidir, ancak simpleks orta büyüklükteki problemler için pratikte genellikle daha hızlıdır.

Uygunsuzluk veya sınırsızlık nasıl ele alınır?

İki aşamalı simpleks yöntemini kullanın: birinci aşama, temel uygun bir çözüm bulmak veya uygunsuzluğu belirlemek için yardımcı bir problem çözer; ikinci aşama, orijinal probleme standart simpleks yöntemini uygular.

Dejenerasyon nedir ve neden önemlidir?

Dejenerasyon, temel uygun bir çözümün birden fazla temel temsiline sahip olduğunda meydana gelir ve bu da döngüye neden olabilir. Bland kuralını (değişkenleri indeks sırasına göre seçin) veya pertürbasyon yöntemlerini kullanarak bunu ele alın.

İlgili yöntemler

Kaynaklar

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

    DOI kaynağını aç
    Kopyalandı.
  2. Vanderbei, R. J. (2014). Linear Programming: Foundations and Extensions (4th ed.). Springer.

    DOI kaynağını aç
    Kopyalandı.