解线性目标规划的《量化优先因子法》

维普资讯 http://

第3卷第7 3期20 0 3年 7月

数学的实践与认识

v l 3 o7 o3 _ N .J l,2 0 uy 0 3

M A TH EM ATI CS N I PRA CTI CE AN D H EO RY T

解线性目标规划的《化优先因子法》量一

基于 L过程的算法 P王琦(东江门五邑大学数理系，广东 5 9 2 )广 2 0 0

摘要：本文提出一种解线性目标规划及整数线性目标规划的《化优先因子法》即把目标规划中表示优 量 .先等级的优先因子 p (￣ 1 2,,用能从数量级上刻划优先因子>>+的本质特征的数来表示，而 t1,… L) 进用S AS/ OR软件包中解线性规划的 LP过程即可求解此线性目标规划 .通过实例给出算法与用 LP过程求解的程序 .

关键词：线性目标规划； 优先因子； P过程 L

1引

言

目标规划是二十世纪六十年代初查尔斯 ( h r e )库柏 ( o p r提出的.进而，尔 C ans、 C oe)查

斯、柏、杰尼 (j i及其它科研工作者于六十一七十年代总结出建立在单纯形法基础上库伊 Ii ) r的求解线性目标规划的方法 .J P . .伊格尼乔 (g i o 1 7 I nz ) 9 6年著《 i目标规划及其扩展》上将述工作推广到能解决相当部分的各种各样的非线性、数、一 1即变量只能取值为 0或 1整 O ( )的目标规划 .采用的方法是将求解非线性与整数单目标规划的某些成功的方法同基本目标规划的算法结合起来 .但其对目标规划模型的求解均是建立在使用线性与非线性目标规划

的软件包上的，且认为不能用线性规划的软件包来求解线性目标规划 .并 本文提出的解目标规划的《化优先因子法》量与文[ 3观点不同，文的方法是将优先 6的本因子数量化后，需使用 S/只 AS OR( tt t a An ls y tm/Op r t n R s ac )件 S ai i l ay i S se sc s e ai e e rh软 o中解线性规划的 LP过程来求解量化优先因子以后的模型一此时线性 (整数线性 )或目标规

划模型已变为了线性

(整数线性 )或规划模型，线性 (整数线性 )划模型的最优解，为此或规即原线性 (整数线性 )或目标规划模型的满意解 .该方法的提出，得极难求解的线性目标规使划问题的求解变得简便，求 .易 即本文提出了一种及其简便的可用线性规划软件包解线性目标规划及整数线性目标规划模型的方法：量化优先因子法》并给出了相应的用 S/《, AS OR软件的 L P过程求解线性 (或整数线性 ) (目标规划的程序 . 本文所研究的目标规划模型为 ( ) GP:L^

M n一∑P∑叫+叫 ) i (五f左收稿日期： 0 1 0— 4 2 0— 9 0

(.) 11

解线性目标规划的《量化优先因子法》

维普资讯 http://

2 6

数

学

的

实

践

与

认

识

3 3卷

f (, …, 工l z, z )+

—

一，∈{,,, ) 1 2… k

(. ) 1 2 (. ) 1 3

l z, 2…, ( l X, X ) (, )f i 1 2…, g 一 6,一，, m I』 0 J= 1 2…, , z,, ’

(. ) 1 4

本文主要讨论^ (一 1 2…,与 g(一1 2…, )为线性函数的情形， (愚，, K) ,, 均即 GP)线性目为

标规划，为 ( GP)记 L .一但优先等级 P (一 1 2…,确定，必有 P O m P+ (= 1 2…,,z,, L)则 r t z,,L)立 .成

求解上述 ( GP)型所得的解，为该目标规划的满意解 .模即

2量化优先因子法方法对于已统一了量纲或无量纲化的线性目标规划 ( GP)型中目标函数的优先因 L模厶∈ (,,,} 12… k:工

子 P(一 1 2…,,权系数 wg, fz,, L)与1 )令 P, 0 z一 1 2…,, (,, L)

P一 1 l;

2 )取 P,在数量级上远远大于 P的数，如取 t为…例L-

1

1—1

