第二章+线性规划课件

*第二章线性规划2.1线性规划模型2.2线性规划理论2.3线性规划的单纯形法2.4单纯形法的进一步讨论2.5改进的单纯形法*2.1线性规划模型

例:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：

产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）15002500

*

问题：工厂应如何安排生产可获得最大的总利润？解：设变量xi为第i种（甲、乙）产品的生产件数（i＝1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3x1

+2x2

≤65；对设备B，两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2x1

+x2

≤40；2.1线性规划模型*

对设备C，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2

≤75；另外，产品数不可能为负，即x1,x2≥0。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500x1+2500x2

。综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：2.1线性规划模型*目标函数Maxz=1500x1+2500x2

约束条件s.t.3x1+2x2≤652x1+x2≤403x2≤75

x1,x2≥0

2.1线性规划模型*

这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subjectto”的缩写，表示“满足于……”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1,x2

的取值。它是一个目标函数、约束函数都是线性函数的最优化问题，即线性规划问题。2.1线性规划模型*一般形式

目标函数：Min(Max)z=c1x1

+c2x2

+…+cnxn

约束条件：

a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2

...am1x1+am2x2

+…+amnxn≤(=,≥)bm

x1，x2，…

，xn≥02.1线性规划模型*标准形式目标函数：Minz=c1x1+c2x2+…

+cnxn

约束条件：a11x1+a12x2+

…

+a1nxn

=

b1a21x1+a22x2+…

+a2nxn

=b2

...am1x1+am2x2+…+amnxn

=bm

x1，x2，…

，xn

≥02.1线性规划模型*

可以看出，线性规划的标准形式有如下四个特点：目标最小化、约束为等式、决策变量均非负、右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:2.1线性规划模型*1.极大化目标函数的问题：设目标函数为

Maxf=c1x1

+c2x2

+…+cnxn

则可以令z

＝-f

，该极大化问题与下面的极小化问题有相同的最优解，即

Maxz=-c1x1

-c2x2-…-cnxn

但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即

Minz

＝-Maxf2.1线性规划模型*2、约束条件不是等式的问题：设约束条件为

ai1x1+ai2x2+…+ainxn

≤bi

可以引进一个新的变量s

，使它等于约束右边与左边之差

s=bi–(ai1x1

+ai2x2

+…+ainxn

)

显然，s

也具有非负约束，即s≥0，这时新的约束条件成为

ai1x1+ai2x2+…+ainxn+s=bi2.1线性规划模型*

当约束条件为

ai1x1+ai2x2+

…

+ainxn

≥bi

时，类似地令

s=(ai1x1+ai2x2+…+ainxn)-bi

显然，s

也具有非负约束，即s≥0，这时新的约束条件成为

ai1x1+ai2x2+…+ainxn-s=bi

2.1线性规划模型*

为了使约束由不等式成为等式而引进的变量s称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。

2.1线性规划模型*

例2.2：将以下线性规划问题转化为标准形式

Maxf=3.6x1

-5.2x2+1.8x3s.t.2.3x1

+5.2x2-6.1x3

≤15.74.1x1

+3.3x3

≥8.9

x1

+x2+x3

=38

x1

,x2,x3≥0

2.1线性规划模型解：首先,将目标函数转换成极小化：令z=-f=-3.6x1+5.2x2-1.8x3

*其次考虑约束，有2个不等式约束，引进松弛变量x4，x5

≥0。于是，我们可以得到以下标准形式的线性规划问题：

Minz=-3.6x1

+5.2x2-1.8x3s.t.2.3x1+5.2x2-6.1x3+x4=15.74.1x1+3.3x3-x5=8.9

x1+x2+x3=38

x1,x2,x3,x4,x5

≥02.1线性规划模型*3.变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令

xj=xj’-xj”其中

xj’≥0，xj”≥0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj’和xj”的大小。2.1线性规划模型*4.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi<0，则把该等式约束两端同时乘以-1，得到：-ai1x1-ai2x2-…-ainxn

=-bi

。2.1线性规划模型*例2.3：将以下线性规划问题转化为标准形式Maxf=-3x1

+5x2+8x3

-7x4s.t.2x1

-3x2+5x3+6x4

≤284x1

+2x2+3x3-9x4

≥396x2+2x3+3x4≤-58

x1,x3,x4

≥02.1线性规划模型*解：首先，将目标函数转换成极小化：令z=-f=3x1–5x2–8x3+7x4

；其次考虑约束，有3个不等式约束，引进松弛变量x5,x6,x7

≥0；由于x2无非负限制，可令x2=x2’-x2”,其中 x2’≥0，x2”≥0；由于第3个约束右端项系数为-58，于是把该式两端乘以-1。于是，我们可以得到以下标准形式的线性规划问题：2.1线性规划模型*Minz=3x1–5x2’+5x2”–8x3+7x4s.t.2x1–3x2’+3x2”+5x3+6x4+x5=284x1+2x2’-2x2”+3x3-9x4-x6=39-6x2’+6x2”-2x3-3x4-x7

=58

x1,x2’,x2”,x3,x4,x5,x6,x7

≥0

2.1线性规划模型*2.2线性规划的理论线性规划的标准形式：

