割平面法Gommoy.doc

精品文档割平面法Gommoy算法步骤:1 求解原整数规划对应的线性规划 min f(x)=cx, .,设最优解为x*.2 如果最优解的分量均为整数,则x*为原整数规划的最优解:否则任选一个x*中不是整数的分量,设其对应的基变量为xp , 定义包含这个基变量的切割约束方程,其中xj为非基变量.3 令,其中为高斯函数符号,表示不大于某数的最大整数. 将切割约束方程变换为,由于,所以有1,因为自变量为整数,则也为整数,所以进一步有=0.4 将切割方程加入约束方程中,用对偶单纯算法求解线性规划,转.算法MATLAB实现代码:function intx,intf=Gomory(A,c,b,base)%约束矩阵:A;%目标函数系数向量:c%约束右端向量:b%初始基向量base%目标函数取最小化时的自变量值:x%目标函数的最小值:minfsz=size(A);nVia=sz(2);n=sz(1);xx=1:nVia; if length(base)=n disp(基变量的个数要与约束矩阵的行数相等!); mx=NaN; mf=NaN; return;end M=0;sigma=-transpose(c) zeros(1,(nVia-length(c);xb=b;while 1 maxs,ind=max(sigma); if maxs=0 vr=find(c=0,1,last); for l=1:vr ele=find(base=l,1); if(isempty(ele) mx(l)=0; else mx(l)=xb(ele); end end if max(abs(round(mx)-mx)=0 if max(abs(round(xb)-xb)1.0e-7 %用对偶单纯形法求得了整数解 vr=find(c=0 ,1,last); for l=1:vr ele =find (base=l,1); if(isempty(ele) mx_1(l)=0; else mx_1(l)=xb(ele); end end intx=mx_1; intf=mx_1*c; return; else sz=size(A); sr=sz(1); sc=sz(2); max_x,index_x=max(abs(round(mx_1)-mx_1); isB,num=find(index_x=base); fi=xb(num)-flooor(xb (num); for i=1:(index_x-1) Atmp(1,i)=a(num,i)-floor(A(num,i); end for i=(index_x+1):sc Atmp(1,i)=a(num,i)-floor(a(num,i); end %下一次对偶单纯形法迭代的初始表格 Atmp(1,index_x)=0; A=A zeros(sr,1);-Atmp(1,:) 1; xb=xb;-fi; base=base sc+1; sigma=sigma 0; continue; end %对偶单纯形法的换基变量过程 else minb_1=inf; chagB_1=inf; sA=size(A); br,idb=min(xb); for j=1:sA(2) if A(idb,j)0 bm=sigma(j)/A(idb,j); if bm0 bz=xb(j)/A(j,ind); if bz A=-1 2 1 0 ;2 1 0 1;C=1;-1;B=2;4;intx,intf=Gomory(A,c,b,3 4)