通過單純形法獲取對象的頂點

我想找到一個由某些方程確定的對象的頂點。例如，。通過單純形法獲取對象的頂點

Eq1: 2x + y + z <= 12; 
Eq2: x + y  >= 23; 
Eq3: x + y + z <= 10;

而且它是由

x >= 0 
y >= 0 
z => 0

有限的，它給出了一個六面體。我想知道這個對象是從哪個頂點創建的。

做到這一點的唯一方法是製作一個代碼來檢查這個方程式的所有可能的變化嗎？

array = array with this equations (6 elements) 

for(i = 1; i <= array.lenght; i++){ 
for(j = 1; j <= array.lenght; j++){ 
    for(k = 1; k <= array.lenght; k++){ 
    //and there check is solve of a variation is possible 
    } 
}  
}

來源

2016-03-13 Pavvi

由於這些是6架飛機，所以它們中的任何2架都將成爲一條直線。那麼，「頂點」是什麼意思？ – NonlinearFruit

當你說「檢查所有可能變化的代碼」時，你的意思是它是否計算出是否存在對所有可能的x，y和z y值進行迭代的解決方案？如果是這樣的話，對於x，y和z的小範圍來說這是可能的（假設它們被約束爲> = 0並且所有方程式都只添加），但是如果您想在解決方案中考慮實數，則這是不可能的。 –

@NonlinearFruit - 頂點是三個平面相交的點。六面體（例如，立方體）具有八個頂點。 –

這就是所謂的vertex enumeration problem：給多面體從半空間表示轉換（這是你必須—一組不等式）的頂點表示。在一般情況下，文獻中有許多算法可以有效地完成這項工作。如果你需要儘可能高效，你應該看看其中的一種算法。

但是隻有六個半空間已知形成一個有界的非退化六面體，蠻力可能就好了。每個頂點都位於三個面的交點處。因此，取三個不等式的每個子集並計算相應方程的交點。如果交點不存在（例如兩個平面平行）或交點不能滿足其他三個不等式中的任何一個，那麼這三個方面不會滿足頂點;否則該點是其中一個頂點。重複每個 C = 20種組合，最終應該有8個頂點。

要計算三個不等式的交點，可以使用一些簡單的線性代數。採取任意三個不等式，例如：

2x + y + z <= 12 
x + y  >= 23 
x   >= 0

它們寫爲矩陣方程：（該矩陣的行是x在每個不等式的係數，y，和z）

┌    ┐┌ ┐ ┌ ┐ 
│ 2 1 1 ││ x │ │ 12 │ 
│    ││ │ │ │ 
│ 1 1 0 ││ y │ = │ 23 │ 
│    ││ │ │ │ 
│ 1 0 0 ││ z │ │ 0 │ 
└    ┘└ ┘ └ ┘

如果矩陣在左邊是單數的（即行列式爲零），沒有共同的交點。否則，通過反轉矩陣計算的解決方案：

┌ ┐ ┌    ┐-1┌ ┐ 
│ x │ │ 2 1 1 │ │ 12 │ 
│ │ │    │ │ │ 
│ y │ = │ 1 1 0 │ │ 23 │ 
│ │ │    │ │ │ 
│ z │ │ 1 0 0 │ │ 0 │ 
└ ┘ └    ┘ └ ┘

任何線性代數庫應該能夠爲你做這個計算，或—因爲這是3D —可以使用Cramer's Rule。然後檢查[x y z]對其他三個不等式以確定它是否是頂點。

來源

2016-03-14 03:54:42

通過單純形法獲取對象的頂點

回答

相關問題