范文一：指派问题例1的数学模型

该题的数学模型为：

miny = 37.7x11 +43.4x12+33.3x13+29.2x14 +32.9x21 +33.1x22+28.5x23+26.4x24 +33.8x31 +42.2x32+38.9x33+29.6x34 +37.0x41 +34.7x42+30.4x43+28.5x44 满足：11 + x 21+ x 31+ x 41=1 （A 只能一个人干） 12 + x 22+ x 32+ x 42=1 （B 只能一个人干） 13 + x 23+ x 33+ x 43=1 （C 只能一个人干） 14 + x 24+ x 34+ x 44=1 （D 只能一个人干）

x 11 + x 12+ x 13+ x 14=1 (甲只能干一项工作） x 21 + x 22+ x 23+ x 24=1 （乙只能干一项工作） x 31 + x 32+ x 33+ x 34=1 （丙只能干一项工作） x 41 + x 42+ x 43+ x 44=1 （丁只能干一项工作） x ij =0，1 （i ，j=1，2，3，4） miny = ∑∑b ij x ij i =1j =1

444

满足：∑x ij =1 （i= 1，2，3，4） i =1

4

∑x ij =1 （j=1，2，3，4） j =1

x ij =0, 1 （i,j=1，2，3，4）

这里存在一个矩阵[bij ] 37.7 43.4 33.3 29.2

[bij 32.9 33.1 28.5 26.4 33.8 42.2 38.9 29.6 37.0 34.7 30.4 28.5

范文二：【doc】一类指派问题的数学模型及解法

一类指派问题的数学模型及解法 第27卷第4期

VoI.27No.42006

青岛理工大学

一

类指派问题的数学模型及解法

胡京爽

(青岛理工大学理学院,青岛266033)

摘要:建立了一类指派问题的0-1规划数学模型,并建立了推广的匈牙利解法.举例演示了解法

的可行性.

关键词:指派问题,0-1规划,匈牙利解法

中图分类号:O221.4

一

般的指派问题?是指:个人被指派去完成项工作,已知每个人做每项工作的某种数量指标(1.,.

如何进行搭配使得完成全部工作后数量指标的总和最小?

引入二维0—1变量X一0或1,表示如果第i个人去做第项工作,则X,取1,否则取0,从而得到指

派问题的数学规划模型:

求minZ一??cXi兰1J=1

s.t?X=1,i一1,2,…,;?X=1,=1,2,….\()或1,i=1,2,….7l,一1,2.…J=1i一1 指派问题可以作为整数规划用分支定界法,或用隐枚举法以及匈牙利解法一.求解.

在实际问题中,有时会遇到更复杂的指派问题:已知A,B两组各有和个人,共有P项工作,现在从

A,B两组人中各取z个人组成z对,去完成z项工作,又知每两个人做每项工作的

某种数量指标C,如何组

队及如何指派工作,能够使完成工作的数量指标的总和最小?这里需要引入三维0—1变量X:0或1,用

以表达组队及工作的选择指派,即,如果在工作分配中A组第i个人和B组第个人配对去做第是项工作,

则X枷取1,否则X取0,从而就形成了三维0-1数学规划模型. 1数学模型

1.1三维指派问题的一般形式

6

求minZ=???cxi=1,=1=1

户p,

s.t??X一Y,1,2,…;??X一=1,2,…;??X一七:::1,2,…,;?=1=1i=1^=1i一1J=1一1

p

—

z,?"一z,?===

式中X驰…Y",均为0—1变量;z?min(m,,)

1.2三维指派问题的特殊形式

在一般形式中,仅考虑z=们====的情形:

求minZ=???cx.

收稿日期:2OO6一O3—3O

126青岛理工大学第27卷

s.t??X.=1,i=1,2.…??X=1,一1,2,…川;??X.=1,k=1,2,…,,2,一1k吉1lI—J,:1J:1

式中X为0—1变量;Cm>0

2指派问题特殊形式的求解方法

2.1概念和性质

定义1设正方体:对于任意的自然数1?i,,k?将数量指标C(=1,2,…,2;=1,2,…,2;k

一

1,2,…,,2)放置在点(k)处,我们称这样形成的数据形式为一指标体阵,记作C一(C.)……

为了方便地表示对体阵的运算,下面引入平面阵的概念.

定义2在空间中建立直角坐标系.规定横轴为X轴,纵轴为y轴,竖轴为Z轴,则C的位置在坐标

为(k)的点处.当固定时.称方阵A=((1,傩)(i一1,2.…)为体阵C的横平面阵;当固定时,称

方阵B,一(C触)(一1,2,…77)为体阵('的纵平面阵;当固定k时,称方阵C=(C)(k一1,2,…,!)

为体阵C的竖平面阵(如图1昕示).

定义3如果体阵C中有一组零元素,它们

分别属于不同的横,纵,竖平面阵,则称它们为独

立零元素组.

定理如果效率体阵中的任意一个平面

阵中的每一个元素,都减去该平面阵中的最小元

素S,新的效率体阵记为c.则以(形成的指派问

题与原指派问题有相同的最优解,最优值减少S.

证明设在第q个纵平面阵上每个元素都减

少,C中元素记为C则有:

???c"X=图1指标体阵

???c.?x+??…x

l=1J=1?J?qk一1i=1女士1

一

???cx+??(一)x一???(_,.x.一??X一???cx一i=1J==1,J?qk1i一1k1l=1,:1k==1l=1==1l=1J_-1k:1 新问题和原问题有相同的最优解,但最优值减少了.

2.2求解方法

2.2.1对效率体阵进行变换

(1)对每个横平面阵的每一个元素分别减去其上的最小元素;(2)对当前体阵的每个纵平面阵的元素

分别减去其上的最小元素;(3)再对当前体阵的每个竖平面阵的元素分别减去其上的最小元素,最后得到

的体方阵中每一个平面阵上必有零元素.根据前面的定理由此体方阵形成的指派问题与原问题有相同的

最优解.

2.2.2寻找当前体阵中的最大独立零元素组

(】)确定只有一个零元素的横平面阵,将其上的零元素用0圈起来,同时将该零元素所在的纵,竖平

面阵上的零元素全部用×号划掉,以保证圈起来的零元素分别处于不同的平面阵中;(2)对当前的体阵确

定只有一个零元素的纵平面阵,将此零元素用0圈起来,同时将该元素所在的横,竖平面阵上的零元素全

部用×划掉;(3)确定当前体阵中只有一个零元素的竖平面阵,圈起此零元素并划掉其所在的横,纵平面

阵上的零元素.反复进行上面的步骤,直到不能进行为止.

对于上面得到的体阵,可能有三种情况:(1)圈的元素个数恰好为,则可得最优解;令圈起来的位

置处的融取1,其它位置处的取0,这时,指派问题的目标函数值为0,达到了最小,问题得到解决;(2)

圈0的元素个数小于,且没有末被标记(圈f)和划×)的零元素.则转至2.2.3;(3)当前体方阵中圈0元

第4期胡京爽:一类指派问题的数学模型及解法

素的个数小于,z,并且未圈0的平面阵中至少有2个以上未标记的零元素,现在对当前体方阵确定只有2

个零元素的平面阵,并选其中1个零元素用0圈起来,划掉其所在的另外2种平面阵中的所有零元素.上述

步骤依次对每一种平面阵的当前状态使用.对得到的当前体方阵,如果属于情形(1),则得最优解;如果属

于情形(2),则转至2.2.3;否则再对当前体阵中未圈0的平面阵进行圈0和划×,在有限步后当前的体方

阵必会化到情形(1)或(2),转至2.2.3.

2.2.3增加新的零元素

(1)由于圈0的个数小于,z,因此必有某横平面阵上没有圈0的元素,则:?将这些横平面阵作上标记

V(上面没有圈0的元素,将来要留下);?用V标记这些横平面阵上的所有零元素所在的纵平面(将来要

盖住);?用V标记这些纵平面阵中圈0元素所在的横平面阵(表明标记V横平面阵包括两类:有圈0元

素和没有圈0元素的,将来要留下);?反复进行上面的步骤,直到不能标记V为止. (2)对当前的体阵,盖住未标记的横平面阵(这些横平面阵已有圈0)和已标记的纵平面阵.因要在留

下的,标记V的横平面阵上减去一个非零元素,同时要在这个横平面阵的原来的零元素上加上减去的这

个数,以确保变换以后的元素都是非负数,并保证原来的圈0元素处仍为零.?从已标记的横平面阵中未

被盖住的元素中取最小的元素,这个元素一定非零,将未被盖住的横平面阵上的元素都减去它,并且将已

盖住的纵平面上的元素都加上此元素.这样可以保证新体方阵中增加了新的零元素,并且原来的圈0的零

元素保持不变.?如果在标记以后的体阵中,已标记的横平面阵上所有元素都被盖住了,则选1个没有圈

0元素所在的横平面阵,取其上非零元素的最小值,此横平面阵上的元素都减去它,然后将原来此横平面

阵上的零元素所在的纵平面阵元素或竖平面阵元素加上它,这样确保所取原来横平面阵上的零元素保持

不变.这时如果新体阵中的某平面阵上没有零元素,则回到2.2.1重新开始.依此进行迭代,直到得到最优

解.

3计算举例

333

求minZ一???c驰x1J1=1

333333

s.t??X一1,i一1,2,3;??X一1,J一1,2,3;??X私一1,k一1,2,3J=1=1I=1=11J1

式中X舶一0或1

用平面阵形式表示体阵:用3个3阶方阵表示3个横平面阵;每一行9个元素构成3阶方阵,即构成3

个竖平面阵;3个横平面阵的第1列,第2列,第3列分别构成3个3阶方阵,即构成3个纵平面阵.所有迭

代过程在其上进行.

『345]『468]『61o13]

(1)初始体阵的展开式:f789ff4712ff141118f;l1194Jl1829Jl1964J

(2)对初始体阵第1个横平面阵每个元素减3,第2个横平面阵每个元素减2,第3个横平面阵每个元

r02]『246]『260]

