70指派问题

例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件事，一人一件，一件一人。一人做一件事一件事由一人做n1in1jijijxczminn,...,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至少选修两门数学，即2xxxxx543213xxxxx98653至少选修三门经济学，即至少选修两门计算机2xxxx97642313xx,xx选修课程要求7674xx,xx2515xx,xx291938xx,xx,xx最后注意，xi取0-1变量。91iixzmin2xxxxx543213xxxxx986532xxxx97642313xx,xx7674xx,xx2515xx,xx291938xx,xx,xx9,,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回答问题：根据计算结果，可以安排各个航班的飞机调度。