时间戳

首页 > 技术文章 > 01分数规划讲解

01分数规划讲解

BLADEVIL 2014-01-08 17:05 原文

　　分数规划是将某个求解最优性问题转化为判定性问题，一般的形式为f(x)=a(x)/b=(x)，求解f(x)的最优值，其中a,b,x为连续实数函数。

　　我们这里讨论f的最小值，即设w=min(f(x)=a(x)/b(x))，那么w=f(xmin)=a(xmin)/b(xmin)=>a(xmin)-w*b(xmin)=0

　　那么我们设一个新的函数g(w)，g(w)=min(a(x)-w*b(x))，首先我们可以得到这个函数的一些性质。

性质：

　　单减性：即对于任意w1<w2都有g(w1)>g(w2)，证明比较容易，假设x1为w1的最优解，x2为w2的最优解，那么有

　　　　g(w1)=a(x1)-w1*b(x1)>a(x1)-w2*b(x1)>=a(x2)-w2*b(x2)=g(w2)

　　唯一性：当且仅当g(w)=0时，w为原问题的最优解。这一性质又被称作Dinkelbach定理。首先我们要证明这一性质，需要证明g(w)=0是w为最优解的充分必要条件。

　　　　首先证明必要性，即对于w为最优解时，g(w)=0。设最优解为wmin，那么我们有

　　　　wmin=a(xmin)/b(xmin)<=a(x)/b(x)，也就是a(x)-wmin*b(x)>=0，因为g(w)是取最小值，所以g(wmin)=0

　　　　然后证明充分性，即对于g(w)=0时，w为原文题的最优解。

　　　　采用反证法，假设w’比w更优，那么w’=a(x')/b(x')<w，那么a(x')-w*b(x')<0，也就是g(w)<0，与题设g(w)=0不符。

这时候，我们可以通过求出来g(w)的值判断w是否为最优解，这样就将原问题的最优性问题转换为了判定性问题。

比如bzoj3232 http://61.187.179.132/JudgeOnline/problem.php?id=3232

这道题要求求v/c的最优值，这样不容易求解，但是我们可以用网络流最小割求出v-w*c的最小值，然后判断与0的关系，这样二分求解。

//By BLADEVIL
const
    lim                         =1e-5;
      
var
    n, m                        :longint;
    pre, other                  :array[0..100010] of longint;
    len                         :array[0..100010] of extended;
    last                        :array[0..3010] of longint;
    tot                         :longint;
    num                         :array[0..60,0..60] of longint;
    key, heng, shu              :array[0..60,0..60] of longint;
    sum                         :longint;
    print                       :extended;
    que, d                      :array[0..3010] of longint;
    source, sink                :longint;
      
function min(a,b:extended):extended;
begin
    if a>b then min:=b else min:=a;
end;
  
function judge(x:extended):extended;
begin
    if abs(x)<lim then exit(0);
    if x<0 then exit(-1) else exit(1);
end;
      
procedure connect(x,y:longint;z:extended);
begin
    inc(tot);
    pre[tot]:=last[x];
    last[x]:=tot;
    other[tot]:=y;
    len[tot]:=z;
end;
      
procedure init;
var
    i, j                        :longint;
      
begin
    read(n,m);
    for i:=1 to n do
        for j:=1 to m do num[i,j]:=(i-1)*m+j;
    for i:=1 to n do
        for j:=1 to m do
        begin
            read(key[i,j]);
            sum:=sum+key[i,j];
        end;
    for i:=1 to n+1 do
        for j:=1 to m do read(heng[i,j]);
    for i:=1 to n do
        for j:=1 to m+1 do read(shu[i,j]);
    source:=num[n,m]+2;
    sink:=source+1;
end;
  
function bfs:boolean;
var
    q, p                        :longint;
    h, t, cur                   :longint;
begin
    fillchar(d,sizeof(d),0);
    d[source]:=1;
    h:=0; t:=1; que[1]:=source;
    while h<t do
    begin
        inc(h);
        cur:=que[h];
        q:=last[cur];
        while q<>0 do
        begin
            p:=other[q];
            if (judge(len[q])>0) and (d[p]=0) then
            begin
                inc(t);
                que[t]:=p;
                d[p]:=d[cur]+1;
                if p=sink then exit(true);
            end;
            q:=pre[q];
        end;
    end;
    exit(false);
end;
  
function dinic(x:longint;flow:extended):extended;
var
    rest, tmp                   :extended;
    q, p                        :longint;
      
begin
    if x=sink then exit(flow);
    rest:=flow;
    q:=last[x];
    while q<>0 do
    begin
        p:=other[q];
        if (judge(len[q])>0) and (d[p]=d[x]+1) and (rest>0) then
        begin
            tmp:=dinic(p,min(rest,len[q]));
            rest:=rest-tmp;
            len[q]:=len[q]-tmp;
            len[q xor 1]:=len[q xor 1]+tmp;
        end;
        q:=pre[q];
    end;
    exit(flow-rest);
end;
  
procedure main;
var
    l, r, mid                   :extended;
    cur                         :longint;
    ans                         :extended;
    i, j                        :longint;
      
begin
    l:=0; r:=90;
    while r-l>lim do
    begin
        mid:=(l+r)/2;
        fillchar(last,sizeof(last),0);
        tot:=1;
        for i:=1 to n do
            for j:=1 to m do
            begin
                connect(source,num[i,j],key[i,j]);
                connect(num[i,j],source,0);
            end;
          
        for i:=1 to n do
            for j:=1 to m do
            begin
                cur:=0;
                if i=1 then inc(cur,heng[i,j]);
                if i=n then inc(cur,heng[i+1,j]);
                if j=1 then inc(cur,shu[i,j]);
                if j=m then inc(cur,shu[i,j+1]);
                if cur>0 then
                begin
                    connect(num[i,j],sink,cur*mid);
                    connect(sink,num[i,j],0);
                end;
            end;
        for i:=1 to n-1 do
            for j:=1 to m do
            begin
                connect(num[i,j],num[i+1,j],heng[i+1,j]*mid);
                connect(num[i+1,j],num[i,j],heng[i+1,j]*mid);
            end;
        for i:=1 to n do
            for j:=1 to m-1 do
            begin
                connect(num[i,j],num[i,j+1],shu[i,j+1]*mid);
                connect(num[i,j+1],num[i,j],shu[i,j+1]*mid);
            end;
        ans:=0;
        while bfs do
            ans:=ans+dinic(source,maxlongint);
        if judge(sum-ans)>0 then l:=mid else r:=mid;
    end;
    writeln(l:0:3);
end;
  
begin
    init;
    main;
end.

 

推荐阅读