大家好,我有一个关于线性规划的问题。
画出下列线性规划的可行域:
分钟
sx + ty
st.
2x + y <= 7
-6x + 5y >= -5
-x + 4y <= 18
y <= 4
(该问题不应改为可行性问题,即不允许s=t=0。)
到目前为止我所做的是计算它们的极值点:
- (0,4)
- (1.5, 4)
- (2.5, 2)
- (0.83, 0)
- (0, 0)
只有一个解决方案
当我选择 s = t = 1 时,我明白如果我有一个解决方案
多个最佳解决方案,其中每个解决方案都是有界的(即,其分量均不具有任意大的数量级)。
?
多个最优解,无界
我的猜测是 s = 1 和 t = 0,这些是点 (0, 4) 和 (0, 0) 和它们之间的整条线,上面有无限多的点 那条线
没有最优解
?
最佳答案
我认为可行域应该进一步延伸到 x 轴和 y 轴之外的左下角,因为您没有 x>0 或 y>0 形式的约束。
1) 参见 4),可能更好的是 s=t=-1
2) 例如,s=-2,t=-1,则 2. 和 3. 之间的每个点都具有相同的最小值。所以解决方案受点 2. 和 3 的限制。另外,您提到的 s=1 ant t=0 是有界解决方案。
3) 例如,s=1, t=-4,则函数 -x + 4y = 18(对于 y <= 4)上的每个点都是最小值的一部分
4) 我不确定这个,但可能 s=t=1,然后当 x=y = -\infinity 时达到最小值,因此没有最小值。
关于algorithm - LP 可行域,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47752172/