素减4:l456ll2510ll10714I;L861jl16o7jl152o1

厂02]『246]『260]

(3)对(2)的新体阵第2个竖平面阵每个元素减去2:I234Il038Il8512I,此新体阵 L861Jl1607Jl1520J

中每个平面阵上都有零元素;

?12]246]26.]

(4)对(3)新体阵进行圈0和划×:l234Il38Il8512I l861Il167Il152?I

128青岛理工大学第27卷

(5)竖线表示盖住纵平面阵,斜线表示盖住横平面阵:l{

(6)村(5)禾盂任兀系藏去最小兀系1,开在盂住的两个纵半向阵上加1开O和划×: 311]2.345]『_3.51239192];『llll3I'37Il6I;

l86Jl166Jl163?J

(7)对(6)第1横平面阵元素都减去1,第1纵平面阵元素都加1,第3竖平面阵都加1:

0

2

3

3

45

.

5

1;1;L

86o儿1815儿1841J

(8)对(7)第2,第3横平面阵分别减去1并圈O和划×:

一]2.234]3422269181]ffl2fi5f

l86Jl1704Jl173?J

由此可得最优解:当X一1,X一1,X一1其官X一0时,达到最小值:4+4+4—12. 参考文献

[1]钱颂迪.运筹学.北京:清华大学出版社,1990

