OPTIMIZATION

TECHNIQUES
Course Instructor
Er. Suraj Shrestha
Assistant professor
Department of Electrical Engineering
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 1
Evaluation Scheme Evaluation Scheme
Internal 40 External 60
Attendance 5
Assignment 10
Assessment 20
Mini Project/Paper review 5
REFERENCE BOOKs
1. JK Sharma, Operation Research; Theory and Applications, Trinity
Publication.
2. Rao, Singiresu S. Engineering Optimization: theory and practice. John
Wiley & Sons, 2019.
3. Taha, Hamdy A. Operations research: an introduction. Pearson Education
India, 2013.
4. Prof. G Srinivasan, Operation Research: Principles and Applications,2010
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 2
 1. Linear Programming Problem
Mathematical Formulation
Example 1
Product Mix Problem
A shop can make two types of sweets (A and B). Let x1 be the number packet of sweets A made Decision
they use two resources flour and sugar. To make one Let x2 be the number packet of sweets B made Variable
packet of A, they need 3Kg of flour and 3 kg of
sugar. To make one packet of B they need 3 Kg of Maximize Z  1000 x1  900 x2 Objective Function
flour and 4 Kg of sugar. They have 21 Kg of Flour Subject to
and 28Kg of sugar. These sweets are sold at Rs. 3 x1  3 x2  21
1000 and 900 per packet respectively. Find the best Constraints
3 x1  4 x2  28
product mix to maximize the revenue.
x1 , x2  0 Non Negativity Restrictions

Flour Sugar Revenue per pkt

Sweets A 3Kg 3Kg Rs. 1000
B 3Kg 4Kg Rs. 900
Availability 21Kg 28Kg
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 3
 Terminology
