运筹学第讲线性规划

运筹学第讲线性规划线性规划问题的几何意义

凸集:设K是n维欧氏空间的一点集，若任意两点X(1)∈K，X(2)∈K的连线上的所有点αX(1)+(1-α)X(2)∈K，(0≤α≤1)则称K为凸集。

注：实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。从直观上讲，凸集没有凹入部分，其内部没有空洞。图中的(a)(b)是凸集，(c)不是凸集。任何两个凸集的交集仍为凸集，如图(d)。第2页,共52页，2024年2月25日，星期天线性规划问题的几何意义结论：任何两个凸集的交集仍为凸集。

证明：设A，B为凸集，则因此同理从而所以A与B的交集为凸集。第3页,共52页，2024年2月25日，星期天线性规划问题的几何意义

凸组合：设X(1)，X(2)，…，X(k)是n维欧氏空间En中的k个点，若存在μ1，μ2，…，μk，且0≤μi≤1,i=1,2,…，k，使X=μ1X(1)+μ2X(2)+…+μkX(k)，则称X为X(1)，X(2)，…，X(k)的凸组合。（当0＜μi＜1时，称为严格凸组合）。

顶点：设K是凸集，X∈K；若X不能用不同的两点X(1)∈K和X(2)∈K的线性组合表示为X=αX(1)+(1-α)X(2)，(0＜α＜1)，则称X为K的一个顶点(或极点)。注

右图中0,Q1,Q2,Q3,Q4都是顶点。第4页,共52页，2024年2月25日，星期天线性规划问题的几何意义关于线性规划问题的几个定理：定理1：若线性规划问题存在可行解，则该问题的可行域是凸集。定理2：线性规划问题的基可行解X对应可行域(凸集)的顶点。定理3：若问题存在最优解，一定存在一个基可行解是最优解。（或在某个顶点取得）

以上证明过程见P16-20.第5页,共52页，2024年2月25日，星期天

单纯形法

尽管若线性规划问题有最优解，必可以在某顶点上得到，虽然顶点数目是有限的(它不大于个)，若采用“枚举法”找所有基可行解，然后一一比较，最终可能找到最优解。但当n,m的数较大时，这种办法是行不通的。（m=20，n=40时，顶点的个数有个）。

如何有效地找到最优解，有多种方法，这里仅介绍单纯形法(SimplexMethod)。第6页,共52页，2024年2月25日，星期天单纯形法

单纯形：单纯形或者n-单纯形是和三角形类似的n维几何体。精确的讲，单纯形是某个n维以上的欧几里得空间中的（n+1）个仿射无关（也就是没有m维平面包含m+1个点；这样的点集被称为处于一般位置）的点的集合的凸包。0-单纯形就是点，1-单纯形就是线段，2-单纯形就是三角形，3-单纯形就是四面体，而4-单纯形是一个五胞体（每种情况都包含内部）。标准n-单纯形：是Rn+1的子集：第7页,共52页，2024年2月25日，星期天单纯形法

单纯形法的基本思路：根据前述定理，如果线性规划问题存在最优解，则可以在基本可行解中找最优解。由于基本可行解的个数是有限的，所以通过建立一种最优性判别准则，将基本可行解逐一进行检查，就可以在有限次检查后得到最优解。但是，在有些情况下，要找出所有的基本可行解是非常麻烦的，单纯形法的优越性就在于不用找出全部的基本可行解。第8页,共52页，2024年2月25日，星期天单纯形法

单纯形法的基本思路：在得到一个基本可行解X1后，判断X1是否是最优解，或者判断此问题没有最优解。如果X1是最优解，或者此问题没有最优解，则求解到此为止；若不然，则依据这个解X1求出下一个基本可行解X2，并且X2要比X1对应的目标函数值有所改善。对X2重复刚才的判断，直到得到问题的解答为止。X1X2X3第9页,共52页，2024年2月25日，星期天单纯形法

单纯形法的基本步骤：(1)确定初始基本可行解X1；(2)记Xk为求出的第k个基本可行解，根据建立的最优性准则，对Xk进行检验，若Xk是最优解，则计算终止;若不然，则转第(3)步；(3)若根据建立的无最优解准则判断此问题没有最优解，则计算终止；若不能判定没有最优解，则转第(4)步；(4)依据Xk求基本可行解Xk+1，使Z(Xk+1)≥Z(Xk)，令k=k+1，转回第(2)步。第10页,共52页，2024年2月25日，星期天单纯形法

