《数学建模-运筹学2013》由会员分享，可在线阅读，更多相关《数学建模-运筹学2013（30页珍藏版）》请在金锄头文库上搜索。
1、运筹学实验报告最优化建模和计算最优化建模和计算1、Lindo 和 Lingo 基本程序 生产 100 套钢架，长 2.9、2.1、1.5 米各 1 根/套，原料长 7.4 米，如何下料？运筹学实验报告下料的所有方案12345678 2.921110000 2.102103210 1.510130234 料头0.10.30.901.10.20.81.4运筹学实验报告给出下料问题的计算程序： Lindo 程序： !min 0.1x1+0.3x2+0.9x3+0x4+1.1x5+0.2x6+0.8x7+1.4x8 min 1x1+1x2+1x3+1x4+1x5+1x6+1x7+1x8 subject
2、 to 2x1+1x2+1x3+1x4+0x5+0x6+0x7+0x8100 0x1+2x2+1x3+0x4+3x5+2x6+1x7+0x8100 1x1+0x2+1x3+3x4+0x5+2x6+3x7+4x8100 end gin x1 gin x2 gin x3 gin x4 gin x5 gin x6 gin x7 gin x8运筹学实验报告Lingo 程序： model: sets: E/1.8/:c,x; F/1.3/:b; link(F,E):a; endsets min=sum(E(j):c(j)*x(j); for(F(i):sum(E(j):a(i,j)*x(j)100);
3、for(E(j):x(j)0); for(E(j):gin(x); data: !c=0.1,0.3,0.9,0,1.1,0.2,0.8,1.4; c=1,1,1,1,1,1,1,1; a=2,1,1,1,0,0,0,0,0,2,1,0,3,2,1,0,1,0,1,3,0,2,3,4; enddata end运筹学实验报告2、建模和编程练习 1 五年期投资计划：五年内有 4 个投资项目，情况是： （1）1 至 4 年，每年年初投资，次年末回收本利 115%； （2）第 3 年初投资，第 5 年末回收本利 125%（最大投资额不超过 4 万元） ； （3）第 2 年初投资，第 5 年末回收本利
4、140%（最大投资额不超过 3 万元） ； （4）每年年初投资，年末回收本利 106%。 给你 10 万，给出投资计划。 请分析投资规律。 项目123455 年末 1x11x21x31x41 1.15x41 2 x32= 10;enddatasets:A/1.N/: c,x;endsetsmin=sum(A(i): c(i)*x(i);sum(A(i): x(i)=5;x(1)=x(7);x(1)+x(8)=1;x(3)+x(5) j，否则就不是。由此，我们就可方便的确定出最短路径;for(roads(i,j):P(i,j)=if(F(i) #eq# D(i,j)+F(j),1,0); end
5、运筹学实验报告7 旅行售货员问题（又称货郎担问题，Traveling Salesman Problem） 有一个推销员，从城市 1 出发，要遍访城市 2，3，n 各一次，最后返 回城市 1。已知从城市 i 到 j 的旅费为ijc，问他应按怎样的次序访问这些城市，使得总旅费最少？ 在下述意义下，引入一些 0-1 整数变量：ijx其它情况，且到巡回路线是从，0,1jiji其目标只是使 njiijijxc1,为最小。这里有两个明显的必须满足的条件： 访问城市 i 后必须要有一个即将访问的确切城市；访问城市 j 前必须要有 一个刚刚访问过的确切城市。用下面的两组约束分别实现上面的两个条件。nixnji
6、j, 2, 1, 11L njxniij, 2, 1, 11L 到此我们得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条 件对于 TSP 来说并不充分，仅仅是必要条件。例如：以上两个条件都满足，但它显然不是 TSP 的解，它存在两个子巡回。下面介绍 一种避免产生子巡回的方法。 把额外变量), 3, 2(niuiL附加到问题中。得到约束条件 njinxnuuijji2, 1。为了证明该约束条件有预期的效果，必须证明：（1）任何含子巡回的路线 都不满足该约束条件；（2）全部巡回都满足该约束条件。 首先证明（1） ，用反证法。假设还存在子巡回，也就是说至少有两个子巡 回。那么至少存在一个
7、子巡回中不含城市 1。把该子巡回记为121iiiikL，则必有111132121nnuunnuunnuuiiiiiikL把这 k 个式子相加，有 1 nn，矛盾！ 故假设不正确，结论（1）得证。 下面证明（2） ，采用构造法。对于任意的总巡回1111nii L，可取 iu访问城市 i 的顺序数，取值范围为2, 1, 0nL。 因此，njinuuji2, 2。下面来证明总巡回满足该约束条件。123456运筹学实验报告()总巡回上的边111111123221nnnuunnnuunnnuunniiiiiiL（）非总巡回上的边 , 3, 2, 12, 3, 2, 2, 2, 1, 1211rjirrj
8、i injnnuuiinjnrnnuunr LLL从而结论（2）得证。 这样我们把 TSP 转化成了一个混合整数线性规划问题。niunjixnjinxnuunixnjxtsxcziijijjinjijniijnjijiijij, 3, 2, 0, 2, 1, 1, 02, 1, 2, 1, 1, 2, 1, 1. .min111,LLLL运筹学实验报告!旅行售货员问题;model: sets:city / 1. 5/: u;link( city, city):dist, ! 距离矩阵;x; endsets n = size( city); data: !距离矩阵，它并不需要是对称的;dist
9、= qrand(1); !随机产生，这里可改为你要解决的问题的数据; enddata!目标函数;min = sum( link: dist * x);FOR( city( K):!进入城市 K;sum( city( I)| I #ne# K: x( I, K) = 1;!离开城市 K;sum( city( J)| J #ne# K: x( K, J) = 1;);!保证不出现子圈;for(city(I)|I #gt# 1:for( city( J)| J#gt#1 #and# I #ne# J:u(I)-u(J)+n*x(I,J)=n-1););!限制 u 的范围以加速模型的求解，保证所加限制
10、并不排除掉 TSP 问题的最优解;for(city(I) | I #gt# 1: u(I)=n-2 );!定义 X 为 01 变量;for( link: bin( x); end运筹学实验报告8 （最大流问题）请计算以下网络的最大流。v1v3v4 图 1 最大流问题的有向网络v5v6v72485124 579343v2运筹学实验报告C=(cij) 最大流问题数学模型 Max Z=flow 0fij cij f1j - fj1 = flow 中间点i： fij - fji =0运筹学实验报告!最大流问题;model:sets:node / 1. 7/: v;link( node, node)/1
11、,2 1,3 1,42,3 2,5 2,63,5 3,64,3 4,65,76,7/: c, f;endsets data:c=4 5 32 4 58 34 1279;enddata!目标函数;max = flow;!约束条件;for( node( i)| i#eq#1:sum( link(i, j): f( i, j)- sum( link(j, i): f( j, i)=flow;);for( node( i)| i#gt#1 #and# i #lt# 7:sum( link(i, j): f( i, j)- sum( link(j, i): f( j, i)=0;);for(link(
12、i, j): f(i,j)=c(i,j);end运筹学实验报告9 （最小费用流问题）请计算以下网络的流量为8的最小费用流(cij,wij)。v1v3v4图 1 最小费用流问题的有向网络v5v6v72,44,68,75,412,44,25,37,39,8 3,64,33,5v2运筹学实验报告C=(cij), W=(wij) 最大流问题数学模型 Min Z= wij*fij 0fij cij f1j - fj1 = 8 中间点i： fij - fji =0运筹学实验报告!最小费用流问题;model:sets:node / 1. 7/: v;link( node, node)/1,2 1,3 1,4
13、2,3 2,5 2,63,5 3,64,3 4,65,76,7/: c, w, f;endsets data:c=4 5 32 4 58 34 1279;w=3 4 64 2 37 56 438;input=?;enddata!目标函数;max = sum( link(i, j): w( i, j)*f( i, j);!约束条件;for( node( i)| i#eq#1:sum( link(i, j): f( i, j)- sum( link(j, i): f( j, i)=input;);for( node( i)| i#gt#1 #and# i #lt# 7:sum( link(i, j
14、): f( i, j)- sum( link(j, i): f( j, i)=0;);for(link( i, j): f(i,j)=c(i,j);end运筹学实验报告10 （配对模型）某公司将8个职员安排到4个办公室，每室2人。有些职员在一 起合作好，有些则不然。已知两两之间相容度，数字越小相容越好。问如何组 合？ 12345678 19342156 2173521 344292 41552 5876 623 74 8运筹学实验报告Min Z= cij*xij(ij) xjk = 1(j=ik=i)(i=1,2,3,4,5,6,7,8) xij =0 1 (ij)运筹学实验报告model:sets:ren / 1. 8/;links(ren, ren) | endsets data:c=9 3 4 2 1 5 61 7 3 5 2 14 4 2 9 21 5 5 28 7 62 34;enddata!目标函数;min = sum( links: c*x);for(links: bin(x);for(ren( i): sum( links(j, k) | j #eq# i #or# k #eq# i: x( j, k) =1);end
