第2章-线性规划

第二章线性规划运筹学中应用最广泛的方法之一，历史悠久，理论成熟。运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大线性规划模型特点决策变量：x1,...,xn表示要寻求的方案，每一组值就是一个方案；约束条件：线性等式或不等式目标函数：Z=ƒ(x1

…xn)线性式，求Z极大或极小一般式minz=c1x1+c2x2+…+cnxnai1x1+ai2x2+…+ainxn

=bi,i=1,…,pai1x1+ai2x2+…+ainxn

bi,i=p+1,…,mxj

0,j=1,…,qxj

符号无限制，

j=q+1,…,ns.t.目标函数（LP）3隐含的假设比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij,bi,ci为确定值

矩阵形式说明：

A1A2………Ana11a12………a1nA=a21a22………

a2n

…am1am2………amn

x1x=x2

xn…

b1b=b2

bm…

c1c=c2

cn…约束矩阵决策向量右端向量价值向量

LP问题的规范型：LP问题的标准型：LP问题的三种形式是等价的：minz=cTxAx

bx0

s.t.minz=cTxAx=bx0

s.t.LP问题的规范型LP问题的标准型LP问题的一般型LP问题的规范型LP问题的一般型LP问题的标准型LP问题的一般型例：将线性规划问题化成标准型(P15例2.1.3)

：解的概念：满足所有约束条件的一组x1,x2，…xn的值称作线性规划的可行解，所有可行解构成的集合称作可行域。使目标函数取得最大或最小值的可行解称为线性规划问题的最优解；对应的目标函数的取值称为最优值。求解线性规划问题就是求其最优解和相应的最优值。图解法？对于只有两个变量的线性规划问题，可以用在平面上作图的方法求解，这种方法称为图解法。

特点：图解法简单、直观，便于初学者了解线性规划基本原理和几何意义。§2.2可行区域与基本可行解step1.画直角坐标系；线性规划问题图解法的步骤对每个约束（包括非负约束）条件，先取等式得到一条直线（平面）并在坐标图中画出该直线，然后取一已知点来判断该点的坐标是否满足该约束条件，若满足，则可行域与已知点在所画直线的同侧，否则可行域在直线的另一侧。若所有的约束均已画出，则可在坐标系中画出可行域。step2.依次做每条约束线，找出可行域;若不存在可行域,则该问题无可行解；step3.做目标函数线，根据目标类型平移,直到该线即将离开可行域时与该线接触的最后一点即为一最优解;

若该线可无限制地在可行域内移动,则该问题无界。例1.maxZ=-X1+X2

2X1-X2-2X1-2X22X1+X25

X1,X20

1.图解法示例解：确定可行域0123X2123X12X1-X2=-2()(0,2)(-1,0)2X1-X2

=-2X1+X2=5()(0,5)(5,0)

X1-2X2=2()(0,-1)(2,0)

X1-2X2

=2X1+X2

=5Z=-X1+X2(1,4)在该点取到最大值32310123X2A1BC42X1-X2

=-2X1-2X2

=2X1+X2

=5(1,4)若目标函数改为minZ=4X1-2X2

2X1-X2-2X1-2X22X1+X25

X1,X20A2A3A4O最优解：A1A2线段上所有的点，最优值为-4X(1)=(0,2)T,X(2)=(1,4)TX=X(1)+(1-)X(2)(01)X1=1-X2=2+4(1-)=4-2(01)minZ=4X1-2X2=-4

2310123X2A1BC42X1-X2

=-2X1-2X2

=2X1+X2

=5(1,4)A2A3A4O可行域：由约束平面围起来的凸多边形区域，可行域内的每一个点代表一个可行解。最优解：总是在可行域的边界上，一般由可行域的顶点表示。有效与无效(紧与松)约束：与最优解相关的约束为有效(紧)约束。图解法的观察【1】无界无有限最优解例2、maxZ=2X1+4X22X1+X28-2X1+X22X1,X20Z=02X1+X2=8-2X1+X2=28246X240X1例3、maxZ=3X1+2X2-X1-X21X1,X20无解无可行解-1X2-1X10-X1-X2

