Introduction to Linear Programming

By:
Dr. Richard Tuyiragize
Mob: +256 775 115365
Email: [Link]@[Link]
[Link] 1
Introduction
• Mathematical programming is used to find the best or optimal
solution to a problem that requires a decision or set of decisions
about how best to use a set of limited resources to achieve a state
goal of objectives.
• Steps involved in mathematical programming
• Conversion of stated problem into a mathematical model that abstracts all the
essential elements of the problem.
• Exploration of different solutions of the problem.
• Finding out the most suitable or optimum solution.

• Linear programming requires that all the mathematical functions in

the model be linear functions.

[Link] 2
Requirements of a LP problem
1 Must seek to maximize or minimize some quantity (the objective
function)

2 Presence of restrictions or constraints - limits ability to achieve

objective

3 Must be alternative courses of action from which to choose

4 Objectives and constraints must be expressible as linear equations or

inequalities
The Linear Programming Model
Let: X1, X2, X3, ………, Xn = decision variables
Z = Objective function or linear function
Requirement: Maximization of the linear function Z.
Z = c1X1 + c2X2 + c3X3 + ………+ cnXn …..Eq (1)
subject to the following constraints:

…..Eq (2)

where aij, bi, and cj are given constants.

[Link] 4
 The Linear Programming Model Cont’d
The linear programming model can be written in more efficient
notation as:

…..Eq (3)

The decision variables, xI, x2, ..., xn, represent levels of n competing activities.
[Link] 5
 Examples of LP Problems
1. A Product Mix Problem

• A manufacturer has fixed amounts of different resources such as raw

material, labor, and equipment.
• These resources can be combined to produce any one of several
different products.
• The quantity of the ith resource required to produce one unit of the jth
product is known.
• The decision maker wishes to produce the combination of products
that will maximize total income.

[Link] 6
 Examples of LP Problems Cont’d
2. A Blending Problem

• Blending problems refer to situations in which a number of

components (or commodities) are mixed together to yield one or
more products.
• Typically, different commodities are to be purchased. Each commodity
has known characteristics and costs.
• The problem is to determine how much of each commodity should be
purchased and blended with the rest so that the characteristics of the
mixture lie within specified bounds and the total cost is minimized.

[Link] 7
 Examples of LP Problems Cont’d
3. A Production Scheduling Problem

• A manufacturer knows that he must supply a given number of items

of a certain product each month for the next n months.
• They can be produced either in regular time, subject to a maximum
each month, or in overtime. The cost of producing an item during
overtime is greater than during regular time. A storage cost is
associated with each item not sold at the end of the month.
• The problem is to determine the production schedule that minimizes
the sum of production and storage costs.

[Link] 8
 Examples of LP Problems Cont’d
4. A Transportation Problem

• A product is to be shipped in the amounts al, a2, ..., am from m

shipping origins and received in amounts bl, b2, ..., bn at each of n
shipping destinations.
• The cost of shipping a unit from the ith origin to the jth destination is
known for all combinations of origins and destinations.
• The problem is to determine the amount to be shipped from each
origin to each destination such that the total cost of transportation is
a minimum.

[Link] 9
 Examples of LP Problems Cont’d
5. A Flow Capacity Problem

• One or more commodities (e.g., traffic, water, information, cash, etc.)

are flowing from one point to another through a network whose
branches have various constraints and flow capacities.
• The direction of flow in each branch and the capacity of each branch
are known.
• The problem is to determine the maximum flow, or capacity of the
network.
The variety of situations to which linear programming has been applied
ranges from agriculture to zinc smelting.
[Link] 10
Developing LP Model
Steps Involved:
• Determine the objective of the problem and describe it by
a criterion function in terms of the decision variables.
• Find out the constraints.
• Do the analysis which should lead to the selection of
values for the decision variables that optimize the
criterion function while satisfying all the constraints
imposed on the problem.

[Link] 11
 Developing LP Model Cont’d
Example: Product Mix Problem
The [Link] Company produces two products: I and II. The raw material requirements,
space needed for storage, production rates, and selling prices for these products are given
in Table 1.

The total amount of raw material available per day for both products is 15751b. The total
storage space for all products is 1500 ft2, and a maximum of 7 hours per day can be used
for production.
[Link] 12
 Developing LP Model Cont’d
Example Problem
• All products manufactured are shipped out of the storage area at the end of the day.
Therefore, the two products must share the total raw material, storage space, and
production time. The company wants to determine how many units of each product
to produce per day to maximize its total income.

Solution
• The company has decided that it wants to maximize its sale income, which depends on
the number of units of product I and II that it produces.
• Therefore, the decision variables, x1 and x2 can be the number of units of products I and
II, respectively, produced per day.

[Link] 13
Developing LP Model Cont’d
• The object is to maximize the equation:
Z = 13x1 + 11x2
subject to the constraints on storage space, raw materials, and production time.

• Each unit of product I requires 4 ft2 of storage space and each unit of product II requires
5 ft2. Thus a total of 4x1 + 5x2 ft2 of storage space is needed each day. This space must
be less than or equal to the available storage space, which is 1500 ft2. Therefore,
4X1 + 5X2  1500