[2]何坚勇.运筹学.北京:清华大学出版社,2000

[3]成思危,胡清淮,刘敏.大型线性目标规划及其应用.郑州:河南科学技术出版社,2000

TheModelandSolutionofaKindofAllocationProblem

HuJing—shuang

(SchoolofScience,QingdaoTechnologicalUniversity,Qingdao266033)

Abstract:ThispaperstatestheestablishmentoftheO-1programmingmodelaboutakindofa1

1ocation

problem,andgivesthesolutiontotheproblem.

Keywords:allocationproblem,O-1programming,Hungarysolution

作者简介:胡京爽(1964一),男,副教授

O

—...,................L -L___f_______________??t__J

241

?

r?

hD?,P

范文三：关于多因素模糊指派问题的数学模型

关于多因素模糊指派问题的数学模型 关于多因素模糊指派l闭题的数学模型

刘心

(东北财经大学数学与数量经济学院,辽宁大连116025) (摘要]本文从经典指派的一般分析出发,运用模糊数学的方法,通过建立单因素"印象矩阵",

对程度模糊集加权,计算单因素评判矩阵,建立多因素评判矩降一l系列过程及最小调整法,对多因

素指派问题进行综合分析和研究,提出了一种关于多因素模糊指派问题的新的数学模型,解决了

经典指派问题在实际问随中的某些不足i进而得到一种在实际问题中普遍适用的方法.j

(关键词]指派;最小调整法;模糊集;评判矩阵.薯..一u.j?

中图分类号:砣24.3文献标识码:A文章~:1008-4096(20O8)o6-0026-03_

一

,引言

运筹学所研究的指派问题,通常是传统的指

派问题.但一般情况下,在工作未完成之前,其

效率矩阵中的元素应该是不确定的.为了得到具

有指导性的决策,有必要对效率矩阵中的元素进

行统计或粗略估计,由此产生了更加贴近于现实

生活的模糊指派问题.有关模糊指派问题,已有

诸多论述,但方法不一.本文通过对多因素指派

问题进行综合分析和研究,提出了一种关于多因

素模糊指派问题的新的数学模型.

运筹学中的指派问题的一般提法是:设有n

个人(或机器等)A,A,…,A,分派去做

n项工作B,B,…,B,要求每项工作需且仅 需一个人去做,每个人需做且仅做一项工作.已 知A完成Bi工作的时间(如工时,成本,费用 等)为C?问如何指派,才能使总的工作时间 最少?

设xi表示A完成Bi工作,并令

r1当指派A去完成B工作

X..={.【0当不指派A去完成B工作 则指派问题数学模型的标准形式为 minZ=

..

cx(Cij?o)

x(i:,2,…,n)

{x1(j=1,2,…,n)

【x皆为0或1

由Cii组成的方阵C=(C.)称为关系矩 阵,只要关系矩阵C给定,指派问题也就相应 确定.

在运筹学中的求解指派问题一般用匈牙利算 法…,由于它由匈牙利数学家柯尼格提出,因 此而得名.此外还有最小调整法嵋j,该方法更 加便捷.

例如:(最优匹配问题)现有A,B,c,D 四项工作,需要甲,乙,丙,丁四人去做,并且 每人只能做一项工作,同时每一项工作必须且只 需一人去做,四人做每项工作所支付的费用 如下:

\\ABCD

田21097

乙1510148

丙l314l611

丁415139

问如何指派使支付总费用(单位:k元) 最低?

由表中的数据构造一个关系矩阵

.

(2)10(9)(7)]I-210(9)(7)]

15(4)148ll15(4)148I叫}

13141611ll131416(11)I .415139JL(4)15139J 收稿日期:2008@9-25

作者简介:刘心(1961一)女,辽宁阜新人,教授,博士研究生,研究方向为经济优化.

26

c-

派问题,就需要利用模糊综合评价的思想去考 虑,由此得到评判矩阵B,然后再利用最小调整 法解B,求出最优解.为此,提出如下方法: 1.建立单因素"印象矩阵"

设P={P,P:,…,P}为被指派的13个

人组成的集合,W={w,W,…,W}为所

指派的n项工作组合的集合,U:{u,U:, …

,U}为所考虑事物相关的因素(如考核教 师教学效果时的熟练程度,涉猎的深广度,逻辑 性,生动性,启发性等因素)集合,其中U为 第i个因素(i=l,2,…,1).

对于u中的第i个因素u,设所有可能出现 的评语有m个,记作V={v,v,…,v},

称之为评语集或程度模糊集(如{很好,好, 一

般,不好};{优,良,及格,不及格}等), 用来刻画每个人完成工作的熟练程度或满意 程度.

由因素ui确定该事物对评语v(j=1,2, …

,m)的隶属度r.i,得出第i个因素ui的单因 素评价集

ri:{rIl,r,…,rim}

它是评语集V上的模糊子集,也就是说, 给出一个模糊映射

f:U—F(V),Ui—f(U,)

