webcab.lib.math.optimization.linearprogramming
Class LinearProgramming

java.lang.Object
  |
  +--webcab.lib.math.optimization.linearprogramming.LinearProgramming

All Implemented Interfaces:

Serializable

public class LinearProgramming

extends Object

implements Serializable

Within this class we provide methods to solve and perform sensitivity analysis on Linear programming problems. A linear programming problem is an (maximum or minimum) optimization problem where the object function and the constraints are linear functions. Moreover, in addition to the given constraints all Linear programming problem have primary constraints which specify that the variables over which he solution is sought is always positive. However, as shown with the PDF within the section entitled `Extending the possible solution set', this requirement can be reduced to requiring that the variables over which the solution is sort are bounded from below.

Overview of Functionality Offered

Within this class we provide a refined Kunzi-Tzschach-Zehnder Simplex algorithm which has been specifically developed to treat Linear Programming optimization problems. The Kunzi-Tzschach-Zehnder Simplex algorithm finds the location and hence value of the maximum or minimum of a given linear programming problem. Note that within our implementation once the problem has been set up you are able to request that the location of the minimum or the maximum of the object function is found by specifying the extremum type (i.e. ExtremumTypes.MINIMUM or ExtremumTypes.MAXIMUM.

Once the solution is known the tightness of the constraints can be evaluated using solutionSlack. We also provide within this class procedures by which sensitivity analysis of the linear programming problem can be performed. These include a general approach include sensitivity grids and scenario analysis, along with the use of dual variable based procedures which allow very efficient sensitivity analysis with respect to boundary shifts.

Detailed Description of Functionality Offered

Within this class we offer the following functionality:

Linear Programming Solver

1. multiLinearSimplex(ExtremumTypes, double[], double[][], double[][]) - Returns the location of the maximum or minimum of the linear programming problem.
2. multiLinearSimplex(ExtremumTypes, double[], int, double[][], int, double[][], int) - Returns the location of the maximum or minimum of the linear programming problem where the number of object function coefficients; inequality and equalities are given. The requirement to provide the number of the coefficients, and constants can on the one hand act as a safety check and on the other allow for example, only the first i-th inequalities from those given to be considered.
3. solutionSlack - Once the solution is know the degree of the slack within each of the inequalities can be recorded.

Sensitivity Analysis - General Framework

1. sensitivityGrid - Two dimensional sensitivity grid for the coefficients of the linear object function. In particular, consider how the changes in the value of the extremum (maximum or minimum) varies when at most two of the coefficients of the linear object function are perturbed.
2. scenarioAnalysisCor - Evaluates the location of the extremum (i.e. maximum or minimum) when the coefficients of the object function, and/or the constant terms of the inequalities or equalities have been perturbed.
3. scenarioAnalysis - Evaluates the value of the extremum (i.e. maximum or minimum) when the coefficients of the object function, and/or the constant terms of the inequalities or equalities have been perturbed.

Dual Problem Techniques - Mapping to Dual problem and Sensitivity Analysis

1. dualCoeff - Evaluates the coefficients on the linear object function of the dual problem when the primal problem is given.
2. dualInequal - Evaluates the inequalities of the dual problem when the primal problem is given.
3. dualEqual - Evaluates the equalities of the dual problem when the primal problem is given.
4. dualSolve - Applies our refinement of the Kunzi-Tzschach-Zehnder Simplex algorithm to find the location of the solution of the dual problem. Please note that if in the primal problem we find the maximum (respec. minimum) then in the dual problem we are required to find the minimum (resp. maximum) of the domain over which the dual problem was considered.
5. dualSensitivity(double[], double[]) - Performs sensitivity analysis of the primal problem based upon the dual variables. This procedure offers a very efficient means by which to analyze the sensitivity of the extremum of the object function to shifts in the boundaries. In particular, for (small) parallel shifts of the linear boundaries we evaluate the absolute change in the value of the extremum (i.e. minimum or maximum) of the primal problems object function.

Remark: The notion of duality like that of the more widely known notion of convexity plays an important role within many advanced topics of linear and non-linear programming. Within are PDF documentation and to a lesser extent within the API documentation, we will provide the information necessary to gain to understanding sufficient to apply these ideas in a consistent and intelligent manner.

Factory Example

Throughout this class we will use the illustration of an imaginary factory production procedure in order to demonstrate how these linear programming methods can be applied to solve real business problems. The factory in question produces a range of five different products. The means of production of producing these five products is limited by the materials available, manpower and so on... We are able to link the study of this factory to a linear programming problem because:

1. Linear Object Function: The profit generated by the factory in the production of the five products is given by a linear function on the five variables where the variables represent the amount of each product which is being produced. The coefficients here will represent the corresponding profit generated from each of the five products (i.e. the first coefficient represents the profit from the first product, the second from the second product and so on...).
2. Constraints: The restrictions on the means of production is represented by linear equality and inequality constraints on the five variables represent the amount of each product being produced.

The linear object function and constraints are a well formed linear programming problem. Our aim below with regard to the factory example is to show what business information can be gained by applying linear optimization techniques to the study of this problem.

See Also:

Serialized Form

Constructor Summary

LinearProgramming()
Creates a new instance.

Method Summary

double[]	dualCoeff(double[] coefficients, double[][] inequalityConstraints, double[][] equalityConstraints) Evaluates the coefficients of the linear object function of the dual problem when the primal problem is given.
double[][]	dualEqual(double[] coefficients, double[][] inequalityConstraints, double[][] equalityConstraints, boolean[] positivity) Evaluates the equality constraints of the dual problem when the primal problem is given.
double[][]	dualInequal(double[] coefficients, double[][] inequalityConstraints, double[][] equalityConstraints, boolean[] positivity) Evaluates the inequality constraints of the dual problem when the primal problem is given.
double	dualSensitivity(double[] dualSolution, double[] boundaryShifts) Performs sensitivity analysis of the primal problem based upon the dual variables.
double[]	dualSolve(double[] coefficients, double[][] inequalityConstraints, double[][] equalityConstraints, boolean[] positivity) Applies the Kunzi-Tzschach-Zehnder Simplex algorithm to find the location of the solution of the dual problem when the primal problem is given.
double	functionValue(double[] coefficients, double[] coordinateValues) Returns the value of the linear programming object function at the given coordinate values.
double[]	multiLinearSimplex(ExtremumTypes extremumType, double[] coefficients, double[][] inequalityConstraints, double[][] equalityConstraints) Returns the location of the extremum (i.e. minimum or maximum) of a linear programming problem.
double[]	multiLinearSimplex(ExtremumTypes extremumType, double[] coefficients, int numberOfVariables, double[][] inequalityConstraints, int numberOfInequalities, double[][] equalityConstraints, int numberOfEqualities) Returns the location of the extremum (i.e. minimum or maximum) of a linear programming problem.
double	scenarioAnalysis(ExtremumTypes extremumType, double[] coefficients, double[][] inequalityConstraints, double[][] equalityConstraints, double[] percentageShiftsOfCoefficients, double[] shiftsOfInequalities, double[] shiftsOfEqualities) Performs Scenario Analysis on a Linear programming problem by evaluating the value of the extremum (i.e.
double[]	scenarioAnalysisCor(ExtremumTypes extremumType, double[] coefficients, double[][] inequalityConstraints, double[][] equalityConstraints, double[] percentageShiftsOfCoefficients, double[] shiftsOfInequalities, double[] shiftsOfEqualities) Performs Scenario Analysis on a Linear programming problem by evaluating the location of the extremum (i.e. maximum or minimum) when the coefficients of the linear object function and the constraints are perturbed.
double[][]	sensitivityGrid(ExtremumTypes extremumType, double[] coefficients, double[][] inequalityConstraints, double[][] equalityConstraints, int noShiftsOfFirst, int noShiftsOfSecond, int middleIndexOfFirst, int middleIndexOfSecond, int firstSelectedIndex, int secondSelectedIndex, double percentageShiftOfFirst, double percentageShiftOfSecond) Evaluates the sensitivity grid for a given Linear programming problem.
double[]	solutionSlack(double[][] inequalities, double[] multiSimplexSolution) Provides information about the `tightness' of each inequality with respect to the results provided by the multiLinearSimplex(ExtremumTypes, double[], double[][], double[][]), or multiLinearSimplex(ExtremumTypes, double[], int, double[][], int, double[][], int) multi simplex methods.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

LinearProgramming

public LinearProgramming()

Creates a new instance.

Method Detail

multiLinearSimplex

