管理运筹学 电子版清华版 运筹学（第三版 上）课后习题详解、配套参考书

1 绪论 1、运筹学的内涵 答：本书将运筹学定义为：“通过构建、求解 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 模型，规划、优化有限资源的合理利用，为科学决策提供量化依据的系统知识体系。” 2、运筹学的工作过程 答： （1）提出和形成问题。即要弄清问题的目标、可能的约束、可控变量、有关的参数以及搜索有关信息资料。 （2）建立模型。即要把问题中的决策变量、参数和目标、约束之间的关系用一定的模型 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示出来。 （3）求解模型。根据模型的性质，选择相应的求解方法，求得最优或者满意解，解的精度要求可由决策者提出。 （4）解的检验和转译。首先检查求解过程是否有误，然后再检查解是否反映客观实际。如果所得之解不能较好地反映实际问题，必须返回第（1）步修改模型，重新求解；如果所得之解能较好地反映实际问题，也必须仔细将模型结论转译成现实结论。 （5）解的实施。实施过程必须考虑解的应用范围及对各主要因素的敏感程度，向决策者讲清楚用法，以及在实施中可能产生的问题和修改的方法。 3、数学模型及其三要素 答：数学模型可以简单的描述为：用字母、数字和运算符来精确地反映变量之间相互关系的式子或式子组。数学模型由决策变量、约束条件和目标函数三个要素构成。决策变量即问题中所求的未知的量，约束条件是决策所面临的限制条件，目标函数则是衡量决策效益的数量指标。 2 线性规划 1、试述线性规划数学模型的组成部分及其特性 答：线性规划数学模型由决策变量、约束条件和目标函数三个部分组成。 线性规划数学模型特征： （1） 用一组决策变量表示某一方案，这组决策变量均为非负的连续变量； （2） 存在一定数量（m）的约束条件，这些约束条件可以用关于决策变量的一组线性等式或者不等式来加以表示； （3） 有一个可以用决策变量加以表示的目标函数，而该函数是一个线性函数。 2、一家餐厅24小时全天候营业，在各时间段中所需要的服务员数量分别为： 2：00~6：00 3人 6：00~10：00 9人 10：00~14：00 12人 14：00~18：00 5人 18：00~22：00 18人 22：00~ 2：00 4人 设服务员在各时间段的开始时点上上班并连续工作八小时，问该餐厅至少配备多少服务员，才能满足各个时间段对人员的需要。试构造此问题的数学模型。 解：用决策变量 , , , , , 分别表示2：00~6：00， 6：00~10：00 ，10：00~14：00 ，14：00~18：00，18：00~22：00， 22：00~ 2：00 时间段的服务员人数。 其数学模型可以表述为： 3、现要截取2.9米、2.1米和1.5米的元钢各100根，已知原材料的长度是7.4米，问应如何下料，才能使所消耗的原材料最省。试构造此问题的数学模型。 解：圆钢的截取有不同的方案，用θ表示每种切割方案的剩余材料。其切割方案如下所示： 2.9 2.1 1.5 θ 1' 1 1 1 0.9 2' 2 0 0 0.1 3' 1 2 0 0.3 4' 1 0 3 0 5' 0 1 3 0.8 6' 0 0 4 1.4 7' 0 2 2 0.2 8' 0 3 0 1.1 目标函数为求所剩余的材料最少，即 4、某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C三种原料的含量要求、各种原料的单位成本、各种原料每月的限制用量、三种牌号糖果的单位加工费及售价如表1所示。问该厂每月生产这三种牌号糖果各多少千克，才能使该厂获利最大？试建立这个问题的线性规划模型。 表1 甲 乙 丙 原料成本 限制用量 A 60%以上 15%以上 2.00 2000 B 1.50 2500 C 20%以下 60%以下 50%以下 1.00 1200 加工费 0.50 0.40 0.30 售 价 3.40 2.85 2.25 解：以 表示甲产品中的A成分， 表示甲产品中的B成分， 表示甲产品中的C成分，依此类推。据表2-16，有： ， ， ， ， ．．．．．．① 其中： ， ， ．．．．．．② 把②逐个代入①并整理得： ， ， ， 原材料的限制，有以下不等式成立： ， ， 在约束条件中共有9个变量，为方便计算，分别用 , ．．． 表示，即令 = ， = ， = ， = ， = ， = ， = ， = ， = 由此约束条件可以表示为： 我们的目的是使利润最大，即产品售价减加工费再减去原材料的价格为最大。 目标函数为 5、某厂在今后4个月内需租用仓库存放物资，已知各个月所需的仓库面积如表2所示。租金与租借 合同 劳动合同范本免费下载装修合同范本免费下载租赁合同免费下载房屋买卖合同下载劳务合同范本下载 的长短有关，租用的时间越长，享受的优惠越大，具体数字见表3。租借仓库的合同每月初都可办理，每份合同具体 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 租用面积数和期限。因此该厂可根据需要在任何一个月初办理租借合同，且每次办理时，可签一份，也可同时签若干份租用面积和租借期限不同的合同，总的目标是使所付的租借费用最小。试根据上述要求，建立一个线性规划的数学模型。 表2 月 份 1 2 3 4 所需面积（100m2） 15 10 20 12 表3 合同租借期限 1个月 2个月 3个月 4个月 单位（100m2）租金（元） 2800 4500 6000 7300 解：设 （i＝1,2,3,4;j=1,2．．．4-i+1）为第i个月初签订的租借期限为j个月的合同租借面积（单位：100 ）； 表示第i个月所需的面积（j表示每100 仓库面积租借期为j个月的租借费）；则线性规划模型为： 6、某农场有100公顷土地及25万元资金可用于发展生产。农场劳动力情况为秋冬季4500人日，春夏季6000人日，如劳动力本身过剩可外出打工，春夏季收入为20元／人日，秋冬季12元／人日。该农场种植三种作物：大豆、玉米和小麦，并饲养奶牛和鸡。种作物不需要专门投资，而饲养动物时每头奶牛投资8000元，每只鸡投资2元。养奶牛时每头需拨出1.5公顷土地种饲草，并占用人工秋冬季为100人日，春夏季为50人日，年净收入3000元／每头奶牛。养鸡不占土地，需人工为每只鸡秋冬季0.3人日，春夏季0.1人日，年净收入为每只8元。农场现有鸡舍允许最多养5000只鸡，牛栏允许最多养50头奶牛，三种作物每年需要的人工及收入情况如表4所示。试决定该农场的经营方案，使年净收入最大。 表4 大豆 玉米 麦子 每公顷秋冬季所需人日数 20 35 10 每公顷春夏季所需人日数 50 75 40 年净收入（元/公顷） 1100 1500 900 解：设 , , 分别代表大豆、玉米、麦子的种植数（公顷）； , 分别代表奶牛和鸡的饲养数； , 分别代表秋冬季和春夏季多余的劳动力（人．日数）则有 7、用图解法求解下列线性规划问题 （1） （2） （3） （4） 解： （1） （2） （3） （4） 8、考虑线性规划： + + + = 5 + + = 2 2 + + + = 6 （1） 通过观察写出初始的基可行解并构造初始单纯形表； （2） 在保持 和 为零的情况下，给出非基变量 增加一个单位时的可行解，并指出目标函数的净增量是多少? （3） 在模型约束条件的限制下， 的最大增量是多少？ （4） 在 有其最大增量时，给出一个新的基可行解。 解：（1）因存在初始可行基 ，故可令 , , 全为0,则可得初始可行解为 ，Z＝5。 初始单纯行表为： cj 2 -1 1 1 0 0 CB XB x1 x2 x3 x4 x5 x6 1 0 0 x4 x5 x6 -1 1 1 1 0 0 1 1 0 0 1 0 2 1 1 0 0 1 5 2 6 (j 3 -2 0 0 0 0 z=0 (2)非基变量 , 仍然取零， 由0变为1,即 ＝1, ＝0, =0,代入约束条件得一个可行解X= 。其目标函数值为Z＝8 因此，随着 增加1个单位目标函数值的净增量为△Z＝8-5=3. （3）因为决策变量全非负所以由约束条件①知 增加可以引起 , , 增加，即条件①对 无约束；由约束条件②知 增加可引起 , 减少，由非负约束知 最大增量为2；同理可得约束条件③的 最大增量为3，综合得 的最大增量为2。 （4） ＝2，非基变量 =0, ＝0,代入约束条件得基可行解X= ，目标函数值为Z＝11。 9、将线性规划模型转化为标准形式 ， 无约束 解：（1）令 ＝ － 并代入模型，这里 >=0, >=0； （2）第二个约束条件方程两侧同乘“-1”； （3）第一个约束条件引入松弛变量 ，第三个约束条件引入 作为松弛变量。 （4）目标函数同乘“-1”，即可实现最少化。 10、用单纯形法求解下述线性规划问题 （1） （2） + 2 + 18 + 4 + 5 （1）解：构造初始单纯行表，并进行初等变换，得： cj 3 1 1 1 CB XB x1 x2 x3 x4 1 1 x3 x4 -2 （2） 1 0 3 1 0 1 4 6 (j 2 -2 0 0 w=10 1 1 x2 x4 -1 1 1/2 0 4 0 -1/2 1 2 4 (j 0 0 1 0 w=6 最优解 ，由非基变量 的检验数为0,知此问题有无穷多最有解，所以该解为无穷多最优解中的一个，最优值为w＝6。 （2）解：此问题用大M法求解，先把问题标准化为： 构造初始单纯行表，并进行初等变换，得： cj -4 -5 -1 0 0 M M CB XB x1 x2 x3 x4 x5 x6 x7 M 0 M x6 x5 x7 3 2 1 -1 0 1 0 (2) 1 0 0 1 0 0 1 1 -1 0 0 0 1 18 4 5 (j -4-4M -5-3M -1 M 0 0 0 M -4 M x6 x1 x7 0 1/2 1 -1 -2/3 1 0 1 (1/2 ) 0 0 1/2 0 0 0 1/2 -1 0 -1/2 0 1 12 2 3 (j 0 -5 -1 M 2M+2 0 0 M -5 M x6 x2 x7 -1 0 (1) -1 -2 1 0 2 1 0 0 1 0 0 -1 0 -1 0 -1 0 1 10 4 1 (j 2M-4 0 -1 M 3M+5 0 0 -1 -5 M x3 x2 x7 -1 0 1 -1 -2 1 0 2 1 0 0 1 0 0 -2 0 0 -1 -3 1 1 10 4 11 (j 2M+5 0 0 M-1 3M+3 1 0 因为所有检验数均为非负，但人工变量 仍为基变量，故此问题无解。 11、求解线性规划问题并给出其中三个最优解： 解：构造初始单纯行表，并进行初等变换，得： cj 3 1 1 1 CB XB x1 x2 x3 x4 1 1 x3 x4 -2 （2） 1 0 3 1 0 1 4 6 (j 2 -2 0 0 w=10 1 1 x2 x4 -1 1 1/2 0 (4 ) 0 -1/2 1 2 4 (j 0 0 1 0 w=6 1 3 x2 x1 0 1 3/8 1/4 1 0 -1/8 1/4 3 1 (j 0 0 1 0 w=6 从单纯形表可以找到两个顶点， ， 。可以找到变量之间存在以下关系： ＝ ＋2； ＝－4 ＋4； 令 ＝1/2则有 ，从而找到了LP问题的三个最优解。 12、（1）如为唯一最优解则要求非基变量的检验数全少于零，从而有 <0， <0。并且要令表中的解为最优解，则要求原问题可行，这只要满足 即可。 （2）要令表中解为无穷多最优解中的一个，则有以下关系成立： <=0， <=0，且 EMBED Equation.DSMT4 =0 若 =0，则 。 （3）要使表中的解为退化的基可行解，则必有 ；当 > 且 >0时， 。 （4）若为无界解，则满足能找到入基变量，但找不到出基变量的条件。即满足： ； > ，且 >0； 。 （5）以 代替 ，即 入基， 出基，则有以下关系成立： > ，且 >0； ； ，且 。 3 线性规划的对偶问题 1． 试从经济角度解释对偶变量的含义。 答：假设有一企业欲将另一个企业拥有的资源收买过来，至少应付出多少代价，才能使此企业愿意放弃生产活动，出让资源。显然后者放弃自己组织生产活动的条件时，对同等数量资源出让的代价不低于该企业自己组织生产活动是的产值。 2． 判断下列说法是否正确 （1） 任何线性规划问题都存在其对偶问题 （正确） （2） 如果原问题存在可行解，则其对偶问题也一定存在可行解；（错） （3） 当原问题为无界解时，对偶问题也为无界解；（错） （4） 当对偶问题无可行解时，原问题一定具有无界解；（错） （5） 若原问题有无穷多最优解，则对偶问题也一定具有无穷多最优解 （错） 3写出下列线性规划问题的对偶问题： （1） + 2 + 2 2 + +3 6 +4 +6 5 解： （2） + 2 + 10 3 +2 15 +2 + 12 无约束 解： 4. 用对偶单纯形法求解下述线性规划问题 （1） （2） +3 3 +2 +2 +3 EMBED Equation.3 30 2 +2 5 2 + +3 +2 EMBED Equation.3 20 （1） 转换化成标准形式： cj 4 12 18 0 0 CB XB x1 x2 x3 x4 x5 0 0 x4 x5 -1 0 -3 1 0 0 -2 -2 0 1 -3 -5 (j 4 12 18 0 0 18 12 x3 x2 1/3 0 1 -11/3 0 -1/3 1 0 1/3 -1/2 1 2/3 (j 2 0 10 2 6 W=36 X=(0,2/3,1,0,0) (2)转化为标准形式 EMBED Equation.DSMT4 cj 1 2 3 4 0 0 CB XB x1 x2 x3 x4 x5 x6 0 0 x5 x6 -1 -2 -2 -3 1 0 -2 -1 -3 -2 0 1 -30 -20 (j 1 2 3 4 0 0 1 0 x1 x6 1 2 2 3 -1 0 0 3 1 4 -2 1 1 2/3 (j 0 0 1 1 1 0 W=30 X＝(30,0,0,0,0,40) minz=30 5 （1）由最终单纯形表可知，为保持原最优解不变应有： 解不等式组得：C (2)将C1=2直接反映进单纯形表中： cj -2 -1 -5 0 0 CB XB x1 x2 x3 x4 x5 -2 -5 x1 x3 1 -1/3 0 1/3 -1/3 0 1 1 -1/5 2/5 5 3 (j 0 10/3 0 -1/3 4/3 0 -5 x4 x3 3 -1 0 1 -1 3/5 4/5 1 0 1/5 15 6 (j 1 3 0 5 1 -30 X=(0,0,6,15,0) max z=30 (3)因为原材料的市场价格0.8小于原材料的影子价格1，所以，可以买进原材料。假设买进原材料100单位，则此公司拥有原材料的总额为130。 b´＝ 将b´反映进单纯形表中： cj -3 -1 -5 0 0 CB XB x1 x2 x3 x4 x5 -3 -5 x1 x3 1 -1/3 0 1/3 -1/3 0 1 1 -1/5 2/5 85/3 111 (j 0 3 0 0 1 w=-30 最终的单纯形表 cj -3 -1 -5 0 0 CB XB x1 x2 x3 x4 x5 -5 0 x3 x5 6/5 3/5 1 1/5 0 -3 1 0 -1 1 9 85 (j 3 2 0 1 0 w=-45 (4) 为非基变量， 所以，最优解不变。 （5）将原问题的最优解X=（5，0，3，0，0）代入不等式 中，不等式仍然成立，故最优解不变。 （6）将原问题的最优解X=（5，0，3，0，0）代入不等式 中，不等式不成立，所以最优解将发生变化。将新的约束条件反映进单纯形表中： cj -3 -1 -5 0 0 0 CB XB x1 x2 x3 x4 x5 x6 -3 -5 0 x1 x3 x6 1 -1/3 0 1/3 -1/3 0 0 1 1 -1/5 2/5 0 3 1 2 0 0 1 5 3 20 -3 -5 0 x1 x3 x6 1 -1/3 0 1/3 -1/3 0 0 1 1 -1/5 2/5 0 0 0 0 -3/5 1/5 1 5 3 20 (j 0 3 0 0 1 0 w=-30 最终单纯形表为： cj -3 -1 -5 0 0 0 CB XB x1 x2 x3 x4 x5 x6 -3 -5 0 x1 x3 x4 1 -1/3 0 0 -2/9 5/9 0 1 1 0 1/3 -1/3 0 0 0 0 -1/3 -5/3 40/9 8/3 5/3 (j 0 3 0 0 1 0 w=-80/3 （40/9，0，8/3，5/3，0，0） Maxz=80/3 4 运输问题 1、运输问题表上作业法的基本步骤。 答：表上作业法的基本步骤可参照单纯形法归纳如下： （1）找出初始基可行解：即要在 阶产销平衡表上给出“ ”个数字格（基变量）； （2）求各非基变量（空格）的检验数，判断当前的基可行解是否是最优解，如已得到最优解，则停止计算，否则转到下一步； (3)确定入基变量，若 ，那么选取 为入基变量； (4)确定出基变量，找出入基变量的闭合回路，在闭合回路上最大限度地增加入基变量的值，那么闭合回路上首先减少为“0”的基变量即为出基变量； （5）在表上用闭合回路法调整运输方案； （6）重复2、3、4、5步骤，直到得到最优解。 2、“最小元素法”和“伏格尔”法的基本思想及基本操作。 答：最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定产销关系，依此类推，一直到给出基本方案为止。 伏格尔法把费用增量定义为给定行或列次小元素与最小元素的差（如果存在两个或两个以上的最小元素费用增量定义为零）。最大差对应的行或列中的最小元素确定了产品的供应关系，即优先避免最大的费用增量发生。当产地或销地中的一方在数量上供应完毕或得到满足时，划去运价表中对应的行或列，再重复上述步骤，即可得到一个初始的基可行解。 3、闭合回路的构成以及利用闭合回路法求检验数的基本操作。 答：判断基可行解的最优性，需计算空格（非基变量）的检验数。闭合回路法即通过闭合回路求空格检验数的方法。从给定的初始方案的任一空格出发寻找闭合回路，闭合回路顶点所在格括号内的数字是相应的单位运价，单位运价前的“+”、“-”号表示运量的调整方向。 空格处单位运量调整所引起的运费增量就是空格的检验数。仿照此步骤可以计算初始方案中所有空格的检验数。 4、利用位势法求检验数以及利用闭合回路进行方案调整的基本操作。 答：位势法求解非基变量检验数的基本步骤： 第一步：把方案表中基变量格填入其相应的运价并令 ；让每一个基变量 都有 ，可求得所有的位势； 第二步：利用 计算各非基变量 的检验数 方案的优化基本步骤： 在负检验数中找出最小的检验数，该检验数所对应的变量即为入基变量。在入基变量所处的闭合回路上，赋予入基变量最大的增量，即可完成方案的优化。在入基变量有最大增量的同时，一定存在原来的某一基变量减少为“0”，该变量即为出基变量。切记出基变量的“0”运量要用“空格”来表示，而不能留有“0”。 5、某玩具公司生产A、B、C三种玩具，每月的生产能力分别为1000、2000和2000件。玩具被运至甲、乙、丙三个百货商店销售。已知各家百货商店每月对三种型号玩具的总销量都是1500件，由于经营环境的原因，各商店销售不同型号玩具的盈利不同，具体数据见表1。又已知丙商店要求至少供应1000件C型玩具且拒绝A型玩具。求能够满足上述条件而又使总盈利最大的供销分配方案。 表1 甲 乙 丙 A 5 4 0 B 16 8 9 C 12 10 11 解：此题属于产大于销问题，可以增加假想的需求部门丁，使供需平衡。由于部门丁不存在，故其盈利都为0。供需平衡表示如下所示： 甲 乙 丙 丁 产量 A 5 4 0 0 1000 B 16 8 9 0 2000 C 12 10 11 0 2000 销量 1500 1500 1500 500 因为原问题为求最大值，故用类伏格尔法（求两最大元素之差，其他步骤相同）求解问题的初始可行基，得 甲 乙 丙 丁 产量 A 500 500 1000 B 1500 500 2000 C 500 1500 2000 销量 1500 1500 1500 500 用位势法进行检验得： 甲 乙 丙 丁 A （-7） 4 （-5） 0 0 B 16 8 （0） （-4） 4 C （-6） 10 11 （-6） 6 12 4 5 0 非基变量检验数全为非负，说明所得初始可行基已为最优解。 表中将A调拨给丁500件，表明玩具A有500件销售不出去。 6、已知某厂每月最多生产甲产品270吨，先运至A1、A2、A3三个仓库，然后再分别供应B1、B2、B3、B4、B5五个用户。已知三个仓库的容量分别为50、100和150吨，各用户的需要量分别为25、105、60、30和70吨。已知从该厂经由各仓库然后供应各用户的储存和运输费用如表2所示。试确定一个使总费用最低的调运方案。 表2 B1 B2 B3 B4 B5 A1 10 15 20 20 40 A2 20 40 15 30 30 A3 30 35 40 55 25 解：此题属于产销不平衡问题，仓库的总存储能力为300t，用户总需求量为290t，但该厂的最大生产能力为270t。故仓库有30t剩余，用户有20t得不到满足，故可假设存在仓库A4 ，它的存储量为20t，用户B6 的需求量为30t。这样就转化为产销平衡问题。与因A4 与B6都是假设的，不需要运输，故运价都为0，但是由A4 运到B6的运输无法发生，因两者皆为假设的，运价为无穷大，设为M。 得到产销平衡表如下所示： B1 B2 B3 B4 B5 B6 产量 A1 10 15 20 20 40 0 50 A2 20 40 15 30 30 0 100 A3 30 35 40 55 25 0 150 A4 0 0 0 0 0 M 20 销量 25 105 60 30 70 30 用伏格尔法求解初始基可行解得： B1 B2 B3 B4 B5 B6 产量 A1 50 50 A2 25 45 30 100 A3 10 60 50 30 150 A4 20 20 销量 25 105 60 30 70 30 用位势法检验是否为最优解，得： B1 B2 B3 B4 B5 B6 A1 （15） 15 (0) (15) (35) (20) 0 A2 20 40 (-30) 30 (0) (-5) 25 A3 (15) 35 40 (30) 25 0 20 A4 (10) (-10) (-15) (0) 0 (M+25) -5 -5 15 20 5 5 -20 因检验数存在负数，故用闭合回路法调整得： B1 B2 B3 B4 B5 B6 产量 A1 50 50 A2 25 60 15 100 A3 50 60 70 30 150 A4 5 15 20 销量 25 105 60 30 70 30 用位势法检验得： B1 B2 B3 B4 B5 B6 A1 （5） 15 (20) (5) (35) (20) 0 A2 20 （10） 15 30 (10) (5) 15 A3 (5) 35 （20） (20) 25 0 20 A4 (10) 0 (15) 0 (10) (M+35) -15 5 15 0 15 5 -20 因检验数全为正，所以已得最优方案。 即A3差30t没有得到满足， B2缺5t，B4缺15t。 7、已知某运输问题的单位运价及最优调运方案如表3所示（括号中的数据代表运输数量），由于产地A2至销地B2的道路关闭，故最优调运方案将发生变化，试在原最优调运方案的基础上，寻找新的最优调运方案。 表3 B1 B2 B3 B4 B5 ai A1 10 20 5（4） 9（5） 10 9 A2 2 10（4） 10 30 6 4 A3 1（3） 20（1） 7 10（1） 4（3） 8 bj 3 5 4 6 3 解：由于A2 到B2道路关闭，则其运价为M，应令其出基，以实现最优调度。先将M反映进产销平衡表，然后用位势法作检验，有： B1 B2 B3 B4 B5 A1 （10） （1） 5 9 (7) 0 A2 （21-M） M (24-M) （40-M） (22-M) M-19 A3 1 20 （1） 10 4 1 0 19 5 9 3 要令A2 B2出基，即令其运输量为0，找出负检验数最小的来进行调整，得： B1 B2 B3 B4 B5 产量 A1 4 5 9 A2 3 1 4 A3 5 1 2 8 销量 3 5 4 6 3 用位势法作检验，有： B1 B2 B3 B4 B5 A1 （11） （1） 5 9 (7) 0 A2 2 （M-22） (2) （18） 6 3 A3 （1） 20 （1） 10 4 1 -1 19 5 9 3 检验数已全为非负，故已得最优调度方案。 8、已知某运输问题的单位运价及最优调运方案如表4所示，试回答下述问题： 表4 B1 B2 B3 B4 B5 B6 ai A1 2（20） 1（30） 3 3 3 5 50 A2 4 2（20） 2（20） 4 4 4 40 A3 3（10） 5 4 2（39） 4 1（11） 60 A4 4 2 2 1（1） 2（30） 2 31 bj 30 50 20 40 30 11 （1） A1到B2、A3到B5、和A4到B1的单位运价，分别在什么范围内变化时上表中给出的最优方案不变； （2） 若A1到B2的单位运价由1变为3，最优方案将发生怎样的变化； （3） 若A3到B5的单位运价由4变为2，最优方案将发生怎样的变化； 解：（1）设A1 到B2的单位运价为x，因A1 到B2是基变量，它的运价变化会引起非基变量检验系数的变化，此时，只需对其再进行位势法 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 即可。 B1 B2 B3 B4 B5 B6 A1 2 x (3-x) (2) (1) (5) 0 A2 （x） 2 2 （20） (1+x) (2+x) 2-x A3 3 （4-x） （3-x） 2 （1） 1 1 A4 (x) (2-x) (1) 1 2 (2) 0 2 x x 1 2 0 要令最优方案不变，则非基变量的检验数非负； 故有x>=0；3-x>=0；4-x>=0；2-x>=0；2+x>=0；1+x>=0 解上述不等式得0<=x<=2。即A1 到B2的单位运价在[0，2]内变化时，最有方案不变。 A3 到B5的单位运价属于非基变量，它的变化不会引起其它检验数变化，故只需保证其检验数非负即可。 先用位势法算出原方案的检验数： B1 B2 B3 B4 B5 B6 A1 2 1 (2) (2) (1) (5) 0 A2 （1） 2 2 （3） (1) (3) 1 A3 3 （3） （2） 2 （1） 1 1 A4 (2) (1) (1) 1 2 (2) 0 2 1 1 1 2 0 设A3 到B5的单位运价为x，则其检验数满足x-（1+2）>=0，即x>=3。也就是说A3 到B5的单位运价大于等于3时，最有方案不变。 同理可以算出A4 到B1的单位运价变化范围是[2，+∞)，此时最优方案不变。 （2）把变化直接反映到表中可得下表： B1 B2 B3 B4 B5 B6 A1 2 3 (0) (2) (1) (5) 0 A2 （3） 2 2 （20） (4) (5) -1 A3 3 （1） （0） 2 （1） 1 1 A4 (3) (-1) (1) 1 2 (2) 0 2 3 3 1 2 0 因存在检验数为负数，最优方案发生改变，用闭合回路法调整得： B1 B2 B3 B4 B5 B6 ai A1 21 29 50 A2 20 20 40 A3 9 40 11 60 A4 1 30 31 bj 30 50 20 40 30 11 重新计算检验数，得： B1 B2 B3 B4 B5 B6 A1 2 3 (0) (2) (0) (5) 0 A2 （3） 2 2 （4） (2) (5) -1 A3 3 （1） （0） 2 （0） 1 1 A4 (3) 2 (0) （1） 2 (3) -1 2 3 3 1 3 0 非基变量检验数均为非负，故为最优方案。 （3）把A3 到B5的单位运价改为2，然后求检验数得： B1 B2 B3 B4 B5 B6 A1 2 1 (2) (2) (1) (5) 0 A2 （1） 2 2 （3） (1) (3) 1 A3 3 （3） （2） 2 （-1） 1 1 A4 (2) (1) (1) 1 2 (2) 0 2 1 1 1 2 0 由于存在负检验数，故最优方案发生变化，此时用闭合回路法调整得： B1 B2 B3 B4 B5 B6 ai A1 20 30 50 A2 20 20 40 A3 10 9 30 11 60 A4 31 31 bj 30 50 20 40 30 11 重新计算检验数，得： B1 B2 B3 B4 B5 B6 A1 2 1 (0) (2) (0) (5) 0 A2 （3） 2 2 （4） (2) (5) -1 A3 3 （1） （0） 2 4 1 1 A4 (1) (-1) (-1) 1 （-1） (2) 0 2 3 3 1 3 0 检验数有负数，用闭合回路法调整得： B1 B2 B3 B4 B5 B6 ai A1 20 30 50 A2 20 20 40 A3 10 39 11 60 A4 1 30 31 bj 30 50 20 40 30 11 重新计算检验数，得： B1 B2 B3 B4 B5 B6 A1 2 1 (2) (2) (1) (5) 0 A2 （1） 2 2 （2） (1) (3) 1 A3 3 （3） （2） 2 （1） 1 1 A4 (2) (1) (1) 1 2 (2) 0 2 1 1 1 2 0 检验数全为非负，故已得最优方案。 5 整数规划 1、用分枝定界法求解下述整数规划问题 （1） （2） 且取整 且取整 解：（1）用单纯型法求得相应星星规划问题 ,最终单纯型表： cj 1 1 0 0 CB XB x1 x2 x3 x4 1 1 x1 x2 1 0 1/32 -3/32 0 1 1/16 25/48 3/2 10/3 (j 0 0 -3/16 -91/48 Z=5/29 即： = ， =29/5 在 基础上分别增加约束条件 EMBED Equation.DSMT4 1和 EMBED Equation.DSMT4 8，分别形成两个子线性规划 和 ： ： 14 + 9 51 14 + 51 -6 +3 1 -6 + 1 1 EMBED Equation.3 8 , , , , ≥0 , , , ≥0 求解 和 有： = =10/3 = =4 有最优解，又 ＜ ，故整数规划有最优值 =4， = 此题求解过程如下图： = ， =29/5 EMBED Equation.DSMT4 1 EMBED Equation.DSMT4 8 = =10/3 = =4 （2）定义相应线性规划 为： 解得： = ， =111/10 在 基础上分别增加约束条件 EMBED Equation.DSMT4 1和 EMBED Equation.DSMT4 2，分别形成两个子线性规划 和 ： ： 3 + 4 12 3 + 4 12 4 +2 9 4 +2 9 1 2 , ≥0 ≥0 求解得 ： = =43/4 = =19/2 在 基础上分别增加约束条件 EMBED Equation.DSMT4 2和 EMBED Equation.DSMT4 3，分别形成两个子线性规划 和 解得： = =10 无解 故： = =10 此题求解过程如 = ， =111/10 EMBED Equation.DSMT4 1 EMBED Equation.DSMT4 2 = =43/4 = =19/2 EMBED Equation.DSMT4 2 EMBED Equation.DSMT4 3 = =10 无可行解 2、某航空公司为满足客运量日益增长的需要，正考虑购置一批新的远程、中程及短程的喷气式客机。每架远程客机价格670万元，中程客机500万元，短程客机350万元。该公司现有资金12000万元可用于购买飞机。据估计年净利润（扣除成本）每架远程客机82万元，中程客机60万元，短程客机40万元。设该公司现有熟练驾驶员可用来配备30架新购飞机。维修设备足以维修新增加40架新的短程客机，每架中程客机维修量相当于4／3架短程客机，每架远程客机维修量相当于5／3架短程客机。为获取最大利润，该公司应购买各类客机各多少架? 解：设购买远程、中程及短程的喷气式客机数量分别为 ， ， ，数学模型如下： max z =82 +60 +40 解得： ，有最大利润1454元。 3、某市为方便学生，拟在新建的7个居民小区增设若干所学校。已知各备选校址代号及其能覆盖的居民小区编号如表1所示，问要覆盖所有居民小区至少应建多少所学校？对应的校址代号是哪些？ 表1 备选校址 A B C D E F 小区编号 1，5，7 1，2，5 1，3，5 2，4，5 3，6 4，6 解：对每一个学校定义一个变量 1，当某居民小区可由第j个学校负责 ＝ 0，当某居民小区不可由第j个学校负责 则对于第1个小区： 对于第2个小区： 对于第3个小区： 对于第4个小区： 对于第5个小区： 对于第6个小区： 对于第7个小区： Min z = 解得： =3 4、求解下述0-1规划问题 （1） （2） 解：（1）将0－1规划问题换形为： 取0或1 显然零解不满足，分枝： (2) 将0－1规划问题换形为： 显然零解不满足，分枝： 故 5、求解例5-3所述的0-1规划问题。 解：将0－1规划问题换形为： 显然零解不可行，用隐枚举法分枝定界： 6、有四项工作要甲、乙、丙、丁四个人去完成，每项工作只允许一个人去完成，每个人只完成其中一项工作。已知每个人完成各项工作的时间如表2所示，问应指派哪个人去完成哪项工作才能使总的消耗时间为最少？ 表2 工作1 工作2 工作3 工作4 甲 10 13 16 19 乙 14 18 17 13 丙 21 12 11 14 丁 14 16 18 12 解：变换系数矩阵： 0 2 6 9 1 4 4 0 10 0 0 3 2 3 6 0 找到独立零元素并在次变换： 0 2 6 10 0 3 3 0 10 0 0 4 1 2 5 0 最后得到下表中的独立零元素： （0） 0 4 10 0 1 1 （0） 12 0 （0） 6 1 （0） 3 0 故最优方案为：甲— ，乙— ，丙— ，丁— 此时总消耗时间最少。 7、甲、乙、丙、丁四人要去完成五项工作，每项工作只由一个人来完成，其中有一人兼做一项工作。试指出每个人去完成哪项（或哪两项）工作才能使总的消耗时间为最少?已知每个人完成各项工作的时间如表3所示。 甲 12 15 10 18 20 乙 8 12 20 14 11 丙 18 9 16 12 15 丁 20 22 15 10 12 解： 甲 12 15 10 18 20 乙 8 12 20 14 11 丙 18 9 16 12 15 丁 20 22 15 10 12 戊 8 9 10 10 11 变换系数矩阵： 2 5 0 8 8 0 4 12 6 1 9 0 7 3 4 10 12 5 0 0 0 1 2 2 1 得最终表： 3 5 （0） 8 8 （0） 3 11 5 0 10 (0) 7 3 4 11 12 7 (0) 0 0 0 1 1 (0) 故最优方案为：甲— ，乙— ，丙— ，丁— ,而乙或丁兼任 8、某电子系统由三种元件组成，为使系统正常运转，每个元件都必须工作良好。如一个或多个元件安装几个备用件将提高系统的可靠性。已知系统运转可靠性为各元件可靠性的乘积，而每一元件的可靠性则是备用件数量的函数，具体数值见表4。又三种元件的价格分别是20、30和40元，重量分别是2、4和6千克。已知全部备用件的费用预算限制为150元，重量限制为20千克，问每个元件各安装多少备件，才能使系统的可靠性最大。 表4 备用件数量 元件1 元件2 元件3 0 0.5 0.6 0.7 1 0.6 0.7 0.9 2 0.7 0.9 1.0 3 0.8 1.0 1.0 4 0.9 1.0 1.0 5 1.0 1.0 1.0 解：设元件1的备用件数从0到5分别位 ，元件2备用件数从0到3分别设为 ，因为在3时已达到最优，故不需再考虑备用件数位4、5的情况；同理设元件3的备用件数从0到2为 。 求解得： ，即元件1、2、3的备用件数分别为2、2、1。 第7章 动态规划 1、某公司打算向它的三个营业区增设6个销售店，每个营业区至少增设1个。各营业区每年增加的利润与增设的销售店个数有关，具体关系如表1所示。试规划各营业区应增设销售店的个数，以使公司总利润增加额最大。 表1 增设销售店个数 营业区A 营业区B 营业区C 1 100（万元） 120（万元） 150（万元） 2 160 150 165 3 190 170 175 4 200 180 190 解：阶段：将每个营业区作为一个阶段，即k=1,2,3 状态变量： 代表从第k各营业区到第3个营业区的店数 决策变量： 代表第k个营业区的销售店数 状态转移律： 边界条件： =6 =0 决策允许集合 阶段标准函数 当 时： 于是有下表2，表中 表示第三个阶段的最优决策。 表2 （单位：万元） 1 2 3 4 1 2 3 4 150 165 175 190 当 时： 于是有表3。 表3 （单位：万元） x2 S2 1 2 3 4 1 120+0 150 1 2 120+150 150+0 150 1 3 120+165 150+150 170+0 300 2 4 120+175 150+165 170+150 180+0 320 3 5 120+190 150+175 170+165 180+150 335 3 当 时： 于是有表4。 表4 x1 S1 g1（x1）+f2（s1 – x1） 0 1 2 3 4 6 0+345 100+375 160+320 190+300 200+270 490 3 故最优分配方案为：A区建3个销售店，B区建2个销售店，C区建1个销售店， 总利润为490万元。 2、某工厂有100台机器，拟分4个周期使用，在每一周期有两种生产任务，据经验把机器投入第一种生产任务，则在一个周期中将有六分之一的机器报废，投入第二种生产任务，则有十分之一的机器报废。如果投入第一种生产任务每台机器可收益1万元，投入第二种生产任务每台机器可收益0.5万元。问怎样分配机器在4个周期内的使用才能使总收益最大？ 解： 阶段：将每个周期作为一个阶段，即k=1,2,3，4 状态变量：第k阶段的状态变量 代表第k个周期初拥有的完好机器数 决策变量：决策变量 为第 周期分配与第一种任务的机器数量，于是 该周期分配在第二种任务的机器数量。 状态转移律： 允许决策集合 令最优函数： 边界条件： =0 当k=4时： 因 是关于 的单调递增函数，故取 ，相应有 ；依次类推，可求得： 当 时： ， 当 时： ， 当 时： ， 计算表明，每一期都将全部机器投入第一种任务中，其中 100， =83， =69， =58 3、某公司生产一种产品，估计该产品在未来四个月的销售量分别为300、400、350和250件。生产该产品每批的固定费用为600元，每件的变动费用为5元，存储费用为每件每月2元。假定第一个月月初的库存为100件，第四个月月底的存货为50件。试求该公司在这四个月内的最优生产计划。 解：阶段：将今后4个月中的每一个月作为一个阶段，即 ； 状态变量：第 阶段的状态变量 代表第 个月初产品存储量； 决策变量：决策变量 代表第 个月的生产量； 状态转移律： （ 是第 个月的销售量）； 边界条件： ， ， ； 固定生产费用 和存贮费 变动生产费用 最优指标函数：最优指标函数具有如下递推形式 当 时： 表1 S4 0 50 100 150 200 250 300 X4 300 250 200 150 100 50 0 F4（S4） 2200 1950 1700 1450 1200 950 100 当K=3时： 表2 x3 S3 0 50 100 150 200 250 300 350 400 450 0 4550 4650 4750 350 4550 50 4300 4400 4500 4600 300 4300 100 4050 4150 4250 4350 4450 250 4050 150 3800 3900 4000 4100 4200 4300 200 3800 200 3550 3650 3750 3850 3950 4050 3550 150，450 3550 250 3300 3400 3500 3600 3700 3800 3300 100，400 3300 300 3050 3150 3250 3350 3450 3550 3050 50，350 3050 350 2200 2900 3000 3100 3200 3300 2800 0 2200 400 2050 2250 2850 2950 3050 2550 2050 当K=2时： 表3 S3 0 50 100 150 200 250 300 350 400 450 0 7150 7250 400 7150 50 6900 7000 7100 350 6900 100 6650 6750 6850 6950 300 6650 150 6400 6500 6600 6700 6800 250 6400 200 6150 6250 6350 6450 6550 6650 200 6150 当K=1时: 表4 x1 S1 0 50 100 150 200 250 300 350 400 450 100 8750 8850 8950 9050 9150 9250 200 8750 利用状态转移律，按上述计算的逆序可推算出最优策略为：第1个月生产200件，第2个月生产400件，第3个月生产350件，最后一个月生产300件。 4、用动态规划求解下述规划问题 （1） （2） 解：（1）解：阶段：将问题的变量数作为阶段，即 ，4，5； 决策变量：决策变量 ； 状态变量：状态变量 代表第 阶段的约束右端项，即从 到 占有的份额； 状态转移律： ； 边界条件： ， ； 允许决策集合： 当k=5时： 当k=4时： 设 ，于是令 可得 又因 <0，所以： 是 的极大值点 于是： 当k=3时： 当k=2时： 当k=1时： 同理 ： =2 故最优解为 ： 最优值为： （2）解：阶段：将问题的变量数作为阶段，即k=1,2； 决策变量：决策变量 ； 状态变量：状态变量 代表第 阶段的约束右端项; 状态转移律： ； 边界条件： ， ； 阶段指标： 基本方程： 其中： 当k=2时： 关于 的单调增函数，故 当k=1时： = 5、某公司经销A、B、C三种产品，由于运输能力的限制，该公司每月只能把6吨的产品运回公司进行销售。产品A、B、C的单件重量分别为20、30和40公斤；进货的批量分别为50、40和20件；单位产品利润分别为80、130和150元。试确定该公司每月A、B、C三种产品的最佳进货量，以使总利润最大。 6、某公司需要在近四周内采购一批原料，估计在未来四周内的价格可能有60、80、90和100四种状态，各状态发生的概率分别为0.2、0.3、0.3和0.2，试求各周应以什么样的价格购入原料，才能使采购价格期望值最小。 解：阶段：将每一周作为一个阶段，即 ； 决策变量：决策变量 代表第 周是否决定采购， 代表第 周决定采购， 代表第 周决定等待； 状态变量：状态变量 代表第 周原材料的市场价格； 中间变量： 代表第 周决定等待，而在以后采取最佳子策略时的采购价格期望值； 最优指标函数：是否采购决定于目前市场价格与等待价格期望值的相对大小，如果前者大于后者，应决定等待；如果前者小于后者，则应决定采购。于是： 边界条件：对于第4周，因为没有继续等待的余地，所以： 即： 、 当 时：只有采购一种选择 、 当 时： 于是： 即第三周的最佳决策为： 当 时： 于是： 即第二周的最佳决策为： 当 时： 于是： 即第一周的最佳决策为： 由以上计算可知，最佳的采购策略为：第一周,第二周只有价格是60时才采购，否则就等待；第三周只要价格不超过80就要采购，否则继续等待；如果已经等待到了第四周，那么无论什么价格都只有采购，别无选择。 7、某工厂生产一种精密仪器，今后四个月的订单分别为2、3、4台。已知生产费用C（万元）同生产量x的关系为： 又若生产出来的产品当月销售不出去，其库存费用为每台每月0.2万元。设在第一个月月初及第四个月月末该产品无库存，试确定在满足需求的条件下，使该工厂生产与库存总费用最小的生产方案。 解：阶段：将今后4个月中的每一个月作为一个阶段，即 ； 状态变量：第 阶段的状态变量 代表第 个月存储量； 决策变量：决策变量 代表第 个月的生产量； 状态转移律： （ 是第 个月的销售量）； 边界条件： ， ； 生产费用 和存贮费 最优指标函数：最优指标函数具有如下递推形式 当 时： 表1 S4 0 1 2 3 4 X4 4 3 2 1 0 F4（S4） 16 13．5 10 5．5 0 当K=3时： 表2 x5 S5 0 1 2 3 4 5 6 0 35 34.7 6 34.7 1 32 31.7 31.4 6 31.4 2 29.5 29.7 29.4 27.1 6 27.1 3 26 27.2 26.4 25.1 21.8 6 21.8 4 21.5 23.7 23.9 22.1 19.8 22 5 19.8 5 16 19.2 20.4 19.6 16.8 20 0 16 6 13.7 15.9 16.1 14.3 0 13.7 7 10.4 11.6 10.8 0 10.4 当K=2时： 表3 x3 S3 0 1 2 3 4 5 6 0 48.2 47.6 46.5 43.4 6 43.4 1 44.7 45.1 43.5 41.4 41.6 5 41.4 2 40.2 41.6 41 38.4 39.6 38 6 38 3 34.7 37.1 37.5 35.9 36.6 36 35.9 0 34.7 4 31.6 33 32.4 34.1 33 33.9 32.8 0 31.6 当K=1时: 表4 x1 S1 0 1 2 3 4 5 0 53.4 55.1 54.4 53.4 2,6 53.4 利用状态转移律，按上述计算的逆序可推算出最优策略有两种：（1）第1个月生产2台，第2个月和第3个月生产6台，最后一个月不生产;(2) 第1个月生产6，第2个月不生产，第3个月生产6台，最后一个月生产2台。总费用为53.4万元。 8、某研发部（乙方）拟承担一种新产品的研发任务，甲方提供研发经费10万元。为适应市场竞争的需要，合同要求乙方应在三个月内向甲方交付一台合格样品，否则乙方将退还甲方10万元的研发费。据估计，研发时投产1台即合格的概率为0.35，投产一批的准备费用为0.25万元，每台的研发费用为1万元。若投产一批而未得到合格样品，可再投产一批，但每批的研发周期是一个月。试分析该研发部应否接受此研发任务，如果接受应该采用怎样的研发策略。 解：阶段：将每个试制周期（1个月）作为一个阶段，即 ； 决策变量：决策变量 代表第 阶段投产试制的台数； 状态变量：状态变量 代表第 阶段初是否已获得合格样品，尚无合格样品时 ，已获得合格样品时 ； 允许决策集合： 状态转移律： ， ； 边界条件： ， ， ，； 阶段指标函数： 最优指标函数： EMBED Equation.DSMT4 当 时： 表1 x3 S3 0 1 2 3 4 5 0 0 0 1 10 7.75 6.48 6 6.04 4.88 3 6 当 时： 表2 x2 S2 0 1 2 3 0 0 0 1 6 5.15 4.78 4.9 2 4.78 当 时： 表3 x1 S1 0 1 2 3 1 4.78 4.36 4.27 4.56 2 4.27 即该公司的最佳试制计划为：第一个月初投产试制2台；如果在第二个月初无合格样品出现，再投产试制2；如果在第三个月初仍然无合格样品出现，再投产试制3。按此最佳试制方案最小期望总费用是4.27元。 9 图论 1、判断下列说法是否正确 （1） 图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、边的长短曲直等都要严格注意。 （错） （2） 当图的点集确定后，树图是所有图中边数最少的简单图。 （正确） （3） 在连通图G中，其权数最大的边必不包含在其最小部分树内。 （正确） （4） 若图中从v1至各点均有唯一的最短路，则连接v1至其他各点的最短路在去掉重复部分后，恰好构成改图的最小部分树。 （正确） （5） 求网络最大流问题可用线性规划数学模型加以描述 （正确） 2、试回答： （1） 具有N个顶点的完全图有多少条边； （2） 具有N个顶点的二分图最多有多少条边； （3） 具有N个顶点的简单图最多有多少条边。 EMBED Equation.DSMT4 3、 在某海上油田的一个区块上有8口油井，它们相互之间的距离如表1所示。已知1号井 距离海岸最近，这一最近距离为5海里。试问从海岸经1号井铺设输油管线将各油井同陆地 连接起来，应如何铺设才能使输油管线的长度最短，最短输油管线的铺设长度是多少？ 表1 （单位：海里） 到 从 2(井 3(井 4(井 5(井 6(井 7(井 8(井 1(井 1.3 2.1 0.9 0.7 1.8 2.0 1.5 2(井 0.9 1.8 1.2 2.6 2.3 1.1 3(井 2.6 1.7 2.5 1.9 1.0 4(井 0.7 1.6 1.5 0.9 5(井 0.9 1.1 0.8 6(井 0.6 1.0 7(井 0.5 解：此问题可转化为求最小部分数来求，用kruskal顺序生枝法求解，得到如下图的最小部分数，总长度为5.2+5＝10.2。 4、已知图1，试求： （1） 最小部分树； （2） 点到其他各点的最短路； （3） 各点之间的最短路。 解：（1） (2) n≤ ≤3 即最多运算到 即可 （３）则在矩阵 中即可以找到V1到各点的最短路以及各点之间的最短路。 5、 A、B、C、D、E、F、G代表七个村落，村落之间的道路连通情况如图2所示（边上的 数据为距离，单位为公里）。这七个村落拟合建一所小学，已知A村有小学生50人、B村有 小学生40人、C村有小学生60人、D村有小学生20人、E村有小学生70人、F村有小学 生80人、G村有小学生100人，试问拟合建的小学应建在哪一个村落，才能使学生上学所 走的总路程最短。 解： 即最多运算到 即可 在 中第一行乘以A地区的人数，同理，其他各行分别乘以B,C,D,E,F,G地区的学生人数。得到以下表: A B C D E F G A 0 75 60 90 240 350 900 B 60 0 108 88 200 220 280 C 72 162 0 96 276 492 468 D 36 44 32 0 60 138 124 E 336 350 322 210 0 273 224 F 560 440 656 552 312 0 120 G 800 700 780 620 320 150 0 Σ 1864 1771 1958 1656 1408 1623 1616 由此表得出：E地区最为合适 6、PERT网络问题 表2 作 业 作业代码 作业时间（天） 紧前作业 产品设计与工艺设计 a 60 ------ 外购零、部件 b 45 a 下料与锻造 c 10 a 工艺装备制造1 d 20 a 模具与铸造 e 40 a 机械加工1 f 18 c 工艺装备制造2 g 30 d 机械加工2 h 15 d、e 机械加工3 k 25 g 装配调试 l 35 b、f、k、h （1） 某新产品研发工程的各项作业、作业时间以及它们之间的相互关系如表2所示，试绘制该工程的网络图并进行网络的结点和作业时间计算； （2） 若该工程每天的间接费用为600元，各项作业的直接费用与时间数据如表3所示，试确定使总费用最小的最优方案。 表3 作业 正常情况下 采取措施的情况下 直接费用率 （元/天） 作业时间 直接费用 极限时间 直接费用 a 60 10,000 60 10,000 ------ b 45 4,500 30 6,300 120 c 10 2,800 5 4,300 300 d 20 7,000 10 11,000 400 e 40 10,000 35 12,500 500 f 18 3,600 10 5,440 230 g 30 9,000 20 12,500 350 h 15 3,750 10 5,750 400 k 25 6,250 15 9,150 290 l 35 12,000 35 12,000 ------ 7、求如图3所示网络的最大流（弧旁数字为弧的容量） 解： SHAPE \* MERGEFORMAT 最大流为22 8．邮递员投递区域的街道分布如图4所示，图中数字为街道长度（单位为公里）。“O”为邮局所在地，试为邮递员设计一条最佳的投递路线，使其每天完成投递任务并返回邮局所经历的路线最短。 解释、修正 求 解 构 造 模 型 现 实 系 统 模 型 现 实 结 论 模 型 结 论 图1-1运筹学的工作过程 � EMBED Equation.DSMT4 ��� 8 4 2 3 4 此题有唯一最有解，� EMBED Equation.DSMT4 ��� 2 3 4 8 4 此题有无穷多最有解，其中一个是� EMBED Equation.DSMT4 ��� 2 4 4 此题为无界解 2 4 3 找不到可行域，此题为无可行解 � EMBED Equation.DSMT4 ��� 3 2 4 W=-5 10 W=-1 W=-8 W=-4 18 11 4 W=-7 14 W=-2 W=-7 W=-10 19 � EMBED Equation.DSMT4 ��� 5 2 26 � EMBED Equation.DSMT4 ��� W=-6 W=-6 15 � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� W=-5 27 W=-2 W=-11 1 � EMBED Equation.DSMT4 ��� W=-6 8 24 W=-9 6 W=-1 � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� 25 W=-5 W=-9 3 9 W=-4 � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� W=-8 W=-8 16 � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� 12 7 W=-3 17 � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� W=-2 W=-7 22 � EMBED Equation.DSMT4 ��� W=-7 20 13 � EMBED Equation.DSMT4 ��� 23 � EMBED Equation.DSMT4 ��� W=-7 W=-6 21 (可行解) W=-9 W=-12 � EMBED Equation.DSMT4 ���=0001000 � EMBED Equation.DSMT4 ���=11 W=-14 1 2 3 5 1 0.5 0.6 0.9 0.7 1 5 4 8 7 6 3 2 0.8 海 岸 0.7 � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� 8 18 7 8 5 � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� 6 � EMBED Equation.DSMT4 ��� 8 � EMBED Equation.DSMT4 ���� EMBED Equation.DSMT4 ��� F A C B D E G 1.5 1.2 1.8 1.6 2.2 3.0 5.0 5.5 3.9 3.2 1.5 图2 � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� 8 10 9 6 12 5 8 6 3 15 11 18 图3 （12，0） （18，0） （15，0） （11，0） （6，0） （5，0） （9，0） （8，0） （10，0） （6，0） （3，0） （8，0） � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ���� EMBED Equation.DSMT4 ��� （12，0） （18，11） （15，2） （11，11） （6，6） （5，5） （9，5） （8，0） （10，10） （6，4） （3，3） （8，7） � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ��� � EMBED Equation.DSMT4 ���� EMBED Equation.DSMT4 ��� 6 2 3 8 2 3 3 3 4 3 1 2 1 3 1.5 2.5 3 6 图4 1 1 6 2 3 8 2 3 3 3 4 3 1 2 1 3 1.5 2.5 3 6 图4 1 1 _1198416967.unknown _1198428532.unknown _1198478642.unknown _1198491839.unknown _1198576493.unknown _1198661165.unknown _1205607595.unknown _1205607973.unknown _1205608414.unknown _1205667692.unknown _1205608223.unknown _1205607749.unknown _1198661483.unknown _1198697795.unknown _1204398581.unknown _1205607507.unknown _1198697806.unknown _1198661590.unknown _1198661776.unknown _1198697676.unknown _1198661553.unknown _1198661184.unknown _1198661439.unknown _1198661183.unknown _1198661174.unknown _1198576874.unknown _1198660626.unknown _1198660750.unknown _1198577080.unknown _1198660618.unknown _1198577079.unknown _1198577078.unknown _1198576614.unknown _1198576727.unknown _1198576503.unknown _1198501570.unknown _1198502050.unknown _1198576269.unknown _1198576446.unknown _1198576455.unknown _1198576278.unknown _1198576073.unknown _1198576094.unknown _1198502177.unknown _1198576013.unknown _1198502151.unknown _1198502070.unknown _1198501869.unknown _1198501966.unknown _1198502000.unknown _1198502019.unknown _1198501925.unknown _1198501808.unknown _1198501843.unknown _1198501650.unknown _1198501687.unknown _1198501711.unknown _1198501606.unknown _1198492991.unknown _1198493104.unknown _1198501233.unknown _1198501460.unknown _1198501558.unknown _1198501305.unknown _1198501347.unknown _1198501281.unknown _1198493615.unknown _1198495854.unknown _1198495957.unknown _1198496284.unknown _1198500324.unknown _1198500133.unknown _1198500165.unknown _1198496015.unknown _1198496203.unknown _1198495984.unknown _1198495886.unknown _1198495920.unknown _1198495863.unknown _1198493941.unknown _1198493974.unknown _1198493835.unknown _1198493124.unknown _1198493452.unknown _1198493614.unknown _1198493115.unknown _1198493056.unknown _1198493079.unknown _1198493089.unknown _1198493068.unknown _1198493035.unknown _1198493047.unknown _1198493005.unknown _1198491953.unknown _1198492907.unknown _1198492931.unknown _1198492949.unknown _1198492121.unknown _1198492120.unknown _1198491951.unknown _1198491952.unknown _1198491949.unknown _1198491950.unknown _1198491947.unknown _1198491948.unknown _1198491861.unknown _1198482579.unknown _1198483856.unknown _1198490992.unknown _1198491240.unknown _1198491421.unknown _1198491010.unknown _1198491220.unknown _1198484077.unknown _1198490696.unknown _1198483933.unknown _1198483745.unknown _1198483817.unknown _1198483840.unknown _1198483808.unknown _1198482633.unknown _1198483491.unknown _1198483432.unknown _1198483021.unknown _1198483145.unknown _1198483236.unknown _1198482688.unknown _1198482584.unknown _1198480595.unknown _1198482529.unknown _1198482542.unknown _1198482426.unknown _1198482458.unknown _1198480635.unknown _1198478771.unknown _1198479142.unknown _1198479997.unknown _1198478869.unknown _1198478738.unknown _1198430508.unknown _1198434551.unknown _1198437573.unknown _1198438932.unknown _1198440063.unknown _1198478471.unknown _1198478607.unknown _1198478641.unknown _1198478597.unknown _1198475483.unknown _1198478205.unknown _1198476479.unknown _1198478115.unknown _1198440233.unknown _1198475296.unknown _1198440382.unknown _1198440107.unknown _1198439528.unknown _1198439845.unknown _1198440017.unknown _1198439660.unknown _1198439844.unknown _1198439194.unknown _1198439502.unknown _1198439192.unknown _1198439193.unknown _1198439191.unknown _1198438529.unknown _1198438607.unknown _1198438747.unknown _1198438931.unknown _1198438817.unknown _1198438709.unknown _1198438539.unknown _1198438354.unknown _1198438401.unknown _1198437756.unknown _1198435692.unknown _1198436201.unknown _1198436242.unknown _1198436313.unknown _1198436970.unknown _1198436260.unknown _1198436234.unknown _1198436133.unknown _1198436166.unknown _1198436075.unknown _1198436109.unknown _1198435701.unknown _1198435219.unknown _1198435467.unknown _1198435144.unknown _1198435218.unknown _1198434715.unknown _1198435131.unknown _1198434799.unknown _1198434602.unknown _1198433061.unknown _1198434283.unknown _1198434343.unknown _1198434399.unknown _1198434473.unknown _1198434355.unknown _1198434306.unknown _1198433218.unknown _1198433878.unknown _1198433970.unknown _1198433520.unknown _1198433620.unknown _1198433300.unknown _1198433498.unknown _1198433250.unknown _1198433204.unknown _1198433211.unknown _1198433197.unknown _1198431765.unknown _1198432480.unknown _1198432702.unknown _1198432968.unknown _1198432561.unknown _1198432396.unknown _1198432457.unknown _1198431858.unknown _1198431885.unknown _1198431773.unknown _1198431837.unknown _1198431557.unknown _1198431751.unknown _1198431759.unknown _1198431744.unknown _1198431510.unknown _1198431544.unknown _1198431545.unknown _1198431474.unknown _1198431367.unknown _1198429659.unknown _1198430024.unknown _1198430347.unknown _1198430394.unknown _1198430443.unknown _1198430402.unknown _1198430368.unknown _1198430090.unknown _1198430203.unknown _1198429882.unknown _1198429923.unknown _1198429896.unknown _1198429798.unknown _1198429203.unknown _1198429512.unknown _1198429548.unknown _1198429611.unknown _1198429575.unknown _1198429525.unknown _1198429479.unknown _1198429497.unknown _1198429428.unknown _1198429455.unknown _1198429040.unknown _1198429049.unknown _1198428840.unknown _1198419090.unknown _1198420110.unknown _1198426222.unknown _1198427163.unknown _1198427194.unknown _1198427732.unknown _1198427748.unknown _1198427725.unknown _1198427153.unknown _1198426223.unknown _1198425626.unknown _1198426169.unknown _1198426221.unknown _1198425878.unknown _1198426022.unknown _1198426094.unknown _1198426118.unknown _1198426033.unknown _1198425895.unknown _1198425664.unknown _1198425637.unknown _1198425208.unknown _1198425556.unknown _1198425592.unknown _1198425617.unknown _1198425222.unknown _1198420772.unknown _1198425134.unknown _1198420387.unknown _1198420466.unknown _1198420340.unknown _1198420186.unknown _1198420329.unknown _1198419955.unknown _1198420096.unknown _1198420107.unknown _1198419957.unknown _1198420034.unknown _1198420076.unknown _1198420086.unknown _1198420089.unknown _1198420043.unknown _1198419958.unknown _1198419956.unknown _1198419819.unknown _1198419862.unknown _1198419871.unknown _1198419827.unknown _1198419779.unknown _1198419795.unknown _1198419334.unknown _1198419426.unknown _1198419437.unknown _1198419353.unknown _1198419231.unknown _1198419310.unknown _1198418122.unknown _1198418342.unknown _1198418410.unknown _1198418432.unknown _1198418910.unknown _1198419019.unknown _1198418422.unknown _1198418380.unknown _1198418402.unknown _1198418367.unknown _1198418259.unknown _1198418318.unknown _1198418333.unknown _1198418308.unknown _1198418218.unknown _1198418251.unknown _1198418150.unknown _1198417648.unknown _1198417886.unknown _1198418033.unknown _1198418108.unknown _1198418027.unknown _1198418028.unknown _1198417916.unknown _1198417722.unknown _1198417806.unknown _1198417691.unknown _1198417340.unknown _1198417561.unknown _1198417616.unknown _1198417341.unknown _1198417098.unknown _1198417140.unknown _1198417047.unknown _1144559550.unknown _1198348931.unknown _1198413873.unknown _1198414857.unknown _1198416695.unknown _1198416893.unknown _1198416943.unknown _1198416729.unknown _1198416374.unknown _1198416621.unknown _1198416070.unknown _1198414291.unknown _1198413885.unknown _1198413898.unknown _1198350019.unknown _1198350991.unknown _1198354628.unknown _1198413844.unknown _1198353285.unknown _1198353422.unknown _1198353103.unknown _1198350824.unknown _1198349489.unknown _1198349669.unknown _1198349997.unknown _1198349613.unknown _1198348988.unknown _1148656906.unknown _1148657377.unknown _1148657488.unknown _1148657607.unknown _1148657674.unknown _1148657710.unknown _1148657642.unknown _1148657572.unknown _1148657533.unknown _1148657438.unknown _1148657265.unknown _1148657316.unknown _1148656966.unknown _1144559870.unknown _1148656778.unknown _1148656855.unknown _1148656875.unknown _1148656820.unknown _1148020431.unknown _1148656638.unknown _1148656707.unknown _1148020478.unknown _1148020499.unknown _1148020529.unknown _1148020455.unknown _1148020371.unknown _1148020411.unknown _1147852520.unknown _1144559738.unknown _1144559831.unknown _1144559850.unknown _1144559743.unknown _1144559761.unknown _1144559572.unknown _1144559592.unknown _1140322194.unknown _1141217585.unknown _1142321729.unknown _1142679503.unknown _1142926339.unknown _1144558651.unknown _1144558686.unknown _1144558979.unknown _1144559534.unknown _1144558976.unknown _1144558977.unknown _1144558716.unknown _1143014441.unknown _1143014554.unknown _1143014628.unknown _1143014672.unknown _1143014581.unknown _1143014519.unknown _1142927810.unknown _1143007210.unknown _1143014357.unknown _1143007785.unknown _1142928237.unknown _1142927036.unknown _1142927227.unknown _1142926538.unknown _1142914375.unknown _1142920503.unknown _1142923386.unknown _1142924099.unknown _1142925584.unknown _1142925644.unknown _1142925499.unknown _1142924108.unknown _1142923453.unknown _1142923874.unknown _1142923436.unknown _1142920911.unknown _1142921905.unknown _1142923358.unknown _1142923365.unknown _1142921893.unknown _1142920563.unknown _1142920031.unknown _1142920141.unknown _1142919927.unknown _1142914493.unknown _1142914186.unknown _1142661162.unknown _1142661461.unknown _1142662487.unknown _1142667817.unknown _1142668065.unknown _1142668072.unknown _1142679193.unknown _1142667825.unknown _1142667504.unknown _1142667512.unknown _1142662768.unknown _1142661512.unknown _1142662450.unknown _1142661244.unknown _1142321973.unknown _1142661134.unknown _1142661143.unknown _1142322083.unknown _1142322029.unknown _1142321754.unknown _1142321937.unknown _1142321743.unknown _1142311479.unknown _1142313598.unknown _1142314892.unknown _1142318568.unknown _1142318629.unknown _1142318210.unknown _1142314701.unknown _1142314854.unknown _1142314688.unknown _1142312512.unknown _1142313012.unknown _1142313597.unknown _1142312865.unknown _1142311807.unknown _1142312497.unknown _1142311576.unknown _1141652751.unknown _1141652938.unknown _1142310981.unknown _1142311021.unknown _1142310955.unknown _1141652835.unknown _1141652879.unknown _1141219519.unknown _1141219520.unknown _1141219601.unknown _1141217637.unknown _1140679260.unknown _1140704447.unknown _1140851249.unknown _1141217400.unknown _1140848122.unknown _1140851178.unknown _1140851190.unknown _1140847902.unknown _1140704553.unknown _1140847884.unknown _1140679763.unknown _1140703099.unknown _1140703325.unknown _1140679859.unknown _1140679663.unknown _1140679751.unknown _1140679500.unknown _1140322603.unknown _1140678952.unknown _1140679045.unknown _1140679195.unknown _1140678994.unknown _1140678842.unknown _1140678925.unknown _1140678801.unknown _1140322383.unknown _1140322472.unknown _1140322531.unknown _1140322389.unknown _1140322218.unknown _1140322232.unknown _1140322284.unknown _1140322231.unknown _1140322207.unknown _1140267724.unknown _1140268037.unknown _1140268487.unknown _1140268533.unknown _1140322089.unknown _1140268503.unknown _1140268138.unknown _1140268257.unknown _1140268066.unknown _1140267867.unknown _1140267894.unknown _1140267935.unknown _1140267934.unknown _1140267881.unknown _1140267847.unknown _1140266817.unknown _1140267048.unknown _1140267268.unknown _1140267304.unknown _1140267120.unknown _1140266943.unknown _1139746940.unknown _1139986378.unknown _1139468832.unknown _1139468755.unknown _1139468782.unknown