Pl一 0 9 9,Pz一 0 0 0 9 9,…,PL一 1一 . 9 9 .0 0 9 9

Pt;

, l I

3令权因子满足∑ (+硼 ),三 0硼 ) 一1 i三， 0∈(,,志=, 12…,}1

经过上述三步以后 ( GP)型就变为 ( P)型 .进而使用具有高速度与高

精度的 L模 L模s/ As OR中解线性规划的 L P过程即可完成对线性目标规划模型的求解 .

3实

例

例 17]某单位领导在考虑本单位职工的调资方案时，次遵守以下规定：【 9巾依1 )不超过年工资总额 6 0 0元； 00 2 )每级的人数不超过定编规定的人数； 3 )二、级的升级面尽可能达到现有人数的 2 ;三 0 4 )三级不足编制的人数可录用新职工，一级的职工中有 1 的要退休 .有关资料见下表 0

解

设 z,z, a别表示提升到一、级和录用到第三级的新职工的人数，定各目 zz分二确

标的优先因子为： P一不超过年工资总额 6 0 0元； 00P一每级的人数不超过定编规定的人数； z

P一二级、级的升级面尽可能达到现有人数的 2 ; a三 0建立目标规划模型为

解线性目标规划的《量化优先因子法》

维普资讯 http://

7期

王

琦：线性目标规划的《化优先因子法》一基于 L过程的算法 解量 P+ p2+ (++ z2 一 z2 z + 3

2 7

M i z= p- n

十 ) p (++ — - d2+ + - d3+

)= 9 0= 00 = 3===

5 0+ 5 0+ l 0 x3 0 x1 0 x2 O 0+,

2 71

一 z1

3

d- i一： -—

= =0一

,

21 7

2. 4

z2z1 2 z3 0,d7,,, 0, = 1,…, 2, 6

+ d;一 -

一3

文 1 3解线性目标规划的单纯型法得到多重解，总于 I, 1 o表 4 9 -用 7汇 - P l3 7— .本文用量化优先因子法求解此模型 . 第一步：化优先因子：量取Pl= 0. 99,户3* P2* = 0 03 .0 3, P2* 一 0. 003 3, P2* 一 0.0 3, 03 一 0. 005, 00 P3*w; -一 0. 00 00 5

第二步： S/用 AS OR软件中 L P过程编 S AS程序如下：程序中， d l d 2分别表示在用 k,kf, (= 1 2 3 4, .表示 . (= 12 3.五，,,)用 2 7』 2 - 7『,,)』

da a L6; t

ip t rw￥x 2x d 1 1 2 2 3 3 d 1 4 d 1d 2d

1d 2_y e￥一 h一 n u _o _ lx 3 l d 2d 1d 2d 1 2 4 2 5 5 6 6 tp d d R S;cr; a ds

s be t . . . . .90 00 3 . . 3 . . 3 . 0 50 00 0 50 mi ujc 0 0 0 0 09 . .0 30 00 30 00 300 0 . .0 0 . 0 0 0 nc onl c 2 on c n3 o c n4 o c n5 oc 6 on

.9 0 00 3 3 0 2. 43

5 0 1 00+1. 1 0. 0 00 50 0一. . 1 0. 0. 0. 0. . 1 .+1一 .

0. 0. 0. 0.

0 0. . 0. 0. 0. 0.

0. 0. 0. 0. 0. 0 . 0. 0. 0. 0. 0. 0.

0. e q e q e q e q

0. 0. 0.

— . 1 0. 0. 0. 0. 0.+1一 . 1 . .1 0.一 . 1 0. 0 0. 0. 1 . . 1 0. 0. 0. 0. 0. 0. .0. 1 0. 0. 0. 0. 0. .

0. 0.+1一 . .1 0. 0.0. 0.

0. 0+1一 . 0. . .10 0 . .

0. e qe q

0. 0 .+1一 . . 1

p o p; r cIr un;

执行上程序，输出结果的解概要中，得 I, 1 o表 4 9解 1在可 - p 13— 7 .根据解 1中工资总额的结余额，调整上程序亦可得表 4 9中解 2解 3解 4再—、、 .

