运筹学 第三章 单纯形法(1,2两节)
- 格式：ppt
- 大小：793.50 KB
- 文档页数：56
下载文档原格式
合集下载
运筹学-单纯形法灵敏度对偶
若新增约束如下：
max z 50x1 100x2 x1 x2 300 2x1 x2 400 x2 250 10x1 30x2 5000(电力约束) x1, x2 , 0
x1 x2 s1
把最优解x1=50,x2 =250代入电力约束 1050+30 250=80005000 新约束不满足,最优解变化
例题：已知某线性规划初始可行基是（S1 S2 S3 a1）， 最终单纯形表如下，求对偶价格不变时的△bi变化范围
x1 x2 s1
50 100 0
X1 50
1
0
0
S3 0
0
0
0
X2 100 0
1
0
s1 0
0
0
1
Zj
50 100 0
δj
0
0
0
（1） △b1的变化范围： ?
（2） △b2的变化范围：?
（3） △b3的变化范围： ? （4） △b4的变化范围：?
1 0 1 2 0.5
B1 p6'
2
1
1
0.5
2
0 0 1 1.5 1.5
Z6' 50 0.5 0 (2) 100 1.5 175
' 6
C6
Z6'
150 175
25
δ6´<0，最优解不变，即仍生产Ⅰ50件，Ⅱ100件。
2、变量xk系数列由pk变为pk´，在最终单纯形表 上xk是基变量
x1 x2 s1
50 100 0
X1 50 1
0
0
S3 0
0
0
0
X2 100 0
1
0
s1 0
0
运筹学课件 单纯形法的计算步骤
第二阶段：以第一阶段的最优解(不含人工变量)为初 始解，以原目标函数为目标函数。
例8 试用两阶段法求解线性规划问题
min z =-3x1+x2+x3
x1 2 x2 x3 11
s.t.
4 x1 2 x1
x2
2x3 3 x3 1
x1 , x2 , x3 0
0 0 -1 0 0
x2
3 5 11/5
Z0=0
Z1=15
x1
如果将x1换入基底，得 另一解，由可行域凸性 易知，有两个最优解必 有无穷多组最优解 当非基底变量的检验数 中有取零值，或检验数 中零的个数大于基变量 个数时，有无穷多解。
四、无（有）界解
max z=x1+x2 -2x1+x2 4 x1- x2 2 -3x1+x23 x1 ,x2 0
反之，若加了人工变量的问题解后最优解中仍含人工变量为 基变量，便说明原问题无可行解。例3的单纯形表格为：
Cj
3
-1
-1
0
0
-M
CB XB b
x1
x2
x3
x4
x5
x6
0 x4 1
1
-2
1
1
0
0
-M x6 13 -4
1
2
0
-1
1
-M x7 1 -2
0
[1] 0
0
0
j
3-6M M-1 3M-1 0
-M
x1 2 x2 x3 x4
11
4 2
x1 x1
x2
2
x3 x3
例8 试用两阶段法求解线性规划问题
min z =-3x1+x2+x3
x1 2 x2 x3 11
s.t.
4 x1 2 x1
x2
2x3 3 x3 1
x1 , x2 , x3 0
0 0 -1 0 0
x2
3 5 11/5
Z0=0
Z1=15
x1
如果将x1换入基底，得 另一解，由可行域凸性 易知，有两个最优解必 有无穷多组最优解 当非基底变量的检验数 中有取零值，或检验数 中零的个数大于基变量 个数时，有无穷多解。
四、无（有）界解
max z=x1+x2 -2x1+x2 4 x1- x2 2 -3x1+x23 x1 ,x2 0
反之，若加了人工变量的问题解后最优解中仍含人工变量为 基变量，便说明原问题无可行解。例3的单纯形表格为：
Cj
3
-1
-1
0
0
-M
CB XB b
x1
x2
x3
x4
x5
x6
0 x4 1
1
-2
1
1
0
0
-M x6 13 -4
1
2
0
-1
1
-M x7 1 -2
0
[1] 0
0
0
j
3-6M M-1 3M-1 0
-M
x1 2 x2 x3 x4
11
4 2
x1 x1
x2
2
x3 x3
《运筹学教程》第三章习题答案
《运筹学教程》第三章习题答案1.影子价格是根据资源在生产中作出的贡献而做的估价。
它是一种边际价格，其值相当于在资源得到最有效利用的生产条件下，资源每变化一个单位时目标函数的增量变化。
又称效率价格。
影子价格是指社会处于某种最优状态下，能够反映社会劳动消耗、资源稀缺程度和最终产品需求状况的价格，是社会对货物真实价值的度量。
只有在完善的市场条件下才会出现，然而这种完善的市场条件是不存在的，因此现成的影子价格也是不存在的。
市场价格是物品和服务在市场上销售的实际价格，是由供求关系决定的。
2.证明：当原问题约束条件右端变为b i′时，原问题变为： maxz=∑C i X js.t. ∑a ij X i≤b i′(i=1,2,3,……,m)X j≥0 (j=1,2,3,……,n)对偶问题为： minp=∑b i′y is.t. ∑a ij y i≥C iy i≥0(i=1,2,3,……,m) (j=1,2,3,……,n) 设，当b i变为b i′原问题有最优解（X1′X2′X3′……X n-1′X n′）时，对偶问题的最优解为（y1′y2′y3′……y n-1′y n′）,则有：又因为当原问题有最优解时，对偶问题也有最优解，且相等，则有：所以3（1）.minp=6y1 + 2y2s.t. -y1+2y2≥-33y1+3y2≥4y1,y2≥0(2)解：令X2=X2′-X2〞，X4= X4′-X4〞，X2′，X2〞，X4′，X4〞≥0 ，原式化为：maxz=2X1 +2X2′-2X2〞-5X3 +2X4′-2X4〞s.t. 2X1 -X2′+X2〞+3X3 +3X4′-3X4〞≤-5-2X1 +X2′-X2〞-3X3 -3X4′+3X4〞≤5-6X1 -5X2′+5X2〞+X3 -5X4′+5X4〞≤-610X1 -9X2′+9X2〞+6X3 +4X4′-4X4〞≤12X1, X2′，X2〞，X3, X4′，X4〞≥0则对偶规划为：.minp= -5y1′+ 5y1〞-6y2 + 12y3s.t. 2y1′-2y1〞-6y2 + 10y3≥2-y1′+y1〞-5y2 -9y3≥2y1′-y1〞+5y2 + 9y3≥-23y1′-3y1〞+y2 + 6y3≥-53y1′-3y1〞-5y2 + 4y3≥2-3y1′+3y1〞+5y2 -4y3≥-2即：minp= -5y1′+ 5y1〞-6y2 + 12y3s.t. 2y1′-2y1〞-6y2 + 10y3≥2-y1′+y1〞-5y2 -9y3=23y1′-3y1〞+y2 + 6y3≥-53y1′-3y1〞+5y2 + 4y3=2令 y1〞- y1′= y1，得：minp= 5y1 -6y2 + 12y3s.t. -2y1-6y2 + 10y3≥2y1-5y2 -9y3=2-3y1+y2 + 6y3≥-5-3y1-5y2 + 4y3=24、试用对偶理论讨论下列原问题与他们的对偶问题是否有最优解。
运筹学 第三章 单纯形法(1,2两节)
第二节 单纯形法
二、基本过程及主要方法
1．如何寻找初始基本可行解X（0）。 初始基本可行解就是迭代开始时的基本可行解。
既然是基本可行解，必须和一个基本矩阵相对应， 这个基本矩阵就是系数列向量组成的满秩矩阵 （参看文献（3）中矩阵部分的内容），但对由m 个系数列向量组成的矩阵判断是否满秩本身就是 一件很不容易的事情，即使满秩了对应的解也不 一定是可行解。参看课本16页例题的最后一部分。
请按如下思路理解：以X（1）、X（2））（X（1）≠X （2））为端点的线段上的任一点都可以表示为[αX（1） +（1-α）X（2）] （0<α<1）当α在（0，1）之间变化时， 上式表示的点就在以X（1）、X（2）为端点的线段上滑 动，（α=1/2时，在二维空间中（初等平面解析几何 中），上式就是中点坐标）。这与前面的定义实质上 是一致的。
因此，是否引入人工变量，必须在观察完所有变量的系数 列向量后才能确定，这一点在做题过程中一定要注意，否则由 于引入了太多的变量会使问题更为复杂。
第二节 单纯形法
（2）用下面的例子说明另一种方法。 如有一个约束条件方程是2X1+3X2-4X3=5,这
可以用以下两个约束条件方程来代替：
2X1+3X2-4X3≤5 2X1+3X2-4X3≥5 在这两个方程中，可分别加进松弛变量或减多 余变量加入人工变量，再求初始基本可行解，但是 有些复杂，一般希望用第一种方法，也可用第四章 的对偶单纯形法直接求解。
简单的说，就是“通过基本矩阵求得的线性规划 问题的解”。
第一节 线性规划问题的几何意义
基本解的形式是 X=（x1*, x2*,…, xm*,0,0,…,0） ， 基变量 非基变量
若每一个分量大于或等于零，这个解就叫基本可行解。 三、 凸集的极点与线性规划问题的基本可行解 定理1 约束条件为AX=b，X≥0线性规划问题的可行解
运筹学
第一章： 建模合理下料问题例1-2：假定现有一批某种型号的圆钢长8m ，需要截取长的毛坯100根、长的毛坯200根，问应怎样选择下料方式，才能既满足需要，又使总的用料最少根据经验，可先将各种可能的搭配方案列出来，如表1-3所示。
例1-2′某一机床需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是，,（m ），这些轴需要用同一种圆钢来做，圆钢长度为。
现在要制造100台机床，最少要用多少圆钢来生产这些轴 方案规格12345678需求量y 1 2 1 1 1 0 0 0 0 100 y 2 0 2 1 0 3 2 1 0 100 y 31 0 1 3 0234 100方案件数 毛坯I Ⅱ Ⅲ Ⅳ需要根数3 2 1 01000 2 4 6200目标函数 minf ＝C1x1+C2x2+…+Cnxn. a11x1+ a12x2+…+a1nxn ≥ b1 a21x1+ a22x2+…+a2nxn ≥ b2 ┇ ┇ ┇ ┇ am1x1+ am2x2+…+amnxn ≥ bmxj ≥0 (j ＝1，2，…，n)运输问题(物资调运问题)例1-3：设某种物资(例如煤炭)共有m 个产地A1、A2 、…、Am ，其产量分别为a1、a2、…、am ；另有n 个销地B1、B2、…、Bn 其销量分别为b1、b2、…、bn 。
已知由产地Ai(i ＝1，2，…，m)运往销地Bj(j ＝1，2，…，n)的单位运价为Cij ，如表1—6所示。
当产销平衡 m n(即∑ai=∑bj 时，问如何调运，才能使总运费最省方式 个 数毛 坯B 1 B 2 … B n需要毛坯数A1A2┇Ama 11 a 12 a 1n a 21 a 22 a 2n ┇ ┇ ┇ a m1 a m2 a mnb 1 b 2 ┇ b mi=1 j=1目标函数 min f=∑∑CijXij 最小i=1 j=1n∑Xij=ai （i＝1，2，…，m）j=1满足 m∑Xij=bj （ j＝1，2，…，n)i=1xij≥0 i＝1，2，…，m；j＝1，2，…，n)第二章：图解法整数规划步骤：写出模型，假设X1,X2…Xn是…1）作可行线2）作等值线3）平移等值线与可行线相交或相切于一点或直线4）例1：见笔记例2例1 某工厂在计划期内要安排工、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A，B两种原材料的消耗，以及资源的限制，如下表所示。
运筹学之单纯形法.ppt
x1 ，x2 ，… ，xn ≥ 0
2.基本过程:
1）加入人工变量;
2）通过单纯形法的迭带,将虚拟的人 工变量从原来的基变量中替换出去, 变成非基变量,使每一个人工变量都 等于0.反之,如果不能都变为非基变 量,表明原问题无可行解.
(一)、大M法：
2.4 单纯形法补遗
2.4.1 进基变量的相持及其突破
Y
结束
N
沿边界找新
的基本可行解
2.1 单纯形法的基本思想
单纯形法的三种形式：1）方程组形式； 2）表格形式；3）矩阵形式。
2.1.1 方程组形式的单纯形法
maxZ=3X1 +5X2
X1
+X3
=8
2X2 +X4 =12
3X1+4X2
+X5 =36
X1 … X5 0
解：(1)、确定初始可行解
B=(a3 a4 a5)=I Z -3X1-5X2 =0 X3 =8- X1 X4=12-2X2
此时可以确定X5为离基变量
Z
+1/2X4 +X5 =42
X3 +2/3X4 -1/3X5 =4
X2 +1/2X4 =6
X1 -2/3X4+1/3X5=4
令X4 =X5 =0
X =(4, 6, 4, 0, 0)T Z =42
。此时4=1/2, 5=1, Z值不
再增大了,X值是最优基本解
即:X*=(4,6)T,Z*=42
X6
X7
CB XB -36 M -M -6 -M -4 0
0
M
0
0
0
X3 100
2
3
1
00
0
2.基本过程:
1）加入人工变量;
2）通过单纯形法的迭带,将虚拟的人 工变量从原来的基变量中替换出去, 变成非基变量,使每一个人工变量都 等于0.反之,如果不能都变为非基变 量,表明原问题无可行解.
(一)、大M法：
2.4 单纯形法补遗
2.4.1 进基变量的相持及其突破
Y
结束
N
沿边界找新
的基本可行解
2.1 单纯形法的基本思想
单纯形法的三种形式：1）方程组形式； 2）表格形式；3）矩阵形式。
2.1.1 方程组形式的单纯形法
maxZ=3X1 +5X2
X1
+X3
=8
2X2 +X4 =12
3X1+4X2
+X5 =36
X1 … X5 0
解：(1)、确定初始可行解
B=(a3 a4 a5)=I Z -3X1-5X2 =0 X3 =8- X1 X4=12-2X2
此时可以确定X5为离基变量
Z
+1/2X4 +X5 =42
X3 +2/3X4 -1/3X5 =4
X2 +1/2X4 =6
X1 -2/3X4+1/3X5=4
令X4 =X5 =0
X =(4, 6, 4, 0, 0)T Z =42
。此时4=1/2, 5=1, Z值不
再增大了,X值是最优基本解
即:X*=(4,6)T,Z*=42
X6
X7
CB XB -36 M -M -6 -M -4 0
0
M
0
0
0
X3 100
2
3
1
00
0
运筹学_单纯形法_的应用举例
(x11+x21+x31)≤100
(x12+x22+x32)≤100
(x13+x23+x33)≤60
通过整理，得到以下模型：
2010年8月
管理工程学院
《运筹学》
11
目标函数：Max z = -15x11+25x12+15x13-30x21+10x22-40x31-10x33 约束条件： s.t. 0.5 x11-0.5 x12 -0.5 x13 ≥ 0 （原材料1不少于50%） -0.25x11+0.75x12 -0.25x13 ≤ 0 （原材料2不超过25%） 0.75x21-0.25x22 -0.25x23 ≥ 0 （原材料1不少于25%） -0.5 x21+0.5 x22 -0.5 x23 ≤ 0 （原材料2不超过50%）
解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样 我们建立数学模型时，要考虑： 对于甲： x11，x12，x13； 对于乙： x21，x22，x23； 对于丙： x31，x32，x33； 对于原料1： x11，x21，x31； 对于原料2： x12，x22，x32； 对于原料3： x13，x23，x33； 目标函数： 利润最大，利润 = 收入 - 原料支出 约束条件： 规格要求 4 个； 供应量限制 3 个。
x21 x22 x23 x24 250000 产量约束为飞机汽油2的产量：
PV p j v j可得有关蒸汽压力的约束条件： 由物理中的分压定律，
n
2.85 x11 1.42 x12 4.27 x13 18.49 x14 0
同样可得有关辛烷数的约束条件16.5 x11 2.0 x12 4.0 x13 17.0 x14 0 为： 7.5x 7.0 x 13.0 x 8.0 x 0
运筹学 (单纯形法原理)
x3 = 6 – 2x1 + 2/5x5 x4 = 16 – 4x1 x2 = 3 –1/5 x5
x3 = 6 – 2 θ ≥0 x4 = 16 – 4 θ ≥0 x2 = 3 ≥0
即：
x1 = θ =min{6/2，16 /4 ，~}=3 相应地有：
x3 = 6 – 2 × 3 =0 x4 = 16 – 4 × 3=4 x2 = 3
xni bi aij x j
j 1
n
（i 1, 2,L , m）
3.代入目标消去基变量，得到非基变量xj的检验数 j
Z c j x j cni xni
j 1 i 1
n Z c j x j cni b a x i ij j j 1 i 1 j 1 n m
b1 M M M 0 .1L bi M M M 0 0L 1 bm
表格单纯形法
max Z c1 x1 c2 x2 cn xn cn1 xn1 cnm xnm
标准型：
a11 x1 a12 x 2 a1n x n x n 1 b1 a x a x a x x b 21 1 22 2 2n n n2 2 s.t. a x a x a x x m2 2 mn n n m bm m1 1 x1 , x 2 , , x n , x n 1 , , x n m 0
m
cni bi (c j cni aij ) x j
i 1 j 1 i 1
m
n
m
j cj zj
n j 1
Z Z 0 (c j z j ) x j Z 0 j x j
运筹学(3)1-3_单纯形法第1部分
运 筹 学
运 筹 帷 幄 之 中
Operations Research
决 胜 千
线性规划
Linear Programming
里 之 外
第四节 单纯形法
线性规划单纯形(Simplex)法
单纯形法(Simplex Method)是美国人丹捷 格 (G.Dantzig)1947年创建的 这种方法简捷、规范，是举世公认的解决线 性规划问题行之有效的法。 单纯形法的表现形式：
⑤根据max{j｜j＞0}=k原则，确定xk为换入变量(进基 变量)，再按规则计算：=min{bi/aik| aik ＞0}=bl/ aik 确定xBl为换出变量。建立新的单纯形表，此时基变量 中xk取代了xBl的位置。
⑥以aik为主元素进行迭代，把xk所对应的列向量变为单位列 向量，即a 变为1，同列中其它元素为0，转第③ 步。
Z
( 0)
0
(x4=3，x5=9), 三种产品的总利润为0！
第四步：分析两个基本表达式，看看目 标函数是否可以改善？
① 分析用非基变量表示目标函数的表达式
Z 2 x1 3x2 3x3
非基变量前面的系数均为正数，所以任何一 个非基变量进基都能使Z值增加 通常把非基变量前面的系数叫“检验数”；
Z 2 x1 3 x2 3x3 2(3 x2 x3 x4 ) 3 x2 3 x3 6 x2 x3 x4
可得相应的目标函数值为Z（1）=6
检验数仍有正的
返回①进行讨论。
Z c j x j c j x j cni xni c j x j cni (bi aij x j )
m
令Z 0 cnibi ,
i 1
运 筹 帷 幄 之 中
Operations Research
决 胜 千
线性规划
Linear Programming
里 之 外
第四节 单纯形法
线性规划单纯形(Simplex)法
单纯形法(Simplex Method)是美国人丹捷 格 (G.Dantzig)1947年创建的 这种方法简捷、规范，是举世公认的解决线 性规划问题行之有效的法。 单纯形法的表现形式：
⑤根据max{j｜j＞0}=k原则，确定xk为换入变量(进基 变量)，再按规则计算：=min{bi/aik| aik ＞0}=bl/ aik 确定xBl为换出变量。建立新的单纯形表，此时基变量 中xk取代了xBl的位置。
⑥以aik为主元素进行迭代，把xk所对应的列向量变为单位列 向量，即a 变为1，同列中其它元素为0，转第③ 步。
Z
( 0)
0
(x4=3，x5=9), 三种产品的总利润为0！
第四步：分析两个基本表达式，看看目 标函数是否可以改善？
① 分析用非基变量表示目标函数的表达式
Z 2 x1 3x2 3x3
非基变量前面的系数均为正数，所以任何一 个非基变量进基都能使Z值增加 通常把非基变量前面的系数叫“检验数”；
Z 2 x1 3 x2 3x3 2(3 x2 x3 x4 ) 3 x2 3 x3 6 x2 x3 x4
可得相应的目标函数值为Z（1）=6
检验数仍有正的
返回①进行讨论。
Z c j x j c j x j cni xni c j x j cni (bi aij x j )
m
令Z 0 cnibi ,
i 1
运筹学——3.单纯形矩阵描述与改进单纯形法
32
计算B的逆矩阵
（6）计算RHS
1 / 2 8 2 1 1 B1 b 1 0 16 16 1 / 4 12 3
23
第2节 改进单纯形法
第1步计算结束后的结果
基 B1 P3 , P4 , P2 ; 基变量 X B1 x3 , x4 , x2 ;
22
（5）计算非基变量的系数矩阵
1 / 2 1 1 1 1 N1 4 B1 N1 1 0 4 1 1 / 4 1 1 1 / 2 4 0 1/ 4
B2 1b i 1 min 1 B2 P5 0 B P 2 5 i 2 8 3 min , , 4 对应x4 1/ 2 2 1/ 4
31
基变换：
新的基
B3 P , P5 , P2 ; 1 换入变量x5 的系数向量是 1 0 1 / 2 0 1 / 2 1 B2 P5 4 1 2 0 2 主元素 0 0 1 / 4 1 1 / 4
确定换出变量
B11b i 1 min 1 B1 P 0 1 B P 1 1 i 2 16 3 min , , 2 对应x3 1 4 0
26
由此得到新的基
B2 P , P4 , P2 1 1 1 B1 P 4 1 0 1 1 0 0 2 4 E2 4 1 0 0 0 0 1 1 0 0 1 0 1/ 2 1 1 B2 E2 B1 4 1 0 0 1 0 0 0 1 0 0 1/ 4 1 0 1/ 2 4 1 2 0 0 1/ 4
运筹学03-单纯形法
C
m n
m个!n。n! m!
定义 在线性规划问题的一个基本可行解中，如果
所有的基变量都取正值，则称它为非退化解，如
果所有的基本可行解都是非退化解。称该问题为
非退化的线性规划问题；若基本可行解中，有基 变量为零，则称为退化解，该问题称为退化的线 性规划问题。
21
解的集合： 解空间
非
基
可 行 解
可本 行可 解行
16
解：① 令X3 =X4 - X5 ② 加松弛变量X6 ③加剩余变量X7 ④ 令Z'= -Z
Max Z'= X1 -2X2 +3X4 -3X5 X1 +X2 +X4 -X5 +X6=7
s.t X1 -X2 +X4 -X5 -X7 =2
X1 , X2 , X4 , … , X7 0
17
3.2 线性规划问题的解
5
向量形式
Max Z CX
s.t
n
Pj x j
b
C c1
c2
cn
j1
X 0
价值向量
x1
X
x2
xn
决策向量
a1 j
Pj
a2 j
anj
列向量
b1
b
b2
bm
右端向量
6
(4) 一般型向标准型的转化
对于各种非标准形式的线性规划问题，我们总可 以通过以下变换，将其转化为标准形式: 目标函数
x1
,
x2 ,
x3 ,
x4
0
(2) 求基本解
由上式得
A
3 6
5 2
1 0
10 b 1254
运筹学一般单纯形法
1
0 0 0 1
0
1 0 0 0
0
0 1 0 -2
3
6 2 →
Cj-Zj
0
2
0
4
x4
x2 →
8
15
3 P1
10 P2
0 P3
0 P4
θi
注
3
-1
4
5
1
0
0
1
段 1 cj-zj
cj ↓ 0 0
→
0
3
10
0
0
基
x3 x4 →
b
24 15
P1
3 -1 3
P2
4 5 10
P3
1 0 0
P4
0 1 0
θi
注
步骤4.2：判断
（１）若所有检验数均≤０时，即得到最优解和 最优值； （２）若检验数存在正值，继续下一步。
3
0 3 1 3
2
（1） 4 0 0
0
0 0 1 0
1
0 0 0 1
0
1 0 -2 -2
6
2 →
Cj-Zj
0 2 0
4
x2
→
2
0
1
0
0
1
Cj-Zj
Cj 段 ↓
→ 基
0 b
3 P1
4 P2
0 P3
0 P4
0 Qi P5 注
0
1 0 0
x3
x4 x5 → x3
6
12 2 0 2
1
3 0 3 1
2
2 （1） 4 0
用主元列对应的变量（入基变量/调入变量）代替之，进入 下一段。
运筹学 第3章 运输问题
第三章运输问题在生产实际中，经常需要将某种物资从一些产地运往一些销地，因而存在如何调运使总的运费最小的问题。
这类问题一般可用线性规划模型来描述，当然可以用单纯形法求解。
但由于其模型结构特殊，学者们提供了更为简便和直观的解法—-表上作业法。
此外,有些线性规划问题从实际意义上看，并非运输问题，但其模型结构类似运输问题，也可以化作运输问题进行求解。
第一节运输问题及其数学模型首先来分析下面的问题。
例3。
1农产品经销公司有三个棉花收购站，向三个纺织厂供应棉花。
三个收购站A1、A2、A3的供应量分别为50kt、45kt和65kt，三个纺织厂B1、B2、B3的需求量分别为20kt、70kt和70kt。
已知各收购站到各纺织厂的单位运价如表3-1所示（单位：千元/kt)，问如何安排运输方案，使得经销公司的总运费最少?设x ij表示从A i运往B j的棉花数量，则其运输量表如下表所示。
表3—2由于总供应量等于总需求量，因此，一方面从某收购站运往各纺织厂的总棉花数量等该收购站的供应量，即x11+x12+x13 = 50x21+x22+x23 = 45x31+x32+x33 = 65另一方面从各收购站运往某纺织厂的总棉花数量等该纺织厂的需要量,即x 11+x 21+x 31 = 20 x 12+x 22+x 32 = 70 x 13+x 23+x 33 = 70因此有该问题的数学模型为min f= 4x 11+8x 12+5x 13+6x 21+3x 22+6x 23+2x 31+5x 32+7x 33x 11+x 12+x 13 = 50 x 21+x 22+x 23 = 45 x 31+x 32+x 33 = 65 x 11+x 21+x 31 = 20 x 12+x 22+x 32 = 70 x 13+x 23+x 33 = 70x ij ≥0，i=1，2，3；j=1，2，3 生产实际中的一般的运输问题可用以下数学语言描述。
运筹学1-4单纯型法的计算步骤
2 X1 1 3 X2 2
Z8
1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 0 0 -1 -5/3 -1/3
从最优表可知: 该LP的
最优解是X*=(1, 2, 0, 0, 0)T 相应的目标函数最优值是Zmax=8
表格单纯形法求解步骤
第一步：将LP化为标准型，并加以整理。
引入适当的松驰变量、剩余变量和人工变量 ，使约束条件化为等式，并且约束方程组的系数 阵中有一个单位阵。
（这一步计算机可自动完成）
确定初始可行基，写出初始基本可行解
第二步：最优性检验
计算检验数，检查： 所有检验数是否≤ 0？
是——结束，写出最优解和目标函数最优值； 还有正检验数——检查相应系数列≤ 0？
是——结束，该LP无“有限最优解”！ 不属于上述两种情况，转入下一步—基变换。
确定是停止迭代还是转入基变换？
0 1 0
0
0
1
0
0
0
1 c1 c2
0 a1,m1 a1,m2 0 a2,m1 a2,m2
1 a a m,m1 m,m2 cm cm1 cm2
a1,n b1
a2,n
b2
am,n bm
cn 0
-Z，x1，…，xm所对应的系数 列向量构成一个基
用矩阵的初等行变换将该基变成单位阵,这时
c1, c2 , , cm 变成0，相应的增广矩
第四步：判断检验数、入基、出基变量。 …….
三、表格单纯形法：
1、 初始单纯形表的建立 (1)表格结构：
Cj 2 3 3 0 0
CB
XB
b xj
x1 x2 x3 x4 x5
j
0 X4
3
第3章 线性规划的单纯形法《管理运筹学》PPT课件
当第一阶段求解结果表明问题有可行解时，第二阶段 是在原问题中去除人工变量，并从此可行解（第一阶段的 最优解）出发，继续寻找问题的最优解。
3.3 关于单纯形法的进一步讨论
根据以上思路，我们用二阶段法来求解下面例题： max z=3x1-x2-x3
x1-2x2+x3≤11 s.t. -4x1+x2+2x3≥3
,
C
CB CN
线性规划问题成为 max z=CBTXB+CNTXN+ CIT XI s.t. BXB+NXN+IXI=b XB，XN，XI≥0
3.2 单纯形法原理
这个线性规划问题可以用表3-1来表示：
表3-1称为初始单纯形表。可以看出，单纯形表中 直接包含了单纯形迭代所需要的一切信息。
3.2 单纯形法原理
3.1 线性规划的基本理论
1.可行区域的几何机构 考虑标准的线性规划问题：
min cT x
Ax b
s.t.
x
0
用Rn表示n维的欧式空间，这里x Rn，c Rn ，b Rn
，A Rmn . 不妨设可行区域 D {x Rn | Ax b, x 0} ，因此线性方程组 Ax b 相容，总可以把多余方程去掉，
3.2 单纯形法原理
1. 单纯形表的结构 设线性规划问题为 max z=CTX+CIT XI s.t. AX+XI=b X，XI≥0 设B是线性规划的一个可行基，为了表达简便，不妨
设这个基B包含在矩阵A中，即 A=[B，N]
3.2 单纯形法原理
变量X和目标函数系数向量C也相应写成：
X
XB XN
3.2 单纯形法原理
第三步：在基变量用非基变量表出的表达式中，观 察进基变量增加时各基变量变化情况，在进基变量增加 过程中首先减少到0的基变量成为“离基变量”.当进基 变量的值增加到使离基变量的值降为0时，可行解移动到 相邻的极点。
3.3 关于单纯形法的进一步讨论
根据以上思路，我们用二阶段法来求解下面例题： max z=3x1-x2-x3
x1-2x2+x3≤11 s.t. -4x1+x2+2x3≥3
,
C
CB CN
线性规划问题成为 max z=CBTXB+CNTXN+ CIT XI s.t. BXB+NXN+IXI=b XB，XN，XI≥0
3.2 单纯形法原理
这个线性规划问题可以用表3-1来表示：
表3-1称为初始单纯形表。可以看出，单纯形表中 直接包含了单纯形迭代所需要的一切信息。
3.2 单纯形法原理
3.1 线性规划的基本理论
1.可行区域的几何机构 考虑标准的线性规划问题：
min cT x
Ax b
s.t.
x
0
用Rn表示n维的欧式空间，这里x Rn，c Rn ，b Rn
，A Rmn . 不妨设可行区域 D {x Rn | Ax b, x 0} ，因此线性方程组 Ax b 相容，总可以把多余方程去掉，
3.2 单纯形法原理
1. 单纯形表的结构 设线性规划问题为 max z=CTX+CIT XI s.t. AX+XI=b X，XI≥0 设B是线性规划的一个可行基，为了表达简便，不妨
设这个基B包含在矩阵A中，即 A=[B，N]
3.2 单纯形法原理
变量X和目标函数系数向量C也相应写成：
X
XB XN
3.2 单纯形法原理
第三步：在基变量用非基变量表出的表达式中，观 察进基变量增加时各基变量变化情况，在进基变量增加 过程中首先减少到0的基变量成为“离基变量”.当进基 变量的值增加到使离基变量的值降为0时，可行解移动到 相邻的极点。
运筹学-3对偶单纯形法
1.对偶单纯形法的应用条件； 2.出基与进基的顺序； 3.如何求最小比值； 4.最优解、无可行解的判断。 作业：教材P76 T2.7
The End of Section 3
灵敏度分析 Exit
即对偶问题具有无
界解，由性质2a知ik 原问a题Lj 无可行解。aik
§2.3 对偶单纯形法 The Dual Simplex Method
Ch2 Dual Problem
2020年6月20日星期六 Page 9 of 9
本节利用对偶性质6：原问题的检验数与对偶问题的基本 解的对应关系，介绍了一种特殊线性规划的求解方法—对 偶单纯形法。
0
-4
-1
0
-1
— 1.6 — —
2
x2
0.4
0
1 -0.2 -0.4 0.2
x1
2.2
1
0
1.4 -0.2 -0.4
检验数 5.6
0
0 -1.8 -1.6 -0.2
最优解： x2=0.4 x1=2.2
Max z = -5.6
§2.3 对偶单纯形法 The Dual Simplex Method
Ch2 Dual Problem
【解】先将约束不等式化为等式，再两边同乘以（－1）， 得到
min z 2x1 3x2 4x3
x1 2x2 x3 x4 3
2x1 x2 3x3 x5 4
x
j
0,
j
1,2,
,5
用对偶单纯形法，迭代过程如下页或看演示(请启用宏)。
§2.3 对偶单纯形法 The Dual Simplex Method
问题中，λ≤j0分母aij<0，
j
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
单纯形法的基本思路
单
单纯形法
单纯形表迭代过程
纯
有关名词、概念
形
目标函数为最小的问题段法
选择基本矩阵的方法总结
解的讨论 解的四种形式及判断方法
改进单纯形法 改进单纯形法的优点
第一节 线性规划问题的几何意义
本节主要介绍凸集的概念及凸集的顶点与 线性规划问题可行解的关系，为理解单纯形法 的解题思路打下基础。
第一节 线性规划问题的几何意义
线性规划问题的解 1.可行解 ：满足线性规划问题全部约束条件的解。 所有可行解的集合称为可行域。 2.最优解 ：在线性规划问题的可行解中，使目标函 数值达到最优的解。 3.基本解及基本可行解
在线性规划问题约束条件方程中，由与约束条 件个数相等的若干个系数列向量组成的满秩矩阵叫 基本矩阵。 一个有n个变量m个约束（m≤n）的线 性规划问题至多可以有Cnm个基本矩阵所谓满秩矩 阵，就是给这个矩阵作行线性变换不会出现某一行
第一节 线性规划问题的几何意义
X（1） X（2）
（A）
X（1）
X（2）
（B）
第一节 线性规划问题的几何意义
凸集定义的另外一种表示形式： 设X（1）、X（2） （X（1）≠X（2））是n维欧氏空间（高 等数学中常用名词，参看文献（3）中的一个点集， 任意两点X（1）、X（2）∈K 的连线上一切点[αX（1）+ （1-α）X（2）] ∈K（0<α<1）,则称K为凸集。
第一节 线性规划问题的几何意义
全为零的情况(与方程组有关的线性变换不考虑列变 换)；所谓矩阵的行线性变换就是给矩阵的某一行元素 同乘以一个非零常数或给矩阵的某一行同乘以非零常 数后再加到另一行，过程与我们中学学过的解方程组 的消元法完全一致。详细内容请参看文献（3）中与 此有关的内容。
令不与基本矩阵中列向量对应的变量（这些变量 就叫非基变量 ）为零后，约束方程中剩余的与基本矩 阵对应的变量就可唯一求得（这些变量就叫基变量）， 求得的这个解就叫基本解（参看课本16页）。
有了定理5，求线性规划问题的最优解可不必在无穷 多的可行解中搜索，只需在有限个基本可行解中搜 索即可。虽然基本可行解至多有个，当n、m较大时， 仍是一个很大的数字。
第一节 线性规划问题的几何意义
例如: 当n=5，m=2，基本矩阵的个数 可能为10个，所谓可能为，就说明还有一 些不是，这还需要一个一个的判断。所以 对比较大是线性规划问题用穷举法将所有 的基本可行解都找出并计算其目标函数值， 选取最优，计算量很大甚至是行不通的。 著名的单纯形法用迭代法而不用穷举法很 好地解决了这个问题。
第二节 单纯形法
二、基本过程及主要方法
1．如何寻找初始基本可行解X（0）。 初始基本可行解就是迭代开始时的基本可行解。
既然是基本可行解，必须和一个基本矩阵相对应， 这个基本矩阵就是系数列向量组成的满秩矩阵 （参看文献（3）中矩阵部分的内容），但对由m 个系数列向量组成的矩阵判断是否满秩本身就是 一件很不容易的事情，即使满秩了对应的解也不 一定是可行解。参看课本16页例题的最后一部分。
第一节 线性规划问题的几何意义
2.极点: 设K是凸集，X∈K ；若X不能用不同的 两点X(1) ∈K ， X(2) ∈K 的线性组合表示为 X=αX（1）+（1-α）X（2） （0<α<1） ，则称此 点是K的一个极点或顶点，其直观意义就是X 不是K中任何线段的内点，也就是说点X不能 在以K内的任意两点为端点的线段上。如三角 形、长方体的顶点就是凸集的集点。
简单的说，就是“通过基本矩阵求得的线性规划 问题的解”。
第一节 线性规划问题的几何意义
基本解的形式是 X=（x1*, x2*,…, xm*,0,0,…,0） ， 基变量 非基变量
若每一个分量大于或等于零，这个解就叫基本可行解。 三、 凸集的极点与线性规划问题的基本可行解 定理1 约束条件为AX=b，X≥0线性规划问题的可行解
第二节 单纯形法
本节主要介绍单纯形法的计算步骤及线性 规划解的讨论方面的内容
一．单纯形法的基本思路
求出线性规划问题的初始基本可行解X（0），并充分 运用它提供的信息，编制初始单纯形表。
判别X（0）是否最优？为此，需要建立一个判别标准。 如X（0）不是最优，就将一个基变量换出，将一个非 基变量换入，组成另一组基本可行解，迭代为另一张 单纯形表，使新的目标函数值较原有的为优。如此逐 步迭代，若问题有最优解，那么经有限次迭代就可求 出最优解。
集是凸集。 定理3 线性规划问题的基本可行解 X对应于可行域D的
极点。
第一节 线性规划问题的几何意义
定理4 线性规划问题若有可行解必有基本可行解。换句 话说，线性规划问题的可行域D如为非空凸集，则 必有极点。
定理5 线性规划问题若有最优解，则一定可以在可行域 D的极点上达到。
注意：这并不是说，只有极点才能使目标函数值最大， 其它点不能。而是说，如在其它点上使目标函数值 达到最大，则一定可以找到一个极点X（m）使目标 函数值达到此最大值。
第三章 单纯形法
本章主要介绍求解线性规划问题的单纯形 法及解的类型，其基本要求为：
1. 理解凸集的极点（顶点）与线性规划问题 解的关系。
2. 熟练掌握单纯形法的迭代过程和应用。 3. 熟悉线性规划问题的标准型掌握两阶段法
和大M法。 4.了解改进单纯形法。
知识结构
凸集、线性规划问题的解
解的几何意义 凸集的极点与基本可行解
请按如下思路理解：以X（1）、X（2））（X（1）≠X （2））为端点的线段上的任一点都可以表示为[αX（1） +（1-α）X（2）] （0<α<1）当α在（0，1）之间变化时， 上式表示的点就在以X（1）、X（2）为端点的线段上滑 动，（α=1/2时，在二维空间中（初等平面解析几何 中），上式就是中点坐标）。这与前面的定义实质上 是一致的。
在上一章第三节我们已经得出这样的结论，若两 个或三个变量的线性规划问题的最优解存在，则可以 在问题的可行域的顶点上达到。这个结论可以推广到 三个以上变量的线性规划问题上去，以下内容是与此 有关的说明与论证。
凸集。若任意两点X（1）、X（2） （X（1）≠X（2））在 某个点集中，且连接这两点的线段上的所有点也在这 个点集之中，称这个点集为凸集。