运筹学线性规划设计.ppt

x2 50 40 30 20 10 10 20 30 40 x1 可行域 目标函数是以Z作为参数的一组平行线 x2 =Z /30-（5/3）x1 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当Z值不断增加时，该直线 x2 =Z /30-（5/3）x1 沿着其法线方向向右上方移动。 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当该直线移到Q2点时，Z（目标函数）值达到最大： Max Z=50?15+30 ? 20=1350 此时最优解=（15，20） Q2（15，20） 二个重要结论： 满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。 最优解必定能在凸多边形的某一个顶点上取得，这一事实也可以推广到更多变量的场合。 二、解的讨论： 最优解是唯一解； 无穷多组最优解： 例1.1的目标函数由 max Z=50x1+30x2 变成： max z=40x1+30x2 s.t. 4x1+3x2 ? 120 2x1+x2 ? 50 x1,x2 ? 0 x2 50 40 30 20 10 10 20 30 40 x1 可行域 目标函数同约束条件：4x1+3x2 ? 120平行的直线 x2 =Z /30-（4/3）x1 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当Z的值增加时，目标函数同约束条件：4x1+3x2 ? 120 重合，Q1与Q2之间都是最优解。 Q1（25，0） Q2（15，20） 解的讨论： 无界解： 例：max S=x1+x2 s.t. -2x1+x2 ? 40 x1-x2 ? 20 x1,x2 ? 0 x2 50 40 30 20 10 10 20 30 40 x1 该可行域无界，目标函数值可增加到无穷大，称这种情况为无界解或无最优解。 解的讨论： 无可行解： 例：max z=2x1+3x2 s.t. x1+2x2 ? 8 x1 ? 4 x2 ? 3 -2x1+x2 ? 4 x1,x2 ? 0 该问题可行域为空集，即无可行解，也不存在最优解。 解的情况： 有可行解 ⊙有唯一最优解 ⊙有无穷最优解 ⊙无最优解 满足约束条件的解X=（x1，x2，¨¨¨ xn ）T 称为线性规划问题的可行解，其中满足目标函数的可行解称为最优解 无可行解 二、线性规划问题解的概念 线性规划标准型的矩阵形式： Max Z = CX （1-9） s.t. AX=b （1-10） X ? 0 （1-11） a11 a12 …. a1n b1 A= a21 a22 …. a2n b = b2 …………………………… ………… am1 am2 …. amn bn c1 x1 0 c2 x2 0 C= X=