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

《LINGO在多目标规划和最大最小化模型中的应用》由会员分享，可在线阅读，更多相关《LINGO在多目标规划和最大最小化模型中的应用（15页珍藏版）》请在装配图网上搜索。

1、LINGO 在多目标规划和最大最小化模型中的应用 在许多实际问题中，决策者所期望的目标往往不止一个，如电力网络管理部 门在制定发电计划时即希望安全系数要大，也希望发电成本要小，这一类问题称 为多目标最优化问题或多目标规划问题。 一、多目标规划的常用解法 多目标规划的解法通常是根据问题的实际背景和特征，设法将多目标规划转 化为单目标规划，从而获得满意解，常用的解法有： 1．主要目标法 确定一个主要目标，把次要目标作为约束条件并设定适当的界限值。 2．线性加权求和法 对每个目标按其重要程度赋适当权重« > 0，且工®二1,然后把工® f (x) i i i i ii 作为新的目标函

2、数(其中f (x), i二1,2,…,p是原来的p个目标)。 i 3．指数加权乘积法 设f (x),i二1,2,…,p是原来的p个目标，令 i Z [ f (x)]ai i i=1 其中a为指数权重，把Z作为新的目标函数。 i 4．理想点法 先分别求出p个单目标规划的最优解f *，令 i h(x) = & (f (x) - f*)2 然后把它作为新的目标函数。 5．分层序列法 将所有p个目标按其重要程度排序，先求出第一个最重要的目标的最优解， 然后在保证前一个目标最优解的前提条件下依次求下一个目标的最优解，一直求 到最后一个目标为止。 这些方法各有其优点和适用

3、的场合，但并非总是有效，有些方法存在一些不 足之处。例如，线性加权求和法确定权重系数时有一定主观性，权重系数取值不 同，结果也就不一样。线性加权求和法、指数加权乘积法和理想点法通常只能用 于两个目标的单位(量纲)相同的情况，如果两个目标是不同的物理量，它们的 量纲不相同，数量级相差很大，则将它们相加或比较是不合适的。 二、最大最小化模型 在一些实际问题中，决策者所期望的目标是使若干目标函数中最大的一个达 到最小(或多个目标函数中最小的一个达到最大)。例如，城市规划中需确定急 救中心的位置，希望该中心到服务区域内所有居民点的距离中的最大值达到最 小，称为最大最小化模型，这种确定目标函数的准则

4、称为最大最小化原则，在控 制论，逼近论和决策论中也有使用。 最大最小化模型的目标函数可写成 minmax{f (X), f (X),•••,/ (X)} X 1 2 p 或 maxmin{f (X),f (X)，…,f (X)} X 1 2 p 式中X (x ,x，…,x )t是决策变量。模型的约束条件可以包含线性、非线性的 1 2 n 等式和不等式约束。这一模型的求解可视具体情况采用适当的方法。 三、用LINGO求解多目标规划和最大最小化模型 1．解多目标规划 用 LINGO 求解多目标规划的基本方法是先确定一个目标函数，求出它的最 优解，然后把此最优值作为约束条件，求

5、其他目标函数的最优解。如果将所有目 标函数都改成约束条件，则此时的优化问题退化为一个含等式和不等式的方程 组。 LINGO 能够求解像这样没有目标函数只有约束条件的混合组的可行解。有 些组合优化问题和网络优化问题，因为变量多，需要很长运算时间才能算出结果， 如果设定一个期望的目标值，把目标函数改成约束条件，则几分钟就能得到一个 可行解，多试几个目标值，很快就能找到最优解。对于多目标规划，同样可以把 多个目标中的一部分乃至全部改成约束条件，取适当的限制值，然后用 LINGO 求解，从中找出理想的最优解，这样处理的最大优势是求解速度快，节省时间。 2．解最大最小化问题 第一步，先把原来较复杂

6、的目标函数式改写为一个简单的目标函数 m i nC 以及p个约束条件： f (X) < C, f (X) < C, , f (X) < C 1 2 p 其他原有的约束条件不变，改写后仍然是一个规划，只是增加了 p个约束条件， 目标函数的形式较为简单。如果能用LINGO求出它的解，则问题已经解决，如 果求解困难，可转入下一步。 第二步，取消目标函数，保留上一步由目标函数改成的 p 个约束条件和所有 原来的约束条件，预设C值为某个常数，此时原规划模型不再是规划，它仅仅包 含等式和不等式，没有目标函数，是许多约束条件的组合，可以称它为“混合组”。 求该混合组的解，其实质是求满足所有约束条

