《运筹学基础及应用》

运筹学

1精选ppt第一章线性规划及单纯形法

(LinearProgramming,LP)线性规划模型图解法单纯形法原理单纯形法计算步骤单纯形法的进一步讨论数据包络分析2精选ppt§1一般线性规划问题的数学模型

1.1引例例1、生产计划问题

Ⅰ

Ⅱ能力设备A2212设备B4

016设备C0515利润23Ⅰ，Ⅱ各生产多少,可获最大利润?3精选ppt

2x1+2x2

12

4x1

16

5x2

15

x1，x2

0注意模型特点

maxZ=2x1+3x2解:设产品Ⅰ,Ⅱ产量分别为变量x1，x22023/4/24精选ppt线性规划模型特点决策变量：向量X=(x1…xn)T决策人要考虑和控制的因素，非负约束条件：关于X的线性等式或不等式目标函数：Z=ƒ(x1

…xn)为关于X的线性函数，求Z极大或极小2023/4/25精选ppt1.2线性规划问题的数学模型三个组成要素：1.决策变量:是决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。2.目标函数:指问题要达到的目的要求，表示为决策变量的函数。3.约束条件:指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。2023/4/26精选ppt一般线性规划问题的数学模型：目标函数：约束条件：2023/4/27精选ppt简写形式：2023/4/28精选ppt矩阵形式表示为：其中：2023/4/29精选ppt1.3线性规划问题的标准形式标准形式：标准形式特点：4.决策变量取值非负。1.目标函数为求极大值；2.约束条件全为等式；3.约束条件右端常数项全为非负；2023/4/210精选ppt一般线性规划问题如何化为标准型：1.目标函数求极小值：令：，即化为：2023/4/211精选ppt2.约束条件为不等式：（1）当约束条件为“≤”时如：可令：，显然（2）当约束条件为“≥”时如：可令：，显然称为松弛变量。称为剩余变量。2023/4/212精选ppt松弛变量和剩余变量统称为松弛变量（3）目标函数中松弛变量的系数由于松弛变量和剩余变量分别表示未被充分利用的资源以及超用的资源，都没有转化为价值和利润，因此在目标函数中系数为零。2023/4/213精选ppt3.取值无约束的变量如果变量x代表某产品当年计划数与上一年计划数之差，显然x的取值可能是正也可能是负，这时可令：其中：令4.变量xj≤0，显然2023/4/214精选ppt例.

将下述线性规划模型化为标准型2023/4/215精选ppt解：令得标准形式为：2023/4/216精选ppt求解线性规划问题：就是从满足约束方程组和约束不等式的决策变量取值中，找出使得目标函数达到最大的值。1.4线性规划问题的解的概念2023/4/217精选ppt可行解：满足约束条件的解称为可行解，可行解的集合称为可行域。最优解：使目标函数达到最大值的可行解。基：约束方程组的一个满秩子矩阵称为规划问题的一个基，基中的每一个列向量称为基向量，与基向量对应的变量称为基变量，其他变量称为非基变量。基解：在约束方程组中，令所有非基变量为0，可以解出基变量的唯一解，这组解与非基变量的0共同构成基解。基可行解：满足变量非负的基解称为基可行解可行基：对应于基可行解的基称为可行基2023/4/218精选ppt例：考察下述线性规划问题：2023/4/219精选ppt（1）可行解，如或满足约束条件，所以是可行解。（2）基系数矩阵A：其中或都构成基。而不构成基。2023/4/220精选ppt（3）基向量、基变量是对应于基的三个基向量，而是对应于这三个基向量的基变量。（4）基解、基可行解、可行基是对应于基的一个基解、基可行解。是对应于基的一个基解、基可行解。均是可行基。练习：P14，例42023/4/221精选ppt

为了便于建立n维空间中线性规划问题的概念及便于理解求解一般线性规划问题的单纯形法的思路，先介绍图解法。求解下述线性规划问题：§2线性规划问题的图解法2023/4/222精选ppt画出线性规划问题的可行域：目标函数等值线2023/4/223精选ppt1、可行域：约束条件所围成的区域。2、基可行解：对应可行域的顶点。3、目标函数等值线：4、目标函数最优值:最大截距所对应的。

