Chapter Two: Linear Programming/LPP

2.1. Introductıon to linear programming

2.2 . Formulatıon of a Lp model

2.3. Methods of solving linear programming

2.4. Duality in LPP

2.5. Sensitivity Analysis

2.1. Introductıon to lP

Definition

 Management decisions in organizations involve trying to make most effective

use of resources (machinery, labor, money, time, warehouse space, and raw

materials) in order to:

o Produce products - such as computers, automobiles, or clothing or

o Provide services - such as package delivery, health services, or investment

decisions.

 To solve problems of resource allocation one may use mathematical

programming.

 Linear programming (LP) is the most common type of mathematical

programming.
 LP seeks to maximize or minimize a linear objective function subject to a

set of linear constraints.

 Linear programming is an analysis technique in which linear algebraic

relationships represent a firm’s decisions given a business objective and

resource constraints.

Structure of LP

 Each LP model consists of three basic elements or components.

 These are:

i.The decision variables, and parameters

ii.The objective function and

iii.The constraints
i. Decision variables (Activities): The activities are usually denoted by decision
variables .

 The values of these activities represent the extent to which each of these is
performed.

 The values of certain variables may or may not be under the decision –maker’s
control.

ii. The objective function:

 the objective (goal) function of each LP problem is expressed in terms of

decision variables to optimize the criterion of optimality (the measure of
performance)

 such as profit, cost, revenue, distance, etc.

 In its general form it is expressed as:

 Optimize (Maximize or Minimize): Z= 𝐶1 𝑋1 + 𝐶2 𝑋2 +------ 𝐶𝑛 𝑋𝑛

iii. The constraints

 There are always certain limitations (or constraints) on the use of

resources, e.g. labor, Machine, Raw material, space, money, etc.

 These limit the degree to which an objective can be achieved.

Assumptions Underlying Linear Programming

 The basic assumptions of linear programming include the following:

i. Proportionality: the measure of effectiveness (profit or loss) in the objective

function and amount of each resource used must be proportional to the value of

each decision variable considered individually.

ii. Additivity: It states that the sum of resources used by different activities must be

equal to the total quantity of resources used by each activity for all resources

individually and collectively.

iii. Divisibility: This assumption implies that solutions need not be in whole numbers
(integers). Instead, they are divisible and may take any fractional value. For example
an optimal solution to a decision variable can take values like 3.5, 1.2, 2.5 etc.
iv. Certainty: the coefficients in the objective function and constrains are

completely known (deterministic) and do not change during the period being

studied.

 Certainty has two aspects in LP models. The first relates to the parameters in the

model. It means that we know for certain these parameters (numerical values).

o If for example we do have an objective function: Maximize profit Z = 2x1 +3x2, the

parameters (coefficients) 2 and 3 represent the per unit contribution of x1 and x2

and we now these unit contributions for certain.

o The other aspect is the assumption that all relevant constraints have been identified

and represented in the model.

v. finiteness: An optimum solution cannot be computed in the situations where

there are infinite number of alternative activities and resource restrictions.

vi. Optimality: In linear programming, the maximum profit solution or the

minimum cost solution always occur at the corner point of the set of feasible

solutions.

vii. Non-negativity: It customary to see one common constraint at the end of

every linear programming model.

 This constraint is about the exclusion of negative values from our solution

to the decision variables.

 This is because decision variables represent quantities and there is no

negative quantity. Only positive values and zero will be allowed.

2.2. Formulatıon of a Lp model

 Formulation is the process of converting the verbal description and numerical

data into mathematical expressions which represents the relevant relationship
among decision factors, objectives and restrictions on the use of resources.

 General form of LPM

 z= 𝐶1 𝑥1 + 𝑐2 𝑥2 +---- 𝑐𝑛 𝑥𝑛 ……..objective function

 Subject to 𝑎11 𝑥1 + 𝑎12 𝑥2 ---𝑎1𝑛 𝑥𝑛 (≤ 𝑜𝑟 ≥) 𝑏1

