使用線性編程查找「最佳擬合線」

這是一個作業問題。我被要求找到最適合一組給定的n個點（2D）的線的係數。係數爲abc in：ax + by = c。假設有n個點，用線性規劃尋找導致最小「最大絕對誤差」的係數，定義爲：max（| a * xi + b * yi -c |），i的範圍從1-n。使用線性編程查找「最佳擬合線」

這裏是我的思維過程：

令M表示最大絕對誤差。線性規劃的目標是使M最小化。由於M是所有| a * xi + b * yi-c |中最大的，它必須比它們中的每一個都大。對於所有的i（第二個表達式是爲了說明絕對符號），所以（a * xi + b * yi-c）< = M，並且（a * xi + b * yi-c）> = -M。

我認爲這足以定義問題。當我把條件放入求解器時，它返回一個等於0的bc，但實際上它不應該。我想我在這裏錯過了一些條件。有人可以指出我嗎？

來源

2013-04-09 turtlesoup

您應該添加一個額外的語句：a或b不應該爲0.如果這兩個值均爲0，那麼您的系統有一個有效的解決方案，但不存在a和b都等於0的線。

編輯：改善Rerito的建議。任何行都有a或b不等於0.行(k*a)*x + (k*b)* y + (k*c)和(a)*x + (b)* y + (c)對於任何非零k都是相同的。所以我會說你需要運行求解器兩次 - 一旦指定a是1，並且一旦指定b是1並且在選擇更好的解決方案之後。您必須運行求解器兩次，因爲最好的解決方案可能是a=0或b=0（但不是兩者）。

來源

2013-04-09 08:26:58

有趣的是，求解器仍然給我所有的0作爲結果。我認爲添加a或b！= 0的條件只會迫使解算器無限接近0，即0 = \ – turtlesoup 2013-04-09 08:42:20

@ user1926344由於pax + pby = pc定義了與ax + by = c'（用'p！= 0'），給你的求解器指定'a = 1或b = 1' :) – Rerito 2013-04-09 08:58:43

@Rerito你將不得不運行求解器兩次以避免錯過最佳解決方案。我爲我的回答添加了一個編輯。感謝您的評論。 – 2013-04-09 09:01:30

使用線性編程查找「最佳擬合線」

回答

相關問題