运筹学之线性规划的标准型及单纯形法.ppt
1 1线性规划的标准型及线性规划的标准型及单纯形法单纯形法2 23 3线性规划的标准型（线性规划的标准型（SLP）Maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm x1,x2,xn04 4标准型的特征标准型的特征目标函数极大化目标函数极大化约束条件为等式约束条件为等式决策变量非负决策变量非负5 5线性规划的标准型线性规划的标准型代数式代数式 Maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm x1,x2,xn0 （xj 0 j=1,2,n）6 6线性规划的标准型线性规划的标准型和式：和式：7 7线性规划的标准型线性规划的标准型向量式：向量式：8 8线性规划的标准型线性规划的标准型矩阵式：矩阵式：9 9非标准型转化为标准型非标准型转化为标准型目标函数极小化转为极大化：目标函数极小化转为极大化：minZ=-max(-Z)，一个数的极小化等价于其相反数的极，一个数的极小化等价于其相反数的极大化。大化。不等式约束的转化：不等式约束的转化：aijxjbi 加入松弛变量加入松弛变量 aijxjbi 减去剩余变量减去剩余变量非正变量：即非正变量：即xk 0 则令则令xk=-xk 自由变量：即自由变量：即xk无约束，令无约束，令xk=xk-x”k1010非标准型转化举例非标准型转化举例之一之一maxZ=70X1+120X2 maxZ=70X1+120X2 9X1+4X2 360 9X1+4X2+X3=360 4X1+5X2 200 4X1+5X2 +x4=200 3X1+10X2300 3X1+10X2 +x5=300 X10 X20 X10 X20 X3 0 x4 0 x5 0 1111非标准型转化举例非标准型转化举例之二之二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 1212非标准型转化举例非标准型转化举例之三之三minZ=-3x1-x2+4x3-x1+2x2+x3=5x1-x2+x3-6x1 0 x2 0 x3无约束无约束1313非标准型转化举例非标准型转化举例之三之三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 x401414基可行解秩基基可行解1515秩设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）,mn1616基基基的概念基的概念：如前所述：如前所述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处在变量转换的交叉点上，称之为枢轴元素处在变量转换的交叉点上，称之为枢轴元素2525单纯形法解题举例单纯形法解题举例单纯形表的格式：单纯形表的格式：CjC1 C2 CN i CBXBbX1 x2 .Xn C1 C2 CMX1X2XMb 1B2bma11 a12 a1na21 a22 a2n am1 am2 amn 1 2 m j 1 2 n 2626产品产品A产品产品B资源限制资源限制劳动力劳动力设备设备原材料原材料9434510360工时工时200台时台时300公斤公斤单位产品利单位产品利润（元）润（元）70120w某厂生产两种产品，需要三种资源，已知各某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源产品的利润、各资源的限量和各产品的资源消耗系数如下表：消耗系数如下表：2727问题：如何安排生产计划，使得获利最多？问题：如何安排生产计划，使得获利最多？步骤：步骤：1、确定决策变量：设生产、确定决策变量：设生产A产品产品x1kg,B产品产品x2kg2、确定目标函数：、确定目标函数：maxZ=70X1+120X23、确定约束条件：、确定约束条件：人力约束人力约束 9X1+4X2360 设备约束设备约束 4X1+5X2 200 原材料约束原材料约束3X1+10X2 300 非负性约束非负性约束X10 X202828 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 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.22929 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 -2 0 03030单纯形法的计算步骤单纯形法的计算步骤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、重复第二步到第五步、重复第二步到第五步3131单纯形法的进一步探讨单纯形法的进一步探讨极小化问题直接求解：检验数的判别由极小化问题直接求解：检验数的判别由j 0 变为变为j 0人工变量法之一：大人工变量法之一：大M法法 人工变量价值系数人工变量价值系数M例例 人工变量法之二：构造目标函数，分阶段求解例人工变量法之二：构造目标函数，分阶段求解例无穷多最优解情形：非基变量检验数无穷多最优解情形：非基变量检验数 j=0退化解的情形：有两个以上退化解的情形：有两个以上 值相等值相等3232单纯形法的计算机求解单纯形法的计算机求解程序说明程序说明应用举例应用举例例题例题1例题例题2
