LinearProgramming.SensitivityGrid Method 

Evaluates the sensitivity grid for a given Linear programming problem.

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 MINIMUM, if the maximum is required then input 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]).

Return Value

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

Remarks

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]).

Exceptions

See Also

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

---