=1如果可行域为空集，线性规划问题无可行解；如果目标函数线可以无限制地在可行域内向改善的方向移动，线性规划问题无界；线性规划问题可能存在无穷多个最优解。图解法的观察（2）

唯一最优解无穷多最优解无有限最优解无可行解有最优解无最优解总结两个变量的LP问题的解：(1)、可行域为凸多边形。(2)、若有最优解，定可在可行域的顶点得到。X(1)X(2)凸多边形凹多边形X(1)X(2)思考：两个以上变量解的情况有又如何呢？2.可行区域的几何结构minZ=CTXAX

=bX0假设：秩(Am×n)=m<nD={X∈Rn|

AX=b,X0}≠Φ

a11a12………a1nA=a21a22………

a2n

…am1am2………amn其中：

b1b=b2

bm…X

=(x1…xn)TC

=(c1…cn)T凸集没有凹陷部分，该集合内任取两点连线上的任何点都应该在集合内。定义1：xSy凸集：S是n维欧氏空间的一个集合,如果对任意

x,yS,0≤≤

1,

有x+(1-)yS。证明：设LP问题的可行解域为集合DD={X|AX=bX0}任取X(1),X(2)D,则

X=X(1)

+(1-)X(2)

0

(0

1)

又因为AX(1)

=b，AX(2)

=b

所以AX=A[X(1)

+(1-)X(2)

]=b

+(1-)b=b

则

XD，D为凸集定理1

D={X∈Rn|AX=b,X0}是凸集。定义2：

给定b∈R1,及非零向量a∈Rn称集合

H={X∈Rn|aTX=b}是Rn中的一个超平面.H+={X∈Rn|aTX

b}H-={X∈Rn|aTX

b}H+，H-和超平面H都是凸集.H+和H-是由超平面H产生的两个闭的半空间定理2任意多个凸集的交集仍是凸集。定义3：结论：线性规划的可行域是凸集。凸集S的顶点X：—S是一个凸集，X∈S，对任意X(1),

X(2)∈S，X(1)≠X(2),和任意的，0<<1,都有X≠X(1)+(1-)X(2).定义4：a11…a1ma1m+1…a1na21…

a2ma2m+1…

a2n………am1…

amm

amm+1…

amnBN(m<n)r(A)=m,至少有一个m阶子式不为03、基本可行解及线性规划的基本原理定义5：基(基阵)——秩为m的约束矩阵Am×n的一个m阶子矩阵B是可逆矩阵，则方阵B称为对应LP问题的一个基。A=(A1…

AmAm+1…

An)=(BN)

基向量非基向量…X=(X1…

Xm

Xm+1…

Xn

)T=(XBT

，XNT)T

基变量非基变量

XBT

XNT…AX=b的求解A=(BN)X=(XBXN)TXBXN(BN)=bBXB+NXN=bBXB=b-NXNXB=B-1b-B-1NXN定义5：基本解——对应于基B，X=为AX=b的一个解。B-1b0基本可行解——基B，基本解X=若B-1b0，称基B为可行基。

B-1b0※基本解中最多有m个非零分量。※基本解的数目不超过Cnm=个。n!m!(n-m)!（续）X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50121003201002001A1A2A3A4A5A=例：MaxZ=40X1+50X2

X1X2X3X4X5X=b=306024基B=(A3A4A5)=I可逆非基N=(A1A2)X3=30-(X1+2X2)X4=60-(3X1+2X2)X5=24-2X2121003201002001A1A2A3A4A5A=Z=40X1+50X2

令X1=

X2=0,X3=30,X4=60,X5=24X===XN0XBB-1b00306024

121又：Ｂ1=(A1A2A3)=320020|B1|=6≠0,

可逆X1=12-(1/3X4-1/3X5)X2=12-(1/2X5)X3=-6-(-1/3X4-2/3X5)令X4=X5=0X=(12,12,-6,0,0)T不是可行解Ｂ1=(A1A2A3)不是可行基。可以直接验证B-1b是否大于等于零。定理3：LP问题的可行解X是基本可行解X的非0分量对应的系数列向量线性无关证明：()显然。不妨设前k个分量非零。若A1,…,Ak

