LESSON 2: LINEAR PROGRAMMING

1 Introduction
Many problems in business and economics are concerned essentially with the allocation of
limited/scarce resources (money personnel materials, space, time) in order to maximize some
measure of performance or minimize some measure of cost.

The mathematical techniques for determining such allocations are referred to as mathematical
programming. Examples include: linear programming, dynamic programming, integer
programming, quadratic programming, and goal programming.

Linear Programming therefore, is a special case of mathematical programming in which the

measure of performance or cost is a linear functions and the restrictions or the availability or
utilization of resources are expressed as linear equations of inequalities.

Definition:
Linear programming is a mathematical technique concerned with the allocation of scarce (or
limited) resources. It is a procedure to optimizes the value of some objective (for example,
maximum profit or minimum cost) when the factors involved (for example, labour or machine
hours) are subject to some constraints (for example, only 1000 labour hours are available in a
week).

Requirements:
 You must be dealing with an allocation problem
 There must be a well defined objective function, which can only be one – maximization or
minimization type only
 There must be alternative courses of action, at least one of which will meet the objective.
That is, the problem must permit a choice or choice between alternative causes of action
 The objective function and the constraints must be mathematically expressed (as equations or
inequalities)
 The form of mathematical relationships must be linear (i.e. of the 1st degree). That is, all
factors involved in the problem must have linear relationships e.g. doubling of output
requires a doubling of labour hours; if one unit provides £10 contribution 10 units will
produce £100 and so on.
 The problem must be capable of being stated in numeric terms.
 These must be one or more restrictions on the factors involved. These may be restrictions on
resources (labour hours, form of materials etc), but they may also be on particular
characteristics, e.g. fertilizer must contain a minimum of 15% phospates and 30% nitrogen or
a patent fuel must contain not more than 5% ash, 2% phosphorous 81% sulphur. That is,
resources must be limited in supply and economically quantifiable.

Basic assumptions:

Proportionality. We assume that proportionality exists in the objective and constraints i.e. the
measure of effectiveness (profit or loss), in the objective function and amount of each resources

1
used must be proportional of the value of each decision variable considered individually. For
example, if we want to double the output we simply double the required resources.

Additivity. Sum of the resources used by different activities must be equal to the total quantity of
resources used by each activity for all the resources individually and collectively i.e. interaction
among the activities of the resources does not exist.

Divisibility. Solutions need not be in whole numbers (integers). Instead they are divisible and
may take any fractional value.
If a fraction of a product cannot be produced (like 1/8 of a bus), an integer programming of
problem exists.

Certainty. We assume that conditions of certainty exist i.e. the coefficients in the objective
function and constraints are completely known (deterministic) and do not change during the
period being studied; e.g. profit per unit of each product, amounts of resources available are
fixed during the planning period.

Finiteness. An optimal solution cannot be computed in the situations where there are infinite
number of alternative activities and resource restrictions

2 Formulation

We shall use the term formulation to mean translating a real world problem into a format of
mathematical equations and inequalities.

Formulating a linear programming problem model therefore means, translating a business

decision into linear programming terminology. This in involves defining the decision variables,
specifying an objective (hence the objective function), identifying the constraints and writing all
constraints as equalities or inequalities.

2.1. Useful steps in formulating LP model

1) Define in verbal terms the objective that you are trying to achieve in solving the problem.
Select only one objective e.g. it might be “reduce cost” or “increase contribution to
profit”.
2) List verbally the decisions that are to be made as specifically as you can.
3) List verbally the constraining factors that affect these decisions. Try to be prices and
complete. There are several types of constraints e.g.

Capacity constraints. Limits because of equipment, space, or manpower available

Market constraints. Limits (either lower or upper or both) on how much product can be
sold or used

Availability constraints. Limits because of scarcity of raw materials, labour, funds or

other resources

2
 Quality or blending constraints. Are constraints that put limits on mixes of ingredients,
usually defining the quality of output products

Production technology or material balance constraints. Constraints that define the

output of some process as a function of the inputs, often with a loss for scrap

Definitional constraints. Constraints that define a given variable. Often such constraints
come from accounting definitions

4) Define specifically the decision variables.

5) Specifically define the constraints, using the decision variables

6) Define the objective function in detail. For each decision variable from step 4, a cost or
profit coefficient must be defined. Its important to include only cost or profits that vary
with the decisions under consideration. Fixed costs should always be excluded.

Note:
Although these six steps give a general out time for formulating LP models, these are no
substitutes for practice and experience.

2.2. General LP Model

Max/Min Z= c1x1 + c2x2 + …… +cnxn

Subject to: a11x1 + a12x2 + …… +a1nxn <=> b1
a21x1 + a22x2 + …… +a2nxn <=> b2
…………………………………
am1x1 + am2x2 + …… + amnxn <=> bm

x1, x2, x3, …, xn>=0

