- 在线时间
- 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.线性规划的局限性
1 k" z* o& I9 p0 `, f8 a只能解决一组线性约束条件下,某一目标只能是一个目标的最大或最小值的问题。, J# i1 w1 z4 Z6 S
. ^! }* Q# J) x) _ 2.实际决策中,衡量方案优劣考虑多个目标* J9 L" `! |; O
这些目标中,有主要的,也有次要的;有最大值的,也有最小值的;有定量的, 也有定性的;有相互补充的,也有相互对立的,LP 则无能为力。
$ _$ T! n3 r) _8 v! m; n" y9 f, c: W+ D- u. I9 `
3.目标规划(Goal Programming)
$ X: v7 ~5 w9 h' Q$ ]/ h |' b. W, H美国经济学家查恩斯(A. Charnes)和库柏(W. W. Cooper)在 1961 年出版的《管理模型及线性规划的工业应用》一书中,首先提出的。% I! ]' D, o) E
1 u6 c4 R5 V6 e6 F- J2 v1 j) w
4.求解思路# @4 `; m2 P$ |1 f: L
(1)加权系数法5 m# x7 A1 Y$ F) t4 _
为每一目标赋一个权系数,把多目标模型转化成单一目标的模型。但困难是要确 定合理的权系数,以反映不同目标之间的重要程度。
8 m$ R' e2 f8 Z- p
7 W7 i, E5 B+ ~ P% l1 }5 E3 F8 @& f(2)优先等级法7 I8 `4 P- p7 F% ~0 b7 _5 u# [$ h
将各目标按其重要程度不同的优先等级,转化为单目标模型。
/ A" m! R* l" Y- L I: }, _
' x6 _7 y4 \9 e; @' Y% a/ r) B$ M- c c(3)有效解法
# o5 p* G0 t+ s8 n! n% r寻求能够照顾到各个目标,并使决策者感到满意的解。由决策者来确定选取哪一个 解,即得到一个满意解。但有效解的数目太多而难以将其一一求出。 ; P( [: w+ Y' E [. p* E
, U0 V. F2 N; t5 Z
2 目标规划的数学模型
; s$ a# h3 Z# o' d# W$ S0 y- H2 w为了具体说明目标规划与线性规划在处理问题的方法上的区别,先通过例子来介绍 目标规划的有关概念及数学模型。
9 `* Q1 O, f Q. _3 g- l- v8 A! `' [6 F, K, o4 a9 O' T
例1 某工厂生产 I,II 两种产品,已知有关数据见下表 ,试求获利最大的生产方案。1 }* U# u9 ]) g5 `* @+ k' T/ L
# f4 h, z3 D' e( Y; p) g) G2 m![]()
/ @* o3 Z8 t2 j8 x; z8 _! H/ Y6 a! C( M- V0 L) f
解 这是一个单目标的规划问题,用线性规划模型表述为:
5 J- s8 L5 k y; p$ m) S
9 |3 t7 ?, r- |3 p2 n ?) K. s) v![]()
6 Z2 [5 J2 [# d; x/ W; U- ^& G6 A
/ d* l" M6 f4 h- F% @% N但实际上工厂在作决策方案时,要考虑市场等一系列其它条件。如
) B7 G3 `7 [4 N4 A; i; @# i5 [. U+ k, B4 F9 K
(i)根据市场信息,产品 I 的销售量有下降的趋势,故考虑产品 I 的产量不大于 产品 II。5 M, _' J0 v1 q' n
* C! l! ^+ O% l: |
(ii)超过计划供应的原材料,需要高价采购,这就使成本增加。, U" @/ ]1 e: v1 O* L) i" e
/ D/ r& g" d3 H- {3 @
(iii)应尽可能充分利用设备,但不希望加班。
q+ c+ i) \% H- q( Q- B1 p
) F8 t5 L2 \8 @(iv)应尽可能达到并超过计划利润指标 56 元。
5 p8 J4 [4 r$ `) U {2 a4 H* W- |, U2 P
这样在考虑产品决策时,便为多目标决策问题。目标规划方法是解决这类决策问题 的方法之一。下面引入与建立目标规划数学模型有关的概念。 6 g j+ `6 B3 f0 v* K$ ^2 W9 ~
8 i; O2 i* j! K1. 正、负偏差变量 : B" d9 H' o( T' Q f! ?
( } @" s5 e( Q! D0 q+ X$ Z 4 l: v: D, [6 b) n, R- ^
; Q6 s: h P. f" Z2. 绝对(刚性)约束和目标约束
2 S* l( D9 ^6 w6 O( I w' w6 i, w
) B4 t" k, P; b: g5 A
0 e& I4 c3 @8 t3 o5 s3. 优先因子(优先等级)与权系数 ; Y3 ]' P4 F$ A" v3 q
" i/ o1 _4 s: \6 F* w( S) \& a' D
; N& Y: b4 e* w0 t: ~
! G. y$ |$ P8 S
" c& r7 V! @6 a
4. 目标规划的目标函数
; F2 q9 b! i; u6 x" h5 W
a2 _8 G+ }" y6 `) W3 ]- N![]()
- u: \/ i- q3 Y7 }& p5 M. u8 L" m5 o, k) E; a- m
对每一个具体目标规划问题,可根据决策者的要求和赋于各目标的优先因子来构造目标 函数,以下用例子说明。
* B5 w# F# j+ P [' a' P+ B) f" r; t/ G
例 2 : 例 1 的决策者在原材料供应受严格限制的基础上考虑:首先是产品 II 的产 量不低于产品 I 的产量;其次是充分利用设备有效台时,不加班;再次是利润额不小于 56 元。求决策方案。 解 按决策者所要求的,分别赋于这三个目标 优先因子。这问题的数学模型是 : U% c' o5 k9 h' D7 R9 ^( X
" i& V9 }% c: h0 E5 b - l, y, q: L; f7 l! L' o6 ]
1 \3 e7 x/ I, t P" U9 a% j1 w5 n5.目标规划的一般数学模型6 k! R3 _, R* X0 z: ^, s# W
2 j. X. m! S- x) [8 O. E! v, W
2 D! a6 _4 ] J
( _4 O$ \2 v! ?! t
9 z9 T( I9 i+ { U3 U建立目标规划的数学模型时,需要确定目标值、优先等级、权系数等,它都具有一 定的主观性和模糊性,可以用专家评定法给以量化。
+ V4 o/ W5 s& L: Q! \
7 Y( ?* _% s, J$ q e& N) d) O3 求解目标规划的序贯式算法: L) I; ^! i) O2 f6 [: @5 p7 W
序贯式算法是求解目标规划的一种早期算法,其核心是根据优先级的先后次序, 将目标规划问题分解成一系列的单目标规划问题,然后再依次求解。
6 q$ X$ ?( t9 E, K
# ~) {9 G4 W6 V, t1 w4 a& g4 o![]()
0 ] w2 `9 @ {; g* ^5 o0 c% n+ q& y
3 e- ?0 |8 I8 u( @
; K% S& _6 l4 }" L( ]9 u. L注 此时最优解的概念与线性规划最优解的概念已有所不同,但为方便起见,仍 称为最优解。
& k( h" e3 k, W/ G. j
& V% }3 s5 H& W v" v# a" P0 g例 3 某企业生产甲、乙两种产品,需要用到 A ,B ,C 三种设备,关于产品的赢利 与使用设备的工时及限制如下表所示。问该企业应如何安排生产,才能达到下列目标:: Z, T) o* l, I) V8 Z: O+ _* G
. b$ M3 e% t; l& }1 D7 @& g" d' X; s 5 V3 X$ o, ]9 N' v
: }0 I1 `% _* ~/ i. L(1)力求使利润指标不低于 1500 元;2 Z; \, R/ {& H
! v- f8 V9 o2 K: @, l+ V(2)考虑到市场需求,甲、乙两种产品的产量比应尽量保持 1:2;3 \& h1 f" f: @5 w9 N$ x1 {" w5 h
1 Y' t8 V9 a1 L- M2 M+ Q+ ?0 ~
(3)设备 A为贵重设备,严格禁止超时使用;- s5 _8 o) ?# W: P' E
) m! z4 u) L- j2 J(4)设备 C 可以适当加班,但要控制;设备B 既要求充分利用,又尽可能不加班。 在重要性上,设备B 是设备C 的 3 倍。
6 [. u: M! x! Z; Q1 v0 M+ ?& `. r; a" R4 z
建立相应的目标规划模型并求解。2 P3 C3 Z( |- D7 ?" S' s3 f6 t ?
/ V* R7 @2 t! h5 I
解 设备 A是刚性约束,其余是柔性约束。首先,最重要的指标是企业的利润, 因此,将它的优先级列为第一级;其次,甲、乙两种产品的产量保持 1:2 的比例,列为 第二级;再次,设备 B C, 的工作时间要有所控制,列为第三级。在第三级中,设备B 的 重要性是设备C 的三倍,因此,它们的权重不一样,设备B 前的系数是设备C 前系数 的 3 倍。由此得到相应的目标规划模型。 $ K& M" a" `- m/ y- i
# N- J7 F u) b6 q; Y! h
![]()
/ S a. G+ |% v' v0 E k- A+ H+ p* N. B; J# m# Q8 H; D
序贯算法中每个单目标问题都是一个线性规划问题,可以使用 LINGO 软件进行求 解。 求第一级目标。LINGO 程序如下: ; F% a' R g4 s. B& [- _% C3 l$ C
( g5 t7 z* m8 u3 d( Y
model:
" L( l0 G5 ?# f. Z5 u% k5 I& wsets: - }, i4 b+ ^% N5 w" s, J- m
variable/1..2/:x;
9 N1 Y. h9 J& eS_Con_Num/1..4/:g,dplus,dminus;
6 r' I# w# p. A9 S' j, ]; rS_con(S_Con_Num,Variable):c; ' j5 |8 b7 W9 _! O0 X0 V
endsets ) C5 @) o# O* A; z6 v. [- R
data:
! a5 u, T* s; t, Cg=1500 0 16 15;
2 h% B Y5 r) M6 p1 `$ W2 L; o# Hc=200 300 2 -1 4 0 0 5; ! S7 L( v2 {$ `3 P
enddata
. f8 O. H F& z3 L+ l, N) E, kmin=dminus(1); 9 p- W, N7 W2 S, A B& I% {
2*x(1)+2*x(2)<12; + g- Y( Z$ Z: M2 I0 w0 a
@for(S_Con_Num(i) sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i)); Z' t9 Q' `* O
end
/ F( O! m0 K9 n( a; W
3 G/ X3 ~& o$ V5 l# \/ O; f$ m求得 dminus(1)=0,即目标函数的最优值为 0,第一级偏差为 0。 求第二级目标,LINGO 程序如下: model: 2 P' ?4 U, d0 [/ _; C j0 u
sets:
3 d; ~+ U; y( v" Dvariable/1..2/:x;
* u: X* b; u0 j3 G! c2 M+ n* e( DS_Con_Num/1..4/:g,dplus,dminus;
1 q5 m% j; m" r4 m7 }S_con(S_Con_Num,Variable):c;
! H& K9 Z* X4 l: ~' h' Hendsets
0 E0 Q. q9 _4 Q( _" Z* ?data:
|2 D4 \7 P* [( ]: |1 Z, _g=1500 0 16 15;
4 T/ |0 m( z- j) L6 N" b( `c=200 300 2 -1 4 0 0 5; J) g9 J7 V F# e! B! Y; Y! B& M
enddata
! e7 f( R, e3 n4 \7 Q4 ]min=dplus(2)+dminus(2); !二级目标函数; ) {- ^" M, ^6 Y0 `
2*x(1)+2*x(2)<12;
7 T2 K; d" j4 `9 c) }& w+ W) `- ]@for(S_Con_Num(i) sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i));
, ]5 _/ W- Y, Z/ ~! l! L, l' P3 x9 Q6 [dminus(1)=0;!一级目标约束;
. m( O, k" v6 `: Q9 r@for(variable gin(x)); - V T9 U' |- N( W' E$ [0 v
end
% w" T! W; z. m- ]6 [( O8 g& p; w& m3 ]: Z" Q/ W# ? }/ {
求得目标函数的最优值为 0,即第二级的偏差仍为 0。 求第三级目标,LINGO 程序如下:
% h) R9 B E' ^" c5 F& Q! z
+ m+ ~. ?9 ^ @ U1 B, |model:
% F+ ?& ~0 d, c0 p, {- Osets: : m7 G9 Q( B. p& \# _
variable/1..2/:x;
, F, n/ O" J% [$ A0 nS_Con_Num/1..4/:g,dplus,dminus;
) @8 I$ [$ M) k* t$ ^$ @S_con(S_Con_Num,Variable):c;
8 T' C- D+ u7 ]0 d9 L. n" \endsets
/ a. v# ]; X* C( C& }5 d/ Kdata: & x) u# X- H- a! t7 |" H9 ?
g=1500 0 16 15; 7 A. `6 f( w; w# {9 _1 o
c=200 300 2 -1 4 0 0 5; - \- W1 M$ Y2 X- @5 D/ d
enddata o# K! c1 I, n- p3 N0 g
min=3*dplus(3)+3*dminus(3)+dplus(4); !三级目标函数;
3 S, m9 a+ {( a6 v: X2*x(1)+2*x(2)<12;
- w" J3 g Q: f5 \* g1 i$ r4 M @for(S_Con_Num(i) sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i)); 8 P' l* E1 a* g7 P. A" K' Z
dminus(1)=0;!一级目标约束;
7 s8 w- c5 h. G( l, k+ G* @/ Vdplus(2)+dminus(2)=0;!二级目标约束;
- W0 P, R0 d* @/ r/ ]" l7 | xend ]( ~3 k }4 q: T2 G4 A4 m
/ W$ j" |. I. {. j4 Q; _
目标函数的最优值为29,即第三级偏差为29。 9 b5 X' n, \, n, h( h: G
; o+ P/ e9 j0 ~' _ O分析计算结果, ,因此,目标规划的最优解为 , 最优利润为1600。+ K" W9 N% _8 A7 ]0 M! t
& l. q. e2 d' H$ r: m* |8 l6 i* s9 K- c上述过程虽然给出了目标规划问题的最优解,但需要连续编几个程序,这样在使 用时不方便,下面用 LINGO 软件,编写一个通用的程序,在程序中用到数据段未知数 据的编程方法。. W B* {+ q% e: @
. s. n0 A' H- |0 K2 y! b
例 4(续例 3) 按照序贯式算法,编写求解例 3 的通用 LINGO 程序。6 I7 {# f9 J4 b( b0 H! s3 a# }5 |, k
6 M0 l, y+ W: x' U- S3 Mmodel: 9 E) s" \+ [4 e4 f% Q4 Y1 {" e
sets: 0 _: b. K3 Y' [
level/1..3/:p,z,goal; . ?/ V# x* x/ [
variable/1..2/:x; 6 B( s2 o% t; S5 z* m& h6 ^
h_con_num/1..1/:b; 4 q6 q, b( ` M3 C; g q
s_con_num/1..4/:g,dplus,dminus;
+ X* J; f5 ?0 x+ |$ t) lh_con(h_con_num,variable):a;
( u8 R: \/ i; f& Cs_con(s_con_num,variable):c;
( r! _' i0 l3 r! e6 Dobj(level,s_con_num)/1 1,2 2,3 3,3 4/:wplus,wminus;
( E. q- N1 E4 m* s2 vendsets ) g: @0 ?6 X8 r3 B) k9 k6 C
data: + B- `, n4 a0 G3 O9 {4 a; m% d/ i
ctr=?;
7 @, V; q4 s% a9 ~goal=? ? 0; ( u, o" r3 f* Q6 {1 c
b=12;
6 ~$ }$ @8 _5 ?) z' dg=1500 0 16 15;
! n& q7 Q! Q+ o* ra=2 2;
0 D$ m! q( ?( ~3 ?$ Hc=200 300 2 -1 4 0 0 5;
$ {) b1 t) c6 Y; j; Y9 hwplus=0 1 3 1;
3 V4 c0 v: C1 ], X9 T7 D" Pwminus=1 1 3 0;
4 [7 B# a! \7 a9 {: d9 V" f- Denddata ! X, d, N. v: x
min=@sum(level:p*z);
4 l3 R& f+ k) c# u1 F1 K" rp(ctr)=1;
2 H& ]6 g7 ]: ^- s( P@for(level(i)|i#ne#ctr:p(i)=0);
8 n, c; P0 {" @) k: d1 i@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))); 2 x% @2 V: e( N/ P" X2 ]
end
# |8 n$ ~' W4 m6 A: G7 D5 p; a* S" R) [& i
' q; f2 p" m6 q2 }7 y+ y( e0 q0 _
) K, m8 p3 h! A9 W
+ D0 J/ }; T- a- @2 ?
3 v3 |' y$ k2 V g: B5 `
4 多标规划的 Matlab 解法 多目标规划可以归结为
2 K9 R, g2 G3 `9 Q! X: m" u$ d- e 3 {+ A& ?/ i$ R% Q
9 L6 A/ D: T" [" k# T; v& R3 A# y[x,fval]= fgoalattain('fun',x0,goal,weight)
$ [9 s8 @7 G% A z4 n. T, W[x,fval]= fgoalattain('fun',x0,goal,weight,A,b) & t4 W# M s- `6 M6 [0 K. k4 q* h+ i
[x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq)
5 ~5 h, J: L" O4 H& ]: Q5 W( Z[x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)
& r9 j4 p( |6 B5 d- s- t0 M( R
' r/ _, o5 a n) a1 ~* L3 g. s* `0 N# ^1 o; q+ m0 X ?
要完整掌握其用法,请用 help fgoalattain 或 type fgoalattain 查询相关的帮助。; I$ K3 M* a0 a, H5 o* E# V4 S
例 5 求解多目标线性规划问题
: @$ N. Y' V0 y2 Y( `; N8 j5 S( g' _! {
![]()
1 l. ?# q4 V% P1 R8 G
, h+ ]9 l. u. N' X解 (i)编写 M 函数 Fun.m:
/ I" E& M; H) v# U @1 @: w' @5 {# b i5 @, T# g, v& Q& n F" v [
function F=Fun(x);
: Z, `/ m( M* d( q" e$ z+ k( j# T9 `# P7 d6 w
F(1)=-100*x(1)-90*x(2)-80*x(2)-70*x(4);
, _4 k. w8 u: g1 J4 `" v: Q2 @ Y: ]1 T! u. L+ m$ `
F(2)=3*x(2)+2*x(4); 8 F% {* ]3 p7 S/ d+ V' }" w/ u
! G1 H( n5 G" q* t' A H# J! H: M
(ii)编写 M 文件
4 Y$ D: v. U! N" p: Q9 X! @( f @% N8 x4 v9 l6 v; N: p2 w* w0 A
a=[-1 -1 0 0 ; C" U2 c5 Q2 l0 `! h' g ^' Y
0 0 -1 -1
8 C9 b) J1 g2 S; f5 q; Y 3 0 2 0
0 g8 F; v& B+ z2 E' {6 o 0 3 0 2]; & x: ^' A* h" j( I6 C6 s5 M
b=[-30 -30 120 48]'; ( m. z$ O! p' ?; @3 T3 z
c1=[-100 -90 -80 -70];
% h) A& ^, {9 a7 g4 `, s& w3 E* gc2=[0 3 0 2]; t. i/ h6 i* O# d* ^4 T0 e
[x1,g1]=linprog(c1,a,b,[],[],zeros(4,1)) %求第一个目标函数的目标值 ( }3 v6 r5 M; h, l+ q
[x2,g2]=linprog(c2,a,b,[],[],zeros(4,1)) %求第二个目标函数的目标值
; T# g0 J7 S" [3 xg3=[g1;g2] %目标goal的值 & C J5 I2 A' s; h9 E7 E1 w' s
[x,fval]=fgoalattain('Fun',rand(4,1),g3,abs(g3),a,b,[],[],zeros(4 ,1)) 0 v0 p8 K- n7 y
%这里权重weight=目标goal的绝对值 7 M1 z7 t; A! |( ?3 j0 `" C1 v0 a
( a. g& b. k! M- o" H* [
就可求得问题的解。 习题1 L0 Z" C6 R6 m6 p. A3 Y# N: L
( N+ t( R Q- I
( P4 a; N) l W! O" m8 y
————————————————8 E; h# R7 B& ~2 s4 I
版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
& L7 O0 J$ d# f" p: s0 f/ L: Y原文链接:https://blog.csdn.net/qq_29831163/article/details/89488932
" O; ^5 l5 Y: W$ G+ q* w; S8 j& A0 Q4 W8 _6 Y' r9 K# o
1 S' r& [1 U: Y+ `0 g: {4 V1 C |
zan
|