运筹学单纯形法

关于运筹学单纯形法基向量、非基向量、基变量、非基变量：

称pj(j=1,2,…,m）为基向量，其余称为非基向量； 与基向量pj(j=1,2,…,m）对应的xj称为基变量，其全体写成XB=（x1，x2，…，xm）T；否则称为非基变量，其全体经常写成XN。基解：对给定基B,设XB是对应于这个基的基变量

XB=(x1，x2，…，xm)T；

令非基变量xm+1=xm+2=…=xn=0，由（2）式得出的解X=（x1，x2，…，xm，0，…，0）T

称为基解。基可行解：所有决策变量满足非负条件(xj≥0)的基解,

称作基可行解。可行基：基可行解所对应的基底称为可行基。第2页,共48页，星期六，2024年，5月写出下述线性规划问题对应的基、基变量、基解、基可行解和可行基。第3页,共48页，星期六，2024年，5月定理2：X是线性规划问题的基可行解的充要条件是它对应于可行域D的顶点。（线性规划问题的基可行解X对应于可行域D的顶点。）定理3：若可行域有界,线性规划问题的目标函数一定可以在其可行域的顶点上达到最优.第4页,共48页，星期六，2024年，5月§3单纯形法（SimplexMethod）例子：求解线性规划问题线性规划问题的最优解，可以从基可行解中找到

图解法有局限性；

枚举法计算量大；§3.1单纯形法的引入0Q4Q31123234Q2Q1X1X2x1+2x2=84x1=164x2=12第5页,共48页，星期六，2024年，5月解:

首先:将该问题化成标准形第二:

找初始可行解(即一个顶点)。系数矩阵A=(p1p2p3p4p5)矩阵形式第6页,共48页，星期六，2024年，5月

因为p3，p4，

p5线性独立，故B=(p3,p4,p5)构成一个基底，对应的基变量x3，x4，x5解出来为（用非基变量表示基变量）

x3=8-x1-2x2x4=16-4x1(a)x5=12-4x2

将(a)代入目标函数中得z=0+2x1+3x2令非基底变量x1=x2=0，则有z=0。这时得到一个基可行解X(0)=(0,0,8,16,12)T---原点第三:判别从目标函数中得知，非基底变量的系数为正，因此，将非基变量换入基底后可使目标函数增大，转入第四步第7页,共48页，星期六，2024年，5月第四:换基底(旋转迭代)

确定换入变量：由于z=0+2x1+3x2

中非基底变量x2系数贡献最大3，故换入基底为x2。换入变量已定，必须从x3，x4，x5换出一个，并且要保证其余均是非负的，即x3，x4，x50。

x3=8-2x2

0

x4=160

x5=12-4x20

由此，只要选择x2=min(8/2，-，12/4)=3，对应基底变量x5=0，从而确定用x2和x5对调，即将x5

换出。有

x3

=2-x1+1/2x5

x4=16-4x1(b)x2=3-1/4x5

第8页,共48页，星期六，2024年，5月

将(b)代入目标函数中得z=9+2x1-3/4x5

令非基变量为零，又得到另一个基可行解

X(1)=(0,3,2,16,0)T–顶点Q4

返回第三步：非基变量x1的系数是正的，还可增大，X(1)

不是最优解。重复上述步骤。由于x1的系数是正的，从而x1为转入变量，再由x3=2-x1

0

x4=16-4x1

0

x2=30

第9页,共48页，星期六，2024年，5月只要选

x1=min{2，16/4，-}=2上式就成立，因为x1=2时，基变量x3=0，从而由x1换出x3，得

x1=2-x3+1/2x5

4x1+x4=16

(c)x2=3-1/4x5高斯消去法（行变换）得

x1=2-x3+1/2x5

x4=8-2x5+4x3x2=3-1/4x5

第10页,共48页，星期六，2024年，5月代入目标函数中，得

z=13-2x3+1/4x5令非基变量x3=x5=0，又得到另一个基可行解X(2)X(2)=(2,3,0,8,0)T–新顶点Q3

同理，返回第三步，再迭代，x5作为转入变量

x1=2+1/2x5

0

x4=8-2x50

x2=3-1/4x5

0

第11页,共48页，星期六，2024年，5月只要取x5=min{-，8/2，12}=4就有上式成立。x5=4时，x4=0，故决定用x5换x4x1=4-1/4x4

x5=4-1/2x4+2x3x2=2+1/8x4–1/2x3

代入得z=14-3/2x3–1/8x4

，令x3，x4=0得z=14。新基可行解为

X(3)=(4,2,0,0,4)T–为最优解，新顶点Q2最优目标值z=14。第12页,共48页，星期六，2024年，5月从实际例子中分析单纯形法原理的基本框架为

第一步：将线性规划模型变换成标准型，确定一个初始可行解（顶点）。

第二步：对初始基可行解最优性判别，若最优，停止；否则转下一步。

第三步：从初始基可行解向相邻的基可行解（顶点）转换，且使目标值有所改善—目标函数值增加，重复第二和第三步直到找到最优解。第13页,共48页，星期六，2024年，5月§3.2初始可行基的确定设线性规划问题：第14页,共48页，星期六，2024年，5月

为了确定初始基可行解，首先要找出初始可行基，其方法如下：从Pj(j=1,2,…,n)中一般能直接观察到存在一个初始可行基

确定初始可行基的几种方法：

形式的不等式

形式的不等式=的情形观察“小加大减+人造”第15页,共48页，星期六，2024年，5月

约束是≤形式的不等式，可以利用化标准型的方法，左端加一个松弛变量，经过整理，重新对xj及aij（i=1,2,…,m；j=1，2，…，n）进行调整编号，则可得下列方程组“小加”第16页,共48页，星期六，2024年，5月x1+a1,m+1xm+1+…+a1nxn=b1x2+a2,m+1xm+1+…+a2nxn=b2

……

xm+am,m+1xm+1+…+amnxn=bmxj≥0，j=1,2,…,n显然得到一个m×m单位矩阵注意：aij和bi已经变化第17页,共48页，星期六，2024年，5月移项整理得

x1=b1-a1,m+1xm+1-…-a1nxn

x2=b2–a2,m+1xm+1-…-a2nxn

……

xm=bm–am,m+1xm+1-…-amnxn

令xm+1=xm+2=…=xn=0，可得

xi=bi

（i=1，2，…，m）

又因bi≥0，所以得到一个初始基可行解：

X（0）=（x1x2…

xm0…0)T

=(b1b2…

bm0…0)T第18页,共48页，星期六，2024年，5月非基向量可以用基向量的线性组合表示将(3)式乘以一个正的数

>0,得到记初始基可行解为X(0),有该解满足约束方程,即§3.3从初始基可行解转换为另一基可行解第19页,共48页，星期六，2024年，5月(4)式和(1)式相加,整理后得到由(5)式可以找到满足约束方程的另一个点X(1),其中是点X(1)的第j个坐标值第20页,共48页，星期六，2024年，5月要使X(1)是一个基本可行解,则要求并且这m个等式中至少要有一个等号成立当时,(6)式必然成立当时,令因此有所以X(1)中的正分量最多有m个,可证明m个向量P1,…,Ps-1,Ps+1,…,Pm,Pj线性无关,按照式(7)确定

值,X(1)就是一个新的基可行解.第21页,共48页，星期六，2024年，5月线性规划解的四种可能：1、有唯一解；2、无穷多最优解；3、无界解；4、无可行解。何时达最优解,何种最优解？§3.4

最优性检验和判别定理第22页,共48页，星期六，2024年，5月将基本可行解X(0)和X(1)分别代入目标函数得由此

j称做检验数,是对线性规划问题的解进行最优性检验的标志.第23页,共48页，星期六，2024年，5月最优解的判别定理：且对一切的j=m+1,...,n有则X(0)

为最优解。若是一个基可行解，第24页,共48页，星期六，2024年，5月无穷多最优解判别定理：若是一个基可行解，且对一切的j=m+1,...,n有又存在某个非基变量的检验数则线性规划问题有无穷多最优解。第25页,共48页，星期六，2024年，5月无界解的判别定理：第26页,共48页，星期六，2024年，5月§3.5基变换换入变量的确定:max(

j>0)=k,j=m+1,…,n;xk是换入变量(也可任选).换出变量的确定:

确定换出变量的原则是保持解的可行性,就是说要使原基可行解的某一正分量xs变成零,同时保持其它的分量均非负(换基原则)min(xi/aij|aij>0)=xs/asj=,s{1,2,…,m}(最小比值准则,或

准则)§3.6旋转运算在确定换入变量xk和换出变量xs以后，要把xk所对应的系数列向量pk变成单位向量，为此,只要对系数矩阵的增广阵进行“行”的初等变换即可。行变换的定义：第27页,共48页，星期六，2024年，5月(第s行)*1/ask得:当is时,(第i行)-(第s行)*aik第28页,共48页，星期六，2024年，5月经过初等变换后,新的增广矩阵是第29页,共48页，星期六，2024年，5月§4单纯形法的计算步骤和单纯形表约束方程组和目标函数组成n+1个变量,m+1个方程的方程组该方程组对应的增广矩阵是第30页,共48页，星期六，2024年，5月第31页,共48页，星期六，2024年，5月第32页,共48页，星期六，2024年，5月确定初始单纯形表后可以得到初始基可行解x0,

若有某个非基底变量xk对应的检验数

k=(ck-zk)>0,则当前解不是最优解，取使目标增长最大的非基底变量进入基底。根据确定xk为换入变量根据确定xs为换出变量将xk对应的列向量Pk=(a1k,,…,ask,…,ank)T变换为aik=0，is

aik=1，i=s重复上述步骤直到所有的检验数满足最优条件，得最优解。第33页,共48页，星期六，2024年，5月§5单纯形法的进一步讨论

人工变量法（确定初始可行基）：原约束方程：AX=b加入人工变量：xn+1，，xn+m

人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。第34页,共48页，星期六，2024年，5月1、大M法方法：在约束条件中，加入人工变量后，要求目标函数不受影响？目标函数中人工变量的系数取（-M）。理由：目标函数实现最大化，就必须将人工变量从基变量中换出，否则目标函数就不可能取得最大化。例1：用大M法求解如下线性规划问题第35页,共48页，星期六，2024年，5月111-211000113-4120-1103/21-20[1]000110M16xx4

x3103-20100-110[1]00-11-211-2010001-3x11x21x341001/3-2/32/3-5/310100-11-2900102/3–4/3-7/3

-31100

MM

-10001M-1M+1zj-cj

0001/31/3M-1/3M-2/3zj-cj0x41x21x312[3]001-22-5410100-11-21-2010001cj0MMX4X6X7

b

CBXBX1X2X3X4X5X6X7

i-3+6M1-M1-3M0M00cj-zj

-11-M00M03M-1cj-zj第36页,共48页，星期六，2024年，5月最优解是目标函数为-2。

第37页,共48页，星期六，2024年，5月2、两阶段法第一阶段：建立一个辅助线性规划并求解，以此判断原线性规划是否存在可行解。辅助线性规划问题：目标函数取成所有的人工变量之和，并对目标函数取极小化，约束条件依然为原问题的以单位矩阵作为可行基的标准型的约束条件。所有人工变量都变成非基变量，目标函数值为0，原问题存在基可行解。转到第二阶段。若目标函数值不为0，至少有一个人工变量不能从基变量中转出，原问题没有可行解。停止。第二阶段：从第一阶段最优表格中去掉人工变量，将目标函数系数换成原问题的目标函数系数，用单纯形法计算，直到得到最优解为止。第38页,共48页，星期六，2024年，5月第一阶段：求解辅助规划问题第39页,共48页，星期六，2024年，5月

111-211000113-4120-1103/21-20[1]000110106xx4

x3103-20100-110[1]00-11-211-2010001

00000

11

0000011zj-cj0x40x20x312[3]001-22-5410100-11-21-2010000cj011X4X6X7

b

CBXBX1X2X3X4X5X6X7

i6-1-30100cj-zj

0-100103cj-zj第40页,共48页，星期六，2024年，5月12[311-20100-3112xx1

x341001/3-2/310100-190012/3-4/3

-31100cj011X4X2X3

b

CBXBX1X2X3X4X5

i-10001cj-zj

0001/31/3cj-zjx6，x7是人工变量，第一阶段求解的最优结果是

=0，因此得最优解为：

第二阶段：取消人工