generalsimpmethod.java

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

package com.sea0108.simpmethod;

/**
 * general simple method of linear programming
 */
public class GeneralSimpMethod extends StandardSimpMethod
{
	private TwoStepMethod tsm;
	protected boolean isMaximization;	
	protected int[] equationTypes;
	private int varNum;  // number of variables
	private int laxityNum = 0; // number of laxity-variables
	private Fraction[] ansWithLaxity;
	
	public GeneralSimpMethod()
	{
		
	}
	
	/**
	 * @param equationTypes:int[]  the elements denote the types of the equations as following
	 *           -1 for <=  or <
	 *            0 for =
	 *            1 for >=  or >	 
	 */
	public GeneralSimpMethod(Fraction[][] matA, Fraction[] vecB,Fraction[] funCoefs,int[] equationTypes,boolean isMaximization)
	{
		this.varNum = funCoefs.length;
		this.equationTypes = equationTypes;
		Fraction[][] mA;
		Fraction[] fCoefs;		
		for(int i : equationTypes)
			if(i !=0)
				laxityNum++;
		
		if(laxityNum>0)
		{
			final int row = matA.length;
			final int col = matA[0].length + laxityNum;					
			mA = new Fraction[row][col];
			fCoefs = new Fraction[col];
			
			for(int j=0;j<col-laxityNum;j++)
			{			
				for(int i =0;i<row;i++)				
					mA[i][j] = matA[i][j];
				fCoefs[j] = funCoefs[j];
			}
			for(int j=col-laxityNum;j<col;j++)
			{
				for(int i =0;i<row;i++)			
					mA[i][j] = new Fraction(0);			
				fCoefs[j] =new Fraction(0);
			}						
			int c = col-laxityNum;		
			for(int i =0;i<row;i++)			
				if(equationTypes[i] !=0)				
					mA[i][c++] =  new Fraction(-equationTypes[i]);		
		}		
		else	
		{			
			mA = matA;
			fCoefs = funCoefs;
		}
		
		if(!isMaximization)
			for(int j=0;j<matA[0].length;j++)
				fCoefs[j].contrary();	
		
		tsm = new TwoStepMethod(mA,vecB,fCoefs);	
		this.isMaximization = isMaximization;
		init(matA,vecB,funCoefs);
		solve();
	}	
	
	public GeneralSimpMethod(Fraction[][] matA, Fraction[] vecB,Fraction[] funCoefs,boolean isMaximization)
	{	
		this.varNum = funCoefs.length;
		this.equationTypes = equationTypes;
		if(!isMaximization)
			for(int j=0;j<matA[0].length;j++)
				funCoefs[j].contrary();
		
		tsm = new TwoStepMethod(matA,vecB,funCoefs);	
		this.isMaximization = isMaximization;
		init(matA,vecB,funCoefs);
		solve();
	}	
	
	private void init(Fraction[][] matA, Fraction[] vecB,Fraction[] funCoefs)
	{
		this.funCoefs = funCoefs;
		this.matA = matA;
		this.vecB = vecB;
	}
	
	private void solve()
	{
		if(tsm.ans == null)
			this.ans = null;
		else
		{
			this.ansWithLaxity = tsm.ans;
			this.ans = new Fraction[varNum];
			for(int i =0;i<varNum;i++)
				ans[i] = ansWithLaxity[i];
		}	
		this.fval = tsm.fval;
		this.iterCount = tsm.iterCount;
		this.iterProcess = tsm.iterProcess;
		this.iterProcess.add(0, "\t（加入" +laxityNum + "个松弛变量）\n" );
		if(!isMaximization && this.fval!=null)
			this.fval.contrary();
	}
	
	public Fraction[] getAnsWithLaxity()
	{
		return ansWithLaxity;
	}
}