LINEAR PROGRAMMING

Introduction
Linear programming (LP) is a branch of mathematics dealing with methods for optimizing the
linear objective function of n independent decision variables subject to m constraints. It is
essentially a quantitative approach that consists of a sequence of steps that will lead to an optimal
solution. LP models are used to help make decisions in many different areas e.g. allocation of
scarce resources, assignment problems, transportation problems, etc. Successful applications of
LP also exist in areas of military, economics, industry, etc.

Situations that lead themselves to modeling using LP techniques are characterized by:
- a single objective / goal
- decision making under certainty
- decision variables
- restrictions to variables or constraints
- linear relationship among the variables
- non-negativity of the decision variables

There are two major LP techniques i.e. graphical LP and the simplex method.
The Graphical LP provides the visual picture of many of the important concepts of LP. However,
it is limited to problems that involve only two decision variables.

The Simplex method solves LP problems in iterations whereby the same computational steps are
repeated a number of times before the optimal solution is obtained. Successive improvements are
made in the iterations until an optimal solution is achieved. The simplex method can handle
problems with more than 2 decision variables making it more useful for solving real problems
which often involve a large number of variables.

LP model / problem formulation

This is the process of translating a statement of a problem into a mathematical statement. The
mathematical statement is referred to as the mathematical model. Developing an appropriate model
is an art that can only be mastered with practice and experience.
1
LP algorithms require that a single objective be specified. There are two main types of objectives
i.e. maximization and minimization e.g. cost minimization & profit maximization. The profit or
cost per unit of an output or input is summarized by an objective function.

Decision variables are the controllable inputs or outputs available to the decision maker i.e. they
represent choices available to the decision maker. For example, some problems involve choosing
a combination of inputs that will minimize cost while others involve choosing a combination of
outputs that will maximize profits.

Constraints are limitations that restrict the alternatives available to decision makers. There are
three types of constraints:
 - this implies an upper limit of the amount of scarce resources available for use
 - this implies the lower boundary that must be achieved
= - this implies an exact amount of the decision variable
The LP model can consist of one or more constraints. The constraints related to a given problem
define the set of all the feasible combinations of decision variables i.e. the feasible solution space.
The non-negativity aspect of LP means that decision variables can only take on positive values or
be equal to zero.

Example 1
Two products X and Y can be produced on a certain machine. There are 12 hours of machine time
available to produce these products. Product X requires 1 hour per unit and Y requires 3 hours per
unit. Both products require one raw material. Product X uses 4 pounds of the raw material per unit
and product Y uses 3 pounds. There are 24 pounds of this raw material available for the two
products.
If the objective is to maximize the profits from these products, and product X contributes $4 per
unit to profit while Y contributes $5 per unit, what quantity of each product should be produced?

Step 1: Identify the decision variable

Products X & Y
Step 2: Formulate the objective function

2
 Max π = 4X + 5Y
Step 3: Identify and formulate the constraints
Machine time X + 3Y  12
Raw material 4X + 3Y  24
Non-negativity X,Y  0
Step 4: The model
Max π = 4X + 5Y
Subject to
X + 3Y  12
4X + 3Y  24
X,Y  0

Example 2
KJ (U) Ltd owns a small paint factory that produces both interior and exterior house paints. Two
basic raw materials A and B are used to manufacture the paints. The maximum availability of A
is 6 tons a day and that of B is 8 tons a day. The daily requirements of the raw materials per ton of
interior and exterior paints are summarized below:

Raw material Tons of r/material per ton Maximum availability (tons)

Exterior Interior
A 1 2 6
B 2 1 8

A market survey has established that the daily demand for interior paint cannot exceed that of
exterior paint by more than 1 ton .The survey also shows that the maximum demand for interior
paint is limited to 2 tons daily.
The wholesale price per ton is $3,000 for exterior paint and $2,000 for interior paint.
How much exterior and interior paints should the company produce daily to maximize income?

Step 1: Identify the decision variables

X1 – Exterior paint, X2 – Interior paint

3
Step 2: Formulate the objective function
Max Y = 3000X1 + 2000X2
Step 3: Identify and formulate the constraints
Raw material A X1 + 2X2  6
Raw material B 2X1 + X2  8
Demand – excess of interior paint over exterior
X2 – X1  1
- maximum demand for interior paint
X2  2
Non-negativity X1, X2  0
Step 4: The model
Max Y = 3000X1 + 2000X2
subject to
X1 + 2X2  6
2X1 + X2  8
X2 – X1  1
X2  2
X1, X2  0

/* insert exercise*/

The Simplex Method (SM)

This is a general LP algorithm that is widely used to solve problems with more than 2 decision
variables. It employs an iterative method / process that starts at a feasible extreme point in the
solution space, normally the origin, and systematically moves from one feasible point to another
until the optimal point is eventually reached. This technique requires simple mathematical
operations but the computations are lengthy as well as tedious and the slightest error can lead to a
great deal of frustration.
Before applying the simplex method on an LP problem, the model must be transformed into a
standard form whose properties are:
- all constraints are equations with a non-negative right hand side