线性无关，则必有k≤m。若k=m,构成基，则X就是基本可行解；若k<m,可以在其余n-k列向量中再找出m-k个，构成m个线性无关的列向量构成基，X就是该基对应的基本可行解。D={X|AX=b，X0}，若A1,…,Ak

线性相关，必有不全为0的1,…,

k使1A1+…+

k

Ak

=0,记＝(1,…,

k,0…,0)T则有A

＝1A1+…+

k

Ak

=0可行域D中点X是顶点X是基本可行解定理4：Xj

>0j=1,…,kXj

=0j=k+1,…,nX＝(X1,…,Xn

)T证：X是D顶点.。不妨设若A1,…,Ak

线性无关,则X是基本可行解.选＝min{|

j≠0}>0Xjj做

X(1)

=X+

0

X(2)

=X-

0又AX(1)

=AX+A＝b

AX(2)

=AX-A=b

所以X(1)DX(2)D而X＝1/2X(1)+1/2X(2)矛盾(j=1,…,K)所以，A1,…,Ak

线性无关，即X为基本可行解.证明：()不妨设X为基本可行解Xj

>0j=1,…,kXj

=0j=k+1,…,n若X不是顶点，则有X(1)≠X(2)D

X=X(1)

+(1-)X(2)

(0<

<1)

Xj

=Xj

(1)

+(1-)Xj

(2)

(j=1,…,n)因为>0，1->0，Xj

(1)

0，

Xj

(2)

0所以Xj

(1)＝

Xj

(2)＝

0(j=k+1,…,n)36因为AX(1)

=bAX(2)

=bA

jXj(1)=bkj=1A

jXj(2)=bkj=1即A1X1(1)+…+Ak

Xk(1)=bA1X1(2)+…+Ak

Xk(2)=b由－得(X1(1)－X1(2))A1+…+(Xk(1)－Xk(2))Ak=0矛盾所以，A1,…,Ak

线性相关.证明：D={X|AX=bX0}，X为可行解X＝(X1,…,Xn

)TXj

>0j=1,…,kXj

=0j=k+1,…,n若A1,…,Ak

线性相关，必有不全为0的1,…,

k使1A1+…+

k

Ak

=0做

＝(1,…,

k,0…,0)T则有A

＝1A1+…+

k

Ak

=0标准形式的LP问题有可行解该LP问题一定有基本可行解定理5：选＝min{|

j≠0}>0Xjj做

X(1)

=X+

0

X(2)

=X－

0又AX(1)

=AX+A＝b

AX(2)

=AX－A=b

所以X(1)DX(2)D显然X(1)和

X(2)中至少有一个非零分量至少比X少一个.若该解为基本可行解，则停止.否则，继续进行该过程，直到剩下一个非零分量，其对应的列向量一定是线性无关的，也就得到了基本可行解。(j=1,…,K)若X为最优解，不妨设Xj

>0j=1,…,kXj

=0j=k+1,…,n若X不是基本可行解，类似定理5，证明：得

X(1)

=X+

0

X(2)

=X－

0显然CT

X(1)

=CTX+CT

CTX

CT

X(2)

=CTX-CT

CTX所以CT

X(1)

=CTX(2)=CTX,即X(1)和X(2)都是最优解。仿照定理5的方法，一定可以构造出一个基最优解。标准形式的LP问题有有限的最优值该LP问题一定有基本可行解是最优解定理6:40LP问题解的性质若(LP)问题有可行解，则可行解集(可行域)是凸集(可能有界，也可能无界)，有有限个顶点。

(LP)问题的基本可行解可行域的顶点。若(LP)问题有最优解，必可以在基本可行解(顶点)达到。可行解基本解基本可行解个数有限，当约束条件为m个，n个变量时，基本可行解个数不超过:Cnm=

n!m!(n-m)!(m<n)§2.3单纯形法引例maxZ=40X1+50X2X1+2X2≤303X1+2X2≤602X2≤24X1，X20minW=-40X1-50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50解：(1)、确定初始可行解B=(A3A4A5)=I令X1=

