Simpleks algoritması ve uç noktalar
Bu soru için kısacası LP = doğrusal program, BFS = temel uygulanabilir çözüm, SEF = standart eşitlik formu.
Simplex algoritması en uç noktadan en uç noktaya yinelediğinden (Simplex'in LP SEF'deyken BFS'den BFS'ye yinelendiği gerçeğine karşılık gelir), uygulanabilir bölge, içinde gerçekleştirilemeyen bir çokyüzlü olduğunda Simplex algoritması geometrik olarak nasıl çalışır? SEF (örneğin yarım boşluk)? Olası bölgenin uç noktaları olmayan bir LP'miz olduğunu varsayalım. Sonra SEF'de bulunan 'eşdeğer' bir LP yazıp onun yerine Simplex algoritmasını çalıştırabiliriz. Ancak, bu yeni çokyüzlü için uç noktalar vardır, oysa orijinal için hiçbiri yoktur. Başlangıçta, bir LP'nin en uç noktalarının, diğerinin uç noktalarına iki taraflı olarak karşılık geldiğini düşünmüştüm, ancak bu açıkça görülüyor.
Öyleyse, bir LP'nin SEF versiyonunun en uç noktaları tam olarak ne zaman orijinalin uç noktalarına iki taraflı olarak karşılık gelir? Dahası, böyle bir eşleştirme geçerli olmadığında, Simplex algoritmasının orijinal LP açısından ne yaptığını geometrik olarak nasıl yorumlayacağız?
Yanıtlar
Simplex algoritması en uç noktadan en uç noktaya yinelenir
Teknik olarak hayır. Simpleks algoritması kadar yineleme esasına göre esas . Olası temel çözümlerin uç noktalara tekabül ettiği görülüyor. (örneğin, ikili simpleks, primal-fizibil bölgenin en uç noktaları olmayan ikili uygulanabilir temel çözümler aracılığıyla yinelenir).
Yazan standart formdaki bir LP düşünün \begin{align} \min \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & Ax = b\\ &x \geq 0 \end{align}Bu LP'nin uygulanabilir bölgesi her zaman çok yüzlüdür. Uç noktaları yoksa, o zaman ya boştur (ve temel uygulanabilir çözümler yoktur) ya da afin bir alt uzayıdır.$\mathbb{R}^{n}$. Şimdi, ikinci durum, olamaz hiçbir afin alt uzay bir alt kümesi olabilir, çünkü gerçekleşmesi$\mathbb{R}_{+}^{n}$.
Şimdi, asıl sorunuza geri dönersek (bence): orijinal bir çokyüzlü ve bunun için bir SEF temsili verildiğinde, bu temsilin uç noktaları var mı ve bunlar orijinal polihderonun uç noktalarına karşılık geliyor mu? Cevap şu: evet, SEF uç noktalara sahip olacak ve hayır, bunlar her zaman orijinal çokyüzlünüzün uç noktalarına karşılık gelmeyebilir.
İşte basit bir örnek: $\mathcal{P} = \{x \in \mathbb{R}\}$1 boyutlu bir çokyüzlü olan. Formülasyonunun bir serbest değişkeni vardır ve kısıtlama yoktur.
Bir SEF temsili oluşturmak için, $x$ tarafından $x^{+} - x^{-}$ ile $x^{\pm} \geq 0$. Şimdi,$(0, 0)$ bu SEF'in en uç noktasıdır. $x=0$, ki bu aşırı bir nokta değildir $\mathcal{P}$.
Sorunuzu tam olarak anladığımdan emin değilim, ama sanırım kafa karışıklığınız temel bir çözümün "uç nokta" olduğu varsayımından kaynaklanıyor. Temel (ilkel veya ikili uygun olması gerekmez) çözüm, yalnızca satır sayısı kısıtlamalarının (bazıları sınır olabilir) kesişmesidir. Bir problemin birincil veya ikili uygulanabilir bir çözüme sahip olmaması mümkündür, bunun sonucunda ya uygulanabilir değildir ya da sınırsızdır. Ders kitabı simpleks algoritmaları bazen algoritmayı gerçekten başlatmak için bir BFS oluşturmak için bir çeşit aşama 1 yaklaşımının gerekli olduğu gerçeğini atlar. Bir ilk aşama 1'in problemi ilkel olarak gerçekleştirilemez bulması ve aynı zamanda bir ikili aşamanın 1 sorunu sınırsız bulması mümkündür.
Güncelleme: mtanneau'nun cevabı muhtemelen söylenecek her şeyi söylüyor, serbest değişkenli tek bir kısıt için de aynı şey geçerli. Sadece simpleks uygulamalarının doğrudan serbest değişkenlerle çalıştığını ve bunları 0 ile sınırlı iki değişkene dönüştürmediğini eklemek istiyorum. Ancak aynı şekilde, algoritma temel çözümler üzerinde yineleniyor ve temel olmayan serbest değişkenlerin değeri alması kuralına uyuyor 0. Ayrıca sınırlı çokyüzlüler için temel çözümlerin uç noktalara karşılık geldiğine dikkat edin.