• Similarly, each unit of product I and II produced requires 5 and 3 Ibs, respectively, of raw
material. Hence a total of 5xl + 3x2 Ib of raw material is used.

[Link] 14
Developing LP Model Cont’d
• This must be less than or equal to the total amount of raw material available, which is
1575 Ib. Therefore,
5x1 + 3x2  1575

• Product I can be produced at the rate of 60 units per hour. Therefore, it must take I
minute or 1/60 of an hour to produce I unit. Similarly, it requires 1/30 of an hour to
produce 1 unit of product II. Hence a total of x1/60 + x2/30 hours is required for the daily
production. This quantity must be less than or equal to the total production time available
each day. Therefore,
x1 / 60 + x2 / 30  7
or x1 + 2x2  420

• Finally, the company cannot produce a negative quantity of any product, therefore x1 and
x2 must each be greater than or equal to zero.

[Link] 15
Developing LP Model Cont’d
The linear programming model for this example can be summarized as:

…..Eq (4)

[Link] 16
Graphical Solution to LP Problems

[Link] 17
Graphical Solution to LP Problems Cont’d
• An equation of the form 4x1 + 5x2 = 1500 defines a straight line in the x1-x2 plane. An
inequality defines an area bounded by a straight line. Therefore, the region below and
including the line 4x1 + 5x2 = 1500 in the Figure represents the region defined by 4x1 +
5x2  1500.
• Same thing applies to other equations as well.
• The shaded area of the figure comprises the area common to all the regions defined by
the constraints and contains all pairs of xI and x2 that are feasible solutions to the
problem.
• This area is known as the feasible region or feasible solution space. The optimal solution
must lie within this region.
• There are various pairs of x1 and x2 that satisfy the constraints such as:

[Link] 18
Graphical Solution to LP Problems Cont’d
• Trying different solutions, the optimal solution will be:
X1 = 270
X2 = 75
• This indicates that maximum income of $4335 is obtained by producing 270 units of
product I and 75 units of product II.

• In this solution, all the raw material and available time are used, because the optimal
point lies on the two constraint lines for these resources.

• However, 1500- [4(270) + 5(75)], or 45 ft2 of storage space, is not used. Thus the storage
space is not a constraint on the optimal solution; that is, more products could be
produced before the company ran out of storage space. Thus this constraint is said to be
slack.

[Link] 19
Summary of the Graphical Method
• Draw the constraint boundary line for each constraint. Use the origin (or any point not on
the line) to determine which side of the line is permitted by the constraint.
• Find the feasible region by determining where all constraints are satisfied simultaneously.
• Determine the slope of one objective function line (iso-line). All other objective function
lines will have the same slope.
• Move a straight edge with this slope through the feasible region in the direction of
improving values of the objective function. Stop at the last instant that the straight edge
still passes through a point in the feasible region. This line given by the straight edge is
the optimal objective function line.
• A feasible point on the optimal objective function line is an optimal solution.
Further Reading:

[Link] 20
The Simplex Method
• When decision variables are more than 2, it is always advisable to use
Simplex Method to avoid lengthy graphical procedure.

• The simplex method is not used to examine all the feasible solutions.

• It deals only with a small and unique set of feasible solutions, the set of
vertex points (i.e., extreme points) of the convex feasible space that
contains the optimal solution.

[Link] 21
The Simplex Method Cont’d
Steps involved:
1. Locate an extreme point of the feasible region.
2. Examine each boundary edge intersecting at this point to see
whether movement along any edge increases the value of the
objective function.
3. If the value of the objective function increases along any edge, move
along this edge to the adjacent extreme point. If several edges
indicate improvement, the edge providing the greatest rate of
increase is selected.
4. Repeat steps 2 and 3 until movement along any edge no longer
increases the value of the objective function.

[Link] 22
 The Simplex Method Cont’d
Example: Product Mix Problem
The N. Dustrious Company produces two products: I and II. The raw material requirements,
space needed for storage, production rates, and selling prices for these products are given
below:

The total amount of raw material available per day for both products is 15751b. The total
storage space for all products is 1500 ft2, and a maximum of 7 hours per day can be used
for production. The company wants to determine how many units of each product to
produce per day to maximize its total income.

[Link] 23
 The Simplex Method Cont’d
Solution

❖ Step 1: Convert all the inequality constraints into equalities by the use of slack
variables. Let:

As already developed, the LP model is:

…..Eq (4)

[Link] 24
The Simplex Method Cont’d
Optimality condition: The entering variable in a maximization (Minimization)
problem is the non basic variable having the most negative (positive) 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 nonnegative (nonpositive)
Feasibility condition: For both the maximization and minimization problems, the
leaving variable is the basic variable associated with the smallest nonnegative
ratio (with strictly positive denominator). Ties are broken arbitrarily.
Gauss-Jordan operations
1. Pivot row
• Replace the leaving variable in the basic column with the entering variable
• New pivot row = current pivot row ÷ pivot element
2. All other rows, including z
• New row = (Current row) – (pivot column coefficient) x (New pivot row)

