利用LINGO开发高级模型选讲.ppt

1、求解非线性方程式的代码： model: x2 y2=2； 2*x2 x y2 y=4。 end，7作为一个综合示例，一条装配线包含一系列工作站，每个工作站在最终产品的加工过程中执行一个或多个特定任务。 装配线周期是所有工作站完成分配给它们的任务所花费的最大时间。 平衡装配线的目标是将加工任务分配给每个工作站，并尽可能使每个工作站执行相同数量的任务。在不合适的平衡装配线中，具有较少瓶颈任务的工作站， 我们必须等到工作站上有很多任务被分配了，问题变得更复杂，因为许多任务之间有优先关系，任务的分配必须遵循这个优先关系。 该模型的目标是最小化装配线周期。 有两种制约。 为了保证每个任务，只能将其分配给

2、一个工作站进行加工。必须保证任务之间满足所有优先关系。 例如，将11个任务(AK )分配给4个工作站(14 )，任务的优先顺序如下图所示。 各项任务所花费的时间如下表所示。 例7.2装配线平衡模型，MODEL: 装配线平衡模型SETS: 具有完成时间属性t的任务集TASK/A B C D E F G H I J K/: T。 不要！ 任务之间的优先级关系的集合(例如，a必须完成才能开始b ) pred (任务)/a、b、c、F C、G F、J G、j、K D、e、H E、I H、J I、J /； 不要！ 工作站集合STATION/1.4/； txs (任务，站点) : x； 不要！ x是派生集

