- 在线时间
- 791 小时
- 最后登录
- 2022-11-28
- 注册时间
- 2017-6-12
- 听众数
- 15
- 收听数
- 0
- 能力
- 120 分
- 体力
- 36395 点
- 威望
- 11 点
- 阅读权限
- 255
- 积分
- 13879
- 相册
- 0
- 日志
- 0
- 记录
- 1
- 帖子
- 616
- 主题
- 542
- 精华
- 12
- 分享
- 0
- 好友
- 225
TA的每日心情 | 开心 2020-11-14 17:15 |
|---|
签到天数: 74 天 [LV.6]常住居民II
 群组: 2019美赛冲刺课程 群组: 站长地区赛培训 群组: 2019考研数学 桃子老师 群组: 2018教师培训(呼伦贝 群组: 2019考研数学 站长系列 |
1.线性规划的局限性8 ?2 I$ a' x$ i
只能解决一组线性约束条件下,某一目标只能是一个目标的最大或最小值的问题。
" B7 P1 p m6 ^- w
$ G. Z) o% d1 {( _ 2.实际决策中,衡量方案优劣考虑多个目标
. c# i/ }: U+ i这些目标中,有主要的,也有次要的;有最大值的,也有最小值的;有定量的, 也有定性的;有相互补充的,也有相互对立的,LP 则无能为力。
5 t9 r! ?8 k) L$ U9 g% W; q! l& G+ w1 n
3.目标规划(Goal Programming)( K0 u- I% {* l* ]
美国经济学家查恩斯(A. Charnes)和库柏(W. W. Cooper)在 1961 年出版的《管理模型及线性规划的工业应用》一书中,首先提出的。7 |5 \2 W$ \- E& `5 L, w* c
, \9 e. D" ]3 X) e4.求解思路
) ?- Z% o# \* s: Z. P S/ f(1)加权系数法# @; J1 U3 V6 P" _6 y% ^
为每一目标赋一个权系数,把多目标模型转化成单一目标的模型。但困难是要确 定合理的权系数,以反映不同目标之间的重要程度。9 x3 W6 W. C4 ^& I
5 w" H2 P8 `8 p+ {# t$ z
(2)优先等级法
; e4 Q' ^ q- Z将各目标按其重要程度不同的优先等级,转化为单目标模型。( l$ m. q8 L! {' n, u5 w
& U# `" v" t9 m5 s8 ]) S0 o9 v$ B; w
(3)有效解法
, x% ]$ N6 I. P/ L) f寻求能够照顾到各个目标,并使决策者感到满意的解。由决策者来确定选取哪一个 解,即得到一个满意解。但有效解的数目太多而难以将其一一求出。 ! `4 |' Y) i q) E8 _+ a& a6 i$ C
c: O% ^9 Y- @! K5 U4 ?2 目标规划的数学模型8 V6 x4 ]" |8 K4 S4 h
为了具体说明目标规划与线性规划在处理问题的方法上的区别,先通过例子来介绍 目标规划的有关概念及数学模型。
3 C! G2 o- S% x4 j/ S7 X1 K# ?/ x( Q
例1 某工厂生产 I,II 两种产品,已知有关数据见下表 ,试求获利最大的生产方案。
' F7 I8 U$ ^% W E: z- C( ]& |; V- S6 W9 Y$ p$ P" |+ l5 C
![]()
2 q. A; u' I: W% R; c' ? {( K. a
' D7 J0 d& K# e) y# {$ N3 u9 K2 H D6 y解 这是一个单目标的规划问题,用线性规划模型表述为: 9 b' H* J3 Y1 I- p2 f s p
, B, B1 y: Y% a, Z3 p3 N
![]()
/ B' j5 ?0 T8 [5 v. k2 U5 J0 C: K3 S: `0 V& t
但实际上工厂在作决策方案时,要考虑市场等一系列其它条件。如
- k T5 n, X# [) H: t, q. B- k
/ t; T+ [: t& h/ W4 \. T0 L4 {(i)根据市场信息,产品 I 的销售量有下降的趋势,故考虑产品 I 的产量不大于 产品 II。9 y+ U# Q! C5 t3 ` G
2 @5 I$ X) S3 L(ii)超过计划供应的原材料,需要高价采购,这就使成本增加。
7 [7 Q) m( \& D- u4 S$ V8 g) @: n9 G8 C7 Z& m
(iii)应尽可能充分利用设备,但不希望加班。 7 t s5 u8 W- ^1 ?/ B- O
* e6 A5 U+ l8 X: l/ x9 b" u5 T(iv)应尽可能达到并超过计划利润指标 56 元。
) x' u$ D( V, U' ]9 J" x4 |: ?" Z' b6 L/ a4 w! P
这样在考虑产品决策时,便为多目标决策问题。目标规划方法是解决这类决策问题 的方法之一。下面引入与建立目标规划数学模型有关的概念。
' ~( j5 A c5 T. m2 L9 m6 N% c5 ^* K6 W6 z7 K$ Q
1. 正、负偏差变量 3 u4 x- y; q, ?
e8 U5 i9 y8 A
& h! h. U6 f- A" I* C% z+ r, s q
2 D# s& }" o% l
2. 绝对(刚性)约束和目标约束 0 L+ K6 L3 l" N6 {: c
( ?; B# K- u0 b/ j* Z# n 4 w$ |+ m. Q+ b9 v' F
3 V/ _1 K5 U" E3 E, f7 t$ A
3. 优先因子(优先等级)与权系数
% @- z L4 M5 f% Q3 y2 n/ b! N) n9 K3 h" G0 ]
1 M: }4 L; o% `; P; r& o% |& z
( [: b. A$ ] f2 ~" K2 ^2 ^$ G1 X) c, `* X% e# u" w: Q8 u
4. 目标规划的目标函数 , F: O; r6 p ]& ^+ V- m U. J
- |- m9 c( y" Z& C
) G+ m: p3 ~& P% s8 G% Q
3 l9 R, R" U) _' n- P, _对每一个具体目标规划问题,可根据决策者的要求和赋于各目标的优先因子来构造目标 函数,以下用例子说明。
" f( C" j; T+ U6 s" a) _5 U
9 c8 c- O2 N$ s1 V1 e例 2 : 例 1 的决策者在原材料供应受严格限制的基础上考虑:首先是产品 II 的产 量不低于产品 I 的产量;其次是充分利用设备有效台时,不加班;再次是利润额不小于 56 元。求决策方案。 解 按决策者所要求的,分别赋于这三个目标 优先因子。这问题的数学模型是 + I0 P8 Q7 g' v# K& B
$ Y& o. |, M) ~8 M5 h
3 C7 n0 c0 ~0 v2 E
/ ^- Y# N; G9 z# v0 r0 \$ W/ L5.目标规划的一般数学模型
5 J. N8 O# U0 t7 s: E6 F
8 I& M" F; ` C7 R3 T" ] $ V6 O; h6 B6 w' R% x
4 G* M1 o0 N7 X: c( x$ s+ `% L9 B+ K3 @3 A8 g) U$ }
建立目标规划的数学模型时,需要确定目标值、优先等级、权系数等,它都具有一 定的主观性和模糊性,可以用专家评定法给以量化。
. Q; |7 A n( e( @- C* J7 d" ]' l4 F! _$ p5 o: t/ X l' s- S3 k! H/ s
3 求解目标规划的序贯式算法1 u/ } o3 N* [ h
序贯式算法是求解目标规划的一种早期算法,其核心是根据优先级的先后次序, 将目标规划问题分解成一系列的单目标规划问题,然后再依次求解。 6 ^7 _+ ^# ~+ o& N; R& P5 }
) G' C- A4 _+ L( J
![]()
$ b& p/ W6 D; S! m: u) D2 G" @ l/ C8 v) s" x
+ K) e5 w! C' ?6 \. Q* x
# s4 }1 m/ D- R6 e8 ]) Y注 此时最优解的概念与线性规划最优解的概念已有所不同,但为方便起见,仍 称为最优解。 5 f$ X* b1 S5 @- E j
8 d5 \% N8 x# w
例 3 某企业生产甲、乙两种产品,需要用到 A ,B ,C 三种设备,关于产品的赢利 与使用设备的工时及限制如下表所示。问该企业应如何安排生产,才能达到下列目标:9 E: }- G5 v. c+ N8 z& `6 h2 ^
7 Z$ R$ s; H. t/ W
![]()
4 M' _, }1 Y2 a+ i4 A
4 u' H8 O( G1 \(1)力求使利润指标不低于 1500 元;: j/ C8 K- Z( \2 U9 G: h. r; e
' A7 V9 H# T8 u% J$ B; D(2)考虑到市场需求,甲、乙两种产品的产量比应尽量保持 1:2;1 a, ]/ a2 M4 j6 W; u
% I" m7 D0 b" R# {" ?6 w. k" a* c(3)设备 A为贵重设备,严格禁止超时使用;
4 A4 b* O8 x; S4 o- N' I/ y& e# d3 _4 q- }0 [
(4)设备 C 可以适当加班,但要控制;设备B 既要求充分利用,又尽可能不加班。 在重要性上,设备B 是设备C 的 3 倍。 H3 A; H2 z; B! C- y/ ? l u/ b
, i4 V L/ T* `9 `" \* i建立相应的目标规划模型并求解。8 W+ X0 r, B" F0 |4 x2 N/ i3 R
+ Y% I- W8 t4 S6 f解 设备 A是刚性约束,其余是柔性约束。首先,最重要的指标是企业的利润, 因此,将它的优先级列为第一级;其次,甲、乙两种产品的产量保持 1:2 的比例,列为 第二级;再次,设备 B C, 的工作时间要有所控制,列为第三级。在第三级中,设备B 的 重要性是设备C 的三倍,因此,它们的权重不一样,设备B 前的系数是设备C 前系数 的 3 倍。由此得到相应的目标规划模型。 ; ` X, X0 _6 Y
4 I9 {% B+ `7 D; X4 d; x9 K( \ * @4 _' w P- \$ ]6 Y
3 z$ F' u! T# T3 P, F: f序贯算法中每个单目标问题都是一个线性规划问题,可以使用 LINGO 软件进行求 解。 求第一级目标。LINGO 程序如下:
! V. x& A$ a, c# z+ _$ d
$ [, U/ t1 k* j% Y& _model:
* D5 ]$ k7 B8 m8 n: u( u# Csets:
& k4 @& X/ Q7 X2 z: Evariable/1..2/:x;
, _3 D; i' _6 `6 K. ES_Con_Num/1..4/:g,dplus,dminus;
" t; Q) d- V- X! e3 WS_con(S_Con_Num,Variable):c;
3 m+ D+ q. h k; o' t0 @8 Nendsets
) f* _/ S8 V$ I3 Tdata: . P9 z; l1 s2 S" W4 m
g=1500 0 16 15;
9 T$ d5 J- k# p+ N4 ac=200 300 2 -1 4 0 0 5;
+ J# U( \% y2 w* e3 genddata
) d1 p7 K4 [5 M" Q/ J+ F& Xmin=dminus(1);
$ Z, ^# A! B6 N/ t" d2*x(1)+2*x(2)<12;
! _& {; g( z4 x" X. }- J8 v@for(S_Con_Num(i) sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i)); 8 z: g/ S% @. V: i
end) ^- z! ^0 m3 B* e* ]" M$ E, |' p
1 Q# Z. { l9 ?! Y求得 dminus(1)=0,即目标函数的最优值为 0,第一级偏差为 0。 求第二级目标,LINGO 程序如下: model:
6 P* E5 j! ?, Q! ?& O( ysets: 3 W, w% ]+ {% n9 _: c4 q
variable/1..2/:x;
/ G3 R1 I9 R" H. I/ o3 LS_Con_Num/1..4/:g,dplus,dminus;
. ~6 k: L% ]1 CS_con(S_Con_Num,Variable):c;
! j: g, Y! L+ [endsets 5 S9 l2 ]) h9 }; |& U3 |; v
data:
+ T9 @: f' t% qg=1500 0 16 15;
7 U: |' h, }/ H$ R- b9 R d* W2 yc=200 300 2 -1 4 0 0 5;
1 W* M& W1 G& I- Fenddata
/ q( m% c- W8 o- t# a7 m0 R: omin=dplus(2)+dminus(2); !二级目标函数; + Y' E- J8 [$ N+ L0 n
2*x(1)+2*x(2)<12;
J1 w4 n* @( T$ U@for(S_Con_Num(i) sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i));
' Q' H0 @: z4 S1 O3 H1 o4 mdminus(1)=0;!一级目标约束; 4 t! T& G) W3 k$ H! H9 p$ B
@for(variable gin(x)); 5 `: {' F. K4 w
end 3 G1 ]) _; w' X1 U% j" ]7 {6 B* C
7 O/ b2 j7 `. c6 F求得目标函数的最优值为 0,即第二级的偏差仍为 0。 求第三级目标,LINGO 程序如下:
" G* \8 x! k' r$ A* F2 Y; r/ l* ?# L0 H% R: F- p* ?+ I5 b; Y6 F
model:
8 `+ z) \" K: T. B s8 `sets: 9 s7 x' j. M. X; t3 p5 |# T
variable/1..2/:x; ; y. K4 m! _% D5 \9 ^- c
S_Con_Num/1..4/:g,dplus,dminus; 3 u" U" i4 p+ y5 P2 o8 U" f" B& y
S_con(S_Con_Num,Variable):c; s# k. Y3 M" a# g6 J; x
endsets
9 O. W$ m$ R% E) c0 V: _data:
# m+ _: A. d1 f+ @7 L" Pg=1500 0 16 15;
5 M% r' e5 `* T% r, @: a; @c=200 300 2 -1 4 0 0 5; 0 ~8 d/ z$ ]0 Y+ `
enddata
: X+ y2 v* ~" u( Vmin=3*dplus(3)+3*dminus(3)+dplus(4); !三级目标函数; * U: v$ P: d+ b0 B
2*x(1)+2*x(2)<12;
9 A3 w* }4 K5 D5 l, }# \ @for(S_Con_Num(i) sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i)); 5 I v, t# e2 y5 f7 O/ m. _. |/ S
dminus(1)=0;!一级目标约束; 4 t, n) X9 I4 P- O
dplus(2)+dminus(2)=0;!二级目标约束;
' g# r: R9 c& K. X. E% ?end
, {. B2 ?1 s+ y Y8 N, U8 ~
N3 U$ a# ]8 }目标函数的最优值为29,即第三级偏差为29。 6 o- f9 o3 Y/ J G5 J5 c
* z2 P+ @4 K* z. B1 M$ ~! g分析计算结果, ,因此,目标规划的最优解为 , 最优利润为1600。
: E8 p6 z, q/ T0 {# P- ~
- m5 b- t1 J* F3 b2 m8 J6 X上述过程虽然给出了目标规划问题的最优解,但需要连续编几个程序,这样在使 用时不方便,下面用 LINGO 软件,编写一个通用的程序,在程序中用到数据段未知数 据的编程方法。 |( ^4 A! k5 V
- d" J4 }( P q+ m- }例 4(续例 3) 按照序贯式算法,编写求解例 3 的通用 LINGO 程序。
1 M/ V7 F* U9 M% [
7 `" K. q6 A n) Smodel: 5 Q: H' ]1 V7 M7 m
sets: 0 m, w; e6 L# [" R' T- X" z' k
level/1..3/:p,z,goal; & t! i/ |' Q! H6 l7 ]+ z
variable/1..2/:x;
# F1 t9 t/ b: J5 y9 h6 ^2 ~h_con_num/1..1/:b; ; k, d) J2 ~+ _3 y6 {3 F; {' M. x
s_con_num/1..4/:g,dplus,dminus; ' L) O3 w! z4 D2 j
h_con(h_con_num,variable):a; ' p: A! L+ m5 W( |; _4 z1 \' B% y
s_con(s_con_num,variable):c; " f1 l* L9 L# M, A# u
obj(level,s_con_num)/1 1,2 2,3 3,3 4/:wplus,wminus;
; t. O; t. n: C$ i; d8 fendsets 8 J. _% i5 G; d Q/ `2 S, y/ Z
data: # ?* n$ K- g1 y0 w- B3 s
ctr=?;
) R1 e2 T( o; y, r- Kgoal=? ? 0; 8 \! x/ Z# t6 t
b=12; 7 V' I6 V* B& b, \
g=1500 0 16 15;
. c& ?: V& O2 R2 m3 ?# Ba=2 2; , t0 d0 ~& S* i( [0 S) q! u
c=200 300 2 -1 4 0 0 5; 8 x$ P% e/ E! ^% R
wplus=0 1 3 1;
& @3 ^% Q v7 ?8 m$ F- I: iwminus=1 1 3 0; / o* ~1 l! q$ I) |9 o
enddata # @- }' a1 z A3 D: c7 o
min=@sum(level:p*z);
" Y9 T: d5 z+ x: ~1 K/ f' m* Xp(ctr)=1; 4 U9 u! _# y4 M l6 W) f' U$ j
@for(level(i)|i#ne#ctr:p(i)=0); 2 \" K# p( h1 M9 s) ]
@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 |, P1 v9 \! M: S9 send ( b4 g( W% a7 l/ b3 O8 r4 s7 {
* |- U9 ?; P4 X3 ]# g
* G+ w% r- f+ c( z* h1 [9 F+ Q. ~& Q
![]()
0 q5 U/ I+ F. p- a( U2 q, `" |6 a; l& }
4 多标规划的 Matlab 解法 多目标规划可以归结为
/ z' E8 O' {7 k& V![]()
0 i$ Z. \' {; C6 L
}6 [5 ~: g# o4 b[x,fval]= fgoalattain('fun',x0,goal,weight) 0 _. J% a* k& v2 y ]; K9 v1 s
[x,fval]= fgoalattain('fun',x0,goal,weight,A,b)
. ?1 ]' P0 a" Q/ ~' A8 q1 e3 t i; l[x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq)
7 I: |8 K# h5 ][x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) + O+ ]* r' o) G+ S) V
) Z; p3 {5 ^% M# D" ?0 h0 K5 J4 X
. W% n0 J$ a! ?4 V
要完整掌握其用法,请用 help fgoalattain 或 type fgoalattain 查询相关的帮助。
) ] N* U; q) Z) [% s 例 5 求解多目标线性规划问题
0 y) E2 l7 ^1 O7 T: U
9 W3 h1 d) {6 N$ h # O: I) F( |" [% a# W3 A
+ S4 J9 c( ?% Y. T0 B+ f解 (i)编写 M 函数 Fun.m:
1 x0 p* Y# L) o) G( s& P' m# Q* X( B) s0 M
function F=Fun(x); . Z' w) s5 `" @5 W) I. J; D9 D
# `- i8 u" T4 ^1 i1 sF(1)=-100*x(1)-90*x(2)-80*x(2)-70*x(4); 0 F: b, e) i* T2 s
9 e/ _- |) E( l1 p" Y1 I: IF(2)=3*x(2)+2*x(4); & E# L! Y! I+ @9 [0 a) J/ [
) m4 e v8 {$ h5 s% a! X5 A. i(ii)编写 M 文件
t7 e' r2 u, b! o$ z$ P! t
+ H a7 z% s" e# i$ Ra=[-1 -1 0 0 3 V, k! V5 e/ z
0 0 -1 -1
) ?5 l4 \4 x7 b* G" h$ R1 v/ E8 k) K 3 0 2 0
T) f W' b% I. X+ ]: J3 ` 0 3 0 2]; 8 H# W w1 L; ?- h" n
b=[-30 -30 120 48]';
" i4 m7 D1 h7 Y0 S* s( {7 D+ Ic1=[-100 -90 -80 -70];
V8 z) V3 a$ d, rc2=[0 3 0 2]; & x, T4 M3 ?. T3 w7 F) W0 B
[x1,g1]=linprog(c1,a,b,[],[],zeros(4,1)) %求第一个目标函数的目标值 " E; z8 Z' X& B8 B: A/ o$ B
[x2,g2]=linprog(c2,a,b,[],[],zeros(4,1)) %求第二个目标函数的目标值 ) O5 C8 j+ ^8 _( r* U5 V7 H
g3=[g1;g2] %目标goal的值
* L2 _! O! ]4 ?+ c5 K+ s2 w[x,fval]=fgoalattain('Fun',rand(4,1),g3,abs(g3),a,b,[],[],zeros(4 ,1))
$ ?' I* L4 S4 {* H2 b6 n%这里权重weight=目标goal的绝对值
1 r4 R2 q: Y$ A2 N( h4 i' q' p# s" {0 N
就可求得问题的解。 习题
$ d; C" G4 w- N/ i1 u* S ' e' x a9 E: \. d& ^
0 q( T: D% x: ^
————————————————
* l6 Z0 J8 H/ C/ _- X4 S7 q版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
+ \3 C9 p# C: f4 s原文链接:https://blog.csdn.net/qq_29831163/article/details/89488932# b+ J# c4 M0 F2 M2 `1 {4 d2 P
% a- a+ T: J1 h5 T
" Z9 n+ ?! X0 u6 W) }# a |
zan
|