第 1 次作业一、填空题（本大题共 30 分，共 10 小题，每小题 3 分）1. 图解法的基本理论是: ______ 2. 最短路是在一网络中，求给定 ______ 到 ______ 的一条路长最短的路3. 最小树是 ______ 最小的树（无圈连通图）。4. 匈牙利算法适用于 ______ 。5. 若标准线性规划问题有可行解，则必有 ______ 。6. 模型在 ______ 确定过程中须注意选择真正起作用的因素，筛去那些对模型目标无显著影响的因素。对选定的因素；应注意它们是 ______ 还是 ______ 的，能否 ______ 等。7. ______ 从第一段开始计算逐段向后递推，计算后一段要用到 ______ 的求优结果，而 ______ 的结果就是全过程的最优策略，即寻优的方向与多阶段决策过程实际进行的方向相同。8. 运筹学的分析步骤一般包括: ______ ； ______ ； ______ ； ______ 。9. 整数规划模型是在其松弛问题基础上附加了 ______ 得整数约束条件，因此，整数规划得解题是 ______ 的后续部分。10. 模型规范要求模型的建立须在 ______ 、 ______ 、 ______ 下进行，相应的环境、范围与要求必然地要对模型起限制作用。此外，要素本身变化有一定限度，要素的相互影响作用也只能在 ______ 内保持有效。二、简答题（本大题共 40 分，共 8 小题，每小题 5 分）1. 简述路的基本概念。2. 图解法适用范围？3. 运输问题的求解方法？4. 多阶段决策过程最优化对决策者的要求5. 整数规划与其松弛问题之间在可行域及其解方面有什么对应关系?6. 线性规划问题可行域的概念？7. 图解法基本思想及步骤？8. 影子价格具有的特点。三、综合分析题（本大题共 30 分，共 2 小题，每小题 15 分）1. 按对变量的不同要求，还可将整数规划分为下述几种类型： ______ ______ ______ 2. 某物流中心拟选择一条从 A 地到 F 地的运输线路，可供选择路线及各点间的距离如下图；试问：应如何选择路线使总距离最短（单位运输成本为一常数， 同时也是使总成本最小）？答案：一、填空题（30 分，共 10 题，每小题 3 分）1. 参考答案：凸集基本理论解题方案：评分标准：1 空 1 分2. 参考答案：一初始点 vs 一终点 vt解题方案：评分标准：1 空 1 分3. 参考答案：权重之和解题方案：评分标准：1 空 1 分4. 参考答案：指派问题解题方案： 评分标准：1 空 1 分5. 参考答案：基可行解解题方案：评分标准：1 空 1 分6. 参考答案：要素 确定性的 不确定性 进行测量解题方案：评分标准：1 空 1 分7. 参考答案：顺序解法前一段最后一段解题方案：评分标准：1 空 1 分8. 参考答案：发现和定义待研究的问题 构造数学模型 寻找经过模型优化的结果 并通过应用这些结果来改善系统的运行效率。解题方案：评分标准：1 空 1 分9. 参考答案：一个决策变量 线性规划解题解题方案：评分标准： 1 空 1 分10. 参考答案：一定的环境 一定的范围 一定的要求 一定的限度解题方案：评分标准：1 空 1 分二、简答题（40 分，共 8 题，每小题 5 分）1. 参考答案：有向图中当链(圈)上的边方向相同时,称为路(回路)。解题方案：评分标准：总体接近程度 2 分，概念 3 分2. 参考答案：两个变量的线性规划问题解题方案：评分标准：概念 5 分3. 参考答案：1）计算机方法；2）单纯形法；3）表上作业法；4）图上作业法；解题方案：评分标准：一点 1 分4. 参考答案：所以决策者在每段决策时不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而做出对全局来讲是最优的决策。解题方案：评分标准：总体接近程度 1 分，概念每个 2 分5. 参考答案： 整数线性规划比线性规划复杂得多，两者得关系很密切，即整数规划要靠线性规划某种解题方法为之提供其松弛问题得最优解，并在此基础上，逐步对解进行整数处理才得到原问题得最优得整数可行解；另外整数规划模型是在其松弛问题基础上附加了一个决策变量得整数约束条件，因此，整数规划得解题是线性规划解题得后续部分解题方案：评分标准：一点 1 分6. 参考答案：线性规划问题全部可行解的集合构成线性规划问题的可行域。解题方案：评分标准：概念 5 分7. 参考答案：1）根据约束条件画出可行域 K。 2）在目标函数族中任选一条目标函数直线L。 3）将 L 沿目标函数增加（减少）的方向平行移动直到刚要离开可行域 K 为止。解题方案：评分标准：总体接近程度 2 分，概念每个 1 分8. 参考答案：1）影子价格是对系统资源的一种最优估价，只有系统达到最优状态时才可能赋予该资源这种价值。 2）影子价格的取值与系统的价值取向有关，并受系统状态变化的影响。3）对偶解影子价格的大小客观地反映资源在系统内的稀缺程度。4）影子价格是一种边际价值，它与经济学中边际成本的概念相同。解题方案：评分标准：一点 1 分。三、综合分析题（30 分，共 2 题，每小题 15 分）1. 参考答案：1）纯整数规划或全整数规划 2）混合整数规划 3）0-1 规划解题方案： 评分标准：每个 1 分2. 参考答案：最短总距离为：16。解题方案：评分标准：每步 3 分