当前位置：文档之家 › 运筹学课件 第二章-对偶问题

运筹学课件 第二章-对偶问题

  • 格式：ppt
  • 大小：1.86 MB
  • 文档页数：81

下载文档原格式

  / 81

合集下载

运筹学课件 第2章：线性规划的对偶理论

运筹学课件 第2章：线性规划的对偶理论

min w 16y1 36y2 65y3
90 y1 3 y 2 y1 2 y 2 5 y 3 70 y , y , y 0 1 2 3
原问题 A b C 约束系数矩阵
对偶问题 约束系数矩阵的转臵
约束条件的右端项向量 目标函数中的价格系数向量 目标函数中的价格系数向量 约束条件的右端项向量 Max z=CX Min w=Y’b 目标函数 AX≤b A’Y≥C’ 约束条件 X≥0 Y≥0 决策变量
若原问题为求极小形式的对称形式线性规划问题， 对偶问题应该具有什么形式？
Min w Y 'b A'Y C Y 0
max w Y 'b A'Y C Y 0
min z CX
Max z CX
AX b X 0
AX b X 0
min w 5 y1 4 y2 6 y3 4 y1 3 y2 2 y3 2 y1 2 y2 3 y3 3 3 y1 4 y3 5 2 y 7 y y 1 2 3 1 y1 0, y2 0, y3无约束
对偶问题 约束系数矩阵的转臵
目标函数中的价格系数向量
目标函数 约束条件
变量
Max z=CX m个 ≤ ≥ = n个 ≥0 ≤0 无约束
约束条件的右端项向量 目标函数 Min w=Y’b m个 ≥0 变量 ≤0 无约束 n个 ≥ 约束条件 ≤ =
【例2-3】写出下列线性规划问题的对偶问题
min 2x1 3x2 5x3 x4
1.初始表中单位阵在迭代后单纯形表中对应的位臵就是B-1 2.对于原问题的最优解，各松弛变量检验数的相反数恰好 是其对偶问题的一个可行解，且两者具有相同的目标函数 值。根据下面介绍的对偶问题的基本性质还将看到，若原 问题取得最优解，则对偶问题的解也为最优解。

《运筹学对偶问题》课件 (2)

《运筹学对偶问题》课件 (2)
《运筹学对偶问题》PPT 课件 (2)
欢迎来到《运筹学对偶问题》PPT课件，本课程将探讨偶问题与对偶问题的定 义、线性、非线性和整数规划的对偶问题，以及对偶理论的应用与经济解释。
对偶问题与对偶问题的定义
什么是对偶问题？
探索如何将原始问题转化为对偶问题，实现问题的 优化与平衡。
对偶问题的定义
详细解释对偶问题的概念和特点，以及与原始问题 之间的关系。
非凸规划的对偶问题
探讨非凸规划问题的对偶性质和求解策略，分析其优缺点。
应用案例
介绍非线性规划对偶问题在实际问题中的应用案例和成果。
整数规划的对偶问题
整数规划的对偶问题
讨论整数规划问题的对偶性质和对偶问题的求解方 法。
二进制分解方法
介绍二进制分解方法在整数规划问题中的应用和优 化策略。
对偶理论的应用
1
交通运输规划
2
研究对偶理论在交通运输规划中的应用，
并分析其对交通流的优化作用。
3
供应链管理
探讨对偶理论在供应链管理中的应用， 优化供应链的效率和降低成本。
金融风险管理
应用对偶理论来管理金融风险，提高资 产配置和风险控制的效果。
对偶问题的经济解释
经济效益
分析对偶问题在经济领域的 应用，帮助优化资源的配置 和提高企业效益。
线性规划的对偶问题
1
松弛变量法
学习如何使用松弛变量法来求解线性规划问题的对偶问题，并了解其优缺点。
பைடு நூலகம்
2
对偶单纯形法
探索对偶单纯形法在求解线性规划问题中的应用，以及如何进行优化。
3
对偶理论的应用
研究对偶理论在实际问题中的实用性，并举例说明其应用。
非线性规划的对偶问题

运筹学课件第二章对偶问题

运筹学课件第二章对偶问题

