运筹学课程设计

一问题提出1二问题分析1三模型建立13.1模型一的建立33.2模型二的建立53.3模型三的建立6四结果分析8五模型评价85.1模型优点85.2模型缺点8六参考文献9旅游最短路一问题提出周先生退休后想到各地旅游。计划从沈阳走遍华北各大城市。请你为他按下 面要求制定出行方案：1. 按地理位置（经纬度）设计最短路旅行方案；2. 如果2010年5月1日周先生从沈阳市出发，每个城市停留3天，可选择航 空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；3. 设计最省时的旅行方案，建立数学模型，修订你的方案；二问题分析第一问要求按地理位置（经纬度）设计最短路旅行方案，求最短路径是一个 典型的旅行售货商（TSP）模型。TSP模型可解的是知道任意两个城市之间的距 离，通过查阅资料可以华北各个城市所在的经纬度，所以首先就需要通过经纬度 计算出任意两个城市之间的距离，得到一个距离矩阵，再建立（TSP）模型， 对模型进行求解。问题的目标函数为minz = 工工d.x. （i丰j）其中x = 0或1 , j jiji=1 j若x = 1表示周先生直接从i市到j市。建立整数目标规划，用Lindo软件求解，ij找出所有X二1，确定最短路的旅行方案。ij第二问要求最经济，所以应从票价方面进行考虑，通过查阅资料可得各城市 之间航空、铁路（快车卧铺或动车）的不同票价，由于要求最经济的旅行互联网 上订票方案，所以选取三种类型票价中最低的票价，构建票价矩阵。用票价矩阵 代替第一问中的距离矩阵，求解出一条最经济路径。第三问要求设定省时的方案就需要考虑时间因素，因为以上三种交通工具中 航空用时最短，选择飞机作为旅行交通工具。通过查阅资料得到各城市间航班的 时间矩阵，用时间矩阵代替第一问中的距离矩阵，求解一条最省时的路径。三模型建立在具体的实现上，我们采用了整数规划法，并辅以LINGO软件编程实现 在下述意义下，引入一些01变量：xij巡回路线是从i到j,且i丰j 其他情况其目标是使血 d x （i丰j）最小。（d表示i市到j市的距离）ij （/iji=1 j这里有两个明显的必须满足的条件：访问城市i后必须要有一个即将访问的确切城市；访问城市j前必须要有一 个刚刚访问过的确切城市。用下面的两组约束分别实现上面的两个条件。厂工 x = 1（i 丰 j, i = 1,2, n）ij i=1工 x = 1（i 主 j, j = 1,2,n）ij到此我们得到了一个模型，他是一个指派问题的整数规划模型。但以上两个 条件对于TSP来说并不充分，仅仅是必要条件。例如：16以上两个条件都满足，但它显然不是TSP的解，它存在两个子巡回。这里，我们将叙述一种在原模型上附加充分的约束条件以避免产生子巡回的 方法。把额外变量u （i = 1,2,n）附加到问题中。可把这些变量看作是连续的。i现在附件下面形式的约束条件：u -u + nx n -1, 2 i 丰 j n.i j ij为了证明该约束条件有预期的效果，必须证明：（1）任何含子巡回的路线都 不满足该约束条件；（2）全部巡回都满足该约束条件。首先证明（1）,用反证法。假设还存在子巡回，也就是说至少有两个子巡回。 那么至少存在一个子巡回中不含城市1把该子巡回记为i1,i2ik,i1，则必有：u 一 u + n n 一 1i1 i 2u 一 u + n n 一 1 i 2 i 3u 一 u + n n 一 1V iki1把这k各式子相加，有n n -1，矛盾。故假设不正确，结论1得证。下面证明（2）,采用构造法。对于任意的总巡回1， ii ， 1,可取 1n-1u为访问城市的顺序数，取值范围为1,2,n-1。因此，u - u n - 2,2 i丰j n.下面来证明总巡回满足该约束条件。 i j(I)总巡回上的边u 一 u + n = n 一 1 n 一 1i1 i 2u u + n = n 一 1 n 一 1V i 2i 2u 2 u + n = n 1 n 1 inin1(II)非总巡回上的边u 一 u n 一 2 n 一 1,r = 1,2,n 一 2,j g 2,3,n 一 i , i irjr r+1u 一 u + n = n 一 1 n 一 1,j g 2,3,n 一 i i1i 2r从而结论(2)得证。这样我们把TSP转化成了一个混合整数线性规划问题。我们就可以利用数学软件LINGO来求解该问题。min z =xij ji=1 jG 丰 j; j = 1,2,n)G 丰 j; i = 1,2,n)G 丰 j; i = 2,3,n; j = 2,3,n)工x = 1ijs.t.1 x = 1ijj=1/ u u + nx 0ji3.1模型一的建立虽然地球不是一个标准的球体，但南北与东西长度相差不大，可以假设地球 为一个球体，球体半径R = 6371229公里。根据球面定理用两点之间的纬度差计算出南北向的距离差为：出东西向的距离差为：x R -180(人)兀 q 一 a)x180b b 丿x x R x cosi/一 180iji j2 x 180最后用勾股定理求出两点之间距离为：d =、：九2 +卩 2j j j所有城市之间的距离矩阵沈阳1北京2天津3石家庄4太原5济南6呼和浩特7沈阳10517.8520.6864.8992.5825.3897.1北京2517.80113.8283.9408.9364.8400.1天津3520.6113.80259.8428.9272.7494.2石家庄4864.8283.9259.80165.4276.5387.5太原5992.5408.9428.9165.40424.5335.1济南6825.3364.8272.7276.5424.50662.5呼和浩特7897.1400.1494.2387.5335.1662.50知道两个城市之间的距离，周先生要自某一城市出发巡回旅游，使总行程 最短，可以看出就是在一个赋权完全图中，找一个最小权的Humilton回路问题。以点0表示周先生的出发城市，称为源点，点1,2,N,表示n个周先生需访 问的城市。X = 1表示周先生需要从点i到点j，因外周先生一定离开某一个城市 ij去另一个城市所以i丰j x = 0表示不需要从点i到点j ； u.表示旅游城市的顺 ，iji序数；d表示对应城市iT j的距离。建立目标函数以及约束条件为：min z = 工工d. xG 丰 j)ij ijG 丰 j; j = 1,2,n)G 丰 j； i = 1,2,n)G 丰 j； i = 2,3,n; j = 2,3,n)工X = 1ijs.t. 1X = 1iju - u =+ nx 0其中辅助条件u lj(i = 1,2,n)可以是连续变化的，虽然这些变量在最优解中 i是普通的整数值。该模型的第一个约束条件是保证每一个城市必须旅游到，第二个约束条件表 示旅行者必须离开每个城市。若模型只有这两个约束,则是一个标准的分配问题, 但其解会存在子回路，因此最后的约束是为了防止子回路出现的约束。以总路线最短为原则，利用整数规划模型求得各城市的旅行优先顺序。 LINDO软件求解结果如下：LAST INTEGER SOLUTION IS THE BEST FOUNDRE-INSTALLING BEST SOLUTION.OBJECTIVE FUNCTION VALUE1)2488.200VARIABLEVALUEREDUCED COSTX121.000000517.799988X271.000000400.100006X311.000000520.599976X461.000000276.500000X541.000000165.399994X631.000000272.700012X751.000000335.100006U35.0000000.000000U43.0000000.000000U52.0000000.000000U64.0000000.000000U71.0000000.000000运行结果只摘取x二1的结果，求得目标函数的最优解为2488.200公里，最短路径为：沈阳T北京T呼和浩特T太原T石家庄T济南T天津T沈阳周先生的最短路的旅游路线如图所示，行程为2488.200公里。显然这是 个循环圈，无论从哪个城市开始，顺序或逆序最总所走的路径总长度都是 2488.200 公里。3.2模型二的建立由于要求最经济，所以可以从票价方面进行考虑，通过查阅资料可以得到各 个城市之间航空、铁路（快车卧铺或动车）的不同票价，由于要求最经济，的旅 行互联网上订票方案，所以选取三种类型票价中最低的票价，构建票价矩阵。用 票价矩阵代替第一问中的距离矩阵作为回路的边权值。各城市之间票价数据如表（单位：元）沈阳北京天津石家庄太原济南呼和浩特沈阳0121.86119.43170.91210.95181.31241.12北京126.54020.8048.0288.0685.80111.46天津119.4320.80067.08112.6761.88135.21石家庄170.9148.0267.08039.0052.70161.21太原210.9588.06112.6739.00091.70110.94济南181.3185.8061.8852.7091.700209.05呼和浩特241.12111.46135.21161.21110.94209.050知道两个城市之间的票价，周先生要自某一城市出发巡回旅游，使总费用最 少，可以看出就是在一个赋权完全图中，找一个最小权的回路问题。以点0表示周先生的出发城市，称为源点，c表示对应城市iT j的票价。建 j立目标函数以及约束条件为：min z = xi=1 jG 丰 j； j = 1,2,n)G 丰 j； i = 1,2,n)G 丰 j； i = 2,3,n; j = 2,3,n)工x = 1(/S.t. x = i(/j=1/ 1u 一 u + nx 0ji以总费用最少为原则建立整数规划模型，用Lindo求解结果如下:LAST INTEGER SOLUTION IS THE BEST FOUNDRE-INSTALLING BEST SOLUTION.OBJECTIVE FUNCTION VALUE1)617.2700VARIABLEVALUEREDUCED COSTX121.000000121.860001X271.000000111.459999X311.000000119.430000X461.00000052.700001X541.00000039.000000X631.00000061.880001X751.000000110.940002U20.0000000.000000U35.0000000.000000U43.0000000.000000U52.0000000.000000U64.0000000.000000U71.0000000.000000根据Lindo求得结果，设计周先生旅行的最经济的路径为：沈阳T北京T呼 和浩特T太原T石家庄T济南T天津T沈阳。3.3模型三的建立现在再讨论最省时的订票方案。三种交通工具的速度分别为：民航飞机行驶一般为800公里/小时，动车速度在150公里/小时一200公里/小时，快速列车 在120公里/小时以内，特快在160公里/小时以内，可见飞机最快，其次动车， 最慢是快车。假设三种交通方式的速度是不变的，则单位里程三种交通方式所花 费的时间分别为航空最短，其次是动车，最长的为快车。所以以时间最省为原则 时，我们采用全程均用飞机为交通工具的方案。根据匀速运动物体速度与路程的关系（T=S/V）可以在已知两地直线距离的 基础上求得民航飞机在任意两城市之间的飞行时间。这样，我们就将最短路线的 模型在改变权数的基础上成功的转化到了求解时间最省的问题上来。沈阳北京天津石家庄太原济南呼和浩 特沈阳00.64720.65081.08101.24061.03161.1214北京0.647200.14220.35490.51110.45600.5001天津0.65080.142200.32480.53610.34090.6178石家庄1.08100.35490.324800.20680.34560.4844太原1.24060.51110.53610.206800.53060.4189济南1.03160.45600.34090.34560.530600.8281呼和浩 特1.12140.50010.61780.48440.41890.82810各城市之间航行时间数据表（单位：小时）s表示对应城市iT j的飞行时 ij以点0表示周先生的出发城市，称为源点, 间。建立目标函数以及约束条件为： min z = 工xij iji=1St工x = 1ij1 x = 1ijj=1/ u 一 u + nx 0ijiG 丰 j； j = 1,2,n)G 丰 j; i = 1,2,n)G 丰 j； i = 2,3,n; j = 2,3,n)以用时最短为原则建立整数规划模型，用Lindo求解结果如下:OBJECTIVE FUNCTION VALUEVARIABLEVALUEREDUCED COSTX131.0000000.650800X211.0000000.647200X361.0000000.340900X451.0000000.206800X571.0000000.418900X641.0000000.3456001)3.110300X721.0000000.500100U26.0000000.000000U30.0000000.000000U42.0000000.000000U53.0000000.000000U61.0000000.000000U74.0000000.000000根据Lindo求得结果为周先生设计最省时的旅行方式，周先生选择飞机为交 通工具，的旅行路线是：沈阳天津济南石家庄太原呼和浩特北 京沈阳。四结果分析本题为一个小规模的旅行商问题，可能存在的路径共有(n-1)!/条。利用城 市的经纬度确定城市的直接距离，写出城市间的距离矩阵，查询资料得到最低票 价矩阵和时间矩阵，构建整数规划模型并引入0 1变量，并引进变量u.表示城 市的旅游顺序，约束条件u u nx n 1避免产生子回路。采用分枝定界法 并使用Lind。软件求的最优解。可以从时间，路程，经济的某一个方面考虑，为 旅行者设计符合自己要求的旅行方案。五模型评价5.1模型优点：(1) 建立的旅行商模型实用性强，对问题求解有很好的针对性。(2) 利用lindo软件可以求解小规模的旅行商问题，可以有效避免陷入局优，克 服初值依赖性，描述简单，使用灵活，运用广泛，运行效率高。5.2模型缺点：(1利用lind(软件求解具有一定的局限性，无法求得大规模的问题；(2)可题三中最省时方案所得的结果与最优解有一定相差，原因在于模型片面过 于依赖城市间空间直线距离。六参考文献1 胡运权，运筹学基础及应用（第四版）：高等教育出版社，2003年11 月。2 王树禾图论，科学教育出版社，2004年1月第一版 姜启源，谢金星，叶俊，数学模型（第三版），北京：高等教育出版社，2003.84谢金星、薛毅优化模型与LINDO/LINGO软件，清华大学出版社2005年 7月第一版