由前面知识可知，前向边流量只能增加，那么边（v,z）就不能是饱和边。
（2）如果边（v,z）为后向边，则必有f（v,z）>0。
由前面知识可知，后向边流量只能减少，那么边（v,z）就不能是零边。
第三步：
若边（v,z）能够成为增流链的边，就使顶点z成为被标号的点，再对被标号点z按照第一步的标号方式进行标号。
第四步：
返回第二步，不断循环，直至不能找到被标号点，则反向追踪找出不饱和链。
20. 用标号法求图所示的网络中从vs到vt的最大流。
参考答案：
（1）Valf=5
（2）Valf=7
21. 简述分枝定界法的主要步骤
参考答案：
第一步：
先不考虑整数约束条件，对一般情况的线性规划问题用单纯形法或对偶单纯形法求解。
如果求出的最优解满足整数规划问题的所有整数约束条件，那么这个最优解也就是整数规划问题的最优解，如果有一个或多个整数约束条件没有被满足，转到第二步。
第二步：
任意选择一个应该是整数而不是整数解的变量xk，设它的非整数解是bk，同时设bk对应的整数位是[bk]，现在将原问题分成两枝，一枝是在原问题的基础上，增加约束条件xk≤[bk]；另一枝是在原问题的基础上，增加约束条件xk≥[bk]+1，这样就构成了两个新的线性规划问题的子问题。
第三步：
按照第3.3节对偶单纯形法扩展应用的思路，分别对分枝后的两个新线性规划子问题继续求解。
若新的解不满足原问题整数约束，再按第二步进行新的分枝，直到满足下面的情况停止分枝：
22. 已知某整数规划不考虑整数约束时最优单纯型表，写出一个割平面方程。
参考答案：
-1/7x3 –2/7x5 +x6 =-6/7；
23. 求解下列0-1规划问题的解。
（1） minZ=8x1 +2x2 +4x3 +7x4 +5x5
参考答案：
（1）（x1 ，x2 ，x3 ，x4 ，x5）=（0，1，1，0，0），Z=6
（2）（x1 ，x2 ，x3 ，x4 ，x5）=（1，1，0，0，0），Z=5
（3）（x1 ，x2 ，x3 ，x4 ，x5）=（0，0，1，1，1），Z=6
24. 简述运输方案的调整过程。
参考答案：
第一步：
确定换入变量
同单纯形法一样，在所有的负检验数中，一般选取检验数最小的非基变量作为换入变量。
第二步：
确定换出变量和调整量
由定理5.4可知，由此时还是非基变量的换入变量和一组基变量可以组成一个唯一的闭回路，找到这个闭回路以后，以此非基变量为起点，取此闭回路中偶数顶点取值最小的基变量做为换出变量，调整量的量值即为此基变量的值。
第三步：
调整方法
（1）闭回路以外的变量取值均保持不变。
（2）针对闭回路，奇数顶点变量的值全部加上调整量，偶数顶点变量的值全部减去调整量。
第四步：
标识方法
为了保证基变量的个数为m+n-1个，在标识上作如下处理：
（1）调整后，原来作为非基变量的换入变量就变成了基变量，所以要把这个变量的值标识成“○”。
（2）调整后，原来作为基变量的换出变量就变成了非基变量，所以要在这个变量的位置打上“×”。
第五步：
继续求检验数，如果存在负的检验数，就返回第一步，否则计算停止，说明找到了最优解。
管理运筹学B第3次作业
（注意：
若有主观题目，请按照题目，离线完成，完成后纸质上交学习中心，记录成绩。
在线只需提交客观题答案。
）
本次作业是本门课程本学期的第3次作业，注释如下：
二、判断题（判断正误，共11道小题）
1. 一般情况下，松弛变量和多余变量的目标函数系数为零。
正确答案：
说法正确
解答参考：
2. 用单纯形法求解标准型线性规划问题时，与检验数大于0相对应的变量都可被选作换入变量。
正确答案：
说法正确
解答参考：
3. 由应用问题建立的线性规划模型中，其约束方程有多种形式
正确答案：
说法正确
解答参考：
4. yi为对偶问题的最优解，若yi>0，说明在最优生产计划中第i种资源已完全耗尽。
正确答案：
说法正确
解答参考：
5. 当所有产量和销量均为整数值时，运输问题的最优解也为整数解。
正确答案：
说法错误
解答参考：
6. 整数规划问题的可行解与其线性规划问题的可行域内的整数点相对应。
正确答案：
说法正确
解答参考：
7.
判断正误
任一图G中，当点集确定之后，树图是G中边数最少的连通图。
正确答案：
说法正确
解答参考：
8. 在有向图中，如图所示
中的边e和eˊ是平行边
正确答案：
说法错误
解答参考：
9. 若Q为f饱和链，则链中至少有一前向边条边为f饱和边，同时至少有一条边后向为f零边。
正确答案：
说法错误
解答参考：
10. 既要满足流值最大又要满足费用最小的流是不存在的。
正确答案：
说法错误
解答参考：
11. 标号法每迭代一步，没有取得永久性标号顶点的标号都会被改变一次。
正确答案：
说法正确
解答参考：
（注意：
若有主观题目，请按照题目，离线完成，完成后纸质上交学习中心，记录成绩。
在线只需提交客观题答案。
）
三、主观题（共9道小题）
12. 求下列图中的指定顶点
（1）到（5）的最短距离和路（径）。
参考答案：
（1）路线：
（1）—（4）—（3）—（5）
（2）路径：
（1）→（3）→
（2）→（4）→（5）
13. 简述在求最小费用流的过程中，寻找由到源到汇的不饱和链的方法
参考答案：
第一步：
如果运输网络G的流值没有达到A，先用最大流算法把流值调到A；如果运输网络G的流值达到A，则不对网络流调整。
第二步：
针对流值为A的运输网络G，构建伴随网络流f的增流网络Gf 。
第三步：
针对增流网络Gf，查看是否存在基于w′的负回路，如果不存在负回路，说明当前的网络流已经是最小费用流，算法终止，否则转到下一步。
第四步：
针对存在的负回路C，令δ=min{c′（e）,e为Gf中负回路的边}。
第五步：
针对负回路C对应运输网络G中的圈，判断该圈是否为增流圈，如果不是增流圈，转到第三步继续寻找负回路，否则转到下一步。
第六步：
针对运输网络G中的增流圈，按照定理9.5，把增流圈中方向与负回路方向一致的所有不饱和边的流量加上δ；把增流圈中方向与负回路方向相反的所有正边的流量减去δ。
第七步：
继续寻找负回路，如果有负回路，继续调整，否则返回第二步。
14. 根据对偶规则填表：
参考答案：
15. 简述如何在单纯型表上判别问题是否具有唯一解、无穷多解、无界解或无可行解
参考答案：
将检验数cj-zj作为判断基本可行解是否为最优解的标准，判断的方法如下：
（1）若所有非基变量的检验数cj-zj<0，已经达到最优解；
（2）若存在cj-zj>0，但所有cj-zj>0所在列对应的所有aij≤0，无界解；
（3）从几何意义的角度就是说，约束条件方程组没有可行域，则线性规划问题五可行解；
（4）在最优单纯形表中，如果出现检验数等于0的个数多于基变量的个数，线性规划模型就有多重解。
16. 简述若标准型变为求目标函数最小，则用单纯形法计算时，如何判别问题已取得最优解。
参考答案：
对目标函数为极小化线性规划问题时，则用单纯形法计算时，当所有非基变量的检验数大于或等于零时，已经达到最优解；
17. 建立下列问题的线性规划模型并化为标准型
某工厂生产A1、A2两种产品，有关的信息由下表给出，建立制定最优生产计划的模型（利润最大）。
参考答案：
提示：
设产品A1、A2的产量分别为x1、x2个单位，maxZ=70x1+120x2
18. 某工厂生产A、B两种产品，已知生产A每公斤要用煤9吨、电4度、劳动力3个；生产B每公斤要用煤4吨、电5度、劳动力10个。
又知每公斤A、B的利润分别为7万元和12万元。
现在该工厂只有煤360吨、电200度、劳动力300个。
问在这种情况下，各生产A、B多少公斤，才能获最大利润，请建立模型。
参考答案：
提示：
设A、B各生产x1、x2公斤，maxZ=7x1+12x2
19. 目标函数中人工变量前面的系数±M（M是充分大的正数）的作用是 。
参考答案：
使人工变量不可能进入最优解
20. 解包含人工变量线性规划问题的单纯形法有 有
参考答案：
大M法、两阶段法
管理运筹学B第4次作业
（注意：
若有主观题目，请按照题目，离线完成，完成后纸质上交学习中心，记录成绩。
在线只需提交客观题答案。
）
本次作业是本门课程本学期的第4次作业，注释如下：
（注意：
若有主观题目，请按照题目，离线完成，完成后纸质上交学习中心，记录成绩。
在线只需提交客观题答案。
）
三、主观题（共4道小题）
1. 找出下列线性规划问题的一组可行解和基本可行解。
参考答案：
提示：
可行解是满足约束条件的解，基本可行解是与基列（线性无关）对应的可行解。
2. 目标函数为maxZ=28x4+x5+2x6，约束形式为“≤”，且x1，x2，x3为松弛变量，表中的解代入目标函数中得Z=14，求出a~g的值，并判断是否最优解。
参考答案：
a=7，b=-6，c=0，d=1，e=0，f=1/3， g=0；最优解
3. 用单纯形法求解下列线性规划。
参考答案：
（1）X=（12/7，15/7），Z=-120/7；
（2）X=（5/6，0，17/5，0，0），Z=81/5；
（3）X=（2，6），Z=36； （3）X=（-3，0），Z=-9
4. 某工厂生产A、B两种产品，每公斤的产值分别为600元和400元。
又知每生产1公斤A需要电2度、煤4吨；生产1公斤B需要电3度、煤2吨，该厂的电力供应不超过100度，煤最多只有120吨，问如何生产以取得最大产值？
建立模型，用图解法求解。
参考答案：
提示：
设A、B各生产x1、x2公斤，maxZ=600x1+400x2，
（x1、x2）=（20，20），产值最大为20000元。
升级会员 