运筹学复习资料.doc

1 ? 1 、分别用图解法和单纯形法求解下面的线性规划问题 Max z=2x1+x2 3x1+5x2 ≤ 15 6x1+2x2 ≤ 24 X1,x2 ≥0 解: 1) 图解法: 由上图可知, B 点为最优点,最优解为( 15/4,3/4 ) ,最优值为 z=33/4 2) 单纯形法: 将上述线性规划问题化为标准形: Max z=2x1+x2 3x1+5x2+x3=5 6x1+2x2+x4=24 X1,x2,x3,x4 ≥0 利用单纯形法运算得到表一至表三: 由表三可知,线性规划问题的最优解为 X*=(15/4,3/4,0,0)T 目标函数的最优值为 max z=33/4 ? 2 已知线性规划问题 Max z=x1+2x2+3x3+4x4 x1+2x2+2x3+3x4 ≤ 20 2x1+x2+3x3+2x4 ≤ 20 x1 ,x2 ,x3 , x4,≥0 其对偶问题的最优解为 W=(,)T ,试根据对偶理论求出原问题的最优解解,该原问题的对偶问题为: min Y=20w1+20w2 w1+2w2 ≥1 (1) w1+2w2>1 x1=0 2w1+w2 ≥2 (2) 2w1+w2>2 x2=0 2w1+3w2 ≥3 (3) 2w1+3w2=3 2 3w1+2w2 ≥4 (4) 3w1+2w2=4 w1,w2 ≥0 将对偶问题的最优解代入,得到(1),(2) 为严格不等式,故由互补松驰性质得到 X1=x2=0 又 w1,w2>0 ,由松驰性质得到原问题约束条件应取等号即 w1>0 2x3+3x4=20 w2 >0 3x3+2x4=20 , 解方程组,得 x3=x4=4 所以原问题的最优解为: X=(0,0,4,4)T 3 已知线性规划问题 Max z=2x1+x2+5x3+6x4 2x1 + x3+ x4≤8 2x1+2x2+x3+2x4 ≤ 12 x1 ,x2 ,x3 , x4,≥0 其对偶问题的最优解为 w=(4,1)T ,试根据对偶理论求出原问题的最优解解,该原问题的对偶问题为: min Y=8w1+12w2 2w1+2w2 ≥2 (1) 2w1+2w2>2 x1=0 2w2 ≥1 (2) 2w2>1 x2=0 w1+ w2 ≥5 (3) w1+w2=5 w1+2w2 ≥6 (4) w1+2w2=6 w1,w2 ≥0 将对偶问题的最优解代入,得到(1),(2) 为严格不等式,故由互补松驰性质得到 X1=x2=0 又 w1,w2>0 ,由松驰性质得到原问题约束条件应取等号即 W1>0 x3+x4=8 W2>0 x3+2x4=12 ,解方程组,得 x3=x4=4 所以原问题的最优解为 X=(0,0,4,4)T ? 4A 工厂计划生产甲、乙两种产品。每千克产品的销售价格和能源消耗量、以及能源资源见表 3-26 ,怎样安排生产计划才能使 A 工厂获益最大? 解: x1 :产品甲的计划生产量; x2 :产品乙的计划生产量,则有如下线性规划问题: max z=7x1 + 12x2 ( 总销售收入) . 9x1 + 4x2 ≤ 360 ( 煤资源限制) 4x1 + 5x2 ≤ 200 ( 电资源限制) 3x1 + 10x2 ≤ 300 ( 油资源限制) x1≥0, x2≥0( 非负条件) 用单纯形法