probleminstandardform.java

Program for linear programming

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package ro.simplex;

import java.util.ArrayList;
import ro.utils.Fraction;

/**
 *
 * @author Doan Chien Thang
 */
public class ProblemInStandardForm extends Problem {
    protected ArrayList<Variable> baseVars;
    protected ArrayList<Variable> nonbaseVars;
    //protected ArrayList<Variable> auxiliaryVars;
    protected ProblemInStandardForm auxiliaryProblem;
    protected Dictionary dict;
    protected Table table;
    protected ArrayList<String> transitions;

    public ProblemInStandardForm(ArrayList<Variable> vars, 
            ArrayList<Constraint> constraints, Objective objective) {
        super(vars, constraints, objective);
        nonbaseVars = null;
//        auxiliaryVars = null;
        auxiliaryProblem = null;
        dict = null;
        table = null;
        transitions = null;
    }

    private String getVariableChangement(String transition) {
        String s[] = transition.split(" ");
        if (s[0].compareTo("G") == 0)
            return "&nbsp;&nbsp;&nbsp;&nbsp;" +
                    "x<sub>" + s[1] + "</sub> = y<sub>" + s[2] + "</sub><br />";
        else if (s[0].compareTo("L") == 0)
            return "&nbsp;&nbsp;&nbsp;&nbsp;" +
                    "x<sub>" + s[1] + "</sub> = -y<sub>" + s[2] + "</sub><br />";
        else
            return "&nbsp;&nbsp;&nbsp;&nbsp;" +
                    "x<sub>" + s[1] + "</sub> = y<sub>" + s[2] + "</sub> - " +
                    "y<sub>" + s[3] + "</sub><br />";
    }

    public String getTransitions() {
        if (transitions == null)
            return "";
        String result = "<div style=\"background-color:#EDEDED;padding:0;" +
                "margin-right:15\">";
//        System.out.println(transitions.size());
        for (int i = 0; i < transitions.size(); i++)
            result += getVariableChangement(transitions.get(i));
        return result + "</div>";
    }

    @Override
    public String toString() {
        String result = "<p>On peut construire le problème en forme standarde " +
                "par changer les variables comme ça:</p><br />";
        result += getTransitions();
        result += "<h1>Problème en forme standarde:</h1>";
        result += super.toString();
        return result;
    }

    @Override
    public String getSolution() {
        String result = "(";
        System.out.println("*****" + nonbaseVars.size());
        for (int i = 0; i < vars.size(); i++) {
            if (i < vars.size() - 1)
                if (nonbaseVars.contains(vars.get(i)))
                    result += "<font color=\"red\">" + 
                            vars.get(i).toString() + "</font>, ";
                else
                    result += vars.get(i).toString() + ", ";
            else
                if (nonbaseVars.contains(vars.get(i)))
                    result += "<font color=\"red\">" + vars.get(i).toString() +
                        "</font>) = (";
                else
                    result += vars.get(i).toString() + ") = (";
        }
        for (int i = 0; i < vars.size(); i++) {
            if (i < vars.size() - 1)
                if (nonbaseVars.contains(vars.get(i)))
                    result += "<font color=\"red\">" + 
                            vars.get(i).getValue() + "</font>, ";
                else
                    result += vars.get(i).getValue() + ", ";
            else
                if (nonbaseVars.contains(vars.get(i)))
                    result += "<font color=\"red\">" + vars.get(i).getValue() +
                            "</font>)";
                else
                    result += vars.get(i).getValue() + ")";
        }
        return result;
    }

    public void setTransitions(ArrayList<String> transitions) {
        this.transitions = transitions;
    }
    
    public void preprocess() {
        this.nonbaseVars = new ArrayList<Variable>();
        this.baseVars = new ArrayList<Variable>();
        for (int i = 0; i < this.vars.size(); i++) {
            if (this.vars.get(i).getPrefix().compareTo("y") == 0) {
                this.vars.get(i).setValue(new Fraction(0));
                this.baseVars.add(this.vars.get(i));
            } else
                this.nonbaseVars.add(this.vars.get(i));
        }
    }

    public String displayDict() {
        return getDictionary().toString();
    }

    public boolean isSolutionAdmissible() {
        for (int i = 0; i < vars.size(); i++)
            if (vars.get(i).getValue().isNegative())
                return false;
        return true;
    }

    public String getAuxiliaryMessage() {
        String result = "<p>La solution de base ";
        result += getSolution();
        if (isSolutionAdmissible())
            return result + " est réalisable.";
        else
            return result + " n'est pas réalisable. " +
                    "On doit résoudre le problème auxiliaire.</p><br />";
    }

    public Dictionary getDictionary() {
        Objective newObjective = this.objective;
        ArrayList<VariableConstraint> varConstraints =
                new ArrayList<VariableConstraint>();
        for (int i = 0; i < constraints.size(); i++) {
            Variable leftVar = null;
            for (int j = 0; j < nonbaseVars.size(); j++) {
                for (int k = 0; k < constraints.get(i).getCoefs().size(); k++)
                    if (constraints.get(i).getVars().get(k).equals(nonbaseVars.get(j))
                    && !constraints.get(i).getCoefs().get(k).equals(new Fraction(0))) {
                        leftVar = nonbaseVars.get(j);
                        varConstraints.add(constraints.get(i).getVarConstraint(leftVar));
                        break;
                    }
            }
        }
        return new Dictionary(newObjective, varConstraints);
    }

