《运筹学》第四章习题及答案

运筹学》第四章习题及答案、思考题1．运输问题的数学模型具有什么特征？为什么其约束方程的系数矩阵的秩最多等于m，n,1？2．用左上角法确定运输问题的初始基本可行解的基本步骤是什么？小元素法的基本思想是什么？为什么在一般情况下不可能用它直接得到运输问题的最优方案？4．沃格尔法（Vogel法）的基本思想是什么？它和最小元素法相比给出的运输问题的初始基本可行解哪一个更接近于最优解？为什么？5．试述用闭回路法检验给定的调运方案是否最优的原理，其检验数的经济意义是什么？6．用闭回路法检验给定的调运方案时，如何从任意空格出发去寻找一条闭回路？这闭回路是否是唯一的？9．如何把一个产销不平衡的运输问题（产大于销或销大于产）转化为产销平衡的运输10．一般线性规划问题应具备什么特征才可以转化为运输问题的数学模型？11．试述在表上作业法中出现退化解的涵义及处理退化解的方法。、判断下列说法是否正确1．运输问题模型是一种特殊的线性规划模型，所以运输问题也可以用单纯形方法求解。2．因为运输问题是一种特殊的线性规划模型，因而求其解也可能出现下列四种情况：有唯一最优解；有无穷多个最优解；无界解；无可行解。3．在运输问题中，只要给出一组（,,xijm，n,1）个非零的，且满足nmx,aijix,b,,ijjj,1i,1，，就可以作为一个基本可行解。4．表上作业法实质上就是求解运输问题的单纯形法。5．按最小元素法或元素差额法给出的初始基本可行解，从每一空格出发都可以找到一闭回路，且此闭回路是唯一的。6．如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。7．如果运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数k，最优调运方案将不会发生变化。8．用位势法计算检验数时，先从某一行（或列）开始，给出第一个位势的值，这个先给出的位势值必须是正的。9．用位势法计算检验数时，每一行（或列）的位势的值是唯一的，所以每个空格的检验数是唯一的。10．当所有产地的产量和销地的销量都是整数时，运输问题的最优解也是整数。三、求解下列产销平衡的运输问题，下表中列出的为产地到销地之间的运2）由上面价。（1）用左上角法、最小元素法、沃格尔法求初始基本可行解；所得的初始方案出发，应用表上作业法求最优方案，并比较初始方案需要的迭代次数。销地产地BBBB产量1234131131273741059销量365620四、用表上作业法求下列产销平衡的运输问题的最优解：（表上数字为产地到销地的运价，M为任意大的正数，表示不可能有运输通道）1）1105672528276253934850销地甲乙丙丁戊产量产地12545330234175203219872045436830172167202467M620357M3710488626151101211127102610911101135912121110产量5657831(6)18637530五、用表上作业法求下列产销不平衡的运输问题的最优解：（表上数字为产地到销地的里程，M为任意大的正数，表示不可能有运输通道）。11016231722100213M1814161203031916M140491123819805242836303460110410758027M44740385126860产量50403060201M211411281310023611312M1203911M181924160产量907080507060368122536产量1218211415六、某农民承包了5块土地共206亩，打算小麦、玉米和蔬菜三种农作物，各种农作物的计划播种面积(亩)以及每块土地种植各种不同的农作物的亩产数量(公斤)见下表，试问怎样安排种植计划可使总产量达到最高？土地块别计划播甲乙丙丁戊作物种类种面积15006006501050800862850800700900950703100095085055070050土地亩数3648443246、(1)?(2)X(3)X(4)?(5)?(6)?(7)X(8)X(9)X(10)?三、解：(1)西北角法：运费为Z=135销地产量BBBB1234产地销量365620

(2)最小元素法：运费为Z=92销地B产量BBB产地1234销地BBB盯量产地1234销量365620

（4）最优调运方案：最少运费Z=85销地BBBB^量产地1234销量365620四、各题的最优调运方案如下：1）最少运费为：535。销地甲乙丙丁产量产地12525215102531553050销量152030351002）最少运费为：226销地甲乙丙丁产量产地115217销地甲乙丙丁戊产量产地1303025152035152041020030销量10152520301004）最少运费为：248181220210102037310410515产量10151210185）最少运费为：2601281021551135510产量5657831（6）最少运费为：450

3025530产量252520102031五、解：各题的最优调运方案如下：1）最短运程为：5240产地甲乙丙丁戊己销量销地160401002408012034010014042060805204060产量1001201006080312）最短运程为：980产地甲乙丙丁戊销量销地14020208023010403303060420产量50403060203）最短运程为：3870产地甲乙丙丁戊己销量销地14060100240503012039070160440产量9070805070604）最短运程为：330产地甲乙丙丁戊己销量销地1218