twostepmethod.java

[数学问题]用分支定界发解线性混合整数规划问题

package com.sea0108.simpmethod;
import java.util.List;

public class TwoStepMethod extends StandardSimpMethod
{	
	private StandardSimpMethod ssm;
	private int mrow;
	private int mcol;
	public List[]  iterProcesses = new List[2];
	public int[] iterCounts = new int[2];
	
	public TwoStepMethod( Fraction[][] matA, Fraction[]  vecB,Fraction[] funCoefs)
	{
		this.funCoefs = funCoefs;
		mrow = matA.length;
		mcol = matA[0].length + mrow;
		Fraction[] fCoefs = new Fraction[mcol];
		Fraction[][] mA = new Fraction[mrow][mcol];
		
		for(int i =0; i<mrow;i++)
			for(int j =0;j<mcol-mrow;j++)
				mA[i][j] = matA[i][j];
		for(int i =0; i<mrow;i++)
			for(int j =mcol-mrow;j<mcol;j++)
				if(i == j - mcol +mrow)
					mA[i][j] = new Fraction(1);
				else
					mA[i][j] = new Fraction(0);
		
		Fraction fr;
		for(int j=0;j<mcol-mrow;j++)
		{	
			fr = new Fraction(0);
			for(int i =0;i<mrow;i++)
				fr = Fraction.add(fr,matA[i][j]);
			fCoefs[j] = fr;
		}		
		for(int i = mcol-mrow; i<mcol; i++)
			fCoefs[i] = new Fraction(0);		
	
		fr = new Fraction(0);
		for(int i =0;i<mrow;i++)
			fr = Fraction.add(fr,vecB[i]);	
		
		ssm = new StandardSimpMethod(mA,vecB,fCoefs,fr);	
		solve();	
	}	
	
	private void solve()
	{
		iterProcesses[0] = ssm.iterProcess;
		iterCounts[0] = ssm.iterCount;
		this.iterProcess.add("\t（二阶段法：阶段一）\n");
		this.iterProcess.addAll(ssm.iterProcess);
		this.iterCount += ssm.iterCount;
		
		//step one
		Fraction[] ans = ssm.ans;	
		final int len = ans.length;
		boolean noAns = false;	
		for(int i =0;i<mrow;i++)
			if(ans[len-1-i].b > 0)	
			{
				noAns = true;
				break;
			}
			
		//step two	
		if(!noAns)
		{
			Fraction[][] stable = ssm.getTable();
			Fraction[][] table = new Fraction[mrow+1][mcol-mrow+1];
			for(int i =0;i<mrow;i++)
				for(int j=0;j<mcol-mrow;j++)
					table[i][j] = stable[i][j];
			for(int i =0;i<mrow;i++)
				table[i][mcol-mrow] = stable[i][mcol];
			for(int j=0;j<mcol-mrow;j++)
				table[mrow][j] = this.funCoefs[j];					
			table[mrow][mcol-mrow] = new Fraction(0);	
			
			//initialization
			int[] baseVar = ssm.getBaseVar();
			for(int i =0;i<mrow;i++)
				StandardSimpMethod.transform(table,i,baseVar[i]);
			
			//solve
			ssm = new StandardSimpMethod(table,baseVar);	
			this.ans = ssm.ans;
			this.fval = ssm.fval;
			this.iterCounts[1] = ssm.iterCount;
			this.iterProcesses[1] = ssm.iterProcess;
			this.iterProcess.add("\t（二阶段法：阶段二）\n");
			this.iterProcess.addAll(ssm.iterProcess);
			this.iterCount += ssm.iterCount;
		}		
	}	
}