QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2075|回复: 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.线性规划的局限性
    " B& g* ~  E, @- K% N2 U0 y只能解决一组线性约束条件下,某一目标只能是一个目标的最大或最小值的问题。
    6 }6 v# f( u; s( B" s; F2 W( u, q1 e! v3 v9 \# I, _: y) O
    2.实际决策中,衡量方案优劣考虑多个目标( |' k2 k! t& k8 f
    这些目标中,有主要的,也有次要的;有最大值的,也有最小值的;有定量的, 也有定性的;有相互补充的,也有相互对立的,LP 则无能为力。
    . j7 R) @$ P0 C1 Y- N. j
    7 s% A/ a4 T9 L+ B+ z6 n: ]3.目标规划(Goal Programming)
    " |" w/ q3 h( b# s0 r+ T0 F, y美国经济学家查恩斯(A. Charnes)和库柏(W. W. Cooper)在 1961 年出版的《管理模型及线性规划的工业应用》一书中,首先提出的。
    8 [0 M2 p2 M5 B5 I% H1 W2 m" ?- X& C
    ! V/ ?  I1 }# B6 h6 s4.求解思路# v% }% {8 K3 q5 H" ~7 Z$ z
    (1)加权系数法
    # [/ {9 i# V  O/ ?+ T- y为每一目标赋一个权系数,把多目标模型转化成单一目标的模型。但困难是要确 定合理的权系数,以反映不同目标之间的重要程度。
    / d3 S5 L0 a$ T: ?6 r( W1 ?! G) p1 ?1 A1 D# T3 J9 b
    (2)优先等级法% S( O8 n  c' r0 A( M
    将各目标按其重要程度不同的优先等级,转化为单目标模型。& I- T  j- G3 v& k

    / d/ J! f  g- z- n# ](3)有效解法
    * }9 `) ]6 Y3 V4 T& A1 {0 Y& O寻求能够照顾到各个目标,并使决策者感到满意的解。由决策者来确定选取哪一个 解,即得到一个满意解。但有效解的数目太多而难以将其一一求出。 % o* h' l8 q3 e2 @; R. ]

    + g' g+ W& g' V2  目标规划的数学模型
    2 `, [( ?7 ~5 x& s为了具体说明目标规划与线性规划在处理问题的方法上的区别,先通过例子来介绍 目标规划的有关概念及数学模型。
      D$ H- u  m9 \& o1 Y& E7 V
    ! E& m- }( D5 i例1  某工厂生产 I,II 两种产品,已知有关数据见下表 ,试求获利最大的生产方案。! m2 c0 p5 E2 h5 n3 l# v2 i  b& C

    8 i5 ?  f6 y2 @" k1 d0 ^9 h: I" H0 s/ A5 B

    % }6 r! I7 S& I2 B解  这是一个单目标的规划问题,用线性规划模型表述为:
    ! ?9 D) T$ Q/ x4 T, E) a, z" e- _$ Q* Q. P5 a" x
    % Z' _% W* q' E0 @( f2 S; ?

    " n. N" n4 l5 a但实际上工厂在作决策方案时,要考虑市场等一系列其它条件。如* |, W. N# `  a1 y
    ) ^8 ?- d7 J* ^
    (i)根据市场信息,产品 I 的销售量有下降的趋势,故考虑产品 I 的产量不大于 产品 II。3 d! d( z3 r* x* t
    / {: @0 U' ~! T6 T$ T3 {
    (ii)超过计划供应的原材料,需要高价采购,这就使成本增加。
    ) {& d2 E, g3 u
    0 L6 G: h  n' \9 W7 Z(iii)应尽可能充分利用设备,但不希望加班。
    ! |9 q) A7 o: k, g9 x. }- V1 j1 o
    3 O6 ]5 V$ I: A! J7 K2 [(iv)应尽可能达到并超过计划利润指标 56 元。  q2 _; j, w* Z- k
    4 B! m+ i2 h+ c; G2 S1 G9 w
    这样在考虑产品决策时,便为多目标决策问题。目标规划方法是解决这类决策问题 的方法之一。下面引入与建立目标规划数学模型有关的概念。 9 ]8 \1 z: J6 @8 L) ?
    ; c( x) y2 c, \& H
    1. 正、负偏差变量 3 k* k5 f5 h' \" z! Q

    . d% B5 C- i/ F* _; `6 T' b, Z( r0 Y2 Y7 M+ I

    % Q+ w6 |& p  [: _' e2. 绝对(刚性)约束和目标约束
    1 _* P6 }( O* s
    9 R, h! c4 {* C0 S( n" Z# B
    ; B- Y2 t. G4 y5 u1 e, G/ i) K7 p( Q. N. m0 f0 G! E% O" _  K, F+ e) _
    3. 优先因子(优先等级)与权系数
    4 h" o: S& Q$ t# @. f& K2 s
    $ U9 ~9 ~# m3 }6 ^0 H, \6 ]: B1 y  P$ o7 c( H

    3 J/ E/ }6 X5 a5 |3 R7 z. y& q* [" a$ M: F7 _1 P
    4. 目标规划的目标函数
    $ W3 \% W; |) ?/ F. A' Q6 T/ R6 b3 e/ N' p, Q; C- {

    9 O: N, m& C. L! C8 P# R* ]' a- V, ]$ O0 T  ~% b9 K- s' W
    对每一个具体目标规划问题,可根据决策者的要求和赋于各目标的优先因子来构造目标 函数,以下用例子说明。 ) E! b0 A3 _; ^
    : w/ [" p! R5 Q3 N2 J
    例 2 : 例 1 的决策者在原材料供应受严格限制的基础上考虑:首先是产品 II 的产 量不低于产品 I 的产量;其次是充分利用设备有效台时,不加班;再次是利润额不小于 56 元。求决策方案。 解  按决策者所要求的,分别赋于这三个目标  优先因子。这问题的数学模型是  & p$ R2 u5 i( P, Q& P3 |+ E
    8 J) }+ f) W  _& A
    3 q6 b" }7 R4 A9 a$ {+ o' m

    4 V; n& {% O4 `  {5.目标规划的一般数学模型
    * a0 J# o- h: A/ s; |6 }& b6 f
    ) G0 f4 B2 B. H1 l( l
    9 C: |0 K. U. u
      B* M. j4 ~, ~: k% B6 T
    5 l- y7 y  _0 A1 W( H* F" f& ^, a建立目标规划的数学模型时,需要确定目标值、优先等级、权系数等,它都具有一 定的主观性和模糊性,可以用专家评定法给以量化。
    7 x4 A/ S6 S0 {( \0 i' E( v
    ! F" U9 H( L$ Q  N1 r/ f3  求解目标规划的序贯式算法$ W6 w* S" a! y' c
    序贯式算法是求解目标规划的一种早期算法,其核心是根据优先级的先后次序, 将目标规划问题分解成一系列的单目标规划问题,然后再依次求解。
    + _+ l9 K' j* J+ c6 e/ J7 g9 O7 e3 ]- o0 y
    4 i: Q. d$ S( N, F& x: C

    ) I4 Z! c( ]1 g: c: E& m; e# S/ c: ~

    # P+ J( k1 {, G+ D( C; s& r4 r& i0 S注  此时最优解的概念与线性规划最优解的概念已有所不同,但为方便起见,仍 称为最优解。
    7 I2 o: V, {6 R/ f0 U
    . S' \, |# R0 g$ I  k: P- F' H例 3  某企业生产甲、乙两种产品,需要用到 A ,B ,C 三种设备,关于产品的赢利 与使用设备的工时及限制如下表所示。问该企业应如何安排生产,才能达到下列目标:
    2 F/ }3 v4 H4 E. x9 ?9 h( f; F( t) V% V0 M

    $ R8 c+ T) j9 ?5 d1 q! ^
    4 b- r8 r5 z6 a$ y6 t; I(1)力求使利润指标不低于 1500 元;& o/ x7 ~; p. k( C

    / k* u: s1 G- ?# W  P' M(2)考虑到市场需求,甲、乙两种产品的产量比应尽量保持 1:2;
    1 g  h: e$ n! w' W2 G& j
    " A, ?" r! }  l1 [- N: R$ d) N0 j& _(3)设备 A为贵重设备,严格禁止超时使用;
    + Z' d) B6 Z& v* L8 u  t% z4 R4 r
    . ]& r' S1 d6 R. e! L* M! A7 t2 |(4)设备 C 可以适当加班,但要控制;设备B 既要求充分利用,又尽可能不加班。 在重要性上,设备B 是设备C 的 3 倍。
    " A6 c( p. ^; x2 I
    6 V$ ~6 B6 u- I5 b建立相应的目标规划模型并求解。9 ]" n* D* }: P9 R, \

    7 {9 i, y2 O: L( U解  设备 A是刚性约束,其余是柔性约束。首先,最重要的指标是企业的利润, 因此,将它的优先级列为第一级;其次,甲、乙两种产品的产量保持 1:2 的比例,列为 第二级;再次,设备 B C, 的工作时间要有所控制,列为第三级。在第三级中,设备B 的 重要性是设备C 的三倍,因此,它们的权重不一样,设备B 前的系数是设备C 前系数 的 3 倍。由此得到相应的目标规划模型。
    - k1 u1 k, W, |' X5 G* K: L; E; @9 T9 g

    ( B: x$ }) F! n$ N+ |, L2 N  M
    / s& P: W4 t% N( g9 }7 \序贯算法中每个单目标问题都是一个线性规划问题,可以使用 LINGO 软件进行求 解。 求第一级目标。LINGO 程序如下:
    ' w) K9 d7 |& J% `
    ' p( R  F5 I0 u" i! e* K" ]2 Ymodel:
    : Z5 p' K8 ~) tsets:
    , G; c3 m7 N1 ]! gvariable/1..2/:x;
    ' l) v% p3 l) D/ }) o% LS_Con_Num/1..4/:g,dplus,dminus;
    ; t9 ^! _! Q! fS_con(S_Con_Num,Variable):c;   f2 M/ k3 p, F  _$ I
    endsets + L+ u. @% b8 T5 ]4 Z) I
    data: - l6 f8 Q$ N* }4 g7 X! k# J- a/ m) v" y
    g=1500 0 16 15;
      R2 c: w& _* {4 t0 ac=200 300 2 -1 4 0 0 5; ; u. Z7 }! M% T6 I, T0 D5 @! f
    enddata # o! L* P7 C0 s3 b0 H3 Y- e1 @
    min=dminus(1);
    ! n+ F1 e; Z! @7 u9 u2*x(1)+2*x(2)<12; 3 }% |% y" ^& l4 B/ H# C0 Z
    @for(S_Con_Num(i)sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i)); 8 L1 }8 T0 F$ w6 u/ d; f3 |* m! `
    end2 l; ~. `3 c1 E6 x

    9 A# x# Z0 L' P, e0 W8 q

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

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

    model:
    & W$ a% v5 ~. W/ u9 A+ |8 }sets:
    . n  f) I4 d) v6 Ovariable/1..2/:x;
    0 o% X$ S  `/ s# L: Z7 t* q$ BS_Con_Num/1..4/:g,dplus,dminus; / x9 i* t0 V0 e  }: k( d
    S_con(S_Con_Num,Variable):c;
    * R0 D9 c5 D) {  Gendsets
    & s9 M' D. S, G: I* w. vdata: 0 _  e+ ]1 R! b) C9 K' D
    g=1500 0 16 15; 9 D( Q* p0 g( q  G0 F3 V
    c=200 300 2 -1 4 0 0 5; ! l  C( M7 Y) z8 ?+ \9 T! Z; E( |
    enddata ; i9 b$ y3 b$ {
    min=dplus(2)+dminus(2);    !二级目标函数; & V0 l  D" v1 i4 I
    2*x(1)+2*x(2)<12; " O7 K8 q6 R/ `8 \! }- w
    @for(S_Con_Num(i)sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i)); , t! K; v) J& J* y8 o
    dminus(1)=0;!一级目标约束;
    % L8 |1 {4 f% a" a@for(variablegin(x)); + [4 n' L- ?! e/ f+ B
    end
    * r; v5 g" T- B8 Q' b
    2 g4 [1 [' W$ @$ L+ G6 v求得目标函数的最优值为 0,即第二级的偏差仍为 0。 求第三级目标,LINGO 程序如下:
    : J. V: ~5 t( @8 j
    ( P; [, X! }  t+ ?model: 4 J0 q/ B% Q5 h- U5 }
    sets: + J5 N' ~; E; q4 ~
    variable/1..2/:x; 9 k; G7 I* w* `; v- E" g0 I
    S_Con_Num/1..4/:g,dplus,dminus; + E7 S0 o# O3 J6 r4 N0 i$ {; `% @# @
    S_con(S_Con_Num,Variable):c; : [4 H; Q. H, _8 ], ]9 Y. V
    endsets   ?5 R+ s& p$ T# a3 E. t+ `' `+ S
    data: % d9 A/ A! d, h' t" D( S2 Q+ F
    g=1500 0 16 15;
    * J4 m& T- X" f" j) x/ A6 R% tc=200 300 2 -1 4 0 0 5; 6 Q5 P9 |1 d, ^# B5 K: A
    enddata 2 A/ W8 L2 Q* s, D
    min=3*dplus(3)+3*dminus(3)+dplus(4);    !三级目标函数; ) P) G9 w( d/ B. ~; V4 H4 }, r8 s' w
    2*x(1)+2*x(2)<12;
    2 N" }1 F  [5 S! k- E- h @for(S_Con_Num(i)sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i));
    3 A4 o1 W( H. e2 m5 U8 d2 Pdminus(1)=0;!一级目标约束;
    * G2 x0 Y2 O3 r# ^dplus(2)+dminus(2)=0;!二级目标约束; : u- {7 O  ]* T' P) G( z
    end
    5 C. K3 Q7 _' I! `. p/ i
    - M3 m. i- M8 u  o' N5 o0 @5 s目标函数的最优值为29,即第三级偏差为29。 & a; V) H8 c- x8 q* b0 `( B
    , O6 g- x( c1 O7 X
    分析计算结果,  ,因此,目标规划的最优解为   , 最优利润为1600。
    - W' N' i# w$ c& R% T/ j6 ?+ S: t6 @
    上述过程虽然给出了目标规划问题的最优解,但需要连续编几个程序,这样在使 用时不方便,下面用 LINGO 软件,编写一个通用的程序,在程序中用到数据段未知数 据的编程方法。  ^  x2 |, {3 X/ ^6 \8 D! a
    ) a) Q* j4 P. z# I" R# B
    例 4(续例 3)  按照序贯式算法,编写求解例 3 的通用 LINGO 程序。
    ' _* S0 Y4 G* z+ A- L' Y; u6 I  _0 b" H# e. k/ L2 \/ K
    model:
    0 z& Y( t+ }  G  u% Psets:
    7 Y) B, ?4 M, N9 }1 w7 Ylevel/1..3/:p,z,goal;
    0 Y! _6 Y3 r; F! bvariable/1..2/:x;
    ; t9 \% M) n  A4 l( ]8 Rh_con_num/1..1/:b; : n3 x8 s' r$ j
    s_con_num/1..4/:g,dplus,dminus; 3 k. q" e0 L3 B- c' d( z) N% z
    h_con(h_con_num,variable):a;
    1 R2 U5 V2 X8 ps_con(s_con_num,variable):c; 5 y; Q' q  y7 d
    obj(level,s_con_num)/1 1,2 2,3 3,3 4/:wplus,wminus; 2 V. [% Y% q9 Q* B4 j& M3 H
    endsets + x, P# h+ e9 v3 Q$ N9 O5 {
    data:
    ; c, ~! q4 H8 uctr=?;
    ) V4 S. z! |* p+ E% x2 y( _2 k4 Hgoal=? ? 0;
    " K! L" l9 {' {8 p$ O1 Y7 g$ z+ F! Kb=12;
    9 \0 }' R/ e6 o# }2 @" eg=1500 0 16 15;
    , B# E/ i" a% J! V& x  wa=2 2;
    + R: C! p+ r0 o2 ^c=200 300 2 -1 4 0 0 5; 9 Y; ?/ v- }$ j+ A1 C* w
    wplus=0 1 3 1;
    9 r; ?! ~6 p9 v9 z  qwminus=1 1 3 0; ; c$ w+ Y+ B0 N% x
    enddata
    + A1 V7 i/ @  m! \min=@sum(level:p*z); % C* f; w" G* q% B0 M7 k
    p(ctr)=1; ) C( U2 p& S3 `) w0 Y
    @for(level(i)|i#ne#ctr:p(i)=0); ( k3 `$ A% \, j# q
    @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)));
    ! k( e% Z/ _& M2 E# z0 c+ Fend
    0 J& m8 G5 i! g2 a7 e" V, t0 W4 c! W( E- ]0 M8 ]5 [5 R( S

    ' A! l: F" l" K$ F& e& u
    * k) |: K" Z2 k2 f' b1 U3 Q9 u8 j* q) J: R1 z) T( A

    ) F# ?# T! M1 _8 y4  多标规划的 Matlab 解法

    多目标规划可以归结为

    $ O$ c0 O; }( N' W2 z) I

    , B+ R$ S+ X7 o: j- m* U% R* j+ O# P- u+ f) ~' J; ~3 W
    [x,fval]= fgoalattain('fun',x0,goal,weight)           
    5 d# O( N6 G) ^- s- x) t* B, I[x,fval]= fgoalattain('fun',x0,goal,weight,A,b)           3 h; q. N7 A7 p* c* F" f7 g
    [x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq)           
    # G0 S* N/ A! g0 Z" K& z[x,fval]= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) ) H$ D1 {2 j  t: E. n0 a! _

    9 j- g# w( r6 W# F4 r. v
    1 ^. r/ K% b0 U要完整掌握其用法,请用 help  fgoalattain 或 type  fgoalattain 查询相关的帮助。% ^9 T0 X* F6 \9 y0 H" `' E
    例 5  求解多目标线性规划问题
    . j! p6 O% b8 l4 \4 x
    ( A2 m% Q7 `! p( q* j  W
    ' W& Y0 Z6 C+ B
    ( D* n) F; S, {2 R1 e" V4 `解  (i)编写 M 函数 Fun.m:
      l2 ]' G/ V. G& g( y6 b# q8 D0 R1 o& o" ^  v) \
    function F=Fun(x);
    ; q, I& o' @6 ~. N$ x8 ?- K2 \7 E  K) z) o
    F(1)=-100*x(1)-90*x(2)-80*x(2)-70*x(4);
    + l' ?% G! B  t# ]! F; y
    1 Q# L' `4 a9 s- }F(2)=3*x(2)+2*x(4);
    & {  m5 P) v3 z1 t" Y2 Z
    . B3 F+ K- I# p( `  D, d3 X; G(ii)编写 M 文件 " P" s5 \. f/ \" l1 G0 w# w
    - ?) O3 w& C* J- t, O. y$ h
    a=[-1 -1  0  0    & Y* L% {' M& i- J/ L
       0  0  -1 -1   
    , \* G# a( b& a5 q5 h2 z   3  0   2  0    2 {( o: Q/ D5 s6 K' r1 s
       0  3   0  2]; 1 V& C& v4 z, Y2 a2 G2 a
    b=[-30 -30 120 48]';
    # c: V: P4 u: Cc1=[-100 -90 -80 -70]; & u, d' r! y3 K0 R) c
    c2=[0 3 0 2];
    1 k" n) I6 f" _9 c[x1,g1]=linprog(c1,a,b,[],[],zeros(4,1))  %求第一个目标函数的目标值
    % s4 f3 w( [9 u8 ^, b( M[x2,g2]=linprog(c2,a,b,[],[],zeros(4,1))  %求第二个目标函数的目标值
    : i( [$ I0 Y& N! R* x6 X9 r# W! u+ d5 {g3=[g1;g2]  %目标goal的值 $ X* ]  Y) d+ m8 C7 z
    [x,fval]=fgoalattain('Fun',rand(4,1),g3,abs(g3),a,b,[],[],zeros(4 ,1))   f, t: i/ s  Y! x% i& y
    %这里权重weight=目标goal的绝对值
    ! P& n0 z+ o4 X) T2 Q& ]/ C/ c9 i2 Z5 `( Q' A

    就可求得问题的解。

    习题( V- \6 k, `% Q3 h' o6 r/ b
    * q- ^1 P) K% u0 \6 X9 ^4 g$ `+ ?; T

    % {1 ^6 C5 _2 s2 `% m+ G6 F4 {6 r7 _————————————————
    - i; k4 q. f. L& Q0 i版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。% f( q$ r; i& o- |( N2 Z8 i7 d
    原文链接:https://blog.csdn.net/qq_29831163/article/details/89488932# ^# T8 H, ?* F3 q

    1 g, ?  R# F! _6 r6 }7 [$ H! ]
    4 \4 e  e+ H, g, l1 b$ k
    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, 2025-7-29 06:46 , Processed in 0.415396 second(s), 50 queries .

    回顶部