线性规划与单纯形法课件

OR11

线性规划与单纯形法2.1LP(linearprogramming)的基本概念

LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。LP有一组有待决策的变量，一个线性的目标函数，一组线性的约束条件。

OR122.1.1LP的数学模型

例题1—生产计划问题某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品A产品B资源限量劳动力设备原材料9434510360200300利润元/kg70120OR13例题1建模问题：如何安排生产计划，使得获利最多？步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：人力约束9X1+4X2≤360

设备约束4X1+5X2

≤200

原材料约束3X1+10X2

≤300

非负性约束X1≥0X2≥0OR14例题2——配方问题养海狸鼠饲料中营养要求：VA每天至少700克，VB每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：饲料VaVbVc价格元/KGIIIIIIIVV32161810.50.220.50.510.220.827495营养要求70030200OR15例题2建模设抓取饲料Ix1kg;饲料IIx2kg;饲料IIIx3kg……目标函数：最省钱minZ=2x1+7x2+4x3+9x4+5x5约束条件：3x2+2x2+x3+6x4+18x5≥700营养要求：

x1+0.5x2+0.2x3+2x4+0.5x5≥300.5x1+x2+0.2x3+2x4+0.8x5=200用量要求：x1

≤50,x2≤60,x3≤50,x4≤70,x5≤40非负性要求：x1

≥0,x2≥0,x3≥0,x4≥0,x5≥0OR16例题3：人员安排问题医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计：

序号时段最少人数安排人数106—1060X1210—1470X2314—1860X3418—2250X4522—0220X5602—0630x6OR17例题3建模目标函数：minZ=x1+x2+x3+x4+x5+x6约束条件：x1+x2

≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30非负性约束：xj

≥0,j=1,2,…6OR18归纳：线性规划的一般模式目标函数：max(min)Z=c1x1+c2x2+c3x3+…+cnxn约束条件：a11x1+a12x2+a13x3+…+a1nxn≤(=≥)b1

a21x1+a22x2+a23x3+…+a2nxn

≤(=≥)b2

…

…

…

…am1x1+am2x2+am3x3+…+amnxn

≤(=≥)bn非负性约束：x1

≥0,x2≥0,…,xn

≥0OR192.1.2线性规划图解法由中学知识可知：y=ax+b是一条直线，同理：Z=70x1+120x2→x2=70/120x1-Z/120也是一条直线，以Z为参数的一族等值线。

9x1+4x2

≤360→x1≤360/9-4/9x2

是直线

x1=360/9-4/9x2

下方的半平面。所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。OR110例1图示.9080604020

020406080100x1

x29x1+4x2

≤3604x1+5x2

≤200

3x1+10x2

≤300ABCDEFGHIZ=70x1+120x2OR111概念概念：1、可行解：满足所有约束条件的解。2、可行域：即可行解的集合。所有约束条件的交集，也就是各半平面的公共部分。满足所有约束条件的解的集合，称为可行域。3、基解：约束条件的交点称为基解（直观）4、基可行解：基解当中的可行解。5、凸集：集合内任意两点的连线上的点均属于这个集合。如：实心球、三角形OR112结论可行域是个凸集可行域有有限个顶点最优值在可行域的顶点上达到无穷多解的情形无界解情形无解情形OR1132.1.3线性规划的标准型代数式maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2

…

…

…am1x1+am2x2+…+amnxn=bm

xj

≥0j=1,2,…,nOR114线性规划的标准型和式：maxZ=∑cjxj

∑aijxj=bii=1,2,…,m

xj≥0

j=1,2,…,nj=1nnj=1OR115线性规划的标准型向量式：maxZ=CX

∑pjxj=bi

i=1,2,…,m

xj≥0j=1,2,…,nC=(c1,c2,c3,…,cn)

X=(X1,X2,X3,…,Xn)Tnj=1OR116线性规划的标准型矩阵式：maxZ=CXAX=bX≥0

其中：

b=(b1,b2,…,bm)T

a11

a12

….a1nA=a21

a22…

a2n

…

…

…

am1

am2

…amnOR117标准型的特征目标函数极大化约束条件为等式决策变量非负OR118非标准型转化为标准型目标函数极小化转为极大化：

minZ=－max(－Z)，一个数的极小化等价于其相反数的极大化。不等式约束的转化：∑aijxj≤bi

加入松弛变量

∑aijxj≥bi

减去剩余变量非正变量：即xk

≤0则令x’k=－xk

自由变量：即xk无约束，令xk=x’k－x”kOR119非标准型转化举例之一maxZ=70X1+120X2maxZ=70X1+120X29X1+4X2≤3609X1+4X2+X3=3604X1+5X2

≤2004X1+5X2+x4=2003X1+10X2

≤3003X1+10X2+x5=300

X1≥0X2≥0Xj≥0j=1,2,…,5OR120非标准型转化举例之二minZ=x1+2x2-3x3maxZ’=x’1－2x2+3(x’3－x”3)

x1+x2+x3

≤9－x’1+x2+x’3－x”3+x4=9-x1-2x2+x3≥2x’1－2x2+x’3－x”3-x5=23x1+x2-3x3=5－

3x’1+x2－3(x’3－

x”3

)=5x1≤0x2≥0x3无约束

x’1≥0x2≥0x’3≥0x”3≥0x4≥0

x5≥0

OR1212.1.4基可行解基的概念：如前所述LP标准型和式：maxZ=∑cjxj

∑aijxj=bi

xj

≥0

j=1,2,…,n