Interpretation
There are n activities whose levels/unknown values are represented by x1, x2, … xn. There are m
resources whose (max/min) values are given by b1, b2, … bm .
 Z= objective function value
 Cj=contribution per unit (max) or cost per unit (min) of activity xj to the objective function
 General LP Model – Cont…
 Cj=contribution per unit (max) or cost per unit (min) of activity xj to the objective function
 Xj = quantity of decision variable j
 aij= resource usage of resource i by decision variable j (resource requirement coefficient per
unit of output)
 bi=total resource constraint of resource i

3
3 Solving LP problems

3.1. Graphical Method

Plot all the constraints and identify the feasible region. The feasible region is one that satisfies
all the constraints simultaneously. The solution to the LP problem lies at one of the extreme
corner points. Use either the vertex (corner point method), or the trial objective function method
(isoprofit or isocost) to identify the optimal solution.

3.1.2 Special Cases

Infinite/alternative optimal solution

There are many optimal solutions. Occurs when the trial objective function line coincides with
one of the constraints

Infeasibility
Means that no solution satisfies all the constraints, including the non-negatively condition i.e. a
feasibility region does not exist. This would show management that the solution is not possible.
Linear programming analysis can help determine whether management’s plan are feasible or not.

Unbounded solution
For a maximization problem, solution is unbounded if it may be made infinitely large without
violating any of the constraints. For a minimization problem, the solution is unbounded if the
value may be made infinitely small.

If this condition were to occur in profit maximization problem the manager could achieve
unlimited profit (managerial utopia). In real life, if this occurs then it means the problem was not
properly formulated

Redundancy
Explain what is meant by redundancy in linear programming.

3.2. Simplex Method

This is an algebraic approach to LP problem solving. It was developed by George Dantzig in

1947.

The simplex algorithm systematically examines the extreme points of a feasible solution region
of a linear programming problem in a sequence such that each solution is at least as good as the
one before it. The search is continued until a solution is reached from which it is not
advantageous to move in terms of the objective function. That is, it moves from one corner to
another, better, one until it arrives at the corner where the objective function has its best value.

Steps:
Convert to standard form by doing the following

4
For constraints of the type < add a slack variable on the LHS of the constraint. Slack variable
represents unused resource.

For constraints of the type >= subtract a surplus variable from the LHS of the constraint.
Write the set of equations in standard form

Terminology
 Basic Variables. Variables with positive values in the current step
 None basic variables. Variables which are currently not in the basis and have zero values
 Number of non-basic variables=n-m
 n=number of unknowns
 m=number of constraints

Improving the solution

The entering variable in maximization is the non-basic variable with the most negative
coefficient in the z equation – a tie is broken arbitrarily. The leaving variable is the basic
variable having the smallest ratio (with +ve denominator). A tie is broken arbitrarily. When all
the non-basic coefficients in the Z-equation are non-negative, the optimum is reached

The entering variable in minimization is the non-basic variable with the most positive coefficient
in the z-equation (a tie is broken arbitrarily). The leaving variable is the basic variable having
the smallest ratio. When all the non-basic coefficients in the Z-equation are non-positive, the
optimum is reached

3.3. Computer Implications

Application of linear programming in the real world inevitably involves the use of electronic
digital computers. In these cases, extensive information, data manipulation, and numerical
computation require high-speed computers.

There are many software packages available that support the solution of linear programming
problems on a microcomputer. Among the many user-friendly packages are:

 The LINDO computer package widely used mathematical programming packages for solving
linear, integral and
 Quantitative systems for business (QSB) package
 OMIS – Operations Management Information Systems
 Management Scientist

3.3.1 Interpretation of Computer output

Reduced Cost. A reduced cost for a decision variable whose value is 0 in the optimal solution is
the amount the variable’s objective coefficient would have to improve (increase for
maximization, decrease for minimization problems) before it could assume a positive value.
Thus the reduced cost for a decision variable with a positive value is 0.

5
Dual Price. This is the amount the objective function will improve per unit increase in the right
hand side value of a constraint.

Shadow price. The shadow prices associated with a primal constraint shows the amount of
improvement in the optimal objective function value as the value of the right hand side of that
constraint is increased by one unit, with all other model parameters unchanged.

Sensitivity Analysis
One important assumption in LP is that of certainty i.e. parameters, constraints, decision
variables, etc. are known with certainty and will remain the same. In practice, this is not likely to
be true. Sensitivity analysis involves investigating the effects of any possible changes on the
optimal solution (hence sometimes referred to as post optimality analysis).

Types of Sensitivity analyses

 Availability of resources
 Profit contribution or cost per unit of decision variables, (coefficients in the objective
function)
 Consumption of resources per unit of decision variables (coefficients in the LHS of
constraint variables)
 Inclusion of a new decision variable or exclusion of one already there
 Inclusion of a new constraint or exclusion of one already there

Simultaneous Changes
 100% Rule for Objective Function Coefficients
