单纯形法基本原理及实例演示

格式：ppt
大小：2.81 MB
文档页数：35

下载文档原格式

单纯形法基本原理及实例演示

定理二：若某个基本可行解所对应的检验向量CN- CB B-1N存在一个检验数=0,则该问题有无数多个最优解。
定理三：若某个基本可行解所对应的检验向量Cj- CB B-1Nj大于0，且aij,都小于0，
则无解。
为了矩阵形求逆计算方便，一般将B 转化为单位矩阵。
2、单纯形法的计算步骤
①将线性规划问题化成标准型。
因为B为基, 故有 XB +B-1N XN = B-1b，解得可行解XB=B-1b-B-1NXN，代入目标函数Z， Z = CB B-1b + (CN- CB B-1N ) XN
令非基变量XN = 0 ，则有 XT = (XB , XN) T =（ B-1b , 0) T Z = CB B-1b
Z = CB B-1b + (CN- CB B-1N ) XN
比值
b bi ai 2
S1 0 1 1 1 0 0 300
S2 0 2 1 0 1 0 400
1 S3 0 0 1 0 0 1 250
Zj=CBNj
0 0 0 00
j c j z j 50 100 0
0
0
0 Z=
初始单纯形表
可行解XB=B-1b-B-1NXN>=0
x1 X2 s1 s2 S3
s2 S3 00 0 -1
比值
b bi ai 2
50
S2 0 2 0 0 1 -1 150
3 x2 100 0 1 0 0 1 250
Zj=CBNj
j cj zj
初始单纯形表
迭代基变次数量
CB
x1
x2
s1
50 100 0
x1 50 ①1 0 1

02-2单纯形法

(Ⅱ )
+ +x3 x2 +
5 2 x4
= 30 = 8 = 6
0 比值
1 x1
0 3 x1 z
-2x4 + x5 = 12 ③ 4 min
1 + 2x4 +x5 = 42 x3 + 2 x4 - 1 x5 = 4 3 3 1 + 2 x4 = 6 x4 + 1 x5 = 4 -2 3 3
1 2
x4
(2.1)
xn+1, xn+2, … , xn+m 称为人工变量。
初始基本可行解：( 人造基本解 )
X0 = ( 0, 0, … , 0, b1, b2, …, bm )T
n个
22
第2 章
单纯形法
2.3 人工变量法
基本思想：
人造解 X0 不是原LP问题的基本可行解。但若能通过单纯形法的迭代步骤，将虚拟的人工变量都替换出去，都变为非基变量（即人工变量xn+1 = xn+2 = … = xn+m = 0），则X0的前n个分量就构成原LP问题的一个基本可行解。
解
3 x1 1 0 3 -3 1 0 3 -3
5 x2 0 2 4 -5 0 1 0 0
0 x3 1 0 0 0 1 0 0 0
0 x4 0 1 0 0 0 1/2 -2 5/2
0 x5 0 0 1 0 0 0 1 0
比值
6 min 9 8
4 min
19
第2 章
单纯形法
2.2 单纯形法的计算过程 cj
基解
cj
cn xn
x1 1 0
┇
x2 … xm 0 … 1 …

第三节单纯形法

θi 32.5 40 25
5 7. 5
注意：单纯形法中，注意：单纯形法中， 1.每一步运算只能用矩阵初等行 1.每一步运算只能用矩阵初等行变换；变换； 2.表中第3列的数总应保持非负 2.表中第表中第3 （≥ 0）； 3.当所有检验数均非正（≤ 0） 3.当所有检验数均非正当所有检验数均非正（得到最优单纯形表。时，得到最优单纯形表。
8
1.初始单纯形表： 1.初始单纯形表：初始单纯形表
CB XB b b1 b2 ┇ bm f
m
cn+1 xn+1 cn+2 xn+2 ┇ ┇ cn+m xn+m m -z
c1 x1 a11 a21 ┇ am1 σ1
… … … … ┇ … …
cn xn a1n a2n ┇ amn σn
m
cn+1 xn+1 1 0 ┇ 0 m 0
-z
15
在最优单纯形表中，非基变量的检验数不在最优单纯形表中，是正数,于是得到最优解为X 是正数,于是得到最优解为X*=(15,10,0,0,45)T 最优目标值为z =32500。注意到非基变量x 最优目标值为z*=32500。注意到非基变量x4 的检验数是0 如果选x 为进基变量，的检验数是0，如果选x4为进基变量，迭代还可以进行下去，但是最优值不会增大，还可以进行下去，但是最优值不会增大，而只有最优解改变，这就是多解的情况。而只有最优解改变，这就是多解的情况。下面再迭代一步，如表2 所示。下面再迭代一步，如表2-9所示。
19
解：单纯形法求解过程如下表。单纯形法求解过程如下表。
CB XB
0 0 0 -z 7 0 0 -z x1 x6 x7 x5 x6 x7

