运筹学第一章线性规划及单纯形法ppt课件

1、第一章第一章 线性规划及单纯形法线性规划及单纯形法目目 录录线性规划介绍线性规划介绍线性规划数学模型线性规划数学模型线性规划的图解法线性规划的图解法 线性规划的单纯形法线性规划的单纯形法问题的提出v在现有各项资源条件的限制下，如何确定方在现有各项资源条件的限制下，如何确定方案，使预期目标达到最优；或为了达到取其案，使预期目标达到最优；或为了达到取其目标，确定使资源消耗最少的方案。目标，确定使资源消耗最少的方案。问题的提出v例例1 美佳公司计划制造美佳公司计划制造I，II两种家电产品。两种家电产品。已知各制造一件时分别占用的设备已知各制造一件时分别占用的设备A、B的台的台时、调试时间及时、调试时

2、间及A、B设备和调试工序每天可设备和调试工序每天可用于这两种家电的能力、各售出一件时的获用于这两种家电的能力、各售出一件时的获利情况如表利情况如表1-1所示。问该公司应制造所示。问该公司应制造A、B两种家电各多少件，使获取的利润为最大。两种家电各多少件，使获取的利润为最大。例例2、生产计划问题、生产计划问题 A B 备用资源备用资源 煤煤 1 2 30 劳动日劳动日 3 2 60 仓库仓库 0 2 24 利润利润 40 50 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0max Z= 40 x1 +50 x2解解:设产品设产品A, B产量分别为变量产量分别为变量

3、x1 ， x2问题的提出例例3：捷运公司拟在下一年度的：捷运公司拟在下一年度的1-4月的月的4个月内需租个月内需租用仓库堆放物资，已知各月所需仓库面积如表用仓库堆放物资，已知各月所需仓库面积如表1-2。仓库租借费用随合同期限而定，合同期越长，折扣仓库租借费用随合同期限而定，合同期越长，折扣越大，具体见表越大，具体见表1-3。租借仓库的合同每月初都可。租借仓库的合同每月初都可办理，每份合同具体规定租用面积数和期限。该厂办理，每份合同具体规定租用面积数和期限。该厂可在任何一月办理租借合同，每次办理一份或若干可在任何一月办理租借合同，每次办理一份或若干份均可。为使租借费用最小，公司应如何选择签订份均

4、可。为使租借费用最小，公司应如何选择签订合同的最优决策？合同的最优决策？月份1234所需仓库面积15102012合同租借期限1个月2个月3个月4个月合同期内的租费2800450060007300例例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 素最低含量素最低含量解：设每单位添加剂中原料解：设每单位添加剂中原料i的用量为的用量为xi(i =1,2,3,4)minZ= 2x1 + 5x2 +6x3+8x4 4x1

