Alter Simplex Algorithm to Minimize on objective f

问题:

I have created the following Simplex Algorithm that maximises on the objective function. I want the opposite to happen. In this example there are two variables and the algorithm must figure out what to multiply these two variables here (13.0 and 23.0) by in order to get the maximum possible result within the constraints set. I want the algorithm to figure out the lowest possible result instead.

My Code:

import java.util.*;


public class Simplex
{
private static final double EPSILON = 1.0E-10;
private double[][] tableaux;
private int numOfConstraints;
private int numOfVariables;

private int[] basis;
/**
 * Constructor for objects of class Simplex
 */
public Simplex()
{


    double[][] thisTableaux = {
        {  5.0, 15.0 },
        {  4.0,  4.0 },
        { 35.0, 20.0 },
    };

    double[] constraints = { 480.0, 160.0, 1190.0 };

    double[] variables = {  13.0,  23.0 };

    numOfConstraints = constraints.length;
    numOfVariables = variables.length;

    tableaux = new double[numOfConstraints+1][numOfVariables+numOfConstraints+1];

    //adds all elements from thisTableaux to tableaux
    for(int i=0; i < numOfConstraints; i++)
    {
        for(int j=0; j < numOfVariables; j++)
        {
            tableaux[i][j] = thisTableaux[i][j];
        }
    } 


    //adds a slack variable for each variable there is and sets it to 1.0
    for(int i=0; i < numOfConstraints; i++)
    {
        tableaux[i][numOfVariables+i] = 1.0;
    }


    //adds variables into the second [] of tableux
    for(int j=0; j < numOfVariables; j++)
    {
        tableaux[numOfConstraints][j] = variables[j];
    }



    //adds constraints to first [] of tableaux
    for(int k=0; k < numOfConstraints; k++)
    {
        tableaux[k][numOfConstraints+numOfVariables] = constraints[k];
    }



    basis = new int[numOfConstraints];

    for(int i=0; i < numOfConstraints; i++)
    {
        basis[i] = numOfVariables + i;
    }

    //show();

    //optimise();

    //assert check(thisTableaux, constraints, variables);


}

public void optimise() {
    while(true) {

        int q = findLowestNonBasicCol();

        if(q == -1) {
            break;
        }

        int p = getPivotRow(q);
        if(p == -1) throw new ArithmeticException("Linear Program Unbounded");

        pivot(p, q);

        basis[p] = q;
    }

}

public int findLowestNonBasicCol() {

    for(int i=0; i < numOfConstraints + numOfVariables; i++)
    {
        if(tableaux[numOfConstraints][i] > 0) {


            return i;
        }
    }

    return -1;


}

public int findIndexOfLowestNonBasicCol() {

    int q = 0;
    for(int i=1; i < numOfConstraints + numOfVariables; i++)
    {
        if(tableaux[numOfConstraints][i] > tableaux[numOfConstraints][q]) {
            q = i;
        }
    }

    if(tableaux[numOfConstraints][q] <= 0) {
        return -1;
    }

    else {
        return q;
    }
}

/**
 * Finds row p which will be the pivot row using the minimum ratio rule.
 * -1 if there is no pivot row
 */
public int getPivotRow(int q) {

    int p = -1;

    for(int i=0; i < numOfConstraints; i++) {

        if (tableaux[i][q] <=0) {
            continue;
        }

        else if (p == -1) {
            p = i;
        }

        else if((tableaux[i][numOfConstraints+numOfVariables] / tableaux[i][q] < tableaux[p][numOfConstraints+numOfVariables] / tableaux[p][q])) {
            p = i;
        }
    }



    return p;


}

public void pivot(int p, int q) {

    for(int i=0; i <= numOfConstraints; i++) {
        for (int j=0; j <= numOfConstraints + numOfVariables; j++) {
            if(i != p && j != q) {
                tableaux[i][j] -= tableaux[p][j] * tableaux[i][q] / tableaux[p][q];
            }
        }
    }

    for(int i=0; i <= numOfConstraints; i++) {
        if(i != p) {
            tableaux[i][q] = 0.0;
        }
    }

    for(int j=0; j <= numOfConstraints + numOfVariables; j++) {
        if(j != q) {
            tableaux[p][j] /= tableaux[p][q];
        }
    }

    tableaux[p][q] = 1.0;

    show();
}

public double result() {
    return -tableaux[numOfConstraints][numOfConstraints+numOfVariables];
}


public double[] primal() {
    double[] x = new double[numOfVariables];
    for(int i=0; i < numOfConstraints; i++) {
        if(basis[i] < numOfVariables) {
            x[basis[i]] = tableaux[i][numOfConstraints+numOfVariables];
        }
    }

    return x;
}

public double[] dual() {
    double[] y = new double[numOfConstraints];

    for(int i=0; i < numOfConstraints; i++) {
        y[i] = -tableaux[numOfConstraints][numOfVariables];
    }

    return y;
}

public boolean isPrimalFeasible(double[][] thisTableaux, double[] constraints) {
    double[] x = primal();

    for(int j=0; j < x.length; j++) {
        if(x[j] < 0.0) {
            StdOut.println("x[" + j + "] = " + x[j] + " is negative");
            return false;
        }
    }

    for(int i=0; i < numOfConstraints; i++) {
        double sum = 0.0;

        for(int j=0; j < numOfVariables; j++) {
            sum += thisTableaux[i][j] * x[j];
        }

        if(sum > constraints[i] + EPSILON) {
            StdOut.println("not primal feasible");
            StdOut.println("constraints[" + i + "] = " + constraints[i] + ", sum = " + sum);
            return false;
        }
    }
    return true;
}


private boolean isDualFeasible(double[][] thisTableaux, double[] variables) {

    double[] y = dual();

    for(int i=0; i < y.length; i++) {
        if(y[i] < 0.0) {
            StdOut.println("y[" + i + "] = " + y[i] + " is negative");
            return false;
        }
    }

    for(int j=0; j < numOfVariables; j++) {
        double sum = 0.0;

        for(int i=0; i < numOfConstraints; i++) {
            sum += thisTableaux[i][j] * y[i];
        }

        if(sum < variables[j] - EPSILON) {
            StdOut.println("not dual feasible");
            StdOut.println("variables[" + j + "] = " + variables[j] + ", sum = " + sum);
            return false;
        }
    }

    return true;

}

private boolean isOptimal(double[] constraints, double[] variables) {

    double[] x = primal();
    double[] y = dual();
    double value = result();

    double value1 = 0.0;
    for(int j=0; j < x.length; j++) {
        value1 += variables[j] * x[j];
    }

    double value2 = 0.0;
    for(int i=0; i < y.length; i++) {
        value2 += y[i] * constraints[i];
    }

    if(Math.abs(value - value1) > EPSILON || Math.abs(value - value2) > EPSILON) {
        StdOut.println("value = " + value + ", cx = " + value1 + ", yb = " + value2);
        return true;
    }

    return true;
}

private boolean check(double[][] thisTableaux, double[] constraints, double [] variables) {
    return isPrimalFeasible(thisTableaux, constraints) && isDualFeasible(thisTableaux, variables) && isOptimal(constraints, variables);
}


}

If you need any more info just ask. Any help appreciated thanks.

回答1:

If you want to minimize f(x), this is equivalent to maximizing -f(x), so if your posted code solves maximization problems correctly, you can use it to minimize any objective function f(x) simply by maximizing its additive inverse -f(x).

Note that you do not change the constraints, only the objective function.

For example, minimizing f(x) = 3x + 5, x >= 1 is equivalent to maximizing -f(x) = -3x -5, x >= 1.

min[f(x), x>=1] = f(1) = 8 = -(-8) = -[-f(1)] = -max[-f(x), x>=1].

In general, min[f(x)] = f(Xmin) = -[-f(Xmax)] = -max[-f(x)] and Xmin = Xmax.

In the above example, min[f(x)] = -max[-f(x)] = 8 and Xmin = Xmax = 1.

In the particular example you give, you would simply need to change the line

double[] variables = {  13.0,  23.0 };

to

double[] variables = {  -13.0,  -23.0 };

The values of the variables returned should then be the same as for the minimum of the case where

double[] variables = {  13.0,  23.0 };

and multiplying the value of the objective function by -1 will give the minimum of the objective for the case where

double[] variables = {  13.0,  23.0 };