(运筹学复习资料.docVIP

?1、分别用图解法和单纯形法求解下面的线性规划问题 Max z=2x1+x2 s.t 3x1+5x2≤15 6x1+2x2≤24 X1,x2≥0 解： 1）图解法： 由上图可知，B点为最优点，最优解为（15/4,3/4），最优值为　z=33/4 2）单纯形法： 将上述线性规划问题化为标准形： Max z=2x1+x2 s.t 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 s.T x1+2x2+2x3+3x4 ≤ 20 2x1+x2+3x3+2x4≤20 x1 ,x2 ,x3 , x4 , ≥0 其对偶问题的最优解为W=(1.2,0.2)T，试根据对偶理论求出原问题的最优解 解，该原问题的对偶问题为： min Y=20w1+20w2 s.T w1+2w2 ≥1　　 (1) w1+2w21 x1=0 2w1+w2 ≥ 2 (2) 2w1+w22 x2=0 2w1+3w2 ≥ 3 (3) 2w1+3w2=3 3w1+2w2 ≥ 4 (4) 3w1+2w2=4 w1,w2 ≥ 0 将对偶问题的最优解代入，得到(1),(2)为严格不等式，故由互补松驰性质得到 X1=x2=0 又w1,w20，由松驰性质得到原问题约束条件应取等号即 w10 2x3+3x4=20 w2 0 3x3+2x4=20， 解方程组，得x3=x4=4 所以原问题的最优解为：X=(0,0,4,4)T 3已知线性规划问题 Max z=2x1+x2+5x3+6x4 s.T 2x1 + x3+ x4 ≤ 8 2x1+2x2+x3+2x4≤12 x1 ,x2 ,x3 , x4 , ≥0 其对偶问题的最优解为w=(4,1)T，试根据对偶理论求出原问题的最优解 解，该原问题的对偶问题为： min Y=8w1+12w2 s.T 2w1+2w2 ≥2　　 (1) 2w1+2w22 x1=0 2w2 ≥ 1 (2) 2w21 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,w20，由松驰性质得到原问题约束条件应取等号即 W10 x3+x4=8 W20 x3+2x4=12，解方程组，得x3=x4=4 所以原问题的最优解为X=(0,0,4,4)T ?4 A工厂计划生产甲、乙两种产品。每千克产品的销售价格和能源消耗量、以及能源资源见表3-26，怎样安排生产计划才能使A工厂获益最大？ 解：x1：产品甲的计划生产量；x2：产品乙的计划生产量，则有如下线性规划问题： max z=7x1 + 12x2 (总销售收入) s.t. 9x1 + 4x2≤ 360 (煤资源限制) 4x1 + 5x2?≤ 200 (电资源限制) 3x1 + 10x2? ≤300 (油资源限制) x1 ?≥ 0，x2 ≥ 0 (非负条件) 用单纯形法求解得：x1=20，x2=24。 原问题的最优解为X＝(20,24)T,对应的对偶价格， 也就是影子价格为(0,1.36,0.52) ?5 已知企业关于获利的线性规划问题如下所示： Max z=-5x1+5x2+13x3 s.T -x1+x2+3x3 ≤ 20 12x1+4x2+10x3≤90