第四章线性规划的标准型及单纯形法课件

运筹学

硕士生导师

OperationsResearch1精选课件ppt第４章

线性规划的标准型及单纯形法2精选课件ppt3精选课件ppt线性规划的标准型（SLP）

Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…a1nxn=b1a21x1+a22x2+…a2nxn=b2

……am1x1+am2x2+…amnxn=bmx1,x2,…,xn≥04精选课件ppt标准型的特征目标函数极大化约束条件为等式决策变量非负5精选课件ppt线性规划的标准型代数式

Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…a1nxn=b1a21x1+a22x2+…a2nxn=b2……am1x1+am2x2+…amnxn=bm

x1,x2,…,xn≥0（xj≥0

j=1,2,…,n）

6精选课件ppt线性规划的标准型和式：7精选课件ppt线性规划的标准型向量式：8精选课件ppt线性规划的标准型矩阵式：9精选课件ppt非标准型转化为标准型目标函数极小化转为极大化：

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

∑aijxj≥bi减去剩余变量非正变量：即xk≤0则令x’k=-xk

自由变量：即xk无约束，令xk=x’k-x”k10精选课件ppt非标准型转化举例之一maxZ=70X1+120X2maxZ=70X1+120X29X1+4X2≤3609X1+4X2+X3=3604X1+5X2≤2004X1+5X2+x4=2003X1+10X2≤3003X1+10X2+x5=300X1≥0X2≥0X1≥0X2≥0X3≥0x4

≥0x5≥0

11精选课件ppt非标准型转化举例之二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

12精选课件ppt非标准型转化举例之三minZ=-3x1-x2+4x3-x1+2x2+x3

=5x1-x2+x3≥-6x1≤0x2≥0x3无约束13精选课件ppt非标准型转化举例之三minZ=-3x1-x2+4x3maxZ’=-3x’1+x2-4(x’3-x”3)

-x1+2x2+x3

=5x’1+2x2+x’3-x”3=5

x1-x2+x3≥-6x’1+x2-（x’3-

x”3）+x4=6x1≤0x2≥0x3无约束

x’1≥0x2≥0x’3≥0x”3≥0x4≥014精选课件ppt基可行解秩基基可行解15精选课件ppt秩设m×n矩阵A中有一个r阶子式D不等于零，而所有r+1阶子式（如果存在的话）全等于零，则称D为矩阵A的最高阶非零子式，称数r为矩阵A的秩，记作R(A)=r。零矩阵的秩为零。m×n矩阵A的秩R(A)≤min{m,n}假设：约束方程组的系数矩阵A的秩为m（R(A)=m）,m<n16精选课件ppt基基的概念：如前所述LP标准型和式：maxZ=∑cjxj

∑aijxj=bi

xj≥0

j=1,2,…,n

矩阵式：maxZ=CXAX=bX≥0

约束方程的系数矩阵A的秩为m，且m<n。设A=B+N，B是A中mxm阶非奇异子矩阵，则称B是LP的一个基，即：B是A中m个线性无关向量组。17精选课件ppt基解不失一般性,设B是A的前m列,即B=(p1,p2,…,pm）,其相对应的变量XB=(x1,x2,…,xm)T,称为基变量；其余变量XN=(Xm+1,…,Xn)T称为非基变量。

令所有非基变量等于零,

则X=（x1,x2,…xm,0,…,0)T称为基解。18精选课件ppt基可行解基可行解：基解可正可负，负则不可行，故称满足非负性条件的基解为基可行解。相应的基为可行基。退化的基可行解：若某个基变量取值为零，则称之为退化的基可行解。基解的数目：最多Cmn=n!/m!(n-m)!19精选课件ppt例题6基可行解说明

maxZ=70X1+120X2P1P2P3P4P59X1+4X2+X3=360941004X1+5X2+x4=200A=450103X1+10X2+x5=300310001Xj≥0j=1,2,…,5这里m=3,n=5。Cmn=1020精选课件ppt例题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图）21精选课件ppt（SLP）的基可行解对应于其可行域的顶点（极点）若（SLP）有最优解，则必有最优基可行解可行基解——迭代——更优的可行基解——最优基解（单纯形法的原理）22精选课件ppt单纯形法最优性检验：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’mjxj23精选课件ppt单纯形法24精选课件ppt单纯形法基变换若σ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处在变量转换的交叉点上，称之为枢轴元素25精选课件ppt单纯形法解题举例单纯形表的格式：CjC1C2…CN

θiCBXBbX1x2….Xn

C1C2

…CMX1X2…XMb1B2…bma11a12…a1na21a22…a2n………am1am2…amnθ1θ2…θmσjσ1σ2…σn26精选课件ppt产品A产品B资源限制劳动力设备原材料9434510360工时200台时300公斤单位产品利润（元）70120某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：27精选课件ppt问题：如何安排生产计划，使得获利最多？步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：人力约束9X1+4X2≤360

设备约束4X1+5X2≤200

原材料约束3X1+10X2≤300

非负性约束X1≥0X2≥028精选课件pptCj70120000CBXBbX1

X2

X3X4X5θi000X3X4X536020030094100

45010310001904030σj0

7012000000120X3X4X224050

307.8010-0.42.5001-0.50.31000.130.7620100σj360034000-12070120X3X1X2842024001-3.121.161000.4-0.2010-0.120.16σj4280

000-13.6-5.229精选课件pptCj3-305-1CBXBbX1

X2

X3X4X5θi3-3-1X1X2X51212710-2[2]001-20000-43112/2=6-27/3=9600-4205-3