目标规划模型：求解思路、序贯式算法

浅夏110

1．线性规划的局限性
只能解决一组线性约束条件下，某一目标只能是一个目标的最大或最小值的问题。
& ]# O* j' ~* K- e
) A+ m/ J4 h* _+ Q 2．实际决策中，衡量方案优劣考虑多个目标
! z( u, n! v8 q% m4 A$ |! A这些目标中，有主要的，也有次要的；有最大值的，也有最小值的；有定量的， 也有定性的；有相互补充的，也有相互对立的，LP 则无能为力。

3．目标规划（Goal Programming）
美国经济学家查恩斯（A. Charnes）和库柏（W. W. Cooper）在 1961 年出版的《管理模型及线性规划的工业应用》一书中，首先提出的。
- P% t. e( y/ v+ V# Z4 j
4．求解思路
（1）加权系数法
为每一目标赋一个权系数，把多目标模型转化成单一目标的模型。但困难是要确 定合理的权系数，以反映不同目标之间的重要程度。
" B  r4 h0 U+ [' |" @
（2）优先等级法
5 i: c+ Q" N% c+ s将各目标按其重要程度不同的优先等级，转化为单目标模型。
' J/ A  G* ^5 l* ~, e' P
; e1 k, ^3 r) R8 h2 Y; S1 u（3）有效解法
寻求能够照顾到各个目标，并使决策者感到满意的解。由决策者来确定选取哪一个 解，即得到一个满意解。但有效解的数目太多而难以将其一一求出。

2  目标规划的数学模型
为了具体说明目标规划与线性规划在处理问题的方法上的区别，先通过例子来介绍 目标规划的有关概念及数学模型。
8 C$ A3 O; a; c4 I  |* y! o7 W; S0 J
8 V  ?' x9 @7 @( i! o1 r例1  某工厂生产 I，II 两种产品，已知有关数据见下表 ，试求获利最大的生产方案。

. W, g) h& \" p! B

解  这是一个单目标的规划问题，用线性规划模型表述为：
( P/ V' _' p- r" o0 c3 b+ d2 v
7 O! t- e9 r6 u7 ]

9 c. h( R5 ]: X  I但实际上工厂在作决策方案时，要考虑市场等一系列其它条件。如
# o7 C  v# T: i' n) S
' G$ {. \7 N. b9 u$ M( A4 n, b（i）根据市场信息，产品 I 的销售量有下降的趋势，故考虑产品 I 的产量不大于 产品 II。

（ii）超过计划供应的原材料，需要高价采购，这就使成本增加。
/ F% U0 Y- M. H9 a
（iii）应尽可能充分利用设备，但不希望加班。
" D2 v  ?5 Q! B0 V/ V5 P
' d, k4 v! }7 k2 I4 E$ b5 E（iv）应尽可能达到并超过计划利润指标 56 元。

/ ^5 w& G8 x0 L7 r+ j  w这样在考虑产品决策时，便为多目标决策问题。目标规划方法是解决这类决策问题 的方法之一。下面引入与建立目标规划数学模型有关的概念。
: w, P+ O) G4 W
& q* [. |+ K" i: t% u; [9 }# H1. 正、负偏差变量
: B6 a! k/ ~0 k9 ^; d, z' a
# s( h  |! l9 q, V

3 [5 n  h7 @; a5 U2. 绝对（刚性）约束和目标约束
* M4 B5 X3 O/ g" j) g
- X0 V, z2 _/ @; n1 C5 b
+ }; |2 U  ]' Z2 ^" L6 }
- k; U3 G- A# ^8 I7 d  V3. 优先因子（优先等级）与权系数




1 W1 h+ Q+ K. Z: t4. 目标规划的目标函数



对每一个具体目标规划问题，可根据决策者的要求和赋于各目标的优先因子来构造目标 函数，以下用例子说明。

