运筹学期末复习资料.doc

( 1) max z=-2 1x - 2x + 3x + 4x 1x - 2x +2 3x - 4x =2 2 1x + 2x -3 3x + 4x =6 1x + 2x + 3x + 4x =7 1x , 2x , 3x , 4x? 0 2. 下表是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量, 1a , 2a , 3a , d, 1c , 2c 为待定常数, 试说明这些常数分别取何值时,以下结论成立。( 1 )表中解为唯一最优解;( 2 )表中解为最优解,但存在无穷多最优解;( 3 )该线性规划问题具有无界解;( 4 )表中解非最优,对解改进,换入变量为 1x ,换出变量为 6x 。基 b 1x 2x 3x 4x 5x 6x 3x d4 1a 10 2a 0 4x 2 -1 -301 -10 6x 3 3a -500 -41 j j c z ? 1c 2c 00 -30 解: ( 1 )有唯一最优解时, d? 0, 1c? 0, 2c ? 0 ( 2) 存在无穷多最优解时, d? 0, 1c? 0, 2c =0或 d? 0, 1c =0 , 2c? 0. ( 3 )有无界解时, d? 0, 1c? 0, 2c? 0且 10a?( 4 )此时,有 d? 0, 1c ? 0 并且 1c? 2c , 30a?, 3/ 3a ? d/4 3. 已知线性规划问题应用对偶理论证明该问题最优解的目标函数值不大于 25. 4. 用对偶单纯形法求解下列线性规划问题: c j-3-2-1000 C Bx Bbx 1x 2x 3x 4x 5x 6 0x 460x 5-40x 6-4 111100 -101010 0-11001 c j-z j-3-2-1000 0x 42-3x 140x 6-4 012110 10-10-10 0-11000 c j-z j0-2-40-30 0x 4-2-3x 14-2x 24 003111 10-10-10 01-100-1 c j-z j00-70-3-2 x 4 为- 2 ,无法迭代,此题无解。 5. 已知线性规划问题 ma xZ=2x 1 +x 2 +5x 3 +6x 4 其对偶问题的最优解为 Y l ﹡=4,Y 2 ﹡=1 ,试应用对偶问题的性质求原问题的最优解。解:原问题的对偶问题为 min w=8y 1 +12y 2s· t 2y 2 +2y 2≥ 2 2y 2≥1y 1 +y 2≥ 5y 1 +2y 2≥6y 1,y 2≥0把y *1 =4,y *2 =1 代入上式,可知头两个约束为严格不算式,则 X *1 =0, X *2 =0, 可得 X 3 +X 4 =8 解得: X *3 =4 X 3 +2X 4 =12 X *4 =4 则原问题最优解为 X *=(0,0,4,4) T, Z*=44 6. MaxZ=3X 1 +4X 2X 1 +X 2≤5 2X 1 +4X 2≤ 12 3X 1 +2X 2≤ 8X 1 ,X 2≥0 其最优解为: 基变量 X 1X 2X 3X 4X 5 X 3 3/2 001 -1/8 -1/4 X 2 5/2 010 3/8 -1/4 X 11100 -1/4 1/2 σj000 -3/4 -1/2 1)