第1章-线性规划及单纯形法

「线性规划」带来巨额财富

与其他传统数学学门相比较,线性规划算是非常「年轻」却非常「实用」的一门应用数学。根据对二十世纪八十年代的一项调查,在美国「财富」杂志(Fortune)名列前五百名的大公司中,百分八十五均曾应用线性规划的方法来协助公司的营运。由此可见线性规划应用面的宽广与普及。第1章线性规划及单纯形法§1一般线性规划问题的数学模型§2图解法§3单纯形法原理§4单纯形法的计算步骤§5单纯形法的进一步讨论§6数据包络分析主要内容§1

一般线性规划问题的数学模型问题的提出线性规划问题的数学模型线性规划问题的标准形式线性规划问题的解常山机器厂生产I、II两种产品，这两种产品都要分别在A、B、C三种不同设备上加工。生产三种产品，已知的条件如下表所示，问该企业应安排生产两种产品各多少件，使总的利润收入为最大。生产每件产品占用设备时间(h)产品I产品II计划期内用于生产的能力设备A2212设备B4016设备C0515单位产品的利润（元）23例1.1生产计划问题1-1问题的提出问题分析占用设备时间(h)产品I产品II可用的能力设备A2212设备B4016设备C0515利润（元）23可控因素(所求变量):设在计划期内生产I、II两种产品的数量分别为目标：达到最大.使得总利润最大，即利润函数：受制条件：计划期内设备的使用量不超过可用量：设备B：设备C：设备A：模型s.t.

1-2线性规划问题的数学模型(1)规划问题的数学模型的3个组成要素：决策变量、目标函数、约束条件(2)线性规划问题的数学模型：决策变量为可控的连续变量、目标函数和约束条件都是线性目标函数约束条件(3)一般线性规划问题的数学模型的表示形式：以上模型的简写形式为待定的决策变量

价值系数矩阵

为系数矩阵(或约束矩阵)。向量表示形式其中矩阵表示形式价值向量右端向量(2)化为标准形式的方法1-3线性规划问题的标准形式取极大bi≥0,等式约束非负约束(1)标准形式①②松弛变量③剩余变量说明：松弛变量和剩余变量在实际问题中分别表示未被利用的资源和超用的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。

例1.2把问题转化为标准形式1-4线性规划问题的解线性规划问题满足约束条件(2)、(3)的解可行解(或可行点)可行域全部可行解的集合最优解使目标函数(1)达到最大值的可行解最优解集合最优值最优解的全体最优解的目标函数值基设Am×n为约束方程组(2)的系数矩阵(设n＞m),R(A)=mB是矩阵A的m×m阶的满秩子矩阵，基向量基变量非基变量基解不失一般性，设基B的每一个列向量Pj

(j=1,…,m)与基向量Pj

对应的变量xj

线性规划中除基变量以外的其他变量

在约束方程组(2)中,令非基变量xm+1=…=xn=0,可解出m个基变量的惟一解XB=(x1,…,xm),X=(x1,…,xm,0,…0)T,基解总数基可行解满足变量非负约束条件(3)的基解可行基对应于基可行解的基

例1.3

列出下述线性规划问题的全部基、基解、基可行解、最优解解：系数矩阵R(A)=2基基解是基可行解？目标函数值x1x2x3x4-45.500×√√√×√×√2/5011/50-1/30011/601/2200-1/2020011P1P2P1P3P1P4P2P3P2P4P3P443/555§2

图解法优点：直观性强、计算方便缺点：只适用问题中有两个变量的情况步骤：建立坐标系，将约束条件在图上表示；确立满足约束条件的范围；绘制出目标函数的图形；确定最优解s.t.

例2.1

用图解法解线性规划x1x2oB(0,6)A(6,0)2x1+2x2=125x2=154x1=16z=9z

=15z

=12Q1Q2Q3Q4唯一最优解线性规划问题解的情况：无可行解(可行域是空集)无界解或无最优解(可行域无界)最优解存在且唯一，则一定在顶点上达到最优解存在且不唯一(无穷多最优解)，一定存在顶点是最优解(1)无可行解s.t.

x1x2o2x1+2x2=12x1+2x2=14(2)无界解s.t.

(3)无穷多最优解x1x2o4x1=16s.t.

