§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的解，它存在两个子巡回
这里,将叙述一种在原模型上附加充分的约束条件以避免产生子巡 回的方法。把额外变量1(=2,3,…,n) 附加到问题中。可把这些变量看作是连续的(最然这些变量在最优 解中取普通的整数值)。现在附加下面形式的约束条件 l4-l2+ nxisn-,2≤i≠jsn 为证明该约東条件有预期的效果,必须证明: (1)任何含子巡回的路线都不满足该约束条件; (2)全部巡回都满足该约束条件。 首先证明(1),用反证法。假设还存在子巡回,也就是说至少有 两个子巡回。那么至少存在一个子巡回中不含城市1。把该子巡回 记为2…,则必有l12-l12+n≤n-1 2-l2+n≤n-1 u tn<n-1
这里，将叙述一种在原模型上附加充分的约束条件以避免产生子巡 回的方法。把额外变量 附加到问题中。可把这些变量看作是连续的（最然这些变量在最优 解中取普通的整数值）。现在附加下面形式的约束条件 − + − 1 2 i j ij u u nx n i j n ， 为证明该约束条件有预期的效果，必须证明： （1）任何含子巡回的路线都不满足该约束条件； （2）全部巡回都满足该约束条件。 首先证明（1），用反证法。假设还存在子巡回，也就是说至少有 两个子巡回。那么至少存在一个子巡回中不含城市1。把该子巡回 记为 u i n i ( = 2, 3, , ) 1 2 1 k i i i i ，则必有 1 2 2 3 1 1 1 1 − + − − + − − + − k i i i i i i u u n n u u n n u u n n
这k个式子相加,有:n≤n-1,矛盾! 故假设不正确,结论(1)得证 下面证明(2),采用构造法。对于任意的总巡回 可取 l4=访问城市顺序数,取值范围为{=23,…,mn}。因此, l1-l/≤n-22≤i≠j≤n。下面来证明总巡回满足该约束条件。 (i)总巡回上的边 L.+n=n-1≤n-1 L.-l.+n=n-1<n +n=n-1
这k个式子相加，有： ，矛盾！ =访问城市i的顺序数，取值范围为 。因此， 。下面来证明总巡回满足该约束条件。 ，可取 n n −1 故假设不正确，结论（1）得证。 下面证明（2），采用构造法。对于任意的总巡回 2 -1 1 1 n i i i u i n = 2, 3, , − − 2 i j u u n 2 i j n (ⅰ)总巡回上的边 1 2 2 3 2 1 1 1 1 1 1 1 − − − + = − − − + = − − − + = − − n n i i i i i i u u n n n u u n n n u u n n n
(i)非总巡回上的边 .≤n-2<n-1J r+1 1u1-u-≤n=2≤n1j∈{=23…n-{ 从而结论(2)得证。 这样我们把TSP转化成了一个混合整数线性规划问题
（ⅱ）非总巡回上的边 从而结论（2）得证。 这样我们把TSP转化成了一个混合整数线性规划问题。 1 2 -1 2 -1 − − − − − r n i j i j u u n n u u n n j i n i i = − 2, 3, , , r r+1 r n = − 1, 2, , 2 j i n i = − 2, 3, , r
min z ∑Cn 1≠ s t ∑ l-l1+nxn≤n-1,2≤i≠j≤n 0.1 l2≥0, i=2.3
, 1 1 1 min . . 1 1, 2, , 1 1, 2, , 1 2 0,1 , 1, 2, , 0, 2, 3, , = = = = = = = = − + − = = = ij ij i j i j n ij j n ij i i j ij ij i z C x s t x j n x i n u u nx n i j n x i j n u i n
显然,当城市个数较大(大于30)时,该混合整数线性规划问题的 规模会很大,从而给求解带来很大问题。TSP已被证明是N难问题, 目前还没有发现多项式时间的算法。对小规模问题,求解这个混合 整数线性规划问题的方式还是有效的。 TSP是一个重要的组合优化问题,除了有直观的应用外,许多其它 看似无联系的优化问题也可转化为TSP。例如: 问题1现需在一台机器上加工n个零件(如烧瓷器),这些零件可 按任意先后顺序在机器上加工。我们希望加工完成所有零件的总时 间尽可能少。由于加工工艺的要求,加工零件j时机器必须处于相 应状态S;(如炉温)。设起始未加工任何零件时机器处于状态S, ,且当所有零件加工完成后需恢复到S状态。已知从状态S;调整到 状态S1(i≠j需要时间C。零件j本身加工时间为D。为方便起见 引入一个虚零件0,其加工时间为0,要求状态为S0,,则{0,1 ,2,…,n}的一个圈置换π就表示对所有零件的一个加工顺序, 在此置换下,完成所有加工所需要的总时间为 ∑(c4+p)=∑c+2 =0 ∑ P,是一个常数,故该零件的加工顺序问题变成TSP
显然，当城市个数较大（大于30）时，该混合整数线性规划问题的 规模会很大，从而给求解带来很大问题。TSP已被证明是NP难问题， 目前还没有发现多项式时间的算法。对小规模问题，求解这个混合 整数线性规划问题的方式还是有效的。 TSP是一个重要的组合优化问题，除了有直观的应用外，许多其它 看似无联系的优化问题也可转化为TSP。例如： 问题1 现需在一台机器上加工n个零件（如烧瓷器），这些零件可 按任意先后顺序在机器上加工。我们希望加工完成所有零件的总时 间尽可能少。由于加工工艺的要求，加工零件j时机器必须处于相 应状态Sj（如炉温）。设起始未加工任何零件时机器处于状态S0， ，且当所有零件加工完成后需恢复到S0状态。已知从状态Si调整到 状态Sj(i≠j)需要时间Cij 。零件j本身加工时间为pj。为方便起见 ，引入一个虚零件0，其加工时间为0，要求状态为S0， ，则{0，1 ，2，…，n}的一个圈置换π就表示对所有零件的一个加工顺序， 在此置换下，完成所有加工所需要的总时间为 由于 是一个常数，故该零件的加工顺序问题变成TSP。 ( ( ) ( ) ) ( ) 0 0 0 = = = + = + n n n i i i i i j i i j C p C p =0 n j j p