例 2反例之反例 ( I, 1 9例 7 1给优先级分配数字的反例 .)见 - p8 3— 6 .Mi 2一 P1 - P ( d-一 d n}+ 24￣ 7).

2 7 1

+ . 2 7 2

+

—}= 4 - —;一 8 - O—一 8 O

8 l+ 1 x+ x 021 x 0 l+ 8 x2+

0 (一 1, ) 2, d, 7

0 (= 1, 3 2, )

解

第一步：化优先因子， P=0 9 9,P *wi 0 0 0 8 2 量令。 . 99 2 - . 0 0,P *=

=0 0 0 2 . 0 0

编S AS程序如下： 第二步：用 S/调 AS OR软件中 L P过程，程如下：编

解线性目标规划的《量化优先因子法》

维普资讯 http://

2 8

数

学

的

实

践

与

认

识

3 3卷

d t: a a ai ut np—

r ow_

￥ xlx ld1 21 d 2d 1 d 2 t pe￥ RH S; 2 dl 2 d

2 3 3 y_一一一

c r s ad;

o j c 0 0 0 09 9 00 0 8 0 00 0 2 . mi be t . . . .9 9 .0 0 . .0 0 0 nco nl c on2 1 1 . . 1一. .1 8. 1 0. 0 0. . 0. 1 . 0. 0.一 . 0. 1 0.

.4

e q

0.

e q

80

c n3 o’

1 0. 8.

0. 0.

0.

0.

1 .

一. 1

e q

8 0

po r c Lp;r un;

从输出结果的解概要中可以得到此线性目标规划的最优解为： X。一 (, ) O4,}一 0 4+ ., 一 28 0

此结果同[]线性目标规划软件包求出的结果 .即量化优先因子后，以用线性规划软件 6用可包求出线性目标规划的解 . 例 3求解下面 O 1型整数线性目标规划模型[p]一 6z . .4M i n— Pldt+ dt)+ Pz (6 l+ Xz+ 4 x3+

+ P3 f

— dt一 7

4 xl+ 2 xz+ 2 x3+ dE— dt一 67 xl+ 3 xz+ 7 x3+ — dt一 1 7

4 xl+ 2 xz+ 2 x3+ di一 -

一 8

X, z— 0或 1 d lX, 3, T,

三 0一 1 2 3 4三，(=,,,)

模型求解本文用量化优先因子法求解 .

第一步：化优先因子：量令 pl 0 9 - . 9,pl*w 1 - 0 4 5 2 . 9,pl*w2 - 0 4 5,p2 0 0 9 2 .9= . 0 9,p3 0 0 0 - .01

第二步： S S程序如下：编 Ada a a; t

Ip t l 2x l d 2d 1 d 2d 1 3 d 1 4 n u x x 3d 1 1 2 2 3 2 4 2 t e￥ d d yp_一

RH S;一

c r s ad;

O O O 0 0. . 495 06 l 4 1 - 1.

.

0 4 5 0.0 0. 0 0 . 9 0 99 001 0. .

mi n.

0. 0 .1一 . . 1

0.O.1 .

0.

0. 0.

0. O.0 .

e q e qe

7 6l 7

4 2 2 - 7 3 7-

O 0

.

0.

0- 0. 0 O一.

0.

0.

. 1.

0 .

4- 2- 2

0 ..

0..

O..

0.

1.

.. 1

.

e‘ q up e b p rdi e r tge

8 ..

.

2

3

.

.

.

.

.

.

p ocLp r;

解线性目标规划的《量化优先因子法》

维普资讯 http://

7期

王琦：线性目标规划的《化优先因子法》一基于 L过程的算法 解量 P

2 9

执行程序可得最优方案为 xl, 2一1 x—1 z—0显然此即为原 0 1目标规划的满意解 .,3,—

4结语与有待进一步解决的问题1 )本文作者已用该方法完成了<筹学>]运"中线性目标规划、数目标规划 ( 0 1目整含— 标规划 )求解工作，明用此方法求解线性目标规划应该是可行的；等说 2 )从理论上完善此方法是有待进一步考虑的问题，于线性目标规划的求解是建立在介单纯形法的基础上的，单纯形法的理论来完成此方法的证明正在进行和进一步完善中.用 能否用其它方法证明量化优先因子法的正确也是有待研究的课题 . 3 )介于目标规划的软件包很难找，如果离开计算机，令是很简单的目标规划也不而即容易求解，以本文提出的方法在完善其理论证明后，为线性目标规划求解提出了一个简所就便、速的方法 .快