x2oQ1Q2Q3Q4x1图解法的启示(1)求解线性规划问题时，解的情况有：惟一最优解、无穷多最优解、无界解、无可行解；(2)若线性规划问题的可行域存在，则可行域是一个凸集；(3)若线性规划问题的最优解存在，则最优解或最优解之一(如果有无穷多的话)一定能够在可行域的某个顶点找到；(4)解题思路：先找出凸集的任一顶点，计算在顶点处的目标函数值，比较周围相邻顶点的目标函数值是否比这个值更优，若为否，则该顶点就是最优解的点或最优解的点之一，否则转到比这个点的目标函数值更优的另一顶点重复上述过程，一直到找出使目标函数值达到最优的顶点为止。内容小结基本概念线性规划、可行解、可行域、最优解、最优值、基基向量、(非)基变量、基解、可行基基本计算把问题转化为标准形式用图解法解线性规划§3单纯形法原理预备知识：凸集和顶点几个基本定理的证明确定初始基可行解从初始基可行解转化为另一基可行解最优性检验和判别3-1预备知识：凸集和顶点凸集如果集合C中任意两个点X1、X2，其连线上的所有点也都是集合C中的点，即对任何有顶点如果集合C中不存在任何两个不同的点X1、X2，使X成为这两个点连线上的一个点，或对任何不存在3-2几个基本定理的证明定理1

若线性规划问题存在可行解，则问题的可行域是凸集。证明：设C表示线性规划问题的可行域则有令即则有显然证毕引理

线性规划问题的可行解X=(x1,…,xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。证明：必要性，由基可行解的定义显然成立。充分性。不失一般性不妨,线性独立的，若当时，恰好构成一个基，从而为相应的基可行解。当时,而R(A)=m,则必有则一定可以从其余列向量中找出m-k个与构成一个基，其对应的解恰好为X.若X为基解，如何判定是基可行解？若X为可行解，如何判定是基可行解？定理2线性规划问题的基可行解对应线性规划问题可行域的顶点。分析：X是可行域的顶点X是基可行解X不是可行域的顶点X不是基可行解定理2线性规划问题的基可行解对应线性规划问题可行域的顶点。X不是可行域的顶点(1)X不是基可行解证明：不失一般性,不妨设X的前m个分量为正，由X是可行解，得使得即存在一组不全为零的数线性相关，由引理知得得得令选取适当的值，使则又即X不是可行域的顶点。从而不是可行域的顶点有即因固有当xi=0时，必有yi=zi=0得(2)X不是可行域的顶点X不是基可行解不失一般性,不妨设因有因线性相关故不全为零证毕若线性规划问题有最优解,一定存在一个基可行解是最优解。定理3证明：设是最优解是目标函数的最大值。若X0不是基可行解，则X0不是可行域的顶点，一定能在可行域内找到通过的X0的直线上的另外两个点而有则由此从而若仍不是基可行解，按上面的方法继续做下去,最后一定可以找到一个基可行解,其目标函数值等于CX0.3-3确定初始基可行解由前面的定理可知：如果一个LP问题有最优解，则一定在某个基可行解处达到。单纯形法的基本思想就是先找到一个初始基可行解，判断它是否最优，如若不是，就找一个更好的基本可行解，再进行判断。如此迭代下去，直至找到最优基本可行解，或者判定该问题无界！！！一种易求初始基可行解的情形系数矩阵化为标准形式取单位矩阵作为基，则就是一个基可行解3-4从初始基可行解转化为另一基可行解设初始基可行解为,其中非零坐标有m个.不失一般性,假定前m个坐标为非零，因固有方程组(*)的增广矩阵可写为得由上式知，因是一个基，则满足或要使X1是一个基可行解，而θ>0,故应对同时成立且至少有一个等号成立。当aij≤0时，上式显然成立。故可令则由上式，知则X1中的正分量个数最多有m个，易证，故只需按来确定的θ值，X1就是一个新的基可行解。线性无关，3-5最优性检验和解的判别将基可行解X0和X1分别代入目标函数得通常简写为

检验数说明：1)当所有的

j≤0时,现有基可行解即为最优解。

2)当所有的

j≤0,又对某个非基变量xj有cj－zj=0，且按可以找到θ>0，这表明可以找到另一个基可行解使目标函数也达到最大，此时该规划有无穷多最优解。3)如果某个