8 Q5 C1 g2 u' _- o例 2 ： 例 1 的决策者在原材料供应受严格限制的基础上考虑：首先是产品 II 的产 量不低于产品 I 的产量；其次是充分利用设备有效台时，不加班；再次是利润额不小于 56 元。求决策方案。 解  按决策者所要求的，分别赋于这三个目标  优先因子。这问题的数学模型是  
% }2 H1 C0 @5 z  m/ C/ z
$ K/ c- @3 r, {5 Y
( n# L  S1 M+ d/ c  A2 v
5．目标规划的一般数学模型




( M' |* \- W' T6 E建立目标规划的数学模型时，需要确定目标值、优先等级、权系数等，它都具有一 定的主观性和模糊性，可以用专家评定法给以量化。

. A; a/ U( ~- z3  求解目标规划的序贯式算法
序贯式算法是求解目标规划的一种早期算法，其核心是根据优先级的先后次序， 将目标规划问题分解成一系列的单目标规划问题，然后再依次求解。




) G- ]; t$ G1 J
注  此时最优解的概念与线性规划最优解的概念已有所不同，但为方便起见，仍 称为最优解。
3 [' ]5 Z1 X; |0 D4 m
例 3  某企业生产甲、乙两种产品，需要用到 A ,B ,C 三种设备，关于产品的赢利 与使用设备的工时及限制如下表所示。问该企业应如何安排生产，才能达到下列目标：



2 O3 M# n% y6 O% }8 B7 f. W; d（1）力求使利润指标不低于 1500 元；

6 l5 y; i! Z' U) n3 r2 Z（2）考虑到市场需求，甲、乙两种产品的产量比应尽量保持 1:2；

（3）设备 A为贵重设备，严格禁止超时使用；
5 u' p+ o+ K, t1 P
（4）设备 C 可以适当加班，但要控制；设备B 既要求充分利用，又尽可能不加班。 在重要性上，设备B 是设备C 的 3 倍。

; I2 R, x- T2 O" v建立相应的目标规划模型并求解。
/ n9 H7 K5 n  D! A: T
' O: n9 _0 a% `5 _解  设备 A是刚性约束，其余是柔性约束。首先，最重要的指标是企业的利润， 因此，将它的优先级列为第一级；其次，甲、乙两种产品的产量保持 1:2 的比例，列为 第二级；再次，设备 B C, 的工作时间要有所控制，列为第三级。在第三级中，设备B 的 重要性是设备C 的三倍，因此，它们的权重不一样，设备B 前的系数是设备C 前系数 的 3 倍。由此得到相应的目标规划模型。


' Q! }8 i' H% J; q8 g) ~
序贯算法中每个单目标问题都是一个线性规划问题，可以使用 LINGO 软件进行求 解。 求第一级目标。LINGO 程序如下：

model:
sets:
variable/1..2/:x;
& q+ X) D- s  n) a3 v7 VS_Con_Num/1..4/:g,dplus,dminus;
5 O) |4 M1 h! j! ^2 D) xS_con(S_Con_Num,Variable):c;
( g0 k5 |$ e$ l7 H( gendsets
7 d* K- y; N& ]& {1 r  b! J  x1 sdata:
* `( `# f" L' F" J' s3 U* g" V* {g=1500 0 16 15;
, g+ ^7 w, Z7 f. i8 B# t* b. gc=200 300 2 -1 4 0 0 5;
5 t. R7 u+ B# _  U4 senddata
7 x! E( a/ e; D! j% r/ ymin=dminus(1);
2*x(1)+2*x(2)<12;
@for(S_Con_Num(i)sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i));
end

6 f+ _7 c3 Z5 M, S$ x; \; h

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

求第二级目标，LINGO 程序如下：

model:
5 o% C" ^+ d, n0 y  S# W5 q1 @sets:
variable/1..2/:x;
S_Con_Num/1..4/:g,dplus,dminus;
0 r4 F' D9 D) {' W* aS_con(S_Con_Num,Variable):c;
0 A6 x7 k9 t% h. y# d$ l# Xendsets
data:
g=1500 0 16 15;
c=200 300 2 -1 4 0 0 5;
  O, P4 ~7 M/ g+ O8 aenddata
min=dplus(2)+dminus(2);    !二级目标函数;
2*x(1)+2*x(2)<12;
@for(S_Con_Num(i)sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i));
dminus(1)=0;!一级目标约束;
@for(variablegin(x));
end
+ h9 d2 J: B% d: r; _$ D0 i
求得目标函数的最优值为 0，即第二级的偏差仍为 0。 求第三级目标，LINGO 程序如下：
. p% Q6 E! c2 [& D) M8 J) n
model:
sets:
variable/1..2/:x;
S_Con_Num/1..4/:g,dplus,dminus;
S_con(S_Con_Num,Variable):c;
endsets
data:
4 J! O& [0 K; c+ k  {5 ^) e9 Dg=1500 0 16 15;
, c* }  a$ G' r! fc=200 300 2 -1 4 0 0 5;
enddata
min=3*dplus(3)+3*dminus(3)+dplus(4);    !三级目标函数;
! u6 z. d. B4 C6 `2*x(1)+2*x(2)<12;
@for(S_Con_Num(i)sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i));
dminus(1)=0;!一级目标约束;
# ]. r# A  V4 Cdplus(2)+dminus(2)=0;!二级目标约束;
end

- D! l1 L+ E5 i; j3 K目标函数的最优值为29，即第三级偏差为29。
" g' E; P/ X& T" k* \' u" b- x
分析计算结果，  ，因此，目标规划的最优解为   ， 最优利润为1600。
3 W8 \& Z1 y4 U8 @: R: D; U/ Z
上述过程虽然给出了目标规划问题的最优解，但需要连续编几个程序，这样在使 用时不方便，下面用 LINGO 软件，编写一个通用的程序，在程序中用到数据段未知数 据的编程方法。
9 I7 W( K5 p+ X" d% [* @+ L1 B8 J' |, ?
5 v  q4 S# I! D. v$ O: A例 4（续例 3）  按照序贯式算法，编写求解例 3 的通用 LINGO 程序。
( v' T" Y+ l0 A# ~0 f+ r
model:
: b# f! @. w8 j3 t  qsets:
level/1..3/:p,z,goal;
variable/1..2/:x;
3 _: a( [1 m1 d$ U4 i; P! rh_con_num/1..1/:b;
s_con_num/1..4/:g,dplus,dminus;
, W, {0 G, U9 D! h$ N% {; t) Yh_con(h_con_num,variable):a;
s_con(s_con_num,variable):c;
5 Z% H& K1 k4 Bobj(level,s_con_num)/1 1,2 2,3 3,3 4/:wplus,wminus;
endsets
+ j" a7 I1 |) n& C  Ydata:
) N) H8 ?; k. l2 z5 g( W3 a* z9 |ctr=?;
% I' f) [1 g% a3 m' {7 t; q) Igoal=? ? 0;
: }9 R# y7 ^$ \/ r$ y( P( X! Zb=12;
g=1500 0 16 15;
3 E) G2 g4 [3 x' z" f, a7 ba=2 2;
( i" |5 G4 t2 J: G7 @0 oc=200 300 2 -1 4 0 0 5;
9 _1 j: b/ Q. N6 jwplus=0 1 3 1;
wminus=1 1 3 0;
enddata
min=@sum(level:p*z);
p(ctr)=1;
, K8 X" @! N0 i7 s4 b+ T@for(level(i)|i#ne#ctr:p(i)=0);
2 u) w( `  L7 D% y@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)));
end





