算法 - 最小化公式

如果我們給出一個方程，比如說3x + 2y < = 10，我們希望找到x和y的值，使得 x + y =最大值和10-3x-2y最小化。如何才能做到這一點？我正在將其視爲動態編程問題！但不知道我是否正確。算法 - 最小化公式

在上面的x = 0和y = 5將是答案。

謝謝。

來源

2012-09-08 VVV

嘗試實施拉格朗日乘數。 – swiecki

我假設x，y> = 0？ – cheeken

是的x和y總是大於0. – VVV

關於這個問題有一個巨大的數學文獻。如果方程都是線性的，那麼答案（如果存在唯一的答案）必須位於由約束描述的多面體的頂點上。查找linear programming. Simplex算法是沿着多面體的邊搜索以找到滿足最小化的頂點的經典方法。

來源

2012-09-08 01:59:20 Gene

Thanke基因！然而，答案總是存在的，因爲我們正在努力將10 - 3x - 2y最小化！ 10 - 3x - 2y不需要是0.單純形算法仍然有效嗎？ – VVV

我很遺憾，我不明白你寫的是什麼。任何可以制定爲線性程序的問題都可以通過單純形算法來解決。（在退化情況下，Simplex可能需要指數時間，Karmarkar的算法總是多項式的，但實現比較棘手，對於小問題，它通常比Simplex慢） – Gene

噢，我想我現在明白了。你的問題是相當無意義的，因爲它是過度約束。如果你有一個半空間和一個單一的最小化或最大化目標，那麼就有一個唯一的答案。你提出2個目標。他們碰巧有相同的解決方案。但幾乎所有這類問題都會有不同的問題。如果你一般需要解決這個問題，你必須找到一個單一的目標，例如兩個（或更多）的加權和。在這種情況下，一個例子就是'x + y - 10 + 3x + 2y = 4x + 3y 10' – Gene

算法 - 最小化公式

回答

相關問題