单纯形法的基本步骤：是否最优转移到另一个基本可行解（找出更大的目标函数值）最优解是否核心是：变量迭代结束找出一个初始可行解循环第11页,共52页，2024年2月25日，星期天单纯形法

单纯形法的基本步骤：(1)确定初始的基本可行解X1；-假设在约束系数矩阵中含有单位阵并且bi≥0，i=1,2,……,m，则令单位阵所在列对应的变量为基变量，其他变量为非基变量，并令非基变量取零值，可得到初始基本可行解。-对于所有行约束条件为“≤”不等式，在每行引入松弛变量化为标准形后，所有松弛变量的系数矩阵正好为单位矩阵。-当化为标准形后系数矩阵中不含有单位阵时，确定初始基本可行解的方法可采用人工变量法。-首先假设系数矩阵含单位阵的情况。第12页,共52页，2024年2月25日，星期天单纯形法

单纯形法的基本步骤：(2)确定最优性判别准则；设线性规划问题(LP)约束系数矩阵中的前m列为一个单位阵，其模型有如下形式，其中bi

≥0，i=1,2,……,m。目标函数：

maxz=c1x1+c2

x2+…+cnxn

约束条件：

s.t.x1+a1m+1

x

m+1+…+a1n

xn=b1

x2+a2m+1

x

m+1+…+a2n

xn

=b2

(LP)

…………

xm+amm+1

x

m+1+…+amnxn=bm

x1，x2，…，xn≥0.第13页,共52页，2024年2月25日，星期天单纯形法

单纯形法的基本步骤：(2)确定最优性判别准则；取x1，…，xm为基变量，xm+1，…，xn为非基变量。基本解为X1=（b1，b2，……，bm，0，……，0）T。将上式约束方程组变为：

x1=b1-（a1m+1

x

m+1+…+a1n

xn）

x2=b2-（a2m+1

x

m+1+…+a2n

xn）…………

xm=bm-（amm+1

x

m+1+…+amnxn）代入目标函数中：

Z=c1

x1+c2

x2+…+cnxn第14页,共52页，2024年2月25日，星期天单纯形法

单纯形法的基本步骤：(2)确定最优性判别准则；记得到目标函数由当前解X1的非基变量的线性表示：其中Z1即为X1对应的目标函数值。第15页,共52页，2024年2月25日，星期天单纯形法

单纯形法的基本步骤：(2)确定最优性判别准则；将上面结果整理后，可得到与原线性规划等价的模型定义：称此等价模型为基本可行解X1对应的典式。第16页,共52页，2024年2月25日，星期天单纯形法

单纯形法的基本步骤：(2)确定最优性判别准则；定理4：设X1=（b1，b2，……，bm，0，……，0）T为线性规划(LP)的基本可行解，如果在其对应的典式中则X1为最优解。注：此定理就是单纯形法中的最优性判别准则。第17页,共52页，2024年2月25日，星期天单纯形法

单纯形法的基本步骤：(2)确定最优性判别准则；证明：设为任一可行解,Z0为其目标函数值。将X0代入基本可行解X1对应的典式的目标函数中，有由式，则有说明Z1为最大值，X1为最优解，定理得证。第18页,共52页，2024年2月25日，星期天单纯形法

单纯形法的基本步骤：(2)确定最优性判别准则；注：典式中的称为基本可行解的检验数，确切地说，是X1的非基变量的检验数。为了统一起见，对X1的基变量也规定检验数，显然，应有(因为典式中不含基变量，实际通过公式计算也为零)，即基变量的检验数为零。第19页,共52页，2024年2月25日，星期天单纯形法例3.1

为下面线性规划问题的一个基本可行解，试判断其是否为最优解。解:将模型化为基本可行解X1对应的典式，X1=(6,2,15,0,0)T

可知，x4,x5为非基变量，约束条件已具有典式形式，只需要将目标函数由非基变量x4,x5线性表示即可：

Z=-(6-x4-6x5)+(2+x4-x5)+2(15-6x4-2x5)+2x4+x5=26-8x4+2x5由此可知，其中不满足最优性准则，因此不能判断X1为最优解。第20页,共52页，2024年2月25日，星期天单纯形法

单纯形法的基本步骤：(3)确定无最优解判别准则；定理5

设X1为线性规划问题的基本可行解，如果在X1对应的典式中存在检验数，并且的约束系数

皆小于等于零，则该线性规划问题的目标函数在可行域上没有上界，即没有最优解（无界解）。例3.2判断下面的问题是否没有最优解。第21页,共52页，2024年2月25日，星期天单纯形法解:取为基本可行解，对于X1此模型已经为典式形式。其中检验数，并且皆小于等于零，由定理判断无最优解。怎么理解？？分析：由约束条件可知，对于x3取任何非负值，此问题都存在可行解，目标函数值为。故而可知当M逐渐增大时，Z也相应增大，当时，