• The problem variables xi are called, they represent the solution or output decision from the
problem. Decision variables
• The revenue function that manufacturer wishes to increase, represents the objective of making
decision on production quantity and is called Objective function.
• The condition matching the resources availability and resource requirement are called
Constraints. These usually limit (or restrict) the values of decision variables can take.
• Also decision variable also should take non negative value.
• This is true for all linear programming problem.
• This is called Non negativity restrictions.
• The problem that have been written down in algebraic form represents the mathematical model
of given system is called the problem formulation.
• In above formulation, the objective function and the constraints are linear. Therefore the model
that we formulated is a Linear Programming Problem (LPP).
• A linear programming problem has a linear objective function, linear constraints and the non
negativity constraints on all decision variables.
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 4
Problem Formulation has following steps Step 1: Identifying Decision Variables
1. Identifying decision variables. Let x1 be the number unit of Model A made
2. Writing objective functions Let x2 be the number unit of Model B made
3. Writing constraints Let x3 be the number unit of Model C made
4. Writing non-negativity restrictions. Step 2: Writing Objective Function
Example 2 Profit function Z  4 x1  2 x2  3 x3
Profit Maximization Problem Step 3: Writing Constraints
A company wishes to produce a product for which Labour: 7 x1  3 x2  6 x3  150
it has three models to choose from. The labor and Material: 4 x1  4 x2  x3  200
material data for each model is given. Supply of Step 4: Writing Non- Negativity restrictions
raw material is 200kg and the available manpower x1 , x2 , x3  0
is 150 hours. Formulate the model to determine
the daily production to maximize profit. Now, The LPP is
Model A Model B Model C Maximize Z  4 x1  2 x2  3 x3
Subject to
Labour (Hour/unit) 7 3 6
7 x1  3 x2  6 x3  150
Material (Kg//Unit) 4 4 5
4 x1  4 x2  x3  200
Profit (Rs./unit) 4 2 3
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU x1 , x2 , x3  0 5
 Mathematical Formulation Step 1: Identifying Decision Variables
Example 3 Let xi = The number of employee beginning work
Work Scheduling Problem on day i.
A post office requires different number of full time for i = 1,2,3….7
employees on different days of a week. All xi are integer
The daily requirement is given in table. Union rules
Step 2: Writing Objective Function
state that each full time employee must work for five
consecutive days and receive two days off. Total Number of Employee
Formulate a LP so that the post office can minimize Z  x1  x2  x3  x4  x5  x6  x7
the number of full time employee who must be hired. Need to be minimized.
Step 3: Writing Constraints
Days of Week No. of full-time
employees required Day 1; x1  x4  x5  x6  x7  17
1 = Monday 17 Day 2; x1  x2  x5  x6  x7  13
2 = Tuesday 13 Day 3; x1  x2  x3  x6  x7  15
3 = Wednesday 15 Day 4; x1  x2  x3  x4  x7  19
4= Thursday 19
Day 5; x1  x2  x3  x4  x5  14
5 = Friday 14
6= Saturday 16 Day 6; x2  x3  x4  x5  x6  16
7 = Sunday 11 Day 7; x3  x4  x5  x6  x7  11
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 6
 Mathematical Formulation
Example 4
Step 4: Writing Non- Negativity restrictions Advertising
xi  0, i  1, 2,3,.., 7 The owner of "Win-win Sports" wishes to determine
how many advertisements to place in monthly
Now, The LPP is
magazines A, B and C. His objective is to advertise in
Minimize Z  x1  x2  x3  x4  x5  x6  x7 such a way that total exposures to principal buyers of
Subject to expensive sports goods is maximized. Percentages of
readers for each magazine are known.
x1  x4  x5  x6  x7  17
x1  x2  x5  x6  x7  13 Exposure in any particular magazine is the number of
advertisements placed, multiplied by number of
x1  x2  x3  x6  x7  15 principal buyers. This data may be used:
x1  x2  x3  x4  x7  19 Magazine A Magazine B Magazine C
Reader 1 Lakh 0.6 lakh 0.4 lakh
x1  x2  x3  x4  x5  14
Principal Buyer 20% 15% 8%
x2  x3  x4  x5  x6  16 Cost per Advt.(Rs) 8000 6000 5000
x3  x4  x5  x6  x7  11 The budgeted amount is at most Rs. 1 lakh for the
xi  0, i  1, 2,3,.., 7 advertisement. The owner has already decided that
magazine A should have no more than 15 advertisements
and that B and C have at least 80 advertisements.
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 7
 Mathematical Formulation
Step 1: Identifying Decision Variables
Let, Now, The LPP is
x1, x2 and x3 be the number of advertisement in Maximize Z  20000 x1  9000 x2  3200 x3
magazines A, B and C respectively Subject to
Step 2: Writing Objective Function
8000 x1  6000 x2  5000 x3  10000
To Maximize Total Exposure to principal buyer. x1  15, x2  80, x3  80
Now Exposure function,
x1 , x2 , x3  0 and integers
Z  (100000  20%) x1  (60000 15%) x2  (40000  8%) x3
 20000 x1  9000 x2  3200 x3
Step 3: Writing Constraints
Budget : 8000 x1  6000 x2  5000 x3  10000
Advertising : x1  15, x2  80, x3  80
Step 4: Writing Non- Negativity restrictions
x1  0, x2  0, x3  0
And should be integers
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 8
Example 5 Mathematical Formulation
Portfolio Optimization Step 1: Identifying Decision Variables
Assume you have inherited Rs. 1 lakh form your father
Let x1 and x2 be the amount invested in each
that can be invested in two kind of stock portfolios, portfolio.
with the maximum investment allowed in either Step 2: Writing Objective Function
portfolio set as Rs. 75,000/-. The first portfolio has as To Maximize total return. Now return function is,
average rate of return of 10%, where as the second has Z  0.1x1  0.2 x2
20%. In terms of risk factor the first and second Step 3: Writing Constraints

portfolio have a risk rating of 4 and 9, resp. on a scale Inherited money; x1  x2  100000
of 0 to 10. Maximum allowed investment in each portfolio;
x1  75000, x1  75000
Since you wish to maximize your returns, you will not
Acceptable return; 0.1x1  0.2 x2  0.12( x1  x2 )
accept an average rate of return below 12% or a risk
Accetable risk factor; 4 x1  9 x2  6( x1  x2 )
above 6. Hence you face the important question… How
Step 4: Writing Non- Negativity restrictions
much should you invest in each portfolio? Formulate x1 , x2  0
this as an LPP.
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 9
 Mathematical Formulation Example 6
The postal department is considering the purchase of
Now, The LPP is vehicles to pick up and deliver mail from various offices.
Maximize Z  0.1x1  0.2 x2 They are considering three types of vehicles. Thos cost of
each these are Rs. 5 lakhs, Rs. 10 lakhs and Rs. 8 lakhs per
Subject to
vehicle, respectively. These require a crew of 2, 4 and 1
x1  x2  100000, persons per day considering multiple shifts. They expect
x1  75000, x2  75000, these to run 60, 100 and 80 km per day. They expect that
0.1x1  0.2 x2  0.12( x1  x2 ), total distance to be covered by the vehicles per day would
be 2000km. Based on the fuel economy, the operating cost
4 x1  9 x2  6( x1  x2 ), per day for these vehicles are Rs. 200, Rs. 350 and Rs. 300
x1 , x2  0 per day. They have budget restriction of Rs. 1.6 Crore and
have 80 people available as crew. Formulate a model to
minimize the operating cost.
Now, The LPP is
Minimize Z  200 x1  350 x2  300 x3
Subject to 5 x  10 x  8 x  160, ( Budget )
1 2 3

2 x1  4 x2  x3  80, (Crew)
60x1  100 x2  80 x3  2000
17/6/2026 x1 , x2 , x3  0, and integers
Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 10
 Example 7 Step 1: Identifying Decision Variables
A manufacturer produces three models I, II and III of a Let x1 , x2 and x3 be the number of production of
certain product using raw material A and B. the following each model.
table gives data for the problem:
Step 2: Writing Objective Function
To Maximize total Price or profit.
Z  30 x1  20 x2  50 x3

Step 3: Writing Constraints

Raw material A; 2x1  3 x2  5 x3  4000
The labor time per unit of model I is twice that of II and
Raw material B; 4x1  2 x2  7 x3  6000
three times that of III. The entire labor force of factory can
produce the equivalent of 1500 units of model I. Market The labor time per unit of model I is twice that of II and
requirements specify the ratios 3:2:5 for the production of three times that of III:
the three respective models. Formulate the problems as a x1  0.5 x2  0.33 x3  1500
linear program.
Minimum Demand of each model
x1  200, x2  200, x3  150

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 11

 Production ratio by market is
Now, The LPP is
3:2:5::x1 : x2 : x3
so
3 x1
  2 x1  3 x2  0
2 x2
2 x2
  5 x2  2 x3  0
5 x3

Step 4: Writing Non- Negativity restrictions

x1 , x2 , x3  0

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 12

 Example 8
To have a balanced campaign, the owner has
A business man is opening new restaurant and has budgeted
determined the following four restrictions:
Rs.8,00,000 for advertisement, for the coming month. He is
considering four type of advertising. a) There should be no more than four television
a) 30 second television commercials advertisements
b) 30 second radio commercials b) There should be no more than four
c) Half page advertisement in a newspaper advertisement in the magazine
d) Full page advertisement in a weekly magazine which will c) There should not be more than 60 percent of all
appear four times during the coming month advertisement in newspaper and magazine put
The owner wishes to reach families a) with income over Rs. together
50,000 and b) with income under Rs. 50,000. The amount of d) There must be at least 45,00,000 exposures to
exposure of each media to families of type a) and b) and the cost of families with annual income over Rs 50,000.
each media is shown below, Formulate this problem as a Linear Programming
model to determine the number of each type of
advertisement to be given so as to maximize the
total number of exposures.

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 13

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 14
 Example 9 Formulate linear programming problem to minimize
A electric utility company wishes to purchase the total purchasing cost.
following quantities (MW) of generator from different Solution:
Machinery’s: Step 1: Identifying Decision Variables
Let Xij = No. of each type of generator
purchased. from each company, where i = 1 to 4
and j=1 to 5
Tenders are submitted by four different Machinery
manufacturer’s who undertake to supply not more than the 10MW 22MW 20MW 15MW 12MW
quantities mentioned below (all types of Generators 275 350 425 150
Tesla 225
combined);
X11 300
X 12 X13 X14 X15
300 325 450 175 100

Cost in table are in Rupees Lakh per MW.

Fuji X21 X 22 X23 X24 X25 250
250 350 475 200 125

Toshiba X31 X32 X33 X34 X35 150

325 275 400 250 175
Bishon
X45 200
X41 X42 X43 X44
175 125 150 250 200
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 15
Step 2: Writing Objective Function Supply
Minimize total purchasing cost

Z  275 X 11  350 X 12  425 X 13  225 X 14  150 X 15 X 11  X 12  X 13  X 14  X 15  300

300 X 21  325 X 22  450 X 23  175 X 24  100 X 25 X 21  X 22  X 23  X 24  X 25  250
250 X 31  350 X 32  475 X 33  200 X 34  125 X 35 X 31  X 32  X 33  X 34  X 35  150
325 X 41  275 X 42  400 X 43  250 X 44  175 X 45 X 41  X 42  X 43  X 44  X 45  200
Step 3: Writing Constraints