public double[] multiLinearSimplex(ExtremumTypes extremumType,
                                   double[] coefficients,
                                   double[][] inequalityConstraints,
                                   double[][] equalityConstraints)
                            throws LinearProgrammingException

Returns the location of the extremum (i.e. minimum or maximum) of a linear programming problem. Recall, that a linear programming problem is a special type of optimization problem where the objective function, inequality constraints and equality constraints are all linear. In order to find the extremum we apply a refined Kunzi-Tzschach-Zehnder simplex algorithm. Below we describe how the object function and constraints are passed to the simplex method.

Application to the Factory Example

Since in the Factory example (see Factory Example description) the linear object function represents the profit level of the factory, the returned solution to the simplex method represents the product mix of the factory which will result in the maximum profit. By then substituting this product mix back into the linear object function we will be able to see the exact profit level which can be achieved by the factory.

Defining the Linear Programming Problem

The linear programming problem is passed to the method by specifying the array of coefficients of the linear object function and by using two 2-dimensional double arrays in order to describe the set of inequality and equality constraints which the solution of the linear programming problem must satisfy. Below we explicitly describe how a given linear programming problem, that is an object function together with a set of inequality and equality constraints can be mapped into the parameters which will be provided to the (simplex) method.

All linear (programming) object functions f can be written in the following form:

f(x₁, x₂, ..., x_N) = coefficients₁ * x₁ + coefficients₂ * x₂ + ... + coefficients_N * x_N, where N is the number of variables considered, coefficients_i are the set of coefficients of the linear function and x₁,...,x_N are the coordinates (i.e. the degrees of freedom of the problem) of the solution set over which a point where the extremum (i.e. maximum or minimum) of the linear function is sought.

The solution set is spanned by the coordinates x₁,...,x_Nx which are subject to a set of inequality and equality constraints. That is, the solution set over which an extremum is sought is any combination of coordinates which satisfies the given constraints. These inequality and equality constraints are supplied in the form of 2 dimensional double arrays, where each line of the 2 dimensional array corresponds to the coefficients within a linear equality or inequality constraint. That is, in order to express the following inequality:

c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b >= 0, you will need to supply a line within the two-dimensional array which contains the inequality constraints coefficients plus the constant b (i.e. the N + 1^th term), according to the following convention: {c₁, c₂, ..., c_N, b} For every inequality of the problem considered you will need to provide such an array within the inequality constraints two-dimensional array.

The equality constraints for the problem are expressed in a similar fashion to the inequality constraints, where the coefficients are listed in order followed by a real number. The equalities should be collected within a two-dimensional array in a similar way to the inequalities and passed as a parameter to the method. In particular, each equality is expressed in the following form: c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b = 0, for which you will need to provide the following array within the equality two-dimensional array:

{c₁, c₂, ..., c_N, b} For each of the equality constraints you will need to first encode then as an array in accordance with the above convention and then add the array to the equality constraints two-dimensional array.

Parameters:

extremumType - used to determine whether location of the minimum or maximum of the object function is sought. If the minimum is required then input ExtremumTypes.MINIMUM, if the maximum is required then input ExtremumTypes.MAXIMUM.

coefficients - The coefficients of the linear objective function f, where f(x₁, x₂, ...) = coefficients₁ * x₁ + coefficients₂ * x₂ + ...

inequalityConstraints - A two-dimensional array containing the coefficients of the inequalities where every array corresponds to another inequality encoded in accordance with the above notes.

equalityConstraints - A two-dimensional array containing the coefficients of the equalities where every array corresponds to another equality encoded in accordance with the above notes.

Returns:

The coordinates of the location of the extremum (i.e. maximum or minimum) of the linear programming problem. That is, a point in N-dimensional space returned as an array of doubles where the first term of the array corresponds to the first coordinate, the second term to the second coordinate and so on.

Throws:

LinearProgrammingException - thrown if either the region given by the constraints is empty or if the function is unbounded on the region.

See Also:

This method also implements the same Kunzi-Tzschach-Zehnder simplex algorithm except that here we also specify the number of variables, inequalities and equalities.

multiLinearSimplex

public double[] multiLinearSimplex(ExtremumTypes extremumType,
                                   double[] coefficients,
                                   int numberOfVariables,
                                   double[][] inequalityConstraints,
                                   int numberOfInequalities,
                                   double[][] equalityConstraints,
                                   int numberOfEqualities)
                            throws LinearProgrammingException

Returns the location of the extremum (i.e. minimum or maximum) of a linear programming problem. Recall, that a linear programming problem is a special type of optimization problem where the objective function, inequality constraints and equality constraints are all linear. In order to find the extremum we apply a refined Kunzi-Tzschach-Zehnder simplex algorithm. This method also has the feature that it requires that the number of variables, inequalities and equalities must be provided, this acts as an extra safety measure. Below we describe how the object function and constraints are passed to the simplex method.

Application to the Factory Example

Since in the Factory example (see Factory Example description) the linear object function represents the profit level of the factory, the returned solution to the simplex method represents the product mix of the factory which will result in the maximum profit. By then substituting this product mix back into the linear object function we will be able to see the exact profit level which can be achieved by the factory.

Defining the Linear Programming Problem

The linear programming problem is passed to the method by specifying the array of coefficients of the linear object function and by using two 2-dimensional double arrays in order to describe the set of inequality and equality constraints which the solution of the linear programming problem must satisfy. Below we explicitly describe how a given linear programming problem, that is an object function together with a set of inequality and equality constraints can be mapped into the parameters which will be provided to the (simplex) method.

All linear (programming) object functions f can be written in the following form:

f(x₁, x₂, ..., x_N) = coefficients₁ * x₁ + coefficients₂ * x₂ + ... + coefficients_N * x_N, where N is the number of variables considered, coefficients_i are the set of coefficients of the linear function and x₁,...,x_N are the coordinates (i.e. the degrees of freedom of the problem) of the solution set over which a point where a maximum of the linear function is sought.

The solution set is spanned by the coordinates x₁,...,x_Nx which are subject to a set of inequality and equality constraints. That is, the solution set over which an extremum is sought is any combination of coordinates which satisfies the given constraints. These inequality and equality constraints are supplied in the form of 2 dimensional double arrays, where each line of the 2 dimensional array corresponds to the coefficients within a linear equality or inequality constraint. That is, in order to express the following inequality:

c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b >= 0, you will need to supply a line within the two-dimensional array which contains the inequality constraints coefficients plus the constant b (i.e. the N + 1^th term), according to the following convention: {c₁, c₂, ..., c_N, b} For every inequality of the problem considered you will need to provide such an array within the inequality constraints two-dimensional array.

The equality constraints for the problem are expressed in a similar fashion to the inequality constraints, where the coefficients are listed in order followed by a real number. The equalities should be collected within a two-dimensional array in a similar way to the inequalities and passed as a parameter to the method. In particular, each equality is expressed in the following form: c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b = 0, for which you will need to provide the following array within the equality two-dimensional array:

{c₁, c₂, ..., c_N, b} For each of the equality constraints you will need to first encode then as an array in accordance with the above convention and then add the array to the equality constraints two-dimensional array.

Parameters:

extremumType - used to determine whether location of the minimum or maximum of the object function is found. If the minimum is required then input ExtremumTypes.MINIMUM, if the maximum is required then input ExtremumTypes.MAXIMUM.

coefficients - The coefficients of the linear objective function f, where f(x₁, x₂, ...) = coefficients₁ * x₁ + coefficients₂ * x₂ + ...

numberOfVariables - One more than the dimension of the linear object function (or equivalently one more than the number of independent variables). This variables is just the length of the array parameter coefficients.

inequalityConstraints - A two-dimensional array containing the coefficients of the inequalities where every array corresponds to another inequality encoded in accordance with the above notes.

numberOfInequalities - The number of inequalities used by the linear programming problem.

equalityConstraints - A two-dimensional array containing the coefficients of the equalities where every array corresponds to another equality encoded in accordance with the above notes.

numberOfEqualities - The number of equalities used by the linear programming problem.

Returns:

The coordinates of the location of the extremum (i.e. minimum or maximum) of the linear programming problem. That is, a point in N-dimensional space returned as an array of doubles where the first term of the array corresponds to the first coordinate, the second term to the second coordinate and so on.

Throws:

LinearProgrammingException - thrown if either the region given by the constraints is empty or if the function is unbounded on the region.

See Also:

This method also implements the same Kunzi-Tzschach-Zehnder simplex algorithm except that here we do not need to specify the number of variables, inequalities and equalities.

functionValue

public double functionValue(double[] coefficients,
                            double[] coordinateValues)