其中f(Ui)=r=(ril'rI2,…,ri)为

关于因素ui的评语模糊向量,rii为关于第i个因 素ui具有评语vi的程度,rii?[0,1]. 令r1为第h个人P完成工作W的情况具 有评语vi的程度,构造矩阵R

R=

rkl1rk12''

rk21rk22

rkn1rkn2..

V1V2''

pI

p2

???

P

称此矩阵为在因素Ui下完成工作W的"印 象矩阵",由于k:1,2,…,n,所以在情况U;

下可以得到13个类似矩阵R,R,…,R.又 由于u?U(i=1,2,…,1),所以整个过程可 以得到l×n个这样的矩阵R(i一1,2,…,l, k=1,2,…,n).

2.对程度模糊集加权

由于程度模糊集{v,v:,…,v}中各种

评价的作用不尽相同,其重要性不宜平均看待, 27

mm.m

..

?.

必须综合考虑.因此在第i个因素H.(i=1,2,

…

,1)情况下,对程度集{v.,v,…,v

加权,得到权重矩阵Q=(q,q,…,q), m

qi?[0,1],q=1.其加权原则是:对于作 用较大的v,给予较大的权重,作用较小的v, 给予较小的权重或零.

3.计算单因素评判矩阵

计算矩阵:OR

这里取为模型M(?,+)(普通矩阵乘

法),为加权平均型的综合评判,依权重的大 小对所有因素均衡兼顾,比较适用于要求总和最 大的情形.R是R的转置,并设

Qw,r

Q

???

QR

称B,(i=1,2,…,1)为在因素u.下的 评判矩阵,则在因素{U,H,…,tl下,有 1个类似的矩阵.

4.建立多因素评判矩阵

由于因素集u的各因素的重要程度不同, 对因素集U={u,H,…,u加权,得权重 矩阵Y=…Vy,…,U},因此在多因素条 件下,lq个人完成某一项工作w的情况为 QR

QR

???

QRlKT

阵B

28

QR

Q:R

则在多因素下,n个人lq项工作的评判矩 B=

YBll

YB:2

???

YB

b1lbl2…bl

b2Ib22…b2

b1bIl2?一b

5.计算矩阵B的最优解

利用经典指派中的最小调整法求出最优解, 最小调整法步骤如下:

(1)取矩阵的每列的一个最小(最大)值,

加括号,得到一个最小(最大)方案.若这些 加括号元素又分属于不同行,则得到相应模糊指 派问题的最优解,否则转(2).

(2)把有两个以上加括号的元素的行中的某 一

个改到同列的其他处,待到某一无加括号元素 行中有一元素加括号,则算一次调整.如此进 行,直到每行有且仅有一个元素加括号为止.每 次调整均以目标函数(其值为各加括号元素之 和)增值最小为原则,即得到相应指派问题的 最优解.

这里需要指出:

(1)在单因素情况下只需计算到第3步, 然后计算B的最优解.

,很多信息来源于人,因此 (2)在实际中

带有一定的主观性,可能包含了一些错误信息, 但从总体上去分析利用综合评判的思想可以去掉 错误信息.此方法对于因素很多时显得很麻烦, 但在实际问题中还是有一定效果的.

参考文献:

[1]程理民,吴江,张玉林.运筹学模型与方法教程 [M].北京,清华大学出版社,2000. [2]夏少刚.运筹学——经济优化方法与模型[M].北 京,清华大学出版社,2005.

3]邹开其,杨听光.指派问题的模糊方法[J].模糊系 统与数学,1999,(Vo1.13). 4]陈水利,李敬功,王向公.模糊集理论及其应用 [M].北京,科学出版社,2005.

(责任编辑:杨放)

范文四：一类指派问题的数学模型与算法研究

一类指派问题的数学模型与算法研究 第25卷第4期

Vo1.25No.4

徐州工程学院(自然科学版)

JournalofXuzhouInstituteofTechnology(NaturalSciencesEdition)

2010年12月

DEC.2O1O

一

类指派问题的数学模型与算法研究

吴树猛,张埂

(中国矿业大学理学院,江苏徐州221008)

摘要:通过建立一个多目标整数规划模型来描述火车站列检任务分配问题;用遗传算法求得

了模型的满意解.研究结果表明改进后的交叉和变异算子显着提高了算法的有效性.

关键词:整数规划;指派问题;遗传算法

中图分类号:0221文献标志码:A文章编号:1674—358X(2010)04—0013—05 列车技术检查是一项十分重要的工作,对于保证列车的正常运行和旅客安全有着极其重要的作用.列检

工作任务繁重,对列检作业人员要求高,所以必须对列检任务进行合理的分配,这对保障列检作业过程的安

全以及提高作业人员的工作效率有重要意义.

1建立模型

1.1问题概述

根据客车列检技术检查作业标准,终到车不列检,始发车在出站前15min进行列检.对于通过车,在站

时问小于6分钟的不列检,其它车辆列检.列检作业人员的作业准则如下:(1)列检

工作按作业队进行,每列

需要列检的列车由一个队负责;(2)作业人员在列车进站前5min到达相应的股道(站内停靠列车的轨道)

等待列车的到达,作业人员在列车完全离开车站后离开作业股道;(3)作业人员需要跨股道前往作业点时,

如果股道上没有列车,可以直接跨越;如果股道上有列车且有号志,作业人员可以从列车下面通过;如果中间

股道上有列车但没有号志,作业人员只能选择从股道的两端通过;(4)当某个列检作业队需要列检的下一列

车至少3Omin后才能到达时,作业人员可以回到股道两端的休息室等待,这种情况下,作业队对下一列车进

行检查时不需要跨越股道到达作业点.列检任务分配方案的相关要求如下:(1)基于安全性考虑,要求作业

队跨越股道数量总和最少;(2)同一班次(如白班)内,各个作业队的工作量(检查列车的数量)基本一致;(3)

各支作业队结束其最后一列车检查任务的时间应该与下班时间基本一致(即白班或夜班最后进站的几辆车

应该由不同的作业队进行列检);(4)各个作业队的就餐时间设计相对合理,应与正常就餐时间大致相同.

1.2列检任务分配方案的数据串表示

假设一个班次有支作业队,辆待检列车,建立一个由0,1组成的参数数据串z,如下: 一1

.

1z1,2…zl,322,

1…z2,"

…zm,

1z2……,(1)

其中,72?{0,1)(i一1,2,…m,J===1,2,…,),若,一1,则表示第i支作业队列检第辆车,否则表示第i

支作业队不列检第J辆车,且

?:1,一1,2,…(2)i=1

数据串分成m等份,每部份由,z位组成,共m×位,所有.76组成的集合计为X.(2)式确保了一辆车

只分配给一支作业队.这样,任何一个列检任务的分配方案都可以用一个rn×位0,1数据串表示.

1.3目标函数

(1)作业队跨股道数量总和最少.

跨股道数量的定义(指列检工人不走股道两端情况下的跨股道数量,实际上在求解的时候,让列检的相

收稿日期:201O1O16

作者简介:吴树猛(1982一),男,江苏徐州人,硕士研究生,主要从事运筹学研究 ?

13?

徐州工程学院(自然科学版)2010年第4期

邻两辆车之间尽可能有大的时间间隔,这样列检工人实际作业时可以选择走股道的两端,所以实际的跨股道

数量比这个值还要小):如果某支作业队列检的相邻两辆车所停靠的股道序号为r,rf1且lrf+一I?2,那

么称该作业队结束当前列检任务转而去执行下一次列检任务时将要跨股道,跨股道的数量为十1一rIl一1.

设跨股道数量总和为C,则

C一?C,(3)f=1

其中C为第i支作业队跨股道数量,于是有模型的第1个目标函数 卿c()一cr?(4)

(2)同一班次内,各支作业队的工作量(即列检的列车总数)基本一致. 用每支作业队列检列车数量的方差来刻画各个作业队工作量的一致程度.设每支作业队列检列车数

量为z(一1,…,),则z的方差d可表示为

一

(一),(5)

?1

其中,===},所以模型的第2个目标函数为

