线性规划解概念和单纯形法详解演示文稿

线性规划解概念和单纯形法详解演示文稿目前一页\总数五十五页\编于九点1（优选）线性规划解概念和单纯形法目前二页\总数五十五页\编于九点2解的解析Maxz=2x1

+3x2+0x3+0x4+0x5s.t.2x1+2x2

+

x3

=12(A)4x1+x4

=16(B)5x2

+x5=15(C)

x1,x2，x3，x4，x5

≥0(D,E)目前三页\总数五十五页\编于九点3解的解析可行解满足上述约束条件(A)、(B)、（C)的解x=(x1,x2，x3，x4，x5

)T称为线性规划问题的可行解，全部可行解的集合成为可行域。最优解

是目标函数z=15达到最大值的可行解x=(3

,3，0，4，0)T成为最优解。目前四页\总数五十五页\编于九点4解的解析基设A为约束方程组3*5阶系数矩阵

P1

P2

P3

P4

P5

22100A=4001005001设B=(P3

P4

P5)目前五页\总数五十五页\编于九点5A中其秩为3,B是A矩阵中的一个3阶的满秩矩阵,称B是线性规划问题的一个基，B中的每一个列向量(如P3

P4

P5)称为基向量，与基向量对应的变量称为基变量，线性规划中除基变量以外的其他变量称为非基变量。目前六页\总数五十五页\编于九点6解的解析基解在约束方程组中，令所有非基变量为0,又因为有B行列式不为0，由各约束方程可解出各基变量的唯一解。将这个解加上非基变量取0的值称为线性规划问题的基解，显然，在基解中变量取非零值的个数不大于方程数，基解的总数不超过20个。目前七页\总数五十五页\编于九点7解的解析基可行解满足变量非负约束条件的基解称为基可行解。可行基对应与基可行解的基成为可行基。目前八页\总数五十五页\编于九点8(回顾)例2.1问题：工厂应如何安排生产可获得最大的总利润？用图解法求解。解：设变量xi为第i种（甲、乙）产品的生产件数（i＝1，2）。根据前面分析，可以建立如下的线性规划模型：Maxz=1500x1+2500x2s.t.3x1+2x2≤65(A)2x1+x2≤40(B)3x2≤75(C)

x1,x2≥0(D,E)目前九页\总数五十五页\编于九点9

图解法求解线性规划102030405010203040OZ=0Z=25000A（5,25）B（15,10）C（20,0）D（0,25）E(0,0)目前十页\总数五十五页\编于九点10

(线性规划的基、基本解与基本可行解)

在一般情况下，由于图解法无法解决三个变量以上的线性规划问题，对于n个变量的线性规划问题，我们必须用解方程的办法来求得可行域的极点。再来进一步考察前例。例2.8把例2.1的线性规划模型标准化，引入松驰变量x3，x4，x5

≥0，得到目前十一页\总数五十五页\编于九点11Maxz=1500x1

+2500x2

s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75

x1

,x2

,x3,x4

,x5

≥0可见：等式约束条件的系数矩阵为目前十二页\总数五十五页\编于九点12从其中取出不同的三列出来，有C53=10种取法目前十三页\总数五十五页\编于九点13其中B1对应的基变量为x1,x2,x3，非基变量为x4,x5

