管 理 运 筹 学 1
第九章 目标规划
§ 1 目标规划问题举例
§ 2 目标规划的图解法
§ 3 复杂情况下的 目标规划
§ 4 加权目标规划
§ 5 目标规划的单纯型法管 理 运 筹 学 2
§ 1 目标规划问题举例线性规划模型的特征是在满足一组约束条件下,寻求一个目标的最优解(最大值或最小值)。
而在现实生活中最优只是相对的,或者说没有绝对意义下的最优,只有相对意义下的满意。
1978年诺贝尔经济学奖获得者,西蒙 (H.A.Simon-美国卡内基 -
梅隆大学,1916-)教授提出“满意行为模型要比最大化行为模型丰富得多”,否定了企业的决策者是,经济人,概念和,最大化,行为准则,提出了,管理人,的概念和,令人满意,的行为准则,对现代企业管理的决策科学进行了开创性的研究管 理 运 筹 学 3
§ 1 目标规划问题举例例 1.企业生产
不同企业的生产目标是不同的 。 多数企业追求最大的经济效益 。
但随着环境问题的日益突出,可持续发展已经成为全社会所必须考虑的问题 。 因此,企业生产就不能再如以往那样只考虑企业利润,必须承担起社会责任,要考虑环境污染,社会效益,
公众形象等多个方面 。 兼顾好这几者关系,企业才可能保持长期的发展 。
例 2,商务活动
企业在进行盈亏平衡预算时,不能只集中在一种产品上,因为某一种产品的投入和产出仅仅是企业所有投入和产出的一部分 。
因此,需要用多产品的盈亏分析来解决具有多个盈亏平衡点的决策问题 ( 多产品的盈亏平衡点往往是不一致的 ) 。
管 理 运 筹 学 4
§ 1 目标规划问题举例例 3,投资
企业投资时不仅仅要考虑收益率,还要考虑风险 。 一般地,风险大的投资其收益率更高 。 因此,企业管理者只有在对收益率和风险承受水平有明确的期望值时,才能得到满意的决策 。
例 4.裁员
同样的,企业裁员时要考虑很多可能彼此矛盾的因素 。 裁员的首要目的是压缩人员开支,但在人人自危的同时员工的忠诚度就很难保证,此外,员工的心理压力,工作压力等都会增加,
可能产生负面影响 。
例 5,营销
营销方案的策划和执行存在多个目标。既希望能达到立竿见影的效果,又希望营销的成本控制在某一个范围内。此外,营销活动的深入程度也决定了营销效果的好坏和持续时间。
管 理 运 筹 学 5
§ 1 目标规划问题举例
【 例 1.1 】 考虑例 1.1.资源消耗如表 9-1所示。 x1,x2,x3分别为甲、乙、丙的产量。
使企业在计划期内总利润最大的线性规划模型为:
产品资源甲 乙 丙 现有资源设备 A 3 1 2 200
设备 B 2 2 4 200
材料 C 4 5 1 360
材料 D 2 3 5 300
利润(元 /件) 40 30 50
表 9-1
1.1 引例管 理 运 筹 学 6
§ 1 目标规划问题举例
321 503040m a x xxxZ
000
3 0 0532
3 6 054
2 0 0422
2 0 023
321
321
321
321
321
xxx
xxx
xxx
xxx
xxx
,,
最优解 X=( 50,30,10),Z= 3400
管 理 运 筹 学 7
§ 1 目标规划问题举例现在决策者根据企业的实际情况和市场需求,需要重新制定经营目标,其目标的优先顺序是:
( 1)利润不少于 3200元
( 2)产品甲与产品乙的产量比例尽量不超过 1.5
( 3)提高产品丙的产量使之达到 30件
( 4)设备加工能力不足可以加班解决,能不加班最好不加班
( 5)受到资金的限制,只能使用现有材料不能再购进
【 解 】 设甲、乙、丙产品的产量分别为 x1,x2,x3。如果按线性规划建模思路,最优解实质是求下列一组不等式的解管 理 运 筹 学 8
§ 1 目标规划问题举例
000
300532
36054
200422
20023
30
05.1
3 2 0 0503040
321
321
321
321
321
3
21
321
xxx
xxx
xxx
xxx
xxx
x
xx
xxx
,,
-
通过计算不等式无解,即使设备加班 10小时仍然无解.在实际生产过程中生产方案总是存在的,无解只能说明在现有资源条件下,不可能完全满足所有经营目标.
这种情形是按事先制定的目标顺序逐项检查,尽可能使得结果达到预定目标,即使不能达到目标也使得离目标的差距最小,这就是目标规划的求解思路,对应的解称为满意解.下面建立例 1.1的目标规划数学模型.
管 理 运 筹 学 9
§ 1 目标规划问题举例设 d- 为未达到目标值的差值,称为负偏差变量( negative deviation
variable)
d+为超过目标值的差值,称为正偏差变量 ( positive deviation
variable),d- ≥0,d+ ≥0.
设 d1-未达到利润目标的差值,d1+ 为超过目标的差值当利润小于 3200时,d1- >0且 d1+ = 0,有
40x1+30x2+50x3+d1- =3200成立当利润大于 3200时,d1+ >0且 d1- =0,有
40x1+30x2+50x3-d1+=3200成立当利润恰好等于 3200时,d1- =0且 d1+=0,有
40x1+30x2+50x3=3200成立实际利润只有上述三种情形之一发生,因而可以将三个等式写成一个等式 40x
1+30x2+50x3+d1- - d1+=3200
管 理 运 筹 学 10
§ 1 目标规划问题举例
3 2 0 0503040
m i n
11321
1
ddxxx
d
( 2)设 分别为未达到和超过产品比例要求的偏差变量,则产量比例尽 量不超过 1.5的数学表达式为,
22 dd,
05.1
m i n
2221
2
ddxx
d
( 3)设 d3ˉ,d3 + 分别为品丙的产量未达到和超过 30件的偏差变量,则产量丙的产量尽可能达到 30件的数学表达式为:
30
m in
333
3
ddx
d
利润不少于 3200理解为达到或超过 3200,即使不能达到也要尽可能接近 3200,可以表达成目标函数{ d1- }取最小值,则有管 理 运 筹 学 11
§ 1 目标规划问题举例
( 4) 设 d4ˉ,d4+为设备 A的使用时间偏差变量,d5ˉ,d5+为设备
B的使用时间偏差变量,最好不加班的含义是 d4+ 和 d5+同时取最小值,等价 于 d4+ + d5+取最小值,则设备的目标函数和约束为:
200422
20023
m in
55321
44321
54
ddxxx
ddxxx
dd
( 5)材料不能购进表示不允许有正偏差,约束条件为小于等于约束.
由于目标是有序的并且四个目标函数非负,因此目标函数可以表达成一个函数:
管 理 运 筹 学 12
§ 1 目标规划问题举例
)(m in 544332211 ddPdPdPdPz
式中,Pj( j=1,2,3,4)称为目标的优先因子,第一目标优于第二目标,第二目标优于第三目标等等,其含义是按 P1,P2,… 的次序分别求后面函数的最小值,则问题的目标规划数学模型为:
5,2,1,0,0,0,0
3 0 0532
3 6 054
2 0 0422
2 0 023
30
05.1
3 2 0 0503040
)(m i n
321
321
321
55321
44321
333
2221
11321
544332211
jddxxx
xxx
xxx
ddxxx
ddxxx
ddx
ddxx
ddxxx
ddPdPdPdPz
jj
、且为整数
-
管 理 运 筹 学 13
§ 2 目标规划的图解法例 6,一位投资商有一笔资金准备购买股票 。 资金总额为 90000元,目前可选的股票有 A和 B两种 ( 可以同时投资于两种股票 ) 。 其价格以及年收益率和风险系数如表 1:
从上表可知,A股票的收益率为 ( 3/ 20) × 100% = 15%,股票 B
的收益率为 4/ 50× 100% = 8%,A的收益率比 B大,但同时 A的风险也比 B大 。 这也符合高风险高收益的规律 。
试求一种投资方案,使得一年的总投资风险不高于 700,且投资收益不低于 10000元 。 用来全部投资一个股票两个目标不能同时达到,
股票 价格(元) 年收益(元)/年 风险系数
A 20 3 0.5
B 50 4 0.2
管 理 运 筹 学 14
§ 2 目标规划的图解法显然,此问题属于目标规划问题 。 它有两个目标变量:一是限制风险,一是确保收益 。 在求解之前,应首先考虑两个目标的优先权 。
假设第一个目标 ( 即限制风险 ) 的优先权比第二个目标 ( 确保收益 ) 大,这意味着求解过程中必须首先满足第一个目标,
然后在此基础上再尽量满足第二个目标 。
建立模型:
设 x1,x2分别表示投资商所购买的 A股票和 B股票的数量 。
首先考虑资金总额的约束:总投资额不能高于 90000元 。 即
20x1+ 50x2≤ 90000。
管 理 运 筹 学 15
§ 2 目标规划的图解法一,约束条件再来考虑风险约束:总风险不能超过 700。 投资的总风险为
0.5x1+ 0.2x2。 引入两个变量 d1+和 d1-,建立等式如下:
0.5x1 +0.2x2=700+d1+-d1-
其中,d1+表示总风险高于 700的部分,d1-表示总风险少于 700的部分,d1+≥ 0。
目标规划中把 d1+,d1-这样的变量称为偏差变量。偏差变量的作用是允许约束条件不被精确满足。
管 理 运 筹 学 16
§ 2 目标规划的图解法把等式转换,可得到
0.5x1 +0.2x2-d1++d1-=700。
再来考虑年收入,
年收入 =3x1+4x2
引入变量 d2+和 d2-,分别表示年收入超过与低于 10000的数量 。
于是,第 2个目标可以表示为
3x1+4x2-d2++d2-=10000。
管 理 运 筹 学 17
§ 2 目标规划的图解法二,有优先权的目标函数本问题中第一个目标的优先权比第二个目标大 。 即最重要的目标是满足风险不超过 700。 分配给第一个目标较高的优先权 P1,
分配给第二个目标较低的优先权 P2。
针对每一个优先权,应当建立一个单一目标的线性规划模型 。
首先建立具有最高优先权的目标的线性规划模型,求解;然后再按照优先权逐渐降低的顺序分别建立单一目标的线性规划模型,方法是在原来模型的基础上修改目标函数,并把原来模型求解所得的目标最优值作为一个新的约束条件加入到当前模型中,并求解 。
管 理 运 筹 学 18
§ 2 目标规划的数学模型
( 1)目标规划数学模型的形式有:线性模型、非线性模型、
整数模型、交互作用模型等
( 2)一个目标中的两个偏差变量 di-,di+至少一个等于零,偏差变量向量的叉积等于零,d- × d+ =0
( 3)一般目标规划是将多个目标函数写成一个由偏差变量构成的函数求最小值,按多个目标的重要性,确定优先等级,
顺序求最小值
( 4)按决策者的意愿,事先给定所要达到的目标值当期望结果不超过目标值时,目标函数求正偏差变量最小 ;
当期望结果不低于目标值时,目标函数求负偏差变量最小 ;
当期望结果恰好等于目标值时,目标函数求正负偏差变量之和最小
9.2 数学模型管 理 运 筹 学 19
§ 2 目标规划的数学模型
( 5)由目标构成的约束称为目标约束,目标约束具有更大的弹性,允许结果与所制定的目标值存在正或负的偏差,如例 1.1中的 5个等式约束;如果决策者要求结果一定不能有正或负的偏差,
这种约束称为系统约束,如例 1.1的材料约束;
( 6)目标的排序问题。多个目标之间有相互冲突时,决策者首先必须对目标排序。排序的方法有两两比较法、专家评分等方法,构造各目标的权系数,依据权系数的大小确定目标顺序;
( 7)合理的确定目标数。目标规划的目标函数中包含了多个目标,决策者对于具有相同重要性的目标可以合并为一个目标,
如果同一目标中还想分出先后次序,可以赋予不同的权系数,
按系数大小再排序。例如,在例 1.1中要求设备 B的加班时间不超过设备 A的时间,目标函数可以表达为,表示在中先求 最小再求 最小。
54 2dd 54 dd,
5d?4d
管 理 运 筹 学 20
§ 2 目标规划的数学模型
( 8)目标规划的一般模型.设 xj( j=1,2,…,n)为决策变量
)1.4(),,1(0,
)1.4(),,1(0
)1.4(),,1(
)1.4(),,1(),(
)1.4()(m i n
1
1
11
eLldd
dnjx
cLlgddxc
bmibxa
adwdwPz
l
l
j
n
j
llljlj
n
j
ijij
L
l
lkllkl
K
k
k
式中 p k 为第 k 级优先因子,k=1,2,…… K ; wkl-,wkl+,为分别赋予第 l个目标约束的正负偏差变量的权系数; gl为目标的预期目标值,l=1,…L,(4.1b)为系统约束,( 4.1c)为目标约束管 理 运 筹 学 21
§ 2 目标规划的数学模型
【 例 1.2】 某企业集团计划用 1000万元对下属 5个企业进行技术改造,各企业单位的投资额已知,考虑 2种市场需求变化、现有竞争对手、替代品的威胁等影响收益的 4个因素,技术改造完成后预测单位投资收益率 ((单位投资获得利润 /单位投资额)
× 100% )如表 1- 2所示.
集团制定的目标是:
( 1)希望完成总投资额又不超过预算;
( 2)总期望收益率达到总投资的 30%;
( 3)投资风险尽可能最小;
( 4)保证企业 5的投资额占 20%左右.
集团应如何作出投资决策.
管 理 运 筹 学 22
§ 2 目标规划的数学模型企业 1 企业 2 企业 3 企业 4 企业 5
单位投资额 (万元 ) 12 10 15 13 20
单位投资收益率预测
rij
市场需求 1 4.32 5 5.84 5.2 6.56
市场需求 2 3.52 3.04 5.08 4.2 6.24
现有竞争对手 3.16 2.2 3.56 3.28 4.08
替代品的威胁 2.24 3.12 2.6 2.2 3.24
期望 (平均 )收益率% 3.31 3.34 4.27 3.72 5.03
表 1- 2
管 理 运 筹 学 23
§ 2 目标规划的数学模型
【 解 】 设 xj( j=1,2,…,5 )为集团对第 j 个企业投资的单位数.
1 0 0 02013151012 1154321 ddxxxxx
( 1)总投资约束:
( 2)期望利润率约束:
)2013151012(3.0
03.572.327.434.331.3
54321
2254321
xxxxx
ddxxxxx
整理得
097.018.023.034.029.0 2254321 = ddxxxxx
管 理 运 筹 学 24
§ 2 目标规划的数学模型
079.152.167.122.007.1
095.044.071.014.115.0
021.148.081.03.021.0
053.148.157.166.101.1
6654321
5554321
4454321
3354321
ddxxxxx
ddxxxxx
ddxxxxx
ddxxxxx
( 4)企业 5占 20%的投资的目标函数为,约束条件 77min dd
)2013151012(2.020 54321775 xxxxxddx
0166.2324.2 7754321 ddxxxxx即
(3)投资风险约束.投资风险值的大小一般用期望收益率的方差表示,但方差是 x的非线性函数.这里用离差( rij- E(rj))近似表示风险值,例如,集团投资 5个企业后对于市场需求变化第一情形的风险是:
则 4种因素风险最小的目标函数为:,约束条件为
521 )03.556.6()34.35()31.332.4( xxx
6
3
)(m in
i
ii dd
管 理 运 筹 学 25
§ 2 目标规划的数学模型
)()()(m i n 7746
3
322111
ddPddPdPddPZ
i
ii
5,,2,17,,2,10,0
0166.2324.2
079.152.167.122.007.1
095.044.071.014.115.0
021.148.081.03.021.0
053.148.157.166.101.1
097.018.023.034.029.0
1 0 0 02013151012
7754321
6654321
5554321
4454321
3354321
2254321
1154321
jiddx
ddxxxxx
ddxxxxx
ddxxxxx
ddxxxxx
ddxxxxx
ddxxxxx
ddxxxxx
iij;;、
=
根据目标重要性依次写出目标函数,整理后得到投资决策的目标规划数学模型:
管 理 运 筹 学 26
§ 2 目标规划的数学模型
【 例 1.3】 车间计划生产 I,II 两种产品,每种产品均需经过 A、
B两道工序加工.工艺资料如表 4- 3所示.
产品工序 产品甲 产品乙 每天加工能力 (小时 )
A 2 2 120
B 1 2 100
C 2.2 0.8 90
产品售价 (元 /件 ) 50 70
产品利润 (元 /件 ) 10 8
( 1)车间如何安排生产计划,使产值和利润都尽可能高
( 2)如果认为利润比产值重要,怎样决策表 1- 3
管 理 运 筹 学 27
§ 2 目标规划的数学模型
【 解 】 设 x1,x2分别为产品甲和产品乙的日产量,得到线性多目标规划模型:
0
908.02.2
1 0 02
1 2 022
810m a x
7050m a x
21
21
21
21
212
211
xx
xx
xx
xx
xxZ
xxZ
、
管 理 运 筹 学 28
§ 2 目标规划的数学模型
( 1)将模型化为目标规划问题.首先,通过分别求产值最大和利润最大的线性规划最优解.
产值最大的最优解,X(1)=( 20,40),Z1= 3800
利润最大的最优解,X (2) =( 30,30),Z2= 540
目标确定为产值和利润尽可能达到 3800和 540,得到目标规划数学模型:
2,1,0
908.02.2
1 0 02
1 2 022
5 4 0810
3 8 0 07050
m i n
21
21
21
2221
1121
21
jddx
xx
xx
xx
ddxx
ddxx
ddZ
jjj
、、
管 理 运 筹 学 29
§ 2 目标规划的图解法三,图解法
1,针对优先权最高的目标建立线性规划建立线性规划模型如下:
Min d1+
s.t.
20x1+ 50x2≤ 90000
0.5x1 +0.2x2-d1++d1-=700
3x1+4x2-d2++d2-=10000
x1,x2,d1+,d1-≥ 0
管 理 运 筹 学 30
§ 2 目标规划的图解法图 2 图解法步骤 2
0 1000 2000 3000 4000 5000
2000
3000
4000
x1
x2
20x1+ 50x2≤900001000
0.5x1 +0.2x2=700
管 理 运 筹 学 31
§ 2 目标规划的图解法
2,针对优先权次高的目标建立线性规划优先权次高 ( P2) 的目标是总收益超过 10000。
建立线性规划如下:
Min d2-
s.t.
20x1+ 50x2≤ 90000
0.5x1 +0.2x2-d1++d1-=700
3x1+4x2-d2++d2-=10000
d1+= 0
x1,x2,d1+,d1-,d2+,d2-≥ 0
管 理 运 筹 学 32
§ 2 目标规划的图解法
3x1+4x2=10000
图 3 图解法步骤 3
0 1000 2000 3000 4000 5000
2000
3000
4000
x1
x2
20x1+ 50x2≤900001000
0.5x1 +0.2x2=700
d1+>0
d1+= 0
d2-=0
d2->0
(810,1476)
管 理 运 筹 学 33
§ 2 目标规划的图解法目标规划的这种求解方法可以表述如下:
1,确定解的可行区域 。
2,对优先权最高的目标求解,如果找不到能满足该目标的解,
则寻找最接近该目标的解 。
3,对优先权次之的目标进行求解 。 注意:必须保证优先权高的目标不变 。
4,重复第 3步,直至所有优先权的目标求解完。
管 理 运 筹 学 34
§ 2 目标规划的图解法四,目标规划模型的标准化例 6中对两个不同优先权的目标单独建立线性规划进行求解 。 为简便,把它们用一个模型来表达,如下:
Min P1( d1+) +P2( d2-)
s.t.
20x1+ 50x2≤ 90000
0.5x1 +0.2x2-d1++d1-=700
3x1+4x2-d2++d2-=10000
x1,x2,d1+,d1-,d2+,d2-≥0
管 理 运 筹 学 35
§ 2 目标规划的图解法
【 例 】 企业计划生产 I,II 两种产品,这些产品需要使用两种材料,要在两种不同设备上加工.工艺资料如表 4- 4所示.
产品资源 产品甲 产品乙 现有资源材料 I 3 0 12(kg)
材料 II 0 4 14(kg)
设备 A 2 2 12(h)
设备 B 5 3 15(h)
产品利润 (元 /件 ) 20 40
表 4- 4
管 理 运 筹 学 36
§ 2 目标规划的图解法
【 解 】 设 x1,x2分别为产品甲和产品乙的产量,目标规划数学模型为:
企业怎样安排生产计划,尽可能满足下列目标:
(1)力求使利润指标不低于 80元
(2)考虑到市场需求,I,II两种产品的生产量需保持 1:1的比例
(3)设备 A既要求充分利用,又尽可能不加班
(4) 设备 B必要时可以加班,但加班时间尽可能少
(5)材料不能超用。
4333322211 )()mi n dPddPddPdPz (
1
2
1 2 1 1
1 2 2 2
1 2 3 3
1 2 4 4
12
3 12 (1 )
4 16 ( 2)
20 40 80 ( 3 )
0 ( 4)
2 2 12 ( 5 )
5 3 15 ( 6)
,,0 ( 1,,4)
ii
x
x
x x d d
x x d d
x x d d
x x d d
x x d d i
管 理 运 筹 学 37
(2)
(1)
(3)
(4 )
x2
x1
(6)
(5)
o 4 6
4
6
2
2
图 4- 1
A
B
C
1 1 2 2 2 3 3 3 4 4m i n ) ( )z P d P d d P d d P d(
4d?
4d?
1d?
1d?
2d?
3d? 2d
3d?
1
2
1 2 1 1
1 2 2 2
1 2 3 3
1 2 4 4
12
3 12 (1 )
4 16 ( 2)
20 40 80 ( 3 )
0 ( 4)
2 2 12 ( 5 )
5 3 15 ( 6)
,,0 ( 1,,4)
ii
x
x
x x d d
x x d d
x x d d
x x d d
x x d d i
满意解
C(3,3)
1min d
22m in dd
33min dd
满意解 X= (3,3)
管 理 运 筹 学 38
§ 2 目标规划的图解法
(3)
x1
x2
20 40 60 80 100
20
40
60
80
100
(2)
(1)
(4)
1d
1d?2d?3d
2d
3d
4d
4d
1 1 2 2 3 3 3 4
1 2 1 1
1 2 2 2
1 2 3 3
1 2 4 4
12
m in ( ) ( )
1 0 5 4 0 0 (1 )
7 8 5 6 0 ( 2 )
2 2 1 2 0 ( 3 )
2,5 1 0 0 ( 4 )
,0,1,,4
jj
Z P d d P d d P d
x x d d
x x d d
x x d d
x x d d
x x d d j
、,
B
C
满意解是线段 上任意点,端点的解是 B(100/3,80/3),C(60,0).
决策者根据实际情形进行二次选择.
BCA
管 理 运 筹 学 39
§ 2 目标规划的图解法
(3)
x1
x2
20 40 60 80 100
20
40
60
80
100
(2)
(1)
(4)
1d
1d?2d?3d
2d
3d
4d
4d
图 5- 3
4,,1,0,
)4(1005.2
)3(12022
)2(56087
)1(400510
21
4421
3321
2221
1121
jddxx
ddxx
ddxx
ddxx
ddxx
jj
、、
B
C
满意解是点 B,X=(100/3,80/3)
1 1 2 2 3 3 3 4 41m i n ( ) ( )Z P d d P d d P d Pd
A
管 理 运 筹 学 40
(3)
x1
x2
20 40 60 80 100
20
40
60
80
100
(2)
(1)
(4)
1d
1d?2d?3d
2d
3d
4d
4d
4,,1,0,
)4(1005.2
)3(12022
)2(56087
)1(400510
21
4421
3321
2221
1121
jddxx
ddxx
ddxx
ddxx
ddxx
jj
、、
满意解是点 A,X=(20,40)
43322111 )2()(m i n dPddPddPZ
A(20,40)
D(80/9,560/9)
32 2dd
注:线段 DA是第二目标函数的组合,
点 A对应的偏差,d2-=100,d3+ =0
点 D对应的偏差,d2-=0,2d3+ =2× 200/9=400/9
管 理 运 筹 学 41
§ 3 复杂情况下的目标规划例 7,一工艺品厂商手工生产某两种工艺品 A,B,已知生产一件产品 A需要耗费人力 2工时,生产一件产品 B需要耗费人力 3工时 。
A,B产品的单位利润分别为 250元和 125元 。 为了最大效率地利用人力资源,确定生产的首要任务是保证人员高负荷生产,要求每周总耗费人力资源不能低于 600工时,但也不能超过 680工时的极限;次要任务是要求每周的利润超过 70000元;在前两个任务的前提下,为了保证库存需要,要求每周产品 A和 B的产量分别不低于 200和 120件,因为 B产品比 A产品更重要,不妨假设
B完成最低产量 120件的重要性是 A完成 200件的重要性的 1倍 。
试求如何安排生产?
管 理 运 筹 学 42
§ 3 复杂情况下的目标规划解:
本问题中有 3个不同优先权的目标,不妨用 P1,P2,P3表示从高至低的优先权 。
对应 P1有两个目标:每周总耗费人力资源不能低于 600工时,
也不能超过 680工时;
对应 P2有一个目标:每周的利润超过 70000元;
对应 P3有两个目标:每周产品 A和 B的产量分别不低于 200和
120件 。
管 理 运 筹 学 43
§ 3 复杂情况下的目标规划采用简化模式,最终得到目标线性规划如下:
Min P1(d1+)+ P1(d2- )+P2(d3-)+ P3(d4-)+ P3(2d5-)
s.t.
2x1+3x2-d1++d1-=680 对应第 1个目标
2x1+3x2-d2++d2-=600 对应第 2个目标
250x1+125x2-d3-+d3+= 70000 对应第 3个目标
x1-d4++d4-=200 对应第 4个目标
x2-d5++d5-=120 对应第 5个目标
x1,x2,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,d5+,d5-≥ 0
管 理 运 筹 学 44
§ 3 复杂情况下的目标规划使用运筹学软件求解可得:
x1=250; x2=60; d1+=0; d1-=0; d2+=80; d2-=0; d3+=0; d3-=0;
d4+=50; d4-=0; d5+=0; d5-=60,目标函数 d4-+2d5- =120。
可见,目标 1、目标 3和目标 4达到了,但目标 2、目标 5都有一些偏差。
管 理 运 筹 学 45
§ 4 加权目标规划
加权目标规划 是另一种解决多目标决策问题的方法,其基本方法是通过量化的方法分配给每个目标的偏离的严重程度一个罚数权重,然后建立总的目标函数,该目标函数表示的目标是要使每个目标函数与各自目标的加权偏差之和最小,假设所有单个的目标函数及约束条件都符合线性规划的要求,那么,整个问题都可以描述为一个线性规划的问题。
如果在例 7中我们对每周总耗费的人力资源超过 680工时或低于 600工时的每工时罚数权重定为 7;每周利润低于 70000
元时,每元的罚数权重为 5;每周产品 A产量低于 200件时每件罚数权重为 2,而每周产品 B产量低于 120件时每件罚数权重为 4。
管 理 运 筹 学 46
§ 4 加权目标规划
则其目标函数化为:
min7d1++7d2-+5d3-+2d4-+4d5-
这就变成了一个普通的单一目标的线性规划问题
min7d1++7d2-+5d3-+2d4-+4d5-
s.t,2x1+3x2-d1++d1-=680
2x1+3x2-d2-+d2+=680
250x1+125x2-d3-+d3+=70000
x1-d4++d4-=200
x2-d5++d5-=120
x1,x2,d1+,d1-,d2-,d2+,d3+,d3-,d4+,d4-,d5+,d5-≥0 。
管 理 运 筹 学 47
§ 5 目标规划的单纯型法单纯形法求解目标规划可参照第一章的步骤,只是目标规划的检验要按优先级顺序逐级进行,不同的是:
( 1)首先使得检验数中 P1的系数非负,再使得 P2的系数非负,
依次进行;
( 2)当 P1,P2,…,Pk对应的系数全部非负时得到最优解;
( 3)如果 P1,…,Pi行系数非负,而 Pi+1行存在负数,并且负数所在列上面 P1,…,Pi行中存在正数时,得到满意解,计算结束.
管 理 运 筹 学 48
§ 5 目标规划的单纯型法
【 例 4.6】 用单纯形法求解下述目标规划问题
)3,2,1(0,,,
8022
402
502
)(m in
21
3321
2221
1121
32211
iddxx
ddxx
ddxx
ddxx
dPddPz
ii
-
【 解 】 以 d1-,d2-,d3- 为基变量,求出检验数,将检验数中优先因子分离出来,每一优先级做一行,列出初始单纯形表 4-5.
管 理 运 筹 学 49
§ 5 目标规划的单纯型法
Cj 0 0 P1 0 0 P1 P2 0
b
CB 基变 量 x1 x2 d1- d1+ d2- d2+ d3- d3+
P1 d1- 1 [2] 1 - 1 50→
0 d2- 2 1 1 - 1 40
P2 d3- 2 2 1 - 1 80
Cj- Zj
P1 - 1 - 2 1 1
P2 - 2 - 2 1
表 4- 5
管 理 运 筹 学 50
§ 5 目标规划的单纯型法表 4- 5中,P1行中 (- 2)最小,则 x2进基,求最小比值易知 d1- 出基,将第二列主元素化为 1,其余元素化为零,得到表 4- 6.
Cj 0 0 P1 0 0 P1 P2 0 b
CB 基 x1 x2 d1- d1+ d2- d2+ d3- d3+
0 x2 1/2 1 1/2 - 1/2 25
0 d2- [3/2] 1/2 1 - 1 15→
P2 d3- 1 1 1 - 1 30
Cj- Zj P1 1 1P
2 - 1 1 - 1 1
表 4- 6
管 理 运 筹 学 51
§ 5 目标规划的单纯型法表 4- 6中 P1行全部检验数非负,表明第一目标已经得到优化,P2
行存在负数,x1的检验数为- P2<0,选 x1进基(也可以选 d1+进基),则 d3- 出基,迭代得到表 4-7.
Cj 0 0 P1 0 0 P1 P2 0
bC
B 基 x1 x2 d1
- d
1
+ d2- d
2
+ d
3
- d
3
+
0 x2 1 2/3 - 2/3 1/3 20
0 x1 1 [1/3] 2/3 10→
P2 d3- 2/3 2/3 1 - 1 20
Cj- Zj P1 1 1P
2 2/3 -2/3 2/3 -2/3 1
表 4-7
管 理 运 筹 学 52
§ 5 目标规划的单纯型法在表 4-7中,P1行的系数全部非负,P2行存在负数,d1+的检验数- 2/3P2<0,
选 d1+进基,则 x1出基,迭代得到表 4-8.
应当注意,表 4-7中不能选 d2+进基,检验数 P1- 2/3P2应理解为“大于零”,
P1,P2是优先级别的比较,而不是“数”的比较.
Cj→ 0 0 P
1 0 0 P1 P2 0 b
CB 基 x1 x2 d1- d1+ d2- d2+ d3- d3+
0 x2 2 1 1 - 1 40
0 d1+ 3 - 1 1 2 - 2 30
P2 d3- - 2 - 2 2 1 - 1 0
Cj- Zj P1 1 1P
2 2 2 - 2 1
表 4- 8
管 理 运 筹 学 53
§ 5 目标规划的单纯型法表 4-8中 P2行的(- 2)小于零,但(- 2)列上面 P1行存在正数 1,
检验数 P1- 2P2>0,所有检验数非负,得到满意解 X=( 0,40)
【 例 】
4,3,2,1,0,,,;100;60;1402;25001230
5.2m in
21
442
331
2221
1121
23423211
lddxx
ddx
ddx
ddxx
ddxx
dPdPdPdPZ
ll
第九章 目标规划
§ 1 目标规划问题举例
§ 2 目标规划的图解法
§ 3 复杂情况下的 目标规划
§ 4 加权目标规划
§ 5 目标规划的单纯型法管 理 运 筹 学 2
§ 1 目标规划问题举例线性规划模型的特征是在满足一组约束条件下,寻求一个目标的最优解(最大值或最小值)。
而在现实生活中最优只是相对的,或者说没有绝对意义下的最优,只有相对意义下的满意。
1978年诺贝尔经济学奖获得者,西蒙 (H.A.Simon-美国卡内基 -
梅隆大学,1916-)教授提出“满意行为模型要比最大化行为模型丰富得多”,否定了企业的决策者是,经济人,概念和,最大化,行为准则,提出了,管理人,的概念和,令人满意,的行为准则,对现代企业管理的决策科学进行了开创性的研究管 理 运 筹 学 3
§ 1 目标规划问题举例例 1.企业生产
不同企业的生产目标是不同的 。 多数企业追求最大的经济效益 。
但随着环境问题的日益突出,可持续发展已经成为全社会所必须考虑的问题 。 因此,企业生产就不能再如以往那样只考虑企业利润,必须承担起社会责任,要考虑环境污染,社会效益,
公众形象等多个方面 。 兼顾好这几者关系,企业才可能保持长期的发展 。
例 2,商务活动
企业在进行盈亏平衡预算时,不能只集中在一种产品上,因为某一种产品的投入和产出仅仅是企业所有投入和产出的一部分 。
因此,需要用多产品的盈亏分析来解决具有多个盈亏平衡点的决策问题 ( 多产品的盈亏平衡点往往是不一致的 ) 。
管 理 运 筹 学 4
§ 1 目标规划问题举例例 3,投资
企业投资时不仅仅要考虑收益率,还要考虑风险 。 一般地,风险大的投资其收益率更高 。 因此,企业管理者只有在对收益率和风险承受水平有明确的期望值时,才能得到满意的决策 。
例 4.裁员
同样的,企业裁员时要考虑很多可能彼此矛盾的因素 。 裁员的首要目的是压缩人员开支,但在人人自危的同时员工的忠诚度就很难保证,此外,员工的心理压力,工作压力等都会增加,
可能产生负面影响 。
例 5,营销
营销方案的策划和执行存在多个目标。既希望能达到立竿见影的效果,又希望营销的成本控制在某一个范围内。此外,营销活动的深入程度也决定了营销效果的好坏和持续时间。
管 理 运 筹 学 5
§ 1 目标规划问题举例
【 例 1.1 】 考虑例 1.1.资源消耗如表 9-1所示。 x1,x2,x3分别为甲、乙、丙的产量。
使企业在计划期内总利润最大的线性规划模型为:
产品资源甲 乙 丙 现有资源设备 A 3 1 2 200
设备 B 2 2 4 200
材料 C 4 5 1 360
材料 D 2 3 5 300
利润(元 /件) 40 30 50
表 9-1
1.1 引例管 理 运 筹 学 6
§ 1 目标规划问题举例
321 503040m a x xxxZ
000
3 0 0532
3 6 054
2 0 0422
2 0 023
321
321
321
321
321
xxx
xxx
xxx
xxx
xxx
,,
最优解 X=( 50,30,10),Z= 3400
管 理 运 筹 学 7
§ 1 目标规划问题举例现在决策者根据企业的实际情况和市场需求,需要重新制定经营目标,其目标的优先顺序是:
( 1)利润不少于 3200元
( 2)产品甲与产品乙的产量比例尽量不超过 1.5
( 3)提高产品丙的产量使之达到 30件
( 4)设备加工能力不足可以加班解决,能不加班最好不加班
( 5)受到资金的限制,只能使用现有材料不能再购进
【 解 】 设甲、乙、丙产品的产量分别为 x1,x2,x3。如果按线性规划建模思路,最优解实质是求下列一组不等式的解管 理 运 筹 学 8
§ 1 目标规划问题举例
000
300532
36054
200422
20023
30
05.1
3 2 0 0503040
321
321
321
321
321
3
21
321
xxx
xxx
xxx
xxx
xxx
x
xx
xxx
,,
-
通过计算不等式无解,即使设备加班 10小时仍然无解.在实际生产过程中生产方案总是存在的,无解只能说明在现有资源条件下,不可能完全满足所有经营目标.
这种情形是按事先制定的目标顺序逐项检查,尽可能使得结果达到预定目标,即使不能达到目标也使得离目标的差距最小,这就是目标规划的求解思路,对应的解称为满意解.下面建立例 1.1的目标规划数学模型.
管 理 运 筹 学 9
§ 1 目标规划问题举例设 d- 为未达到目标值的差值,称为负偏差变量( negative deviation
variable)
d+为超过目标值的差值,称为正偏差变量 ( positive deviation
variable),d- ≥0,d+ ≥0.
设 d1-未达到利润目标的差值,d1+ 为超过目标的差值当利润小于 3200时,d1- >0且 d1+ = 0,有
40x1+30x2+50x3+d1- =3200成立当利润大于 3200时,d1+ >0且 d1- =0,有
40x1+30x2+50x3-d1+=3200成立当利润恰好等于 3200时,d1- =0且 d1+=0,有
40x1+30x2+50x3=3200成立实际利润只有上述三种情形之一发生,因而可以将三个等式写成一个等式 40x
1+30x2+50x3+d1- - d1+=3200
管 理 运 筹 学 10
§ 1 目标规划问题举例
3 2 0 0503040
m i n
11321
1
ddxxx
d
( 2)设 分别为未达到和超过产品比例要求的偏差变量,则产量比例尽 量不超过 1.5的数学表达式为,
22 dd,
05.1
m i n
2221
2
ddxx
d
( 3)设 d3ˉ,d3 + 分别为品丙的产量未达到和超过 30件的偏差变量,则产量丙的产量尽可能达到 30件的数学表达式为:
30
m in
333
3
ddx
d
利润不少于 3200理解为达到或超过 3200,即使不能达到也要尽可能接近 3200,可以表达成目标函数{ d1- }取最小值,则有管 理 运 筹 学 11
§ 1 目标规划问题举例
( 4) 设 d4ˉ,d4+为设备 A的使用时间偏差变量,d5ˉ,d5+为设备
B的使用时间偏差变量,最好不加班的含义是 d4+ 和 d5+同时取最小值,等价 于 d4+ + d5+取最小值,则设备的目标函数和约束为:
200422
20023
m in
55321
44321
54
ddxxx
ddxxx
dd
( 5)材料不能购进表示不允许有正偏差,约束条件为小于等于约束.
由于目标是有序的并且四个目标函数非负,因此目标函数可以表达成一个函数:
管 理 运 筹 学 12
§ 1 目标规划问题举例
)(m in 544332211 ddPdPdPdPz
式中,Pj( j=1,2,3,4)称为目标的优先因子,第一目标优于第二目标,第二目标优于第三目标等等,其含义是按 P1,P2,… 的次序分别求后面函数的最小值,则问题的目标规划数学模型为:
5,2,1,0,0,0,0
3 0 0532
3 6 054
2 0 0422
2 0 023
30
05.1
3 2 0 0503040
)(m i n
321
321
321
55321
44321
333
2221
11321
544332211
jddxxx
xxx
xxx
ddxxx
ddxxx
ddx
ddxx
ddxxx
ddPdPdPdPz
jj
、且为整数
-
管 理 运 筹 学 13
§ 2 目标规划的图解法例 6,一位投资商有一笔资金准备购买股票 。 资金总额为 90000元,目前可选的股票有 A和 B两种 ( 可以同时投资于两种股票 ) 。 其价格以及年收益率和风险系数如表 1:
从上表可知,A股票的收益率为 ( 3/ 20) × 100% = 15%,股票 B
的收益率为 4/ 50× 100% = 8%,A的收益率比 B大,但同时 A的风险也比 B大 。 这也符合高风险高收益的规律 。
试求一种投资方案,使得一年的总投资风险不高于 700,且投资收益不低于 10000元 。 用来全部投资一个股票两个目标不能同时达到,
股票 价格(元) 年收益(元)/年 风险系数
A 20 3 0.5
B 50 4 0.2
管 理 运 筹 学 14
§ 2 目标规划的图解法显然,此问题属于目标规划问题 。 它有两个目标变量:一是限制风险,一是确保收益 。 在求解之前,应首先考虑两个目标的优先权 。
假设第一个目标 ( 即限制风险 ) 的优先权比第二个目标 ( 确保收益 ) 大,这意味着求解过程中必须首先满足第一个目标,
然后在此基础上再尽量满足第二个目标 。
建立模型:
设 x1,x2分别表示投资商所购买的 A股票和 B股票的数量 。
首先考虑资金总额的约束:总投资额不能高于 90000元 。 即
20x1+ 50x2≤ 90000。
管 理 运 筹 学 15
§ 2 目标规划的图解法一,约束条件再来考虑风险约束:总风险不能超过 700。 投资的总风险为
0.5x1+ 0.2x2。 引入两个变量 d1+和 d1-,建立等式如下:
0.5x1 +0.2x2=700+d1+-d1-
其中,d1+表示总风险高于 700的部分,d1-表示总风险少于 700的部分,d1+≥ 0。
目标规划中把 d1+,d1-这样的变量称为偏差变量。偏差变量的作用是允许约束条件不被精确满足。
管 理 运 筹 学 16
§ 2 目标规划的图解法把等式转换,可得到
0.5x1 +0.2x2-d1++d1-=700。
再来考虑年收入,
年收入 =3x1+4x2
引入变量 d2+和 d2-,分别表示年收入超过与低于 10000的数量 。
于是,第 2个目标可以表示为
3x1+4x2-d2++d2-=10000。
管 理 运 筹 学 17
§ 2 目标规划的图解法二,有优先权的目标函数本问题中第一个目标的优先权比第二个目标大 。 即最重要的目标是满足风险不超过 700。 分配给第一个目标较高的优先权 P1,
分配给第二个目标较低的优先权 P2。
针对每一个优先权,应当建立一个单一目标的线性规划模型 。
首先建立具有最高优先权的目标的线性规划模型,求解;然后再按照优先权逐渐降低的顺序分别建立单一目标的线性规划模型,方法是在原来模型的基础上修改目标函数,并把原来模型求解所得的目标最优值作为一个新的约束条件加入到当前模型中,并求解 。
管 理 运 筹 学 18
§ 2 目标规划的数学模型
( 1)目标规划数学模型的形式有:线性模型、非线性模型、
整数模型、交互作用模型等
( 2)一个目标中的两个偏差变量 di-,di+至少一个等于零,偏差变量向量的叉积等于零,d- × d+ =0
( 3)一般目标规划是将多个目标函数写成一个由偏差变量构成的函数求最小值,按多个目标的重要性,确定优先等级,
顺序求最小值
( 4)按决策者的意愿,事先给定所要达到的目标值当期望结果不超过目标值时,目标函数求正偏差变量最小 ;
当期望结果不低于目标值时,目标函数求负偏差变量最小 ;
当期望结果恰好等于目标值时,目标函数求正负偏差变量之和最小
9.2 数学模型管 理 运 筹 学 19
§ 2 目标规划的数学模型
( 5)由目标构成的约束称为目标约束,目标约束具有更大的弹性,允许结果与所制定的目标值存在正或负的偏差,如例 1.1中的 5个等式约束;如果决策者要求结果一定不能有正或负的偏差,
这种约束称为系统约束,如例 1.1的材料约束;
( 6)目标的排序问题。多个目标之间有相互冲突时,决策者首先必须对目标排序。排序的方法有两两比较法、专家评分等方法,构造各目标的权系数,依据权系数的大小确定目标顺序;
( 7)合理的确定目标数。目标规划的目标函数中包含了多个目标,决策者对于具有相同重要性的目标可以合并为一个目标,
如果同一目标中还想分出先后次序,可以赋予不同的权系数,
按系数大小再排序。例如,在例 1.1中要求设备 B的加班时间不超过设备 A的时间,目标函数可以表达为,表示在中先求 最小再求 最小。
54 2dd 54 dd,
5d?4d
管 理 运 筹 学 20
§ 2 目标规划的数学模型
( 8)目标规划的一般模型.设 xj( j=1,2,…,n)为决策变量
)1.4(),,1(0,
)1.4(),,1(0
)1.4(),,1(
)1.4(),,1(),(
)1.4()(m i n
1
1
11
eLldd
dnjx
cLlgddxc
bmibxa
adwdwPz
l
l
j
n
j
llljlj
n
j
ijij
L
l
lkllkl
K
k
k
式中 p k 为第 k 级优先因子,k=1,2,…… K ; wkl-,wkl+,为分别赋予第 l个目标约束的正负偏差变量的权系数; gl为目标的预期目标值,l=1,…L,(4.1b)为系统约束,( 4.1c)为目标约束管 理 运 筹 学 21
§ 2 目标规划的数学模型
【 例 1.2】 某企业集团计划用 1000万元对下属 5个企业进行技术改造,各企业单位的投资额已知,考虑 2种市场需求变化、现有竞争对手、替代品的威胁等影响收益的 4个因素,技术改造完成后预测单位投资收益率 ((单位投资获得利润 /单位投资额)
× 100% )如表 1- 2所示.
集团制定的目标是:
( 1)希望完成总投资额又不超过预算;
( 2)总期望收益率达到总投资的 30%;
( 3)投资风险尽可能最小;
( 4)保证企业 5的投资额占 20%左右.
集团应如何作出投资决策.
管 理 运 筹 学 22
§ 2 目标规划的数学模型企业 1 企业 2 企业 3 企业 4 企业 5
单位投资额 (万元 ) 12 10 15 13 20
单位投资收益率预测
rij
市场需求 1 4.32 5 5.84 5.2 6.56
市场需求 2 3.52 3.04 5.08 4.2 6.24
现有竞争对手 3.16 2.2 3.56 3.28 4.08
替代品的威胁 2.24 3.12 2.6 2.2 3.24
期望 (平均 )收益率% 3.31 3.34 4.27 3.72 5.03
表 1- 2
管 理 运 筹 学 23
§ 2 目标规划的数学模型
【 解 】 设 xj( j=1,2,…,5 )为集团对第 j 个企业投资的单位数.
1 0 0 02013151012 1154321 ddxxxxx
( 1)总投资约束:
( 2)期望利润率约束:
)2013151012(3.0
03.572.327.434.331.3
54321
2254321
xxxxx
ddxxxxx
整理得
097.018.023.034.029.0 2254321 = ddxxxxx
管 理 运 筹 学 24
§ 2 目标规划的数学模型
079.152.167.122.007.1
095.044.071.014.115.0
021.148.081.03.021.0
053.148.157.166.101.1
6654321
5554321
4454321
3354321
ddxxxxx
ddxxxxx
ddxxxxx
ddxxxxx
( 4)企业 5占 20%的投资的目标函数为,约束条件 77min dd
)2013151012(2.020 54321775 xxxxxddx
0166.2324.2 7754321 ddxxxxx即
(3)投资风险约束.投资风险值的大小一般用期望收益率的方差表示,但方差是 x的非线性函数.这里用离差( rij- E(rj))近似表示风险值,例如,集团投资 5个企业后对于市场需求变化第一情形的风险是:
则 4种因素风险最小的目标函数为:,约束条件为
521 )03.556.6()34.35()31.332.4( xxx
6
3
)(m in
i
ii dd
管 理 运 筹 学 25
§ 2 目标规划的数学模型
)()()(m i n 7746
3
322111
ddPddPdPddPZ
i
ii
5,,2,17,,2,10,0
0166.2324.2
079.152.167.122.007.1
095.044.071.014.115.0
021.148.081.03.021.0
053.148.157.166.101.1
097.018.023.034.029.0
1 0 0 02013151012
7754321
6654321
5554321
4454321
3354321
2254321
1154321
jiddx
ddxxxxx
ddxxxxx
ddxxxxx
ddxxxxx
ddxxxxx
ddxxxxx
ddxxxxx
iij;;、
=
根据目标重要性依次写出目标函数,整理后得到投资决策的目标规划数学模型:
管 理 运 筹 学 26
§ 2 目标规划的数学模型
【 例 1.3】 车间计划生产 I,II 两种产品,每种产品均需经过 A、
B两道工序加工.工艺资料如表 4- 3所示.
产品工序 产品甲 产品乙 每天加工能力 (小时 )
A 2 2 120
B 1 2 100
C 2.2 0.8 90
产品售价 (元 /件 ) 50 70
产品利润 (元 /件 ) 10 8
( 1)车间如何安排生产计划,使产值和利润都尽可能高
( 2)如果认为利润比产值重要,怎样决策表 1- 3
管 理 运 筹 学 27
§ 2 目标规划的数学模型
【 解 】 设 x1,x2分别为产品甲和产品乙的日产量,得到线性多目标规划模型:
0
908.02.2
1 0 02
1 2 022
810m a x
7050m a x
21
21
21
21
212
211
xx
xx
xx
xx
xxZ
xxZ
、
管 理 运 筹 学 28
§ 2 目标规划的数学模型
( 1)将模型化为目标规划问题.首先,通过分别求产值最大和利润最大的线性规划最优解.
产值最大的最优解,X(1)=( 20,40),Z1= 3800
利润最大的最优解,X (2) =( 30,30),Z2= 540
目标确定为产值和利润尽可能达到 3800和 540,得到目标规划数学模型:
2,1,0
908.02.2
1 0 02
1 2 022
5 4 0810
3 8 0 07050
m i n
21
21
21
2221
1121
21
jddx
xx
xx
xx
ddxx
ddxx
ddZ
jjj
、、
管 理 运 筹 学 29
§ 2 目标规划的图解法三,图解法
1,针对优先权最高的目标建立线性规划建立线性规划模型如下:
Min d1+
s.t.
20x1+ 50x2≤ 90000
0.5x1 +0.2x2-d1++d1-=700
3x1+4x2-d2++d2-=10000
x1,x2,d1+,d1-≥ 0
管 理 运 筹 学 30
§ 2 目标规划的图解法图 2 图解法步骤 2
0 1000 2000 3000 4000 5000
2000
3000
4000
x1
x2
20x1+ 50x2≤900001000
0.5x1 +0.2x2=700
管 理 运 筹 学 31
§ 2 目标规划的图解法
2,针对优先权次高的目标建立线性规划优先权次高 ( P2) 的目标是总收益超过 10000。
建立线性规划如下:
Min d2-
s.t.
20x1+ 50x2≤ 90000
0.5x1 +0.2x2-d1++d1-=700
3x1+4x2-d2++d2-=10000
d1+= 0
x1,x2,d1+,d1-,d2+,d2-≥ 0
管 理 运 筹 学 32
§ 2 目标规划的图解法
3x1+4x2=10000
图 3 图解法步骤 3
0 1000 2000 3000 4000 5000
2000
3000
4000
x1
x2
20x1+ 50x2≤900001000
0.5x1 +0.2x2=700
d1+>0
d1+= 0
d2-=0
d2->0
(810,1476)
管 理 运 筹 学 33
§ 2 目标规划的图解法目标规划的这种求解方法可以表述如下:
1,确定解的可行区域 。
2,对优先权最高的目标求解,如果找不到能满足该目标的解,
则寻找最接近该目标的解 。
3,对优先权次之的目标进行求解 。 注意:必须保证优先权高的目标不变 。
4,重复第 3步,直至所有优先权的目标求解完。
管 理 运 筹 学 34
§ 2 目标规划的图解法四,目标规划模型的标准化例 6中对两个不同优先权的目标单独建立线性规划进行求解 。 为简便,把它们用一个模型来表达,如下:
Min P1( d1+) +P2( d2-)
s.t.
20x1+ 50x2≤ 90000
0.5x1 +0.2x2-d1++d1-=700
3x1+4x2-d2++d2-=10000
x1,x2,d1+,d1-,d2+,d2-≥0
管 理 运 筹 学 35
§ 2 目标规划的图解法
【 例 】 企业计划生产 I,II 两种产品,这些产品需要使用两种材料,要在两种不同设备上加工.工艺资料如表 4- 4所示.
产品资源 产品甲 产品乙 现有资源材料 I 3 0 12(kg)
材料 II 0 4 14(kg)
设备 A 2 2 12(h)
设备 B 5 3 15(h)
产品利润 (元 /件 ) 20 40
表 4- 4
管 理 运 筹 学 36
§ 2 目标规划的图解法
【 解 】 设 x1,x2分别为产品甲和产品乙的产量,目标规划数学模型为:
企业怎样安排生产计划,尽可能满足下列目标:
(1)力求使利润指标不低于 80元
(2)考虑到市场需求,I,II两种产品的生产量需保持 1:1的比例
(3)设备 A既要求充分利用,又尽可能不加班
(4) 设备 B必要时可以加班,但加班时间尽可能少
(5)材料不能超用。
4333322211 )()mi n dPddPddPdPz (
1
2
1 2 1 1
1 2 2 2
1 2 3 3
1 2 4 4
12
3 12 (1 )
4 16 ( 2)
20 40 80 ( 3 )
0 ( 4)
2 2 12 ( 5 )
5 3 15 ( 6)
,,0 ( 1,,4)
ii
x
x
x x d d
x x d d
x x d d
x x d d
x x d d i
管 理 运 筹 学 37
(2)
(1)
(3)
(4 )
x2
x1
(6)
(5)
o 4 6
4
6
2
2
图 4- 1
A
B
C
1 1 2 2 2 3 3 3 4 4m i n ) ( )z P d P d d P d d P d(
4d?
4d?
1d?
1d?
2d?
3d? 2d
3d?
1
2
1 2 1 1
1 2 2 2
1 2 3 3
1 2 4 4
12
3 12 (1 )
4 16 ( 2)
20 40 80 ( 3 )
0 ( 4)
2 2 12 ( 5 )
5 3 15 ( 6)
,,0 ( 1,,4)
ii
x
x
x x d d
x x d d
x x d d
x x d d
x x d d i
满意解
C(3,3)
1min d
22m in dd
33min dd
满意解 X= (3,3)
管 理 运 筹 学 38
§ 2 目标规划的图解法
(3)
x1
x2
20 40 60 80 100
20
40
60
80
100
(2)
(1)
(4)
1d
1d?2d?3d
2d
3d
4d
4d
1 1 2 2 3 3 3 4
1 2 1 1
1 2 2 2
1 2 3 3
1 2 4 4
12
m in ( ) ( )
1 0 5 4 0 0 (1 )
7 8 5 6 0 ( 2 )
2 2 1 2 0 ( 3 )
2,5 1 0 0 ( 4 )
,0,1,,4
jj
Z P d d P d d P d
x x d d
x x d d
x x d d
x x d d
x x d d j
、,
B
C
满意解是线段 上任意点,端点的解是 B(100/3,80/3),C(60,0).
决策者根据实际情形进行二次选择.
BCA
管 理 运 筹 学 39
§ 2 目标规划的图解法
(3)
x1
x2
20 40 60 80 100
20
40
60
80
100
(2)
(1)
(4)
1d
1d?2d?3d
2d
3d
4d
4d
图 5- 3
4,,1,0,
)4(1005.2
)3(12022
)2(56087
)1(400510
21
4421
3321
2221
1121
jddxx
ddxx
ddxx
ddxx
ddxx
jj
、、
B
C
满意解是点 B,X=(100/3,80/3)
1 1 2 2 3 3 3 4 41m i n ( ) ( )Z P d d P d d P d Pd
A
管 理 运 筹 学 40
(3)
x1
x2
20 40 60 80 100
20
40
60
80
100
(2)
(1)
(4)
1d
1d?2d?3d
2d
3d
4d
4d
4,,1,0,
)4(1005.2
)3(12022
)2(56087
)1(400510
21
4421
3321
2221
1121
jddxx
ddxx
ddxx
ddxx
ddxx
jj
、、
满意解是点 A,X=(20,40)
43322111 )2()(m i n dPddPddPZ
A(20,40)
D(80/9,560/9)
32 2dd
注:线段 DA是第二目标函数的组合,
点 A对应的偏差,d2-=100,d3+ =0
点 D对应的偏差,d2-=0,2d3+ =2× 200/9=400/9
管 理 运 筹 学 41
§ 3 复杂情况下的目标规划例 7,一工艺品厂商手工生产某两种工艺品 A,B,已知生产一件产品 A需要耗费人力 2工时,生产一件产品 B需要耗费人力 3工时 。
A,B产品的单位利润分别为 250元和 125元 。 为了最大效率地利用人力资源,确定生产的首要任务是保证人员高负荷生产,要求每周总耗费人力资源不能低于 600工时,但也不能超过 680工时的极限;次要任务是要求每周的利润超过 70000元;在前两个任务的前提下,为了保证库存需要,要求每周产品 A和 B的产量分别不低于 200和 120件,因为 B产品比 A产品更重要,不妨假设
B完成最低产量 120件的重要性是 A完成 200件的重要性的 1倍 。
试求如何安排生产?
管 理 运 筹 学 42
§ 3 复杂情况下的目标规划解:
本问题中有 3个不同优先权的目标,不妨用 P1,P2,P3表示从高至低的优先权 。
对应 P1有两个目标:每周总耗费人力资源不能低于 600工时,
也不能超过 680工时;
对应 P2有一个目标:每周的利润超过 70000元;
对应 P3有两个目标:每周产品 A和 B的产量分别不低于 200和
120件 。
管 理 运 筹 学 43
§ 3 复杂情况下的目标规划采用简化模式,最终得到目标线性规划如下:
Min P1(d1+)+ P1(d2- )+P2(d3-)+ P3(d4-)+ P3(2d5-)
s.t.
2x1+3x2-d1++d1-=680 对应第 1个目标
2x1+3x2-d2++d2-=600 对应第 2个目标
250x1+125x2-d3-+d3+= 70000 对应第 3个目标
x1-d4++d4-=200 对应第 4个目标
x2-d5++d5-=120 对应第 5个目标
x1,x2,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,d5+,d5-≥ 0
管 理 运 筹 学 44
§ 3 复杂情况下的目标规划使用运筹学软件求解可得:
x1=250; x2=60; d1+=0; d1-=0; d2+=80; d2-=0; d3+=0; d3-=0;
d4+=50; d4-=0; d5+=0; d5-=60,目标函数 d4-+2d5- =120。
可见,目标 1、目标 3和目标 4达到了,但目标 2、目标 5都有一些偏差。
管 理 运 筹 学 45
§ 4 加权目标规划
加权目标规划 是另一种解决多目标决策问题的方法,其基本方法是通过量化的方法分配给每个目标的偏离的严重程度一个罚数权重,然后建立总的目标函数,该目标函数表示的目标是要使每个目标函数与各自目标的加权偏差之和最小,假设所有单个的目标函数及约束条件都符合线性规划的要求,那么,整个问题都可以描述为一个线性规划的问题。
如果在例 7中我们对每周总耗费的人力资源超过 680工时或低于 600工时的每工时罚数权重定为 7;每周利润低于 70000
元时,每元的罚数权重为 5;每周产品 A产量低于 200件时每件罚数权重为 2,而每周产品 B产量低于 120件时每件罚数权重为 4。
管 理 运 筹 学 46
§ 4 加权目标规划
则其目标函数化为:
min7d1++7d2-+5d3-+2d4-+4d5-
这就变成了一个普通的单一目标的线性规划问题
min7d1++7d2-+5d3-+2d4-+4d5-
s.t,2x1+3x2-d1++d1-=680
2x1+3x2-d2-+d2+=680
250x1+125x2-d3-+d3+=70000
x1-d4++d4-=200
x2-d5++d5-=120
x1,x2,d1+,d1-,d2-,d2+,d3+,d3-,d4+,d4-,d5+,d5-≥0 。
管 理 运 筹 学 47
§ 5 目标规划的单纯型法单纯形法求解目标规划可参照第一章的步骤,只是目标规划的检验要按优先级顺序逐级进行,不同的是:
( 1)首先使得检验数中 P1的系数非负,再使得 P2的系数非负,
依次进行;
( 2)当 P1,P2,…,Pk对应的系数全部非负时得到最优解;
( 3)如果 P1,…,Pi行系数非负,而 Pi+1行存在负数,并且负数所在列上面 P1,…,Pi行中存在正数时,得到满意解,计算结束.
管 理 运 筹 学 48
§ 5 目标规划的单纯型法
【 例 4.6】 用单纯形法求解下述目标规划问题
)3,2,1(0,,,
8022
402
502
)(m in
21
3321
2221
1121
32211
iddxx
ddxx
ddxx
ddxx
dPddPz
ii
-
【 解 】 以 d1-,d2-,d3- 为基变量,求出检验数,将检验数中优先因子分离出来,每一优先级做一行,列出初始单纯形表 4-5.
管 理 运 筹 学 49
§ 5 目标规划的单纯型法
Cj 0 0 P1 0 0 P1 P2 0
b
CB 基变 量 x1 x2 d1- d1+ d2- d2+ d3- d3+
P1 d1- 1 [2] 1 - 1 50→
0 d2- 2 1 1 - 1 40
P2 d3- 2 2 1 - 1 80
Cj- Zj
P1 - 1 - 2 1 1
P2 - 2 - 2 1
表 4- 5
管 理 运 筹 学 50
§ 5 目标规划的单纯型法表 4- 5中,P1行中 (- 2)最小,则 x2进基,求最小比值易知 d1- 出基,将第二列主元素化为 1,其余元素化为零,得到表 4- 6.
Cj 0 0 P1 0 0 P1 P2 0 b
CB 基 x1 x2 d1- d1+ d2- d2+ d3- d3+
0 x2 1/2 1 1/2 - 1/2 25
0 d2- [3/2] 1/2 1 - 1 15→
P2 d3- 1 1 1 - 1 30
Cj- Zj P1 1 1P
2 - 1 1 - 1 1
表 4- 6
管 理 运 筹 学 51
§ 5 目标规划的单纯型法表 4- 6中 P1行全部检验数非负,表明第一目标已经得到优化,P2
行存在负数,x1的检验数为- P2<0,选 x1进基(也可以选 d1+进基),则 d3- 出基,迭代得到表 4-7.
Cj 0 0 P1 0 0 P1 P2 0
bC
B 基 x1 x2 d1
- d
1
+ d2- d
2
+ d
3
- d
3
+
0 x2 1 2/3 - 2/3 1/3 20
0 x1 1 [1/3] 2/3 10→
P2 d3- 2/3 2/3 1 - 1 20
Cj- Zj P1 1 1P
2 2/3 -2/3 2/3 -2/3 1
表 4-7
管 理 运 筹 学 52
§ 5 目标规划的单纯型法在表 4-7中,P1行的系数全部非负,P2行存在负数,d1+的检验数- 2/3P2<0,
选 d1+进基,则 x1出基,迭代得到表 4-8.
应当注意,表 4-7中不能选 d2+进基,检验数 P1- 2/3P2应理解为“大于零”,
P1,P2是优先级别的比较,而不是“数”的比较.
Cj→ 0 0 P
1 0 0 P1 P2 0 b
CB 基 x1 x2 d1- d1+ d2- d2+ d3- d3+
0 x2 2 1 1 - 1 40
0 d1+ 3 - 1 1 2 - 2 30
P2 d3- - 2 - 2 2 1 - 1 0
Cj- Zj P1 1 1P
2 2 2 - 2 1
表 4- 8
管 理 运 筹 学 53
§ 5 目标规划的单纯型法表 4-8中 P2行的(- 2)小于零,但(- 2)列上面 P1行存在正数 1,
检验数 P1- 2P2>0,所有检验数非负,得到满意解 X=( 0,40)
【 例 】
4,3,2,1,0,,,;100;60;1402;25001230
5.2m in
21
442
331
2221
1121
23423211
lddxx
ddx
ddx
ddxx
ddxx
dPdPdPdPZ
ll