[管理学]线性规划与单纯形方法01.ppt

x2 50 40 30 20 10 10 20 30 40 x1 可行域 当该直线移到Q2点时，S（目标函数）值达到最大： Max S=50*15+30*20=1350 此时最优解=（15，20） Q2（15，20） 二个重要结论： 满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。 二个重要结论： 满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。 最优解必定能在凸多边形的某一个顶点上取得，这一事实也可以推广到更多变量的场合。 解的讨论： 最优解是唯一解； 解的讨论： 最优解是唯一解； 无穷多组最优解： 例1的目标函数由 max S=50x1+30x2 变成： max S=40x1+30x2 s.t. 4x1+3x2 ? 120 2x1+x2 ? 50 x1,x2 ? 0 例1 max S=50x1+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 = S/30-（4/3）x1 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当S的值增加时，目标函数同约束条件：4x1+3x2 ?120 重合，Q1与Q2之间都是最优解。 Q1（0，40） 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 该可行域无界，目标函数值可增加到无穷大，称这种情况为无界解或无最优解。 -2x1+x2 ? 40 x1-x2 ? 20 解的讨论： 无可行解： 例：max S=2x1+3x2 s.t. x1+2x2 ? 8 x1 ? 4 x2 ? 3 -2x1+x2 ? 4 x1,x2 ? 0 该问题可行域为空集，即无可行解，也不存在最优解。 解的情况： 有可行解 ⊙有唯一最优解 ⊙有无穷最优解 ⊙无界解(无最优解） 无可行解 线性规划问题解的概念 线性规划标准型的矩阵形式： Max S = 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