Industrial Engineering linear programming 4th Lecture
SOLUTION OF LINEAR PROGRAMMING MODELS
1 . The Graphical Method ( GM )
2 . The simplex Method ( SM ) The Graphical Method ( GM ) - So far we have
learnt how to construct a mathematical model for a Linear Programming Problem
( LPP ) If we can find the values of the decision variables X1 X2 , X3 , . . . . . Xn ,
which can optimize ( maximize of minimize ) the objective function Z then we say
that these values of x , are the optimal solution of the Linear Program ( LP ) .
The graphical method is applicable to solve the LPP involving two decision
variables x1 , and x2 . We may take these decision variables as x , y instead of x1 ,
X2 To solve the LP model , the graphical method includes two major steps
a ) The determination of the solution space that defines the feasible solution . Note
that the set of values of the variables x1 , R2 , X3 . . . . . X which satisfy all the
constraints and also the non - negative conditions is called the feasible solution of
the LP .
b ) The determination of the optimal solution from the feasible region .
To determine the feasible solution of a LP , we have the following steps Step 1
: Since the two decision variables X1 and X2 are non - negative , consider only the
first quadrant of xy - coordinate plane .
Step 2 : Each constraint is of the form ax1 + bx2 ≤ c or ax1 + bx2 ≥c
Draw the line ax1 + bx2 = c
For each constraint , the line ( 1 ) divides the first quadrant in to two regions say R
, and R2 , suppose ( X1 , 0 ) is a point in R . If this point satisfies the equation ax +
by ≤ c or (≥ c ) , then shade the region R1 . If ( x1 , 0 ) does not satisfy the inequality
, shade the region R2 .
Step 3 : Corresponding to each constraint , we obtain a shaded region . The
intersection of all these shaded regions is the feasible region or feasible solution of
the LP .
Industrial Engineering linear programming 4th Lecture
Ex: find the feasible solution for the LP model .
maximize z = 50x1 + 18x2
Subject to the constraints
2x1 + x2 ≤ 100 ( 1 )
x1 + x2 ≤ 80 (2)
x1 ≥ 0 x2 ≥ 0
Step 1 : Since x2 ≥0 , x2 ≥0 , we consider only the first quadrant of the xy - plane
Step 2 : We draw straight lines for the equation
2x1 + x2 = 100
x1 + x2 = 80
To determine two points on the straight line 2x1 + x2 = 100
Put x2 = 0 , 2x1 = 100
x1 = 50
( 50 , 0 ) is a point on the line ( 1 )
put x = 0 in ( 2 ) , y = 100
( 0 , 100 ) is the other point on the line ( 1 ).
Plotting these two points on the graph paper .
In the same manner (80,0) and (0,80) will be the two points of the line (2) for the
equation x1 + x2 = 80
Industrial Engineering linear programming 4th Lecture
draw the line which represent the line 2x1 + x2 = 100 . Every point in the shaded
region OABC is a feasible solution of LPP ,
since this point satisfies all the constraints including the non - negative Constraints
b ) .This method includes the following steps :
Step 1 : Find the feasible region of the LLP .
Step 2 : Find the co - ordinates of each vertex of the feasible region . These co -
ordinates can be obtained from the graph or by solving the equation of the lines .
Step 3 : At each vertex ( corner point ) compute the value of the objective function
.
Step 4 : identify the corner point at which the value of the objective function is
maximum ( or minimum depending on the LP ) The co - ordinates of this vertex is
the optimal solution and the value of Z is the optimal value .
Industrial Engineering linear programming 4th Lecture
2x1 + x2 = 100
x1 + x2 = 80
x1=20 , x2=60 , B(20,60)
Points Max Z = 50X1 + 18X2
O (0,0) 0
A (0,80) 1440
B (20,60) 2080
C (50,0) 2500 the maximum value is the optimal solution
Industrial Engineering linear programming 4th Lecture
The Simplex Method
For solving problems involving more than two variables or problems involving a
large number of constraints. It provides us with a systematic way of examining the
vertices of the feasible region to determine the optimal value of the objective
function. It provides us with a systematic way for examining the vertices of the
feasible region to determine the optimal value of the objective function.
The linear programming problem standard form
Z= 𝑐1 𝑥1 +𝑐2 𝑥2 +…..+𝑐𝑛 𝑥𝑛 Objective function(Max or Min )
Subject to
𝑎11 +𝑎12 𝑥2 +…..+𝑎1𝑛 𝑥𝑛 ≤ 𝑏1
𝑎21 𝑥1 +𝑎22 𝑥2 +…..+𝑎2𝑛 𝑥𝑛 ≤ 𝑏2
.
Constraints
.
𝑎𝑚1 𝑥1 +𝑎𝑚2 𝑥2 +…..+𝑎𝑚𝑛 𝑥𝑛 ≤ 𝑏𝑚
Where
xi ≥ 0 and bi ≥ 0 Non-negative constraints
After adding slack variables, the corresponding system of constraint equations
is
𝑎11 𝑥1 +𝑎12 𝑥2 +…..+𝑎1𝑛 𝑥𝑛 + 𝒔𝟏 = 𝑏1
𝑎21 𝑥1 +𝑎22 𝑥2 +…..+𝑎2𝑛 𝑥𝑛 + 𝒔𝟐 = 𝑏2 slack variable
.
.
𝑎𝑚1 𝑥1 +𝑎𝑚2 𝑥2 +…..+𝑎𝑚𝑛 𝑥𝑛 + 𝒔𝒎 = 𝑏𝑚
Where 𝒔𝒊 ≥0
Industrial Engineering linear programming 4th Lecture
Example 2:
Find the optimal solution for the following linear programming model
Max Z = 4𝑥1 + 6𝑥2
Subject to
- 𝑥1 + 𝑥2 ≤ 11
𝑥1 + 𝑥2 ≤ 27
2𝑥1 +5𝑥2 ≤ 90
𝑥1 , 𝑥2 ≥ 0
Solution:
1-Convert each in quality in the set of constraints to an equation by adding slack
variables
- 𝑥1 + 𝑥2 + 𝑆1 = 11
𝑥1 + 𝑥2 + 𝑆2 = 27
2𝑥1 + 5𝑥2 + 𝑆3 = 90
Z-4x1-6x2=0
2- Constructing the initial simplex table
3-Locate the most negative entry in the bottom row .The column for this entry is
called the pivoting column .
4- Choose the departing or leaving variable from the row (pivot row) of the smallest
positive element.
5- The pivot element obtained from the intersection of the pivoting column and
pivoting row
. Entering variable
𝐁. 𝐯 𝒙𝟏 𝒙𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑 R.H.S Ratio(b)
Departing variable
𝑆1 -1 1 1 0 0 11 11/1=11
𝑆2 1 1 0 1 0 27 27/1=27
𝑺3 2 5 0 0 1 90 90/5=18
Z -4 -6 0 0 0 0
Pivoting column
Industrial Engineering linear programming 4th Lecture
6- Construct the new table after pivoting
𝑜𝑙𝑑 𝑝𝑖𝑣𝑜𝑡 𝑟𝑜𝑤
New pivot row =
𝑝𝑖𝑣𝑜𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡
New rows = old row − (𝑝𝑖𝑣𝑜𝑡 𝑐𝑜𝑙𝑢𝑚𝑛 𝑐𝑜𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡 ∗ 𝑛𝑒𝑤 𝑝𝑖𝑣𝑜𝑡 𝑟𝑜𝑤)
First iteration
𝐁. 𝐯 𝒙𝟏 𝒙𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑 R.H.S Ratio
𝑿𝟐 -1 1 1 0 0 11 -11
𝑺2 2 0 -1 1 0 16 8
𝑺3 7 0 -5 0 0 35 5
Z -10 0 6 0 0 66
Second iteration
𝐁. 𝐯 𝒙𝟏 𝒙𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑 R.H.S Ratio*
𝑿𝟐 0 1 2/7 0 1/7 16
𝑺𝟐 0 0 3/7 1 -2/7 6
𝑿1 1 0 -5/7 0 0 5
Z 0 0 -8/7 0 10/7 116
Third iteration
𝐁. 𝐯 𝒙𝟏 𝒙𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑 R.H.S Ratio*
𝑿𝟐 0 1 -2/3 0 1/3 12
𝑺𝟏 0 0 7/3 1 -2/3 14
𝑿1 1 0 5/3 0 -1/3 15
Z 0 0 0 8/3 2/3 132
7- When all elements in the bottom row have positive values means we have the
optimal solution.
(X1,X2,S1,S2,S3)= (15,12,14,0,0) with Z= 4X1+6X2=4*15+6*12 =132
Industrial Engineering linear programming 4th Lecture
Example
Find the optimal solution for the following LP model :
Minimize Z =X1-3X2+2X3 (
Subject to :
3X1 - X2+2X3 ≤ 7
-2X1 +4X2 ≤ 12
-4X1 + 3X2 +8X3 ≤ 10
X1 ,X2 ,X3 ≥ 0
Solution:
We have to change the problem into Max type ,take W= -Z.
Max W = - X1+3X2- 2X3
W+X1-3X2+ 2X3=0
Subject to 3X1 - X2+2X3 + S1= 7
-2X1 +4X2 +S2 = 12
-4X1 + 3X2 +8X3 +S3 = 10
𝐁. 𝐯 𝒙𝟏 𝒙𝟐 𝒙3 𝑺𝟏 𝑺𝟐 𝑺𝟑 R.H.S Ratio(b)
𝑆1 3 -1 2 1 0 0 7 7/-1
𝑆2 -2 4 0 0 1 0 12 12/4=3
𝑺3 -4 3 8 0 0 1 10 10/3=
3.3
W 1 -3 2 0 0 0 0
Industrial Engineering linear programming 4th Lecture
First iteration:
𝐁. 𝐯 𝒙𝟏 𝒙𝟐 𝒙3 𝑺𝟏 𝑺𝟐 𝑺𝟑 R.H.S Ratio(b)
𝑆1 5/2 0 2 1 1/4 0 10 4
𝑥2 -1/2 1 0 0 1/4 0 3 negative
𝑺3 -5/2 0 8 0 -3/4 1 1 negative
W -1/2 0 2 0 3/4 0 9
Second iteration:
𝐁. 𝐯 𝒙𝟏 𝒙𝟐 𝒙3 𝑺𝟏 𝑺𝟐 𝑺𝟑 R.H.S Ratio(b)
𝑥1 1 0 4/5 2/5 1/10 0 4
𝑥2 0 1 2/5 1/5 3/10 0 5
𝑺3 0 0 10 1 -1/2 1 11
W 0 0 12/5 1/5 4/5 0 11
Where all W ≥ 0 .The optimal solution is reached, x1=4 , x2= 5, x3=0, W= 11
And the solution of the given LPP is
x1=4 , x2= 5, x3=0, Z= - 11
