Chapter线性规划及单纯形法实用

会计学1Chapter线性规划及单纯形法实用22023/1/17§1线性问题的数学模型问题的提出

例1.用一块边长为a的正方形铁皮做一个容器，应如何裁剪，才能使做成容器的容积最大？ax解：利用高等数学的知识

V=(a-2x)2x

求V(x)的最大值即可。

[问题？]第1页/共74页32023/1/17线性规划的数学模型问题的提出–

例2

(生产计划安排，要求利润最大)解：设在计划期内生产产品I和产品II分别为x1和x2件(决策变量)目标是要使

z=2x1+3x2达到最大。(目标函数)限制条件是：

（约束条件）

2x1+2x2

12和

2x1

16以及

5x2

15

要求x1,x20加工设备ABC单件利润产品I2402元产品II2053元设备时限12h16h15h——第2页/共74页42023/1/17线性规划的数学模型问题的提出–

例子之三(合理下料问题)

现有一批10m长的贵重钢筋，需要截取3m和4m长的钢筋各50根，试问如何截取，才能使原料最省？问题分析：先确定截取方案建立数学规划模型问题：模型是否有别的形式？截取方案IIIIII3m钢筋2304m钢筋102废料长0m1m2m第3页/共74页52023/1/17线性规划问题数学模型的定义线性规划模型组成的三要素：决策变量目标函数约束条件定义1

在线性规划数学模型中，如果决策变量为可控的连续变量，目标函数和约束条件都是线性的，称这类模型为线性规划问题的数学模型。问题：例一中的问题是否为线性规划模型？第4页/共74页62023/1/17线性规划问题数学模型的一般形式关于幻灯片中的数学符号：小写斜体字母表示实数，如a,b,c,x,x1,y,z等小写黑体字母表示向量，如x,y,z等大写黑体字母表示矩阵，如A,B,C等线性规划(LP)数学模型的一般形式或第5页/共74页72023/1/17线性规划数学模型向量和矩阵形式(LP)向量形式(LP)矩阵形式

第6页/共74页82023/1/17线性规划问题的标准形式什么是(LP)问题的标准形式？

满足如下条件：目标函数是求极大值；约束条件全为等式；bi和xj全为非负数。第7页/共74页92023/1/17(LP)一般形式向标准形式的转化(LP)一般形式向标准形转化的情况：目标函数是求极小值；约束条件为不等式“”的情形（松弛变量，例2）；约束条件为不等式“”

的情形（剩余变量，例3）；取值无约束的变量；某个变量xj0问题：某个变量有上下界限制，比如lxju，如何处理？例3.见书P12。第8页/共74页102023/1/17线性规划问题解的若干重要概念线性规划问题的任务

从满足约束条件（2）和非负条件（3）的方程组中，找到使目标函数（1）取得最大值的解。可行解和可行域

满足约束和非负条件的解x。最优解基、基向量、基变量

设A=(aij)mn，r(A)=m，称A的一个m阶满秩子矩阵B称为(LP)问题的的一个基。基解

由基矩阵B确定的m个基变量，并上非基变量取0的解。基(本)可行解

同时是可行解的基解。可行基第9页/共74页112023/1/17利用初等变换求基可行解例4.教材14页，列出(LP)问题的全部基，基解、基可行解并指出最优解。问题:I)如何判断一个解是基可行解；

II）表1-1中为何少了两行？利用p1,p2,p4

求基解的过程第10页/共74页122023/1/17§2图解法求最优解什么时候用图解法？

(LP)模型仅含两个决策变量。

求解方法和根据：根据约束画出求解区域，一般为第一象限的凸多边形

(有界或无界)，标记出顶点坐标；求目标函数的梯度：设目标函数是z=c1x1+c2x2，则

n=gradz=(c1,c2)

为等值线c1x1+c2x2=h的法线方向，沿n的方向函数值增加的最快，沿-n方向函数值减少的最快。移动等值线c1x1+c2x2=h在区域顶点或边界达到最大最小值。

