COVENANT UNIVERSITY OTA

COLLEGE OF BUSINESS AND SOCIAL SCIENCES

DEPARTMENT OF ECONOMICS AND DEVELOPMENT STUDIES

Course Code and Title: ECO 215; Mathematics for Economists

MODULE SIX: LINEAR PROGRAMMING (LP)

5.1 Introduction

Linear Programming (LP) is a mathematical technique of great practical importance. Since the
origin of linear ramming in the 1940’s there have been important theoretical and computational
development and its methods are now used every day in many parts of the world. Linear
programming it is used in economic decision problems. However, its importance extends even
beyond its practical applications.

In real life scenario, LP is part of a very important area of mathematics especially ‘optimization
techniques’. The application of LP in Economics include Leontief’s input-output model, the
determination of shadow prices; in Business LP is applied in maximizing profit in a factory that
manufactures a number of different products from the same raw material using the same resources;
etc.

LP is at time referred to as ‘linear optimization’ and it can also be defined as the problem of
maximizing or minimizing a function specified by linear and non-negativity constraints. Thus, LP
is the optimization of an outcome based on some set of constraints using a linear mathematical
model.

Three (3) major elements (ingredients) in LP include: a) The objective function, b) a set of
constraints; c) a set of non-negativity restrictions. LP can be of the minimizing or maximizing
type.

1
Example

Find numbers x1 and x2 that will maximise the sum x1+ x2 s.t. the constraints x1 ≥ 0 and x2 ≥ 0;
where: x1 + 2x2 ≤ 4

4x1 + 2x2 ≤ 12

-x1 + x2 ≤ 1

From above, there are two unknowns and five constraints and they are all linear in the sense that
each involves an inequality in some linear function of the variables. The first two constraints, (x1
≥ 0 and x2 ≥ 0) are special and they are called non-negativity constraints and are usually found in
LP problems. The other constraints are then called the main constraints and the function to be
maximised (x1+ x2) is known as the objective function.

5.2 Long hand Notation

A maximized program in n variables and subject to m constraints will appear as follows when
completely written.

Max.  = C 1X2 + C 2X2 +…………+ CnXn

Subject to (s.t.) A11 X1+ A 12X2+…………+A1nX n ≤ R1

A 21X 1+A 22X2+…………+A2nX n ≤ R2

A m1X 1+A m2X 2+….……+A mnX n≤ Rm

And Xj ≥ 0 (j= 1,2,………n)

The  symbol serves as a general symbol for the maxima (object to be maximized). Xj
(j=1,2,………n) denotes choice variables and Ci (i=1,2.……n) denotes their coefficients in the
objective function which are a set of given constants. Ri (i=1,2.……n) is another set of constraints
which represents restrictions imposed in the program. For uniformity, all m constraints have been
written as ≤ inequalities. However, if a case of ≥ constraint appears, it can always be converted to

2
≤ form by multiplying by -1. The coefficients of the choice variables in the constraints are denoted
by Aij.

A minimization program may be written as;

Min. C= C 1X1 + C 2X2+……………+ CnXn

S.t. A 11X1+A 12X2+……………+A 1nXn ≥ R1

A 21X1+A 22X2+……………+A 2nXn ≥ R2

A m1X1+A m2X2+……………+A mn Xn ≥ Rm

And Xj ≥ (1,2,……………n)

The C symbol stands for minimal (the object to be minimized). Cj stands for the set of given
constant coefficients as are Ri however, the R stands for requirements. The constants in this case
appear as ≥ inequalities.

5.3 Ʃ Notation

n n
Max.  =  CjXj
j 1
s.t.  Aij
j 1
Xj ≤ Ri (i= 1,2,3………m)

And Xj ≥ 0 (j= 1,2,3…………n)

Or

n n
Min. C=  Cj
j 1
Xj s.t.  Aij Xj ≥ Ri
j 1
(i=1,2,3…………m)

And Xj ≥ 0 (j= 1,2,3…………n)

3
5.4 Methods of Solving LP Problems

1) Simplex Approach/Method.
2) Graphical Approach/Method
3) Matrix Algebra Approach/Method

5.4.1 Simplex Method

