QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2393|回复: 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.线性规划的局限性  {: U8 u3 l/ h5 u
    只能解决一组线性约束条件下,某一目标只能是一个目标的最大或最小值的问题。
    / J; Z3 {( {0 j4 p' M1 q0 R- _7 i
    " n1 K/ o3 j: f$ K9 Q/ j 2.实际决策中,衡量方案优劣考虑多个目标* v! y$ Q5 W% c  q4 s
    这些目标中,有主要的,也有次要的;有最大值的,也有最小值的;有定量的, 也有定性的;有相互补充的,也有相互对立的,LP 则无能为力。
    + L& E( q5 g: X' s! I7 \* z3 P* Q( h3 Y# V
    3.目标规划(Goal Programming)
    ! K# L# U7 z' j5 q5 y; m美国经济学家查恩斯(A. Charnes)和库柏(W. W. Cooper)在 1961 年出版的《管理模型及线性规划的工业应用》一书中,首先提出的。
      [3 c; l& Z3 I6 |$ }* O! E
    : `) _+ ]9 S7 E: [' {4.求解思路
    ( L& l1 f8 f6 @8 d(1)加权系数法$ [9 J3 Z) y& F. M( X
    为每一目标赋一个权系数,把多目标模型转化成单一目标的模型。但困难是要确 定合理的权系数,以反映不同目标之间的重要程度。
    ' F9 K9 U7 K* @5 n. O- R% U" B  V# l2 @! N& C
    (2)优先等级法" u$ z  c, x* b. c4 O% X
    将各目标按其重要程度不同的优先等级,转化为单目标模型。
    ; a1 `& @5 z& y" \5 s  _+ e- ?0 w3 R* a8 l: a+ O- `3 d; E
    (3)有效解法
    ( v7 x8 ?) v) o7 }+ w! z寻求能够照顾到各个目标,并使决策者感到满意的解。由决策者来确定选取哪一个 解,即得到一个满意解。但有效解的数目太多而难以将其一一求出。 8 p9 e  f  |8 @+ q# X/ |, R$ [

    , Z: R3 e7 M, G! L2  目标规划的数学模型$ Y8 X% r8 [7 D* u; g. O
    为了具体说明目标规划与线性规划在处理问题的方法上的区别,先通过例子来介绍 目标规划的有关概念及数学模型。# M( y; L5 U) ]  E2 t4 T* G

    + b' b6 }% }4 ^/ C6 B6 j例1  某工厂生产 I,II 两种产品,已知有关数据见下表 ,试求获利最大的生产方案。1 ^6 q- p4 k/ f* s. B

    9 [7 f, P0 ~+ [7 {; @5 S/ o! p+ W& w3 Z
    - V% M- r3 O$ `2 _7 r2 k+ T
    解  这是一个单目标的规划问题,用线性规划模型表述为: * v5 a+ W! u# P) Y, y

    & n( l7 d2 {) c6 u. Q2 Z/ `7 l

    ) e% q* ^. V2 z5 [但实际上工厂在作决策方案时,要考虑市场等一系列其它条件。如& w8 \  x% g$ D% j" s

    , Z7 [9 p5 F: ~(i)根据市场信息,产品 I 的销售量有下降的趋势,故考虑产品 I 的产量不大于 产品 II。: V3 ~; K, X) c. _
    5 f9 r/ j2 U; @& _5 ^/ l- p
    (ii)超过计划供应的原材料,需要高价采购,这就使成本增加。# j. h! N' ~4 B- O& S; v
    ' W9 u: X; ]" {6 ^2 k5 z" B
    (iii)应尽可能充分利用设备,但不希望加班。
    3 B+ \2 u# \3 |3 O+ Y/ n, ~1 n6 d* Z( c- V3 U1 U
    (iv)应尽可能达到并超过计划利润指标 56 元。: F4 W0 P* T3 I  ~/ }4 |% S
    4 u- ?7 z4 O2 _5 `. X( c* L* B+ _
    这样在考虑产品决策时,便为多目标决策问题。目标规划方法是解决这类决策问题 的方法之一。下面引入与建立目标规划数学模型有关的概念。
    + R( ~5 Q6 O# t: y& W0 {8 j" a# B( Q3 j: P
    1. 正、负偏差变量
    1 M, R+ {9 p! W1 l
    / e' x# A4 Y1 {1 @; u# t) a
    ; j7 C# e( E% }1 m: S6 S- _2 c3 x1 N5 v! D- J/ t
    2. 绝对(刚性)约束和目标约束 # j) _* _7 _% G  C5 h6 ~1 s

    8 k% n% A8 n( _  g/ I* L2 f
    : Y! i* b3 q2 q; p1 {. A2 i+ f# C
    3. 优先因子(优先等级)与权系数 + s8 q* t- q9 y4 X/ P- g  I

    5 ?, N& g7 x2 R1 S, m, |' {/ y/ v6 d5 x
    : Z, r% ~8 \8 L8 d: v" K# |7 `/ W1 z+ \& N* N7 n

    7 I' O/ v! {6 F, R# ~, H9 ?4. 目标规划的目标函数
    7 w$ Y) H  o. {6 a. ~9 [7 e; R4 {8 ~& p/ j" W

    ! X& Q' Q6 O3 y& `# n4 \7 x% S/ X
    8 F( X# I9 }8 e$ Y( r1 k8 I对每一个具体目标规划问题,可根据决策者的要求和赋于各目标的优先因子来构造目标 函数,以下用例子说明。
    3 F2 [# E; h& K( c. N  Q# ~8 q# b5 `, ~$ q) `" s. e$ i
    例 2 : 例 1 的决策者在原材料供应受严格限制的基础上考虑:首先是产品 II 的产 量不低于产品 I 的产量;其次是充分利用设备有效台时,不加班;再次是利润额不小于 56 元。求决策方案。 解  按决策者所要求的,分别赋于这三个目标  优先因子。这问题的数学模型是  ) H! K% r& s, ?2 l. P# z- x

    $ V! w3 ^2 @2 D$ y' \2 D
    ; w8 B% u0 B+ K7 O* e! l& [  e8 S: c% {
    5.目标规划的一般数学模型/ o4 i8 M& a" J2 Q

    - h5 B' ], z8 F9 `5 @
      h' Q+ D0 g  z) x& W* ?, \3 u0 d+ p  r, c  D8 l
    5 N# Z  l+ Z# a
    建立目标规划的数学模型时,需要确定目标值、优先等级、权系数等,它都具有一 定的主观性和模糊性,可以用专家评定法给以量化。
    3 ?+ |& c2 c0 P* r  D
    / K. ^1 B5 T3 `( S+ i1 W3  求解目标规划的序贯式算法
    $ `$ H% w& I8 k* g/ R0 A/ s5 D. G序贯式算法是求解目标规划的一种早期算法,其核心是根据优先级的先后次序, 将目标规划问题分解成一系列的单目标规划问题,然后再依次求解。 5 u8 l% G5 L7 b8 m3 i6 d% y
    ' f3 ~6 T% r- i, T  ]
    + k: u' @9 h" x: l$ l2 l

    ! k9 h! U$ H. f2 W+ d& K9 Q  f  g# W5 V

      o* J) k4 D: v* k5 G/ ^& c注  此时最优解的概念与线性规划最优解的概念已有所不同,但为方便起见,仍 称为最优解。
    0 z7 z) T, N  D
    ! a* H& F& _  s$ Z9 C例 3  某企业生产甲、乙两种产品,需要用到 A ,B ,C 三种设备,关于产品的赢利 与使用设备的工时及限制如下表所示。问该企业应如何安排生产,才能达到下列目标:' s+ w& N$ e) Z. F; u) q3 [, S
    & n" z! D6 @  _  F: Q/ ?

    & a) D5 `4 M* v4 b+ J/ M1 Q
    $ d' A5 M% c. z' h( J% r! W(1)力求使利润指标不低于 1500 元;
    8 W, p( X. h9 n8 c- g( o- s- P2 x3 @
    (2)考虑到市场需求,甲、乙两种产品的产量比应尽量保持 1:2;8 ^& G8 \# o5 ?5 X

      _1 d/ I" c+ _+ D' M- u4 q(3)设备 A为贵重设备,严格禁止超时使用;
    ) d7 i7 J8 C- U5 l! j8 j$ W6 j! U8 H/ m4 X6 c% ]* @
    (4)设备 C 可以适当加班,但要控制;设备B 既要求充分利用,又尽可能不加班。 在重要性上,设备B 是设备C 的 3 倍。
    ; v1 s3 r( D% ^. C& l4 f/ r
    * J8 A5 U" {# s0 c9 o0 a& C建立相应的目标规划模型并求解。4 z+ g3 s, C& ^
    ; B' A, E) V/ }! [& `, Z
    解  设备 A是刚性约束,其余是柔性约束。首先,最重要的指标是企业的利润, 因此,将它的优先级列为第一级;其次,甲、乙两种产品的产量保持 1:2 的比例,列为 第二级;再次,设备 B C, 的工作时间要有所控制,列为第三级。在第三级中,设备B 的 重要性是设备C 的三倍,因此,它们的权重不一样,设备B 前的系数是设备C 前系数 的 3 倍。由此得到相应的目标规划模型。
    - T6 k8 I. R4 ]6 z$ u9 e! H- ^3 n7 U6 {- B# m

    1 C6 ]. o( o/ ~- p# Z( {" o! y
    " R, B5 [: d! D) G! C1 b序贯算法中每个单目标问题都是一个线性规划问题,可以使用 LINGO 软件进行求 解。 求第一级目标。LINGO 程序如下:
    0 V4 `' H8 A) {& P3 _9 n1 d
    ! ?- B7 O- a# q' gmodel: 8 d9 J) e# ?  m$ s/ g& v1 V
    sets:
    : n# P- K7 [# ]& w. H* Fvariable/1..2/:x;
    ; ]! \- h; Z5 K& F( [: V; US_Con_Num/1..4/:g,dplus,dminus;
    2 L0 U  j; J& v6 Q7 XS_con(S_Con_Num,Variable):c;
    . x1 N: a/ v8 ~) g1 v8 G9 iendsets
    ' d6 A' P0 B( k' f& E! Zdata:
    - N, {! g  m: S  N! Wg=1500 0 16 15;
    5 @+ H# x1 ]! d2 p$ fc=200 300 2 -1 4 0 0 5; * H, @2 ?: G5 {
    enddata   n4 d; A& q7 K' z1 @
    min=dminus(1);
    " M1 y: W; k3 b& ^" \2*x(1)+2*x(2)<12; ( l5 v' V4 N6 J' `1 z7 V
    @for(S_Con_Num(i)sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i));
    ) Y: ~. [+ O) i4 k" N7 |end
    ; i& I  P( x+ S' W* @+ u/ F+ v+ ^, ?( A

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

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

    model: ! `+ @5 \* c( ^8 B) X4 d. C, N: a7 p
    sets: + v  f0 s/ a& E. t4 h% o5 v
    variable/1..2/:x; $ X7 z) @& J" a8 i- K1 u
    S_Con_Num/1..4/:g,dplus,dminus; 2 U" X! T' ]" U
    S_con(S_Con_Num,Variable):c;
    6 J' a4 P$ ^3 |: L4 h* ?5 _; Jendsets
    : B8 ~0 i. B# S( b, ddata: ( G, W% ~  K1 h* `# @# n, s. }# t
    g=1500 0 16 15; ) [6 k; {/ H! `. O/ U
    c=200 300 2 -1 4 0 0 5;
    ( S$ u. P# _- g) ?, T) l$ eenddata + f2 ~6 a; p" P5 A6 i7 C+ r
    min=dplus(2)+dminus(2);    !二级目标函数; & j* c) K/ g' v9 e* t3 N
    2*x(1)+2*x(2)<12;
    ' r; r. h* G/ U  x@for(S_Con_Num(i)sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i));
    ; _1 Y6 o5 y+ m+ Q1 }* Kdminus(1)=0;!一级目标约束; , q3 A3 W& V' l3 Z7 \, X/ X: `
    @for(variablegin(x)); : ~& a( ~& I0 e) E+ V
    end . X: z; L4 r5 @2 L# ^8 A# \5 P

    & M: ^0 x* e3 g/ c6 ?+ d: O) ?( Y& T求得目标函数的最优值为 0,即第二级的偏差仍为 0。 求第三级目标,LINGO 程序如下: 4 H: ^4 s$ r. j/ p
    1 V$ v  l/ d9 ]2 C
    model:
    - c. K6 N9 T8 N, xsets:
    7 F, _% m3 `. N& E% ?3 x0 s7 a  r/ }variable/1..2/:x; 7 b4 w0 P6 [2 ~
    S_Con_Num/1..4/:g,dplus,dminus;
    9 }  H; C0 G+ m8 u) j* x+ hS_con(S_Con_Num,Variable):c; , G, C) B; T: d! G0 v2 s
    endsets ; {  o2 w2 f# g! q. ~
    data: : f2 K  y2 I  C; D& s8 T
    g=1500 0 16 15;
      x) Q) L6 ^# s; b* Z8 h% t5 jc=200 300 2 -1 4 0 0 5;
    ; m, F+ X/ {( jenddata
    ( h, Y- ]4 Y4 [+ i$ e; T) Cmin=3*dplus(3)+3*dminus(3)+dplus(4);    !三级目标函数; : L+ {  N* V/ q+ J0 z
    2*x(1)+2*x(2)<12;
    . O0 c" O0 ^/ c- S8 \% ^ @for(S_Con_Num(i)sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i));
    ) _; H# h: n/ s/ Ndminus(1)=0;!一级目标约束; 1 \# f7 w* K9 X' k
    dplus(2)+dminus(2)=0;!二级目标约束; ( n8 Q3 M: }) Z7 b9 h
    end
    2 o0 T. h1 |' B' y9 x- f2 v3 k' T; z* B
    目标函数的最优值为29,即第三级偏差为29。 * ]2 ~  L6 @# p* D4 x

    6 @% w: G! b" q0 [+ d, o分析计算结果,  ,因此,目标规划的最优解为   , 最优利润为1600。
    - I# ]" @2 g1 o- W( F1 d
    3 d9 o  _' L! K5 I5 r  S* t' y. S! [9 t上述过程虽然给出了目标规划问题的最优解,但需要连续编几个程序,这样在使 用时不方便,下面用 LINGO 软件,编写一个通用的程序,在程序中用到数据段未知数 据的编程方法。
    ' v# Z: \* X) L  [; a8 |! |0 v4 k7 j" c9 I/ t
    例 4(续例 3)  按照序贯式算法,编写求解例 3 的通用 LINGO 程序。
    1 K9 U8 {/ H  H, p4 ~" V) V# |. P1 h
    $ \7 b( }2 y0 r" W3 H: Smodel: 5 F/ ]8 [3 L# B% w
    sets: 7 }8 b. r! r8 ]9 C% X) M  e5 k/ l
    level/1..3/:p,z,goal;   n' ]. f" u0 j- \2 x8 P; N7 a+ _
    variable/1..2/:x;
    ; Z/ q& p8 V  nh_con_num/1..1/:b;
    1 Y. H) `& J& E9 }. c  [s_con_num/1..4/:g,dplus,dminus; : f( U2 ?% w- }8 i  r4 o
    h_con(h_con_num,variable):a; 4 a" {0 E9 g4 h# C/ i, z
    s_con(s_con_num,variable):c;
    $ j! F( O( ^' yobj(level,s_con_num)/1 1,2 2,3 3,3 4/:wplus,wminus;
    1 q# a4 N; g1 r* c* M' S. lendsets 4 d9 v7 I" b+ o9 ]7 c1 G3 I
    data: : K: _6 {, |/ T6 H2 h
    ctr=?;
    4 i7 B* C8 ?! _$ W$ h% s4 J+ Lgoal=? ? 0;
    " V9 X/ w9 L/ T! a$ P% U5 t6 D, |+ A5 [b=12; 1 T- M3 T! x) ?1 ]* I: Y
    g=1500 0 16 15;
    ; B$ ~$ y0 F$ j9 va=2 2;
    3 X  ?5 i' q5 T: e1 i: Pc=200 300 2 -1 4 0 0 5;
    / X. S+ A: B6 i" R% I3 vwplus=0 1 3 1; . d/ ]" d0 a9 x- D/ C2 B' ^4 i  Y
    wminus=1 1 3 0;
    8 N& v8 P) i2 I- Henddata 5 v5 _2 C$ t- T( I6 T
    min=@sum(level:p*z);
    # s8 y9 |3 m/ Q$ i! Up(ctr)=1;
    ! B: c" A, B) [2 _7 d@for(level(i)|i#ne#ctr:p(i)=0); ! e5 X; F' s0 X) l
    @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)));
    3 l; x5 c4 u, _& Z$ e0 gend ) c% {" v" F2 T- T, N
      ?: @9 ~# s- v8 X
      v9 y6 Q1 y6 D" N8 R

    5 k1 e/ C# U1 s
    , w; @# X, {1 V/ ~+ W9 w& J8 y+ S# ~# e2 G4 ]
    4  多标规划的 Matlab 解法

    多目标规划可以归结为


    8 k: @5 a" K1 u! J' g9 \) T% T- Z
    . T  t. F$ o: B' E( Q2 s
    / f- O, _! L# G) |$ }0 ~0 Y[x,fval]= fgoalattain('fun',x0,goal,weight)           / E1 T5 _; R5 S3 f: g- N
    [x,fval]= fgoalattain('fun',x0,goal,weight,A,b)           4 |( D, ^; v/ F& r( G
    [x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq)           6 G/ [  @! q' z  P1 u
    [x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)
    ; X$ U% h% k: k( r" s% x
    / ]0 d. _' Y' L+ m2 x% L  B  w4 l1 f- N; u% m  g  O
    要完整掌握其用法,请用 help  fgoalattain 或 type  fgoalattain 查询相关的帮助。( K1 u$ Z* J& P
    例 5  求解多目标线性规划问题
    ! ?* U2 F" y+ @; D6 d4 @2 F7 K+ g% S8 O

    " U! v# L2 k/ H6 P/ d" ^2 i6 t& n* B
    解  (i)编写 M 函数 Fun.m:
    , ]6 ~% Z3 N- S6 ?" w4 l, a' H$ Q( R* e0 ?
    function F=Fun(x);
    & J& c: Q' ?( x5 w8 w9 @% U( x# D9 t" H8 k% K- j
    F(1)=-100*x(1)-90*x(2)-80*x(2)-70*x(4);   r8 V+ t! i% R- S/ ^  {, j' ?5 i  ?
    0 {- b; K, [% j9 J
    F(2)=3*x(2)+2*x(4); / `! s# U$ W/ `, t5 r4 ^
    # ?* y# _6 g$ E1 S" U0 i8 Z& S
    (ii)编写 M 文件 % B& a/ Z( l! d% J9 N" `2 X

    % c1 I- U1 c1 l! W# z7 p2 ua=[-1 -1  0  0   
      z5 d5 v. }- r& y& |; p0 K   0  0  -1 -1   
    4 b" f! @8 m* _! [0 J   3  0   2  0    # \8 \+ q% _+ j. Q! f6 S8 j- x" h
       0  3   0  2]; 2 J1 x/ |! P' f9 D. w3 Q6 j6 x
    b=[-30 -30 120 48]'; ' G0 D  p( V, ^+ Z% h
    c1=[-100 -90 -80 -70]; ) E( L, Q6 t9 e7 S8 @3 m
    c2=[0 3 0 2];
    5 R. [6 I5 r0 i  p+ c/ o[x1,g1]=linprog(c1,a,b,[],[],zeros(4,1))  %求第一个目标函数的目标值   h! ?  W" H: O- _$ I& Y: m
    [x2,g2]=linprog(c2,a,b,[],[],zeros(4,1))  %求第二个目标函数的目标值
    ) `) T, W: o+ d5 K6 Fg3=[g1;g2]  %目标goal的值 * b7 u' s) I, n, w5 H) [
    [x,fval]=fgoalattain('Fun',rand(4,1),g3,abs(g3),a,b,[],[],zeros(4 ,1)) / p7 L$ T! j  t
    %这里权重weight=目标goal的绝对值
    $ y! c3 k( `$ j- @) E1 [3 c! _# e% t9 j* j* D$ ^7 `' E

    就可求得问题的解。

    习题
    , l$ z1 R- ~0 F7 ]* _9 y4 [' \  d  q4 T/ C) W  |) K: N) f
    , [* u6 R, I6 c. j$ X
    ————————————————* K/ R& t. G% ^! z: H" E# v
    版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    1 W# Q( v1 h6 j" q  [原文链接:https://blog.csdn.net/qq_29831163/article/details/89488932! A5 J0 ]2 u  C1 Q

    & b! e! b8 f2 ?4 H# [( O  f  p/ v! n8 G; w# u6 F
    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-6-14 17:22 , Processed in 0.423715 second(s), 51 queries .

    回顶部