4
 - all the variables are non-negative
- the objective function may be a minimization or maximization type

A constraint of the type  (  ) can be converted to an equation by adding a slack variable to

(subtracting a slack variable from) the left hand side (LHS) of the constraints.
e.g. in the constraint X1 + 2X2  6, add a slack variable S1 such that
X1 + 2X2 + S1 = 6, S1  0
In the constraint 3X1 + 2X2  5, subtract S2 such that 3X1 + 2X2 - S2 = 5
The LHS of the equation can always be made non-negative by multiplying both sides by
-1. The direction of an inequality is reversed when both sides are multiplied by -1.
The maximization of a function f(x) is equivalent to the minimization of a function –f(x).

In general the standard LP model will include m equations and n unknowns where m<n. To
determine the extreme points for the standard LP model, set (n-m) variables to zero and then solve
for the remaining m variables. The mandatory requirement of (n-m) variables to be set to zero is
that the remaining variables have a unique non-negative solution. The unique solutions resulting
from setting (n-m) variables equal to zero are all basic solutions and the variables set to zero are
called non-basic variables. Each basic variable is associated with an iteration and the maximum
number of iterations in the simplex method can not exceed n C m

The simplex algorithm (SA)

The simplex technique involves generating a series of solutions that are in tabular form (the
tableaus). By inspecting each tableau, one can immediately tell if it represents an optimal solution
or not.
The steps of a simplex algorithm are as follows:
a) Using the standard form, determine a starting basic feasible solution by setting (n-m)
appropriate non-negative variables to zero.
b) Select an entering variable from among the current non-basic variables which when
increased above zero can improve the value of the objected variable. If none exists stop
and conclude that the current basic solution is over, otherwise go to step c.

5
 c) Select a leading variable from among the current basic variables that must be set to zero
i.e. become non-basic when the entering variable becomes basic.
d) Determine the new basic solution by making the entering variable basic and the leaving
variable non-basic.

Example
Consider the LP problem below
Max Z = 4X1 + 5X2
subject to
X1 + 3X2  12
4X1 + 3X2  24
X1, X2  0
Sln
Transform the problem into standard LP form by adding slack variables S1 and S2
Max Z = 4X1 + 5X2
subject to
X1 + 3X2 + S1 = 12
4X1 + 3X2 + S2 = 24
X1, X2, S1, S2  0
The slack variables are not given coefficients in the objective function because they do not produce
any contribution to the objective.
From above, S1 and S2 are basic & X1 and X2 are non-basic.

1st tableau
Basic Z X1 X2 S1 S2 sln
Z 1 4 5 0 0 0
S1 0 1 3 1 0 12
S2 0 4 3 0 1 24

6
The optimality condition
The entering variable in a maximization (minimization) problem is the non-basic variable having
the most positive (negative) coefficient in the Z-row. Ties are broken arbitrarily.
The optimum is reached at the iteration where all the Z-row coefficients of the non-basic variables
are negative (positive).

/*optimality condition helps in determining the entering variable*/

The feasibility condition

For both maximization and minimization problems, the leaving variable is the basic variable
associated with the smallest non-negative ratio and ties are broken arbitrarily.

/*feasibility condition helps in determining the leaving variable*/

In the example, to determine the entering variable, select the largest value in the Z-row. So, X2
will enter the basis (basic variable).
To determine the variable that will leave the basis, divide each positive coefficient in the column
of the entering variable (pivot column) into the corresponding solution.
i.e. 12/3 = 4, 24/3 =8
The smaller of the two ratios indicates the variable that will leave the basis. Thus, S 1 will leave
and be replaced by X2
Definition
The pivot equation is the row associated with the leaving variable.
The pivot element is the intersection of the pivot column and the pivot equation.

Determination of the new basic solution

After determining the entering variable and the leaving variable, the next tableau is obtained by
applying the Gauss-Jordan computations.
The computations effect a change in the basis by carrying out appropriate computations on the
pivot equation and the rest of the equations. These computations are of two types:
i) Pivot row
New pivot row = Current pivot row / Pivot element

7
ii) All other rows, including the Z-row
New row = (Current row) - [(its pivot column coefficient) * (New pivot row)]
Applying the computations to the example,
2nd tableau

Basic Z X1 X2 S1 S2 sln
Z 1 7/3 0 -5/3 0 -20
X2 0 1/3 1 1/3 0 4
S2 0 3 0 -1 1 12
The third tableau is developed in the same way as the previous one i.e.
-determine the entering variable in the column with the largest positive value in the Z-row i.e. X1
-determine the leaving variable by dividing the solution in each row by the corresponding

coefficient in the pivot column i.e. 4 = 12 and 12 =4

1/ 3 3
The smallest ratio indicates the leaving variable i.e. S2
-divide each value in the row of the leaving variable by the pivot element to obtain the new main
row values.
-compute values for the X2 row i.e. multiply each new main row value by the X2 row pivot value
i.e. 1/3 and subtract from the corresponding current values.
-compute the new Z-row values.

