在相等性約束

我曾問一個問題，它可以在這裏找到的情況下求解線性規劃：

在相等性約束

，並已提出線性規劃。我查閱了線性編程和Simplex方法。但是我所遇到的所有例子都有不等式約束，這些約束使用鬆弛變量轉換爲平等。單純形法然後交換基本變量和非基本變量以獲得最佳解決方案。

但我的問題是：

減少：
X1 + X2 + ... + XN

受：
A1 * X1 + A1 * X2 + a1 * x3 + ... + a1 * xn = c1;
a2 * x1 + a2 * x2 + a2 * x3 + ... + a2 * xn = c2;
a3 * x1 + a3 * x2 + a3 * x3 + ... + a3 * xn = c3;

現在我不知道如何應用單工方法，因爲我沒有任何基本的變量。
另外我不能只求解線性方程，因爲我有n個變量和3個方程。
有人可以告訴我一個出路嗎？

來源

2013-06-25 user1925405

投票結束。這不是一個「編程問題」，因爲該術語通常用於SO。這是一個關於單純形法在線性規劃中的應用的問題。 –

這是一個編程問題。請參閱問題中的鏈接。我對這個建議的方法感到困惑，所以我想我會在這裏提出這個問題，這樣人們可能會提出一種替代編程技術，如果線性編程不應該工作的話。 – user1925405

您可以改寫每個方程分爲兩個不等式：

a1*x1 + a1*x1 + a1*x3 + … + a1*xn ≤ c1 
a1*x1 + a1*x1 + a1*x3 + … + a1*xn ≥ c1

這假定標a1係數實際上是不同的;否則你的整個LP將是高度相互依賴的，要麼解決或根本無法解決。接下來您可以添加鬆弛變量再次開啓不平等到平等：

a1*x1 + a1*x1 + a1*x3 + … + a1*xn + y1a = c1 y1a ≥ 0 
a1*x1 + a1*x1 + a1*x3 + … + a1*xn - y1b = c1 y1b ≥ 0

現在這些Y1A和Y1B是你最初的基本變量，你就可以開始旋轉。如果最初的基本解決方案已經可行，或者找到一個最佳的解決方案，或者如果沒有找到一個可行的解決方案。

來源

2013-06-25 05:05:43 MvG

謝謝！你能解釋一下最小化到最大化的轉化嗎？我認爲你只是否定了目標函數中的變量。即上述功能應該最大化：-x1 -x2 -x3 ... -xn。對？如果是的話，現在單純如何進行？它必須選擇一個非基本變量，目標函數中的係數是正數，對嗎？ – user1925405

或者你也許使用了二元性。但我一直無法理解這一點。你能否解釋一下，如果這適用？ – user1925405

@ user1925405：簡單方法的逐步介紹將超出SO回答的範圍，即imo。如果在線可用資源不足，我建議您獲取Cormen等人的「算法簡介」一書的副本。據我記得，那裏的簡單描述是可以理解的。簡短的回答，雖然：在最大化和最小化意味着否定目標函數，權利之間切換。如果有一個你不明白的單純形法的特定步驟，用明確的（並且最好簡單的）數字發佈一個新問題可能會有所幫助。 – MvG

你不必自己動手，這就是建模語言存在的原因。我建議你試試GLPK或SCIP。

他們有自己的建模語言，GLPK有GNU MathProg，SCIP有ZIMPL，所以你可以方便地編寫你的LP問題。 閱讀文檔。

有關的問題是this。

來源

2013-06-25 08:12:06 Ali

在教科書

「組合優化」的肯內特·施泰格茨和克里斯托Papadimitiou

你可以找到單純形算法的詳細的，自包含的說明。如果我沒有記錯，對於只給出等式約束但沒有基礎的情況，則引入具有額外的成本爲零的人爲變量的人工基礎。直觀地說，這就像在約束矩陣的一邊「粘合」單位矩陣。然後，單純形算法開始「推出」人造基礎，即迭代直到人造變量都不再包含在基礎內，這意味着找到原始公式的基礎。

來源

2013-06-26 13:28:08 anonymous

線性編程可以解決這個問題。不要描述了使用兩個不等式的約束，只是將其饋送給像GLPK這樣的求解器。例如，你可以在GMPL幾行寫：

param k, n; 
param a{1..k}{1..n}; 
param c{1..k}; 
var x{1..n}, >= 0; 

minimize cost : sum{i in 1..n} x[i]; 
s.t. constraints{j in 1..k} : sum{i in 1..n}(a[j][i] * x[i]) = c[j];

正如你在這裏說了，不過，你的模型可能有沒有最佳：沒有非負約束，它只是一個欠定線性系統，無限的解決方案。我假設x必須保持非負數，並且約束條件稍微複雜一些，就像在你的鏈接文章中一樣。

來源

2014-11-11 17:16:28

在相等性約束

回答

相關問題