Geometri ve sayısal algoritmalar · 45 / 53
Linear programming, Simplex ve duality
Anla → iz sür → uygula → gerekçelendir
2 dk okuma · uygulama için ayrıca zaman ayırLinear programming, doğrusal amaç fonksiyonunu doğrusal eşitlik/eşitsizlikler altında optimize eder. Feasible bölge bir polyhedron'dur. Problem infeasible, unbounded veya sonlu optimumlu olabilir. Integer programming farklıdır: sürekli LP çözümünü yuvarlamak genellikle geçerli tamsayı çözüm vermez.
Simplex uygun köşeler arasında pivot yapar; pratikte güçlüdür ancak genel worst-case polinom zaman garantisi yoktur. Ellipsoid ve interior-point yöntemleri uygun modelde polinom zaman teorisini sağlar. Degeneracy, cycling, sayısal tolerans ve kötü koşullanmış kısıtlar uygulamanın gerçek sorunlarıdır. Bland benzeri pivot kuralları cycling'i önleyebilir.
Dual problem kaynakların marjinal değerini modeller. Weak duality ile primal feasible amaç dual bound'u geçemez; strong duality uygun sonlu LP koşullarında optimumların eşit olduğunu söyler. Complementary slackness optimumu doğrulamak için kullanılır. Min-cost flow ve matching bazı özel yapılarda integer çözümlü LP bağlantılarına sahiptir. Solver çıktısında yalnız objective değil feasibility ve optimality certificate kontrol edilir.
Adım adım iz sürme
max 3x+2y; x+y≤4, x≤2, x,y≥0 için köşeler (0,0),(2,0),(2,2),(0,4). En iyi (2,2), değer 10.
Maliyet ve varsayımlar
Köşe tarama örneği yalnız küçük modeldir; genel LP çözücüsü değildir. Simplex worst-case üstel olabilir.
Çalıştırılabilir örnek
Python 3 ile çalıştır. Assert küçük bir örneği denetler; genel doğruluk ispatı değildir. Bazı ileri örnekler özellikle küçük model veya referans oracle'dır; tam üretim uygulaması değildir.
vertices=[(0,0),(2,0),(2,2),(0,4)]
best=max(vertices,key=lambda p:3*p[0]+2*p[1])
assert best==(2,2)KAVRADIĞINI KONTROL ET
Sıra sende
Kısıt x+y≤−1 ve x,y≥0 olursa ne olur?
Çözümün mantığını göster
Feasible nokta yoktur: infeasible. Unbounded ile karıştırma; unbounded için feasible yönde amaç sınırsız iyileşir.
Bir adım ileri
- Örneği değiştirmeden önce girdi sözleşmesini ve invariantı yaz.
- Uygun olan boş, sınır, tekrar ve adversarial girdileri ekle. Basit bir oracle ile karşılaştır.
- Belirtilen modelde maliyeti çıkar; farklı girdi büyüklüklerini ölç ve farkları gerekçelendir.
Temel kaynaklar ve ders notları
Bu eğitimde özgün anlatım kullanıldı; aşağıdaki kaynaklar ispatlar ve ileri okumalar sunar. Bağlantılar daha geniş ders modülünü kapsayabilir.
MIT 6.046J · Design and Analysis ↗Jeff Erickson · Algorithms ↗