书中的方法是把目标函数z当做参数处理。第11页/共74页132023/1/17一般情况求解区域的确定约束一般都可化成ax1+bx2+c=0(a>0，b0)的形式[特殊情形？]第12页/共74页142023/1/17一个用图解法求极值的例子用图解法求如下线性规划问题的极值。最大值点x*=(1,4),Zmax=3；最小值点x*=(4,1),Zmin=3；A(2,0)B(4,1)C(1,4)D(0,2)第13页/共74页152023/1/17图解法的其他情形–无穷多最优解无穷多最优解(书，P16，见下图)

问题1：什么情况下发生？问题2：这个最优解如何表示？第14页/共74页162023/1/17图解法的其他情形–无界解(无最优解)求下面规划问题的最优解。

问题1：如果目标函数是求极大，是否有最优解？问题2：能否定量说明z是无下界的？第15页/共74页172023/1/17图解法的其他情形–无可行解求下面规划问题的最优解。第16页/共74页182023/1/17§3单纯形基本原理–预备知识凸集定义1.1：如果集合C中任意两点x(1)，x(2)，其连线上的所有点也在集合C中，即对任何x(1)C，x(2)C，0<<1，都有

x(1)+(1)x(2)C，则称C为凸集。

顶点定义1.2：如果凸集C中不存在任何两个不同的点x(1)、x(2)

，使x成为x(1)和x(2)连线上的某个点，这样的x称为C的顶点。

（问题：书上的数学描述是否妥当？）第17页/共74页192023/1/17单纯形法的基本定理定理1.1

若(LP)问题有可行解，则问题的可行域为凸集。

利用凸集的定义，结合LP的矩阵形式[P8]证明。引理1.1(LP)问题可行解x为基可行解的充要条件是x的非零分量所对应的系数列向量是线性独立的。

利用基可行解的定义证明。定理1.2(LP)问题的可行解x是可行域(凸集)顶点的充要条件是x为一个基可行解。

利用分块矩阵的形式，结合引理1.1利用反证法

(较长,最后证)。第18页/共74页202023/1/17引理1.1的证明引理1.1(LP)问题可行解x为基可行解的充要条件是x的非零分量所对应的系数列向量是线性独立的。证明：充分性设x为一可行解，不妨设其非零分量(正分量)为前k个，即x=(x1,

x2

,

,

xk,

0,,0)T，xi>0(1

ik),若x是基可行解，则必有km(为什么？)，由可行基的定义，部分向量组p1,p2,,pk必线性无关。

必要性若x为可行解(同上假设)，其对应系数列向量p1,p2,,pk线性独立(无关)，同样km(为什么？)。

(1)、若k=m,则p1,p2,,pk刚好构成一个基矩阵，而x=(x1,

x2

,

,

xk,

0,,0)T为对应基可行解。

(2)、若k<

m

，则可以利用p1,p2,,pk构造一个基，因为rank(A)=m,从pk+1,p2,,pn中必可以选出mk列，和p1,p2,,pk共同组成一个基，这样一定可以办到(为什么？)

，其对应基解恰为x。这样的x称为退化的基可行解。第19页/共74页212023/1/17单纯形法的基本定理–凸组合性质凸组合定义1.3设x(1),x(2),,

x(m)是En中的m个向量，而1,2,,

m是满足1+2++

m=1，i0的m个实数，称向量x=

1x(1)+2x(2)

++

mx(m)为x(1),x(2),,

x(m)的凸组合。 问题：凸组合和普通线性组合有什么区别？引理1.2

En中的点集为凸集的充要条件是对任何正整数m,中任意m个点x(1),x(2),,

x(m)的凸组合x都在内。

充分性：利用定义证凸集；必要性：数学归纳法+凸集定义。第20页/共74页222023/1/17单纯形法的基本定理-顶点表示定理引理1.3

设(LP)问题的可行域C有界，则任何可行解xC都可以表示成C的顶点的凸组合。