Returns the value of the linear programming object function at the given coordinate values. The object function is described by its coefficients (see multiLinearSimplex).

The linear (programming) object functions f can be written in the following form:

f(x₁, x₂, ..., x_N) = coefficients₁ * x₁ + coefficients₂ * x₂ + ... + coefficients_N * x_N, where N is the number of variables considered, coefficients_i are the set of coefficients of the linear function and x₁,...,x_N are the coordinates (i.e. the degrees of freedom of the problem) of the solution set over which a point where a maximum of the linear function is sought.

Parameters:

coefficients - The coefficients of the linear objective function f, where f(x₁, x₂, ...) = coefficients₁ * x₁ + coefficients₂ * x₂ + ...

coordinateValues - The N-dimensional point x₁, x₂, ..., x_N where the function will be evaluated. The number of coordinate values must match the number of coefficients.

Returns:

The value of the object function at the given coordinates.

solutionSlack

public double[] solutionSlack(double[][] inequalities,
                              double[] multiSimplexSolution)

Provides information about the `tightness' of each inequality with respect to the results provided by the multiLinearSimplex(ExtremumTypes, double[], double[][], double[][]), or multiLinearSimplex(ExtremumTypes, double[], int, double[][], int, double[][], int) multi simplex methods. For this method to be able to return the `tightness' of the inequality constraints it requires to know the location of the extremum (i.e. minimum or maximum) found and the inequalities for the corresponding linear programming problem. Once this information is provided (via parameters) this method will return an array of the the distances from the `boundary' defined by each inequality to the point where the extremum was found.

Further Explanation and Description of possible applications

All inequalities take the following form:

c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b >= 0

Let's assume that this inequality is a constraint of a linear programming problem for which the solution is xi = ai for all i. Now for this particular inequality there will exist some real number say d such that:

c₁ * a₁ + c₂ * a₂ + ... + c_N * a_N + b + d = 0

In the language used above the constant d is the distance from the `boundary' for the considered inequality. If this inequality is the ith inequality within the set of inequalities then the constant d will be the ith element of the array returned by this method.

The value of knowing whether a given parameter is tight or not, and moreover being able to measure the exact `distance' from the boundary (in the above sense), is that we are able to move the boundaries which are not tight in and still ensure that for the resulting linear programming problem will have an extremum (i.e. maximum or minimum) at the same point and of the same value. To given a precise meaning to the term `move in the boundaries'; for the problem described above we are able to replace the original inequality with the condition that:

c₁ * a₁ + c₂ * a₂ + ... + c_N * a_N + b + d >= 0

By performing such analysis for each of the inequalities we are able to see which constraints can be varied (i.e. moved in) and by how much.

Remark: It is a general property of all linear programming problems that the extremum (i.e. maximum or minimum) will always lie on the boundary. Therefore, at least one of the constraints will be tight.

Application to the Factory Example

If us consider the Factory Example (see Factory Example description) where the Linear programming problem represents the production procedure of a factory with a certain product mix. In this instance the boundaries represent the restrictions on the means of production (such as the amount of a given material available etc), and the object function represents the profit from a given product mix. In this instance, by knowing the explicit amount the means of production (represented by a boundary) can be cut back without effecting the over-all profitability of the factory will allow the factory management to tie up less capital in the means of production whilst still achieving the same level of profitability. By cutting an these excess costs within the production procedure will increasing the factory's return on capital employed whilst keeping the profitability at the same level.

Parameters:

inequalities - The same two-dimensional array of inequalities used with the multi simplex method.

multiSimplexSolution - The array returned by the multi simplex method.

Returns:

An array of values, one value for every inequality, containing the distances of every inequality from zero.

sensitivityGrid

public double[][] sensitivityGrid(ExtremumTypes extremumType,
                                  double[] coefficients,
                                  double[][] inequalityConstraints,
                                  double[][] equalityConstraints,
                                  int noShiftsOfFirst,
                                  int noShiftsOfSecond,
                                  int middleIndexOfFirst,
                                  int middleIndexOfSecond,
                                  int firstSelectedIndex,
                                  int secondSelectedIndex,
                                  double percentageShiftOfFirst,
                                  double percentageShiftOfSecond)
                           throws LinearProgrammingException

Evaluates the sensitivity grid for a given Linear programming problem. In particular, we consider how the changes in the value of the extremum (i.e. minimum or maximum) varies when at most two of the coefficients of the linear object function are perturbed.

Remark: The nature of the sensitivity grid is described in finer detail within the PDF documentation. We advise that this API documentation should be used in conjunction with the PDF documentation.

The purpose of the sensitivity grid is to determine how the value of the extremum (i.e. minimum or maximum) of the given linear programming problem is effected by perturbations (i.e. shifts) of the two selected coefficients of the linear object function. This approach to sensitivity analysis allows the study of the stability of the solution to be studied when any two of the coefficients of the linear object function to be perturbed. Such sensitivity analysis is particularly appropriate in the following two instances:

• Investigating `what if scenarios' for the given business problem at hand.
• Establish stability of the extremum under perturbations of the coefficients. This is particularly useful when the coefficients (i.e. model input data) represent readings which are exposed to measurement errors.

Application to the Factory Example

In the case of the Factory Example (see Factory Example description) since the coefficients of the linear object function represent the profitability of the individual products, a sensitivity grid will allow us to see how the maximum profitability of the factory will vary as the level of profitability of two of its five products varies. By performing such analysis you will be able to understand how stable the profitability of the factory is to changes in the profitability of the individual products.

Notes on Coefficient and perturbation Selection

The selection of which particular coefficients to shift and the size and number of these shifts should be made with the particular business problem in mind. For example, your application may suggest certain appropriate combinations of coefficients and shift sizes for which the sensitivity grid will display valuable qualitative information. On the other hand you may wish to investigate a particular phenomenon which has been hypothesized, in which case your choices should reflect the given problem at hand.

Even if you do not have any a-priori idea as to what particular shifts to consider, by repeatedly applying the sensitivity grid approach you will be able to build up an intuition as to what shifts are most appropriate for which stability questions you are considering.

Sensitivity Grid applied to the factory example

Say the coefficients of the linear object function (of order five), evaluates the profit of the production of five different products and the constraints of the problem represent the physical limitations of the production procedure of the these products from the available resources. By finding the maximum of the object function we are actually finding the balance of the production procedure between the five products which results in the greatest profit.

Now if we consider the sensitivity grid in which the 1st and 2nd coefficients are shifted (i.e. the production levels of the first and second products) we are able to determine how the total maximum achievable profit will be effected if the balance between the 1st and 2nd manufactured products and the remaining three products is varied.

By performing such analysis you will not only be able to see if you production could be rebalanced so that the over-all profit level is increased by also whether a given product mix profit level is stable to unforeseen changes in the production level of each good.

Defining the Linear Programming Problem

The linear programming problem is passed to the method by specifying the array of coefficients of the linear object function and by using two 2-dimensional double arrays in order to describe the set of inequality and equality constraints which the solution of the linear programming problem must satisfy. Below we explicitly describe how a given linear programming problem, that is an object function together with a set of inequality and equality constraints can be mapped into the parameters which will be provided to the (simplex) method.

All linear (programming) object functions f can be written in the following form:

f(x₁, x₂, ..., x_N) = coefficients₁ * x₁ + coefficients₂ * x₂ + ... + coefficients_N * x_N, where N is the number of variables considered, coefficients_i are the set of coefficients of the linear function and x₁,...,x_N are the coordinates (i.e. the degrees of freedom of the problem) of the solution set over which a point where a extremum (i.e. maximum or minimum) of the linear function is sought.

The solution set is spanned by the coordinates x₁,...,x_Nx which are subject to a set of inequality and equality constraints. That is, the solution set over which an extremum is sought is any combination of coordinates which satisfies the given constraints. These inequality and equality constraints are supplied in the form of 2 dimensional double arrays, where each line of the 2 dimensional array corresponds to the coefficients within a linear equality or inequality constraint. That is, in order to express the following inequality:

c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b >= 0, you will need to supply a line within the two-dimensional array which contains the inequality constraints coefficients plus the constant b (i.e. the N + 1^th term), according to the following convention: {c₁, c₂, ..., c_N, b} For every inequality of the problem considered you will need to provide such an array within the inequality constraints two-dimensional array.

The equality constraints for the problem are expressed in a similar fashion to the inequality constraints, where the coefficients are listed in order followed by a real number. The equalities should be collected within a two-dimensional array in a similar way to the inequalities and passed as a parameter to the method. In particular, each equality is expressed in the following form: c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b = 0, for which you will need to provide the following array within the equality two-dimensional array:

{c₁, c₂, ..., c_N, b} For each of the equality constraints you will need to first encode then as an array in accordance with the above convention and then add the array to the equality constraints two-dimensional array.

Notes on the Sensitivity Grid's parameters and structure

Here we provide further explanation of the parameters which effect the construction of the sensitivity grid of a given linear programming problem. These parameters effect the number of elements of the 2-dimensional array, the `directions' in which the coefficients are shifted and the size of these shifts.