miha(X)=(?一x_2).(6)X?,

(3)各支作业队结束其最后一列车的检查任务的时间应该与下班时间基本一致(即白班或夜班最后进站

的几辆车应该由不同的作业队进行列检).

,),结束最后一辆车的列检工作的时间为设第i支作业队下班的时间为a(一1,2,…

(一1,2,…,

m),a?屈,令T一?(a一),模型的第3个目标函数为

m

—in丁(z)一?(a一).(7)?X=

1.4约束条件

在1.2中已经得到模型的第一个约束条件为

?一1,J=1,2,…,.(8)

其次,合理的列检方案不应出现这样一种情况:当作业队正在检查的列车还没有离开的时候,而需要其

检查的下一列车却已经到达,称这种情况为"时间矛盾",计出现"时间矛盾"的次数为N,则应有

N(z)一N:==0,(9)

?X=

其中为第i支作业队出现"时间矛盾"的次数.

另外,为了确保每支作业队在每个班次之内有合理的就餐及休息时间?T,就要求在每天的l1点到13

点之间(晚班23点到01点)各支作业队应该至少有连续的时间段?T,使得在这个时段内没有列检任务,令

每支队在11点到13点时间段内的最大连续空闲时间为丁2,得到模型的最后一个约束条件为

T2()??丁.(1O)

?X

1.5列检任务分配问题的数学模型

列检作业任务分配问题的数学模型为:

目标:

minc()一?C,

min(z)一去(?z一×),

?14?

吴树猛,等:一类指派问题的数学模型与算法研究

约束条件:

minT()一?(a一届)I=1

?.27一1,J一1,2,…il

N(z)一?N一0,i一1

Tz()??T.

其中.7CE{0,1},,37EX.

2模型求解及算法

对于复杂的整数规划问题,目前还没有精确算法有效求解n],故尝试用遗传算法求

解模型的满意解,

求解的难点在于适应函数的定义以及交叉和变异算子的设计. 2.1个体,个体编码及结构空间

以X中一个方案作为个体S,采用二进制编码,即S—aa?…al,naz—az,……a…

a…,a,?{0,

1),s?A,且>:a一1(i===1,2,…,m;一1,2,…,),A为结构空间. i=1

结构空间A和集合X是等价的(这种等价并非在任何情况下都成立,此处的等价源

于模型中的列检方

案恰好可以用一个0,1数据串来表示),所以在求解过程中从个体到参数集就无需

译码.下文在不致混淆的

情况下,个体s和分配方案.2C等价,a和z等价.

2.2适应函数

适应函数的定义比较困难,因为模型是离散的.如何量化个体的适应程度呢?可以采取给个体"打分"的

方法,假定个体的得分随着它接近目标的程度和满足约束条件的程度的增大而呈指数增长,具体如下:

(1)个体要满足的第1个目标是要求作业队跨股道的数量总和最少,由跨股道的定义以及具体的股道分

布图可确定跨股道数量的最大值C,显然最小值为0,即O?C?C,定义个体在该目标上的得分为y一

exp(1一C/C),1?l?e.

(2)个体要满足的第2个目标是要求各个作业队的工作任务尽量均衡,设的最大值为,则有o?

?,定义个体在该目标上的得分为Yz—exp(1--a/a),1?z?g.

(3)对于个体要满足的第3个目标和第3个约束条件,作如下考虑:如果某个个体使得每支作业队检查

的列车的编号越分散,那么该个体就越能有效满足第3个目标和第3个约束条件.这是因为如果要求同一支

