standardsimpmethod.java

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

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

/**
 * standard simple method for maximization of linear programming
 */
public class StandardSimpMethod 
{
	public static final Fraction MAX = Fraction.MAX_VALUE;
	protected Fraction[] funCoefs; 
	protected Fraction[][] matA;   
	protected Fraction[]  vecB;  
	private int[] baseVar;     
	private Fraction[][] table;
	public Fraction[] ans;       
	public Fraction fval;    
	private int tableRow;
	private int tableCol;
	public int iterCount = 0;
	private String line;
	public ArrayList<String> iterProcess = new ArrayList<String>();
	
	protected StandardSimpMethod()
	{
		
	}
	
	public  StandardSimpMethod(Fraction[][] matA, Fraction[]  vecB,Fraction[] funCoefs)
	{
		init(matA,vecB,funCoefs);
		solve();
	}
	
	public StandardSimpMethod(Fraction[][] matA, Fraction[]  vecB,Fraction[] funCoefs,Fraction negFval)
	{
		init(matA,vecB,funCoefs);
		this.table[tableRow-1][tableCol-1] = negFval;
		solve();
	}
	
	protected  StandardSimpMethod(Fraction[][] table, int[] baseVar)
	{	
		this.tableRow = table.length;
		this.tableCol = table[0].length;
		this.ans = new Fraction[tableCol-1];
		this.table = table;
		this.baseVar = baseVar;
		initLine();
		solve();
	}
	
	private void init(Fraction[][] matA, Fraction[]  vecB,Fraction[] funCoefs)
	{
		this.funCoefs = funCoefs;
		this.matA = matA;
		this.vecB = vecB;
		this.tableRow = matA.length + 1;
		this.tableCol = matA[0].length + 1;
		this.ans = new Fraction[tableCol-1];				
		initTable();
		initBaseVar();
		initLine();
	}
	
	private void initTable()
	{
		table = new Fraction[tableRow][tableCol];
		for(int i=0; i<tableRow-1; i++)
			for(int j=0; j<tableCol-1; j++)
				table[i][j] = matA[i][j];
		
		for(int i=0; i<tableRow-1; i++)
			table[i][tableCol-1] = vecB[i];			
		for(int i=0; i<tableCol-1; i++)
			table[tableRow-1][i] = funCoefs[i];				
		table[tableRow-1][tableCol-1] =  new Fraction(0);
	}	

	private void initBaseVar()
	{
		baseVar = new int[tableRow-1];
		for(int i=0; i<tableRow-1; i++)
			baseVar[i] = tableCol - tableRow + i;
	}
	
	private void  initLine()
	{
		StringBuilder sb = new StringBuilder();
		for(int i =0;i<80;i++)
			sb.append("——");
		StringBuilder s = new StringBuilder();
		for(int i =0;i<tableCol;i++)
			s.append("\t    ");
		line =  sb.toString().substring(0,(int)(0.73*s.length()));
	}
	
	private void solve()
	{	
		iterProcess.add(showTable());
		boolean findAns = false; //if findAns is true then we find the best answer	
		while( !findAns )
		{	
			int inVar = -1;
			int outVar = -1;
			Fraction d = new Fraction(0);
			for(int i = 0; i<tableCol-1; i++)
				if(table[tableRow-1][i].compareTo(d)>0)
				{					
					d = table[tableRow-1][i];				
					inVar = i;			
				}				
		
			if(inVar>=0)
			{
				d = MAX;		
				for(int i =0;i<tableRow-1;i++)				
					if(table[i][inVar].b>0)
					{
						Fraction r =  Fraction.divide(table[i][tableCol-1],table[i][inVar]);					
						if(r.compareTo(d)<0)
						{				
							d = r;
							outVar = i;					 
						}
					}							
			}

			if(inVar >=0 && outVar>=0)
			{			
			    baseVar[outVar] = inVar;
				transform(table,outVar,inVar);	
				iterCount++;
				iterProcess.add(showTable());	
			}	
			else
			{			
				findAns = true;
				getResult(inVar);
			}	   
		}
	}	
	
	public static void transform(Fraction[][] table,int r,int c)
	{
		final int tableRow = table.length;
		final int tableCol = table[0].length;
		Fraction d = table[r][c];
		if(!d.equals(new Fraction(1)))
			for(int i=0; i<tableCol; i++)
				table[r][i]  = 	Fraction.divide(table[r][i], d);		
	
		for(int i=0; i<tableRow; i++)
			if(i!=r && table[i][c].b!=0)
			{
				d = table[i][c];	
				for(int j=0; j<tableCol; j++)
					table[i][j] = Fraction.minus(table[i][j], Fraction.multiply(table[r][j],d));	
			}			
	}
	
	private void getResult(int inVar)
	{	
		for(int i =0; i<tableCol-1; i++)
			ans[i] = new Fraction(0);		
		for(int i =0; i<tableRow-1; i++)
			ans[baseVar[i]] = table[i][tableCol-1];		
							
		if(inVar<0)				
			fval = table[tableRow-1][tableCol-1].contraryNumber();			
		else
		{				
			ans[inVar] = MAX;					
			fval = MAX;
		}	
	}
	
	public String showTable()
	{
		StringBuilder sb = new StringBuilder();
		sb.append("\t（求最大）迭代（"  + iterCount+  "）：基（");
		for(int i =0;i<tableRow-2;i++)
			sb.append((baseVar[i]+1)+ "，");
		sb.append((baseVar[tableRow-2]+1) + "）\n");			
		
		for(int i = 0;i<tableRow -1;i++)
		{	
			for(int j =0;j<tableCol-1;j++)
				sb.append("\t" + table[i][j]);		
			sb.append("\t|\t" + table[i][tableCol-1] + "\n");
		}	
		sb.append("\t" + line + "\n");
		for(int j =0;j<tableCol-1;j++)
			sb.append("\t" + table[tableRow-1][j]);
		sb.append("\t    （" + table[tableRow-1][tableCol-1].contraryNumber() + "）\n");
			
		return sb.toString();
	}		

	protected int[] getBaseVar()
	{
		return baseVar;
	}
	
	protected Fraction[][] getTable()
	{
		return table;
	}
}