MincTx(LP)s.t.Ax=b

x≥0其中,c,x

Rn

；

b

Rm；

A为

mn

矩阵*线性规划问题解的基本概念可行解:{x|Ax=b,

x≥0}最优解:使目标函数取最优的可行解基，基变量，非基变量：若B=[P1P2…Pm]为A的一个m阶可逆矩阵，则称B为一个基或基矩阵，对应的x1,…,xm称为基变量，剩余的n-m个变量称为非基变量。A=[BN]基本解:非基变量为0时，满足约束Ax=b的解。基本解至少有n-m个分量为0，至多有m个非零分量非零分量的个数少于m时，称为退化的基本解基本解的个数最多有C(n,m)=n!/(m!(n-m)!)基本可行解：还满足非负约束x≥0的基本解。基本可行解的个数至多为C(n,m)=n!/(m!(n-m)!)最优基本可行解：使目标函数取最优的基本可行解*线性规划问题解的基本概念*线性规划问题的性质解的存在性：若(LP)的可行域非空，则可行域是个凸集，且(LP)一定存在有限最优解或无界最优解解在顶点的可达性：若(LP)存在有限最优解，则最优解可在某个顶点处达到顶点与基本可行解的关系：x0是(LP)的可行域顶点的充分必要条件是x0是(LP)的基本可行解→可通过求基本可行解得到有限最优解*2.3线性规划的单纯形法一、引例：*2.3线性规划的单纯形法解：转换为标准型：*2.3线性规划的单纯形法（1）求一个初始基本可行解*2.3线性规划的单纯形法（2）求一个改进的基本可行解*（2）求一个改进的基本可行解（续）*2.3线性规划的单纯形法（3）继续上述过程直到非基变量的检验数都为非正（或目标函数不能再减少）*2.3线性规划的单纯形法定理：考虑(LP),设x

为其一个基本可行解，A=[B,N]，其中B为m阶非奇异矩阵，使xT=[xBT,xNT],这里xB=B-1b≥0,xN=0，相应地cT=[cBT,cNT]

。那么，

1）若对任意的j，非基变量检验数j≤0,则

x

是最优解.特别地，若还存在某个j，使j=0，则（LP）有无穷多个最优解.2）若存在j，j>0,且B-1pj≤0,则(LP)无有限最优解.二、最优解的判断*三、单纯形法的计算步骤初始基本可行解是否最优解或无限最优解?结束沿边界找新的基本可行解NY*（1）确定一个初始基本可行解:A=[B,N]，xT=[xBT,xNT],cT=[cBT,cNT],

f=cBT

xB.这里xB=B-1b≥0,xN=0.（2）计算非基变量检验数=cNT-cBTB-1N,根据最优解判别定理，判断

x

是否为最优解.若是，则停止，否则转下一步.（3）求一改进的基本可行解

1)确定换入变量:k=max{j|j∈NI},相应的xk为换入变量. 2)确定换出变量:按θ规则计算

θ=min{i/aik|aik

>0}=r/ark

以xr为换出变量.这里=B-1b,ak=B-1pk3)用pk代替pBr,得到新的基矩阵B,并将B变换为单位矩阵:

以ark为主元素进行迭代(即用高斯消去法)把 pk=(a1k…ark…

amk)T变为(0…1

…0)T.（4）重复（2）、（3）直到得到最优解.三、单纯形法的计算步骤（续）*四、单纯形表：设x

为初始基本可行解,相应分解A=[B,N]minfs.t.f-cBTxB-cNTxN=0

BxB+NxN=b

xB,

xN≥0minfs.t.f-0

xB+(cBTB-1N-cNT)xN=cBTB-1b

xB+B-1NxN=B-1b

xB,

xN≥0

检验数*

检验数fxBTxNTRHS目标行10TcBTB-1N-cNTcBTB-1

b1行

xB0IB-1NB-1bM行1列m列n-m列1列作变换，使前m+1列对应的m+1阶矩阵变为单位矩阵,得：fxBTxNTRHS目标行1-cBT-cNT01行约束行0BNbM行1列m列n-m列1列*fx1x2x3x4x5RHSf1250000x30121008x40100104x50010013引例的单纯型表：换入变量：x2，因为max{2,5}=5换出变量：x5,因为min{8/2,3/1}=3*fx1x2x3x4x5RHSf12000-5-15x301010-22x40100104x20010013fx1x2x3x4x5RHSf100-20-1-19x101010-22x4000-1122x20010013最优解x*=(2,3,0,2,0)T,f*=-19*2.4单纯形法的进一步讨论初始基本可行解的确定退化情形的处理*初始基本可行解的确定当初始基本可行解不能通过观察法很容易得到时，如何确定初始基本可行解？*初始基本可行解的确定带来的问题：人工变量的引入，改变了原问题的约束条件，得到的是与原问题不同的新问题，而新问题的最优解不一定是原问题的最优解（除非新问题的最优解正好人工变量都为零）.（人工变量是“非法”的变量，松弛变量是“合法”的变量）解决方法：大M法两阶段法*大M法若(x,0)T是DMLP的有限最优解，则x是LP的