- 在线时间
- 791 小时
- 最后登录
- 2022-11-28
- 注册时间
- 2017-6-12
- 听众数
- 15
- 收听数
- 0
- 能力
- 120 分
- 体力
- 36125 点
- 威望
- 11 点
- 阅读权限
- 255
- 积分
- 13778
- 相册
- 0
- 日志
- 0
- 记录
- 1
- 帖子
- 616
- 主题
- 542
- 精华
- 10
- 分享
- 0
- 好友
- 225
TA的每日心情 | 开心 2020-11-14 17:15 |
---|
签到天数: 74 天 [LV.6]常住居民II
 群组: 2019美赛冲刺课程 群组: 站长地区赛培训 群组: 2019考研数学 桃子老师 群组: 2018教师培训(呼伦贝 群组: 2019考研数学 站长系列 |
1.线性规划的局限性
1 {' X2 T& Q( k7 X$ o只能解决一组线性约束条件下,某一目标只能是一个目标的最大或最小值的问题。+ l1 n/ ?" \0 K# k0 {
4 k; y) W4 A @, U$ u
2.实际决策中,衡量方案优劣考虑多个目标
* \" a7 T8 v: T" `( _8 B4 I( h3 }这些目标中,有主要的,也有次要的;有最大值的,也有最小值的;有定量的, 也有定性的;有相互补充的,也有相互对立的,LP 则无能为力。/ B) u' o; h1 ~2 V+ V A, \
! c( k9 ] X0 D- v! s0 k
3.目标规划(Goal Programming)0 B/ x4 ?1 W1 w8 l) \3 ^" x7 }
美国经济学家查恩斯(A. Charnes)和库柏(W. W. Cooper)在 1961 年出版的《管理模型及线性规划的工业应用》一书中,首先提出的。
: i% U4 s& w( ^" p- Y- L; C
9 R5 G/ {4 f/ p& q4.求解思路
3 R* A! u$ v; Y' t# H# Q(1)加权系数法+ v! j, z4 I8 P G$ m4 U
为每一目标赋一个权系数,把多目标模型转化成单一目标的模型。但困难是要确 定合理的权系数,以反映不同目标之间的重要程度。
a4 u2 @* Z" g3 n3 X6 e5 y# Z& @1 [
( a1 v! r+ Y1 i! U: p6 y9 k(2)优先等级法# v6 E& P" z7 u4 F
将各目标按其重要程度不同的优先等级,转化为单目标模型。
# n [6 e% v8 Z, w# M1 S9 F# L2 m2 V5 x. w8 W! L
(3)有效解法
Y4 X0 k$ g$ D- X; e6 f2 J) O寻求能够照顾到各个目标,并使决策者感到满意的解。由决策者来确定选取哪一个 解,即得到一个满意解。但有效解的数目太多而难以将其一一求出。 2 ~; f \3 j* N
2 P. @; k f+ m, Z+ A" f) N6 d$ T8 r1 @2 目标规划的数学模型4 u6 f) Q7 f4 _- Y$ V9 {
为了具体说明目标规划与线性规划在处理问题的方法上的区别,先通过例子来介绍 目标规划的有关概念及数学模型。
. r* K$ X+ x- m) N9 ]& Z
7 H( n+ D: w5 B e. S; a例1 某工厂生产 I,II 两种产品,已知有关数据见下表 ,试求获利最大的生产方案。
3 _3 P8 s, }5 [* M. t5 l; {/ f3 I" n. N/ k; Z* J5 v
+ U# s* I/ I4 T0 I
2 q: E' D' E U, x解 这是一个单目标的规划问题,用线性规划模型表述为: + R+ `# o1 P% \7 J4 k
$ W, E! l' k) ^- {# M" z; J![]()
0 _" J* o( \* K9 ^! z Q& L
$ W4 ^: g" E$ d& v" Q* X但实际上工厂在作决策方案时,要考虑市场等一系列其它条件。如
) V& \5 E- W7 T) S0 F$ U& T w9 j+ s0 i* W, s
(i)根据市场信息,产品 I 的销售量有下降的趋势,故考虑产品 I 的产量不大于 产品 II。
+ u: u, a& i6 e! Z& H6 d+ B9 \
9 i {9 h, W+ L" Q8 I(ii)超过计划供应的原材料,需要高价采购,这就使成本增加。0 H2 n9 d) v; l7 r) k1 t6 S
, S" E' i2 t( H* ~1 h3 Q3 L(iii)应尽可能充分利用设备,但不希望加班。 3 a9 c* ~8 G, Z) w+ F
; a1 x$ Q) G, R1 M2 |- E. [# m. n(iv)应尽可能达到并超过计划利润指标 56 元。# f* p0 B8 e T
2 Y+ v1 ^$ e) a8 p这样在考虑产品决策时,便为多目标决策问题。目标规划方法是解决这类决策问题 的方法之一。下面引入与建立目标规划数学模型有关的概念。 " t1 b7 w j. v# B( e6 c
! v0 {$ M6 N2 o" P3 N& w% c1. 正、负偏差变量 6 l) @0 I3 z7 Z. @, C
! y" L0 i5 Q$ R1 ~% {4 j" c
* m3 L' C- k8 a7 J" F; B9 E& w
! c% ~: h/ E/ _7 {$ H
2. 绝对(刚性)约束和目标约束 * V$ L0 z4 _2 R/ \! e; y
0 I2 [' M% `$ q2 E- o2 ?
![]()
1 n1 |' L+ l! B$ f( P; P( O& g1 Q* b: h2 J
3. 优先因子(优先等级)与权系数
6 L0 Z( K/ T: o4 F1 V! T
8 ~ m M) I6 |( g. U: `, ^0 J+ N8 _ , X9 ~3 S5 C6 X
. q8 }" }" a7 C2 N$ p
9 c- c6 f- Z8 f; w; A) M
4. 目标规划的目标函数 # |8 t4 G3 R |# p- E
3 [. u& ?8 U* D5 v
![]()
) E9 k' [# V; a, _9 N% e4 }
# D" U9 J2 F2 Q3 u: C- h+ u4 d, U对每一个具体目标规划问题,可根据决策者的要求和赋于各目标的优先因子来构造目标 函数,以下用例子说明。
! r0 A( l) v. u7 Z! G# v+ A9 A$ u, Q( U2 Q# A: A
例 2 : 例 1 的决策者在原材料供应受严格限制的基础上考虑:首先是产品 II 的产 量不低于产品 I 的产量;其次是充分利用设备有效台时,不加班;再次是利润额不小于 56 元。求决策方案。 解 按决策者所要求的,分别赋于这三个目标 优先因子。这问题的数学模型是
6 G6 J+ z2 ^ e
- Z F. u+ q8 i+ \; N2 |( j( D+ {![]()
X: w3 t' S4 v" G$ u
, D) s0 m; @# G6 S- Q. j, v$ X# {5.目标规划的一般数学模型
; Y3 i: W+ q/ u, j) }' Q* [4 ]
* h6 ?+ S9 Z5 R5 J. p * d9 M. g) K6 b, a0 @
7 @% P1 U& F' O5 |4 X, o: [
/ r/ f/ [- K# C3 W
建立目标规划的数学模型时,需要确定目标值、优先等级、权系数等,它都具有一 定的主观性和模糊性,可以用专家评定法给以量化。 0 r$ a% r: J+ g! W+ x W$ G6 o
" F: ~4 Y4 C- d0 J6 Y" f
3 求解目标规划的序贯式算法
. L! t Z: k% U, u5 F序贯式算法是求解目标规划的一种早期算法,其核心是根据优先级的先后次序, 将目标规划问题分解成一系列的单目标规划问题,然后再依次求解。
5 p$ [2 m2 e2 N% x, v# [9 c, X) d7 |4 U" ?/ z, d! n `
![]()
, j! |/ g- z0 n+ [8 k+ y$ x4 \8 y9 g5 R: C: |
4 Y1 w: j6 j! b2 S+ e, l1 Z
; t- H4 O8 o* H/ P
注 此时最优解的概念与线性规划最优解的概念已有所不同,但为方便起见,仍 称为最优解。 " I( V2 @/ K# T: U6 f
6 Q) z" [& T4 T# ^
例 3 某企业生产甲、乙两种产品,需要用到 A ,B ,C 三种设备,关于产品的赢利 与使用设备的工时及限制如下表所示。问该企业应如何安排生产,才能达到下列目标:4 T& E9 c7 ^3 G: l0 J% d
; U8 ^' e9 p) p! `. o6 M) \# |![]()
\4 P9 F% k1 d$ b4 t$ j
: M4 y- r$ y) K# E(1)力求使利润指标不低于 1500 元;$ c! i$ `. g& Q* O
1 Q& A' o( l# E) c
(2)考虑到市场需求,甲、乙两种产品的产量比应尽量保持 1:2;2 K' b% f) u: H2 D$ K* z
) R3 k! H/ A/ b6 }(3)设备 A为贵重设备,严格禁止超时使用;
8 W& L# g% ] \2 e) n/ y, n/ w6 J8 h0 ~) f. i) g& W
(4)设备 C 可以适当加班,但要控制;设备B 既要求充分利用,又尽可能不加班。 在重要性上,设备B 是设备C 的 3 倍。
9 w( B. p1 }0 l5 Y. O8 x; A
0 E5 c8 [9 n$ G: K9 c! B9 f; q建立相应的目标规划模型并求解。
0 W4 G" e9 j7 @! k9 f! O: X( Z" R; U$ a3 c$ H- @" k ?
解 设备 A是刚性约束,其余是柔性约束。首先,最重要的指标是企业的利润, 因此,将它的优先级列为第一级;其次,甲、乙两种产品的产量保持 1:2 的比例,列为 第二级;再次,设备 B C, 的工作时间要有所控制,列为第三级。在第三级中,设备B 的 重要性是设备C 的三倍,因此,它们的权重不一样,设备B 前的系数是设备C 前系数 的 3 倍。由此得到相应的目标规划模型。
3 N4 ^. e* Z+ y* V$ o3 c. r
1 G$ t5 w; r5 Y![]()
" A8 ]+ e/ n+ m
- J- ~5 E! m, J0 x: B( U+ Z/ ]9 t序贯算法中每个单目标问题都是一个线性规划问题,可以使用 LINGO 软件进行求 解。 求第一级目标。LINGO 程序如下:
% I! a4 F. v. \6 Q9 h6 r7 @9 }! ?( S9 w, ?: a: w$ o( P
model:
# l( ?# q1 y3 Z8 H% F( u5 H3 Gsets:
- o7 J, a5 w8 Z% Lvariable/1..2/:x;
& o- q( o T: l- m& y, oS_Con_Num/1..4/:g,dplus,dminus;
. y; n" x i' @& i7 X) s/ wS_con(S_Con_Num,Variable):c;
# s) l6 Q# a4 n+ Z( wendsets
0 M( \! J% e' O, X: Cdata:
1 t I! T2 v! @6 n7 @$ m# w+ fg=1500 0 16 15; 0 r' c5 ` Z9 ]2 [$ i
c=200 300 2 -1 4 0 0 5; / Y$ ?: Q& r5 M; v+ x. Q5 B9 ?
enddata a# F `6 J* c4 |- n, s5 j0 n
min=dminus(1); " C8 n* a# U* H' `' g/ U
2*x(1)+2*x(2)<12;
5 \ |' L i" B& v% b@for(S_Con_Num(i) sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i)); # Z8 k. k8 l0 }" P C0 k* R" r
end
. R+ p5 O; q+ {0 Z+ H1 F# |! s6 }1 y) [( [
求得 dminus(1)=0,即目标函数的最优值为 0,第一级偏差为 0。 求第二级目标,LINGO 程序如下: model: # l' T' S; ?% u( c% Z
sets: ! S& u- g3 A5 G+ o5 G, r
variable/1..2/:x; `' c* Z( j g+ ?
S_Con_Num/1..4/:g,dplus,dminus;
, D% U3 D. S! dS_con(S_Con_Num,Variable):c; # E# l( A5 d R4 {, ], F
endsets ( C* g4 u' u- x* }! N
data: * G8 C3 j' W% N8 G7 A* E# r1 I
g=1500 0 16 15; & k/ C0 N: c9 J! V7 y* G# i
c=200 300 2 -1 4 0 0 5;
' \0 x! T; s8 h4 senddata
, o3 ]0 u% P/ F fmin=dplus(2)+dminus(2); !二级目标函数;
) t4 K2 ?' r& f# `, S2 @2*x(1)+2*x(2)<12;
- t: q i5 ^( E- g( C@for(S_Con_Num(i) sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i));
" G' N$ Z8 O, Y2 u) Tdminus(1)=0;!一级目标约束;
& \" d5 Z2 R: f$ O* |@for(variable gin(x));
3 j9 T7 \5 N3 j; y- Oend 4 f% V6 K2 d" e c
. Z" ^4 z; I r( d7 W/ i z7 o求得目标函数的最优值为 0,即第二级的偏差仍为 0。 求第三级目标,LINGO 程序如下:
2 U) @+ Q# v5 U& V- b7 I, _# \# K' G7 K9 L w
model:
& L, D) d: t: o- asets:
9 [, |9 b2 [, k1 p# x/ [5 D2 ^5 kvariable/1..2/:x;
+ U, h9 y+ S( }* ZS_Con_Num/1..4/:g,dplus,dminus; 7 n; b! _- {# f0 t$ ]8 a
S_con(S_Con_Num,Variable):c; 0 j& V+ ^3 h, n" N8 H; u ^
endsets : O: w9 r- G. k( g
data: ( D, u# U& L. c! Z7 S2 z3 s* W
g=1500 0 16 15;
. {6 y2 L4 E$ j; qc=200 300 2 -1 4 0 0 5; 9 e* x7 @6 u+ Q
enddata ! B _: P* v$ _* z- s
min=3*dplus(3)+3*dminus(3)+dplus(4); !三级目标函数;
+ Z4 N% q, r" }4 Y3 r6 b2*x(1)+2*x(2)<12;
+ h& I; {5 L9 @3 m @for(S_Con_Num(i) sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i)); 2 I- r5 }! {" V6 ~" p
dminus(1)=0;!一级目标约束;
% {+ }% p* Y/ ?5 c! \dplus(2)+dminus(2)=0;!二级目标约束; 2 E( T9 N9 ~- s: x, n" c
end
" {6 `# I! X* B; y9 P9 x* |% M) V; o1 m& W% y& O2 L1 B
目标函数的最优值为29,即第三级偏差为29。 8 R& l! x( N6 j' z" {
% _9 B( z$ s' v. b. r$ q0 Z分析计算结果, ,因此,目标规划的最优解为 , 最优利润为1600。
' J! Y- v( w. L$ j! n; V
* m- h* z8 R4 E5 O0 [上述过程虽然给出了目标规划问题的最优解,但需要连续编几个程序,这样在使 用时不方便,下面用 LINGO 软件,编写一个通用的程序,在程序中用到数据段未知数 据的编程方法。. X% _, m3 F' Y% _. G. W7 |
- Y. f' |9 j- T- l: Z
例 4(续例 3) 按照序贯式算法,编写求解例 3 的通用 LINGO 程序。! f4 K/ M) R$ p, c8 i9 P
% k- k; Z, H0 ~$ g2 Vmodel:
0 T1 \6 t, J2 N1 u) u( Qsets:
7 W# E& K! g# xlevel/1..3/:p,z,goal; n, T3 S: ^9 C( z. ]) c
variable/1..2/:x; + H$ e4 b3 x2 }7 i( q$ d H
h_con_num/1..1/:b; , p& a: N4 h) l
s_con_num/1..4/:g,dplus,dminus; # O- T+ F0 c3 M% N7 D, {% \; J2 \
h_con(h_con_num,variable):a; 7 {1 H: V% z) {6 U* [
s_con(s_con_num,variable):c;
2 R4 M8 U# k( ?; H% eobj(level,s_con_num)/1 1,2 2,3 3,3 4/:wplus,wminus; / [4 z9 _: s. [8 i; M, |. ?
endsets * I# b: s6 f3 v; {3 S- n1 |% G
data: % m$ r {7 r8 d; a
ctr=?;
: l% C1 i/ V7 v8 m; c0 b: G9 N; \goal=? ? 0;
9 }* J+ L& h [1 F V' G- g4 ]$ Fb=12;
, e* ^# x! g( H% ^) M! K" w; \g=1500 0 16 15; ( {6 J2 v4 ^4 K/ Y3 d
a=2 2; . Q" Y* P7 Z7 z3 w; R% w
c=200 300 2 -1 4 0 0 5; ! u. |3 y" ]% s6 j
wplus=0 1 3 1; + s, }; P/ v2 V; X3 I" P0 C/ A
wminus=1 1 3 0; 5 r; }; Z# x. o6 _ v" T
enddata ! g' |' V4 i( _5 B
min=@sum(level:p*z); - ^2 L" V& H+ M) |7 `; m
p(ctr)=1;
, ^' ^* S1 q4 K+ I O@for(level(i)|i#ne#ctr:p(i)=0);
0 F. g! y* B2 Q: k8 ~1 R. u@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)));
" u: k; V( E& T3 m" Vend
Q$ f! x, E& p" C; r3 D0 |, l1 L+ k* X3 F6 `9 g" A; m( C
% D) i9 d% c' |5 S7 v+ {# X0 A) q. |& Q9 b
![]()
1 h+ B7 N5 k: e8 k& Y# l" _" u- m0 w) d4 B2 k" G) K5 @ E) ^
4 多标规划的 Matlab 解法 多目标规划可以归结为 - g E$ d# e+ M
9 I& y0 x# G: n! }1 @$ A7 f: P6 R
& O0 U' a7 q$ R, u" E[x,fval]= fgoalattain('fun',x0,goal,weight) : q' l; e0 x' |
[x,fval]= fgoalattain('fun',x0,goal,weight,A,b)
; K& i' A0 p: F5 |( ?: \. X4 }[x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq)
! |0 O' Q$ z- |[x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) ( D* a% {7 | r% M3 Y) W* i8 j9 \
A2 B! z' l) T
3 P. R7 O0 f! m, H- L. o要完整掌握其用法,请用 help fgoalattain 或 type fgoalattain 查询相关的帮助。
7 u, e5 R7 F- ^& r6 ^: A 例 5 求解多目标线性规划问题
3 K8 e, y% M3 }4 [; M J) H) q: Y! G
![]()
7 |- S9 @" w1 Y' ^
" H* |- l) k/ ?; [: {0 s解 (i)编写 M 函数 Fun.m: , W) @3 `9 O! e1 T; E5 Q, ~
! K9 B. s/ P3 `0 f& \function F=Fun(x); 5 S* K* d$ Y. r' W( o% s. P
% r/ z# a/ J& \+ e, D) V9 Q% |) ?
F(1)=-100*x(1)-90*x(2)-80*x(2)-70*x(4);
( d! W: V- N2 ^& \, |( E6 x- H" O
F(2)=3*x(2)+2*x(4); 5 U) m K0 g1 |/ ?3 _
+ @7 M: H) D4 @* U! P(ii)编写 M 文件
. ` T' ^) c7 G [9 P# W! [+ L
5 v3 Q* }" @5 qa=[-1 -1 0 0 A' n2 R/ U! H9 Q2 }/ [
0 0 -1 -1 ) k' g/ _' M2 `9 C4 C* I
3 0 2 0 : e! p; C" R$ o4 \* q) b- \
0 3 0 2];
?: a! I2 _+ K3 y' eb=[-30 -30 120 48]'; 1 J5 u; O# _0 q
c1=[-100 -90 -80 -70];
4 {# P5 y! e# f- p8 u% M) Fc2=[0 3 0 2];
9 a7 o/ B: G& v- T y# c3 U[x1,g1]=linprog(c1,a,b,[],[],zeros(4,1)) %求第一个目标函数的目标值
3 C( S. Z' Z. l[x2,g2]=linprog(c2,a,b,[],[],zeros(4,1)) %求第二个目标函数的目标值
: p7 L- e$ O& M" M% p) F' C* l$ @g3=[g1;g2] %目标goal的值 $ ~- s8 W% r5 t( E$ A2 y% m
[x,fval]=fgoalattain('Fun',rand(4,1),g3,abs(g3),a,b,[],[],zeros(4 ,1)) & Z4 I X9 Z. {! X
%这里权重weight=目标goal的绝对值
& Z2 e5 P& v5 ~0 y5 A
1 z1 T9 l7 Z: M, c9 M9 x就可求得问题的解。 习题6 j& o! l+ a& G" i7 Z! ^
![]()
- E4 \, d" o" j) c e3 D
: }, t6 m# E: t( X1 A% `% T————————————————' J( N; u; O& O# d
版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。' U9 c! d& `4 k7 ^2 J' Q4 g1 ]2 C
原文链接:https://blog.csdn.net/qq_29831163/article/details/89488932
- J6 P* h e$ I: e: Q& N; a; w9 b# B5 n+ C+ d
+ O" }5 O9 @) N* R+ A& A$ _1 H |
zan
|