例3指派问题(运输问题的特殊形式)某商业公司计划开办5家新的商店。为了尽早建成营业,商业公司决定由5家建筑公司分别承包。已知建筑公司Ai(i=1,2,…,5)对商店Bj的造价(万元)为cij(i,j=1,2,…,n),见表。商业公司对5家建筑公司怎样分配任务,才能使得总的建造费用最少?B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106例1指派问题1、问题分析注意5家商店,5家建筑公司,一家建筑公司承建一家新的商店,一家商店只能由一家建筑公司承建。这称为一一对应指派,也称为标准指派问题。2、变量设置设0-1变量5,4,3,2,1j,iji0ji,1xij商店建筑公司不承包第,商店建筑公司承包第cij表示第i建筑公司承建第j商店的成本(造价),i,j=1,2,3,4,5B1B2B3B4B5A1X11X12X13X14X15A2X21X22X23X24X25A3X31X32X33X34x35A4X41X42X43X44X45A5X51X52X53X54x55建筑公司新商店行相加=1列相加=1建筑公司A1只能在五家新商店中选一家;商店B1只能选择一家建筑公司;55ijiji1j1cx,,,,..,,,,,,,,,,5iji15ijj1ijminzx1j12345stx1i12345x01ij12345这类标准的指派问题,可以用手工的匈牙利解法,可以查阅相关参考书。3、建立数学模型一家商店一家建筑公司一家建筑公司一家商店4、指派问题的扩展标准指派问题:n个人做n件事,一人一件,一件一人。一人做一件事一件事由一人做n1in1jijijxczminn,...,2,1j,i,1,0xn,...,2,1j,1xn,...,2,1i,1xijn1iijn1jij人多事少,有些事可以几个人合做rm1iijjj,rx第jr件事至少r个人完成;rn1jijii,1x第ir个人至少做1件事;在建立实际问题的指派问题时,要留心人数和事数的对应关系;有些问题表面看来不是指派问题,但是只要善于联系,很多问题可以直接用指派问题去解释。例2某学校规定,管理学专业的学生毕业时必须至少学习两门数学课、三门经济学课和两门计算机课。这些课程的编号、名称、学分、所属类别和先选修课要求如下表。毕业时,学生最少可以学习这些课程中的那些课程。编号名称学分所属类别先选课要求1经济数学5数学2数理统计4数学3微观经济学4数学、经济学1,24数据结构3数学、计算机75计量经济学4数学、经济学1,26电子商务3计算机、经济学77计算机程序设计2计算机8宏观经济学2经济学39经济模型建立3经济学、计算机1,2例2选课问题1、问题分析对每门课程而言,每个同学都有选修与不选修两种选择。凡是这类选择,都可以用0-1变量来描述。需要注意的是该问题是以课程少为目标,当然也可以用学分尽量多为目标。另外需要特别注意的是课程的先选要求如何描述。2、变量设置设xi表示第i门课程的决策结果:xi=1,表示选择该门课程;xi=0表示不选择该门课程,i=1,2,…,9;或者定义为3、建立数学模型ci,表示每门课程的相应学分,i=1,2,…,9。01xi选择第i门功课,不选择第i门功课目标函数:总课程数最少91iixmin也可以换成总学分最多,即91iiixcmax至少选修两门数学,即2xxxxx543213xxxxx98653至少选修三门经济学,即至少选修两门计算机2xxxx97642313xx,xx选修课程要求7674xx,xx2515xx,xx291938xx,xx,xx最后注意,xi取0-1变量。91iixzmin2xxxxx543213xxxxx986532xxxx97642313xx,xx7674xx,xx2515xx,xx291938xx,xx,xx9,,2,1i,1,0xi一般的优化软件都有专门求解0-1规划的功能。s.t.某航空公司经营A,B,C三个城市的航线,这些航线每天班次起飞与到达时间如下表所示。设飞机在机场停留的损失费大致与停留时间的平方成正比,又每架飞机从降落到下班起飞至少需2小时准备时间,试决定一个使停留费用损失为最小的分派飞行方案。航班号起飞城市起飞时间到达城市到达时间101A9:00B12:00102A10:00B13:00103A15:00B18:00104A20:00C24:00例3航班编排问题105A22:00C2:00(次日)106B4:00A7:00107B11:00A14:00108B15:00A18:00109C7:00A11:00110C15:00A19:00111B13:00C18:00112B18:00C23:00113C15:00B20:00114C7:00B12:00问题分析:根据所给资料,城市A每天有五个航班进出,城市B每天有5个航班进出,城市C每天有4个航班进出,根据已知数据,绘制成如图1的飞行网络图ABC图1各航班时刻网络图模型假设(1)飞机在某个城市,经过2小时准备时间后,任何时刻都可以起飞,且安全;(2)飞机到达一个城市后,准备后,可以飞往任何一个下一个城市;(3)同一架飞机不能够同时出现两个不同的航线上;(4)飞机的停留损失费用为停留时间的平方倍;(5)计算一天24小时内的损失总费用;(6)航班准时起飞,准时到达;(7)任何一班飞机到达目的的,可以作为下一班的任何飞行;变量设置:先将达到航班和离开航班的时间对应绘制表1和表2toformABCA\9~12(101)10~13(102)15~18(103)20~24(104)22~2(105)B4~7(106)11~14(107)15~18(108)\13~18(111)18~23(112)C7~11(109)15~19(110)7~12(113)15~20(114)\表1ABC1067111091410718108191101019102101031510420105221011211312102131031811420106410711111131081511218104011521111811223114151101511371097到达离开表2x(i,j)城市A第i航班飞机用于第j航班,x(i,j)=1,否则,x(i,j)=0;y(i,j)城市B第i航班飞机用于第j航班,y(i,j)=1,否则,y(i,j)=0;z(i,j)城市C第i航班飞机用于第j航班,z(i,j)=1,否则,z(i,j)=0t1(i,j),t2(i,j),t3(i,j)城市A,B,C的第i航班飞机用于第j航班的停留时间;t1(i,j)1234562381315722232591181920256891516212410141520253对于城市A各种可能的调度等待时间时间如下表3表3城市B的各种调度等待时间如表4t2(i,j)678111211623272562152226245310172119241316232725614815191722表4城市C的各种调度等待时间如表5t3(i,j)910131447715155771515111313212112881616表5建立模型由于各个航班按时到达和出发,故不用考虑航线之间飞几条用的冲突问题,故只需要考虑每个城市的飞机的调度问题。且最优调度方案与飞用去时间的比例系数无关。所以模型为])j,i(t)j,i(z)j,i(t)j,i(y)j,i(t)j,i(x[minj,i23j,i22j,i21城市A的飞机调度约束10,9,8,7,6i1x5,4,3,2,1j1x51jij106iij城市B的飞机约束14,13,3,2,1i1y12,11,8,7,6j1y12,11,8,7,6jij14,13,3,2,1iij城市C的飞机约束12,11,5,4i1z14,13,10,9j1z14,13,10,9jij12,11,5,4iij变量约束1,0y,z,xijijij模型求解利用lingo求解sets:afrom/6,7,8,9,10/:;ato/1..5/:;linka(afrom,ato):x,t1;bfrom/1,2,3,13,14/:;bto/6,7,8,11,12/:;linkb(bfrom,bto):y,t2;cfrom/4,5,11,12/:;cto/9,10,13,14/:;linkc(cfrom,cto):z,t3;endsetsmin=@sum(linka:t1^2*x)+@sum(linkb:t2^2*y)+@sum(linkc:t3^2*z);@for(afrom(i):@sum(linka(i,j):x(i,j))=1);@for(ato(j):@sum(linka(i,j):x(i,j))=1);@for(bfrom(i):@sum(linkb(i,j):y(i,j))=1);@for(bto(j):@sum(linkb(i,j):y(i,j))=1);@for(cfrom(i):@sum(linkc(i,j):z(i,j))=1);@for(cto(j):@sum(linkc(i,j):z(i,j))=1);@for(linka:@bin(x));@for(linkb:@bin(y));@for(linkc:@bin(z));data:t1=2,3,8,13,1522,23,25,9,1119,20,25,6,815,16,21,2,414,15,20,25,3;t2=16,23,27,25,615,22,26,24,510,17,21,19,2416,23,27,25,68,15,19,17,22;t3=7,7,15,157,7,15,1513,13,21,218,8,16,16;enddata计算结果Globaloptimalsolutionfoundatiteration:0Objectivevalue:2447.000A城市航班调度:x(6,3)=x(7,4)=x(8,5)=x(9,1)=x(10,2)=1;B城市航班调度:y(1,12)=y(2,7)=y(3,11)=y(13,6)=y(14,8)=1;C城市航班调度:z(4,13)=z(5,14)=z(11,10)=z(12,9)=1回答问题:根据计算结果,可以安排各个航班的飞机调度。