运筹学第三章课后习题答案.ppt

2020 1 2 1 3 1与一般线性规划的数学模型相比 运输问题的数学模型具有什么特征 答 与一般线性规划的数学模型相比 运输问题的数学模型具有如下特征 1 运输问题不象一般线性规划问题那样 线性规划问题有可能有无穷多最优解 运输问题只有有限个最优 2 运输问题约束条件系数矩阵的元素等于0或1 且每一列有两个非零元素 3 运输问题的解的个数不可能大于 m n 1 个 3 2运输问题的基可行解应满足什么条件 试判断形表3 26和表3 27中给出的调运方案是否作为表上作业法迭代时的基可行解 为什么 2020 1 2 2 表3 26 解 表3 26产地个数m 3 销地个数n 4 m n 1 3 4 1 6个 而表3 26中非零个数的分量为5个 6个 所以表3 26不可作为表上作业法时的基可行解 2020 1 2 3 表3 27 解 表3 27产地个数m 5 销地个数n 5 m n 1 5 5 1 9个 而表3 27中非零个数的分量为10个 9个 也不可作为表上作业法时的基可行解 2020 1 2 4 3 3试对给出运输问题初始基可行解的最小元素法和Vogel法进行比较 分析给出的解之质量不同的原因 解 对于任意给出运输问题初始基可行解的最小元素法和Vogel法进行比较 分析给出的两种不同的方法求出的解确有不同的原因 初看起来 最小元素法十分合理 但是 有时按某一最小单位运价优先安排物品调运时 却可能导致不得不采用运费很高的其他供销点时 从而使整个运输费用增加 我们称各销售地或供应地的单位运价中找出的最小单位运价和次小单位运价之差为罚数 若罚数的值不大 当不能按最小单位运价安排运输时造成的运费损失不大 但如果罚数很大 不按最小运价组织运输就会造成很大损失 故应尽量按最小运价安 2020 1 2 5 排运输 这就是最小元素法和沃格尔法质量不同的原因 3 7表3 28和表3 29分别给出了各产地和各销地的产量和销量 以及各产地至各销地的单位运价 试用表上作业法求最优解 表3 28 2020 1 2 6 表3 29 解 1 表3 28用三种方法计算 用闭回路法检验 用最小元素法计算如下表所示 2020 1 2 7 最小元素法求解如下 从上表计算知 x12 5 x13 3 x21 5 x24 3 x31 1 x33 3 总费用 5 1 3 4 5 1 3 0 1 3 3 5 40 2020 1 2 8 西北解法计算如下 从上表计算知 x11 6 x12 2 x22 3 x23 5 x33 1 x34 3 总费用 6 4 2 1 3 2 5 5 1 5 3 1 65 2020 1 2 9 用沃格尔法求解如下 2020 1 2 10 从上表计算知 x12 5 x13 3 x21 3 x23 2 x24 3 x33 1 总费用 5 1 3 4 3 1 2 5 3 0 1 5 35 在上述三种计算方法中 这种方法计算所需运输费用是最省的 但还不知是否最优 现用闭回路法检验如下 闭回路法检验如下 2020 1 2 11 第一个闭回路 11 走4 1 5 4线路 11 4 1 5 4 4 2020 1 2 12 第二闭回路 14 走6 0 5 4线路 14 6 0 5 4 7 2020 1 2 13 第三个闭回路 22 走2 1 4 5线路 22 2 1 4 5 0 2020 1 2 14 第四个闭回路 31 走3 1 5 5线路 31 3 1 5 5 2 2020 1 2 15 第五个闭回路 32 走7 1 4 5线路 32 7 1 4 5 2 2020 1 2 16 第六个闭回路 34 走1 5 5 0线路 34 1 5 5 0 1 至此 六个闭回路全部计算完 11 4 14 2 22 0 31 2 32 2 34 1 即全部检验数 均大于或等于0 即用上述三种方法计算中 用沃格尔法计算所得结果z 35为最优解 2020 1 2 17 解 2 表3 29用三种方法计算 用位势法检验 因为总产量 13 总销量 10 所以该题的总产量 总销量 所以该题是产销不平衡的问题 故假设一销地B5 用最小元素法计算如下表所示 表3 29 2020 1 2 18 最小元素法求解 x11 1 x14 1 x15 3 x21 2 x32 3 x33 2 x34 1 总费用 1 3 1 4 3 0 2 2 3 3 2 8 1 5 41 2020 1 2 19 西北角法求解 x11 3 x12 2 x22 1 x23 1 x33 2 x34 2 x35 2 总费用 3 3 2 7 1 4 1 3 1 8 2 5 3 0 48 2020 1 2 20 沃格尔法求解 2020 1 2 21 x11 2 x15 3 x23 2 x31 1 x32 3 X33 0 x34 2 总费用 2 3 0 6 3 0 2 3 1 4 3 3 2 5 35 在最小元素法中 总费用 41 在用西北角法计算中 总费用 56 因此用沃格尔法计算所需费用 35是最小的 但不知是否最优 还要用对偶变量法 位势法 加以检验 如表3 30所示 表3 30位势法检验 表3 30位势法检验 表3 30位势法检验 表3 30位势法检验 表3 30位势法检验 表3 30位势法检验 2020 1 2 22 表3 30位势法检验 由 13 1 故知z 35还不是最优解 经上表调整后得 x11 1 x13 1 x15 3 x23 1 x24 1 x31 2 x32 3 x33 0 x34