运筹学课后答案

(3)若所有价值系数均增加 1，最优解是否改变？为什么? 答：不会改变。因为检验数不变。 (4)若所有价值系数均乘以 2，最优解是否改变？为什么? 答：最优解不变。因为检验数不变。 (5)写出该运输问题的对偶问题，并给出其对偶问题的最优解。
3.12 1，2，3 三个城市每年需分别供应电力 320，250 和 350 单位，由 I，Ⅱ两个电站提供，它们的最大 供电量分别为 400 个单位和 450 个单位，单位费用如表 3—37 所示。由于需要量大于可供量，决定城市 1 的供应量可减少 0～30 单位，城市 2 的供应量不变，城市 3 的供应量不能少于 270 单位，试求总费用最低 的分配方案(将可供电量用完)。
3.4 详细说明用位势法(对偶变量法)求检验数的原理。 解：原问题的检验数也可以利用对偶变量来计算 ：
其中，ui 和 vj 就是原问题约束对应的对偶变量。由于原问题的基变量的个数等于 m+n-1。所以相应的检验 数就应该等于 0。即有： 由于方程有 m+n-1 个， 而变量有 m+n 个。所以上面的方程有无穷多个解。任意确定一个变量的值都可以 通过方程求出一个解。然后再利用这个解就可以求出非基变量的检验数了。 3.5 用表上作业法求解运输问题时，在什么情况下会出现退化解？当出现退化解时应如何处理？ 解：当 数字格的数量小于 m+n-1 时，相应的解就是退化解。如果出现了退化解，首先找到同时划去的行和列，然 后在同时划去的行和列中的某个空格中填入数字 0。只要数字格的数量保持在 m+n-1 个的水平即可。
3.1 与一般线性规划的数学模型相比，运输问题的数学模型具有什么特征? 答： 1、运输问题一定有有限最优解。 2、约束系数只取 0 或 1。 3、约束系数矩阵的每
列有两个 1， 而且只有两个 1。前 m 行中有一个 1，或 n 行中有一个 1。 4、对于产销平衡的运输问题，所有的约束都取等式。
3.2 运输问题的基可行解应满足什么条件？将其填入运输表中时有什么体现？并说明在迭代计算过程中 对它的要求。 解：运输问题基可行解的要求是基变量的个数等于 m+n-1。填入表格时体现在数字格的个 数也应该等于 m+n-1。在迭代过程中，要始终保持数字格的个数不变。
3] X(2,1) - X(2,2) + X(2,3) + X(2,4) + X(2,5) = 40
+ 2 X(4,1)+100X(4,2)+5 X(4,3)+ 3 X(4,4)+6 X( 4, 5)
+ 100X(5,1)+4X(5,2)+5X(5,3)+6 X( 5, 4) +5 X( 5, 5)
2]-X(1,1) + X(1,2) + X(1,3) + X(1,4) + X(1,5) = 10
3.13 试写出本章例 5 转运问题的数学模型。
解解：：对 已知偶问a1题＝如 10，下a：2＝40，a3 = a4 = a5 = 0
m
n
mb1a=x Zb2= b3＝aiu0，i b4＝b3jv0j，b5＝20 Q＝50
i 1
j 1
下ui 面 就v j 是 c相ij 应i的模1,型2, ：m; j 1,2,, n MINuZi ,=v j无约束, i ຫໍສະໝຸດ Baidu1,2,m; j 1,2,, n
3.6 一般线性规划问题具备什么特征才能将其转化为运输问题求解，请举例说明。
☆★☆★☆ 解：如果线性规划问题有“供”和“需”的关系，并且有相应的“费用”，就可以考虑将线性规划问题转成运输 问题求解。例如，生产满足需求的问题。 3.7 试判断表 3-30 和表 3-31 中给出的调运方案可否作为表上作业法迭代时的基可行解?为什么? 答：都不是。数字格的数量不等于 m+n-1。
☆★☆★☆
运筹学课后答案
☆★☆★☆
☆★☆★☆
☆★☆★☆
☆★☆★☆
☆★☆★☆
☆★☆★☆
☆★☆★☆
☆★☆★☆
☆★☆★☆
☆★☆★☆
☆★☆★☆
ij cij (ui v j ) i 1,2,m; j 1,2,, n cij (ui v j ) 0 i 1,2,m; j 1,2,, n
3.11 表 3-36 示出一个运输问题及它的一个解：
试问：
☆★☆★☆
(1)表中给出的解是否为最优解？请用位势法进行检验。 答：是最优解。 (2) 如 价 值 系 数 c24 由 1 变 为 3 ， 所 给 的 解 是 否 仍 为 最 优 解 ？ 若 不 是 ， 请 求 出 最 优 解 。 答 ： 原来的解不是最优解。新的最优解是： x12=3,x13=5,x21=8,x22=2,x33=1,x34=3，其他变量为 0 。
4 X(1,1最)+优5 解 X(1是,2： )+u31 X(11,3,)u+2 2X0(,1u,34)+01,00X(1, 5)
+ 5 X(2,1)+ X(2,2)+v21X(12,,3v)2+1020, vX3 (2,54,)v+4 4X1(2, 5)
+ 3 X(3,1)+2X(3,2)+3 X(3,3)+5 X(3, 4) + 5 X( 3, 5)
3.8 表 3-32 和表 3-33 分别给出了各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用 表上作业法求最优解。
3.9 试求出表 3-34 给出的产销不平衡运输问题的最优解。
3.10 某市有三个面粉厂，它们供给三个面食加工厂所需的面粉。各面粉厂的产量、各面食加工厂加工面 粉的能力、各面食加工厂和各面粉厂之间的单位运价，均表示于表 3-35 中。假定在第 1，2 和 3 面食加工 厂制作单位面粉食品的利润分别为 12 元、16 元和 11 元，试确定使总效益最大的面粉分配计划(假定面粉厂 和面食加工厂都属于同一个主管单位)。
3.3 试对给出运输问题初始基可行解的西北角法、最小元素法和 Vogel 法进行比较，分析给出的解之质量 不同的原因。 解：用西北角法可以快速得到初始解，但是由于没有考虑运输价格，效果不好；最小元素 法从最小的运输价格入手，一开始效果很好，但是到了最后因选择余地较少效果不好； Vogel 法从产地和 销地运价的级差来考虑问题，总体效果很好，但是方法较复杂。