单纯形法2(原理)

单纯形法原理

理论方法算法步骤

第1页
min z=6x1)+ x2=1
1
x2
s.t. 3x 4 x 1.5 1 2
x1 , x2 0
目标等值线：
作业讲评可行域
6x1+4x2 ＝3
6x1+4x2 ＝1 6x1+4x2 ＝0
最优解
最优解：x1 ＝0.5,x2=0 0 最优值：minz=3
X4 =190- 2X2 ≥0 X5 =240- 3X2 ≥0
b1 b2 b3 min( , , ) a12 a22 a32
选择X2=min(100/1,190/2,240/3)=80 方能同时满足以上三个约束
这时X5=0决定了应该用X2去换X5
第24页
实例
用非基变量表示基变量
X1+X2+X3 =100
第12页
实例 Max Z=1.5X1+2.4X2
X1+ X2 ≤100 3X1+2X2 ≤190 2X1+3X2 ≤240 X1 、X2 ≥0
不是标准型
第13页
实例
化成标准型
Max Z=1.5X1+2.4X2+0X3+0X4+0X5 X1+X2+X3 =100 3X1+2X2 +X4 =190 2X1+3X2 +X5 =240 X1 、X2、X3、X4、X5 ≥0
第26页
实例
求解
Z=192-0.1X1-0.8X5 X3 =20-1/3X1+1/5X5 X4 =30-5/3X1+2/3X5 X2 =80-2/3X1- 1/3X5

第三讲单纯形法

