运筹学课后习题三

1、运筹学课后习题三 习题三 3.1某公司今后三年内有五项工程可以考虑投资。每项工程的期望收入和年度费用(万元)如表3-10所示。 表3-10 工 程 1 2 3 4 5 资金拥有量 费 用 第一年 第二年 第三年 5 1 8 4 7 2 5 9 l 如何投资使总收益最大，建立该问题的数学模型，说明是什么模型，可以用什么方法求解。 图3-10 表3-11 地址i 1 2 3 4 5 6 7 8 9 10 11 12 投资额(万元) 900 1200 1000 750 680 800 720 1150 1200 1250 850 1000 收益（万元） 400 500 450 350 300 400

2、 320 460 500 510 380 400 【解】设xj为投资第j个点的状态，xj=1或0，j=1,2,12 maxz?400x1?500x2?450x3?400x12?900x1?1200x2?1000x3?850x11?1000x12?9000?44771212 ?x?2,x?3,x?1,x?2,x?3,x?4?j?jjjjjj?1j?5j?5j?8j?8?j?1?x?1或0，j?1,?,12?j最优解：x1x5=x12=0，其余xj=1,总收益z=3870万元，实际完成投资额8920万元。 3.3 一辆货车的有效载重量是20l maxz?5x1?8x2?4x3?6x4?7x5?3x

3、6?6x1?5x2?3x3?4x4?7x5?2x6?20?3x1?7x2?4x3?5x4?6x5?2x6?56 ?x4?x5?0?x?x?12?1?xj?0或13.4 女子体操团体赛规定：（1）每个代表队由5名运动员组成，比赛项目是高低杠、平衡 木、鞍马及自由体操。（2）每个运动员最多只能参加3个项目并且每个项目只能参赛一次；（3）每个项目至少要有人参赛一次，并且总的参赛人次数等于10；（4）每个项目采用10分制记分，将10次比赛的得分求和，按其得分高低排名，分数越高成绩越好。已知代表队5名运动员各单项的预赛成绩如表3-13所示。 表3-13 甲 乙 丙 丁 戊 高低杠 平衡木 鞍马 自由体操

4、 8.6 9.2 8.8 8.5 8.0 9.7 8.3 8.7 7.8 9.4 8.9 8.5 9.3 9.5 8.2 9.4 8.1 9.6 7.9 7.7 怎样安排运动员的参赛项目使团体总分最高，建立该问题的数学模型。 【解】设xij（i=1，2，5；j1，2，3，4）为第i人参赛j项目的状态，即 ?1xij?0第i人参赛j项目 第i人不参赛j项目54记第i人参赛j项目的成绩为cij,，目标函数 maxz?cijxij i?1j?1每个运动员最多只能参加3个项目并且每个项目只能参赛一次,约束条件： xi1?xi2?xi3?xi4?3i?1,2,?,5 每个项目至少要有人参赛一次，并且总的

5、参赛人次数等于10，约束条件： x1j?x2j?x3j?x4j?x5j?1j?1,2,3,4 ?xi?1j?154ij?10 数学模型为 maxz?cijxiji?1j?154?xi1?xi2?xi3?xi4?3i?1,2,?,5?x?x?x?x?x?1j?1,2,3,4 2j3j4j5j?1j?54?xij?10?i?1j?1?xij?1或0,i?1,2,?,5;j?1,2,3,43.5利用01变量对下列各题分别表示成一般线性约束条件 （1）x1+2x28、4x1+x210及2x1+6x218 三个约束中至少两个满足 （2）若x15，则x210，否则x28 （3）x1取值2，4，6，8中的一