第二章线性规划的对偶理论与灵敏度分析一、学习目的与要求 1、掌握对偶理论及其性质 2、掌握对偶单纯形法3、熟悉灵敏度分析的概念和内容4、掌握限制常数与价值系数、约束条件系数的变化对原最优解的影响5、掌握增加新变量和增加新的约束条件对原最优解的影响，并求出相应因素的灵敏度范围6、了解参数线性规划的解法 二、课时 6学时第一节 线性规划的对偶问题一、对偶问题的提出定义：一个线性规划问题常伴随着与之配对的、两者有密切联系的另一个线性规划问题，我们将其中一个称为原问题，另一个就称为对偶问题，在求出一个问题的解时，也同时给出了另一问题的解。

应用：在某些情况下，解对偶问题比解原问题更加容易；对偶变量有重要的经济解释(影子价格)；作为灵敏度分析的工具；对偶单纯形法(从一个非可行基出发，得到线性规划问题的最优解)；避免使用人工变量(人工变量带来很多麻烦，两阶段法则增加一倍的计算量)。

例：某家具厂木器车间生产木门与木窗；两种产品。

加工木门收入为56元/扇，加工木窗收入为30元/扇。

生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时；该车间每日可用木工总共时为120小时，油漆工总工时为50小时。

问：(1)该车间应如何安排生产才能使每日收入最大？(2)假若有一个个体经营者，手中有一批木器家具生产订单。

他想利用该木器车间的木工与油漆工来加工完成他的订单。

他就要考虑付给该车间每个工时的价格。

他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图而愿意为他加工这批订单、又使自己所付的工时费用最少。

解(1)：设该车间每日安排生产木门x1扇，木窗x2扇，则数学模型为⎪⎩⎪⎨⎧≥≤+≤++=-0502120343056max 21212121x x x x x x x zX*=(15,20)’ Z*=1440元解(2)：设y 1为付给木工每个工时的价格，y 2为付给油工每个工时的价格⎪⎩⎪⎨⎧≥≥+≥++=-0303562450120min 21212121y y y y y y y wY*=(2,24)’ W*=1440元将上述问题1与问题2称为一对对偶问题，两者之间存在着紧密的联系与区别：它们都使用了木器生产车间相同的数据，只是数据在模型中所处的位置不同，反映所要表达的含义也不同。

运筹学课件第二章线性规划的对偶理论及其应用

运筹学课件第二章线性规划的对偶理论及其应用
对偶问题同时解
– 原问题为基础可行解，对偶问题为非可行解，但满足
互补松弛条件；则当对偶问题为可行解时，取得最优 解
13
2.2.5 原问题检验数与对偶问题的解
• 在主对偶定理的证明中我们有：对偶(min型)变量的最 优解等于原问题松弛变量的机会成本，或者说原问题松 弛变量检验数的绝对值
• 容易证明，对偶问题最优解的剩余变量解值等于原问题 对应变量的检验数的绝对值
1
1/2 5/2
1
1
0
1/2 3/2
0
0
0
1/2 3/2
OBJ=
39
9/2
3
6
6
0
3/2
3/2
cj - zj
1/2
0
0
0
0
3/2 -M-3/2
0
x4
4
0
0
1
1
1
1
3
5
x1
6
1
0
2
2
0
1
1
3
x2
4
0
1
1
(1)
0
1
2
OBJ=
42
5
3
7
7
0
2
1
cj - zj
0
0
1
1
0
2 -M+1
0
x4
ቤተ መጻሕፍቲ ባይዱ
8
0
1
0
0
1
0
1
5
x1
数值，
g(Y0)=Y0b= CBB1 b
而原问题最优解的目标函数值为
f(X0)=CX0= CBB1 b 故由最优解判别定理可知Y0 为对偶问题的最优解。证毕。

运筹学(第2章 线性规划的对偶理论)

运筹学(第2章 线性规划的对偶理论)

min w 15 y1 24 y 2 5 y 3 6 y 2 y 3 y4 2 s.t 5 y1 2 y 2 y 3 y5 1 yi 0
分别用单纯形法求解上述2个规划问题，得到最终单纯形表如 下表：
原问 题最 优表
XB x3 x1 x2
-2 3 -3 1 5 7 1 -4 -6
2 y1 3 y2 y3 2 3 y y 4 y 3 1 2 3 5 y1 7 y2 6 y3 4 y1 , y2 , y3 0
(2) 非对称型对偶问题 若给出的线性规划不是对称形式，可以先化成对 称形式再写对偶问题。也可直接按教材表2-2中的对 应关系写出非对称形式的对偶问题。
y2
y3
1/4
1/2
-4/5
15/2 15/2
1
0 0
0
1 0
-1/4
1/2 7/2
1/4
-3/2 3/2
j
原问题与其对偶问题的变量与解的对应关系： 在单纯形表中，原问题的松弛变量对应对偶 问题的变量，对偶问题的剩余变量对应原问 题的变量。
弱对偶性；强对偶性；
最优性; 无界性; 互补松弛性
性质1 对称性定理：对偶问题的对偶是原问题 min W= Y b s.t. YA ≥ C Y≤0
对偶性质（Dual property）

