在线时间 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.线性规划的局限性
2 F1 _+ u# K6 m/ z: y' Z2 B9 S& a, N$ Y 只能解决一组线性约束条件下,某一目标只能是一个目标的最大或最小值的问题。0 \' B5 Q- c9 ?1 _+ \
* I; ^# ^: T" }/ O. o
2.实际决策中,衡量方案优劣考虑多个目标
$ |# q( O& i6 m5 Z$ [' ~' Q1 K* t3 _ 这些目标中,有主要的,也有次要的;有最大值的,也有最小值的;有定量的, 也有定性的;有相互补充的,也有相互对立的,LP 则无能为力。5 y {+ }4 F0 v9 X5 ~
8 t5 q7 T/ O4 ~2 V9 D/ C) A9 H
3.目标规划(Goal Programming)& \. s% r9 l! s
美国经济学家查恩斯(A. Charnes)和库柏(W. W. Cooper)在 1961 年出版的《管理模型及线性规划的工业应用》一书中,首先提出的。
& j1 R7 `1 Q+ @# \) O1 F+ i) N
" K# j6 B0 @6 a6 p; H6 l 4.求解思路
" I/ _- F9 ~8 m5 x( v$ l4 n8 q) U: z (1)加权系数法) q+ D2 H( q; C* H& p6 |! p) k @
为每一目标赋一个权系数,把多目标模型转化成单一目标的模型。但困难是要确 定合理的权系数,以反映不同目标之间的重要程度。
3 T' u3 G0 Q" a4 N7 E+ T ; B9 C8 g1 U7 j1 O) \* a
(2)优先等级法5 J6 F4 \: @% @* r* p
将各目标按其重要程度不同的优先等级,转化为单目标模型。
( l/ C5 L0 G& m
( x% v" a6 a9 n5 @8 H4 E) l- H. ]0 { (3)有效解法
# i. N/ x8 ~4 y" a [8 m 寻求能够照顾到各个目标,并使决策者感到满意的解。由决策者来确定选取哪一个 解,即得到一个满意解。但有效解的数目太多而难以将其一一求出。 1 ?3 `/ Y. d2 l+ z) X/ t+ {
" c8 @: }& O) Y$ O& M 2 目标规划的数学模型
( S3 t' ^$ r: I! { 为了具体说明目标规划与线性规划在处理问题的方法上的区别,先通过例子来介绍 目标规划的有关概念及数学模型。
- M" s; b6 u V1 g/ R5 L2 v
8 u& F% W2 E! X7 Q; g% H! d 例1 某工厂生产 I,II 两种产品,已知有关数据见下表 ,试求获利最大的生产方案。2 J4 r+ M2 i% Z
2 r; g- g) r b: [. j J3 w 6 U$ V7 n& B" ~* h( s# _& h
! v* k5 w& Y- E# b) n4 K2 Z 解 这是一个单目标的规划问题,用线性规划模型表述为: , w V$ G7 G3 ~8 s
! O5 x4 E5 U# s' O
9 l1 M. x+ j5 c" T2 b; q
. X5 i- l( x% O' V$ j
但实际上工厂在作决策方案时,要考虑市场等一系列其它条件。如; e f; a7 n9 e) o {# i' A' T0 g$ u
: P( d2 P8 e% z6 ]- B5 L (i)根据市场信息,产品 I 的销售量有下降的趋势,故考虑产品 I 的产量不大于 产品 II。
" n! P8 Q) d* Z# t) H8 _7 f
i2 P1 T! j' m7 \7 X (ii)超过计划供应的原材料,需要高价采购,这就使成本增加。6 R5 |4 P9 r s' g3 B6 K
, C- y; y9 z+ ?4 x# D9 u* }
(iii)应尽可能充分利用设备,但不希望加班。 , Y/ b6 v7 ~- b' U# {1 U# d
$ }$ E+ H* l9 q (iv)应尽可能达到并超过计划利润指标 56 元。
. j: a9 P! o V/ w, e
! u$ C6 s7 Z+ F* ~$ g3 J( P 这样在考虑产品决策时,便为多目标决策问题。目标规划方法是解决这类决策问题 的方法之一。下面引入与建立目标规划数学模型有关的概念。
1 O; W5 ?7 A5 r$ D: ?4 |5 `' N
- H% ?( h9 h4 A 1. 正、负偏差变量 3 U. a" n4 i. m5 _
; q$ W# e7 m2 d8 c
/ _' X& N+ D0 A2 z
, |9 @& |: `, E" ]. S1 ~ 2. 绝对(刚性)约束和目标约束
! J# s: Z4 x$ X7 ]+ u0 w- g
/ V' y0 c, g u! D- S2 e
1 {! X) l/ t& W2 ~, k/ r ' |- y% `$ n# l+ P
3. 优先因子(优先等级)与权系数 8 h2 O6 B9 W2 h( p+ n9 ]% T2 e
9 }! n3 H" s9 G8 `' e6 A4 y1 M 5 U/ B: ?# l1 w4 W2 i3 ~$ b. b" n
' u9 u, Y* r6 v9 ~ a6 D 6 Y/ b7 E: z3 ]) V7 s4 p7 f; H
4. 目标规划的目标函数
6 ]7 h. h8 Z4 i1 }' t u* o4 O! l2 ~ ' w* z+ Z; r0 y
& P( i( |8 o7 @& n4 M4 |, r
' F& E+ G! l& V/ F 对每一个具体目标规划问题,可根据决策者的要求和赋于各目标的优先因子来构造目标 函数,以下用例子说明。
6 j9 i% q& k8 J/ n6 y' x
( N& q, w) g* z0 |6 H 例 2 : 例 1 的决策者在原材料供应受严格限制的基础上考虑:首先是产品 II 的产 量不低于产品 I 的产量;其次是充分利用设备有效台时,不加班;再次是利润额不小于 56 元。求决策方案。 解 按决策者所要求的,分别赋于这三个目标 优先因子。这问题的数学模型是
! P' g) _9 Y1 ~8 ~4 K
T, x' E* A6 v3 Z; _7 @. ? % B& |4 o. C* K- o/ o
( ~$ n* Q( a/ d0 x
5.目标规划的一般数学模型9 u! T4 P4 D' Q
' a2 y+ e3 {" I$ b
& {( M. j0 D4 Y$ V4 l3 Z
7 B- r. g- z( k; u" h
( l; {& Z* Z7 W4 s5 m( d; W" J- t6 h 建立目标规划的数学模型时,需要确定目标值、优先等级、权系数等,它都具有一 定的主观性和模糊性,可以用专家评定法给以量化。
/ Q: q6 s: f& z6 P 6 w! W8 N) \1 ^! b, r( [4 F
3 求解目标规划的序贯式算法
6 p5 ^% |4 F9 D5 x 序贯式算法是求解目标规划的一种早期算法,其核心是根据优先级的先后次序, 将目标规划问题分解成一系列的单目标规划问题,然后再依次求解。
. C1 R4 b; ~& H# {4 e
6 \$ V b7 F5 \. f5 V ' F1 w' {2 V: Y5 }
7 A' Z! y$ V g2 u& U
; M X+ t S9 o9 ]
0 `; B* j1 H) C. _ 注 此时最优解的概念与线性规划最优解的概念已有所不同,但为方便起见,仍 称为最优解。
* w& R1 W2 u. y+ _ 6 g- ~+ l- D! Q2 I( D
例 3 某企业生产甲、乙两种产品,需要用到 A ,B ,C 三种设备,关于产品的赢利 与使用设备的工时及限制如下表所示。问该企业应如何安排生产,才能达到下列目标:
' c+ i% X6 j L3 V+ X 9 @: q. w, ], Q1 c9 u; |. B; D
6 d, z" u- ]2 Q z- F' D: W
* U; |4 X1 z% l- X* Z (1)力求使利润指标不低于 1500 元;1 H+ e9 w! y) I6 q7 r8 ~ \
8 I6 P9 Z* ?3 `. `
(2)考虑到市场需求,甲、乙两种产品的产量比应尽量保持 1:2;6 X8 b+ O4 @( Z' Q0 n7 Z
) x4 O" t% B: z7 `7 T (3)设备 A为贵重设备,严格禁止超时使用;1 m! i: e* U q: b2 H( \
) T/ I2 z' D- f4 v
(4)设备 C 可以适当加班,但要控制;设备B 既要求充分利用,又尽可能不加班。 在重要性上,设备B 是设备C 的 3 倍。& |* z3 N/ M8 C K
; L: m% B( u/ D
建立相应的目标规划模型并求解。
! B L4 T4 p5 n4 p7 n9 T 1 ~- J7 q! b9 y# c+ L4 P
解 设备 A是刚性约束,其余是柔性约束。首先,最重要的指标是企业的利润, 因此,将它的优先级列为第一级;其次,甲、乙两种产品的产量保持 1:2 的比例,列为 第二级;再次,设备 B C, 的工作时间要有所控制,列为第三级。在第三级中,设备B 的 重要性是设备C 的三倍,因此,它们的权重不一样,设备B 前的系数是设备C 前系数 的 3 倍。由此得到相应的目标规划模型。 % J: h& ^, c; ^
* W" w! _+ a8 Z0 B$ X' [ . u: R. c3 @+ y( r) X4 t2 K( r
5 O8 {( `; G& l* a
序贯算法中每个单目标问题都是一个线性规划问题,可以使用 LINGO 软件进行求 解。 求第一级目标。LINGO 程序如下: 8 v: m1 z% k# W. z% i
+ d* }- u4 E. A# N model: 8 l* v: W+ Z; N+ m8 d1 k
sets:
: j. s' U7 \% K; Q( }! W variable/1..2/:x; " _, A& D$ u) D
S_Con_Num/1..4/:g,dplus,dminus;
3 r: k8 ]0 i7 Y# Q- l S_con(S_Con_Num,Variable):c; $ {' O2 v- U# R$ b9 N2 n# k( w
endsets
+ x/ k) W/ X% o2 s' l T data: 1 X& T& y3 B/ ?( r0 W$ F
g=1500 0 16 15; ! B% W5 g1 Z( I5 A8 n. n! S- x
c=200 300 2 -1 4 0 0 5;
+ J/ t: h T1 i' ~8 \4 h+ E8 _ enddata
* L5 f$ @5 Q! B4 g/ X$ p$ D min=dminus(1); ( M/ x2 ]. {, m: W
2*x(1)+2*x(2)<12; " ?+ y; p& C5 g1 ^4 q$ h
@for(S_Con_Num(i) sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i)); $ K5 p- A3 {' J$ ?# V! }
end! }% L; v6 D# x9 k" V7 h, E
% T3 g# n$ A2 R; A2 C' d 求得 dminus(1)=0,即目标函数的最优值为 0,第一级偏差为 0。
求第二级目标,LINGO 程序如下:
model:
+ j3 i$ O# M' u: V W( { sets: " {7 b- e) L- q8 Z9 J
variable/1..2/:x; 7 I! C" f' T: D( m5 a
S_Con_Num/1..4/:g,dplus,dminus; , o ~6 P* Z6 @! O* k. U" k+ o
S_con(S_Con_Num,Variable):c; 1 E1 b" L5 E- H: l
endsets # I' e6 y5 D+ m% r
data: # @* a+ E/ Z# }% Z+ ?
g=1500 0 16 15;
2 U% d2 g5 z0 Z P/ i3 P/ J c=200 300 2 -1 4 0 0 5; ) z" e, ^8 W" D9 x6 x
enddata . k- M# q; p8 E; z! ?8 z/ N
min=dplus(2)+dminus(2); !二级目标函数; - ?$ ^) A% s5 c0 v) W% A$ I
2*x(1)+2*x(2)<12; . Y% z( D( Z4 }' @0 d
@for(S_Con_Num(i) sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i)); ; [2 t6 V& ]+ F2 ~6 W
dminus(1)=0;!一级目标约束;
# b- @* Q/ @1 Y/ N @for(variable gin(x)); 1 ], _% Q8 V8 |* h
end ' j6 W, C' D, m! F4 F- x" ^
+ p; _) U5 X9 x) o$ @( r" g
求得目标函数的最优值为 0,即第二级的偏差仍为 0。 求第三级目标,LINGO 程序如下: * b3 F+ d# \' O, W, |( H
4 N U4 Y8 s$ Z model:
( s u# d& s6 |& @) ~, B sets:
* E0 {& O" x7 `. }; ]( w( Y variable/1..2/:x;
# k: T& k" b6 O; i; }. ^, v S_Con_Num/1..4/:g,dplus,dminus;
" H1 W" e% R5 _: W S_con(S_Con_Num,Variable):c; ! @. l8 \. ~, b! Y, H! y
endsets
) g6 z& E3 ?2 g/ v data:
. S$ Q2 s2 F# p9 k( K: B, T+ k g=1500 0 16 15; ; r$ K8 j5 R# Z! C/ b# X: [! P7 g3 L$ N
c=200 300 2 -1 4 0 0 5; , h8 ?# z, u3 K! p. x; s
enddata 1 O. c3 g2 c/ n0 n6 a& C4 F
min=3*dplus(3)+3*dminus(3)+dplus(4); !三级目标函数; 7 U5 U4 Z' J' h( ~8 g; C+ x. S
2*x(1)+2*x(2)<12;
! I2 K) `* s1 f5 X/ t2 C @for(S_Con_Num(i) sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i));
1 C: u1 w4 {+ I dminus(1)=0;!一级目标约束; 0 A. X- b. I7 b- I5 r" _
dplus(2)+dminus(2)=0;!二级目标约束; $ k8 M: P: ~) o# D
end
& c* o: g* \) t$ o : V/ |3 G+ _! X5 W" l1 }( J: e
目标函数的最优值为29,即第三级偏差为29。 & s8 j n9 c1 y. q" k5 G h) M
" Q9 E- w; L2 `; @5 t
分析计算结果, ,因此,目标规划的最优解为 , 最优利润为1600。
3 b( [; m' Z G$ x, c
7 m* X0 \) h! o 上述过程虽然给出了目标规划问题的最优解,但需要连续编几个程序,这样在使 用时不方便,下面用 LINGO 软件,编写一个通用的程序,在程序中用到数据段未知数 据的编程方法。
; M7 Z. y! S1 M : O% Z1 Z! K# `+ b( k
例 4(续例 3) 按照序贯式算法,编写求解例 3 的通用 LINGO 程序。! ?. @( t, D r
4 _" i( S8 U6 G" d' p7 B% s; m- o model: 4 v1 B/ S: @8 u- B/ o+ J5 p6 A
sets:
1 \4 j4 g0 {" i7 T6 |. v/ W level/1..3/:p,z,goal;
; R4 U$ E+ l& o8 c: k/ h variable/1..2/:x; ( ?. O8 `$ s9 D: ?4 [
h_con_num/1..1/:b;
3 g% H D I ~" z/ h) f s_con_num/1..4/:g,dplus,dminus;
+ }/ O# m* @* v+ U h_con(h_con_num,variable):a;
! Y b* K* x8 \3 E; M% c& \( C s_con(s_con_num,variable):c; 1 T1 Q) [/ ~) S/ k
obj(level,s_con_num)/1 1,2 2,3 3,3 4/:wplus,wminus;
6 e, B1 w( E" ?( S- D endsets
, w! i4 u8 I) G F$ ~3 l data: 4 g$ Y: h' b$ Q. {! L
ctr=?;
, k& | e: b# C- U# ^ goal=? ? 0;
2 l+ L6 q& e" c; ~0 C4 U b=12;
, L% z, x* H) V( I9 m' c g=1500 0 16 15; 9 Q0 \: |+ g" F* v! E; X& s% Z
a=2 2; # S, S* X# G' b+ u
c=200 300 2 -1 4 0 0 5; 6 l2 }3 S& H& B" O$ g- C- Z# O0 @
wplus=0 1 3 1; / E3 N; |7 X, Y8 h; ] Q; Q
wminus=1 1 3 0; 0 H( [6 ]/ @: e8 _( E
enddata 5 m& F5 N0 R: ?3 G
min=@sum(level:p*z); + o( u3 m8 j: X, K
p(ctr)=1; , q. Z7 R% f D
@for(level(i)|i#ne#ctr:p(i)=0); 0 i2 }( A* H; J
@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)));
" P- F. }9 r3 c' u% W% e: ^0 @5 O* C& V end
1 v# u0 E- K: U4 A u/ |0 ?
0 P9 [/ R, `4 ~; X
$ U/ {8 u) S5 N! x/ b; i; V0 x : s- |) d* }. N) t$ [- w
& A8 s8 q0 e( E
2 L. {: h$ m% J 4 多标规划的 Matlab 解法 多目标规划可以归结为
2 L) U2 L' S& X! v9 `
" [$ D# o* m( U: }) K7 a: m- g
+ A0 Y/ T- d ~/ I; K* I [x,fval]= fgoalattain('fun',x0,goal,weight)
, h. S% ~- k( w1 o0 b0 @0 L [x,fval]= fgoalattain('fun',x0,goal,weight,A,b) 4 p4 {+ i* R% c1 a( z: R- X
[x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq)
/ C) U9 p7 m _ [x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) ' L& l1 l5 \$ j9 `4 b
5 H* y9 U* v/ N' F. e
( l2 U+ X+ _4 ^) L" h! p/ m
要完整掌握其用法,请用 help fgoalattain 或 type fgoalattain 查询相关的帮助。 * y' i. C# e, x0 a$ k
例 5 求解多目标线性规划问题 ( i$ q6 j- n& S1 e [: V
! ?# }1 ^. h0 i$ I2 g/ m$ j
- K3 Q1 R+ f! `, \" ~. l% ]
: E! y! X: T7 N4 T. \+ r) v6 J
解 (i)编写 M 函数 Fun.m: f! z8 Z P2 { c
6 p- h: T* h7 z7 q6 F7 x: V
function F=Fun(x);
$ h1 _: Q, |' a
' L* ~6 D* v1 H' C% m9 a+ Y1 I4 @5 y F(1)=-100*x(1)-90*x(2)-80*x(2)-70*x(4);
, ~8 d# W, Z* ^: v* P/ W" X6 b, _
/ b) r3 y2 M1 M. b4 c F(2)=3*x(2)+2*x(4); 7 N# Q. G; d1 r& v
" t2 F& r0 x: W" m/ u6 m: d1 Q
(ii)编写 M 文件 1 M/ I% G1 {+ e! v- P. L
6 e3 H9 i. l/ S( U6 n( L a=[-1 -1 0 0 : B' k. W1 F5 k( f; d
0 0 -1 -1 % u2 O2 i0 {$ m0 I: y5 d
3 0 2 0
' j* k, t% _- |8 X+ _. @6 ~7 ` 0 3 0 2]; 9 W1 J( s& t9 r0 s6 M3 z
b=[-30 -30 120 48]';
% V6 j7 s5 z" C6 E c1=[-100 -90 -80 -70];
" U7 E* \' Z. R2 i( @$ h9 v c2=[0 3 0 2];
( N* A' f. F$ m0 b2 S( C$ l [x1,g1]=linprog(c1,a,b,[],[],zeros(4,1)) %求第一个目标函数的目标值
' m y9 _8 o0 ~" A! f [x2,g2]=linprog(c2,a,b,[],[],zeros(4,1)) %求第二个目标函数的目标值 |, [6 d/ s# N0 x' L
g3=[g1;g2] %目标goal的值
2 d1 @9 D+ N5 E5 A) n [x,fval]=fgoalattain('Fun',rand(4,1),g3,abs(g3),a,b,[],[],zeros(4 ,1)) ! }* U- I5 t5 y8 k. J0 Q' d" ?9 o
%这里权重weight=目标goal的绝对值
* z1 K5 f6 D$ L $ a8 K. w5 X9 j* I. M F5 B( i
就可求得问题的解。
习题 . W+ t# d7 A8 ~1 z: |( u
: D* f" Z% }* [; P
5 ]' w7 z* x! F4 I( T5 V5 l
————————————————
9 W% X' z. Q! L 版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。0 Z: X; S# k* O" |& a1 s& o
原文链接:https://blog.csdn.net/qq_29831163/article/details/89488932
2 d% S/ f# @- m0 V& J 3 i1 Q7 H- n9 k# k& R
; g) I- ^4 g8 ?9 T/ p; v6 ^
zan