Thapar Institute of Engineering and Technology, Patiala

School of Mathematics
Optimization Methods (UMA-035)
Lab Experiment - 1 (Graphical Method)

Algorithm of Graphical Method to solve LPP

Step 1: Enter the provided data (coefficients of variables in objective function, coefficients of
variables in constraints, right hand side elements of the constraints) in array’s (namely C, A, B).
Step 2: Select the range of x1 in which graph to be plotted.
Step 3: Find non-negative value of 𝑥2 from the ith constraint (say 𝑥2𝑖 ) in terms of 𝑥1
Step 4: Plot the graph between 𝑥2𝑖 and 𝑥1
Step 5: Assume an empty array (say, solution) matrix to store the obtained solution
Step 6: Store the ith row of A in an array (say, A1)
Step 7: Store the ith row of B in an array (say, B1)
Step 7: Store the (i+1)th row of A in an array (say, A2)
Step 8: Store the (i+1)th row of B in an array (say, B2)
Step 9: Combine A1 and A2 (say, A3)
Step 10: Combine B1 and B2 (say, B3)
Step 11: Find solution of system of equations A3X=B3
Step 12: Store solution in the considered empty array
Step 13: Assume first column of solution as x1
Step 14: Assume second column of solution as x2
Step 15: Find such rows of solution which does not satisfy the first constraint
Step 16: Delete such rows from Solution
Step 17: Assume first column of solution as x1
Step 18: Assume second column of solution as x2
Step 19: Find such rows of solution which does not satisfy the first constraint
Step 20: Repeat for all the constraints
Step 21: Find value of objective function (say, OBJ) corresponding to ith row of solution
Step 22: Find maximum or minimum value of objective function
Step 23: Find that row corresponding to which OBJ is max or min
Step 24: The row represents an optimal solution

Write a MATLAB code to solve the following LPPs by graphical method:

1. Maximize/Minimize (3x1 + 2x2) Subject to 2x1 +4x2< = 8, 3x1 + 5x2>= 15,

x1>=0, x2>= 0.
2. Maximize/Minimize (3x1 + 2x2) Subject to 2x1 +4x2> = 8, 3x1 + 5x2>= 15,
x1>=0, x2>= 0.
3. Maximize/Minimize (3x1 + 2x2) Subject to 2x1 +4x2< = 8, 3x1 + 5x2<= 15,
x1>=0, x2>= 0
 Thapar Institute of Engineering and Technology, Patiala
School of Mathematics

Optimization Techniques (UMA-035)

Lab Experiment- 2 (Basic feasible solutions)
————————————————————————————————————————–

Algorithm to find BFS

Consider the LPP:

Max z = C t X
subject to AX = b, X ≥ 0
Initially define Input paramenters:
1. Number of constraints as m,
2. Number of unknowns n,
3. Entries bi of the R.H.S. vector b and entries aij of matrix A,
4. Position of basic variables as pi where 1 ≤ i ≤ m .

Step 1: Construct the basis matrix B from the already defined basic variables pi ’s.
Step 2: If det(B) 6= 0, then find XB = B −1 b, otherwise display (’ Not a Basic solution’) and
STOP.
Step 3: If XBi < 0 for some i then display (’ Not a B.F.S’) and STOP.
If XBi = 0 for some i then display (’ Degenerate B.F.S’ ) and STOP.
If XBi > 0 for all i then display (’ Non-degenerate B.F.S’ ) and STOP.

Write a MATLAB code to compute the basic feasible solutions of an LPP and test your program
on the following set of examples:
1. Convert the following linear programming problem in standard form and find all bfs.
M ax. z = x1 + 2x2 , subject to − x1 + x2 ≤ 1, x1 + x2 ≤ 2, x1 , x2 ≥ 0.

2. Check if the the variables (1) (x1 , x4 ) (2) (x3 , x2 ) can be in the basis for the following problem
M ax. z = x1 + 2x2 − x3 + x4 ,

subject to x1 + x2 − x3 + 3x4 = 15, 5x1 + x2 + 4x3 + 15x4 = 12, x1 , x2 , x3 , x4 ≥ 0.

3. Solve the following LPP by using finding all its BFS.

M ax. z = −x1 + 2x2 − x3 , subject to x1 ≤ 4, x2 ≤ 4, − x1 + x2 ≤ 6, − 1x1 + 2x3 ≤ 4, x1 , x2 , x3 ≥