性质4 强对偶性：若原问题及其对偶问题均具有可行解， 则两者均具有最优解，且它们最优解的目标函数值相等， 即 max z min w
故
证明：将原问题化成标准形式
m ax z c j x j
j 1 n n
yi 0 (i 1,, m)
是对偶问题的可行解, 又因

运筹学第2章-线性规划的对偶理论

运筹学第2章-线性规划的对偶理论
❖ 影子价格不是市场价格，而是在现有技术和管理条件下， 新增单位资源所能够创造的价值，是特定企业的一种边 际价格；不同企业或同一企业不同时期，同种资源的影 子价格可能不同；当市场价格高于影子价格，可以卖出； 相反，则应买进，以获取更大收益
Ma例x：Z （ 2第x一1 章3例x22）
2 x1 2 x2 12
当原问题和对偶问题都取得最优解时，这 一对线性规划对应的目标函数值是相等的：
Zmax=Wmin
二、原问题和对偶问题的关系
1、对称形式的对偶关系
（1）定义：若原问题是
MaxZ c1 x1 c2 x2 cn xn
a11x1 a12 x2 a1n xn b1
s.t.a21
x1
a22
二、 手工进行灵敏度分析的基本原则 1、在最优表格的基础上进行； 2、尽量减少附加计算工作量；
5y3 3
，y
2
3
0
（用于生产第i种产 品的资源转让收益不 小于生产该种产品时 获得的利润）
对偶变量的经济意义可以解释为对工时及原材 料的单位定价 ；
若工厂自己不生产产品A、B和C，将现 有的工时及原材料转而接受外来加工时， 那么上述的价格系统能保证不亏本又最富 有竞争力（包工及原材料的总价格最低）
内，使得产品的总利润最大 。
MaxZ 2x1 3x 2
2x1 2x2 12
s.t.54xx12
16 15
x1, x 2 0
它的对偶问题就是一个价格系统，使在平衡了 劳动力和原材料的直接成本后，所确定的价格系统 最具有竞争力：
MinW 12y1 16y2 15y3
2y1 4y2
2
s.t.2y1y，1y
y1, y2, , ym 0

运筹学2对偶问题86页PPT


§2.1线性规划的对偶模型 Dual model of LP
Ch2 Dual Problem
05.05.2020
Page 9 of 19
例如，第一种资源的影子价格为y1=2，第二种资源的影子 价格为y2=2，即当第一种资源增加一个单位时，Z增加2个 单位，当第二种资源增加一个单位时，Z增加2个单位。
Ch2 Dual Problem
05.05.2020
Page 8 of 19
由后面的对偶性质可知：原问题和对偶问题的最 优值相等，故有
Z C B X B C B B 1b Yb
m
bi y i i 1
Z bi
yi
i 1, , m
即yi是第i种资源的变化率，说明当其它资源供应量bk(k≠i) 不变时，bi增加一个单位时目标值Z增加yi个单位。
§2.1线性规划的对偶模型 Dual model of LP
Ch2 Dual Problem
05.05.2020
Page 6 of 19
【解】设xj为每天第j种食物的用量，数学模型为
minZ0.5x1 0.4x2 0.8x3 0.9x4 0.3x5 0.2x6
13x1 25x2 14x3 40x4 8x5 11x6 80 24x1 9x2 30x3 25x4 12x5 15x6 150 18x1 7x2 21x3 34x4 10x5 180 x1、x2、x3、x4、x5、x6 0
型为： max Z 100 x1 80 x 2 70 x 3
9 x1 8 x 2 6 x 3 500
5 8
x x
1 1
4x2 3x2
7 x3 2x3
450 300
7
x
1

运筹学课件2.2 对偶理论


原问题的标准型和典则型 max z cx 0 xs Ax xs b x 0, xs 0
max z cB B b (c N cB B N ) xN 1 ( c B B ) x s 1 1 1 xB B b B Nx N B xs x B , x N , xs 0
用例1.1的最优解解释
CB
30 50
cj xB
50
30
0
0
x2
b x1
1350
x2
1 0 0
x3
1 -1/2 -5
x4
-2 3/2 -15