6、个 ?x1?2x2?8?y1m?x1?5?ym?x?5?(1?y)m?x1?2y1?4y2?6y3?8y4?4x1?x2?10?y2m1?【解】(1)?2x1?6x2?18?y3m (2)?x?10?ym(3)?y1?y2?y3?y4?1?2?y?y?y?1?y?0或1，j?1,2,3,4?x?8?(1?y)m122?j?2 ?y?0或1?yj?0或1，j?1,2,36考虑下列数学模型 minz?f(x1)?g(x2) 其中 ?10?6x1,若x1?0?15?10x2,若x2?0 f(x1)?,g(x2)?0,若x?00,若x?012?满足约束条件 （1）x18或x26 （2）|x1x2|=0

7、，4或8 （3）x1+2x220、2x1+x220及x1+x220 三个约束中至少一个满足 （4）x10，x20 将此问题归结为混合整数规划的数学模型。 minz?10y1?6x1?15y2?10x2?x1?y1m;x2?y2m?x?8?ym3?1?x2?6?(1?y3)m?x1?x2?0y4?4y5?4y6?8y7?8y8【解】?y4?y5?y6?y7?y8?1?x1?2x2?20?y9m?2x1?x2?20?y10m?x1?x2?20?y11m?y?y?y?21011?911?x1?0,x2?0;yj?0或1，j?1,2,?， 7用分枝定界法求解下列ip问题 条件（1）条件（2）条件（3）

8、 条件（4）maxz?x1?x2minz?x1?2x2?x1?x2?10?3x1?2x2?7（1）? （2）? 10x?2x?502x?4x?5?1?122?x,x?0且为整数?x,x?0且为整数?12?12【解】(1)x=(1,2),或x（0,3）z=3 (2) x=(5,0),z=5 8用割平面法求解下列ip问题 maxz?2x1?3x2minz?2x1?3x2?x1?2x2?9?x1?2x2?9（1）? （2）? 2x?x?102x?x?10?1?122?x,x?0且为整数?x,x?0且为整数?12?12【解】(1)x=(3,3),z=15 (2)x=(5,2),z=16 9用隐枚举法求

9、解下列bip问题 ?x1?x2?4x3?5x4?3?5x1?2x2?x3?6?（1）? （2）?3x1?x2?2x3?2x4?4 ?4x1?2x2?x3?7?x1?3x2?2x3?4x4?7?x?0或1，j?1,2,3?j?xj?0或1，j?1,2,3,4?【解】(1)x=(1,1,1),z=8 (2)x=(1,1,1,0),z=4 10用分枝定界隐枚举法求解下列bip问题 maxz?4x1?3x2x3minz?4x1?x2?x3?3x4maxz?4x1?x2?x3?3x4?x1?x2?4x3?5x4?8?x1?5x2?x3?2x4?x5?8?3x?x?2x?2x?4（1）?1 （2）?234

10、?2x1?2x2?3x3?2x4?x5?4x?3x?2x?4x?7234?1?x?0或1，j?1,?,5?j?xj?0或1，j?1,2,3,4?【解】(1)x=(1,0,1,1),z=8 (2)x=(1,1,0,0,0),z=2 minz?3x1?x2?2x3?6x4?x5 习题四 4.1 工厂生产甲、乙两种产品，由、二组人员来生产。组人员熟练工人比较多，工作效率高，成本也高；组人员新手较多工作效率比较低，成本也较低。例如，a组只生产甲产品时每小时生产10件，成本是50元有关资料如表4.21所示。 表4.21 a组 b组 产品售价(元/件) 产品甲 效率(件/小时) 10 8 80 成本(元/件) 50 45 产品乙 效率(件/小时) 8 5 75 成本(元/件) 45 40 二组人员每天正常工作时间都是8小时，每周5天。一周内每组最多可以加班10小时，加班生产的产品每件增加成本5元。 工厂根据市场需求、利润及生产能力确定了下列目标顺序： p1：每周供应市场甲产品400件，乙产品300件 p2：每周利润指标不低于500元 p3：两组都尽可能少加班，如必须加班由组优先加班 建立此生产计划的数学模型。 【解】 解法一：设x1, x2分别为a组一周内正常时间生产产品甲、乙的产量，x3, x4分别为a组一周内加班时间生产产品甲、乙的产量；x5, x6分别为b组一