运筹学课后习题及答案PPT演示课件

1、第二章 线性规划 2.1(1) max z=2x1+x 4x1+ 3x212 2x1+ x28 4x1- x28 x1 0, x20448s.t.0 x1x24x1+ 3x2=122x1+ x2=84x1- x2=8由图知由图知,有唯一最优解有唯一最优解, x*=(9/4,1)t,z*=11/2 2.1(2) max z=3x1+2x -x1+ 2x24 3x1+ 2x214 x1- x23 x1 0, x2014/327s.t.0 x1x2由图知由图知,有无穷多最优解有无穷多最优解, x*=(4,1)+(1- )(5/2,13/4)=(5/2+3 /2,13/4-9 /4), z*=140,

2、1-x1+2x2=43x1+2x2=14x1- x2=3 2.1(3) max z=2x1+3x2 x1- x22 -3x1+ 2x24 x1 0, x20s.t.此线性规划问题无界解此线性规划问题无界解220 x1x2-3x1+2x2=4x1- x2=2 2.1(4) max z=x1+x2 x1- x20 3x1- x2-3 x1 0, x20s.t.220 x1x23x1-x2=-3x1- x2=0此线性规划问题无可行解此线性规划问题无可行解10500cbxbx1x2x3x4b 00 x3x4354210019838/5105000010 x3x1 0 1 14/5 2/5 1 0 -3

3、/5 1/5 21/58/53/24 0 10-216510 x2x101 1 0 5/14 -1/7 -3/14 2/73/210 0 -5/14 -25/1435/22.4（1） 解：首先化标准形式：解：首先化标准形式：j0 x*=(1,3/2,0,0)t， z*=35/2max z=10 x1+5x2 3x1+ 4x2+x3 =9 5x1+2x2 +x4=8 x1, x2, x3, x40 单纯形表为：单纯形表为：100200000cbxbx1x2x3x4x5b 000 x3x4x51121061000100015002001200500-200100200000000200 x3x4x

4、2 2/3 1 1/3 0 0 1 1 0 0 0 1 0 -1/6 0 1/6 300200200450200600 100/3 0 0 0-100/3400000100200 x3x1x2 0 1 0001100-2/31-1/3-1/601/6500/3200400/3 000-100/3-100/3140000/3j0 x*=(200，400/3，500/3,0,0)t， z*=140000/32.4（2）单纯形表为单纯形表为: :解解: :大大m法法:变为标准形式并添加人工变量，则原线性变为标准形式并添加人工变量，则原线性规划问题化为：规划问题化为：2.5（1）max z= 3x1+

5、 2x2 mx6-mx7 x1+ 2x2+ x3 =7 x1- x2 - x4 +x6 =1 x1+ x2 - x5 +x7 =2 x1, x2, x3 , x4 ,x5, x6, x70s.t.0,2172 23 max2121212121xxxxxxxxxxz32000-m-mcbxbx1x2x3x4x5x6x7b0 x3121000077-mx61-10-101011-mx71100-101223+2m20-m-m000 x3031100623x11-10-1001-mx70201-1111/205+2m03+m-m00 x3001-1/23/2 9/233x1100-1/2-1/2 3

6、/2-2x20101/2-1/2 1/2-0001/25/232000-m-mcbxbx1x2x3x4x5x6x7b0 x5002/3-1/313 -3x1101/3-2/30 3-2x2011/31/30 2600-5/34/30130 x50110153x11210070 x40311060-4-30021续表续表j0 x*=(7,0,0,6,5,0,0)t， z*=21两阶段法两阶段法: :第一阶段第一阶段: :min w = x6+x7 x1+ 2x2+ x3 =7 x1- x2 - x4 +x6 =1 x1+ x2 - x5 +x7 =2 x1, x2, x3 , x4 ,x5, x

7、6, x70s.t.0000011cbxbx1x2x3x4x5x6x7b0 x31210000771x61-10-1010111x71100-10122-20011000 x303110-10620 x11-10-10101-1x70201-1-1111/20-20-11100 x3001-1/23/21/2-3/2 9/230 x1100-1/2-1/21/21/2 3/2-0 x20101/2-1/2-1/21/2 1/2-0000011因为基变量中不含人工变量因为基变量中不含人工变量, ,因此进行第二阶段求解因此进行第二阶段求解: :32000cbxbx1x2x3x4x5b0 x3001