j
20 x1 15
0 1 0
y1=5, y2=15是对偶问题的最优解，此时原、对偶问 题都可行。
习题
习题2.8，P.89。
原问题与对偶问题的对应关系
问题与解的 状态
对偶问题
有最优解 无界 不可能 不可能 无可行解 不可能
原 问 题
有最优解 一定 无界 不可能
无可行解 不可能
不一定/肯 定 肯定/不 可能 一定
对偶问题的典则型
原问题为 对偶问题是
max z CX AX b X 0
minw yb yA变量
ys1 0 ，得基本解
1 1
Y (cB B ,0, cB B N cN )
目标函数
w cB B b
1
若对偶问题的基本解可行，则
c N cB B N ( N ) 0 1 cB B ( s ) 0
1
说明对偶问题解可行是原问题可行解最优的条 件。 1 同样可以看出原问题基本解可行： B b 0 是对偶问题最优解的条件。因此原问题与对偶 问题同时可行，目标函数值相等，同时得最优 解。

4运筹学第二章线性规划的对偶理论-PPT精选文档44页


证：设原问题为： max z=CX；AX≤b；X≥0 则 对偶问题为：min ω=Yb；YA≥C；Y ≥0
因X(0)是原问题的可行解，所以AX(0)≤b
又因Y(0)是对偶问题的可行解，所以Y(0)A≥C
Y (0) A X(0) ≤ Y (0) b
Y (0) A X(0) ≥ CX (0)
因此， CX(0) ≤Y(0) A X(0) ≤ Y(0) b 结论成立。
20
军事运筹学
6﹒互补松弛性：若X(0)是原问题的可行解， Y(0)是对偶 问题的可行解，则YξX(0)=0和Y(0)Xξ=0 当且仅当X(0)， Y(0)是最优解。
证： 设原问题和对偶问题的标准型是
max z=CX AX+xξ=b X≥0，Xξ ≥0
min ω =Yb YA－Yξ=C Y≥0，Yξ ≥0
6
军事运筹学
4.1 对偶问题的提出
min ω=8 y1+16y2 +12y3
y1+4y2
≥2
2 y1 +4y3≥3
与
y1 ， y2 ，y3≥0 12
max z＝2x1+3x2 x1＋ 2x2 ≤8
4x1
≤16
4x2 ≤12
x1﹐x2 ≥0
有何关 系？
对愿模型设： A= 4 0 04
b=(8,16,12)T C=(2，3)
X=（x1，x2）T
Y=（y1，y2 ，y3 ） 则可得:
max z=CX AX≤b （5.1） 和
min ω =Yb YA ≥ C （5.2）
X≥0
Y≥0
我们把（5.2）式的问题称为（5.1）式问题的对偶线 性规划问题。
7
军事运筹学

《运筹学》第二章 对偶问题



3 x1 2 x2
7x4 4
2 x1 3 x2 4 x3 x4 6
x1 0, x2 , x3 0, x4无 约 束
解：原问题的对偶问题为
mi nW 5 y1 4 y2 6 y3
4 y1 3 y2 2 y3 2

20
一组互为对偶的线性规划问题的解之间只有 下列三种情况:
(1)两个规划问题都有可行解(此时,两个规划问题都有最优 解,且最优值相等);
(2)两个规划问题都不可行; (3) 一个规划问题不可行,另一个规划问题有可行解,且具有
无界解。
21
（4）互补松弛性： 在线性规划问题的最优解中，
则 aij xj * = bi ；
bi , 则 y i* = 0 (4)’ 互补松弛性：
在线性规划问题的最优解中， 则 aij yi * = cj ；
>cj , 则 xj* = 0
n
若 y i * >0,
j=1 n
若 a ij xj * <
j=1
m
若 x j * >0,
i=1 m
若 a ij yi*
i=1 22
m
= 证b：i y∵i*
y1 3 y1

2 y2
3 y3 4 y3
3 5

2 y1 7 y2 y3 1
y1

0,
y2

0,
y
无
3
约
束
对偶问题的对 偶还是原问题
14
• 练习 写出下列线性规划问题的对偶问题.
max Z 4x1 3x2 2x3
4x1
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