j>0,又Pj的所有分量aij≤0,则对任意θ>0,恒有而θ取值可无限大，故目标函数也可无限增大,此时规划问题有无界解。内容小结基本概念凸集、顶点基本结论1)若线性规划问题存在可行解，则可行域是凸集。2)

可行解X为基可行解X的正分量所对应的系数列向量是线性独立的。3)

基可行解对应可行域的顶点。4)一定存在一个基可行解是最优解。§4单纯形法的计算步骤单纯形法的计算步骤：step1、求出线性规划的初始基可行解，列出初始单纯形表。先化成标准形式,设法使系数矩阵中包含一个单位矩阵,不妨设此单位矩阵是(P1,P2,…,Pm),以此作为基可得一个初始基可行解X=(b1,b2,…,bm

).构造初始单纯形表cj

→c1…cm…cj

…cnx1…xm…xj…xnCB基bc1c2cmx1x2xmb1b2bmcj

-zj0…0……1…00…00…1…a1j…a1n…a2j…a2n…amj…amnStep2

进行最优性检验

若表中所有的

j≤0,则表中的基可行解就是问题的最优解，计算结束。否则转下一步。

Step3

基可行解转换，得到新单纯形表。(1)确定入基变量.对应的变量xk作为换入基的变量.(2)确定出基变量.xl作为换出基的变量.alk称为主元素(3)生成新的单纯形表Step4

重复第二、三步一直到计算终止。cj

→c1…cl…cm…cj

…ck…cnCB基bx1…xl…xm…xj…xk…xnc1x11……0……0…ckxk0……0……1…cmxm0……1……0…cj

-zj

0……0……0…s.t.

例1用单纯形法求解线性规划问题解：将上述问题化为标准形式组成初始基，得到初始基可行解初始单纯形表cj

→23000CB基bx1x2x3x4x50x312221000x416400100x51505001cj

-zj23000为入基变量为出基变量[]cj

→23000CB基bx1x2x3x4x50x312221000x416400100x51505001cj

-zj23000[]cj

→23000CB基bx1x2x3x4x5cj

-zjx3x4x2003301001/5164001062010-2/52000-3/5为入基变量为出基变量[]cj

→23000CB基bx1x2x3x4x5cj

-zjx1x4x2203301001/5400-214/53101/20-1/500-10-1/5上表中所有的

j≤0,得到最优解为

X=(3,3,0,4,0

).最优值为

1、当取法不唯一时，可任取一个对应的xj为入基变量。2、相持，即取法不唯一时。可任取一个基变量作为出基变量，则下表中其他基变量的值将等于0，这种现象称为退化。退化的基可行解关于单纯形方法的几点说明(3)退化问题的处理摄动方法、字典序方法和Bland反循环方法问题由定理知，一个非退化的线性规划问题一定可以在有限步内得到最优解或判定无最优解。但是对于一个退化问题，情况又怎样呢？例1可见，它是一个退化的可行基。列出它的单纯形表，并进行迭代取作为初始可行基。cj

→3/4-1501/50-6000CB基bx1x2x3x4x5x6x70x501/4-60-1/2591000x601/2-90-1/5030100x710010001cj

-zj

3/4-1501/50-6000[]3/4x101-240-4/25364000x600303/50-15-2100x710010001cj

-zj

0307/50-33-3003/4x10108/25-84-1280-150x20011/500-1/2-1/151/3000x710010001cj

-zj

002/25-18-1-10[][]1/50x3025/801-525/2-75/2250-150x20-1/160101/401/120-1/6000x71-25/800525/275/2-251cj

-zj

-1/40032-30[]cj

→3/4-1501/50-6000CB基bx1x2x3x4x5x6x71/50x3025/801-525/2-75/2250-150x20-1/160101/401/120-1/6000x71-25/800525/275/2-251cj

-zj

-1/40032-30[]1/50x30-125/2105001050-1500-6x40-1/440011/3-2/300x71125/2-1050000-501501cj

-zj

1/2-120001-10上述迭代过程中，初始表与最后表完全相同，即迭代6次后，又回到初始基。出现了“死循环”，永远也得不到最优解。[]0x50-5/42101/5001-30-6x401/6-30-1/150101/300x710010001cj

-zj

7/4-330-1/500020[]0x501/4-60-1/2591000x601/2-90-1/5030100x710010001cj