Demand
Step 4: Writing Non- Negativity restrictions
X 11  X 21  X 31  X 41  175 X ij  0
X 12  X 22  X 32  X 42  125
X 13  X 23  X 33  X 43  150
X 14  X 24  X 34  X 44  250
X 15  X 25  X 35  X 45  200
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 16
Now, The LPP is
Supply
Minimize Z  275 X  350 X  425 X  225 X  150 X
11 12 13 14 15
X 11  X 12  X 13  X 14  X 15  300
300 X 21  325 X 22  450 X 23  175 X 24  100 X 25
X 21  X 22  X 23  X 24  X 25  250
250 X 31  350 X 32  475 X 33  200 X 34  125 X 35
X 31  X 32  X 33  X 34  X 35  150
325 X 41  275 X 42  400 X 43  250 X 44  175 X 45 X 41  X 42  X 43  X 44  X 45  200
Subject to
X ij  0
Demand

X 11  X 21  X 31  X 41  175
X 12  X 22  X 32  X 42  125
X 13  X 23  X 33  X 43  150
X 14  X 24  X 34  X 44  250
X 15  X 25  X 35  X 45  200

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 17

 DEFINITION OF GENERAL LPP LPP IN STANDARD FORM
Max / Min Z = c1 x1  c 2 x2  c3 x3  ....c n xn Max Z = c1 x1  c 2 x2  c3 x3  ....c n xn
Subject to Subject to
a11 x1  a12 x2  a13 x3  ......  a1n xn  b1 a11 x1  a12 x2  a13 x3  ......  a1n xn  b1
a21 x1  a22 x2  a23 x3  ......  a2 n xn  b2 a21 x1  a22 x2  a23 x3  ......  a2 n xn  b2
............................. .............................
am1 x1  am 2 x2  am 3 x3  ......  amn xn  bm am1 x1  am 2 x2  am 3 x3  ......  amn xn  bm
xi  0, i  1, 2,....n xi  0, i  1, 2,....n
mn b j  0, j  1, 2,....m
mn

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 18

 ASSUMPTION IN LINEAR PROGRAMMING PROBLEM

1. Linearity: The Objective function and constraints are linear. The profit from

A and B is sum of the individual profits.

2. Proportionality: If the profit of one item is A, the profit of two item is 2A

3. Divisibility and multiplicity: Multiplicity is same as proportionality.

Divisibility ensures that profit of ½ item is A/2.

4. Deterministic: All parameters and co-efficients are deterministic are known

with certainity. They don’t change during or after the formulation.

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 19

 LINEAR PROGRAMMING PROBLEM- Solutions
Graphical Method (Maximization)
x2
Considering following Linear Programming
Problem,
Maximize Z = 6x1  5 x2 (0, 6)
Subject to 3 x1  2 x2  12
x1  x2  5 C (0,5)
3 x1  2 x2  12 B (2,3)
x1 , x2  0
Feasible x1  x2  5
Converting inequalities to equations, Region
x1 x2 (5, 0)
x1  x2  5 x1  x2  5 (i)   1 Intercept form O(0, 0)
5 5 A(4, 0) x1
x1 x2
3x1  2 x2  12 3 x1  2 x2  12 (ii)  1
4 6
For intersection point solving Eq.(i) and (ii). which is (2,3).
The four corner points or extreme points are O(0,0), A(4,0),
B(2,3) and C(0,5).
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 20
Value of objective function at extreme points
At (0,0); Z= 0
At (4,0); Z = 6×4+5×0 = 24
At (0,5); Z = 6×0+5×5 =25
At (2,3); Z = 6×2+5×3 = 27
Here, the corner point given by x1=2 and x3=3 has the maximum objective function
value of Z= 27. This is the best solution or Optimal Solution.

Feasible Region: Common region of graph where all constraints are satisfied.
Feasible Solution: Values of Decision variable which satisfy all the constraints.
Optimal Solution: Best Feasible solution for most favorable value of objective function.

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 21

Graphical Method

1. Plot the constraints on a graph.