7、件并且使目标函数等于给定值的一 组决策变量的值，求出来的结果是可行解，它未必是最优解。在存在可行解的前 提下，使目标函数值小的可行解优于使目标函数值大的可行解，使目标函数值越 小的可行解越接近最优解。 第三步，对具体问题作出分析，对目标函数可能达到的最小值(即 C 的最 小值)作适当估计，然后在此估计值的基础上由大到小改变 C 的值进行试算， 使可行解越来越接近最优解。对于目标函数值离散的情况，不难找到最优解。 例：装配线平衡模型。一条装配线含有一系列的工作站，在最终产品的加工 过程中每个工作站执行一种或几种特定的任务。装配线周期是指所有工作站完成 分配给它们各自的任务所化费时间中的最大值

8、。平衡装配线的目标是为每个工作 站分配加工任务，尽可能使每个工作站执行相同数量的任务，其最终标准是装配 线周期最短。不适当的平衡装配线将会产生瓶颈——有较少任务的工作站将被迫 等待其前面分配了较多任务的工作站。 问题会因为众多任务间存在优先关系而变得更复杂，任务的分配必须服从这 种优先关系。 这个模型的目标是最小化装配线周期。有2类约束： ① 要保证每件任务只能也必须分配至一个工作站来加工； ② 要保证满足任务间的所有优先关系。 例 有11件任务（A—K）分配到4个工作站（1—4）,任务的优先次序如下 图。每件任务所花费的时间如下表。 解：用变量x表示任务i（i二A,

9、B,…,K）分配给工作站k（k二1,2,3,4）的情况， ik x二1表示分配，x二0表示不分配，t表示完成各项任务所需时间，则目标函 ik ik i 数为 ik min max X t x 1< k <4 约束条件（1）：每项任务只能且必须分配至一个工作站来做，可以表示为： x = 1, i = 1,2,…,11 ； ik k=1 约束条件（2）：各项任务间如果有优先关系，则排在前面的任务i对应的工 作站（序号）应当小于（或等于）排在后面的任务j所对应的工作站（序号）， 即对所有有顺序的任务i < j : X （kx - kx ） > 0 ； jk ik k=1

10、约束条件（3）： x = 0或1。 ik 这是一个非线性规划（目标函数非线性），但可以化为线性规划，增加一个 变量，再增加四个约束条件：艺tx <乙k = 1,2,3,4，目标函数变为min Z。 i ik i=1 LINGO 程序为： 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 /

11、； ! 工作站集合； station/1..4/； tsx(task, station):x； ! x是派生集合txs的一个属性。如果x(i, k)=l,则表示第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)；

12、 !对于每一个存在优先关系的作业对来说，前者对应的工作站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 计算的部分结果为 Global optimal so

13、lution found at iteration: 1255 Objective value: 50.00000 Variable Value Reduced Cost CYCTIME 50.00000 0.000000 X( A, 1) 1.000000 0.000000 X( A, 2) 0.000000 0.000000 X( A, 3) 0.000000 45.00000 X( A, 4) 0.000000 0.000000 X( B, 1) 0.000000 0.000000 X( B, 2) 0.000000 0.000000 X

14、( B, 3) 1.000000 11.00000 X( B, 4) 0.000000 0.000000 X( C, 1) 0.000000 0.000000 X( C, 2) 0.000000 0.000000 X( C, 3) 0.000000 9.000000 X( C, 4) 1.000000 0.000000 X( D, 1) 0.000000 0.000000 X( D, 2) 1.000000 0.000000 X( D, 3) 0.000000 50.00000 X( D, 4) 0.000000 0.00000

