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. MINIMUM or 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
MultiLinearSimplex - Returns the
location of the maximum or minimum of the linear programming problem.
MultiLinearSimplex - 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.
SolutionSlack - Once the solution is know the degree of
the slack within each of the inequalities can be recorded.
Sensitivity Analysis - General Framework
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.
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.
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
DualCoeff - Evaluates the coefficients on the linear object
function of the dual problem when the primal problem is given.
DualInequal - Evaluates the inequalities of the dual problem
when the primal problem is given.
DualEqual - Evaluates the equalities of the dual problem when
the primal problem is given.
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.
DualSensitivity - 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:
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...).
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.