QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2425|回复: 0
打印 上一主题 下一主题

[建模教程] 目标规划模型:求解思路、序贯式算法

[复制链接]
字体大小: 正常 放大
浅夏110 实名认证       

542

主题

15

听众

1万

积分

  • TA的每日心情
    开心
    2020-11-14 17:15
  • 签到天数: 74 天

    [LV.6]常住居民II

    邮箱绑定达人

    群组2019美赛冲刺课程

    群组站长地区赛培训

    群组2019考研数学 桃子老师

    群组2018教师培训(呼伦贝

    群组2019考研数学 站长系列

    跳转到指定楼层
    1#
    发表于 2020-6-1 15:20 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta |邮箱已经成功绑定
    1.线性规划的局限性, a) s- p8 M5 e" T  \4 a3 h
    只能解决一组线性约束条件下,某一目标只能是一个目标的最大或最小值的问题。
    / N: C) f  g+ p$ p% n- D/ ^( M0 C2 u3 A/ y" y
    2.实际决策中,衡量方案优劣考虑多个目标
    ' D+ n7 z4 H$ j. k5 M: F4 Q. \这些目标中,有主要的,也有次要的;有最大值的,也有最小值的;有定量的, 也有定性的;有相互补充的,也有相互对立的,LP 则无能为力。* `# K: H" k. n% `! d( `5 S) a3 l8 G
    5 Y7 b% m+ y  H: U) R& M. u2 M
    3.目标规划(Goal Programming)
    , e, @) T, p/ G: D" V: b美国经济学家查恩斯(A. Charnes)和库柏(W. W. Cooper)在 1961 年出版的《管理模型及线性规划的工业应用》一书中,首先提出的。
    5 q/ {/ T( _$ A* Y3 _7 t, s
    - ?2 b) i' o1 f. z& [4.求解思路$ G4 A5 }9 d5 C% X! Z+ u
    (1)加权系数法
    6 _  S- A  L( [7 w为每一目标赋一个权系数,把多目标模型转化成单一目标的模型。但困难是要确 定合理的权系数,以反映不同目标之间的重要程度。: Z# A% H( B4 f: y

      F. N' X& i  D, [2 b; @(2)优先等级法
    2 ^) _+ {9 y! X0 F9 N将各目标按其重要程度不同的优先等级,转化为单目标模型。; ]! \5 f1 m+ ^$ b
    0 x1 h; R( C6 D5 T
    (3)有效解法0 H7 F( |9 _0 ?. |2 F/ h: ^
    寻求能够照顾到各个目标,并使决策者感到满意的解。由决策者来确定选取哪一个 解,即得到一个满意解。但有效解的数目太多而难以将其一一求出。
    4 Q2 f+ o2 L2 G' ~; X+ @4 W, L+ j2 N- |- l/ `7 }3 A" @
    2  目标规划的数学模型) ^& n" z8 |9 v+ b8 Y
    为了具体说明目标规划与线性规划在处理问题的方法上的区别,先通过例子来介绍 目标规划的有关概念及数学模型。0 O9 Y2 D1 e3 {9 P
    2 f9 ?+ f0 M4 V( `, t
    例1  某工厂生产 I,II 两种产品,已知有关数据见下表 ,试求获利最大的生产方案。4 @! R5 ~' J' T  U- ?* ]1 G$ _1 w

    + T  U$ |0 E# }) ?( k( W  K% y( O
    : g9 B" y! E/ P) i
    解  这是一个单目标的规划问题,用线性规划模型表述为: / m" j  t. F! |5 e, V
    , n' f. j9 i+ ]5 e
    ) t  v( I( `- L  @$ k

    , ^* G$ }  ]8 S# P8 C; F. a2 |- F但实际上工厂在作决策方案时,要考虑市场等一系列其它条件。如
    % O4 F8 ]1 Q9 X
    # `! ^1 Y& z6 @, g1 ?(i)根据市场信息,产品 I 的销售量有下降的趋势,故考虑产品 I 的产量不大于 产品 II。- V" w: r( m$ J& d1 r# t

    $ C) m/ _  n6 k' T(ii)超过计划供应的原材料,需要高价采购,这就使成本增加。  `: p* B* N& E- h

    ( P+ P; E' v, _0 |- `# x5 G( ^(iii)应尽可能充分利用设备,但不希望加班。
    ' X  u+ [7 k7 _  }8 L- M- u; p  p) |  [' q  q* s  J6 v3 m
    (iv)应尽可能达到并超过计划利润指标 56 元。: }, Y3 g/ h5 i3 Q0 f

      C- L3 r- @% c6 X  [这样在考虑产品决策时,便为多目标决策问题。目标规划方法是解决这类决策问题 的方法之一。下面引入与建立目标规划数学模型有关的概念。 + N+ {8 L+ y. ^2 U) L# P6 c0 e
    ; L' `8 {9 C" S* P7 j; [
    1. 正、负偏差变量
    $ w& x9 d: s" i* R9 Q* \5 D
    # v- a: ^( r! L& o( t" |1 d4 J
    1 x; O2 }2 v- V1 K! Q0 K9 E( J, s  v$ E" c
    2. 绝对(刚性)约束和目标约束
    ' N( _  R. l; [  }% X- [- w( H2 C$ X+ h$ o6 I* X* F+ M0 m
    ! o7 M- ?* Y) P
    ' U2 r2 d6 I3 b" e3 v
    3. 优先因子(优先等级)与权系数
    : o. [  Q4 o: m9 x
    8 a' }) f; q! o
    ; |3 h5 c! S% C1 j, z1 u- |7 V
    2 L# J9 e# {# T" ^6 ~9 _" {1 y" [8 p* c3 a
    4. 目标规划的目标函数 - y, T6 w: p1 Y; ]/ ]# }$ I

    - z+ f: n' L% H6 i6 a9 C/ ?# W% q* r! H
    ) K, p0 u* @% Q0 t  M
    对每一个具体目标规划问题,可根据决策者的要求和赋于各目标的优先因子来构造目标 函数,以下用例子说明。
    ) ~% J' p; Z6 Z, x( s. y$ Z/ t- Q. }% l6 U& [* ~
    例 2 : 例 1 的决策者在原材料供应受严格限制的基础上考虑:首先是产品 II 的产 量不低于产品 I 的产量;其次是充分利用设备有效台时,不加班;再次是利润额不小于 56 元。求决策方案。 解  按决策者所要求的,分别赋于这三个目标  优先因子。这问题的数学模型是  
    / M, v) |* a  M5 t& D4 Z. i' e: j" l" e7 \
    * P5 }+ B2 m2 ^8 }7 U) c- O- \

    4 M- E; Z( r3 y  ?3 x5 w# _8 M+ L- |5.目标规划的一般数学模型. x6 y6 `; w' Q- W$ m" y: J
    1 |; j. }" S0 b, Z
    * m5 J- f3 D: W* X
    % Z9 J1 ~6 H+ T" r
    2 e6 _9 U- p& _- R  u' C
    建立目标规划的数学模型时,需要确定目标值、优先等级、权系数等,它都具有一 定的主观性和模糊性,可以用专家评定法给以量化。
    1 E8 |; n7 F& a  T
    ) G% Y( n/ [- ~0 u6 t3  求解目标规划的序贯式算法7 p6 t- a1 g8 [& G4 ^$ g
    序贯式算法是求解目标规划的一种早期算法,其核心是根据优先级的先后次序, 将目标规划问题分解成一系列的单目标规划问题,然后再依次求解。
    ! H( X4 A2 i3 u# e
    . K' c1 ~/ `* v* g+ i  z: l; e! n- c- _0 u# K2 p) p

    - X3 `4 ?1 R) C: a6 @# ]5 B0 L1 E) t  |* ~9 \7 ]- z

    8 ^. K& ^5 L* U" _& b' v注  此时最优解的概念与线性规划最优解的概念已有所不同,但为方便起见,仍 称为最优解。
    " s* C3 l2 {% \/ K$ L' C0 M
    8 q. r6 [  L  Z( t" R例 3  某企业生产甲、乙两种产品,需要用到 A ,B ,C 三种设备,关于产品的赢利 与使用设备的工时及限制如下表所示。问该企业应如何安排生产,才能达到下列目标:
    5 `! J6 R! P' }
    3 q' U: `. z% X, q* A3 D9 ~" ^: R( W5 g% w1 F

    1 b4 ]5 ~' Z, b! e! Y(1)力求使利润指标不低于 1500 元;9 X7 m* }; f" C  ^% j( g
    & C2 G2 d, z: S! H( e! Z- d
    (2)考虑到市场需求,甲、乙两种产品的产量比应尽量保持 1:2;  j; S) o+ a$ i/ C
    2 d+ H& z, z5 B& D9 Y9 i4 M
    (3)设备 A为贵重设备,严格禁止超时使用;6 @; p; a. c* }% H3 Z8 N6 m

    . l; c1 x5 `/ k" @(4)设备 C 可以适当加班,但要控制;设备B 既要求充分利用,又尽可能不加班。 在重要性上,设备B 是设备C 的 3 倍。
    & L; Q  e) r  X0 {* |6 Y* ^% ^/ j$ J# [& c
    建立相应的目标规划模型并求解。$ m& q" E. V% S* ~6 }
    . u; y% i# O8 P% }- F2 l% H1 `: T) C( O
    解  设备 A是刚性约束,其余是柔性约束。首先,最重要的指标是企业的利润, 因此,将它的优先级列为第一级;其次,甲、乙两种产品的产量保持 1:2 的比例,列为 第二级;再次,设备 B C, 的工作时间要有所控制,列为第三级。在第三级中,设备B 的 重要性是设备C 的三倍,因此,它们的权重不一样,设备B 前的系数是设备C 前系数 的 3 倍。由此得到相应的目标规划模型。
    - S) I% s! d0 l2 N% b6 E( ^
    : X& N7 E4 @; S; y
    ( R0 g! [* f8 n
    ! ]1 m, k3 h* ~( e序贯算法中每个单目标问题都是一个线性规划问题,可以使用 LINGO 软件进行求 解。 求第一级目标。LINGO 程序如下:
    5 ~  ]0 R: A, X$ R# ]& q; }0 I! B0 R2 c7 C8 z: ^' G
    model:
    " N7 h1 `$ y+ ]+ y1 Z7 Usets:
    ' U5 }$ T7 @" Yvariable/1..2/:x; " T- c' }" k8 J3 @1 w' ~( A2 \
    S_Con_Num/1..4/:g,dplus,dminus; ' f# d7 G8 Y* C4 `% I
    S_con(S_Con_Num,Variable):c; 7 _1 {' @- _  ?' p/ G$ e& c
    endsets ; G* @3 f* ?9 M: S0 y& O7 X
    data:
    ! c9 A' y5 c' z# s$ @' Y2 W* ]g=1500 0 16 15;
    . m( Q$ U9 o! T" qc=200 300 2 -1 4 0 0 5;
    , e  |; H' t' Y( Z  Z1 E) uenddata
    % r: C# |: j2 k5 \- Y( z% p+ amin=dminus(1);
    , v3 `$ O# ^" K& A- [2*x(1)+2*x(2)<12;
    , N: O, k6 V7 W2 E$ A$ R3 |( b# T@for(S_Con_Num(i)sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i)); * g1 [2 X3 J9 m6 j
    end; C! o4 j( \8 A

    2 o; G/ {: }& \+ }& A( {1 |

    求得 dminus(1)=0,即目标函数的最优值为 0,第一级偏差为 0。

    求第二级目标,LINGO 程序如下:

    model: 8 |- r% b) z1 n
    sets:
    9 x6 |- [" x" E% @; L* Nvariable/1..2/:x;
    ) Q% I, m, f/ F4 H8 wS_Con_Num/1..4/:g,dplus,dminus; $ d; i  b+ h, M4 H
    S_con(S_Con_Num,Variable):c; 4 Q3 F- a; |1 F7 a1 k) q* L
    endsets
      Z5 A7 }; P$ P$ gdata:
    , q: T! H5 F  Q0 kg=1500 0 16 15; 8 |0 w; m& \8 w
    c=200 300 2 -1 4 0 0 5; 4 Q# E5 K7 R% Q' B
    enddata
      y4 L- K3 U6 J6 mmin=dplus(2)+dminus(2);    !二级目标函数; # r' u" d& H, [) ]3 }+ N
    2*x(1)+2*x(2)<12;
    ; `) r  B  P( ]( G; k: H6 u@for(S_Con_Num(i)sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i));
    2 U- p4 h7 Z% c) k" n1 rdminus(1)=0;!一级目标约束;
    . _- Z: a; U0 N4 w3 n' Y@for(variablegin(x));
    3 J: Q* `. l6 i/ |: T9 m2 tend
    1 y! _, y! Q+ H. y. H' @& t4 V+ i: S
    求得目标函数的最优值为 0,即第二级的偏差仍为 0。 求第三级目标,LINGO 程序如下:
    - f, \$ t' E4 k
    1 e  t" Q4 x0 o+ d# [2 B( `' xmodel:
    $ `( s8 a/ \0 g7 c! rsets:
    - _+ Z! h1 z1 |/ y+ o- Qvariable/1..2/:x;
      {! w% i) ?5 r3 ^4 U2 c/ L! WS_Con_Num/1..4/:g,dplus,dminus; ! h  _. N/ z$ G+ |0 U9 \
    S_con(S_Con_Num,Variable):c; & d4 A4 u% F" V7 X: {  @9 M6 p
    endsets 7 @3 b. }7 R) o8 R% c" x0 Z$ N
    data:
    , S( K% d/ d7 K5 i! T8 Qg=1500 0 16 15;
    + s! B3 \5 h3 q+ pc=200 300 2 -1 4 0 0 5; # ^# \3 ^; @/ [, H* @7 h1 K
    enddata * X7 ?$ B3 H$ |% \2 z2 t; k' D
    min=3*dplus(3)+3*dminus(3)+dplus(4);    !三级目标函数;
    ( q, v% I$ c; n# B: T4 \' h! i2*x(1)+2*x(2)<12;
      Y% ?1 {. d8 S5 c: m, l" s @for(S_Con_Num(i)sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i)); $ d8 K- r- x! Z
    dminus(1)=0;!一级目标约束;
    8 _$ ]& b5 E% H" E0 Udplus(2)+dminus(2)=0;!二级目标约束;
    . d. ]% p7 h/ W! e9 p, i7 h( Yend
    ) W- l8 k0 U. e% o) ?9 @) `, Q. J" v( g- r" Y% C5 @- M
    目标函数的最优值为29,即第三级偏差为29。
    * t( S* p# k: |5 s) e5 L$ |9 q! X) Y- h
    分析计算结果,  ,因此,目标规划的最优解为   , 最优利润为1600。. g# }/ {1 S4 Y& K6 W# p; ~
    , p" ~  ~' i( [0 Q) E5 m
    上述过程虽然给出了目标规划问题的最优解,但需要连续编几个程序,这样在使 用时不方便,下面用 LINGO 软件,编写一个通用的程序,在程序中用到数据段未知数 据的编程方法。
    ; w; @, P: a: l7 s6 u$ ^, L# p1 j% t3 M
    例 4(续例 3)  按照序贯式算法,编写求解例 3 的通用 LINGO 程序。
    0 S2 l9 }6 d" S6 p1 u7 G* C# H7 E# a% R1 `/ s
    model: 4 Q; l/ R2 q. J" S
    sets: 9 L0 K0 E1 z0 `1 P/ E
    level/1..3/:p,z,goal;
    3 k* I% Q! o2 f( Q/ Jvariable/1..2/:x;
    - K) s  {* [6 L5 b, s+ j* zh_con_num/1..1/:b;
    2 Z# d* d" G" M- Ds_con_num/1..4/:g,dplus,dminus; 7 Y) ^1 H0 A% a: M0 P
    h_con(h_con_num,variable):a;   p0 D* z- d! j, Z
    s_con(s_con_num,variable):c;
    5 ]% n. \6 o/ s+ y, W" b8 Uobj(level,s_con_num)/1 1,2 2,3 3,3 4/:wplus,wminus; - l# {0 K2 z3 O& \1 r5 ?9 X/ \$ g
    endsets % B7 ~" F+ f0 O1 {, S6 h) J
    data: 2 Q* V% m- _2 Y7 F  v9 \6 j3 `
    ctr=?;
    ( _7 A! h9 V0 x9 W' I% Z6 hgoal=? ? 0;
    $ \- b* x5 B1 ?+ L# U: u( E- h# bb=12; 6 L2 }2 @3 |# R- j8 G2 D
    g=1500 0 16 15;
    3 N; a9 u2 O! |* s0 ua=2 2; 7 w2 k+ J: ?* J0 `
    c=200 300 2 -1 4 0 0 5; : G0 P0 H9 K8 C( S% @4 n' W; V; |
    wplus=0 1 3 1;
    5 r5 Q- |0 G- j4 [  u& ]wminus=1 1 3 0;
    ( S! V0 S2 J. r6 w: @enddata
    + W: v3 P; ^6 s3 _( J( `5 Rmin=@sum(level:p*z);
    6 ~' V& Y; {+ {- b1 U0 e' ]p(ctr)=1;
    8 e- s: I2 k& k+ q# y@for(level(i)|i#ne#ctr:p(i)=0); $ x. o8 _  Z- h1 Q  t% d
    @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)));
    ; L2 V4 P! {. t$ H4 eend
    6 m5 ~' x7 k" `" ^$ Q+ D
    ! e$ u/ P. ?0 m: w2 G  h4 L8 m/ w  A8 h$ Y4 P$ m

    3 O* F) y4 u) S6 A) |$ w4 x& c3 Z
    $ c9 [* J( r/ U9 h9 L5 }* s
    3 n# I5 e! E6 H$ [0 X/ l) Q4  多标规划的 Matlab 解法

    多目标规划可以归结为


    * v- x6 u( j: l  m5 @7 _! m# |8 |' j: K- M% O
    ) o7 ?  i1 h3 s6 }* w. P
    [x,fval]= fgoalattain('fun',x0,goal,weight)           ) O- M# ?3 S' m* |% d
    [x,fval]= fgoalattain('fun',x0,goal,weight,A,b)           % X2 c- H7 e) G: N( G
    [x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq)           
    : Q8 f( o6 E& s+ p[x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)
    5 L' Z4 O4 K; |, x
    , S5 M' {* {* \9 \/ W  V  w: x, q, m# H* L; \7 a; a, _1 X, t/ [6 W
    要完整掌握其用法,请用 help  fgoalattain 或 type  fgoalattain 查询相关的帮助。
    ( {2 f8 j! T3 l* n 例 5  求解多目标线性规划问题
    & Q6 N3 b( T8 ]- m4 O7 A8 z
    9 W1 ^2 X1 z4 ?
    . P9 T, b$ }, n' s4 Z9 L# h2 J' f$ I/ k5 ?$ G% o
    解  (i)编写 M 函数 Fun.m:
    + b2 ^1 w& l' c- I
    ( E! Q6 {. u8 Y4 `! X8 Ffunction F=Fun(x);
    1 R9 D" I, e; o: ^2 p( q) u% k, W, G& y% Z& w
    F(1)=-100*x(1)-90*x(2)-80*x(2)-70*x(4); 1 `2 E) n3 }9 c
    + y' n# ]8 ]% s, L/ y
    F(2)=3*x(2)+2*x(4);
    7 K: G8 P9 b/ |
    3 A5 u8 Q& M6 W3 s1 X1 G4 Q(ii)编写 M 文件
    * w2 A$ U1 K9 M9 y) l9 F  @; [5 e; {
    ; j' k( e& C& W0 ?( v: d1 Ma=[-1 -1  0  0   
    0 ?# g3 z" S3 w, I  U; h   0  0  -1 -1    5 j! f; J; Q1 q; S! r5 ~8 U
       3  0   2  0    # T4 A# Q. ^% J
       0  3   0  2]; % j! {& o' ]! H8 ^1 ^- ^
    b=[-30 -30 120 48]'; 3 @3 U* ^4 J5 g+ D! V) R* U3 w  M3 w
    c1=[-100 -90 -80 -70];
    . @+ ^6 \, e* r/ u& V; {8 ic2=[0 3 0 2]; : V* N) [# {# |% J/ d3 w
    [x1,g1]=linprog(c1,a,b,[],[],zeros(4,1))  %求第一个目标函数的目标值 1 ^: v4 H# D- P
    [x2,g2]=linprog(c2,a,b,[],[],zeros(4,1))  %求第二个目标函数的目标值 0 z. L% @, _+ [
    g3=[g1;g2]  %目标goal的值 ; f0 C" r" _( X# n8 L$ z
    [x,fval]=fgoalattain('Fun',rand(4,1),g3,abs(g3),a,b,[],[],zeros(4 ,1))   V# K. F8 Z% R! l
    %这里权重weight=目标goal的绝对值
    " T3 @2 b" w6 c7 \& _, u/ G) m4 }- l, d7 {' Q$ @, z

    就可求得问题的解。

    习题
    / J! u) a4 C: N; g
    ; n( M7 l: l! h  |! {$ W' M
    8 ~+ z) [  W: ]0 _————————————————# W' }' m. L( g! N" p
    版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    # t9 {, K: G) K$ w$ k' S# M7 K原文链接:https://blog.csdn.net/qq_29831163/article/details/89488932
    " `0 D- J7 R% d( v8 b
    4 A5 P' v  `" [+ c& t2 |) h
    3 [# d" C. x+ v
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-7-29 06:23 , Processed in 0.317062 second(s), 50 queries .

    回顶部