[Link] 25
The Simplex Method Cont’d
Summary steps of the simplex method
1. Determine a staring basic feasible solution
2. Select an entering variable using the optimality condition. Stop if there
is no entering variable; the last solution is optimal; Else, go to Step 3
3. Select a leaving variable using the feasibility condition
4. Determine the new basic solution by using the appropriate Gauss Jordan
computations. Go to step 2

Reading material
Taha A. Hamdy (2007) 8th edition, Chapter 3

[Link] 26
 Simplex Tableau
❖ Step I: Set up the initial tableau

In any
iteration, a
variable that
has a
nonzero
value in the
solution is
called a
basic
variable.

[Link] 27
Simplex Tableau Cont’d

[Link] 28
Solution
The simplex solution yields the optimum production program for N.
Dustrious Company.
➢ The company can maximize its sale income to $4335 by producing
270 units of product I and 75 units of product II.

➢ There will be no surplus of raw materials or production time.

➢ But there will be 45 units of unused storage space.

[Link] 29
Further reading:
1. Illustrative example (File attachment)
2. Hillier, F. S. and Lieberman G (2001) Chapter 4, page 123

[Link] 30
Sensitivity Analysis
❖ Sensitivity analysis helps to test the sensitivity of the optimum solution with
respect to changes of the coefficients in the objective function, coefficients in the
constraints inequalities, or the constant terms in the constraints.
❖ For Example in the case study discussed:
➢ The actual selling prices (or market values) of the two products may vary from time
to time. Over what ranges can these prices change without affecting the optimality of
the present solution?
➢ Will the present solution remain the optimum solution if the amount of raw materials,
production time, or storage space is suddenly changed because of shortages,
machine failures, or other events?
➢ The amount of each type of resources needed to produce one unit of each type of
product can be either increased or decreased slightly. Will such changes affect the
optimal solution ?

[Link] 31
Marginal Values of Additional Resources
❖ The critical questions are:
➢ What is the income value (or marginal value) of each additional unit of each type of
❖ Theresources?
critical questions are:
➢ What is the income
maximum value
cost(or marginal
( or value)
marginal cost)of each
that additional
they should beunit of each
willing typeforof
to pay
resources?
each additional unit of resources?
➢ What is
❖ Answers to the maximum
these questionscost
can( or
bemarginal
obtainedcost)
fromthat
the they should
objective be willing
function to last
in the pay for
each additional unit of resources?
tableau of the simplex solution:
❖ Answers to these questions can be obtained from the objective function in the last
tableau of the simplex solution:

[Link] 32
Marginal Values of Additional Resources Cont’d
❖ Because S1, S2 and S3 represent surplus resources, the negatives of these
variables (i.e., -S1, -S2, -S3) represent additional units of these resources that
can be made available.
❖ The income values (or marginal values of additional units of these resources can
be obtained by taking the partial derivatives of Z with respect to -S1, -S2 and -S3.
❖ Therefore, the marginal value of one additional unit of:

[Link] 33
Marginal Values of Additional Resources Cont’d
❖ Thus, the marginal values of additional units of resources can be obtained
directly from the coefficients of the objective function in the last tableau of a
simplex solution.

❖ The N. Dustrious Company should be willing to pay up to $15/7 for an additional

unit of raw materials and $16/7 for an additional unit of production time.

❖ If the actual cost of an additional unit (i.e., marginal cost) of these resources are
smaller than the marginal value, the company should be able to increase its
income by increasing production.

❖ The marginal values above are valid, however, only as long as there is surplus
storage space available.

[Link] 34
Further reading:
1. Hamdy, A. Taha (2005). Chapter 3, Section 3.6. Pages 123 – 150

[Link] 35
Special cases on LP solutions- Infeasibility

• The feasible region is empty

• That is, no solution satisfies
the constraints (i.e., there is
no feasible solution)
• So, no optimal solution exists

[Link] 36
Special cases on LP solutions-– Unique solution

• The feasible region is not

empty
• All of the points in the
feasible region are feasible
solutions
• But we have a single optimal
solution
[Link] 37
Special cases on LP solutions-– Alternative optima

• The feasible region is not

empty
• There are many feasible
solutions
• Also, there are many optimal
solutions
• but still there are corner points
that are also optimum!
[Link] 38
Special cases on LP solutions-– Unboundedness

• The feasible region is

unbounded and
• You can increase the
objective function value
as much as you can while
you are still in the feasible
region
• Unbounded feasible region
does not mean
unboundedness of LP
[Link] 39
Software for solving LPs
• There are many software for solving LPs

• They mostly use Simplex type of algorithms

• We will learn how to solve simple LPs in Excel
• Excel solver uses Simplex Algorithm

• Other software
• CPLEX (one of the best solvers for LPs)
• TORA
• Matlab has a function to solve LPs (linprog)
• Optimization software can solve LPs (GAMS, Xpress, Lindo, Lingo, AMPL)

[Link] 40