2. Plot also non negativity restrictions( restrict yourself to quadrant where both
x1 and x2 are ≥0.
3. Identify feasible region that contains the set of points satisfying all the
constraints.
4. Identify corner points or extreme points.
5. Evaluate the objective function at all the corner points.
6. The corner point that has the best value of the objective function (maximum
or minimum depending on the objective function ) is optimal.

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 22

 LINEAR PROGRAMMING PROBLEM- Solutions
Graphical Method (Minimization)
Considering following Linear Programming x2
Problem,
Minimize Z = 7x1  5 x2 A(0,5)
Subject to Feasible
x1  x2  4 Region
(0, 4)
5 x1  2 x2  10 2 10
B( , )
x1 , x2  0 3 3
Converting inequalities to equations,
x1 x2
x1  x2  4 x1  x2  4 (i)   1 Intercept form C (4, 0)
4 4
x1 x2 (2, 0) x1
5x1  2 x2  10 5 x1  2 x2  10 (ii)  1
2 5
For intersection point solving Eq.(i) and (ii). which is
(2/3,10/3). The three corner points or extreme points are,
A(0,5), B(2/3,10/3) and C(4,0).
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 23
Value of objective function at extreme points
At (4,0); Z = 7×4+5×0 = 28
At (0,5); Z = 7×0+5×5 =25
At (2/3,10/3); Z = 7×2/3+5×10/3 = 64/3=21.333
Here, the corner point given by x1=2 and x3=3 has the minimum objective function
value of Z= 21.3. This is the best solution or Optimal Solution.

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 24

 LINEAR PROGRAMMING PROBLEM- Solutions
Simplex Algorithm
Converting given LPP in to LPP in standard form,
i. By adding Slack variable to convert “less than or equal to” constraint.
Ex. x1≤ 10 is converted to x1+x2 = 10 , here x2 is slack variable. And x2 ≥ 0.
ii. By Subtracting Surplus variable to convert “ greater than or equal to” constraint.
Ex. Ex. x1 ≥ 27 is converted to x1- x2 = 27 , here x2 is surplus variable. And x2 ≥ 0
iii. Convert unrestricted variable x1 as difference of two non negative variables.
Ex. If x1 is unrestricted variable , then substitute x1= x2-x3 in entire LPP, where x2 ≥ 0
and x3 ≥ 0
iv. In case right hand side of constraint is negative, then constraint is multiplied by
negative sign.
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 25
 LINEAR PROGRAMMING PROBLEM- Solutions
Example SYSTEM OF EQUATION
Maximize Z = 6x1  5 x2 x1  2 x2  x3  4 x4  2 x5  2
Subject to x1  x2  x3  3x4  x5  4
7x1  3 x2  15
Without solving this system of equation can we find a
3 x1  2 x2  12
solution to this system of equation?
5 x1  4 x2  60
x1 , x2  0 Elementary Row Operation
1. Multiply a row by a scalar.
Now, The LPP in standard form is
2. Add/subtract a row to another row
7x1  3 x2  x3  15
3. Interchange two row.
3 x1  2 x2 - x4  12
5 x1  4 x2  60 By applying Elementary Row Operation
x1 , x2  0 x1  2 x2  x3  4 x4  2 x5  2
x1  x2  x3  3x4  x5  4
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 26
 LINEAR PROGRAMMING PROBLEM- Solutions
Can be converted to
R2  R2  R1
x1  2 x2  x3  4 x4  2 x5  2
x2  2 x3  x4  3 x5  2
Then to this
R1  R1  2 R2
x1  3 x3  2 x4  4 x5  6
x2  2 x3  x4  3 x5  2
• Now the solution is x1= 6 , x2 = 2 and x3= x4 =x5 =0
• Solution of last system of equation x1= 6 , x2 = 2 and all variables are zero. Such
system is called canonical system.
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 27
 • A variable xi is said to be basic variable, if it appears with
unit co-efficient in ith equation and zero in all other equations.
• Those variable which are not basic are called non basic
variables.
• By applying elementary row operation any given variable
can be made to be basic variable. This is called pivot
operation.
• The solution obtained from canonical system by setting non
basic variable to zero and solving for basic variable is known
as basic solution.
• A basic feasible solution is a basic solution in which value of
basic variable is non negative.
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 28
Simplex Algorithm (Tabular form)

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 29

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 30
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 31
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 32
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 33
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 34
 Example 10 Solution:
A shop can make two types of sweets (A and B). they
Step 1: Identifying Decision Variables
use two resources flour and sugar. To make one piece
of A, they need 3 paw of flour and 1 paw of sugar. To Let x1 be the number unit of Sweet A made
make one piece of B they need 2 paw of flour and 1
Let x2 be the number unit of Sweet B made
paw of sugar. They have 12 paw of Flour and 5 paw of
sugar. These sweets are sold at Rs. 6 and 5 per piece Step 2: Writing Objective Function
respectively. Find the best product mix to maximize
Profit function Z  6 x1  5 x2
the revenue.
Sugar Flour Revenue per piece Step 3: Writing Constraints
Sweets A 1paw 3paw $. 6 Sugar: x1  x2  5
B 1paw 2paw $. 5 Flour: 3x1  2 x2  12
Availability 5paw 12paw
Step 4: Writing Non- Negativity restrictions

x1 , x2  0

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 35

35
 Now, The LPP is Simplex table
Maximize Z = 6x1  5 x2 Iteration 1
subject to Cj 6 5 0 0
x1  x2  5 Basis

4. Leaving Var
CBj x1 x2 x3 x4 RHS(Bj)  (ratio)
3x1  2 x2  12 (xBj)
x1 , x2  0 0 x3 1 1 1 0 5 5/1=5

Writing given LPP in Standard form 0 x4 3 2 0 1 12 12/3= 4 Minimum

ratio
Maximize Z = 6x1 + 5x2 + 0.x3 + 0.x4
Zj 0 0 0 0 0
Subject to
x1 + x2 + x3 = 5 Cj -Zj 6 5 0 0
3x1 + 2x2 + x4 = 12
1. Entering Var
x1 , x2, x3, x4  0 2. Key Column
Zj = ∑CBj * xi Positive Maximum Cj - Zj 3. Key row

5. Pivot Element
 Variable with maximum positive cj-zj
enters
17/6/2026  Variable
Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU with minimum ratio Leaves. 36
Simplex table
Cj 6 5 0 0
CBj Basis x1 x2 x3 x4 RHS(Bj) ?
0 x3 1 1 1 0 5 5/1=5

0 x4 3 2 0 1 12 12/3=4
Zj 0 0 0 0 0
Cj -Zj 6 5 0 0 Minimum
ratio
0 x3 0 1/3 1 -1/3 1 1 1/3=3 R1new  R1old  R2 new  1 1 1 0 : 5  1 2 / 3 0 1 / 3 : 4 

6 x1 1 2/3 0 1/3 4 4 2/3=6 R2 new  R2 old / 3   0 1 / 3 1 1 / 3 :1

Zj 6 4 0 2 24
Cj -Zj 0 1 0 -2
5 x2 0 1 3 -1 3 R1new  R1old  3
6 x1 1 0 -2 1 2 R2 new  R2 old  2 / 3  R1new
 1 2 / 3 0 1/ 3 : 4   2 / 3  0 1 3 1 : 3
Zj 6 5 3 1 27
 1 0 2 1 : 2
Cj -Zj 0 0 -3 -1
Here all cj-zj ≤0, we have reached to optimal solution.
17/6/2026
The Optimal values are x1=2, x2=3. Max Z=27.
Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 37
 Example 11 Maximize Z = 6x1  8 x2
subject to
x1  x2  10
2x1  3 x2  25
x1  5 x2  35
x1 , x2  0
Solution:
Writing given LPP in Standard form
Maximize Z = 6x1 + 8x2 + 0.x3 + 0.x4 + 0.x5
Subject to
x1 + x2 + x3 = 10
2x1 + 3x2 + x4 = 25
x1 + 5x2 + x5 = 35
x1 , x2, x3, x4  0

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 38

 Cj 6 8 0 0 0
CB j Basis x1 x2 x3 x4 x5 RHS( Bj)  (ratio)
0 x3 1 1 1 0 0 10 10/1 =10
0 x4 2 3 0 1 0 25 25/3 = 8.3 Minimum
ratio
0 x5 1 5 0 0 1 35 35/5 = 7
Zj 0 0 0 0 0 0 Minimum
ratio
Cj - Zj 6 8 0 0 0
0 x3 4/5 0 1 0 -1/5 3 3*5/4 =15/4 R1new  R1old  R3new
0 x4 7/5 0 0 1 -3/5 4 4*5/7=20/7 R2 new  R2old  3R3new
8 x2 1/5 1 0 0 1/5 7 7*5=35 R3new  R3old / 5
Zj 8/5 8 0 0 8/5 56
Cj - Zj 22/5 0 0 0 -8/5
 Cj 6 8 0 0 0 Minimum
CBj Basis x1 x2 x3 x4 x5 RHS(Bj) (ratio) ratio

0 x3 0 0 1 -20/35 1/7 5/7 10/1 =10 R1new  R1old  4 / 5R2 new

6 x1 1 0 0 5/7 -3/7 20/7 X R2 new  5 / 7 R2old
8 x5 0 1 0 -1/7 2/7 45/7 45/7*7/2 = 45/2 R3new  R3old  1/ 5R2 new
Zj 0 0 0 22/7 - 2/7 480/7
Cj - Zj 0 0 0 -22/7 2/7
0 x5 0 0 7 -4 1 5 R1new  7 R1old
6 x1 1 0 3 -1 0 5 R2 new  R2od  3 / 7 R1new
8 x2 0 1 -2 1 0 4 R3new  R3old  2 / 7 R1new
Zj 6 8 2 2 0 70
Cj - Zj 0 0 -2 -2 0
Here all cj-zj ≤0, we have reached to optimal solution. The Optimal values are x1=5, x2=4,x3=0
Max Z=70.
Three Observation from this table
1. Variable that already left the basis can re-enter the basis.
2. Theta Should be strictly non negative, otherwise do not evaluate.
3. All numbers are represented in fractional form
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 40
Big M Method (Tabular form)
• In all problem involving “greater than or equal to” (≥) constraints, surplus
variable (negative slack), automatically do not qualify to be initial basic
variable, they end up giving infeasible solution.

• So we add artificial variable to constraints to get basic feasible solution.

• Since artificial variable are not the part of problem, they should not be part of
solution. We give small contribution of artificial variable to objective function.

• For Maximization problem, we multiply artificial variable by very large positive

number “M → ∞”, called “big M” and subtract it from objective function, which
avoids artificial variable from appearing into the solution.

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 41

Procedure adopted for Big M Method

1. Write LPP in standard form

i. For each “ ≥” type constraint, add surplus and artificial variable.

ii. For each “=“ type constraints, add only artificial variable (required to obtain
basic feasible solution.)

2. In objective function, assign a very high (Negative coefficient) penalty for each
artificial variable and assign zero “0” for each surplus variable.

3. Apply Simplex method to above formulated LPP and derive the optimal solution.

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 42

Example 12
Minimize Z = 3x1  4 x2
subject to
2x1  3 x2  8
5x1  2 x2  12
x1 , x2  0 Solution:
Writing given LPP in Standard form
Maximize Z* = - Z = -3x1 - 4x2 - 0.x3 - 0.x - M.a - M.a
4 1 2
Subject to
2x1 + 3x2 - x3 + a1 = 8
5x1 + 2x2 - x4 + a2 = 12
x1 , x2, x3, x4 , a1 , a2 0

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 43

 Simplex table
Cj -3 -4 0 0 -M -M
CBj Basis x1 x2 x3 x4 a1 a2 RHS(Bj) ?
-M a1 2 3 -1 0 1 0 8 8/2=4
-M a2 5 2 0 -1 0 1 12 12/5=2.4
Zj -7M -5M M M -M -M
Cj -Zj 7M-3 5M-4 -M -M 0 0
-M a1 0 11/5 -1 2/5 1 -2/5 16/5 16/5 11/5=16/11 R1new  R1old  2 R2 new
-3 x1 1 2/5 0 -1/5 0 1/5 12/5 12/5 2/5=6 R2 new  R2 old / 5
Zj -3 - M - -M

Cj -Zj 0 -M 0 -

-4 x2 0 1 -5/11 2/11 5/11 2/11 16/11 R1new  R1old  5 / 11

-3 x1 1 0 2/11 -3/11 -2/11 3/11 20/11 R2 new  R2 old  2 / 5  R1new
Zj -3 -4 14/11 1/11 -14/11 -17/11 -124/11
Cj -Zj 0 0 -14/11 -1/11 -M+14/11 -M+17/11

Here all cj-zj ≤0, we have reached to optimal solution.

The Optimal values are x1=16/11, x2=20/11. Min Z=124/11.
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 44
Two Phase Method
Phase I
1. Convert of constraints into equality constraints using slack surplus and artificial
variables, and write the LPP in standard form.

2. We assume a new auxiliary objective function constructed as:

Max W = 0.x1+0.x2+…..+[Link]-a1-a2-….-am

(-1) is the price added for each of the artificial variable a1,a2,,….,am

0 price is assigned to each of the variables x1,x2,…,xn including slack and surplus
variables.

∴Max W = 0, if all artificial variables are zero.

Or Max W > 0, if at least one artificial variable is positive

3. Apply Simplex method to above formulated LPP and derive the optimal solution.
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 45
Two Phase Method contd.

Phase II

1. When iteration of phase I ends, then we go to phase II to obtain the optimum value
of the objective function of the original problem.

2. Assign actual co-efficient of the variable including slack and surplus variables and
zero coefficient value to any artificial variable present in the basis of the last table
of phase I. Also remove the artificial variables which are not present in the basis of
last table of Phase I.

3. Then apply simplex algorithm to obtain the optimal solution.

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 46

Example 13 Simplex table
Minimize Z = 3x1  4 x2
Cj 0 0 0 0 -1 -1
subject to
CBj Basis x1 x2 x3 x4 a1 a2 RHS(Bj) ?
2x1  3 x2  8
-1 a1 2 3 -1 0 1 0 8 8/2=4
5x1  2 x2  12
Solution: x1 , x2  0 -1 a2 5 2 0 -1 0 1 12 12/5=2.4
Zj -7 -5 1 1 -1 -1
Writing given LPP in standard form
Cj -Zj 7 5 -1 -1 0 0
Maximize Z* = -3x1  4 x2
Subject to -1 a1 0 11/5 -1 2/5 1 -2/5 16/5 16/5 11 R1new  R1old  2 R2 new
/5=16/11
2x1  3 x2  x3 +a1 =8 0 x1 1 2/5 0 -1/5 0 1/5 12/5 12/5 2/
R2 new  R2 old / 5
5x1  2 x2 - x4 +a2  12 5=6
Zj 0 -11/5 1 -2/5 0 2/5 -16/5
x1 , x2 , x3, x4 , a1 , a2  0
Phase I Cj -Zj 0 11/5 -1 2/5 0 7/5
Defining auxiliary Objective function 0 x2 0 1 -5/11 2/11 5/11 2/11 16/11
R1new  R1old  5 / 11
Minimize W = a1  a2
0 x1 1 0 2/11 -3/11 -2/11 3/11 20/11
Given LPP as, R2 new  R2 old  2 / 5  R1new
Zj 0 0 0 0 0 0 0
Maximize W* =0.x1 +0.x2  0.x3  0.x4  a1  a2
Cj -Zj 0 0 0 0 -1 -1
subject to
2x1  3 x2  x3 +a1 8
5x1  2 x2  x4  a2  12
x1 , x2 , x3 , x4 , a1 , a2  0
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 47
Phase II Notes:
Cj -3 -4 0 0

CBj Basis x1 x2 x3 x4 RHS(Bj) 

-4 x2 0 1 -5/11 2/11 16/11

-3 x1 1 0 2/11 -3/11 20/11

Zj -3 -4 14/11 1/11 -124/11

Cj -Zj 0 0 -14/11 -1/11

Here all cj-zj ≤0, we have reached to optimal solution.

The Optimal values are x1=20/11, x2=16/11. Min Z=124/11.

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 48

 Simplex table
Example 13
Cj 3 2 0 0 -M
Maximize Z = 3x1  2 x2
subject to CBj Basis x1 x2 x3 x4 a1 RHS 
2x1  x2  2 0 x3 2 1 1 0 0 2 2/1=2
3x1  4 x2  12
-M a1 3 4 0 -1 1 12 12/4=
x1 , x2  0
3
Solution: Zj -3M -4M 0 M -M
Maximize Z = 3x1  2 x2  0.x3  0.x4  Ma1 Cj-Zj 3+3M 2+4M 0 -M 0
subject to 0 x3 2 1 1 0 0 2
2x1  x2  x3 2
2 x2 -5 0 -4 -1 1 4
3x1  4 x2 -x4 + a1  12
x1 , x2 , x3 , x4 , a1  0 Zj 4+5M 2 2+4M M -M 6 R2 new  R2old  4  R1new
Cj-Zj -1-5M 0 -2-4M -M 0

Here all Cj – Zj  0, we have reached to optimal solution.

The Optimal values are x1=0, x2=4. Max Z=6.

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 49

 Simplex table
Example 14
Maximize Z = x1  5 x2 Cj 1 5 0 0 -M
subject to CBj Basis x1 x2 x3 x4 a1 RHS 
3x1  4 x2  6 0 x3 3 4 1 0 0 6 6/4=3/4
x1  3 x2  3
-M a1 1 3 0 -1 1 3 3/3=1
x1 , x2  0
Zj -3M -4M 0 M -M
Solution:
Maximize Z = x1  5 x2  0.x3  0.x4  Ma1 Cj-Zj 3+3M 2+4M 0 -M 0
subject to 0 x3 5/3 0 0 4/3 -4/3 2 2/(4/3)=3/2 R1new  R1old  4 R2 new
3x1  4 x2  x3 6 5 x2 1/3 1 0 -1/3 1/3 1 X R2 new  R2old / 3
x1  3 x2 -x4 + a1  3
Zj 5/3 5 0 -5/3 5/3
x1 , x2 , x3 , x4 , a1  0
Cj-Zj -2/3 0 0 5/3 -M-5/3
0 x4 5/4 0 0 1 -1 3/2 R1new  R1old  3 / 4

5 x2 3/4 1 0 0 0 3/2 R2 new  R2 old

Zj 15/4 5 0 0 0 15/2  R1new  1/ 3

Cj-Zj -15/4 0 0 0 -M
Here all Cj – Zj  0, algorithm terminates.
The optimal solution is, x1 = 0, x2 =3/2, Zmax = 15/2
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 50
 Simplex table
Termination conditions Cj 4 3 0 0
a. Degeneracy CBj Basis x1 x2 x3 x4 RHS 

Example 15 0 x3 2 3 1 0 8 8/2 =4
Maximize Z = 4x1  3 x2 0 x4 3 2 0 1 12 12/3= 4
subject to
Zj 0 0 0 0 0
4x1  3 x2  8
3x1  2 x2  12
Cj - Z j 4 3 0 0
x1 , x2  0 0 x3 0 5/3 1 -2/3 0 X R1newR1old -2 R2new
Solution: 4 x1 1 2/3 0 1/3 4 4/(2/3)= 6 R2new1/3R2old
Maximize Z = 4x1  3 x2  0.x3  0.x4 Zj 4 8/3 0 4/3 16
subject to Cj - Z j 0 1/3 0 -4/3
2x1  3 x2  x3 =8 R1new3/5R1old
3 x2 0 1 3/5 -2/5 0
3x1  2 x2 + x4  12
4 x1 1 0 -2/5 3/5 4 R2new1R2old -2/3 R1new
x1 , x2 , x3 , x4  0
Zj 4 3 1/5 6/5 16
Cj - Z j 0 0 -1/5 -6/5

Since, all Cj – Zj  0 , the algorithm terminates.

The optimal solution is, x1 = 4, x2 = 0, Max Z = 16 .
17/6/2026 51
Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU
When there is tie in the leaving
Cj 4 3 0 0
variable , one of the basic variable CBj Basis x1 x2 x3 x4 RHS 
takes zero value in next iteration. This 0 x3 2 3 1 0 8 8/2 =4
phenomena is known as degeneracy. 0 x4 3 2 0 1 12 12/3= 4
Zj 0 0 0 0 0
There is no proper way to eliminate Cj - Zj 4 3 0 0
degeneracy or to avoid it. Sometimes, 4 x1 1 3/2 1/2 0 4 R1new1/2R1old

a different breaking rule can result in 0 x4 0 -5/2 -3/2 1 0 R2newR2old - 3R1new

Zj 4 6 2 0 16
termination.
Cj - Zj 0 -6 -2 0
In this example, if we had chosen to
Since, all Cj – Zj  0 , the algorithm terminates.
leave x3 instead of x4 , in the first The optimal solution is, x1 = 4, x2 = 0, Max Z = 16 .
iteration, the algorithm terminates to
give the optimal solution after one
iteration.
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 52
 Simplex table
b. Alternate Optimum Cj 4 3 0 0
Non – Basic with Cj - Zj = 0, CBj Basis x1 x2 x3 x4 RHS 
can enter the basis.
0 x3 8 6 1 0 25 25/8
Example 16 0 x4 3 4 0 1 15 15/3 =5

Maximize Z = 4x1  3 x2
Zj 0 0 0 0 0
subject to Cj - Zj 4 3 0 0
8x1  6 x2  25 4 x1 1 3/4 1/8 0 25/8 25/8*4/3 R1new1/8 R1old
= 25/6
3x1  6 x2  15 0 x4 0 7/4 -3/8 1 45/8 45/14 R2newR2old - 3R1new
x1 , x2  0
Zj 4 3 1/2 0 25/2
Solution: Cj - Zj 0 0 -1/2 0
Maximize Z = 4x1  3 x2  0.x3  0.x4
4 x1 1 0 2/7 -3/7 5/7 R1newR1old – 3/4R2new
subject to
8x1  6 x2  x3 = 25 3 x2 0 1 3/4 4/7 45/14 R2new4/7 R2old
3x1  6 x2 + x4  15 Zj 4 3 1/2 0 25/2
x1 , x2 , x3 , x4  0 Cj - Zj 0 0 -1/2 0

It looks as though the simplex algorithm seems to be getting into an infinite loop, although the optimal solution has been
found. This phenomenon is called alternate optimum. All non basic Cj – Zj  0 , at least one non basic Cj – Zj = 0, can
enter basis.
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 53
c. Unboundedness Simplex table
Cj 4 3 0 0
Example 17 
CBj Basis x1 x2 x3 x4 RHS (Bj)
Maximize Z = 4x1  3 x2
0 x3 1 -6 1 0 5 5
subject to
x1  6 x2  5 0 x4 3 0 0 1 11 11/3
3x1  11 Zj 0 0 0 0 0
x1 , x2  0 Cj - Z j 4 3 0 0
Solution: 0 x3 0 -6 1 -1/3 4/3 X R1newR1old – R2new
Maximize Z = 4x1  3 x2  0.x3  0.x4
4 x1 1 0 0 1/3 11/3 X R2new1/3R2old
subject to
x1  6 x2  x3 =5 Zj 4 0 0 4/3 44/3
3x1 + x4  11 Cj - Z j 0 3 0 -4/3
x1 , x2 , x3 , x4  0
Here, x2 can enter the basis, but we are unable to fix the leaving variable,
because all co-efficient entering column are  0. the algorithm terminates,
cause unable to find leaving variable.
This phenomena is called unboundedness, indicating x2 can take any value.

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 54

 d. Infeasibility Simplex table
Example 18 Cj 4 3 0 0 -M
CBj Basis x1 x2 x3 x4 a1 RHS 
Maximize Z = 4x1  3 x2
subject to 0 x3 1 2 1 0 0 3 3/1=3
x1  4 x2  3 -M a1 3 1 0 -1 1 12 12/3 =4
3x1  x2  12 Zj -3M -M 0 M M
x1 , x2  0
Cj - Zj 3M+4 M+3 0 -M 0
Solution:
4 x1 1 4 1 0 0 3
Maximize Z = 4x1  3 x2  0.x3  0.x4  Ma1
-M a1 0 -11 -3 -1 1 3 R2newR2old – 3R1new
subject to
x1  4 x2  x3 =3 Zj 4 11M 3M+4 M -M
3x1 +x 2 -x 4 + a1  12 Cj - Zj 0 3-11M -3M-4 -M 0
x1 , x2 , x3 , x4  0
Here, all Cj – Zj  0, optimality condition seems to be satisfied but an
artificial variable is in the basis.
This means problem is infeasible and does not has feasible solution.

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 55

 Duality in Linear Programming Problem
Introduction to Duality Theory
Every LPP has a corresponding mirror image formulation called the Dual. If the
original problem has n variables and m constraints then its dual will have m
variable and n constraints.

If a given LPP can be thought of resource allocation model in which objective is

to maximize revenue or profit subject to constraint on the consumption of
resources, then its dual corresponds to an LPP which minimizes consumption of
resources subject to some profit maximizing constraints.

When an LPP contains large number of constraints and smaller number of

variable, computational effort can be largely reduced by converting it into dual
problem.
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 56
Some interesting properties of Dual LPP are; Relationships Between Primal and Dual Problem
a) Any feasible solution of dual model provides
a bound on the objective to the original Primal Dual
primal. Maximization Minimization
b) Optimal solution of dual = Optimal solution Minimization Maximization
of primal Problem Number of variables (n) Number of Constraints(n)
c) Dual of a dual model is once again the Number of Constraints (m) Number of Variables (m)
original primal model. RHS (b) Objective function
Coefficient (c)
Primal Dual Formulation
Objective function RHS(b)
Primal Dual Coefficient (c)
Max Z = CT X Min W = bT Y Constraint coefficient (A) Constraint Coefficient (AT)
Subject to Subject to
AX ≤ b AT Y ≥ CT
X≥0 Y≥0
 In any LPP, the dual of dual is primal