15、0 X( E, 1) 0.000000 0.000000 X( E, 2) 0.000000 0.000000 X( E, 3) 1.000000 15.00000 X( E, 4) 0.000000 0.000000 X( F, 1) 0.000000 0.000000 X( F, 2) 0.000000 0.000000 X( F, 3) 0.000000 12.00000 X( F, 4) 1.000000 0.000000 X( G, 1) 0.000000 0.000000 X( G, 2

16、) 0.000000 0.000000 X( G, 3) 0.000000 12.00000 X( G, 4) 1.000000 0.000000 X( H, 1) 0.000000 0.000000 X( H, 2) 0.000000 0.000000 X( H, 3) 1.000000 12.00000 X( H, 4) 0.000000 0.000000 X( I, 1) 0.000000 0.000000 X( I, 2) 0.000000 0.000000 X( I, 3) 1.000000

17、 12.00000 X( I, 4) 0.000000 0.000000 X( J, 1) 0.000000 0.000000 X( J, 2) 0.000000 0.000000 X( J, 3) 0.000000 8.000000 X( J, 4) 1.000000 0.000000 X( K, 1) 0.000000 0.000000 X( K, 2) 0.000000 0.000000 X( K, 3) 0.000000 9.000000 X( K, 4) 1.000000 0.000000

18、 例：工件的安装与排序问题。某设备由24 个工件组成，安装时需要按工艺 要求重新排序。 I. 设备的24个工件均匀分布在等分成六个扇形区域的一圆盘的边缘上，放 在每个扇形区域的 4 个工件总重量与相邻区域的 4 个工件总重量之差不允许超过 一定值。 II. 工件的排序不仅要对重量差有一定的要求，还要满足体积的要求，即两 相邻工件的体积差应尽量大，使得相邻工件体积差不小于一定值。 问题 1：按重量排序算法； 问题 2：按重量和体积排序算法； 请按下表中的工件数据（重量单位：g,体积单位：cm3）进行实时计算。 表 工件的重量和体积数据 序 号 1 2 3 4 5 6

19、7 8 9 10 重 量 348 352 347 349 347. 5 347 330 329 329 327. 5 体积 101. 5 102 105 105. 5 106 104 94 98 100. 5 98.5 序 号 11 12 13 14 15 16 17 18 19 20 重 量 329 331. 5 348. 5 347 346. 5 348 347. 5 348 333 330 体积 98 99 104. 5 105 107. 5 104. 5

20、 104 104. 5 97 97 序 号 21 22 23 24 重 量 332. 5 331. 5 331. 5 332 体积 99 98 96.5 94.5 解：对问题1和2分别求解。 （1） 对问题1，仅考虑重量进行排序。 用i = 1,2,…,24表示24个工件，W表示各工件的重量，j = 1,2,…,6表示圆盘 i 上的6个扇区， D 表示各扇区上4个工件的总重量， X 是0-1型决策变量，表示 j ij 工件i是否放在扇区j 上, X = 1表示放，X

21、 = 0表示不放。 ij ij 每个工件必须且只能放到一个位置上，每个位置放一个且仅放一个工件，每 个扇区放4个工件，重量之和为D。目标函数是：相邻扇区上的D之差的（绝 jj 对值）最大值达到最小，建立0-1规划模型如下： min max{| D 1< k <6 k+1 -D 1} k 艺 X = 4, j = 1,2,... ,6 ij i=1 艺 X = 1, i = 1,2,…,24 ij j=1 D =1LWX ,j = 1,2,…,6,D = D j i ij 7 1 i=1 X = 0 或1 ij 模型中的D是虚拟的，D = D使得1

22、-6-1扇区构成圆盘，引入D的目的 7 7 1 7 只是使目标函数的表达式简洁。该0-1规划模型的目标函数是相邻扇区上的D j 之差（绝对值）的最大值达到最小，属于最大最小化模型。 按照前面所述把规划模型转化为混合组的步骤，去掉目标函数，增加约束条 件： I D — D l< C, j = 1,2,...,6 j +1 j 保留原来的约束条件，并令C为某个常数，原规划就转化成了一个包含150个变 量， 36个等式约束， 6个不等式约束的非线性混合组。 由于24个工件的重量数据多数为整数，部分有小数，小数的最小计数单位 为0.5 ，所以相邻扇区重量之差的基本计数单位是0.5 ，

23、即| D -D |的可能取 j +1 j 值是离散的。令C取0, 0.5，1，1.5，2，……中的具体值（C值越小越好）。 用LING O编程求解，不难求得当C=0.5时有可行解，因C=0时无可行解，故C=0.5 时的可行解就是最优解。 用第一组工件的重量数据，编写LINGO程序如下： model: sets: gj/1..24/:w; shq/1..6/:d; bl（gj,shq）:x; endsets data: w=348 352 347 349 347.5 347 330 329 329 327.5 329 331.5 348.5 347 346.5 348 347.