This was introduced in 1947 by G.B. Dantzig is a very efficient numerical method that finds the
solution in a finite number of operations. For economists, it is probably more important to
understand the duality theory of LP than the details of the simplex method.

5.4.2 Graphical Approach/Method

The general process for solving LP problems using graph involving inequalities (the constraints)
on the x,y plane to form a walled-off area called the feasible region. Then you figure out the
coordinates of the corners of the feasible region, by examining the intersection points of the various
pairs of lines and test these corner points in the formula called the optimization equation for which
you are trying to find the maximum or minimum value.

The graphical method however only works well when there are only two decision variables. One
can extend the method to the case with three decision variable. Then the feasible set is a convex
polyhedron in 3-space, and the level surfaces of the objective function are planes in 3-space.
However, it is not easy to visualize in such cases. For more than three decision variables, no
graphical method is available. By using the duality theory, however one can solve LP problems
graphically when either the number of unknowns or the number of constraints is less than or equal
to three.

Even in two and three decision variable, if the feasible region is unbounded, a finite (optimal)
solution might not exist. Though the graphical method is the most commonly used method, it
should be noted that other methods such as the matrix algebra method are also employed in solving
linear programming problems. This is illustrated in Figure 5.1 below:

4
 Figure 5.1: Graphical Illustration of Feasible Region in LP

Numerical Example

A). A baker has 150 grams of flour, 22 kilos of sugar and 27.5 kilos of butter with which to make
two types of cake. Suppose that making one dozen A cakes requires 3 kilos of flour, 1 kilo of sugar
and I kilo of butter, whereas making one dozen B cakes require 6 kilos of flour, 0.5 kilo of sugar
and I kilo of butter. Suppose that the profit from one dozen A cakes is 20 and from one dozen B
cakes is 30. How many dozen A cakes (x1) and dozen B (x2) cakes will maximize the baker’s
profit?

Solution

An output of x1 dozen A cakes and x2 dozen B cakes would need 3x1 + 6x2 kilos of flour because
there are only 150 kilos of flour, the inequality:

3x1 + 6x2 ≤ 150 ( flour constraint)

n
must hold. Similarly, for sugar,  Aij
j 1

x1 + 0.5x2 ≤ 22 (sugar constraint)

5
and for butter,

x1 + x2 ≤ 27.5 ( butter constraint)

of course, x1 ≥ 0 and x2 ≥ 0. the profit obtained from producing x1 dozen 2)cakes and x2 dozen b
cakes is:

z= 20x1 + 30x2

in short, the problem is to,

max. z = 20x1 + 30x2 s.t. 3x1 + 6x2 ≤ 150

x1 + 0.5x2 ≤ 22 x1 ≥ 0 , x2 ≥ 0

x1 + x2 ≤ 27.5

5.5 Review Question

Plot the graph using information above

Hints:

The output pair (x1 and x2) is called feasible or admissible for problem:

(i) if all the five constraints are satisfied. Look at the flour constraint, 3x1 + 6x2 ≤150.

if we use all the flour, then 3x1 + 6x2 = 150 and we call this the flour border. We can find similar
borders for the other two inputs.

The straight lines will represent the flour, butter and sugar borders. In order for (x1, x2) to be
feasible, it has to be on or below to the southwest of each of the three borders simultaneously.
Because constraints x1 ≥ 0 and x2 ≥ 0 restrict (x1, x2) to the nonnegative quadrant, the set of feasible
pairs for problem (i) called the feasible region is the S region. This portion S is also known as the
convex polyhedron and the end points (e.g. O,A,B,C,D) are called extreme points of the set S.

6
The final solution: the baker maximizes profit by producing 5 dozen A cakes and 22.5 dozen B
cakes and making a profit of N775.

5.6 Applications of Linear Programming (LP) Concept

Generally, LP has led to the central concepts of optimization theory, such as duality,
decomposition, and the importance of convexity and its generalizations. Also it is applied in
microeconomics and company management, such as planning, production, transportation,
technology and other issues. It is also applied in almost all facets of business (e.g. advertising,
production planning, transportation, distribution, and aggregate production planning problems
etc). In the petroleum industry, LP is used for data processing manager at a large oil company
recently estimated that from 5 to 10 percent of the firm’s computer time was devoted to the
processing of LP and LP-like models.

Example

