管理运筹学基础作业
- 格式：docx
- 大小：50.68 KB
- 文档页数：14
24. 简述运输方案的调整过程。 参考答案：
第一步：确定换入变量 同单纯形法一样，在所有的负检验数中，一般选取检验数最小的非基变 量作为换入变量。
第二步：确定换出变量和调整量 由定理 5.4 可知，由此时还是非基变量的换入变量和一组基变量可以组 成一个唯一的闭回路，找到这个闭回路以后，以此非基变量为起点，取
（2）两个终点。
（3）两个始点，两个终点。
（4）工序循环不是统筹图。
19. 简述在求最大流过程中，寻找由到源到汇的不饱和链的方法。
参考答案：
标号法寻找增流链的步骤： 第一步：对未检查的边(u,v)的顶点 v 进行标号，标号的方式为(u,边的方向,
l(v))，其中标号的各个部分按照如下确定：
（1）u：表示被标号点 v 的前一个顶点。 （2）边的方向：当被标号点 v 为终点时，即边(u,v)为前向边时，用
（1）
min Z = 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
-4/9 x1 –1/9 x5 –4/9 x6 +x7 = 2/3 ； 17. 简述西北角法、最小元素法、差值法确定运输问题初始基本可行解的过程并指出那种方法得出的解较 优。
参考答案：西北角法：按照地图中的上北下南，左西右东的判断，对调运表中的最 西北角上的空格优先满足最大供应，之后划去一行或一列，重复这种做法，直至 得到初始可行解。最小元素法：对调运表中的最小运价对应的空格优先没醉最大 供应，之后划去一行或一列，重复这种做法，直至得到初始可行解。差值法：在 运价表中，计算各行和各列的最小运价和次最小运价之差，选出最大者，它所在 某行或某列中的最小运价对应的空格优先满足最大供应，重复这种做法，直至得 到初始可行解。一般来讲，用差值法求出的初始可行解最接近最优解，也就是最优的。
本次作业是本门课程本学期的第 1 次作业，注释如下：
一、判断题(判断正误，共 14 道小题)
1. 判断正误 线性规划问题的一般模型中不能出现等式约束。 你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 2. 在线性规划模型的标准型中,bj（j=1，2，…m）一定是非负的。 你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 3. 判断正误 线性规划问题的基本解一定是基本可行解 你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 4. 线性规划问题的最优解只能在可行域的顶点上达到。 你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 5.
21. 简述分枝定界法的主要步骤
参考答案：
第一步：先不考虑整数约束条件，对一般情况的线性规划问题用单纯形法或 对偶单纯形法求解。如果求出的最优解满足整数规划问题的所有整 数约束条件，那么这个最优解也就是整数规划问题的最优解，如果 有一个或多个整数约束条件没有被满足，转到第二步。
第二步：任意选择一个应该是整数而不是整数解的变量 xk，设它的非整数解 是 bk，同时设 bk 对应的整数位是[bk]，现在将原问题分成两枝，一 枝是在原问题的基础上，增加约束条件 xk≤[bk]；另一枝是在原问 题的基础上，增加约束条件 xk≥[bk]+1，这样就构成了两个新的线 性规划问题的子问题。
判断正误
整数规划解的目标函数值一般优于其相应的线性规划问题的目标函数值。
你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 11. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。 你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 12. 第一个顶点和最后一个顶点相同的闭链叫回路。 你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 13. 判断正误 任一运输网络中至少存在一个流。 你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 14. 判断正误 Djisktra 算法可求出非负赋权图中一顶点到任一顶点的最短距离。 你选择的答案： 说法正确 [正确] 正确答案：说法正确
判断正误
同一问题的线性规划模型是唯一的。
你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 6. 判断正误 任何线性规划问题存在并具有唯一的对偶问题。 你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 7. 对偶问题的对偶不一定是原问题。 你选择的答案： 说法错误 [正确]
f 为 G 上一个流，若 e 为 f 不饱和边，那么 e 也一定为 f 正边。
你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 15. 判断正误 统筹网络中任一节点都表示前一道工序的结束和后一道工序的开始 你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 16. ．在统筹网络图中只能有一个始点和一个终点。 你选择的答案： 说法正确 [正确] 正确答案：说法正确
第三步：按照第 3.3 节对偶单纯形法扩展应用的思路，分别对分枝后的两个 新线性规划子问题继续求解。若新的解不满足原问题整数约束，再 按第二步进行新的分枝，直到满足下面的情况停止分枝：
22. 已知某整数规划不考虑整数约束时最优单纯型表，写出一个割平面方程。
参考答案： -1/7 x3 –2/7 x5 +x6 =-6/7； 23. 求解下列 0-1 规划问题的解。
“+”标示；当被标号点 v 为始点时Байду номын сангаас即边(u,v)为后向边时，用 “-”标示。
（3）l(v)：当被标号点 v 为终点时，l(v)=min{l(u),c(u,v)-f(u,v)}； 当被标号点 v 为始点时，l(v)=min{l(u),f(u,v)}。
另外，默认源 x 的标号为(0,+,+∞)。 第二步：继续检查，判断顶点 v 后面的边(v,z)能否成为增流链的边，边(v,
解答参考：
（注意：若有主观题目，请按照题目，离线完成，完成后纸质上交学习中心，记录成绩。在线只需提交客 观题答案。)
二、主观题(共 3 道小题)
15. 简述编制统筹图的基本原则。
参考答案：统筹图是有向图，箭头一律向右；统筹图只有一个起始点。一个终点， 没有缺口；两个节点之间只能有一个作业相连；统筹图中不能出现闭合回路。
第五步：继续求检验数，如果存在负的检验数，就返回第一步，否则计算停 止，说明找到了最优解。
本次作业是本门课程本学期的第 3 次作业，注释如下：
一、判断题(判断正误，共 11 道小题)
1. 一般情况下，松弛变量和多余变量的目标函数系数为零。 你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 2. 用单纯形法求解标准型线性规划问题时，与检验数大于 0 相对应的变量都可被选作换入变量。 你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 3. 由应用问题建立的线性规划模型中，其约束方程有多种形式 你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 4. yi 为对偶问题的最优解，若 yi>0，说明在最优生产计划中第 i 种资源已完全耗尽。 你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 5. 当所有产量和销量均为整数值时，运输问题的最优解也为整数解。 你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 6. 整数规划问题的可行解与其线性规划问题的可行域内的整数点相对应。 你选择的答案： 说法正确 [正确]
边。
第三步：若边(v,z)能够成为增流链的边，就使顶点 z 成为被标号的点，再对 被标号点 z 按照第一步的标号方式进行标号。
第四步：返回第二步，不断循环，直至不能找到被标号点，则反向追踪找出不饱和链。
20. 用标号法求图所示的网络中从 vs 到 vt 的最大流。
参考答案：
（1）Valf =5
（2）Valf =7
本次作业是本门课程本学期的第 2 次作业，注释如下： 一、判断题(判断正误，共 16 道小题)
1.
线性规划一般模型中的变量不一定是非负的。 你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 2.
用图解法求最优解时，只需求出可行域顶点对应的目标值，通过比较大小，就能
找出最优解。
你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 3. 图解法与单纯形法求解的形式不同，但从几何上理解，两者是一致的。 你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 4.
z)若成为增流链中的边所具备的条件如下： （1）如果边(v,z)是前向边，则应该有 f(v,z)<c(v,z)。
由前面知识可知，前向边流量只能增加，那么边(v,z)就不能是饱 和边。
（2）如果边(v,z)为后向边，则必有 f(v,z)>0。 由前面知识可知，后向边流量只能减少，那么边(v,z)就不能是零
解答参考： （注意：若有主观题目，请按照题目，离线完成，完成后纸质上交学习中心，记录成绩。在线只需提交客
观题答案。) 二、主观题(共 8 道小题) 17. Djisktra 算法能否求有负权的有向图中两点间的最短路径，举例说明。 参考答案：
Djisktra 算法不能求有负权的有向图中两点间的最短路径。如下图：
正确答案：说法错误 解答参考： 8. 判断正误 运输问题的求解结果可能出现下列 4 种情况之一：有唯一解；有无穷多最优解；无界解；可行解。 你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 9. 在运输问题中，只要给出一组含有（m + n -1）个非零的 xij 且满足全部约束，就可以作为基本可行解。 你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 10.
第一步：确定换入变量 同单纯形法一样，在所有的负检验数中，一般选取检验数最小的非基变 量作为换入变量。
第二步：确定换出变量和调整量 由定理 5.4 可知，由此时还是非基变量的换入变量和一组基变量可以组 成一个唯一的闭回路，找到这个闭回路以后，以此非基变量为起点，取
（2）两个终点。
（3）两个始点，两个终点。
（4）工序循环不是统筹图。
19. 简述在求最大流过程中，寻找由到源到汇的不饱和链的方法。
参考答案：
标号法寻找增流链的步骤： 第一步：对未检查的边(u,v)的顶点 v 进行标号，标号的方式为(u,边的方向,
l(v))，其中标号的各个部分按照如下确定：
（1）u：表示被标号点 v 的前一个顶点。 （2）边的方向：当被标号点 v 为终点时，即边(u,v)为前向边时，用
（1）
min Z = 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
-4/9 x1 –1/9 x5 –4/9 x6 +x7 = 2/3 ； 17. 简述西北角法、最小元素法、差值法确定运输问题初始基本可行解的过程并指出那种方法得出的解较 优。
参考答案：西北角法：按照地图中的上北下南，左西右东的判断，对调运表中的最 西北角上的空格优先满足最大供应，之后划去一行或一列，重复这种做法，直至 得到初始可行解。最小元素法：对调运表中的最小运价对应的空格优先没醉最大 供应，之后划去一行或一列，重复这种做法，直至得到初始可行解。差值法：在 运价表中，计算各行和各列的最小运价和次最小运价之差，选出最大者，它所在 某行或某列中的最小运价对应的空格优先满足最大供应，重复这种做法，直至得 到初始可行解。一般来讲，用差值法求出的初始可行解最接近最优解，也就是最优的。
本次作业是本门课程本学期的第 1 次作业，注释如下：
一、判断题(判断正误，共 14 道小题)
1. 判断正误 线性规划问题的一般模型中不能出现等式约束。 你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 2. 在线性规划模型的标准型中,bj（j=1，2，…m）一定是非负的。 你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 3. 判断正误 线性规划问题的基本解一定是基本可行解 你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 4. 线性规划问题的最优解只能在可行域的顶点上达到。 你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 5.
21. 简述分枝定界法的主要步骤
参考答案：
第一步：先不考虑整数约束条件，对一般情况的线性规划问题用单纯形法或 对偶单纯形法求解。如果求出的最优解满足整数规划问题的所有整 数约束条件，那么这个最优解也就是整数规划问题的最优解，如果 有一个或多个整数约束条件没有被满足，转到第二步。
第二步：任意选择一个应该是整数而不是整数解的变量 xk，设它的非整数解 是 bk，同时设 bk 对应的整数位是[bk]，现在将原问题分成两枝，一 枝是在原问题的基础上，增加约束条件 xk≤[bk]；另一枝是在原问 题的基础上，增加约束条件 xk≥[bk]+1，这样就构成了两个新的线 性规划问题的子问题。
判断正误
整数规划解的目标函数值一般优于其相应的线性规划问题的目标函数值。
你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 11. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。 你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 12. 第一个顶点和最后一个顶点相同的闭链叫回路。 你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 13. 判断正误 任一运输网络中至少存在一个流。 你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 14. 判断正误 Djisktra 算法可求出非负赋权图中一顶点到任一顶点的最短距离。 你选择的答案： 说法正确 [正确] 正确答案：说法正确
判断正误
同一问题的线性规划模型是唯一的。
你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 6. 判断正误 任何线性规划问题存在并具有唯一的对偶问题。 你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 7. 对偶问题的对偶不一定是原问题。 你选择的答案： 说法错误 [正确]
f 为 G 上一个流，若 e 为 f 不饱和边，那么 e 也一定为 f 正边。
你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 15. 判断正误 统筹网络中任一节点都表示前一道工序的结束和后一道工序的开始 你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 16. ．在统筹网络图中只能有一个始点和一个终点。 你选择的答案： 说法正确 [正确] 正确答案：说法正确
第三步：按照第 3.3 节对偶单纯形法扩展应用的思路，分别对分枝后的两个 新线性规划子问题继续求解。若新的解不满足原问题整数约束，再 按第二步进行新的分枝，直到满足下面的情况停止分枝：
22. 已知某整数规划不考虑整数约束时最优单纯型表，写出一个割平面方程。
参考答案： -1/7 x3 –2/7 x5 +x6 =-6/7； 23. 求解下列 0-1 规划问题的解。
“+”标示；当被标号点 v 为始点时Байду номын сангаас即边(u,v)为后向边时，用 “-”标示。
（3）l(v)：当被标号点 v 为终点时，l(v)=min{l(u),c(u,v)-f(u,v)}； 当被标号点 v 为始点时，l(v)=min{l(u),f(u,v)}。
另外，默认源 x 的标号为(0,+,+∞)。 第二步：继续检查，判断顶点 v 后面的边(v,z)能否成为增流链的边，边(v,
解答参考：
（注意：若有主观题目，请按照题目，离线完成，完成后纸质上交学习中心，记录成绩。在线只需提交客 观题答案。)
二、主观题(共 3 道小题)
15. 简述编制统筹图的基本原则。
参考答案：统筹图是有向图，箭头一律向右；统筹图只有一个起始点。一个终点， 没有缺口；两个节点之间只能有一个作业相连；统筹图中不能出现闭合回路。
第五步：继续求检验数，如果存在负的检验数，就返回第一步，否则计算停 止，说明找到了最优解。
本次作业是本门课程本学期的第 3 次作业，注释如下：
一、判断题(判断正误，共 11 道小题)
1. 一般情况下，松弛变量和多余变量的目标函数系数为零。 你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 2. 用单纯形法求解标准型线性规划问题时，与检验数大于 0 相对应的变量都可被选作换入变量。 你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 3. 由应用问题建立的线性规划模型中，其约束方程有多种形式 你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 4. yi 为对偶问题的最优解，若 yi>0，说明在最优生产计划中第 i 种资源已完全耗尽。 你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 5. 当所有产量和销量均为整数值时，运输问题的最优解也为整数解。 你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 6. 整数规划问题的可行解与其线性规划问题的可行域内的整数点相对应。 你选择的答案： 说法正确 [正确]
边。
第三步：若边(v,z)能够成为增流链的边，就使顶点 z 成为被标号的点，再对 被标号点 z 按照第一步的标号方式进行标号。
第四步：返回第二步，不断循环，直至不能找到被标号点，则反向追踪找出不饱和链。
20. 用标号法求图所示的网络中从 vs 到 vt 的最大流。
参考答案：
（1）Valf =5
（2）Valf =7
本次作业是本门课程本学期的第 2 次作业，注释如下： 一、判断题(判断正误，共 16 道小题)
1.
线性规划一般模型中的变量不一定是非负的。 你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 2.
用图解法求最优解时，只需求出可行域顶点对应的目标值，通过比较大小，就能
找出最优解。
你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 3. 图解法与单纯形法求解的形式不同，但从几何上理解，两者是一致的。 你选择的答案： 说法正确 [正确] 正确答案：说法正确 解答参考： 4.
z)若成为增流链中的边所具备的条件如下： （1）如果边(v,z)是前向边，则应该有 f(v,z)<c(v,z)。
由前面知识可知，前向边流量只能增加，那么边(v,z)就不能是饱 和边。
（2）如果边(v,z)为后向边，则必有 f(v,z)>0。 由前面知识可知，后向边流量只能减少，那么边(v,z)就不能是零
解答参考： （注意：若有主观题目，请按照题目，离线完成，完成后纸质上交学习中心，记录成绩。在线只需提交客
观题答案。) 二、主观题(共 8 道小题) 17. Djisktra 算法能否求有负权的有向图中两点间的最短路径，举例说明。 参考答案：
Djisktra 算法不能求有负权的有向图中两点间的最短路径。如下图：
正确答案：说法错误 解答参考： 8. 判断正误 运输问题的求解结果可能出现下列 4 种情况之一：有唯一解；有无穷多最优解；无界解；可行解。 你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 9. 在运输问题中，只要给出一组含有（m + n -1）个非零的 xij 且满足全部约束，就可以作为基本可行解。 你选择的答案： 说法错误 [正确] 正确答案：说法错误 解答参考： 10.