作业队所检查列车中相邻两辆车的编号之差要大于或等于m一1,那么就不会出现每个班次最后进站的一

1辆车被同一支作业队列检的情况,或者相邻编号之差小于m一1的若干辆车被同一支作业队列检的情况,

这样,每支作业队的下班时间就不会相差太大.而且,编号越分散,每支作业队在检查相邻两辆车之间就会有

更大的时间间隔,可以使得作业队在休息时间段内有大段空闲时问,同时,时间间隔的增大可以使得作业人

员更少选择跨越股道到达作业点.鉴于此,将第3个目标和第3个约束条件转化成一个目标,即要求分配方

案的m组列车中出现相邻编号之差小于17l一1的次数之和Nb要尽可能小. 设Nb为Nb最大值,则有O?Nb?Nb,定义个体在该目标上的得分为

3一exp(1一N6/N6),1?3?P.

(4)个体要满足的第2个约束条件是出现"时间矛盾"的次数应该为0.设N为N的最大值,O?N?

N,定义个体在该约束上的得分为Y一exp(1一N/N),1?Y?e. (5)由前文可知个体编码方法完全满足第3个约束条件.

综上,定义个体S的适应函数

_厂:A—R.

-厂(5)一yl4-yz+y34-y4,5?A,4?厂?4P.

具体编程求解时,适应函数的显式表达式根据具体的股道分布图,作业队数量及列车时刻表求得.

'

.

]5.

徐州工程学院(自然科学版)2O1o年第4期

2.3进化策略

2.3.1群体大小

设定群体规模大小与个体位数之比为0.7].

2.3.2遗传策略

(1)选择算子:适应值比例选择算子.

(2)交叉算子:点交叉.由于交叉就是一对等位基因进行基因互换,所以,如果等位基因中的两个基因相

同,那么这一对等位基因进行交叉是没有意义的,所以只对那些包含两个不同基因的等位基因进行互换,这

样的等位基因称为"有效互换等位基因".但是采用点交叉从交配池中随机选择的两个个体进行交叉操作后,

会出现交叉后的个体不在结构空间中的情况,所以要对交叉算子进行改进,方法如下:首先,记录随机选择的

两个个体中"有效互换等位基因"的位置,个数以及等位基因在不同个体上的基因类型.假如这样的"有效互

换等位基因"个数小于3则不进行交叉操作(因为交叉后个体没有变化),反之则进行.交叉方法(图1):记随

机选出的两个个体为S和5.,并且在位置3处存在一对"有效互换等位基因",在位置3处,s上的基因为1,

s上的基因为0.第1步,对位置3处的"有效互换等位基因"进行互换,即:在位置3处,s上的基因变为0,

s2上的基因变为1.由X的定义可知,经过第1步的操作,在5上,编号为3的待检列车没有被分配给任何

一

支作业队;在5z上,却有两支队同时列检编号为3的待检列车.为了确保5,5交叉之后仍处在结构空间

中,需进行第二步操作:假如在进行第l步互换之前,在5上,3号列车分配给第2支作业队,该1基因的位

置为+3,而第1步互换之后,第1和第2支作业队同时列检3号车,也就是在s.上,位置3和位置+3处

的基因都是1,所以将5上位置+3处的1基因变为0,同时将S上位置+3处的0基因变为1.其余各

"有效互换等位基因"的互换操作同理.

(3)变异算子:考虑到本文中5和的等价性,所以变异操作是指对每一辆车所分配的列检队伍进行变

异,并使得变异后的个体仍处在结构空间中,具体方法:对于第i辆车来说,在基因,a,…,a中任取一

个,如果所取基因为1则将其变异为0,同时在另外一1个0基因中任取一个并将其变异为1;反之,如果取

的基因为0则将其变异为1,同时将另外一个1基因变异为0. (4)采用精英保留策略:如果当代最佳个体的适应值小于上一代最佳个体的适应值,则用上一代群体中

适应值前1o的个体替换当代群体中适应值后1O%的个体.

2.3.3群体初始化

对每一辆待检列车,随机选择一支队伍,位串相应位置为1,其它置为0. 2.3.4算例结果

为验证模型和算法的有效性,结合徐州火车站的列车时刻表,在Matlab环境下编程求解],取群体规模

为100,P一o.6,P一0.02,进化300代.结果如下:c一56,N一0,一0.2500,Nb一0,厂===10.4781.图2为

适应值曲线.

上

第1步l第2步

11010

?

16?

图1交叉算子

进化代数

图2最佳个体适应值曲线

吴树猛,等:一类指派问题的数学模型与算法研究

3结语

文中模型变量和个体的等价性为编码提供了便利,但同时也为交叉和变异算子的设计带来难度,算例结

果证明了模型和算法是有效的.为进一步降低算法复杂度,提高程序效率,可以尝试研究对个体进行非二进

制编码.

参考文献:

[1]郭倩倩,吴开信,郝光.一类模糊多目标指派问题的解法及应用EJ].西华大学:自然科学版,20O6,25(2):70—71

[2]方必和,刘雪梅.一类特殊二维0—1规划的广义指派模型求解EJ].运筹与管理,2006,16(3):66—68.

E32李敏强,寇纪淞,林丹,等.遗传算法的基本理论与应用EM].北京:科学出版社,2002.

E4]蔡旭晖,刘卫国,蔡立燕.MATLAB基础与应用教程[M].北京:人民邮电出版

社,2009.

StudyontheModelandAlgorithmsforanAssignmentProblem

WUShu—meng.ZHANGGeng

(SchoolofScience,ChinaUniversityofMiningandTechnology,Xuzhou221008,China) Abstract:Amulti—