令非基变量x4=0,x5=0，则得对应方程组3x1+2x2+x3=652x1+x2=403x2=75得对应基本解该10个方阵中除B4外，其余均为满秩矩阵，故均为线性规划的基。x(1)=(7.5,25,-7.5,0,0)T类似，可得所有基本解为目前十四页\总数五十五页\编于九点14X(3）=(15,10,0,0,45)TX(2)=(5,25,0,5,0)TX(9)=(0,32.5,0,7.5,-22.5)TX(6）=(65/3,0,0,-10/3,75)TX(1)=(7.5,25,-7.5,0,0)TX(8)=(0,40,-15,0,-45)T

X(5）=(20,0,5,0,75)T

X(10)=(0,0,65,40,75)T

X(7）=(0,25,15,15,0)T不是可行解是可行解,对应顶点A是可行解,对应顶点B是可行解,对应顶点C不是可行解不是可行解不是可行解是可行解,对应顶点D是可行解,对应顶点E目前十五页\总数五十五页\编于九点15

图解法求解线性规划102030405010203040OZ=0Z=25000A（5,25）B（15,10）C（20,0）D（0,25）E(0,0)目前十六页\总数五十五页\编于九点16上图各约束直线的交点是由以下方法得到：在标准化的等式约束中，令其中的非基变量为零，求出其他基变量的唯一解，得LP问题的基解

(x1,x2,x3,x4,x5)T,若其分量全为非负，则该解称为基可行解,对应于线性规划可行域的一个极点（顶点）；若基解中至少有一个分量为负值则该交点不是可行域的极点。2.线性规划解的概念

目前十七页\总数五十五页\编于九点17下面讨论线性规划标准形式的基、基本解、基本可行解的概念。考虑线性规划标准形式的约束条件：

Ax=b，x≥0其中A为m×n的矩阵，n>m，秩(A)

=m，b

Rm

。在约束等式中，令n维空间的解向量：

x=(x1，x2，…，xn)T2.线性规划解的概念

（1）线性规划的基：对于线性规划的约束条件

Ax=b，x≥0

目前十八页\总数五十五页\编于九点18设B是A矩阵中的一个非奇异（满秩）的m×m子矩阵，则称B为线性规划的一个基。用前文的记号，A=(p1，p2，…，pn)，其中pj=(a1j，a2j，…，amj)T

Rm

，任取A中的m个线性无关列向量pj

Rm

构成矩阵B=(pj1，pj2，…，pjm)。那么B为线性规划的一个基。我们称对应于基B的变量xj1，xj2，…，xjm为基变量；而其他变量称为非基变量。2.线性规划解的概念

目前十九页\总数五十五页\编于九点19可以用矩阵来描述这些概念。设B是线性规划的一个基，则A可以表示为

A=[B,N

]

x也可相应地分成

xBx=xN其中xB为m维列向量，它的各分量称为基变量，与基B的列向量对应；xN为n-m列向量，它的各分量称为非基变量，与非基矩阵N的列向量对应。

2.线性规划解的概念目前二十页\总数五十五页\编于九点20（2）线性规划问题的基本解、基本可行解和可行基：对于线性规划问题，设矩阵B=(pj1，pj2，…，pjm)为一个基，令所有非基变量为零，可以得到m个关于基变量xj1，xj2，…，xjm的线性方程，解这个线性方程组得到基变量的值。我们称这个解为一个基本解；若得到的基变量的值均非负，则称为基本可行解，同时称这个基B为可行基。2.线性规划解的概念

目前二十一页\总数五十五页\编于九点21矩阵描述为，对于线性规划的解

xB

B-1b

x==

xN0

称为线性规划与基B对应的基本解。若其中B-1b0，则称以上的基本解为一基本可行解，相应的基B称为可行基。

2.线性规划解的概念目前二十二页\总数五十五页\编于九点22

我们可以证明以下结论：线性规划的基本可行解就是可行域的极点。这个结论被称为线性规划的基本定理，它的重要性在于把可行域的极点这一几何概念与基本可行解这一代数概念联系起来，因而可以通过求基本可行解的线性代数的方法来得到可行域的一切极点，从而有可能进一步获得最优极点。2.线性规划解的概念

目前二十三页\总数五十五页\编于九点23利用求解线性规划问题基本可行解（极点）的方法来求解较大规模的问题是不可行的。单纯形法的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点（要求新极点的目标函数值不比原目标函数值差）。

3.单纯形法目前二十四页\总数五十五页\编于九点243.单纯形法初始基本可行解是否最优解或无限最优解?结束沿边界找新的基本可行解NY单纯形法的基本过程目前二十五页\总数五十五页\编于九点25需要解决的三个问题：（1）如何找到一个初始的基本可行解。（2）如何判别当前的基本可行解是否已达到了最优解。（3）若当前解不是最优解，如何去寻找一个改善了的基本可行解。单纯型原理是由美国数学家丹齐格（G.B.Danzig）在1947年为研究美国空军资源的优化配置时提出的一种方法。目前二十六页\总数五十五页\编于九点26下面举例说明单纯型法的思想maxz=2x1+x2

(4.1)maxz=2x1+x2例：maxz=2x1+x2目前二十七页\总数五十五页\编于九点27将上式标准化为为基变量，将基变量用非基变量表示为

取令非基变量x1=0,令非基变量等于0，得到一个基本可行解目前二十八页\总数五十五页\编于九点28我们想让x1从非基变量转为基变量，今后我们称之为进基。因基变量只有三个，因此必须从原有的基x3，x4，x5，中选一个离开基转为非基变量。下解决两个问题：1)x1应取多大的值？2)x1进基，x3，x4，x5那一个出基？现在，还是非基变量，仍取零值。

现在，还是非基变量，仍取零值。

x1要增加，x3，x4，x5

≥0。

==4=最小比值规则目前二十九页\总数五十五页\编于九点29把以上的运算制成一张表格，称单纯型表。

0

21000

基b

0150240505100[6]201011001

5

21000X1进基，x4出基。目前三十页\总数五十五页\编于九点30

0

21000

基b

01524010510012/601/6004/60-1/61

3123/2

01/30-1/30想一想：下一步应选哪个变量进基，又选哪个变量出基呢？下一步的单纯形表又怎样列呢？目前三十一页\总数五十五页\编于九点31

0

21000

基b0

15/227/213/2

0015/4-15/21001/4-1/2010-1/43/2

000-1/4-1/2

由上表得该LP问题的最优解为：2X=(7/2,3/2,15/2,0,0)T,maxz=17/2目前三十二页\总数五十五页\编于九点32考虑标准形式的线性规划问题：Maxz=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2

...

am1x1+am2x2+…+amnxn

=bm

x1,x2,…,

xn

≥0

x1

c1

b1

a11a12..a1n

x2

c2

b2

a21a22..a2nX=.C=

.

B=.A=

.........

xn

cn

bn

am1am2..amn

3.单纯形法Maxz=CXs.t.AX=bX≥0目前三十三页\总数五十五页\编于九点33这里，矩阵A表示为：A=(p1，p2，…，pn)，若找到一个可行基，无防设B=(p1，p2，…，pm)，则m个基变量为x1,x2,…,xm，n-m个非基变量为xm+1，xm+2，…，xn。通过运算，所有的基变量都可以用非基变量来表示：3.单纯形法目前三十四页\总数五十五页\编于九点34

x1=b’1-（a’1m+1xm+1+a’1m+2xm+2+…+a’1nxn）

x2=b’2-（a’2m+1xm+1+a’2m+2xm+2+…+a’2nxn）(2-11).`..

xm=b’m-（a’mm+1xm+1+a’mm+2xm+2+…+a’mnxn）

把它们代入目标函数，得

z=z’+m+1xm+1+m+2xm+2+…+nxn

(2-12)其中

j=cj-（c1a’1j+c2a’2j+…+cma’mj）

我们把由非基变量表示的目标函数形式称为基B相应的目标函数形式。3.单纯形法目前三十五页\总数五十五页\编于九点353、单纯形法表格单纯形法考虑：bi>0i=1,…,m

Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn

≤b1

a21x1+a22x2+…+a2nxn

≤b2…………

am1x1+am2x2+…+amnxn

≤bm

x1，x2，…，xn≥0目前三十六页\总数五十五页\编于九点363、单纯形法加入松弛变量：Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn+xn+1=b1

a21x1+a22x2+…+a2nxn+xn+2=b2…………

am1x1+am2x2+…+amnxn+xn+m=bm

x1，x2，…，xn，xn+1，…，xn+m≥0目前三十七页\总数五十五页\编于九点37显然，xj=0j=1,…,n;

xn+i=bii=1,…,m是基本可行解

对应的基是单位矩阵。以下是初始单纯形表：

mm其中：f=∑cn+ibi

j=cj-∑cn+iaij为检验数cn+i

=0i=1,…,m

i=1i=1an+i,i=1,an+i,j=0(j≠i)i,j=1,…,m为约束方程系数3、单纯形法b价值系数方程组右侧常数比率计算值目前三十八页\总数五十五页\编于九点383、单纯形法表格单纯形法的计算步骤（1）找出初始可行基，确定初始基可行解，建立初始单纯形表；（2）检验各非基变量的检验数，若所有σj≤0，则已达最优解，停止计算；否则，转入下一步；（3）若有某个σj>0，其对应系数列向量≤0，则此问题是无界解，停止计算；否则，转入下一步；（4）决定换入和换出基变量；（5）用矩阵的初等行变换法将xk所对应的列向量变换为（0，0，…，1，…，0）T，换入新的基变量，得到新的单纯形表，返回步骤（2）。目前三十九页\总数五十五页\编于九点39例2.10：用单纯形法的基本思路解例2.8的线性规划问题

Maxz=1500x1

+2500x2

s.t.3x1

+2x2

+x3

=652x1

+x2

+x4=403x2

+x5

=75

x1,x2,x3,x4,x5

≥03.单纯形法目前四十页\总数五十五页\编于九点40解列出单纯形表并进行单纯形变换

最优解x1=5x2=25x4=5（松弛标量，表示B设备有5个机时的剩余）最优值z*=700003、单纯形法目前四十一页\总数五十五页\编于九点41注意：单纯形法中，1、每一步运算只能用矩阵初等行变换；2、表中第三列（b列）的数总应保持非负（≥0）；3、当所有检验数均非正（≤0）时，得到最优单纯形表。当所有非基变量的检验数均<0,则相应的最优解是唯一的。3、单纯形法

目前四十二页\总数五十五页\编于九点424.单纯形法的进一步讨论4.1大M法：引入人工变量xn+i

≥0（i=1,…,m）及充分大正数M。得到：Max

z=c1x1+c2x2+…+cnxn-Mxn+1-…-Mxn+m

s.t.

a11x1+a12x2+…+a1nxn

+xn+1

=b1a21x1+a22x2+…+a2nxn+xn+2=b2...am1x1+am2x2+…+amnxn+xn+m=bm

x1，x2，…，xn，xn+1，…，xn+m

≥0对于规模较大的问题，用试算的方法取得初始基可行解很困难，必须有一个初始可行基的系统化方法。目前四十三页\总数五十五页\编于九点43显然，xj=0j=1,…,n;

xn+i=bi

i=1,…,m

是基本可行解。对应的基是单位矩阵。结论：由于

Max

z=c1x1+c2x2+…+cnxn-Mxn+1-…-Mxn+m则若得到的最优解满足

xn+i=0

i=1,…,m则是原问题的最优解；否则，原问题无可行解。4.单纯形法的进一步讨论目前四十四页\总数五十五页\编于九点44例2.11：（LP）Maxz=5x1

+2x2

+3x3

-x4

s.t.x1+

2x2+

3x3=152x1

+x2

+5x3=20

x1

+2x2

+4x3

+x4

=26

x1

,x2

,x3

,x4

≥04.单纯形法的进一步讨论目前四十五页\总数五十五页\编于九点45

Max

z=5x1+2x2+3x3-x4-Mx5-Mx6

s.t.

x1+2x2+3x3+x5

=152x1+x2+5x3+x6=20

x1+2x2+4x3+x4

=26

x1,x2,x3,x4,x5,x6

≥0大M法问题(LP-M）4.单纯形法的进一步讨论目前四十六页\总数五十五页\编于九点46大M法

（LP-M）

得到最优解：(25/3，10/3，0，11)T

最优目标值：112/34.单纯形法的进一步讨论目前四十七页\总数五十五页\编于九点47

4.2

两阶段法：

引入人工变量xn+i

≥0，i=1,…,m；

构造:Maxz=-xn+1

-xn+2

-…-xn+m

s.t.

a11x1+a12x2+…+a1nxn+xn+1

=b1

a21x1+a22x2+…+a2nxn+xn+2

=b2

...

am1x1+am2x2+…+amnxn+xn+m

=bmx1,x2...

xn,xn+1,…,xn+m

≥04.单纯形法的进一步讨论目前四十八页\总数五十五页\编于九点48第一阶段求解上述问题：显然，xj=0j=1,…,n;

xn+i=bi

i=1,…,m是基本可行解,它对应的基是单位矩阵。结论：若得到的最优解满足xn+i=0

i=1,…,m则是原问题的基本可行解;否则，原问题无可行解。得到原问题的基本可行解后，第二阶段求解原问题。目前四十九页\总数五十五页\