运筹学习题答案(第三章) PPT课件

运筹学教程 第二版 习题解答 第三章习题解答 3 1与一般线性规划的数学模型相比 运输问题的数学模型具有什么特征 答 1 运输问题一定有有限最优解 2 约束系数只取0或1 3 约束系数矩阵的每列有两个1 而且只有两个1 前m行中有一个1 或n行中有一个1 4 对于产销平衡的运输问题 所有的约束都取等式 3 2运输问题的基可行解应满足什么条件 将其填入运输表中时有什么体现 并说明在迭代计算过程中对它的要求 解 运输问题基可行解的要求是基变量的个数等于m n 1 填入表格时体现在数字格的个数也应该等于m n 1 在迭代过程中 要始终保持数字格的个数不变 第三章习题解答 3 3试对给出运输问题初始基可行解的西北角法 最小元素法和Vogel法进行比较 分析给出的解之质量不同的原因 解 用西北角法可以快速得到初始解 但是由于没有考虑运输价格 效果不好 最小元素法从最小的运输价格入手 一开始效果很好 但是到了最后因选择余地较少效果不好 Vogel法从产地和销地运价的级差来考虑问题 总体效果很好 但是方法较复杂 第三章习题解答 3 4详细说明用位势法 对偶变量法 求检验数的原理 解 原问题的检验数也可以利用对偶变量来计算 第三章习题解答 其中 ui和vj就是原问题约束对应的对偶变量 由于原问题的基变量的个数等于m n 1 所以相应的检验数就应该等于0 即有 由于方程有m n 1个 而变量有m n个 所以上面的方程有无穷多个解 任意确定一个变量的值都可以通过方程求出一个解 然后再利用这个解就可以求出非基变量的检验数了 第三章习题解答 3 5用表上作业法求解运输问题时 在什么情况下会出现退化解 当出现退化解时应如何处理 解 当数字格的数量小于m n 1时 相应的解就是退化解 如果出现了退化解 首先找到同时划去的行和列 然后在同时划去的行和列中的某个空格中填入数字0 只要数字格的数量保持在m n 1个的水平即可 第三章习题解答 3 6一般线性规划问题具备什么特征才能将其转化为运输问题求解 请举例说明 解 如果线性规划问题有 供 和 需 的关系 并且有相应的 费用 就可以考虑将线性规划问题转成运输问题求解 例如 生产满足需求的问题 第三章习题解答 3 7试判断表3 30和表3 31中给出的调运方案可否作为表上作业法迭代时的基可行解 为什么 答 都不是 数字格的数量不等于m n 1 第三章习题解答 第三章习题解答 3 8表3 32和表3 33分别给出了各产地和各销地的产量和销量 以及各产地至各销地的单位运价 试用表上作业法求最优解 第三章习题解答 第三章习题解答 3 9试求出表3 34给出的产销不平衡运输问题的最优解 第三章习题解答 第三章习题解答 3 10某市有三个面粉厂 它们供给三个面食加工厂所需的面粉 各面粉厂的产量 各面食加工厂加工面粉的能力 各面食加工厂和各面粉厂之间的单位运价 均表示于表3 35中 假定在第1 2和3面食加工厂制作单位面粉食品的利润分别为12元 16元和11元 试确定使总效益最大的面粉分配计划 假定面粉厂和面食加工厂都属于同一个主管单位 第三章习题解答 第三章习题解答 第三章习题解答 3 11表3 36示出一个运输问题及它的一个解 第三章习题解答 试问 1 表中给出的解是否为最优解 请用位势法进行检验 答 是最优解 2 如价值系数c24由1变为3 所给的解是否仍为最优解 若不是 请求出最优解 答 原来的解不是最优解 新的最优解是 x12 3 x13 5 x21 8 x22 2 x33 1 x34 3 其他变量为0 3 若所有价值系数均增加1 最优解是否改变 为什么 答 不会改变 因为检验数不变 第三章习题解答 4 若所有价值系数均乘以2 最优解是否改变 为什么 答 最优解不变 因为检验数不变 5 写出该运输问题的对偶问题 并给出其对偶问题的最优解 第三章习题解答 3 121 2 3三个城市每年需分别供应电力320 250和350单位 由I 两个电站提供 它们的最大供电量分别为400个单位和450个单位 单位费用如表3 37所示 由于需要量大于可供量 决定城市1的供应量可减少0 30单位 城市2的供应量不变 城市3的供应量不能少于270单位 试求总费用最低的分配方案 将可供电量用完 第三章习题解答 第三章习题解答 第三章习题解答 3 13试写出本章例5转运问题的数学模型 解 已知a1 10 a2 40 a3 a4 a5 0b1 b2 b3 0 b4 30 b5 20Q 50下面就是相应的模型 MINZ 4X 1 1 5X 1 2 3X 1 3 2X 1 4 100X 1 5 5X 2 1 X 2 2 2X 2 3 100X 2 4 4X 2 5 3X 3 1 2X 3 2 3X 3 3 5X 3 4 5X 3 5 2X 4 1 100X 4 2 5X 4 3 3X 4 4 6X 4 5 100X 5 1 4X 5 2 5X 5 3 6X 5 4 5X 5 5 第三章习题解答 2 X 1 1 X 1 2 X 1 3 X 1 4 X 1 5 103 X 2 1 X 2 2 X 2 3 X 2 4 X 2 5 404 X 3 1 X 3 2 X 3 3 X 3 4 X 3 5 05 X 4 1 X 4 2 X 4 3 X 4 4 X 4 5 06 X 5 1 X 5 2 X 5 3 X 5 4 X 5 5 07 X 1 1 X 2 1 X 3 1 X 4 1 X 5 1 08 X 1 2 X 2 2 X