X2=0X(1)=(0,0,30,60,24)TW(1)=0minW=-40X1-50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50(2)、判定解是否最优W=0-40X1-50X2当X1从0↗或X2从0↗W从0↘，∴X(1)不是最优解(3)、由一个基可行解→另一个基可行解。∵50>40选X2从0↗，X1=0X3=30-2X20，X230/2

X4=60-2X20，X260/2

X5=24-2X20，X224/2√

X2=min(30/2,60/2,24/2)=12X2进基变量，

X5出基变量。minW=-40X1-50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50B2=(A3A4A2)minW=-40X1-50X2

④X1+2X2+X3=30①3X1+2X2+X4=60②2X2+X5=24③X1…X50minW=-600-40X1+25X5X1+X3-X5=63X1+X4-X5=36X2+1/2X5=12X1…X50③×1/2

，③代入④式，①－③，②－③令X1=X5=0X(2)=(0,12,6,36,0)TW(2)=-600(2)'

判断：minW=-600-40X1+25X5∵40>0，∴X(2)不是最优解。(3)'

选X1从0↗，X5=0X3=6-X10

√X4=

36-3X10

X2=120

X1=min(6/1,36/3)=6X1进基，

X3出基。minW=-600-40X1+25X5X1+X3-X5=63X1+X4-X5=36X2+1/2X5=12X1…X50B3=(A1A4A2)minW=-840+40X3-15X5X1+X3-X5=6

-3X3+

X4+2X5=18X2+1/2X5=12令X3=X5=0,X(3)=(6,12,0,18,0)TW(3)=-840minW=-600-40X1+25X5④X1+X3-X5=6①3X1+X4-X5=36②X2+1/2X5=12③X1…X50①代入④式，②-3*①(2)"判断：minW=-840+40X3-15X5

∵15>0∴X(3)不是最优解(3)"

选X5从0↗，X3=0X1=6+X50

X4=

18-2X50

√X2=12-1/2X5

0

X5=min(18/2,12/1/2)=9X5进基，

X4出基。minW=-840+40X3-15X5X1+X3-X5=6

-3X3+

X4+2X5=18

X2+1/2

X5

=12B4=(A1A5A2)minW=-975+35/2X3+15/2X4X1-1/2X3+1/2X4=15

-3/2X3+1/2X4+

X5=

9X2+3/4X3-1/4X4=15/2

令X3=X4=0,X(4)=(15,15/2,0,0,9)TW(4)=-975minW=-840+40X3-15X5④X1+X3-X5=6

①-3X3+

X4+2X5=18②

X2+1/2

X5

=12③②

×1/2

，②代入④式，①+(1/2)②

，③-(1/4)②

判断：minW=-975+35/2X3+15/2X4，maxZ=975达到最优。例1

x1x2x3x4x5-z04050000x3x4x5306024

121003201002001maxZ=40X1+50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50(-z)+40X1+50X2=0X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50X230/2

X260/2

X224/2回顾min例1

x1x2x3x4x5-z-60040000-25x3x4x2636121010-13001-101001/2(-z)+40X1-25X5=-600X1+X3-X5=63X1+X4-X5=36X2+(1/2)X5=12X1…X50X16/1

X136/3例1

x1x2x3x4x5-z-840

00-40015x1x4x2618121010-100-31201001/2(-z)-40X3+15X5=-840X1+X3-X5=6-3X3+X4+2X5=18X2+1/2X5=12X1…X50X518/2

X512/1/2例1(-z)-35/2X3-15/2X4=-975X1-1/2X3+1/2X4=15-3/2X3+1/2X4+X5=9X2+3/4X3-1/4X4=15/2X1…X50

x1x2x3x4x5-z-975

00-35/2

-15/20x1x5x215915/210-1/21/2000-3/21/21013/4-1/40X(4)=(15,15/2,0,0,9)TmaxZ=9750(0,0)X2X1ADCB(0,12)(6,12)(15,7.5)X(1)=(0,0,30,60,24)T；Z(1)=0X(2)=(0,12,6,36,0)T

；

