数学规划及lingo软件的使用[1]

《数学规划及lingo软件的使用[1]》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学规划及LINGO软件的使用—飞行管理问题司守奎海军航空工程学院数学教研室，烟台，264001Email：sishoukui@163.com1．数学建模竞赛中的数学规划问题2000年B题，管道订购与运输问题；2001年B题，公交车调度；2002年B题，彩票中的数学；2003年B题，露天矿生产的车辆安排；2004年A题，奥运会临时超市网点设计；2003年B题，电力市场的输电堵塞管理；2005年B题，DVD在线租赁；2005年D题，DVD在线租赁；2006年A题，出版社的资源配置；2006年C题，易拉罐形状和尺寸的最优设计；2007年B题，乘公交看奥运；2007年C题，手机“套餐”优惠几

2、何；2007年D题，体能测试时间安排。建立数学规划时，尽量建立线性模型，或者可以线性化的模型。下面我们以2007年D题体能测试时间安排为例说明。某校按照教学计划安排各班学生进行体能测试，以了解学生的身体状况。测试包括身高与体重、立定跳远、肺活量、握力和台阶试验共5个项目，均由电子仪器自动测量、记录并保存信息。该校引进身高与体重测量仪器3台，立定跳远、肺活量测量仪器各1台，握力和台阶试验测量仪器各2台。身高与体重、立定跳远、肺活量、握力4个项目每台仪器每个学生的平均测试（包括学生的转换）时间分别为10秒、20秒、20秒、15秒，台阶试验每台仪器一次测试5个学生，需要3分30秒。每个学生测

3、试每个项目前要录入个人信息，即学号，平均需时5秒。仪器在每个学生测量完毕后学号将自动后移一位，于是如果前后测试的学生学号相连，就可以省去录入时间，而同一班学生的学号是相连的。学校安排每天的测试时间为8：00－12：10与13：30－16：45两个时间段。5项测试都在最多容纳150个学生的小型场所进行，测试项目没有固定的先后顺序。参加体能测试的各班人数见附表。学校要求同一班的所有学生在同一时间段内完成所有项目的测试，并且在整个测试所需时间段数最少的条件下，尽量节省学生的等待时间。请你用数学符号和语言表述各班测试时间安排问题，给出该数学问题的算法，尽量用清晰、直观的图表形式为学校工作人员及

4、各班学生表示出测试时间的安排计划，并且说明该计划怎样满足学校的上述要求和条件。最后，请对学校以后的体能测试就以下方面提出建议，并说明理由：如引进各项测量仪器的数量；测试场所的人员容量；一个班的学生是否需要分成几个组进行测试等。[1]空军雷达学院建立了“班级隔离”的模型。经简单分析，即可知所需时间段不会超过9个。建立的数学规划模型为1956min∑sign∑xijj=1i=156s.t.∑xijti≤Tj，j=1,2,L,9i=19∑xij=1，i=1,2,L,56j=1x=0或1，i=1,2,L,56；j=1,2,L,9ij为了求解上述非线性规划问题，把上面问题看成是装箱问题，用近似算

5、法求解。实际上我们可以建立线性0−1整数规划模型，引入0−1变量⎧0,第j个时间段没有班级参加测试yj=⎨⎩1,第j个时间段有班级参加测试建立的0−1整数规划模型如下9min∑yjj=156s.t.∑xijti≤Tj，j=1,2,L,9i=19∑xij=1，i=1,2,L,56j=156∑xij≤Myj，j=1,2,L,9i=1x=0或1，i=1,2,L,56；j=1,2,L,9ij这里M为一个充分大的正实数。2．图论中的数学规划问题[2]（1）最小生成树的0−1整数规划模型节点1表示树根，总共有n个节点。点i到点j的距离用c表示，当两个节点之间没有ij线路相通时，两点之间距离用M（充

6、分大的实数）表示。引入0−1整数变量⎧1,(i≠j)表示从i到j的边在树中，xij=⎨⎩0，表示该边不在树中.最小生成树问题的0−1整数规划模型如下2nnminz=∑∑cijxiji==11jn⎧⎪∑xij=1,j=2,L,n,i≠j⎪i=1n⎪⎪s.t.⎨∑x1j≥1,j=2⎪⎪u=0,1≤u≤n−1,i=2,3,L,n,1i⎪⎪⎩uj≥uk+xkj−(n−2)(1−xkj)+(n−3)xjk,k=1,L,n,j=2,L,n,j≠k.其中决策变量x是0−1型，约束变量u是整数型。ijj[3]（2）TSP（旅行商）问题的0−1整数规划模型引入0−1整数变量⎧0,表示不走i到j的路线xi

7、j=⎨⎩1，表示走从i到j的路线则TSP模型可表示为nnmin∑∑cijxiji==11jns.t.∑xij=1，i=1,2,L,nj=1n∑xij=1，j=1,2,L,ni=1u=1，2≤u≤n，i=2,3,L,n1iu−u+1≤(n−1)(1−x)，i=2,3,L,n；j=2,3,L,nijij[3]（3）没有公共仓库的K个商人的TSP问题K个商人合作走过n个城市，各个商人走过的Hamilton圈没有公共点。引入0−1整数变量⎧0,商人k不