因此Z为最大值，规划无最优解。第22页,共52页，2024年2月25日，星期天单纯形法

单纯形法的基本步骤：(4)基本可行解的迭代；定义:根据已有的基本可行解求新的基本可行解称为迭代。定义:将原基本可行解X1中的某个非基变量变为基变量，称为进基变量；将X1的某个基变量变为非基变量，称为出基变量。注:迭代的过程实际就是要实现进基变量和出基变量之间的转换。第23页,共52页，2024年2月25日，星期天单纯形法迭代方法:设为基变量，并且存在检验数，由X1的典式形式的目标函数的表达式可知其中Z1为X1对应的目标函数值。由于，故若选xk为进基变量时(一般基变量的取值大于零)，可使目标函数值进一步增加。因此确定xk为进基变量。基本可行解X1的典式形式的约束方程组为在基本可行解中，基变量的个数是固定的m个,xk进基，则必有一个基变量转换为非基变量。第24页,共52页，2024年2月25日，星期天单纯形法为了确定出基变量，首先在典式的约束中，令除xm以外的其余非基变量仍取零值，得到:根据这个关系式，又考虑到每个决策变量的可行性，从而选取xk，使其满足如下的关系式:第25页,共52页，2024年2月25日，星期天单纯形法当时，因为bi非负，故只需要即可;当时，则需。综合上面两种情况，因此，应使xk满足注:因为最优性判别准则和无最优解判别定理不成立，故可以保证的存在性，以及。按照上面的规则确定的变量xk，当时，使得原第l个基变量的值变为:即基变量xl

成为出基变量。第26页,共52页，2024年2月25日，星期天单纯形法可以证明，矩阵仍为可行基，因此得到新的基本可行解，其中各分量的值为:根据X1的典式的表达式中的目标函数，将X2代入计算得:新解比原解有所改善，增量为至此，完成了基本可行解的迭代。第27页,共52页，2024年2月25日，星期天单纯形法

定义:一般称

为最小比值规则，或称为规则，其中的称为中心元素（主元）。现将基本可行解的迭代过程归纳如下：设已得到基本可行解对应的典式形式。(1)取对应的xk为进基变量。（主要是提高收敛效率，使得每次的增量最大。）(2)按最小比值规则确定xk的值，并确定出基变量。(3)按右式确定新的基本可行解。第28页,共52页，2024年2月25日，星期天单纯形法例3.3

根据基本可行解X1以及典式，迭代求新的基本可行解，并指出目标函数值的增量。其典式为X1的目标函数值为Z1=26解:由于，所以确定x5为进基变量。按最小比值规则计算出

因此，同时确定xl为出基变量，取零值，另外x4为非基变量仍取零值。第29页,共52页，2024年2月25日，星期天单纯形法将这些取值代入X2计算公式中，得到新的基本可行解为其目标函数值为目标函数值的增量为。对X2还应继续判断其是否是最优解。则问题转化为如何确定新的基本可行解X2的检验数。第30页,共52页，2024年2月25日，星期天单纯形法

单纯形法的基本步骤：(5)新的基本可行解的检验数的确定。不失一般性，考虑下面的线性规划模型:假设已得到的基本可行解不是最优解。并假设经过计算，确定x5为进基变量，x1为出基变量，a15为中心元素，得到新的基本可行解,第31页,共52页，2024年2月25日，星期天单纯形法

单纯形法的基本步骤：(5)新的基本可行解的检验数的确定。为了判断X2是否最优解，需要对约束方程组进行适当变换，找出X2对应的典式形式。为此，首先要在约束方程组中将新基变量x2,x3,x5显式表示出来，然后代入目标函数，得到目标函数由新的非基变量的线性表示，从而得到X2对应的检验数。这些变换可以经过下面的矩阵变换实现，即根据约束方程组构造矩阵式，对其进行初等行变换，变为矩阵式第32页,共52页，2024年2月25日，星期天单纯形法

单纯形法的基本步骤：(5)新的基本可行解的检验数的确定。即：将进基变量x5对应的第5列向量化为单位向量，其中将中心元素a15化为1。由上面得到转化后的矩阵式，得到新的基本可行解X2对应的典式形式：其中即为新解X2的检验数，根据他们的正负，可以判断X2是否最优解。第33页,共52页，2024年2月25日，星期天单纯形法例3.4

