第6章单纯形法的灵敏度分析与对偶
1
a．c
1≤24
b．c
2≥6
c．c
s2≤8
2
a.c
1≥-0.5
b.-2≤c
3≤0
c.c
s2≤0.5
3
a.b
1≥150
b.0≤b
2≤83.333
c.0≤b
3≤150
4
a.b
1≥-4
b.0≤b
2≤300
c.b
3≥4
5
a.利润变动范围c
1≤3，故当c
1=2时最优解不变
b.根据材料的对偶价格为1判断，此做法不利
c.0≤b
2≤45
d.最优解不变，故不需要修改生产计划
e.此时生产计划不需要修改，因为新的产品计算的检验数为-12小于零，对原生
产计划没有影响。
6
均为唯一最优解，根据从计算机输出的结果看出，如果松弛或剩余变量为零且对
应的对偶价格也为零，或者存在取值为零的决策变量并且其相差值也为零时，可
知此线性规划有无穷多组解。
7
a.minf=10y
1+20y
2.
s.t.y
1+y
2≥2,
y
1+5y
2≥1,
y
1+y
2≥1,
y
1,y
2≥0.
b.maxz=100y
1+200y
2.
s.t.1/2y
1+4y
2≤4,
2y
1+6y
2≤4,8.2y
1+3y
2≤2,
y
1,y
2≥0.
a.minf=-10y
1+50y
2+20y
3-20y
4.
s.t.-2y
1+3y
2+y
3-y
2≥1,
3y
1+y
2≥2,
-y
1+y
2+y
3-y
2=5,
y
1,y
2,y
2≥0,y
3没有非负限制。
b.maxz=6y
1-3y
2+2y
3-2y
4.
s.t.y
1-y
2-y
3+y
4≤1,
2y
1+y
2+y
3-y
4=3,
-3y
1+2y
2-y
3+y
4≤2,
y
1,y
2,y
4≥0,y
3没有非负限制
9.对偶单纯形为
maxz=4y
1-8y
2+2y
3
s.ty
1-y
2≤1,
-y
1-y
2+y
3≤2,
y
1-2y
2-y
3≤3,
y
1,y
2,y
3≥0
目标函数最优值为:10
最优解:x
1=6,x
2=2,x
3=0
运筹学2对偶问题
运筹学教程
运筹学Operations Research Chapter 2 对偶问题Dual
Problem
1. 线性规划的对偶模型 Dual Model of LP 2.对偶性质 对偶性质 3.对偶单纯形法 对偶单纯形法 4.灵敏度分析 灵敏度分析
Dual property Dual Simplex Method Sensitivity Analysis
运筹学教程
§2.1线性规划的对偶模型 线性规划的对偶模型 Dual
model of LP
Ch2 Dual Problem2022年11月26日星期五 Page 2 of 19
在线性规划问题中，存在一个有趣的问题，即每一个线性规
划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。
【例2.1】 某企业用四种资源生产三种产品，工艺系数、 例
资源限量及价值系数如下表：产品 资源 Ⅰ Ⅱ Ⅲ Ⅳ 每件产品利润 9 5 8 7 100 8 4 3 6 80 6 7 2 4 70 500 450 300 550 A B C 资源限量
建立总收益最大的数学模型。
运筹学教程
§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP
Ch2 Dual Problem2022年11月26日星期五 Page 3 of 19
设x1,x2,x3分别为产品A,B,C的产量，则线性规划数学模 解
型为： m Z = 100x + 80x + 70x ax1 2 3
9x1 + 8x2 + 6x3 ≤ 500 5x + 4x + 7x ≤ 450 2 3 1 8x1 + 3x2
+ 2x3 ≤ 300 7x + 6x + 4x ≤ 550 2 3 1 x1, x2, x3 ≥ 0 现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产 品，而将现有的资源转让或出租给其它企业，那么资源的转让价格
1 第二章线性规划的对偶理论与灵敏度分析
一、学习目的与要求
1、掌握对偶理论及其性质
2、掌握对偶单纯形法
3、熟悉灵敏度分析的概念和内容
4、掌握限制常数与价值系数、约束条件系数的变化对原最优解的影响
5、掌握增加新变量和增加新的约束条件对原最优解的影响，并求出相应因素的灵敏度范围
6、了解参数线性规划的解法
二、课时 6学时
第一节 线性规划的对偶问题
一、对偶问题的提出
定义：一个线性规划问题常伴随着与之配对的、两者有密切联系的另一个线性规划问题，我们将其中一个称为原问题，另一个就称为对偶问题，在求出一个问题的解时，也同时给出了另一问题的解。
应用：在某些情况下，解对偶问题比解原问题更加容易；对偶变量有重要的经济解释(影子价格)；作为灵敏度分析的工具；对偶单纯形法(从一个非可行基出发，得到线性规划问题的最优解)；避免使用人工变量(人工变量带来很多麻烦，两阶段法则增加一倍的计算量)。
例：某家具厂木器车间生产木门与木窗；两种产品。加工木门收入为56元/扇，加工木窗收入为30元/扇。生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时；该车间每日可用木工总共时为120小时，油漆工总工时为50小时。
问：(1)该车间应如何安排生产才能使每日收入最大？
(2)假若有一个个体经营者，手中有一批木器家具生产订单。他想利用该木器车间的木工与油漆工来加工完成他的订单。他就要考虑付给该车间每个工时的价格。他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图而愿意为他加工这批订单、又使自己所付的工时费用最少。
解(1)：设该车间每日安排生产木门x1扇，木窗x2扇，则数学模型为
0502120343056max21212121xxxxxxxz 2 X*=(15,20)’ Z*=1440元
解(2)：设y1为付给木工每个工时的价格，y2为付给油工每个工时的价格
第二章 线性规划的对偶问题
４７ 习题二2.1 写出下列线性规划问题的对偶问题
(1) max z ＝10x1＋ x2＋2x3 (2) max z ＝2x1＋ x2＋3x3＋ x4
st. x1＋ x2＋2 x3≤10 st. x1＋ x2＋ x3 ＋ x4 ≤5
4x1＋ x2＋ x3≤20 2x1－ x2＋3x3 ＝－4
xj ≥0 （j＝1,2,3） x1 － x3＋ x4≥1
x1，x3≥0，x2，x4无约束
(3) min z ＝3x1＋2 x2－3x3＋4x4 (4) min z ＝－5 x1－6x2－7x3
st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3 ≥15
x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3 ≤20
2x1－3x2－7x3 －4x4＝2＝ x1－ x2－ x3＝－5
x1≥0，x4≤0，x2，，x3 无约束 x1≤0， x2≥0，x3 无约束
2.2 已知线性规划问题max z＝CX，AX=b，X≥0。分别说明发生下列情况时，其对偶问题的解的变化：
（1）问题的第k个约束条件乘上常数λ（λ≠0）；
（2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上；
（3）目标函数改变为max z＝λCX（λ≠0）；
（4）模型中全部x1用31'x代换。
2.3 已知线性规划问题 min z＝8x1＋6x2＋3x3＋6x4
st. x1＋2x2 ＋ x4≥3
3x1＋ x2＋ x3＋ x4≥6
x3 ＋ x4＝2
x1 ＋ x3 ≥2
xj≥0（j＝1,2,3,4）
(1) 写出其对偶问题；
