LinearProgramming.DualEqual Method 

Evaluates the equality constraints 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

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

See Also

LinearProgramming Class | WebCab.COM.Math.Optimization.LinearProgramming Namespace | 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.

---