装配线平衡模型.docx

《装配线平衡模型.docx》由会员分享，可在线阅读，更多相关《装配线平衡模型.docx（15页珍藏版）》请在第一文库网上搜索。

1、7综合举例例7.1求解非线性方程组其11NGO代码如下：mode1:x2+y2=2;2*x2+x+y2+y=4;end计算的部分结果为Feasib1eso1utionfoundatiteration:0Variab1eVa1ueX0.4543360Y1.339247例72装配线平衡模型一条装配线含有一系列的工作站，在最终产品的加工过程中每个工作站执行种或几种特定的任务。装配线周期是指所有工作站完成分配给它们各自的任务所化费时间中的最大值。平衡装配线的目标是为每个工作站分配加工任务，尽可能使每个工作站执行相同数量的任务，其最终标准是装配线周期最短。不适当的平衡装配线将会产生瓶颈一一有较少任务的工

2、作站将被迫等待其前面分配了较多任务的工作站。问题会因为众多任务间存在优先关系而变得更复杂，任务的分配必须服从这种优先关系。这个模型的目标是最小化装配线周期。有2类约束：要保证每件任务只能也必须分配至一个工作站来加工；要保证满足任务间的所有优先关系。例有11件任务(A-K)分配到4个工作站(1-4),任务的优先次序如下图。每件任!任务之间的优先关系集合(必须完成才能开始B,等等)；PRED(TASK,TASK)/A,BB,CC,FC,GF,JG,JJ,KD,EE,HE,IH,JI,J/;!工作站集合；STATION/1.4/;TXS(TASK,STATION):X;!X是派生集合TXS的一个属性