(证明略，图解示意，考虑x的三种情况：顶点、边界点和内点)第21页/共74页232023/1/17一个顶点表示的例子例设x是三角形中任意一点，x(1),x(2),x(3)是三角形的三个顶点，试将x表示为x(1),x(2)和x(3)的凸组合。解：连接x(1)和x交x(2)x(3)于x，因三角形是凸集,

x

=x(1)+(1)x(1)

x

=x(2)+(1)x(3)

(2)0<,<1

(2)代入(1)得：x

=x(1)+(1)x(2)+(1)(1)x(3)

，验证组合系数之和为1即可。第22页/共74页242023/1/17基可行解和最优解的关系定理1.3

若(LP)问题有最优解，则一定存在一个基可行解是最优解。

定理的应用：定理1.1(可行域是凸集)

定理1.2(凸集顶点对应基的可行解)

定理1.3(某个基可行解是最优解)

证明思路：设x*是最优解，全部基可行解

x(1),x(2),,

x(m)，

希望最优值在某个顶点x(k)达到，利用引理1.3建立x*和x(1),x(2),,

x(m)之间的关系，再利用最优解性质和不等式放缩证明即可。

问题：关于书上的证明?第23页/共74页252023/1/17§4单纯形法迭代求解的基本思想第24页/共74页262023/1/17迭代法求解(续1)上述操作的实质是消元法主元素的选取，进基和离基。第25页/共74页272023/1/17迭代法求解(续2)问题：那个变量离基？第26页/共74页282023/1/17迭代法求解(续3)迭代法小结：先求得一个初始基可行解，一般要获得一个单位阵基；判断获得的解是否是最优解，如判断目标函数中非基变量的系数；如果不是最优解，按照消元法进行基可行解的转换；重复和，直至求得最优解。第27页/共74页292023/1/17第1次作业总结首页写清专业+姓名+学号

（单页、草纸、背面！）作业版本拷贝！基本概念不清晰

最优解和最优值。

如作业1.2（a）中，最优解

为x(1)=(0,3,0,0,7/2,0)T,

和x(2)=(0,0,3/2,0,8,0)T,

最优值为z*=3。问题：参考图解法的(a)，利用x(1)和x(2)给出一个新最优解？第28页/共74页302023/1/17一个求解所有基解的matlab程序(作业1.2)%BFSBase’sFeasiblesolutionbyyaomingchen,2011.03.12c=[312];%目标函数系数A=[1236300;81-4020;30000-1];%约束矩阵b=[9100]';%右端项[mn]=size(A);%矩阵规模MaxNumofBase=nchoosek(n,m);%最大的基数量comb=combntns(1:n,m);%具体的列组合fori=1:MaxNumofBase%对每个可能的基

x=zeros(1,n);%解分量全赋0值

ploc=comb(i,:);%基列的位置

B=A(:,ploc);%取出A的作为基的各列

ifrank(B)>m-1%如果r(B)=3Base=[];forj=1:m%将B表示成（p1p2...pk）的形式

Base=[Base,blanks(10),'p',int2str(ploc(j))];enddisp([‘BASE=’,Base]);%显示基是哪些列构成的

x(ploc)=B\b%求x_B并放入基列位置

zvalue=c*x(1:m)'%计算最优值

endend第29页/共74页312023/1/17初始基可行解的获得设法构造一个初始单位阵基。如果约束条件都是“”形式，化标准型直接获得；如果约束条件是“=”或“”形式，采用人工变量法(稍后讲)。不妨设(LP)标准形前m列是单位阵，即典型形式(典式)。第30页/共74页322023/1/17最优解的判别-检验数最优解的判别：用非基变量表示目标函数值。第31页/共74页332023/1/17单纯形表的建立cjc1c2cmcm+1cjcnCBBbx1x2xmxm+1xjxnc1x1b11a1m+1a1ja1nc2x2b21a2m+1a2ja2ncmxmbm1amm+1amjamnj=cj-zj000B–基(变量)；CB-

基变量对应目标函数系数；b–右端项

检验数的计算：j=cj

