运筹学习题参考答案.doc

习题参考答案第二章 习 题1.线性规划模型为：2. 标准形式为：3.（1）最优解为（2,2），最优值为8.（2）根据等式约束得：代入规划等价于：先用图解法求线性规划得最优解为（0,6）代入原规划可得最优解为（0,6,0）最优值为18.4.（1）以为基变量可得基可行解（3,1,0），对应的基阵为：以为基变量可得基可行解（2,0,1），对应的基阵为：（2）规划转化为标准形式：以为基变量可得基可行解（0,1,4,0），对应的基阵为：5. 以为基变量可得基可行解（0,2,3,9），对应的典式为：非基变量的检验数为。6. (1) a=0,b=3,c=1,d=0;(2) 基可行解为(0,0,1,6,2)（3）最优值为3.7.（1）最优解为（1.6,0,1.2），最优值为-4.4； （2）令，则，在规划中用替代，并化标准形式。最优解为（1,0,1），最优值为3；（3）无最优解（4）最优解为（0,3,1）最优值为7.8.（1）最优解为（2,0,0），最优值为4； （2）无最优解（3）最优解为（0,0,4），最优值为4；（4）没可行解。9.（1）最优解为（3,0,0），最优值为-15；（2）允许增加值是2，允许减少值是6，在区间（0,8）内取值最优基不变。（3）最优解变为（2,0,0），最优值变为-10；（4）最优解为（0,0,2），最优值为-16；（5）最优解为（2,0,0），最优值变为-10。10.模型输入如下：model:min=-5*x1+8*x2+4*x3+6*x4+2*x5;x1+2*x2+2*x3+x4-x5=4;-x1+2*x2-2*x3+x42;free(x1);bnd(-2,x5,8);end第三章 习 题1. 2. 3. 4.（1）最优解为（8,0），最优值为-16；（2）最优解为（2,2），最优值为12；（3）最优解为（6,0,0），最优值为12；(4) 最优解为（2,2.5），最优值为-16.5；5. model:min=3*x1+2*x2+4*x3+6*x4+2*x5;2*x1+x2+2*x3+x4-x5=4;-2*x1+x2-2*x3+x42;GIN(x1);GIN(x2);bin(x5);end第四章 习 题1. 阶段数：4状态变量：每个季度开始时的存储量, 最大值为1600；决策变量：每个季度的生产量；状态转移关系：用表示第个季度的销售量，则该季度末的库存量为显然第季度初的存储量等于前一季度末的存储量，有：根据库存限制可以得出决策变量的取值范围，即：获得函数：当季成本=生产成本+存储成本=设表示第季初库存为时，经过第季度及以后各季度的最优成本，则显然有：最后一季度的函数为：2. 表示第i个点到点A的最短路程，则 最短路长度为26，最短路为：A-B1-C1-D2-E2-F3最优方案是物品1装5个，物品2装0个，物品3装0个，最大价值为60.4求最小旅行费用周游线路，表4-14是5个城市中从城市i到城市j的费用。注意其中两个城市之间往返的费用是不相等的。表4-5 5个城市间的费用表 ji123451911782136124310859471262512943第五章 多目标规划1 设表示第i个项目是否投资，如果投资为1，否则取值为0，则对应的多目标规划为：该问题要求建立多目标规划模型，不要求求解。2. 求解以下多目标规划的有效解和弱有效解。CBA第一个目标的最优解在点A处为两条直线的交点，解方程组：得最优解为.第二个目标的最优解为x轴上点B（2,0）和点C（4,0）的一部分。所以有效解的集合为，弱有效解除了有效解外还包括集合，即弱有效解集合为。3第一个目标的最优值为13，第二个目标在第一个目标最优的基础上的最优解为（0,2.5,5.5），最优值为-5.4设两种产品正常生产的产量分别为，加班生产的产量为，问题的硬约束为有效工时限制和加班工时限制，即： 目标函数为。由于加班生产的利润低于正常生产的利润，所以最优解自然满足当正常生产的工时有剩余时加班生产的工时为0.对应的规划为：利润最大为576.同时软约束为:利润大于等于576，加班时间不超过50小时，产品A的产量不低于产品B产量的2/3，即：根据题意第一个软约束的目标优先级要大于等于后两个，对应的目的规划为：5.计算下列判别矩阵的权重、并做一致性检验权重为（0.324259，0.116036,0.103216,0.456489）一致性检验系数为0.96093，通过检验。第六章 图与网络优化1.最小支撑树如下图加粗线所示：4351267687662332341最小树权重为23.2 （1）最短路如下图加粗线所示：752267213642345671图6-40 网络图最短路长度为10.（2）最短路如下图加粗线所示：4523132175362345671最短路长度为8.3找增广路标号如下：6,65,43,25,44,43,23,27,61,02,2123456-4,1+1,1+2,1+3,1-新可行流为：6,65,53,35,54,43,13,27,61,02,2123456-该可行流没有增广路，就是最大流，最大流流量为11。4最大流如下图所示：4,46,47,5131,12,1225,54,45,42345671图6-43网络图5顶点标号为：115,33,42,43,43,32,66,41,32,512345603477最小费用流为：5,23,22,23,33,326,312,123456对应的费用为56。第七章 网络计划技术1.网络计划图为：02489ACDGEFB92. 诊断下列网络计划图是否正确G100642ABCD8EF12IH1614JK18节点12和节点18都没有没有后续节点，出现两个结束时刻，所以是错误的。3 根据下列网络计划图，写出工程工作的紧前关系。026489ABCDEF图7-27 网络计划图紧前关系如下：工作ABCDEF作业时间2102210203紧前工作无无A BB CD4.该工程的关键线路为A-C-E-G-H-I,最短工期为60.5.网络计划图为：026489ABCDEF9G9H99JKI关键线路为：A-B-C-D-G-H-J-K.最短工期为：50试计算出该工程的最短工期。6 由于工作C的紧前工作为A和B，该工程的紧前关系等价于：表7-9 工程的紧前关系工作ABCDEFGH作业时间1215221020132415紧前工作无无A BCCE DCD G网络计划图为：174235ABCDEFH6G设每个节点出现时间分别为，则有规划：其最短工期为：76.设每个工作的赶工时间为，为了便于管理要求赶工时间为整数。则赶工的规划模型为：计算可得工期可以缩短到62天，其中工作B赶工3天，工作C赶工6天，工作G赶工1天，工作H赶工4天。第八章 运输问题1把三个产品作为三个供给方，三个百货商店作为需求方，由于丙百货商店要求至少供应C玩具1000件，可以先满足这些需求，安排丙百货商店1000件C玩具，丙百货商店剩余需求为500件。C玩具剩余供量为1000件。问题的目标是要求总盈利额最大，而运输问题的目标是运输总成本最小。记每个商店销售不同玩具的盈利额为，则总的盈利额为。由于运到三个百货店的总量是3500件，如果用一个常数d减去每个商店销售不同商品的盈利额，则有：因而求总的盈利额最大等价于求达到最小，可以把看成单位运输费用，就是总费用。d可以取任意大于16的常数，这里取d=20.同时丙百货商店要拒绝进A玩具，设对应的运输费用为足够大的整数，这里取100.所以对应的运输问题为：甲乙丙可供量412112000C81091000需求供给为4000件，总需求为3500件，供给大于需求，增加新的虚拟需求点，需求量为500件。甲乙丙可供量A151610001000B4121102000C810901000需求量15001500500500求解该运输问题的最优方案就是总盈利额最大的方案。本题主要掌握转化过程，不要求求解。2求总运费最小的运输问题，其中某一步的运输图见表8-30。表8-36 解题过程B1B2B3供应量A13(3)(5)(7)3A22(4)4(2)(4)6A3(5)1(6)5(3)d需要量abce (1) 写出a=5，b=5，c=5，d=6，e=15的值，并求出最优运输方案。最优方案为：3B11B21B3供应量0A13(3)(5)4(7)631A21(4)5(2)(4)262A31(5) (6)35(3)6需要量555e(2)当A3到B1的单位运费大于等于8时，表中运输方案为最优方案3初始方案为：表8-37 运输问题数据单位运输费用B1B2B3供应量A1150150A230170200A350200250需要量1802202004. 用最小元素法给出下列运输问题的初始方案：表8-38 运输问题数据单位运输费用B1B2B3供应量A1150150A218020200A3502002505050需要量1802202505.用最小元素法求初始方案为：单位运输费用B1B2B3B4供应量A150200250A228020300A3150100250需要量280220200100A1 B1回路改变费用为3-3+4-1=3A1 B4回路改变费用为2-3+2-1=0A2 B3回路改变费用为2-4+3-1=0A2 B4回路改变费用为4-4+2-1=1A3 B1回路改变费用为2-1+4-2=3A3 B3回路改变费用为5-2+3-1=5所有非数字格的费用改变量都大于等于0，所以该方案是最优方案，最少运费为1110.6. 用位势法计算下列运输问题：供需不平衡，增加虚拟需求点表8-40 运输问题数据单位运输费用B1B2B3供应量A12340150A21220200A33210250需要最小元素法求初始方案单位运输费用B1B2B3供应量A110050150A218020200A3100150250需要位势为：单位运输费用2B13B22B30供应量0A110050150-1A218020200-1A3100150250需要数字格的费用改变量为：单位运输费用2B13B22B30供应量0A102150-1A211200-1A321250需要数字格的费用改变量都大于等于0，该方案为最优方案，对应的运输费用为870.第九章 排队论1该系统是M/M/1系统，其中，修理店空闲的概率在店内的平均顾客数顾客在店内的平均逗留时间等待服务的平均顾客数平均等待修理的时间2该系统是M/M/1系统，