The dimensions of the sensitivity grid is noShiftsOfFirst by noShiftsOfSecond, where the noShiftsOfFirst is the number of shifts of the first selected coefficient and noShiftsOfSecond is the number of shifts of the second selected coefficients of the linear object function. The particular coefficients of the linear object function which are shifted are selected by the integer parameters firstSelectedIndex, secondSelectedIndex which correspond to the index of the coefficients of the linear object function. Please note that the indexing of these coefficients starts from 0, that is the 1st coefficient of the linear object function corresponds to 0, to 2nd coefficient to 1, and on on.

Note that the noShiftsOfFirst represents the `height' of the sensitivity grid and noShiftsOfSecond represents the `width' of the sensitivity grid, with respect to the returned 2 dimensional double array. When constructing the sensitivity grid it is necessary to assign a `middle cell' which corresponds to the given initial values of the coefficients of the linear object function. The middle cell will contain the value of the extremum of the given linear programming problem before the coefficients of the object function have been perturbed.

Remark: The returned sensitivity grid will have the property that for a given `row' only the second selected coefficient of the object function is varied, where as for a given `column' of the sensitivity grid only the first selected coefficient is varied.

Within this methods the sizes of the shifts are provided to the method as percentages of a selected coefficients default values. That is, the shifts are proportional to the absolute value of the default (middle cell) values of the two selected coefficients. The absolute size of each shift of the first selected coefficient is firstSelectedShift := percentageShiftOfFirst * abs(coefficients[firstSelectedIndex]), and correspondingly the size of each shift of the second selected coefficient is secondSelectedShift := percentageShiftOfSecond * abs(coefficients[secondSelectedIndex]), where abs is the absolute value. Therefore, if the object function under consideration is denoted by f, and x0 denotes the given values of the coefficients of the linear object function, then the (i,j)th' cell of the sensitivity grid is given by:

f(x0[0], x0[1], ... ,x0[firstSelectedIndex] + (i - middleIndexOfFirst) firstSelectedShift, ... ,x0[secondSelectedIndex] + (j - middleIndexOfSecond) * secondSelectedShift, ..., x0[n]).

Parameters:

extremumType - used to determine whether location of the minimum or maximum of the object function is found. If the minimum is required then input ExtremumTypes.MINIMUM, if the maximum is required then input ExtremumTypes.MAXIMUM.

coefficients - The coefficients of the linear object function f, where f(x₁, x₂, ...) = coefficients₁ * x₁ + coefficients₂ * x₂ + ...

inequalityConstraints - A two-dimensional array containing the coefficients of the inequalities, where each line corresponds to another inequality and contains the inequality coefficients of every variable and a constant value b as described above.

equalityConstraints - A two-dimensional array containing the coefficients of the equalities, where each line (i.e. array) corresponds to another equality and contains the equality coefficients of every variable and a constant value b as described above.

noShiftsOfFirst - The number of shifts (or perturbations) of the first coefficient selected considered within the sensitivity grid. This parameter also corresponds to the `height' of the sensitivity grid given by the returned 2 dimensional double array.

noShiftsOfSecond - The number of shifts (or perturbations) of the second coefficient selected considered within the sensitivity grid. This parameter also corresponds to the `width' of the sensitivity grid given by the returned 2 dimensional double array.

middleIndexOfFirst - The first coordinate of the grid cell which will contain the evaluation of extremum (i.e. maximum or minimum) of the linear programming problem for the default linear object function before any shifts of the coefficients has taken place. Note that the indexing of the sensitivity grid begins with 0.

middleIndexOfSecond - The second coordinate of the grid cell which will contain the evaluation at extremum (i.e. maximum or minimum) of the linear programming problem for the given linear object function before any shifts of the coefficients has taken place. Note that the indexing of the sensitivity grid begins with 0.

firstSelectedIndex - The index (beginning with 0) of the first coefficient of the linear (programming) object function which will be shifted.

secondSelectedIndex - The index (beginning with 0) of the second coefficient of the linear (programming) object function which will be shifted.

percentageShiftOfFirst - the amount as a percentage expressed in decimal format (i.e. 0.01 = 1 percent) of the initial given value of the first selected coefficient which is shifted between each `column' of the sensitivity grid. The size of each of these shifts in absolute terms is given by percentageShiftOfFirst * abs(initialPoint[firstSelectedIndex]).

percentageShiftOfSecond - the amount as a percentage expressed in decimal format (i.e. 0.01 = 1 percent) of the initial given value of the second selected coefficient which is shifted between each `row' of the sensitivity grid. The size of each of these shifts in absolute terms is given by percentageShiftOfSecond * abs(initialPoint[secondSelectedIndex]).

Returns:

a 2 dimensional double array representing the sensitivity grid of dimensions noShiftsOfFirst by noShiftsOfSecond.

Throws:

LinearProgrammingException - thrown if either the region given by the constraints is empty or if the function is unbounded on the region.

scenarioAnalysisCor

public double[] scenarioAnalysisCor(ExtremumTypes extremumType,
                                    double[] coefficients,
                                    double[][] inequalityConstraints,
                                    double[][] equalityConstraints,
                                    double[] percentageShiftsOfCoefficients,
                                    double[] shiftsOfInequalities,
                                    double[] shiftsOfEqualities)
                             throws LinearProgrammingException

Performs Scenario Analysis on a Linear programming problem by evaluating the location of the extremum (i.e. maximum or minimum) when the coefficients of the linear object function and the constraints are perturbed. In particular, this method returns the location of the extremum (i.e. maximum or minimum) of the given Linear Programming problem after one or both of the following has been performed:

1. The coefficients of the linear object function have been perturbed.
2. The constraints (or boundaries) of the linear programming function have been linearly shifted.

Overview of Scenario Testing

Scenario Analysis (also known as back testing) is another technique which allows a linear programming problem to be put under various stresses and to measure the implications in terms of the change in the location (and hence value) of the extremum of the object function. The advantage of Scenario Analysis (over Sensitivity Grids) is that it allows all (rather than only two) coefficients of the linear object function to be shifted and parallel shifts of the inequalities and equalities to be made and for the resulting effects on the location of the extremum to be recorded.

Remark: Further details concerning the application and use of Scenario Analysis is described within the accompanying PDF documentation.

Application to the Factory Example

In the case of the Factory Example (see Factory Example description) Scenario Analysis will allow you to see the effect of structural changes within the production procedure and market. For example, say there is a shortage of a particular `means of production' and because of a structural change in the market the profitability of a given product reduces. By applying a suitable parallel shift to the constraint which represents the `means of production' in shortage, and by making the appropriate change of the coefficient corresponding to the change in the profitability of a particular product. Through this method we are able to evaluate the product mix (i.e. location) which results in the greatest profit for the factor under the new business conditions.

Defining the Linear Programming Problem

The linear programming problem is passed to the method by specifying the array of coefficients of the linear object function and by using two 2-dimensional double arrays in order to describe the set of inequality and equality constraints which the solution of the linear programming problem must satisfy. Below we explicitly describe how a given linear programming problem, that is an object function together with a set of inequality and equality constraints can be mapped into the parameters which will be provided to the (simplex) method.

All linear (programming) object functions f can be written in the following form:

f(x₁, x₂, ..., x_N) = coefficients₁ * x₁ + coefficients₂ * x₂ + ... + coefficients_N * x_N, where N is the number of variables considered, coefficients_i are the set of coefficients of the linear function and x₁,...,x_N are the coordinates (i.e. the degrees of freedom of the problem) of the solution set over which a point where an extremum (i.e. minimum or maximum) of the linear function is sought.

The solution set is spanned by the coordinates x₁,...,x_Nx which are subject to a set of inequality and equality constraints. That is, the solution set over which an extremum is sought is any combination of coordinates which satisfies the given constraints. These inequality and equality constraints are supplied in the form of 2 dimensional double arrays, where each line of the 2 dimensional array corresponds to the coefficients within a linear equality or inequality constraint. That is, in order to express the following inequality:

c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b >= 0, you will need to supply a line within the two-dimensional array which contains the inequality constraints coefficients plus the constant b (i.e. the N + 1^th term), according to the following convention: {c₁, c₂, ..., c_N, b} For every inequality of the problem considered you will need to provide such an array within the inequality constraints two-dimensional array.