4 )能否将量化了优先因子的线性目标规划，其他的线性规划软件包求解也是值得尝用试的课题 .

5 )能否用量化优先因子法求解非线性目标规划，们正在进一步的研究中 .我参考文献：[ Ch re 1 3 an s A,C o e W .M a a e n o esa d Id sra Ap l ain fLie rP o rmmig[] o p rW n g me tM d l n n u til pi t s o n a rg a c o n M .Vos lI n, l,Ne Yo k:J h i y& S n,1 6 . ad l w r o nW l e o s 9 1

[2 Ch r e] an sA,e 1 A g a p o r mmig mo e frme i pa nn J .M a a e n o e o daPa nn ta. o l rg a n dl o da ln ig[] n g me tM d lfrMe i ln ig.M a a me t Sce e, 1 6 n ge n i nc 9 8, 1 ( 4

8):I 8 1 3 3— 5.

[] C an s A,e 1 Noe o n a pi t n o o lp o rmmig mo e o da pa nn J . Ma a e n 3 h re ta. t n a p l ai fa g a rga c o n d lfrme i ln ig[] n g me tS i n e,1 8,1 8 ce c 96 4( ):43— 4 6 1 3.

[] Ch r e,Ni a sR .A a rg a 4 a n sA l u J h Go l o rmmigfr a p we ln ig[] P n o n o rPa nn M .M a a e n ce c sac p r M n g me tS in eRee rhRe otI 5,Pit b gh:Ca n gi- e l n v r iy, 1 6 . I t s ur r e eM l on U i e s t 9 8

[] Ir Y.Ma a e n asa d Aco t gfrCo to[] hcg a dMc al 5 ii i n g me tGo l n c ui o nrlM .C ia o: n n l n y& C o,1 6 . 9 5[ 3伊格尼西奥 JP著，胡运权译 .目标规划及其应用[] 6 M .哈尔滨工业大学出版社，1 8 . 9 8[]甘应爱等 .运筹学[] 7 M .清华大学出版社，9 0 1 9.[]倪勤 .S 8 AS最优化软件速成[] M .科学出版社， 9 8 19 .

A e ho f r So v ng Li a oa og a m i M t d o l i ne r G l Pr r m ng byM e s i i r t c o t N um b r a ur ng Pr o i y Fa t r wi h e—

t l o ihm s d o t he A g r t ba e n he Lp o e s Pr c sW ANG Qi

( p rm e to a h m a is& Ph sc De a t n fM t e tc y is,W y i nv r iyJa g e u ie st in m n,Gu n d n 2 0 0,Ch n ) U a g o g5 9 2 iaAb t a t I h s p p r,we p e e ta n w t o o ov n i e r g a r g a mi g ( r sr c: n t i a e r s n e me h d f r s lig ln a o lp o r m n ol e r it g r g a r g a i a n e e o

lp o r mm i g) b a u i g p i rt a t r t u n n y me s rn ro iy f c o s wih n mb r Th i e r g a e. el a o l n

p o r mm i g, ( r i e r i t g r o l p o r mm i g ) who e r o iy f c o s a e b e r ga n o l a n e e g a r g a n n s p i r t a t r h v e n

n mb r d,c n b o v d sn t e LP Pr c s o ov n i e r p o r u ee a e s l e u ig h o e s f r s li g ln a r g mmi g n S/ n i AS ORs f wa e o t r .S m e e a p e r i e o l m i a i g t e a g rt m n h r g a o x m l s a e g v n f r i u n tn h l o ih a d t e p o r mm e Fi l l naly.

s v r lo h r q e to s o e e r h l d b h s m e h d a e ls . e e a t e u s i n f r s a c e y t i t o r itKey o ds: w r lne oalpr i ar g ogr m m i a ng;prort a t i iy f c or; LP oc s Pr e s