最优性检验和解的判别
将X (0)
( x10 ,
x20 ,,
x
0 m
,0,
,0)T
和
X (1) ( x10 -a1 j ,, xm0 amj ,0,,0)T
代入目标函数
m
z(0) ci xi0 i 1
m
z(1) ci ( xi0 aij ) c j i 1
m
m
ci
x
0 i
(c j
单纯形法引例4这样如此下去可得要有一个变为非基变量此时目标函数变为由于目标函数中的变量系数都小于等于0所以42004为最优解最优值z14标本无需切片处理而代之在标本表面涂上一层铂金当电子撞击标本表面各点时便产生次及电子呈现立体状态可观察标本的形状及表面的特征
第1章线性规划与单纯形法
第1节线性规划问题及其数学模型第2节线性规划问题的几何意义第3节单纯形法第4节单纯形法的计算步骤第5节单纯形法的进一步讨论第6节应用举例
1 0 1 0 -1/2
0 0 -4 1 2
0 1 0 0 1/4
0 0 -2
0 1/4
1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0
0 0 -3/2 -1/8 0
j
--8/2
3/(1/4)
单纯形法迭代原理：确定初始可行解
n
目标函数：max z c j x j j 1
令这m个不等式至少有一个等号成立。
可令
min i
xi0 aij
aij
0
xl0 alj
故X (1)是一个可行解，其分量xi1 xi0
aij

系统工程导论_09单纯形法

（1）
第三、第一次迭代，得到初始基本可行解后，就进入迭代过程，但在开始迭代前应建立一个判断标准，以便决定每次迭代后的基本可行解是否是最优解，从而决定迭代过程是停止还是继续。选取临近顶点，如果能使目标函数值增大，则为新的基础可行解。 1）选择引入变量：选大原则；考虑目标函数 f x 13x1 11x 2 ，由于 x1 的系数 13 比 x 2 的系数 11 大，故选 x1 为引入变量； 2）选择退出变量：最小比值规则（或规则）；
x3 1500 4 x1 41500 / 4 x1 4375 x1 由于 x 2 0 ，根据（1）有： x 4 1575 5 x1 51575 / 5 x1 5315 x1 ，取 x 420 x 1420 / 1 x 1420 x 1 1 1 5
x1 2 x 2 x3 10 s.t. 2 x1 3 x 2 3 x3 10 （Ⅰ） x 0, x 0, x 0 2 3 1
线性规划问题（Ⅰ）和（Ⅱ）之间有如下关系： ① 一个问题的目标函数系数是另一个问题约束条件的右端常数； ② 一个问题的第 i 个约束条件的各系数是另一个问题第 i 个变量的约束条件系数（或，一个问题的约束条件的系数矩阵是另一个问题的约束条件系数矩阵的转置）； ③ 一个问题是求目标函数的极大值，约束条件全都是“≤”形式，而另一个问题是求目标函数的极小值，约束条件全都是“≥”形式； ④ 两个问题的变量均非负。一般情况：
3 x1 6 x2 24 s.t. 2 x1 x2 10 x 0, x 0 2 1
解：最优解为 x1 4 ， x2 2 ，最优值为 f x 14 。

2-5 单纯形法

(4)、maxσj =σm+k→xm+k 换入变量
σj>0
由最小θ 比值法求： θ = min bi aim+k aim+k >0
=
br arm+k
定xr为换出变量，arm+k为主元。
(5)、以arm+k为中心，换基迭代
σm+k
……
0
…… 初等行变换
a1m+k
Pm+k =
0
…
arm+k amm+k
i 1
i
i
定理1：对解X(1) ，若检验数 j ( j=m+1,…,n)全部 0，则X(1)为最优解。
定理2：对X(1)，若有某个非基变量xm+k→σm+k>0
且相应的Pm+k =(a1m+k ,… ,amm+k )T 0，则原问题无有限最优解。
定理2证明
xi =bi - aij xj
i 1
j m 1
(c c a
j i 1
)x j
基变量用非基变量表示，目标函数也用非基变量表示当xj =0 (j=m+1,…,n)时,
X (b b ,0,0) Z cb
1 m m i 1 i i
T
三、单纯形法原理
max Z c x
x3 =45 - x1 - x2
x4=80 - 2x1 - x2
x5 =90 - x1 - 3 x2
令x1 = x2 =0 X(1) =(0, 0, 45, 80, 90)T Z(1) =0
(2)、判定解是否最优 Z=0+4x1+5x2 当x1从0↗或x2从0↗ Z从0↗ ∴ X(1) 不是最优解

单纯形法

单纯形法一、单纯形法的原理线性方程组的解：⎩⎨⎧=----=+-+-4322425432154321x x x x x x x x x x （1） 5个未知数，两个方程组。

方程的解多于1个。

两种初等变换：51）方程组的任一方程乘上一个不为零的数。

2）方程组的任一方程两边同乘上一个常数，分别加到另一个方程的两边。

式（1）做变换得到：（①×-1）⎩⎨⎧=-+-=+-+-2322242543254321x x x x x x x x x （2）式（2）做变换得到：（②×2）⎩⎨⎧=-+-=---232642354325431x x x x x x x x （3）方程组（1）、（2）、（3）同解，可令0543===x x x 。

得到：61=x ，22=x 。

选择3x ，4x ，5x 不同的值，相应地有不同的1x 和2x 的值，因此方程组有多组解。

基本变量：如果变量i x 的系数在某一个方程为1，而在其它所有方程为0，则称i x 为该方程组中的基本变量。

非基本变量：凡不是基本变量的变量都叫做非基本变量。

1x ，2x 为基本变量；3x ，4x ，5x 为非基本变量。

旋转运算：运用初等变换，可使一给定变量化为基本变量，这一运算，成为旋转运算。

基本变量的个数，与方程的个数相同。

基本解：设非基本变量为0，求得相应的基本变量的值，得到一组解，这组解称为基本解。

基本可行解：基变量的值为非负时的基本解称为基本可行解。

单纯形法的思路；1）先不考虑目标函数，从满足约束条件开始，寻求一个初始基本可行解； 2）求具有较佳目标函数值的另一个基本可行解，以改进初始解；3）对目标函数做有限次的改善。

当某一个基本可行解不能再得到改善时，即求得最优解，单纯形法结束。

二、单纯形算法例：54321325max x x x x x Z +-++= 约束条件为：⎪⎩⎪⎨⎧≥≥≥≥≥=+++=+++0,0,0,0,0743********53214321x x x x x x x x x x x x x （5）以上线性规划问题中，具有： 1）全部变量非负；2）全部约束条件都是等式；5 3）右端常数都是正的。

《单纯形方法》课件

04
最优解的确定
检查终止条件
在迭代过程中或迭代结束后，检查是否满足终止条件。
确定最优解
如果满足终止条件，则当前最优解即为所求的最优解；否则继续迭代。
CHAPTER 04
单纯形方法的案例分析
案例一：生产计划问题
总结词
线性规划问题，目标是最大化利润，约束条件包括生产能力、市场需求等。
VS
详细描述
02 它包含了决策变量、约束条件和目标函数的系数。
03 通过构建单纯形表格，可以方便地表示线性规划问题的数学模型。
单纯形迭代
1
单纯形迭代是求解线性规划问题的主要方法之一。
2
该方法通过不断迭代，逐步逼近最优解。
3
在每次迭代中，根据当前解的情况，通过一系列计算找到下一个迭代点，直到达到最优解或满足终止条件。
CHAPTER 02
单纯形方法的原理
线性规划问题
01
线性规划是数学优化技术的一种，用于在有限的资源下，寻找一组变量的最优解。
02
线性规划问题通常表示为在一组线性不等式约束下，最小化或最大化一个线性目标函数。
03
线性规划问题广泛应用于生产计划、资源分配、投资组合优化等领域。
单纯形表格
01 单纯形表格是用于描述线性规划问题的一种表格形式。
改进的方法与策略
混合整数规划
将整数规划与线性规划相结合，以处理包含整数约束的优化问题。
并行计算
利用多核处理器或多计算机系统，加快单纯形方法的计算速度。
全局优化
通过引入新的算法和策略，以实现全局最优解，而不仅仅是局部最优解。
自适应算法
根ห้องสมุดไป่ตู้问题的特性，动态调整算法参数，以提高求解效率。

单纯形法

XB =B-1b-B-1NX N 代入目标函数，使目标函数用非基变量
表示，即：
Z=cT X=(cTB
cTN) XB XN =cTBXB +cTN XN =cTB (B-1b-B-1NXN )+cTN XN
=cTBB-1b+(cTN -cTBB-1N)XN cBT B-1b+σNXN cBT B-1b+(σm+1,σm+1,
Z=CTBB-1b+(σm+1 ,
σm+k ,
xm+1

σ
n
)

CTB B-1b+σ m+k

xn
因为 m+k 0, 故当λ→+∞时，Z→－∞。
18
表格单纯形法
B
N
b
CBT
CNT
I
B-1N
B-1b
0
CNT -CBT B-1N
19
可将这些重要结论的计算设计成如下一个简单的表格，即单纯形表来完成：
min z=－6x1－4x2
x3 =100－2x1－3x2
+x4 =120－4x1－2x2
令有则有：
XN=(0,0)T XB=(100,120)T X（1）=（0，0，100，120）T为对应于基B1的基可行解。
问：
X（1）是否最优呢？——否
因为： x1和x2在目标函数中的系数为正，当x1↑，z ；x2↑，z 。
础上寻找一个新的基本可行解，并使目标函数值有所改善。
具体做法是：
先从检验数为负的非基变量中确定一个换入变量，使它从非基

第五章单纯形法

Cj→ 50 100 0
0
0
↓
x1
x2
S3
S4
S5
解
50 x1 1 0 1 0 -1
50
0 S4 0 0 -2 1 1
50
100 x2 0 1
00
1
250
Zj 50 100 50 0 Cj-Zj 0 0 -50 0
50 -50
27500
此时，Cj-Zj≤0 则此时为最优解。即：x1=50 x2=250 S3=0 S4=50 S5=0
y1
5 2 42
y2
3 1 14
y3
3 1 25
≥60 ≥40 ≥35
食品单价
≤≤ ≤ ≤
minZ
1.5 0.7 0.9 1.2
max
W
原规划与对偶规划之间的关系
1.原规划若有n个变量，则对偶规划有n个约束条件；原规划有m个约束条件，则对偶规划有m个变量。
2.若原规划的目标函数是求极大值，则对偶规划的目标函数是求极小值，且这两个极值相等。
本题解题过程
由题：
Cj列表示每一个基变量对目标函数的贡献
初始表最右端bi列，表示的是各松弛变量的最大值，即相应资源的约束条件的上限
初始表提供的基本可行解为
x1= x2=0 不生产A、B
S3=5
闲置的药品A的生产能力
S4=4
闲置的药品B的生产能力
S5=5
闲置的电力资源
例2某：医院营养室专门为病员制作甲、乙、丙三种
营养食品，其中每种食品都要包含两种主要营养素A、B，具体数据如下表，而且A营养素的供应量为12千克，B营养素的供应量为20千克，试问该营养室每天制作甲、乙、丙三种食品各多少份才能使其利润最高？

运筹学课件1-3单纯形法原理

§1.3 单纯形法原理

理论方法算法步骤单纯形表

算例
第1页
一、基本概念
考虑线性规划标准形式 max z CX s .t . AX b X 0 ：
其中A为m×n阶矩阵
可行解：满足AX=b,且X≥0的解称为可行解。可行域：全部可行解的集合称为可行域。最优解：使目标函数达到最大值的可行解称为最优解。基：设B是系数矩阵A的一个m×n阶的满秩子矩阵，称B是(LP)的一个基。
－5 0 0
2.5 0 4 4 0 3
1.5 17.5 22 19
－3 0 0 0
问：基解中零的个数至少有多少个？至少n-m个
例3
x1=0, x3=0 x2=3, x4=-2 是基解，但不是可行解
D
max z=x1+2x2 s.t. x1+x23 x2 1 x1, x2 0
max z=x1+2x2 s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40
第12页
三、几个基本定理
引理线性规划问题的可行解为基可行解的充要条件是它的正分量所对应的系数列向量线性无关。
证：（2）充分性
若向量 P1 , P2 , , Pk 线性无关，
则必有 k m
T
当 k m 时， P1 , P2 , , Pm 构成基
从而 X ( x1 , , x m , 0 , , 0 ) 为相应的基可行解
若X
(X
(0)
(0)
证。
(0)
不是基可行解
(0)
,由定理 2 知 X
到通过 X
) CX ) CX

03第三章单纯形法

第三章单纯形法在线性规划的计算求解中，应用最多且最著名的就是单纯形法。

这种方法是美国运筹学家G .B.Dantzig 丹捷格在1947年提出的。

后来经过人们多次改进，形成了许多变种。

实践证明单纯形法是一种使用方便、行之有效的算法。

§3.1 单纯形法的原理基本可行解的存在定理已经表明，若线性规划有最优解，则一定存在最优基本可行解，因此求线性规划问题就归结为寻找最优基本可行解。

单纯形法的基本思想就是从一个基本可行解出发，检查该基本可行解是否为最优解；若不是，则再设法求另一个未检查过的基本可行解，如此继续，直到查询到最优解为止。

按照以上的思路，需要解决三个难题： 1、如何求出第一个基本可行解？2、如何判断这个基本可行解就是最优解？3、若不是最优解，如何从一个基本可行解过渡到另一个未检查过的基本可行解？第一个问题的彻底解决尚需留待今后，但是我们知道，求基本可行解就是解线性方程组=A x B ，由于且()r m =A ，故可以解出m 个变量，称之为基本变量，剩下的n-m 个变量称之为自由变量。

于是，最简单的方法就是令所有的自由变量的值为零相应得到的解就是基本解。

例3.1 考虑线性规划1234134123m in 324..246350,1,2,3,4j z x x x x s t x x x x x x x j =-++-+=-++=≥= （3.1）把约束方程写成表格的形式，如表3-1：20 -4 1 6 -1 1 3 0 5从上述表格的左端可以看出，由第二、四列构成一个单位子矩阵，或曰子块，即对角元为1，其余为0，因此把2x 和4x 解出，即把2x 和4x 作为基本变量，余下1x 和3x 作为自由变量。

41321362453x x x x x x =-+=+- （3.2）令所有的自由变量130x x ==，而426,5x x ==，从而得到一个基本解(0,5,0,6)T 。

若需要判断该基本解是否基本可行解？只需看左端有单位子矩阵时，右列的元素是否都是非负，若是，则为基本可行解。

1-4(1)单纯形法PPT课件

CB (B1b B1 NX N ) C N X N
CB B1b (CN CB B1N )X N
线性规划1-4
证复明习：
min S CX
AX b X 0
定理1-1（最优性判别定理）对于 (LP) 的基 B，若有
X
XB XN
且，则基本可行解
是 ( LP )的最优解，称为最优基本可行解,
y1n y2n
ymm1 ymm2 ymn
(CN CB B1N ) ( y0m1, y0m2 ,, y0n )
线性规划1-4
例：min S x1 x2 2x3 2x4
x1 x2 x1 2 x2
0x3 2x3
x4 x4
1 2
x j 0, j 1,2,3,4 A
x j 0, j 1,2,n
CB B1b y00 CN CB B1 N ( y0m1 , y0m2 , , y0n )
线性规划1-4
CN CB B1N ( y0m1 , y0m2 , , y0n )
min S CX
AX b X 0
非基变量 x j 的检验数
线性规划1-4
典式的分量形式: y00
min S y00 y0m1 xm1
CB B1b
y0m2 xm2
y0n xn
x1 y1m1 xm1 y1m2 xm2 y1n xn y10
1 1
1 B2
01 2 N1
1 1 0
b 2
0
E1
2 1 0 2B1N0 B11b
x1 x2 x1 2 x2
0x3 2x3
x4 x4
1 2
x1
2x3 x4 0 x2 2x3 0x4 1
C

2-1单纯形法原理

bl' a'
lmk
上页下页返回
4、迭代运算
写成增广矩阵的形式,进行迭代.
x1 x2 xm xm1....xl
xn
b
1
a1m1 ...a1mk ...a1n ....... ...... .......
1
alm1 ...almk ...aln
....... ...... ........
1 amm1 ...ammk ...amn
xm
的
k
mk
0
并且对应的非基变量的系数
a' 0, i 1,2,..m i ,mk
则具有无界解（或无最优解）。
上页下页返回
2、最优性检验与解的判别
（4）之证明： x1
b1'
a x ' 1mk mk
x2
b2'
a' 2mk
xmk
........
.......... .
xm
bm'
a' mmk
xmk
X (2) (2,3,0,8,0)T 最优解
X (3) (4,2,0,0,4)T 目标函数为： Z 14 1.5x3 0.125x4
最优值Ｚ＝１４
上页下页返回
代入目标函数 Z 9 2 • 结合图形法分析（单纯形法的几何意义）
令：x1 x5 0, 得一基可
x2
X (1) (0,3,2,16,0)T
j m 1
j m1
cm1xm1 ... cn xn
m
n
m
cibi'
(c j ciai'j )x j
i 1
j m 1

ch5 (1) 单纯形法

管理运筹学
求解得到此线性规划的一个基本解：
x1=0，x2=400，x3=－100， x4=0，x5=－150 由于在这个基本解中x3与x5不满足该线性规划x3 ≥0， x5 ≥0的约束条件，显然
不是此线性规划的可行解。
管
理
运
筹
学
一个基本解可以是可行解，也可
以是非可行解，它们之间的主要区别在于其所有变量的解是否满足非负的
例如：
管理运筹学
0 1 0
0 0 1
1 0 0
那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。
管
理
运
筹
学
实际上，这个基本可行解中的各个变
量或等于某个bj或等于零。
在本例题中我们就找到了一个基是单位矩阵。
1 B2 ( p3 , p4 , p5 ) 0 0
5 2
的增大是最先达到0的。所以，应该选
2
x5 由 x5
基变量变为非基变量，也就是用 x 去替换
这一过程称为“换基”，或者称为“迭
代”。：
管理运筹学
令对应的非基变量
一个新的基本可行解：
x1 x 5 0,
可以求得
x 2 2 5 0, x 3 5 0, x 4 1 5 0
为了对新的基本可行解进行最优性检验，我们用新的非基变量表示目标函数，由（1）式可得：
管理运筹学
首先将其变为如下的标准型：
m ax z 5 0 x1 1 0 0 x 2 s .t x1 x 2 x 3 3 0 0 x1 x 2 x 4 4 0 0 x 2 x5 2 5 0 x j 0， j 1, 2, L 5 .

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

单纯形法求解—动态演示
在求解LP问题时,有人给出了图解法,但对多维变量时,却无能为力,于是
美国数学家G·B·Dantgig(丹捷格)发明了一种“单纯形法”的代数算法，尤其是方便于计算机运算。这是运筹学史上最辉煌的阶段。
一、关于标准型解的若干基本概念
线性规划问题标准型的矩阵形式：
Max Z = CX
Z = CX AX=b
设 A=（B , N）（B为一个基，即线性无关向量组R(A)=R(B)）
XT= (XB , XN) T （XB 为基变量，XN为非基变量） C= (CB , CN) （CB 为基变量系数，CN为非基变量系数）则有： Z= (CB , CN) (XB , XN) T= CB XB+CN XN AX =（ B , N） (XB , XN) T = B XB+ N XN = b 因为B为基, 故有 XB +B-1N XN = B-1b，
比值
b bi ai 2
50
S2 0 2 0 0 1 -1 150
2 x2 100 0 1 0 0 1 250
Zj=CBNj j cj zj
0 100 0
0 100
Z=25000
初始单纯形表
迭代基变次数量
CB
x1
X2
s1
50 100 0
S1 0 1 0 1
s2 S3
00 0 -1
比值
检验系数区
Z=CBB-1b
初始单纯形表
迭代基变次数量
CB
x1
x2
s1
s2
s3
50 100 0 0 0
比值
b bi ai 2
1 Zj=CBNj j cj zj
Z=CBB-1b
初始单纯形表
基
迭代次数
变
CB
x1
X2
s1
s2
量
50 100 0 0
1 110
2 101
0
0 100
Zj=CBNj
CB
S1 0
x1 X2 s1 50 100 0 111
s2 S3
比值
b bi
00
ai 2
0 0 300
S2 0 2 1 0 1 0 400
1 S3 0 0 1 0 0 1 250
Zj=CBNj
j cj zj
Z=0
初始单纯形表
迭代基变次数量
CB
S1 0
x1 X2 s1 50 100 0 111
50 100 0 111 210
s2 S3
比值
b bi
00
ai 2
0
0
300
300 1
1
0
400
400 1
1 S3 0
0 ①1
0
0
1 250 250
1
Zj=CBNj 0 0 0 0 0 Z=0
j c j z j 50 100 0 0 0
初始单纯形表可行解XB=B-1b-B-1NXN>=0
迭代基变次数量
CB
S1 0 S2 0
x1 X2 s1
50 100 0 111 210
s2 S3
比值
b bi
00
ai 2
0
0
300
300 1
1
0
400
400 1
2 x2
0 ①1 0 0 1 250 250
1
Zj=CBNj j cj zj
Z=CBB-1b
初始单纯形表
迭代基变次数量
s2 S3 00 0 -1
比值
b bi ai 2
50
S2 0 2 0 0 1 -1 150
2 x2 100 0 1 0 0 1 250
Zj=CBNj j cj zj
Z=25000
初始单纯形表
迭代基变次数量
CB
S1 0
x1 X2 s1 50 100 0 101
s2 S3 00 0 -1
00
ai 2
0 0 300
S2 0 2 1 0 1 0 400
1 S3 0 0 1 0 0 1 250
Zj=CBNj 0 0 0 0 0
j c j z j 50 100 0 0 0
0 Z=
初始单纯形表可行解XB=B-1b-B-1NXN>=0
迭代基变次数量
CB
S1 0 S2 0
x1 X2 s1
s2 S3
00 0 -1
比值
b bi ai 2
50
S2 0 2 0 0 1 -1 150
2 x2 100 0 1 0 0 1 250
Zj=CBNj 0 100 0 j c j z j 50 0 0
0 100 0 -100
Z=25000
初始单纯形表
迭代基变次数量
CB
x1 X2 s1 50 100 0
解得可行解XB=B-1b-B-1NXN，代入目标函数Z， Z = CB B-1b + (CN- CB B-1N ) XN
令非基变量XN = 0 ，则有 XT = (XB , XN) T =（ B-1b , 0) T Z = CB B-1b
Z = CB B-1b + (CN- CB B-1N ) XN
b bi ai 2
50
S2 0 2 0 0 1 -1 150
2 x2 100 0 1 0 0 1 250
Zj=CBNj 0 100 0 j c j z j 50 0 0
0 100 0 -100
Z=25000
初始单纯形表
迭代基变次数量
CB
x1
X2
s1
50 100 0
S1 0 1 0 1
（a）
C (c1, c2 ,, cn );
s.t. AX=b X0
（ b）（c）
X (x1, x2 ,, xn )T
a11 a12 …. a1n
b1
A= a21 a22 …. a2n
……………………………
am1 am2 …. amn
b = b2
…………
bm
基矩阵
示例:
目标函数
约束条件
x1 x2 x3 x4
3 0 00 3
0 2 0 0= 2
0 0 11 1
max z 3x1 2x2 x3 x4
3x1
3
s.t.
2x2
2
x3 x4 1
x1 x2 x3
0
行列式≠0 基矩阵
300 020 001
X1,x2,x3为基变量,x4为非基变量
1、单纯形法原理：
迭代基变次数量
CB
x1
X2
s1
s2
S3
比值
b bi aij
1 Zj=CBNj j cj zj
Z=CBB-1b
初始单纯形表
迭代基变次数量
CB
x1 X2 s1 s2 S3
目标函数系数区
比值
b bi aij
基变量区
1
约束条件
右端系
系数区数
Zj=CBNj j cj zj
x1 X2 s1
50 100 0 111 210
s2 S3
比值
b bi
00
ai 2
0
0
300
300 1
1
0
400
400 1
2 x2 100 0
①1
0
0
1 250 250
1
Zj=CBNj j cj zj
Z=CBB-1b
初始单纯形表
迭代基变次数量
CB
S1 0 S2 0
x1 X2 s1
CB
xS11 500
xx1 X2 s1
5500 100 0 ①1 0 1
s2 S3 00 0 -1
比值
b bi ai 2
50
S2 0 2 0 0 1 -1 150
3 x2 100 0 1 0 0 1 250
Zj=CBNj
j cj zj
初始单纯形表
迭代基变次数量
CB
x1 50
x1 x2 s1 50 100 0 ①1 0 1
50 100 0 111 210
s2 S3
比值
b bi
00
ai 2
0
0
300
300 1
1
0
400
400 1
2 x2 100 0
①1
0
0
1 250 250
1
Zj=CBNj j cj zj
Z=CBB-1b
初始单纯形表
迭代基变次数量
CB
S1 0
x1 X2 s1 50 100 0 101
CB
S1 0 S2 0
x1 X2 s1
50 100 0 111 210
s2 S3
比值
b bi
00
ai 2
0
0
300
300 1
1
0
400
400 1
2 x2 100 0
①1
0
0
1 250 250
1
Zj=CBNj j cj zj
Z=CBB-1b
初始单纯形表
迭代基变次数量
CB
S1 0 S2 0
s2 S3 00
比值
b bi ai 2
S1 0 ①1

单纯形法基本原理及实例演示

合集下载