zj=cj(c1a1j+c2a2j+…+cmamj)第32页/共74页342023/1/17用单纯形表求解的例子(书p26.例5)cj23000CBBbx1x2x3x4x50x312221000x416400100x51505001j=cjzj23000化标准型建立初始单纯形表，计算检验数；确定进基变量，x2进基

(检验数最大);确定离基变量，=min{12/2,16/0,15/5}

=3，x5离基。

由主元a32确定。第33页/共74页352023/1/17单纯形表上的迭代算法cj23000CBBbx1x2x3x4x50x312221000x416400100x51505001j=cjzj2300001001/533x22010-2/562000-3/5所有检验数非正，最优解x*=(3,3,0,4,0)T，最优值z*=15第1次迭代：对主元所在行和列进行初等变换，并计算检验数。第2次迭代：x1进基，x3离基，主元a12=2，消元并计算检验数。2x13101/20-1/50x43x2400-214/5301001/5j=cjzj00-10-1/5第34页/共74页362023/1/17单纯形算法的一般形式cjc1clcmckcjCBBbx1xlxmxkxjc1x1b11a1ka1jcixibiaikaijclxlbl1alkaljcmxmbm1amkamjj=cj-zj000kj第35页/共74页372023/1/17单纯形算法的计算步骤把(LP)化成标准形式，建立初始单纯形表；

（一般能获得一个单位阵基作为初始可行基）计算所有变量的检验数，若所有j0(1jn)，则当前解x即为最优解，迭代结束。否则转;确定k=max{j|j>0},则xk待进基；若所有aik0,则停止计算，(LP)无最优解，否则转；计算=min{bi/aik|aik>0,1im}=bl/alk,则xl离基；以alk为主元,通过高斯消元法进行基可行解的转换，求得表中一新基可行解，转步骤。

(注：若在和中出现多个k或者l,则按照自然顺序选择)第36页/共74页382023/1/17迭代一次之后的形式cjc1clcmckcjCBBbx1xlxmxkxjc1x110cixi0ckxk1cmxm10j=cj-zj000第37页/共74页392023/1/17迭代前后解,函数值,检验数等的变化第38页/共74页402023/1/17一个讲练的例子(大家参与)第39页/共74页412023/1/17最优性检验标准(※)若所有j<0(m+1jn),则x(k)为(LP)唯一的最优解。设x(k)是最优解，有某个r=0(m+1rn),且存在air>0(1im),则

(LP)有无穷多最优解。若有某个j>0(m+1jn),但是

pj=(a1j,a2j,…,amj)0,则(LP)无有限的最优解和最优值（无最优解）。采用人工变量方法时(大M法和二阶段法)，满足最优条件时人工变量不为零，则原LP问题无可行解。第40页/共74页422023/1/17§5人工变量法–问题的提出如果原（LP）问题的约束全是“”号的形式，可以引入m个松弛变量xn+m，使得后m列自然形成初始单位阵基，再用单纯形法进行迭代求解。如果原（LP）问题的约束是“”和“”号，或者三种符号（、、）都有的的混合形式，且化成标准形式后约束矩阵不具备初始单位阵基，这时候怎么办？解决办法：自然的想法就是在标准形约束矩阵中，人工加入若干单位向量，(和已有的)形成初始单位阵基。化标准型第41页/共74页432023/1/17人工变量法–大M法例6求解如下线性规划问题(书P29)标准形中只有p4是单位向量？强行加入两列p6和p7

，或者说在第2、3个约束上分别加入人工变量，即x6和x7。人工变量的系数问题？目标函数中人工变量系数都取M(M>0充分大)。第42页/共74页442023/1/17用大M法求解例6cj-30100-M-MCBBbx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx790310001cjzj-2M-34M10-M00检验数比较：

形式aM+b1.a>0,aM+b>02.a<0,aM+b<03.若0<a1<a2

则a1M+b1<a2M+b2

此时可省略常数b1-21-10-110cjzj0x20x4-M

x7330211-10660403-316M04M03M-4M0第43页/共74页452023/1/17用大M法求解例6（续）cj-30100-M-MCBBbx1x2x3x4x5x6x70x400001-1/21/2-1/20x23011/30001/3-3x11102/301/2-1/21/6cjzj00303/2-M-M0x400001-1/21/2-1/20x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4cjzj-9/2000-3/4-M-M

