运筹学线性规划及单纯形法.pptx

目 录线性规划介绍线性规划数学模型线性规划的图解法 线性规划的单纯形法第1页/共130页问题的提出在现有各项资源条件的限制下，如何确定方案，使预期目标达到最优；或为了达到取其目标，确定使资源消耗最少的方案。第2页/共130页问题的提出例1 美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表1-1所示。问该公司应制造A、B两种家电各多少件，使获取的利润为最大。第3页/共130页第4页/共130页例2、生产计划问题 A B 备用资源 煤 1 2 30 劳动日 3 2 60 仓库 0 2 24 利润 40 50第5页/共130页 x1+2x2 30 3x1+2x2 60 2x2 24 x1，x2 0max Z=40 x1+50 x2解:设产品A,B产量分别为变量x1，x2第6页/共130页问题的提出例3：捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资，已知各月所需仓库面积如表1-2。仓库租借费用随合同期限而定，合同期越长，折扣越大，具体见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积数和期限。该厂可在任何一月办理租借合同，每次办理一份或若干份均可。为使租借费用最小，公司应如何选择签订合同的最优决策？第7页/共130页月份1234所需仓库面积15102012合同租借期限1个月2个月3个月4个月合同期内的租费2800450060007300第8页/共130页例4求：最低成本的原料混合方案 原料 A B 每单位成本 1 4 1 0 2 2 6 1 2 5 3 1 7 1 6 4 2 5 3 8 每单位添 加剂中维生 12 14 8 素最低含量第9页/共130页解：设每单位添加剂中原料i的用量为xi(i=1,2,3,4)minZ=2x1+5x2+6x3+8x4 4x1+6x2+x3+2x4 12 x1+x2+7x3+5x4 14 2x2+x3+3x4 8 xi 0(i=1,4)第10页/共130页补充作业、运输问题 从仓库到工厂运送单位原材料的成本，工厂对原材料的需求量，仓库目前库存分别如表所示，求成本最低的运输方案。工厂 仓库 1 2 3 库存 1 2 1 3 50 2 2 2 4 30 3 3 4 2 10 需求 40 15 35第11页/共130页设xij为i 仓库运到 j工厂的原棉数量(i 1，2，3，j 1，2，3)minZ=2x11+x12+3x13+2x21+2x22+4x23+3x31 +4x32+2x33x11+x12+x13 50 x21+x22+x23 30 x31+x32+x33 10 x11+x21+x31=40 x12+x22+x32=15x13+x23+x33=35 xij 0第12页/共130页一、线性规划模型特点决策变量：向量(x1 xn)T 决策人要考虑和控制的因素非负约束条件：线性等式或不等式目标函数：Z=(x1 xn)线性式，求Z极大或极小线性规划介绍第13页/共130页二、线性规划解决的管理问题：1.合理利用线材问题；合理利用线材问题；2.配料问题；配料问题；3.投资问题；投资问题；4.产品生产计划；产品生产计划；5.劳动力安排；劳动力安排；6.运输问题。运输问题。线性规划介绍第14页/共130页1.要求达到某些数量上的最大化或最小化；要求达到某些数量上的最大化或最小化；2.在一定的约束条件下追求其目标。在一定的约束条件下追求其目标。三、线性规划问题的共同点：线性规划介绍第15页/共130页线性规划的数学模型一、线性规划数学模型的一般形式二、线性规划数学模型的标准形式第16页/共130页用数学语言描述目标函数约束条件解：用变量x1和x2分别表示美佳公司制造家电I和II的数量。第17页/共130页18线性规划的一般式max(min)Z=C1x1+C2x2+Cnxna11x1+a12x2+a1nxn (=,(=,)b)b1 1a21x1+a22x2+a2nxn (=,(=,)b)b2 2 am1x1+am2x2+amnxn (=,(=,)b)bm mxj j 0(0(j=1,n)第18页/共130页简写为：第19页/共130页用矩阵和向量形式表示：第20页/共130页线性规划标准形式线性规划的标准形式目标函数：max约束条件：=变量符号：0第21页/共130页（一）（一）一般式一般式（二）（二）矩阵式矩阵式（三）（三）向量式向量式返回线性规划标准型的几种表示法第22页/共130页(一一)一般型一般型MaxZ=C1X1+C2X2+CnXna11X1+a12X2+a1nXn=b=b1 1a21X1+a22X2+a2nXn=b=b2 2 am1X1+am2X2+amnXn=b=bm mXj j 0(0(j=1,2,n)其中其中 bi 0(0(i=1,2,m)返回第23页/共130页(二二)矩阵型矩阵型maxZ=CXAX=bX 0 0 P P1 1 P P2 2 P Pn n a11 a12 a1n其中其中 A=A=a21 a22 a2n am1 am2 amn X1 X=X2 XnC=(C1 C2 Cn)b1 b=b2 bm返回第24页/共130页(三三)向量型向量型 X1AX=(P1 P2 Pn)X2 =b Xn P1 X1+P2 X2+Pn Xn=b返回第25页/共130页(四四)化标准型化标准型 1.约束条件约束条件 3.变量变量 2.目标函数目标函数返回 4.右端项系数右端项系数第26页/共130页1.约束条件x3为松弛变量x4为剩余变量 松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。当约束条件为“”时，当约束条件为“”时，第27页/共130页例例1 1maxZ=2X1+X2+0X3+0X4+0X5 5x2 15 6x1+2x2 24 x1+x2 5 xi 0+X3 =15 +X4 =24 +X5 =5 松弛变量松弛变量第28页/共130页例例2 2minZ=2X1+5X2+6X3+8X4 4x1+6x2+x3+2x4 12 x1+x2+7x3+5x4 14 2x2+x3+3x4 8 xi 0(i=1,4)-X5 =12 -X6 =14 -X7=8 剩余变量剩余变量 7）+0X5+0X6+0X7第29页/共130页 x1+2x2+x3 =30 3x1+2x2 +x4 =60 2x2 +x5=24 x1,x5 0 0 转化为：maxZ=40 x1+50 x2+0 x3+0 x4+0 x5 x1+2x2 30 3x1+2x2 60 2x2 24 x1，x2 0 例：max Z=40 x1+50 x2松弛变量第30页/共130页例:4x1+6x2+x3+2x4 12 x1+x2+7x3+5x4 14 2x2+x3+3x4 8 xi 0(i=1,4)4x1+6x2+x3+2x4-x5 =12 x1+x2+7x3+5x4 -x6 =14 2x2+x3+3x4 -x7=8 x1,x7 0 0 剩余变量返回第31页/共130页令令Z=-Z2.目标函数目标函数xoZ-Z第32页/共130页minZ=2X1+5X2+6X3+8X4maxZ=-2X1-5X2-6X3-8X4返回第33页/共130页3.3.变量3 x1-3 x1 +2x2 8 x1-x1 4x2 14x1,x1,x2 0 0a、x 0的情况，3x1+2x2 8 x1 4x2 14 x2 0 0令x1=x1-x1 b、x取值无约束的情况。令x -x。令x=x-x第34页/共130页x1+x2 11x1 16x1,x2 0 0 c、x两边有约束的情况。x1+x2 5-6 x1 10 x2 0 0-6+6 x1+6 10+6 令x1=x1+6 0 x1 16x1+x2+x3 =11x1 +x4=16x1,x2,x3 ,x4,0 0第35页/共130页将 min Z=-x1+2x2 3x3x1+x2+x3 7x1-x2+x3 2 2x1，x2 0 0，x3无限制化为标准型例：第36页/共130页解：令x3=x4-x5 加松弛变量x6加剩余变量x7 令Z=-ZmaxZ=x1 2x2+3x4 3x5 x1+x2+x4-x5+x6 =7x1-x2+x4-x5 -x7=2x1,x2,x4,x7 0 0min Z=-x1+2x2 3x3x1+x2+x3 7x1-x2+x3 2 2x1，x2 0 0，x3无限制返回第37页/共130页X1+X2+X3 -9-X1-X2-X3 94.4.右端项系数返回第38页/共130页例：例：将将 min Z=-X1+2X2-3X3X1+X2+X3 7X1-X2+X3 2 2X1，X2 0 0，X3无限制无限制化为标准型化为标准型第39页/共130页解：解：令令X3=X4-X5 加松弛变量加松弛变量X6 加剩余变量加剩余变量X7 令令Z=-ZmaxZ=X1-2X2+3X4-3X5 X1+X2+X4-X5+X6 =7X1-X2+X4-X5-X7=2X1,X2,X4,X7 0 0返回第40页/共130页练 习第41页/共130页第42页/共130页线性规划的图解法maxZ=CX (3)AX=b (1)X 0 (2)定义1 1：满足约束(1)(1)、(2)(2)的X=(x1 xn)T称为LP问题的可行解，全部可行解的集合称为可行域。定义2 2：满足(3)(3)的可行解称为LP问题的最优解.第43页/共130页1、判别线性规划问题的求解结局；2、是在存在最优解的条件下，找出问题的最优解。1、在平面上建立直角坐标系2、图示约束条件，找出可行域3、图示目标函数和寻找最优解图解法求解的目的：图解法的步骤：第44页/共130页例1、maxZ=40 x1+50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1,x2 0 0第45页/共130页(1)、建立坐标系 x1+2x2 30 x1+2x2=30 (0,15)(30,0)DABC3x1+2x2=60(0,30)(20,0)2x2=24203010X1 X1+2X2 303X1+2X2 60 2X2 24 X1,X2 0X20102030 x1 0 x1=0(纵纵)x2 0 x2=0(横横)(2)、确定可行域 解：x1+2x2 303x1+2x2 60 2x2 24 x1,x2 0 0maxZ=40 x1+50 x2第46页/共130页(3)、求最优解解：x1=15,x2=7.5Z=40 x1+50 x2x2=-4/5x1+Z/50 x20102030203010 x1DABCC点：x1+2x2=30 3x1+2x2=60maxZ=975 x1+2x2 303x1+2x2 60 2x2 24 x1,x2 0 0maxZ=40 x1+50 x2第47页/共130页Z=40 x1+80 x2=0 X1+2x2=30DABCx20 x1最优解：BC线段B点 C点x(1)=(6,12)x(2)=(15,7.5)x=x(1)+(1-)x(2)(0 1)求解例2、maxZ=40 x1+80 x2 x1+2x2 303x1+2x2 60 2x2 24 x1,x2 0 0第48页/共130页x1=6 +(1-)15x2=12 +(1-)7.5x1=15-9 x2=7.5+4.5 (0 1)maxZ=1200 X=+(1-)x1 6 15x2 12 7.5第49页/共130页无界解无有限最优解例3、maxZ=2x1+4x2 2x1+x2 8 8-2x1+x2 2x1,x2 0 0Z=02x1+x2=8-2x1+x2=28246x240 x1Z=0第50页/共130页例4、maxZ=3x1+2x2-x1-x2 1 1x1,x2 0 0无解无可行解-1x1-1x20第51页/共130页max z=x1+3x2 x1+x26s.t.-x1+2x28 x1 0,x20练 习第52页/共130页max z=x1+3x2s.t.x1+x26-x1+2x28x1 0,x20可行域目标函数等值线最优解64-860 x1x2练 习第53页/共130页由图解法得到的启示(1)、线性规划问题的解的情况有四种：唯一最优解；无穷多最优解；无界解；无可行解。(3)、若有最优解，定可在可行域的顶点得到。(2)、若线性规划可行域存在，则可行域是一个凸集。(4)、解题思路是找出凸集的各顶点的最大目标函数值。第54页/共130页线性规划解的情况唯一解无穷多解 无有限最优解 无可行解有解无解当目标函数的直线族与某约束条件直线平行，且该问题有解时。第55页/共130页线性规划解的情况唯一解无穷多解 无有限最优解 无可行解有解无解有解但可行域可伸展到无穷时第56页/共130页线性规划解的情况唯一解无穷多解 无有限最优解 无可行解有解无解约束条件直线无公共区域。第57页/共130页线性规划的单纯形法一、线性规划的基本概念二、单纯形法的迭代原理三、单纯形法的计算步骤四、单纯形法的进一步讨论五、单纯形法小结第58页/共130页线性规划的相关概念 矩阵的秩矩阵A中，不为零的子式的最高阶数，称为矩阵A的秩。逆矩阵设有n阶方阵A，如果存在n阶方阵B，满足AB=BA=E，则称A阵是可逆的，且称B是A的逆矩阵。第59页/共130页线性规划的相关概念矩阵的初等变换：矩阵的初等变换：（1 1）对调矩阵的两行或两列；）对调矩阵的两行或两列；（2 2）以非零数）以非零数k k乘矩阵的某一行（列）的所有元素；乘矩阵的某一行（列）的所有元素；（3 3）以数）以数k k乘矩阵的某行（列）的所有元素加到另乘矩阵的某行（列）的所有元素加到另一行（列）的对应元素上去。一行（列）的对应元素上去。对方程组的系数矩阵对方程组的系数矩阵A A作初等行变换，得到新作初等行变换，得到新的方程组与原方程组同解。的方程组与原方程组同解。第60页/共130页目标函数约束条件解：用变量x1和x2分别表示美佳公司制造家电I和II的数量。第61页/共130页 可行解可行解满足方程约束条件的解满足方程约束条件的解X（x1，x2，xn)T,称为线称为线性规划问题的可行解。全部可行解的集合称为可行域。性规划问题的可行解。全部可行解的集合称为可行域。最优解最优解使目标函数达到最大值的可行解称为最优解使目标函数达到最大值的可行解称为最优解线性规划的基本概念MaxZ=C1X1+C2X2+CnXna11X1+a12X2+a1nXn=b=b1 1a21X1+a22X2+a2nXn=b=b2 2 am1X1+am2X2+amnXn=b=bm mXj j 0(0(j=1,2,n)第62页/共130页基(基阵)设A为约束方程组约束方程组的mn阶系数矩阵系数矩阵,(n=m)，设其秩为m，B是矩阵A中的一个mm阶的满秩子矩阵，称B是线性规划问题的一个基。线性规划的基本概念如果矩阵如果矩阵A的满秩子矩阵不是唯一的，的满秩子矩阵不是唯一的，则基阵也是不唯一的则基阵也是不唯一的第63页/共130页B=(P1,P2,Pm)基向量基阵B中的每一个列向量Pj称为基向量，基变量与基向量对应的变量称为基变量，非基变量基变量外的其他变量称为非基变量。第64页/共130页线性规划的基本概念A=(P1 Pm Pm+1 Pn)=(B N)基向量 非基向量 基阵 非基矩阵X=(x1 xm xm+1 xn)T=(XB XN)T 基变量 非基变量 XB XN第65页/共130页Max Z=2x1+3x2+x3s.t.x1+3x2+x315 2x1+3x2-x3 18 x1-x2+x3 3 x1,x2,x30Max Z=2x1+3x2+x3s.t.x1+3x2+x3+x4 =15 2x1+3x2-x3 +x5 =18 x1-x2+x3 +x6 =3 x1,x2,x3,x4,x5,x6,0第66页/共130页Max Z=2x1+3x2+x3s.t.x1+3x2+x3+x4 =15 2x1+3x2-x3 +x5 =18 x1-x2+x3 +x6 =3 x1,x2,x3,x4,x5,x6,0第67页/共130页MaxZ=C1X1+C2X2+CnXna11X1+a12X2+a1nXn=b=b1 1a21X1+a22X2+a2nXn=b=b2 2 am1X1+am2X2+amnXn=b=bm mXj j 0(0(j=1,2,n)其中其中 bi 0(0(i=1,2,m)n=m线性规划的基本概念第68页/共130页找出该线性规划问题的全部基解，指出其中的基可行解，并确定最找出该线性规划问题的全部基解，指出其中的基可行解，并确定最优解优解线性规划的基本概念MaxZ=2x1+3x2+x3x1+x3=5=5x1+2x2 +x4=10=10 x2 +x5=4=4xj j 0(0(j=1,2,5)第69页/共130页序号x1x2x3x4x5z是否可是否可行解行解10051045是20452017是35005410是40550-120否5100-50415否652.5001.517.5 是7540-3022否82430019是MaxZ=2x1+3x2+x3x1+x3=5=5x1+2x2 +x4=10=10 x2 +x5=4=4xj j 0(0(j=1,2,5)为何不选x2、x4、x5作为基变量？第70页/共130页定理1 若线性规划问题存在可行解，则问题的可行域是凸集。定理2 线性规划问题的基可行解X对应线性规划问题可行域的顶点。定理3 若线性规划问题有最优解，一定存在一个基可行解是最优解线性规划的基本定理第71页/共130页AX=b的求解XB XN(B N)=bBXB+NXN=bBXB=b-NXNB-1 BXB=B-1（b-NXN）XB=B-1 b-B-1N XNA=(B N)X=(XB XN)T1.XN0，B-1 b 0则 XB=B-1 b，即X=为 AX=b的一个解。2.若同时B为单位矩阵，则 XB=b，即X=(b，0)为AX=b的一个解第72页/共130页线性规划的基本概念A=(P1 Pm Pm+1 Pn)=(B N)基向量 非基向量 基阵 非基矩阵X=(x1 xm xm+1 xn)T=(XB XN)T 基变量 非基变量 XB XN返回第73页/共130页序号x1x2x3x4x5z是否可是否可行解行解10051045是20452017是35005410是40550-120否5100-50415否652.5001.517.5 是7540-3022否82430019是MaxZ=2x1+3x2+x3x1+x3=5=5x1+2x2 +x4=10=10 x2 +x5=4=4xj j 0(0(j=1,2,5)验证第74页/共130页例：Max Z=2x1+3x2+x3s.t.x1+3x2+x315 2x1+3x2-x3 18 x1-x2+x3 3 x1,x2,x30Max Z=2x1+3x2+x3s.t.x1+3x2+x3+x4 =15 2x1+3x2-x3 +x5 =18 x1-x2+x3 +x6 =3 x1,x2,x3,x4,x5,x6,0第75页/共130页基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=20第76页/共130页基变量x1、x2、x4，非基变量x3、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=18第77页/共130页基变量x1、x2、x5，非基变量x3、x4、x6基础解为（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0）是基础解，但不是可行解，不是一个极点。第78页/共130页基变量x1、x2、x6，非基变量x3、x4、x5基础解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4）是基础可行解，表示可行域的一个极点。目标函数值为：z=18第79页/共130页基变量x2、x3、x4，非基变量x1、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0）是基础解，但不是可行解。第80页/共130页基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=15第81页/共130页基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10）是基础解但不是可行解。第82页/共130页 基本解中最多有m m个非零分量。基本解的数目不超过 Cnm=个。n!m!(n-m)!第83页/共130页例1、x1+2x2+x3 =30 3x1+2x2 +x4 =60 2x2 +x5=24 X1 X5 0 01 2 1 0 03 2 0 1 00 2 0 0 1P1 P2 P3 P4 P5A=基阵B非基阵N求出一个基本解，并判断是不是可行解？第84页/共130页令X1=X2=0,则 X3=30,X4=60,X5=24X=XN 0 XB B-1 b00306024第85页/共130页例：给定约束条件 -x3+x4=0=0 x2+x3+x4=3 -x1+x2+x3+x4=2 xj 0 0(j=1,2,3,4)求出基变量是x1,x3,x4的基解，是不是可行解？第86页/共130页 0 -1 1解：B=(P1 P3 P4)=0 1 1 -1 1 1 0 1 -1 0B-1=-1/2 1/2 0 3 1/2 1/2 0 2b=第87页/共130页 x1 x3 =B-1 b x4 XB=X=(1,0,3/2,3/2)T 是 基本可行解 0 1 -1 0 1 =-1/2 1/2 0 3 =3/2 1/2 1/2 0 2 3/2第88页/共130页单纯形法的迭代原理找出一个基可行解判断是否最优转换到相邻的基可行解找到最优解否是第89页/共130页单纯形法计算步骤1.求初始基可行解，列出单纯形表第90页/共130页例题5：用单纯形法求解线性规划问题第91页/共130页解：1、先将上述问题化成标准形式有找到一个初始基可行解Max z=2x1+x2+0 x3+0 x4+0 x5 5x2+x3 =156x1+2x2 +x4 =24 x1+x2 +x5=5X=(0,0,15,24,5)T15245P1P2P3P4P5第92页/共130页2、列初始单纯形表：CjCBXBb j=cj-zjMax z=2x1+x2+0 x3+0 x4+0 x5 5x2+x3 =156x1+2x2 +x4 =24 x1+x2 +x5=5第93页/共130页X1进基；Cj21000CBXBbx1x2x3x4x50 x315051000 x424620100 x5511001 j=cj-zjX4出基；-4521000Max z=2x1+x2+0 x3+0 x4+0 x5 5x2+x3 =156x1+2x2 +x4 =24 x1+x2 +x5=5第94页/共130页Cj21000CBXBbx1x2x3x4x50 x315051000 x424620100 x5511001 j=cj-zjx120 x315051002x124/612/601/600 x5511001 j=cj-zj第95页/共130页3、列新单纯形表：Cj21000CBXBbx1x2x3x4x50 x315051002x1412/601/600 x5104/60-1/61 j=cj-zj01/30-1/300 x315051002x1412/601/600 x5104/60-1/61 j=cj-zj3123/2X2进基；X5出基；第96页/共130页Cj21000CBXBbx1x2x3x4x50 x315051002x1412/601/600 x5104/60-1/61 j=cj-zj0 x315051002x1412/601/601x23/2010-1/43/2 j=cj-zjx21第97页/共130页Cj21000CBXBbx1x2x3x4x50 x315051002x1412/601/601x23/2010-1/43/2 j=cj-zj0 x315051002x17/21001/4-1/21x23/2010-1/43/2 j=cj-zj0 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2 j=cj-zj第98页/共130页4 4、列新单纯形表：解为：X=(7/2,3/2,15/2,0,0)。Cj21000CBXBbx1x2x3X4X50 x315/20015/4-15/22x17/21001/4-1/21x23/2000-1/43/2 j=cj-zj000-1/4-1/2目标函数值为:maxZ=2x1+x2+0 x3+0 x4+0 x5 =27/2+13/2+015/2+0+0=8.5第99页/共130页 解：练习题原问题化为标准型第100页/共130页列初始单纯形表Cj3501000CBXBbx1x2x3x4x5x6x70 x53511101000 x612510-10100 x7500-11001 j=cj-zj第101页/共130页列初始单纯形表35010003512Cj3501000CBXBbx1x2x3x4x5x6x70 x53511101000 x612510-10100 x7500-11001 j=cj-zjX2入基，X6出基第102页/共130页Cj3501000CBXBbx1x2x3x4x5x6x70 x53511101005x212510-10100 x7500-11001 j=cj-zj23-40111-10-220060-502350 x523-40111-105x212510-10101x4500-11001 j=cj-zjx518-40201-1-11751-10011-220600-5690 x318-40201-1-15x21751-100111x4500-11001 j=cj-zj14-20010.5-0.50.5-10000-3-2-39-20100.5-0.5-0.52631000.50.50.5第103页/共130页Cj3501000CBXBbx1x2x3x4x5x6x70 x39-20100.5-0.5-0.55x22631000.50.50.51x414-20010.5-0.50.5 j=cj-zj-10000-3-2-3作业：第104页/共130页人工变量法当化为标准形后的约束条件的系数矩阵中当化为标准形后的约束条件的系数矩阵中不存在单位矩阵时，可以人为地增加变量，不存在单位矩阵时，可以人为地增加变量，在最优解中人工变量取值必须为零。为此，在最优解中人工变量取值必须为零。为此，令目标函数中人工变量的系数为任意大的令目标函数中人工变量的系数为任意大的负值负值M M。这种人为增加变量的方法称为。这种人为增加变量的方法称为人工变量法，亦称大人工变量法，亦称大M M法。法。第105页/共130页例1 1：Max z=6x1+4x2 2x1+3x2 1004x1+2x2 120 x1 =14 x2 22x1,x2 0第106页/共130页maxZ=6x1+4x22x1+3x2+x3 =1004x1+2x2 +x4 =120 x1 =14 x2 -x5 =22x1 x5 0解：maxZ=6x1+4x2 2x1+3x2 1004x1+2x2 120 x1 =14 x2 22x1 x2 0化成标准型化成标准型第107页/共130页maxZ=6x1+4x22x1+3x2 +x3 =1004x1+2x2 +x4 =120 x1 =14 x2 -x5 =22x1 x7 0加人工变量加人工变量+x+x66+x+x77-Mx6-Mx7第108页/共130页Cj64000-M-MCBXBbx1x2x3x4x5x6x70 x310023100000 x41204201000-Mx6141000010-Mx7220100-101 j=cj-zj列初始单纯形表第109页/共130页 6 4 0 0 0 -6 4 0 0 0 -M -M CB xB b x1 x2 x3 x4 x5 x6 x70 0 x3 100 2 3 1 0 0 0 0 100 2 3 1 0 0 0 0 0 0 x4 120120 4 4 2 0 1 0 0 0 2 0 1 0 0 0-M x6 14 1 0 0 0 0 1 0 14 1 0 0 0 0 1 0 -M x7 22 0 1 0 0 -1 0 1 -36 36 M M+6 +6 M+4 0 0 -+4 0 0 -M 0 0 0 0Cj0 0 x3 72 0 3 1 0 0 -2 0 72 0 3 1 0 0 -2 0 0 0 x4 64 0 64 0 2 0 1 0 2 0 1 0 -4 0-4 0 6 x1 14 1 0 0 0 0 1 0 14 1 0 0 0 0 1 0 -M x7 22 0 1 0 0 -1 0 1 8484-22M 0 0 M+4 0 0 -0 0 -M 6-M 0第110页/共130页Cj0 0 x3 6 0 0 1 0 (3)-2 -3 6 0 0 1 0 (3)-2 -3 0 0 x4 2020 0 0 0 0 0 1 2 -4 -2 0 1 2 -4 -2 6 x1 14 1 0 0 0 0 1 0 14 1 0 0 0 0 1 0 4 x2 22 0 1 0 0 -1 0 1 172172 0 0 0 0 4 0 0 4 6-6-M 4-4-M0 0 x5 2 0 0 1/3 0 1 -2/3 -1 2 0 0 1/3 0 1 -2/3 -1 0 0 x4 1 16 0 6 0 0 -2/3 1 0 -8/3 0 0 -2/3 1 0 -8/3 0 6 x1 14 1 0 0 0 0 1 0 14 1 0 0 0 0 1 0 4 x2 24 0 1 1/3 0 0 -2/3 -2 180180 0 0 0 -4/3 0 -4/3 0 0 -M-10/3 -M 6 4 0 0 0 -6 4 0 0 0 -M -M CB xB b x1 x2 x3 x4 x5 x6 x7解为：X=(14,24,0,16,2)。目标函数值为:maxZ=6x1+4x2=614+424=180第111页/共130页练 习用大M法求解下列问题：第112页/共130页两阶段法对添加人工变量后的线性规划问题分两个阶段来计算，称为两阶段法。第113页/共130页两阶段法 第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中其它变量的系数取零，人工变量的系数取某个正的常数(一般取1)1)，在保持原问题约束条件不变的情况下求这个目标函数极小化时的解。第114页/共130页作辅助问题原问题第115页/共130页两阶段法在第一阶段中，当人工变量取值为0 0时，目标函数值也为0 0。这时候的最优解就是原线性规划问题的一个基可行解。如果第一阶段求解结果最优解的目标函数值不为0 0，也即最优解的基变量中含有非零的人工变量，表明原线性规划问题无可行解。第116页/共130页解题过程：第1阶段：解辅助问题当进行到最优表时，若W=0,则得到原问题的一个 基本可行解，转入第2阶段。若W0,则判定原问题无可行解。第2 2阶段：去除人工变量，求解原问题。第一阶段的最优解为原问题的初始基可行解。第117页/共130页maxZ=-x1+2x2 x1+x2 2-x1+x2 1 x2 3 3x1 x2 0例：x1+x2-x3 =2-x1+x2 -x4 =1 x2 +x5 =3x1 x5 01.化标准型：maxZ=-x1+2x2+x6+x72.增加人工变量，构造单位矩阵：,x6,x7 0第118页/共130页3.3.建立只包含人工变量的辅助问题。minW=x6+x7 x1+x2-x3 +x6 =2-x1+x2 -x4 +x7=1 x2 +x5 =3x1 x7 0Cj0000011CBxBbx1x2x3x4x5x6x71x6211-100101x71-110-10010 x530100100 j=cj-zj0-2110002133第119页/共130页 0 0 0 0 0 1 1 CB xB b x1 x2 x3 x4 x5 x6 x71 x6 2 1 1 -1 0 0 1 0 1 x7 1 -1 (1)0 -1 0 0 1 0 x5 3 0 1 0 0 1 0 0 3 0 -2 1 1 0 0 00 x1 1/2 1 0 -1/2 1/2 0 1/2 -1/2 0 x2 3/2 0 1 -1/2 -1/2 0 1/2 1/20 x5 3/2 0 0 -1/2 1/2 1 -1/2 -1/2 0 0 0 0 0 0 1 11 x6 1 2 0 -1 1 0 1 -1 0 x2 1 -1 1 0 -1 0 0 1 0 x5 2 1 0 0 1 1 0 -1 1 -2 0 1 -1 0 0 2解为：X=(1/2,3/2,0,0,3/2,0,0)。目标函数值为:minW=x6+x7=0可转入第二阶段。去除人工变量，以第一阶段最优解为基可行解。第120页/共130页 -1 2 0 0 0 CB xB b x1 x2 x3 x4 x5-1 x1 1/2 1 0 -1/2 1/2 0 2 x2 3/2 0 1 -1/2 -1/2 0 0 x5 3/2 0 0 /2 1/2 1 3/2 0 0 1/2 3/2 0解为：X=(0,3,1,2,0)。目标函数值为:maxZ=-x1+2x2=64.去除人工变量，以第一阶段的最优解为基可行解,求解原问题。0 x4 1 2 0 -1 1 02 x2 2 1 1 -1 0 00 x5 1 -1 0 1 0 1 4 -3 0 2 0 00 x4 2 1 0 0 1 12 x2 3 0 1 0 0 10 x3 1 -1 0 1 0 1 6 -1 0 0 0 -2第121页/共130页计算中的几个问题计算中的几个问题目标函数极大化时解的最优性判别 以i i 0 0作为判别表中解是否最优的标志目标函数极小化时解的最优性判别 以i i 0 0作为判别表中解是否最优的标志1 1、目标函数情况第122页/共130页2、退化解 （5，6，7）（1，6，7）（1，2，7）（3，2，7）（3，4，7）（5，4，7）（5，6，7）第123页/共130页在下一次迭代中有一个或几个基变量为0，从而出现退化解。可能会导致循环，永远达不到最优解。退化解第124页/共130页退化问题解决办法Bland 原则 （1976 年 第9届国际数学规划大会）第125页/共130页3 3、无可行解的判别 当线性规划问题中添加人工变量后，无论用人工变量法或两阶段法，初始单纯形表中的解因含非零人工变量，故实质上是非可行解。当求解结果出现所有i 0 0时，如基变量中仍含有非零的人工变量(两阶段法求解时第一阶段目标函数值不等于零)，表明问题无可行解。第126页/共130页单纯形法小结第127页/共130页找出初始基可行解列出初始单纯形表计算检验数i所有i 0基变量中含人工变量有非基变量检验数为零唯一最优解对某一i0有Pi 0无界解无可行解无穷多最优解xk进基迭代运算1.用xk替换xl2.列出新的单纯形表1）对主元素行（第l行）blbl/alk,alj/alk2)其他行（il）bibiaikbl/alk，aij=aij-aikalj/alk是是是是否否否否单纯形法计算步骤框图第128页/共130页作 业P43P431.1(2)(3)1.1(2)(3)1.2(2)1.2(2)1.81.81.131.131.16 1.16 第129页/共130页感谢您的观看！第130页/共130页