𝑎21 𝑥1 + 𝑎22 𝑥2 ---𝑎2𝑛 𝑥𝑛 (≤ 𝑜𝑟 ≥) 𝑏2

.
.
.

𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 --𝑎𝑚𝑛 𝑥𝑛 (≤ 𝑜𝑟 ≥) 𝑏𝑚`

𝑥1 ≥ 0, 𝑥2 ≥ 0, …,𝑥𝑛 ≥0
OR

𝑛
Z= 𝑗=1 𝑐𝑗 𝑥𝑗

𝑛
𝑗=1 𝑎𝑖𝑗 𝑥𝑗 (≤ 𝑜𝑟 ≥) 𝑏𝑖 for i=1,2,…,m

𝑥𝑗 ≥ 0 for j=1,2,…n

Where

Z= value of overall measure of performance

𝑥𝑗 =level of activity for (j=1, 2, …, n)

𝑐𝑗 = increase in z that would result from each unit increase in level of activity n

for (j=1, 2, …, n).

𝑏𝑖 = amount of resource i that is available for allocation to activities for (i= 1,2,…,m).

𝑎𝑖𝑗 = amount of resource i consumed by each unit of activity j.

Example 2.1: Maximization

 A firm is engaged in producing two products, A and B. Each unit of product

A requires 2 Kg of raw materials and 4 Labour hours for processing, whereas

each unit of product B requires 3 kg of raw materials and 3 hours of labour,

of the same type. Every week, the firm has an availability of 60 kg of raw

materials and 96 labour hours. One unit of product A sold yields Birr 40 and

one unit of B sold gives Birr 35 as profit.

 . Formulate linear programming problem to this problem.

Solution

• Objective function-the first major requirement of an LPP is that we should be able to

identify the goal in terms of objective function. For this problem, the goal of a firm is

maximization of profit, which would be obtained producing and selling products A and B.

Assume product A , product B and profit represented by 𝑥1 , 𝑥2 and z respectively. Z

would be equal to 40𝑥1 + 35𝑥2 is then objective function, relating the profit and the out put

level of each of the two items. Further, since the problem calls for a decision about the

optimal values of 𝑥1 and 𝑥2 , these are known as decision variables.

• Constraints- another component of LP is resource are limited. This limitation is know as

constraint and it is explained by inequality mathematical relationship. Each unit of product

A requires 2 kg of raw material while each unit of product B needs 3 kg. The total

consumption would be 2𝑥1 + 3𝑥2 ≤ 60. Similarily, it is given that a unit of A requires 4

labour hours for its production and one unit of B requires 3 hours. With an availability of 96

hours a week. We have 4𝑥1 + 3𝑥2 ≤ 96 as labour hours constraint.

 Non Negative Condition-, 𝑥1 and 𝑥2 being the number of units produced,

can not have negative values. Thus, both of them can assume values only

greater than or equal to zero. This is non negativity condition, expressed

symbolically as 𝑥1 ≥ 0 𝑎𝑛𝑑 𝑥2 ≥ 0

 Now we can write the problem in complete form as follows:

𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑧 = 40𝑥1 + 35𝑥2 ………….profit

Subject to 2𝑥1 + 3𝑥2 ≤ 60 …………..raw material constraints

4𝑥1 + 3𝑥2 ≤ 96 …………….Labour constraints

𝑥1 , 𝑥2 ≥ 0 ………………..Non Negativity
 Example 2.2: Minimization

 The Agricultural Research institute suggested to a farmer to spread out at

least 4800kg of a special phosphate fertilizer and not less than 7200 kg of a

special nitrogen fertilizer to raise productivity of crops in his fields. There

are two sources for obtaining these mixtures A and B. Both of these are

available in bags weighing 100kg each and they cost Birr 40 and Birr 24

respectively. Mixture A contains phosphate and nitrogen equivalent of 20 kg

and 80 kg respectively, while mixture B contains these ingredients

equivalent of 50 kg each.

 Write this as a linear programming.

• Objective function-in this problem, such a combination of mixture of A and B is

sought to be purchased as would minimize the total cost. If , are taken to

represent the number of bags of mixture of A and B respectively , the objective

function can be expressed as follows.

• 𝑀𝑖𝑛𝑚𝑖𝑧𝑒 𝑧 = 40𝑥1 + 24𝑥2 ….cost

• Constraints-In this problem there are two constraints, namely a minimum of

4800 kg of phosphate and 7200 kg of nitrogen ingredients are required. It is

known that each bag of mixture A contains s 2020 kg and each bag of mixture B

contains 50 kg of phosphate. The phosphate requirements can be 20𝑥1 +

50𝑥2 ≥ 4800 . Similarily, with the gievn information on the contents, the

nitrogen requirment can be writen as. 80𝑥1 + 50𝑥2 ≥ 7200

• Non Negative Condition-, decision variables 𝑥1 and 𝑥2 being the number of bags

mixtures A and B can not have negative values. Thus, 𝑥1 ≥ 0 𝑎𝑛𝑑 𝑥2 ≥ 0

• Now we can write linear programming as follows:

• 𝑀𝑖𝑛𝑚𝑖𝑧𝑒 𝑧 = 40𝑥1 + 24𝑥2 ……………....cost

• Subject to 20𝑥1 + 50𝑥2 ≥ 4800 ….. phosphate requirements

80𝑥1 + 50𝑥2 ≥ 7200…… Nitrogen requirements

𝑥1 , 𝑥2 ≥ 0 ……………….…..Non Negativity
Exercise 2.1: An animal feed company must produce at least 200 kgs of a mixture

consisting of ingredients 𝑥1 and 𝑥2 daily. 1 costs Birr 3 per kg and 𝑥2 Birr 8 per kg.

No more than 80 kg of 𝑥1 can be used and at least 60 kg of 𝑥2 must be used.

• Formulate a mathematical model to the problem.

Exercise 2.2

 Suppose that a machine shop has two different types of machines; machine 1 and

machine 2, which can be used to make a single product. These machine vary in the

amount of product produced per hr., in the amount of labor used and in the cost of

operation. Assume that at least a certain amount of product must be produced and

that we would like to utilize at least the regular labor force.

 Formulate a mathematical model to the problem

2.2. Methods of Solving Linear Programming Problems le

2.2.1. Graphic method

2.2.2. Algebraic method or simplex Method.

2.2.1. Graphic method – is method to solve linear programming problems by graph and it can be used only when

two variables are involved.

 It consists of the following steps:-

Step I: Defining the problem-The decision variables, the objective functions, and the constraint restrictions.

Step II: Draw a graph that includes all the constraints/restrictions and identify the feasible region.

Plot the constraints graphically.

Step III: Obtain the point on the feasible region that optimizes the objective function-the optimal solutions

Step IV: Interpret results.

Theorem 1: If a linear programming problem has a solution, then it must occur at a
vertex, or corner point, of the feasible set S associated with the problem.
• If the objective function Z is optimized at two adjacent vertices of S, then it is
optimized at every point on the line segment joining these vertices, in which case
there are infinitely many solutions to the problem.
Theorem 2-Existence of a Solution

• Suppose we are given a linear programming problem with a feasible set S and an
objective function P = ax + by.
a. If S is bounded, then P has both a maximum and a minimum value on S.
b. If S is unbounded and both a and b are nonnegative, then P has a minimum
value on S provided that the constraints defining S include the inequalities x 
0 and y  0.
c. If S is the empty set, then the linear programming problem has no solution:
that is, P has neither a maximum nor a minimum value.
The Method of Corners

1. Graph the feasible set.

2. Find the coordinates of all corner points (vertices) of the feasible set.

3. Evaluate the objective function at each corner point.

4. Find the vertex that renders the objective function a maximum or a

minimum.

– If there is only one such vertex, it constitutes a unique solution to the

problem.

– If there are two such adjacent vertices, there are infinitely many optimal

solutions given by the points on the line segment determined by these

vertices.
1. Maximization

 Consider Example 2.1. For this problem, the decision variables are , the

number of units of the products A and B respectively.

 Step 1: define problem-the objective function and the constraints are

reproduced as, units of the products A and B respectively. The objective

function and the constraints are reproduced as

𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑧 = 40𝑥1 + 35𝑥2 ………….profit

Subject to 2𝑥1 + 3𝑥2 ≤ 60 …………..raw material constraints

4𝑥1 + 3𝑥2 ≤ 96 …………….Labour constraints

𝑥1 , 𝑥2 ≥ 0 ………………..Non Negativity
Step 2:Plot constraints

o Every constraint is represented by a straight line

o The constraints of raw materials, 2𝑥1 + 3𝑥2 ≤ 60, states that any

combinations 2𝑥1 + 3𝑥2 that does not exceed 60 is acceptable and

similarly, the constraints of raw materials, 4𝑥1 + 3𝑥2 ≤ 96, states that

any combinations 4𝑥1 + 3𝑥2 that does not exceed 96 is acceptable.

o We can draw two straight lines.

o To draw two straight lines we need two points.

Constraint #1: 2𝑥1 + 3𝑥2 ≤ 60

 Steps to draw
o replace the inequality with an equality, 4𝑥1 +
3𝑥2 = 96,
o Find intercepts
𝑥1 𝑥𝟐
0 32
24 0
o
o draw the graph
Constraint #2: 4𝑥1 + 3𝑥2 ≤ 96

Steps to draw
o replace the inequality with an equality, 4𝑥1 +
3𝑥2 = 96,
o Find intercepts
𝑥1 𝑥𝟐
0 32
24 0
o
o draw the graph
#Mark feasible region

 Feasible region should be a convex set

 The constraints in a LP problem form a system of linear inequalities, which have a

solution set S.

 Each point in S is a candidate for the solution of the linear programming problem
and is referred to as a feasible solution.

 The feasible region in our example is given by OPQR, so we need to obtain the
ordinates of each of these points (given values of 𝑥1 and 𝑥2 ) and calculate the values
of objective function by substituting them in objective function.

 For intersection points we can obtain values by solving simultaneously equations

representing those lines.

 In our example the ordinate point Q can be obtained by solving the two equations
simultaneously.
2𝑥1 + 3𝑥2 = 60
4𝑥1 + 3𝑥2 = 96
 This gives 𝑥 = 18 and 𝑥 = 8
# Combined-Constraint Graph
#Get optimal solution

 The Z- values corresponding to the various points in respect of the given problem
are shown here

Points 𝑥1 𝑥2 𝑧 = 40𝑥1 + 35𝑥2

O 0 0 0
P 0 20 700
Q 18 8 1000 Maximum
R 24 0 960

 Among all the points in the set S, the point(s) that optimizes the objective function

of the linear programming problem is called an optimal solution.

 In our Example, since z is highest at point Q, optimal solution is to produce 18 units

of product A and 8 units of product B every week, to get the profit Birr 1000. No

other product mix under the given conditions could yield more profit than this.
II. Minimization

 Now we shall consider the graphical solution to the LP problems the

minimization nature. Here , Example, 2.2 is reconsidered.

• 𝑀𝑖𝑛𝑚𝑖𝑧𝑒 𝑧 = 40𝑥1 + 24𝑥2 …Total cost

• Subject to 20𝑥1 + 50𝑥2 ≥ 4800 …phosphate requirements

80𝑥1 + 50𝑥2 ≥ 7200… Nitrogen requirements

𝑥1 , 𝑥2 ≥ 0 ……………….…Non Negativity

 Here the decision variables 𝑥1 and 𝑥2 , represent, respectively, the number of

bags mixture A and of mixture B, to be bought.

 First graph restrictions.

Constraint #1: 20𝑥1 + 50𝑥2 ≥ 4800
 Steps to draw
o replace the inequality with an equality, 20𝑥1 + 50𝑥2 ≥ 4800 ,
o Find intercepts
𝑥1 𝑥𝟐
0 96
240 0

o draw the graph

Constraint #2: 80𝑥1 + 50𝑥2 ≥ 7200

 Steps to draw

o replace the inequality with an equality, 80𝑥1 +

50𝑥2 ≥ 7200 ,

o Find intercepts

𝑥1 𝑥𝟐
0 144
90 0

o draw the graph

#Feasible and Optimal Solutions

 The constraints in a LP problem form a system of linear inequalities, which have

a solution set S.

 Each point in S is a candidate for the solution of the linear programming

problem and is referred to as a feasible solution.

 The set S itself is referred to as a feasible set.

 The feasible region in our example here represents a convex set, however, it is
not bounded from all the sides, as was incase of maximization problem.

 The region is unbounded on the upper side because none of the restrictions in the
problem places an upper limit on the value of either of the decision variables.

 Obviously, if such limits are placed, the feasible region would be a bounded one.
 So we need to obtain the ordinates of each of these points (given
values of 𝑥1 and 𝑥2 ) and calculate the values of objective function
by substituting them in objective function.

 For intersection points we can obtain values by solving

simultaneously equations representing those lines.

 In our example the ordinate point Q can be obtained by solving the

two equations simultaneously.

• 20𝑥1 + 50𝑥2 = 4800

• 80𝑥1 + 50𝑥2 = 7200

 This gives 𝑥1 = 40 and 𝑥2 = 80
• Obtaining the optimal solution- as incase of maximization problems, the optimal
solution can also be obtained at extreme point – at extreme point P, Q, or R in
our example. We can evaluate the ordinates at each of these points as follows.

• The Z- values corresponding to the various points in respect of the given

problem are shown here.
Points 𝑥1 𝑥2 𝑧 = 40𝑥1 + 35𝑥2
P 0 144 3456 Minimum
Q 40 80 3520
R 240 0 9600

 In our Example, since total cost is minimum at point P, optimal solution is to

buy 144 bags of mixture of B only and none of mixture of A. This would entail
a total cost of Birr 3456.
#Biding and Non Binding Constraints

• Once Optimal solution to an LPP is obtained, we may classify the constraints as binding

and non binding.

• Binding-A constraint is termed binding if the left hand side and right hand side if it are

equal when optimal decision variables are substituted into the constraint.

• Consider example 2.1, the optimal values of decision variables are 𝑥1 = 18 and 𝑥2 = 8.

• Substituting these values in the two constraints we get

2𝑥1 + 3𝑥2 = 60=2*18+3*8=60= (RHS) and

4𝑥1 + 3𝑥2 = 96=4*18+3*8= 96= (RHS)

Thus, both constraints are binding by nature.

Non binding-if the substitution of the decision variables does not lead to an

equality between left and right sides of the constraints, it is said to be non

binding. In example 2.2, 𝑥1 = 0 and 𝑥2 = 144

• Substituting these values in two equations we get

• 20𝑥1 + 50𝑥2 = 4800 =20*0+50*144=7200≠ 4800 𝑅𝐻𝑆 𝑎𝑛𝑑

• 80𝑥1 + 50𝑥2 = 7200= 80*0+50*144=7200=RHS

• Accordingly, the first of the constraints is non binding and the second one

is a binding one.
Some special cases

• In each of the two examples discussed so far, we have obtained a unique

optimal solutions.

• There are problems having multiple optimal solution, no feasible solution

and unbounded solution.

o Multiple Optimal Solution –In some cases in a given problem there may be

more than one optimal solution. Each of multiple optima would naturally

yield the same objective function value. To fully understand, let us consider

the following example.

Example 2.3. Solve graphically the following LP.
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑧 = 8𝑥1 + 16𝑥2
Subject to 𝑥1 + 𝑥2 ≤ 200
𝑥2 ≤ 125
3𝑥1 + 6𝑥2 ≤ 900
𝑥1 , 𝑥2 ≥ 0
• The constraints are shown in the following Figure.

• To obtain optimal solution we need to evaluate extreme points of the

feasible region as follows as:

Points 𝑥1 𝑥2 𝑧 = 8𝑥1 + 16𝑥2

O 0 0 0
A 0 125 2000
B 50 125 2400
C 100 100 2400 Maximum
D 200 0 1600

 The points B and C are optima values.

• Infeasibility- A linear program which is over constrained so that no point

satisfies all the constraints is said to be infeasible.

• As we have discussed a solution is said to be feasible if it satisfies all the

constraints and the non negative conditions.

• Sometimes it is possible that the constraints may be inconsistent so that there

so no feasible solution to the problem.

• Such a solution is called infeasible.

• Or he FR cannot be identified as constraints do not form a common area in

the first quadrant of the graph.

• This leads to the condition of infeasibility.

Example 2.4. Solve graphically the following LP.

𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑧 = 20𝑥1 + 30𝑥2

Subject to 2𝑥1 + 𝑥2 ≤ 40

4𝑥1 − 𝑥2 ≤ 20

𝑥1 ≥ 30

𝑥1 , 𝑥2 ≥ 0

 When we put these constraints in graph, we do not find common point in

the areas. Therefore, all the constraints can not be satisfied and such, there

is no feasible solution to the given problem.

• Unsoundness-For maximization type of LP problem, unsoundness occurs when there is no

constraint on the solution so that one or more of the decision variables can be increases

indefinitely without violating any of the restrictions (constraints).

• Thus, an unbounded LPP occurs if it is possible to find points in the feasible region with

arbitrarily large values (may be profit of revenue).

• This suggests that practically if we find the solution to be unbounded for a profit maximizing LP

problem, it may be concluded that the problem has not been correctly formulated.

• Consider the following example.

Example 2.4.

Maximize 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑧 = 10𝑥1 + 20𝑥2

𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 2𝑥1 + 4𝑥2 ≥ 16
4𝑥1 +5𝑥2 ≥ 15
𝑥1 , 𝑥2 ≥ 0
 Clearly the above figure shows, here the objective function is not bound over the
feasible region and we can move the iso-profit line upward without any limit.
 The problem has therefore, unbounded solution.
Exercise 2.3: A Production Problem

 Ace Novelty wishes to produce two types of souvenirs: type-A will

result in a profit of $1.00, and type-B in a profit of $1.20. To

manufacture a type-A souvenir requires 2 minutes on machine I and

1 minute on machine II. A type-B souvenir requires 1 minute on

machine I and 3 minutes on machine II. There are 3 hours available

on machine I and 5 hours available on machine II.

 How many souvenirs of each type should Ace make in order to

maximize its profit? Use graphic method.

Exercise 2.4.: A Nutrition Problem

 A nutritionist advises an individual who is suffering from iron and vitamin B

deficiency to take at least 2400 milligrams (mg) of iron, 2100 mg of vitamin

B1, and 1500 mg of vitamin B2 over a period of time. Two vitamin pills are

suitable, brand-A and brand-B. Each brand-A pill costs 6 cents and contains

40 mg of iron, 10 mg of vitamin B1, and 5 mg of vitamin B2. Each brand-B

pill costs 8 cents and contains 10 mg of iron and 15 mg each of vitamins B1

and B2.

 What combination of pills should the individual purchase in order to meet the

minimum iron and vitamin requirements at the lowest cost? Use graph

method.
Exercise 2.6. Solve graphically for the optimal solution:

Max z = 2x1 + 6x2

s.t. 4x1 + 3x2 < 12
2x1 + x2 > 8
x1, x2 > 0
Exercise 2.7. Solve graphically for the optimal solution:

Max z = 3x1 + 4x2

s.t. x1 + x2 > 5
3x1 + x2 > 8
x1, x2 > 0
2.2.2. Algebraic method or simplex Method.

 Graphical method studied earlier in section 2.2.1 is limited to business problems

with only two decision variables.

 Simplex algorithm overcomes this problem by offering a more versatile method to

solve business problems.

• This algorithm is one of the most popular ones used in finding solutions to business

problems.

• Simplex algorithm can deal with maximization and minimization problems under

constraints of resources and demand.

• The assumptions of additive, proportionality, divisibility and no negativity

discussed in section 2.2.1 hold good for developing an optimal solution using

simplex method.
2.2.2. Algebraic method or simplex Method

 The simplex method is an iterative procedure.

 Beginning at a vertex of the feasible region S, each iteration brings us to

another vertex of S with an improved value of the objective function.

• The iteration ends when the optimal solution is reached. S

• The assumptions of additive, proportionality, divisibility and no negativity

discussed in section 2.2.1 hold good for developing an optimal solution using

simplex method.

• Simplex algorithm can deal with maximization and minimization problems

under constraints.
i. Maximization Problems all constraints of ≤ type)

1. Standardize the problem

Introduce slack variables

2. Obtain initial solution (with slack variables)- initial simplex tableau.

3. Test if solution is optimal

o Determine whether the optimal solution has been reached by examining all

entries in the last row to the left of the vertical line.

4. If optimal, stop and exit; else go to step 5

o If all the entries are nonnegative, the optimal solution has been reached.

5. Obtain a revised solution and go back to step 3

Example : A Production Problem

 Ace Novelty wishes to produce two types of souvenirs: type-A will

result in a profit of $1.00, and type-B in a profit of $1.20. To

manufacture a type-A souvenir requires 2 minutes on machine I and 1

minute on machine II. A type-B souvenir requires 1 minute on

machine I and 3 minutes on machine II. There are 3 hours available

on machine I and 5 hours available on machine II.

 How many souvenirs of each type should Ace make in order to

maximize its profit? Use simplex method

Step 1: Convert the LP to standard form

Maximize the objective function

x1+1.2.x 2 = z

6
x1+ x2 = z
5

subject to the system of inequalities

2x1+x2+≤ 180

x1+3x2+≤ 300

• This is a standard maximization problem and may be solved by

the simplex method.
• To use simplex method introduce the slack variables s1 and s2 into the

inequalities and turn these into equations, getting

2x1+x2+s1+ 0S2=180

x1+3x2 +0s1+s2=300

 Next, rewrite the objective function in the form

6
Z= x1 + x2 +0S1 + 0S2
5
Step 2- obtaining the initial simplex tableau

x1 x2 s1 s2 z Constant
2 1 1 0 0 180
1 3 0 1 0 300
–1 – 6/5 0 0 1 0

Step 3. Determine whether the optimal solution has been reached.

– Since there are negative entries in the last row of the

tableau, the initial solution is not optimal.

x1 x2 s1 s2 z Constant
2 1 1 0 0 180
1 3 0 1 0 300
–1 – 6/5 0 0 1 0
Step 4. Perform the pivot operation.

 Obtain a revised solution and go back to step 3

 Since the entry – 6/5 is the most negative entry to the left of the vertical line
in the last row of the tableau, the second column in the tableau is the pivot
column.

 Divide each positive number of the pivot column into the corresponding entry
in the column of constants and compare the ratios thus obtained.

– We see that the ratio 300/3 = 100 is less than the ratio 180/1 = 180, so
row 2 is the pivot row.

x1 x2 s1 s2 z Constant
2 1 1 0 0 180
180= =180
1
1 3 0 1 0 300
300= =100
3
–1 – 6/5 0 0 1 0
 The entry 3 lying in the pivot column and the pivot row is the pivot element.
Perform the pivot operation.

x1 x2 s1 s2 z Constant
2 1 1 0 0 180

1 3 0 1 0 300

–1 – 6/5 0 0 1 0

 Convert the pivot element into a 1.

x1 x2 s1 s2 z Constant
2 1 1 0 0 180
𝟏
New 𝑹𝟐 = 𝑹
𝟑 𝟐 1 3 0 1 0 300
–1 – 6/5 0 0 1 0

x1 x2 s1 s2 z Constant
2 1 1 0 0 180
1/3 1 0 1/3 0 100
–1 – 6/5 0 0 1 0
  Use elementary row operations to convert the pivot column into a unit
column. For each row other than key the values of row shall

 New row element= old row element-( row element in the key column*
corresponding replacement value)
x1 x2 s1 s2 z Constant
New 𝑹𝟏 = 𝑶𝒍𝒅 𝑹𝟏 − 𝑹𝟐 2 1 1 0 0 180
1/3 1 0 1/3 0 100
𝟔
New𝑹𝟑 = 𝑶𝒍𝒅 𝑹𝟑 + 𝑹 –1 – 6/5
𝟓 𝟐 0 0 1 0

x1 x2 s1 s2 z Constant
5/3 0 1 –1/3 0 80
1/3 1 0 1/3 0 100
–3/5 0 0 2/5 1 120
 This completes an iteration.
 Step 5-Obtain a revised solution and go back to step 3

 The last row of the tableau contains a negative number, so an optimal

solution has not been reached.

 Therefore, we repeat the iteration step.

 Since the entry – 3/5 is the most negative entry to the left of the

vertical line in the last row of the tableau, the first column in the

tableau is now the pivot column.

x1 x2 s1 s2 z Constant
5/3 0 1 –1/3 0 80
1/3 1 0 1/3 0 100
–3/5 0 0 2/5 1 120
 Divide each positive number of the pivot column into the corresponding
entry in the column of constants and compare the ratios thus obtained.

 We see that the ratio 80/(5/3) = 48 is less than the ratio 100/(1/3) = 300, so
row 1 is the pivot row now
x1 x2 s1 s2 z Constant
5/3 0 1 –1/3 0 80 80
=48
5/3
1/3 1 0 1/3 0 100 100
=300
1/3
–3/5 0 0 2/5 1 120

x1 x2 s1 s2 z Constant
5/3 0 1 –1/3 0 80
1/3 1 0 1/3 0 100
–3/5 0 0 2/5 1 120

 The entry 5/3 lying in the pivot column and the pivot row is the pivot element.
  Convert the pivot element into a 1.
x1 x2 s1 s2 z Constant
𝟑 5/3 0 1 –1/3 0 180
New 𝑹𝟏 = 𝟓 𝑹𝟏
1/3 1 0 1/3 0 100
–3/5 0 0 2/5 1 120

 Use elementary row operations to convert the pivot column into a unit column.

x1 x2 s1 s2 z Constant
5/3 0 1 –1/3 0 180
𝟏 1/3 1 0 1/3 0 100
New 𝑹𝟐 = 𝑶𝒍𝒅 𝑹𝟐 − 𝟑 𝑹𝟏
𝟑 –3/5 0 0 2/5 1 120
New𝑹𝟑 = 𝑶𝒍𝒅 𝑹𝟑 + 𝟓 𝑹𝟏

x1 x2 s1 s2 z Constant
1 0 3/5 –1/5 0 48
0 1 –1/5 2/5 0 84
0 0 9/25 7/25 1 148.8
 The last row of the tableau contains no negative numbers, so an optimal solution
has been reached.
Step 4.in revised . Determine the optimal solution.

 Locate the basic variables in the final tableau.

• In this case, the basic variables are x1 , x2 and z

o The optimal value for x1 48.

o The optimal value for x2 is 84.

o The optimal value for z is 148.8.

o Thus, the firm will maximize profits at $148.80 by producing 48 type-A

souvenirs and 84 type-B souvenirs.