多目标规划模型

发表于 阅读次数： 本文字数： 3.2k 阅读时长 ≈ 11 分钟

在许多实际问题当中，衡量一个方案的好坏标准可能不只一个。比如生产某个东西的时候想要“物美价廉”——既要质量好，又要成本低。这一类问题统称为多目标最优化问题或者多目标规划问题。

标准形式

多目标规划问题一般可以写成如下形式：

其中, $x=\left(x_1, x_2, \ldots, x_m\right)^T \in R^m, p \geq 2$

例题1 生产计划问题

下面以一道例题来展示常见的多目标规划模型

某厂生产三种布料$A_1,A_2,A_3$，改厂两班生产，每周生产时间为$80h$，能耗上限$160t$标准煤。其他数据如下表：

布料 生产速度(m/h) 利润(元/m) 每周最大销售量(m) 能耗(t/km)
$A_1$ 400 0.15 40000 1.2
$A_2$ 510 0.13 51000 1.3
$A_3$ 360 0.20 36000 1.4

问每周生产三种布料各多少米，才能使得该厂的利润最高，而能耗最少？

设该厂每周生产三种布料分别$x_1,x_2,x_3$小时。总利润为$y_1=f_1(x)$（元），总能耗为$y_2=f_2(x)$（吨标准煤），其中$x=(x_1,x_2,x_3)^T$，则上述问题的数学模型为：

其中

可以发现，多目标规划问题与以前所讲的规划问题的主要区别在于：目标函数不止一个，而是$p$个。$(p\ge2)$

多目标问题的解法

多目标问题的解法大致可以分为两类：直接解法和间接解法。其中常用的多为间接解法：根据问题的实际背景和特征，设法讲多目标优化问题转化为单目标优化问题，从而得到满意的解法。

间接解法有：主要目标法，分层序列法，线性加权求和法。

假设我们现在的问题数学模型形如

下面简述三种解法。

主要目标法

不妨设$f_1(x)$为主要目标。那么我们为$f_2(x)$设定一个阈值$\theta$，将其转化为一个约束$f_2(x)\le \theta$。

这里的阈值$\theta$需要自己主观确定，确定的合理一点。

注：论文写作时，使用主要目标法之前，应先将原数学模型写出来。

分层序列法

假设$y_1$比$y_2$重要（给目标函数的重要性排个序），那么先不管$y_2$，解第一个模型：

假设解出了最优解：$x=x^\star,y_1=f_1(x^\star)$

接着我们需要在“不牺牲$y_1$的情况下最小化$y_2$”，即解第二个模型：

但是分析发现，条件$f_1(x)\le f_1(x^\star)$是很难满足的。如果第一个模型只有唯一解，那么对于第二个模型要满足$f_1(x)\le f_1(x^\star)$，也只有唯一解（即$x=x^\star$）。

在实际建模中，为了确保$y_2$有一定的“生存空间”，往往将第二个模型的限制条件$f_1(x)\le f_1(x^\star)$增加一个裕度$\eta$，适当的放松对于$y_1$优化的力度：

线性加权求和法

取权重$w_1,w_2\in(0,1)$，且$w_1+w_2=1$，将原模型转化为

$w_1,w_2$​的取值情况要讨论，需要讨论取不同权重对于结果的影响。

例题

国赛2005B《DVD在线租赁》T2T3

问题重述

DVD租赁网站的会员可以租赁DVD。每个会员每个月可以提交至多2次订单，订单包含了一个基于该会员对DVD偏爱程度排序的DVD列表（长度最大为10），每次租赁可以获得3张DVD。会员看完3张DVD之后需要将3张DVD寄回才可以继续下次租赁。

T2：表2列出了网站手上的100中DVD及其现有张数、当前需要处理的1000位会员的订单。对这些DVD进行分配，使会员获得最大的满意度。

T3：继续考虑表2，并假设表2中DVD现有的数量全部为0。作为网站经营管理人员，决定每种DVD的购买量，以及如何对这些DVD进行分配，才能使得一个月内95%的会员得到他想看的DVD，并且满意度最大？

表2节选

DVD编号 D001 D002 D003 …
DVD现有数量 10 40 15 …
会员C001 6(表示第6想要) 0(表示不想要) 0 …
会员C002 0 0 0 …
会员C003 0 0 3(表示第3想要) …
会员编号… … … … …

模型假设

  1. 假设按照公历月份进行租赁业务，即会员的所有租赁必须在当月内完成DVD的租与还。
  2. 假设网站对会员进行一次租赁业务时，只能向其提供3张该会员已经预定的DVD，否则不进行租赁。（这个可以减少计算量）

问题二模型建立与求解

我们设会员得到了其第$i$想要的DVD所产生的满意度为$11-i$，对得到不想要的DVD的满意度为$0$，依此将表2的订单矩阵转化为满意度矩阵$C$，其中$c_{ij}$表示第$i$位会员对第$j$中DVD的满意度。显然每位会员最大满意度为$10+9+8=27$​。依照假设2，只有该会员的满意度达到了27，才会给这位会员寄出DVD，对总满意度产生贡献。

