《运筹学》习题(二)

班级 姓名 一、 判断题

1、 无约束的变量xj，通常令xjxjxj，其中xj0,xj0，在用单纯形法求得的最优解中有可能同时出现xj0,xj0。

2、用单纯形法求解标准形的线性规划问题时，与j0对应的变量都可以被选作换入变量。 3、单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负。

4、单纯形法计算中，选取最大正检验数k对应的变量xk作为换入变量，将使目标函数值得到最快的增长。 答：

二、 单纯形法迭代中，任何从基变量中替换出来的变量，在紧接着的下一次迭代中，会不会再进入基变量中？为什么？

答：

三、 下表为用单纯形法计算时某一步的表格，已知该线性规划问题中目标函数为

max z5x13x2，约束条件均用“≤”关系连接，x3, x4为松弛变量，该表中解代入目标函数可得z =10。求a---g的值；问此表所给的解是否为最优解。

x1 x2 0 e 1 x3 1 0 f x4 0.2 1 g x3 x1

答：

2 a c d b cjzj

四、 X0是线性规划问题

max zCXAXb X0的最优解。以上问题中若目标函数中的C换成C*后，则问题的最优解变为X*。

求证： (C* C)(X* X0)≥0 证明：

五、 用单纯形法求解下述问题： max S=x1+x2

2x1+x2≤8 2x1+5x2≤20 x1+x2≤5 x1, x2≥0

解：加入松弛变量，用单纯形法解得如下：

Cj→ CB 0 0 0 1 0 0 1 0 1 XB X3 X4 X5 S X1 X4 X5 S X1 X4 X2 S b 8 20 5 0 4 12 1 3 4 2 1 X1 2* 2 1 1 1 0 0 0 1 0 0 0 1 X2 1 5 1 1 1/2 4 1/2* 1/2 0 0 1 0 0 X3 1 0 0 0 1/2 1 0 X4 0 1 0 0 0 1 0 0 0 1 0 0 0 X5 0 0 1 0 0 0 1 0 -1 -8 2 -1 θ ←λ ←λ ←λj j ji

六、 试利用两阶段法第一阶段的求解，找出下述方程组的一个可行解，并利用计算得到的最终单纯形表说明该方程组有多余方程。

 x12x2x32x3xx1123 2x13x24x37x1,x2,x30解：

附 《运筹学》习题（一）的答案

一、答案：（1）（2）（4）（5）为正确;（3）（6）错。

二、解：线性规划问题也可以看成是条件极值问题，即要在满足所有约束的条件下，求目标函数的

极值。它与微积分中讲到的条件极值是不同的：

（1）它的约束条件中可以有不等式约束而后者的限制条件都是等式； （2）它的约束条件的个数一般地都多于变量的个数，而后者恰恰相反； （3）它的目标函数与约束条件都是线性的，而后者不必如此。

三、解：线性规划的数学模型含有变量、目标函数和约束条件三个部分。变量必须是连续的，目标函数是对变量的线性函数，约束条件是对变量的线性等式或不等式。所以，（1）（3）（4）是线性规划模型，（2）不是，因目标函数非线性。

x1,x3x3x3，化为标准形为 四、答案： （1）、令x1x22x32x3Mx40x5max z2x1x2x3x3x4 4x1 x2x3x3 x56x1x,x,x,x,x,x 0 123345x2,x4x4x4，化为标准形为 （2）、令x23x3x4x40x5Mx60x7Mx8max z2x1x2 x3 x4 x4x5 7 x1 x22x3x5x x6 8123 2x4 2x32x4 x7x81 x1  xj0 j1,2,,8

五、答案：可行解有（a）（c）（e）（f），基本解有（a）（b）（f），基本可行解有（a）（f）。

六、答案：（1）是凸集，（2）不是。 七、解：该问题的可行域如图1所示。我们以下面四种情形分别进行讨论：

1、c = d =0时，显然，此时点O, A, B, C都是最优解（此时任何可行解都是最优解）。 2、（1）c =0 , d >0时，目标函数等值线为x2函数等值线为x2z，显然，点C为最优解。（2）c = 0, d < 0时，目标dz，显然，点O, A为最优解。 d3、（1）c > 0, d =0时，目标函数等值线为x1函数等值线为x1z，显然，点A为最优解。（2）c < 0, d =0时，目标cz，显然，点O, C为最优解。 cczc5c54、（1）c >0, d >0时，目标函数等值线为x2x1。易知时，点A为最优解；ddd2d23c5c3c3时，点A, B为最优解；时，点B为最优解；时，点B, C为最优解；时，

4d2d4d4cz点C为最优解。（2）c > 0, d < 0时，目标函数等值线为x2x1，点A为最优解。（3）c < 0,

ddczczd < 0时，x2x1，点O为最优解。（4）c < 0, d > 0时，x2x1，点C为最优解。

dddd八、1、解：设x1—每日生产零件甲的数量 ，x2—每日生产零件乙的数量 。 钻床的工时

约束为：3x1+5x2≤8×60 = 480，每台铣床上的时间约束为：(20x1 +15x2)÷5≤480， 即 4 x1+3x2≤480。每天不同机床运行时间之差可表示为：|(3x1+5x2)  (4x1+3x2)| = | x12x2| ，因此均衡生产的要求是：|x1 2x2|≤30 将非线性约束替换为两个线性约束得：x12x2≤30 x1+2x2≤30 配套的组数取决于这两种零件中较小的数量，因此目标函数为min{x1 ,x2}。这一非线性函数可化为线性的，即设x3 = min { x1 ,x2}得x1≥x3 , x2≥ x3 ，这样目标就是使z = x3最大。

最后得线性规划模型为：max z = x3

3x1+5x2≤480 4x1+3 x2≤480 x12 x2≤30  x1+2x2≤30 x1≥x3 x2≥x3 x1, x2, x3≥0.

2、设安排在第j班次开始上班的司乘人员数为xj。假定该公交线路已经运营,由于各个司乘人员必须连续工作8个小时才能下班，所以正在第一班次的时间上班人数x1应不少于60；同理，正在第二至第六班次上班人数x2, x3, x4, x5, x6分别不少于70，60，50，20，30。综合以上的分析得线性规划模型： min z = x1 + x2+ x3+ x4+ x5+ x6

x 1 + x 6 ≥60 x 1 + x 2 ≥70 x 2 + x 3 ≥60 x 3 + x 4 ≥50 x 4 + x 5 ≥20 x 5 + x 6 ≥30

x1，x2，x3，x 4，x 5，x 6≥0.