lingo例题讲解1!10

1、例题讲解Model:title Assignment Problem;sets:worker/w1,w2,w3,w4,w5/:capacity;job/j1,j2,j3,j4,j5/:demend;routes(worker,job):cost,volume;endsetsmin=sum(routes:cost*volume);for(job(j):sum(worker(i):volume(i,j)=demend(j);for(worker(i):sum(job(j):volume(i,j)=capacity(i);data:capacity=1,1,1,1,1;demend=1,1,1,1,

2、1;cost=8 6 10 9 12 9 12 7 11 9 7 4 3 5 8 9 5 8 11 8 4 6 7 5 11;Enddataend练习For our example, we have eleven tasks (A through K) to assign to four workstations (1 through 4). The task precedence diagram looks like this:The times to complete the various tasks are given in the table below:Task:A B C D E

3、 F G H I J KMinutes:45 11 9 50 15 12 1212 12 8 9We need to find an assignment of tasks to workstations that minimize the assembly line抯 cycle time.MODEL: ! Assembly line balancing model; ! This model involves assigning tasks to stations in an assembly line so bottlenecks are avoided. Ideally, each s

4、tation would be assigned an equal amount of work.; SETS: ! The set of tasks to be assigned are A through K, and each task has a time to complete, T; TASK/ A B C D E F G H I J K/: T; ! Some predecessor,successor pairings must be observed(e.g. A must be done before B, B before C, etc.); PRED( TASK, TA

5、SK)/ A,B B,C C,F C,G F,J G,J J,K D,E E,H E,I H,J I,J /;! There are 4 workstations; STATION/1.4/; TXS( TASK, STATION): X; ! X is the attribute from the derived set TXS that represents the assignment. X(I,K) = 1 if task I is assigned to station K; ENDSETS DATA: ! Data taken from Chase and Aquilano, PO

6、M; ! There is an estimated time required for each task: A B C D E F G H I J K; T = 45 11 9 50 15 12 12 12 12 8 9; ENDDATA ! The model; ! *Warning* may be slow for more than 15 tasks; ! For each task, there must be one assigned station;FOR( TASK( I): SUM( STATION( K): X( I, K) = 1); ! Precedence cons

7、traints; ! For each precedence pair, the predecessor task I cannot be assigned to a later station than its successor task J; FOR( PRED( I, J): SUM( STATION( K): K * X( J, K) - K * X( I, K) = 0); ! For each station, the total time for the assigned tasks must be less than the maximum cycle time, CYCTI

8、ME; FOR( STATION( K): SUM( TXS( I, K): T( I) * X( I, K) = 0);Suppose task I is a predecessor to task J. If I were incorrectly assigned to a workstation later than J, the sum of the terms K * X( I, K) would exceed the sum of the terms K * X( J, K) and the constraint would be violated. Thus, this cons

9、traint effectively enforces the predecessor relations.We compute the cycle time using the following constraints:! For each station, the total time for the assigned tasks must be less than the maximum cycle time, CYCTIME; FOR( STATION( K): SUM( TXS( I, K): T( I) * X( I, K) = CYCTIME);The quantity:SUM

10、( TXS( I, K): T( I) * X( I, K)in this constraint computes the cycle time for station K. We use the FOR statement to make the CYCTIME variable greater than or equal to the cycle times for all the orkstations. If we couple this with the fact that we are minimizing CYCTIME in the objective, CYCTIME wil

11、l be squeezed into exactly equaling the maximum of the cycle times for each of the workstations. By squeezing CYCTIME to the correct value, we avoid using the MAX function. Had the MAX function been used, LINGO would have had to resort to its nonlinear solver to handle the piecewise linear MAX. Avoi

12、ding nonlinear models whenever possible is a critical modeling practice.Solving the model, we get the following nonzero values for the assignment variable X: Variable ValueSolution: ASLBALSummarizing this solution, we have:WorkstationAssigned TasksCycle Time1D502A453B, E, H, I504C, F, G, J, K50The cycle t