The equality constraints for the problem are expressed in a similar fashion to the inequality constraints, where the coefficients are listed in order followed by a real number. The equalities should be collected within a two-dimensional array in a similar way to the inequalities and passed as a parameter to the method. In particular, each equality is expressed in the following form: c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b = 0, for which you will need to provide the following array within the equality two-dimensional array:

{c₁, c₂, ..., c_N, b} For each of the equality constraints you will need to first encode then as an array in accordance with the above convention and then add the array to the equality constraints two-dimensional array.

Notes on the Scenario Analysis parameters

As mentioned above Scenario Analysis stresses the linear optimization problem by shifting one or both of the following:

1. Linear Object Function Coefficients Shifts - which are described by the array percentageShiftsOfCoefficients
2. Equality and Inequality Constraints Shift - for which the (parallel) inequality shifts are described by the array shiftsOfInequalities, and the (parallel) equality shifts are described by the array shiftsOfEqualities

Below be details the way in which a given set of shifts of the object function and constraints is described in terms of the methods parameters.

Object Function Coefficient Shifts: Within this methods the sizes of the shifts of the objects functions coefficients are provided to the method as percentages of a selected coefficients initial values. That is, the shifts are proportional to the absolute value of the (initial) values of the coefficients. The absolute size of each shift of the i-th coefficient is Absolute Shift size := percentageShift[i] * abs(coefficients[i]), where abs is the absolute value, percentageShift[i] is the i-th term of the parameter array percentageShiftsOfCoefficients and coefficients[i] is the i-th coefficient. By considering each of the coefficients shifts we are able to populate the parameter array percentageShiftsOfCoefficients.

Equality Constraint Shifts: A parallel shift of an equality constraint by `d', is equivalent to mapping the constraint:

c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b >= 0, into: c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b + d >= 0,

In accordance with the notes above concerning the construction of the 2-dimensional array equalityConstraints; representing the equality constraints, this parallel shifted equality constraint would be represented within the 2-dimensional array as:

{c₁, c₂, ..., c_N, b+d}

In order to construct the 2-dimensional array representing the set of shifted equality constraints we go through each of the constraints contained within the Linear programming problem and make the changes within the 2-dimensional array equalityConstraints, which correspond to the absolute shifts of the constant term for each of the equality constraints.

Inequality Constraint Shifts: A parallel shift of an inequality constraint by `d', is equivalent to mapping the constraint:

c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b > 0, into: c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b + d > 0,

In accordance with the notes above concerning the construction of the 2-dimensional array inequalityConstraints; representing the inequality constraints, this parallel shifted inequality constraint would be represented within the 2-dimension array as:

{c₁, c₂, ..., c_N, b+d}

In order to construct the 2-dimensional array representing the set of shifted inequality constraints we go through each of the constraints contained within the Linear programming problem and make the changes within the 2-dimensional array inequalityConstraints, which correspond to the absolute shifts of the constant term for each of the inequality constraints.

Parameters:

extremumType - used to determine whether location of the minimum or maximum of the object function is found. If the minimum is required then input ExtremumTypes.MINIMUM, if the maximum is required then input ExtremumTypes.MAXIMUM.

coefficients - The coefficients of the linear object function f, where f(x₁, x₂, ...) = coefficients₁ * x₁ + coefficients₂ * x₂ + ...

inequalityConstraints - A two-dimensional array containing the coefficients of the inequalities, where each line corresponds to another inequality and contains the inequality coefficients of every variable and a constant value b as described above.

equalityConstraints - A two-dimensional array containing the coefficients of the equalities, where each line (i.e. array) corresponds to another equality and contains the equality coefficients of every variable and a constant value b as described above.

percentageShiftsOfCoefficients - an array which represents the percentages shifts in decimal format (i.e. 1 percent = 0.01) of the coefficients of the linear object function. The first term of the array represents the percentage shift of the first coefficient, the second term the second coefficient and son on. Please note that if the coefficient is negative for example -100, then a shift of 2%, gives result in a coefficient of -102.

shiftsOfInequalities - this is an array which represents the absolute change of the constant terms within the inequalities, which corresponds to a parallel shift of each of the boundaries. Here the first terms of the array corresponds to the absolute change of the first inequalities constant term, the second term corresponds to the absolute change of the second constant term and on so.

shiftsOfEqualities - this is an array which represents the absolute change of the constant terms within the equalities, which corresponds to a parallel shift of each of the boundaries. Here the first terms of the array corresponds to the absolute change of the equalities constant term, the second term corresponds to the absolute change of the second constant term and so on.

Throws:

LinearProgrammingException - thrown if either the region given by the constraints is empty or if the function is unbounded on the region.

scenarioAnalysis

public double scenarioAnalysis(ExtremumTypes extremumType,
                               double[] coefficients,
                               double[][] inequalityConstraints,
                               double[][] equalityConstraints,
                               double[] percentageShiftsOfCoefficients,
                               double[] shiftsOfInequalities,
                               double[] shiftsOfEqualities)
                        throws LinearProgrammingException

Performs Scenario Analysis on a Linear programming problem by evaluating the value of the extremum (i.e. maximum or minimum) when the coefficients of the linear object function and the constraints are perturbed. In particular, this method returns the value of the extremum of the given Linear Programming problem after one or both of the following has been performed:

1. The coefficients of the linear object function have been perturbed.
2. The constraints (or boundaries) of the linear programming function have been linearly shifted.

Overview of Scenario Testing

Scenario Analysis (also known as back testing) is another technique which allows a linear programming problem to be put under various stresses and to measure the implications in terms of the change in the value of the extremum (i.e. minimum or maximum) of the object function. The advantage of Scenario Analysis (over Sensitivity Grids) is that it allows all (rather than only two) coefficients of the linear object function to be shifted and parallel shifts of the inequalities and equalities to be made and for the resulting effects on the extremum to be recorded.

Remark: Further details concerning the application and use of Scenario Analysis is described within the accompanying PDF documentation.

Application to the Factory Example

In the case of the Factory Example (see Factory Example description) Scenario Analysis will allow you to see the effect of structural changes within the production procedure and market. For example, say there is a shortage of a particular `means of production' and because of a structural change in the market the profitability of a given product reduces. By applying a suitable parallel shift to the constraint which represents the `means of production' in shortage, and by making the appropriate change of the coefficient corresponding to the change in the profitability of a particular product. Through this method we are able to evaluate the value of the maximum profit for the factor under the new business conditions.

Defining the Linear Programming Problem

The linear programming problem is passed to the method by specifying the array of coefficients of the linear object function and by using two 2-dimensional double arrays in order to describe the set of inequality and equality constraints which the solution of the linear programming problem must satisfy. Below we explicitly describe how a given linear programming problem, that is an object function together with a set of inequality and equality constraints can be mapped into the parameters which will be provided to the (simplex) method.

All linear (programming) object functions f can be written in the following form:

f(x₁, x₂, ..., x_N) = coefficients₁* x₁ + coefficients₂* x₂ + ... + coefficients_N* x_N, where N is the number of variables considered, coefficients_i are the set of coefficients of the linear function and x₁,...,x_N are the coordinates (i.e. the degrees of freedom of the problem) of the solution set over which a point where an extremum (i.e. maximum or minimum) of the linear function is sought.

The solution set is spanned by the coordinates x₁,...,x_Nx which are subject to a set of inequality and equality constraints. That is, the solution set over which an extremum is sought is any combination of coordinates which satisfies the given constraints. These inequality and equality constraints are supplied in the form of 2 dimensional double arrays, where each line of the 2 dimensional array corresponds to the coefficients within a linear equality or inequality constraint. That is, in order to express the following inequality:

c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b >= 0, you will need to supply a line within the two-dimensional array which contains the inequality constraints coefficients plus the constant b (i.e. the N + 1^th term), according to the following convention: {c₁, c₂, ..., c_N, b} For every inequality of the problem considered you will need to provide such an array within the inequality constraints two-dimensional array.

The equality constraints for the problem are expressed in a similar fashion to the inequality constraints, where the coefficients are listed in order followed by a real number. The equalities should be collected within a two-dimensional array in a similar way to the inequalities and passed as a parameter to the method. In particular, each equality is expressed in the following form: c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b = 0, for which you will need to provide the following array within the equality two-dimensional array:

{c₁, c₂, ..., c_N, b} For each of the equality constraints you will need to first encode then as an array in accordance with the above convention and then add the array to the equality constraints two-dimensional array.

