2-4对偶单纯形法

若新增约束如下：
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

y4 y5 cj
－2 －1 0
15 24 5 y1 y2 y3 0 ［－6］ ［－ ］ －1 －2 －1 －5 15 0 －5 15 －5/4 15/2 15/2 24 1 0 0 1 0 0 5 1/6 [-2/3] 1 0 1 0
0 y4 1 0 0 －1/6 －1/3 4
0 y5 0 1 0 0 1 0
C-CBB-1A≥0
对于标准线性规划问题：
min f = CX
max z = bY
s.t. AT Y ≥ C
AX = b s.t. X ≥ 0
最优基B
可行基B 对偶可行基B 单纯形法 保持可行性 对偶单纯形法 保持对偶可行性
可行基B
对偶可行基B
可行基B
对偶可行基B
对于标准线性规划问题：
min f = CX AX = b s.t. X ≥ 0
•
下面通过例题说明对偶单纯形法的步骤：
例3 用对偶单纯形法求解线性规划问题： min w = 15 y1 + 24 y2 + 5 y3
6 y2 + y3 ≥ 2 y1 + 2 y2 + y3 ≥ 1 ：先将问题改写为：
' min w = 15 y1 + 24 y2 + 5 y3 min w = 15 y1 + 24 y2 + 5 y3 + 0 y4 + 0 y5
对偶单纯形法
对偶单纯形法并不是求解对偶问题解的方法，而是利 用对偶理论求解原问题的解的方法。 对于标准线性规划问题：
min f = CX AX = b s.t. X ≥ 0
max z = bY T s.t. A Y ≥ C

对偶单纯形法例题详细步骤
对偶单纯形法是一种常用的解除线性规划问题的数学方法，由美国数学家鲍门士（George B. Dantzig）在1950年提出，早期更多用于研究管理科学问题，现在广泛用于线性规划问题的求解。

先来回顾一下线性规划的定义：给定线性约束条件和目标函数，要求寻找这样一组变量使目标函数极值化，称为线性规划问题，其中的线性约束条件主要可以分为等于约束和不等于约束，可以分为最大化型和最小化型。

由于线性规划问题本身涉及到多个变量约束严格，可能由于几何等原因不容易采取直接解决，而且有可能会涉及到多目标求解，因此对偶单纯形法是一种更为合理的求解方法。

该方法的目标是建立一个对偶问题，该问题只有一个变量，可以用单纯形法解决。

通过构建相应的对偶问题，将多个目标变量整合为一个，用一个变量来表示即可，这样只需解决一个线性规划问题，就可以根据对偶变量的极值情况，求出原始变量的最优解。

具体到此例来说，我们的目标就是要找出最优解。

我们先要把问题抽象为一个线性规划问题，它包括等式约束条件和不等式约束。

接下来我们可以根据问题性质来分析模型，确定问题的类型，然后找出原始最优解，剩余的就是利用对偶单纯形法求解，方法往往是把原始的规划问题转换为对偶的单纯形问题，求出对偶变量的最优解，再把它转换成原始问题的最优解。

总之，对偶单纯形法是一种非常灵活有效的求解线性规划问题的数学方法，其安全可靠性被广泛应用于解决众多线性规划问题。

X4 19 2 4/3 0 X3 50 -1/2 -1/3 1 σj= cj - zj -4 -2/3 0
X4 X5 X6 19 0 0 1 2/3 -10/3 0 -1/6 4/3 0 -13/3 -10/3
bθ
2 1 Z = 88
∴ 最优生产计划是：生产1个单位产品C，生产2个单位产 品D，不生产A、B产品。可得最大总利润 88 个单位。
可能改变 C – CBB-1A ≤ 0 变
求出使该表达式仍然成立的 C 的变化范围
若 C 的变化超出该范围，则原最优解将改变
例1：某工厂用甲、乙两种原料生产A、B、C、 D
四种产品，要求确定总利润最大的最优生产 计划。该问题的线性规划模型如下：
Max Z = 9 x1 +8x2 + 50x3 + 19x4
则：在原最终单纯形表上，新变量对应的系数列为Pj '= B-1Pj，
检验数为 σj= Cj – CBB-1 Pj
若 σj= Cj – CBB-1 Pj ≤ 0，则原最优解不变；
若 σj= Cj – CBB-1 Pj ≥ 0，则继续迭代以求出新的最优解。
例3： 沿用例1 ►
如果该工厂考虑引进新产品E ，已知生产 E 产品1 个单位要消耗甲材料3个单位和乙材料1个单位。
要求：⑶产品E 的利润达到多少时才值得投产？
解： 设生产 E 产品X7个单位，单位产品的利润为C7，
则模型变为：
Max Z = 9 x1 +8x2 + 50x3 + 19x4 + 0x5 + 0x6+ C7x7 3x1+ 2 x2 + 10 x3 + 4 x4 + x5 + 3 x7 = 18（甲材料） 2x3+ 1/2x4 + x6 + x7 = 3 （乙材料）