矩阵式：maxZ=CXAX=bX≥0

约束方程的系数矩阵A的秩为m，且m<n。设A=B+N，B是A中m

m阶非奇异子矩阵，则称B是LP的一个基，即：B是A中m个线性无关向量组。nj=1nj=1OR122基解的概念

不失一般性,设B是A的前m列,即B=(p1,p2,…,pm）,其相对应的变量XB=(x1,x2,…,xm)T,称为基变量；其余变量XN=(Xm+1,…,Xn)T称为非基变量。令所有非基变量等于零,则X=（x1,x2,…xm,0,…,0)T称为基解。OR123基可行解的概念基可行解：基解可正可负，负则不可行（违背非负性约束条件），称满足所有约束条件的基解为基可行解。退化的基可行解：若某个基变量取值为零，则称之为退化的基可行解。基解的数目：最多Cmn=n!/m!(n-m)!OR124例题6基可行解说明

maxZ=70X1+120X2P1P2P3P4P5

9X1+4X2+X3=36094100

4X1+5X2+x4=200A=45010

3X1+10X2+x5=300310001

Xj≥0j=1,2,…,5这里m=3,n=5。Cmn=10OR125例题6基可行解说明基（p3,p4,p5）

，令非基变量x1,x2=0，则基变量x3=360,x4=200,x5=300,可行解基（p2,p4,p5）,令非基变量x1=0,x3=0基变量x2=90,x4=－250,x5=－600.非可行解基（p2,p3,p4

），令非基变量x1,x5=0，则基变量x2=30,x3=240,x4=50,可行解（P21图）OR1262.2单纯形法2.2.1初始基可行解的确定从系数矩阵中找到一个可行基B，不妨设B由A的前m列组成，即B=(P1,P2,……Pm)。进行等价变换－－约束方程两端分别左乘B－1得

X1++a’1m+1xm+1+…+a’1nxn=b’1

x2++a’2m+1xm+1+…+a’2nxn=b’2

……………..

xm+a’mm+1xm+1+…+a’mnxn=b’m令非基变量为0，得基可行解X(0)=(b1’，b2’，……bm，0，……0）Tz0=∑cibi’OR1272.2单纯形法2.2.2最优性检验：LP经过若干步迭代，成为如下形式：X1++a’1m+1xm+1+…+a’1nxn=b’1

x1=b’1-∑

a’1jxj

x2++a’2m+1xm+1+…+a’2nxn=b’2x2=b’2-∑a’2jxj

……………..……………..

xm+a’mm+1xm+1+…+a’mnxn=b’mxm=b’m-∑a’mjxjOR128单纯形法一般性表示：xi=b’i-∑a’ijxji=1,2,…m将xi代入目标函数得：Z=∑

cjxj=∑

cixi+∑

cjxj

=∑ci（b’i-∑a’ijxj

）+∑

cjxj

=∑cibi’+∑(cj-∑

cia’ij)xj

令：σj=cj-∑

cia’ij

z0=∑cibi’则Z=z0+∑σjxj

σj判别准则：

σj≤0

时,达到最优解OR129单纯形法2.2.2基变换若存在σj≥0，则取max{σj

}=σK

，相应之非基变量XK若取非零，将使Z增加,故令XK

进基。令XK≠0，其余非基变量保持为零。XK

原是非基变量，取零值，若XK

≠0将迫使某个原基变量为零，当XK取值超过任意b’i/a’ik

时,将破坏非负性条件,于是令θ=min{b’i/a’ik

a’ik>0}=b’L/a’Lk

。

这时原基变量XL=0，由基变量变成非基变量，a’Lk处在变量转换的交叉点上，称之为枢轴元素σj≥0OR130单纯形法解题举例单纯形表的格式：

CjC1C2

…

Cn

θiCBXBbx1

x2

….xn

C1C2

…Cmx1x2…xmb1b2…bma11a12

…a1na21a22

…a2n…

…

…am1am2…

amnθ1θ2

…θm

σjσ1σ2

…σnOR131

CjC1C2

…

CnCBXBbX1

X2

X3X4X5θj

000X3X4X5360200300

94100

45010310001904030σj0

70120000

00120X3X4X224050

307.8010-0.42.5001-0.50.31000.130.7620100σj3600

34000-12701200X3X1X2842024

001-3.121.161000.4-0.2010-0.120.16σj4280

000-13.6-5.2OR1322.2.3单纯形法的计算步骤

找到初始可行基，建立单纯形表计算检验数，若所有σj≤0

则得最优解，结束。否则转下步若某σK

≥0而P’K≤0，则最优解无界，结束。否则转下步根据max{σj

}=

σK原则确定XK

进基变量；根据θ规则：θ=min{b’i/a’ik

a’ik

>0}=b’L/a’Lk

确定XL为出基变量以a’Lk

为枢轴元素进行迭代，回到第二步OR1332.3单纯形法的进一步探讨2.3.1极小化问题直接求解：检验数的判别由所有σj≤0

即为最优，变为所有σj≥0则为最优。人工变量法之一：大M法人工变量价值系数M例

人工变量法之二：构造目标函数，分阶段求解例2.3.2无穷多最优解情形：非基变量检验数σj=02.3.3退化解的情形：有两个以上θ值相等OR1342.3.4单纯形法的计算机求解程序说明应用举例例题1例题2OR1352.5LP应用举例之一例13合理下料问题料长7.4米，截成2.9、2.1、1.5米各200根。如何截取余料最少？关键：设变量。