运筹学基础及应用
P43例13 、混合配料问题：某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如表1-19所示。问该厂每月生产这三种牌号糖果各多少千克，使该厂获利最大。试建立这个问题的线性规划的数学模型。
表1-19
P44例14、投资项目的组合问题：兴安公司有一笔30万元的资金，考虑今后三年内用于下列项目的投资：
（1）三年内的每年年初均可投资，每年获利为投资额的20%，其本利可一起用于下一年投资；
（2）只允许第一年初投入，于第二年末收回，本利合计为投资额的150%，但此类投资限额不超过15万元；
（3）允许于第二年初投入，于第三年末收回，本利合计为投资额的160%，但限额投资20万元；
（4）允许于第三年初投入，年末收回，可获利40%，但限额为10万元。
试为该公司确定一个使第三年末本利和为最大的投资组合方案。
P44例15、生产、库存与设备维修综合计划的安排：红光厂有2台车床，1台钻床，1台磨床，承担4中产品的生产任务．已知生产各种产品所需的设备台时及生产单位产品的售价如表１－20所示．对各种产品今后三个月的市场最大需求（小于最大需求量时即可全部销出）及各产品在今后三个月的生产成本分别如表1－21和表1－22所示．上述设备在1~3月内各需进行一次维修,具体安排为:2台车床于2月份、3月份各维修一台,钻床安排在2月份维修,磨床安排在3月份维修.各设备每月工作22天.每天2班,每班8h,每次维修占用半各月时间.又生产出来的产品当月销售不出去(超过最大需求量)时,可在以后各月销售,但需付每件每月储存费5元.但规定每月底各种产品储存量均不得超过100件.1月初各产品无库存,要求3月底各产品均库存50件.试安排该厂各月的生产计划,使总的利润为最大.
表１－20a值单位：h
表1－21 最大需求量单位：件
P81例1、某食品公司经销的主要产品之一是糖果。它下面设有三个加工厂，每天的糖果生产量分别为：A1—7t,A2—4t,A3—9t.该公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量为：B1—3t,B2—6t,B3—5t,B4—6t.已知从每个加工厂到各销售门市部每吨糖果的运价如表3—1所示，问该食品公司应如何调运，在满足各门市部销售需要的情况下，使总的运费支出为最少。
表3—1
P95例2、设有A1、A2、A3三个产地生产某种物资，其产量分别为7t、5t、7t，B1、B2、B3、B4四个销地需要该种物资，销量分别为2t、3t、4t、6t，又知各产销地之间的单位运价见表3—25，试决定总运费最少的调运方案。
表3—25 单位运价表单位：元/t
P96例3、设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同，已知各化肥厂年产量，各地区年需要量及从各化肥厂到各地区单位化肥的运价如表3—29所示，试决定使总的运费最节省的化肥调拨方案。
表3—29 运价：万元/万t
P98例4、在本章的例1中，如果假定：（1）每个工厂生产的糖果不一定直接发运到销售点，可以将其中几个产地的糖果集中一起运；（2）运往各销地的糖果可以先运给其中几个
销地，再转运给其他销地；（3）除产、销地之外，中间还可以有几个转运站，在产地之间、销地之间或产地与销地之间转运。已知各产地、销地、中间转运站及相互之间每吨糖果的运价如表3—33所示，问在考虑到产销地之间直接运输和非直接运输的各种可能方案的情况下，如何将三个厂每天生产的糖果运往销售地，使总的运费最少。
表3—33
P108例2、有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，他们完成翻译不同文字所需的时间（h）如表4—1所示。应如何分配，使这四个人分别完成这四项任务总的时间为最小。
表4—1
P120例3、东方大学计算机实验室聘用4名大学生（代号1、2、3、4）和两名研究生（代号5、6）值班答疑。已知每人从周一至周五每天最多可安排的值班时间及每人每h值班的报酬如下表4—7所示：
表4—7
该实验室开放时间为上午8：00至晚上10：00，开放时间内须有且仅须一名学生值班。规定大学生每周值班不少于8h，研究生每周不少于7h，每名学生每周值班不超过3次，每次值班不少于2h，每天安排值班的学生不超过3人，且其中必须有一名研究生。试为该实验室安排一张人员的值班表，使总支付的报酬为最少。
P121例4 红星日用化工厂为发运产品，下一年度需6种不同容积的包装箱。每种包装箱的需求量及生产一个的可变费用如下表4—8所示：
由于生产不同容积包装箱时需进行专门准备、下料等，生产某一容积包装箱的固定费用均为1200元。又若某一容积包装箱数量不够时，可用比它容积大的代替。试问该化工厂应订做哪几种代号的包装箱各多少个，使费用最节省。
P122例5 春江市计划为新建的5个居民小区中的两个分别各设立一所小学。表4—9给出了各小区内及各小区间的平均不行时间（min）及各居民小区的小学生人数。要求为该市提供决策建议，两所小学应分别建于哪两个居民小区，以及各居民小区学生应分到哪所小学上学，使学生总的上学步行时间为最短。
P123例6 清源市下设八个区，表4—11给出救护车从一个区至另一个区的车程时间（min）。该市拟建救护中心，要求各区离救护中心的车程时间必须在8min之内。试为该市提供决策建议：至少建多少个救护中心，建于何处？
表4—11 单位：min
P125习题四
4.1、试利用0—1变量对下列各题分别表示成一般线性约束条件。
（a）x1+x2≤2或2*x1+3*x2≥5。
（b）变量x只能取值0、3、5或7中的一个。
（c）变量x或等于0，或≥50。
（d）若x1≤2，则x2≥1，否则x2≤4。
（e）以下四个约束条件中至少满足两个：x1+x2≤5，x1≤2，x3≥2，x3+x4≥6。
4.2、某钻井队要从以下10个可供选择的井位中确定5个钻井探油，目的使总的钻探费用最小。若10个井位代号为s1，s2，……，s10，相应的钻探费用为c1，c2，……，c10，
并且井位的选择上要满足下列条件：
（1）或选择s1和s7，或选择钻探s8；
（2）选择了s3或s4就不能选s5，或反过来也一样；
（3）在s2、s6、s9、s10中最多只能选两个。
试建立这个问题的数学模型。
4.4、已知下列五名运动员各种姿势的游泳成绩（各为50m）如表4—13所示。试问如何从中选拔一个4*50m混合泳的接力队，使预期的比赛成绩为最好。
表4—13 单位：s
4．5P125D、E五项任务，每个人完成各项任务的时间如表4-14所示。由于任务数多余人数，故考虑：
（a）任务E必须完成，其它四项中可任选3项完成；
（b）其中有一人完成两项，其他每人完成一项；
（c）任务A由甲或丙完成，任务C由丙或丁完成，任务E由甲、乙或丁完成，且规定4人中丙或丁完成两项任务，其他每人完成一项；
试分别确定最优分配方案，使完成任务的总时间最少。
4．6P126某物资有m个生产点（i=1,……，m），第i个生产点产量为a(i),该物资销往n个需求点，第j个需求点销量为b(j)(j=1,……，n),有∑a(i)≥∑b(j),已知从各生产点到各需求点，需经p个中间编组站之一转运（k=1,……，p）,若启用第k个编组站，不管转运量多少，均发生固定费用f(k).已知第k个中间编租站转运的最大容量限制为q(k),用c(ik)和c(kj)分别表示从i到k和从k到j的单位物资的运输费用，试确定一个使总费用为最小的该种物资的调运方案。
4．10一条多品种流水线上要轮换生产5种不同零件，表4-15给出了一开始生产某个零的准备时间及从生产一个零件转换生产另一个零件时所需的设备调整时间。试确定分枝定界法找出上述5个零件轮换生产的顺序，使总的准备及设备调整时间为最短。
表4—15 单位：h
4.13需生产2000件某种产品，该种产品可利用A.B.C.D设备中的任意一种加工。已知每种设备的生产准备结束费用，生产该产品时的单件成本以及每种设备限定的最大加工数量（件）如表4-16所示，诗建立该问题的数学模型并求解。
表4-16
工费用表4-17。又只要有零件在上述设备上加工，不管加工1种或多种，分别发生的一次性准备费用为dA,dB,dC元，若要求：
1。上述10种零件每种加工1件；
2。若第1种零件在设备A上加工，则第2种零件应在设备B 或C上加工。反之若第1种零件在设备B或C上加工，则第2种零件应在设备A 上加工；
3。零件3，4，5必须在A，B，C三台设备上加工；
4。在设备C上加工的零件种数不超过3种.试对此问题建立整数规划的数学模型，目标是使总的费用为最小
表4-17
4.15 鞍山街邮局从周一到周日每天所需值班人员如表4—18所示：
参考文献 [1] 胡运权．运筹学教程．北京：高等教育出版社，2005 [2] 胡运权．运筹学基础及应用．哈尔滨：哈尔滨工业大学出版社，1998 [3] 《运筹学》编写组．运筹学．北京：清华大学出版社， 1990 [4] 张莹．运筹学基础．北京：清华大学出版社，2002 [5] 袁亚湘，孙文瑜．最优化理论与方法．北京：科学出版社，1999 [6] 何坚勇．运筹学基础．北京：清华大学出版社， 2000 [7] 马振华等．现代应用数学手册—运筹学与最优化理论卷．北京：清华大学出版社，2000 [8] 牛映武．运筹学．西安：西安交通大学出版社，1993 [9] 梁工谦．运筹学- 典型题解析集自测试题。西安：西北工业大学出版社，2002 [10] 徐永仁．运筹学试题精选与答题技巧．哈尔滨：哈尔滨工业大学出版社，2000 [11] 徐玖平，胡知能，王緌．运筹学(第二版)．北京：科学出版社，2004 [12] 刘满风，傅波，聂高辉．运筹学模型与方法教程- 例题分析与题解．北京：清华大学出版社，2001 [13] 胡运权．运筹学习题集．北京：清华大学出版社，2002 [14] 盛昭瀚，朱乔，吴广谋．DEA理论、方法与应用．北京：科学出版社，1996 [15] Frederick ~S．Hillier，Gerald~J．Lieberman．Introduction to Operations Research (6th Ed．)．Beijing：China Machine Press/ McGraw - Hill，1999 [16] J．D．Wiest，F．K．Levy．统筹方法管理指南．北京：机械工业出版社，1983 [17] 王元等．华罗庚科普著作选集．上海：上海教育出版社，1984 [18] 江景波等．网络计划技术．北京：冶金工业出版社，1983 [19] David R．Anderson，Dennis J．Sweeney，Thomas A．Williams．数据、模型与决策．北京：机械工业出版社，2003 [20] Frederick S．Hillier，Mark S．Hillier，Jerald J．Lieberman．Introduction to Management Science．Beijing：McGraw - Hill Comanies，Inc．，2001
运筹学基础及应用 习题解答 习题一 P46 (a) 该问题有无穷多最优解，即满足2 1 0664221≤≤=+x x x 且的所有()21,x x ，此时目标函数值3=z 。 (b) 用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。 (a) (1) 图解法
最优解即为?? ?=+=+82594321 21x x x x 的解??? ??=23,1x ，最大值235=z (2)单纯形法 首先在各约束条件上添加松弛变量，将问题转化为标准形式 ???=++=+++++=8 25943 ..00510 max 421321 4321x x x x x x t s x x x x z 则43,P P 组成一个基。令021==x x 得基可行解()8,9,0,0=x ，由此列出初始单纯形表 21σσ>。5 839,58min =?? ? ??=θ
02>σ，23 28,1421min =??? ? ?=θ 0,21<σσ，表明已找到问题最优解0 , 0 , 2 3 1,4321====x x x x 。最大值 2 35 *=z (b) (1) 图解法 \\ 最优解即为?? ?=+=+5 24262121x x x x 的解??? ??=23,27x ，最大值217=z (2) 单纯形法 首先在各约束条件上添加松弛变量，将问题转化为标准形式
1234523124125 max 2000515.. 6224 5z x x x x x x x s t x x x x x x =+++++=?? ++=??++=? 则3P ，4P ，5P 组成一个基。令021==x x 得基可行解()0,0,15,24,5x =，由此列出初始单纯形表 21σσ>。245min ,,461θ? ?=-= ?? ? 02>σ，15 33min ,24,5 22θ??== ??? 新的单纯形表为
运筹学基础及应用 P43例13 、混合配料问题:某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如表1-19所示。问该厂每月生产这三种牌号糖果各多少千克，使该厂获利最大。试建立这个问题的线性规划的数学模型。 表1-19 甲乙丙原料成本(元/kg) 每月限制用量(kg) A 2.00 2000 ?60% ?30% B 1.50 2500 C 1.00 1200 ?20% ?50% ?60% 0.50 0.40 0.30 加工费(元/kg) 3.40 2.85 2.25 售价(元/kg) P44例14、投资项目的组合问题:兴安公司有一笔30万元的资金，考虑今后三年内用于下列项目的投资: (1) 三年内的每年年初均可投资，每年获利为投资额的20%，其本利可一起用于下一年投资; (2) 只允许第一年初投入，于第二年末收回，本利合计为投资额的150%，但此类投资限额不超过15万元; (3) 允许于第二年初投入，于第三年末收回，本利合计为投资额的160%，但限额投资20万元; (4) 允许于第三年初投入，年末收回，可获利40%，但限额为10万元。 试为该公司确定一个使第三年末本利和为最大的投资组合方案。 P44例15、生产、库存与设备维修综合计划的安排:红光厂有2台车床，1台钻床，1台磨床，承担4中产品的生产任务(已知生产各种产品所需的设备台时及生
产单位产品的售价如表,,20所示(对各种产品今后三个月的市场最大需求(小于最大需求量时即可全部销出)及各产品在今后三个月的生产成本分别如表1,21和表1,22所示( 上述设备在1~3月内各需进行一次维修,具体安排为:2台车床于2月份、3月份各维修一台,钻床安排在2月份维修,磨床安排在3月份维修.各设备每月工作22天.每天2班,每班8h,每次维修占用半各月时间.又生产出来的产品当月销售不出去(超过最大需求量)时,可在以后各月销售,但需付每件每月储存费5元.但规定每月底各种产品储存量均不得超过100件.1月初各产品无库存,要求3月底各产品均库存50件.试安排该厂各月的生产计划,使总的利润为最大. 表,,20 a值单位:h ij i ? ? ? ? j 车床 ,., ,., ,., 钻床 ,., ,., ,., 磨床 ,., ,., ,., 售价(元,件) ,, ,, ,, ,, 表 1,21 最大需求量单位:件 K ? ? ? ? j 1月 200 300 200 200 2月 300 200 0 300 3月 300 100 400 0 表,,22 产品成本单位:元,件 K ? ? ? ? j ,月 ,, ,, ,, ,, ,月 ,, ,, ,, ,, ,月 ,, ,, ,, ,, P81例1、某食品公司经销的主要产品之一是糖果。它下面设有三个加工厂，每天的糖果生产量分别为:A1—7t,A2—4t,A3—9t.该公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量为:B1—3t,B2—6t,B3—5t,B4—6t.已知
计算题一一 1. 下列线性规划问题化为标准型。 （10分） mi nZ x-|+5x 2-2x 3 min Z 4为 2x 2+3x 3 4x ,+5x 2 6X 3=7 8% 9x 2 10x 3 11 12% 13x 2 14 X 1 0,X 2 无约束，X 3 B1 B2 B3 B4 产量 A1 10 6 7 12 4 16 10 & 9 9 A3 5 4 10 10 4 销S 5 2 4 6 i （i 1,2,3）的投资额为x 时，其收益分别为 g 1（x 1） 4禺4区） g （x 3） 2x3 ，问应如何分配投资数额才能使总收益最大？ （15分） 5.求图中所示网络中的最短路。 （15分） 计算题二 X 1 X 2 X 3 6 2x 1 X 2 3x 3 5 X 1 X 2 10 X 1 0,X 2 0,X 3符号不 限 满足 〈 2. 写出下列问题的对偶问题 （10分） 9x 2,
5.某项工程有三个设计方案。 据现有条件，这些方案不能按期完成的概率分别为 0.5,0.7,0.9, 1某工厂拥有 A,B,C 三种类型的设备，生产甲、乙两种产品，每件产品在生产中需要使用 的机时数， （2）利用单纯形法求最优解；（15分） 2、用对偶理论判断下面缰性规划是否存在最优解：〔10分）屮 maxz = 2孔 +2x 3 * 满足： J 対+ 2皿叫 3. 判断下表中的启案能否作为恚上作业法求解运输间题的初始启宪，说朋理由.ho 分 n 4.如图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要 从V l 出发，经过这个交通网到达 V8，要寻求使总路程最短的线路。 （15分） ■.■'2 1