정수 조합

Question

다중 변수 형식에 대한 정수 조합을 찾기위한 모듈을 작성하고자합니다. 예 :

8x + 9y <= 124 

모듈은 x 및 y.Eg에 대해 가능한 모든 양의 정수를 반환합니다. x = 2, y = 12이다. 정확히 124 일 필요는 없으며 124보다 작거나 같은 숫자 일 수 있습니다. 정확한 해결책을 찾을 수없는 경우 to124에 가깝도록해야합니다.

나는 변수의 수는 어떤 ... (5,10,100, ..., n은)

모든 알고리즘은이 문제를 해결할 수있을 수 있기 때문에 무력으로 해결하고 싶지 않아?

Answer 1

문제를 정수 프로그래밍 문제로 다시 작성하면 문제를 해결할 수 있습니다.

방정식을 제약 조건으로 다시 작성하십시오. 우리는 느슨한 변수 z을 도입

8x + 9y < = 124

8x + 9y + z = 124

으로 알 수 있습니다. z을 가능한 한 작게하려면 objective function을 Minimize z으로 만듭니다. 모든 솔버는 z를 증가시키기 전에 x 및 y의 가능한 모든 정수 값을 시도합니다.

귀하의 전체 IP는 다음과 같습니다

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

는 상업용 또는 오픈 소스 LP/IP 솔버를 사용하여 해결합니다. 어떤 이유로, 당신은 x 또는 y이 더 크거나 작게하려면,

당신이 더 일반적으로뿐만 아니라 objective function co-efficients.

있는 사람을 제어 할 수 있습니다 (R의 Optim을 패키지는 하나의 가능성은, 엑셀 찾기도. 할 것입니다) , Min Cx x + Cy y + Cz z 및 필요에 맞게 비용 매개 변수 Cx Cy 및 Cz의 가중치를 제어하십시오.

희망이 있습니다.