离散最优化模型

离散最优化模型李治[e-mail]华中农业大学理学院华中农业大学李治离散问题是整数规划、组合数学图论、网络流等许多学科讨论和研究的对象，这类问题在生产调度、交通控制、物流、管理科学和社会科学等有着广泛的用途。在我们历年的数模的竞赛中，离散问题是很重要的一个方面。如“锁具装箱”，“灾情巡视路线”等等，本身就是个典型的离散问题；也有的问题里包含着离散的子问题，如“车辆安排问题”，是个受到整数的约束的优化问题。近几年的“乘公交，看奥运”，“体能测试时间安排”，“地面搜索”,“NBA赛程的分析与评价”,“眼科病床的合理安排”,“会议筹备”等等都属于离散型问题。华中农业大学李治因此，在准备数模竞赛的过程中，有必要认真的研究如何提高建立离散模型的质量。下面就离散优化问题，介绍一下常见模型、算法及如何进行算法分析等。华中农业大学李治建立规划模型的要点与技巧一、准确理解题意二、选择适当的决策变量要点：通过仔细读题，弄清楚我们最终要解决的问题是什么?是单目标问题还是多目标问题？已知条件有哪些？为了简化与解决问题，需要做哪些必要的基本假设？需要优化的目标是由哪些因素决定的？适当引入决策变量来表示这些因素。华中农业大学李治三、设法用决策变量表示目标函数四、仔细分析约束条件通常引入的决策变量有0-1变量，整数变量等。在用决策变量表示目标函数时，有时需要引入中间变量，有时要利用取整函数、符号函数、绝对值函数等等。决策变量满足的约束主要有两方面：一是自身应有的约束，如非负约束、取整约束等等；二是题目要求及客观实际的约束，这种约束又可分为“硬约束”与“软约束”。华中农业大学李治一、多目标问题的妥协二、非线性规划的线性化三、复杂规划问题的拆分值得注意的技巧：有时可将复杂的问题分成一系列较为简单的子问题求解线性加权法；理想点法，极大极小法等有时通过引入人工变量可将非线性规划问题线性化华中农业大学李治一常见离散优化模型涉及整数规划、0-1规划、组合优化和图论等：如竞赛中常涉及的有下料问题；指派问题、选址问题、装箱问题、背包问题、最短路问题、TSP（旅行商）问题等。离散优化研究那些含有有限个可行解的、日常生活中大量存在的问题，一个重要而普遍的应用领域就是考虑如何有效利用稀缺资源来提高生产力等。套钢架,用长为2.9m、2.1m和1.5m的元钢各一根,已知原料长7.4m,问如何下料,使用的原材料最省?分析:下料方式：最省：1.所用刚架根数最少；2.余料最少下料问题离散优化模型华中农业大学李治原料截成所需长度的根数下料方法ⅠⅡⅢⅣⅤⅥⅦⅧ所需根长2.9m211100002.1m021032101.5m10130234剩余料头0.10.30.901.10.20.81.4:,为则问题的线性规划模型根数种办法下料的原材料的表示按第设ixi离散优化模型取整jjxjxxxxxxxxxxxxxxxxts;8,7,6,5,4,3,2,1,0100432310023321002..876431765324321离散优化模型写出模型后可以直接用LINGO求解钢管下料;Min=0.1*x1+0.3*x2+0.9*x3+0*x4+1.1*x5+0.2*x6+0.8*x7+1.4*x8;2*x1+x2+x3+x4100;2*x2+3*x3+3*x5+2*x6+x7100;x1+x3+3*x4+2*x6+3*x7+4*x8100;@gin(x1);@gin(x2);@gin(x3);@gin(x4);@gin(x5);@gin(x6);@gin(x7);end…Bn,分派给n人A1,A2,…An去做,每人只做一件工作且每件工作只派一个人去做,设Ai完成Bj的工时为cij,问应如何分派才能完成全部工作的总工时最少.否则去做分派给工作设解01:ijijABxninjijijxcf11min）（或）（）（njixnixnjxtsijnjijniij,...,2,1,10,...,2,11,...,2,11..11每件工作只派1人每个人只做1件工作指派问题离散优化模型华中农业大学李治如求6个人做6项工作的最优指派，收益情况如下表。指派问题人工作1工作2工作3工作4工作5工作61201516547217153312863912181630134128112719145—7102110326———61113指派问题;sets:flight/1..6/;assign(flight,flight):c,x;endsetsdata:c=20151654717153312869121816301312811271914-99710211032-99-99-9961113;enddata人工作1工作2工作3工作4工作5工作61201516547217153312863912181630134128112719145—7102110326———61113max=@sum(assign:c*x);@for(flight(i):@sum(flight(j):x(i,j))=1;@sum(flight(j):x(j,i))=1);@for(assign:@bin(x));end华中农业大学李治?,,,,,1,2:),(),(),(),(),(),(),(:7,,,37654321的年利润最大问如何选择地址使公司元总投资不超过元每年可获利元投资若选个汉口汉阳至少个武昌至多并规定汉商二十一世纪行街步武广司门口亚贸中商个地址有拟议中汉阳建立专卖店汉口某公司拟定在在武昌例bcbAAAAAAAAiii否则选择解,0,1:iiAx71maxiiixcf7,...,2,110112..765432171ixxxxxxxxbxbtsiiii或选址问题离散优化模型华中农业大学李治装箱问题(binpackingproblem)装箱问题在工业生产及日常生活中有广泛的用途，其应用在实际生活中无处不在，货物装运，服装裁剪，以及我们计算机科学中的存储分配、共享资源调度、文件存储都是装箱问题在实际应用中的体现。所以具有重要的研究价值。当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲，装箱问题是一个很难的组合优化问题，即使用计算机也是不容易解决的。离散优化模型、…、n的n种物品，体积分别为v1、v2、…、vn。将这n种物品装到容量都为V的若干箱子里(更一般的装箱问题还可以要求容量不是相同的)。约定这n种物品的体积均不超过V，即对于1≤i≤n，有0＜vi≤V。不同的装箱方案所需要的箱子数目可能不同。成功装载是指能把所有物品都装入箱子。最优装载是指使用最少箱子的成功装载。装箱问题的描述华中农业大学李治装箱问题的数学表示如下(0-1规划模型)：niiyyz1)(minnjiijjVyx1s.t.},,1{nNiNjxniij11NjxNiyiji1010或或yi=1表示箱子i装入物品，反之表示箱子i空着xij=1表示物品j装入箱子i，反之表示物品j未放入箱子i个物品,其中6个长0.51m，6个长0.27m，6个长0.26m，余下12个长0.23m，箱子长为1m，问最少需多少个箱子才能把30个物品全部装进箱子。装箱问题的LINGO软件求解离散优化模型:WP/w1..w30/:W;XZ/v1..v30/:Y;LINKS(WP,XZ):X;ENDSETSDATA:W=0.51,0.51,0.51,0.51,0.51,0.51,0.27,0.27,0.27,0.27,0.27,0.27,0.26,0.26,0.26,0.26,0.26,0.26,0.23,0.23,0.23,0.23,0.23,0.23,0.23,0.23,0.23,0.23,0.23,0.23;ENDDATAMIN=@SUM(XZ(I):Y(I));C=1;!C是箱子长度;@for(XZ:@bin(y));!限制Y是0-1变量;@for(LINKS:@bin(X));!限制X是0-1变量;@for(WP(I):@sum(XZ(J):X(I,J))=1);!每个物品只能放入一个箱子;@for(XZ(J):@SUM(WP(I):W(I)*X(I,J))=C*Y(J));!每个箱子内物品的总长度不超过箱子;end离散优化模型华中农业大学李治装箱问题的分类一维装箱问题更多的是带约束的装箱问题，如二维装箱问题（条形装箱问题、剪裁问题）、三维装箱问题、变容装箱问题、有色装箱问题、对偶装箱问题等。在竞赛中应注意区分和鉴别离散优化模型的背包。第j件物品的价值是，体积是。求将哪些物品装入背包可在满足背包容量允许的前提下使价值总和最大。背包问题在经济管理、资源分配、投资决策、装载设计等领域有着重要的应用价值。一维0/1背包问题jx0jx设为二进制变量，如果物品j被放入背包，则，否则。背包问题的数学模型描述如下：njjjxc1maxnjxWxwtsjnjjj,,2,1},1,0{..1离散优化模型：“超市大赢家”提供了50种商品作为奖品供中奖顾客选择,车的容量为1000dm3,奖品i占用的空间为widm3,价值为vi元,具体的数据如下:vi={220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1}wi={80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1}。离散优化模型:goods/w1..w50/:w,c,x;endsetsdata:c=220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1;w=80,82,85,70,72,70,66,50,55,25,50,5