运筹学模型与软件实践

–
s.t.–
–
设 显 工 A然厂2x、商希1xB人望 1资希出源2望售的xx总资2 2出的 源x售 1收 后价,32购 所x格xx价 得2分33,越 不别 x小 应为323越比,yxxx好生1 4 4 4和产 产y2品10 2所55得少
A资源 B资源
目标函数 min g(y)=25y1+15y2
2020/4/3
引入对偶问题
设： x1 为生产大轿车的数量(辆)
x2 为生产载重汽车的数量(辆)
全年的利润值 z 4x1 3x2 (千元)
原材料限制： 2x1 2x2 1600
工时的限制： 5x1 2.5x2 2500
大轿车座椅限制： x1 400
2020/4/3
非负约束： x1 0 ； x2 0
“在周长一定的四边形中,以正方形的面积为最大”, 或者 “在面积为一定的四边形中,以正方形的周长为最小”, 这实际上是一个现象的两种提法。
2020/4/3
引入对偶问题
(2)实际的例子（汽车生产）：
某汽车工厂生产大轿车和载重汽车两种型号的汽车 ，已知生产每辆汽车所用的钢材都是2吨／辆，该工厂每 年供应的钢材是1600吨；工厂的生产能力是每2.5小时可 生产一辆载重汽车，每5小时可生产一辆大轿车，工厂全 年的有效工时为2500小时；已知供应给该厂大轿车用的 座椅每年可装配400辆。出售一辆大轿车可获利4千元， 出售一辆载重汽车可获利3千元。问工厂如何安排生产才 能获利最大
2y1+2.5y2 >=3
用于生产一辆大轿车的材料销售利润、工时利润 和座椅利润之和不低于出售一辆大轿车所得的利润
W>=1600y1+2500y2+400y3
为了使材料的价格和工时费在市场上有竞争力， 对工厂来说最佳的决策是，在满足上述的约束条件的 基础上，售价越低越好，这就是总利润最小值。
2020/4/3
y1 2y2 1 产 品1的 所 得
s.t.
2y1 y2 2 2y1 3y2 3
产 品2的 所 得 产 品3的 所 得
3y1 2y2 4 产 品4的 所 得
y1, y2 0
2020/4/3
3、原始问题和对偶问题最优解之间的互补松弛关系
min z=CTX s.t. AX≥b
X ≥0
引进松弛变量
max y=bTW
s.t. ATW≤C
对偶
W≥0
引进松弛变量
min z=CTX s.t. AX-XS=b
X, XS≥0
X，Xs
max y=bTW s.t. ATW+WS=C
W, WS≥0
3、原始问题和对偶问题最优解的充分必要条件 (1)原始可行条件（PFC）
AX-XS=b X, XS ≥0
Kuhn-Tucher 条 件
(2)对偶可行条件（DFC）
ATW+WSBaidu NhomakorabeaC W, WS ≥0
(3)互补松弛条件（CSC） XTWS=0
WTXS=0
2020/4/3
• 任何线性规划问题都有其对偶问题 • 对偶问题有其明显的经济含义
X ≥0
对偶的定义
min y=-bTW s.t. -ATW≥-C
W ≥0
2020/4/3
三、原始对偶关系
1、可行解的目标函数值之间的关系
设XF、WF分别是原始问题和对偶问题的可行解
z=CTXF ≥WTAXF ≥WTb=y
2、最优解的目标函数值之间的关系
设Xo、Wo分别是原始问题和对偶问题的最优解
z=CTXo=WoTAXo=WoTb=y
W，Ws
2020/4/3
XTWS=0 WTXS=0
互补松弛关系
原始问题和对偶问题变量、松弛变量的维数
min z=CTX
n
m
s.t. AX-XS=b
X
XS
X, XS ≥0 m
A
-I = b
max y=bTW
W
s.t.
ATW+WS=C
W, WS ≥0 n AT
XTWS=0
WTXS=0
2020/4/3
m
显然工厂决策者认为当minW=maxZ时，这两种方案 具有相同的结果，都是最优解
2020/4/3
一、对偶的定义
原始问题 min z=CTX s.t. AX≥b
X ≥0
min
CT
对偶问题（旋转90°） max y=bTW s.t. ATW≤C
W ≥0
max bT
m
A
≥b
n AT ≤ C
n
m
2020/4/3
对偶规划的要点
• 从min变成max • 价值系数与右端向量互换 • 系数矩阵转置 • 按规则添上不等式
2020/4/3
二、对偶问题的性质
对偶的对偶就是原始问题
min z=CTX s.t. AX≥b
X ≥0
对偶的定义
max y=bTW s.t. ATW≤C
W ≥0
max z’=-CTX
s.t. -AX≤-b
现在提一个新的问题： 如果工厂不再打算生产汽车，而是把钢材和座椅以
比买价高的价格卖出，把工厂的生产能力以更高的工时 费来接受外协加工，那么材料和工时的定价应该是多少 才划算？
2020/4/3
在考虑定价时，肯定要和生产汽车时 的情况进行比较，起码应当使两种情况 下的总利润相等。
2020/4/3
设y1表示出售单位钢材的利润，y2表示外协加工 的工时利润，y3表示出售每套大轿车座椅的利润，那 么，用于生产一辆载重汽车的材料销售利润和工时利 润之和不应该低于出售一辆载重汽车所得的利润，即
WS
I
=C
n
原始问题的变量 原始问题的松弛变量
x1
xj
xn xn+1 xn+i xn+m
w1 wi wm wm+1
wm+j
wn+m
对偶问题的变量 对偶问题的松弛变量
xjwm+j=0 wixn+i=0 (i=1,2,…,m; j=1,2,…,n)
在一对变量中，其中一个大于0，另一个一定等于0
2020/4/3
maxf (x) x1 2x2 3x3 4x4
x1 2x2 2x3 3x4 25
s.t. 2x1 x2 3x3 2x4 15
x1,x2,x3,x4 0
A资源 B资源
假设有商人要向厂方购买资源A和B，问他们谈判原料 价格的模型是怎样的？
2020/4/3
maxf (x) x1 2x2 3x3 4x4
2020/4/3
第三章 对偶规划、灵敏度分析与实验
• 对偶理论简介 • 对偶线性规划应用 • 单纯形方法的灵敏度分析 • LINDO软件求解与灵敏度
分析
• 投资的收益和风险组合问 题
• WinQSB软件的应用
DUAL
2020/4/3
引入对偶问题
(1)说法： 一般,我们把下面的两个现象称为对偶现象,例如