[管理学]管理运筹学作业答案MBA.doc

运筹学作业答案 第1章 线性规划基本性质P47 11（2）解：设每天从煤矿运往城市的煤为吨，该问题的LP模型为：P48 12（2）3-10（1）（2）解：，则该LP问题无可行解。P48 12（3）1-50（1）（2）QZ=0Z=10-1P解：目标函数等值线与函数约束（2）的边界线平行，由图可知则该LP问题为多重解（无穷多最优解）。则（射线QP上所有点均为最优点）P48 12（4）（1）（2）（3）Z=0Q解：由图可知Q点为最优点。则P48 13（2） P49 15解：可行域的极点与基本可行解是一一对应的。（1）对于，不满足约束条件，即不是可行解，也就不是基本可行解，故不是该可行域的极点。（2）对于，是可行解。此时基变量为，由此得到的基矩阵为，所以不是基本解，也就不是基本可行解，故不是该可行域的极点。（3）对于，是可行解。此时基变量为，由此得到的基矩阵为，所以不是基本解，也就不是基本可行解，故不是该可行域的极点。P50 1812345678A(2.9)11120000100B(2.1)12001023100C(1.2)20314620100余料00.30.90.40.50.20.81.1解：设按第种截法下料根，该问题的LP模型为：第2章 单纯形法P70 21（2）解：标准化为，容易得第一次迭代： 则为进基变量（此时仍为非基变量） 则为进基变量，6为主元 此时：第二次迭代： 则为进基变量 则为进基变量，为主元 此时：此时，则（图解法略）注意由方程组形式求的每个基本可行解与图解法求得的可行域的极点之间的一一对应关系。P70 22（1）解：化标准形为：2200b01110021012200而它所对应的系数列向量则该LP问题无最优解（无界解）。补充作业：求解下列LP问题：解：标准化后求解过程如下：63000b06031110020010（1）201010020110012063000030041030/4610120100100（2）01503000100011615101/201/21/2501-3/20-1/21/200-9/20-9/2-3/2，则最优解为：P70 22（4）解：建立该LP问题的大M法辅助问题如下： 00b81（4）20102632000130021/411/201/4082（5/2）01/214/50001（3/5）1/103/10101/52/5000/2305/311/61/2/6212/300/301/3000/2/2由于出现非基变量的检验数为0，故该LP问题有多重解。则最优解为： P71 22 （5）解：目标函数化标准形为：函数约束添加人工变量，拟采用两阶段法求解。第一阶段：两阶段法辅助问题目标函数为：0000b2（1）210026211010371111001741010000212100-20（3）3102/35022015/20550008/310-1/301/31/30-02/301-7/31-2/31/30-11/300（11/3）01/3-2/3110011/30-2/3-5/300310004/113/111/11030101-5/11-1/117/110100101/11-2/113/110000由第一阶段最终单纯形表可得，故原LP问题存在可行基，转入第二阶段继续求解。第二阶段：求解原LP问题。11b31000-3010（1）3110010-000231000130101110010000此时故原LP问题的最优解为：补充作业：求解下列LP问题：解：建立大法的辅助问题如下： 211000b4（4）220011020240010010016482001040002111/21/2-1/4001/4018031/210-1/236012060（1）01120001/2002412（1/2）001/4080120001-1/200120601010000-1/218241001/2002024001000120601010000-1/2该LP问题有多重解。最优解为：，第3章 对偶原理P92 31 （1）（2）（4）（1） （2） （4） P92 32 （6）（6） P93 36 （1）用对偶单纯形法求解LP问题解： 000b010005100100（）0010001/3200（）10030011/3211/300000116/5010（1/5）017/50012/58/5101/500000060501010110412000000该LP问题有多重解。最优解为： P93 37解：（1）设甲、乙、丙三种产品每月的产量分别为件，建立LP模型为：32100b0400121104000500（2）12012503210001500（3/2）01100325011/2101/250001/2021000102/332001012/300，则最优解为即：每月生产甲产品200件，乙产品100件。最大总产值为800千元。（2）对偶问题为： 由对偶性质可得：，即A设备的影子价格为1/3千元，即元350元。故外租外厂A设备不划算。补充作业：1、已知线性规划问题，其对偶问题的最优解为：，。试用对偶性质求出原问题的最优解。解：该问题的对偶问题为：将对偶问题的最优解代入到对偶问题的所有函数约束中去，发现（1）（2）为严格不等式，由互补松弛性定理（或松紧定理）知 又因，由互补松弛性定理（或松紧定理）知原问题的两个约束条件应该取严格等式，综上可得： ，解得故原问题的最优解为： ,第5章 运输模型P144 51解：调拨站工厂1234产量15 27.5 13 （10）4.5 （2）12026.5 28 （10）4 6 （7）171.534 （10）7 5 15.5 （1）111销量101010104036.534.5，则该方案为非最优方案又，则为进基变量，调整量，为离基变量。新方案为：调拨站工厂1234产量15 27.5 0.53 （3）4.5 （9）12026.5 2.58 （10）4 （7）6 17134 （10）7 5 15.5 （1）111销量10101010403734.5，则该方案仍不是最优方案，为进基变量，调整量，为离基变量。新方案为：调拨站工厂1234产量15 17.5 0.53 （2）4.5 （10）12026.5 1.58 （9）4 （8）6 0.517134 （10）7 （1）5 25.5 1110销量10101010404734.5此时此方案为最优方案。（元）第6章 整数规划P171 62 （2）解：先用图解法求出松弛问题的最优解为：。无可行解由上可知：该IP问题的最优解为，。P171 62 （4）解：将原问题转化为求 其松弛问题的最优解为无可行解无可行解与相矛盾则原IP问题无可行解。P172 65解：此题满足标准指派问题的三个条件，直接用匈牙利法求解如下： 即解矩阵为指派方案为：机床1加工零件2，机床2加工零件3，机床3加工零件5，机床4加工零件1，机床5加工零件4，总加工费用为：（元）P173 67解：（1）该指派问题要求目标函数最大化，根据匈牙利法适用的标准指派问题三必要条件应先化为最小化问题，记 即解矩阵为 指派方案为：甲翻译德文，乙翻译日文，丙翻译法文，丁翻译俄文，戊翻译英文，总翻译效率为：（印刷符号/小时）（2）由于甲不能胜任翻译德文，乙不能胜任翻译日文，效益矩阵变化为： 即解矩阵为 指派方案为：甲翻译日文，乙翻译德文，丙翻译法文，丁翻译俄文，戊翻译英文，总翻译效率为：（印刷符号/小时）第8章 网络分析P232 81 解：（1）不连通图（2）真子图，是的真子图。支撑子图，是的支撑子图。（3） 开链、简单链 开链、简单链、初等链 闭链、简单链、圈 闭链、简单链、圈 闭链、简单链、圈 开链P233 85 （a）（b）（c）解：（a）1246735（b）13478652（c）14235971086P233 87 （a）解：s25t4163点到各点的最短路为：，路长为6，路长为2，路长为8，路长为6，路长为3P234 89 解：距离矩阵为 （1）各点到点的最短路即：最短路最短距离351340（2）点到各点的最短路即：最短路最短距离0213P234 811 解：截量67758则最大流量为： 该网络的最小截集为： P235 812 （a）s143t2761336415423 则最大流量为： 该网络的最小截集为： P235 812 （b）5s143t291310554649t54 则最大流量为： 该网络的最小截集为： - 33 -