运筹学 第二章 单纯形法

运筹学单纯形法
运筹学单纯形法，又称单纯性法，是一种用于求解线性规划问题的数学方法，它在运筹学中发挥着重要作用。

它主要应用于决策及资源分配问题，可以帮助决策者更好地把握资源的优化配置，并寻求最优解。

单纯性法是以线性规划问题作为理论基础，它是将该问题转化为一系列形如Ax=b的线性方程组的运筹学方法。

在这个方程组通过调整方程中的系数和右面常数而变换为形如Cx≤d的不等式形式，而这种不等式系统称为单纯性约束条件。

单纯性法从不等式中寻找一系列基向量，并通过改变基向量来实现改变不等式的求解方程之间的关系，从而求出最优解的问题。

传统的单纯性法分为有界单纯性和无界单纯性两种情形。

无界单纯性以简单费用曲线方法、扩展的简单费用曲线方法和增广次数法三大类。

有界单纯性主要是对对角单纯性和非对角单纯性这两类单纯性系统分别使用不同的方法进行求解。

单纯性求解方法在线性规划问题求解中具有重要应用，它能通过求解线性规划问题中的一系列互不相关的子问题来求出最优解。

使用该方法，可以以最少的成本达到最优的收益，它包括费用最低优化、网络流优化、全格研究和数学优化模型等。

12/3 4
z
1 2
x4
x5 42
x3
2 3
x4
1 3
x5
4
新典式
主元化 为1，主 元所在
x2
1 2
x4
6
列的其 余元素
x1
2 3
x4
1 3
x5
4
化为0
观察最后一个典式，所有检验数均为非负， 故其对应的基本可行解为最优解，即
X * 4,6,6,0,0T z* 42
去掉引入变量，得原问题的最优解为：
运筹学课件
目录
运筹学概论 第一章 线性规划基础 第二章 单纯形法 第三章 LP对偶理论 第四章 灵敏度分析 第五章 运输问题 第六章 整数规划 第七章 动态规划 第八章 网络分析
第二章 单纯形法
(SM-Simplex Method)
1947年，美国运筹学家Dantzig提出，原理是 代数迭代。
单纯形法中的单纯形的这个术语，与该方法毫 无关系，它源于求解方法的早期阶段所研究的一 个特殊问题，并延用下来。
CB B1b B1b
z
CB B1N CN X N X B B1NX N
CB B1b B1b
上述方程组的矩阵形式为
10
0 I
CB
B1N B1N
CN
z XB XN
CB B1b B1b
上式的系数增广阵称为对应于基B的单纯形表：
T(B)
CB B1b B1b
0 I
CB
B1N B1N
CN
形式的LP问题，必须解决三个问题： ⑴初始基本可行解的确定； ⑵解的最优性检验； ⑶基本可行解的转移规则。 这里先放一下⑴，研究⑵和⑶，为此，

第一步：求对偶问题的可行基 B ，列出单纯形表。 n n aij x j bi (i 1,, m) max z c j x j j 1 j 1 x j 0 ( j 1,, n) cj CB c1 c2 … cm 基 x1 x2 … xm cj - zj b b*1 b*2 … b*m c1 x1 1 0 … 0 0 … … … … … … cm xm 0 0 … 1 0 … … … … … cj xj a1j a2j … amj … … … … … cn xn a1n a2n … amn
cj CB 0 0
0 y4 1 0 0
0 y5 0 1 0
[ -6 ]
-2 -24
cj-zj
max w 15 y1 24 y2 5 y3 0 y4 0 y5
6 y2 y3 y4 2 y5 1 5 y1 2 y2 y3 y 0 15
min w 15 y1 24 y2 5 y3
6 y 2 y3 2 5 y1 2 y 2 y3 1 y 0 13
max w 15 y1 24 y2 5 y3 0 y4 0 y5
化标 准形
6 y2 y3 y4 2 y5 1 5 y1 2 y2 y3 y 0 15
影子价格(shadow price)
是反映资源最优使用效果的价格。 用微积分描述资源的影子价格，即当资源增加一个数量而得到目标函 数新的最大值时，目标函数最大值的增量与资源的增量的比值，就是目标 函数对约束条件（即资源）的一阶偏导数。 用线性规划方法求解资源最优利用时，即在解决如何使有限资源的总 产出最大的过程中，得出相应的极小值，其解就是对偶解，极小值作为对 资源的经济评价，表现为影子价格。 这种影子价格反映劳动产品、自然资源、劳动力的最优使用效果。 另外一种影子价格用于效用与费用分析。广泛地被用于投资项目和进 出口活动的经济评价。例如，把投资的影子价格理解为资本的边际生产率 与社会贴现率的比值时，用来评价一笔钱用于投资还是用于消费的利亏； 把外汇的影子价格理解为使市场供求均衡价格与官方到岸价格的比率，用 来评价用外汇购买商品的利亏，使有限外汇进口值最大。 因此，这种影子价格含有机会成本即替代比较的意思，一般人们称之 为广义的影子价格。

产，已知生产单位产品所需的设备台时及A、B两种 原材料的消耗，以及资源的限制如下表所示：
甲 乙 设备 1 1 原料A 2 1 原料B 0 1 单件利润 50（元/件） 100（元/件）
Байду номын сангаас
资源限制 300台时 400千克 250千克
问:工厂应分别生产多少个产品甲、乙才能使工厂获利最多？
设生产甲产品x1个，生产乙产品x2个
j 1
n
n aij x j (或 ， ）bi (i 1, 2, , m) s.t. j 1 x 0( j 1, 2, , n) j
n j 1 n p j x j (或 ， ）b s.t. j 1 x 0( j 1, 2, , n) j
x2 B
C z=27500=50x1+100x2 z=20000=50x1+100x2 D z=0=50x1+100x2 E
A
z=10000=50x1+100x2
x1
图2-2
解的几种可能结果
唯一最优解解 无穷多个最优解 无界解(可行域无界，常为模型遗漏了某些 必要的约束条件) 无可行解（可行域为空集，约束条件自相矛 盾,资源满足不了人们的需求）
(2) MinZ Max(Z ) 3 y1 5 x2 y2 y3
(3) 3 y1 2 x2 y2 y3 6
3 y1 2 x2 y2 y3 6
(4)在第一、第三约束左端加上松弛变量 x4,x6≥0 ，在第二约束左端减去剩余变量 x5≥0
解:
2x1+x2=400 x2=250
100
100 200 300
x2≤250