线性规划单纯形方法

线性规划单纯形方法第1页，共23页，2023年，2月20日，星期六线性规划问题基本定理定理一若线性规划问题存在可行解，则问题的可行域是凸集。定理二线性规划问题的基本可行解X对应线性规划问题可行域（凸集）的顶点。定理三若线性规划问题有最优解，一定存在一个基可行解是最优解(即最优解一定在某顶点上)。从上述三个定理可以看出，要求线性规划问题的最优解，只要比较可行域（凸集）各个顶点(或者说基可行解)对应的目标函数值即可，最大的就是我们所要求的最优解。第2页，共23页，2023年，2月20日，星期六§3.2单纯形方法思路：从一个基可行解（极点）出发（如何去找一个基可行解？），判断其是否为最优解，（如何判断？），

若不是，则转换到相邻的基可行解（另一个极点），并使目标函数值不断增大，一直找到最优解为止。第3页，共23页，2023年，2月20日，星期六

单纯形法：先找到一个初始基可行解，如果不是最优解，设法转换到另一个基可行解（换基迭代，即从极点到极点），并使目标函数不断增大，一直到找到最优解为止。

B1X(1)B1X(1)B2X(2)B3X(3)BnX(n)XN=0X=(XB,XN)第4页，共23页，2023年，2月20日，星期六2.3.1

单纯形表单纯形法的具体步骤：（一）确定初始基可行解在L.P问题的标准型：中，不妨设B是一个可行基，于是A=（B,N)

不失一般性假定B=（P1,…,Pm),基变量XB=（x1,…,xm)T

N

=(Pm+1,…,Pn),非基变量XN=（xm+1,…,xn)T.则

X=〔XB,XN〕T相应有C=(CB,CN)第5页，共23页，2023年，2月20日，星期六于是，原问题化为：第6页，共23页，2023年，2月20日，星期六初始基可行解oI第7页，共23页，2023年，2月20日，星期六检验数第8页，共23页，2023年，2月20日，星期六为什么？第9页，共23页，2023年，2月20日，星期六。

对上面分析过程进行总结：（1）在标准型中，找一个单位基矩阵并求出该基对应的基可行解。当L.P问题的约束条件全部为“≤”时，在变换为标准型的过程引进松驰变量，就自然得到了一个单位矩阵----初始可行基和初始基可行解。（2）检验该基可行解是否最优？通过非基变量的检验数。（3）若不是最优，则另找一个基产生一个基可行解-----换基迭代。直到最优。对此原理，我们可以通过单纯形表来实现。第10页，共23页，2023年，2月20日，星期六单纯形表第11页，共23页，2023年，2月20日，星期六说明1、表中基变量所在位置并不一定正好在前m个位置上，但总可以通过调换重新排成上表形式。2、表中最下一行称为检验数行，对应于非基变量的检验数为：（用于检验是否还须继续迭代）3、不难看出，基变量的检验数均为0第12页，共23页，2023年，2月20日，星期六2.3.2单纯形法的步骤引例：解L.P问题第13页，共23页，2023年，2月20日，星期六第一步：把模型化为标准形式后找出初始可行基，建立初始单纯形表（见下表）。本例中取初始基B1=(P3,P4)=I,则

cj

4300CBXB

b

x1x2x3x400

x3

x42426

23103201

Z0

4300第14页，共23页，2023年，2月20日，星期六

cj

4300CBXB

b

x1x2x3x400

x3

x42426

23103201

Z0

4300由表得基可行解:第15页，共23页，2023年，2月20日，星期六（二）最优检验第16页，共23页，2023年，2月20日，星期六第三步：换基迭代第17页，共23页，2023年，2月20日，星期六

第18页，共23页，2023年，2月20日，星期六

cj

4300CBXBb

x1x2x3x400x3x42426

2310

[3]2011226/3

Z

0

430004x3x120/326/3

0[5/3]1-2/312/301/3413

Z104/3

01/30-4/334x2x1

46

013/5-2/510-2/53/5

Z36

00-1/5-6/5第19页，共23页，2023年，2月20日，星期六

1.上第一表中,x1为换入变量；又由于比值=min(24/2，26/3）=26/3,确定x4为换出变量.x1所在列和x4所在行的交叉处为主元。进行迭代后，X(2)=(26/3,0,20/3,0)T，目标函数值为Z（2）=104/3，但不是最优值。

2.第二次迭代x2为换入变量，x3为换出变量。进行迭代后，X(1)=(6，4，0，0)T,因最后一行的所有检验数都已是正数或零，因此目标函数值为Z*=Z（3）=36是最优值。第20页，共23页，2023年，2月20日，星期六第21页，共23页，2023年，2月20日，星期六

cj

31000CBXBb

x1x2x3x4x5000x3X4x54218

11100-11010

[6]20014-3

Z

0

31000003x3X4x1153

02/310-1/604/3011/611/3001/6

Z9

0000-1/2

第22页，共23页，2023年，2月20日，星期六

该问题的最