《LINGO在多目标规划和最大最小化模型中的应用.pdf》由会员分享，可在线阅读，更多相关《LINGO在多目标规划和最大最小化模型中的应用.pdf（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、LINGOLINGO 在多目标规划和最大最小化模型中的应用在多目标规划和最大最小化模型中的应用在许多实际问题中，决策者所期望的目标往往不止一个，如电力网络管理部门在制定发电计划时即希望安全系数要大，也希望发电成本要小，这一类问题称为多目标最优化问题或多目标规划问题。一、多目标规划的常用解法一、多目标规划的常用解法多目标规划的解法通常是根据问题的实际背景和特征，设法将多目标规划转化为单目标规划，从而获得满意解，常用的解法有：1主要目标法确定一个主要目标，把次要目标作为约束条件并设定适当的界限值。2线性加权求和法对每个目标按其重要程度赋适当权重i 0，且i1，然后把ifi(x)ii作为新的目标函数
2、（其中fi(x),i 1,2,p是原来的p个目标）。3指数加权乘积法设fi(x),i 1,2,p是原来的p个目标，令Z fi(x)aii1p其中ai为指数权重，把Z作为新的目标函数。4理想点法先分别求出p个单目标规划的最优解fi*，令h(x)(f(x)fi*2i)然后把它作为新的目标函数。5分层序列法将所有p个目标按其重要程度排序，先求出第一个最重要的目标的最优解，然后在保证前一个目标最优解的前提条件下依次求下一个目标的最优解，一直求到最后一个目标为止。这些方法各有其优点和适用的场合，但并非总是有效，有些方法存在一些不足之处。例如，线性加权求和法确定权重系数时有一定主观性，权重系数取值不同，结
3、果也就不一样。线性加权求和法、指数加权乘积法和理想点法通常只能用于两个目标的单位（量纲）相同的情况，如果两个目标是不同的物理量，它们的量纲不相同，数量级相差很大，则将它们相加或比较是不合适的。二、最大最小化模型二、最大最小化模型在一些实际问题中，决策者所期望的目标是使若干目标函数中最大的一个达到最小（或多个目标函数中最小的一个达到最大）。例如，城市规划中需确定急救中心的位置，希望该中心到服务区域内所有居民点的距离中的最大值达到最小，称为最大最小化模型，这种确定目标函数的准则称为最大最小化原则，在控制论，逼近论和决策论中也有使用。最大最小化模型的目标函数可写成minmaxf1(X),f2(X),
4、fp(X)X或maxminf1(X),f2(X),fp(X)X式中X(x1,x2,xn)T是决策变量。模型的约束条件可以包含线性、非线性的等式和不等式约束。这一模型的求解可视具体情况采用适当的方法。三、用三、用 LINGOLINGO 求解多目标规划和最大最小化模型求解多目标规划和最大最小化模型1解多目标规划用 LINGO 求解多目标规划的基本方法是先确定一个目标函数，求出它的最优解，然后把此最优值作为约束条件，求其他目标函数的最优解。如果将所有目标函数都改成约束条件，则此时的优化问题退化为一个含等式和不等式的方程组。LINGO 能够求解像这样没有目标函数只有约束条件的混合组的可行解。有些组合优
5、化问题和网络优化问题，因为变量多，需要很长运算时间才能算出结果，如果设定一个期望的目标值，把目标函数改成约束条件，则几分钟就能得到一个可行解，多试几个目标值，很快就能找到最优解。对于多目标规划，同样可以把多个目标中的一部分乃至全部改成约束条件，取适当的限制值，然后用 LINGO 求解，从中找出理想的最优解，这样处理的最大优势是求解速度快，节省时间。2解最大最小化问题第一步，先把原来较复杂的目标函数式改写为一个简单的目标函数minC以及p个约束条件：f1(X)C,f2(X)C,fp(X)C其他原有的约束条件不变，改写后仍然是一个规划，只是增加了p个约束条件，目标函数的形式较为简单。如果能用 LI
6、NGO 求出它的解，则问题已经解决，如果求解困难，可转入下一步。第二步，取消目标函数，保留上一步由目标函数改成的p个约束条件和所有原来的约束条件，预设C值为某个常数，此时原规划模型不再是规划，它仅仅包含等式和不等式，没有目标函数，是许多约束条件的组合，可以称它为“混合组”。求该混合组的解，其实质是求满足所有约束条件并且使目标函数等于给定值的一组决策变量的值，求出来的结果是可行解，它未必是最优解。在存在可行解的前提下，使目标函数值小的可行解优于使目标函数值大的可行解，使目标函数值越小的可行解越接近最优解。第三步，对具体问题作出分析，对目标函数可能达到的最小值（即 C 的最小值）作适当估计，然后在
7、此估计值的基础上由大到小改变 C 的值进行试算，使可行解越来越接近最优解。对于目标函数值离散的情况，不难找到最优解。例：例：装配线平衡模型。装配线平衡模型。一条装配线含有一系列的工作站，在最终产品的加工过程中每个工作站执行一种或几种特定的任务。装配线周期是指所有工作站完成分配给它们各自的任务所化费时间中的最大值。平衡装配线的目标是为每个工作站分配加工任务，尽可能使每个工作站执行相同数量的任务，其最终标准是装配线周期最短。不适当的平衡装配线将会产生瓶颈有较少任务的工作站将被迫等待其前面分配了较多任务的工作站。问题会因为众多任务间存在优先关系而变得更复杂，任务的分配必须服从这种优先关系。这个模型的
8、目标是最小化装配线周期。有 2 类约束：要保证每件任务只能也必须分配至一个工作站来加工；要保证满足任务间的所有优先关系。例有 11 件任务（AK）分配到 4 个工作站（14），任务的优先次序如下图。每件任务所花费的时间如下表。(A)(B)(C)(G)(J)(H);(F)(K)(E)(I)/GHIJ时间451195015121212128任务ABCDEFK9解：用变量xik表示任务i(i A,B,K)分配给工作站k(k 1,2,3,4)的情况，xik1表示分配，xik 0表示不分配，ti表示完成各项任务所需时间，则目标函数为minmaxtixik1k4i111约束条件（1）：每项任务只能且必须分
9、配至一个工作站来做，可以表示为：xk14ik1,i 1,2,11；约束条件（2）：各项任务间如果有优先关系，则排在前面的任务i对应的工作站（序号）应当小于（或等于）排在后面的任务j所对应的工作站（序号），即对所有有顺序的任务i j：(kxjk kxik)0；k14约束条件（3）：xik 0或1。，这是一个非线性规划（目标函数非线性），但可以化为线性规划，增加一个变量，再增加四个约束条件：tixikZ,k1,2,3,4，目标函数变为minZ。i 111LINGO 程序为：model:!装配线平衡模型;sets:!任务集合，有一个完成时间属性 t;task/A B C D E F G H I J
10、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/;tsx(task,station):x;!x 是派生集合 txs 的一个属性。如果 x(i，k）1，则表示第 i 个任务指派给第 k 个工作站完成;endsetsdata:!任务 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 个时，模型的求解
11、将变得很慢;!每一个作业必须指派到一个工作站，即满足约束;￥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:b
12、in(x);:end计算的部分结果为 Global optimal solution found at iteration:1255 Objective value:Variable Value Reduced Cost CYCTIME X(A,1)X(A,2)X(A,3)X(A,4)X(B,1)X(B,2)X(B,3)X(B,4)X(C,1)X(C,2)X(C,3)X(C,4)X(D,1)X(D,2)X(D,3)X(D,4)/X(E,1)X(E,2)X(E,3)X(E,4)X(F,1)X(F,2)X(F,3)X(F,4)X(G,1)X(G,2)X(G,3)X(G,4)X(H,1)X(H,2)
13、X(H,3)X(H,4)X(I,1)X(I,2)X(I,3)X(I,4)X(J,1)X(J,2)【X(J,3)X(J,4)X(K,1)X(K,2)X(K,3)X(K,4)例：工件的安装与排序问题。例：工件的安装与排序问题。某设备由 24 个工件组成，安装时需要按工艺要求重新排序。I 设备的 24 个工件均匀分布在等分成六个扇形区域的一圆盘的边缘上，放在每个扇形区域的4个工件总重量与相邻区域的4个工件总重量之差不允许超过一定值。II工件的排序不仅要对重量差有一定的要求，还要满足体积的要求，即两相邻工件的体积差应尽量大，使得相邻工件体积差不小于一定值。问题 1：按重量排序算法；问题 2：按重量和体
14、积排序算法；请按下表中的工件数据（重量单位：g，体积单位：cm3）进行实时计算。序1号重348量体积序11号重329量体98积序21号重量体99积23521021299229833471051323表 工件的重量和体积数据5674(34983299818348932919333971020330971061534710416348330941710414；34710524332*解：对问题1和2分别求解。（1）对问题1，仅考虑重量进行排序。用i 1,2,24表示24个工件，Wi表示各工件的重量，j 1,2,6表示圆盘上的6个扇区，Dj表示各扇区上4个工件的总重量，Xij是0-1型决策变量，表示
15、工件i是否放在扇区j上，Xij1表示放，Xij 0表示不放。：每个工件必须且只能放到一个位置上，每个位置放一个且仅放一个工件，每个扇区放4个工件，重量之和为Dj。目标函数是：相邻扇区上的Dj之差的（绝对值）最大值达到最小，建立0-1规划模型如下：minmax|Dk1 Dk|1k624Xij 4,j 1,2,6i16Xij1,i 1,2,24j124DjWiXij,j 1,2,6,D7 D1i1X 0或1ij模型中的D7是虚拟的，D7 D1使得1-6-1扇区构成圆盘，引入D7的目的只是使目标函数的表达式简洁。该0-1规划模型的目标函数是相邻扇区上的Dj之差（绝对值）的最大值达到最小，属于最大最小
16、化模型。按照前面所述把规划模型转化为混合组的步骤，去掉目标函数，增加约束条件：|Dj1 Dj|C,j 1,2,6保留原来的约束条件，并令C为某个常数，原规划就转化成了一个包含150个变量，36个等式约束，6个不等式约束的非线性混合组。由于24个工件的重量数据多数为整数，部分有小数，小数的最小计数单位为，所以相邻扇区重量之差的基本计数单位是，即|Dj1 Dj|的可能取值是离散的。令C取0，1，2，中的具体值（C值越小越好）。用LINGO编程求解，不难求得当C=时有可行解，因C=0时无可行解，故C=时的可行解就是最优解。用第一组工件的重量数据，编写LINGO程序如下：model:sets:gj/1
17、.24/:w;shq/1.6/:d;bl(gj,shq):x;endsetsdata:w=348 352 347 349 347 330 329 329 329 347 348 348 333 330 332;enddatafor(bl:bin(x);c=;!常数C可以设定不同的值试一试;for(gj(i):sum(shq(j):x(i,j)=1);for(shq(j):sum(gj(i):x(i,j)=4);&for(shq(j):d(j)=sum(gj(i):w(i)*x(i,j);for(shq(j)|j#lt#6:d(j+1)-d(j)=-c);d(1)-d(6)=-c;end运行结果
18、如下：Feasible solution found at iteration:15994 Variable Value】C W(1)W(2)W(3)W(4)W(5)W(6)W(7)W(8)W(9)W(10)W(11)W(12)W(13)W(14)W(15)W(16)W(17)W(18)W(19)W(20)W(21)W(22)W(23)W(24)D(1)D(2)D(3)D(4)D(5)D(6)X(1,1)X(1,2)、X(1,3)X(1,4)X(1,5)X(1,6)X(2,1)X(2,2)X(2,3)X(2,4)X(2,5)X(2,6)X(3,1)X(3,2)X(3,3)X(3,4)X(3,5
19、)X(3,6)X(4,1)X(4,2)X(4,3)X(4,4)X(4,5)X(4,6)|X(5,1)X(5,2)X(5,3)X(5,4)X(5,5)X(5,6)X(6,1)X(6,2)X(6,3)X(6,4)X(6,5)￥X(6,6)X(7,1)X(7,2)X(7,3)X(7,4)X(7,5)X(7,6)X(8,1)X(8,2)X(8,3)X(8,4)(X(8,5)X(8,6)X(9,1)X(9,2)X(9,3)X(9,4)X(9,5)X(9,6)X(10,1)X(10,2)X(10,3)X(10,4)X(10,5)X(10,6)X(11,1)X(11,2)X(11,3)X(11,4)X(11
20、,5)X(11,6)X(12,1)X(12,2)）X(12,3)X(12,4)X(12,5)X(12,6)X(13,1)X(13,2)X(13,3)X(13,4)X(13,5)X(13,6)X(14,1)X(14,2)X(14,3)X(14,4)X(14,5)X(14,6)X(15,1)X(15,2)X(15,3)X(15,4)X(15,5)X(15,6)、X(16,1)X(16,2)X(16,3)X(16,4)X(16,5)X(16,6)X(17,1)X(17,2)X(17,3)X(17,4)X(17,5)X(17,6)X(18,1)X(18,2)X(18,3)X(18,4)X(18,5)X
21、(18,6)X(19,1)X(19,2)X(19,3)X(19,4)X(19,5)X(19,6)X(20,1)X(20,2)X(20,3)X(20,4)X(20,5)X(20,6)X(21,1)X(21,2)X(21,3)X(21,4)X(21,5)X(21,6)X(22,1)X(22,2)X(22,3)X(22,4)X(22,5)X(22,6)X(23,1)X(23,2)X(23,3)X(23,4)X(23,5)X(23,6)X(24,1)X(24,2)X(24,3)X(24,4)X(24,5)X(24,6)由此求出一种放置方案（答案不唯一），见下表：扇区一二三四五六工件 9,13,1,6
22、4,5 2,10 3,11 14,1517,24 7,12 8,23 18,20 16,19 21,22总重量 1357 1357 1357（2）对问题2，既考虑重量，也考虑体积进行排序。符号规定与问题1略有不同，j是圆盘上的位置序号，k是扇区编号，每个扇区有4个位置，Vi表示各工件体积，Dk表示各扇区上4个工件的总重量，Tj表示第j个位置上所放工件的体积，Xij是0-1型决策变量，表示工件i是否放在位置j上，Xij1表示放，Xij 0表示不放。每个工件必须且只能放到一个位置上，每个位置放一个且仅放一个工件，每个扇区放4个工件，重量之和为Dk，目标函数有两个：相邻扇区上的Dk之差的最大值达到最
23、小；相邻位置上工件的体积之差的最小值达到最大。建立双目标规划模型如下：minmax|Dk1 Dk|,k 1,2,5,|D6 D1|目标函数：maxmin|TT|,j 1,2,23,|TT|j1j24124Xij1,j 1,2,24i124Xij1,i 1,2,24j14k24约束条件：Dk WiXij,k 1,2,6j4k3 i124TjVjXij,j 1,2,24i1X 0或1ij把问题1的计算结果作为约束条件，即增加约束条件：Di1357,i 1,2,5。然后考虑第二个目标：相邻位置上工件的体积之差（绝对值）的最小值达到最大，把这个目标也改成约束条件，即再增加约束条件：|Tj1Tj|H,j 1,2,23,|T24T1|HH是希望达到的目标函数的值，此时双目标规划就变成了没有目标函数，仅含有等式和不等式的混合组，这样处理的最大优点是计算速度快。编写LINGO程序，当H=时，找到可行解。注意：解答不唯一，且不能肯定这一定是最优解时，可以在LINGO求解的基础上做一些手工调整，得到更好的方案。