5、 + 6x2 + x3+2x4 12 x1 + x2 +7x3+5x4 14 2x2 + x3+3x4 8 xi 0 (i =1,4)补充作业、运输问题补充作业、运输问题 从仓库到工厂运送单位原材料的成本，工厂对原从仓库到工厂运送单位原材料的成本，工厂对原材料的需求量，仓库目前库存分别如表所示，求成本材料的需求量，仓库目前库存分别如表所示，求成本最低的运输方案。最低的运输方案。 工厂工厂 仓库仓库 1 2 3 库存库存 1 2 1 3 50 2 2 2 4 30 3 3 4 2 10 需求需求 40 15 35设设xij为为i 仓库运到仓库运到 j工厂的原棉数量工厂的原棉数量(i 1，2，3，

6、 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一、线性规划模型特点一、线性规划模型特点决策变量：向量决策变量：向量(x1 xn)T 决策人要考决策人要考虑和控制的因素非负虑和控制的因素非负约束条件：线性等式或不等式约束条件：线性等式或不等式目标函数：目标函数：Z=(x1 xn) 线性式，求线性式，求Z极极大

7、或极小大或极小线性规划介绍二、线性规划解决的管理问题：二、线性规划解决的管理问题： 合理利用线材问题；合理利用线材问题；配料问题；配料问题；投资问题；投资问题；产品生产计划；产品生产计划；劳动力安排；劳动力安排；运输问题。运输问题。线性规划介绍要求达到某些数量上的最大化或最小化；要求达到某些数量上的最大化或最小化；在一定的约束条件下追求其目标。在一定的约束条件下追求其目标。三、线性规划问题的共同点：三、线性规划问题的共同点： 线性规划介绍线性规划的数学模型一、线性规划数学模型的一般形式一、线性规划数学模型的一般形式二、线性规划数学模型的标准形式二、线性规划数学模型的标准形式用数学语言描述用数学

8、语言描述目标函数目标函数约束条件约束条件解：用变量解：用变量x1和和x2分别表示美佳公司制造家电分别表示美佳公司制造家电I和和II的数量。的数量。线性规划的一般式max(min)Z=C1x1+ C2x2+Cnxna11x1+ a12x2+ a1nxn (=, )b1a21x1+ a22x2+ a2nxn (=, )b2 am1x1+ am2x2+ amnxn (=, )bmxj 0(j=1,n)简写为：简写为：njjjXCZ1max(min), 2 , 1(0), 2 , 1(1njxmibxajinjjij用矩阵和向量形式表示：用矩阵和向量形式表示：线性规划标准形式), 2 , 1(0),

9、2 , 1(. .1njxmibxatsjinjjij线性规划的标准形式线性规划的标准形式目标函数：目标函数：max约束条件约束条件：=变量符号变量符号：0njjjXCZ1max（一一般式（一一般式（二矩阵式（二矩阵式（三向量式（三向量式前前往往线性规划标准型的几种表示法线性规划标准型的几种表示法(一一) 一般型一般型MaxZ=C1X1+ C2X2+CnXna11X1+ a12X2+ a1nXn =b1a21X1+ a22X2+ a2nXn =b2 am1X1+ am2X2+ amnXn =bmXj 0(j=1,2,n)其中其中 bi 0 (i=1,2,m)前前往往(二二) 矩阵型矩阵型max

10、Z=CXAX=bX 0 P1 P2 P1 P2 PnPn a11 a11 a12 a1na12 a1n其中其中 A= a21 a22 A= a21 a22 a2n a2n am1 am1 am2 amnam2 amn X1 X= X2 XnC=(C1 C2 Cn ) b1 b= b2 bm前前往往(三三) 向量型向量型CXZmax01Xbxpnjjj X1AX=(P1 P2 Pn ) X2 = b Xn P1 X1+ P2 X2 + +Pn Xn=b前前往往(四四) 化标准型化标准型 1. 约束条件约束条件 3. 变量变量 2. 目标函数目标函数前前往往 4. 右端项系数右端项系数1. 约束条

11、件约束条件x3为松弛变量为松弛变量x4为剩余变量为剩余变量 松弛变量或剩余变量在实际问题中分别表示松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数为价值和利润，所以引进模型后它们在目标函数中的系数均为零。中的系数均为零。当约束条件为当约束条件为“”时，时，242621 xx如2426321xxx可化为当约束条件为当约束条件为“”时，时，18121021xx如181210321xxx可化为例例1 1maxZ=2X1+ X2+0X3 +0X4+0X5 5x2 15 6x1 + 2x2

12、 24 x1 + x2 5 xi 0+X3 =15 +X4 =24 +X5 = 5 松弛变量松弛变量例例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 x1 +2x2 +x3 =30 3x1 +2x2 +x4 =60 2x2 +x5 =24 x1 , , x5 0 转化为：转化为：maxZ=40 x1+ 50 x2+0 x3 +0 x4+0 x5 x1

13、 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0 例：例：max Z= 40 x1 +50 x2松弛变量松弛变量例例: 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 剩余变量剩余变量前前往往njjjXCZ1minnjjjXCZ1max令令Z = -Z2. 目标函数目标函数xoZ-ZminZ=2X1+ 5X2+6X3

14、+8X4maxZ= -2X1 - 5X2 -6X3 -8X4前前往往3.3.变量变量3 x1 -3 x1 +2x2 8 x1 - x1 4x2 14x1 , x1 ,x2 0a、x 0的情况，的情况，3x1+2x2 8 x1 4x2 14 x20令令x1= x1- x1= x1- x1 x1 b、x取值无约束的情况。取值无约束的情况。令令x -x。令令x= x-xx= x-xx1 +x2 11x1 16x1 , x2 0 c、x两边有约束的情况。两边有约束的情况。x1+x2 5-6 x1 10 x20-6+6 x1+6 10+6 令令x1 = x1 +6 0 x1 16x1 +x2+ x3 =

15、 11x1 +x4 = 16x1 , x2 , x3 , x4 ,0将将 min Z = -x1+2x2 3x3x1+x2 +x3 7x1 -x2 +x3 2x1，x20，x3无限制无限制化为标准型化为标准型例：例：解：解： 令令x3 =x4 - x5 加松弛变量加松弛变量x6x6加剩余变量加剩余变量x7 x7 令令Z= -ZZ= -ZmaxZ= x1 2x2 +3x4 3x5 x1 +x2 +x4 -x5 +x6 =7x1 -x2 +x4 -x5 -x7 =2x1 , x2 , x4 , , x7 0min Z = -x1+2x2 3x3x1+x2 +x3 7x1 -x2 +x3 2x1，x

16、20，x3无限制无限制前前往往X1+X2 +X3 -9-X1-X2 -X3 94.4.右端项系数右端项系数前前往往例：将例：将 min Z = -X1+2X2 -3X3X1+X2 +X3 7X1 -X2 +X3 2X1，X20，X3无限制无限制化为标准型化为标准型解：解： 令令X3 =X4 - X5 加松弛变量加松弛变量X6X6 加剩余变量加剩余变量X7 X7 令令Z= -ZZ= -ZmaxZ= X1 -2X2 +3X4 -3X5 X1 +X2 +X4 -X5 +X6 =7X1 -X2 +X4 -X5 - X7 =2X1 , X2 , X4 , , X7 0前前往往练练 习习线性规划的图解法线

17、性规划的图解法maxZ=CX (3)AX=b (1)X 0 (2)定义定义1 1：满足约束：满足约束(1)(1)、(2)(2)的的X=(x1 xn)TX=(x1 xn)T称为称为LPLP问题的可行解，全部可行解的集合称为可行域。问题的可行解，全部可行解的集合称为可行域。定义定义2 2：满足：满足(3)(3)的可行解称为的可行解称为LPLP问题的最优解问题的最优解. .1、判别线性规划问题的求解结局；、判别线性规划问题的求解结局；2、是在存在最优解的条件下，找出问题的最优解。、是在存在最优解的条件下，找出问题的最优解。 1、在平面上建立直角坐标系、在平面上建立直角坐标系2、图示约束条件，找出可行

18、域、图示约束条件，找出可行域3、图示目标函数和寻找最优解、图示目标函数和寻找最优解图解法求解的目的：图解法求解的目的：图解法的步骤：图解法的步骤：例例1、maxZ=40 x1+ 50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0(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 (横

19、横)(2)、确定可行域、确定可行域 解：解： x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0maxZ=40 x1+ 50 x2(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 0maxZ=40 x1+ 50 x2Z= 40 x1 + 80 x2 =0 X1 + 2x2 =30DABCx20 x1最优解：最优

20、解：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 x1 =6 + (1- )15x2=12 + (1- )7.5x1 =15-9x2 =7.5+4.5 (0 1)maxZ=1200 X= = +(1- )x1 6 15x2 12 7.5无界解无界解无有限最优解无有限最优解例例3、 maxZ=2x1+ 4x2 2x1+x2 8-2x1+x2 2x1 , x2 0Z=02x1+ x2=8-2x1+

21、 x2=28246x240 x1Z=0例例4、 maxZ=3x1+2x2 -x1 -x2 1x1 , x2 0无解无解无可行解无可行解-1x1-1x20max z=x1+3x2 x1+ x26s.t. -x1+2x28 x1 0, x20练练 习习max z=x1+3x2s.t. x1+ x26-x1+2x28x1 0, x20可行域可行域目标函数等值线目标函数等值线最优解最优解64-860 x1x2练练 习习由图解法得到的启示由图解法得到的启示(1)、线性规划问题的解的情况有四种：唯一最优解；、线性规划问题的解的情况有四种：唯一最优解；无穷多最优解；无界解；无可行解。无穷多最优解；无界解；无

22、可行解。(3)、若有最优解，定可在可行域的顶点得到。、若有最优解，定可在可行域的顶点得到。(2)、若线性规划可行域存在，则可行域是一个凸集。、若线性规划可行域存在，则可行域是一个凸集。(4)、解题思路是找出凸集的各顶点的最大目标函数、解题思路是找出凸集的各顶点的最大目标函数值。值。线性规划解的情况线性规划解的情况唯一解唯一解无穷多解无穷多解 无有限最优解无有限最优解 无可行解无可行解有解有解无解无解当目标函数当目标函数的直线族与的直线族与某约束条件某约束条件直线平行，直线平行，且该问题有且该问题有解时。解时。线性规划解的情况线性规划解的情况唯一解唯一解无穷多解无穷多解 无有限最优解无有限最优解

23、 无可行解无可行解有解有解无解无解有解但可有解但可行域可伸行域可伸展到无穷展到无穷时时线性规划解的情况线性规划解的情况唯一解唯一解无穷多解无穷多解 无有限最优解无有限最优解 无可行解无可行解有解有解无解无解约束条件约束条件直线无公直线无公共区域。共区域。线性规划的单纯形法一、线性规划的基本概念一、线性规划的基本概念二、单纯形法的迭代原理二、单纯形法的迭代原理三、单纯形法的计算步骤三、单纯形法的计算步骤四、单纯形法的进一步讨论四、单纯形法的进一步讨论五、单纯形法小结五、单纯形法小结线性规划的相关概念线性规划的相关概念 矩阵的秩矩阵A中，不为零的子式的最高阶数，称为矩阵A的秩。逆矩阵设有n阶方阵A

24、，如果存在n阶方阵B，满足AB=BA=E，则称A阵是可逆的，且称B是A的逆矩阵。线性规划的相关概念线性规划的相关概念矩阵的初等变换：矩阵的初等变换：（1 1对调矩阵的两行或两列；对调矩阵的两行或两列；（2 2以非零数以非零数k k乘矩阵的某一行列的所有元素；乘矩阵的某一行列的所有元素；（3 3以数以数k k乘矩阵的某行列的所有元素加到另乘矩阵的某行列的所有元素加到另一行列的对应元素上去。一行列的对应元素上去。对方程组的系数矩阵对方程组的系数矩阵A A作初等行变换，得到新作初等行变换，得到新的方程组与原方程组同解。的方程组与原方程组同解。目标函数目标函数约束条件约束条件解：用变量解：用变量x1和

25、和x2分别表示美佳公司制造家电分别表示美佳公司制造家电I和和II的数量。的数量。 可行解满足方程约束条件的解X（x1，x2，xn)T, 称为线性规划问题的可行解。全部可行解的集合称为可行域。最优解使目标函数达到最大值的可行解称为最优解线性规划的基本概念线性规划的基本概念MaxZ=C1X1+ C2X2+CnXna11X1+ a12X2+ a1nXn =b1a21X1+ a22X2+ a2nXn =b2 am1X1+ am2X2+ amnXn =bmXj 0(j=1,2,n)基(基阵) 设A为约束方程组的mn阶系数矩阵, (n=m)，设其秩为m，B是矩阵A中的一个mm阶的满秩子矩阵，称B是线性规划

26、问题的一个基。线性规划的基本概念线性规划的基本概念如果矩阵如果矩阵A的满秩子矩阵不是唯一的，的满秩子矩阵不是唯一的，则基阵也是不唯一的则基阵也是不唯一的B=(P1,P2,Pm)基向量基阵B中的每一个列向量Pj称为基向量，基变量与基向量对应的变量称为基变量，非基变量基变量外的其他变量称为非基变量。线性规划的基本概念线性规划的基本概念A= (P1 Pm Pm+1 Pn )= (B N) 基向量基向量 非基向量非基向量 基阵基阵 非基矩阵非基矩阵X= (x1 xm xm+1 xn )T=(XB XN)T 基变量基变量 非基变量非基变量 XB XNMax Z=2x1+3x2+x3s.t. x1+3x2

27、+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,0100111010132001131Max 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,0100111010132001131MaxZ=C1X1+ C2X2+CnXna11X1+ a12X2+ a

28、1nXn =b1a21X1+ a22X2+ a2nXn =b2 am1X1+ am2X2+ amnXn =bmXj 0(j=1,2,n)其中其中 bi 0 (i=1,2,m)n=m线性规划的基本概念线性规划的基本概念找出该线性规划问题的全部基解，指出其中的基可行解，并确定最找出该线性规划问题的全部基解，指出其中的基可行解，并确定最优解优解线性规划的基本概念线性规划的基本概念MaxZ=2x1+ 3x2+x3x1+ + x3 =5x1 + 2x2 + x4 =10 x2 +x5 =4xj 0(j=1,2,5)序号x1x2x3x4x5z是否可是否可行解行解10051045是20452017是3500

29、5410是40550-120否5100-50415否652.5001.517.5 是7540-3022否82430019是MaxZ=2x1+ 3x2+x3x1+ + x3 =5x1 + 2x2 + x4 =10 x2 +x5 =4xj 0(j=1,2,5)为何不选为何不选x2、x4 、 x5作为基变量？作为基变量？v定理定理1 若线性规划问题存在可行解，则问题的可行若线性规划问题存在可行解，则问题的可行域是凸集。域是凸集。v定理定理2 线性规划问题的基可行解线性规划问题的基可行解X对应线性规划问对应线性规划问题可行域的顶点。题可行域的顶点。v定理定理3 若线性规划问题有最优解，一定存在一个基若

30、线性规划问题有最优解，一定存在一个基可行解是最优解可行解是最优解线性规划的基本定理线性规划的基本定理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的一个解的一个解线性规划的基本概念线性规划的基本概念A= (P1 Pm Pm+1 Pn )

31、= (B N) 基向量基向量 非基向量非基向量 基阵基阵 非基矩阵非基矩阵X= (x1 xm xm+1 xn )T=(XB XN)T 基变量基变量 非基变量非基变量 XB XN前前往往序号x1x2x3x4x5z是否可是否可行解行解10051045是20452017是35005410是40550-120否5100-50415否652.5001.517.5 是7540-3022否82430019是MaxZ=2x1+ 3x2+x3x1+ + x3 =5x1 + 2x2 + x4 =10 x2 +x5 =4xj 0(j=1,2,5)验证验证例：例：Max Z=2x1+3x2+x3s.t. x1+3x2

32、+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 x1+3x2+x3=152x1+3x2-x3=18x1-x2+x3=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量基变量x1、x2、x3，非基变量，非基变量x4、x5、x6基础解为基础解为x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基础可行解，表示可行域的

33、一个极点。是基础可行解，表示可行域的一个极点。目标函数值为：目标函数值为：z=20 x1+3x2+x4=152x1+3x2=18x1-x2=3基变量基变量x1、x2、x4，非基变量，非基变量x3、x5、x6基础解为基础解为（x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0）是基础可行解，表示可行域的一个极点。是基础可行解，表示可行域的一个极点。目标函数值为：目标函数值为：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1+3x2=152x1+3x2+x5=18x1-x2=3x1+3x2+x3+x4=152x1+3x

34、2-x3+x5=18x1-x2+x3+x6=3基变量基变量x1、x2、x5，非基变量，非基变量x3、x4、x6基础解为基础解为x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0）是基础解，但不是可行解，不是一个极点。是基础解，但不是可行解，不是一个极点。x1+3x2=152x1+3x2=18x1-x2+x6=3基变量基变量x1、x2、x6，非基变量，非基变量x3、x4、x5基础解为基础解为x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4）是基础可行解，表示可行域的一个极点。是基础可行解，表示可行域的一个极点。目标函数值为：目标函数值为：z=18x1+3x2+x3+x

35、4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3+x4=153x2-x3=18-x2+x3=3基变量基变量x2、x3、x4，非基变量，非基变量x1、x5、x6基础解为基础解为（x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0）是基础解，但不是可行解。是基础解，但不是可行解。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3=153x2-x3+x5=18-x2+x3=3基变量基变量x1、x2、x3，非基变量，非基变量x4、x5、x6基础解为基础解为x1，x2，x3，x4，x5，x6）=（

36、0，3，6，0，15，0）是基础可行解，表示可行域的一个极点。是基础可行解，表示可行域的一个极点。目标函数值为：目标函数值为：z=15x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3=153x2-x3=18-x2+x3+x6=3基变量基变量x1、x2、x3，非基变量，非基变量x4、x5、x6基础解为基础解为（x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10）是基础解但不是可行解。是基础解但不是可行解。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3 基本解中最多有基本解中最多

37、有m m个非零分量。个非零分量。 基本解的数目不超过基本解的数目不超过 Cnm = Cnm = 个。个。n!m!(n-m)!例例1、 x1+2x2 +x3 =30 3x1+2x2 +x4 =60 2x2 +x5=24 X1 X5 01 2 1 0 03 2 0 1 00 2 0 0 1P1 P2 P3 P4 P5A=基阵基阵B非基阵非基阵N求出一个基本解，并判断是不是可行解？求出一个基本解，并判断是不是可行解？令令X1 = X2 =0, 那么那么 X3=30, X4=60, X5=24X= = = XN 0 XB B-1 b00306024例：给定约束条件例：给定约束条件 -x3+x4 =0

38、x2 +x3 +x4 =3 -x1 +x2 +x3+x4 =2 xj 0 ( j=1,2,3,4 )求出基变量是求出基变量是x1 , x3 , x4的基解，是不是可行解？的基解，是不是可行解？ 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= x1 x3 = B-1 b x4 XB = X=(1, 0, 3/2, 3/2)T 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单纯形

39、法的迭代原理找出一个基找出一个基可行解可行解判判断断是是否否最最优优转换到相邻的转换到相邻的基可行解基可行解找到最优解找到最优解否否是是单纯形法计算步骤v1.求初始基可行解，列出单纯形表求初始基可行解，列出单纯形表CXZ max01Xbxpnjjj例题例题5：用单纯形法求解线性规划问题：用单纯形法求解线性规划问题0,524261552max212121221xxxxxxxxxz解：解： 1、先将上述问题化成标准形式有、先将上述问题化成标准形式有找到一个初始基可行解找到一个初始基可行解Max z=2x1+x2+0 x3+0 x4+0 x5 5x2+x3 =156x1+2x2 +x4 =24 x1

40、+ x2 +x5=5X=(0,0,15,24,5)T15245P1 P2 P3P4 P52、列初始单纯形表：、列初始单纯形表：CjCBXBb j=cj-zjMax z=2x1+x2+0 x3+0 x4+0 x5 5x2+x3 =156x1+2x2 +x4 =24 x1+ x2 +x5=5X1进基；进基；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=5Cj21

41、000CBXBbx1x2x3x4x50 x315051000 x424620100 x5511001 j=cj-zjx120 x315051002x124/612/601/600 x5511001 j=cj-zj3、列新单纯形表：、列新单纯形表：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出基；出基；Cj21000CBXBbx1x2x3x4x50 x3150

42、51002x1412/601/600 x5104/60-1/61 j=cj-zj0 x315051002x1412/601/601x23/2010-1/43/2 j=cj-zjx21Cj21000CBXBbx1x2x3x4x50 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-zj4 4、列新单纯形表：、列新单纯形表：解为：解为：X=(7

43、/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.50,51253553max432143421321421xxxxxxxxxxxxxxxz 解：解：练习题练习题原问题化为标准型原问题化为标准型0,51253553max72174364215321421xxxxxxxxxxxxxxxxxz列初始单纯形表列

44、初始单纯形表Cj3501000CBXBbx1x2x3x4x5x6x70 x53511101000 x612510-10100 x7500-11001 j=cj-zj0,51253553max72174364215321421xxxxxxxxxxxxxxxxxz列初始单纯形表列初始单纯形表35010003512Cj3501000CBXBbx1x2x3x4x5x6x70 x53511101000 x612510-10100 x7500-11001 j=cj-zjX2入基，入基，X6出基出基Cj3501000CBXBbx1x2x3x4x5x6x70 x53511101005x212510-10100

45、 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.5144)0 , 0 , 0 ,14, 9 ,26, 0(*zx最优值最优解Cj3501000CBXBbx1x2x3x4x5x6

46、x70 x39-20100.5-0.5-0.55x22631000.50.50.51x414-20010.5-0.50.5 j=cj-zj-10000-3-2-3作业：作业：人工变量法人工变量法v当化为标准形后的约束条件的系数矩阵中当化为标准形后的约束条件的系数矩阵中不存在单位矩阵时，可以人为地增加变量，不存在单位矩阵时，可以人为地增加变量，在最优解中人工变量取值必须为零。为此，在最优解中人工变量取值必须为零。为此，令目标函数中人工变量的系数为任意大的令目标函数中人工变量的系数为任意大的负值负值M M。这种人为增加变量的方法称为人。这种人为增加变量的方法称为人工变量法，亦称大工变量法，亦称大M

47、 M法。法。例例1 1：Max z= 6x1 +4x2 2x1 +3x2 1004x1 +2x2 120 x1 =14 x2 22x1 ,x2 0maxZ=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化成标准型化成标准型maxZ=6x1+4x22x1 +3x2 +x3 =1004x1 +2x2 +x4 =120 x1 =14 x2 - x5 = 22x1 x7 0加人工变量加人工

48、变量+x6+x7-Mx6 -Mx7Cj64000-M-MCBXBbx1x2x3x4x5x6x70 x310023100000 x41204201000-Mx6141000010-Mx7220100-101 j=cj-zj列初始单纯形表列初始单纯形表 6 4 0 0 0 - M - M 6 4 0 0 0 - M - M CB xB b x1 x2 x3 CB xB b x1 x2 x3 x4 x5 x6 x7x4 x5 x6 x70 x3 100 2 3 1 0 0 0 0 0 x3 100 2 3 1 0 0 0 0 0 x4 120 4 2 0 1 0 0 x4 120 4 2 0 1 0

49、 0 0 0 0 -M x6 14 1 0 0 0 0 1 0 -M x6 14 1 0 0 0 0 1 0 -M x7 22 0 1 0 -M x7 22 0 1 0 0 -1 0 10 -1 0 1 -36 M M +6 M +4 0 0 - M 0 0 -36 M M +6 M +4 0 0 - M 0 0Cj0 x3 72 0 3 1 0 0 -2 0 0 x3 72 0 3 1 0 0 -2 0 0 x4 64 0 2 0 1 0 x4 64 0 2 0 1 0 -4 0 0 -4 0 6 x1 14 1 0 0 0 0 1 6 x1 14 1 0 0 0 0 1 0 0 -M x7

50、 22 0 1 0 -M x7 22 0 1 0 0 -1 0 10 -1 0 1 84-22M 0 M+4 0 0 -M 6-M 84-22M 0 M+4 0 0 -M 6-M 0 0Cj0 x3 6 0 0 1 0 (3) -2 -3 0 x3 6 0 0 1 0 (3) -2 -3 0 x4 20 0 0 0 1 2 -4 -2 0 x4 20 0 0 0 1 2 -4 -2 6 x1 14 1 0 0 0 0 1 0 6 x1 14 1 0 0 0 0 1 0 4 x2 22 0 1 0 0 -1 0 14 x2 22 0 1 0 0 -1 0 1 172 0 0 0 0 4 6-M

51、4-M 172 0 0 0 0 4 6-M 4-M0 x5 2 0 0 1/3 0 1 -2/3 -1 0 x5 2 0 0 1/3 0 1 -2/3 -1 0 x4 16 0 0 -2/3 1 0 -8/3 0 0 x4 16 0 0 -2/3 1 0 -8/3 0 6 x1 14 1 0 0 0 0 1 0 6 x1 14 1 0 0 0 0 1 0 x2 24 0 1 1/3 0 0 -2/3 -2 x2 24 0 1 1/3 0 0 -2/3 -2 180 0 0 -4/3 0 0 -M-10/3 -M 180 0 0 -4/3 0 0 -M-10/3 -M 6 4 0 0 0 - M

52、 - M 6 4 0 0 0 - M - M CB xB b x1 x2 CB xB b x1 x2 x3 x4 x5 x6 x3 x4 x5 x6 x7x7解为：解为：X=(14,24,0,16,2)。 目标函数值为目标函数值为:maxZ=6x1+4x2 =614+424=180练练 习习用大用大M法求解下列问题：法求解下列问题：两阶段法两阶段法对添加人工变量后的线性规划问题分两个对添加人工变量后的线性规划问题分两个阶段来计算，称为两阶段法。阶段来计算，称为两阶段法。两阶段法两阶段法 第一阶段是先求解一个目标函数中只第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，即令目标包含人工

53、变量的线性规划问题，即令目标函数中其它变量的系数取零，人工变量的函数中其它变量的系数取零，人工变量的系数取某个正的常数系数取某个正的常数( (一般取一般取1)1)，在保持原，在保持原问题约束条件不变的情况下求这个目标函问题约束条件不变的情况下求这个目标函数极小化时的解。数极小化时的解。作辅助问题作辅助问题原问题原问题njjjxcz1max0),.,2 , 1(1jnjijijxmibxamiiyw1min0),.,2 , 1(1jnjijijxmibxaiyiy,两阶段法两阶段法在第一阶段中，当人工变量取值为在第一阶段中，当人工变量取值为0 0时，时，目标函数值也为目标函数值也为0 0。这时候

54、的最优解就是。这时候的最优解就是原线性规划问题的一个基可行解。如果第原线性规划问题的一个基可行解。如果第一阶段求解结果最优解的目标函数值不为一阶段求解结果最优解的目标函数值不为0 0，也即最优解的基变量中含有非零的人，也即最优解的基变量中含有非零的人工变量，表明原线性规划问题无可行解。工变量，表明原线性规划问题无可行解。解题过程：解题过程：第第1阶段：解辅助问题当进行到最优表时，阶段：解辅助问题当进行到最优表时，若若W=0, 则得到原问题的一个则得到原问题的一个 基本可行解，转基本可行解，转入第入第2阶段。阶段。若若W0, 则判定原问题无可行解。则判定原问题无可行解。 第第2 2阶段：去除人工

55、变量，求解原问题。第一阶段阶段：去除人工变量，求解原问题。第一阶段的最优解为原问题的初始基可行解。的最优解为原问题的初始基可行解。maxZ= -x1 +2x2 x1 +x2 2-x1 +x2 1 x2 3x1 x2 0例：例： x1 +x2 -x3 =2-x1 +x2 -x4 =1 x2 +x5 =3x1 x5 01.化标准型：化标准型：maxZ= -x1 +2x2 +x6+x72.增加人工变量，构造单位矩阵：增加人工变量，构造单位矩阵：,x6, x7 03. 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 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