对例3.3中得到的基本可行解X2，判断其是否是最优解。由此可得到在求X2的检验数时用到的矩阵解:是根据得到的，而X1对应的典式为将进基变量x5对应的第5列向量化为单位向量，将中心元素a15=6化为1，得到:第34页,共52页，2024年2月25日，星期天单纯形法由此矩阵可知，的检验数，全部小于等于零，因此X2就是最优解。第35页,共52页，2024年2月25日，星期天单纯形法小结单纯形法的主要步骤：Step1

确定初始的基本可行解X1，求出X1对应的典式；Step2

根据最优性准则判别定理判断X1是否是最优解，若是，算法停止，X1即为最优解。否则，根据无最优解判别准则判断此线性规划是否无最优解，若是，算法停止，此规划无最优解；否则，转Step3；Step3

由确定xk为进基变量，根据最小比值规则确定xk的值，确定中心元素和出基变量；Step4

采用初等行变换将中心元素化为1，并将中心元素所在列化为单位列向量确定新的基本可行解X2，以及X2对应的检验数，转Step2。第36页,共52页，2024年2月25日，星期天单纯形法单纯形法的求解过程，实际上是在一系列表格上进行的。从这些表格上可以得到基本解、检验数等信息，这些表格称为单纯形表。每一个单纯形表相当于一个矩阵，每次迭代就是对矩阵进行初等行变换。例3.5

求解下面的线性规划问题第37页,共52页，2024年2月25日，星期天单纯形法解:单纯形表的主要步骤1：构造初始单纯形表；单纯形表是根据线性规划问题的基本可行解对应的典式形式得到的。现在取X1=(5,0,0,6,24)T求作为初始基本可行解，显然，模型中目标函数不是典式形式，因此需要将x4=6-x2+4x3代入目标函数Z，经整理得到Z=6+x2+2x3。第38页,共52页，2024年2月25日，星期天单纯形法构造初始单纯形表cj02-210CBXBbx1x2x3x4x50x15111000x4601-4100x52402601cj-zj01200CB表示基变量的系数，XB表示当前基变量，b表示当前基变量的取值，cj行为基变量的价值系数，为待填入的按最小比值规则计算的值。第39页,共52页，2024年2月25日，星期天单纯形法解:单纯形表的主要步骤2：迭代求新的基本可行解及其检验数；在上面的单纯形表中，x2,x3检验数大于零，不满足最优性准则，需要进行迭代。确定中心元素以及进、出基变量，将中心元素化为1，中心元素所在列化为单位向量。cj02-210CBXBbx1x2x3x4x50x151110050x4601-410-0x524026014cj-zj01200第40页,共52页，2024年2月25日，星期天单纯形法解:单纯形表的主要步骤2：迭代求新的基本可行解及其检验数；cj02-210CBXBbx1x2x3x4x50x1112/300-1/63/20x42207/3012/366/7-2x3401/3101/612cj-zj01/320-1/3第41页,共52页，2024年2月25日，星期天单纯形法解:单纯形表的主要步骤3：继续迭代；cj02-210CBXBbx1x2x3x4x52x23/23/2100-1/40x437/2-7/20015/4-2x37/2-1/20101/4cj-zj-1/2000-1/4此表格中全部检验数均小于等于零，故得到最优解X*=(0,3/2,7/2,37/2,0)T,其对应的目标函数值为29/2。最优单纯形表第42页,共52页，2024年2月25日，星期天单纯形法例3.5用单纯形法求解解:初始基本可行解为X1=(7,0,0,12,0,10)T,所给模型即为典式，可直接建立单纯形表进行计算。第43页,共52页，2024年2月25日，星期天单纯形法cj0-130-20CBXBbx1x2x3x4x5x60x1713-102070x4120-2410030x6100-4308110/3cj-zj00-130-20第44页,共52页，2024年2月25日，星期天单纯形法cj0-130-20CBXBbx1x2x3x4x5x60x11015/201/4203x330-1/211/4000x610-5/20-3/481cj-zj-901/20-3/4-20第45页,共52页，2024年2月25日，星期天单纯形法cj0-130-20CBXBbx1x2x3x4x5x6-1x245/2101/104/503x351/5013/102/500x611100-1/2101cj-zj-11-1/500-4/5-12/50由上表得知，最优解为X*=(0,4,5,0,0,11)T,最优值为11。第46页,共52页，2024年2月25日，星期天软件实现例3.6求解Max2x1+3x2St.4x1+3x2<=103x1+5x2<=12x1≥0x2≥0model:m