Z(2)=600X(3)=(6,12,0,18,0)T；Z(3)=840

X(4)=(15,7.5,0,0,9)T；Z(4)=975思考：线性规划问题的求解方法minZ=CTXAX

=bX0其中，Am×n

满秩X

=(x1…xn)T

D={X∈Rn|

AX=b,X0}≠Φ单纯形法的理论基础对应基B，其基本解为XB=B-1b,XN=0;

当B-1b≥0，为基本可行解。

当B-1b>0，为非退化的基本可行解。对应可行基B：XB=B-1b-B-1NXNZ=CBTB-1b+(CNT

-CBT

B-1N)XNminZ=CTXAX=b

X0XB+B-1NXN=B-1bXB

，XN0原线性规划可变形为minZ=CBT

B-1b-(CBT

B-1N-CNT)XNA=(B,N)XBXNX=AX=b

X0minZ=CBT

B-1b-(CBT

B-1A-CT)X令A=B-1A=(I,B-1N)b=B-1b,z0=CBT

B-1b

令A=B-1A=(I,B-1N)b=B-1b,z0=CBT

B-1b

10…0a1m+1…a1n01…0a2m+1…a2n………00…1amm+1…amnA=若A的前m列构成基B，则minZ=CTX

AX=

bX0CBT

B-1bB-1bCBTB-1A-CTB-1A若CBT

B-1A-CT

0，则B为最优基。0b-CTA对应基B的单纯形表为了叙述方便，我们不妨假设（LP）问题为如下形式：或典则方程组（典式）非基变量检验数单纯形表

X1X2…

Xm

Xm+1…

Xm+k

…XnXBZ000

…0m+1…m+k…

nX1b110…0a1m+1…a1m+k…a1nX2b201…0a2m+1…a2m+k…

a2nXr

br

00…0arm+1…arm+k…

arnXm

bm

00…1amm+1…amm+k

…

ann

P1P2

…PmPm+1…Pm+k

…Pn…………………………………………此时，B=(P1P2…Pm)＝I对应的基本可行解为定理1：对解X(1)

，若检验数j(j=1,…,n)全部

0,则X(1)为最优解。证明：Xi=bi-aij

xjJ=m+1n令非基变量Xk

=(﹥0)X(2)

=(b1-a1k,…,bm

-amk

,0,…,,…,0)TAX(2)

=bX(2)0Z=Z0-k

，当时

Z-定理2：对X(1)，若有某个非基变量Xk→k>0且相应的Pk

=(a1k,…,amk

)T

0，则原问题无有限最优解。换基迭代公式：(1)、决定进基变量：maxj=k>0,则Xk

为进基变量(2)、决定离基变量：bi-aikXk

0

(i=1,2,…,m)，Xk

