基可行解個數等於可行域頂點數？

1樓：Dyn98

先將原LP問題化為標準形式，即所有的不等號通過鬆弛變數等形式化為等號後；

不妨假設化成標準形式後一共有5個變數x1,...,x5，兩個約束條件，如下：

3x1+5x2+2x3+x4 = 5

2x1+4x3+x5 = 6

且所有變數均不小於0

5個變數即對應乙個五維的空間（意味著不加約束的情況下[x1,...,x5]可以取遍五維空間內的所有點），加上兩個等號約束條件後，五維空間降為三維（意味著加上兩個約束條件後，[x1,...,x5]只能取五維空間內的乙個三維子空間內的點了）

又因為所有變數都不小於0，因此這個降下來的三維空間是三維座標系的第一卦象，那麼第一卦象的頂點是什麼呢，就是原點[0,0,0]。

然後通過不斷的變換基我們就能得到所有的頂點。

題主說的這個問題，乙個頂點確實可以對應多個基可行解，當我們的可行域本身已經是乙個點的時候（由於xi>=0這些約束的存在），本來應該是多個的基可行解就會被壓縮到這乙個頂點上，比如：

x+y+z=1

z=1x,y,z>=0

這個約束條件對應的可行域應該是一條直線（3個變數，2個約束，維度=3-2=1，是一條直線），本來通過變換基（令x,y分別等於0）我們可以得到2個基可行解，但是由於約束（x,y,z>=0）的存在，事實上這兩個基可行解被壓縮到了乙個點[0,0,1]上，因此乙個頂點可以對應多個基可行解。

2樓：z zhong

乙個頂點有可能對應多個基可行解。舉個二維的例子，三條直線交與一點。兩條直線相交構成乙個基點解，那這個頂點就對應了3個基點解。