第三讲 规划模型规划模型,特别是线性规划模型是数学在经济社会中应用最广泛的一种数学模型,
问题 1 生猪出售的时机一饲养场每天头投入 4元资金用于饲养以及设备、
人力,估计可使得一头 80kg的生猪每天增重 2kg,目前生猪出售的市场价格是 8元 /kg,但是预测每天会降低 0.1元,问该什么时候出售这样的生猪?如果上面的估计和预测有出入,对结果有多大影响,
问题分析 饲养场每天投入 4元,按目前的的价格,
可以产生 16元的经济效益,因此值得饲养这种生猪,但是,估计价格会逐步降低,我们可以想象,当价格降得太低时,那时饲养生猪便无利可图,因此存在一个适当的出售生猪的时机,使得饲养场获得的利润最大,
模型假设 每天投入 4元资金使得这种生猪体重每天增加常数 r kg,生猪出售的市场价格每天降低常数 s元,r=2,s=0.1.
我们假设生猪可以随时出售,且能够全部售出 (即需求量远大于此饲养场的生猪数量 ).
模型建立 我们记第 t天时一头生猪的体重为 w
公斤,出售生猪的单价为 p元 /kg;从现在到第 t天为止投入的资金为 C元 ;R为出售收入 (单位,
元 ),Q为从现在开始所获得的纯利润 (单位,元 ).
);80)(8(
,4,8,80
rtstpwR
tCstprtw
.)(0 最大使得函数上求在 tQtt?
( 1 ) )4808(
6 4 04)80)(8(
808
2
tsrrst
trtst
CRQ
生猪目前价值
640元
);80)(8(
,4,8,80
rtstpwR
tCstprtw
模型求解 用配方法我们知,当
( 2 ) 2404
rs
srt
时 Q取得最大值,现 r=2,s=0.1,则当 t=10时,
Qmax=20.
敏感性分析 由于模型假设中的参数 (r,s)时估计和预测的,所以我们应该它们有所变化时对模型结果的影响,这就是敏感性分析,
( 1 ) )4808(2 tsrr s tQ
1,设 s=0.1保持不变,研究 r对结果的影响,由 (2)得
.5.1,60406040 r
rr
rt
( 2 ) 2404 rs srt
2,设 r=2保持不变,研究 s对结果的影响,由 (2)得
.15.00,203203 s
ss
st
可以看出,t是 r的增函数,r=1.9,t=8.4; r=2.1,t=11.4;
可以看出,t是 s的减函数,s=0.09,t=13.3;
s=0.11,t=7.3;
3,我们也可以用相对改变量来表示结果对参数的敏感程度,t对 r的敏感程度记做 S(t,r),它为
dr
dt
t
r
rr
ttrtS?
/
/),(
,6040 rt
.36060),(,2
trrt
rrtS本例中解释
ds
dt
t
s
ss
ttstS?
/
/),(,同理
.33),(,
st
stS本例中解释
.203 st
强健性分析 (Robustness)
建模过程中我们假设了生猪的体重增加和价格的降低都是常数,由此得到的 w和 p都是线性函数,这是对现实情况的简化,一般地,我们记
w=w(t),p=p(t),则 (1)式为
.6404)()()( ttwtptQ
.4)()()()(
,04)()()()()(:
twtptwtp
twtptwtptQ
得求导求极值解释问题 2 消费者的选择回忆实物交换模型,
我们引入了无差别曲线
O x
y
y0
x0
M
N
y1
x1
p1
y2
x2
p
2
M1
N1
p3··
·
现在我们利用无差别曲线来考虑当一个消费者用一定数量的钱来购买这两种商品时,他会如何安排他的钱来购买它们呢?
记消费者占有这两种商品的数量分别为 q1,q2,这时消费者的满意度,或者说商品给消费者带来的效用记做 U(q1,q2),经济学中称为 效用函数,
U(q1,q2)=c的图形就是无差别曲线,
设两种商品的单价分别为
p1,p2,消费者有钱 s元,因此他的选择是使得 U(q1,q2)达到最大,经济学上称这种最优状态为 消费者的均衡,O q1
q2
M
N
M1
N1Q·
2p
s
1p
s
.,,),,(m a x
.,
,,
221121
2211
21
sqpqptsqqU
qpqp
qq
求因此模型为分别为钱他用于购买两种商品的确定时图解法
.::,
L a g ra n g e,),(
21
21
21
pp
q
U
q
U
qqU
最优解应满足求解乘数法便可用函数确定后当解释结果一致
.:,21
21
ppqUqU最优解应满足
.
,.
,,
21
比时达到之比等于它们的价格之在两种商品的边际效用消费者的均衡状态是上式表明量个单位时效用函数的增意为商品购买量增加一为边际效用经济学中称
q
U
q
U
.0,,)(,3;1,0,.2;0,,.1
:
2
21
21
1
21
baqbqaU
qqU
qq
U
几个常用效用函数问题 3 林场经营一个林场,其中的树木按高度划分成不同的等级,当树木被采伐出售时,不同等级的经济价值不同,取一适当的时间,当作初始时刻,此时所有高度的树木的分布称为 初始分布,经过一个 生长周期 后,树木按高度的分布不同了,为了达到持续采伐的目的,要求经过采伐与栽种,树木高度恢复成原来的分布,我们称为 持续采伐方案,
我们想求经济效益最高的持续采伐方案,
持续采伐方案模型假设 1,不考虑树木的自然死亡 ;
2,树木在每年的固定的时间采伐 ;每采伐一棵树木,立即在原地栽种一个新苗 ;
3,假设树木按高度分成 n组,第 i组树木的高度区间是 [hi-1,hi),h0=0,hn=∞.过了一年,树木可能转为高一级的一组 (所占比例为 gi),也可能由于生长迟缓,仍在本组,
4.第 i组树木的价格为 pi.特别地,p1=0.
.,组树木的株数为第我们记记号 ix i
对于持续采伐方案而言,每年的同一时刻的各组树木的株数保持不变,应此不看成时间的函数,只是 i的函数,
我们将初始时刻选在栽种之后,初始分布用向量
.,),,( 1 称为未采伐向量表示nxxx
.0
.),,(,
1
1
y
yyy n
显然表示采伐向量记同理?
:
.,1
为下面所有的式子成立于是持续采伐充要条件采伐后栽种新苗数为另外 nyy
.
,)1(
,,)1(
,)1(
,)()1(
11
111221
333223
222112
11111
nnnnn
nnnnnn
n
yxxgx
yxgxgx
yxgxgx
yxgxgx
yyyxgx
.
,1
的最大树木数表示这一林场所能栽种s
sxx n
.
,,)1(
,)1(
,)()1(
11
333223
222112
11111
nnnnn
n
yxxgx
yxgxgx
yxgxgx
yyyxgx
写成矩阵形式为
,RyyGxx
称 此式为持续采伐条件,其中 G称为生长矩阵,
100
0100
010
001
0001
1
1
32
21
1
n
n
g
g
gg
gg
g
G
0000
0000
1111
R
,RyyGxx
持续采伐条件,
100
0100
010
001
0001
1
1
32
21
1
n
n
g
g
gg
gg
g
G
.)()( xIGyRI写为持续采伐条件可等价地展开就是xIGyRI )()(
.
,)1(
,,)1(
,)1(
,)()1(
11
111221
333223
222112
11111
nnnnn
nnnnnn
n
yxxgx
yxgxgx
yxgxgx
yxgxgx
yyyxgx
.
,
,,
,
,
11
11221
33223
22112
112
nnn
nnnnn
n
xgy
xgxgy
xgxgy
xgxgy
xgyy
.
,
,,
,
,
11
11221
33223
22112
112
nnn
nnnnn
n
xgy
xgxgy
xgxgy
xgxgy
xgyy
由此我们可以推出 (y≥0)
.11332211 nn xgxgxgxg?
( 1 )
0.,
,
1
11332211
in
nn
xsxx
xgxgxgxg
可以证明,林场可持续采伐的充要条件为最大经济效益模型当采伐向量为 y时,林场的经济收益为
.3322 nn ypypypQ
从而最大经济效益模型为
0.,
,
..
m a x
1
11332211
3322
in
nn
nn
xsxx
xgxgxgxg
ts
ypypypQ
我们称这个模型为 线性规划模型,这里的参数 pi,
gi,s都当作已知,在,运筹学,中我们会学习求解线性规划问题,
我们先利用线性规划问题的一般理论来求解此问题,结论是,对最佳持续采伐方案而言,最大经济效益由仅仅采伐某一特定类别的全部树木达到,
,kQk 益为种树木所得到的经济效我们设仅采伐第到由持续采伐条件我们得因此
.0;,0,
111
nkk
i
yyyy
kix
.
,
,,
,
,
11
11221
33223
22112
112
nnn
nnnnn
n
xgy
xgxgy
xgxgy
xgxgy
xgyy
.
,0
,,0
,0
,
11
1122
3322
2211
11
kkk
kkkk
k
xgy
xgxg
xgxg
xgxg
xgy
.1,,2,1,11 ki
g
xg
x
i
ii
i?解得到由持续采伐条件我们得因此
.,0;0,111
kix
yyyy
i
nkk
代入总量式子解得以及将
.,0
.1,,2,1,1111
kix
ki
g
xg
g
xg
x
i
ii
ii
i
.
1
1
1
3
1
2
1
1
kg
g
g
g
g
g
s
x
于是
.
1111
1321
11
k
k
kkkk
gggg
sp
xgpypQ
.
,,,2
求得最优解进行比较就可以通过逐一计算 nQQ?
线性规划问题线性规划问题的一般形式,
,,,2,1,0
.,,1,),(
..
m i n )m a x (
2211
2211
njx
mibxaxaxa
ts
xcxcxcZ
j
ininii
nn
或或目标函数非负约束 约束条件
x=(x1,…,xn)称为决策变量,约束条件的限制作用往往使得决策变量 x的取值区域为一个有界闭区域 Ω,称为 可行域,线性规划问题的 最优解一定会在可行域的边界上达到,
,,,2,1,0
.,,2,1,
..
m a x
2211
2211
njx
mibxaxaxa
ts
xcxcxcZ
j
ininii
nn
线性规划问题的标准形式,
理论上的求解方法是单纯形方法,而且也已经开发出了很多的软件可以求解一些具体的线性规划问题,如 LINDO,运筹学软件等等,下面的例子我们或者图解或者用软件来求解,
例 1 一家具公司生产桌子和椅子,用于生产的全部劳力共计 450个工时,原料是 400个单位的木材,已知每张桌子要使用 15个工时的劳力和 20个单位的木材,售价为 80元 ;每张椅子要使用 10个工时的劳力和
5个单位的木材,售价为 45元,问为达到最大收益,应如何安排生产,
该问题的数学模型为依题意张椅子张子设家具公司安排生产桌解
,
.,,21 xx
21 4580m a x xxZ
,0,
,4501015
,400520
..
21
21
21
xx
xx
xx
ts
原料限制劳力限制图解法四边形 OABC为可行域 ;
.
,
4580
:
21
的最大者从中找出使之与可行域有交点作目标函数等值线
c
cxx
结论,最优解在 B(14,24)点达到,
O A
B
C
4501015 21 xx
1x
2x
因此,该公司安排生产 14张桌子,24张椅子,总共可卖得 2200元,共计 400个单位的原料,以及 450
个工时的劳力,
例 2 奶制品的生产与销售一奶制品加工厂用牛奶生产 A,B两种奶制品,
1桶牛奶可以在甲类设备上用 12小时加工成 3公斤的
A,
或者在乙类设备上用 8小时加工成 4公斤的 B.
根据市场需求,生产的 A,B全部能售出,且每公斤 A获利 24元,每公斤 B获利 16元,
现在加工厂每天能得到 50桶牛奶的供应,每天正式工人总的劳动时间为 480小时,并且甲类生产设备每天至多能加工 100公斤的 A,乙类设备的生产能力没有限制,
1) 若市场上还可以用 35元可以买到 1桶牛奶,
是否追加这项投资?若投资,每天最多购买多少桶牛奶?
2) 若可以聘用临时工人以增加劳动时间,付给临时工人的工资最多是每小时几元?
3) 由于市场需求变化,每公斤 A的获利增加到 30元,是否应该改变生产计划?
试为该加工厂制订一个生产计划,使每天的获利最大,并进一步讨论以下 3个附加问题,
分析,这个问题是要使得加工厂每天获利最大,要作的决策是如何安排生产,即各用多少桶牛奶来生产这两种奶制品,
1桶牛奶加工成产品 A可获利 3× 24=72元,
加工成产品 B则获利 4× 16=64元,
因此,我们应该尽可能的多生产 A,但是生产
A回受到设备的限制 ;另外,生产 A耗时也多一些,而工人的总的劳动时间也是有限制的,
原料也有限制,
解,设每天用于生产 A,B两种产品的牛奶分别为 x,y桶,
加工厂可获利 Z元,于是模型为
yxZ 6472m a x
,0,
,1003
,480812
,50
..
yx
x
yx
yx
ts
原料限制劳力限制设备限制模型求解,图解法
c
y
x
64
72
O x
y
3/1 0 0?x
50 yx
480812 yx
D
求出交点 D的坐标为
(20,30),最大获利为 3360
元,
最优解处第三个约束条件即对甲类设备的限制没有起到作用,
,0,
,1003
,480812
,50
..
yx
x
yx
yx
ts
紧约束,它们中的任何一个放松一些或者在限制严些,都会对结果立刻起到改变作用,不等式右边改变 1个单位的资源时所起的作用叫做影子价格,
稍作改变时,结果不变,甲类设备的加工能力的影子价格为 0.
牛奶资源当我们将目前牛奶的总量由 50变成 50+h时，对应的目标函数值的增量为 ΔZ，则 牛奶资源的影子价格就是：
h
Z
h
0
lim
为了回答附加问题,我们需要知道 1桶牛奶的影子价格,以及确定上面的牛奶资源的变化范围,为此我们先了解线性规划对偶问题,不过,在 LINDO软件求解线性规划时,一起求出来了,
0
l im
,[,]
h
d e in
Z
h
Z
h h h
h
由于目标函数以及约束条件都是线性的,可以证明在一定的范围内 (见灵敏度分析 ),影子价格保持不变,
求解,用 LINDO软件我们先阅读这个问题的求解 报告,
1) 原料牛奶的影子价格为 48元,因此,若现在还可以 35元购买得 1桶牛奶用于生产,是值得投资来追加生产,具体数量则看灵敏度分析中的数据,
2) 劳力的影子价格为 2元,因此,聘用临时工的价格应该低于影子价格,才可能给企业带来利润,故临时工每小时的工资最多为 2元,
3) 第三个问题就是灵敏度分析或者参数规划问题,从报告知,X的系数在 64~96之间则不用调整计划,现在的最优解仍然为最优解,90落在此范围内,不调整,
2.对偶问题及其相关理论与应用
21 4580m a x xxZ
0
4501015
400520
21
21
21
xx
xx
xx
ts
,
,..
回到讲过的生产桌椅的例子,由它得到的数学问题为
0,
45105
801520
s,t,
450400m i n
21
21
21
211
yy
yy
yy
yyZ
另一家同等条件的企业更换经营方式,采用出售劳力和原料,直接为用户定制桌椅的生产方式,为此需要给木材和劳力定价,设单位的木材、
劳力的价格分别为 y1 和 y2,由于竞争,经营者希望 y1 和 y2 尽可能小,但是降低不是无限度的,
它至少应保证 企业得到在同等条件下加工成桌椅后出售的收入,因此它所对应的数学问题为
0,
,4501015
400520
,.
21
21
21
xx
xx
xx
ts
21 4580m a x xxZ
0,
45105
801520
s,t,
450400m i n
21
21
21
211
yy
yy
yy
yyZ
而原来的模型为
0,s,t,
)(m i n
xbAX
XCx Tf
)(,..
)( m a x
CwA0wCAw
wbbww
TTT
TT
ts
g
等价地互为对偶问题
若上面的问题为原问题,则称 w 为 对偶变量,
问题对偶问题的理论
)()( o p to p t gf wx?
.0 xsws wx
定理 1(对偶定理 ) 互为对偶的两个线性规划问题,若其中之一有有穷的最优解,则另外一个也有有穷的最优解,且最优值相等,即,若二者之一有无界的最优解,则另外一个没有最优解,
定理 2(互补定理 ) 对于互为对偶的两个线性规划问题的最优解而言,若其一问题的任一约束不等式严格成立 (即松弛变量为正,非紧约束 ),则相应的对偶变量必为零 ;而任何一个最优解的正分量相对应的约束必为等式 (即松弛变量为零 ).事实上,
正问题的影子价格就是对偶问题的最优解,
作业,写出家具厂安排生产例子的对偶问题并用图解法求解,
并且求家具厂安排生产例子中的影子价格,
若要工人加班生产,加班费最多给多少?
对偶问题的应用例 3.1 假设一工厂可生产五种产品,分别以 P1
至 P5代表,其价格依次为 550,600,350,400,
200,每件产品均需经过研磨及钻孔两道工序,
所需研磨工时依次为 12,20,0,25,15;所需钻孔工时依次为 10,8,16,0,0.此外,每件产品均需要 20小时的装配工时,而工厂在一个生产周期内的总生产能力限制为,研磨 288工时,钻孔
192工时,装配 384工时,问
(1)工厂如何安排生产,以求最大收入,
54321 200400350600550 xxxxxZ m a x
2 8 81502012 54321 xxxxx 25
192016810 54321 xxxxx 0
38420022020 54321 xxxxx 20
解,令 xi 表示生产的这五种产品的数量,则问题归结为如下线性规划问题,
s.t.
我们运用 LINDO软件来求解,得到最优解为
x1=12,x2=7.2,x3=x4=x5=0,最优值
Z=10920.
从报告中我们还得知,研磨和装配能力用尽,
而钻孔能力还有 14.4的剩余,我们对此问题进一步分析相关问题,
(2)如果增加研磨,钻孔和装配能力,那么每种能力的单位增长,会带来多少经济价值,
(3)从上面的结果我们可以这样认为,与 P1,P2
相比,P3,P4,P5的价格定低了,不值得生产,那么价格提到什么程度,它们才值得生产,
75.23,0,25.6 321 www
31332211 75.2325.6 bbbwbwbwZ o p t
为回答这两个问题,我们需求解对偶问题,令对偶变量为 w1,w2,w3,用 LINDO软件求解原问题时,
事实上对偶问题是同时求解的,最优解为我们从对偶定理知道,当以最佳方式生产时,
因此我们可以这样认为,一个单位的研磨能力带来的效益是 6.25,装配能力则为 23.75,
而 w2=0 则反映了目前的钻孔能力有余,
不过,上面关于影子价格的讨论是要在最优解附近变化比较小,且最优解保持不变时才 是 正确的,若只有一个资源 (此处的每一种能力 )发生变化,其变化范围我们可以从 Range Analysis中直接查到,
关于成本下降 (reduced cost)的解释,或者是为发展某一产品暂时性的损失,或者是政府部门应给的补贴,
3.多目标问题简介
实际问题中我们往往希望多个目标都最优,
但是这一般是不可能的,通常我们用 某种线性组合 的方式,定义一个新的目标函数,将多目标问题转化为一个线性规划问题,
问题 1 生猪出售的时机一饲养场每天头投入 4元资金用于饲养以及设备、
人力,估计可使得一头 80kg的生猪每天增重 2kg,目前生猪出售的市场价格是 8元 /kg,但是预测每天会降低 0.1元,问该什么时候出售这样的生猪?如果上面的估计和预测有出入,对结果有多大影响,
问题分析 饲养场每天投入 4元,按目前的的价格,
可以产生 16元的经济效益,因此值得饲养这种生猪,但是,估计价格会逐步降低,我们可以想象,当价格降得太低时,那时饲养生猪便无利可图,因此存在一个适当的出售生猪的时机,使得饲养场获得的利润最大,
模型假设 每天投入 4元资金使得这种生猪体重每天增加常数 r kg,生猪出售的市场价格每天降低常数 s元,r=2,s=0.1.
我们假设生猪可以随时出售,且能够全部售出 (即需求量远大于此饲养场的生猪数量 ).
模型建立 我们记第 t天时一头生猪的体重为 w
公斤,出售生猪的单价为 p元 /kg;从现在到第 t天为止投入的资金为 C元 ;R为出售收入 (单位,
元 ),Q为从现在开始所获得的纯利润 (单位,元 ).
);80)(8(
,4,8,80
rtstpwR
tCstprtw
.)(0 最大使得函数上求在 tQtt?
( 1 ) )4808(
6 4 04)80)(8(
808
2
tsrrst
trtst
CRQ
生猪目前价值
640元
);80)(8(
,4,8,80
rtstpwR
tCstprtw
模型求解 用配方法我们知,当
( 2 ) 2404
rs
srt
时 Q取得最大值,现 r=2,s=0.1,则当 t=10时,
Qmax=20.
敏感性分析 由于模型假设中的参数 (r,s)时估计和预测的,所以我们应该它们有所变化时对模型结果的影响,这就是敏感性分析,
( 1 ) )4808(2 tsrr s tQ
1,设 s=0.1保持不变,研究 r对结果的影响,由 (2)得
.5.1,60406040 r
rr
rt
( 2 ) 2404 rs srt
2,设 r=2保持不变,研究 s对结果的影响,由 (2)得
.15.00,203203 s
ss
st
可以看出,t是 r的增函数,r=1.9,t=8.4; r=2.1,t=11.4;
可以看出,t是 s的减函数,s=0.09,t=13.3;
s=0.11,t=7.3;
3,我们也可以用相对改变量来表示结果对参数的敏感程度,t对 r的敏感程度记做 S(t,r),它为
dr
dt
t
r
rr
ttrtS?
/
/),(
,6040 rt
.36060),(,2
trrt
rrtS本例中解释
ds
dt
t
s
ss
ttstS?
/
/),(,同理
.33),(,
st
stS本例中解释
.203 st
强健性分析 (Robustness)
建模过程中我们假设了生猪的体重增加和价格的降低都是常数,由此得到的 w和 p都是线性函数,这是对现实情况的简化,一般地,我们记
w=w(t),p=p(t),则 (1)式为
.6404)()()( ttwtptQ
.4)()()()(
,04)()()()()(:
twtptwtp
twtptwtptQ
得求导求极值解释问题 2 消费者的选择回忆实物交换模型,
我们引入了无差别曲线
O x
y
y0
x0
M
N
y1
x1
p1
y2
x2
p
2
M1
N1
p3··
·
现在我们利用无差别曲线来考虑当一个消费者用一定数量的钱来购买这两种商品时,他会如何安排他的钱来购买它们呢?
记消费者占有这两种商品的数量分别为 q1,q2,这时消费者的满意度,或者说商品给消费者带来的效用记做 U(q1,q2),经济学中称为 效用函数,
U(q1,q2)=c的图形就是无差别曲线,
设两种商品的单价分别为
p1,p2,消费者有钱 s元,因此他的选择是使得 U(q1,q2)达到最大,经济学上称这种最优状态为 消费者的均衡,O q1
q2
M
N
M1
N1Q·
2p
s
1p
s
.,,),,(m a x
.,
,,
221121
2211
21
sqpqptsqqU
qpqp
求因此模型为分别为钱他用于购买两种商品的确定时图解法
.::,
L a g ra n g e,),(
21
21
21
pp
q
U
q
U
qqU
最优解应满足求解乘数法便可用函数确定后当解释结果一致
.:,21
21
ppqUqU最优解应满足
.
,.
,,
21
比时达到之比等于它们的价格之在两种商品的边际效用消费者的均衡状态是上式表明量个单位时效用函数的增意为商品购买量增加一为边际效用经济学中称
q
U
q
U
.0,,)(,3;1,0,.2;0,,.1
:
2
21
21
1
21
baqbqaU
qqU
U
几个常用效用函数问题 3 林场经营一个林场,其中的树木按高度划分成不同的等级,当树木被采伐出售时,不同等级的经济价值不同,取一适当的时间,当作初始时刻,此时所有高度的树木的分布称为 初始分布,经过一个 生长周期 后,树木按高度的分布不同了,为了达到持续采伐的目的,要求经过采伐与栽种,树木高度恢复成原来的分布,我们称为 持续采伐方案,
我们想求经济效益最高的持续采伐方案,
持续采伐方案模型假设 1,不考虑树木的自然死亡 ;
2,树木在每年的固定的时间采伐 ;每采伐一棵树木,立即在原地栽种一个新苗 ;
3,假设树木按高度分成 n组,第 i组树木的高度区间是 [hi-1,hi),h0=0,hn=∞.过了一年,树木可能转为高一级的一组 (所占比例为 gi),也可能由于生长迟缓,仍在本组,
4.第 i组树木的价格为 pi.特别地,p1=0.
.,组树木的株数为第我们记记号 ix i
对于持续采伐方案而言,每年的同一时刻的各组树木的株数保持不变,应此不看成时间的函数,只是 i的函数,
我们将初始时刻选在栽种之后,初始分布用向量
.,),,( 1 称为未采伐向量表示nxxx
.0
.),,(,
1
1
y
yyy n
显然表示采伐向量记同理?
:
.,1
为下面所有的式子成立于是持续采伐充要条件采伐后栽种新苗数为另外 nyy
.
,)1(
,,)1(
,)1(
,)()1(
11
111221
333223
222112
11111
nnnnn
nnnnnn
n
yxxgx
yxgxgx
yxgxgx
yxgxgx
yyyxgx
.
,1
的最大树木数表示这一林场所能栽种s
sxx n
.
,,)1(
,)1(
,)()1(
11
333223
222112
11111
nnnnn
n
yxxgx
yxgxgx
yxgxgx
yyyxgx
写成矩阵形式为
,RyyGxx
称 此式为持续采伐条件,其中 G称为生长矩阵,
100
0100
010
001
0001
1
1
32
21
1
n
n
g
g
gg
gg
g
G
0000
0000
1111
R
,RyyGxx
持续采伐条件,
100
0100
010
001
0001
1
1
32
21
1
n
n
g
g
gg
gg
g
G
.)()( xIGyRI写为持续采伐条件可等价地展开就是xIGyRI )()(
.
,)1(
,,)1(
,)1(
,)()1(
11
111221
333223
222112
11111
nnnnn
nnnnnn
n
yxxgx
yxgxgx
yxgxgx
yxgxgx
yyyxgx
.
,
,,
,
,
11
11221
33223
22112
112
nnn
nnnnn
n
xgy
xgxgy
xgxgy
xgxgy
xgyy
.
,
,,
,
,
11
11221
33223
22112
112
nnn
nnnnn
n
xgy
xgxgy
xgxgy
xgxgy
xgyy
由此我们可以推出 (y≥0)
.11332211 nn xgxgxgxg?
( 1 )
0.,
,
1
11332211
in
nn
xsxx
xgxgxgxg
可以证明,林场可持续采伐的充要条件为最大经济效益模型当采伐向量为 y时,林场的经济收益为
.3322 nn ypypypQ
从而最大经济效益模型为
0.,
,
..
m a x
1
11332211
3322
in
nn
nn
xsxx
xgxgxgxg
ts
ypypypQ
我们称这个模型为 线性规划模型,这里的参数 pi,
gi,s都当作已知,在,运筹学,中我们会学习求解线性规划问题,
我们先利用线性规划问题的一般理论来求解此问题,结论是,对最佳持续采伐方案而言,最大经济效益由仅仅采伐某一特定类别的全部树木达到,
,kQk 益为种树木所得到的经济效我们设仅采伐第到由持续采伐条件我们得因此
.0;,0,
111
nkk
i
yyyy
kix
.
,
,,
,
,
11
11221
33223
22112
112
nnn
nnnnn
n
xgy
xgxgy
xgxgy
xgxgy
xgyy
.
,0
,,0
,0
,
11
1122
3322
2211
11
kkk
kkkk
k
xgy
xgxg
xgxg
xgxg
xgy
.1,,2,1,11 ki
g
xg
x
i
ii
i?解得到由持续采伐条件我们得因此
.,0;0,111
kix
yyyy
i
nkk
代入总量式子解得以及将
.,0
.1,,2,1,1111
kix
ki
g
xg
g
xg
x
i
ii
ii
i
.
1
1
1
3
1
2
1
1
kg
g
g
g
g
g
s
x
于是
.
1111
1321
11
k
k
kkkk
gggg
sp
xgpypQ
.
,,,2
求得最优解进行比较就可以通过逐一计算 nQQ?
线性规划问题线性规划问题的一般形式,
,,,2,1,0
.,,1,),(
..
m i n )m a x (
2211
2211
njx
mibxaxaxa
ts
xcxcxcZ
j
ininii
nn
或或目标函数非负约束 约束条件
x=(x1,…,xn)称为决策变量,约束条件的限制作用往往使得决策变量 x的取值区域为一个有界闭区域 Ω,称为 可行域,线性规划问题的 最优解一定会在可行域的边界上达到,
,,,2,1,0
.,,2,1,
..
m a x
2211
2211
njx
mibxaxaxa
ts
xcxcxcZ
j
ininii
nn
线性规划问题的标准形式,
理论上的求解方法是单纯形方法,而且也已经开发出了很多的软件可以求解一些具体的线性规划问题,如 LINDO,运筹学软件等等,下面的例子我们或者图解或者用软件来求解,
例 1 一家具公司生产桌子和椅子,用于生产的全部劳力共计 450个工时,原料是 400个单位的木材,已知每张桌子要使用 15个工时的劳力和 20个单位的木材,售价为 80元 ;每张椅子要使用 10个工时的劳力和
5个单位的木材,售价为 45元,问为达到最大收益,应如何安排生产,
该问题的数学模型为依题意张椅子张子设家具公司安排生产桌解
,
.,,21 xx
21 4580m a x xxZ
,0,
,4501015
,400520
..
21
21
21
xx
xx
xx
ts
原料限制劳力限制图解法四边形 OABC为可行域 ;
.
,
4580
:
21
的最大者从中找出使之与可行域有交点作目标函数等值线
c
cxx
结论,最优解在 B(14,24)点达到,
O A
B
C
4501015 21 xx
1x
2x
因此,该公司安排生产 14张桌子,24张椅子,总共可卖得 2200元,共计 400个单位的原料,以及 450
个工时的劳力,
例 2 奶制品的生产与销售一奶制品加工厂用牛奶生产 A,B两种奶制品,
1桶牛奶可以在甲类设备上用 12小时加工成 3公斤的
A,
或者在乙类设备上用 8小时加工成 4公斤的 B.
根据市场需求,生产的 A,B全部能售出,且每公斤 A获利 24元,每公斤 B获利 16元,
现在加工厂每天能得到 50桶牛奶的供应,每天正式工人总的劳动时间为 480小时,并且甲类生产设备每天至多能加工 100公斤的 A,乙类设备的生产能力没有限制,
1) 若市场上还可以用 35元可以买到 1桶牛奶,
是否追加这项投资?若投资,每天最多购买多少桶牛奶?
2) 若可以聘用临时工人以增加劳动时间,付给临时工人的工资最多是每小时几元?
3) 由于市场需求变化,每公斤 A的获利增加到 30元,是否应该改变生产计划?
试为该加工厂制订一个生产计划,使每天的获利最大,并进一步讨论以下 3个附加问题,
分析,这个问题是要使得加工厂每天获利最大,要作的决策是如何安排生产,即各用多少桶牛奶来生产这两种奶制品,
1桶牛奶加工成产品 A可获利 3× 24=72元,
加工成产品 B则获利 4× 16=64元,
因此,我们应该尽可能的多生产 A,但是生产
A回受到设备的限制 ;另外,生产 A耗时也多一些,而工人的总的劳动时间也是有限制的,
原料也有限制,
解,设每天用于生产 A,B两种产品的牛奶分别为 x,y桶,
加工厂可获利 Z元,于是模型为
yxZ 6472m a x
,0,
,1003
,480812
,50
..
yx
x
yx
yx
ts
原料限制劳力限制设备限制模型求解,图解法
c
y
x
64
72
O x
y
3/1 0 0?x
50 yx
480812 yx
D
求出交点 D的坐标为
(20,30),最大获利为 3360
元,
最优解处第三个约束条件即对甲类设备的限制没有起到作用,
,0,
,1003
,480812
,50
..
yx
x
yx
yx
ts
紧约束,它们中的任何一个放松一些或者在限制严些,都会对结果立刻起到改变作用,不等式右边改变 1个单位的资源时所起的作用叫做影子价格,
稍作改变时,结果不变,甲类设备的加工能力的影子价格为 0.
牛奶资源当我们将目前牛奶的总量由 50变成 50+h时，对应的目标函数值的增量为 ΔZ，则 牛奶资源的影子价格就是：
h
Z
h
0
lim
为了回答附加问题,我们需要知道 1桶牛奶的影子价格,以及确定上面的牛奶资源的变化范围,为此我们先了解线性规划对偶问题,不过,在 LINDO软件求解线性规划时,一起求出来了,
0
l im
,[,]
h
d e in
Z
h
Z
h h h
h
由于目标函数以及约束条件都是线性的,可以证明在一定的范围内 (见灵敏度分析 ),影子价格保持不变,
求解,用 LINDO软件我们先阅读这个问题的求解 报告,
1) 原料牛奶的影子价格为 48元,因此,若现在还可以 35元购买得 1桶牛奶用于生产,是值得投资来追加生产,具体数量则看灵敏度分析中的数据,
2) 劳力的影子价格为 2元,因此,聘用临时工的价格应该低于影子价格,才可能给企业带来利润,故临时工每小时的工资最多为 2元,
3) 第三个问题就是灵敏度分析或者参数规划问题,从报告知,X的系数在 64~96之间则不用调整计划,现在的最优解仍然为最优解,90落在此范围内,不调整,
2.对偶问题及其相关理论与应用
21 4580m a x xxZ
0
4501015
400520
21
21
21
xx
xx
xx
ts
,
,..
回到讲过的生产桌椅的例子,由它得到的数学问题为
0,
45105
801520
s,t,
450400m i n
21
21
21
211
yy
yy
yy
yyZ
另一家同等条件的企业更换经营方式,采用出售劳力和原料,直接为用户定制桌椅的生产方式,为此需要给木材和劳力定价,设单位的木材、
劳力的价格分别为 y1 和 y2,由于竞争,经营者希望 y1 和 y2 尽可能小,但是降低不是无限度的,
它至少应保证 企业得到在同等条件下加工成桌椅后出售的收入,因此它所对应的数学问题为
0,
,4501015
400520
,.
21
21
21
xx
xx
xx
ts
21 4580m a x xxZ
0,
45105
801520
s,t,
450400m i n
21
21
21
211
yy
yy
yy
yyZ
而原来的模型为
0,s,t,
)(m i n
xbAX
XCx Tf
)(,..
)( m a x
CwA0wCAw
wbbww
TTT
TT
ts
g
等价地互为对偶问题
若上面的问题为原问题,则称 w 为 对偶变量,
问题对偶问题的理论
)()( o p to p t gf wx?
.0 xsws wx
定理 1(对偶定理 ) 互为对偶的两个线性规划问题,若其中之一有有穷的最优解,则另外一个也有有穷的最优解,且最优值相等,即,若二者之一有无界的最优解,则另外一个没有最优解,
定理 2(互补定理 ) 对于互为对偶的两个线性规划问题的最优解而言,若其一问题的任一约束不等式严格成立 (即松弛变量为正,非紧约束 ),则相应的对偶变量必为零 ;而任何一个最优解的正分量相对应的约束必为等式 (即松弛变量为零 ).事实上,
正问题的影子价格就是对偶问题的最优解,
作业,写出家具厂安排生产例子的对偶问题并用图解法求解,
并且求家具厂安排生产例子中的影子价格,
若要工人加班生产,加班费最多给多少?
对偶问题的应用例 3.1 假设一工厂可生产五种产品,分别以 P1
至 P5代表,其价格依次为 550,600,350,400,
200,每件产品均需经过研磨及钻孔两道工序,
所需研磨工时依次为 12,20,0,25,15;所需钻孔工时依次为 10,8,16,0,0.此外,每件产品均需要 20小时的装配工时,而工厂在一个生产周期内的总生产能力限制为,研磨 288工时,钻孔
192工时,装配 384工时,问
(1)工厂如何安排生产,以求最大收入,
54321 200400350600550 xxxxxZ m a x
2 8 81502012 54321 xxxxx 25
192016810 54321 xxxxx 0
38420022020 54321 xxxxx 20
解,令 xi 表示生产的这五种产品的数量,则问题归结为如下线性规划问题,
s.t.
我们运用 LINDO软件来求解,得到最优解为
x1=12,x2=7.2,x3=x4=x5=0,最优值
Z=10920.
从报告中我们还得知,研磨和装配能力用尽,
而钻孔能力还有 14.4的剩余,我们对此问题进一步分析相关问题,
(2)如果增加研磨,钻孔和装配能力,那么每种能力的单位增长,会带来多少经济价值,
(3)从上面的结果我们可以这样认为,与 P1,P2
相比,P3,P4,P5的价格定低了,不值得生产,那么价格提到什么程度,它们才值得生产,
75.23,0,25.6 321 www
31332211 75.2325.6 bbbwbwbwZ o p t
为回答这两个问题,我们需求解对偶问题,令对偶变量为 w1,w2,w3,用 LINDO软件求解原问题时,
事实上对偶问题是同时求解的,最优解为我们从对偶定理知道,当以最佳方式生产时,
因此我们可以这样认为,一个单位的研磨能力带来的效益是 6.25,装配能力则为 23.75,
而 w2=0 则反映了目前的钻孔能力有余,
不过,上面关于影子价格的讨论是要在最优解附近变化比较小,且最优解保持不变时才 是 正确的,若只有一个资源 (此处的每一种能力 )发生变化,其变化范围我们可以从 Range Analysis中直接查到,
关于成本下降 (reduced cost)的解释,或者是为发展某一产品暂时性的损失,或者是政府部门应给的补贴,
3.多目标问题简介
实际问题中我们往往希望多个目标都最优,
但是这一般是不可能的,通常我们用 某种线性组合 的方式,定义一个新的目标函数,将多目标问题转化为一个线性规划问题,