2.4 运输问题
2.1 线性规划的模型与图解法
2.1.1 问题的引入 （１）生产安排问题 如何合理使用有限的人力、物力和资金， 使得收到最好的经济效益。
例1：某工厂可生产甲、乙两种产品，需消耗煤、 电、油三种资源。现将有关数据列表如下：
资源单耗 资源 产品
甲 9 4 3 7
乙 4 5 10 12
•约束条件的类型与非负条件对偶 •非标准的约束条件类型对应非正常的非负规划：
min z 5 x x 3 x
1 2
3
2x 2x x 1
1 2 3
x 3 x 4 x 10
1 2 3
2x 2x x 5
2.3.2 灵敏度分析
一、定义：
灵敏度分析讨论建模时的系数及有关变量变化时对 解的影响。 反映在两个方面
最优性： j C j C B B 1 Pj 1 可行性：X B B b
二、目的：
（1）参数在何范围内变化最优解（基）不变。 （2）参数变化，最优解有何变化。 1.资源向量b的变化分析
4.最优性
设X，分别是( P )与( D )问题的可行解， Y 且C X Y b，则 X， Y皆为最优解。
图示为：
CX Yb
z w CX Yb
* *
5.强对偶性 设 如果(P)问题有最优解，则(D)问题也有最 优解，且最优值相等。 证：对(P)增加松弛变量XS，化为标准型：
min w 2 y1 y2 y1 2 y2 1 y1 y 2 1 y1 y2 0 y , y 0 1 2
s.t.
s.t.
若原问题xj≤0，则对偶问题第j个约束
反号（与规定形式比）。同理，若原问题 第i个约束反号（与规定形式比），则对偶 问题yi≤0。
( D ) min w 2 y1 y2 y1 2 y2 1 y1 y2 1 y1 y2 0 y , y 0 1 2
令x2’=-x2，则上式化为：
max z x1 x2 ' x1 x2 ' x3 2 s.t. 2 x1 x2 ' x3 1 x , x ' , x 0 1 2 3
（3）下料问题
如何截取原材料，在达到截取要求的 情况下，使废料最少。
例3：料长7.4米，截成2.9、2.1、1.5米各 200根,方案如下表。如何截取余料最少？
方案 料型 2.9米 2.1米 1.5米 合计 残料 1 1 0 3 7.4 0 2 2 0 1 7.3 0.1 3 0 2 2 7.2 0.2 4 1 2 0 7.1 0.3 5 0 1 3 6.6 0.8
例1：写出下列LP问题的对偶问题
(1) max z x1 x2 x1 x2 x 3 2 s.t. 2 x1 x2 x3 1 x1 , x2 , x3 0
( D ) min w 2 y1 y2 y1 2 y2 y1 y2 s.t. y1 y2 y1 , y2 1 1 0 0
s.t. -YA ≤ -C Y ≥0
2、弱对偶性 设X、Y分别是(P)问题和(D)问题的任一可行解，则
CX ≤ Yb
注：此性质只适用于(P)max型与(D)min型。
3、无界性 若原问题（对偶问题）为无界解，则其对偶 问题（原问题）无可行解。 证：用反证法 若（D）有可行解，则由弱对偶性，有Z(x)≤w(y) 即(P)的目标函数值有上界 这与(P)有无界解相矛盾，所以命题成立。 注：性质3的逆命题不成立。 事实上，原问题（对偶问题）无可行解，则对偶问 题（原问题）有无界解或无可行解。
养的前提下使购买食品的费用最小？
解：设xj(j=1,2,3,4)为第j种食品每天的 购入量，z为每天购买食品的总费用，则 配餐问题的线性规划模型为： min z=14x1+6x2 +3x3+2x4 1000x1+800x2 +900x3+200x4 3000 50x1+ 60x2 + 20x3+ 10x4 55 400x1+200x2 +300x3+500x4 800 x1,x2 ,x3 ,x4 0
（P）
三、对偶变量的经济含义—影子价格
1、影子价格的定义：
max z CX AX b X 0
式中：bi—第i种资源的拥有量，yi—对第i种资源的估价。
定义： (D)问题的最优解y*=CBB-1为(P)问题资源的 影子价格。 于是CBB-1:
(1)作为(D)问题的最优解y*—买主最低的价格
写出上述对偶问题的对偶问题
min w 2 y1 y2 y1 2 y2 y1 y2 y1 y2 y1 , y2 1 1 0 0
令w' w
max w' 2 y1 y2 y1 2 y2 y1 y2 s.t. y1 y2 y1 , y2 1 1 0 0
s.t. 9x1 + 4x2 ≤360 4x1 + 5x2 ≤200 3x1 +10x2 ≤300 x1，x2≥0 ——约束条件
（２）配料问题 如何合理地搭配（混合）材料，以最 经济的方式，达到配比要求。
例2：（营养配餐问题）假定一个成年人每天
需要从食物中获得3000千卡的热量、55克蛋白 质和800毫克的钙。如果市场上只有四种食品 可供选择，它们每千克所含的热量和营养成分 和市场价格见下表。问如何选择才能在满足营
(2)作为(P)问题的影子价格—卖主内部掌握 的价格
例5.煤、电、油例的最终表：
X*=(20,24,84,0,0)T，z*=428=w*，
Y*=(0,1.36,0.52)=CBB-1
资源煤的影子价格为0
资源电的影子价格为1.36 资源油的影子价格为0.52
影子价格越高，说明这种资源对生产越重要。
解：（1）电的影子价格为1.36
即电的增量在[-50, 26.92]内变动时，可使原最优基B 不变。
（2）因为25 ＜26.92，所以原有影子价格仍适用，而 1.36 ＞1，故值得接受。 （3）
（4）
第２章
线性规划
（Linear Programming）
第２章
线性规划
2.1 线性规划的模型与图解法 2.2 单纯形法 2.3 对偶问题与灵敏度分析
解：设xj(j=1,2,3,4,5)为采用第j种方案截 取的原料根数，z为截取后的余料总米数， 则下料问题的线性规划模型为： min z=0x1+0.1x2 +0.2x3+0.3x4+0.8x5 x1+2x2 + x4 200 2x3+ 2x4 + x5 200 3x1+ x2 +2x3 +3x5 200 xj 0(j=1,2,3,4,5)
资源限量 360 200 300
煤 电 油 单位产品价格
试拟订使总收入最大的生产方案。
甲 煤(t)
电（kw· h) 油（t） 单价（万元）
乙 4
5 10 12
资源限量 360
200 300
9
4 3 7
解：设甲乙产品产量分别为x1和x2 kg，——决策变量 总收入为z万元。 则 max z = 7x1 +12x2 ——目标函数
≤0则不投产
若σn+1>0，则用单纯形法迭代至最优。
例：回顾煤电油例的终表。
（1）请指出电的影子价格是多少？并给出使最优基仍适用的 电的变化范围？ （2）若有人愿以每度1元的价格向该厂供应25度电，是否值得 接受？ （3）甲产品的价格在何范围内变化时，原最优解不变？ （4）若现又考虑一新产品丙，资源单耗为10、2、5，售价为 6.5，是否应投产？
≥
C
n
m
对偶问题模型的特点：
原问题（P） 目标max型 有n个变量（非负） 对偶问题（D） 目标min型 有n个约束（大于等于）
有m个约束（小于等于） 价格系数 资源向量
技术系数矩阵 第i个约束为等式 第j个变量为自由变量
有m个变量（非负） 资源向量 价格系数
技术系数矩阵的转置 第i个变量为自由变量 第j个约束为等式
s.t.
若原问题第i个约束为“=”，则对偶问题yi为自 由变量。同理，若原问题xj为自由变量，则对偶问 题第j个约束为“=”式。
(3) max z x1 x2 x1 x2 x3 2 s.t. 2 x1 x2 x3 1 x 0, x 0, x 0 2 3 1
结果：
（1）若Cj的变化使检验数仍全部≤0，则原问题 最优解不变。 （2）若Cj的变化使检验数中含有>0的量，则应 用单纯形法迭代至最优。
3.追加新变量的分析。
问题：新加入的变量是否应进基（如新产品是 否应投产） 方法：只需计算新变量Xn+1的检验数
σ
=Cn+1-CBB-1Pn+1 >0则投产 n+1
问如何决定生产方案，使总收入最大？
生产模型(P)
现有另一厂商，提出购买全部资源煤、电、油。 设煤、电、油的购买单价分别为y1,y2,y3，总花费为w。
购买模型(D)
称(D)为(P)的对偶问题， (P)为(D)的原问题。
2. 对偶模型的一般式
原问题（P) max z=CX s.t. AX≤b X ≥0 max m C A ≤ b n AT 对偶问题(D) min w=Yb s.t. YA≥C Y ≥0 min b
b1 ... 记b br br ... 问题：Δ br在何范围时可使原问题最优基不变。 bm