x*=(0,5/2,3/2,0,0,0,0)T,z*=3/2.第44页/共74页462023/1/17大M法的理论分析对标准形式的(LP)问题，设约束矩阵无单位阵基，令

xk=(xn+1,xn+2,…,xn+k)T,(k

m),则大M法是求解：第45页/共74页472023/1/17大M法的理论分析第46页/共74页482023/1/17一个无可行解的例子(P18,P42)cj2-100-MCBBbx1x2x3x4x50x3111100-Mx54-130-11cjzj-M3M0-M0单纯形表的迭代过程：-1x2111100-Mx51-40-3-11cjzj-4M0-3M-M0

人工变量x5=10,由定理5.1,原问题无可行解。第47页/共74页492023/1/17人工变量法–两阶段方法大M方法的缺点：带有非数值符号M，不方便计算。什么是两阶段方法？

和大M方法一样，同样引入人工变量xT=(xn+1,xn+2,…,xn+k)T,(k

m)，并设e=(1,1,…,1)

,构造一新的线性规划问题（TP，Two-PhaseProgramming）两阶段方法的计算步骤：引入人工变量并构造新的(TP)问题：目标函数中原决策变量系数全取0，人工变量系数皆取1，且目标函数求极小)；

第一阶段，求(TP)问题的最优解(一般xT=0),同时得到原(LP)问题的基可行解(未必最优)；

第二阶段，删除(TP)最终单纯表中人工变量列，利用第一阶段的得到的基可行解，以及原(LP)的目标函数继续迭代求解。第48页/共74页502023/1/17两阶段方法求解的例子(习题1.1a)约束化等式构造TP问题第49页/共74页512023/1/17第一阶段:求解TP问题cj000011CBBbx1x2x3x4x5x61x5646-10101x64420-101cjzj-8-811001x5204-111-10x1111/20-1/401/4cjzj0-41-1020x21/201-1/41/41/4-1/40x13/4101/8-3/8-1/83/8cjzj000011x*=(3/4,1/2,0,0,0,0)T2300

第50页/共74页522023/1/17第二阶段：求原LP问题因为c4z4=3/2>0

但p4=(-1/2,-3)<0

故原LP无最优解。

本幻灯片42页。cj2300CBBbx1x2x3x43x21/201-1/41/42x13/4101/8-3/8cjzj001/203x22210-1/20x36801-3cjzj-4003/2第51页/共74页532023/1/17原问题如果是求极小(无穷多最优解)因为求极小，所有检验数非负停止迭代；继续迭代可得到另外一个最优解。cj2300CBBbx1x2x3x43x21/201-1/41/42x13/4101/8-3/8cjzj001/200x4204-112x13/213/2-1/40cjzj001/20第52页/共74页542023/1/17两阶段方法的理论分析（情况1）首先若(LP)有可行解，(TP)问题一定有最优解？ 这是因为e=(1,...,1)T,对任意xT0,y=exT0有下界。 如xT=0

就是(TP)的一个最优解，但这个最优解未必能达到。第53页/共74页552023/1/17两阶段方法的理论分析（情况2）第54页/共74页562023/1/17情况2的例子cj000011CBBbx1x2x3x4x5x60x42-1211001x54-44-10101x6010-1001cjzj3-42000第一阶段的求解过程（注意求极小）：0x21-1/211/21/2001x50-20-3-2101x6010-1001cjzj104200第55页/共74页572023/1/17情况2的例子(续1)cj-110000CBBbx1x2x3x4x5x61x21-1/211/21/2000x50-20-3-2101x6010-1001cjzj104200第一阶段的结果没有获得单位阵基，开始第二阶段：1x210x50-1x10cjzj00-5-2120101/201/2-1x1

00-1-1/201/2

x4