我们定义$x_{ij}$

对于每种DVD，分配的总量不能超过现有的数量$n_j$，故有

只给下订单的DVD进行分配，即只有满意度指数$c_{ij}\not=0$的时候才会将一张$j$种DVD分配给会员$i$，故有

相当于“若$c{ij}=0$，则$x{ij}=0$”。这用了一个很巧妙的方式。

根据假设2，每个会员要么得到3张其预定的DVD，要么不得。故有

在上述约束的前提下，我们需要最大化总体满意度指数和

显然每位会员最大的满意度指数为$27$，1000位会员的最大满意度指数和为$1000\times 27=27000$​，依此进行归一化

由此可得问题二的0-1整数线性规划模型如下：

其中$zi$是一个人工变量，用于解决限制$\sum{j=1}^{100}x_{ij}=3或0$。

Lingo代码

需要先设置xls文件的区域名称$^{[1]}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
MODEL:
SETS:
A /1..1000/:z;  
B /1..100/:dvd; 
link(A,B):ordC,C,x;      
ENDSETS

DATA:
ordC = @OLE("...\2005Bdata.xls", 'ordC');
dvd = @OLE("...\2005Bdata.xls", 'dvd');
ENDDATA

CALC:
@for(A(i):
    @for(B(j):
        C(i,j)=@if(ordC(i,j) #EQ# 0,0,11-ordC(i,j));
    )
);
ENDCALC

max=@sum(link(i,j):C(i,j)*x(i,j))/27000;
@for(A(i):@sum(B(j):x(i,j))=3*z(i));
@for(B(j):@sum(A(i):x(i,j))<=dvd(j));
@for(link(i,j):x(i,j)<=C(i,j));
@for(link(i,j):@bin(x(i,j)));
@for(A(i):@bin(z(i)));
END

解得总体最大满意度为$91.56\%$，只有6个人没有成功租赁。

问题三模型建立与求解

问题三大体上和问题二接近，但是由于同时要最小化dvd的购买量（减少成本），允许在当前某些会员无法满足租赁要求的时候，让其等待，利用部分会员归还的dvd对其进行租赁。

根据问题一（略），一个月中每张有$0.6$的概率被租赁两次，$0.4$的概率被租赁一次。即在二次租赁的情况下，每购买一张DVD当于发挥了$0.6\times 2+0.4=1.6$张DVD的作用。

由此我们在问题二的模型的基础上，进一步考虑DVD两次租赁的情况，满足$95\%$的会员的DVD需求，同时进一步追求DVD总购买量最小，建立双目标线性规划模型。

对于每种DVD，分配的总量不超过购买量的1.6倍

$95\%$的会员可以看到他想看的3张DVD，DVD总共至少要$1000\times3\times95\%=2850$张

希望购买的DVD总数量尽量少

由此可得问题三的双目标线性规划模型如下：

我们使用主要目标法，我们引入总体最小满意度$\theta\in[0,1]$，将关于满意度的目标转化为约束：

可以稍微对“为什么选取最小化DVD购买量为主要目标”作出一些合理的解释，比如“商家主要追求利润最大化，会员满意度在一定要求（比如90%）之上就差不多了”。

所以这里的$\theta$可以自己主观调整。我们设$\theta=0.95$。在实际计算中，如果要求$y_i$为整数，可能难以求得可行解，因而我们取消了对$y_i$的整数约束，在计算之后再对其进行取整。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
MODEL:
SETS:
A /1..1000/:z;  
B /1..100/:y; 
link(A,B):ordC,C,x;      
ENDSETS

DATA:
ordC = @OLE("...\2005Bdata.xls", 'ordC');
theta=0.95;
@OLE("...\T3_Output.xlsx",'y')=y;
ENDDATA

CALC:
@for(A(i):
    @for(B(j):
        C(i,j)=@if(ordC(i,j) #EQ# 0,0,11-ordC(i,j));
    )
);
ENDCALC

min=@sum(B(j):y(j));
@sum(link(i,j):C(i,j)*x(i,j))/27000>=theta;
@sum(link(i,j):x(i,j))>=1000*3*0.95;
@for(B(j):@sum(A(i):x(i,j))<=1.6*y(j));
@for(A(i):@sum(B(j):x(i,j))=3*z(i));
@for(link(i,j):x(i,j)<=C(i,j));
@for(link(i,j):@bin(x(i,j)));
@for(A(i):@bin(z(i)));
!@for(B(j):@gin(y(j)));
END

当$\theta=0.95$时，我们解得DVD总最小购买量$\min\ z=1781.250$，各种DVD需要的购买量$y_j$如下表（节选）

DVD编号 总计 1 2 3 4 5 …
$y_j$ 1781.250 13.125 20 15 23.125 12.5 …
round($y_j$) 1782 13 20 15 23 13 …

这里我和老师求出来的不太一样（1823），可能是我写的代码哪里出错了，还望斧正！

所有数据和代码打包放这里了。

参考文献

$[1]$ LINGO与EXCEL之间的数据传递 - GShang - 博客园 (cnblogs.com)