5.4 任务优化分配模型 5.4.1 模型的建立
在给出模型之前，我们对定义一些基本符号： n1表示任务数，n2表示会员数；
d?i,j?为会员j和任务i之间的距离；
?i为任务i完成的可能性指标； ?为阈值；
Vj表示会员j愿意接受任务点的集合；
ej表示会员j所能接受任务限额；
?1,i?Vj，当i?Vj时，任务i由会员j完成； xij??0,i?Vj?Qj表示会员j的信誉值；
tj表示会员j开始预定任务的时间；
C表示任务完成所支付总金额限制；
（1）目标函数的确定
在总费用一定的限制情况下，一个合理的定价方案，最关键的是要保证平台所给出的任务要尽量多地完成。因此，我们以任务的完成量最大为目标函数，即：
max??xi?1j?1n1n2ij.
（2）约束条件的确定
约束条件一：同一个会员的预定任务数量有限额限制，设会员j接受任务点的集合可表示为Aj?ixij?1，即：
i?Aj???xij?e?j.
其中，e?j为重新定义的用户限额。考虑到每个会员完成任务的能力有限，我们定义每个会员的限额最大不超过5，即：
?ej,ej?5. e?j??5,e?5j?约束条件二：会员只接受的任务满足自己期望的任务。考虑到附件1中每个区域的用户对任务的期望值不同，我们对上述优化模型中的阈值?按区域重新设定。根据附件一中的经纬度，我们按城市将用户分成佛山、广州、东莞和深圳四块区域，并将期望值设成?1，?2，?3和?4.
考虑不同地区用户的不同期望阈值，定义特征函数
?1,j?Tzyjz??，z?1,2,3,4，
?0,j?Tz其中，T1，T2，T3和T4分别为佛山、广州、东莞和深圳四块区域的用户集合。
10
会员j愿意接受任务点的集合为
?QjPi???Vj??i1???maxQc?di,j??j????????z,d?i,j??r,yiz?1?， ?????即：
Aj?Vj.
约束条件三：同一个任务最多只能被一位会员完成，即：
?xj?1n2ij?1，d?i,j??r.
约束条件四：开始预约任务时间早的会员优先挑选任务，如果任务i是会员j1和j2都满意的，那么开始时间较早的会员优先挑选。即：
xij1tj1?xij2tj2，?i?Vj1?Vj2.
约束条件五：平台支付给用户的总费用有一定限制，即：
?P??C.
ii?1n1综上所述，建立任务分配优化模型如下：
max??xi?1j?1n1n2ij
?Pi??P0?0.5Ri??Si?Qi?Ti???xij?e?j?i?Aj?n2??xij?1,d?i,j??r?j?1? s.t.?xij1tj1?xij2tj2,?i?Vj1?Vj2??Aj?Vj?n1??Pi??C?i?1?i?1,2,,n,j?1,2,,n?1?2????5.4.2 基于最大流的启发式算法[1]
考虑到上述优化模型的约束条件比较复杂，一般的线性规划方法无法求解。为了求
解最大任务完成数量，我们考虑到在每一个任务发布后，所有对该任务感兴趣的会员都可以对该任务发起请求。在这样的优化前提之下，我们可以将问题转化为一个网络流的最大流问题去求解。我们设计了一种基于最大流的启发式算法对模型进行求解，具体步骤如下：
Step1：计算(?1,?2,?3)的大致范围，设定初始温度T0、点每次移动一步的长度、迭代深度；
Step2：向(?1,?2,?3)随机投点，投点时删除会使总价格高出额定值的点；
11
Step3：对集合中每个点向8个方向移动，并调用算法二计算其在新的位置的最大任务接单数，算法二步骤如下：
-Step3.1：建图，为任务和会员添加相对应的点，并添加源点和汇点；
-Step3.2：每个会员和汇点之间连一条边，边的流量是这个用户的任务分配限额，每个任务与源点之间连一条边，边的流量是1；
-Step3.3： 每个会员i和任务j之间两两配对，计算会员i对任务j的满意度。如果会员i对任务j感到满意，那么就在会员i和任务j之间连一条边； -Step3.4：调用Dinic算法，计算源点到汇点之间的最大流；
如果新的结果更好，则将新的节点添加进正在计算的点集合中，如果没有比原来的结果更好，则以概率P接受该结果；
Step4：当迭代深度超过一定的深度时，退出算法，输出最优解。 (算法介绍见附录一) 5.4.3 求解结果
对上述算法，利用MATLAB编程（具体代码见附录二），得到现任务定价及完成情况表（部分），具体详见附件一。
表5-3 原方案与现方案任务定价及完成情况表 任务号码 A0022 A0012 A0468 A0018 A0006 A0450 A0693 A0264 A0835 A0830 A0468 A0734 原定价 65 65.5 80 66 75 85 65.5 67 85 85 80 75 原完成情况 1 0 0 0 0 0 0 0 1 1 0 0 现定价 65 70.5 86 71 77.5 87 69.5 72 82 79 90 90 现完成情况 1 1 1 1 1 1 1 1 1 1 0 0 表5-4 原方案与现方案总定价和完成率情况表 原方案 现方案 5.4.4 结果分析
总定价 57641.5 58732.6 任务平均定价 68.87 70.17 完成率 62.1% 86.6% 考虑到深圳等地区的任务定价有一定的提高，使得现方案的总费用比原方案大约增加了1.9%，但现方案的任务完成率比原方案的任务完成率提高了24.5%，说明现方案比原方案大大提高了系统整体效益。
12
在?56000,76000?范围内随机改变初始设定的价格总和上限D，求得在不同价格上限下任务完成数量的最大值，如下图所示：
10009008007006005004003002005.6任务完成数量5.866.26.46.66.8价格总和上限77.27.47.6x 104
图5-1 任务最大完成量与价格总和上限关系图
由上图可知，任务最大完成量与价格总和上限总体成正相关，价格上限较低，在56000~60000范围内，任务最大完成数量变化不大，在330件上下波动；价格在60000~71500范围内，任务最大完成数量随价格总和上限的提高而增加；价格上限较低，在71500~75000范围内，任务最大完成数量变化不大，在950件上下波动。
6 问题三的模型建立与求解
6.1 问题三的分析
APP拍照任务定价问题是一个任务发布者（APP平台）和任务完成者（会员）间双向决策问题。任务发布者希望在任务成本较小的情况下，任务的完成率尽可能的大，完成任务的时间尽可能的短；而作为任务完成者追求任务完成后的收益尽可能的大。分析问题一与问题二中任务的定价规律和任务完成情况，发现会存在下面的一些问题： （1）有些任务由于定价的不合理，或者是由于任务难度等其他原因不能达到所有会员的满意程度，导致该任务未被完成，影响到任务的完成率。
（2）由于会员选择任务时不合理性，例如一个信誉高的会员选择多个项目，没有考虑到项目的分散程度，在完成任务过程中增加了成本而减少了收益。而对APP平台来讲，会导致任务完成的时间延长，甚至无法完成影响到任务的完成率。
为了解决这些问题，我们借助一般商品的打包销售原理，对问题一与问题二中任务的定价规律和模型进行优化，建立打包定价模型。 6.2 打包模型的建立
6.2.1 打包原则
（1）距离相近的任务（集中度较高的任务）应考虑打包发布；
（2）未完成的任务应尽量与自己距离相近的已完成的任务打包发布； （3）距离相近的价格差比较大的任务应尽量考虑打包发布.
打包原则（1）可以有效提高任务的吸引力，节省会员完成任务的成本，缩短任务
13
完成的时间。某任务未完成的主要原因是由于该任务的吸引力达不到用户对该任务的满意度，若将直接将若干距离较近且未完成的任务打包，显然不能提高任务的吸引力，有效提高完成率。打包原则（2）、（3）能够提升那些吸引力较低或者吸引力达不到用户对该任务的满意度的任务的吸引力，提升任务的完成率。 6.2.2 二次打包模型
根据上述三条打包原则，建立二次打包模型如下：
第一次打包：根据原则（1），集中度较高的已完成任务进行打包。设T是所有任务集合，T1是已被完成任务的集合，d?i,j?表示两点之间的直线距离，当T1中两点间的距离d?i,j??r时，两任务打包发布。
第二次打包：根据原则（1），（2），（3），针对未完成的任务进行分配。对于未完成的任务，我们考虑将它们分配到第一次打包完成后的任务包内，设第一次打包时将任务集T1划分成?S1,S2,,Sl?，定义任务点i到集合Sj的距离为
d?i,Sj??mind?i,k?,k?Sj.
定义任务点i与集合Sj中任务的价格差为
??i,Sj??Pi??k?Sj?P?kSj.
为简化模型，我们采用平均价格定义任务集合S?j??i??Sj的满意度
?S??jk?S?j?P?kSj?1.
综合上述三条原则，当任务点i满足如下约束时，我们认为可以将未完成的任务i打包分配到集合Sj，
?d?i,Sj??mind?i,k??d0,k?Sj,i?T/T1??Pk???k?S?j. ??0??S?j?Sj?1???Sj??N?这里，我们取N?5.
若上述两限制都满足时，将任务点i合并到价格差最大的集合，即：
max??i,Sj??Pi??k?Sj?P?kSj.
14
全国大学生数学建模竞赛2017年B题“拍照赚钱”的任务定价及优秀论文精选