Min Z = CT
X Max W = bT Y
Subject to Subject to itself.
AX ≥ b AT Y ≤ CT
X≥0 Y≥0
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 57
 Primal and Dual relationship for constraint and variables
Primal Dual Primal Dual
(Minimization) (Maximization) (Maximization) (Minimization)
≥ Variable ≤ Constraint ≤ Constraint ≥ Variable
≤ Variable
Unrestricted variable
≥ Constraint
Equation constraint
& ≥ Constraint
Equation constraint
≤ Variable
Unrestricted variable
≥ Constraint ≥ Variable ≥ Variable ≥ Constraint
≤ Constraint ≤ Variable ≤ Variable ≤ Constraint
Equation constraint Unrestricted Variable Unrestricted Variable Equation constraint

Some Results:
Primal Problem Dual Problem Conclusions

Feasible Solution Feasible Solution Finite optimal solution for both exists.

No Feasible Solution Feasible Solution Dual Objective function is unbounded.

Feasible Solution No Feasible Solution Primal Objective function is unbounded.

No Feasible Solution No Feasible Solution No Solution Exists

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 58
Dual Simplex Algorithm (Tabular form)

 Dual Feasible if, Cj – Zj  0

 Primal Feasible if, RHS  0
Procedure
1. Make Primal Feasible
2. When Primal is feasible, it becomes optimal solution.
3. If RHS  0, primal feasible, we can not proceed dual simplex.

