QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2060|回复: 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.线性规划的局限性
    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(variablegin(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
    转播转播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-23 05:05 , Processed in 0.760659 second(s), 50 queries .

    回顶部