单纯形法步骤
- 格式：docx
- 大小：32.10 KB
- 文档页数：3
下载文档原格式
合集下载
单纯形方法（SimplexMethod）
单纯形⽅法（SimplexMethod）最近在上最优理论这门课，刚开始是线性规划部分，主要的⽅法就是单纯形⽅法，学完之后做了⼀下⼤M算法和分段法的仿真，拿出来与⼤家分享⼀下。
单纯形⽅法是求解线性规划问题的⼀种基本⽅法。
线性规划就是在⼀系列不等式约束下求⽬标函数最⼤值或最⼩值的问题，要把数学中的线性规划问题⽤计算机来解决，⾸先要确定⼀个标准形式。
将所给的线性规划问题化为标准形式：s.t.是英⽂subject to 的简写，意思是受约束，也就是说第⼀个⽅程受到后⾯两个⽅程的约束。
对于求最⼤值问题可以将⽬标函数加负号转换为最⼩值问题。
对于求最⼤值问题可以将⽬标函数加负号转换为最⼩值问题。
其他的问题就是将实际问题中的不等式约束改为等式约束，主要⽅法是引进松弛变量和剩余变量，以及将⾃有变量转换为⾮负变量。
①对于不等式，引⼊松弛变量将其变为等式形式如下：②对于不等式，引⼊剩余变量将其变为等式形式如下：③若变量为⾃有变量（可取正、负或零，符号⽆限制），则引⼊两个⾮负变量将其表⽰如下：关于线性规划问题的解：确定了标准形式，我们就针对这个标准形式讨论⼀下线性规划问题的解。
线性规划问题的解能满⾜标准形式中约束条件的向量X的值，但只有最优解才能使⽬标函数值最⼩。
对于上⽂中的标准形式，约束矩阵A是⼀个m*n维矩阵，且m<n，所以⼀定可以从A中找到⼀个满秩m*m矩阵。
这个矩阵就称作矩阵A的⼀个基阵，矩阵A就可以写作 [B N] , 相应的解 x 也可以写成 x=(xB,xN)’，那么 Ax=b 就变为，左式两端同乘B矩阵的逆，得到。
由此引出下列名词：基阵：⾮奇异矩阵（满秩矩阵、可逆矩阵）B基向量：基阵B由m个线性⽆关的向量组成，称之为基向量基变量：向量xB各分量，与基向量对应的xB中的m个分量成为基变量⾮基变量：向量xN各分量基本解：令xN各分量为0，由得到的解称为基阵B对应的基本解基本可⾏解：当成⽴时，称基本解为基本可⾏解，因为只有满⾜所有分量不⼩于0，才符合标准形式中的约束条件（最后⼀条）。
单纯形法求解过程
单纯形法求解过程单纯形法是一种经典的线性规划求解方法，它是由乔治·达竞士等人在1947年提出的。
该方法的基本思想是，通过在单纯形空间内不断移动顶点的位置来寻找最优解。
单纯形法是目前广泛应用的线性规划求解方法之一，它求解线性规划问题可大大地简化计算过程。
单纯形法的求解过程包括以下几个步骤：1. 将线性规划问题转化为标准形式线性规划问题的标准形式为：$ \max_{x} \ \ c^T x $$s.t. \ Ax=b$$x\geq 0$其中，$x$是要求解的向量；$b$是一个常数向量；$A$是一个$m\times n$的矩阵；$c$是一个常数向量。
2. 初始化单纯形表因为单纯形法是通过移动顶点来寻找最优解的方法，因此需要初始化单纯形表。
单纯形表是将原始的约束条件表示为不等式形式时形成的。
例如，对于一个带有3个变量的线性规划问题，其单纯形表的形式如下：CB | X1 | X2 | X3 | X4 | RHS----|-----|-----|-----|-----|----0 | a11| a12| a13| 0 | b10 | a21| a22| a23| 0 | b20 | a31| a32| a33| 0 | b31 | z1 | z2 | z3 | 0 | 0其中，CB代表成本系数，X1、X2、X3、X4分别代表变量。
a11、a12、a13等代表矩阵A中的元素，b1、b2、b3代表矩阵b中的元素。
3. 选择进入变量和离开变量在单纯形表中，规定最后一列为等式右边的常数（RHS），即b。
在单纯形法的求解过程中，首先需要选择一个“进入变量”，即在单纯形表的第一行中，寻找一个系数为正的变量，使得将其加入目标函数后，目标函数值可以上升。
这里以X1为例，X1为进入变量。
接着，需要选择一个“离开变量”，即在单纯形表中，寻找一个使得添加X1变量后，约束条件不改变且取得约束条件中系数最小的一个变量离开。
运筹学课件1-4单纯形法计算步骤
b 21 4
9 4
3 x1 1 -1 3 4 -1 12
9 x2 3 1 9 0 1 0
0 x3 1 0 0 1 0 0
0 x4 0 1 0 -3 1 -9
θ 7 4
9/4 -
所以把x3换出为非基变量，x1为换入变量即新的基变量。
第20页
cj
CB 0 0
0 9 3
XB x3 x4 cj-zj x3 x2 cj-zj x1
cj-zj
x3 x1 x5 cj-zj
6
0 1 0
5
5/2 1/2 1
0
1 0 0
0
-1/2 1/2 -1
0
0 0 1
75 5
0
2
0
-3
0
5
x2
5
0
1
0
-1
1
第10页
cj CB 0 0 0 0 6 0 XB x3 x4 x5 b 90 75 80 105/2 75/2 5
6 x1 1 2 2
5 x2 3 1 2
9/4
-
3 9
9/4 25/4
1 0 0
25
第24页
cj CB 0 0 XB x3 x4 cj-zj b 21 4
3 x1 1 -1 3
9 x2 3 1 9
0 x3 1 0 0
0 x4 0 1 0 θ 7 4
0
9
x3
x2 cj-zj x1 x2 cj-zj
9
4
4
-1 12
0
1 0 0 1 0
1
0 0 1/4 1/4 -3
i 1
第1页
单纯形表求解线性规划问题
第四节 单纯形法的计算步骤
上表中由于所有σ 上表中由于所有 j>0 ，表明已求得最优解 x1=4， x2=2， x3=0， x4=0， x5=0， x6=4， ， ， ， ， ， ， Z=14。 。 当确定x 为换入变量计算θ值时 值时， ◆当确定 6为换入变量计算 值时，有两个相 同的最小值： 同的最小值：2/0.5=4，8/2=4。任选其中一 ， 。 个作为换出变量时， 个作为换出变量时，则下面表中另一基变 量的值将等于0，这种现象称为退化 退化。 量的值将等于 ，这种现象称为退化。含有 一个或多个基变量为0的基可行解称为 的基可行解称为退化 一个或多个基变量为 的基可行解称为退化 的基可行解。 的基可行解。
18
迭代
xB
次数
cB
x1
x2
x3
x4
x5 bi
θi
50
x1
100
0
0
0
50 0 100
1 0 0
0
0 0 1
0
1 -2 0
- 50
0 1 0
0
-1 1 1
- 50
50 50 250 -27500
2
x4 x2
σj
2010年8月
管理工程学院
18
《运筹学》 运筹学》
19
所有的检验数 σ j ≤ 0, 此基本可行解： 此基本可行解：
2010年8月
管理工程学院
5
《运筹学》 运筹学》
6
c1 … cl b b1´
⋮
c j→ cB c1
⋮
… cm … xm …0 …⋮ 0 …1 …
⋮
…cj …xj …a1j´ …⋮ a2j´ …⋮ amj´
… ck … cn … xk …xn …0 …⋮ 1 …0
第5章_单纯形法
初始可行解:第一个找到的可行域的顶点。
三、单纯形法试算程序框图（见图5—1）
开始
转变为标准型[增加额外 变量(松弛、剩余、人工 变量)]
建立初始单纯形表
最优
是
停
否 找出“换入”“换出”变量
修正单纯形表
图5—1
5.2 线性规划模型的变换
一、线性规划模型标准型的特点 ⑴目标函数是求极大值或极小值； ⑵所有的变量都是非负的； ⑶除变量的非负约束外，其余的约束条件都
ABCD 含量（单位/千克）
最低需求量 （单位）
糖
5 2 4 2 60
蛋白质
3 2 1 4 40
脂肪
3 1 2 5 35
单价（元/千克） 1.5 0.7 0.9 1.2
例3是例2的对偶问题，例3与例2互为对偶线性规 划原规划与对偶规划具有对称性，如图所示：
食品
单一营
养成分单价
AB C D
单一营养
（x1） （x2） （x3） （x4） 成分需求量
m
c a Z j
i ij
i 1
解b
b 1
b 2
…… b
n
目标函 数
例1
求max Z=7x1+10x2 满足 7x1+7x2≤49 10x1+5x2≤50 x1，x2≥0
用单纯形法求解。
例2
第2章例1中我们得线性规划模型为： 目标函数：max Z = 50x1+100x2
满足 x1 + x2 ≤300 2x1 + x2 ≤400 x2 ≤250 x1，x2 ≥0
…… am1x1 + am2x2 + ……+ amnxn ≤(≥，=) bm x1，x2 …… xn≥ 0
运筹学单纯形法的计算步骤
b2
0… 0
a2,m+1
…
a2n
2
…
…
…
…
cm xm
bm
0… 1
am,m+1
…
amn
m
-z -z 值 0 … 0
m+1
…
n
XB 列——基变量， CB 列——基变量的价值系数(目标函数系数) cj 行——价值系数，b 列——方程组右侧常数 列——确定换入变量时的比率计算值
下面一行——检验数， 中间主要部分——约束方程系数
(4).根据max(j > 0) =k，拟定xk为换入变量，按 规则计算 =min{bi/aik\aik>0}
可拟定第l行旳基变量为换出变量。转入下一步。
(5).以 alk 为主元素进行迭代(即用高斯消去法或称为旋转变 换)，把 xk 所对应的列向量变换为(0，0，…，1，…，0)T，将
XB 列中的第 l 个基变量换为 xk，得到新的单纯形表，返回(2)。
b
x1
x2
x3
x4
x5
2 x1 2 0 x4 8 3 x2 3
1
0
1
0 -1/2 -
0 0 -4 1 (2 ) 4
0 1 0 0 1/4 12
-z
-13
0
0 -2
0 1/4
X(2)=(2，3，0，8，0)T， z2 =13
cj
2 30 0 0
CB XB
b
x1
x2
x3
x4
x5
2 x1 4 0 x5 4 3 x2 2
量，给出第一阶段的数学模型为：
min = x6+x7
x1-2x2+x3+x4
单纯形法的计算步骤
变量作为换出变量。
L
min
bi
aik
a ik
0
单纯形法旳计算环节
Page 4
③ 用换入变量xk替代基变量中旳换出变量，得到一种新旳基。 相应新旳基能够找出一种新旳基可行解，并相应地能够画出 一种新旳单纯形表。
④ 5）反复3）、4）步直到计算结束为止。
单纯形法旳计算环节
将3化为1
换入列
j
乘
,
x2
,
x3
,
x4
0
Page 1
单纯形法旳计算环节
Page 2
2）求出线性规划旳初始基可行解，列出初始单纯形表。
j
检验数
1 c1 (c3a11 c4a21 ) 3 (0 2 0 1) 3
单纯形法旳计算环节
Page 3
3）进行最优性检验
假如表中全部检验数 止。不然继续下一步。
，j 则表0中旳基可行解就是问题旳最优解，计算停
单纯形法旳计算环节
例1.8 用单纯形法求下列线性规划旳最优解
max Z 3 x1 4 x2
2 x1 x2 40
x1
3x2
30
x1
,
x2
0
解：1）将问题化为原则型，加入松驰变量x3、x4则原则型为:
max Z 3 x1 4 x2
2 x1 x2 x3 40
x1
3x2
x4
30
x1
以
1/3 后
j
得
到
j
30 5/3 0 10 1/3 1
5/3 0
18 1
0
40
1
0
0
Page 5
bi /ai2，ai2>0
单纯形法的计算步骤
运筹学基础及应用
解：化标准型
max
z 2 x1 x2 0 x3 0 x4 0 x5 5 x2 x3 15 6 x 2 x x4 24 1 2 x5 5 x1 x2 x1 , , x5 0
运筹学基础及应用
表1：列初始单纯形表 （单位矩阵对应的变量为基变量）
运筹学基础及应用
单纯形表
- Z x1基变量 x 2 ... xm XB 0 1 1E 0 单位阵 ....... 0 1 1 c c 0... c 1 2 m xm xNn 非基变量 1 .... X a1m 1 ...a1n a 2 m 1N...a 2 n
非基阵 ......
在上一节单纯形法迭代原理中可 知，每一次迭代计算只要表示出当前的约 束方程组及目标函数即可。
a1m 1 xm 1 ..... a1n xn b1 x1 x a2 m 1 xm 1 ..... a2 n xn b2 2 .......... .......... .......... ..... xm amm 1 xm 1 ..... amn xn bm Z c1 x1 ... cm xm cm 1 xm 1 ... cn xn 0
3
0 1 5/4 -15/2 1*3/2 0 0 1/4 -1/2 +0*15/2 检验数<=0 1 0 -1/4 3/2
cj z j
8.5
0
0
-1/4
-1/2
最优解为X=(7/2,3/2,15/2,0,0) 目标函数值Z=8.5
cj
CB
0 0 0
2
1
0最小的值对应 0 0
C4单纯形计算步骤
由于所添加的剩余变量的系数为1不能构成初始可行基变量为此引入一个人为的变量注意此时约束条件已为型以便取得初始基变量故称为人工变量
运筹学
讨论区 orppt07@ orppt123456 李健 lijian@ 北京化工大学经济管理学院
上节内容回顾
一．线性规划与单纯形法
xi bi
j m 1
a x
ij
n
n
j
(i 1, 2,
m)
(1-24)
将(1-24)代入(1-20),目标函数变成
z ci bi
i 1 m j m 1
(c c a )x
j i 1 i ij
m
j
(1-25)
，j m 1, 令z0 ci bi， j c j ci aij
§4.2 标准LP的单纯形计算步骤
例2 请用单纯型表求解下LP
max z 2 x1 3 x2 x1 2 x2 8 16 4 x1 s.t. 4 x2 12 x1 , x2 0
max z 2 x1 3 x2 0 x3 0 x4 0 x5 8 x1 2 x2 x3 4 x x4 16 1 s.t. 4x2 x5 12 x1 , x2 , x3 , x4 , x5 0
max z 2 x1 3 x2 0 x3 0 x4 0 x5 8 x1 2 x2 x3 4 x x4 16 1 s.t. 4x2 x5 12 x1 , x2 , x3 , x4 , x5 0
§4.1 单纯形表
cj
cB
0 0 0
i 1 i 1
m
m
,n
运筹学
讨论区 orppt07@ orppt123456 李健 lijian@ 北京化工大学经济管理学院
上节内容回顾
一．线性规划与单纯形法
xi bi
j m 1
a x
ij
n
n
j
(i 1, 2,
m)
(1-24)
将(1-24)代入(1-20),目标函数变成
z ci bi
i 1 m j m 1
(c c a )x
j i 1 i ij
m
j
(1-25)
，j m 1, 令z0 ci bi， j c j ci aij
§4.2 标准LP的单纯形计算步骤
例2 请用单纯型表求解下LP
max z 2 x1 3 x2 x1 2 x2 8 16 4 x1 s.t. 4 x2 12 x1 , x2 0
max z 2 x1 3 x2 0 x3 0 x4 0 x5 8 x1 2 x2 x3 4 x x4 16 1 s.t. 4x2 x5 12 x1 , x2 , x3 , x4 , x5 0
max z 2 x1 3 x2 0 x3 0 x4 0 x5 8 x1 2 x2 x3 4 x x4 16 1 s.t. 4x2 x5 12 x1 , x2 , x3 , x4 , x5 0
§4.1 单纯形表
cj
cB
0 0 0
i 1 i 1
m
m
,n
单纯形法解题步骤
三、单纯形法的解题步骤第一步：作单纯形表.）（1）把原线性规划问题化为标准形式；）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵；）（3）目标函数非基化；）（4）作初始单纯形表.第二步：最优解的判定.(1) 若所有检验数都是非正数，即，则此时线性规划问题已取得最优解.(2) 若存在某个检验数是正数，即，而所对应的列向量无正分量，则线性规划问题无最优解.如果以上两条都不满足，则进行下一步.第三步：换基迭代.，并确定所在列的非基变量为进基变量.（1）找到最大正检验数，设为（2）对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号.主元是最大正检验数所在列，用常数项与进基变量所对应的列向量中正分量的比值最小者；替换出基变量，从而得到新的基变量.也就是主元所在（3）换基：用进基变量（4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表；（5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止.例3 求.解（1）化标准型：令，引进松弛变量，其标准型为求（2）作单纯形表：在约束方程组系数矩阵中的系数构成单位矩阵，故取为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）.表 6.8（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为标函数取得最优值.目性规划问题的最优解为：.原线目标函数的最优值为14，即.例4 用单纯形方法解线性规划问题.求.解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出，,代入目标函数, 经整理后，目标函数非基化了.作单纯形表，并进行换基迭代（见表6.9）.最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变换，基变量出基，非基变量进基.表 6.9目前最大检验数，其所在列没有正分量，所以该线性规划问题没有最优解.例5用单纯形方法解线性规划问题.求解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵，取为基变量，而目标函数没有非基化.从约束方程找出，,代入目标函数，经整理得,目标函数已非基化.作单纯形表，并进行换基迭代(见表6.10).最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变换，基变量出基，非基变量x2进基，先将主元化为1，然后再将主元所在列的其他元素化为零.表 6.10至此，检验数均为非正数，故得基础可行解.原问题的最优解为：.最优值为6，即.如果我们再迭代一次，将基变量出基，非基变量进基（见表6.11）.表 6.11可得到另一个基础可行解,原问题的最优解为：，最优值仍为6，说明该线性规划问题有无穷多最优解，其最优解均为6.如何知道线性规划问题有无穷多最优解呢？这主要反映在单纯形表中.如果非基变量所对应的检验数为0，我们可对此列继续进行换基迭代，就可以得到另一个基础可行解.以此作下去，可得到许多基础可行解，即相对应的最优解有无穷多个.（4） 011 0。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
单纯形法步骤：
1. 给定初始点 )0(x 初始单纯形边长 a ，
α ， 收缩系数 β ， 延伸系数 γ 以及精度要求 ε。
2. 作出初始单纯形图
3. 找出坏点 )(h x 、好点 )(e x 计算中心点 )1(+n x 及 反射点 )2(+n x 和各点上的目标函数值
4. 比较反射点和除了坏点上的函数值，
5.
⑴. 如果反射点上的函数值比好点差，但比坏点外的其他顶点函数值好，认为反射成功，将反射点代替坏点构成新的单纯形，转7 ⑵. 如果反射点上的函数比好点还要好，说明反射点很好，可以沿此方向作延伸尝试，如果延伸点上的函数值比好点还好，则将延伸点取代坏点，形成新单纯形，转7。
反之，延伸点上函数值不如好点，说明延伸失败，但反射还是成功的，所以仍可用反射点代替坏点，然后转7
5. 如果反射点连坏点都不如，说明反射失败，那么作收缩，找出收缩点的函数值，并转
6.；如果反射点仅比坏点好，则将反射点取代坏点，然后收缩，转下一步6。
6. 如果收缩点上函数比坏点还差，说明收缩也失败，作缩小运算，形成缩小后的单纯形转7；反之（即收缩点上的函数值比坏点好），说明收缩成功，用收缩点代替坏点，形成新的单纯形转。
转下一步7。
7. 检查是否满足精度要求 ()(1)max
(()i n f x f x ε+-≤
如满足，停止迭代，否则转3，继续迭代。
%三个考察点，最优，次差，最差
best = vx(: , 1) ; fbest = vf(1) ;
soso = vx(: , n) ; fsoso = vf(n) ;
worst = vx(: , n+1) ; fworst = vf(n+1) ;
center = sum(vx(: , 1:n) , 2) ./ n ;
r = 2 * center - worst ;%反射点
fr = feval(fun , r) ;
if fr < fbest %比最好的结果还好，说明方向正确，考察扩展点，以期望更多的下降
e = 2 * r - center ; %扩展点
fe = feval(fun , e) ;
if fe < fr %在扩展点和反射点中选择较优者去替换最差点
vx(: , n+1) = e ; f(: , n+1) = fe ;
else
vx(: , n+1) = r ; vf(: , n+1) = fr ;
end
else
if fr < fsoso %比次差结果好，能够改进
vx(: , n+1) = r ; vf(: , n+1) = fr ;
else %比次差结果坏，当压缩点无法得到更优值的时候，考虑收缩
shrink = 0 ;
if fr < fworst %由于r点更优所以向r点的方向找压缩点
c = ( r + center ) ./ 2 ; fc = feval(fun , c) ;
if fc < fr %确定从r压缩向c可以改进
vx(: , n+1) = c ; vf(: , n+1) = fc ;
else %否则的话，准备进行收缩
shrink = true ;
end
else
c = (worst + center) ./ 2 ; fc = feval(fun , c) ;
if fc < fr %确定从r压缩向c可以改进
vx(: , n+1) = c ; vf(: , n+1) = fc ;
else %否则的话，准备进行收缩
shrink = 1 ;
end
end%fr < fworst
if shrink %压缩点并非更优，考虑所有点向best收缩
for i = 2:n+1
vx(: , i) = ( vx(i) + best ) ./ 2 ; vf(: , i) = feval(fun , vx(: , i)) ;
end
end %shrink
end%fr < fsoso
end %fr < fbest
[vf index] = sort(vf) ;
vx = vx(:,index) ;。