可以將線性規劃問題轉化爲可行方法的算法

Question

我需要一種自動使線性規劃問題可行的算法。具體地說，該算法是這樣的：其輸入是線性規劃問題，其可能不具有可行解，並且其輸出是類似的編程（具有用最小值修改的參數），這必然具有可行解。我是算法中的新手，並詢問是否有任何針對此類問題的研究/工作？任何建議和意見，表示讚賞。 謝謝， 理查德

Answer 1

添加一組「人工變量」，每個方程一個，其中單位重量在該方程中，其他地方爲零重量。然後，您可以選擇該設置作爲您的第一個基礎，並添加「消除人爲變量」作爲初始目標。如果你能消除所有的人爲變量，你可以丟棄它們，並且你將有一個可行的基礎來解決你最初的問題。如果不能消除人爲變量，就沒有可行的解決方案。

原來的問題（在規範形式 - 任何LP問題可以轉換爲這個！）：

minimize c.x, given: [A]x = b, x_i>=0 
    (but first, need feasible solution) 

找到一個可行的解決方案（假設所有b_j>=0;如果沒有，只是-1乘以行） ：

minimize sum(y), given: y + [A]x = b, x_i>=0, y_j>=0 
    with initial, feasible solution: x_i=0, y_j=b_j 

這種方案有變化和優化;例如，你不一定需要將所有東西都轉換成規範形式來做這種事情（儘管它對簡單的解釋很有用）。您應該能夠在任何線性編程文本中找到更多細節。

請注意，這與「鬆弛變量」的其他答案類似，不同之處在於沒有必要將任何東西平方（這會使問題非線性，因而在線性編程框架內更難以求解）。 ）

Answer 2

您可以只添加slack variables約束，然後最小化值的平方和。