algorithm - LP 可行域

Question

大家好，我有一个关于线性规划的问题。

画出下列线性规划的可行域:

分钟

 sx + ty

st.

 2x +  y <= 7
-6x + 5y >= -5
 -x + 4y <= 18
       y <= 4

(该问题不应改为可行性问题，即不允许s=t=0。)

到目前为止我所做的是计算它们的极值点:

1. (0,4)
2. (1.5, 4)
3. (2.5, 2)
4. (0.83, 0)
5. (0, 0)

给出线性程序具有的 s 和 t 的适当值

1. 只有一个解决方案

   当我选择 s = t = 1 时，我明白如果我有一个解决方案

2. 多个最佳解决方案，其中每个解决方案都是有界的(即，其分量均不具有任意大的数量级)。

   ?

3. 多个最优解，无界

   我的猜测是 s = 1 和 t = 0，这些是点 (0, 4) 和 (0, 0)和它们之间的整条线，上面有无限多的点那条线

4. 没有最优解

   ?

Answer 1

我认为可行域应该进一步延伸到 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 时达到最小值，因此没有最小值。