24、5 348 333 330 332.5 331.5 331.5 332; enddata @for(bl:@bin(x)); c=0.5; !常数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); @for(shq(j)|j#lt#6:d(j+1)-d(j)>=-c); d(1)-d(6)<=c; d(

25、1)-d(6)>=-c; end 运行结果如下： Feasible solution found at iteration: 15994 Variable 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) Value

26、 0.5000000 348.0000 352.0000 347.0000 349.0000 347.5000 347.0000 330.0000 329.0000 329.0000 327.5000 329.0000 331.5000 348.5000 347.0000 346.5000 348.0000 347.5000 348.0000 333.0000 330.0000 332.5000 331.5000 331.5000 332.0000 1357.000 1356.500 1357.000 D( D( D( 4)

27、 5) 6) 1357.500 1357.000 1357.500 X( 1, 1) 0.000000 X( 1, 2) 1.000000 X( 1, 3) 0.000000 X( 1, 4) 0.000000 X( 1, 5) 0.000000 X( 1, 6) 0.000000 X( 2, 1) 0.000000 X( 2, 2) 0.000000 X( 2, 3) 0.000000 X( 2, 4) 1.000000 X( 2, 5) 0.000000 X( 2, 6) 0.0000

28、00 X( 3, 1) 0.000000 X( 3, 2) 0.000000 X( 3, 3) 0.000000 X( 3, 4) 0.000000 X( 3, 5) 1.000000 X( 3, 6) 0.000000 X( 4, 1) 0.000000 X( 4, 2) 0.000000 X( 4, 3) 1.000000 X( 4, 4) 0.000000 X( 4, 5) 0.000000 X( 4, 6) 0.000000 X( 5, 1) 0.000000 X( 5, 2)

29、 0.000000 X( 5, 3) 1.000000 X( 5, 4) 0.000000 X( 5, 5) 0.000000 X( 5, 6) 0.000000 X( 6, 1) 0.000000 X( 6, 2) 1.000000 X( 6, 3) 0.000000 X( 6, 4) 0.000000 X( 6, 5) 0.000000 X( 6, 6) 0.000000 X( 7, 1) 0.000000 X( 7, 2) 1.000000 X( 7, 3) 0.000000 X(

30、 7, 4) 0.000000 X( 7, 5) 0.000000 X( 7, 6) 0.000000 X( 8, 1) 0.000000 X( 8, 2) 0.000000 X( 8, 3) 1.000000 X( 8, 4) 0.000000 X( 8, 5) 0.000000 X( 8, 6) 0.000000 X( 9, 1) 1.000000 X( 9, 2) 0.000000 X( 9, 3) 0.000000 X( 9, 4) 0.000000 X( 9, 5) 0.

31、000000 X( 9, 6) 0.000000 X( 10, 1) 0.000000 X( 10, 2) 0.000000 X( 10, 3) 0.000000 X( 10, 4) 1.000000 X( 10, 5) 0.000000 X( 10, 6) 0.000000 X( 11, 1) 0.000000 X( 11, 2) 0.000000 X( 11, 3) 0.000000 X( 11, 4) 0.000000 X( 11, 5) 1.000000 X( 11, 6) 0.00

32、0000 X( 12, 1) 0.000000 X( 12, 2) 1.000000 X( 12, 3) 0.000000 X( 12, 4) 0.000000 X( 12, 5) 0.000000 X( 12, 6) 0.000000 X( 13, 1) 1.000000 X( 13, 2) 0.000000 X( 13, 3) 0.000000 X( 13, 4) 0.000000 X( 13, 5) 0.000000 X( 13, 6) 0.000000 X( 14, 1) 0.000

33、000 X( 14, 2) 0.000000 X( 14, 3) 0.000000 X( 14, 4) 0.000000 X( 14, 5) 0.000000 X( 14, 6) 1.000000 X( 15, 1) 0.000000 X( 15, 2) 0.000000 X( 15, 3) 0.000000 X( 15, 4) 0.000000 X( 15, 5) 0.000000 X( 15, 6) 1.000000 X( 16, 1) 0.000000 X( 16, 2) 0.00

