[2018年必威体育精装版整理]01分数规划.docVIP

pku 3621 sightseeing cows 解题报告 题意:求存在一个环路,所有的点权之和/所以的边权之和 最大是多少？ 算法:此题是对01分数规划的应用,那么首先明白01分数规划的思想. 01分数规划的思想的描述如下：令c=(c1,c2,…,cn)和d=(d1,d2,…,dn)为n维整数向量，那么一个0-1分数规划问题用公式描述如下:FP: 最小化(c1x1+…cnxn)/(d1x1…dnxn)=cx/dx xi∈{0,1}这里x表示列向量(x1,x2,…,xn)T .0-1值向量的子集Ω称作可行域，而x则是Ω的一个元素，我们称x为可行解。即可以简化为y=c/d.那么再演变一下：y-c/d=0.我们目标是求y.那么我们可以假设函数f(y)=y-c/d. 重要结论: 对于分数规划问题，有许多算法都能利用下面的线性目标函数解决问题。Q(L): 最小化 cx-Ldx xi∈{0,1} 记z(L)为Q(L)的最值。令x*为分数规划的最优解，并且令L*=(cx*)/(dx*)(注：分数规划的最值)。那么下面就容易知道了：z(L) 0 当且仅当 LL*z(L) = 0 当且仅当 L=L*z(L) 0 当且仅当 LL*此外，Q(L*)的最优解也能使分数规划最优化。因此，解决分数规划问题在本质上等同于寻找L=L*使z(L)=0 因此,求解f(y)=0,为其函数的最优解，即可以利用二分的思想逐步推演y,从而求得最优解. 回到题目,我们知道是求解segma(f[V])/segma(E[v])的最大值,同时每个结点对应一个点权,每条边对应一个边权,那么我们就可以联想到应用01分数规划的思想来求解.而01分数规划是与二分紧紧联系在一起的.那么怎么应用二分求解呢？ 我们首先想想当仅仅有2个结点环路的时候,问题就演变为f(y)=y-c/d,而y是通过二分逐步推算出来的,那么我们的任务就变为在一定的精度范围内测试求解其最优解.当y-c/d0时,y减少; y-c/d0时,y增大.在2个结点之间,那么我们就可用重新将图的权变为y-c/d,这样问题就回到2个结点的环路是否存在负权回路,存在说明y-c/d0,不存在y-c/d0.从而进一步推算最优解y。 对于0-1分数规划的Dinkelbach算法的分析 武钢三中 吴豪[译]摘要:0-1分数规划问题是指求出解集{xi|xi=0或1}使目标(c1x1+c2x2++cnxn) /(d1x1+d2x2+…+dnxn)=cx/dx达到最大。对于分数规划问题，Dinkelbach提出了一个算法，它通过解决一个子问题Q(L)来得到原文题的解。这里Q是一个线性的最小化目标函数cx-Ldx，且满足x等于0或1。在本文中，我们证明了Dinkelbach算法在最坏情况下可以在O(log(nM))的时间内解决子问题，这里M=max{max|ci|,max|di|,1}。1．0-1分数规划问题要使两个线性函数的比值最大或最小的问题，我们称作分数规划问题或双曲线问题。分数规划问题在许多领域都可以找到[22]。它在经济学中的应用有些常见的例子，如寻找最优收入比率或者在效益约束下的最佳物资调配问题。另外，系统效率也常常用比率来衡量，如收益/时间、利润/风险和消费/时间。有大量的文章对这类问题做了分析[3，5，12，20，24]。有几类分数规划问题已被广泛地研究。如0-1分数规划问题[1],它包含最优比率生成树问题[4]，最优比率环问题[8，6，19]，分数背包问题[15]，以及分数剪枝问题[10]。在本文中，我们研究0-1分数规划问题，它的描述如下：令c=(c1,c2,…,cn)和d=(d1,d2,…,dn)为n维整数向量，那么一个0-1分数规划问题用公式描述如下:FP: 最小化(c1x1+…cnxn)/(d1x1…dnxn)=cx/dx xi∈{0,1}这里x表示列向量(x1,x2,…,xn)T .0-1值向量的子集Ω称作可行域，而x则是Ω的一个元素，我们称x为可行解。贯穿全文，我们假定对于任意可行解x,dx都是正数。这里我们记C=max{max|ci|,1},D=max{max|di|,1}。那么，显然问题的最优解在区间[-nC,nC]内。对于分数规划问题，有许多算法都能利用下面的线性目标函数解决问题。Q(L): 最小化 cx-Ldxxi∈{0,1}记z(L)为Q(L)的最值。令x*为分数规划的最优解，并且令L*=(cx*)/(dx*)(注：分数规划的最值)。那么下面就容易知道了：z(L) 0当且仅当LL*z(L) = 0当且仅当L=L*z(L) 0当