目标函数等值线有无数条，且平行。（观察规律)2023/4/224精选ppt解的几种情况：(2)无穷多最优解(1)唯一最优解若目标函数改为：约束条件不变，则:目标函数等值线此时，线段上所有点都是最优值点。2023/4/225精选ppt解的几种情况：(4)无界解(3)无可行解：当可行域为空集时，无可行解。若目标函数不变，将约束条件1和3去掉，则可行域及解的情况见下图。目标函数等值线此时，目标函数等值线可以向上无穷远处平移，Z值无界。2023/4/226精选ppt几点说明：1、图解法只能用来求解含有两个决策变量的线性规划问题。2、若最优解存在，则必在可行域的某个顶点处取得。3、线性规划问题的解可能是：唯一最优解、无穷多最优解、无最优解、无界解。2023/4/227精选ppt§3．单纯形法原理凸集：如果集合C中任意两个点，其连线上的所有点也都是集合C中的点。上图中（1）（2）是凸集，（3）（4）不是凸集顶点：如果对于凸集C中的点X，不存在C中的任意其它两个不同的点，使得X在它们的连线上，这时称X为凸集的顶点。3.1预备知识2023/4/228精选ppt3.2线性规划问题基本定理定理1:若线性规划问题存在可行解，则问题的可行域是凸集。证明:设是线性规划的任意两个可行解，则于是对于任意的，设，则所以也是问题的可行解，即可行域是凸集。

2023/4/229精选ppt引理:

线性规划问题的可行解X为基可行解的充要条件是X的正分量所对应的系数列向量线性无关。证明:设（1）必要性显然。（2）设A的秩为m。可行解X的前k个分量为正，且它们对应的系数列向量线性无关，则。当时，恰好构成一组基，而就是这组基对应的基可行解。

当时，在基础上从其余列向量中可以找出个线性无关的向量，恰好构成一组基，而X就是这组基对应的基可行解。2023/4/230精选ppt定理2:

线性规划问题的基可行解X对应线性规划问题可行域（凸集）的顶点。证明:问题即是要证明:X是基可行解X是可行域顶点，也即要证明其逆否命题：X不是基可行解X不是可行域顶点。（1）X不是基可行解X不是可行域顶点。假设X是可行解，但不是基可行解，

X的前k个分量为正,其余分量为0，则有又X不是基可行解，所以由引理知，正分量对应的列向量线性相关。即存在一组不全为零的数，使得2023/4/231精选ppt用非零常数乘以上式得：（1）+（3）得：（1）-（3）得：令选择合适的，使得所有的于是均是可行解，并且，所以X不是可行域顶点。2023/4/232精选ppt（2）X不是可行域顶点X不是基可行解。设不是可行域的顶点，因而可以找到可行域内另两个不同的点，使得，用分量表示即为：

易知，当时，必有所以所以于是（1）-（2）得而不全为零，于是知线性相关，X不是基可行解。2023/4/233精选ppt定理3:

若线性规划问题有最优解，一定存在一个基可行解是最优解。引理：

有界

凸集中的任何一点均可表示成顶点的凸组合。证明:假设是可行域顶点，不是可行域顶点，且目标函数在处达到最优，即。由引理知：可表示为的凸组合，即因此假设是所有中最大者，则2023/4/234精选ppt而是目标函数的最大值，所以也是最大值，也即，目标函数在可行域的某个顶点达到了最优。从上述三个定理可以看出，要求线性规划问题的最优解，只要比较可行域（凸集）各个顶点对应的目标函数值即可，最大的就是我们所要求的最优解。2023/4/235精选ppt

单纯形方法的基本思路自从1947年丹齐格（G.BDantzig）提出单纯形方法以来，迄今为止仍是求解线性规划问题的最有效的方法。在介绍这种方法之前，先通过一个例子介绍单纯形方法的基本思想。例