A). Find the maximal and minimal value of z = 3x + 4y subject to the following constraints:

The three inequalities above are the constraints. z = 3x + 4y is the optimization equation. The first
step is to find the (x, y) corner points (solution) of the feasibility region that will have the largest
and smallest values of z. This will lead the inequality below and depicted in Figure 5.2 using more-
easily graphed equivalents:

7
 Source: Adapted from Stapel, E. Linear Programming: Introduction, Purplemath,
<[Link] Accessed 25 March 2012>

To establish the corner solution (points), which may not be clear from the graph, the lines forming
a system of linear equations will be paired and solve as:

Thus, the corner solutions are as follows: (2, 6), (6, 4), and (–1, –3).

The above can be proved: the maximum and minimum values of the optimization equation will be
on the corners of the feasibility region. Therefore, to find final solution, these three points will be
substituted into the initial equation: z = 3x + 4y as:

(2, 6): z = 3(2) + 4(6) = 6 + 24 = 30

(6, 4): z = 3(6) + 4(4) = 18 + 16 = 34
(–1, –3): z = 3(–1) + 4(–3) = –3 – 12 = –15
8
Then the maximum of z = 34 occurs at (6, 4), and the minimum of z = –15 occurs at (–1, –3).

5.7 Other Areas LP are Applied

LP is equally applied to other areas apart from Economics, which include:

5.7.1 Finance: The problem of the investor could be a portfolio-mix selection problem. In
general, the number of different portfolios can be much larger than the example indicates, more
and different kinds of constraints can be added. The decision problem involves determining the
mix of funding for a number of products when more than one method of financing is available.
The objective may be to maximize total profits, where the profit for a given product depends on
the method of financing. For example, funding may be done with internal funds, short-term debt,
or intermediate financing (amortized loans).

5.7.2 Production and Operations Management: In the process industries a given raw material
can be made into a wide variety of products. For example, in the oil industry, crude oil is refined
into gasoline, kerosene, home-heating oil, and various grades of engine oil. Given the present profit
margin on each product, the problem is to determine the quantities of each product that should be
produced. The decision is subject to numerous restrictions such as limits on the capacities of
various refining operations, raw-material availability, demands for each product, and any
government-imposed policies on the output of certain products. Similar problems also exist in the
chemical and food-processing industries.

5.7.3 Human Resource Management: Personnel planning problems can also be analyzed with
linear programming. For example, in the telephone industry, demands for the services of installer-
repair personnel are seasonal. The problem will be to determine the number of installer-repair
personnel and line-repair personnel to have on the work force each month where the total costs of
hiring, layoff, overtime, and regular-time wages are minimized. The constraints set includes
restrictions on the service demands that must be satisfied, overtime usage, union agreements, and
the availability of skilled people for hire.

9
5.7.4 Distribution Chain: Consider a case in which there are m factories that must ship goods
to n warehouses. A given factory could make shipments to any number of warehouses. Given the
cost to ship one unit of product from each factory to each warehouse, the problem is to determine
the shipping pattern (number of units that each factory ships to each warehouse) that minimizes
total costs. This decision is subject to the restrictions that demand at each factory cannot ship more
products than it has the capacity to produce.

5.8 Review Question

A). Given food items A and B, find the decision that you will make about how much of each food
to buy using the considerations in the Table 5.1 below:

per unit of Item A per unit of Item B Minimum requirements

Units of
carbohydrates 3 1 8

units of vitamins 4 3 19

Units of protein 1 3 7

Unit cost 25 50

Hint: you are to find a choice of the numbers of units of items A and B that will meet the minimum
nutritional requirements at minimal cost. Then, formulate the problem in terms of linear
inequalities and an objective function. You can solve the problem geometrically/graphically.

B). Company ABCD makes a net return of N1.00 on each X1 and N1.50 for each X2 produced.
The firm has 150 pounds of dough mix and 50 pounds of topping mix. Each X1 uses 1 pound of
dough mix and 4 ounces (16 ounces= 1 pound of topping mix), while each X2 uses 1 pound of
dough mix and 8 ounces of topping mix. Based on the past demand per week, a salesperson can

10
sell at least 50 X1 and 25 X2. Find the number of X1 and X2 that company ABCD should make to
maximize net return using LP approach.

11