4  多标规划的 Matlab 解法

多目标规划可以归结为

［x,fval］= fgoalattain('fun',x0,goal,weight)           
［x,fval］= fgoalattain('fun',x0,goal,weight,A,b)           
, X  U$ Y: f1 K& s+ I3 \［x,fval］= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq)           
［x,fval］= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)

& F9 y; m: a; m" V
要完整掌握其用法，请用 help  fgoalattain 或 type  fgoalattain 查询相关的帮助。
例 5  求解多目标线性规划问题


- h( ]% `! t2 M: _& k& X( F; }
1 g3 K+ F+ B8 Z6 y解  （i）编写 M 函数 Fun.m:

1 |% K4 B, H" M  Pfunction F=Fun(x);

6 \$ C' X$ _7 N& ?F(1)=-100*x(1)-90*x(2)-80*x(2)-70*x(4);

6 P( K) Y: ]- }) JF(2)=3*x(2)+2*x(4);

5 Q; u  E& q+ H' n* }: v$ a, C（ii）编写 M 文件

a=[-1 -1  0  0   
   0  0  -1 -1   
   3  0   2  0   
   0  3   0  2];
5 A; p+ ?9 H3 s' z/ Xb=[-30 -30 120 48]';
c1=[-100 -90 -80 -70];
c2=[0 3 0 2];
/ {& L9 V: V( B9 b  t6 F[x1,g1]=linprog(c1,a,b,[],[],zeros(4,1))  %求第一个目标函数的目标值
0 P0 w. y0 d2 c[x2,g2]=linprog(c2,a,b,[],[],zeros(4,1))  %求第二个目标函数的目标值
g3=[g1;g2]  %目标goal的值
[x,fval]=fgoalattain('Fun',rand(4,1),g3,abs(g3),a,b,[],[],zeros(4 ,1))
7 Z' ^( w! F  Y& X. P0 _$ e! Q%这里权重weight=目标goal的绝对值
! N; F: D( \' K! T
0 w! Y  a: l3 h+ o( b' F

就可求得问题的解。

习题

; r* d8 r( O& M7 o' c0 H
7 V, k! [% t) r: m; l" M8 W$ |————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
6 B  q8 i( e0 ?! C原文链接：https://blog.csdn.net/qq_29831163/article/details/89488932