§7综合举例 例7.1求解非线性方程组 jx2+y2=2 2x2+x+y2+y=4 代码: model x^2+y^2=2; 2*x^2+x+y^2+y=4; end
例7.1 求解非线性方程组 代码： model: x^2+y^2=2; 2*x^2+x+y^2+y=4; end §7 综合举例 2 2 2 2 2 2 4 x y x x y y + = + + + =
例7.2装配线平衡模型 条装配线含有一系列的工作站,在最终产品的加工过程中每个工作站执行 种或几种特定的任务。装配线周期是指所有工作站完成分配给它们各自的任务 所化费时间中的最大值。平衡装配线的目标是为每个工作站分配加工任务,尽可 能使每个工作站执行相同数量的任务,其最终标准是装配线周期最短。不适当的 平衡装配线将会产生瓶颈——有较少任务的工作站将被迫等待其前面分配了较多 任务的工作站。 问题会因为众多任务间存在优先关系而变得更复杂,任务的分配必须服从这 种优先关系 这个模型的目标是最小化装配线周期。有2类约束: ①要保证每件任务只能也必须分配至一个工作站来加工; ②要保证满足任务间的所有优先关系 例有11件任务(AK)分配到4个工作站(1-4),任务的优先次序如下图 每件任务所花费的时间如下表 F (A)—(B)—(C大 G (K) H (D) (E)
一条装配线含有一系列的工作站，在最终产品的加工过程中每个工作站执行 一种或几种特定的任务。装配线周期是指所有工作站完成分配给它们各自的任务 所化费时间中的最大值。平衡装配线的目标是为每个工作站分配加工任务，尽可 能使每个工作站执行相同数量的任务，其最终标准是装配线周期最短。不适当的 平衡装配线将会产生瓶颈——有较少任务的工作站将被迫等待其前面分配了较多 任务的工作站。 问题会因为众多任务间存在优先关系而变得更复杂，任务的分配必须服从这 种优先关系。 这个模型的目标是最小化装配线周期。有2类约束： ① 要保证每件任务只能也必须分配至一个工作站来加工； ② 要保证满足任务间的所有优先关系。 例 有11件任务（A—K）分配到4个工作站（1—4），任务的优先次序如下图 。每件任务所花费的时间如下表。 例7.2 装配线平衡模型 （I） （H） （G） （J） （K） （F） （A） （B） （C） （D） （E）
任务 ABCDEF6H1JK 时间4511950151212121289 MODEL !装配线平衡模型; SETS !任务集合,有一个完成时间属性T; TASKABCDEFGHIJK: T !任务之间的优先关系集合(A必须完成才能开始B,等等) PRED( TASK, TASK)/A, BB, CC, F C, G F,J G,JJ, KD,EE, H E, I H,J L,J/ 工作站集合 STATION/ 1. 4/ TXS( TASK, STATION): X !X是派生集合TXS的一个属性。如果X(1,K)=1,则表示第个任务指派给第K个工作站完成; ENDSETS DATA !任务 A BCDEFG H|JK的完成时间估计如下 T=4511950151212121289; ENDDATA !当任务超过15个时,模型的求解将变得很慢; !每一个作业必须指派到一个工作站,即满足约束①; @FOR( TASK( D: @SUM( STATION( K): X(I, K)) !对于每一个存在优先关系的作业对来说,前者对应的工作站必须小于后 者对应的工作站J,即满足约束② @FOR( PRED( I, J): @SUM( STATION( K): K*X(J, K-K*(I, K)>=0) !对于每一个工作站来说,其花费时间必须不大于装配线周期 @FOR( STATION( K @SUM( TXS(I, K): T(DX(I, K))<=CYCTIME) !目标函数是最小化转配线周期 MIN E CYCTIME, 指定X(1,J)为0/1变量 @FOR( TXS: BIN X) END
MODEL: !装配线平衡模型; SETS: !任务集合，有一个完成时间属性T; TASK/ A B C D E F G H I J K/: T; !任务之间的优先关系集合（A 必须完成才能开始B，等等）; PRED( TASK, TASK)/ A,B B,C C,F C,G F,J G,J J,K D,E E,H E,I H,J I,J /; ! 工作站集合; STATION/1..4/; TXS( TASK, STATION): X; ! X是派生集合TXS的一个属性。如果X（I，K）＝1，则表示第I个任务指派给第K个工作站完成; ENDSETS DATA: !任务A B C D E F G H I J K的完成时间估计如下; T = 45 11 9 50 15 12 12 12 12 8 9; ENDDATA ! 当任务超过15个时，模型的求解将变得很慢; !每一个作业必须指派到一个工作站，即满足约束①; @FOR( TASK( 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); !对于每一个工作站来说，其花费时间必须不大于装配线周期; @FOR( STATION( K): @SUM( TXS( I, K): T( I) * X( I, K)) <= CYCTIME); !目标函数是最小化转配线周期; MIN = CYCTIME; !指定X(I,J) 为0/1变量; @FOR( TXS: @BIN( X)); END 任务 A B C D E F G H I J K 时间 45 11 9 50 15 12 12 12 12 8 9
J7.3旅行售货员问题(又称货郎担问题, Traveling Salesman Problem) 有一个推销员,从城市1出发,要遍访城市2,3,…,n各一次,最 后返回城市1。已知从城市i到j旅费为C;;问他应按怎样的次序 访问这些城市,使得总旅费最少? 可以用多种方法把TSP表示成整数规划模型。这里介绍的一种建立 模型的方法,是把该问题的每个解(不一定是最优的)看作是一次 在下述意义下,引入一些0-1整数变量: ,巡回路线是从倒,且i≠ 0,其它情况 其目标只是使∑Cnx为最小
有一个推销员，从城市1出发，要遍访城市2，3，…，n各一次，最 后返回城市1。已知从城市i到j的旅费为Cij，问他应按怎样的次序 访问这些城市，使得总旅费最少？ 可以用多种方法把TSP表示成整数规划模型。这里介绍的一种建立 模型的方法，是把该问题的每个解（不一定是最优的）看作是一次 “巡回” 。 在下述意义下，引入一些0-1整数变量： 例7.3 旅行售货员问题（又称货郎担问题，Traveling Salesman Problem） 1 0 ij i j i j x = ， 巡回路线是从 到 ，且 ， 其它情况 其目标只是使 为最小。 , 1= ij ij i j C x
这里有两个明显的必须满足的条件: 访问城市i后必须要有一个即将访问的确切城市; 访问城市j前必须要有一个刚刚访问过的确切城市 用下面的两组约束分别实现上面的两个条件。 ∑ 到此得到了一个模型,它是一个指派问题的整数规划模型。但以上 两个条件对于TSP来说并不充分,仅仅是必要条件 例如 以上两个条件都满足,但它显然不是TSP的解,它存在两个子巡回
这里有两个明显的必须满足的条件： 访问城市i后必须要有一个即将访问的确切城市； 访问城市j前必须要有一个刚刚访问过的确切城市。 用下面的两组约束分别实现上面的两个条件。 1 1 n ij j x = = i n =1, 2, , 1 1 n ij i x = = j n =1, 2, , 1 2 3 4 5 6 到此得到了一个模型，它是一个指派问题的整数规划模型。但以上 两个条件对于TSP来说并不充分，仅仅是必要条件。 例如： 以上两个条件都满足，但它显然不是TSP的解，它存在两个子巡回