管理运筹学线性规划.ppt

管理运筹学线性规划线性规划 1经济管理学院经济管理学院第一讲第一讲 线性规划线性规划2经济管理学院经济管理学院第一章第一章 线性规划的数学模型线性规划的数学模型 线性规划线性规划 Linear Programming LP规划论中的静态规划规划论中的静态规划解决有限资源的最佳分配问题解决有限资源的最佳分配问题求解方法：求解方法：图解法图解法单纯形解法单纯形解法 3经济管理学院经济管理学院第一章第一章 线性规划的数学模型线性规划的数学模型4经济管理学院经济管理学院第一节第一节 线性规划一般模型线性规划一般模型一、线性规划问题的三个要素一、线性规划问题的三个要素 决策变量决策变量决策问题待定的量值称为决策变量。决策问题待定的量值称为决策变量。决策变量的取值要求非负。决策变量的取值要求非负。约束条件约束条件任任何何问问题题都都是是限限定定在在一一定定的的条条件件下下求求解解，把把各各种种限限制制条条件件表表示示为一组等式或不等式，称之为约束条件。为一组等式或不等式，称之为约束条件。约束条件是决策方案可行的保障。约束条件是决策方案可行的保障。LP的约束条件，都是决策变量的线性函数。的约束条件，都是决策变量的线性函数。目标函数目标函数衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。目标函数是决策变量的线性函数。目标函数是决策变量的线性函数。有的目标要实现极大，有的则要求极小。有的目标要实现极大，有的则要求极小。5经济管理学院经济管理学院第一节第一节 线性规划一般模型线性规划一般模型例例例例1.1.生产计划问题生产计划问题生产计划问题生产计划问题 某某厂厂生生产产、两两种种产产品品，已已知知生生产产单单位位产产品品所所需需的的设设备备台台时时及及A、B两两种种原原材材料料的的消消耗耗，以以及及资资源源的的限限制制，相相关关数据如表所示：数据如表所示：问如何安排问如何安排、两产品的产量，使利润为最大。两产品的产量，使利润为最大。二、线性规划模型的构建二、线性规划模型的构建 产品资源工时单耗 资源限制设备原料A原料B 1 1 2 1 0 1300台时400千克250千克单位产品获利 50元 100元6经济管理学院经济管理学院第一节第一节 线性规划一般模型线性规划一般模型(1)决决策策变变量量。要要决决策策的的问问题题是是、两两种种产产品品的的产产量量，因因此此有有两两个个决决策策变变量量：设设x1为为产产品品产产量量，x2为为产品产量。产品产量。(2)约约束束条条件件。生生产产这这两两种种产产品品受受到到现现有有生生产产能能力力的制约，原料用量也受限制。的制约，原料用量也受限制。设备的生产能力总量为设备的生产能力总量为300台时，则约束条件表述为台时，则约束条件表述为 x1+x2 300A、B两种原材料两种原材料约束条件为约束条件为2x1+x2 400 x2 250建立模型建立模型7经济管理学院经济管理学院第一节第一节 线性规划一般模型线性规划一般模型(3)(3)目标函数目标函数目标函数目标函数。目标是利润最大化，用目标是利润最大化，用Z表示利润，则表示利润，则 maxZ=50 x1+100 x2(4)(4)非非非非负负负负约约约约束束束束。、产产品品的的产产量量不不应应是是负负数数，否否则则没没有有实实际意义，这个要求表述为际意义，这个要求表述为 x1 0，x2 0综上所述，该问题的数学模型表示为综上所述，该问题的数学模型表示为 maxZ=50 x1+100 x2 x1+x2 300 2x1+x2 400 x2 250 x1 0,x2 08经济管理学院经济管理学院第一节第一节 线性规划一般模型线性规划一般模型 某某名名牌牌饮饮料料在在国国内内有有三三个个生生产产厂厂，分分布布在在城城市市A1、A2、A3,其其一一级级承承销销商商有有4个个，分分布布在在城城市市B1、B2、B3、B4，已已知知各各厂厂的的产产量量、各各承承销销商商的的销销售售量量及及从从Ai到到Bj的的每每吨吨饮饮料料运运费费为为Cij，为为发发挥挥集集团团优优势势，公公司司要要统统一筹划运销问题，求运费最小的调运方案。一筹划运销问题，求运费最小的调运方案。例例例例2.2.运输问题运输问题运输问题运输问题 销地产地B1 B2 B3 B4产量A1A2A3 6 3 2 5 7 5 8 4 3 2 9 7523销量 2 3 1 49经济管理学院经济管理学院第一节第一节 线性规划一般模型线性规划一般模型(1)(1)决策变量决策变量决策变量决策变量。设从设从Ai到到Bj的运输量为的运输量为xij，(2)(2)目标函数目标函数目标函数目标函数。运费最小的目标函数为运费最小的目标函数为minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34(3)(3)约束条件约束条件约束条件约束条件。产量之和等于销量之和产量之和等于销量之和,故要满足：故要满足：供应平衡条件供应平衡条件x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3销售平衡条件销售平衡条件x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4非负性约束非负性约束 xij0 (i=1,2,3；j=1,2,3,4)10经济管理学院经济管理学院第一节第一节 线性规划一般模型线性规划一般模型用一组非负决策变量表示一个决策问题，用一组非负决策变量表示一个决策问题，存在一定的等式或不等式的线性约束条件，存在一定的等式或不等式的线性约束条件，有一个希望达到的目标，可表示成决策变量的线性有一个希望达到的目标，可表示成决策变量的线性函数。可能是最大化，也可能是最小化。函数。可能是最大化，也可能是最小化。线性规划一般模型的代数式线性规划一般模型的代数式 为：为：三、线性规划的一般模型三、线性规划的一般模型 max(min)Z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn (,)b1a21x1+a22x2+a2nxn (,)b2 am1x1+am2x2+amnxn(,)bmx1,x2,xn()011经济管理学院经济管理学院第二节第二节 线性规划的图解法线性规划的图解法 图解法即是用图示的方法来求解线性规划问题。图解法即是用图示的方法来求解线性规划问题。一个二维的线性规划问题，可以在平面图上求解，一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，这就比较麻三维的线性规划则要在立体图上求解，这就比较麻烦，而维数再高以后就不能图示了。烦，而维数再高以后就不能图示了。一、图解法的基本步骤一、图解法的基本步骤12经济管理学院经济管理学院第二节第二节 线性规划的图解法线性规划的图解法1.可行域的确定可行域的确定 例例1的数学模型为的数学模型为 maxZ=50 x1+100 x2 x1+x2 300 2x1+x2 400 x2 250 x1 0,x2 0 x2=2502x1+x2=400五边形五边形ABCDO内内(含边界含边界)的任意一点的任意一点(x1，x2)都是满足所有都是满足所有约束条件的一个解，称之可行解约束条件的一个解，称之可行解。满足所有约束条件的解的集合，称之为可行域。即所有约束满足所有约束条件的解的集合，称之为可行域。即所有约束条件共同围城的区域。条件共同围城的区域。x1+x2=300ABCDOz=0=50 x1+100 x2 Z=27500=50 x1+100 x213经济管理学院经济管理学院第二节第二节 线性规划的图解法线性规划的图解法2.最优解的确定最优解的确定目标函数目标函数 Z=50 x1+100 x2 代表以代表以Z为参数的一族平行线。为参数的一族平行线。等值线：位于同一直线上的点的目标函数值相同。等值线：位于同一直线上的点的目标函数值相同。最优解：可行解中使目标函数最优最优解：可行解中使目标函数最优(极大或极小极大或极小)的解。的解。最优值最优值:取最优解时对应的目标函数值取最优解时对应的目标函数值14经济管理学院经济管理学院第二节第二节 线性规划的图解法线性规划的图解法由由线线性性不不等等式式组组成成的的可可行行域域是是凸凸集集(凸凸集集的的定定义义是是：集合内部任意两点连线上的点都属于这个集合集合内部任意两点连线上的点都属于这个集合)。可可行行域域有有有有限限个个顶顶点点。设设规规划划问问题题有有n个个变变量量，m个个约束，则顶点的个数不多于约束，则顶点的个数不多于Cnm个。个。目目标标函函数数最最优优值值一一定定在在可可行行域域的的边边界界达达到到，而而不不可可能在其内部。能在其内部。二、几点说明二、几点说明15经济管理学院经济管理学院第二节第二节 线性规划的图解法线性规划的图解法三三、解的可能性、解的可能性x1=82x2=123x1+4 x2=36例例 maxZ=3x1+4 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0Z=24Z=36Z=12唯一最优解：只有一个最优点。唯一最优解：只有一个最优点。多多重重最最优优解解：无无穷穷多多个个最最优优解解。若若在在两两个个顶顶点点同同时时得到最优解，则它们连线上的每一点都是最优解。得到最优解，则它们连线上的每一点都是最优解。16经济管理学院经济管理学院第二节第二节 线性规划的图解法线性规划的图解法无无界界解解：线线性性规规划划问问题题的的可可行行域域无无界界，使使目目标标函函数数无限增大而无界。（缺乏必要的约束条件）无限增大而无界。（缺乏必要的约束条件）三三、解的可能性（续）、解的可能性（续）例如例如 maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1 0,x2 0-2x1+x2=2x1-3 x2=3Z=6Z=1217经济管理学院经济管理学院第二节第二节 线性规划的图解法线性规划的图解法无可行解：若约束条件相互矛盾，则可行域为空集无可行解：若约束条件相互矛盾，则可行域为空集三三、解的可能性（续）、解的可能性（续）例如例如 maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1 0,x2 0-2x1+x2=2x1-3 x2=318经济管理学院经济管理学院第三节第三节 线性规划的标准型线性规划的标准型线性规划问题的数学模型有各种不同的形式，如线性规划问题的数学模型有各种不同的形式，如目标函数有极大化和极小化；目标函数有极大化和极小化；约束条件有约束条件有“”、“”和和“”三种情况；三种情况；决策变量一般有非负性要求，有的则没有。决策变量一般有非负性要求，有的则没有。为为了了求求解解方方便便，特特规规定定一一种种线线性性规规划划的的标标准准形形式式，非标准型可以转化为标准型。标准形式为：非标准型可以转化为标准型。标准形式为：目标函数极大化，目标函数极大化，约束条件为等式，约束条件为等式，右端常数项右端常数项bi0，决策变量非负。决策变量非负。一一、标准型、标准型19经济管理学院经济管理学院第三节第三节 线性规划的标准型线性规划的标准型1.代数式代数式二、标准型的表达方式二、标准型的表达方式 有代数式、矩阵式：有代数式、矩阵式：maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxnbm x1,x2,xn 0maxZ=cjxj aijxjbi (i=1,2,m)xj0 (j=1,2,n)简记20经济管理学院经济管理学院第三节第三节 线性规划的标准型线性规划的标准型2.矩阵式矩阵式 21经济管理学院经济管理学院第三节第三节 线性规划的标准型线性规划的标准型 目标函数极小化问题目标函数极小化问题目标函数极小化问题目标函数极小化问题 minZ=CTX，只需将等式两端乘以，只需将等式两端乘以-1 即变为极大化问题。即变为极大化问题。因为因为minZ=-max(-Z)=CTX，令，令Z=-Z，则，则maxZ=-CX 右端常数项非正右端常数项非正右端常数项非正右端常数项非正 两端同乘以两端同乘以-1 约束条件为不等式约束条件为不等式约束条件为不等式约束条件为不等式当约束方程为当约束方程为“”时，左端加入一个非负的松弛变量，就把不等式时，左端加入一个非负的松弛变量，就把不等式变成了等式；变成了等式；当约束条件为当约束条件为“”时，不等式左端减去一个非负的剩余变量时，不等式左端减去一个非负的剩余变量(也可称也可称松弛变量松弛变量)即可。即可。决策变量决策变量决策变量决策变量x xk k没有非负性要求没有非负性要求没有非负性要求没有非负性要求 令令xk=xk-x k，xk=xk，x k 0，用，用xk、x k 取代模型中取代模型中xk三、非标准型向标准型转化三、非标准型向标准型转化 22经济管理学院经济管理学院第三节第三节 线性规划的标准型线性规划的标准型例例1 的标准型的标准型 例例1 maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 x1,x2,x3,x4,x5 0 maxZ=3x1+5 x2+0 x3+0 x4+0 x5 23经济管理学院经济管理学院 minZ=x1+2 x2+3 x3 x1+2 x2+x35 2x1+3 x2+x36 -x1 -x2 -x3-2 x1 0,x30 第三节第三节 线性规划的标准型线性规划的标准型例例 minZ=x1+2 x2-3 x3 x1+2 x2-x3 5 2x1+3 x2-x3 6 -x1 -x2 +x3 -2 x1 0,x3 0标准化标准化124经济管理学院经济管理学院第三节第三节 线性规划的标准型线性规划的标准型标准化标准化2 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x35 2x1+3(x2-x 2)+x36 -x1 -(x2-x 2)-x3-2 x1,x2,x 2,x3 0 标准化标准化3 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x35 2x1+3(x2-x 2)+x36 x1+(x2-x 2)+x3 2 x1,x2,x 2,x3 025经济管理学院经济管理学院第三节第三节 线性规划的标准型线性规划的标准型标准化标准化4 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x3+x4=5 2x1+3(x2-x 2)+x36 x1+(x2-x 2)+x3 2 x1,x2,x 2,x3,x4 0标准化标准化5 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x3+x4 =5 2x1+3(x2-x 2)+x3 -x5=6 x1+(x2-x 2)+x3 2 x1,x2,x 2,x3,x4,x5 026经济管理学院经济管理学院第三节第三节 线性规划的标准型线性规划的标准型标准化标准化6 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x3+x4 =5 2x1+3(x2-x 2)+x3 -x5 =6 x1+(x2-x 2)-x3 +x6=2 x1,x2,x 2,x3,x4,x5,x6 0标准化标准化7 maxZ=-x1-2(x2-x 2)-3x3+0 x4+0 x5+0 x6 x1+2(x2-x 2)+x3+x4 =5 2x1+3(x2-x 2)+x3 -x5 =6 x1+(x2-x 2)-x3 +x6 =2 x1,x2,x 2,x3,x4,x5,x6 0 27经济管理学院经济管理学院第四节第四节 线性规划解的概念线性规划解的概念可行解：可行解：满足约束条件满足约束条件AX=b,X0的解。的解。最优解：最优解：使目标函数最优的可行解，称为最优解。使目标函数最优的可行解，称为最优解。基基mn，且，且m个方程线性无关，即矩阵个方程线性无关，即矩阵A的秩为的秩为m；根；根据线性代数定理可知，据线性代数定理可知，nm，则方程组有多个解，这，则方程组有多个解，这也正是线性规划寻求最优解的余地所在。也正是线性规划寻求最优解的余地所在。一、线性规划解的概念一、线性规划解的概念 28经济管理学院经济管理学院第四节第四节 线性规划解的概念线性规划解的概念线性方程组的增广矩阵线性方程组的增广矩阵例例1 的标准型的标准型 maxZ=50 x1+100 x2+0 x3+0 x4+0 x5 x1 +x2 +x3 =300 2 x1 +2x2 +x4 =400 x2 +x5=250 x1,x2,x3,x4,x5 0单位矩阵单位矩阵29经济管理学院经济管理学院第四节第四节 线性规划解的概念线性规划解的概念基矩阵：基矩阵：系数矩阵系数矩阵A中任意中任意m列所组成的列所组成的m阶非奇异子矩阵，称阶非奇异子矩阵，称为该线性规划问题的一个基矩阵。为该线性规划问题的一个基矩阵。或称为一个基，用或称为一个基，用B表示。表示。称基矩阵的列为基向量，用称基矩阵的列为基向量，用Pj表示表示(j=1,2,m)。不。不在在B中的向量称为非基向量中的向量称为非基向量30经济管理学院经济管理学院第四节第四节 线性规划解的概念线性规划解的概念基变量：基变量：与基向量与基向量Pj相对应的相对应的m个变量个变量xj称为基变量，称为基变量，其余的其余的m-n个变量为非基变量。个变量为非基变量。基解：基解：令所有非基变量等于零，对令所有非基变量等于零，对m个基变量所求的解，个基变量所求的解，对应一个特定的基矩阵能求得一组唯一解，这个对应于基的解对应一个特定的基矩阵能求得一组唯一解，这个对应于基的解称为基解。称为基解。结合图解来看，基解是各约束方程及坐标轴之间交点的坐标。结合图解来看，基解是各约束方程及坐标轴之间交点的坐标。基变量是基变量是x3,x4,x5非基变量是非基变量是x1,x2令非基变量令非基变量x1=x2=0，得到一个基解得到一个基解 x3=300，x4=400，x5=25031经济管理学院经济管理学院第四节第四节 线性规划解的概念线性规划解的概念基可行解：满足非负性约束的基解称为基可行解。基可行解：满足非负性约束的基解称为基可行解。可行基：对应于基可行解的基，称为可行基。可行基：对应于基可行解的基，称为可行基。最优基：最优解对应的基矩阵，称为最优基。最优基：最优解对应的基矩阵，称为最优基。非可行解可行解基解32经济管理学院经济管理学院第四节第四节 线性规划解的概念线性规划解的概念 定理定理定理定理1 1.若线性规划问题存在可行域，则其可行域一定是凸集。若线性规划问题存在可行域，则其可行域一定是凸集。定理定理定理定理2 2.线性规划问题的基可行解对应可行域的顶点。线性规划问题的基可行解对应可行域的顶点。定定定定理理理理3 3.若若可可行行域域有有界界，线线性性规规划划的的目目标标函函数数一一定定可可以以在在可可行行域域的顶点上达到最优。的顶点上达到最优。二、线性规划的基本定理二、线性规划的基本定理 线线性性规规划划问问题题可可以以有有无无数数个个可可行行解解，最最优优解解只只可可能能在在顶顶点点上上达达到到，而而有有限限个个顶顶点点对对应应的的是是基基可可行行解解，故故只只要要在在有有限限个个基基可行解中寻求最优解即可。可行解中寻求最优解即可。从从一一个个顶顶点点出出发发找找到到一一个个可可行行基基，得得到到一一组组基基可可行行解解，拿拿目目标函数做尺度衡量一下看是否最优。标函数做尺度衡量一下看是否最优。如如若若不不是是，则则向向邻邻近近的的顶顶点点转转移移，换换一一个个基基再再行行求求解解、检检验验，如此迭代循环目标值逐步改善，直至求得最优解。如此迭代循环目标值逐步改善，直至求得最优解。三、线性规划的解题思路三、线性规划的解题思路 33经济管理学院经济管理学院第二章第二章 线性规划单纯形法线性规划单纯形法 单纯形法单纯形法(Simplex Method)是美国人丹捷格是美国人丹捷格(G.Dantzig)1947年创建的年创建的这种方法简捷、规范，是举世公认的解决线性这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。规划问题行之有效的方法。单纯形法的表现形式：单纯形法的表现形式：代数法代数法表格法表格法矩阵法矩阵法34经济管理学院经济管理学院第二章第二章 线性规划单纯形法线性规划单纯形法35经济管理学院经济管理学院第一节第一节 单纯形法原理单纯形法原理一、代数解法一、代数解法 非奇异子阵，做为一个基基变量基变量x3,x4,x5非基变量非基变量x1,x2 maxZ=50 x1+100 x2+0 x3+0 x4+0 x5 x1 +x2 +x3 =300 2 x1 +x2 +x4 =400 x2 +x5=250 x1,x2,x3,x4,x5 036经济管理学院经济管理学院第一节第一节 单纯形法原理单纯形法原理将基变量用非基变量线性表示，即将基变量用非基变量线性表示，即x3=300-x1 -x2 x4=400-2x1 -x2 x5=250-x2 令非基变量令非基变量x1=0，x2=0，找到一个初始基可行解，找到一个初始基可行解：x1=0，x2=0，x3=300，x4=400，x5=250即即X0=(0,0,300,400,250)T一个可行解就是一个生产方案，在上述方案中两种产品都不一个可行解就是一个生产方案，在上述方案中两种产品都不生产，利润生产，利润Z=0。1.求初始基可行解求初始基可行解 37经济管理学院经济管理学院第一节第一节 单纯形法原理单纯形法原理确定入基变量确定入基变量 maxZ=50 x1+100 x2+0 x3+0 x4+0 x5 x1 +x2 +x3 =300 2 x1 +x2 +x4 =400 x2 +x5=250从目标函数从目标函数maxZ=50 x1+100 x2+0 x3+0 x4+0 x5可知：可知：非非基基变变量量x1和和x2的的系系数数均均为为正正数数，生生产产哪哪种种产产品品都都会会增加利润。增加利润。因因为为x2的的系系数数大大于于x1的的系系数数，即即生生产产单单位位乙乙产产品品比比甲甲产产品品利利润润更更高高一一些些，故故应应优优先先多多生生产产乙乙产产品品，即即优优先先把把x2作为入基变量。作为入基变量。2.第一次迭代第一次迭代 38经济管理学院经济管理学院第一节第一节 单纯形法原理单纯形法原理确定离基变量确定离基变量基变量用非基变量线性表示基变量用非基变量线性表示x3=300-x1 -x2 x4=400-2x1 -x2 x5=250-x2保持原非基变量保持原非基变量x1=0，x2变成基变量时应保证变成基变量时应保证 x3,x4,x5非负，即有非负，即有2.第一次迭代（续）第一次迭代（续）x3 =300-x2 0 x4=400-x2 0 x5=250-x2 0 x2 300 x2 400 x2 250 则离基变量为则离基变量为x539经济管理学院经济管理学院第一节第一节 单纯形法原理单纯形法原理2.第一次迭代（续）第一次迭代（续）主元主元进基变量所在列为主列，离基变量所在行为主行进基变量所在列为主列，离基变量所在行为主行 maxZ=50 x1+100 x2+0 x3+0 x4+0 x5 x1 +x2 +x3 =300 2 x1 +x2 +x4 =400 x2 +x5=250 40经济管理学院经济管理学院第一节第一节 单纯形法原理单纯形法原理基变换基变换进行初等变换，变主元为进行初等变换，变主元为1，主列为单位列向量。，主列为单位列向量。2.第一次迭代（续）第一次迭代（续）-Z+50 x1+100 x2+0 x3+0 x4+0 x5=0 x1 +x2 +x3 =300 2 x1 +x2 +x4 =400 x2 +x5=250-Z+50 x1+0 x2+0 x3+0 x4-100 x5+25000=0 x1 +x3 -x5 =50 2 x1 +x4 -x5 =150 x2 +x5 =250此时此时x2，x3，x4为基变量为基变量初等行变换初等行变换41经济管理学院经济管理学院第一节第一节 单纯形法原理单纯形法原理2.第一次迭代（续）第一次迭代（续）将基变量用非基变量线性表示，即将基变量用非基变量线性表示，即x2=250-x5 x3=50 x1+x5x4=150-2x1+x5令非基变量令非基变量x1=0，x5=0，找到另一个基可行解，找到另一个基可行解 x1=0，x2=250，x3=50，x4=150，x5=0即即X1=(0,250,50,150,0)T目标函数目标函数Z=2500042经济管理学院经济管理学院第一节第一节 单纯形法原理单纯形法原理确定入基变量确定入基变量3.第二次迭代第二次迭代 目标函数目标函数，Z=50 x1+0 x2+0 x3+0 x4-100 x5+25000 非基非基变量变量x1的系数的系数 1=50（检验数）为正数，（检验数）为正数，确定确定x1为入基变量。为入基变量。-Z+50 x1+0 x2+0 x3+0 x4-100 x5+25000=0 x1 +x3 -x5 =50 2 x1 +x4 -x5 =150 x2 +x5 =250第一次迭代结果第一次迭代结果43经济管理学院经济管理学院第一节第一节 单纯形法原理单纯形法原理确定出基变量确定出基变量3.第二次迭代第二次迭代（续）（续）x3=50+x5-x1 0 x2=150-2x1+x5 0 x4=250 x5 0 x1 50 x1 75基变量用非基变量线性表示基变量用非基变量线性表示 x1=50+x5-x1 x2=150-2x1+x5 x4=250 x5保持原非基变量保持原非基变量x5=0，x1变成基变量时应保证变成基变量时应保证 x2,x3,x5非负，即非负，即 对应的对应的x3定为出基变量定为出基变量44经济管理学院经济管理学院第一节第一节 单纯形法原理单纯形法原理基变换基变换变主元为变主元为1，主列为单位列向量。，主列为单位列向量。3.第二次迭代（续）第二次迭代（续）-Z+50 x1+0 x2+0 x3+0 x4-100 x5+25000=0 x1 +x3 -x5 =50 2 x1 +x4 -x5 =150 x2 +x5 =250-Z+0 x1 +0 x2-50 x3+0 x4-50 x5+27500 =0 x1 +x3 -x5 =50 -2x3 +x4 +x5 =50 x2 +x5 =250基变量为基变量为x1 x2 ，x4 45经济管理学院经济管理学院第一节第一节 单纯形法原理单纯形法原理3.第二次迭代（续）第二次迭代（续）将基变量用非基变量线性表示，即将基变量用非基变量线性表示，即x1 =50 x3+x5x2=250-x5x4=50+2x3-x5 令非基变量令非基变量x3=0，x5=0，又找到一个基可行解又找到一个基可行解 目标函数目标函数-Z+0 x1 +0 x2-50 x3+0 x4-50 x5+27500 =0 x1=50，x2=250，x3=0，x4=50，x5=0即即 X2=(50,250,0,50,0)T Z=27500 检验数检验数j非正，得最优解非正，得最优解X*=(4,6,4,0,0)T，Z*=4246经济管理学院经济管理学院第一节第一节 单纯形法原理单纯形法原理二、单纯形法的几何意义二、单纯形法的几何意义X0=(0,0,300,400,250)TX1=(0,250，50，150,0)TX1=(50,250,0,50,0)Tx2=2502x1+x2=400 x1+x2=300ABCDO47经济管理学院经济管理学院第二节第二节 表格单纯形法表格单纯形法 表格单纯形法，是对上节讨论的方法步骤进行具体表格单纯形法，是对上节讨论的方法步骤进行具体化、规范化、表格化的结果。化、规范化、表格化的结果。一、单纯形法表一、单纯形法表CjC1C2CjCn比比值值CBXBbx1x2xjxnCB1xB1b1a11a12a1ja1n 1CB2xB2b2a21a22a2ja2n 2CBnxBnbmam1am2amjamn m检验数检验数 j-Z 1 2 j n48经济管理学院经济管理学院第二节第二节 表格单纯形法表格单纯形法将线性规划问题化成标准型。将线性规划问题化成标准型。找出或构造一个找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。阶单位矩阵作为初始可行基，建立初始单纯形表。计计算算各各非非基基变变量量xj的的检检验验数数 j=Cj-CBPj，若若所所有有 j0，则则问问题题已已得得到最优解，停止计算，否则转入下步。到最优解，停止计算，否则转入下步。在在大大于于0的的检检验验数数中中，若若某某个个 k所所对对应应的的系系数数列列向向量量Pk0，则则此此问问题是无界解，停止计算，否则转入下步。题是无界解，停止计算，否则转入下步。根根据据max j j0=k原原则则，确确定定xk为为换换入入变变量量(进进基基变变量量)，再再按按 规规则则计计算算：=minbi/aik|aik0=bl/aik 确确定定xBl为为换换出出变变量量。建立新的单纯形表，此时基变量中建立新的单纯形表，此时基变量中xk取代了取代了xBl的位置。的位置。以以aik为为主主元元素素进进行行迭迭代代，把把xk所所对对应应的的列列向向量量变变为为单单位位列列向向量量，即即aik变为变为1，同列中其它元素为，同列中其它元素为0，转第，转第 步。步。二、单纯形法的计算步骤二、单纯形法的计算步骤 49经济管理学院经济管理学院第二节第二节 表格单纯形法表格单纯形法 maxZ=3x1+5 x2+0 x3+0 x4+0 x5=0 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 三、单纯形法计算举例三、单纯形法计算举例Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=950经济管理学院经济管理学院第二节第二节 表格单纯形法表格单纯形法检验数检验数 j81010060101/2012300-21x3x2x5050-30300-5/208-4Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=951经济管理学院经济管理学院第二节第二节 表格单纯形法表格单纯形法Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4检验数检验数 j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1最优解最优解:X*=(4,6,4,0,0)T，Z*=4252经济管理学院经济管理学院第二节第二节 表格单纯形法表格单纯形法最优基最优基 Cj35000比比值值CBXBbx1x2x3x4x50 x340012/3-1/35x260101/203x14100-2/31/3检验数检验数 j-42000-1/2-1x3x2x1最优基的逆最优基的逆 最优基和最优基的逆最优基和最优基的逆53经济管理学院经济管理学院第二节第二节 表格单纯形法表格单纯形法例如例如maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1,x2 0标准化标准化 maxZ=3x1+2 x2-2x1+x2+x3 =2 x1-3 x2 +x4=3 x1,x2,x3,x4 0Cj比比值值CBXBb检验数检验数 jx1x2x3x432002-211031-301x3x40003200-3检验数检验数 j80-512x3x103-31-301-90110-3此时，此时，检验数检验数 2=11 0，还没有得到最优解。，还没有得到最优解。确定确定x2进基，但进基，但x2所在列的系数向量元素非正，无界所在列的系数向量元素非正，无界 值不存在，有进基变量但无离基变量。值不存在，有进基变量但无离基变量。54经济管理学院经济管理学院第三节第三节 人工变量问题人工变量问题 用单纯形法解题时，需要有一个单位阵作为初始基。用单纯形法解题时，需要有一个单位阵作为初始基。当约束条件都是当约束条件都是“”时，加入松弛变量就形成了初始基。时，加入松弛变量就形成了初始基。但实际存在但实际存在“”或或“”型的约束，没有现成的单位矩阵。型的约束，没有现成的单位矩阵。一、人工变量一、人工变量 采用人造基的办法：采用人造基的办法：人工构造单位矩阵人工构造单位矩阵人工构造单位矩阵人工构造单位矩阵在没有单位列向量的等式约束中加入人工变量，构成原线性在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。规划问题的伴随问题，从而得到一个初始基。人工变量是在等式中人为加进的，只有它等于人工变量是在等式中人为加进的，只有它等于0时，约束条件时，约束条件才是它本来的意义。才是它本来的意义。处理方法有两种：处理方法有两种：大大M 法法两阶段法两阶段法55经济管理学院经济管理学院第三节第三节 人工变量问题人工变量问题没有单位矩阵，不符合构造初始基的条件，需加入人工变量没有单位矩阵，不符合构造初始基的条件，需加入人工变量。人工变量最终必须等于人工变量最终必须等于0才能保持原问题性质不变。才能保持原问题性质不变。为保证人工变量为为保证人工变量为0，在目标函数中令其系数为，在目标函数中令其系数为-M。M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。变量中替换出去。如若到最终表中人工变量仍没有置换出去，那么这个问题就没如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。有可行解，当然亦无最优解。大大M法法 例如例如 maxZ=3x1-x2-2 x3 3x1+2 x2-3 x3=6 x1 -2 x2+x3=4 x1,x2,x3 056经济管理学院经济管理学院第三节第三节 人工变量问题人工变量问题按大按大M法构造人造基，引入人工变量法构造人造基，引入人工变量x4,x5 的辅助问题如下：的辅助问题如下：maxZ=3x1 -x2 -2 x3-M x4-M x5 3x1+2 x2-3 x3 +x4 =6 x1 -2 x2+x3 +x5=4 x1,x2,x3,x4,x5 0Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53-1-2-M-M632-31041-2101-10M3+4M-1-2-2M00 x4x5-M-M2457经济管理学院经济管理学院第三节第三节 人工变量问题人工变量问题Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53-1-2-M-M632-31041-21013+4M-1-2-2M00 x4x5-M-M24检验数检验数 j212/3-11/3020-8/32-1/310-3-8M/31+2M-1-4M/30 x1x53-M-1检验数检验数 j31-2/301/61/210-4/31-1/61/20-5/30-M-5/6-M-1/2x1x33-258经济管理学院经济管理学院第四节第四节 单纯形法补遗单纯形法补遗进基变量相持：进基变量相持：单纯形法运算过程中，同时出现多个相同的单纯形法运算过程中，同时出现多个相同的 j最大。最大。在在符符合合要要求求的的 j(目目标标为为max：j0，min：j0)中中，选选取取下下标标最最小小的非基变量为换入变量；的非基变量为换入变量；离基变量相持：离基变量相持：单纯形法运算过程中，同时出现多个相同的最小单纯形法运算过程中，同时出现多个相同的最小值。值。继续迭代，便有基变量为继续迭代，便有基变量为0，称这种情况为，称这种情况为退化解退化解退化解退化解。选取其中下标最大的