34、0000 X( 16, 3) 0.000000 X( 16, 4) 0.000000 X( 16, 5) 1.000000 X( 16, 6) 0.000000 X( 17, 1) 1.000000 X( 17, 2) 0.000000 X( 17, 3) 0.000000 X( 17, 4) 0.000000 X( 17, 5) 0.000000 X( 17, 6) 0.000000 X( 18, 1) 0.000000 X( 18, 2) 0.000000 X( 18, 3) 0.000

35、000 X( 18, 4) 1.000000 X( 18, 5) 0.000000 X( 18, 6) 0.000000 X( 19, 1) 0.000000 X( 19, 2) 0.000000 X( 19, 3) 0.000000 X( 19, 4) 0.000000 X( 19, 5) 1.000000 X( 19, 6) 0.000000 X( 20, 1) 0.000000 X( 20, 2) 0.000000 X( 20, 3) 0.000000 X( 20, 4) 1.0000

36、00 X( 20, 5) 0.000000 X( 20, 6) 0.000000 X( 21, 1) 0.000000 X( 21, 2) 0.000000 X( 21, 3) 0.000000 X( 21, 4) 0.000000 X( 21, 5) 0.000000 X( 21, 6) 1.000000 X( 22, 1) 0.000000 X( 22, 2) 0.000000 X( 22, 3) 0.000000 X( 22, 4) 0.000000 X( 22, 5) 0.000

37、000 X( 22, 6) 1.000000 X( 23, 1) 0.000000 X( 23, 2) 0.000000 X( 23, 3) 1.000000 X( 23, 4) 0.000000 X( 23, 5) 0.000000 X( 23, 6) 0.000000 X( 24, 1) 1.000000 X( 24, 2) 0.000000 X( 24, 3) 0.000000 X( 24, 4) 0.000000 X( 24, 5) 0.000000 X( 24, 6) 0.0000

38、00 由此求出一种放置方案（答案不唯一），见下表： 扇区 一 二 三 四 五 六 工件 9,13, 1,6 4,5 2,10 3,11 14,15 17,24 7,12 8,23 18,20 16,19 21,22 总重量 1357 1356.5 1357 1357.5 1357 1357.5 2）对问题2，既考虑重量，也考虑体积进行排序。 符号规定与问题1略有不同，j是圆盘上的位置序号，k是扇区编号，每个 扇区有4个位置， V 表示各工件体积， D 表示各扇区上4个工件的总重量， T 表 i k j 示第j个位置上所放工件

39、的体积，X是0-1型决策变量，表示工件i是否放在位 ij 置j 上, X二1表示放，X二0表示不放。 ij ij 每个工件必须且只能放到一个位置上，每个位置放一个且仅放一个工件，每 个扇区放4个工件，重量之和为D，目标函数有两个：①相邻扇区上的D之差 kk 的最大值达到最小；②相邻位置上工件的体积之差的最小值达到最大。 建立双目标规划模型如下： 目标函数： minmax{lD — D I,k 二 1,2,D — D 1} J k+1 k 6 1 maxmin{lT — T I, j 二 l,2,・・・,23,l T — T I} j +1 j 24 1 艺 X = 1

40、, j = 1,2,…24 ij i=1 艺 X = 1, i = 1,2,…24 ij j=1 约束条件： < D =另艺WX ,k = 1,2,…,6 k i ij j=4k—3 i=1 T =艺 V X , j = 1,2,…24 j j ij i=1 X = 0 或1 ij 把问题1的计算结果作为约束条件，即增加约束条件：D = 1357,i = 1,2,^,5。 i 然后考虑第二个目标：相邻位置上工件的体积之差（绝对值）的最小值达到最大， 把这个目标也改成约束条件，即再增加约束条件： I T -T l> H, j = 1,2,...,23, I T -T l> H j+1 j 24 1 H是希望达到的目标函数的值，此时双目标规划就变成了没有目标函数，仅 含有等式和不等式的混合组，这样处理的最大优点是计算速度快。 编写LINGO程序，当H =4.5时，找到可行解。 注意：解答不唯一，且不能肯定这一定是最优解时，可以在LINGO求解的基 础上做一些手工调整，得到更好的方案。