-zj

3/4-1501/50-600注:在实际计算中,单纯形方法出现死循环的现象是极其少见的.为了解决这个问题,1952年,A.Charnes

提出摄动法;1954年,G.B.Dantzig

提出字典序法.本节例子是E.Beale于1955年提出的.

勃兰特法则1974年,R.G.Bland利用组合方法成功地解决了退化的线性规划问题,并提出了两条简便的规则,称为勃兰特法则：②选取最小比数中下标最小的基变量为换出变量。①选取中下标最小的非基变量为换入变量，其中§5单纯形法的进一步讨论人工变量法两阶段法关于解的判别单纯形法计算的向量矩阵描述单纯形法小结例:用单纯形法求解线性规划问题解：化为标准形式增加列向量,构造出单位阵5-1人工变量法系数矩阵约束条件可相应表位：人工变量约束条件中增加人工变量后,目标函数如何处理?对任何可行解,原问题的等式约束必须满足,故在最优解中人工变量取值必须为零.为此,令目标函数中人工变量的系数为足够大的一个负值,用-M表示,只要当人工变量的取值不为0,目标函数就不可能极大化.cj

→-30100-

M-M

CB基bx1x2x3x4x5x6x70x441111000-

Mx61-21-10-110-

Mx790310001cj

-zj

-4M-34M10-

M00[]0x4330211-100x21-21-10-110-

Mx7660403-31cj

-zj

6M-304M+103M-4M00x400001-1/21/2-1/20x23011/30001/3-3x11102/301/2-1/21/6cj

-zj

00303/2-M-3/2-M+1/20x400001-1/21/2-1/20x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4cj

-zj

-9/2000-3/4-M+3/4-M-1/4[][]5-2两阶段法基本思想

第一阶段：通过求解辅助问题的最优基可行解得到原问题的初始基可行解。

第二阶段：求原问题的最优解辅助问题设原问题为不妨假设如果某一个元素小于0,该方程两边乘于-1后则可以使右端数变成正数。考虑如下辅助问题：其中首先用单纯形法解辅助问题。原问题与辅助问题的关系1.若原问题有可行解,则辅助规划的最优值为0,反之亦然。就可以得到辅助规划的初始基可行解3．辅助规划有可行解同时,所以即辅助问题的目标函数有下界,所以该问题一定有最优解。4．先求辅助规划的最优基可行解,如果最优值为0，则所以其非零分量对应系数矩阵的列向量线性无关。是原问题的基可行解。的基可行解，2.由于,所以以为基变量，,所以是原问题的可行解。由于是辅助规划的非零分量对应的系数矩阵的列向量也线性无关,所以所以求辅助问题的三种情况cj

→00000-1-1

CB基bx1x2x3x4x5x6x70x441111000-1x61-21-10-110-1x790310001cj

-zj

-2400-100[]0x4330211-100x21-21-10-110-1x7660403-31cj

-zj

60403-400x400001-1/21/2-1/20x23011/30001/30x11102/301/2-1/21/6cj

-zj

00000-1-1[][]0x400001-1/21/2-1/20x23011/30001/30x11102/301/2-1/21/6cj

-zj

00000-1-1cj

→-30100CB基bx1x2x3x4x50x400001-1/20x23011/300-3x11102/301/2cj

-zj

00303/20x400001-1/20x25/2-1/2100-1/41x33/23/20103/4cj

-zj

-9/2000-3/45-3关于解的判别例1用单纯形法求解线性规划问题将上述问题化为标准形式cj

→33000CB基bx1x2x3x4x53x13101/20-1/50x4400-214/53x2301001/5cj

-zj

00-3/200[]3x141001/400x5500-5/25/413x22011/2-1/40cj

-zj

00-3/200无穷多最优解例2用单纯形法求解线性规划问题将上述问题化为标准形式cj

→230CB基bx1x2x30x116401cj

-zj230无界解例3用单纯形法求解线性规划问题将上述问题化为标准形式cj

→2300-MCB基bx1x2x3x4x50x31222100-Mx514120-11cj

-zj2+M3+2M0-M03x26111/200-Mx52-10-1-11cj

-zj-1-M0-3/2-M-M0无解5-4单纯形法计算的向量矩阵描述线性规划的标准形式初始单纯形表为初始解非基变量基变量bBNIcj-zj