Notes on the Scenario Analysis parameters

As mentioned above Scenario Analysis stresses the linear optimization problem by shifting one or both of the following:

1. Linear Object Function Coefficients Shifts - which are described by the array percentageShiftsOfCoefficients
2. Equality and Inequality Constraints Shift - for which the (parallel) inequality shifts are described by the array shiftsOfInequalities, and the (parallel) equality shifts are described by the array shiftsOfEqualities

Below be details the way in which a given set of shifts of the object function and constraints is described in terms of the methods parameters.

Object Function Coefficient Shifts: Within this methods the sizes of the shifts of the objects functions coefficients are provided to the method as percentages of a selected coefficients initial values. That is, the shifts are proportional to the absolute value of the (initial) values of the coefficients. The absolute size of each shift of the i-th coefficient is Absolute Shift size := percentageShift[i] * abs(coefficients[i]), where abs is the absolute value, percentageShift[i] is the i-th term of the parameter array percentageShiftsOfCoefficients and coefficients[i] is the i-th coefficient. By considering each of the coefficients shifts we are able to populate the parameter array percentageShiftsOfCoefficients.

Equality Constraint Shifts: A parallel shift of an equality constraint by `d', is equivalent to mapping the constraint:

c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b >= 0, into: c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b + d >= 0,

In accordance with the notes above concerning the construction of the 2-dimensional array equalityConstraints; representing the equality constraints, this parallel shifted equality constraint would be represented within the 2-dimensional array as:

{c₁, c₂, ..., c_N, b+d}

In order to construct the 2-dimensional array representing the set of shifted equality constraints we go through each of the constraints contained within the Linear programming problem and make the changes within the 2-dimensional array equalityConstraints, which correspond to the absolute shifts of the constant term for each of the equality constraints.

Inequality Constraint Shifts: A parallel shift of an inequality constraint by `d', is equivalent to mapping the constraint:

c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b > 0, into: c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b + d > 0,

In accordance with the notes above concerning the construction of the 2-dimensional array inequalityConstraints; representing the inequality constraints, this parallel shifted inequality constraint would be represented within the 2-dimension array as:

{c₁, c₂, ..., c_N, b+d}

In order to construct the 2-dimensional array representing the set of shifted inequality constraints we go through each of the constraints contained within the Linear programming problem and make the changes within the 2-dimensional array inequalityConstraints, which correspond to the absolute shifts of the constant term for each of the inequality constraints.

Parameters:

extremumType - used to determine whether location of the minimum or maximum of the object function is found. If the minimum is required then input ExtremumTypes.MINIMUM, if the maximum is required then input ExtremumTypes.MAXIMUM.

coefficients - The coefficients of the linear object function f, where f(x₁, x₂, ...) = coefficients₁ * x₁ + coefficients₂ * x₂ + ...

inequalityConstraints - A two-dimensional array containing the coefficients of the inequalities, where each line corresponds to another inequality and contains the inequality coefficients of every variable and a constant value b as described above.

equalityConstraints - A two-dimensional array containing the coefficients of the equalities, where each line (i.e. array) corresponds to another equality and contains the equality coefficients of every variable and a constant value b as described above.

percentageShiftsOfCoefficients - an array which represents the percentages shifts in decimal format (i.e. 1 percent = 0.01) of the coefficients of the linear object function. The first term of the array represents the percentage shift of the first coefficient, the second term the second coefficient and son on. Please note that if the coefficient is negative for example -100, then a shift of 2%, gives result in a coefficient of -102.

shiftsOfInequalities - this is an array which represents the absolute change of the constant terms within the inequalities, which corresponds to a parallel shift of each of the boundaries. Here the first terms of the array corresponds to the absolute change of the first inequalities constant term, the second term corresponds to the absolute change of the second constant term and on so.

shiftsOfEqualities - this is an array which represents the absolute change of the constant terms within the equalities, which corresponds to a parallel shift of each of the boundaries. Here the first terms of the array corresponds to the absolute change of the equalities constant term, the second term corresponds to the absolute change of the second constant term and so on.

Throws:

LinearProgrammingException - thrown if either the region given by the constraints is empty or if the function is unbounded on the region.

dualCoeff

public double[] dualCoeff(double[] coefficients,
                          double[][] inequalityConstraints,
                          double[][] equalityConstraints)
                   throws LinearProgrammingException

Evaluates the coefficients of the linear object function of the dual problem when the primal problem is given. Note that if the primal problem is a minimization (resp. maximization) problem then the dual problem will be a maximization (resp. minimization) problem.

Below we describe the convention under which the primal problem is passed to the method and give a motivation for the dual problem of the primal problem using the factory example.

Interpretation of the Dual Problem of the Factory Problem Example

In the case of the Factory Example (see Factory Example description) the transformation of the primal linear programming problem (i.e. the given problem) into its dual problem; corresponds essentially to viewing the same problem from another angle. More precisely, for our factory problem the primal problem is of the following form:

• Object function: Maximize ``Profit Function per unit cost''
• Constraints: Minimize ``Cost per unit of profit''

Then then dual problem will corresponding the viewing this problem as:

• Object function: Minimize ``Cost per unit of profit''
• Constraints: Maximize ``Profit Function per unit cost''

Though the above illustration is not literally true, in essence this is exactly the mapping which is taking place when the primal problem is mapped into its dual problem.

Defining the Primal Linear Programming Problem

The given linear programming problem known as the primal problem is passed to the method by specifying the array of coefficients of the linear object function and by using two 2-dimensional double arrays in order to describe the set of inequality and equality constraints which the solution of the linear programming problem must satisfy. Below we explicitly describe how a given linear programming problem, that is an object function together with a set of inequality and equality constraints can be mapped into the parameters which need to be provided to this method.

Though in order to evaluate the coefficients of the dual problems object function we do not required knowledge of the primal problems object function we show the template by which the primal problems object function is given is illustrate its familiarity with how the dual problems object function is returned (see notes below) and by implication its relationship to the duals function.

All linear (programming) object functions f can be written in the following form:

f(x₁, x₂, ..., x_N) = coefficients₁* x₁ + coefficients₂* x₂ + ... + coefficients_N* x_N, where N is the number of variables considered, coefficients_i are the set of coefficients of the linear function and x₁,...,x_N are the coordinates (i.e. the degrees of freedom of the problem) of the solution set over which a point where an extremum (i.e. minimum or maximum) of the linear function is sought.

The solution set is spanned by the coordinates x₁,...,x_Nx which are subject to a set of inequality and equality constraints. That is, the solution set over which an extremum is sought is any combination of coordinates which satisfies the given constraints. These inequality and equality constraints are supplied in the form of 2 dimensional double arrays, where each line of the 2 dimensional array corresponds to the coefficients within a linear equality or inequality constraint. That is, in order to express the following inequality:

c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b >= 0, you will need to supply a line within the two-dimensional array which contains the inequality constraints coefficients plus the constant b (i.e. the N + 1^th term), according to the following convention: {c₁, c₂, ..., c_N, b} For every inequality of the problem considered you will need to provide such an array within the inequality constraints two-dimensional array.

The equality constraints for the problem are expressed in a similar fashion to the inequality constraints, where the coefficients are listed in order followed by a real number. The equalities should be collected within a two-dimensional array in a similar way to the inequalities and passed as a parameter to the method. In particular, each equality is expressed in the following form: c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b = 0, for which you will need to provide the following array within the equality two-dimensional array:

{c₁, c₂, ..., c_N, b} For each of the equality constraints you will need to first encode then as an array in accordance with the above convention and then add the array to the equality constraints two-dimensional array.

When there are no equality or inequality constraints

If the considered primal linear programming problem does not have any equality or inequalities constraints then the corresponding 2-dimension array parameter should be given as either an empty array (i.e. {}) or as a NULL array.

Form of the Returned duals Object Function

The (returned) dual object function like the primal's object function (see notes above) is given as an array of its coefficients. This is possible since all dual problems object functions take the following form:

g(y₁, y₂, ..., y_M) = dualCoeff₁* y₁ + dualCoeff₂* y₂ + ... + dualCoeff_M* y_M, where `dualCoeff_i' are M real numbers where M is the number of constraints (inequality or equality) and the y_j's are the dual variables.

Parameters:

coefficients - The coefficients of the linear object function f of the primal problem, where f(x₁, x₂, ...) = coefficients₁ * x₁ + coefficients₂ * x₂ + ...

inequalityConstraints - A two-dimensional array containing the coefficients of the inequalities of the primal problem, where each line corresponds to another inequality and contains the inequality coefficients of every variable and a constant value b as described above.

equalityConstraints - A two-dimensional array containing the coefficients of the equalities of the primal problem, where each line (i.e. array) corresponds to another equality and contains the equality coefficients of every variable and a constant value b as described above.

Returns:

The coefficients of the object function of the dual problem of the given linear programming problem.

LinearProgrammingException

See Also:

Evaluates the inequality constraints of the dual problem when the primal problem is given., Evaluates the equality constraints of the dual problem when the primal problem is given.

dualInequal

public double[][] dualInequal(double[] coefficients,
                              double[][] inequalityConstraints,
                              double[][] equalityConstraints,
                              boolean[] positivity)
                       throws LinearProgrammingException

Evaluates the inequality constraints of the dual problem when the primal problem is given.

Interpretation of the Dual Problem of the Factory Problem Example

In the case of the Factory Example (see Factory Example description) the transformation of the primal linear programming problem (i.e. the given problem) into its dual problem; corresponds essentially to viewing the same problem from another angle. More precisely, for our factory problem the primal problem is of the following form:

• Object function: Maximize ``Profit Function per unit cost''
• Constraints: Minimize ``Cost per unit of profit''

Then then dual problem will corresponding the viewing this problem as:

• Object function: Minimize ``Cost per unit of profit''
• Constraints: Maximize ``Profit Function per unit cost''

Though the above illustration is not literally true, in essence this is exactly the mapping which is taking place when the primal problem is mapped into its dual problem.

Primary Constraints

The notion of the dual problem of a `linear programming problem' does not depend on the existence of the primary constraints. However it should also be noted that the primary constraints are required when `simplex based' algorithms are used to solve such problems. Here in the context of the dual problem we offer the most general implementation by allowing you to set, using the positivity parameters the coordinates for which the primary constraints (if any) will apply.

Remark: It may also be the case that the simplex algorithm can be applied to the dual problem but cannot be applied to the given primal problem. In such instances you may even be able to find the location of the primal problem if the location of the solution of the primal problem and the dual problem correspond.

Existence of Equalities in the Dual problem

Here we detail the nature of the application of duality to linear programming problems. We include this section in order to detail aspects of the application of duality to problems having linear constraints and a linear object function. In terms of purely understanding how to apply this component this section can be safely skipped.

The notion of the dual problem applies to broader situations than that of a linear programming problem. Even in the context of problems with linear constraints and a linear object function the notion of the dual problem does not require the requirement of `simplex type' algorithms (such as implemented in multiLinearSimplex) that the coordinate components of the solution are all positive; that is:

x_i >= 0, where {x_i} are the coordinate components of the primal problems solution. In order to be able to apply a simplex algorithm we will need to ensure that ALL coordinate components are positive. However, in the context of the dual problem it is not necessary that any of the coordinates are required to be positive. In fact, if we require that all the coordinates are positive then the dual problem will only have inequality constraints with no equality constraints even if the given primal problem has equality constraints. Moreover, if there exist n-coordinates for which the non-positivity conditions is not required to hold then the dual problem will have n equality constraints.

Defining the Primal Linear Programming Problem

The given linear programming problem known as the primal problem is passed to the method by specifying the array of coefficients of the linear object function and by using two 2-dimensional double arrays in order to describe the set of inequality and equality constraints which the solution of the linear programming problem must satisfy. Below we explicitly describe how a given linear programming problem, that is an object function together with a set of inequality and equality constraints can be mapped into the parameters which need to be provided to this method.

All linear (programming) object functions f can be written in the following form:

f(x₁, x₂, ..., x_N) = coefficients₁* x₁ + coefficients₂* x₂ + ... + coefficients_N* x_N, where N is the number of variables considered, coefficients_i are the set of coefficients of the linear function and x₁,...,x_N are the coordinates (i.e. the degrees of freedom of the problem) of the solution set over which a point where an extremum (i.e. maximum or minimum) of the linear function is sought.

The solution set is spanned by the coordinates x₁,...,x_Nx which are subject to a set of inequality and equality constraints. That is, the solution set over which an extremum is sought is any combination of coordinates which satisfies the given constraints. These inequality and equality constraints are supplied in the form of 2 dimensional double arrays, where each line of the 2 dimensional array corresponds to the coefficients within a linear equality or inequality constraint. That is, in order to express the following inequality:

c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b >= 0, you will need to supply a line within the two-dimensional array which contains the inequality constraints coefficients plus the constant b (i.e. the N + 1^th term), according to the following convention: {c₁, c₂, ..., c_N, b} For every inequality of the problem considered you will need to provide such an array within the inequality constraints two-dimensional array.

The equality constraints for the problem are expressed in a similar fashion to the inequality constraints, where the coefficients are listed in order followed by a real number. The equalities should be collected within a two-dimensional array in a similar way to the inequalities and passed as a parameter to the method. In particular, each equality is expressed in the following form: c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b = 0, for which you will need to provide the following array within the equality two-dimensional array:

{c₁, c₂, ..., c_N, b} For each of the equality constraints you will need to first encode then as an array in accordance with the above convention and then add the array to the equality constraints two-dimensional array.

When there are no equality or inequality constraints

If the considered primal linear programming problem does not have any equality or inequalities constraints then the corresponding 2-dimension array parameter should be given as an empty array (i.e. {}).

Form in which the Inequalities are returned

The inequality of the dual problem are returned in an identical fashion to how the inequalities of the primal problem are given (as shown above). That is, we will return an array of dimension 2, which represents the inequalities of the dual problem, where the k-th term of the array contains the terms:

{d₁, d₂, ..., d_M, e} containing the k-th inequality of the dual problem, that is: d₁ * y₁ + d₂ * y₂ + ... + d_M * y_M + e >= 0, where M is the dimension of the dual solution space and the y's are the dual variables of that space.

If there are no inequality constraints then this methods returns an empty array (i.e. {}).

Parameters:

coefficients - The coefficients of the linear object function f of the primal problem, where f(x₁, x₂, ...) = coefficients₁ * x₁ + coefficients₂ * x₂ + ...

inequalityConstraints - A two-dimensional array containing the coefficients of the inequalities of the primal problem, where each line corresponds to another inequality and contains the inequality coefficients of every variable and a constant value b as described above.

equalityConstraints - A two-dimensional array containing the coefficients of the equalities of the primal problem, where each line (i.e. array) corresponds to another equality and contains the equality coefficients of every variable and a constant value b as described above.

positivity - an array of boolean values (i.e. TRUE or FALSE) where the k-th term is true if the k-th basis element of the space over which the linear programming problem is considered has the requirement that it must be positive (as is the case with the so called primary constraints). Please note in the case of traditional linear programming problems where the primary constraints require that all coordinates of the solution are positive all terms of this array will be `TRUE'. Also, note that the length of this array will correspond to the number of coordinates (or dimensions) over which the problem is considered.

Returns:

this methods returns the inequality constraints of the dual problem as a array of dimension 2, in accordance with the above convention.

LinearProgrammingException

See Also:

Evaluates the coefficients of the linear object function of the dual problem when the primal problem is given., Evaluates the inequality constraints of the dual problem when the primal problem is given., Evaluates the equality constraints of the dual problem when the primal problem is given.

dualEqual

public double[][] dualEqual(double[] coefficients,
                            double[][] inequalityConstraints,
                            double[][] equalityConstraints,
                            boolean[] positivity)
                     throws LinearProgrammingException

Evaluates the equality constraints of the dual problem when the primal problem is given.

Interpretation of the Dual Problem of the Factory Problem Example

In the case of the Factory Example (see Factory Example description) the transformation of the primal linear programming problem (i.e. the given problem) into its dual problem; corresponds essentially to viewing the same problem from another angle. More precisely, for our factory problem the primal problem is of the following form:

• Object function: Maximize ``Profit Function per unit cost''
• Constraints: Minimize ``Cost per unit of profit''

Then then dual problem will corresponding the viewing this problem as:

• Object function: Minimize ``Cost per unit of profit''
• Constraints: Maximize ``Profit Function per unit cost''

Though the above illustration is not literally true, in essence this is exactly the mapping which is taking place when the primal problem is mapped into its dual problem.

Primary Constraints

The notion of the dual problem of a `linear programming problem' does not depend on the existence of the primary constraints. However it should also be noted that the primary constraints are required when `simplex based' algorithms are used to solve such problems. Here in the context of the dual problem we offer the most general implementation by allow you to set, using the positivity parameters the coordinates for which the primary constraints (if any) will apply.

Remark: It may also be the case that the simplex algorithm can be applied to the dual problem but cannot be applied to the given primal problem. In such instances you may even be able to find the location of the primal problem if the location of the solution of the primal problem and the dual problem correspond.

