CHAPTER I

LINEAR PROGRAMMING PROBLEM

Linear Programming is a mathematical process that

has been developed to help management in decision
making, involving the efficient allocation of scares
resources to achieve a certain objective.

LP is a method for choosing the best alternative from

a set of feasible alternatives
To apply LP, the following conditions must be
satisfied:
a. Objective Function :Is the goal or objective of a
management, stated as an intent to maximize or to
minimize some important quantity such as profits
or costs.
b. Constraints: Are limitations or restrictions imposed
by the problems and constraints include:
1. Resource constraints: Are restrictions that should
be clearly identifiable and measurable in quantitative
terms, which arise from limitation of available
resources.
Examples of limited resources:
Plant capacity
Raw materials availability
Labor power
Market demand, etc
2. Non-negativity constraints: Are constraints that require the
decision variables not to take on negative values
c. Linearity: The Objective Function and the constraints must be
linear in nature in order to have a Linear Programming Problems
d. Feasible alternative
There should be a series of feasible alternative course of action
available to the decision-making determined by resource constraints.
Thus, we have to choose the best alternative
Linear Programming Problems can be solved by using:
i. The Geometric method called” Graphical Method”
1.2. GRAPHICAL SOLUTION
To use the graphic method, the following steps are
needed:
1. Identify the problem
i.e.: The decision variables, the objective function and
the constraints
2. Draw a graph including all the constraints and
identify the feasible region
3. Obtain a point on the feasible region that
optimizes the objective function-Optimal solution
4. Interpret the results
 Maximization Problem
Example: Consider two models of color TV sets;
Model A and B, are produced by a company to
maximize profit. The profit realized is $300 from A
and $250 from set B. The limitations are
a. availability of only 40hrs of labor each day in the
production department.
b. a daily availability of only 45 hrs on machine time
c. ability to sale 12 set of model A.
 Resource used per unit

Constraints Model A Model B MaximumAvailable hrs.

(X1) (X2)

Labor hr. 2 1 40

Machine hr. 1 3 45

Marketing hr. 1 0 12

Profit $300 $250

Required;
1. Formulate the mathematical model of the problem
2. How many sets of each model will be produced
each day so that the total profit will be as large as
possible?
Class activity
A manufacturer of high weight mountain tents makes two
types of tents, REGULAR tent and SUPER tent. Each
REGULAR tent requires 1 labor-hour from the cutting
department and 3labor-hours from the assembly department.
Each SUPER tent requires 2 labor-hours from the cutting
department and 4 labor-hours from the assembly department
.The maximum labor hours available per week in the cutting
department and the assembly department are 32 and 84
respectively. Moreover, the distributor, because of demand,
will not take more than 12 SUPER tents per week. The
manufacturer sales each REGULAR tents for $160 and
costs$110 per tent to make. Whereas SUPER tent sales for
$210 per tent and costs $130 per tent to make.
Required:
A. Formulate the mathematical model of the problem
B. Using the graphic method, determine how many of
each tent the company should manufacture each tent
the company should manufacture each week so as to
maximize its profit?
C. What is this maximum profit assuming that all the
tents manufactured in each week are sold in that
week?
Minimization Problem
A company owns two flour mills (A and B) which have
different production capacities for HIGH, MEDIUM and
LOW grade flour. This company has entered contract
supply flour to a firm every week with 12, 8, and 24
quintals of HIGH, MEDIUM and LOW grade
respectively. It costs the Co. $1000 and $800 per day to
run mill A and mill B respectively. On a day, mill A
produces 6, 2, and 4 quintals of HIGH, MEDIUM and
LOW grade flour respectively.
Mill B produces 2, 2 and 12 quintals of HIGH,
MEDIUM and LOW grade flour respectively. How many
days per week should each mill be operated in order to
meet the contract order most economically standardize?
SPECIAL CASES IN GRAPHICS METHODS
1. Redundant Constraint
If a constraint when plotted on a graph doesn’t form
part of the boundary making the feasible region of the
problem that constraint is said to be redundant.
Example:
A firm is engaged in producing two products A and B.
Each unit of product A requires 2Kg of raw material and
4 labor-hrs for processing. Where as each unit of
product B requires 3Kg of raw materials and 3hrs of
labor. Every unit of product A requires 4 hrs for
packaging where as B needs 3.5hrs. Every week the
firm has availability of 60Kg of raw material, 96 labor-
1 unit of product A sold yields $40 profit and 1 unit of
B sod yields $35 profit.
Required:
a. Formulate this problem as a LPP
b. Find the optimal solution
2. Multiple optimal Solutions
/Alternative optimal solutions/
-This is a situation where by a LPP has more than one
optimal solution.
Multiple optimal Solutions will be found if two
corners give optimal solution, then the line segment
joining these points will be the solution.
==>We have unlimited number of optimal solution
with out increasing or decreasing the objective
function.
Example:
The information given below is for the products A and B.
_____________________________________________________________________
Machine hours per week Maximumavailable
Department Product A Product B per week
_____________________________________________________________________

