第四章线性规划的标准型及单纯形法

1、运运 筹筹 学学 硕士生导师硕士生导师 Operations Research顶点。最优的点，最终达到目标函数转换到另一个更好的顶某个顶点开始，基本思路：从可行域的单纯形算法线性规划的重要算法：个算法之一。年来最成功的提出，是近年由美国人10100.1947DantzigBG Maxz=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm x1,x2,xn0 目标函数极大化目标函数极大化 约束条件为等式约束条件为等式 决策变量非负决策变量非负 代数式代数式 Maxz=c1x1+c2x2

2、+cnxns.t. a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm x1,x2,xn0 （xj 0 j=1,2,n） 和式：和式：njxmibxaTSxcMaxZObjjijnjijnjjj, 2 , 10, 2 , 1.:11 向量式：向量式： TnnnjijnjjxxxxxxXcccCnjxmibxpTSCXMaxZObj,),(, 2 , 10, 2 , 1.:2121211 矩阵式：矩阵式： mnmmnTmaaaaaaaaaAbbbBXBAXTSCXMaxZObj211222211121121),(0.: 目

3、标函数极小化转为极大化：目标函数极小化转为极大化： minZ=-max(-Z) ，一个数的极小化等价于其相反数的极，一个数的极小化等价于其相反数的极大化。大化。 不等式约束的转化：不等式约束的转化： aijxjbi 加入松弛变量加入松弛变量 aijxjbi 减去剩余变量减去剩余变量 非正变量：即非正变量：即xk 0 则令则令xk =- xk 自由变量：即自由变量：即xk无约束，令无约束，令xk= xk- x”kmaxZ=70X1+120X2 maxZ=70X1+120X2 9X1+4X2 360 9X1+4X2+X3=360 4X1+5X2 200 4X1+5X2 +x4=200 3X1+10

4、X2300 3X1+10X2 +x5 =300 X10 X20 X10 X20 X3 0 x4 0 x5 0 minZ=x1+2x2-3x3 maxZ=x1-2x2+3(x3- x”3) x1+x2+x3 9 -x1+x2+x3- x”3 + x4=9 -x1-2x2+x3 2 x1-2x2+x3 - x”3 - x5= 2 3x1+x2-3x3=5 - 3x1+x2-3(x3 - x”3 )=5 x1 0 x2 0 x3无约束无约束 x1 0 x2 0 x3 0 x”3 0 x40 x50 minZ=-3x1-x2+4x3-x1+2x2+x3 =5x1-x2+x3 -6x1 0 x2 0 x

5、3无约束无约束minZ=-3x1-x2+4x3 maxZ=-3x1+x2-4(x3- x”3) -x1+2x2+x3 =5 x1+2x2+x3- x”3 =5 x1-x2+x3 -6 x1+x2-（x3 - x”3 ）+x4= 6 x1 0 x2 0 x3无约束无约束 x1 0 x2 0 x3 0 x”3 0 x40 秩 基 基可行解 设mn矩阵A中有一个r阶子式D不等于零，而所有r+1阶子式（如果存在的话）全等于零，则称D为矩阵A的最高阶非零子式，称数r为矩阵A的秩，记作R(A)=r。 零矩阵的秩为零。 mn矩阵A的秩R(A)min m,n 假设：约束方程组的系数矩阵A的秩为m（R(A)=m

6、）,mn基的概念基的概念：如前所述：如前所述LP标准型标准型和式：和式：maxZ= cjxj aijxj=bi xj 0 j=1,2,n 矩阵式：矩阵式：maxZ=CX AX=b X 0 约束方程的系数矩阵约束方程的系数矩阵A的秩为的秩为m，且，且m0 = bL/ aLk 。 这时原基变量这时原基变量XL=0，由基变量变成非基变量，由基变量变成非基变量aLk处在变量转换的交叉点上，称之为枢轴元素处在变量转换的交叉点上，称之为枢轴元素单纯形表的格式：单纯形表的格式： CjC1 C2 CN i CBXBbX1 x2 . Xn C1 C2 CMX1X2XMb 1B2bma11 a12 a1na21

7、a22 a2n am1 am2 amn 1 2 m j 1 2 n 产品产品A产品产品B资源限制资源限制劳动力劳动力设备设备原材料原材料9434510360工时工时200台时台时300公斤公斤单位产品利单位产品利润（元）润（元）70120w某厂生产两种产品，需要三种资源，已知各某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源产品的利润、各资源的限量和各产品的资源消耗系数如下表：消耗系数如下表： 问题：如何安排生产计划，使得获利最多？问题：如何安排生产计划，使得获利最多？ 步骤：步骤：1、确定决策变量：设生产、确定决策变量：设生产A产品产品x1kg,B产品产品x2kg

8、2、确定目标函数：、确定目标函数：maxZ=70X1+120X23、确定约束条件：、确定约束条件： 人力约束人力约束 9X1+4X2360 设备约束设备约束 4X1+5X2 200 原材料约束原材料约束3X1+10X2 300 非负性约束非负性约束X10 X20 Cj70 120 0 0 0CBXBbX1 X2 X3 X4 X5i 0 0 0X3X4X5360200300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1 904030j0 70 120 0 0 0 0 0 120X3X4X224050 30 7.8 0 1 0 -0.4 2.5 0 0 1 -0.5 0.3 1 0

9、 0 0.130.7620100j3600 34 0 0 0 -12070120X3X1X2842024 0 0 1 -3.12 1.16 1 0 0 0.4 -0.2 0 1 0 -0.12 0.16j4280 0 0 0 -13.6 -5.2 Cj3 -3 0 5 -1CBXBbX1 X2 X3 X4 X5i 3 -3 -1X1X2X512127 1 0 -2 2 0 0 1 -2 0 0 0 0 - 4 3 112/2=6- 27/3=96 0 0 - 4 2 0 5 -3 -1X4X2X56191/2 0 -1 1 0 0 1 -2 0 0 -3/2 0 -1 0 118 -1 0 -

10、2 0 0 1、找到初始可行基，建立单纯形表、找到初始可行基，建立单纯形表 2、计算检验数，若、计算检验数，若j 0 则得最优解。否则转下步则得最优解。否则转下步 3、若某、若某K 0而而PK 0 ，则最优解无界，否则转则最优解无界，否则转下步下步 4、根据、根据max j = K 原则确定原则确定XK 进基变量；根进基变量；根据据规则规则 = min bi / aik aik 0 = bl/ alk 确定确定XL出出基变量基变量 5、以、以alk 为枢轴元素进行迭代为枢轴元素进行迭代 6、重复第二步到第五步、重复第二步到第五步 极小化问题直接求解：检验数的判别由极小化问题直接求解：检验数的判别由j 0 变为变为j 0 人工变量法之一：大人工变量法之一：大M法法 人工变量价值系数人工变量价值系数M例例 人工变量法之二：构造目标函数，分阶段求