运筹学1210ppt课件

一、 线性规划的图解法：例 1. Max Z = 4X1 + 3X2s.t 2X1 + 3X2 = 0 (5)1.2 线性规划问题的解和 单纯形法单纯形法X243210 1 2 3 X1 (5)(4) (2)(3)DE C( 1.5, 1 )(1)(5)A BZ=4 Z=6 Z=9解空间2X1 + 3X2 = 6 3X1 + 2X2 = 32X2 = 52X1 + X2 = 4Max Z = 4X1 + 3X2 s.t 2X1 + 3X2 = 0 (5)最优解：极点 CX1=1.5 , X2=1Max Z = 9极点X243210 1 2 3 X1 Z=20(5)(4) (2)(3)DEC( 1.5, 1 )(1)A B解空间最优解：极点 BX1=2 , X2=0Max Z = 20Max Z = 4X1 + 3X2 s.t 2X1 + 3X2 = 0 (5)Max Z=10x1+x2X243210 1 2 3 X1 Z=483/13(5)(4) (2)(3)DEC( 1.5, 1 )(1)A B解空间最优解：极点 DX1=3/13 , X2=24/13Max Z = 483/13Max Z = 4X1 + 3X2 s.t 2X1 + 3X2 = 0 (5)Max Z=x1+20x2X243210 1 2 3 X1 Z=0(5)(4) (2)(3)DEC( 1.5, 1 )(1)A B解空间最优解：极点 AX1=0 , X2=0Max Z = 0Max Z = 4X1 + 3X2 s.t 2X1 + 3X2 = 0 (5)Max Z= - x1 - x2X243210 1 2 3 X1 Z=6(5)(4) (2)(3)DEC(1)A B解空间最优解：极点 D,C和 C， D之间的点。Max Z = 6Max Z = 4X1 + 3X2 s.t 2X1 + 3X2 = 0 (5)Max Z= 2 x 1 + 3x2解空间 ： (可行域 )，所有满足约束条件的点的集合。 解空间的顶点称为 极点 ： 线性规划模型最优解存在的话，则一定可以线性规划模型最优解存在的话，则一定可以在某个极点处得到。在某个极点处得到。极点的代数性质：把例 1. 化为标准形式Max Z = 4X1 + 3X2 + 0S1 + 0S2 + 0S3 + 0S4 s.t 2X1 + 3X2 + S1 = 6 3X1 + 2X2 + S2 = 32X2 + S3 = 52X1 + X2 + S4 = 4X1, X2, S1, S2, S3, S4 = 0 X243210 1 2 3 X1 Max Z = 4X1 + 3X2 s.t 2X1 + 3X2 = 0 (5)(5)(4) (2)(3)DEC( 1.5, 1 )(1)A BZ=9解空间极点 零变量A : X1 = X2 = 0 B : X2 = S4 = 0C : S1 = S4 = 0D : S1 = S2 = 0E : X1 = S2 = 0Max Z = 4X1 + 3X2 + 0S1 + 0S2 + 0S3 + 0S4 s.t 2X1 + 3X2 + S1 = 6 3X1 + 2X2 + S2 = 32X2 + S3 = 52X1 + X2 + S4 = 4X1, X2, S1, S2, S3, S4 = 0非极点 :至多只有一个变量等于零 ; 极点 :至少有二个变量等于零 :结论 : 可行域中的点 : 非极点 :至多只有一个变量等于零 ; 极点 :至少有二个变量等于零 :故我们可以在约束条件方程组中，令若干个变量等于零而求出一组解，它可能即为极点，是最优解可能出现的地方 。+ S1 = 6+ S2 = 3+ S3 = 5+ S4 = 4得解： X1=0， X2=0， S1=6 , S2=3, S3=5, S4=4 。即为基本可行解 A 点 , MaxZ=0。对此 基本可行解， X1， X2称为非基变量，S1, S2, S3, S4称为基变量，基变量 (S1, S2, S3, S4 ） 组成基。在前面例子的约束条件中：2X1 + 3X2 + S1 = 6 3X1 + 2X2 + S2 = 3 2X2 + S3 = 52X1 + X2 + S4 = 4X1, X2, S1, S2, S3, S4 = 0令 X1， X2=0 得方程组：在前面例子的约束条件中：2X1 + 3X2 + S1 = 6 3X1 + 2X2 + S2 = 3 2X2 + S3 = 52X1 + X2 + S4 = 4X1, X2, S1, S2, S3, S4 = 03X2 = 62X2 + S2 = 32X2 + S3 = 5X2 + S4 = 4 得解： X1=0， X2=2， S1=0 , S2= -1, S3=1, S4=2 为不可行基本解，舍弃。令 X1， S1=0 得方程组：3X2 +S1 = 62X2 = 32X2 + S3 = 5X2 + S4 = 4 得解： X1=0， X2=3/2， S1=3/2 , S2= 0, S3=2, S4=5/2 即为基本可行解 E点， MaxZ=9/2。对此 基本可行解， X1， S2 称为非基变量，X2, S1, S3, S4称为基变量，基变量（ X2, S1, S3, S4）组成基。在前面例子的约束条件中：2X1 + 3X2 + S1 = 6 3X1 + 2X2 + S2 = 3 2X2 + S3 = 52X1 + X2 + S4 = 4X1, X2, S1, S2, S3, S4 = 0令 X1， S2=0 得方程组：2X1 + 3X2 = 6 3X1 + 2X2 + S2 = 3 2X2 + S3 = 52X1 + X2 = 4得解： X1=3/2， X2=1， S1=0, S2=11/2, S3=3, S4=0 即为基本可行解 C点， MaxZ=9。对此 基本可行解， S1， S4 称为 非基变量 ，X1 , X2, S2, S3称为基变量， 基变量 （ X1 , X2, S2, S3）组成基。在前面例子的约束条件中：2X1 + 3X2 + S1 = 6 3X1 + 2X2 + S2 = 3 2X2 + S3 = 52X1 + X2 + S4 = 4X1, X2, S1, S2, S3, S4 = 0令 S1， S4=0 得方程组：一般的对有 m+ n个变量（ 决策变量、松弛变量 ）， m个约束方程的线性规划模型令其中 n 个变量等于零，解剩下的 个变量， 个约束方程的方程组，求出一组解：称为 基本解 。相对这个基本解：个令为零的变量，称为 非基变量 。其它的 个变量，称为 基变量 ，这些基变量的集合称为 基 。 基本解满足非负性约束条件，称为 基本可行解，否则称为 不可行解 。基本可行解即对应于 极点 。个线性方程组。故要考虑改进，从而得到解线性规划 单纯形方法 。求解线性规划的基本思路：对约束条件方程组，依次令 n个变量为零求出共 个基本解，如解不可行（有变量的值为负），则舍去，否则是基本可行解，则计算相应的目标函数值，最后，从这些目标函数值集合中找到最优解。但如此求解， 计算量是很大的，要解线性规划问题各类解的关系示意图：下列方框表示所以满足约束方程组的解 X 。不可行解可行解X 0X 0基本可行解 非基本可行解基本解 非基本解基本 最优解 非基本 最优解有限个解 可用基本解