建模工件安装问题.doc

作业三：工件的安装与排序问题（钟建忠，汪灵枝，刘琳岚）摘要：本文以实际工件的安装为背景，讨论了工件的排序问题。通过认真分析工件安装时的工艺要求，针对相邻扇区重量和的差不大于一定值的限制条件，考虑各扇区重量和的值波动范围较小和较大的两种情况，分别建立了模型。模型I主要是根据对工件的重量的要求为约束条件，以及借助0-1变量Xij（序列号为i的工件放入J区间），建立了规划模型I 。约束条件为相邻区间的重量和不超过一个定值m.借助软件进行求解满足条件的解。问题二是按重量和体积进行工件排序。建立模型二；定义0-1变量Z（I,k）（表示序列号为i的工件放入第K个位置）。约束条件为（）相邻区间的重量和不超过一个定值m ；（）相邻的工件体积之差不小于一定值p。借助软件进行求解。问题三。当无法通过内部调试来满足要求时，我们详细讨论了更换新工件的各种情况，并提出了具体的解决方案，给出了更换新工件重量和体积的范围。如： 当被更换工件的重量为时，新工件的重量的范围： 当被更换工件的体积为时，新工件的体积的范围： 建立的模型能有效的解决工件的安装和排序问题。对实际运用具有指导意义。3.1问题的重述3.1.1 问题的由来由于工件的重量和体积不同，安装时需要按工艺要求重新排序。3.1.2 问题的要求1）设备的24个工件均匀分布在等分成六个扇形区域的一圆盘的边缘上，放在每个扇形区域的4个工件总重量与相邻区域的4个工件总重量之差不允许超过一定值（如4g）。 2）.工件的排序不仅要对重量差有一定的要求，还要满足体积的 当工件确实不满足上述要求时，允许更换少量工件。要求，即两相邻工件的体积差应尽量大，使得相邻工件体积差不小于一定值（如3 ）；3）当工件确实不满足上述要求时，允许更换少量工件3.1.3问题的提出请按上述要求给出：问题时，1按重量排序算法； 问题2按重量和体积排序算法； 问题3当工件不满足要求指出所更换工件及新工件的重量和体积值范围，并输出排序结果。 请按下面两组工件数据（重量单位：g ，体积单位： ），进行实时计算： 序号重量体积序号重量体积1348101.51358.510323521022357.5103334710533551034349105.54351103.55347.51065355.510363471046357102733094734196832998834296.59329100.5934095.510327.598.51034497113299811342.595.112331.59912343.596.513348.5104.513357.5102.5143471051435510315346.5107.515353.5103.516348104.516356.5103.517347.510417356103.518348104.518352.5104193339719342.59820330972034496.521332.59921339.59822331.59822341.59623331.596.523341962433294.524345973.2基本假设模型一的假设；1）24片叶片均匀分布在圆盘上。2）不考虑每个象限内的排序。3）不考虑叶片的体积等其他因素。模型二的假设；（1）24片叶片均匀分布在圆盘上。（2）叶片排序不仅要保证重量差，两相邻叶片的体积差因尽量大，使相邻的叶片体积差不小于一定值。（3）只要满足重量差。体积差即可。不考虑其他约束条件，无需考虑最优的排序方案。3.3符号的约定1) xij-表第i件工件是否在第j扇区上，在为1，不在为0；2）Mj表示第j扇区的总重量。mi表示序列号为i的重量。3) 表示相邻扇区的总重量之差不超过的定值4）表示相邻工件的体积之差不小于的定值5）Z(i，k)表示将序列号为i的工件放入第k个位置。6)Mj表示第J区间的总重量。Mi表示序列号为i的重量。7)Vi表示序列号为i的体积3.4问题的分析3.4.1 问题的分析问题一：针对问题一按工件的重量排序的算法。题目要求每个相邻的象限的总重量差值不能超过某个数值（m）但主要问题是对工件的安排如何将这些工件分配到各个象限，此时我们引入0-1变量来确定第几个工件是否放到第几象限，最后通过一些约束条件来建立规划模型即可进行求解。问题二：在考虑重量排序的情况下，我们还必须使得相邻的两个工件的体积相差不小于一个定值。定义0-1规划；Z(i，k)表示将i序列号的工件放入k位置，第一对重量条件进行约束|Mj-Mj+1|=得出满足约束条件的排序解。列出一组满足排序的排序法进行验证。问题三：考虑三种情况下的更换条件；1只考虑重量时，不满足条件；2同时考虑重量和体积时；（1）重量不满足；（2）体积不满足；3重量和体积都不满足要求时；用相邻工件的体积之差不小于一定值，相邻区间重量和不大于一定值进行约束。得出更换工件的范围。3.5模型的建立与求解（1）模型I 规划模型 本模型通过对已知条件各个象限的总重量的要求的分析给出了对重量的约束条件，并且引进了0-1变量，进而建立了模型I。(2)模型II 规划模型 本模型通过对已知条件各个象限的总重量的要求的分析给出了对重量的约束条件和相邻工件体积差的约束条件。引入0-1变量。3.5.1问题一的分析与求解1 对每个象限的总质量的差的取值的分析由已知条件要求相邻的每个象限的总重量不得超过一个定值m可得出一个约束条件：（1） 每个相邻象限工件总重量的约束条件： Mj-Mj+1 (j=1,2,3,4,5) M6-M1 2对每个工件被放到第几象限的分析（1） 首先要引进一个0-1变量 （j=1,2,3,4,5,6）扇区工件重量 123456m1=1m2=1mi=1m24=1=4=4=4=4=4=4(2)由于每个工件都要放到其中一个象限中去，为了确保满足上述条件则有以下式子成立 =1(3)由已知条件有总共有6个象限每个象限要有4个工件。为确保满足上述条件则有以下式子成立 =4 （j=1,2,3,4,5,6）3 模型I一 模型的建立按重量排序算法可以建立模型I条件：（1）每个相邻象限的工件的总重量的差的约束条件： Mj-Mj+1 (j=1,2,3,4,5) M6-M1 (2)0-1变量的条件： =1 = 1（j=1,2,3,4,5,6）二 模型的求解。 使用Lingo软件，对模型I进行求解（具体程序见附录）三模型的结果分析；令=4得到其中之一排序如下表所示一二三四五六第一组工件；序号重量序号重量序号重量序号重量序号重量序号重量334743495347.56 347134823521132912331.57330/8329932910327.51634817347.51834813348.51434715346.5193332033021332.522331.523331.524332每象限的重量之和相差2.5第二组工件；令=4得到其中之一排序如下表所示一二三四五六第一组工件；序号重量序号重量序号重量序号重量序号重量序号重量22341.52357.51358.518 352.5335519342.51735663574341/834293401034416356.5734111342.513357.55355.515353.52334121339.512343.520339.52434514355相邻象限的重量和之差为0.53.5.2问题二的分析与求解1对相邻工件体积的差值的分析2对相邻扇区重量的差值的分析3模型II一 模型的建立按重量和体积的排法可建立模型II定义0-1变量；Z(i，k)= 0 1 将序列号为i的工件放入第k个位置。条件：=1 Z(i,k)=1(j=1.24)体积差约束条件；当k为1-23是；|Z(i,k)*V(i)- Z(i,k+1)*V(i)|= (i=124)当k为24是；|Z(i,24)*V(i)- Z(i,1)*V(i)|= 重量差约束条件；|-|=(n=15)|-|=二 模型的求解 用lingo软件进行求解三 模型II结论第一组排序；一二三四五六第一组工件；序号体积序号体积序号体积序号体积序号体积序号体积210214105610412 991101.55106199721992494.5310522982396.515107.54105.513104.58981710418104.51098.511989100.516104.52097794重量和13591357.51356.51355.513571357第二组排序；（最小体积差为4.5.扇区重量差为2）一二三四五六第二组工件；序号体积序号体积序号体积序号体积序号体积序号体积1103210331034 103.55103.56102896.5995.510971195.11296.57961410315103.516103.517103.51810413102.52096.5219822962396249719983.5.3对问题三的分析与求解1只考虑重量时，不满足条件；2同时考虑重量和体积时；（1）重量不满足；（2）体积不满足；3重量和体积都不满足要求时；一 模型的建立(一)只考虑重量时，不满足条件：设第扇区和第扇区之间的重量和不满足条件（与扇区相邻, 与扇区相邻，其重量分别为,），只需更换其中一个扇区中某一工件。不妨设更换第 个扇区中的一个工件，记该工件的重量为, 这样，更换后第扇区的重量和为，则需满足： | | 解得： + + 即： 令 = 则 的范围： 设新工件的重量为=+，所以新工件的重量范围为： （二）同时考虑重量和体积时 当体积满足要求，重量不满足要求时，在更换时，我们只需按上述(一)的方法只更换工件的重量而保持其体积不变。 当重量满足要求，体积不满足要求时，我们可以按照上述(一)的思想方法进行更换，具体更换方法如下： 我们假设第个工件和第个工件之间的体积不满足条件（与工件相邻, 与 工件相邻，其体积分别为,），只需更换，中某一工件。不妨更换第 个工件。 这样，更换后第个工件的体积为 ,则需满足： | | 解得： + 或 + 或 即： 或 （三）当重量和体积都不满足要求时，我们可以分步更换： 先不考虑体积，只考虑重量，则可以按上述(一)的方法将其重量更换为满足重量要求的情形。然后再按照(二)的方法将其体积更换为满足体积要求的情形。 若先不考虑重量，只考虑体积， (二)- 的方法将其体积更换为满足体积要求的情形。然后再按照(二)- 的方法将其重量更换为满足重量要求的情形。 三 对模型结论的分析当工件不满足要求指出所更换工件及新工件的重量和体积值范围时有如下结果； 当被更换工件的重量为时，新工件的重量的范围： 当被更换工件的体积为时，新工件的体积的范围： 六模型的评价与推广1模型的优点：（1）推广容易。模型一和二运用数学软件找出可行方案比人工推算简便，有较强的推广价值。（2） 实用性强。便于准确的按要求安装。（3） 条理清晰。2模型的缺点：（1）模型一只考虑重量约束。模型二只考虑叶片重量和体积对叶片进行排序。与实际使用的排序有一定的差别。七参考文献1.数学建模案例分析 中国水利水电出版社2.数学建模教程 江苏教育出版社3.运筹学 高等教育出版社4.数学模型 高等教育出版社八附录第一问：第一组数据：model:sets:yuanjian/1.24/:X;qu/1.6/:V;links(qu,yuanjian):Y;endsetsfor(qu(i):sum(yuanjian(j):Y(i,j)=4);for(yuanjian(j):sum(qu(i):Y(i,j)=1);for(qu(i):V(i)=sum(yuanjian(j):X(j)*Y(i,j);for(qu(i)|i #lt# 6:(V(i)-V(i+1)=-m);V(1)-V(6)=-m;sum(links:Y)=24;for(links:bin(Y);data:m=0.5;X=ole(F:Book1.xls,weigh1);enddataend第二问： model:sets:yuanjian/1.24/:V;xuhou/1.24/:;paixu(yuanjian,xuhou):Y;endsetsfor(yuanjian(i):sum(xuhou(j):Y(i,j)=1);for(xuhou(j):sum(yuanjian(i):Y(i,j)=1);abs(sum(paixu(i,j)|j #lt# 24 :Y(i,j)*V(i)-sum(paixu(i,j)|j #lt# 23 :Y(i,j+1)*V(i)=P;abs(sum(yuanjian(i):Y(i,24)*V(i)-sum(yuanjian(i):Y(i,1)*V(i)=P;for(paixu(i,j):bin(Y(i,j);data:P=3;V=101.5 102 105 105.5 106 104 94 98 100.5 98.5 98 99 104.5 105 107.5 104.5 104 104.5 97 97 99 98 96.5 94.5;enddataend第一组数据运行结果： P=3， Y( 1, 6) 1.000000 Y( 2, 24) 1.000000 Y( 3, 8) 1.000000 Y( 4, 12) 1.000000 Y( 5, 15) 1.000000 Y( 6, 13) 1.000000 Y( 7, 1) 1.000000 Y( 8, 17) 1.000000 Y( 9, 9) 1.000000 Y( 10, 20) 1.000000 Y( 11, 16) 1.000000 Y( 12, 5) 1.000000 Y( 13, 11) 1.000000 Y( 14, 10) 1.000000 Y( 15, 21) 1.000000 Y( 16, 23) 1.000000 Y( 17, 18) 1.000000 Y( 18, 22) 1.000000 Y( 19, 19) 1.000000 Y( 20, 14) 1.000000 Y( 21, 7) 1.000000 Y( 22, 3) 1.000000 Y( 23, 4) 1.000000 Y( 24, 2) 1.000000model:sets:yuanjian/1.24/:V;xuhou/1.24/:;paixu(yuanjian,xuhou):Y;endsetsfor(yuanjian(i):sum(xuhou(j):Y(i,j)=1);for(xuhou(j):sum(yuanjian(i):Y(i,j)=1);abs(sum(paixu(i,j)|j #lt# 24 :Y(i,j)*V(i)-sum(paixu(i,j)|j #lt# 23 :Y(i,j+1)*V(i)=P;abs(sum(y