4. Check if the following LPP has a degenerate BFS, Find all basis corresponding to this solution.
M ax. z = x1 + x2 + x3 , subject to x1 + x2 ≤ 1, − x2 + x3 ≤ 0, x1 , x2 , x3 ≥ 0.

1
 Thapar Institute of Engineering and Technology, Patiala
School of Mathematics
Optimization Techniques (UMA-035)
Lab Experiment- 3 (The simplex method)
————————————————————————————————————————–
The Simplex Algorithm ( with slack variables only)

Consider an LPP with all constraints of (≤) type given as

Max z = C t X
subject to AX ≤ b, X ≥ 0
Convert the above problem to standard form by adding slack variables:
Max z = C t X
subject to AX + IXs = b, X ≥ 0
Where Xs = (s1 , s2 , . . . , sm ) is a vector of slack variables.
Initially definethe following Input paramenters:
1. Enter the Matrix A = [A I], where I is an identity matrix of order m.
2. Entries bi of the R.H.S. vector b and entries aij of matrix A
3. Define [m,n]=size (A)
4. Input the variables s1 , s2 , . . . sm as basic variables.
Step 1: Construct the basis matrix B from the already defined basic variables.
Step 2: Calculate Zj − cj = CBt (B −1 Aj ) − cj for each j ∈ 1, 2 . . . n
Find [val, k] = min{(Zj − cj ), j ∈ 1,  2 . . . n} 
XBi k xB
While val < 0 calculate θk = min k
| αi > 0 = kr and go to next step
i∈1,2...m αi αr
Step 3 Update the basis by leaving the variable xk and entering the variable xl = (xBr ) and go to
Step 1.
Note: The variables in the basis are named as (xB1 , xB2 , . . . xBm ) and in the present case we have
initial basic variables as slack variables taken in the order s1 , s2 , . . . sm . So one can understand that
initially xB1 = s1 , xB2 = s2 , . . . xBm = sm . Similarly when the basis is updated by adding a variable
xk to the basis by replacing a variable xl = xBr , then the new rth basic variable will be xBr = xl .
Write a MATLAB code for the simplex method and test your program on the following
examples:
1 M ax. z = x1 + 2x2 , subject to − x1 + x2 ≤ 1, x1 + x2 ≤ 2, x1 , x2 ≥ 0.
2 M ax. z = 4x1 + 6x2 + 3x3 + x4 , (Ans: x1 = 1/3, x3 = 4/3s2 = 3; z = 16/3
subject to
x1 + 4x2 + 8x3 + 6x4 ≤ 11, 4x1 + x2 + 2x3 + x4 ≤ 7, 2x1 + 3x2 + x3 + 2x4 ≤ 2, x1 , x2 , x3 ≥ 0.
3 M in. z = −3/4x4 + 20x5 − 1/2x6 + 6x7 , (Ans: x1 = 3/4, x4 = 1, x6 = 1; z = −5/4
subject to
x1 + 1/4x4 − 8x5 − x6 + 9x7 = 0, x2 + 1/2x4 − 12x5 − 1/6x6 + 3x7 = 0, x3 + x6 = 1,
xi ≥ 0, i = 1, 2 . . . 7

2
 Thapar Institute of Engineering and Technology, Patiala
School of Mathematics
Optimization Techniques (UMA-035)
Lab Experiment- 4 (The Big-M method)
————————————————————————————————————————–
The Big M method
Consider an LPP with mixed type of constraints (≤, ≥, =) and then convert the problem into
standard form as given below.
(P) Max z = C t X ‘
subject to AX = b, X ≥ 0
Assume that the matrix A does not have an identity submtrix in it. Now, add artificial variables
Ri for i ∈ {1, 2, . . . , m} so that the new problem has a identity submatrix in it, and the matrix A
is now updated as [AI]. Assign a value M > 105 max(ci ), for convenience, the value of M can be
taken as M = 106 .
Now the new problem is of the following form:
(Ps ) Max z = C t X + 106 .et R
subject to AX + IRi = b, X, R ≥ 0
Where R = (R1 , R2 , . . . , Rm ) is a vector of artificial variables and e = (1, 1, . . . , 1)t is a vector of
one’s.
Initially define the following Input paramenters:
1. Enter the Matrix A = [A I], where I is an identity matrix of order m.
2. Entet the the R.H.S. vector b and the cost matrix C = [C 106 e].
3. Define [m,n]=size (A)
4. Input the variables R1 , R2 , . . . Rm as basic variables.
Now apply simplex method to solve the problem (Ps ). Suppose an optimal basic feasible solution
of the problem (Ps ) so obtained is XB .
If (XBi = Rj > 0, for some i, j ∈ {1, 2, . . . , m}) %i.e. artificial variable appear in basis
display( The problem (P) is infeasible)
Else (XBi 6= Rj , for all i, j ∈ {1, 2, . . . , m})
display (XB is an optimal basic feasible solution of problem (P) )

Note: The variables in the basis are named as (xB1 , xB2 , . . . xBm ) and in the present case we have
initial basic variables as artificial variables taken in the order R1 , R2 , . . . Rm . So one can understand
that initially xB1 = R1 , xB2 = R2 , . . . xBm = Rm . The idea behind Big M method is to remove
artifical variables from the basis
Similarly when the basis is updated by adding a variable xk to the basis by replacing a variable
xl = xBr , then the new rth basic variable will be xBr = xl .
Write a MATLAB code for the simplex method and test your program on the following
examples:
1. M in. z = 3x1 + 5x2 , S.T. x1 + 3x2 ≥ 3, x1 + x2 ≥ 2, x1 , x2 ≥ 0.
2. M in. z = 12x1 + 10x2 , S.T. 5x1 + x2 ≥ 10, 6x1 + 5x2 ≥ 30, x1 + 4x2 ≥ 8, x1 , x2 ≥ 0.
3. M ax. z = 3x1 + 2x2 , S.T. x1 + x2 ≤ 2, x1 + 3x2 ≤ 3, x1 − x2 = 1 x1 , x2 ≥ 0.

3
 Thapar Institute of Engineering and Technology, Patiala
School of Mathematics
Optimization Techniques (UMA-035)
Lab Experiment- 5 (The Two phase method)
————————————————————————————————————————–
The Two phase method
Consider an LPP with mixed type of constraints (≤, ≥, =) and then convert the problem into
standard form as given below.
(P) Max z = C t X ‘
subject to AX = b, X ≥ 0
Assume that the matrix A does not have an identity submatrix in it. Now, add artificial variables
Ri for i ∈ {1, 2, . . . , m} so that the new problem has a identity submatrix in it, and the matrix A
is now updated as [A I]. Now construct the Phase-I problem as
(P H1 ) min z = Ot X + et R
subject to AX + IRi = b, X, R ≥ 0
Where R = (R1 , R2 , . . . , Rm )t is a vector of artificial variables and e = (1, 1, . . . , 1)m×1 is a vector
of one’s and O = (0, 0 . . . , 0)n×1 is a vector of zeros.
Initially define the following Input paramenters:
1. Enter the Matrix A = [A I], where I is an identity matrix of order m.
2. Entet the the R.H.S. vector b and the cost matrix C = [O e](n+m)×1 .
3. Define [m,n]=size (A)
4. Input the variables R1 , R2 , . . . Rm as initial basic variables.
Now apply simplex method to solve the problem (P H1 ). Suppose an optimal basic feasible solution
of the problem (Ps ) so obtained is XB .
If (XBi = Rj > 0, for some i, j ∈ {1, 2, . . . , m}) %i.e. artificial variable appear in basis
display( The problem (P) is infeasible)
Else (XBi 6= Rj , for all i, j ∈ {1, 2, . . . , m})
display (XB is an optimal basic feasible solution of problem (P H1 ) and goto Phase II )
Phase-II
Treat the optimal basic feasible solution of Phase-I as initial basic feasible solution of Phase-II,
while incorporating the folloiwng:
1. Update the cost matrix C = (c1 , c2 . . . cn )t from original variables.
2. Update the matrix Alpha =Alpha(1:n,:) ( where Alpha=inv(B)*A)
( means ignore the columns of artifial variables and update Alpha matrix by considering only
first n columns of original variables)
3. Calculate Zj − cj and follow the simplex procedure to obtain an optimal basic feasible solution
of the problem (P).
Note: The variables in the basis are named as (xB1 , xB2 , . . . xBm ) and in the present case we have
initial basic variables as artificial variables taken in the order R1 , R2 , . . . Rm . So one can understand
that initially xB1 = R1 , xB2 = R2 , . . . xBm = Rm . The idea behind Phase-I method is to remove
artifical variables from the basis and obtain an initial basic feasible solution of the problem (P).
Then Phase-II uses the BFS obtained in Phase-I to get an optimal BFS of problem (P).
Write a MATLAB code for the two phase method and test your program on the
following examples:

4
1. M in. z = 3x1 + 5x2 , S.T. x1 + 3x2 ≥ 3, x1 + x2 ≥ 2, x1 , x2 ≥ 0.
2. M in. z = 12x1 + 10x2 , S.T. 5x1 + x2 ≥ 10, 6x1 + 5x2 ≥ 30, x1 + 4x2 ≥ 8, x1 , x2 ≥ 0.
3. M ax. z = 3x1 + 2x2 , S.T. x1 + x2 ≤ 2, x1 + 3x2 ≤ 3, x1 − x2 = 1 x1 , x2 ≥ 0.

5
 Thapar Institute of Engineering and Technology, Patiala
School of Mathematics

Optimization Techniques (UMA-035)

Lab Experiment- 6 (The dual simplex method)
————————————————————————————————————————–

The dual simplex method

Convert the given linear programming problem in the following form:
(P ) min / max z = C t X + Ot s
subject to AX + Is = b, X, s ≥ 0
Where s = (s1 , s2 , . . . , sm )t is a vector of slack variables and O = (0, 0 . . . , 0)n×1 is a vector of zeros.
Also Assume that atleast one of the component bi of the RHS vector b = (b1 , b2 , . . . , bm ) is negative
Initially define the following Input paramenters:
1. Enter the Matrix A = [A I], where I is an identity matrix of order m.
2. Entet the the R.H.S. vector b and the cost matrix C = [c O](n+m)×1 .
3. Define [m,n]=size (A)
4. Input the variables s1 , s2 , . . . sm as initial basic variables.
Now construct the simplex table using s1 , s2 , . . . , sm as initial basic variables. If the simplex table
depicts an optimal but Infeasible solution, then dual simplex method is applicable. So apply
the following procedure.
1. Select the leaving variable as XBr = min{XBi | XBi < 0}
i
 
zk − ck |zj − cj |
2. Select the entering variable xk using the formula = minj : yrj < 0
yrk |yrj |
3. Now update the basis as by removing rth basic variable with k th nonbasic variable. Again
construct the simplex table and repeat the above procedure until an optimal basic feasible
soluiton is not obtained.
Write a MATLAB code for the dual simplex method and test your program on the
following examples:
1. M in. z = 3x1 + 5x2 , S.T. x1 + 3x2 ≥ 3, x1 + x2 ≥ 2, x1 , x2 ≥ 0.
2. M in. z = 12x1 + 10x2 , S.T. 5x1 + x2 ≥ 10, 6x1 + 5x2 ≥ 30, x1 + 4x2 ≥ 8, x1 , x2 ≥ 0.
3. min. z = 3x1 + 2x2 , S.T. x1 + x2 ≤ 1, x1 + 2x2 ≥ 3, x1 , x2 ≥ 0.

6
 Thapar Institute of Engineering and Technology, Patiala
School of Mathematics
Optimization Techniques (UMA-035)
Lab Experiment- 7 (Least cost method)
————————————————————————————————————————–
Least cost method of Transportation problem
Consider a cost matrix representation of a Transportation problem:

ui ↓
c11 c12 ... c1n
x11 x12 x1m a1

c21 c22 ... c2n

x21 x22 x2m a2
.
. .
. .
.
cm1 cm2 ... cmn
xm1 xm2 xmn am

b1 b2 ... bn
Here ai is the availability of the product at source Si and bj is the requirement of the same at
destination Dj , cij represents the cost of trasporting a unit product from source Si to destination
Dj . The variable xij is the quantity to be transported from the source i to destination j.

Initially define Input paramenters:

1. Enter the number of sources as m, and destinations as n.
2. Enter the cost coefficients cij , the availabilty at ith source as ai and demand at j th destination
as bj for each i = 1, 2 . . . m , j = 1, 2, . . . n.
Intially take k = 1
Step 1: Define cpq = min(cij ), and assign xpq = min(ap , bq ), go to Step 2.
Step 2: If min(ap , bq ) = ap , then update bq = bq − ap , ap = ap − xpq else min(ai , bj ) = bq , then
update ap = ap − bq , bq = bq − xpq .
Step 3 Assigne cpq = 105 (a very large no.) , Setk = k + 1, if k = m + n − 1 go to Step 4 else go
to Step 1.
X
Step 4: Stop and note the BFS and calculate the objective function value z = cij xij
i,j

Write a MATLAB code to compute the basic feasible solutions of a Transportation problem using
Northwest corner rule and test your program on the following set of examples:
1. Consider the cost matrix of the following transportation roblem
D1 D2 D3 D4 ai
S1 2 10 4 5 12
S2 1 6 12 8 11 25
S3 3 9 5 7 20
bj 25 10 15 5

7
2. Consider the cost matrix of the following transportation roblem
D1 D2 D3 D4 D5 ai
S1 3 11 4 14 15 15
S2 6 16 18 2 28 25
S3 10 13 15 19 17 10
S4 7 12 5 8 9 15
bj 20 10 15 15 5

8
 Thapar Institute of Engineering and Technology, Patiala
School of Mathematics
Optimization Methods (UMA-035)
Lab Experiment - 8 (Multi-objective LPP)

Algorithm of Weighted Sum Method to multi-objective LPP

Step 1:Transform the multi-objective linear programming problem (P1) into its equivalent single
objective linear programming problem (P2).
(P1)
Maximize/Minimize (CiX), i=1,2,…,m
Subject to
AX<= or =or >= b
X>=0.
(P1)
Maximize/Minimize (C1X+ C2X+…+ CmX)/m
Subject to
AX<= or =or >= b
X>=0.
Step 2: Find an optimal solution of the problem i.e., an efficient solution of the problem (P1) by an
appropriate method (Simplex method or Big-M method or Two-Phase method).

Write a MATLAB code to solve the following multi-objective LPPs by weighted sum method:

1. Maximize (3x1 + 2x2+4x3) 2. Maximize (x1 + 4x2+x3)

Maximize (x1 + 5x2+3x3) Maximize (2x1 + 7x2+5x3)
Subject to Subject to
2x1 +4x2 +x3< = 8, x1+x2 +x3< = 8,
3x1 + 5x2 +4x3>= 15, x1+ 5x2 +4x3>= 15,
x1>=0, x2>= 0, x3>= 0 x1>=0, x2>= 0, x3>= 0
 Thapar Institute of Engineering and Technology, Patiala
School of Mathematics
Optimization Methods (UMA-035)
Lab Experiment - 9 (Fibonacci Search Technique)

Algorithm of Fibonacci Search Technique

Fibonacci numbers

𝐹0 𝐹1 𝐹2 𝐹3 𝐹4 𝐹5 𝐹6 𝐹7 𝐹8
1 1 2 3 5 8 13 21 34

𝐹0 = 1, 𝐹1 = 1, 𝐹𝑛 = 𝐹𝑛−1 + 𝐹𝑛−2 , 𝑛 > 1.

𝐼𝑛𝑡𝑒𝑟𝑣𝑎𝑙 𝑜𝑓 𝑢𝑛𝑐𝑒𝑟𝑡𝑎𝑖𝑛𝑡𝑦
Step 1: Using the relation, Measure of effectiveness= , find the value of
𝐿0
Measure of effectiveness.
1
Step 2: Using the relation 𝐹 ≤ Obtained value of measure of effectiveness, find the smallest natural
𝑛
number 𝑛.
Step 3:Store the given interval 𝑎, 𝑏
Step 3: Find 𝐿0 = 𝑏 − 𝑎
Step 4:for 𝑖 = 𝑛, find
𝐹𝑖−2 𝐹𝑖−1
𝑥1 = 𝑎 + 𝐿0 , and 𝑥2 = 𝑎 + 𝐿0 ,
𝐹𝑖 𝐹𝑖

Step 5:If 𝑓 𝑥1 > 𝑓 𝑥2 and the problem is of minimum. Then, repeat Step 3 with 𝑛 = 𝑛 − 1𝑎 =
𝑥1 and 𝑏 = 𝑏.
If 𝑓 𝑥1 < 𝑓 𝑥2 and the problem is of minimum. Then, repeat Step 3 with 𝑛 = 𝑛 − 1𝑎 = 𝑎and
𝑏 = 𝑥2 .
If 𝑓 𝑥1 > 𝑓 𝑥2 and the problem is of maximum. Then, repeat Step 3 with 𝑛 = 𝑛 − 1𝑎 = 𝑎and
𝑏 = 𝑥2 .
If 𝑓 𝑥1 < 𝑓 𝑥2 and the problem is of maximum. Then, Then, repeat Step 3 with 𝑛 = 𝑛 − 1𝑎 =
𝑥1 and 𝑏 = 𝑏.
Step 6:Repeat Step 3 to upto 𝑖 = 2.

Write a MATLAB code to solve the following problem

Example:
Minimize the function 𝑥(𝑥 − 2), 0 ≤ 𝑥 ≤ 1.5 within the interval of uncertainty 0.25L0.