17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 59

Dual Simplex Algorithm Dual Simplex table
Cj -4 -7 0 0
(Tabular form)
CBj Basis x1 x2 x3 x4 RHS(Bj)
Example 19 Minimize Z = 4x1  7 x2
0 x3 -2 -3 1 0 -5
subject to
0 x4 -1 -7 0 1 -9
2x1  3 x2  5
Zj 0 0 0 0 0
x1  7 x2  9
Cj -Zj -4 -7 0 0
Solution: x1 , x2  0
= (C -Z )/Key
j j
4 1
Above LPP can be written as Row

0 - 11/7 0 1 -3/7 -8/7 R1new  R1old  3  R2 new

Maximize Z* =-Z=- 4x1  7 x2 x3
R2 new  R2 old  (1/ 7)
subject to -7 x2 1/7 1 0 -1/7 9/7

-2x1  3 x2  5 Zj -1 -7 0 1 -9
Cj -Zj -3 0 0 -1
- x1  7 x2  9
 21/11 - - 7/3
x1 , x2  0
Writing given LPP in Standard form -4 x1 1 0 -7/11 3/11 8/11 R1new  7 / 11 R2 new

Maximize Z* =-Z=- 4x1  7 x2  0.x3  0.x4 -7 x2 0 1 -1/17 -20/119 145/119 R2 new  R2 old  1/ 7 R1new
1 1 
-4 35/17 -177/7  7 1 0  7 : 9 / 7
subject to Zj -7 8/17  
1 7 3 
 1 0  : 8 / 17 