objectiveintegerprogrammingmodelisproposedtodescribetheassignmentproblem oftrains"examining.Ageneticalgorithmispresentedtogetasatisfactorysolutionofthemode1.There—

suitsshowthattheimprovedcrossoveroperatorandmutationoperatorhasgreatlyincreasedtheeffective—

nessofthegeneticalgorithm.

Keywords:integerprogramming;assignmentproblem;geneticalgorithm (责任编辑燕善俊)

?

17?

范文五：具有优先级的指派问题数学模型及应用

A b stra c t In ac tua l a ssignm en t p rob lem , the que stion is often m e t wh ich som e du ty needed first to con sid2

e r. Th is a rtic le e stab lishe s the a ssignm en t p rob lem m a them a tica l mode l w ith the p rio rity. In th is m a them a tica l

mode l, the p rio rity h ighe r du ty ob ta ined first con side red. F ina lly, expound th is que stion’s so lu tion w ith an exam 2

p le。

Key word A ssignm en t p rob lem M a them a tica l mode l H unga rian so lu tion

1 引言 2 具有优先级的指派问题的数学模型

在日常生活和企业生产经营管理工作中 ,经常面临着给传统的指派问题不能很好解决任务的重要程度是不同 人“分派 ”工作任务的问题 ,由于每个人的专长不同 ,因此 ,每 ,针对这种情况 ,把任务进行分类 ,根据任务的重 的指派问题

()个人完成同一项工作任务的效率 或所需时间 、费用 也不相 要程度进行分级 ,可以称之为优先级 , 不同的任务具有不同 同 。因此 ,就产生了应如何指派哪个人去完成何任务 ,从而 的优先级 ,然后在保证优先级高的问题先解决的原则 ,再进 [ 1 ] 使完成任务的总效率最大或所需时间和费用最少的问题 , 行任务分配 ,从而得到更合理的任务指派方案 。

为了使问题简化 ,我们只考虑 n 人 n事的指派问题 , 需 这就是指派问题 , 1955年库恩提出了指派问题的解法 。 近年

要完成的任务仅分为两个优先级 ,多个优先级的情况 ,可类 来有人对传统的指派问题作了一些有意义的推广 , [ 5 ]似解决 。对于 如“一事多人 ”和“一人多事 ”的指派问题等等 。传统的指派 m 人 n事的指派问题 ,我们可以参照文献 的

(方法 ,使之转化为 n人 n事的指派问题 。现假设有 n项任务 问题是在给定条件下求总效率最高 如总费用最少 、总时间

)要指派 n个人去完成 ,每项任务需安排 1 人承担 ,每人仅能 最少等等 的指派方案 。但在一些特殊情况下 ,总效率最高

分派一项工作 ,其中有 m 项任务具有较高的优先级 ,需要优 的指派方案并不一定就是好方案 。比如 ,在一供电系统中有

先考虑 ,用 E表示优先级较高的任务的下标集合 。设编号为 数处发生故障急需停电检修 ,且供电系统只有在所有故障排