Existence of Equalities in the Dual problem

Here we detail the nature of the application of duality to linear programming problems. We include this section in order to detail aspects of the application of duality to problems having linear constraints and a linear object function. In terms of purely understanding how to apply this component this section can be safely skipped.

The notion of the dual problem applies to broader situations than that of a linear programming problem. Even in the context of problems with linear constraints and a linear object function the notion of the dual problem does not require the requirement of `simplex type' algorithms (such as implemented in multiLinearSimplex) that the coordinate components of the solution are all positive; that is:

x_i >= 0, where {x_i} are the coordinate components of the primal problems solution. In order to be able to apply a simplex algorithm we will need to ensure that ALL coordinate components are positive. However, in the context of the dual problem it is not necessary that any of the coordinates are required to be positive. In fact, if we require that all the coordinates are positive then the dual problem will only have inequality constraints with no equality constraints even if the given primal problem has equality constraints. Moreover, if there exist n-coordinates for which the non-positivity conditions is not required to hold then the dual problem will have n equality constraints.

Defining the Primal Linear Programming Problem

The given linear programming problem known as the primal problem is passed to the method by specifying the array of coefficients of the linear object function and by using two 2-dimensional double arrays in order to describe the set of inequality and equality constraints which the solution of the linear programming problem must satisfy. Below we explicitly describe how a given linear programming problem, that is an object function together with a set of inequality and equality constraints can be mapped into the parameters which need to be provided to this method.

All linear (programming) object functions f can be written in the following form:

f(x₁, x₂, ..., x_N) = coefficients₁* x₁ + coefficients₂* x₂ + ... + coefficients_N* x_N, where N is the number of variables considered, coefficients_i are the set of coefficients of the linear function and x₁,...,x_N are the coordinates (i.e. the degrees of freedom of the problem) of the solution set over which a point where an extremum (i.e. maximum or minimum) of the linear function is sought.

The solution set is spanned by the coordinates x₁,...,x_Nx which are subject to a set of inequality and equality constraints. That is, the solution set over which an extremum is sought is any combination of coordinates which satisfies the given constraints. These inequality and equality constraints are supplied in the form of 2 dimensional double arrays, where each line of the 2 dimensional array corresponds to the coefficients within a linear equality or inequality constraint. That is, in order to express the following inequality:

c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b >= 0, you will need to supply a line within the two-dimensional array which contains the inequality constraints coefficients plus the constant b (i.e. the N + 1^th term), according to the following convention: {c₁, c₂, ..., c_N, b} For every inequality of the problem considered you will need to provide such an array within the inequality constraints two-dimensional array.

The equality constraints for the problem are expressed in a similar fashion to the inequality constraints, where the coefficients are listed in order followed by a real number. The equalities should be collected within a two-dimensional array in a similar way to the inequalities and passed as a parameter to the method. In particular, each equality is expressed in the following form: c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b = 0, for which you will need to provide the following array within the equality two-dimensional array:

{c₁, c₂, ..., c_N, b} For each of the equality constraints you will need to first encode then as an array in accordance with the above convention and then add the array to the equality constraints two-dimensional array.

When there are no equality or inequality constraints

If the considered primal linear programming problem does not have any equality or inequalities constraints then the corresponding 2-dimension array parameter should be given as an empty array (i.e. {}).

Form in which the Equalities are returned

The equalities of the dual problem are returned in an identical fashion to how the equalities of the primal problem are given (as shown above). That is, we will return an array of dimension 2, which represents the equalities of the dual problem, where the k-th term of the array contains the terms:

{d₁, d₂, ..., d_M, e} containing the k-th equality of the dual problem, that is: d₁ * y₁ + d₂ * y₂ + ... + d_M * y_M + e = 0, where M is the dimension of the dual solution space and the y's are the dual variables of that space.

If there are no inequality constraints then this methods returns an empty array (i.e. {}).

Parameters:

coefficients - The coefficients of the linear object function f of the primal problem, where f(x₁, x₂, ...) = coefficients₁ * x₁ + coefficients₂ * x₂ + ...

inequalityConstraints - A two-dimensional array containing the coefficients of the inequalities of the primal problem, where each line corresponds to another inequality and contains the inequality coefficients of every variable and a constant value b as described above.

equalityConstraints - A two-dimensional array containing the coefficients of the equalities of the primal problem, where each line (i.e. array) corresponds to another equality and contains the equality coefficients of every variable and a constant value b as described above.

positivity - an array of boolean values (i.e. TRUE or FALSE) where the k-th term is true if the k-th basis element of the space over which the linear programming problem is considered has the requirement that it must be positive (as is the case with the so called primary constraints). Please note in the case of traditional linear programming problems where the primary constraints require that all coordinates of the solution are positive all terms of this array will be `TRUE'. Also, note that the length of this array will correspond to the number of coordinates (or dimensions) over which the problem is considered.

LinearProgrammingException

See Also:

Evaluates the coefficients of the linear object function of the dual problem when the primal problem is given., Evaluates the inequality constraints of the dual problem when the primal problem is given.

dualSolve

public double[] dualSolve(double[] coefficients,
                          double[][] inequalityConstraints,
                          double[][] equalityConstraints,
                          boolean[] positivity)
                   throws LinearProgrammingException

Applies the Kunzi-Tzschach-Zehnder Simplex algorithm to find the location of the solution of the dual problem when the primal problem is given. Please note that if in the primal problem we find the maximum (respec. minimum) then in the dual problem we are required to find the minimum (resp. maximum), over the domain for which the dual problem is considered.

Interpretation of the Dual Problem of the Factory Problem Example

In the case of the Factory Example (see Factory Example description) the transformation of the primal linear programming problem (i.e. the given problem) into its dual problem; corresponds essentially to viewing the same problem from another angle. More precisely, for our factory problem the primal problem is of the following form:

• Object function: Maximize ``Profit Function per unit cost''
• Constraints: Minimize ``Cost per unit of profit''

Then then dual problem will corresponding the viewing this problem as:

• Object function: Minimize ``Cost per unit of profit''
• Constraints: Maximize ``Profit Function per unit cost''

Though the above illustration is not literally true, in essence this is exactly the mapping which is taking place when the primal problem is mapped into its dual problem.

Primary Constraints

The notion of the dual problem of a `linear programming problem' does not depend on the existence of the primary constraints. However it should also be noted that the primary constraints are required when `simplex based' algorithms are used to solve such problems. Here in the context of the dual problem we offer the most general implementation by allow you to set, using the positivity parameters the coordinates for which the primary constraints (if any) will apply.

Remark: It may also be the case that the simplex algorithm can be applied to the dual problem but cannot be applied to the given primal problem. In such instances you may even be able to find the location of the primal problem if the location of the solution of the primal problem and the dual problem correspond.

Defining the Primal Linear Programming Problem

The given linear programming problem known as the primal problem is passed to the method by specifying the array of coefficients of the linear object function and by using two 2-dimensional double arrays in order to describe the set of inequality and equality constraints which the solution of the linear programming problem must satisfy. Below we explicitly describe how a given linear programming problem, that is an object function together with a set of inequality and equality constraints can be mapped into the parameters which need to be provided to this method.

All linear (programming) object functions f can be written in the following form:

f(x₁, x₂, ..., x_N) = coefficients₁* x₁ + coefficients₂* x₂ + ... + coefficients_N* x_N, where N is the number of variables considered, coefficients_i are the set of coefficients of the linear function and x₁,...,x_N are the coordinates (i.e. the degrees of freedom of the problem) of the solution set over which a point where an extremum (i.e. minimum or maximum) of the linear function is sought.

The solution set is spanned by the coordinates x₁,...,x_Nx which are subject to a set of inequality and equality constraints. That is, the solution set over which an extremum is sought is any combination of coordinates which satisfies the given constraints. These inequality and equality constraints are supplied in the form of 2 dimensional double arrays, where each line of the 2 dimensional array corresponds to the coefficients within a linear equality or inequality constraint. That is, in order to express the following inequality:

c₁ * x₁ + c₂ * x₂ + ... + c_N * x_N + b >= 0, you will need to supply a line within the two-dimensional array which contains the inequality constraints coefficients plus the constant b (i.e. the N + 1^th term), according to the following convention: {c₁, c₂, ..., c_N, b} For every inequality of the problem considered you will need to provide such an array within the inequality constraints two-dimensional array.

The equality constraints for the problem are expressed in a similar fashion to the inequality constraints, where the coefficients are listed in order followed by a real number. The equalities