LinearProgramming.DualSolve Method 

Applies the Kunzi-Tzschach-Zehnder Simplex algorithm to find the location of the solution of the dual problem when the primal problem is given.

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.

Remarks

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 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. {}).

See Also

LinearProgramming Class | WebCab.COM.Math.Optimization.LinearProgramming Namespace

---