第 i个人完成第 j项任务的“成本 ”为 c, i, j = 1, 2, , n ,效 除以后才能恢复供电 ,应如何分配检修任务才能使供电系统 ij

) ( 益矩阵记为 C = c。 停电检修时间最短 ,而在此条件下又使总检修时间最少 ? 为 ij n n 了区别起见 ,在文献 [ 2 ]中把传统的指派问题称为 A 指派问 m in ? = ??c x ij ij i = 1 j = 1 题 ,而把上述问题称为 B 指派问题 。在实践中 ,我们还经常 n n s. t. m in F = m in?? cx 碰到另外一种类型的指派问题 ,即实际分配任务数不超过总 ij iji = 1 j| E 人数也不超过总任务数的指派问题 。显然 ,这是一类不同于 E是优先级较高的任务的下标集合 [ 3 ] n 其它问题的指派问题 , 我们 把 它 称 为 C 指 派 问 题 。文 献 s. t. i = 1, 2 , , n ?x= 1 ij i = 1 [ 1 ] [ 4 ]对一些特殊的指派问题进行了有意义的研究 ,取得 n 了较好的效果 。 j = 1 , 2, , n ?x= 1 ij j = 1 在教育教学管理中 ,人们也常常遇到“指派 ”问题 ,例如 xij = 0 或 1 i, j = 1, 2 , , n 学生上课教室的分配 、学生宿舍的分配 、任课教师的指派等 另外 ,决策者在分派任务时 ,一般先考虑较重要的任 务 等 ,这些问题都可以使用指派问题模型来解决 。由于种种原 安排问题 ,然后再考虑一般任务的安排 , E 是优先级较高 的 因 ,在实际生活中 ,对于类似的指派问题都会有一些特殊要 ()任务 即重要的任务 的下标集合 ,该模型比以前的其他模型 求 。在学生宿舍的分配中 ,某些学生因为身体原因 ,需要照 更接近实际生活 。

顾 ;在任课教师的指派中 ,有些课程需要较好的教师担任 ,必

3 具有优先级的指派问题的求解方法 须优先考虑 。显然 ,在传统的指派问题中 ,人与人之间 、任务

指派问题是一类特殊性的整数规划问题 ,又是特殊的 0 与任务之间都 是 平 等 对 待 的 , 对 于 这 些 特 殊 的 要 求 无 法 满

足 ,因此 ,急需一个新的模型来解决此问题 。 - 1规划问题和特殊的运输问题 [ 1 ] ,因此 ,指派问题可以使

过改进匈牙利解法得到问题的解 ,经过试验 ,认为此法可行 。3表 具体方法如下 :第一步 ,利用匈牙利解法求解优先级别较高 教室 3教室 4教室 5的任务的指派方案 ,此时 ,优先级别较高的任务的效率矩阵 85 70 50 2班不变 ,优先级别较低的任务的效率矩阵变为 0。第二步 ,利用 60 40 35 3班匈牙利解法求解优先级别较低的任务的指派方案 。 60 50 30 5班该方法对于所有人都能够做所有事的情况 ,肯定可以求

得最优解 ,但如果存在有些人不能够做某件事的情况 ,该方 使用匈牙利解法可以求得分配方案为 : 其中 2 班分在教 法就不一定能够求得最优解 ,可以考虑使用其他方法求解 。 室 5, 3班分在教室 4 , 5班分在教室 3。4 具有优先级的指派问题的应用举例 按照传统的指派问题 ,我们也可以得到一个分配方案 , 其中 1班分在教室 3, 2班分在教室 2 , 3班分在教室 1 , 4班分 例 1、某教学单位现有在校生 5个班级 ,有 5个教室可供 在教室 4 , 5班分在教室 5;该方案总费用 f = 35 + 45 + 30 + 30 分配 ,根据班级的学生人数 、教室的座位数及教室的设备情 + 30 = 170。教室 1、教室 2的费用合计为 45 + 30 = 75。按照 况 ,我们可以得到各班分得某教室的费用情况如表 1 ,其中教 优先考虑教室 1、教室 2的原则 ,我们也可以得到另外一个分 室 1、教室 2 设备较好 ,应优先考虑该教室的分配 ,问如何分

配方案 ,其中 1班分在教室 1, 2 班分在教室 5 , 3 班分在教室 配教室使其总花费最小 ?

4 , 4班分在教室 2, 5班分在教室 3;该方案总费用 f = 20 + 50表 1

+ 40 + 35 + 60 = 205。教室 1、教室 2的费用合计为 20 + 35 = 教室 1教室 2教室 3教室 4教室 555。其总费用增长了 20. 6% ,但教室 1、教室 2的费用却减少 20 40 35 75 60 1班了 26. 7% 。若考虑到教室 1、教室 2 的设备价值较高等其他 35 45 85 70 50 2班因素 ,这样分配充分体现了教室 1、教室 2的优先地位 。 30 45 60 40 35 3班 5 结束语 30 35 70 30 50 4班具有优先级的指派问题模型 ,较好的解决了具有特殊要 30 45 60 50 30 5班求的指派问题 ,该模型更接近现实生活 , 因此具有较强的应 第一步 : 确定优先级别较高的教室 1、教室 2 的分配方 用价值 ,但该模型还存在一些问题 ,还需要进一步完善 ,特别 案 。此时 ,其余教室不参与分配 ,因此 ,其费用为 0。见表 2 是具有优先级的指派问题的解法急需进一步优化 。表 2

参考文献 : 教室 1教室 2教室 3教室 4教室 5

20 40 0 0 0 1班[ 1 ] 黄龙生 ,徐光辉 . 有资格限制的指派问题的求解方法 .

35 45 0 0 0 2班 运筹与管理 , 2005, 1: 28,31

30 45 0 0 0 3班BA IGuo - zhong. B - a ssignm en t p rob lem s [ J ]. Jou rna l of [ 2 ]

( ) 30 35 0 0 0 System s Sc ience and System s Enginee ring, 1997 , 6 1 : 1 4班

30 45 0 0 0 - 4. 5班

[ 3 ] 白国仲 ,毛经中 . C 指派问题 . 系统工程 理论与实践 ,使用匈牙利解法求得分配方案为 :其中 1班分在教室 1 ,

2003, 3: 107,1114班分在教室 2,其他班没有分配 。

任德华 ,卢桂章 . 最短时限最少耗费指派问题的一种解 [ 4 ] 第二步 :求其余教室分配方案 。由于 1 班分得教室 1, 4

法 . 自动化与仪表 , 2005, 3: 1,4 班分得教室 2,原问题变为 2 班 、3 班 、5 班来分配教室 3、教

() [ 5 ] 室 4、教室 5的问题 。其效率矩阵如表 3: 胡运权 . 运筹学教程 第二版 . 清华大学出版社 , 2003()) 上接第 145页 版 . 北京 :电子工业出版社 , 2005.

[ 2 ] 潘爱民 . COM 原理与应用 [ M ]. 北京 : 清华大学出 版 5 结束语 社 , 1999.

[ 3 ] 程 展 鹏 . Bo rland C + + B u ilde r6 应 用 技 术 开 发 解 析 通过 COM 技术 ,可以在应用 系统中独立调用 MA TLAB

[M ]. 北京 :清华大学出版社 , 2003.编写的 算 法 程 序 。在 MA TLAB 中 开 发 的 COM 组 件 通 过

( ) [ 4 ] COM B u ilde r工具打包后 ,可以完全脱离 MA TLAB 环境 ,从而 刘志俭 . MA TLAB 外部程序接口 6. x[M ]. 北京 :科学

出版社 , 2002. 实现与 C + + B u ilde r的无缝 连接 , 充分 利用了 MA TLAB 资

( ) [作者简介 ] 石学文 1971 - ,男 ,曲阜师范大学电气 源 。本文所 设 计 的 自 适 应 模 糊 P ID 控 制 器 已 在 浙 江 天 煌

THJ - 2型过程控制实验平台上调试 成功 ,获得 了良好的控 信息与自动化学院讲师 ,硕士 ,主要研究方向 : 过程控制 、计

转载请注明出处范文大全网 » 指派问题例1的数学模型