N0,…,0基可行解基变量非基变量B-1bIB-1NB-1cj-zj0,…,0-y1,…,-ym关系：或s.t.

例1用单纯形法求解线性规划问题(计算用向量矩阵描述)解：将上述问题化为标准形式组成初始基，初始单纯形表cj

→23000CB基bx1x2x3x4x50x312221000x416400100x51505001cj

-zj23000组成基若取0x40100cj

→23000CB基bx1x2x3x4x52x13101/20-1/50x4400-214/53x2301001/5cj

-zj00-10-1/50x40100cj

→23000CB基bx1x2x3x4x50x312221000x416400100x51505001cj

-zj230000x40100cj

→23000CB基bx1x2x3x4x52x13101/20-1/50x4400-214/53x2301001/5cj

-zj00-10-1/50x401006数据包络分析数据包络分析(dataenvelopentanalysis,DEA)：一种对具有相同类型决策单元进行绩效评价的方法.衡量单位绩效的指标：投入产出比(一个投入一个产出)6-1

基本概念例11

有4个银行储蓄所,每月均完成10000笔人民币的存款、取款业务,但投入情况不同,见下表,试分析这4个储蓄所的绩效储蓄所B1B2B3B4职员数63107营业面积(m2)1001205070解：o6职员数营业面积1293120906030B1B2B4B3连接B2B4和B4B3组成一条凸的折线，通过B3作水平线,通过B2作一垂线。生产可行集：虚线和折线B2B4B3右上方所有点组成的集合生产前沿面：由虚线和折线B2B4B3形成的数据包络线DEA有效：处于生产前沿面上的决策单元DD(5.6,93.3)6-2

评价决策单元DEA有效性的C2R模型DEA有效性的评价是对已有决策单元绩效的比较评价，属相对评价。设有n个决策单元(j=1,2,…,n),每个决策单元有相同的m项投入(i=1,2,…,m),和相同的s项产出(r=1,2,…,s)。xij:

第j单元的第i项投入量；yrj

:

第j单元的第r项产出量；vi：第i项投入的权值；ur：第r项产出的权值；决策单元投入产出hj：第j决策单元投入产出比通过适当选取权值vi和ur，使对j=1,…,n有则对第j0个决策单元的绩效评价可归结为如下优化模型：分式规划模型对偶问题对偶问题的经济意义：为了评价j0决策单元的绩效，可用一个假想的组合决策单元与其比较.决策单元的投入和产出.分别表示这个组合若非DEA有效若DEA有效课后习题1.8已知某线性规划问题的和用单纯形法得到的表如下,试求未知数a~l的值.x1x2x3x4x5x46bcd10x51-13e01cj

-zja-1200初始单纯形表x1x2x3x4x5x1fg2-11/20x54hi11/21cj

-zj0-7jkl迭代后x1为入基变量g=1,h=0(1)(1’)(2)(2’)(1)×1/2=(1’)b=2,c=4,d=-2,f=3(1)×1/2+(2)=(2’)i=5(1)×(-3/2)+(3)=(3’)(3)(3’)j=5,k=-3/2,l=01.9试将下述问题改写成线性规划问题转化

1.10判断下列说法是否正确,并简要说明理由.a)对取值无约束的变量xj

,通常令,其中,在用单纯形法求得的最优解中,有可能同时出现.b)若X1,X2分别是某一线性规划的最优解,则X=λX1+(1-λ)X2也是该问题的最优解,其中0≤λ

≤1。c)单纯形法计算中选取最大正检验数对应的变量作为换入基的变量，将使迭代后的目标函数值得到最快增长.╳╳√

1.10判断下列说法是否正确,并简要说明理由.a)对取值无约束的变量xj

,通常令,其中,在用单纯形法求得的最优解中,有可能同时出现.╳设xj

对应的列为Pj

，则对应的列为Pj

和-Pj分析：若在最优解中,同时出现则一定为基变量，Pj

和–Pj一定同时为基向量，这样与基的定义产生矛盾

1.10判断下列说法是否正确,并简要说明理由.c)单纯形法计算中选取最大正检验数对应的变量作为换入基的变量，将使迭代后的目标函数值得到最快增长.分析：s.t.

cj

→22.1000CB基bx1x2x3x4x50x312221000x