005/21-1/2-101-5/401/4110-1001001/40--第56页/共74页582023/1/17情况2的例子(续2)cj-110000CBBbx1x2x3x4x5x61x2101-5/401/410x40005/21-1/2-1-1x1010-1001cjzj001/40--抛弃人工变量，继续迭代：1x210101/20x300012/5-1x101002/5cjzj000-1/10x*=(0,1,0)T,z*=1.第57页/共74页592023/1/17两阶段方法的理论分析（情况3）第58页/共74页602023/1/17一个无可行解的例子(本幻灯片P49,和大M法关系)cj00001CBBbx1x2x3x4x50x31111001x54-130-11cjzj1-3010第一阶段的迭代过程：0x21111001x51-40-3-11cjzj40310

人工变量x5=10,由情况3,原问题无可行解。第59页/共74页612023/1/17§6单纯形法的矩阵形式(※)例6.1

单纯形表迭代变化的实质（本幻灯片P44-46）cj-30100-M-MCBBbx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx790310001cjzj-2M-34M10-M000x400001-1/21/2-1/20x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4cjzj-9/2000-3/4-M-M问题：B1对应最终单纯形表那些列，原来那些列是什么？第60页/共74页622023/1/17矩阵形式的单纯形表目标函数值：

z=cBB1b非基变量检验数：

N=cN

cBB1N基变量检验数：

B=cB

cB=0记号：y=cBB1称为单纯形乘子。ccBcNBxBxNbcBxB检验数I=B1BB1NB1bB=0N=cNcBB1NcBB1b第61页/共74页632023/1/17例10.确定B1,单纯形乘子y和计算检验数（用矩阵形式）确定B=?

B1=?求B1b=?计算迭代后的p1和p3确定单纯形乘子y=cBB1计算x3和x5的检验数计算目标函数值cj203000CBBbx1x4x2x3x4x50x3122021000x4164100100x515005001j=cjzj2030002x131001/20-1/50x44010-214/53x23001001/5j=cjzj000-10-1/5第62页/共74页642023/1/17例11.确定单纯形表中的未知量（大家参与）如下表，给出了某线性规划问题计算过程中的一个单纯形表，目标函数为maxz=28x4+x5+2x6,约束条件全为“”，表中x1,x2,x3为松弛变量，表中解的目标函数值为

z=14。

（1）.求

a~g

的值；

（2）.求原约束矩阵的第五列p5。CBBbx1x2x3x4x5x62x6a30-14/30110x256d205/2028x400ef100cjzjbc00-1g第63页/共74页652023/1/17修正单纯形算法为什么要引入修正单纯形算法？单纯形表每次迭代过程有m1列未发生变化[参见下2页]；单纯形表操作不适合大规模的LP问题计算。迭代前后两个表中的基B和新基B的关系问题1.迭代前的基B是什么，B1是什么？问题2.迭代后的新基B是什么？B1如何计算？两个基的逆之间的关系：(Bnew)1=(Blk)

1=ElkI=ElkB

1推导两个逆矩阵之间的关系式用原基的逆表示新基表中其他量皆可以用B

1表示第64页/共74页662023/1/17迭代之前cjc1clcmckcjCBBbx1xlxmxkxjc1x1b11a1ka1jcixibiaikaijclxlbl1alkaljcmxmbm1amkamjj=cj-zj000kj第65页/共74页672023/1/17迭代之后cjc1clcmckcjCBBbx1xlxmxkxjc1x110cixi0ckxk1cmxm10j=cj-zj000第66页/共74页682023/1/17修正单纯形算法的计算步骤对标准形式的LP问题，写出矩阵A,b

和c;

确定初始单位阵基B(=I),记录基向量下标集合I、非基变量集合J和cB；计算xB=B1b.计算单纯形乘子y=cBB1,并计算检验数N=cN

yN

，若所有j0(m+1jn)，则当前解x即为最优解，迭代结束。否则转;计算k=max{j|j>0},确定k,并计算pk=B1pk；若所有aik0,则停止计算，(LP)无最优解，否则转；计算=min{bi/aik|aik>0,1im}=bl/alk,

修改集合I,J和cB；形成Elk,并计算B1=ElkB

1,xB=Elk