解决最小值的不等式

Question

我正在研究一个编程问题,它归结为一组方程和不等式:

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

我想解决的价值X,这将使的绝对最低C,考虑到输入D和列表,并A与B包括a[0 - n]和b[0 - n ].

我目前在Python中正在解决这个问题,但问题一般是与语言无关.

澄清更新:系数x[0 - n]仅限于非负整数集.

Answer 1

这看起来像线性编程问题.在单纯的算法通常给出了良好的效果.它基本上走过由不等式划分的子空间的边界,寻找最优.

从视觉上考虑它:每个不等式表示一个半空间,一个n维空间中的平面,你必须在它的右侧.您的实用程序功能正是您要优化的功能.如果空间是封闭的,最佳位置将是封闭空间的一个顶点; 如果它是开放的,那么最佳可能是无限的.