在线时间 791 小时 最后登录 2022-11-28 注册时间 2017-6-12 听众数 15 收听数 0 能力 120 分 体力 36352 点 威望 11 点 阅读权限 255 积分 13866 相册 0 日志 0 记录 1 帖子 616 主题 542 精华 12 分享 0 好友 225
TA的每日心情 开心 2020-11-14 17:15
签到天数: 74 天
[LV.6]常住居民II
群组 : 2019美赛冲刺课程
群组 : 站长地区赛培训
群组 : 2019考研数学 桃子老师
群组 : 2018教师培训(呼伦贝
群组 : 2019考研数学 站长系列
1.线性规划的局限性
. ?3 k, b, T# T 只能解决一组线性约束条件下,某一目标只能是一个目标的最大或最小值的问题。3 u8 e" X" k/ G
8 u6 S) r4 _: K4 u- G0 Z" Z, ?
2.实际决策中,衡量方案优劣考虑多个目标" {( r/ `& o$ O
这些目标中,有主要的,也有次要的;有最大值的,也有最小值的;有定量的, 也有定性的;有相互补充的,也有相互对立的,LP 则无能为力。
{4 v& a) S; \# c- d" y 1 Q+ G* Z; j0 t( W$ O
3.目标规划(Goal Programming)5 W9 X1 J U; H# F, K& R" ]
美国经济学家查恩斯(A. Charnes)和库柏(W. W. Cooper)在 1961 年出版的《管理模型及线性规划的工业应用》一书中,首先提出的。5 X. J. p2 w2 Z% O
+ ]; K& q" x4 m9 ]
4.求解思路
8 |5 D) f1 `1 Y/ B/ Q, } (1)加权系数法" K4 V# C; W5 n! h) _" G
为每一目标赋一个权系数,把多目标模型转化成单一目标的模型。但困难是要确 定合理的权系数,以反映不同目标之间的重要程度。
" Z" D/ s0 g! t7 m0 [7 [; r4 u 8 H# Z1 o4 E. I/ Q0 A2 k: H/ P
(2)优先等级法
, ~& c, S. x4 R3 M* i8 D/ A 将各目标按其重要程度不同的优先等级,转化为单目标模型。
3 w( _! r1 `, H3 s6 V" e3 k
3 T3 B( {, ~. h" F3 h/ q6 z (3)有效解法 y# p& I, T: B& K/ @" i) _
寻求能够照顾到各个目标,并使决策者感到满意的解。由决策者来确定选取哪一个 解,即得到一个满意解。但有效解的数目太多而难以将其一一求出。 # N J: w4 ~4 B- ^0 Y/ p& F' x
6 n p. J5 c2 r9 P% Y
2 目标规划的数学模型& V0 P0 E) N; v. s- x
为了具体说明目标规划与线性规划在处理问题的方法上的区别,先通过例子来介绍 目标规划的有关概念及数学模型。5 K& `9 `7 q5 m/ ]" [# j: y
: E3 x* a$ C) H( `; [ 例1 某工厂生产 I,II 两种产品,已知有关数据见下表 ,试求获利最大的生产方案。
5 y. L* O' a# {0 y4 F. d/ a5 G
8 K$ O1 c) u+ P) }1 @! ^& L " k5 S4 s" a( w" ?. _% v
0 I& G+ \( O- ~- |: E' m$ D" _. n 解 这是一个单目标的规划问题,用线性规划模型表述为: 6 X0 A+ v# e& Y0 K
% d2 `: v6 Y7 V0 I6 ]. T
' ~1 Z9 @5 }4 X/ j! Z8 Z
2 f- ^8 I: z, q- E( c0 Y4 T* l* N6 q 但实际上工厂在作决策方案时,要考虑市场等一系列其它条件。如
/ o' k# ^- \) v- R$ X# G
- h3 a3 J! y$ t L$ }, Z (i)根据市场信息,产品 I 的销售量有下降的趋势,故考虑产品 I 的产量不大于 产品 II。- M4 }6 b/ k' Q/ `8 g
( N* U7 s0 d, [, Z* w0 }
(ii)超过计划供应的原材料,需要高价采购,这就使成本增加。
! P T3 Y; _% \! Q) R
0 L$ N$ A3 Q" ` (iii)应尽可能充分利用设备,但不希望加班。 ! a' h# w; d3 q
+ u* k4 g6 C9 \% U (iv)应尽可能达到并超过计划利润指标 56 元。; ~8 R, Q$ W4 c+ R0 X: p2 W+ u# t. d
# L2 V* G/ l! B6 I2 s& o" M" z. P 这样在考虑产品决策时,便为多目标决策问题。目标规划方法是解决这类决策问题 的方法之一。下面引入与建立目标规划数学模型有关的概念。 . ]( }" K( V% f; t
+ G4 F% U; L8 C. f& d9 ^& @& G 1. 正、负偏差变量 2 n7 |" o- Q: X1 i4 W4 }
# Q6 T; v/ A3 J: q
6 E* _, \" B% M3 E9 J0 v4 t! e $ O4 B. g" A0 O1 H9 ]1 A1 i
2. 绝对(刚性)约束和目标约束 . b$ B' a, J' W; S7 U& T* Q6 Q
5 B4 Z2 [, c9 l( I
& q, j2 V' I1 G3 \" |, D5 u6 R
6 j$ M' u2 e- s( s6 T% G/ K2 D 3. 优先因子(优先等级)与权系数 . Z! m9 D; ^5 z* q7 `5 v* n
2 L. C# ?4 x7 `+ m2 W$ U
- u0 @# k- v( b6 E" H- K
2 S: L/ o. z4 p# P
5 F; K& U/ L& r6 j1 { 4. 目标规划的目标函数 $ j" |7 \" `* C, s/ [8 e+ E3 p) t
/ q: z+ Q6 X2 M: [
* Y8 b' B5 F8 |0 F # \- C; Q' G2 w, Q; ^
对每一个具体目标规划问题,可根据决策者的要求和赋于各目标的优先因子来构造目标 函数,以下用例子说明。
- w7 w: h! r+ [, B, ^; P) Z
+ t3 b1 Y* [8 q* f6 w% Q& a 例 2 : 例 1 的决策者在原材料供应受严格限制的基础上考虑:首先是产品 II 的产 量不低于产品 I 的产量;其次是充分利用设备有效台时,不加班;再次是利润额不小于 56 元。求决策方案。 解 按决策者所要求的,分别赋于这三个目标 优先因子。这问题的数学模型是 # h) r( `# L& o; i4 a
- h, N4 H1 D% `! B+ o% h6 N
& U0 J' @( m( a& `
i7 G: b3 M6 ^+ A* H1 q: w 5.目标规划的一般数学模型
/ r. L1 ~; q8 Q* G9 F! S - f5 K3 k$ w& q9 C9 n
; T T) {2 d$ C7 k- E. l, O $ i4 G1 G- _5 \, A/ r/ J1 @% g
2 L5 R+ M3 k* E6 F! i 建立目标规划的数学模型时,需要确定目标值、优先等级、权系数等,它都具有一 定的主观性和模糊性,可以用专家评定法给以量化。 / I6 u4 g. S, R# Y! E1 G$ H
4 u+ O4 J8 _+ y8 j 3 求解目标规划的序贯式算法4 j" b# W! d- t* _2 O
序贯式算法是求解目标规划的一种早期算法,其核心是根据优先级的先后次序, 将目标规划问题分解成一系列的单目标规划问题,然后再依次求解。
7 e. z' r' s- F$ s& O$ O 2 l( _ j! N+ }. n& E7 }, ?
: v1 s; \+ D: y' f# Y3 e: |" S
, G6 c9 N; ~; V, d% y# X
3 Y) T1 [( J" H- l7 a
" ?: d- d3 \! K5 [5 `# A 注 此时最优解的概念与线性规划最优解的概念已有所不同,但为方便起见,仍 称为最优解。
& v [0 l7 x8 W$ \$ g( v( r
: O) W# H0 w. m9 J* E 例 3 某企业生产甲、乙两种产品,需要用到 A ,B ,C 三种设备,关于产品的赢利 与使用设备的工时及限制如下表所示。问该企业应如何安排生产,才能达到下列目标:8 F& J" z2 D/ Y1 k. ]
" I1 e- g. c/ _* P0 t ; U, U2 ?0 z; p. i5 Y1 _- c6 F
1 D- y' t3 T6 L, T4 }/ e- @: y/ o& i
(1)力求使利润指标不低于 1500 元;" G2 K& v# x# O
2 ~* }, l* }, x$ a) i
(2)考虑到市场需求,甲、乙两种产品的产量比应尽量保持 1:2;5 b0 r) Q n6 P2 F' h: P$ A
9 O I7 H' V1 M5 a8 X (3)设备 A为贵重设备,严格禁止超时使用;& W# T: w5 q8 {
% q$ R1 o0 y6 i3 P A' ^9 x8 F8 [& _
(4)设备 C 可以适当加班,但要控制;设备B 既要求充分利用,又尽可能不加班。 在重要性上,设备B 是设备C 的 3 倍。
& f" \6 V/ c T" m6 @6 `0 O9 Q - Z9 c# }# v7 z2 m9 X) T
建立相应的目标规划模型并求解。
, w9 f, F# N1 {4 U$ M/ m/ n
5 }3 z! W: ?" _: w' b6 X: H 解 设备 A是刚性约束,其余是柔性约束。首先,最重要的指标是企业的利润, 因此,将它的优先级列为第一级;其次,甲、乙两种产品的产量保持 1:2 的比例,列为 第二级;再次,设备 B C, 的工作时间要有所控制,列为第三级。在第三级中,设备B 的 重要性是设备C 的三倍,因此,它们的权重不一样,设备B 前的系数是设备C 前系数 的 3 倍。由此得到相应的目标规划模型。
: o' o% W. D/ L! Q5 |" w7 T0 T7 l
+ k% V& ?' \7 Y; s6 s8 j
/ E5 w3 u& g" [5 f ) v" c& @& A& H6 i
序贯算法中每个单目标问题都是一个线性规划问题,可以使用 LINGO 软件进行求 解。 求第一级目标。LINGO 程序如下: : r: b+ ^! I! _9 p
/ E# i* X( G& H- e8 R5 p# [' Y* T
model:
8 L/ ?8 l& s+ I% P8 B6 I8 G sets:
' d# B/ t' I/ n. A1 H variable/1..2/:x; - B5 H2 R6 D5 O
S_Con_Num/1..4/:g,dplus,dminus; f1 \! j& g# \ ~& \& p
S_con(S_Con_Num,Variable):c; 3 H8 } n0 @+ Z4 d p" t/ E3 Q
endsets
+ |/ B9 H2 g5 m" L1 p6 E9 J- Z data:
0 q" u; S. I0 \ z g=1500 0 16 15; 9 |( p6 A! |" Z; N; o3 s/ A! |
c=200 300 2 -1 4 0 0 5;
$ i0 D5 ?& _6 ]: @' {- ~5 q% U( s enddata
3 O8 z! Y1 Y/ K( g+ } min=dminus(1); " t# q# z5 ^4 a9 h* P
2*x(1)+2*x(2)<12;
2 {, ^, I( c$ K; b/ r @for(S_Con_Num(i) sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i));
0 _; U S/ z" e% J end. O7 J* H! a* E
- R# ~, t: v% B& a6 P9 u( ^# R7 c- ` 求得 dminus(1)=0,即目标函数的最优值为 0,第一级偏差为 0。
求第二级目标,LINGO 程序如下:
model:
8 g( E0 v3 X8 l" y sets: 8 j( b# H) [2 r8 [/ d C' p
variable/1..2/:x;
$ O. @) J. _4 U9 U; C S_Con_Num/1..4/:g,dplus,dminus;
) J. r" ]& i9 L S_con(S_Con_Num,Variable):c;
+ I1 j3 A- P8 k# ~. s+ z endsets
; k8 ` a z# i: F data:
0 T0 L& }- P2 k; R& h8 e$ @. E g=1500 0 16 15; ' |, W4 I: {/ d6 o
c=200 300 2 -1 4 0 0 5; 4 R9 P$ A4 h" I% R8 r$ y! M5 O
enddata 2 _7 @4 q4 F4 v" R
min=dplus(2)+dminus(2); !二级目标函数; 7 p7 H( g( h( \4 o: N6 `
2*x(1)+2*x(2)<12; " C/ ^% p" M6 H+ f
@for(S_Con_Num(i) sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i));
9 G# s0 ^7 h8 T" @4 G dminus(1)=0;!一级目标约束;
: P) z1 Q: Q& H3 V' }4 F R @for(variable gin(x)); " {9 ]0 f* a T. g
end 7 x6 {4 H! @; a
& S5 B7 G4 e6 b/ {+ X4 j
求得目标函数的最优值为 0,即第二级的偏差仍为 0。 求第三级目标,LINGO 程序如下:
$ N) r# Q4 O6 W L( O0 I9 H, h 3 R( N3 u- T" y1 B
model: % d9 O; \& ]# m0 k. d3 I# u
sets:
* j4 N* D% \7 c7 J variable/1..2/:x;
7 n; ^9 Q" p" H& v S_Con_Num/1..4/:g,dplus,dminus; ( ?3 Q) k6 t0 z' l9 M4 x, B
S_con(S_Con_Num,Variable):c;
! g& A2 L3 t+ I1 D- g7 A endsets , b; k2 i, X5 ~9 y
data:
2 s9 n) O' D9 K: [# r g=1500 0 16 15;
% T& O8 @* [3 ^1 _0 k/ C' [+ I c=200 300 2 -1 4 0 0 5; # r8 \6 E" h# H" J& [* E5 W) E
enddata # E7 `+ g D' O8 P( k8 V
min=3*dplus(3)+3*dminus(3)+dplus(4); !三级目标函数;
6 ]$ r. p; B2 S# o& u/ O 2*x(1)+2*x(2)<12;
3 b6 ?9 `* C% Y% Z" t. X: | @for(S_Con_Num(i) sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i));
5 r+ r; S6 ~# _8 p dminus(1)=0;!一级目标约束;
, ^* X1 b1 y$ G7 J2 U! ] dplus(2)+dminus(2)=0;!二级目标约束; 3 l8 T ^1 h0 J2 y3 e" G
end2 n4 C$ s2 S+ |
; \9 j( f. w6 ]( X
目标函数的最优值为29,即第三级偏差为29。 9 K" H, {! o0 @
6 C" }( I' `. d3 y: L# _ 分析计算结果, ,因此,目标规划的最优解为 , 最优利润为1600。, p2 i. G4 G8 { `, e
8 ], V' j/ k$ @+ z, T/ m
上述过程虽然给出了目标规划问题的最优解,但需要连续编几个程序,这样在使 用时不方便,下面用 LINGO 软件,编写一个通用的程序,在程序中用到数据段未知数 据的编程方法。+ b$ G/ f) p3 C$ x d) c
# D8 x! i; Z! j& t. p, Z 例 4(续例 3) 按照序贯式算法,编写求解例 3 的通用 LINGO 程序。
, c6 u; T! d3 y4 V0 X ( r- `2 S4 A1 d5 X# f+ o, J
model:
* x$ ~ `* M+ S7 z2 p sets: k& i2 R( @7 \4 Y4 H
level/1..3/:p,z,goal;
. {8 D0 O; q2 D8 \: E variable/1..2/:x; % v: j/ t; E6 }, f* e
h_con_num/1..1/:b; " L& u: ^& d% N+ r. M8 Y7 ]
s_con_num/1..4/:g,dplus,dminus;
1 G, h1 x" Q1 a/ I h_con(h_con_num,variable):a; 8 y; p: v" r! t. T G9 ?; W4 A
s_con(s_con_num,variable):c; 1 D3 J8 F; r9 D4 n5 ^
obj(level,s_con_num)/1 1,2 2,3 3,3 4/:wplus,wminus; 6 s) W" `: P% c! i+ H
endsets ; O4 ]$ g" c7 L, H
data: 3 D+ g: F9 B4 y8 x; U% b& z; y
ctr=?; / {4 l: B1 h0 Z, Y9 a! h
goal=? ? 0; 8 C& h/ m! [& z: P, S) `
b=12;
! I- h0 z; |3 _ X/ L0 } g=1500 0 16 15;
5 D' X% B) F- ^; p) y, ^ a=2 2;
& ~9 V1 Z% y: V+ E1 x+ A c=200 300 2 -1 4 0 0 5; ; [2 s6 M, O( Q- n
wplus=0 1 3 1; " H' k! _! P+ K/ {, y( }
wminus=1 1 3 0; 6 S+ u6 @# r8 e4 _8 G- L
enddata
$ y7 y" G5 Z) k; M min=@sum(level:p*z); # H3 |5 \* D4 h" x
p(ctr)=1;
1 y: Y! L( c: Z# S. t: ~9 f8 ]7 ] @for(level(i)|i#ne#ctr:p(i)=0); 4 r# E" \0 g& 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))); ! l$ ?2 X! ?8 i
end
0 }, O* c. o, J' q4 l+ C( X0 o! N
8 h% U/ v# ^% x" s& p
1 E9 r3 I8 {' {2 Z. j/ T7 Q & I1 y* B1 j$ S4 P3 Z) X* I
K; Q( Q) S2 ^# |! {6 u5 Z
: r- k: J. p" F ]* W 4 多标规划的 Matlab 解法 多目标规划可以归结为
3 e# z. l' y2 q& s) b. [
# C3 R1 W5 X; D- @4 @
9 y$ ]% T6 t, E1 I) C4 }- A
[x,fval]= fgoalattain('fun',x0,goal,weight) 2 c! `# C$ W% O# h! h- h% K
[x,fval]= fgoalattain('fun',x0,goal,weight,A,b) ( G1 s5 ^( L! T, e
[x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq) ! @" H+ R& J8 B- j) V( |
[x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)
9 g8 Q" I- J" H6 R; _- a
6 Z+ o' R) |) H* x( N/ _
# k, \( |1 L7 P( A; D 要完整掌握其用法,请用 help fgoalattain 或 type fgoalattain 查询相关的帮助。 6 r% x% _* Z( x
例 5 求解多目标线性规划问题
8 Z# L% `) e0 D; _6 m" C; y
4 V) G' g: X4 }: _8 L / f& g) k( F6 q# n
! f) |7 I; z% ?$ s 解 (i)编写 M 函数 Fun.m:
' n7 E. N; C+ T 8 h, i, ~- y( E2 Y) n# ~
function F=Fun(x); ) S' d, i- K9 w' p" H e
" k( s7 H0 }! H* ^: o; U, j( s/ ?
F(1)=-100*x(1)-90*x(2)-80*x(2)-70*x(4); : x0 A0 N$ C: o% H& s$ f8 l
6 m& L1 o/ |# m
F(2)=3*x(2)+2*x(4);
. r# ~$ w& x W- u& X4 n. e
% ]. V: z; r$ b" E$ K% U (ii)编写 M 文件
, u0 c* k& \% p
3 z7 O7 z- F) E0 { a=[-1 -1 0 0
' P- p3 Q) T2 F" L1 D# `. Z 0 0 -1 -1 0 e' M2 ?; o0 I) j2 d: S3 {- O1 O
3 0 2 0
8 ?% T6 R4 n' j' }; R( q; n 0 3 0 2];
. L3 C8 q3 J/ Y o) h b=[-30 -30 120 48]'; ) ?" U* e# ]; a3 I9 Y7 t, y! W& i
c1=[-100 -90 -80 -70]; + A9 `3 W1 ~! ~( ^% f
c2=[0 3 0 2]; ) H- Y Q* |' m' |; i n; U* x
[x1,g1]=linprog(c1,a,b,[],[],zeros(4,1)) %求第一个目标函数的目标值
6 ~1 h( \9 V* B% g }, [ q [x2,g2]=linprog(c2,a,b,[],[],zeros(4,1)) %求第二个目标函数的目标值 5 n; w- Q/ P& |* u* K
g3=[g1;g2] %目标goal的值 5 d, }& z, k, t! x2 I/ L
[x,fval]=fgoalattain('Fun',rand(4,1),g3,abs(g3),a,b,[],[],zeros(4 ,1)) # |! U4 b1 J# b1 b
%这里权重weight=目标goal的绝对值 5 q5 w+ ]8 L0 I; s* e
9 ?1 v# V8 N$ w: ~; @9 n
就可求得问题的解。
习题 - q1 z' ]3 ?& J- s# b
m+ l Q( G# x$ h# _
% r5 F5 S( D* O6 \" r: z ————————————————/ ]( X: _ X2 h+ Z* o @$ v
版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。, G u1 L+ `. k+ f* b) [; G- ~ b
原文链接:https://blog.csdn.net/qq_29831163/article/details/89488932 Z8 f3 g/ z h5 @
6 a; O$ Y# A% u* s) W7 s % s: u1 b( v9 F5 k2 q4 e- W' K) R
zan