3、。如果X(I,K)=1,则表示第I个任务指派给第K个工作站完成；ENDSETSDATA:!任务ABcdefghijK的完成时间估计如下；T=4511950151212121289;ENDDATA!当任务超过15个时，模型的求解将变得很慢；!每一个作业必须指派到一个工作站，即满足约束；FOR(TSK(I):SUM(STATION(K):X(I,K)=1);!对于每一个存在优先关系的作业对来说，前者对应的工作站I必须小于后者对应的工作站J,即满足约束；FOR(PRED(I,J):SUM(STATION(K):K*X(J,K)-K*X(I,K)=0);!对于每一个工作站来说，其花费时间必须不大于装配

4、线周期;FoR(STATION(K):SUI(TXS(I,K):T(I)*X(I,K) )/ J f 7 / 7 34123412341234121.0000000.0000000.0000000.0000000.00000045.000000.0000000.0000000.0000000.0000000.0000000.0000001.00000011.000000.0000000.0000000.0000000.0000000.0000000.0000000.0000009.0000001.0000000.0000000.0000000.0000001.0000000.0000000.0

5、0000050.000000.0000000.0000000.0000000.0000000.0000000.0000001.00000015.000000.0000000.0000000.0000000.0000000.0000000.0000000.00000012.000001.0000000.0000000.0000000.0000000.0000000.0000000.00000012.000001.0000000.0000000.0000000.0000000.0000000.0000001.00000012.000000.0000000.0000000.0000000.00000

6、00.0000000.0000001.00000012.000000.0000000.0000000.0000000.0000000.0000000.0000000.0000008.0000001.0000000.000000X（K,1）O.OOOOOOO.OOOOOOX（K,2）O.OOOOOOO.OOOOOOX（K,3）O.OOOOOO9.OOOOOOX（K,4）1.OOOOOOO.OOOOOO例7.3旅行售货员问题（又称货郎担问题，Trave1ingSa1esmanProb1em）有一个推销员，从城市1出发，要遍访城市2,3,，n各一次，最后返回城市1。已知从城市i到j的旅费为问他应按怎

7、样的次序访问这些城市，使得总旅费最少？可以用多种方法把TSP表示成整数规划模型。这里介绍的一种建立模型的方法，是把该问题的每个解（不一定是最优的）看作是一次“巡回”。在下述意义下，引入一些OT整数变量：ct其目标只是使八月为最小。这里有两个明显的必须满足的条件：访问城市i后必须要有一个即将访问的确切城市；访问城市j前必须要有一个刚刚访问过的确切城市。用下面的两组约束分别实现上面的两个条件。到此我们得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于TSP来说并不充分，仅仅是必要条件。例如：以上两个c都满足，但它显%是TSP的解，它存在两个子巡回。这当人!门将叙述一种号4型上附加充

8、分的约束条件以避免产生子巡回的方法。把额外亭4（,2,3,勃森至N题中。可把这些变量看作是连续的（最然这些变量在最14敕数名唆附水J面形式的约束条件2ui-1,2ijn为了证明该约束条件有预期的效5必须证明：（1）任何含子巡回的路线都不满足该约束条件；（2）全部巡回都满足该约束条件。首先证明（1）,用反证法。假设还存在子巡.，也就是说至少有两个子巡回。那么至少存在一个子巡回中不含城市I。把该子巡回记为也则必有把这k个式子相加，有nn-f矛盾！故假设不正确，结论（1）得证。.下面证明（2）,采用构造法。对于任意的总巡回14-/，可取访问城市i的躯序数，取值范围为，1，”一2。因此，如一w-2,2

9、*。下面来证明总巡回满足该约束条件。（i）总巡回上的边（ii）非总巡回上的边从而结论（2）得证。这样我们把TSP转化成了一个混合整数线性规划问题。显然，当城市个数较大（大于30）时，该混合整数线性规划问题的规模会很大，从而给求解带来很大问题。TSP已被证明是NP难问题，目前还没有发现多项式时间的算法。对于小规模问题，我们求解这个混合整数线性规划问题的方式还是有效的。TSP是个重要的组合优化问题，除了有直观的应用外，许多其它看似无联系的优化问题也可转化为TSP。例如：问题1现需在一台机器上加工n个零件（如烧瓷器），这些零件可按任意先后顺序在机器上加工。我们希望加工完成所有零件的总时间尽可能少。由

10、于加工工艺的要求，加工零件/时机器必须处于相应状态（如炉温）。设起始未加工任何零件时机皆处于状态”,且当所有零件加工完成后需恢复到s。状态。已知从状态调整到状态Sjei）需要时间与。零件,本身加工时间为为方便起见，引入一个虚零件0,其加工时间为0,要求状态为%,则0,1,2,n的一个圈置换就表示对所有零件的一个加工顺序，在此置换下,完成所有加工所需要的总时间为P,由于=是一个常数，故该零件的加工顺序问题变成TSPo!旅行售货员问题；mode1:sets:city/1.5/:u;1ink(city,city):dist,!距离矩阵:endsetsn=size(city);data:!距离矩阵，它

11、并不需要是对称的;dist=qrand(1);!随机产生，这里可改为你要解决的问题的数据;enddata!目标函数；min=sum(1ink:dist*x);1OR(city(K):!进入城市K;sum(city(I)I#ne#K:x(I,K)=1;!离开城市K;SUn(city(J)IJ#ne#K:x(K,J)=1;)；!保证不出现子圈；for(city(I)11#gt#1:for(city(J)J#gt#1#and#1#ne#J:u(I)-u(J)+n*x(I,J)=n-1);)；for(city(I)II#gt#1:u(I)=n-2);!定义X为01变量；for(1ink:bin(x);

12、end计算的部分结果为:G1oba1optima1so1utionfoundatiteration:77Objectiveva1ue:1.692489Variab1eVa1ueReducedCostN5.OOOOOO0.000000U(1)0.0000000.000000U(2)1.0000000.000000U(3)3.0000000.000000U(4)2.0000000.000000U(5)0.0000000.000000DISK1,1)0.44917740.000000DIST(1,2)0.27245060.000000DIST(1,3)0.12404300.000000D1ST(1,

13、4)0.92468480.000000DIST(1,5)0.40217060.000000DISK2,1)0.70914690.000000D1ST(2,2)0.16851990.000000DIST(2,3)0.89896460.000000DISTC2,D0.25027470.000000DIST(2,5)0.89475710.000000DIST(3,D0.8648940E-010.000000DIST(3,2)0.60205910.000000D1ST(3,3)0.33808840.000000DIST(3,4)0.68131640.000000DIST(3,5)0.22362710.000000D1ST(4,1)0.97629870.000000DIST(4,2)0.88663430.000000DIST(4,3)