8、-1/23/2 9/233x1100-1/2-1/2 3/2-2x20101/2-1/2 1/2-0001/25/20 x5002/3-1/313-3x1101/3-2/303-2x2011/31/302600-5/34/30130 x50110153x11210070 x40311060-4-30021j0 x*=(7,0,0,5,6)t， z*=21解解: :变为标准形式并添加人工变量，则原线性规划问变为标准形式并添加人工变量，则原线性规划问题化为：题化为：2.5（4）max z= -x1- 3x2- 4x3- 3x4-mx7-mx8 3x1+ 6x2+ x3 + 2x4 x5 +x7 =

9、15 6x1+ 3x2 + 2x3 + x4 x6 +x8=12 x1, x2, x3 , x4 ,x5, x6, x7 , x8 0s.t.0,1223615263 343 min4321432143214321xxxxxxxxxxxxxxxxz-1-3-4-300-m-mcbxbx1x2x3x4x5x6x7x8b-mx73612-1010155-mx863210-1011229m-19m-33m-43m-3-m-m00-mx709/203/2-11/21-1/292-1x111/21/31/60-1/601/6240-2/5+9/2m-11/3-17/6+3/2m-m-1/6+1/2m0-

10、3x20101/3-2/91/92/9-1/9218-1x1101/301/9-2/9-1/92/9100-11/3-2-5/91/90 x60903-212-118-1x1121/32/3-1/301/3050-1-11/3-7/3-1/30-5j0 x*=(5,0,0,0,0,18,0,0)t， z*=52.6 线性规划问题线性规划问题max zcx，axb，x0，如如x*是该问题的最优解，又是该问题的最优解，又0为某一常数，分别讨为某一常数，分别讨论下列情况时最优解的变化：论下列情况时最优解的变化：1.目标函数变为目标函数变为max zcx；2.目标函数变为目标函数变为max z（c）x

11、；3.目标函数变为目标函数变为max z x, 约束条件变为约束条件变为 axb c123456161223344556123456min607060. .502030,0wxxxxxxxxxxxxs txxxxxxxxxxxx2.10. 解解:设第设第j（j=1,2, ,6）时段上班的人数为）时段上班的人数为xj142536123456123456m ax201003020025150. .3020,0zyxxyxxyxxys txxxxxxxxxxxxy123456,yxxxxxx设一共植了 棵树，男生中有 人挖坑人栽树人浇水；女生中有 人挖坑人栽树人浇水.2.11 某班有男生某班有男生3

12、0人，女生人，女生20人，周日去植树。根据经验，一人，周日去植树。根据经验，一天男生平均每人挖坑天男生平均每人挖坑20个，或栽树个，或栽树30棵，或给棵，或给25棵树浇水；女棵树浇水；女生平均每人挖坑生平均每人挖坑10个，或栽树个，或栽树20棵，或给棵，或给15棵树浇水。问应怎棵树浇水。问应怎样安排，才能使植树（包括挖坑、栽树、浇水）最多？样安排，才能使植树（包括挖坑、栽树、浇水）最多？ 111213xxx212223xxx313233xxx111213111213212223212223313233313233()()()xxxxxxxxxxxxxxxxxx设该厂每月生产甲品牌糖果千克，其中用原料a 千克，用原料b 千克，用原料c 千克;生产乙品牌糖果千克，其中用原料a 千克，用原料b 千克，用原料c 千克;生产丙品牌糖果千克，其中用原料a 千克，用原料b 千克，用原料c 千克。2.12 某糖果厂用原料某糖果厂用原料a、b、c加工成三种不同牌号的糖果甲、加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中乙、丙。已知各种牌号糖果中a、b、c三种原料的含量要求、三种原料的含量要求、各种原料的单位成本、各种原料每月的限制用量、三种牌号各种原料的单位成本、各种原料每月的限制用量、三种牌号糖果的单位加工费