에 대한 불평등 해결 : 나는 절대 줄 것이다 X의 값을 해결 할내가 방정식과 불평등의 세트로 귀결 프로그래밍 문제에 일하고 있어요 최소값
x[0]*a[0] + x[1]*a[1] + ... x[n]*a[n] >= D
x[0]*b[0] + x[1]*b[1] + ... x[n]*b[n] = C
을 최소 C이고 입력이 D이고 목록이 A이고 B이 a[0 - n] 및 b[0 - n ] 인 경우
저는 현재 파이썬에서이 문제를 다루고 있습니다. 그러나 문제는 일반적으로 언어에 구애받지 않습니다.
CLARIFICATION UPDATE : 계수 x[0 - n]은 음수가 아닌 정수로 제한됩니다.
문제는 linear programming입니다.
이것은 linear programming처럼 보입니다. Simplex algorithm은 일반적으로 좋은 결과를 제공합니다. 기본적으로 불평등으로 구분 된 부분 영역의 경계를 따라 가면서 최적을 찾습니다.
시각적으로 생각해보십시오. 각 부등식은 반 공간, 즉 n 차원 공간에있는 평면을 나타내며 오른쪽에 있어야합니다. 당신의 유틸리티 기능이 당신이 최적화하려고하는 것입니다. 공간이 닫히면 최적 공간은 닫힌 공간의 꼭지점 중 하나에있게됩니다. 그것이 열려 있으면 최적이 무한 할 수도 있습니다.
최소화 기능을 구현하는 방법에 대한 아이디어는 Matlab 또는 Mathematica를 사용하거나 Numerical Recipes in C의 코드를 참조하십시오. 제공된 링크는 1992 년 버전의 책에 제공됩니다. 최신 버전은 Amazon에서 사용할 수 있습니다.
이 company에는 이런 종류의 작업을 수행하는 도구가 있습니다.
선형 프로그래밍에서 wikipedia 항목을 살펴보십시오. 정수 프로그래밍 섹션은 당신이 찾고있는 것입니다 (정수 인 x [i]의 제약은 쉬운 것이 아닙니다).
브랜치 & 바운드, 브랜치 & 잘라 내기 등의 파이썬 라이브러리 검색 (필자는 아직 scipy에서 구현되지 않았다).
흥미로운 링크 :
유무 X [0] ..., X [n]이 제로보다 같거나 커야? –
예, 가능합니다. 명확한 질문 주셔서 감사합니다. – pbh101
흠, 그렇다면 선형 프로그래밍을 고수 할 것입니다 ... –