3rd tableau
Basic Z X1 X2 S1 S2 sln
Z 1 0 0 -8/9 -7/9 88/3
X2 0 0 1 4/9 -1/9 8/3
X1 0 1 0 -1/3 1/3 4

In this tableau, all the non-basic variables have negative coefficients in the Z-row, hence optimality
has been reached.
The optimal values are X1 = 4, X2 = 8/3 and Z = 88/3

Exercise

8
Solve the LP problem below using the simplex algorithm
Max Y = 3X1 + 2X2
subject to
X1 + 2X2  6
2X1 + X2  8
X2 – X1  1
X2  2
X1, X2  0

Sensitivity Analysis
A decision maker is more than interested in the immediate solution to a problem. He would want
to know how sensitive the optimal solution would be to changes in the value of one or more of the
parameters in the problem. If the solution is sensitive to such changes, the decision maker will
want to obtain more precise estimates of the suspect parameters.
Sensitivity analysis is carried out after the optimal solution of an LP model is obtained. The goal
is to determine whether changes in the model’s coefficients will leave the solution unchanged and
if not how a new optimum (assuming it exists) can be obtained efficiently. Much of the information
needed to de sensitivity analysis is contained in the final optimal tableau.

Consider the JK (U) ltd problem

Max Y = 3X1 + 2X2
subject to
X1 + 2X2  6
2X1 + X2  8
X2 – X1  1
X2  2
X1, X2  0
solved to:

9
Basic Z X1 X2 S1 S2 S3 S4 sln
Z 1 0 0 1/3 4/3 0 0 38/3
X2 0 0 1 2/3 -1/3 0 0 4/3
X1 0 1 0 -1/3 2/3 0 0 10/3
S3 0 0 0 -1 1 1 0 3
S4 0 0 0 -2/3 1/3 0 1 2/3

Status of the resources

Considering the final tableau and by observing the values of the slack variables, we obtain the
following:

Resource Slack Status

Raw material A S1 = 0 scarce
Raw material B S2 = 0 scarce
Limit in excess of X2 S3 = 3 abundant
Limit in demand of X2 S4 = 2/3 abundant

A positive slack means that the resource is not used up completely i.e. it is abundant while a zero
slack indicates that the entire amount of the resource is consumed by the activities in the model.
Any increase in the maximum limit of the abundant resources will simply make them more
abundant without affecting the optimum solution. Therefore raw materials A and B that are scarce
can be increased for the purpose of improving the solution.

Unit worth of the resources

A unit worth of a resource is the rate of improvement in the optimum value as a result of a unit
increases in the available amount of that resource. Consider the optimum tableau in the example
and observe the coefficients in the Z-row under the starting basic variables i.e. S1, S2, S3, S4. The
unit worth of raw material A is 1/3 implying that 1/3 units are added to Z per additional ton of raw
material A. Likewise the unit worth of B is 4/3 implying that 4/3 units are added to Z per additional
ton of raw material B.
The unit worth is sometimes referred to as the shadow price / imputed price / dual price.

10
Maximum change in resource availability
Consider changing the first resource by the amount  1 meaning that the availability of raw

material A is now 6+  1 tons. Add  1 to the right hand side of the first constraint in the starting
tableau and solve for the optimum solution. It will be noticed that the change will affect only the
right hand side of each iteration. The changes in the right hand side resulting from  1 can be
obtained directly from the successive tableaus as follows:
-get the constant components exactly equal to the right hand side of the iteration before  1 is
added.
-add a linear term in  1 whose coefficient is that under S1 in the same iteration.

RHS elements in iteration

Ego 0 (starting) 1 2 (optimum)

Z 0 12 12 2 + 1 1
3 3

1 6+  1 2+  1 4 + 2 1
3 3

2 8 4 10 - 1 1
3 3
3 1 5 3 - 1 1

4 2 2 2 - 2 1
3 3

We use the coefficients of S1 because it is uniquely associated with the first constraint where a
change has been effected. Thus, for the RHS changes in 2nd, 3rd and 4th constraints use the
coefficients of S2, S3, and S4 respectively.
A change in the available resource means that the feasibility of the solution is affected.
Thus,  1 should not be changed in such a way that any of the basic variables will be negative.

This means that  1 must be restricted to the range that will maintain the non-negativity of the
RHS of the constraint equations in the optimal tableau i.e.

X1: 10 - 1  1  0 …………………..(i)
3 3

11
X2: 4 + 2  1  0 ……………………(ii)
3 3
S3: 3 - 1  1  0 ………………………….(iii)

S4: 2 - 2  1  0 …………………….(iv)
3 3

To determine the possible range for  1 consider two cases

Case I:  1 >0

Relation (ii) is always satisfied for  1 >0. Relations (i), (iii) and (iv) produce  1  10,  1

 3 and  1  1 respectively. Thus, all relations are satisfied for  1  1

Case II:  1 <0

Relations (i), (iii) and (iv) are always satisfied where as (ii) yields the limit
 1  -2.
By combining cases I & II we find that -2   1  1 will always result in a feasible solution.

12