《运筹学课程设计案例》由会员分享，可在线阅读，更多相关《运筹学课程设计案例（5页珍藏版）》请在金锄头文库上搜索。
1、01 规划模型中国东方航空公司需要分配他的机组成员，使其覆盖所有将要飞行的航班。 我们所研究的重点是，为驻扎在北京市的三组机组人员指定如下表第一列列出的 所有航班，另外 12 列显示的是 12 条可行的航线（每列数字代表该航线覆盖的航 班，及其顺序号）。在这些航线中，需要选择 3 条（一对机组人员负责一条航线）， 但是要保证覆盖所有的航班（允许在一个航班上有多个机组人员，多出的机组人 员被视为乘客，但是工会合同要求，多余的机组人员被视为正在工作，得到应有 的工资）。把一对机组人员分配给某条航线的成本由表中的最后一行给出（以万 元为单位）。目标是分配三队机组人员，使他们飞行所有的航班的总成本最小
2、。可行的航线航班1234567891011121、北京一 上海11112、北京一 广州11113、北京一 西安11114、上海 重庆223235、上海一 北京23556、重庆 广州3347、重庆 西安333348、广州一 北京24459广州 重庆22210、西安 一北京244511、西安上海22442成本/万 元234675789989用 0 1 变量建模有 12 条可行的航线，相应的，我们有 12 个是或否的决策： 应该指定一地机组人员飞行j航线吗？ （j=l, 2,，12） 因此，我们使用 12个0-1 变量分别代表这些决策：1I,如果给航线j指定一组机组人员；0否则。该模型最有趣的地方是
3、,每个约束条件实际上是保证一个航班被覆盖。例如 考虑表中的最后一个航班（西安到上海）。五条航线（也就是 6航线、9航线、 10航线、11航线和12航线）包括航班,因此,公司之上会选择其中一条航线飞x +x +x +x +x 三 1行。结果约束条件是 69101112对另外11个航班使用类似的约束完成BIP模型是Min=2X +3X +4X+6X +7X +5X +7X1234567+8X +9X +9X +8X +9X8 9 10 11 12s.t.x +x +x +x $11 4 7 10x +x +x +x $ 12 5 8 11x +x +x +x $ 13 6912x +x +x+x
4、+x $ 14 791012x +x +x +x $ 1161011x+x+x $ 1459x+x+x+x+x $ 17 8 10 11 12x +x +x +x $ 12459x+x+x $ 15 8 11x +x +x +x $ 13 7 8 12x+x+x+x+x $1（ 北京上海）（ 北京广州）（ 北京西安）（ 上海重庆）（上海北京）（重庆广州）（重庆西安）（广州北京）广州重庆）（西安北京）（西安上海）x+x+x+x+x+x+x+x+x+x+x+1 2 3 4 5 6 7 8 9 10 116 9 10 11 12x12=3（共三队机组成员）x且 j是0-1变量。j=1, 2,，12该 BIP 模型的一个最优解是X=13（选择飞行航线 3 ）X=14（选择飞行航线 4 ）X =111 （现则飞行航线 11）x x=1 x=1其余 j=0，总成本为180 000元（另一最优解为 1,5x12=1x0其他 j= ）。
