整數組合

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的權重以滿足您的需求。

希望有所幫助。