- 在线时间
- 791 小时
- 最后登录
- 2022-11-28
- 注册时间
- 2017-6-12
- 听众数
- 15
- 收听数
- 0
- 能力
- 120 分
- 体力
- 35386 点
- 威望
- 11 点
- 阅读权限
- 255
- 积分
- 13559
- 相册
- 0
- 日志
- 0
- 记录
- 1
- 帖子
- 621
- 主题
- 542
- 精华
- 10
- 分享
- 0
- 好友
- 225
TA的每日心情 | 开心 2020-11-14 17:15 |
---|
签到天数: 74 天 [LV.6]常住居民II
群组: 2019美赛冲刺课程 群组: 站长地区赛培训 群组: 2019考研数学 桃子老师 群组: 2018教师培训(呼伦贝 群组: 2019考研数学 站长系列 |
1.线性规划的局限性
7 A% b$ F; i( W只能解决一组线性约束条件下,某一目标只能是一个目标的最大或最小值的问题。8 W$ Q2 n+ f( e* [. Z
3 l+ P# O5 Z) G5 V# _( e h4 R: Q 2.实际决策中,衡量方案优劣考虑多个目标. Y3 m1 Q/ r' w+ T2 A5 i: V
这些目标中,有主要的,也有次要的;有最大值的,也有最小值的;有定量的, 也有定性的;有相互补充的,也有相互对立的,LP 则无能为力。) @0 X# Q7 ~" z4 x Y8 |6 N% L
) k7 e! R1 c) y+ Y
3.目标规划(Goal Programming)
+ E1 M3 y* d f& ?美国经济学家查恩斯(A. Charnes)和库柏(W. W. Cooper)在 1961 年出版的《管理模型及线性规划的工业应用》一书中,首先提出的。) {! T: X9 {$ f
% U4 Y e3 h; X9 g1 l4.求解思路
' m0 s/ V5 Y3 P/ W: d(1)加权系数法, I" P0 D( D9 L( i4 L
为每一目标赋一个权系数,把多目标模型转化成单一目标的模型。但困难是要确 定合理的权系数,以反映不同目标之间的重要程度。
) D- m9 U. `' S. y% b$ D4 i0 Z" v* H J
(2)优先等级法 ~) {% N! |* \, |" F
将各目标按其重要程度不同的优先等级,转化为单目标模型。' t: Y/ u3 y4 j5 _( s1 T' I+ `# i: I
# V1 r9 N% s" }
(3)有效解法) b' {8 m2 v2 Q& k6 x- I" x
寻求能够照顾到各个目标,并使决策者感到满意的解。由决策者来确定选取哪一个 解,即得到一个满意解。但有效解的数目太多而难以将其一一求出。
0 o, f, ?* [& B( k4 D) f5 `3 S
5 T3 K: D L) @" ~- `( P8 {2 目标规划的数学模型% t) Q6 j r5 a, f# p" h
为了具体说明目标规划与线性规划在处理问题的方法上的区别,先通过例子来介绍 目标规划的有关概念及数学模型。/ {& p! l7 ^5 o8 r
) E; n" c2 U8 Z0 h5 c) S M% p
例1 某工厂生产 I,II 两种产品,已知有关数据见下表 ,试求获利最大的生产方案。! j( M) V$ v9 u- i% m# \. j# T% X0 @
6 d, [. E/ }/ \$ j7 `7 C# T8 T S/ F( [
9 J: d0 H; b6 b
解 这是一个单目标的规划问题,用线性规划模型表述为:
; p+ b0 \9 Y2 `4 i: y* U! P2 n+ E' {: X
B c w+ N$ N5 ~$ e
- m0 A: m* ~5 S: f }2 _/ e
但实际上工厂在作决策方案时,要考虑市场等一系列其它条件。如
+ T7 H4 g: Y/ p' s& ]+ u' [' m2 i3 a! W
(i)根据市场信息,产品 I 的销售量有下降的趋势,故考虑产品 I 的产量不大于 产品 II。
. o# k* Z1 }6 \- l! m, Z3 X
) }# N, S3 T9 c* P. s M: q(ii)超过计划供应的原材料,需要高价采购,这就使成本增加。
# F! V" F) P- {0 q, f# U# {- _- h( M& ]9 {7 m
(iii)应尽可能充分利用设备,但不希望加班。
7 b6 f* W4 W/ B. J% ` g5 ]7 z" W |/ i5 E4 u
(iv)应尽可能达到并超过计划利润指标 56 元。
+ l0 W4 Q& E& E& w o
p' |6 @) W6 [3 A I' ^这样在考虑产品决策时,便为多目标决策问题。目标规划方法是解决这类决策问题 的方法之一。下面引入与建立目标规划数学模型有关的概念。 # u: \$ U) a2 V$ {( [
3 a }" u2 x- ^# W6 S3 |1 H1. 正、负偏差变量 ) h( `& s- U$ X$ L- _# Z) s0 L
3 A/ N8 `( l$ ]! M% [8 S
3 {; N8 L; Z+ K; u8 b$ E
5 j0 x1 G; u w$ }2 F0 |/ v+ y+ o" }2. 绝对(刚性)约束和目标约束 * s* [) g; v4 a p
) {, K, k) z0 ^3 S7 F7 P1 F. x$ {& ~, ?0 Y
6 n' U1 Z2 k, C( M$ ]( ?( F
3. 优先因子(优先等级)与权系数
; J) M/ ?& i& o% S
! Z% I( ~ P* I/ s+ Q
, L' x% n2 W0 [$ }& g; m; m4 E
* M! Y* ? h% U2 @5 h5 d
$ r' @4 z6 u0 C" R* q, }' k4. 目标规划的目标函数
9 | I2 v% M1 \& f/ @! E
) z) F% m: t3 @, G; o8 m4 V" E* m% b! j* d3 b2 ~3 n/ ] X# N
D* E7 \9 _- x/ M9 u2 |5 f; G对每一个具体目标规划问题,可根据决策者的要求和赋于各目标的优先因子来构造目标 函数,以下用例子说明。 U$ u. f$ F8 w$ `9 z
7 O; a* V( Z/ Q
例 2 : 例 1 的决策者在原材料供应受严格限制的基础上考虑:首先是产品 II 的产 量不低于产品 I 的产量;其次是充分利用设备有效台时,不加班;再次是利润额不小于 56 元。求决策方案。 解 按决策者所要求的,分别赋于这三个目标 优先因子。这问题的数学模型是
9 j4 k# `* y2 _! S
0 s* U* A% }- x- K
9 s+ ~+ m! |! K8 [
5 _( a% w( | c! b* N' H5.目标规划的一般数学模型+ g5 f Y- w# ~7 b; F% x2 O+ l4 o
$ n" k+ D& ^" P
5 L" q0 R& U+ T6 r
9 ]! [0 l4 F5 g; @
9 j4 |) v/ n" S& d0 R+ L; L
建立目标规划的数学模型时,需要确定目标值、优先等级、权系数等,它都具有一 定的主观性和模糊性,可以用专家评定法给以量化。 4 m+ i- k! [# c+ d; m0 d
! T1 \+ K+ g: ~$ @# s* ]3 k
3 求解目标规划的序贯式算法4 X6 z# }1 W- ~5 l, n: p: l3 _5 h
序贯式算法是求解目标规划的一种早期算法,其核心是根据优先级的先后次序, 将目标规划问题分解成一系列的单目标规划问题,然后再依次求解。 " I8 T. B, z; t4 c7 G U; d
: f; }1 }# v1 M
X1 F+ f" z( {) V
Q/ a$ |( |' |% h* Y
( y1 C) E2 F' s" @9 `, i5 W+ }
& h0 H: y' \8 [0 |& Q' o# g W注 此时最优解的概念与线性规划最优解的概念已有所不同,但为方便起见,仍 称为最优解。
* ^2 G! E" X" X% e* J
5 N! [- @' |! F- ?: @8 `5 n例 3 某企业生产甲、乙两种产品,需要用到 A ,B ,C 三种设备,关于产品的赢利 与使用设备的工时及限制如下表所示。问该企业应如何安排生产,才能达到下列目标:( U# j2 u3 G% q
5 v. W, h c! g7 [. a
) {) m: s: Q1 ?- ~
6 F0 {5 ^( i( S(1)力求使利润指标不低于 1500 元;! I# U1 |7 R# i8 u
8 G: k# }3 f8 Z4 u% G. C(2)考虑到市场需求,甲、乙两种产品的产量比应尽量保持 1:2;
' T$ @+ D' Y! K1 Z( y
. O) Y. b& N, Q, }. z& `(3)设备 A为贵重设备,严格禁止超时使用;
0 Y- t6 \# I, E g1 F: V! j2 A* \* L- w: ~; t5 S& Z/ J. `
(4)设备 C 可以适当加班,但要控制;设备B 既要求充分利用,又尽可能不加班。 在重要性上,设备B 是设备C 的 3 倍。7 p3 z8 B! t( ?) x7 _% N8 f
% \" \7 u$ m/ Z; V- X' d4 ?
建立相应的目标规划模型并求解。
" \& S: X( U7 b& y
1 F b* M7 Z9 Q3 I% ~解 设备 A是刚性约束,其余是柔性约束。首先,最重要的指标是企业的利润, 因此,将它的优先级列为第一级;其次,甲、乙两种产品的产量保持 1:2 的比例,列为 第二级;再次,设备 B C, 的工作时间要有所控制,列为第三级。在第三级中,设备B 的 重要性是设备C 的三倍,因此,它们的权重不一样,设备B 前的系数是设备C 前系数 的 3 倍。由此得到相应的目标规划模型。 ' s- v. A K0 x' L& Z
' k1 ` J& B! D# O( r4 Y, t8 K2 @
: f: D! E" H7 G* e1 n7 i
9 P. A$ y+ i: o* A' o, u1 Q: B8 _1 {
序贯算法中每个单目标问题都是一个线性规划问题,可以使用 LINGO 软件进行求 解。 求第一级目标。LINGO 程序如下: ) M) e4 `* i3 g# L
# V0 J- s& s1 S9 `
model: 5 P O% a- h8 A! Y+ M8 D
sets:
5 j; C8 l' J' p+ T6 \: ]7 `# s6 kvariable/1..2/:x; + i- M1 X0 |$ T- \
S_Con_Num/1..4/:g,dplus,dminus; 6 P9 W8 Q+ { q4 y. N+ L
S_con(S_Con_Num,Variable):c; $ L9 F) }5 I* ?3 J: G9 @
endsets
- b6 S) R% |$ w+ ~- P, T" ldata:
$ E" L, T$ P7 m6 Z8 ~2 qg=1500 0 16 15;
n$ E ?- o0 k _# Z" C& Fc=200 300 2 -1 4 0 0 5; # J. s L% e! S0 t- g
enddata * |& p( }0 q$ L+ c# |6 w+ g
min=dminus(1); & N8 {1 c( y7 f& L8 ?, f7 Q. ]
2*x(1)+2*x(2)<12;
# Z3 [4 R9 ?1 Z. u. F6 o& g! _5 t4 N@for(S_Con_Num(i)sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i)); + ~$ T" K3 ~ W; d" {
end
! m* u \( E D
, D" O) L3 t. t" i9 a' m; L求得 dminus(1)=0,即目标函数的最优值为 0,第一级偏差为 0。 求第二级目标,LINGO 程序如下: model: 8 O4 Z4 w. o5 }9 T4 C% x5 r" c+ g( z
sets: % V! a" z8 T7 x0 X, g; D3 T' c6 @
variable/1..2/:x;
% m% L7 ~8 N' @ I1 M3 wS_Con_Num/1..4/:g,dplus,dminus; 9 |+ ]2 Z$ R! ~5 U- \! n+ M
S_con(S_Con_Num,Variable):c; / F' P7 v) ?2 j2 O9 _, P" N! H) a# r) j
endsets
) ]5 e; _! X% u6 O7 }+ Q) D2 qdata:
8 j: m% y( }3 Q f# Wg=1500 0 16 15; 6 p- C2 A" ?* o
c=200 300 2 -1 4 0 0 5;
' T# w0 j) Y: B# { A! Denddata
- ^ N6 y9 o4 `min=dplus(2)+dminus(2); !二级目标函数;
* [, h- \3 z+ l- L! s2*x(1)+2*x(2)<12; 9 T3 {+ V' F0 Q, p
@for(S_Con_Num(i)sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i)); 2 z/ ]: A7 o% p8 |4 X
dminus(1)=0;!一级目标约束;
t5 \" i$ `$ b" \* ?( I+ B7 j" l@for(variablegin(x));
& ?! Z: \' F1 f8 o" c% D# Qend
9 M' o+ r4 p, e6 G' b4 c) v% H8 W* w4 j7 C4 w0 m6 j! i
求得目标函数的最优值为 0,即第二级的偏差仍为 0。 求第三级目标,LINGO 程序如下: 7 }/ V& [4 p( b5 p N
X6 m7 O0 N/ cmodel: 1 G% c- @5 B+ b
sets:
% |" \" M- d4 k3 H6 q6 T; Rvariable/1..2/:x; $ D3 Q; U( n$ A
S_Con_Num/1..4/:g,dplus,dminus;
3 C, Q9 C6 q# x% C, OS_con(S_Con_Num,Variable):c;
( K S$ y+ z" `' gendsets
' N# K; k/ N) Ndata:
" n* X6 K, ]0 u7 h: j0 j5 Zg=1500 0 16 15; 5 p; I5 x, i% H4 X6 r
c=200 300 2 -1 4 0 0 5;
! Y, I1 A0 n/ F; lenddata # i) I8 R2 p% F, v D$ s7 ]' X
min=3*dplus(3)+3*dminus(3)+dplus(4); !三级目标函数; ( G( W1 `- [, z8 ]
2*x(1)+2*x(2)<12;
m t6 U* L+ T! } L& | @for(S_Con_Num(i)sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i));
2 k; e! P/ g- ?' U. pdminus(1)=0;!一级目标约束; 2 u$ ?; J8 } Z/ ]+ L
dplus(2)+dminus(2)=0;!二级目标约束; , F) J" U# g- I6 s; |2 K+ g
end6 O1 X& Y3 l# [* b) T8 }
6 g; E- D( i! k8 Q& ]
目标函数的最优值为29,即第三级偏差为29。
2 G; }8 j. m6 D7 a2 D, f) E1 v0 ~1 v6 a7 U' H( w4 e5 F$ A
分析计算结果, ,因此,目标规划的最优解为 , 最优利润为1600。( @! i5 f# C: t! x# @: T7 w. o0 _
& @) d) V0 S- R4 t
上述过程虽然给出了目标规划问题的最优解,但需要连续编几个程序,这样在使 用时不方便,下面用 LINGO 软件,编写一个通用的程序,在程序中用到数据段未知数 据的编程方法。
# C( A- `. D$ e' a% V; ?
+ G7 B8 _8 x, d例 4(续例 3) 按照序贯式算法,编写求解例 3 的通用 LINGO 程序。5 l% M; D. L0 ]/ ~9 \9 F
2 s5 A, _# s9 }) f& O8 n8 Z& i
model:
3 p: m6 X. Y# k9 t( p5 i4 u- n) ^sets:
6 u" ?2 \) f* {5 Flevel/1..3/:p,z,goal;
: G/ R8 o, Y3 l( ivariable/1..2/:x; / I" ]/ n+ H; I
h_con_num/1..1/:b;
- @) }2 ^# Y; w4 K' R2 ws_con_num/1..4/:g,dplus,dminus; ; O5 R/ G5 O9 e/ Y
h_con(h_con_num,variable):a;
+ S7 X$ f' B& ?' e$ Hs_con(s_con_num,variable):c;
; `7 J4 w% E1 x* yobj(level,s_con_num)/1 1,2 2,3 3,3 4/:wplus,wminus;
. q6 W4 f ^" \2 Uendsets . a! H: c; B7 x: T/ P
data: ; L9 O+ W# p/ Q G8 u: H7 f
ctr=?;
: v9 J# Y4 x ~4 p1 mgoal=? ? 0; 1 f6 W1 ~3 c9 m' W' u; y+ c& `) j& ~
b=12;
, E+ | K1 _1 k' r8 Og=1500 0 16 15;
' p: g5 x3 \0 H2 l; l: Ma=2 2;
6 y) ^! P# J: l; Ec=200 300 2 -1 4 0 0 5; ; k) z5 i7 ?* C- A$ G7 T6 J
wplus=0 1 3 1;
% d' H) |: F& X' l! }, \$ \' t2 Nwminus=1 1 3 0;
I, X/ ~; K( m- Fenddata & B: s; _1 G& Z# X1 O+ s* D
min=@sum(level:p*z); - q3 P, P4 I" k5 U
p(ctr)=1; - G @- T0 v( P# r- \7 N" n9 V) }
@for(level(i)|i#ne#ctr:p(i)=0);
! L/ r% |& f! ^% _: y) y@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))); ' B; X5 H! y0 f8 Z9 q1 W
end % t( b8 j) I6 |: f# X
+ m; {' t) S6 p: _7 P7 W+ D7 N: `3 C' @9 u; K, @* B
- ?- ?" y6 [2 d; N( H5 Y" N# U
2 U9 V/ y5 N& S9 d; @ X
6 ?7 @1 s, C: Q* z. U4 多标规划的 Matlab 解法 多目标规划可以归结为 9 Y5 `- ^, p" ]' ?6 u8 j! i6 }
( W, h) j: g. w! e% S
+ }/ o+ B, P/ ~( H
[x,fval]= fgoalattain('fun',x0,goal,weight)
4 X) k: N% I! u& a+ l5 q) Z[x,fval]= fgoalattain('fun',x0,goal,weight,A,b) 5 a0 ]* Q) U: K: S
[x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq) % Q# a( t; G2 i
[x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)
5 t j& I3 j" o5 n- ]: N
4 v1 h+ ?4 B0 k- S8 r8 x5 H1 \ p
要完整掌握其用法,请用 help fgoalattain 或 type fgoalattain 查询相关的帮助。
8 `; p8 b- T t 例 5 求解多目标线性规划问题 ; n/ D6 p" G1 l3 u; w& H
; O, [) k9 x( t
1 q) i! r p( ^# C
6 `: B8 \% ^: i1 R# w! B4 F
解 (i)编写 M 函数 Fun.m: / i9 _' v- O8 F$ H
$ Z' U! p) m4 O' x6 T
function F=Fun(x); ! t# Q1 W4 ~/ L- H8 X2 N1 A3 Y
5 o7 D z# w. {1 g! u0 r/ Q& uF(1)=-100*x(1)-90*x(2)-80*x(2)-70*x(4);
h/ k4 w$ f$ v6 q N7 t: A) p% X: N6 }8 F: Y, B
F(2)=3*x(2)+2*x(4);
. x( q5 p8 q1 r# F# F, I) k6 E
(ii)编写 M 文件
* y1 R' a5 n5 s# K, }, }" }3 q& s- E! v, B
a=[-1 -1 0 0 $ T3 w1 \. n7 w9 k. W1 J1 Q
0 0 -1 -1 " E# G& h8 h$ m( t8 x& p+ V
3 0 2 0
. w0 V0 `2 p1 A- ^. H 0 3 0 2]; : K6 K8 _7 t* _! g( V$ j
b=[-30 -30 120 48]';
6 C& d x# Z; D+ Gc1=[-100 -90 -80 -70];
- _6 M7 [+ T9 E/ `c2=[0 3 0 2];
u5 M9 N$ f9 O' M[x1,g1]=linprog(c1,a,b,[],[],zeros(4,1)) %求第一个目标函数的目标值
/ h3 y4 L' p# v7 N9 w' H[x2,g2]=linprog(c2,a,b,[],[],zeros(4,1)) %求第二个目标函数的目标值 * ]0 x m4 M+ q' D
g3=[g1;g2] %目标goal的值 2 H3 F' E! B5 c1 t
[x,fval]=fgoalattain('Fun',rand(4,1),g3,abs(g3),a,b,[],[],zeros(4 ,1)) 1 s( [& D2 z& L6 g! W/ B
%这里权重weight=目标goal的绝对值 6 o* @. c2 \3 g/ f5 k, T
( b9 D0 D6 Z" C* ?就可求得问题的解。 习题
- Q- C: ~+ S. j v
! D& o( d) h% Q# f0 G* x0 ?$ X; n4 S0 `* D
————————————————
G* V) h, n# w* f+ h" t; t- @! X版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
- g$ y* t( A8 y' S! m原文链接:https://blog.csdn.net/qq_29831163/article/details/89488932
/ \" R0 x- E' @4 i9 A1 {: T' h
% x8 I0 u; D4 t8 U$ B
5 R. n [) W7 _ |
zan
|