整数组合

Question

我想编写一个模块，找了多变量fomula整数组合。例如

8x + 9y <= 124 

该模块将返回所有可能的正整数为x和y.Eg. x = 2，y = 12。 它不neccessary正好124，可以是任何数量小于或等于124，如果没有准确的可以找到解决办法必须是尽可能接近更多钞票to124。

我不想用蛮力解决为变量的数量可以是任何...（5,10,100，... n）的

任何算法可以解决这个问题？

Answer 1

您可以通过重铸你的问题作为整数规划问题解决此问题。

重写你的公式作为约束。

8x + 9y < = 124作为

8x + 9y + z = 124

注意，我们引入了松弛变量z。我们希望z要尽可能小，这样使objective function是Minimize z任何求解器将尝试增加ž之前x和y的所有可能的整数值。

您的全IP将是：

 
Min z 
8x + 9y + z = 124 
x,y,z >=0 and Integer 

解决使用任何商业或开源的LP/IP求解。 （R的的Optim包是一种可能性，Excel求解也会做。）

如果出于任何原因，你想x或y是更大或更小，可以控制这些以及与objective function co-efficients.

更普遍，Min Cx x + Cy y + Cz z并控制成本参数CxCy和Cz的权重以满足您的需求。

希望有所帮助。