1、整数规划 -指派问题小组成员： 李钢 ，黄可杰，许文静，叶珉铨，陈凯文，陈琦-2015-5-整数规划 -指派问题题目介绍分析思路分类讨论谢谢观赏目录1234某航空公司经营 A， B， C三个城市之间的航线，这些航线每天班机起飞与到达时间如表 1-1所示。设飞机在机场停留损失费用大致与停留时间的平方成正比，又每架飞机从降落到下班起飞至少需要 2小时准备时间，求出一个使停留费用损失为最小的飞行方案。航班号 起飞城市 起飞时间 到达城市 到达时间101 A 9:00 B 12:00102 A 10:00 B 13:00103 A 15:00 B 18:00104 A 20:00 C 24:00105
2、 A 22:00 C 2:00(次日 )106 B 4:00 A 7:00107 B 11:00 A 14:00108 B 15:00 A 18:00109 C 7:00 A 11:00110 C 15:00 A 19:00111 B 13:00 C 18:00112 B 18:00 C 23:00113 C 15:00 B 20:00114 C 7:00 B 12:00设飞机停留一小时的损失为 a元 ,则停留两小时的损失为 22a,即 4a元，则 3小时为 9a元， 4小时为 16a元，以此类推。可以建立以下反应飞机停留损失费用的表格。分类讨论：ABC在 A城市停留的时间损失在 B城市的损失
3、在 C城市的损失第一种情况：在 A城市停留的时间损失。可以看出， 101航班和 106航班中间停留 2小时，所以损失为 4a,以此类推，有如下表格 。101 102 103 104 105106 4a 9a 64a 169a 225a107 361a 400a 625a 36a 64a108 225a 256a 441a 4a 16a109 484a 529a 16a 81a 121a110 196a 225a 400a 625a 9a起飞到达解得最优解为：起 飞到达 101 102 103 104 105106 0 1 0 0 0107 0 0 0 1 0108 0 0 0 0 1109 0 0 1 0 0110 1 0 0 0 0分类讨论：ABC在 A城市停留的时间损失在 B城市的损失在 C城市的损失第二种情况：在 B城市的损失106 107 108 111 112101 256a 529a 9a 625a 36a102 225a 484a 4a 576a 25a103 100a 289a 441a 361a 576a113 64a 225a 361a 289a 484a114 256a 529a 9a 625a 36a起飞到达