Cutting 3 6 900
Assembl y 1 1 200
Profit per unit $8 $16
_____________________________________________________________________
A ssume that the company has a marketing constraint on selling products B and
therefore it can sale a maximum of 125units of this product.
Required:
a. Formulate the LPP of this problem
b. Find the optimal solution
3. Infeasible Solution
A solution is called feasible if it satisfies all the
constraints and the constraints and non-negativity
condition. However, it is sometimes possible that the
constraints may be inconsistent so that there is no
feasible solution to the problem. Such a situation is
called infeasibility.
 The Simplex Method
• Simplex: a linear-programming algorithm that can solve
problems having two or more than two decision variables.
• The simplex technique involves generating a series of
solutions in tabular form, called tableaus. By inspecting the
bottom row of each tableau, one can immediately tell if it
represents the optimal solution. Each tableau corresponds to
a corner point of the feasible solution space.
• The first tableau corresponds to the origin. Subsequent
tableaus are developed by shifting to an adjacent corner
point in the direction that yields the highest (smallest) rate
of profit (cost).

17
 STEPS IN simplex method
 Initialization/Standardization:
a. transform all the constraints to equality by introducing slack,
surplus, and artificial variables
b. Construct the initial simplex tableau
 Iteration
– determine the entering basic variable by selecting the variable
(automatically a non-basic variable) with the most positive value (in case
of maximization) or with the most negative (in case of minimization) in the
last row (Cj-Zj-row).
– Determine the leaving basic variable by applying the
minimum ratio test as following:
• Divide the current value by its corresponding pivot element
(“pivot number”)

18
 Cont’d…
 Solve for the new BF solution by using
elementary row operations (multiply or divide a
row by a nonzero constant; add or subtract a
multiple of one row to another row)

 Divide the pivot row by the “pivot number” (the

number in the intersection of the pivot row and
pivot column)
 For each other row that has a positive coefficient
in the pivot column, subtract from this row the
product of the absolute value of this coefficient
and the new pivot row. 19
 Example 1

A Juice Company has available two kinds of food Juices: Orange

Juice and Grape Juice. The company produces two types of
punches: Punch A and Punch B. One bottle of punch A requires
20 liters of Orange Juice and 5 liters of Grape Juice.1 Bottle of
punch B requires 10 liters of Orange Juice and 15 liters of Grape
Juice.
From each of bottle of Punch A a profit of $4 is made and from each
bottle of Punch B a profit of $3 is made .Suppose that the
company has 230 liters of Orange Juice and 120 liters of Grape
Juice available
Required:
a. Formulate this problem as a LPP
b. How many bottles of Punch A and Punch B the company should
produce in order to maximize profit?
 Example 2
• An organization has three machine shops viz. A, B and C
and it produces three product viz. X1, X2 and X3. Using
these three machine shops. Each product involves the
operation of the machine shops. The time available at the
machine shops A, B and C are 100, 72 and 80 hours
respectively. The profit per unit of product X1, X2 and X3
is $22, $6 and $2 respectively. The following table shows
the time required for each operation for unit amount of each
product. Determine an appropriate product mix so as to
maximize the profit.

21
 Solution
Machine Products Time
Shop available
X1 X2 X3

A 10 2 1 100
B 7 3 2 72
C 2 4 1 80
Profit / unit 22 6 2
The linear programming formulation of the product mix
problem is:
Maximize: 22x1 + 6x2 + 2x3
Subject to: 10x1 + 2x2 + x3 ≤ 100
7x1 + 3x2 + 2x3 ≤ 72
2x1 + 4x2 + x3 ≤ 80
x1 , x2 , x3 ≥ 0 22
 Cont’d…
• We introduce slack variables S1, S2 and S3 to make the
inequalities equation. Thus, the problem can be stated as
Zmax : 22x1 + 6x2 + 2x3 + 0S1 + 0S2+ 0S3

Subject to: 10x1 + 2x2 + x3 + S1 = 100

7x1 + 3x2 + 2x3 + s2 = 72
2x1 + 4x2 + x3 + s3 = 80
x1, x2, x3, s1, s2, s3 ≥ 0
• From the above equation the Initial tableau can be
obtained in a straight forward manner. Here the basic
variables are S1, S2, and S3.
23
 Cont’d…

 Cj-Zj = 22 is the largest positive value. Hence X1 should be

taken as a basic variable in the next iteration.
 2. Calculate the minimum of the ratios
Min 100/10 , 72/7 , 80/2= 10
 The variable S1 corresponding to which minimum occurs is
made a non basic variable.
24
 Cont’d…
• 3. From the Table 1, the Table 2 is calculated using the
following rules:
• i. The revised basic variables are X1, S2, S3.
• ii. Since X1 is the incoming variable we make X1
coefficient one by dividing each element of row 1 by 10.
Thus the numerical value of the element corresponding to
X2 is 2/10, corresponding to X3 is 1/10, corresponding to S 1
is 1/10, corresponding to S2 is 0/10 and corresponding to S3
is 0/10 in Table 2.

