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

Question

我需要一种自动使线性规划问题可行的算法。具体来说，该算法的输入是一个线性规划问题，可能没有可行的解决方案，而它的输出是一个类似的规划（参数修改为最小值），它必然有可行的解决方案。我是算法的新手，请问是否有针对此类问题的现有研究/工作？任何建议和意见表示赞赏。谢谢，理查德

Answer 1

您可以将松弛变量添加到约束中，然后最小化值的平方和。

Answer 2

Add a set of "artificial variables", one per equation, with unit weight in that equation and zero weight everywhere else. Then, you can choose that set as your first basis, and add "eliminate the artificial variables" as an initial goal. If you can eliminate all the artificial variables, you can discard them, and you will have a feasible basis for your initial problem; if you cannot eliminate the artificial variables, there is no feasible solution.

original problem (in canonical form -- any LP problem can be converted to this!):

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

to find a feasible solution (assuming all b_j>=0; if not, just multiply the row by -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

There are variations and optimizations on this kind of scheme; for instance, you don't necessarily need to convert everything to canonical form to do this kind of thing (though it is useful for simplicity of explanation). You should be able to find more details in any linear programming text.

Note that this is similar to the other answer of "slack variables", except that there is no point in squaring anything (which would make the problem nonlinear, and thus more difficult to solve within a linear programming framework...)