For all objective function coefficients that are changed, sum the percentages of the allowable
increases and the allowable decreases represented by the changes. If the sum of the percentage
changes does not exceed 100%, the optimal solution will not change.

 100% Rule for Constraint Right Hand Sides

For all right-hand sides that are changed, sum the percentages of allowable increases and
allowable decrease. If the sum of the percentages does not exceed 100%, the dual prices will not
change

4 Duality
Associated with any LP problem is another mirror – image like problem. If the original problem
is termed the primal, its image is termed the dual. The primal and the dual are so much related
that all the information required to formulate one will also be required for the other.
Furthermore, the solution to one gives the solution to the other.
To take the dual of a primal problem that has all inequalities in the same direction, follow the
following steps:

 Form the dual objective function from the primal right-hand side (RHS) coefficients
 Form the ith dual constraint from the ith column of coefficients in the primal constraints
 Form the dual RHS coefficients from the primal objective function coefficients

6
 If the primal is a maximization, form the dual as a minimization (and vice versa), and reverse
the direction of the inequalities in the constraints
 We associate a dual variable with the ith primal constraint. Thus the number of variables in
the dual problem depends upon the number of primal constraints, not the number of primal
variables. (Discuss the importance of the duality theorem)

5 Typical applications

Marketing Application
 Media selection
 Marketing research

Financial Application
In finance, LP has been applied in problem situations involving capital budgeting, make or buy
decisions, asset allocation, portfolio selection, financial planning etc.

Production management application

Many LP applications have been developed for production and operations management,
including scheduling, staffing, inventory control and capacity planning, etc

Blending problems
Blending problems arise whenever a manager must decide how to blend two or more resources
to produce one or more products. In these situations, the resources contain one or more essential
ingredients that must be blended into final products that will contain specific percentages of
each. In most of these applications then, management must decide how much of each resource to
purchase to satisfy product specifications and product demand at minimum cost.

Blending problems occur frequently in:

 Petroleum industry (e.g. blending crude oil to produce different octane gasolines)
 Chemical industry e.g. blending chemicals to produce fertilizers and weed killers)
 Food industry e.g. blending ingredients to produce soft drinks and soups

Data Envelop Analysis (DEA)

This is an application of LP that has been used to measure the relative efficiency of operating
units with the same goals and objectives.

6 Exercises

Exercise 1
Maridadi furniture Ltd manufactures two products; tables and chairs which require material and
labour. In any given week there are 96 units of material available while labour availability is up
to 168 labour hours. Each table requires 3 units of material whereas the chair requires 4 units.
Manufacturing a table or a chair requires 6 hours. Market research shows that whereas there is
no limit to the number of tables that can be sold, the market can only absorb 18 chairs per week.
The contribution to profit for 1 table and 1 chair and £12 and £20 respectively

7
Determine the best combination of tables and chairs in order to maximize the contribution to
profit

Exercise 2
A client of an investment firm has $10,000 available for investment. He has instructed
that his money be invested in three stocks so that no more than $5,000 is invested in any
one stock but at least $1,000 is invested in each stock. He has further instructed the firm
to use its current data and invest in a manner that maximizes his overall gain during a one
– year period. The stocks, the current price per share, and the firm’s projected stock price
a year from now, are summarized in the following table.
Current Projected Price
Stock Price ($) 1 Year Hence ($)
James Industries 25 35
QM Inc. 50 60
Delicious Candy 100 125

Formulate this problem as a linear programming problem.

Exercise 3
Electronic Communications manufactures portable radio systems that can be used for two-way
communications. The company’s new product, which has a range of up to 25 miles, is
particularly suitable for use in a variety of business and personal applications. The distribution
channels for the new radio are as follows:
 Marine equipment distributors
 Business equipment distributors.
 National chain of retail stores
 Mail order.

Because of differing distribution and promotional costs, the profitability of the product will vary
with the distribution channel. In addition, the advertising cost and the personal sales effort
required will vary with the distribution channels. The table below summarizes the contribution
to profit, advertising cost and personal sales effort data pertaining to the Electronic
Communications problem.
Advertising Personal Sales
Distribution Profit per Cost per Effort per
Channel Unit sold Unit Sold Unit Sold
Marine distributors $90 $10 2 hours
Business distributors $84 $ 8 3 hours
National retail stores $70 $ 9 3 hours
Mail order $60 $15 None

The firm has set the advertising budget at $5,000 and there is a maximum of 1,800 hours of sales
force time available for allocation to sales effort. Management has also decided to produce
exactly 600 units for the current production period. Finally, an ongoing contract with the

8
national chain of retail stores requires that at least 150 units be distributed through this
distribution channel.

Electronic Communications is now faced with the problem of establishing a strategy that will
provide for the distribution of the radios in such a way that overall profitability of the new radio
production will be maximized. Decisions must be made as to how many units should be
allocated to each of the four distribution channels, as well as how to allocate the advertising
budget and sales force effort to each of the four distribution channels.

Formulate the Electronic Communication problem as a linear programming problem.