用消元法解线性规划问题.(1.3.1)解求解线性规划问题（1.2.4），实际上是求线性方程组精选ppt精选ppt(1.3.2)精选ppt安徽省十一五规划教材(1.3.3)精选ppt安徽省十一五规划教材(1.3.4)精选ppt安徽省十一五规划教材精选ppt2468x1246OABCD2x1+3x2=6x2x1=4x2=3x1+2x2=8图1.2.1精选ppt3.3确定初始基可行解寻求最优解的思路：线性规划问题的最优解一定会在基可行解中取得，我们先找到一个初始基可行解。然后设法转换到另一个基可行解，并使得目标函数值不断增大，直到找到最优解为止。设给定线性规划问题：2023/4/243精选ppt因此约束方程组的系数矩阵为：添加松弛变量得其标准形为：2023/4/244精选ppt由于该矩阵含有一个单位子矩阵，因此，这个单位阵就是一组基，就可以求出一个基可行解：说明：如果约束条件不全是形式，如含所有形式，则无法找到一个单位阵做为一组基，这时需要添加人工变量。后面的内容介绍。称其为初始基可行解。2023/4/245精选ppt3.4从初始基可行解转换为另一个基可行解

思路：对初始基可行解的系数矩阵进行初等行变换，构造出一个新的单位矩阵，其各列所对应的变量即为一组新的基变量，求出其数值，就是一个新的基可行解。

设有初始基可行解，并可设前m个分量非零，即，于是2023/4/246精选ppt

由构造初始可行基的方法知前m个基向量恰好是一个单位阵，所以约束方程组的增广矩阵为由于任意系数列向量均可由基向量组线性表示，则非基向量中的用基向量组线性表示为：2023/4/247精选ppt设有，则（1）+（2）得：由此式可知，我们找到了满足约束方程组的另一个解，要使其成为可行解，只要对所有i=1,2,…m，下式成立要使其成为基可行解，上面m个式中至少有一个取零。（基可行解中非零分量的个数不超过m个。）（与比较）2023/4/248精选ppt只要取于是前m个分量中的第l个变为零，其余非负，第j个分量为正，于是非零分量的个数，并可证得线性无关，所以是新的基可行解。2023/4/249精选ppt3.4最优性检验和解的判别设有基可行解比较两者对应的目标函数值，哪一个更优？2023/4/250精选ppt2）若对所有的，则，

就是最优解。是判断是否达到最优解的标准，称为检验数。1）当时，，目标函数值得到了改进，

不是最优解，需要继续迭代。易知2023/4/251精选ppt当所有时，现有顶点对应的基可行解即为最优解。当所有时，又对某个非基变量有则该线性规划问题有无穷多最优解。3.如果存在某个，又向量的所有分量，对任意，恒有，则存在无界解。结论2023/4/252精选ppt§4单纯形法的计算步骤

Max(min)Z=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2………am1x1+am2x2+…+amnxn=bmxj0(j=1,…,n)设有线性规划问题：2023/4/253精选ppt(1)找到初始可行基，建立初始单纯形表.(4)重复二、三两步，直至找到最优解。§4单纯形法的计算步骤

(2)进行最优性检验。计算检验数，若所有≤0

则得最优解，结束.否则转下步.若某≥0而≤0，则最优解无界，结束.否则转下步.(3)从一个可行解转换到另一个目标函数值更大的基可行解。由最大增加原则确定进基变量；由最小比值原则选择出基变量；以为主元素进行换基迭代。2023/4/254精选ppt……(1)找到初始可行基，建立初始单纯形表.00…………………是初始基。2023/4/255精选ppt(2)进行最优性检验计算检验数，若所有≤0

则得最优解，结束.否则转下步.若某≥0而≤0，则最优解无界，结束.否则转下步.检验数的计算方法：基变量的检验数一定为0。判断是否达到最优时，只要考虑非基变量检验数。2023/4/256精选ppt(3)从一个可行解转换到另一个目标函数值更大的基可行解。由最小比值原则选择出基变量；进基变量由最大增加原则确定进基变量：

当某些非基变量的检验数时，为使目标函数值增加地更快，一般选择正检验数中最大者对应的非基变量进基

，成为新的基变量。

为确保新的基可行解的非零分量非负，按下述规则求得最小比值，其所对应的原基变量中的出基。于是，新的一组基是：2023/4/257精选ppt以为主元素进行换基迭代：即利用初等行变换将进基变量

所在的系数列变为单位列向量，而变为1。这样原来基矩阵中的就不再是单位向量，取而代之的是，这样就找到了一组新的基。(4)重复二、三两步，直至找到最优解。说明：若目标函数是求最小，可以不必将其转变为求最大，但在使用单纯形法求解时，确定进基变量，应找负检验数中最小者，并应以检验数全部为正作为判别最优的条件。2023/4/258精选ppt

