- 在线时间
- 791 小时
- 最后登录
- 2022-11-28
- 注册时间
- 2017-6-12
- 听众数
- 15
- 收听数
- 0
- 能力
- 120 分
- 体力
- 35400 点
- 威望
- 11 点
- 阅读权限
- 255
- 积分
- 13563
- 相册
- 0
- 日志
- 0
- 记录
- 1
- 帖子
- 621
- 主题
- 542
- 精华
- 10
- 分享
- 0
- 好友
- 225
TA的每日心情 | 开心 2020-11-14 17:15 |
---|
签到天数: 74 天 [LV.6]常住居民II
群组: 2019美赛冲刺课程 群组: 站长地区赛培训 群组: 2019考研数学 桃子老师 群组: 2018教师培训(呼伦贝 群组: 2019考研数学 站长系列 |
1.线性规划的局限性
) l2 c9 i! O* ]只能解决一组线性约束条件下,某一目标只能是一个目标的最大或最小值的问题。3 u: E/ d1 q2 x3 c9 i
9 H/ Q/ z& A8 Y/ w
2.实际决策中,衡量方案优劣考虑多个目标! O! |* x! P) [, N
这些目标中,有主要的,也有次要的;有最大值的,也有最小值的;有定量的, 也有定性的;有相互补充的,也有相互对立的,LP 则无能为力。
@7 S5 m4 i& V% ?3 D: b
5 k6 R x0 E6 ^" J2 g; D* [3.目标规划(Goal Programming)
+ T: @# J8 n( F* S$ u8 I美国经济学家查恩斯(A. Charnes)和库柏(W. W. Cooper)在 1961 年出版的《管理模型及线性规划的工业应用》一书中,首先提出的。
0 Q1 R/ r5 {1 N( P* i& }8 A7 F5 ]; C$ [
4.求解思路
2 y5 l6 F1 o6 W) ~ |' z, m(1)加权系数法
; {; ?/ A: L5 q* N为每一目标赋一个权系数,把多目标模型转化成单一目标的模型。但困难是要确 定合理的权系数,以反映不同目标之间的重要程度。) Z5 p1 T8 @( `2 y/ F. D' q8 z% \2 N$ @
, V$ x( g3 ]9 [) D) x3 n+ v- b* j(2)优先等级法
% y+ a$ ^2 [3 d) u' t将各目标按其重要程度不同的优先等级,转化为单目标模型。
! y# A8 U. z' E8 K+ v( A
) u L/ T4 c& D9 z! N6 w(3)有效解法; G# i. p" c: u4 R! B1 }
寻求能够照顾到各个目标,并使决策者感到满意的解。由决策者来确定选取哪一个 解,即得到一个满意解。但有效解的数目太多而难以将其一一求出。 5 S- z. l! \5 J+ Y
3 v$ h7 R9 o8 {- \6 ?
2 目标规划的数学模型- u- W. Y' v- x' V2 l U6 S
为了具体说明目标规划与线性规划在处理问题的方法上的区别,先通过例子来介绍 目标规划的有关概念及数学模型。! b4 {; F8 t t: Q
9 R4 p5 ~- X. N# e: F2 d例1 某工厂生产 I,II 两种产品,已知有关数据见下表 ,试求获利最大的生产方案。
' n6 _: G% K+ \$ s. _& E* V2 U$ E, G: I% v3 Z. P) r4 X3 ]5 X$ z
+ i* s* s/ h/ P4 T2 E
2 H& F% Q& x0 X. Q' h7 v解 这是一个单目标的规划问题,用线性规划模型表述为: ) u! |/ z! l9 V3 c
7 P4 j* ]; d0 ^' s6 @* V
/ h g& z s" @$ H
/ `3 O0 V V9 ^/ Z% Z. @, T但实际上工厂在作决策方案时,要考虑市场等一系列其它条件。如, @" g' J) i: v [: D; _
, m) e) K9 u1 Z: z0 j3 m(i)根据市场信息,产品 I 的销售量有下降的趋势,故考虑产品 I 的产量不大于 产品 II。
% L8 H2 l" x9 j$ Y, \( r" W/ H! G1 |& W* L& o4 ^0 n
(ii)超过计划供应的原材料,需要高价采购,这就使成本增加。; {5 W9 c1 p B# c% l3 P' h
' Y( E5 @1 ]% K4 U+ D! K
(iii)应尽可能充分利用设备,但不希望加班。
, l+ m1 E, e$ q8 i( J* u f) [) z' K( C
(iv)应尽可能达到并超过计划利润指标 56 元。
) ]0 } E: A4 C' L( R1 T7 n7 [: S& ^& n# E
这样在考虑产品决策时,便为多目标决策问题。目标规划方法是解决这类决策问题 的方法之一。下面引入与建立目标规划数学模型有关的概念。 # [- {7 l: v- y
; K: {( C" ?: k* r2 ^+ P( g" B9 G
1. 正、负偏差变量 : a$ y6 o/ p* g5 f( s
8 c9 x7 l: J% A) \: w# x! U# C F' |% F9 n" R) P
& [2 H! n6 K/ X% G N
2. 绝对(刚性)约束和目标约束
, p# Y9 h+ r& P) o9 Y; k: W4 q9 e- v* T3 `$ \ a v
! y$ M! S, Z! | N( q8 {+ S* p. z- N0 a0 [( o* o4 ^
3. 优先因子(优先等级)与权系数 $ ^; l. _* C: G* r+ s1 K& D
7 v" }9 D0 W, P3 p# f4 d
. c) S; [4 m2 B3 s& t# O! u7 `8 Q
! \* R3 ? Z, F
4. 目标规划的目标函数
3 X7 C$ y6 j1 r" _. x K4 k$ m" r+ y1 N
2 C2 S) v% z) Y7 E# M
. k, ~1 U( p7 g
对每一个具体目标规划问题,可根据决策者的要求和赋于各目标的优先因子来构造目标 函数,以下用例子说明。
/ D# B" j' [. }, q5 t
& ~# E: P2 O5 m6 s9 Z6 Y g例 2 : 例 1 的决策者在原材料供应受严格限制的基础上考虑:首先是产品 II 的产 量不低于产品 I 的产量;其次是充分利用设备有效台时,不加班;再次是利润额不小于 56 元。求决策方案。 解 按决策者所要求的,分别赋于这三个目标 优先因子。这问题的数学模型是 1 u2 J+ [/ F& l1 W% ~7 P
' D* X* {8 C/ r
$ m. _+ ` u' s8 O5 C0 S5 |/ B4 q3 M
8 c: i5 z+ m# P3 B# Z6 I: J D5.目标规划的一般数学模型
! ]: n# C9 x8 M; X3 ]1 }. i5 F* W8 {3 Y/ ^( b8 s& [
6 g. M1 Z: z: ]: _. X& W t& H) v
8 ^, T' D6 {: Y& i7 A建立目标规划的数学模型时,需要确定目标值、优先等级、权系数等,它都具有一 定的主观性和模糊性,可以用专家评定法给以量化。 : t& \# D7 g8 J2 U3 J; {1 \
7 g, N/ g7 Z% }. @3 求解目标规划的序贯式算法1 v& n! F5 o! Z5 A, L! h# ^- C
序贯式算法是求解目标规划的一种早期算法,其核心是根据优先级的先后次序, 将目标规划问题分解成一系列的单目标规划问题,然后再依次求解。 / q$ o6 I1 c1 l8 R# T' K, c, P" F
( H9 k. p' [. c3 b. z: x& H* S
% K0 R" u) v1 j" [8 {- j" o0 L+ W& u- n
: f: v$ ~* g4 g9 P- J# G! ~
% J$ d; Y+ f7 U- S# F2 W5 V( x, r
注 此时最优解的概念与线性规划最优解的概念已有所不同,但为方便起见,仍 称为最优解。 $ o) Y! G. Y+ e8 C& l; c( f8 o% j
) B$ i) k" r. O% t, @; K L. @$ R9 H. A
例 3 某企业生产甲、乙两种产品,需要用到 A ,B ,C 三种设备,关于产品的赢利 与使用设备的工时及限制如下表所示。问该企业应如何安排生产,才能达到下列目标:! d9 e9 r' Y' h6 Z: y! L
) a- ], t8 z1 N5 L O/ |
2 u' W( N+ [0 G4 S* B2 b: ^ R" z( f) K* y Y
(1)力求使利润指标不低于 1500 元;7 @$ Q5 `+ w- ^! H5 |- \
5 x: S( S2 W I8 N C( E
(2)考虑到市场需求,甲、乙两种产品的产量比应尽量保持 1:2;1 j( t; L- R. k+ O9 ~3 L
. l* U6 u3 h3 ]& i1 Q" Q(3)设备 A为贵重设备,严格禁止超时使用;
& l! [5 b G' n" l8 b0 B
2 b0 `* J+ E: g$ W! K' ](4)设备 C 可以适当加班,但要控制;设备B 既要求充分利用,又尽可能不加班。 在重要性上,设备B 是设备C 的 3 倍。
i2 ?; L1 ]+ W5 S. G6 y$ o7 j# y- n
7 G5 h3 y, e( |* t; w1 V/ S% |, o# O建立相应的目标规划模型并求解。* r+ L5 T3 [2 A
/ m1 x2 W/ Z( G/ s+ j解 设备 A是刚性约束,其余是柔性约束。首先,最重要的指标是企业的利润, 因此,将它的优先级列为第一级;其次,甲、乙两种产品的产量保持 1:2 的比例,列为 第二级;再次,设备 B C, 的工作时间要有所控制,列为第三级。在第三级中,设备B 的 重要性是设备C 的三倍,因此,它们的权重不一样,设备B 前的系数是设备C 前系数 的 3 倍。由此得到相应的目标规划模型。
* a& F# n7 |* Y: D/ i! Y$ H! K* U
# @* n6 [( @- U# c, c0 X
4 H! U* E# B; m' C9 M+ f A2 {% G- t0 E. O, V; k9 s, L
序贯算法中每个单目标问题都是一个线性规划问题,可以使用 LINGO 软件进行求 解。 求第一级目标。LINGO 程序如下:
: n$ o, t7 R/ f! o9 Y9 ^( k5 u5 {- h' Z, q
model: " O5 R( F- k/ X
sets: 8 \+ I) w0 g) W& ^- b1 L# N
variable/1..2/:x; ) ?3 P5 d* Z! E9 t3 E$ ^9 m( t# V
S_Con_Num/1..4/:g,dplus,dminus;
6 P- s/ t3 {; E1 AS_con(S_Con_Num,Variable):c; 8 V Z N* h% u* U; L
endsets " Y3 o+ \ Y' I& g
data:
# P8 g6 e% ~: h( Og=1500 0 16 15;
* U7 g4 R( S+ Sc=200 300 2 -1 4 0 0 5; & ^5 P0 j: r; B$ x
enddata
6 j2 `0 s2 o* u3 F# y" rmin=dminus(1); $ ~2 O L* [4 b; m; w1 J X3 l4 f
2*x(1)+2*x(2)<12;
" P, d4 X0 J. E: E! a@for(S_Con_Num(i)sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i));
/ W t# E/ u @end2 S" n6 M7 z6 G( E, K, Z8 @# @) @
0 I) y% w+ P; [$ ~) A& ~& `) W求得 dminus(1)=0,即目标函数的最优值为 0,第一级偏差为 0。 求第二级目标,LINGO 程序如下: model:
2 A# t4 {* g# R" Z+ ssets:
) r# r1 u U ], V- v* ~variable/1..2/:x; ) s1 n2 M( u1 e/ f8 c! J& U: Q
S_Con_Num/1..4/:g,dplus,dminus; - }6 g! b6 ]+ ^, d; |% v+ b
S_con(S_Con_Num,Variable):c; , ~/ R x8 y* f( W
endsets
# a/ o/ c+ e6 {data: 6 f W1 w" l/ T1 K$ @; g6 S
g=1500 0 16 15; 4 ~* P y; K7 f
c=200 300 2 -1 4 0 0 5;
1 b) B5 f1 d: R+ V6 S# Menddata
, l1 i6 `+ p2 z! b" [min=dplus(2)+dminus(2); !二级目标函数;
! J8 [ u" X; `8 E/ g2*x(1)+2*x(2)<12;
3 t, B q. a X) L- l: C' a@for(S_Con_Num(i)sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i));
: l# I( @7 a, W8 `6 r6 Gdminus(1)=0;!一级目标约束; * [* i+ P4 t$ p
@for(variablegin(x));
! _4 u- d7 m) r; H5 q* U" Vend
1 s5 y6 [, x% A
& `, }0 c) J+ w9 {求得目标函数的最优值为 0,即第二级的偏差仍为 0。 求第三级目标,LINGO 程序如下: " m0 b4 e1 y. w
r O' n5 |0 ~# p, i1 jmodel:
: [3 Z1 B% X, A# T0 `2 Z. N' jsets:
5 ]1 Y$ ^) m a& mvariable/1..2/:x;
! X& G A& q9 r8 [. pS_Con_Num/1..4/:g,dplus,dminus; 1 L' s2 C8 D7 k) {$ U
S_con(S_Con_Num,Variable):c;
w0 u! |. \* }0 [& kendsets
1 O9 T& I: m. edata: 5 a* F" v: i( g7 W! A& i k- Q
g=1500 0 16 15;
) N! p- {; T+ v- h i% Uc=200 300 2 -1 4 0 0 5;
7 w/ G3 U8 X t1 k7 }4 U0 `: Jenddata 1 e7 \: `4 `' [8 g3 w& z
min=3*dplus(3)+3*dminus(3)+dplus(4); !三级目标函数; 6 U3 U% T& w; u4 M: b
2*x(1)+2*x(2)<12;
. ^; c6 u2 p" K3 L! q# K1 L @for(S_Con_Num(i)sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i));
! W, ]7 k: n9 c9 Kdminus(1)=0;!一级目标约束;
~# F( d3 t( u, z, P/ x; gdplus(2)+dminus(2)=0;!二级目标约束;
7 {: O! H1 Q/ [8 o6 O; yend
% V) a" b/ I% K6 @" D0 I0 }; a* b; `, w5 [) n; D. X# @
目标函数的最优值为29,即第三级偏差为29。
8 r- @! O: F1 J
6 q* |" P1 g% L8 K$ q8 D分析计算结果, ,因此,目标规划的最优解为 , 最优利润为1600。
4 s+ k% U& M) B N I8 c) H; |2 ?5 [! r- w8 M3 J+ a. z0 O
上述过程虽然给出了目标规划问题的最优解,但需要连续编几个程序,这样在使 用时不方便,下面用 LINGO 软件,编写一个通用的程序,在程序中用到数据段未知数 据的编程方法。7 J* P; t8 X4 K1 k6 J- _+ ]
{; S7 o3 v! x1 o" W6 ~4 |例 4(续例 3) 按照序贯式算法,编写求解例 3 的通用 LINGO 程序。
% n8 a, A% R# K% h1 O. K
B% d B: X- g( K I& kmodel: 5 V( m5 ]6 n7 d
sets: 1 Q/ u5 B, I$ z) @2 J I5 y* u8 m y
level/1..3/:p,z,goal;
* M$ s; |/ h2 d1 }' u5 ~variable/1..2/:x; 1 p0 ^& m9 _* f _% Y$ }/ h8 d
h_con_num/1..1/:b;
' }4 g' i( X$ S) [8 t0 js_con_num/1..4/:g,dplus,dminus; ) J. S3 M- q3 m0 v7 U, ]* f" r* |
h_con(h_con_num,variable):a; : O% i% S9 i* l- ^% J: w
s_con(s_con_num,variable):c; 1 t# q7 ^7 {7 O
obj(level,s_con_num)/1 1,2 2,3 3,3 4/:wplus,wminus; 5 a- G7 h1 F* v7 W* x- K
endsets
2 m5 ~8 c, q) j! y& z5 }data: # ~; D* U" H: K1 p( L' O) t
ctr=?; 8 ^" i+ W4 G7 @
goal=? ? 0;
j, V$ O e( D! j sb=12;
1 b) E4 J0 N( i/ u# C' [g=1500 0 16 15; + y% A0 `* K1 b# Y4 u
a=2 2; , @3 ^$ w: C' H& L I6 N, E
c=200 300 2 -1 4 0 0 5; 5 {7 a7 y- k/ T: s
wplus=0 1 3 1;
- V8 l) p$ O; o8 _wminus=1 1 3 0;
5 i- }: m# K% \; ~: uenddata
! S9 M9 s8 v- C, ~6 Imin=@sum(level:p*z); ; x# ~$ O l3 I, F4 y
p(ctr)=1; % T/ Y' J7 I6 o/ c7 D1 w
@for(level(i)|i#ne#ctr:p(i)=0); : }( t1 g5 s6 E7 ~; O
@for(level(i):z(i)=@sum(obj(i,j):wplus(i,j)*dplus(j)+wminus(i,j)* dminus(j))); @for(h_con_num(i)sum(variable(j):a(i,j)*x(j))<b(i)); @for(s_con_num(i)sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i)); @for(level(i)|i #lt# @size(level)bnd(0,z(i),goal(i)));
0 \# G8 t0 W( v+ h7 k$ |0 n/ xend U7 T% P8 _# L _5 e L$ o9 M) u
* J5 ^9 {( y" b0 S" R
9 v" M( j' o( W- T; f5 `4 n9 G2 A1 H2 C! J3 C$ Z0 {( z
$ }7 S0 e6 l3 M; j/ Q* d7 d6 L+ Z) A( K0 U# k# D; b
4 多标规划的 Matlab 解法 多目标规划可以归结为
) W. b6 C0 x: W
' V: j, X5 B; b5 d4 L& d4 [# N
: T, x7 y7 L# e+ F& H( N[x,fval]= fgoalattain('fun',x0,goal,weight)
. i9 d$ B4 Z2 p' X, a[x,fval]= fgoalattain('fun',x0,goal,weight,A,b)
) f2 @& j. Q$ E8 g[x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq) - F$ B- k) b5 J& i) F% e
[x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) ( J+ k) I9 G7 x; T; v0 w1 `
0 B$ Y5 J1 f/ v0 y8 T# t6 p# l+ \
要完整掌握其用法,请用 help fgoalattain 或 type fgoalattain 查询相关的帮助。9 U' ]6 _0 m; L+ J9 G8 L5 f+ v& A
例 5 求解多目标线性规划问题
+ n' b6 n' H5 E
! ]# o8 @+ O( v, l# k. k- a1 E3 C( w+ d* L" R7 j" G
8 C+ s0 i% ^( k5 _+ u$ b7 t# T& X4 `' Q解 (i)编写 M 函数 Fun.m: ( w. f0 W1 E" K
* @, ]! b1 b3 X" s
function F=Fun(x);
4 s: x1 f1 B( r) n" |6 }6 J$ c" y# E5 @/ A% l6 ?
F(1)=-100*x(1)-90*x(2)-80*x(2)-70*x(4); 3 y R A3 t2 Q6 I9 ~3 [& F, j
9 H2 ^: \: ~) Q+ D+ G* I" _( lF(2)=3*x(2)+2*x(4); : ~1 e- D0 y' M, V7 X% Y/ C
; S* ^2 m, w$ n9 g4 ?+ ^(ii)编写 M 文件 " J4 k3 p+ Z2 `3 |* R0 g
7 h* m" R r. B0 `, _& e
a=[-1 -1 0 0
5 p# }+ J6 s% a; {5 d/ P+ D8 I 0 0 -1 -1
3 D+ o( ~# r3 l; r5 H n3 ? O5 s 3 0 2 0 " v W- x0 s( B$ P6 g* U4 D
0 3 0 2];
/ O0 O8 U# A* Y/ A2 C, Ub=[-30 -30 120 48]';
9 t, k7 p/ J" T7 k3 ic1=[-100 -90 -80 -70];
# F" @8 D' u9 Q8 v" Lc2=[0 3 0 2];
) b" P9 D) I L3 K3 @[x1,g1]=linprog(c1,a,b,[],[],zeros(4,1)) %求第一个目标函数的目标值 # I' a* M- t; }/ l0 b+ h
[x2,g2]=linprog(c2,a,b,[],[],zeros(4,1)) %求第二个目标函数的目标值
5 P# b9 }" o: b& N( \. l7 x/ a! ag3=[g1;g2] %目标goal的值 M% t7 }+ ?+ I
[x,fval]=fgoalattain('Fun',rand(4,1),g3,abs(g3),a,b,[],[],zeros(4 ,1))
+ m( I) a0 P8 u1 K8 ~5 B%这里权重weight=目标goal的绝对值
/ {7 H( X8 ^% G; i9 s0 Y9 e! P) y' L. N: m- C) x, \
就可求得问题的解。 习题' r7 A/ \! `/ i& R
7 i% Z, c2 _5 \$ ^' U1 A
; U, x% h/ b5 P& A————————————————
$ k9 e0 Z3 ]: c$ q8 t版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。3 f% G. d2 M3 z) B! ~- X
原文链接:https://blog.csdn.net/qq_29831163/article/details/89488932
4 e" h# G4 {2 B3 b
+ ~$ U) y% D: Q- g, w% [4 ?$ a' k q+ S
|
zan
|