一、简答题（每小题3分,共21分）1.线性规划问题在何条件下无解?2.整数规划问题有否无穷多组最优解?3.动态规划问题一定会有解吗?它是否会有多组最优解?4.一个线性规划问题若无可行解,则

Question

一、简答题（每小题3分,共21分）
1.线性规划问题在何条件下无解?
2.整数规划问题有否无穷多组最优解?
3.动态规划问题一定会有解吗?它是否会有多组最优解?
4.一个线性规划问题若无可行解,则其对偶问题的解的情况如何?
5.图论中的欧拉图一定是哈米尔图吗?哈米尔顿图一守是欧拉图吗?
6.一个网络最大流问题在何条件下存在“增广链”?
7.若一个整数线性规划问题的松驰问题的最优表中有如下的情况
XB b X1 X2 X3 X4
X2 10 3/7 -8 5/6 1 0 7 3/8
则请写出其相应的割平面方程,并指出下一步该如何求解?

Answer 1

1.当所有非基变量检验数都小于或等于零且基变量中有非零的人工变量时,线性规划问题无解,其根源是存在互相矛盾的约束条件.
2.整数规划问题可以有多组最优解,但没有无穷多组最优解.
3.不敢确定.
4.线性规划问题无可行解,其对偶问题有无界解.
5.欧拉图不一定是哈密尔顿图,但哈密尔顿图一定是欧拉图.
6.每条前向弧都是非饱和弧,每条后向弧都是非零流弧,就存在增广链.
7.我们没有学割平面法.