-2x1  3 x2  x3  5 -35/17 7 
Cj -Zj 0 0 -8/17 11 11
  0 1 1 / 17 20 / 119 : 145 / 119 

- x1  7 x2  x4  9
x1 , x2 , x3 , x4  0
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 60
Example 20 Minimize Z = 7x1  5 x2 Cj -7 -5 0 0

subject to CBj Basis x1 x2 x3 x4 RHS

x1  x2  4 0 x3 -1 -1 0 0 -4

5x1  2 x2  10 0 X4 -5 -2 0 1 -10

x1 , x2  0 Zj 0 0 0 0
Solution:
Cj - Z j -7 -5 0 0
Above LPP can be written as

Maximize Z* =-Z=- 7x1  5 x2 7/5 5/2 - -

subject to 0 x3 0 -3/5 1 -1/5 -2 R1newR1old + R2new

-x1  x2  4 -7 x1 1 2/5 0 -1/5 2 R2new -1/5R2old
- 5x1  2 x2  10 Zj -7 -14/5 0 -7/5 -14

x1 , x2  0 Cj - Z j 0 -11/5 0 7/5
Writing given LPP in Standard form  - 11/5 7/5
Maximize Z* =-Z=- 7x1  5 x2  0.x3  0.x4 -5 x2 0 1 -5/3 1/3 10/3 R1new-5/3R1old
subject to -7 X1 1 0 2/3 -1/3 2/3 R2newR20ld -2/5R1new
-2x1  3 x2  x3  4 Zj -7 -5 11/3 2/3 -64/3
- 5x1  2 x2  x4  10 Cj - Z j 0 0 -11/3 -2/3
x1 , x2 , x3 , x4  0
Here, Cj – Zj  0 and RHS are positive, algorithm terminates.
The optimal values, X1 = 2/3, X2 = 10/3, Minimum Z = 64/3
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 61
 Example 21 Maximize Z = 4x1  x2  5 x3 Dual Simplex table