maxZ=3x1+5x2+0x3+0x4+0x5x1+x3=82x2+x4=123x1+4x2+x5=36x1

，x2，x3

，x4，x5

0解将模型标准化例maxZ=3x1+5x2x1

82x2

123x1+4x236

x1

，x2

02023/4/259精选pptCj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9作出单纯形表，进行迭代检验数最大比值最小2023/4/260精选ppt检验数j81010060101/2012300-21x3x2x505030300-5/208-4Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=92023/4/261精选pptCj比值CBXBb检验数jx1x2x3x4x53500081010060101/2012300-21x3x2x505030300-5/208-4检验数j40012/3-1/360101/204100-2/31/3x3x2x105342000-1/2-1最优解:X*=(4,6,4,0,0)T，Z*=422023/4/262精选ppt特殊情况：（1）出现两个或两个以上相同的最大，此时可任选一个所对应的变量作为进基变量。

（2）利用规则决定出基变量时，出现两个或两个以上的最小比值，则迭代后，会出现一个或几个基变量等于零的情况，我们称此为退化现象。进而可能会出现迭代过程的循环，致使永远达不到最优解。出现退化现象时，可考虑采用“勃兰特”规则决定进基变量和出基变量的选择。2023/4/263精选ppt单纯形法计算中用规划确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现了退化解，当出现退化时，进行多次迭代，而基又返回到最初的情形

，即出现计算过程的循环，使永远达不到最优解。为解决这个问题我们介绍勃兰特规则：

（1）当存在两个或两个以上最大检验数时，选取中下标最小的非基变量为换入变量；

（2）当按规则计算时，存在两个或两个以上最小比值时，选取下标最小的基变量为换出变量。精选ppt5.1人工变量

用单纯形法解题时，需要有一个单位阵作为初始基。当约束条件都是“≤”时，加入松弛变量就形成了初始基。但实际存在“≥”或“＝”型的约束，没有现成的单位矩阵。采用人造基的办法：添加人工变量，构造单位矩阵§5单纯形法的进一步讨论

2023/4/265精选ppt

人工单位矩阵的构造方法在“

”的不等式约束中减去一个剩余变量后可变为等式约束，但此剩余变量的系数是（-1），所以再加入一个人工变量，其系数是（+1），因而在系数矩阵中可得到一个相应的单位向量，以便构成初始单位阵，即初始基矩阵。在原本就是“

=”的约束中可直接添加一个人工变量，以便得到初始基矩阵。注意：人工变量是在等式中人为加进的，只有它等于0时，约束条件才是它本来的意义。求解带人工变量的线性规划有两种方法：☆大M法☆两阶段法2023/4/266精选ppt5.2大M法△没有单位矩阵，不符合构造初始基的条件，需加入人工变量。△人工变量最终必须等于0才能保持原问题性质不变。为保证人工变量为0，在目标函数中令其系数为（-M）。（求最小值问题中，人工变量系数取M）△M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。△如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。2023/4/267精选ppt例解线性规划解化为标准型此时无单位矩阵作为初始基。2023/4/268精选ppt添加人工变量，构造初始基：（求最小值问题中，人工变量系数取M）2023/4/269精选ppt-30100-M-Mx1x2x3x4x5x6x71111000-21-10-1100310001初始单纯形表：CCBXBb0x44-Mx61-Mx79-3-2M4M10-M0041330211-10-21-10-11060403-311-10x430x21-Mx76-3+6M01+4M03M-3M02023/4/270精选ppt-30100-M-Mx1x2x3x4x5x6x7CCBXBb00303/2-M-3/2-M+1/2-33/20001-1/21/2-1/2011/30001/3102/301/2-1/21/60x400x23-3x11-3/2000-3/4-M+3/4-M-1/40x400x25/21x33/20001-1/21/2-1/2-1/2100-1/41/41/43/20103/4-3/41/42023/4/271精选ppt此时人工变量全部出基，并已达最优条件。最优解为，最优值为注意：计算机上使用大M法时，需要用机器最大字长的数字代替M，但当某些系数与之较接近时，还是可能会出错。另外一种求解带人工变量的线性规划问题的方法不会出现这种问题-------两阶段法。2023/4/272精选pptmaxZ=