biaik(aik>0θ=minaik

>0=biaikbrark则第r个基变量（XBr）为换出变量。定理3：经单纯形法得到的X(2)

=(b1-a1k,…,bm

-

amk

,0,…,,…,0)T是基本可行解，在非退化情况下有Z(2)<

Z(1)

θ=minaik

>0=biaikbrark注：证明：不妨设XBr

=Xm

=0,Xk

==bmamk(﹥0)X(1)中P1,…

Pm线性无关，下证P1,…

Pm-1,Pk线性无关。若否，因为P1,…

Pm线性无关则Pk

=a1kP1+…+am-1,kPm-1+amk

Pm①而Pk

=l1P1+…+lm-1Pm-1②

①-②(a1k-

l1)P1+…+(am-1k-

lm-1)Pm-1+amkPm=0P1,…,Pm线性相关，矛盾。即X(2)是基本解，且是可行解.Z(2)=

Z(1)-

k<Z(1)单纯形法基本步骤(1)、定初始基，初始基本可行解，典式，检验数(3)、若有k>0，Pk全

0，停，没有有限最优解；否则转(4)(2)、对应于非基变量检验数j全

0。

若是，停，得到最优解；若否，转(3)。θ=minaik

>0=biaikbrark定第r个基变量（XBr）为离基变量，ark为主元。由最小θ比值法求：k＝max{j|j=1,…,n}>0,k→Xk

Xk为进基变量j>0(4)、转(2)k0

……a1k0ark1amk

0初等行变换Pk

=…………(5)、以ark为中心，换基迭代在单纯形表上解决下述问题maxZ=40X1+50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50MinZ’=-40X1-50X2X1X2X3X4X5Z’

04050000θX3301210015X460

3

201030X5240(2)00112-60040000-25X36(1)010-16X4363001-112X21201001/2-84000-40015X161010-1X41800-31(2)9X21201001/224

z’-97500-35/2-15/20X11510-1/21/20X5900-3/21/21X215/2013/4-1/40本问题的最优解X=(15,15/2,0,0,9)T

Z=975几点说明：(1)、例minZ=-X1-2X2X1

4X2

3X1+2X2

8

X1,X20

X1+X3=

4X2+X4=

3X1+2X2+X5=

8

X1，…

，X50X1X2X3X4X5Z

012000X3410100X430(1)010X5812001Z

-6100-20X3410100X2301010X52

(1)00-21(接下表)

X1X2X3X4X5Z

-80000-1X32001(2)-1X2301010X12100-21Z

-80000-1X41001/21-1/2X2201-1/201/2X14

10100非基变量检验数为0X(1)=(2,3)Z(1)=-8X(2)=(4,2)Z(2)=-8无穷多解全部解：X=α+(1-α)

(0α1)2432(2)、3X1+4X264X1+X223X1+2X23X1,X20MinZ=-10X1-12X2X1X2X3X4X5Z

01012000X363(4)100X4241010X5332001

X1X2X3X4X5

z

01012000θi

X363(4)1003/2

X42410102/1

X53320013/2

z-1810-300θi

X23/23/411/4002

X41/213/40-1/4102/13

X50

(3/2)0-1/2010

z

-1800-8/30-2/3

X23/2011/20-1/2

X41/2005/61-13/6

X1010-1/302/3退化解X*=(0,3/2,0,1/2,0)TZmin=-18X1X2X3X4X5Z

041000X32-11100X44(1)-4010X581-2001(3)例：minZ=-4X1-X2-X1+X2

2X1-4X2

4X1-2X2

8X1,X20Z-160170-40X360-3110X141-4010X540(2)0-11z-500009/2-17/2X312001-1/23/2X112100-12X22010-1/21/2本问题无界。X1X2OZ=0Z=-4X1-X2X1-2X2

8-X1+X2

2

X1-4X2

4

一、两阶段法：原问题minZ=Cj

xj

j=1nxj

0j=1naij

xj

=bi0

(i=1,2,…,m)作辅助问题minW=yi

i=1mxj

，

yi0j=1naij

xj

+yi

=bi(i=1,2,…,m)§2.4初始解第1阶段最优基B*min=*(1)、*﹥0

(2)、*=0

yi

≡0(i=1,2,…,m)①B*基变量无人工变量②B*基变量含人工变量yr单纯形表中，yr+ark

yk

+arj

xj

=0(﹡)

k∈Jj∈JJ：非基变量下标集合,判定原问题无可行解。1)arj

全=0

(﹡)

式多余方程2)arj

有0

元，设为ars

0

以ars为主元，换基迭代，最后得到①maxZ=-X1+2X2X1+X2

2-X1+X21X2

3X1X2

0例1：minZ’=X1-2X2minW=X6+X7X1+X2-X3+X6=2-X1+X2-X4+X7=1X2+X5=3X1…X7

0X1+X2-X3=2-X1+X2-X4=1X2+X5=3X1…X5

0第一阶段：求

00000-1-1

X1X2X3X4X5X6X7W

3

0

2-1-10

00X6211-10010X71-1

(1)0-1001X530100100W

1

+20-1100-2X61(2)0-1101-1X21-1

10-1001X52100110-1

W

0

00000-1-1X11/210-1/21/201/2-1/2X23/20

1-1/2-1/201/21/2X53/2001/21/21-1/2-1/2

-12000X1X2X3X4X5z’

-5/2001/23/20X11/210-1/2(1/2)0X23/201-1/2-1/20X53/2001/21/21z’-4-30200X4120