管理运筹学复习(1)某工厂在计划期内要安排I,n 两种产品的生产.生产单位产品所需的设备台时及两种原材料的消耗以及资源的限制如下表所示:工厂每生产一单位产品I 可获利 50元,每生产一单位产品n 可获利 100元,问工厂应分别生产多少单位产品I 和产品n 才能使获利最多? 解:50X 什100X 2 ;满足约束条件: X i2< 3002X i2< 400 X 2< 250 X i >(2>0o(2):某锅炉制造厂,要制造一种新型锅炉10台,需要原材料为/ 63.5 X 4的锅炉钢管,库存的原材料的长度只有 5500 一种规格,问如何下料,才能使总的用料根数最少?需要多 少根原材料? 解:为了用最少的原材料得到 10台锅炉,需要混合使用 14种下料方案设按14种方案下料的原材料的根数分别为X 123456 7891011121314, 可列出下面的数学模型:f = X 1234567891011121314满足约束条件: 2X 1 + X 2 + X 3+ X 4 > 80X 2+ 3X 5 + 2X 6+ 2X 7+ X $+ X 9+ X 10 羽20 X 3+ X 6+ 2X 8+ X 9+ 3X 11 + X 12+ X 13 >350 X 4+ X 7+ X 9 + 2X 10 + X 12+ 2X 13 + 3X 14 > 10X 1 , X2, X3, X4, X5, X6, X7, X8 , X9 , X10 , X11 , X12, X13 , X14 > 0(3)某公司从两个产地A 1、A 2将物品运往三个销地B 1、B 2、B 3,各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示:应如何调运,使得总运输费最小?解:此运输问题的线性规划的模型如下f =6X ii+4X i2+6X 13+6X21+5X22+5X 23约束条件:X l11213=200X212223 =300X ii2i=150X l222=150X l323=200> 0(1,21,2,3)⑷某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3,各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示:应如何组织运输,使得总运输费为最小?解:这是一个产大于销的运输问题,建立一个假想销地B4,得到产销平衡如下表:(5) 某公司从两个产地 A1、A2将物品运往三个销地 B1、B2、B3,各产地的产量、各销地的销量和各产地运往各销地的每件物品的运输单价如下表所示:解:这是一个销大于产的运输问题,建立一个假想销地A3,得到产销平衡如下表:(6) 某公司在三个地方有三个分厂,生产同一种产品,其产量分别为 300箱、400箱、500箱。
需要供应四个地方的销售,这四地的产品需求分别为400箱、250箱、350箱、200箱。
三个分厂到四个销地的单位运价如下表所示:①应如何安排运输方案,使得总运费为最小?②如果2分厂的产量从400箱提高到了 600箱,那么应如何安排运输方案,使得总运费为最小?③如果销地甲的需求从400箱提高到550箱,而其他情况都同①,那该如何安排运输方案,使得运费为最小?解:①此运输问题的线性规划的模型如下21Xn+17X 12+23X 约束条件:13+25X 14 + 10X 21+15X 22 +30X 23+19 X 24 +23X 31 +21X 32+20X 33 +22X 34 X111213 14=300X21222324 =400X31323334 =500X112131 =400X122232 =250X132333 =350X142434 =200(7) 整数规划的图解法某公司拟用集装箱托运甲、乙两种货物,这两种货物每件的体积、重量、可获利润以及托甲种货物至多托运4件,问两种货物各托运多少件,可使获得利润最大?解:设X12分别为甲、乙两种货物托运的件数,其数学模型如下所示:2X什 3X2约束条件:195X1+273X 2 < 1365,4X i +40X 2 < 140,X i < 4,X i, X2> 0,X i, X2为整数。
(8)指派问题有四个工人,要分别指派他们完成四项不同的工作,每人做各项工作所消耗的时间如下表所示:问应如何指派工作,才能使总的消耗时间为最少?解:弓I入0— 1变量,并令1 -,当指派第i人去完成第j项工作时;I。
,当不指派第i人去完成第j项工作时;此整数规划的数学模型为:15X11+18X12+21X13+24X14+19X21+23X22+22X23+18 X 24+26X 31+17X32+16X 33+19X 34 +19X41 +21X42+23X43+17X44 约束条件:X111213 14 =1 (甲只能干一项工作)X21222324 =1 (乙只能干一项工作)X31323334 =1 (丙只能干一项工作)X41424344 =1 (丁只能干一项工作)X11213141 =1 ( A工作只能一个人干)X12223242 =1 ( B工作只能一个人干)X13233343 =1 ( C工作只能一个人干)X14243444 =1 ( D工作只能一个人干)为 0— 1 变量,(1,2,3,41,2,3,4)(9)有优先权的目标规划的图解法一位投资商有一笔资金准备购买股票, 资金总额为90000元,目前可选的股票有 A 、B 两股票 价格/元 年收益/ (兀/年) 风险系数 A 20 3 0.5 B 50 4 0.2从表可知:股票A 的收益率为(3/20 )X 10015%股票B 的收益率为(4/50 )X 1008%, A 的收益率比B 大,但同时A 的风险也比B 大,这符合高风险高收益的规律。
试求一种投资方案,使得一年的总投资风险不高于 700,且投资收益不低于10000元 解:设X 1、X 2分别表示投资商所购买的股票 A 和股票B 的数量。
1.针对优先权最高的目标建立线性规划 建立线性规划模型如下:d 1+约束条件:20X 1+50X 2三900000.5X 什 0.2X 211-=7003X 1+4X 222- =10000X 1 , X 2 , d 1+, d 2-三 02. 针对优先权次高的目标建立线性规划建立线性规划模型如下:d2-约束条件:20X 1+50X 2三900000.5X 1+0.2X 211- =700 3X 1+4X 222-=10000 d 10X 1 , X 2 , d 1+,d 1-, d 2+, d 2-= 03. 目标规划模型的标准化对于两个不同优先权的目标单独建立线性规划进行求解, 为方便,把他们用一个 模型来表达:+ -P 1(d 1)2(d 2)约束条件: 20X 1+50X 2 三 90000 ,0.5X 1+0.2X 211 =700, 3X 1+4X 222- =10000,X 1 , X 2 , d 1+, d 1 , d 2+, d 2 = 0。
(10)某工厂试对产品A B 进行生产,市场需求并不是很稳定,因此对每种产X 1 4000X 11000 2000 3000 4000 5000品分别预测了在销售良好和销售较差时的预期利润,这两种产品都经过甲、乙两台设备加工,已知产品A和B分别在甲和乙设备上的单位加工时间,甲、乙设备的可用加工时间以及预期利润如表所示,要求首先是保证在销售较差时,预期利润不少于5千元,其次是要求销售良好时,预期销售利润尽量达到1万元。
试建立目标规划模型。
i2+ -P i(d i)2(d2)约束条件:4X 什3X2 三 45,2X 什5X2 三 305X什5X2ii- =50,8X什6X222- =i00,X i , X2 ,,— 0i,2(ii) 动态规划石油输送管道铺设最优方案的选择问题:如图所示,其中A为出发点,E为目的地,B、C、D分别为三个必须建立油泵加压站的地区,其中的B i、B2、B3i、C2、C3i、D2分别为可供选择的各站站点。
图中的线段表示管道可铺设的位置,第四阶段:D i — E 3; D2 — E 4;第三阶段:C i— D i — E 5;C2 — D2— E 8;C3— D i — E 8; C3—D2—E 8 ; 第二阶段:B i — C i — D i — E ii;B i — C2—D2— E ii; B2— C i — D i — E 8;B3—C i — D i — E 9 ; B3—C2 — D2 — E 9;第一阶段:A— B i—C i — D i — E i4; A—B i—C2— D2 — E i4 ;A— B2—C i — D i — E i3 ; A—B3—C i — D i — E i3;A— B3 — C2 — D2—E i3最优解:A— B2— C i — D i — E ; A—B3—C i — D i — E ; A— B3—C2—D2 — E 最优值:i3(i2 )最小生成树问题某大学准备对其所属的7个学院办公室计算机联网,这个网络的可能联通的途径如图所示,图中V1 ,……,V7表示7个学院办公室,图中的边为可能联网的途径,边上的所赋权数为这条路线的长度,单位为百米。
请设计一个网络能联通 7个学院办公室,并使总的线路长度为最短。
③在G2中找到一个圈(V2, V3, V5, V7, V2),去掉其中权数最大的边⑤在G4中找到一个圈(V2, V3, V7, V2),去掉其中权数最大的边[V3 , V7],得图G5,如上图所示⑥在G5中已找不到任何一个圈了,可知 G5即为图G的最小生成树。
这个最小生成树的所有边的总权数为3+3+3+1+2+7=19(13)某一个配送中心要给一个快餐店送快餐原料,应按照什么路线送货才能使送货时间最短。
下7 / 19(18,3)V7表示7个地名,其中 V1表示配送中 边所赋的权数表示开车送原料通过这段 ②{V 1}{ V 2 , V 3, V 4, V 5 , V 6 7},边的集合{[, ] I ,两点中一点属于I,而另一点属 于 J}={[ V i , V 2], [ V i , V 3]},并有S i2ii2=0+4=4 ; S i3ii3=0+18=18(S l213)= S i2 =4给边[V i , V 2]中的未标号的点V 2标以(4, 1),表示从V i 到V 2的距离为4,并且在 V i 到V 2的最短路径上V 2的前面的点为V i.③ 这时{V i , V 2}{V 3 , V 4 , V 5 , V 6 7},边的集合{[ , ] I ,两点中一点属于I,而另一点 属于 J}={[ V i , V 3] , [ V 2 , V 3] , [ V 2 , V 4]},并有S 23223=4+12=16 ; S 24224=4+16=20 ; (S 2324 , S i3)= S 23 =16 给边[V 2 , V 3]中的未标号的点V 3标以(16 , 2)④ 这时{V i , V 2 , V 3}{V 4 , V 5 , V 6 7},边的集合{[ , ] I ,两点中一点属于I,而另一 点属于 J}={[ V 2 , V 4] , [ V 3 , V 4] , [ V 3 , V 5]},并有 S 34334=16+2=18 ; S 35335=16+6=22 ; S 24224 =4+16=20(S 343524)= S 34 =18给边[V 3 , V 4]中的未标号的点V 4标以(18 , 3)⑤ 这时{V i , V 2 , V 3 , V 4}{V 5 , V 6 7},边的集合{[ , ] I ,两点中一点属于I,而另一 点属于 J}={ [ V 4 , V 6] , [ V 4 , V 5] , [ V 3 , V 5]},并有S 46446 = 18+7=25 ; S 45445 = 18+8=26 ; (S 4645 35)= S 35 =24给边[V 3 , V 5]中的未标号的点V 5标以(24 , 3)⑥ 这时{V i , V 2 , V 3 , V 4 , V 5 }{V 6 , V 7},边的集合{[ , ] I ,两点中一点属于 I,而另一点属于 J}={[ V 5 , V 7] , [ V 4 , V 6] },并有S 57557 =22+5=27 ; (S 5746)= S 46 =25给边[V 4 , V 6]中的未标号的点V 6标以(25 , 4) ⑦ 这时{V i , V 2 , V 3 , V 4 , V 5 , V 6 }{ V 7},边的集合{[ , ] I ,两点中一点属于 I,而另一点属于 J}={[ V 5 , V 7] , [ V 6 , V 7] },并有S 67667 =25+6=31 ; (S 5767)= S 57 =27 给边[V 5 , V 7]中的未标号的点V 7标以(27 , 5)⑧ 此时{V i , V 2 , V 3 , V 4 , V 5 , V 6 , V 7}空集,边集合{[ , ] I ,两点中一点 属于I,而另一点属于J}=空集,计算结束。