3x1-x2-2x33x1+2x2-3x3=6x1-2x2+x3=4x1,x2,x3≥0S.t.例解线性规划

maxZ=

3x1-x2-2x3-Mx4-Mx53x1+2x2-3x3+x4

=6

x1-2x2+x3+x5=4x1,x2,x3,x4,x5≥0解按大M法构造人造基，引入人工变量x4,x5的辅助问题如下：2023/4/273精选ppt作出单纯形表，进行迭代Cj比值CBXBb检验数jx1x2x3x4x53-1-2-M-M632-31041-21013+4M-1-2-2M00x4x5-M-M24检验数j212/3-11/3020-8/32-1/310-3-8M/31+2M-1-4M/30x1x53-M2023/4/274精选ppt检验数j212/3-11/3020-8/32-1/310-3-8M/31+2M-1-4M/30x1x53-M-1检验数j31-2/301/61/210-4/31-1/61/20-5/30-M-5/6-M-1/2x1x33-2最优解:X*=(3,0,1)T，Z*=72023/4/275精选ppt5.3两阶段法

第一阶段：构造目标函数只含人工变量的线性规划问题，求解后判断原线性规划问题是否有基本可行解，若有，则进行第二阶段；第二阶段：将第一阶段的最终单纯形表所对应的解，去掉人工变量，作为第二阶段的初始单纯形表的初始基可行解，进行单纯形法的迭代。2023/4/276精选ppt解（1）化标准型、并添加人工变量得：

Minf=2x1+3x2（此处未将目标变为MAX）s.t.x1+x2–x3+x6=350x1-x4+x7=1252x1+x2+x5=600x1,x2,x3,x4,x5,,x6,x7≥0例：目标函数：Minf=2x1+3x2

约束条件：s.t.x1+x2≥350x1≥

1252x1+x2≤

600x1,x2≥0

2023/4/277精选ppt（2）构造第一阶段问题：

Minz=x6+x7(Maxz=-x6-x7)s.t.x1+x2–x3+x6=350x1-x4+x7=1252x1+x2+x5=600x1,x2,x3,x4,x5,,x6,x7≥0

说明：原问题目标函数无论是求MAX还是求MIN，构造的第一阶段问题目标函数都是求最小MIN。2023/4/278精选ppt求解第一阶段问题：2023/4/279精选ppt此时所得可行解目标函数值为0，故原规划问题有基可行解。转入第二步。2023/4/280精选ppt（3）去掉人工变量，得到第二阶段的单纯形表，在此基础上继续求解。最优解为：2023/4/281精选ppt5.4关于解的不同情况的判别1、无穷多最优解例：解：将问题化为标准型：2023/4/282精选ppt2023/4/283精选ppt从上表中可知，已达最优解，为，而，若将选为进基变量迭代后，可得另一最优解。上述两最优解分别对应两个顶点，而两点连线上的点均是最优解，故有无穷多最优解。判别无穷多最优解的方法：单纯形表的检验数行已达最有性条件（全部小于或等于零），且有一个非基变量的检验数为零，此时有无穷多最优解。2023/4/284精选ppt

2、无可行解

例用单纯形表求解下列线性规划问题解：化为标准型：2023/4/285精选ppt基变量CB2030000-Mbx1x2s1s2s3a1s1s2a100-M31010001001001100-11150304015—40cj-zj20+M30+M00-M0-40M单纯形表求解线性规划问题2023/4/286精选ppt1x2s2a1300-M3/1011/100001001007/100-1/100-111530255030250/7cj-zj11+7/10M0-3-M/100-M02x2x1a13020-M011/10-3/100010010000-1/10-7/10-116304cj-zj00-3-M/10-11-7M/10-M0迭代次数基变量CBx1x2s1s2s3a1b比值2030000-M单纯形法的最终表里有人工变量大于零，则此线性规划无可行解。2023/4/287精选ppt

3、无界解例用单纯形表求解下面线性规划问题。解2023/4/288精选ppt

迭代次数基变量CBx1x2s1s2b比值11000s1s2001-110-3201161—cj-zj110001x1s2101-1100-13119cj-zj02-101此时的检验数仍为正，但系数列全为负，此时可判断这个线性规划问题是无界的，即目标函数值可以取得无限大。2023/4/289精选pp