3、合TXS的属性。 如果是X(I，K)1，则第I个任务将分配给第k个工作站来完成。 endsets数据： 任务A B C D E F G H I J K的完成时间估计如下。 t=45十一九五十五十二十二十二八九。 结束数据！ 任务超过15的话，模型的解决会变慢请停止！ 每个作业必须分配给满足约束条件的工作站，for (task (I ) : sum (station (k ) : x (I，K)=1。 不要！ 对于处于优先级关系的每个工作对，对应于前者的站I必须小于对应于后者的站j，即，满足约束条件的FOR(PRED(I，j ) : sum (station (k ) : k * x (j，K)

4、 - K * X(I，k ) ) 每个工作站所需的时间不超过组装生产线周期，即for (站(k ) : sum (txs (I，K): T(I) * X(I，k ) )=cyc时间。 不要！ 目标函数是使接线周期最小化。MIN=CYCTIME； 不要！ 将X(I，j )指定为0/1变量。 FOR(TXS: BIN(X): END，一个推销员从城市1出发，一次访问城市2，3，n，最后返回城市1。 众所周知，从城市I到j的旅费是Cij，为了使总旅费最少，应该以怎样的顺序访问这些城市。 可以通过多种方式将TSP表示为整数修订模型。 建立这里所介绍的模型的一种方法是将这个问题的每个解(不一定是最佳的)

5、视为一次“循环”。 在下列意义上，引入几个0-1整数变量：例7.3旅行销售员问题(也称为货郎担保问题，Traveling Salesman Problem )只是最小化其目标。 这里显然有两个条件需要满足。 访问城市I后，需要访问的准确城市。 在访问城市j之前，需要一个刚刚访问的正确城市。 以上两个条件分别用以下两个制约来实现。 然后获得了一个模型，即指定问题的整数修订模型。 然而，这两个条件对于TSP是不充分的，并且仅仅是必要的条件。 例如，显然虽然满足这两种条件，但存在两个子巡回演出而不是TSP的解。 在此，对原来的模型附加充分的制约条件，使得不发生子巡回演出的方法进行叙述。 把多馀的变量

6、附加到问题上。 这些变量可以看作是连续的(最大似然这些变量在最优解中取普通的整数值)。 目前，必须添加以下形式的约束，以证明包括(1)子巡回演出的路径不满足此约束，以证明此约束具有预期效果。 (2)所有巡回都满足该制约条件。首先证明(1)，使用反证法。 假定子旅行团还存在，也就是说至少有两个子旅行团。至少有一个子旅行团有时不包含城市1。 把这个子旅行团记下来的话，一定有。 加上这k个公式，有矛盾，=城市I的访问顺序数，值的范围， 所以， 以下证明总巡回满足这一制约条件。 可以取，所以假设不正确，结论(1)得到了证明。 其次证明(2)，采用结构法。 对于任意的总巡回，()总巡回上的边，()非总巡

7、回上的边，以及(2)都得到了证明。 这样将TSP转换为混合整数线性修正图问题。 显然，当城市数量大(超过30 )时，该混合整数线性校正问题的规模变大，从而给解决带来很大的问题。 证明TSP是一个NP难题，目前尚未发现多项式时间算法。 对于小规模问题，求解该混合整数线性修正图问题的方式是有效的。 TSP是一个重要的组合优化问题，除了直观的应用程序之外，还可以将许多看似未联系的优化问题转换为TSP。 例如，问题1现在需要在一台机器上加工n个部件(烧瓷等)，这些部件能够以任意优先顺序加工成机器。 我们想尽可能减少在加工和完成所有零件之前的总时间。 根据加工工艺的要求，在加工零件j时，机器必须处于相应

8、的状态Sj (炉温等)。 最初加工没有进行任何加工的零件时，机械处于状态S0，所有的零件加工完成后，需要返回到S0的状态。 已知从状态Si调整到状态Sj(ij )需要时间Cij。 设部件j自身的加工时间为pj。 为了方便起见，当引入加工时间为0、要求状态为S0的虚设部件0时，0，1，2， n的一圈置换表示对所有部件的一个加工顺序，在该置换下，完成所有加工所需的总时间是一个常数，因此该部件、 旅行销售员的问题model : sets : city/1.5/: u 链接(城市，城市) 3360 dist， 距离矩阵x； endsets n=大小(city )； data: 距离矩阵不需要是对称的，

9、dist=qrand(1)； 不要！ enddata随机生成，可以在此处更改为需要解决的问题的数据！ 目标函数min=sum (链接： dist * x ):for (城市(k ) : 进入城市k的和(城市(I )|I # ne # k : x (I，K)=1。 不要！ 离开城市k。 和(天空(j )|j # ne # k : x (k，J)=1 )； 不要！ 保证子循环不出现的事件(city (I )|I # gt # 13360 for (j )|j # gt #1#和# I # ne # j 3360 u (I )。 )； 不要！ 限制u的范围加快模型的求解，保证所加的限制不排除TSP问

10、题的最佳解的for(city(i)|i#gt#1:u(i)=n-2 )。 不要！ 定义x为01变量的for(link: bin(x): end，规定的n个点pi (I=1，2，n )构成集合pi。 cij表示从任一点pi到另一点pj的距离，如果从pi到pj没有弧键，则规定为cij=、CII=0(I=1，2，n )。 指定终点pN，求出从pi点到pN的最短路径。 在动态修正法中，用点pi表示状态，决定集合是pi以外的点，在选定了点pj之后，得到cij转移到新的状态利益pj，在状态为pN的情况下，过程停止。 这是一个不定期的多阶段决策过程。 定义f(i ) :从点pi到终点pN的最短距离，由最佳化

11、原理得到：函数方程式，用LINGO容易解决。 例7.4最短路问题， 最短路的问题model: data: n=10； 最终数据集： cities/1.n/: f 不要！ 十个城市roads (城市，城市)/1、2、3、42、5、63、5、64、7、85、85、9结束集数据3360 d=6536971197410579。 结束数据f (n )=0； 接口，接口，接口，接口，接口，接口，接口。 不要！ 很明显，如果P(i，j)=1，则从点I到点n的最短路径的第一步是i - j，否则就是。 由此，能够简单地确定最短路径。for(roads(i，j):P(i，j)=if(F(i) #eq# D(i，j

12、) F(j )，1，0 end，例7.5露天矿生产的车辆安排(CMCM2003B )钢铁工业是国家工业的现代化的铁矿石多采自露天开采，其生产主要通过电动叉车(以下简称刀片)装载车、电动车轮自卸卡车(以下简称卡车)运输完成。 提高这些大型设备的利用率是提高露天矿经济效益的首要任务。 露天矿有几座爆破生成的石材山，每座山被称为叶片，每座叶片预先根据铁的含量把石材分成矿石和岩石。 一般来说，平均铁含量在25%以上的是矿石，否则是岩石。 已知每刀片的矿石、岩石数、矿石的平均铁含量(称为品位)。 每台刀片式服务器最多可安装一台刀片式服务器，平均装载时间为5分钟。 卸货地点(以下简称卸货地点)有排出矿石的

13、矿石泄漏、2个铁路倒置场(以下简称倒置场)和排出岩石的岩石泄漏、岩场等，各卸货地点有各自的产量要求。 从国家资源保护的角度和矿山经济效益考虑，矿石应该组合排放点所需的铁含量(假设要求均为29.5% 1%，称为品位限制)输送到排放点，组合的量在一个班次(8小时)内满足品位限制即可。 从长远来看，放点可以移动，但位移内不变。 卡车的平均倾卸时间为3分钟。 使用卡车载重量为154吨，平均时速为28。 卡车的燃料消耗量很大，每班车消耗近1吨的柴油。 因为发动机点火时需要消耗相当多的电池能量，所以一次换挡在起动时只点火一次。 卡车等待时消耗的能量也相当大，原则上安排时卡车不应该等待。 刀片式服务器和放置

14、点都不能同时为两台以上的卡车提供服务。 卡车每次都满载运输。 从每个刀片式服务器到每个卸载点的道路是专用宽度60？ 的双向车道不会发生堵塞现象，各条道路的行驶距离是已知的。 在一个班次的生产修订计划中，出动了几个叶片，出动了应该包含分别在哪个叶片的内容的几辆卡车，分别在哪个路线上各运送几次(由于随机要素的影响，装载时间和运送时间不正确，所以时间修订计划无效，各路径合格的修订版不等待卡车就要满足产量和质量(品位)的要求，但好的修订版应考虑以下两个原则之一：1.总运输量(吨公里)最小，同时出动最少的卡车，运输成本最小2 .利用现有车辆的运输请为两个原则分别建立数学模型，提供换班生产修订计划的快速算

15、法。 以下例子说明了具体的生产修订计划、相应的总运输量以及岩石和矿石的产量。 某露天矿有叶片10个、卸货5个、现有叶片7台、卡车20台。 各班次的产量要求为矿石泄漏1.2万吨，倒置场1.3万吨，倒置场1.3万吨，岩石泄漏1.9万吨，岩石场1.3万吨。叶片位置和叶片位置的二维示意图如下，各叶片位置和各叶片点间的距离(公里)如下表：各叶片矿石、岩石数(万吨)和矿石的平均铁含量如下表：各叶片矿石、岩石数(万吨)和矿石的平均铁含量如下表： sets 3333 xie/1 . 5 /:xsubject，xnum 链接(Xie，Cai ) 3360距离，l子对象，编号，che，b； end sets da

16、ta :创建=302829323133313331。 xsubject=1.2 1.3 1.3 1.9 1.3。 距离=5. 265.194.002.952.742.461.901.901.901.13.272.253.093.515.615.613.53.652.461.060.570.641 cy=1. 251.10.351.051.151.351.051.151.351.351.25。 CK=0. 951.051.001.051.101.251.051.301.351.25。 enddata、 目标函数min=sum (Cai (I ) 3360 sum (Xie (j ) 3360 number (j，I ) * 154 *距离(j，I ) ) )不要！ max=sum (链接(I，j ) :编号(I，j ) ) :不要！ 最大值=最小值(3)最小值(4)最小值(1)最小值(2)最小值(5)。 不要！ 最小(Cai ) : 求和(j ) : 数字(j，I ) * 154 *距离(j，I