LINGO在多目标规划和最大最小化模型中的应用

LINGO在多目标规划和最大最小化模型中的应用在许多实际问题中，决策者所期望的目标往往不止一个，如电力网络管理部门在制定发电计划时即希望安全系数要大，也希望发电成本要小，这一类问题称为多目标最优化问题或多目标规划问题。一、多目标规划的常用解法多目标规划的解法通常是根据问题的实际背景和特征，设法将多目标规划转化为单目标规划，从而获得满意解，常用的解法有：1．主要目标法确定一个主要目标，把次要目标作为约束条件并设定适当的界限值。2．线性加权求和法对每个目标按其重要程度赋适当权重0i，且1ii，然后把)(xfiii作为新的目标函数（其中pixfi,,2,1),(是原来的p个目标）。3．指数加权乘积法设pixfi,,2,1),(是原来的p个目标，令piaiixfZ1)]([其中ia为指数权重，把Z作为新的目标函数。4．理想点法先分别求出p个单目标规划的最优解*if，令2*))(()(iifxfxh然后把它作为新的目标函数。5．分层序列法将所有p个目标按其重要程度排序，先求出第一个最重要的目标的最优解，然后在保证前一个目标最优解的前提条件下依次求下一个目标的最优解，一直求到最后一个目标为止。这些方法各有其优点和适用的场合，但并非总是有效，有些方法存在一些不足之处。例如，线性加权求和法确定权重系数时有一定主观性，权重系数取值不同，结果也就不一样。线性加权求和法、指数加权乘积法和理想点法通常只能用于两个目标的单位（量纲）相同的情况，如果两个目标是不同的物理量，它们的量纲不相同，数量级相差很大，则将它们相加或比较是不合适的。二、最大最小化模型在一些实际问题中，决策者所期望的目标是使若干目标函数中最大的一个达到最小（或多个目标函数中最小的一个达到最大）。例如，城市规划中需确定急救中心的位置，希望该中心到服务区域内所有居民点的距离中的最大值达到最小，称为最大最小化模型，这种确定目标函数的准则称为最大最小化原则，在控制论，逼近论和决策论中也有使用。最大最小化模型的目标函数可写成)}(,),(),(max{min21XfXfXfpX或)}(,),(),(min{max21XfXfXfpX式中TnxxxX),,,(21是决策变量。模型的约束条件可以包含线性、非线性的等式和不等式约束。这一模型的求解可视具体情况采用适当的方法。三、用LINGO求解多目标规划和最大最小化模型1．解多目标规划用LINGO求解多目标规划的基本方法是先确定一个目标函数，求出它的最优解，然后把此最优值作为约束条件，求其他目标函数的最优解。如果将所有目标函数都改成约束条件，则此时的优化问题退化为一个含等式和不等式的方程组。LINGO能够求解像这样没有目标函数只有约束条件的混合组的可行解。有些组合优化问题和网络优化问题，因为变量多，需要很长运算时间才能算出结果，如果设定一个期望的目标值，把目标函数改成约束条件，则几分钟就能得到一个可行解，多试几个目标值，很快就能找到最优解。对于多目标规划，同样可以把多个目标中的一部分乃至全部改成约束条件，取适当的限制值，然后用LINGO求解，从中找出理想的最优解，这样处理的最大优势是求解速度快，节省时间。2．解最大最小化问题第一步，先把原来较复杂的目标函数式改写为一个简单的目标函数Cmin以及p个约束条件：CXfCXfCXfp)(,,)(,)(21其他原有的约束条件不变，改写后仍然是一个规划，只是增加了p个约束条件，目标函数的形式较为简单。如果能用LINGO求出它的解，则问题已经解决，如果求解困难，可转入下一步。第二步，取消目标函数，保留上一步由目标函数改成的p个约束条件和所有原来的约束条件，预设C值为某个常数，此时原规划模型不再是规划，它仅仅包含等式和不等式，没有目标函数，是许多约束条件的组合，可以称它为“混合组”。求该混合组的解，其实质是求满足所有约束条件并且使目标函数等于给定值的一组决策变量的值，求出来的结果是可行解，它未必是最优解。在存在可行解的前提下，使目标函数值小的可行解优于使目标函数值大的可行解，使目标函数值越小的可行解越接近最优解。第三步，对具体问题作出分析，对目标函数可能达到的最小值（即C的最小值）作适当估计，然后在此估计值的基础上由大到小改变C的值进行试算，使可行解越来越接近最优解。对于目标函数值离散的情况，不难找到最优解。例：装配线平衡模型。一条装配线含有一系列的工作站，在最终产品的加工过程中每个工作站执行一种或几种特定的任务。装配线周期是指所有工作站完成分配给它们各自的任务所化费时间中的最大值。平衡装配线的目标是为每个工作站分配加工任务，尽可能使每个工作站执行相同数量的任务，其最终标准是装配线周期最短。不适当的平衡装配线将会产生瓶颈——有较少任务的工作站将被迫等待其前面分配了较多任务的工作站。问题会因为众多任务间存在优先关系而变得更复杂，任务的分配必须服从这种优先关系。这个模型的目标是最小化装配线周期。有2类约束：①要保证每件任务只能也必须分配至一个工作站来加工；(A)(B)(C)(F)(G)(K)(J)(I)(H)(E)(D)②要保证满足任务间的所有优先关系。例有11件任务（A—K）分配到4个工作站（1—4），任务的优先次序如下图。每件任务所花费的时间如下表。任务ABCDEFGHIJK时间4511950151212121289解：用变量ikx表示任务),,,(KBAii分配给工作站)4,3,2,1(kk的情况，1ikx表示分配，0ikx表示不分配，it表示完成各项任务所需时间，则目标函数为11141maxminiikikxt约束条件（1）：每项任务只能且必须分配至一个工作站来做，可以表示为：11,,2,1,141ixkik；约束条件（2）：各项任务间如果有优先关系，则排在前面的任务i对应的工作站（序号）应当小于（或等于）排在后面的任务j所对应的工作站（序号），即对所有有顺序的任务ji：0)(41kikjkkxkx；约束条件（3）：10或ikx。这是一个非线性规划（目标函数非线性），但可以化为线性规划，增加一个变量，再增加四个约束条件：4,3,2,1,111kZxtiiki，目标函数变为Zmin。LINGO程序为：model:!装配线平衡模型;sets:!任务集合，有一个完成时间属性t;task/ABCDEFGHIJK/:t;!任务之间的优先关系集合（A必须完成才能开始B，等等）;pred(task,task)/A,BB,CC,FC,GF,JG,JJ,KD,EE,HE,IH,JI,J/;!工作站集合;station/1..4/;tsx(task,station):x;!x是派生集合txs的一个属性。如果x(i，k）＝1，则表示第i个任务指派给第k个工作站完成;endsetsdata:!任务ABCDEFGHIJK的完成时间估计如下;T=4511950151212121289;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计算的部分结果为Globaloptimalsolutionfoundatiteration:1255Objectivevalue:50.00000VariableValueReducedCostCYCTIME50.000000.000000X(A,1)1.0000000.000000X(A,2)0.0000000.000000X(A,3)0.00000045.00000X(A,4)0.0000000.000000X(B,1)0.0000000.000000X(B,2)0.0000000.000000X(B,3)1.00000011.00000X(B,4)0.0000000.000000X(C,1)0.0000000.000000X(C,2)0.0000000.000000X(C,3)0.0000009.000000X(C,4)1.0000000.000000X(D,1)0.0000000.000000X(D,2)1.0000000.000000X(D,3)0.00000050.00000X(D,4)0.0000000.000000X(E,1)0.0000000.000000X(E,2)0.0000000.000000X(E,3)1.00000015.00000X(E,4)0.0000000.000000X(F,1)0.0000000.000000X(F,2)0.0000000.000000X(F,3)0.00000012.00000X(F,4)1.0000000.000000X(G,1)0.0000000.000000X(G,2)0.0000000.000000X(G,3)0.00000012.00000X(G,4)1.0000000.000000X(H,1)0.0000000.000000X(H,2)0.0000000.000000X(H,3)1.00000012.00000X(H,4)0.0000000.000000X(I,1)0.0000000.000000X(I,2)0.0000000.000000X(I,3)1.00000012.00000X(I,4)0.0000000.000000X(J,1)0.0000000.000000X(J,2)0.0000000.000000X(J,3)0.0000008.000000X(J,4)1.0000000.000000X(K,1)0.0000000.000000X(K,2)0.0000000.000000X(K,3)0.0000009.000000X(K,4)1.0000000.000000例：工件的安装与排序问题。某设备由24个工件组成，安装时需要按工艺要求重新排序。I．设备的24个工件均匀分布在等分成六个扇形区域的一圆盘的边缘上，放在每个扇形区域的4个工件总重量与相邻区域的4个工件总重量之差不允许超过一定值。II．工件的排序不仅要对重量差有一定的要求，还要满足体积的要求，即两相邻工件的体积差应尽量大，使得相邻工件体积差不小于一定值。问题1：按重量排序算法；问题2：按重量和体积排序算法；请按下表中的工件数据（重量单位：g，体积单位：cm3）进行实时计算。表工件的重量和体积数据序号12345678910重量348352347349347.5347330329329327.5体积101.5102105105.51061049498100.598.5序号11121314151617181920重量329331.5348.5347346.5348347.5348333330体积9899104.5105107.5104.5104104.59797序号21222324重量332.5331.5331.5332体积999896.594.5解：对问题1和2分别求解。（1）对问题1，仅考虑重量进行排序。用24,,2,1i表示24个工件，iW表示各工件的重量，6,,2,1j表示圆盘上的6个扇区，jD表示各扇区上4个工件的总重量，ijX是0-1型决策变量，表示工件i是否放在扇区j上，1ijX表示放，0ijX表示不放。每个工件必须且只能放到一个位置上，每个位置放一个且仅放一个工件，每个扇区放4个工件，重量之和为jD。目标函数是：相邻扇区上的j