subject to
Cj 4 -1 5 0 0 0
3x1  4 x2  5 x3  30
CBj Basis x1 x2 x3 x4 x5 x6 RHS(Bj) 
5x1  8 x2  7 x3  40
4x1  6 x2  5 x3  36 0 x4 3 4 5 1 0 0 30

x1 , x2 , x3  0 0 x5 -5 -8 -7 0 1 0 -40

Solution:Above LPP can be written as 0 x4 4 6 5 0 0 1 36

Maximize Z = 4x1  x2  5 x3 Zj 0 0 0 0 0 0
subject to Cj-Zj 4 -1 5 0 0 0
3x1  4 x2  5 x3  30  -4/5 1/8 -5/7 - - -
-5x1  8 x2  7 x3  40
0 x4 1/2 0 3/2 1 1/2 0 10 10*2/3 R1newR1old – 4R2new
4x1  6 x2  5 x3  36 =20/3
-1 x2 5/8 1 7/8 0 -1/8 0 5 5*8/7 R2new -1/8R2old
x1 , x2 , x3  0 =40/7
0 x4 1/4 0 -1/4 0 3/4 1 6 X R3newR3old – 6R2new
Writing given LPP in Standard form
Maximize Z = 4x1  x2  5 x3  0.x4  0.x5  0.x6 Zj -5/8 -1 -7/8 0 1/8 0 -5
subject to Cj-Zj 37/8 0 47/8 0 -1/8 0
3x1  4 x2  5 x3  x4  30
-5x1  8 x2  7 x3  x5  40
4x1  6 x2  5 x3  x6  36
x1 , x2 , x3 , x4 , x5 , x6  0
Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 62
17/6/2026
 Cj 4 -1 5 0 0 0
CBj Basis x1 x2 x3 x4 x5 x6 RHS(Bj) 
0 x4 -4/7 -12/7 0 1 5/7 0 10/7 2 R1newR1old –3/2R2new
5 x3 5/7 8/7 1 0 -1/7 0 40/7 X R2new 8/7R2old
0 x6 3/7 2/7 0 0 5/7 1 52/7 10.5 R3newR3old + 1/4R2new
Zj 25/7 40/7 5 0 -5/7 0 200/7
Cj - Zj 3/7 -47/7 0 0 5/7 0
0 x5 -4/5 -12/5 0 7/5 1 0 2 X R1new7/5R1old
5 X3 3/5 4/5 1 1/5 0 0 6 10 R2new R2old +1/7R1new
0 X6 1 2 0 -1 0 1 6 6 R3newR3old –5/6R1new
Zj 3 4 5 1 0 0 30
Cj – Zj 1 -5 0 -1 0 0
0 X5 0 -4/5 0 3/5 1 4/5 34/5 R1newR1old + 4/5R3new
5 X3 0 -2/5 1 4/5 0 -3/5 12/5 R2new R2old-3/5R3new
4 X1 1 2 0 -1 0 1 6 R3newR3old
Zj 4 6 5 0 0 1 36
Cj - Zj 0 -7 0 0 0 -1
Here, Cj – Zj  0 and RHS are positive, algorithm terminates.
17/6/2026 Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 63
The optimal values, X1 = 6, X2 = 0, x3 = 12/5 Maximum Z = 36
 Post Optimality Analysis (Sensitivity Analysis)
The study of changes in optimal solution due to changes in LPP parameters (A, b or c) is called Post
optimality analysis (Sensitivity Analysis).

The objective of sensitivity analysis is to reduce computational effort considerably; which arises when
some error may appear in the data and requires the solving of problem again and again from beginning.
This will help the calculation in the erroneous problem usable for the solution of correct problem.
Following variations will be studied for post
Effect of these variations in LPP are;
optimality analysis;
 Optimal solution remain unchanged i.e.
 Variation in cost vector “c”
basic variable and their value remain
 Variation in requirement vector “b unchanged.
 Variation in element of matrix “A”  Basic variable remain the same but these
 Addition or deletion of new variable value have been changed
 Addition or deletion of new constraints  The basic solution changes entirely.
Asst. Prof. Suraj Shrestha, IOE-PAS(WRC), TU 64
17/6/2026