可以将线性规划问题转化为可行方法的算法

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约束，然后最小化值的平方和。