/* * 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 Problem {    public static final int HAS_ONE_SOLUTION = 1;    public static final int HAS_INFINITVE_SOLUTIONS = 2;    public static final int IS_UNBOUND = 3;    public static final int NO_SOLUTION = 4;    protected ArrayList<Variable> vars;    protected ArrayList<Constraint> constraints;    protected Objective objective;    protected int answer;    public Problem(ArrayList<Variable> vars, ArrayList<Constraint> constraints,            Objective objective) {        this.vars = vars;        this.constraints = constraints;        this.objective = objective;    }    @Override    public String toString() {        String result = "<div style=\"background-color:#EDEDED;padding:10;" +                "margin-right:15\">";        result += objective.toString();        for (int i = 0; i < constraints.size(); i++)            result += constraints.get(i).toString();        result += "<b>Conditions: ";        for (int i = 0; i < vars.size(); i++) {            if (i < vars.size() - 1)                result += vars.get(i).getConstraintString() + ", ";            else                result += vars.get(i).getConstraintString() + "<br />";        }        return result + "</b></div>";    }    public ArrayList<Variable> getVars() {        return this.vars;    }    public void refinePositiveConstraints(            ArrayList<Constraint> newConstraints,            Variable currentVar) {        for (int i = 0; i < constraints.size(); i++) {            for (int j = 0; j < constraints.get(i).getCoefs().size(); j++) {                if (vars.get(j).equals(currentVar)) {                    newConstraints.get(i).getCoefs().add(                            constraints.get(i).getCoefs().get(j));                }            }        }    }    public void refineNegativeConstraints (            ArrayList<Constraint> newConstraints,            Variable currentVar) {        for (int i = 0; i < constraints.size(); i++) {            for (int j = 0; j < constraints.get(i).getCoefs().size(); j++)                if (vars.get(j).equals(currentVar))                    newConstraints.get(i).getCoefs().add(                            constraints.get(i).getCoefs().get(j).getOpposite());        }    }    public void refineBelongsRConstraints (            ArrayList<Constraint> newConstraints,            Variable currentVar) {        for (int i = 0; i < constraints.size(); i++) {            for (int j = 0; j < constraints.get(i).getCoefs().size(); j++)                if (vars.get(j).equals(currentVar)) {                    newConstraints.get(i).getCoefs().add(                            constraints.get(i).getCoefs().get(j));                    newConstraints.get(i).getCoefs().add(                            constraints.get(i).getCoefs().get(j).getOpposite());                }        }    }    public void refineObjective(Objective newObjective,             Variable currentVar) {        for (int i = 0; i < objective.getCoefs().size(); i++)            if (vars.get(i).equals(currentVar)) {                if (currentVar.getConstraint() == ConstraintTypes.GREATER_THAN)                    newObjective.getCoefs().add(objective.getCoefs().get(i));                else if (currentVar.getConstraint() == ConstraintTypes.LESS_THAN)                    newObjective.getCoefs().add(                            objective.getCoefs().get(i).getOpposite());                else                    newObjective.getCoefs().add(objective.getCoefs().get(i));                if (currentVar.getConstraint() == ConstraintTypes.BELONG_R)                    newObjective.getCoefs().add(                            objective.getCoefs().get(i).getOpposite());            }    }    public void setObjective(Objective newObjective) {        if (objective.getType() == Objective.MINIMIZE)            for (int i = 0; i < newObjective.getCoefs().size(); i++)                newObjective.getCoefs().set(i,                        newObjective.getCoefs().get(i).getOpposite());        newObjective.setType(Objective.MAXIMIZE);    }    public void addNewVariablesToGetEquations(            ArrayList<Variable> newVars, ArrayList<Constraint> newConstraints) {        String newPrefix = "u";        int index = 0;        for (int i = 0; i < newConstraints.size(); i++) {            Variable var;            newConstraints.get(i).setValue(constraints.get(i).getValue());            switch (constraints.get(i).getType()) {                case ConstraintTypes.GREATER_THAN:                    var = new Variable(null, ++index, newPrefix,                            ConstraintTypes.GREATER_THAN);                    var.setValue(constraints.get(i).getValue().getOpposite());                    newVars.add(var);                    for (int j = 0; j < index - 1; j++)                        newConstraints.get(i).getCoefs().add(new Fraction(0));                    newConstraints.get(i).getCoefs().add(new Fraction(-1));                    break;                case ConstraintTypes.LESS_THAN:                    var = new Variable(null, ++index, newPrefix,                            ConstraintTypes.GREATER_THAN);                    var.setValue(constraints.get(i).getValue());                    newVars.add(var);                    for (int j = 0; j < index - 1; j++)                        newConstraints.get(i).getCoefs().add(new Fraction(0));                    newConstraints.get(i).getCoefs().add(new Fraction(1));                    break;                case ConstraintTypes.EQUAL_TO:                    for (int j = 0; j < index; j++)                        newConstraints.get(i).getCoefs().add(new Fraction(0));                    break;                default:                    break;            }        }        for (int i = 0; i < newConstraints.size(); i++) {            for (int j = newConstraints.get(i).getCoefs().size();                j < newVars.size(); j++)                newConstraints.get(i).getCoefs().add(new Fraction(0));        }    }    public Problem refinedProblem() {        ArrayList<Variable> newVars = this.vars;        ArrayList<Constraint> newConstraints = new ArrayList<Constraint>();        Objective newObjective = this.objective;        for (int i = 0; i < this.constraints.size(); i++) {            Constraint constraint1, constraint2;            if (this.constraints.get(i).getType() == ConstraintTypes.EQUAL_TO) {                constraint1 = new Constraint(ConstraintTypes.GREATER_THAN,                        this.constraints.get(i).getCoefs(),                        this.constraints.get(i).getVars(),                        this.constraints.get(i).getValue());                constraint2 = new Constraint(ConstraintTypes.LESS_THAN,                        this.constraints.get(i).getCoefs(),                        this.constraints.get(i).getVars(),                        this.constraints.get(i).getValue());                newConstraints.add(constraint1);                newConstraints.add(constraint2);            } else                newConstraints.add(this.constraints.get(i));        }        return new Problem(newVars, newConstraints, newObjective);    }    public ProblemInStandardForm getStandardForm() {        ArrayList<Variable> newVars = new ArrayList<Variable>();        ArrayList<Constraint> newConstraints = new ArrayList<Constraint>();        ArrayList<String> transitions = new ArrayList<String>();        ArrayList<Fraction> newObjCoeffs = new ArrayList<Fraction>();        ArrayList<Fraction> newConsCoeffs = new ArrayList<Fraction>();        Objective newObjective = new Objective();        String newPrefix = "y";        int currentIdx = 0;        for (int i = 0; i < constraints.size(); i++)            newConstraints.add(new Constraint());        for (int i = 0; i < vars.size(); i++) {            Variable var, var1;            switch(vars.get(i).getConstraint()) {                case (ConstraintTypes.GREATER_THAN):                    var = new Variable(vars.get(i).getValue(), ++currentIdx,                            newPrefix, ConstraintTypes.GREATER_THAN);                    newVars.add(var);                    transitions.add("G " + vars.get(i).getIndex() + " "                           + currentIdx);                    refinePositiveConstraints(newConstraints, vars.get(i));                    refineObjective(newObjective, vars.get(i));                    break;                case (ConstraintTypes.LESS_THAN):                    var = new Variable(vars.get(i).getValue(), ++currentIdx,                            newPrefix, ConstraintTypes.GREATER_THAN);                    newVars.add(var);                    transitions.add("L " + vars.get(i).getIndex() + " "                           + currentIdx);                    refineNegativeConstraints(newConstraints, vars.get(i));                    refineObjective(newObjective, vars.get(i));                    break;                case (ConstraintTypes.BELONG_R):                    var = new Variable(vars.get(i).getValue(), ++currentIdx,                            newPrefix, ConstraintTypes.GREATER_THAN);                    newVars.add(var);                    var1 = new Variable(vars.get(i).getValue(), ++currentIdx,                            newPrefix, ConstraintTypes.GREATER_THAN);                    newVars.add(var1);                    transitions.add("B " + vars.get(i).getIndex() + " " +                            (currentIdx - 1) + " " + currentIdx);                    refineBelongsRConstraints(newConstraints, vars.get(i));                    refineObjective(newObjective, vars.get(i));                    break;                default:                    break;            }        }        for (int i = 0; i < newConstraints.size(); i++)            newConstraints.get(i).setVars(newVars);        newObjective.setVars(newVars);        int numOfVarsBefore = newVars.size();        setObjective(newObjective);        newObjective.setValue(new Fraction(0));        addNewVariablesToGetEquations(newVars, newConstraints);        for (int i = numOfVarsBefore; i < newVars.size(); i++)            newObjective.getCoefs().add(new Fraction(0));        ProblemInStandardForm stdFormProblem =                new ProblemInStandardForm(newVars, newConstraints,                newObjective);        stdFormProblem.setTransitions(transitions);//        stdFormProblem.dict = stdFormProblem.getDictionary();        return stdFormProblem;    }    public String getSolution() {        String result = "(";        for (int i = 0; i < vars.size(); i++) {            if (i < vars.size() - 1)                result += vars.get(i).toString() + ", ";            else                result += vars.get(i).toString() + ") = (";        }        for (int i = 0; i < vars.size(); i++) {            if (i < vars.size() - 1)                result += vars.get(i).getValue() + ", ";            else                result += vars.get(i).getValue() + ")";        }        return result;    }    public Objective getObjective() {        return this.objective;    }    public String solution() {        String text = "";        Problem refinedProblem = this.refinedProblem();        ProblemInStandardForm stdFormProblem = refinedProblem.getStandardForm();        //System.out.println(constraint.toString());        text = "<body style=\"padding:0px 0px 0px 10px;" +                "font-family:cambria Math;font-size:16\"><h1>Problème en forme générale</h1>";        text += "Voici le problème en forme générale: <br /><br />";        text += this.toString();        text += "<p>On peut changer les variables comme ?a " +                "pour gagner le problème sous forme standarde:</p><br />";        text += stdFormProblem.toString();        stdFormProblem.preprocess();        stdFormProblem.setDict();        text += stdFormProblem.getAuxiliaryMessage();        if (!stdFormProblem.isSolutionAdmissible()) {            stdFormProblem.getAuxiliaryProblem();            ProblemInStandardForm auxiliaryProblem =                    stdFormProblem.auxiliaryProb();            text += auxiliaryProblem.toString();            text += auxiliaryProblem.getSolution();            text += auxiliaryProblem.simplexMethod();//            text += stdFormProblem.getSolution();//            text += auxiliaryProblem.getDict();            text += "<h1>Retour au problème original: </h1>";            stdFormProblem.updateDict(auxiliaryProblem);            if (!auxiliaryProblem.objective.getObjectiveValue().equals(0)) {                return text + "<p><b><font color=\"red\">Le problème ne possède " +                            "pas une solution réalisable.</font></b></p></body>";            }/*            text += stdFormProblem.getSolution();            text += "<p><b>Valeur de l'objective = " +                    stdFormProblem.getObjective().getObjectiveValue() + "</b></p>";*/        }        //text += stdFormProblem.displayDict();        Dictionary dict = stdFormProblem.getDict();        text += dict.toString();        Variable inVar = null;        Variable outVar = null;        text += stdFormProblem.getSolution();        text += stdFormProblem.simplexMethod();        text += "</body>";        return text;    }}