运筹学习题答案注释(第3章)

运筹学习题答案注释(第3章) 3.8 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 3-32和表3-33分别给出了各产地和各销地的产量和销量，以及各产地至各销地的单 位运价，试用表上作业法求最优解。 表3-32 销地 B1 B2 B3 B4 产量 产地 A1 4 1 4 6 8 A2 1 2 5 0 8 A3 3 7 5 1 4 销量 6 5 6 3 20 解：由最小元素法求得上述运输问题的初始基可行解，其过程如下： 产量 B B B B 表3.8-1 1234 销地 4 1 4 6 产地 8 A 1 1 2 5 0 8 A 2 3 7 5 1 4 A 3 销量 6 5 6 3 20 由于0为最小，所以，取3与8的最小值放在x24位置上，划去B4列，得表3.8-2 表3.8-2 销地 产量 产地 B B B B 1234 4 1 4 6 8 A 1 1 2 5 0 5 A 2 3 3 7 5 1 4 A 3 销量 6 5 6 0 在没画线的 表格 关于规范使用各类表格的通知入职表格免费下载关于主播时间做一个表格详细英语字母大小写表格下载简历表格模板下载 中，由于1最小，所以取6与5的最小值放在x21位置上，划去A2行， 得表3.8-3 在表3.8-3中的没画线的表格中，由于1最小，所以取8与5的最小值放在x12位置上，划去B2列，得表3.8-4 运筹学习题答案及注释 第1页 在表3.8-4中没画线的表格中，由于3最小，所以取4与1的最小值放在x31位置上， 划去B1列，得表3.8-5 产量 B B B B 1234表3.8-3 销地 4 1 4 6 产地 8 A 1 1 2 5 0 A 20 5 3 3 7 5 1 4 A 3 销量 1 5 6 0 表3.8-4 销地 产量 产地 B B B B 1234 4 1 4 6 3 A 1 5 1 2 5 0 A 20 5 3 3 7 5 1 4 A 3 销量 1 0 6 0 表3.8-5 销地 产量 产地 B B B B 1234 4 1 4 6 3 A 1 5 1 2 5 0 A 20 5 3 3 7 5 1 3 A 31 销量 0 0 6 0 在表3.8-5中没画线的表格中，由于4最小，所以取3与6的最小值放在x13位置上， 划去A1行，得表3.8-6 在表3.8-6中没画线的表格中，由于5最小，所以取3与3的最小值放在x33位置上， 划去A3行和B3列，得表3.8-7，这样就得到了一个初始基可行解，如表3.8-8所示。 在表3.8-8中，使用闭回路法计算非基变量的检验数（括弧内的数），得表3.8-9： 运筹学习题答案及注释 第2页 - c13 + c33 - c31 = 4-4+5-3 = 2 σ14 = c14- c13 + c33 - c31 + c21 - c24 = 6-4+5-3+1-0 = 5 σ11 = c11得表3.8-6 销地 产量 B B B B 1234产地 4 1 4 6 A 13 5 3 1 2 5 0 A 20 5 3 3 7 5 1 3 A 31 销量 0 0 3 0 表3.8-7 销地 产量 产地 B B B B 1234 4 1 4 6 A 10 5 3 1 2 5 0 A 20 5 3 3 7 5 1 A 30 3 1 销量 0 0 0 0 表3.8-8 销地 产量 产地 B B B B 1234 4 1 4 6 8 A 1 5 3 1 2 5 0 8 A 25 3 3 7 5 1 4 A 33 1 销量 6 5 6 3 20 σ22 = c22 - c12 + c13 - c33 + c31 - c21 = 2-1+4-5+3-1 = 2 σ23 = c23 - c33 + c31 - c21 = 5-5+3-1 = 2 σ32 = c32 - c33 + c13 – c12 = 7-5+4-1 = 5 σ34 = c34 - c24 + c21 – c13 = 1-0+1-3 = -1 在表3.8-9中，由于检验数σ34 = -1?0 ，所以表3.8-9中的解不是最优解。选x34 运筹学习题答案及注释 第3页 为换入变量，找到闭回路为：x34 x24 x21 x31 ，由于3与1的最小数为1，故调整量为1， 选x31为换出变量，调整后的解如表3.8-10所示 产量 B B B B 1234表3.8-9 4 1 4 6 销地 8 A 1产地 5 3 1 2 5 0 8 A 25 3 3 7 5 1 4 A 33 1 销量 6 5 6 3 20 表3.8-10 销地 产量 产地 B B B B 1234 4 1 4 6 8 A 1 5 3 1 2 5 0 8 A 26 2 3 7 5 1 4 A 33 1 销量 6 5 6 3 20 在表3.8-10中，使用闭回路法计算各非基变量的检验数，得表3.8-11： 表3.8-11 销地 产量 产地 B B B B 1234 4 1 4 6 8 A 1 5 3 1 2 5 0 8 A 26 2 3 7 5 1 4 A 33 1 销量 6 5 6 3 20 在表3.8-11中，由于所有检验数均大于等于 0 ，所以表3.8-11中的解就是最优解，其最小运价为39 。 解：由最小元素法求得上述运输问题的初始基可行解，如下表3.8-21： 在表3.8-21中，使用闭回路法计算非基变量的检验数（括号内的数），得表3.8-22： 运筹学习题答案及注释 第4页 在表3.8-22中，由于所有检验数均大于等于 0 ，所以表3.8-22中的解就是最优解， 其最小运价为 31 。 表3-33 销地 B1 B2 B3 B4 产量 产地 A1 9 3 8 7 3 A2 4 9 4 5 3 A3 5 7 6 2 5 销量 1 3 2 5 11 表3.8-21 产量 B B B B 1234销地 9 3 8 7 产地 3 A 1 3 4 9 4 5 3 A 21 2 5 7 6 2 5 A 30 0 5 销量 1 3 2 5 11 表3.8-22 销地 产量 产地 B B B B 1234 9 3 8 7 3 A 1 3 4 9 4 5 3 A 21 2 5 7 6 2 5 A 30 0 5 销量 1 3 2 5 11 3.9 试求表3-34给出的产销不平衡运输问题的最优解。 表3-34 销地 B1 B2 B3 B4 产量 产地 A1 3 7 6 4 5 A2 2 4 3 2 2 A3 4 3 8 5 6 销量 3 3 2 2 运筹学习题答案及注释 第5页 解：由于该运输问题的产量大于销量，产销不平衡，可增加一个假想的销地B5，其销量为: (5+2+6)-(3+3+2+2)=3,运费为0 ，使之变为产销平衡问题，如表3.9-1所示： 表3.9-1 销地 B1 B2 B3 B4 B5 产量 产地 A1 3 7 6 4 0 5 A2 2 4 3 2 0 2 A3 4 3 8 5 0 6 销量 3 3 2 2 3 13 由最小元素法求得上述运输问题的初始基可行解，如下表3.9-2 。 表3.9-2 产量 B B B B B 12345销地 产地 3 7 6 4 0 5 A 13 0 2 2 4 3 2 0 2 A 20 2 4 3 8 5 0 6 A 3 3 3 销量 3 3 2 2 3 13 表3.9-3 销地 产量 产地 B B B B B 12345 3 7 6 4 0 5 A 13 0 2 2 4 3 2 0 2 A 20 2 4 3 8 5 0 6 A 3 3 3 销量 3 3 2 2 3 13 在表3.9-2中，使用闭回路法计算非基变量的检验数（括号内的数），得表3.9-3 。 在表3.9-3中，由于有多个检验数均小于 0 ，选最小的检验数σ15 = -4 ，其位置上的变量x15为换入变量，找到闭回路为：x15 x35 x32 x12 ，由于3与0的最小数为0，故调整量为0，选x12为换出变量，调整后的解如表3.9-4所示 。在表3.9-4中，使用闭回路法计算各非基变量的检验数（括号内的数）。 在表3.9-4中，只有检验数σ23小于 0 ，选其位置上的变量x23为换入变量，找闭回路为：x23 x13 x11 x21 ，由于2与0的最小数为0，故调整量为0，选x21为换出变量，调整后的解如表3.9-5所示 ，使用闭回路法计算各非基变量的检验数（括号内的数）。 运筹学习题答案及注释 第6页 产量 B B B B B 12345表3.9-4 销地 3 7 6 4 0 产地 5 A 13 2 0 2 4 3 2 0 2 A 20 2 4 3 8 5 0 6 A 3 3 3 销量 3 3 2 2 3 13 表3.9-5 销地 产量 产地 B B B B B 12345 3 7 6 4 0 5 A 13 2 0 2 4 3 2 0 2 A 2 0 2 4 3 8 5 0 6 A 3 3 3 销量 3 3 2 2 3 13 在表3.9-5中，由于只有检验数σ14小于 0 ，选其位置上的变量x14为换入变量，找到闭回路为：x14 x24 x23 x13 ，由于2与2的最小数为2，故调整量为2，选x13为换出变量，调整后的解如表3.9-6所示 。在表3.9-6中，使用闭回路法计算各非基变量的检验数 （括号内的数）。 表3.9-6 销地 产地 产量 B B B B B 12345 3 7 6 4 0 5 A 13 2 0 2 4 3 2 0 2 A 2 2 0 4 3 8 5 0 6 A 3 3 3 销量 3 3 2 2 3 13 在表3.9-6中，由于所有检验数均大于等于 0 ，所以表3.9-6中的解就是最优解，其最小运价为 32 。 3.10 某市有三个面粉厂，它们供给三个面食加工厂所需面粉。各面粉厂的产量、各面食加 运筹学习题答案及注释 第7页 工厂加工面粉的能力、各面食加工厂和各面粉厂之间的单位运价，均示于表3-35中。假定在第1，2和3面食加工厂制作单位面粉食品的利润分别为12元、16元和11元，试确定使总效益最大的面粉分配计划（假定面粉厂和面食加工厂都属于同一个主管单位）。 表3-35 食品厂 1 2 3 面粉厂产量 面粉厂 ? 3 10 2 20 ? 4 11 8 30 ? 8 11 4 20 食品厂需量 15 25 20 解：由题意知：该问题为产量大于需量的不平衡问题，可以假想一个虚拟的面食加工厂4，其需量为（20+30+20）-（15+25+20）= 10 ，从而变为平衡问题。又该题求总效益最大的面 粉分配 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，可以转化为下面运输问题，运往虚拟的面食加工厂4的运费为 0 ，如下表。 表3.10-1 食品厂 1 2 3 4 面粉厂产量 面粉厂 ? -9 -6 -9 0 20 ? -8 -5 -3 0 30 ? -4 -5 -7 0 20 食品厂需量 15 25 20 10 70 则容易得知，其总效益就是总运费的相反数。 由最小元素法求得上述运输问题的初始基可行解，并使用闭回路法计算非基变量的检验 数（括号内），得表3.10-2 。 表3.10-2 食品厂 1 2 3 4 面粉厂产量 面粉厂 -9 -6 -9 0 ? 20 0 20 -8 -5 -3 0 ? 30 15 15 -4 -5 -7 0 ? 20 10 10 食品厂需量 15 25 20 10 70 在表3.10-2中，由于所有检验数均大于等于 0 ，所以表3.10-2中的解就是最优解，其最小运费为 425 。即面粉分配计划为：面粉厂?的面粉20单位运往面食加工厂3，面粉厂?的面粉15单位运往面食加工厂1，面粉厂?的面粉15单位运往面食加工厂2，面粉厂?的面粉10单位运往面食加工厂2，面粉厂?的面粉10单位不向外运输，其总效益最大， 为425元 。 3.11 在表3-36示出一个运输问题及它的一个解，试问： 运筹学习题答案及注释 第8页 （1）表中给出的解是否为最优解？请用位势法进行检验。 （2）若价值系数c24由1变为3，所给的解是否仍为最优解？若不是，请求出最优解。 （3）若所有价值系数均增加1，最优解是否改变？为什么？ （4）若所有价值系数均乘以2，最优解是否改变？为什么？ （5）写出该运输问题的对偶问题，并给出其对偶问题的最优解。 产量 B B B B 1234表3-36 销地 4 1 4 6 产地 8 A 1 5 3 1 2 6 1 10 A 28 2 3 7 5 1 4 A 3 3 1 销量 8 5 6 3 22 解：（1）设i 行的位势ui ，第i 列的位势vi ，则可以得到下列方程组： u，v,112u，v,413u，v,1 21 u，v,124 u，v,533 u，v,134 令u1 = 0，得：v2 = 1 ，v3 = 4 ， u3 = 1 ，v4 = 0，u2 = 1 ，v1 = 0。 由公式σij = cij – ( ui + vj ) ,可以计算出各非基变量的检验数（括号内）。如表3.11-1 ： 表3.11-1 销地 产量 产地 B B B B 1234 4 1 4 6 8 A 1 5 3 1 2 6 1 10 A 28 2 3 7 5 1 4 A 3 3 1 销量 8 5 6 3 22 在表3.11-1中，由于所有检验数均大于等于 0 ，所以表3.11-1中的解是最优解，其目标函数值（最小运价）为43 （2）若价值系数c24由1变为3，并使用闭回路法计算非基变量的检验数（括号内），得表 3.11-2 。 在表3.11-2中，由于有多个检验数小于 0 ，所以该解不是最优解。选最小的检验数 运筹学习题答案及注释 第9页 σ22 = -2 ，其位置上的变量x22为换入变量，找到闭回路为：x22 x24 x34 x33 x13 x12 ，由于2、3与5的最小数为2，故调整量为2，选x24为换出变量，调整后的解如表3.11-3所示 。在表3.11-3中，使用闭回路法计算各非基变量的检验数（括号内）。 产量 B B B B 1234表3.11-3 销地 4 1 4 6 产地 8 A 1 3 5 1 2 6 3 10 A 28 2 3 7 5 1 4 A 3 1 3 销量 8 5 6 3 22 在表3.11-3中，由于所有检验数均大于等于 0 ，所以表3.11-3中的解是最优解。 （3）若所有价值系数均增加1，最优解是否改变？为什么？ 若所有价值系数均增加1，最优解不改变。因为若所有价值系数均增加1，使用闭回路法计算检验数时，在计算式子中，其偶数顶点增加的价值系数恰好被奇数顶点增加的价值系 数抵消，因而检验数不变，故最优解不变。 （4）若所有价值系数均乘以2，最优解是否改变？为什么？ 若所有价值系数均乘以2，最优解不改变。因为若所有价值系数均乘以2，使用闭回路法计算检验数时，在计算式子中，其偶数顶点的价值系数、奇数顶点增加的价值系数均乘以 2，因而检验数变为原来的2倍，但检验数的正负没有变，故最优解不变。 （5）写出该运输问题的对偶问题，并给出其对偶问题的最优解。 该运输问题的对偶问题为： max ,z,8u，10u，4u，8v，5v，6v，3v 1231234 ，,4uv, ,11，,1uv,12,，,4uv,13，,6uv,14,，,1uv,21，,2uvst. , ,22，,6uv,23,，,1uv,24，,3uv,31,，,7uv,32,，,5uv33,，,1uv,34,,,,,,,的符号不限uuuvvvv,1231234 其对偶问题的最优解为：（0，1，1，0，1，4，0），其目标函数值为43 。 运筹学习题答案及注释 第10页 u1+v2 = 1 u1+v3 = 4 u2+v1 = 1 u2+v4 = 1 u3+v3 = 5 u3+v4= 1 运筹学习题答案及注释 第11页