    public void updateSolution(Variable inVar, Variable outVar, 
            Dictionary dict) {
        for (int i = 0; i < dict.getVarConstraints().size(); i++) {
            int index = this.vars.indexOf(
                    dict.getVarConstraints().get(i).getLeftVar());
            this.vars.get(index).setValue(
                    dict.getVarConstraints().get(i).getValue());
        }
        inVar.setValue(new Fraction(0));
        int index = this.baseVars.indexOf(outVar);
        this.baseVars.remove(outVar);
        this.baseVars.add(index, inVar);
        index = this.nonbaseVars.indexOf(inVar);
        this.nonbaseVars.remove(inVar);
        this.nonbaseVars.add(index, outVar);
    }
    
    public String simplexMethod() {
        String result = "";
        this.dict = getDictionary();
        result += dict.toString();
        this.table = new Table(dict, this);
        Variable inVar = null;
        Variable outVar = table.getOutVar();
        int count = 0;
        while (outVar != null) {
            inVar = table.getInVar(outVar);
            count++;
            dict = dict.getNewDictionaryByChangeVariableRoles(inVar, outVar);
            this.updateSolution(inVar, outVar, dict);
            result += "<p><b>" + outVar.toString() +
                " sortie et " + inVar.toString() + " entre</b>" +
                "</p></br />" + dict.toString();
            result += "<p>" + this.getSolution() + "</p><br />";
            table = new Table(dict, this);
            outVar = table.getOutVar();
        }
        switch (this.answer) {
            case Problem.HAS_INFINITVE_SOLUTIONS:
                result += "<p>Infinitf solution</p>";
                break;
            case Problem.HAS_ONE_SOLUTION:
                result += "<p>Has one solution</p>";
                break;
            case Problem.IS_UNBOUND:
                result += "<p>Is unbound</p>";
                break;
            case Problem.NO_SOLUTION:
                result += "<p>No solution</p>";
                break;
            default:
                break;
        }
        return result;
    }

    public void getAuxiliaryProblem() {
        ArrayList<Variable> newVars = new ArrayList<Variable>();
        ArrayList<Variable> newBaseVars = new ArrayList<Variable>();
        ArrayList<Variable> newNonbaseVars = new ArrayList<Variable>();
        ArrayList<Constraint> newConstraints = new ArrayList<Constraint>();
        Objective newObjective = new Objective();

        for (int i = 0; i < this.vars.size(); i++) {
            newVars.add(this.vars.get(i));
//            newBaseVars.add(this.vars.get(i));
        }
        
        String prefix = "t";
        int numOfNegativeConstraints = 0;
        for (int i = 0; i < this.constraints.size(); i++)
            if (this.nonbaseVars.get(i).getValue().isNegative()) {
                numOfNegativeConstraints++;
                Variable var = new Variable(new Fraction(0),
                        numOfNegativeConstraints, prefix,
                    ConstraintTypes.GREATER_THAN);
                if (this.constraints.get(i).getValue().isNegative())
                    var.setValue(
                            this.constraints.get(i).getValue().getOpposite());
                else
                    var.setValue(
                            this.constraints.get(i).getValue());
            newVars.add(var);
            newNonbaseVars.add(var);
            }
        for (int i = 0; i < numOfNegativeConstraints; i++) {
            
        }

        int index = 0;
        for (int i = 0; i < this.constraints.size(); i++) {
            Constraint newConstraint = new Constraint();
            Constraint constraint = this.constraints.get(i);
            newConstraint.setVars(newVars);
            for (int j = 0; j < constraint.getCoefs().size(); j++) {
                newConstraint.getCoefs().add(constraint.getCoefs().get(j));
            }
            if (this.nonbaseVars.get(i).getValue().isNegative()) {
                index++;
                for (int j = 1; j < index; j++)
                    newConstraint.getCoefs().add(new Fraction(0));
                if (constraint.getValue().isNegative())
                    newConstraint.getCoefs().add(new Fraction(-1));
                else
                    newConstraint.getCoefs().add(new Fraction(1));
                for (int j = index + 1; j <= numOfNegativeConstraints; j++)
                    newConstraint.getCoefs().add(new Fraction(0));
            } else {
                newNonbaseVars.add(this.nonbaseVars.get(i));
                for (int j = 1; j <= numOfNegativeConstraints; j++)
                    newConstraint.getCoefs().add(new Fraction(0));
            }
            newConstraint.setValue(constraint.getValue());
            newConstraints.add(newConstraint);
        }

        newObjective.setVars(newVars);
        for (int i = 0; i < vars.size(); i++)
            newObjective.getCoefs().add(new Fraction(0));
        for (int i = 1; i <= numOfNegativeConstraints; i++)
            newObjective.getCoefs().add(new Fraction(-1));
        newObjective.setType(Objective.MAXIMIZE);
        newObjective.setValue(new Fraction(0));
        /*for (int i = 0; i < newVars.size(); i++)
            if (newVars.get(i).getPrefix().compareTo("t") == 0)
                newVars.get(i).setValue(new Fraction(0));*/
        this.auxiliaryProblem =
                new ProblemInStandardForm(newVars, newConstraints, newObjective);
        for (int i = 0; i < this.vars.size(); i++)
            if (!newNonbaseVars.contains(newVars.get(i))) {
                newVars.get(i).setValue(new Fraction(0));
                newBaseVars.add(newVars.get(i));
            }
        this.auxiliaryProblem.baseVars = newBaseVars;
        this.auxiliaryProblem.nonbaseVars = newNonbaseVars;
    }

    public ProblemInStandardForm auxiliaryProb() {
        return this.auxiliaryProblem;
    }
}