25
 Cont’d…
iii. The incoming basic variable should only appear in
the first row. So we multiply first row of Table 2 by
7 and subtract it from the second row of Table 1
element by element.
Thus, The element corresponding to x1 in the second
row of Table 2 is zero.
The element corresponding to X2 is
3 – 7*2/10 = 16
By using this way we get the elements of the second
and the third row in Table 2. 26
 Cont’d…

1. cj-zj = 8/5. So x2 becomes a basic variable in the next iteration.

2. Calculate the minimum of the ratios
10/2/10, 7/16/10 , 60/18/5
Min = Min 50, 20/16, 300/18 = 20/16
Hence the variable S2 will be a non basic variable in the next
iteration.
27
 Cont’d…
 3. From Table 2, the Table 3 is calculated using the rules (i), (ii)
and (iii) mentioned above.

Note that all Cj – zj <0, so that the solution is X1 = 73/8, X2 =

30/8 and S3 = 177/4 maximizes the objective function. The
Maximum Profit is: 22*73/8 + 6*30/8 = 1606/8 + 180/8 =
1786/8 = $223.25
28
 Example 2
• Consider the following linear programming
problem
• Maximize: 60x1 + 70x2 +0s1 + 0s2 + 0s3
• Subject to: 2x1 + x2 + s1 = 300
3x1 + 4x2 + s2 = 509
4x1 + 7x2 + s3 = 812
x1, x2, s1, s2 ,s3 ≥ 0
• simplex computation starts with the first
compact standard simplex table as given
below: 29
 Cont’d…

Using the following rules the Table 2 is computed from

the Table 1.
i. The revised basic variables are s1, s2 and x2.

30
 Cont’d…
• ii. As x2 is the incoming basic variable we make the
coefficient of x2 one by dividing each element of
row-3 by 7. Thus the numerical value of the element
corresponding to x1 is 4/7, corresponding to s3 is
1/7 in Table 2.
• iii. The incoming basic variable should appear only
in the third row. So we multiply the third-row of
Table 2 by 1 and subtract it from the first-row of
Table 1 element by element. Thus the element
corresponding to x2 in the first-row of Table 2 is 0.
31
 Cont’d…
 Therefore the element corresponding to x1 is 2-1*4/7=10/7 and
the element corresponding to S3 is 0-1*1/7=-1/7

 3. Like Table 2, the Table 3 is computed sing the rules (i), (ii), (iii)
as described above.

32
Cont’d…

33
 Cont’d…
 From the Table 3, Table 4 is calculated following the usual steps.

Note that cj –zj ≥ 0 for all j, so that the objective function can’t be
improved any further.
Thus, the objective function is maximized for x1 = 691/5 and
x2=118/5 and The maximum value of the objective function is
9944.

34
 Big M Method
Example
• Solve the following linear programming model using the simplex
procedure.
Minimize: 6x1 + 9x2
Subject to:10x1 + 4x2 ≥ 400
X2 ≥ 14
x1, x2 ≥0
• We start the procedure by writing the model in its standard form. The
standard form for the above model is:
Minimize:6x1 + 9x2 + 0S1 + 0S2 + MA1 + MA2
Subject to:10x1 + 4x2 - S1 + A1 = 400
X2 – S2 + A2 = 14
x 1, x 2 ≥ 0 35
 Cont’d…

Once we developed a simplex tableau, testing it if it is giving

us the optimal solution should be our usual procedure. This
is done by looking at values in the net evaluation row.

36
 Cont’d…
• we develop the next tableau in a minimization
problem by selecting the variable with the largest
negative value to be the next variable to enter the
next tableau. Hence we will select 6 – 10M to be
the largest negative number. This is because M is
just a very large number. So, whenever we
compare numbers that involve M, we just
disregard any constant number associated with it,
but give attention to the coefficient of M. Then,
the one with the greatest coefficient will be
selected to be the largest number. Look at the
numbers in the net evaluation row of the initial
simplex tableau. 37
 Cont’d…
 10 is the greatest coefficient of M. This made
6–10M to be selected being the largest
negative number and an indicator for the next
variable to enter the basis. Look at the
following tableau:

38
 Cont’d…
• The second tableau is not the optimal tableau because
there is a negative number in the net evaluation row.
This indicates that we can get a better solution by
bringing the variable having this negative value (X 2
in this case) to the basis. Therefore, the 3 rd tableau is
developed by taking this concept into consideration.
Look at the following tableau.

39
Cont’d…

40
 Cont’d…
• Since there is no any negative value in the net
evaluation row, the 3rd tableau is the optimal tableau.
Therefore, the optimal solution to the above linear
programming model is: x1 = 34.4 and x2 = 14. The
level of the objective function is 332.4. There is no
slack variable in the final tableau. This means, the
solution to S1 and S2 is zero.

41
Thank you
42