CHAPTER 7

Linear Optimization

Optimization in Linear Programming (LP) refers to the process of finding the best possible
solution from a set of feasible solutions defined by a system of linear equations or inequalities.
In simple terms:
Linear programming is a mathematical technique used to maximize or minimize a linear
objective function, subject to a set of linear constraints (equations or inequalities).
It is a central topic of optimization. It provides a powerful tool in modeling many applications. LP
has attracted most of its attention in optimization for two main reasons:

Applicability:
There are many real-world applications that can be modeled as linear programming.

Solvability:
There are theoretically and practically efficient techniques for solving large scale problems.
Advantages of Linear Programming:

i. It helps in attaining the optimum use of productive factors. Linear programming indicates
how a manager can utilize his production factors most effectively by a better selection and
distribution of these elements. For example, more efficient use of man power and machines
can be obtained by the use of linear programming.
ii. It improves the quality of decision. The individual having a clear idea of relationships
within the basic equations, inequalities or constraints can have a better idea about the
problem and its solution.
iii. It can improve the knowledge and skill of tomorrow’s executive.
iv. Linear programming allows modification of its mathematical solutions.
v. It highlights the bottlenecks in the production process.
Limitations of Linear Programming:

i. For large scale problems having many limitations and constraints, the computational
difficulties are enormous. It may sometimes be possible to get over these difficulties by
splitting the main problem into smaller ones, deriving solutions for them and then
combining the results.
ii. According to the linear programming problem, the solution variables can have any value,
like some of the variables can have only integral values. Such situations justify the use of
special methods.
 iii. The model does not take into the effect of time.
iv. Many times, it is not possible to express both the objective function and constraints in
linear form. The misapplication of linear programming under non-linear conditions usually
results an incorrect solution.

Formulation of L.P.P:
Each optimization problem consists of three elements:

1. Decision variables: Describe choices that are under our control.

2. Objective functions: Describes a criterion that we wish to minimize (e.g. cost) or
maximize (e.g. profit).
3. Constraints: Describes the limitations that restrict choices for decision variables.

Formally, we use the term Linear Programming (LP) to refer to an optimization problem in which
the objective function is linear and each constraint is a linear inequality or equality.
Example:

A company makes two products (say 𝑃 and 𝑄) using two machines (say 𝐴 and 𝐵). Each unit of 𝑃
that is produced requires 50 minutes processing time on machine 𝐴 and 30 minutes processing
time on machine 𝐵. Each unit of 𝑄 that is produced requires 24 minutes processing time on
machine 𝐴 and 33 minutes processing time on machine 𝐵.

Machine 𝐴 is going to be available for 40 hours and machine 𝐵 is going to be available for 35
hours. The profit per unit of 𝑃 is $25 and the profit per unit of 𝑄 is $30. Company policy is to
determine the production quantity of each product in such a way as to maximize the net profit
given that the available resources should not exceeded.

Task:
The aim is to formulate the problem of deciding how much of each product to make in the current
week as an LP.

Identifying Decision Variables:

We often start with identifying decision variables (i.e. what we want to determine among those
things which are under our control).
The company wants to determine the optimal product to make in the current week. So, there are
two decision variables:

𝑥: the number of units of 𝑃

𝑦 : the number of units of 𝑄

Setting Objective Function:

We want to maximize the net profit. The profit per each unit of product 𝑃 is $25 and profit per
each unit of product 𝑄 is $20. Therefore, the net profit is 25𝑥 + 30𝑦, as we produce x units of 𝑃
and y units of 𝑄.

We typically use the variable 𝑧 to denote the value of the objective. So the objective function can
be stated as

max 𝑧 = 25𝑥 + 30𝑦

Finding Constrains:

The amount of time that machine 𝐴 is available restricts the quantities to be manufactured. If we
produce 𝑥 units of 𝑃 and 𝑦 units of 𝑄, machine 𝐴 should be used for 50𝑥 + 24𝑦 minutes since
each unit of 𝑃 requires 50 minutes processing time on machine 𝐴 and each unit of 𝑄 requires 24
minutes processing time on machine 𝐴. On the other hand, machine 𝐴 is available for 40 hours or
equivalently for 2400 minutes. This imposes the following constraint,

50𝑥 + 24𝑦 ≤ 2400

Similarly, the amount of time that machine 𝐵 is available imposes the following constraint

30𝑥 + 33𝑦 ≤ 2100

Note: In most problems the decision variables are required to be non-negative and this should be
typically

50𝑥 + 24𝑦 ≤ 2400 (machine 𝐴 time)

30𝑥 + 33𝑦 ≤ 2100 (machine 𝐵 time)

𝑥≥0

𝑦≥0
Here is the L.P:

max 𝑧 = 25𝑥 + 30𝑦

50𝑥 + 24𝑦 ≤ 2400

30𝑥 + 33𝑦 ≤ 2100

𝑥≥0

𝑦≥0
Different kind of solution:

Basic solution: The solution of 𝑚 basic variables, when each of the 𝑛 non-basic variables is
considered zero is called basic solution.

For example, 2𝑥1 + 2𝑥2 + 3𝑥3 − 8𝑥4 = 4 (1)

3𝑥1 + 5𝑥2 + 4𝑥3 − 6𝑥4 = 8 (2)

Let, 𝑥1 , 𝑥2 are basic variables and 𝑥3 = 𝑥4 = 0 are non basic variables.

Solving these two equations we get,

𝑥1 = 1, 𝑥2 = 1

This is the basic solution.

Feasible solution: 𝑥𝑗 (𝑗 = 1,2 … … . . 𝑛) is a feasible solution of a linear programming problem if

it satisfies the constraints and the non- negative condition.

For example, 𝑥1 + 2𝑥2 + 4𝑥3 − 3𝑥4 = 3 (1)

4𝑥1 + 3𝑥2 − 2𝑥3 − 5𝑥4 = 2 (2)

Let, 𝑥2 , 𝑥4 are basic variables and 𝑥1 = 𝑥3 = 0 are non basic variables.

Solving these two equations we get,

𝑥2 = 9, 𝑥4 = 5

This is the feasible solution.

Basic feasible solution: In a linear programming problem a feasible solution which is also basic
is called basic feasible solution. In the other words, it is a basic solution which satisfy the non-
negative condition.

For example, 4𝑥1 + 2𝑥2 + 3𝑥3 − 8𝑥4 = 6 (1)

3𝑥1 + 5𝑥2 + 4𝑥3 − 6𝑥4 = 8 (2)

We obtain the basic feasible solution are

𝑥1 = 1 , 𝑥2 = 1 , 𝑥3 = 𝑥4 = 0

𝑥2 = 0 , 𝑥3 = 2 , 𝑥1 = 𝑥4 = 0

𝑥3 = 2 , 𝑥4 = 0 , 𝑥1 = 𝑥2 = 0
Optimal solution: An optimal solution is a feasible solution where the objective function reaches
its (maximum or minimum) value.

For example, the most profit or the least cost.

Non-degenerate basic feasible solution: A basic feasible solution is called non-degenerate basic
feasible solution if it has exactly 𝑚 positive.

For example, 𝑥1 + 2𝑥2 + 𝑥3 = 4 (1)

2𝑥1 + 𝑥2 + 𝑥3 = 5 (2)

Let, 𝑥1 , 𝑥2 are basic variables and 𝑥3 = 0 are non basic variables.

Solving these two equations we get,

𝑥1 = 2, 𝑥2 = 1

This is the non-degenerate basic feasible solution.

Degenerate basic feasible solution: A basic feasible solution is said to be degenerate basic
feasible solution if at least one of the basic variables is zero.

For example, 4𝑥1 + 2𝑥2 + 3𝑥3 − 8𝑥4 = 6 (1)

3𝑥1 + 5𝑥2 + 4𝑥3 − 6𝑥4 = 8 (2)

Let, 𝑥3 , 𝑥4 are basic variables and 𝑥1 = 𝑥2 = 0 are non basic variables.

Solving these two equations we get,

𝑥3 = 2, 𝑥4 = 0

This is the degenerate basic feasible solution.

Problem:1 Find all the basic feasible solution of the following L.P.P

2 x1 + 6 x 2 + 2 x3 + x 4 = 3

6 x1 + 4 x 2 + 4 x3 + 6 x 4 = 2

Solution: Given that,

2 x1 + 6 x 2 + 2 x3 + x 4 = 3

6 x1 + 4 x 2 + 4 x3 + 6 x 4 = 2

x1 , x 2 , x3 , x 4  0
The total number of solution set is 4 C 2 = 6

Now, let x1 and x 2 are basic and x3 = x4 = 0 (non- basic)

2 x1 + 6 x2 = 3 (1)

6 x1 + 4 x2 = 2 (2)

Solving (1) and (2), we get

1
x1 = 0 and x 2 =
2

1
Solution is (0, ,0,0)
2

Let, x1 and x3 are basic and x2 = x4 = 0 (non -basic)

2 x1 + 2 x3 = 3 (3)

6 x1 + 4 x3 = 2 (4)

Solving (3) and (4), we get

7
x1 = −2 and x3 =
2

7
Solution is (−2,0, ,0)
2

Let, x1 and x 4 are basic and x2 = x3 = 0 (non -basic)

2x1 + x4 = 3 (5)

6 x1 + 6 x4 = 2 (6)

Solving (5) and (6) we get

8 −7
x1 = and x 4 =
3 3

8 −7
Solution is ( ,0,0, )
3 3

Let, x 2 and x3 are basic and x1 = x4 = 0 (non- basic)

6 x 2 + 2 x3 = 3 (7)
4 x 2 + 4 x3 = 2 (8)

Solving (7) and (8) we get

1
x2 = and x3 = 0
2

1
Solution is (0, ,0,0)
2

Let, x 2 and x 4 are basic and x1 = x3 = 0 (non- basic)

6 x2 + x4 = 3 (9)

4 x2 + 6 x4 = 2 (10)

Solving (9) and (10) we get

1
x2 = and x4 = 0
2

1
Solution is (0, ,0,0)
2

Let, x3 and x 4 are basic and x1 = x2 = 0 (non- basic)

2 x1 + 6 x2 = 3 (11)

6 x1 + 4 x2 = 2 (12)

Solving (11) and (12), we get

x3 = 2 and x4 = −1

Solution is (0,0,2,−1)

Finally, we obtain the basic feasible solution are

1
x1 = 0, x 2 = , x3 = 0, x 4 = 0
2

1
x1 = 0, x 2 = , x3 = 0, x 4 = 0
2

1
x1 = 0, x 2 = , x3 = 0, x 4 = 0
2
Problem: Reduce the following L.P into standard form

Maximize 𝑍 = 2𝑥1 − 3𝑥2 + 𝑥3

Subject to the constraints 2𝑥1 + 3𝑥2 ≤ 5

𝑥1 + 𝑥3 ≥ 3

𝑥1 + 2𝑥2 = 1

Where 𝑥3 ≥ 0 and𝑥1 , 𝑥2 are unrestricted in sign.

Solution: Introducing slack and surplus variables we get,

2𝑥1 + 3𝑥2 + 0. 𝑥3 + 𝑠1 = 5

𝑥1 + 0. 𝑥2 + 𝑥3 − 𝑠2 = 3

𝑥1 + 2𝑥2 + 0. 𝑥3 = 1

Where 𝑥3 ≥ 0 , 𝑠1 ,𝑠2 ≥ 0 and 𝑥1 , 𝑥2 are unrestricted in sign.

Now put, 𝑥1 = 𝑥1 ′ − 𝑥1 "

𝑥2 = 𝑥2 ′ − 𝑥2 "

𝑥3 = 𝑥3 ′

Putting the value, Max Z = 2(𝑥1 ′ − 𝑥1 ") − 3( 𝑥2 ′ − 𝑥2 ") + 𝑥3 ′ + 0. 𝑠1 + 0. 𝑠2

Sub to 2(𝑥1 ′ − 𝑥1 ") + 3( 𝑥2 ′ − 𝑥2 ") + 0. 𝑥3 + 𝑠1 = 5

(𝑥1 ′ − 𝑥1 ") + 0. 𝑥2 + 𝑥3 ′ − 𝑠2 = 3

(𝑥1 ′ − 𝑥1 ") + 2( 𝑥2 ′ − 𝑥2 ") + 0. 𝑥3 = 1

Where, 𝑥1 ′, 𝑥1 ", 𝑥3 ′, 𝑥2 ′, 𝑥2 ", 𝑠1 , 𝑠2 ≥ 0

This is required standard form of the L.P.P.

L.P.P is canonical form.

Application of L.P:

• Business and industry

1. Petroleum industry: Exploration production and refining distribution and pollution
control.
2. Food processing industry: Determine the optimal mix of feeds, optimal allocation
of crates from various plants to different ware houses etc.
 3. Iron and steel industry: Decide the types of products to be made in the rolling mills
so as to maximize the profit. Metal working industries, paper and textile industries
use L.P for the optimal use of the raw materials to maximize the profit minimize
the losses.
• L.P has been also used in determining the best route for air crafts and ships.
• Financial industry and firms use L.P for evaluating investment plan.
Administration, education and politics also employ L.P for solve their problems.

Sensitivity Analysis:
Sensitivity Analysis is a technique used to determine how the variation in the output of a model
(such as a linear programming problem) can be attributed to different variations in its input
parameters. In the context of linear programming (LP), it helps in understanding how changes in
coefficients of the objective function or constraints affect the optimal solution.
Purpose of Sensitivity Analysis:

• To analyze the stability and robustness of the optimal solution.

• To help decision-makers understand the impact of uncertainties.
• To guide adjustments in resource allocation, pricing, or production planning.

Key Components in Sensitivity Analysis (in LP):

1. Objective Coefficient Range:

o Shows how much an objective function coefficient (like profit per unit) can change
without changing the optimal solution mix.
2. Right-Hand Side (RHS) Range:
o Indicates how much the availability of a resource (constraint RHS) can change
without altering the current basis of the solution.

3. Shadow Price (Dual Value):

o Represents the change in the objective function value per unit increase in the RHS
of a constraint, assuming other data remains unchanged.

4. Reduced Cost:
o Indicates how much the objective function coefficient of a non-basic variable must
improve before it enters the solution.
Tools and Techniques of Sensitivity Analysis:
1. Graphical Method (for 2-variable problems):

o Visual representation of feasible region, objective function, and effects of changes

in coefficients.
o Useful for small-scale problems.

2. Simplex Method Table (Final Tableau):

o Provides sensitivity information such as shadow prices and reduced costs after
solving the LP problem.
3. Computer-Based Tools:
o Software tools that automatically generate detailed sensitivity reports:

▪ Microsoft Excel Solver:

▪ Produces Sensitivity Report with allowable increases/decreases,
shadow prices, and reduced costs.

▪ LINDO / LINGO:
▪ Specialized LP software with advanced sensitivity analysis features.

▪ TORA:
▪ Educational software that offers simplex and sensitivity analysis
support.

4. Duality Theory:
o The concept of converting the primal problem to its dual to analyze sensitivity and
economic interpretations.

5. What-If Analysis:
o Manually changing input values (like resource availability or cost/profit) to observe
impact on results.

Therefore, Sensitivity analysis is an essential part of linear programming that helps evaluate the
reliability of the optimal solution under uncertainty. By using various analytical and software-
based tools, it aids in informed and flexible decision-making.
 Graphical method of linear programming
Formulation and Graphical Solutions of System of Linear Inequalities and
Linear Programming:

Linear Programming Problem:

Linear Programming Problem is the class of optimization problem. When a linear function of
several variables is to be optimized subject to a number of conditions called constraints, which are
also the linear functions of non-negative involved variables. Usually, constraints of the problem
are of linear inequality type.

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?

Solution of the Problem:

Let’s first tabulate the given information:

Type-A Type-B Time Available

Profit / $1.00 $1.20

unit
Machine 2 min 1 min 180 min
I
Machine 1 min 3 min 300 min
II

Let x be the number of type-A souvenir and y be the type-B souvenir.

Then the total profit (in dollars) is given by, P = x+1.2y

Which is the objective function to be maximized.

The total amount of time that machine I is used is 2x+y and must not exceed 180 minutes. Thus,
we have the inequality: 2x+y≤180

The total amount of time that machine II is used is x+3y and must not exceed 300 minutes.

Thus. we have the inequality: x+3y≤300

Finally, neither x nor y can be negative, so, x ≥ 0, y ≥ 0

In short, we want to maximize the objective function: P = x+1.2y

Subject to the system of inequalities,

2x+y≤180

x+3y≤300

x≥ 0, y≥ 0

Graphical Solution of the Problem:

We first graph the feasible set S for the problem:

We shall graph the solution for the inequality: 2x+y≤180

Considering only positive values for x and y,

200
(0,180)

2x+y≤180

100

(90,0)
X
100 200

2x+y=180
We shall graph the solution for the inequality: x+3y≤300

Considering only positive values for x and y,

Y
200

(0,100) x+3y≤300

100

(300,0)
X

100 200 300

x+3y=300

Graph the intersection of the solutions to the inequalities yielding the feasible set S.
(Where the feasible set S is bounded)
 Y

200

D(0,100)
100 C(48,84)
S
A(0,0) X
B(90,0) 100

x+3y=300
2x+y=180

Tabular Form:

Vertex P=x+1.2y

A(0,0) 0

B(90,0) 90

C(48,84) 148.8

D(0,100) 120

Identifying the vertex with the highest value for P

We can see that, P is maximized at the vertex C(48,84) and has a value of 148.80.
So, we conclude that ACE Novelty would maximize its profit at $148.80 by producing 48
type-A souvenirs and 84 type-B souvenirs.
Problem-1:Solve graphically the following L.P.P.

Maximize 𝑧 = 5𝑥1 + 3𝑥2

Subject to 𝑥1 + 𝑥2 ≤ 6

0 ≤ 𝑥1 ≤ 3

0 ≤ 𝑥2 ≤ 3

2𝑥1 + 3𝑥2 ≥ 3

𝑥1 , 𝑥2 ≥ 0

Solution: The solution space satisfying the given constraints and meeting the non-negativity
restrictions 𝑥1 ≥ 0 and 𝑥2 ≥ 0 is shown shaded figure bellow

Any point in this shaded region is a feasible solution to the given problem. The vertices of the
3
convex region ABCDE are 𝐴(0,1), 𝐵(0,3), 𝐶 (3,3), 𝐷(3,0) and 𝐸 (2 . 0)

Values of the objective function 𝑧 = 5𝑥1 + 3𝑥2 at these vertices are

𝑧(𝐴) = 𝑧(0,1) = 5.0 + 3.1 = 3

𝑧(𝐵) = 𝑧(0,3) = 5.0 + 3.3 = 9

𝑧(𝐶 ) = 𝑧(3,3) = 5.3 + 3.3 = 24

𝑧(𝐷) = 𝑧(3,0) = 5.3 + 3.0 = 15
3 3 15
𝑧(𝐸 ) = 𝑧 ( , 0) = 5. + 3.0 =
2 2 2
Since the maximum value of z is 24, which occurs at the vertex𝐶 (3,3), the solution to given
problem is

𝑥1 = 3, 𝑥2 = 3, 𝑎𝑛𝑑 𝑧𝑚𝑎𝑥 = 24

Problem-2: Solve graphically the following L.P.P.

Minimize 𝑧 = 20𝑥1 + 10𝑥2

Subject to 𝑥1 + 2𝑥2 ≤ 40

3𝑥1 + 𝑥2 ≥ 30

4𝑥1 + 3𝑥2 ≥ 60

𝑥1 , 𝑥2 ≥ 0
Solution: The solution space satisfying the given constraints and meeting the non-negativity
restrictions 𝑥1 ≥ 0 and 𝑥2 ≥ 0 is shown shaded figure bellow

Any point in this shaded region is a feasible solution to the given problem. The co-ordinates of the
vertices of the convex region ABCD are 𝐴(6,12), 𝐵(4,18), 𝐶(40,0) and 𝐷(15,0).

Values of the objective function 𝑧 = 20𝑥1 + 10𝑥2 at these vertices are

𝑧(𝐴) = 𝑧(6,12) = 20.6 + 10.12 = 240

𝑧(𝐵) = 𝑧(4,18) = 20.4 + 10.18 = 260

𝑧(𝐶 ) = 𝑧(40,0) = 20.40 + 10.0 = 800

𝑧(𝐷) = 𝑧(15,0) = 20.15 + 10.0 = 300

Since the minimum value of z is 240, which occurs at the vertex 𝐴(5,12), the solution to the given
problem is

𝑥1 = 6, 𝑥2 = 12 𝑎𝑛𝑑 𝑧𝑚𝑖𝑛 = 240

Problem-3: Solve graphically the following L.P.P.

Maximize Z = −0.1x1 + 0.5x2

Subject to 2 x1 + 5x2  80

x1 + x2  20

x1 , x2  0

Solution: The solution space satisfying the constraints 2 x1 + 5x2  80 and x1 + x2  20 and
meeting the non-negativity restrictions x1  0 and x2  0 is shown shaded in the figure below.

The co-ordinates of the vertices of the convex region OABC are O(0,0), A(0,16), B(6.5,13.5) and
C(20,0).Values of the objective function z = −0.1x1 + 0.5x2 at these vertices are
Z (0) = Z (0,0) = (−0.1).(0) + (0.5).(0) = 0

Z ( A) = Z (0,16) = (−0.1).(0) + (0.5).(16) = 8

Z ( B) = Z (6.5,13.5) = (−0.1).(6.5) + (0.5).(13.5) = 6.10

Z (C ) = Z (20.0,0) = (−0.1).(20) + (0.5).(0) = −2

Since the maximum value of z is 8,which occurs at the vertex A(0,16),the solution of the given
problem is x1 = 0, x2 = 16 with Z max = 8 .

Problem-4:Solve graphically the following L.P.P.

Maximize Z = 40x1 + 100x2

Subject to 12x1 + 6 x2  3000

4x1 + 10x2  2000

2 x1 + 3x2  900

x1 , x2  0
Solution: The solution space satisfying the given constraints and meeting the non-negativity
restrictions x1  0 and x2  0 is shown shaded in the figure below.

The co-ordinates of the vertices of the convex region OABC are O(0,0), A(0,200), B(187.5,125)
and C(250,0).Values of the objective function z = 40x1 + 100x2 at these vertices are
Z (0) = Z (0,0) = (40).(0) + (100).(0) = 0

z ( A) = z (0,200) = (40).(0) + (100).(200) = 20,000

z ( B) = z (187.5,125) = (40).(187.5) + (100).(125) = 20,000

z (C ) = z (250,0) = (40).(250) + (100).(0) = 10,000

Thus the maximum value of z occurs at two vertices A and B of the convex shaded region
[Link], there is no unique optimal solution to the problem and any point between A and
B on the line AB can be taken as an optimal solution with optimal value z=20,000

Problem-5: Solve graphically the following L.P.P.

Maximize𝑧 = 2𝑥1 + 3𝑥2

Subject to𝑥1 + 𝑥2 ≤ 1

3𝑥1 + 𝑥2 ≤ 4
𝑥1 , 𝑥2 ≥ 0
Solution:The solution space satisfying the given constraints and meeting the non-negativity
restrictions 𝑥1 ≥ 0 and 𝑥2 ≥ 0 is shown shaded figure bellow

Any point in this shaded region is a feasible solution to the given problem.

The co-ordinates of the vertices of the convex region OAB are 𝑂(0,0), 𝐴(0,1) and 𝐵(1,0).

Values of the objective function 𝑧 = 2𝑥1 + 3𝑥2 at these vertices are

𝑧(𝑂) = 𝑧(0,0) = 2.0 + 3.0 = 0

𝑧(𝐴) = 𝑧(0,1) = 2.0 + 3.1 = 3

𝑧(𝐵) = 𝑧(1,0) = 2.1 + 3.0 = 2

Since the maximum value of z is 3, which occurs at the vertex 𝐴(0,1), the solution to the given
problem is 𝑥1 = 0, 𝑥2 = 1 with 𝑧𝑚𝑎𝑥 = 3

Problem-6: Solve graphically the following L.P.P.

Maximize 𝑧 = 5𝑥1 + 3𝑥2

Subject to 3𝑥1 + 5𝑥2 ≤ 15

5𝑥1 + 2𝑥2 ≤ 10

𝑥1 , 𝑥2 ≥ 0
Solution: The solution space satisfying the given constraints and meeting the non-negativity
restrictions 𝑥1 ≥ 0 and 𝑥2 ≥ 0 is shown shaded figure bellow

Any point in this shaded region is a feasible solution to the given problem.
20 45
The co-ordinates of the vertices of the convex region OABC are 𝑂(0,0), 𝐴(0,3), 𝐵 (19 , 19 ) and
𝐶 (2,0)

Values of the objective function 𝑧 = 5𝑥1 + 3𝑥2 at these vertices are

𝑧(𝑂) = 𝑧(0,0) = 5.0 + 3.0 = 0

𝑧(𝐴) = 𝑧(0,3) = 5.0 + 3.3 = 9
20 45 20 45 235
𝑧 (𝐵 ) = 𝑧 ( , ) = 5. + 3. =
19 19 19 19 19
𝑧(𝐶 ) = 𝑧(2,0) = 5.2 + 3.0 = 10
235 20 45
So, the maximum value of z is , which occurs at the vertex 𝐵 (19 , 19 ) ,the solution to the given
19
problem is
20 45 235
𝑥1 = 19 , 𝑥2 = 19 with 𝑧𝑚𝑎𝑥 = 19

The Simplex Method

Iteration Method: A linear programming problem is

maximize 𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛
Subject to the constraints,
𝑎11 𝑥1 + 𝑎11 𝑥1 + . .. +𝑎1𝑛 𝑥𝑛 ≤ 𝑏1

𝑎21 𝑥1 + 𝑎22 𝑥2 + . . . +𝑎2𝑛 𝑥𝑛 ≤ 𝑏2

… .. . .. . .. . ..

𝑎1𝑚 𝑥1 + 𝑎2𝑚 𝑥2 + ⋯ . .. + 𝑎𝑚𝑛 𝑥𝑛 ≤ 𝑏𝑛

𝑥𝑗 ≥ 0, 𝑗 = 1,2 . . . 𝑛

Step-1:
Introducing slack variables 𝑆𝑗 ≥ 0, 𝑗 = 1,2, . . . . . . 𝑚 to convert the inequality to an equation
and adding them into objective function with co- efficient zero. We get,
Maximize 𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 + 0. 𝑠1 + 0. 𝑠2 + ⋯ + 0. 𝑠𝑚
subject to constraints,

a11 x1 + a12 x 2 + .......... .......... .. + a1n x n + s1 + 0.s 2 + ...... + 0.s m = b1

a 21 x1 + a 22 x 2 + .......... .......... .. + a 2 n x n + 0.s1 + s 2 + ...... + 0.s m = b2
.......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......
.......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......
a m1 x1 + a m 2 x 2 + .......... .......... .. + a mn x m + 0.s1 + 0.s 2 + ...... + 1.s m = bm
In Initial basic feasible solution is obtained by

𝑥1 = 0 = 𝑥2 . . . . . = 𝑥𝑛 and 𝑠1 = 𝑏1 , 𝑠2 = 𝑏2 . . .. 𝑠𝑚 = 𝑏𝑚

𝑏1 , 𝑏2 , . . . 𝑏𝑛 ≥ 0
Step 3:
Rewriting objective function, we obtain,
− c1 x1 + c2 x2 + .......... .. + c j x j + Z j = 0

Step- 4:
Placing the restate objective function below the system of equation of construction,

a11 x1 + a12 x 2 + .......... .......... .. + a1n x n + s1 + 0.s 2 + ...... + 0.s m = b1

a 21 x1 + a 22 x 2 + .......... .......... .. + a 2 n x n + 0.s1 + s 2 + ...... + 0.s m = b2
.......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......
.......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......
a m1 x1 + a m 2 x 2 + .......... .......... .. + a mn x m + 0.s1 + 0.s 2 + ...... + s m = bm
− c1 x1 + c 2 x 2 + .......... .. + c j x j + Z j = 0

Step -5:
Thus the initial table associate with this system is

𝑥1 𝑥2 ……… 𝑥𝑛 𝑠1 𝑠2 ……… 𝑠𝑛 z Constant Min path

𝑎11 𝑎12 ……… 𝑎1𝑛 1 0 ……… 0 0 𝑏1 𝑏1
= 𝑑1
𝑎11
𝑎21 𝑎22 ……… 𝑎2𝑛 0 1 ……… 0 0 𝑏2 𝑏2
= 𝑑2
𝑎21
𝑎𝑛1 𝑎𝑛2 ……… 𝑎𝑚𝑛 0 0 ……… 1 0 𝑏𝑛 𝑏𝑛
= 𝑑3
𝑎𝑛1
-𝑐1 -𝑐2 ……… -𝑐𝑛𝑛 0 0 ………. 0 1 0
Set up the initial simplex tableau.
Determine whether the optional solution has been reached by examining all entries in the last row
to the left of the vertical line
If all entries are non-negative, the optional solution has been reached and proceed to step 4.
If negative entries exist, the optional solution has not been reached and we have to do iteration
again.
Perform the point operation. Return to step 2.
Determine the optional solution.
Step 6: Determine whether the optional selection has been reached.
Since their negative entries in the last row, the initial selection is not optional.

Step 7: Performing the pivot operation.

Let (a) since the entry -𝑐1 is the most (-ve) to the left of the vertical line in the last row, the 1st
column is the pivot column.
(b) Divide each positive number / -ve number of the p.c into the corresponding entry in the column
of constants and compare the ratios thus obtained.

𝑥1 𝑥2 ……… 𝑥𝑛 𝑠1 𝑠2 ……… 𝑠𝑛 z Constant Min path

𝑎11 𝑎12 ……… 𝑎1𝑛 1 0 ……… 0 0 𝑏1 𝑏1
= 𝑑1
𝑎11
𝑎21 𝑎22 ……… 𝑎2𝑛 0 1 ……… 0 0 𝑏2 𝑏2
= 𝑑2
𝑎21
𝑎𝑛1 𝑎𝑛2 ……… 𝑎𝑛𝑛 0 0 ……… 1 0 𝑏𝑛 𝑏𝑛
= 𝑑3
𝑎𝑛1
-𝑐1 -𝑐2 ……… -𝑐𝑛 0 0 0 0 1 0

Here we face 4 cases.

𝑏
If all entries or any entry in p.c –ve but const +ve i.e 𝑎 1 = no result is counted.
11
𝑏1
2. Again if -𝑎 = no result is counted.
11
𝑏1
But if 𝑎 = 𝑑1 it is counted.
11
If every element in the p.c is –ve in a certain table of simplex Method, then the given problem
leads to an unbounded solution because we can’t apply the minimum ratio in the table.

From Minimum Ratio, the smallest value is estimated. Let it is 𝑑1 , so the 1st row is Pivot row.

The intersection of p.c and p.r is 𝑎11 . So 𝑎11 is p.E

𝑥1 𝑥2 ……… 𝑥𝑛 𝑠1 𝑠2 ……… 𝑠𝑛 z Constant

𝑎11 𝑎12 ……… 𝑎1𝑛 1 0 ……… 0 0 𝑏1
𝑎21 𝑎22 ……… 𝑎2𝑛 0 1 ……… 0 0 𝑏2
𝑎𝑛1 𝑎𝑛2 ……… 𝑎𝑛𝑛 0 0 ……… 1 0 𝑏𝑛
-𝑐1 -𝑐2 ……… -𝑐𝑛 0 0 0 0 1

Step 8: Now convert the Pivot element into 1 by dividing by 𝑎11 and use elementary row
operations to convert the Pivot column into a unit column.
All entries below the unit or 1 are 0.

𝑅1 ×(- 𝑎21 ) + 𝑅2 =𝑅2 ’

𝑅1 ×(- 𝑎31 ) + 𝑅3 =𝑅3 ’

.
.
.
𝑅1 ×(- 𝑎𝑛1 ) + 𝑅𝑛 =𝑅𝑛 ’

𝑅1 × 𝑐1 +(- 𝑐1 )=P
This completes the iteration if there is no any –ve value in the last row.

So, we have obtained an optional solution.

𝑏
𝑥1 =𝑎 1
11

𝑥2 =0
.
.
.
𝑥𝑛 =0
𝑏
Z= 𝑥1 (- 𝑐1 ) ×𝑎 1
11

The optional solution is called Unique if all the non-basic variables have –ve values for their
relative profits. This means that any increase in the decision variables will result in an immediate
decrease in the objective function.
For minimization problem:
We have to find the most +ve value from the Pivot column.
Here, we introduce with surplus variables.

𝑥1 𝑥2 ……… 𝑥𝑛 𝑠1 𝑠2 ……… 𝑠𝑛 z Constant

𝑎11 𝑎12 ……… 𝑎1𝑛 1 0 ……… 0 0 𝑏1
𝑎21 𝑎22 ……… 𝑎2𝑛 0 1 ……… 0 0 𝑏2
𝑎𝑛1 𝑎𝑛2 ……… 𝑎𝑛𝑛 0 0 ……… 1 0 𝑏𝑛
-𝑐1 -𝑐2 ……… -𝑐𝑛 0 0 0 0 1 0
Minimize. Z = c1 x1 + c2 x2 + .......... .......... ... + cn xn
Subject to the constraints,
a11 x1 + a12 x 2 + .......... ... + a1n x n  b1
a 21 x1 + a 22 x 2 + .......... ... + a 2 n x n  b2
.......... .......... .......... .......... .......... .......
a n1 x1 + a n 2 x 2 + .......... ... + a nn x n  bn

Adding surplus variables and making inequalities in equations, we get,

Z = c1 x1 + c2 x2 + .......... .......... ... + cn xn + 0.s1 + 0.s 2 + .... + 0.s n

Subject to constraints,
a11 x1 + a12 x2 + .......... .......... .. + a1n xn + s1 + 0.s2 + ...... + [Link] = b1
a21 x1 + a22 x2 + .......... .......... .. + a2 n xn + 0.s1 + s2 + ...... + [Link] = b2
.......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......
.......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......
am1 x1 + am 2 x2 + .......... .......... .. + amn xm + 0.s1 + 0.s2 + ...... + sm = bm

𝑥1 𝑥2 ……… 𝑥𝑛 𝑠1 𝑠2 ……… 𝑠𝑛 z Constant

𝑎11 𝑎12 ……… 𝑎1𝑛 1 0 ……… 0 0 𝑏1
𝑎21 𝑎22 ……… 𝑎2𝑛 0 1 ……… 0 0 𝑏2
𝑎𝑛1 𝑎𝑛2 ……… 𝑎𝑛𝑛 0 0 ……… 1 0 𝑏𝑛
-𝑐1 -𝑐2 ……… -𝑐𝑛 0 0 0 0 1 0

Artificial Variable:

Constrains in LPP with ≤, ≥ then we have to add variables left hand of these constraints. These
variables are called Artificial Variables i.e surplus, slack variable.
In simplex method of solving L.P.P, the role of artificial variable: slack, surplus help us to obtain
initial basic feasible solution.

Theorem 1:

If for any basic feasible selection xB if a L.P.P at any iteration of simple algorithm Z j − C j  0
for all the non-basic vectors of A, then xB is an optional solution.

Proof: Let
A = (a1 , a2,.......,an )
B = (1 , 2,.......,  m )
Here, Ax = b .....(i)
xB = B−1b [BxB = b]
is the basic feasible solution and the of objection function is ZB = CB xB .

Z j − C j  0 For all column vectors a j . It is required to prove that Z B is the optimal value of the
objective function corresponding to the basic feasible solution xB .

Let, x ' = [ x '1 , x2' ..... xn' ] be any feasible solution of the problem which makes the objective function
n
to z =  c j x j
j =1

We have to prove that Ax = b z  zB

Since x  is a solution of Ax = b , we have Ax = b

 Ax = BxB
 xB = B−1 (Ax ) = (B−1 A)x  =   [  = [y1 , y2 ...yn ]]
 xB = (y1 , y2 ,..., yn )[ x1 , x2 ,..., yn ] ......(ii)
[ xB1 , xB2 ...xBn ] =
n
Equating we get, xBi =  yij x j ......(iii )
i =1

Now Z j − C j  0 for all columns a j of A

 c j  z j for all j
 c j x j  z j x j as x j  0
n n
  c j x j   z j x j
j =1 j =1
n n n
  c j x j   ( cBi yij )
j =1 j =1 j =1
m n
 z   CBi  x j yij
j =1 j =1
m
 z   CBi xBi [ from (iii)]
i =1

 z  cB xB
 z  zB ..............(iv)

Hence zB is the optimal value of the objective function corresponding to the basic feasible solution
zB .

Hence the theorem is proved.

(i) consider the value of Z j − C j for a column vector  r , r = 1,2,...., m

 i = 1 y1 j + 2 y2 j + ..... +  i yij + .... +  m ymj

 y j = ej

A unit vector ith component unity.

 cBi = c j
 z j − c j = cB y j − cBi = cB ei − cBi = cBi − cBi = 0

Thus z j − c j = 0 for all columns corresponding to B.V.

Problem 1: Solve the following L.P.P problem by using simplex method.

6
Maximize, P = x + y
5

Subject to 2 x + y  180

x + 3 y  300

x, y  0
Solution: Introducing slack variables u and v into the given inequalities we get,
2x+y+u=180

x+3y+v=300
6
 −x − y + 0.u + 0.v + p = 0
5

Now the initial tableau associated this system is

Initial Simplex table:

Cj 1 6 0 0
5
CB Basic x1 x2 s1 s2 Solution Ratio
variable XB
0 s1 2 1 1 0 180 6
0 s2 1 3 0 1 300 3
Zj 0 0 0 0 0
Cj − Z j 1 6 0 0
5
From table we can see the 2nd column and the 2nd row is the pivot column and row respectively.
And 3 is the pivot element.
Iteration-I:

Cj 1 6 0 0
5
CB Basic x1 x2 s1 s2 Solution Ratio
variable XB
0 s1 5 0 1 1 80 48
−
3 3
6 x2 1 1 0 1 100 300
5 3 3
Zj 2 6 0 2 0
5 5 5
Cj − Z j 3 0 0 2
−
5 5
Also, not optimal.

3rd table:
 Cj 1 6 0 0
5
CB Basic x1 x2 s1 s2 Solution Ratio
variable XB
1 x1 1 0
3 1 48 48
−
5 5
6 x2 0 1 1 2 84 300
−
5 5 5
Zj 1 6 9 1 144.4
5 25 5
Cj − Z j 0 0 9 1
− −
25 5
The last row of the table contains all negative numbers so an optimal solution has been reached.

Problem 2: Use the simplex method to solve the following LPP

Maximize Z = 7 x1 + 5x2

Subject to: x1 + 2 x2  6

4 x1 + 3 x2  12
x1 , x2  0

Solution: The given LPP is,

Maximize Z = 7 x1 + 5x2

Subject to: x1 + 2 x2  6

4 x1 + 3 x 2  12
x1 , x 2  0

Introducing slack variables in the given equation we get,

Maximize Z = 7 x1 + 5x2 + s1 .0 + s2 .0

Subject to: x1 + 2 x2 + s1 = 6

4 x1 + 3 x 2 + s 2 = 12
x1 , x 2 , s1 , s 2  0

Now, Putting the decision variables x1 = x2 = 0

We get, s1 = 6, s2 = 12

Which are the initial values of the slack variables.

Let us tabulate the system as follows

Initial Table:

Cj 7 5 0 0
CB Basic Basic x1 x2 s1 s2 Ratio
variable solution
B XB
0 s1 6 1 2 1 0 6
0 s2 12 4 3 0 1 3
Zj 0 0 0 0
Cj − Z j 7 5 0 0

Since 7 is the most positive element in C −z

j j
, the pivot column is the column containing x and
1

the pivot row is the row containing the minimum ratio 3.

2nd Table:

Cj 7 5 0 0
CB B XB x1 x2 s1 s2
0 s1 3 0 5/4 1 -1/4
7 x1 3 1 3/4 0 1/4
Zj 7 -21/4 0 7/4
Cj − Zj 0 -1/4 0 -7/4
Since all C j − Z j is either zero or negative. Optimal solution has been reached

x1 = 3, x 2 = 0, Z max = 21

This is the required result of the given problem.

Problem 3: Use the simplex method to solve the following LPP

Minimize Z = x1 − 3x2 + 2 x3

Subject to 3x1 − x2 + 2 x3  7
 2 x1 − 4 x 2  −12
− 4 x1 + 3 x 2 + 8 x3  10
x1 , x 2 , x3  0

Solution: The given LPP can be written as

Minimize Z = x1 − 3x2 + 2 x3

Subject to 3x1 − x2 + 2 x3  7

− 2 x1 + 4 x 2  12
− 4 x1 + 3 x 2 + 8 x3  10
x1 , x 2 , x3  0

Introducing slack variables in the above inequalities we get,

Minimize Z = x1 − 3x2 + 2 x3 + s1 .0 + s 2 .0 + s3 .0

Subject to 3x1 − x2 + 2 x3 + s1 = 7

− 2 x1 + 4 x 2 + s 2 = 12
− 4 x1 + 3 x 2 + 8 x3 + s3 = 10
x1 , x 2 , x3 , s1 , s 2 , s3  0

Now pitting x1 = x2 = x3 = 0

We get s1 = 7, s 2 = 12, s3 = 10 which are the initial values of the slack variables.

Let us tabulate the system as follows

Initial Table:

Cj 1 -3 2 0 0 0
CB B XB x1 x2 x3 s1 s1 s1 Ratio
0 s1 7 3 -1 2 1 0 0 -7
0 s2 12 -2 4 0 0 1 0 3
0 s3 10 -4 3 8 0 0 1 3.33
Zj 0 0 0 0 0 0
Cj − Zj 1 -3 2 0 0 0
Since -3 is the most negative element in C −z
j j
, the pivot column is the column containing x 2

and the pivot row is the row containing the minimum ratio 3.

2nd Table:

Cj 1 -3 2 0 0 0
CB B XB x1 x2 x3 s1 s1 s1
0 s1 7 3 -1 2 1 0 0
-3 x2 3 -1/2 1 0 0 1/4 0
0 s3 10 -4 3 8 0 0 1

3rd Table:

Cj 1 -3 2 0 0 0
CB B XB x1 x2 x3 s1 s1 s1 Ratio
0 s1 10 5/2 0 2 1 ¼ 0 4
-3 x2 3 -1/2 1 0 0 ¼ 0 -6
0 s3 -1 5/2 0 -8 0 ¾ -1 -2/5
Zj 3/2 -3 0 0 -3/4 0
Cj − Zj -1/2 0 2 0 3/4 0

4th Table:

Cj 1 -3 2 0 0 0

CB B XB x1 x2 x3 s1 s1 s1
1 x1 4 1 0 4/5 0 1/10 0
-3 x2 3 -1/2 1 0 0 ¼ 0
0 s3 -1 5/2 0 -8 2/5 ¾ 1
Zj 7/2 -3 4/5 2/5 -13/20 0
Cj − Zj -5/2 0 6/5 -2/5 13/20 0
5th Table:

Cj 1 -3 2 0 0 0
CB B XB x1 x2 x3 s1 s1 s1
1 x1 4 1 0 4/5 2/5 1/20 0
-3 x2 5 0 1 2/5 1/5 9/20 0
0 s3 11 0 0 10 1 -1/2 1
Zj 1 -3 -2/5 -1/5 -5/4 0
Cj − Zj 0 0 12/5 1/5 5/4 0
Since all C j − Z j is either positive or zero. Optimal solution has been reached

x1 = 4, x 2 = 5, Z min = −11.

This is the required result of the LPP.

Problem-4: Use the simplex method to solve the following LPP

Minimize Z = −2 x1 + 3x2

Subject to. 2 x1 − 5x2  7

4x1 + x2  8

7 x1 + 2 x2  16

x1 , x2  0

Solution: Introducing slack variable in the given inequalities.

Minimize Z = −2 x1 + 3x2 + s1.0 + s2 .0 + s3.0

subject to 2 x1 − 5x2 + s1 = 7

4 x1 + x2 + s2 = 8

7 x1 + 2 x2 + s3 = 16

x1, x2 , s1, s2 , s3  0

Putting the decision variables x1 = x2 = 0 , we get s1 = 7, s2 = 8, s3 = 16 which are the initial values
of slack variables.
 cj −2 3 0 0 0 Ratio
cB Basic Basic x1 x2 s1 s2 s3
variable solution
(B ) (X B )
0 s1 7 2 −5 1 0 0 3.5
0 s2 8 4 1 0 1 0 2
0 s3 16 7 2 0 0 1 2.25
zj 0 0 0 0 0
cj − zj −2 3 0 0 0

cB B XB x1 x2 s1 s2 s3
0 s1 7 2 −5 1 0 0
−2 x1 2 1 1 0 1 0
4 4
0 s3 16 7 2 0 0 1

cj −2 3 0 0 0
cB B XB x1 x2 s1 s2 s3
0 s1 3 0 − 11 1 −1 0
4 2
−2 x1 2 1 1 0 1 0
4 4
0 s3 −2 0 −1 0 7 −1
4 4
zj −2 −1 0 −1 0
2 2
cj − zj 0 7 0 1 0
2 2

Here, x1 = 2, x2 = 0 . Thus Minimum Z = −4

Problem-5: Solve the following L.P.P problem by using simplex method.

Maximize, Z = 3x1 + 2 x 2 + 5 x 3

Subject to x1 + 2 x 2 + x3  430

x1 + 4 x 2  420

3x1 + 2 x3  460

x1 , x 2 , x 3  0

Solution: Introducing slack variables s1 , s 2 , s 3 the problem can be expressed in the standard form
as maximize Z= 3x1 + 2 x2 + 5 x3 + 0.s1 + 0.s 2 + 0.s 3

Subject to x1 + 2 x 2 + x3 + s1 = 430

x1 + 4 x 2 + s 2 = 420

3x1 + 2 x 3 + s 3 = 460

x1 , x 2 , x 3 , s1 , s2 , s3  0

The basic feasible solution is x1 = x 2 = x 3 =0 (non-basic)

s1 =430 (basic)

s 2 =420 (basic)

s 3 =460 (basic) With Z=0

Forming the initial tableau as

1st table:

Cj 3 2 5 0 0 0 Ratio=
CB B Xa x1 x2 x3 s1 s2 s3 X a / p.c
0 s1 430 1 2 1 1 0 0 430
0 s2 420 1 4 0 0 1 0 
0 s3 460 3 0 2 0 0 1 230

Zj 0 0 0 0 0 0

Cj −Z j 3 2 5 0 0 0
The arrow denotes the pivot column and row respectively. And 2 is the pivot element. Since
C j − Z j is positive under some columns 1st table is not optimal. In 1st table x 3 is incoming
variable, s 3 is outgoing variable. In table 2 s 3 is replaced by x3

2nd table: Note: R3 = R3 / 2

'

Cj 3 2 5 0 0 0
CB B Xa x1 x2 x3 s1 s2 s3
0 s1 430 1 2 1 1 0 0
0 s2 420 1 4 0 0 1 0
5 x3 230 3/2 0 1 0 0 1/2

Zj 0 0 0 0 0 0

Cj −Z j 3 2 5 0 0 0

3rd table:Note: R1 = R1 − R3
'

Cj 3 2 5 0 0 0 Ratio=
CB B x1 x2 s1 s2 X a / p.c
Xa x3 s3
0 s1 200 -1/2 2 0 1 0 -1/2 100
0 s2 420 1 4 0 0 1 0 105
5 x3 230 3/2 0 1 0 0 1/2 

Zj 15/2 0 5 0 0 5/2

Cj −Z j -9/2 2 0 0 0 -5/2

The arrow denotes the pivot column and row respectively. And 2 is the pivot element. Since
C j − Z j is positive under some columns 1st table is not optimal. In 1st table x 2 is incoming
variable, s1 is outgoing variable. In table 4 s1 is replaced by x 2
4th table: Note: R1' = R1 / 2 then R2' = 4 R1' − R2

Cj 3 2 5 0 0 0
CB B Xa x1 x2 x3 s1 s2 s3
2 x2 100 -1/4 1 0 1/2 0 -1/4
0 s2 20 -2 0 2 0 -1 -1
5 x3 230 3/2 0 1 0 0 1/2

Zj 7 2 5 1 0 2

Cj −Z j -4 0 0 -1 0 -2

Since C j − Z j is either negative or zero under all column, 4th table is optimal.

Thus, the optimal basic feasible solution is x1 = 0 , x2 = 100 , x3 = 230 with Z max = 1350.

Problem-6: Solve the following L.P.P problem by using simplex method.

Maximize, Z = 2 x1 + x2

Subject to x1 + 2 x2  10

x1 + x2  6

x1 − x2  2

x1 , x 2  0

Solution: Introducing slack variables s1 , s 2 , s 3 the problem can be expressed in the standard form
as maximize Z= 2 x1 + x2 + 0.s1 + 0.s 2 + 0.s 3
Subject to x1 + 2 x2 + s1 = 10

x1 + x2 + s2 = 6

x1 − x2 + s3 = 2

x1 , x 2 , x 3 , s1 , s2 , s3  0
The basic feasible solution is x1 = x 2 = x 3 =0 (non-basic)

s1 =10 (basic)

s 2 =6 (basic)

s 3 =2 (basic) With Z=0

Forming the initial tableau as

1st table:

Cj 2 1 0 0 0 Ratio=
CB B x1 x2 s1 s2 X a / p.c
Xa s3
0 s1 10 1 2 1 0 0 10
0 s2 6 1 1 0 1 0 6
0 s3 2 1 -1 0 0 1 2

Zj 0 0 0 0 0

Cj −Z j 2 1 0 0 0

The arrow denotes the pivot column and row respectively. And 1 is the pivot element. Since
C j − Z j is positive under some columns 1st table is not optimal. In 1st table x1 is incoming

variable, s 3 is outgoing variable. In table 2 s 3 is replaced by x1

2nd table: Note: R1 = R1 − R3 R2 = R2 − R3

' '

Cj 2 1 0 0 0 Ratio=
CB B x1 x2 s1 s2 X a / p.c
Xa s3
0 s1 8 0 3 1 0 -1 8/3
0 s2 4 0 2 0 1 -1 2
2 x1 2 1 -1 0 0 1 -2
Zj 2 -2 0 0 2

Cj −Z j 0 3 0 0 -2
The arrow denotes the pivot column and row respectively. And 2 is the pivot element. Since
C j − Z j is positive under some columns 1st table is not optimal. In 1st table x 2 is incoming
variable, s1 is outgoing variable. In table 2 s1 is replaced by x 2

3rd table: Note: R2' = R2 / 2

Cj 2 1 0 0 0
CB B Xa x1 x2 s1 s2 s3
0 s1 8 0 3 1 0 -1
1 x2 2 0 1 0 1/2 -1/2
2 x1 2 1 -1 0 0 1
Zj 2 -2 0 0 2

Cj −Z j 0 3 0 0 -2

4th table: Note: R1' = R1 − 3R2

Cj 2 1 0 0 0

CB B Xa x1 x2 s1 s2 s3
0 s1 2 0 0 1 -3/2 1/2
1 x2 2 0 1 0 1/2 -1/2
2 x1 4 1 0 0 1/2 1/2
Zj 2 1 0 3/2 1/2
Cj −Z j 0 0 0 -3/2 -1/2

Since C j − Z j is either negative or zero under all columns, 4th table is optimal.

Thus, the optimal basic feasible solution is x1 = 4 , x2 = 2 , with Z max = 10

Problem-7: Use the Simplex method to solve the following LPP
Maximize Z = 4 x1 + 10x2

Subject to 2 x1 + x2  50

2 x1 + 5 x 2  100
2 x1 + 3 x 2  90
x1 , x 2  0
Solution: The given LPP
Maximize Z = 4 x1 + 10x2

Subject to 2 x1 + x2  50

2 x1 + 5 x 2  100
2 x1 + 3 x 2  90
x1 , x 2  0

Introducing slack variables in the given equation we get,

Max Z = 4 x1 + 10x2 + s1 .0 + s 2 .0 + s3 .0

Sub to 2 x1 + x2 + s1 = 50

2 x1 + 5 x 2 + s 2 = 100
2 x1 + 3 x 2 + s3 = 90
x1 , x 2 , s1 , s 2 , s 3  0

Now putting the decision variables x1 = x2 = 0

We get,
s1 = 50, s 2 = 100, s3 = 90 which are the initial values of slack variables.

Let us tabulate the system as follows:

Initial Table

Cj 4 10 0 0 0
CB B XB x1 x2 s1 s2 s3 Ratio

0 s1 50 2 1 1 0 0 50
0 s2 100 2 5 0 1 0 20
0 s3 90 2 3 0 0 1 45

Zj 0 0 0 0 0

Cj − Zj 4 10 0 0 0

Since 10 is the most positive element in C −z j j

, the pivot column is the column containing x 2

and the pivot row is the row containing the minimum ratio 20.
2nd Table:

Cj 4 10 0 0 0
CB B XB x1 x2 s1 s2 s3
0 s1 50 2 1 1 0 0
10 x2 20 2/5 1 0 1/5 0
0 s3 90 2 3 0 0 1

Zj 4 10 0 2

Cj − Zj 0 0 0 -2

3rd Table:

Cj 4 10 0 0 0
CB B XB x1 x2 s1 s2 s3
0 s1 30 8/5 0 1 -1/5 0

10 x2 20 2/5 1 0 1/5 0

0 s3 -30 -4/5 0 0 3/5 -1

Zj 4 10 0 2 0

Cj − Zj 0 0 0 -2 0

Since all C j − Z j is either zero or negative. Optimal solution has been reached

x1 = 0, x 2 = 20, Z max = 200

Problem-8: Use the Simplex method to solve the following LPP

Z = 2 x1 + x2

subject to, − x1 + 2 x2  2

x1 + x2  4

x1  3

x1 , x2  0
Solution: Introducing slack variable in the given inequalities.

Maximum Z = 2 x1 + x2 + s1.0 + s2 .0 + s3.0

subject to, − x1 + 2 x2 + s1 = 2

x1 + x2 + s2 = 4

x1 + s3 = 3

x1, x2 , s1, s2 , s3  0

Putting the decision variables x1 = x2 = 0 ,we get s1 = 2, s2 = 4, s3 = 3 which are the initial values of
slack variables.

cj 2 1 0 0 0
Ratio
cB Basic Basic x1 x2 s1 s2 s3
variable solution
(B ) (X B )
0 s1 2 −1 2 1 0 0 −2
0 s2 4 1 1 0 1 0 4
0 s3 3 1 0 0 0 1 3

zj 0 0 0 0 0

cj − zj 2 1 0 0 0
 cj 2 1 0 0 0
Ratio
cB B XB x1 x2 s1 s2 s3
0 s1 5 0 2 1 0 0 2.5
0 s2 1 0 1 0 1 −1 −1
2 x1 3 1 0 0 0 1 3
zj 2 0 0 0 2
cj − zj 0 1 0 0 −2

cj 2 1 0 0 0

cB B XB x1 x2 s1 s2 s3
1 x2 5 0 1 1 0 0
2 2
0 s2 1 0 1 0 1 −1
2 x1 3 1 0 0 0 1

cj 2 1 0 0 0
cB B XB x1 x2 s1 s2 s3
1 x2 5 0 1 1 0 0
2 2
0 s2 3 0 0 1 −1 1
2 2
2 x1 3 1 0 0 0 1
zj 2 1 1 0 2
2
cj − zj 0 0 −1
2
0 2

x1 = 3; x2 = 5
2

Maximum Z = 6 + 5
2

= 11 Ans.
2
 Dual Problem
Definition of Dual Problem:

When we solve a maximization or minimization problem, it relates to mirror image problem based
on the same data. Here the original problem is called Primal Problem and the image problem is
called Dual Problem.

Assumption:
 If the Primal Problem contains a large number of rows (constraints) and a smaller number
of variables, then we can solve it by converting it into dual.

 We can check the accuracy by converting Maximization to Minimization and Minimization

to Maximization and gives the complete information about the optimum solution.
Application:

 Problem:
Let us consider, a patient needs 12, 17, 2.5 and 6 units of vitamins C, D, E and K respectively. The
food F contains 1 unit of C and 2 units of D, 1 unit of E and 1 unit of K. The food G contains 1
unit of C and 1 unit of D. Find the minimum cost of buying the vitamins if the cost per unit of F
and G be 20 TK and 16 TK.

So, the problem describes in equation:

Minimize Z=20𝑥1 + 16𝑥2

Subject to 𝑥1 + 𝑥2 ≥ 12

2𝑥1 + 𝑥2 ≥ 17

𝑥1 ≥ 2.5

𝑥1 ≥ 6

𝑥1 , 𝑥2 ≥ 0

 A dealer sells the above-mentioned vitamin C, D, E and K if problem is to fix the cost and
the price of F and G foods do not exceed the amount mentioned above. His problem is also
to get a maximum profit in selling the vitamins.

Maximize 𝑃 = 12𝑢 + 17𝑣 + 2.5𝑤 + 6𝑡

Subject to 𝑢+2𝑣 + 𝑤 + 𝑡 ≤ 20

𝑢 + 𝑣 ≤ 16

𝑢, 𝑣, 𝑤 ≥ 0
Kinds of Dual Problem:
1. Symmetric:

All constraints of both (Primal and Dual) are inequalities and variables are non-negative.
[Link]:

All constraints are equations and all primal variables are non-negative but Dual variables may be
unrestricted.
3. Mixed Type:

Some constraints are equations or inequalities for Primal problem and some variables are
unrestricted or non-negative.
Formulation:

 Each and every unsymmetric and mixed type problem convert into symmetric type problem
by proper adjustment.

 For maximization problem, write all constraints involve the sign ≤ with all variables non-
negative in Primal Problem. It will be ≥ in Dual problem.

 To find the pivot column, we have to find the most positive value in the last row in Simplex
Method.
The iteration will be finished if we get all values in the last row are negative or zeros

 For minimization problem, write all constraints involve the sign ≥ with all variables non-
negative in primal problem. It will be ≤ in Dual Problem.

 To find the pivot column, we have to find the most negative value in the last row.
The iteration will be finished if we get all values in the last row are positive or zeros.

Fundamental Theorem or Strong Duality Theorem:

A Primal Problem has a solution if and only if the corresponding Dual Problem has a solution

Fundamental Theorem or Strong Duality Theorem:

A Primal Problem has a solution if and only if the corresponding Dual Problem has a solution.
Theorem: If either of the primal or dual has unbounded solution, then the other will have no
feasible solution.
Theorem 1. State and prove that the main duality theorem or fundamental theorem of duality.
Statement: If both the primal and the dual problems have feasible solutions, the both have
optimal solutions and Max. Z = min. W

Proof: When both the primal and the dual problems have feasible solutions, then there is a lower
bound on the minimum value of W as well as an upper bound on the maximum value of Z .In
other words , neither the primal nor the dual have an unbounded solution. Therefore, both must
have optimal solutions.
The symmetric primal dual programmed in matrix-vector notation are
Primal

Maximize Z = cx

Subject to Ax  b

x0
Dual
Minimize W = yb

Subject to yA  c

y0

Let the finite optimal solution to the primal be

xB = B −1b
And the corresponding optimal value of the primal objective function be
Z = cB xB

= cB ( B −1b)
The corresponding conditions for optimality are

Z j 
−cj  0

Or c B
B
−1

A − c, c B B −1  0

Or cB B −1 A − c  0, cB B −1  0
Now to verify that the associated optimal dual solution is y B = c B B −1 , only observed that the above
relation then demonstrates that the feasibility conditions for the dual problem are satisfied.

The corresponding value of the dual objective function is given by

W = yb = (cB B −1 )b = cB ( B −1b) = cB xB = max .Z .

Now it only remains to be shown that W is also the optimal value of the dual objective function.
Now, for all feasible x j and y j , Z  W which will also be true for extreme optimal and dual
values. i.e, max .Z  min.W

Or W  min .W

But W cannot be less than min .W

max .Z  min.W

Theorem 2: State and prove the complementary slackness theorem in linear programming.

Statement: Let x0 and y 0 Be the feasible solutions to the primal problem (p)
Maximize Z = c T x

Subject to Ax  b

x0
And its dual problem (D)

Minimize W = bT y
Subject to AT y  c

y0

Then necessary and sufficient conditions for x0 and y 0 to be optimal to their respective
problem is that

Proof:
Necessary conditions:

Let
 = y T
0 (b − Ax 0 ) and
 = x0
T
( AT
y0 − c)
Since x0 and y 0 Be the feasible solutions to the primal and its dual respectively, we have

  0 , 0

And  +  = y0T (b − Ax0 ) + x0T ( AT y0 − c)

= y0T b − y0T Ax 0 + x0T AT y0 − x0T c


= y 0T b − x0T c  y0T Ax0 = x0T AT y0 
Now if x 0 and y 0 are optimal, Then

c T x0 = bT y0 , so that  + =0

But since   0 and   0 , this gives  = 0  = 0

y 0T (b − Ax 0 ) = 0 x T
( AT
y0 − c) = 0
i.e. and 0

Thus, the conditions are necessary.

Sufficient condition:

Let the given condition hold for the feasible solutions x 0 and y 0

That is
 = y0T (b − Ax0 ) = 0 and  = x0T ( AT y0 − c) = 0

0 =  +  = y 0T b − x0T c  y 0T b = x0T c  c T x0 = bT y0

Since c x0 = b y0 , hence the solutions x 0 and y 0 are optimal.

T T

Problem 1: Maximization 𝑍 = 3𝑥 + 2𝑦

Subject to −𝑥 + 2𝑦 ≤ 4

3𝑥 + 2𝑦 ≤ 14

𝑥 − 𝑦 ≤ 13

𝑥, 𝑦 ≥ 0
At first, we draw a table for primal problem,

x y constant
-1 2 4
3 2 14
1 -1 13
3 2 0

Now we interchange the columns and rows and head the three columns,

u v W Constant
-1 3 1 3
2 2 -1 2
4 14 13 0

So, the dual problem for minimization,

𝑝 = 4𝑢 + 14𝑣 + 13𝑤

Subject to −𝑢 + 3𝑣 + 𝑤 ≥ 3

2𝑢 + 2𝑣 − 𝑤 ≥ 2
We can write in maximization by changing sign,

𝑢 − 3𝑣 − 𝑤 ≤ −3

−2𝑢 − 2𝑣 + 𝑤 ≤ −2
By slackness condition:

𝑝 − 4𝑢 − 14𝑣 − 13𝑤 = 0

Subject to 𝑢 − 3𝑣 − 𝑤 + 𝑥 = 0

−2𝑢 − 2𝑣 + 𝑤 + 𝑦 = 0

Associated with dual problem

u v w X Y p constant Min Ratio

-1 -3 -1 1 0 0 -3 1
-2 -2 1 0 1 0 -2 1
-4 -14 -13 0 0 1 0
 Table 2

u v w X Y p constant
1 1 1 1 0 0 1
−3 3 −3
8 0 5 2 1 0 0
− −
3 3 3
26 0 25 14 0 1 14
− − −
3 3 3
The optimal solution of the dual minimization problem is 𝑍𝑚𝑖𝑛 = 14
14
where x=− ,𝑦=0
3

−14
Now 𝑍𝑚𝑎𝑥 = 3 × + 0 = −14
3

Problem 2: Solve the linear programming problem

Maximization, 𝑍 = 4𝑥 + 3𝑦

Subject to, 𝑥 ≤ 6

𝑦≤8

𝑥+𝑦 ≤7

3𝑥 + 𝑦 ≤ 15

−𝑦 ≤ 1

𝑥, 𝑦 ≥ 0by using duality theory.

Solution: Given,

Maximization, 𝑍 = 4𝑥 + 3𝑦

Subject to, 𝑥 ≤ 6

𝑦≤8

𝑥+𝑦 ≤7

3𝑥 + 𝑦 ≤ 15

−𝑦 ≤ 1

𝑥, 𝑦 ≥ 0
At first, we draw a table for primal problem,
 x y constant
1 0 6
0 1 8
1 1 7
3 1 15
0 -1 1
4 3

Now we interchange the columns and rows and head the three columns,

u v W q R constant
1 3 1 3 0 4
0 2 1 1 -1 3
6 8 7 15 0
So, the dual problem for minimization,

𝑝 = 6𝑢 + 8𝑣 + 7𝑤 + 15𝑞 + 0. 𝑟

Subject to 𝑢 + 0. 𝑣 + 𝑤 + 3𝑞0. 𝑟 ≥ 4

0. 𝑢 + 𝑣 + 𝑤 + 𝑞 − 𝑟 ≥ 3

𝑢, 𝑣, 𝑤, 𝑞, 𝑟 ≥ 0

By surplus condition:

Maximization Z= −6𝑢 − 8𝑣 − 7𝑤 − 15𝑞 − 𝑟

Subject to 𝑢 − 0. 𝑣 + 𝑤 + 3𝑞 + 0. 𝑟 − 𝑥 + 0. 𝑦 = 4

0. 𝑢 + 𝑣 + 𝑤 + 𝑞 − 𝑟 + 0. 𝑥 − 𝑦 = 3
𝑢, 𝑣, 𝑤, 𝑞, 𝑟, 𝑥, 𝑦 ≥ 0

Initial Table

Cj -6 -8 -7 -15 -1 0 0 Min
Ratio
CB B XB u V w Q r x y
-6 u 4 1 0 1 3 0 -1 0 4
3
-8 v 3 0 1 1 1 -1 0 -1 3
Zj -6 -8 -14 -26 8 6 8 𝑍𝑚𝑎𝑥
= −48
Zj −Cj 0 0 -7 -11 9 6 8
 Table 2

Cj -6 -8 -7 -15 -1 0 0 Min
Ratio
CB B XB u V w q r x y
-15 u 4 1 0 1 1 0 1 0 4
−
3 3 3 3
-8 v 5 1 1 2 0 -1 1 -1 5
−
3 3 3 3 2
Zj -5 -8 -14 -26 8 6 8 𝑍𝑚𝑎𝑥
100
Zj −Cj 11 0
−
10 0 9 7 8 =−
3
3 3 3

Cj -6 -8 -7 -15 -1 0 0
CB B XB u V W q r x y
-15 u 1 1 1 0 1 1 1 1
− −
2 2 2 2 2 2 2
-7 v 5 1 3 1 3
-2 3 1 −3
− −
2 2 2 2 2 2
Zj -4 -3 -7 -15 3 4 3 𝑍𝑚𝑎𝑥
Zj −Cj 2 5 0 0 4 4 3 = −25

Members reached
1 5
Here = 2 𝑎𝑛𝑑 𝑣 = 2 , 𝑍𝑚𝑖𝑛 = 25 which is the optimal solution.

Problem 3: Solve the linear programming problem

Maximization, 𝑍 = 5𝑥 + 4𝑦

Subject to, 3𝑥 + 4𝑦 ≤ 24

3𝑥 + 2𝑦 ≤ 18

𝑦≤5

𝑥, 𝑦 ≥ 0by using duality theory.

Solution: Given,

Maximization, 𝑍 = 5𝑥 + 4𝑦
Subject to, 3𝑥 + 4𝑦 ≤ 24

3𝑥 + 2𝑦 ≤ 18

𝑦≤5

𝑥, 𝑦 ≥ 0

At first, we draw a table for primal problem,

x y constant
3 4 24
3 2 18
0 1 5
5 4

Now we interchange the columns and rows and head the three columns,

u v W constant
3 3 0 5
4 2 1 4
24 18 5 0

So, the dual problem for minimization,

𝑝 = 24𝑢 + 18𝑣 + 5𝑤

Subject to 3𝑢 + 3𝑣 + 0. 𝑤 ≥ 5

4𝑢 + 2𝑣 + 𝑤 ≥ 4

𝑢, 𝑣, 𝑤 ≥ 0

By surplus condition, we get,

Minimization Z= 24𝑢 + 18𝑣 + 5𝑤 − 0. 𝑥 − 0. 𝑦

Subject to 3𝑢 + 3𝑣 + 0. 𝑤 − 𝑥 + 0. 𝑦 = 5

4𝑢 + 2𝑣 + 𝑤 + 0. 𝑥 − 𝑦 = 4

𝑢, 𝑣, 𝑤, 𝑥, 𝑦 ≥ 0
Initial Table

Cj -24 -18 0 0 Min

B u V w x y Ratio
CB XB
0 x 5 3 3 0 -1 0 5
=0
0
0 Y 4 4 2 1 0 -1 4
Zj 0 0 0 0 0 Z=0
Zj −Cj 24 18 5 0 0
Table-2

Cj -24 -18 -5 0 0 Min

B u v w x y Ratio
CB XB
0 u 5 3 3 0 −1 0 5
3
-5 v 4 4 2 1 0 -1 1
Zj -20 -10 -5 0 5 𝑍𝑚𝑎𝑥
Zj −Cj 4 8 0 0 5 = −20

Table-3

Cj -24 -18 -5 0 0
CB B XB u V w x y
-24 u 5 1 1 0 1 0
−
3 3
-5 w 8 0 -2 1 4 -1
−
3 3
Zj -24 -14 -14 -5 5 𝑍𝑚𝑎𝑥
80
Zj −Cj 0 4 4 0 5 =
3
5 8 80
Here = 3 , 𝑣 = 0, 𝑤 = − 3 , 𝑍𝑚𝑖𝑛 = which is the optimal solution.
3

Problem-4: Use the Dual Simplex method to solve the following Linear Programming
Problem.

minimize 𝑧 = 2𝑥1 + 9𝑥2 + 𝑥3

Subject to 𝑥1 + 4𝑥2 + 2𝑥3 ≥ 5

3𝑥1 + 𝑥2 + 2𝑥3 ≥ 4
 𝑥1 , 𝑥2 , 𝑥3 ≥ 0

Solution:
The primal problem is,

minimize 𝑧 = 2𝑥1 + 9𝑥2 + 𝑥3

Subject to 𝑥1 + 4𝑥2 + 2𝑥3 ≥ 5

3𝑥1 + 𝑥2 + 2𝑥3 ≥ 4

𝑥1 , 𝑥2 , 𝑥3 ≥ 0

The table for the primal problem is,

𝒙𝟏 𝒙𝟐 𝒙𝟑 Constant
1 4 2 5
3 1 2 4
2 9 1
Now interchanging the row into column we get,

𝒖 𝒗 Constant
1 3 2
4 1 9
2 2 1
5 4
Now our dual problem ismaximize 𝑝 = 5𝑢 + 4𝑣

Subject to 𝑢 + 3𝑣 ≤ 2

4𝑢 + 𝑣 ≤ 9

2𝑢 + 2𝑣 ≤ 1

𝑢, 𝑣 ≥ 0

Introducing slack variables in the dual problem, we get

maximize 𝑝 = 5𝑢 + 4𝑣 + 𝑥1 . 0 + 𝑥2 . 0 + 𝑥3 . 0

Subject to 𝑢 + 3𝑣 + 𝑥1 = 2

4𝑢 + 𝑣 + 𝑥2 = 9

2𝑢 + 2𝑣 + 𝑥3 = 1

𝑢, 𝑣, 𝑥1 , 𝑥2 , 𝑥3 ≥ 0
Hence the system of linear equation is

𝑢 + 3𝑣 + 𝑥1 + 𝑥2 . 0 + 𝑥3 . 0 = 2

4𝑢 + 𝑣 + 𝑥1 . 0 + 𝑥2 + 𝑥3 . 0 = 9

2𝑢 + 2𝑣 + 𝑥1 . 0 + 𝑥2 . 0 + 𝑥3 = 1

−5𝑢 − 4𝑣 + 𝑥1 . 0 + 𝑥2 . 0 + 𝑥3 . 0 + 𝑝 = 0
Now we will solve the system by simplex method

Initial Table:

𝒖 𝒗 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒑 Constant Ratio
1 3 1 0 0 0 2 2
4 1 0 1 0 0 9 2.25
2 2 0 0 1 0 1 .5
-5 -4 0 0 0 1 0

𝒖 𝒗 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒑 Constant
0 2 1 0 -1/2 0 3/2
0 -3 0 1 -2 0 7
1 1 0 0 ½ 0 ½
0 1 0 0 5/2 1 5/2

Since it is a maximization problem and there is no –ve term left, optimal solution has been reached.

Here, 𝑥1 = 0, 𝑥2 = 0, 𝑥3 = 5/2

Hence, maximize 𝑝 = 5/2

Problem5:

Use the Dual Simplex method to solve the following Linear Programming Problem.

minimize 𝑧 = 2𝑥1 + 2𝑥2 + 4𝑥3

Subject to 2𝑥1 + 3𝑥2 + 5𝑥3 ≥ 2

3𝑥1 + 𝑥2 + 7𝑥3 ≤ 3

𝑥1 + 4𝑥2 + 6𝑥3 ≤ 5

𝑥1 , 𝑥2 , 𝑥3 ≥ 0
Solution:
The primal problem is,

minimize 𝑧 = 2𝑥1 + 2𝑥2 + 4𝑥3

Subject to 2𝑥1 + 3𝑥2 + 5𝑥3 ≥ 2

−3𝑥1 − 𝑥2 − 7𝑥3 ≥ −3

−𝑥1 − 4𝑥2 − 6𝑥3 ≥ −5

𝑥1 , 𝑥2 , 𝑥3 ≥ 0

The table for the primal problem is

𝒙𝟏 𝒙𝟐 𝒙𝟑 Constant
2 3 5 2
-3 -1 -7 -3
-1 -4 -6 -5
2 2 4

Interchanging the row into column, we get

u v w Constant
2 -3 -1 2
3 -1 -4 2
5 -7 -6 4
2 -3 -5

Now our dual problem is

Maximize𝑝 = 2𝑢 − 3𝑣 − 5𝑤

Subject to 2𝑢 − 3𝑣 − 𝑤 ≤ 2

3𝑢 − 𝑣 − 4𝑤 ≤ 2

5𝑢 − 7𝑣 − 6𝑤 ≤ 4

u, v, w ≥ 0

Now introducing slack variable in dual problem

Maximize p= 2u-3v-5w+0.x1 + 0. x2 + 0. x3

Subject to 2u-3v-w+x1 =2
 3u-v-4w+x2 =2

5u-7v-6w+x3 =2

𝑢, 𝑣, 𝑤, 𝑥1 , 𝑥2 , 𝑥3 ≥ 0

Hence the system of linear equation is

2𝑢 − 3𝑣 − 𝑤 + 𝑥1 + 𝑥2 . 0 + 𝑥3 . 0 = 2

3𝑢 − 𝑣 − 4𝑤 + 𝑥1 . 0 + 𝑥2 + 𝑥3 . 0 = 2

5𝑢 − 7𝑣 − 6𝑤 + 𝑥1 . 0 + 𝑥2 . 0 + 𝑥3 = 4

−2𝑢 + 3𝑣 + 5𝑤 + 𝑥1 . 0 + 𝑥2 . 0 + 𝑥3 . 0 + 𝑝 = 0

Now we will solve the system by simplex method.

Initial Table:

𝒖 𝒗 𝒘 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒑 Constant Ratio
2 -3 -1 1 0 0 0 2 1
3 -1 -4 0 1 0 0 2 .6
5 -7 -6 0 0 1 0 4 .8
-2 3 5 0 0 0 1

2nd Table:

𝒖 𝒗 𝒘 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒑 Constant
2 -3 -1 1 0 0 0 2
1 -1/3 -4/3 0 1/3 0 0 2/3
5 -7 -6 0 0 1 0 4
-2 3 5 0 0 0 1

3rd Table:

𝒖 𝒗 𝒘 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒑 Constant
0 -7/3 5/3 1 0 0 0 2/3
1 -1/3 -4/3 0 1/3 0 0 2/3
0 16/3 -2/3 0 5/3 -1 0 -2/3
0 7/3 7/3 0 2/3 0 1 4/3

Since it is a maximization problem and there is no –ve term left, optimal solution has been reached.
Thus, x1 = 0, x2 = 2/3, x3 = 0
Hence, maximize p = 4/3

Problem6:

Use the Dual Simplex method to solve the following Linear Programming Problem.

minimize 𝑐 = 6𝑥 + 8𝑦

Subject to 40𝑥 + 10𝑦 ≥ 2400

10𝑥 + 15𝑦 ≥ 2100

5𝑥 + 15𝑦 ≥ 1500

𝑥, 𝑦 ≥ 0

𝒙 𝒚 Constant
40 10 2400
10 15 2100
5 15 1500
6 8

Interchanging the row into column, we get

𝒖 𝒗 𝒘 Constant
40 10 5 6
10 15 15 8
2400 2100 1500

Hence our dual problem is

max. 𝑝 = 2400𝑢 + 2100𝑣 + 1500𝑤

Subject to 40𝑢 + 10𝑣 + 5𝑤 ≤ 6

10𝑢 + 15𝑣 + 15𝑤 ≤ 8

𝑢, 𝑣, 𝑤 ≥ 0

Now introducing slack variable in dual problem

Maximize p= 2400u+2100v+1500w+0.𝑥 + 0. 𝑦

Subject to 40𝑢 + 10𝑣 + 5𝑤 + 𝑥 = 6

 10𝑢 + 15𝑣 + 15𝑤 + 𝑦 = 8

𝑢, 𝑣, 𝑤, 𝑥, 𝑦 ≥ 0
Hence the system of linear equation is

40𝑢 + 10𝑣 + 5𝑤 + 𝑥 = 6

10𝑢 + 15𝑣 + 15𝑤 + 𝑦 = 8

- 2400u-2100v-1500w+0.𝑥 + 0. 𝑦 + 𝑝 = 0

Now we will solve the system by simplex method.

Initial Table:

𝒖 𝒗 𝒘 𝒙 𝒚 𝒑 Constant Ratio
40 10 5 1 0 0 6 .15
10 15 15 0 1 0 8 .8
-2400 -2100 -1500 0 0 1 0 0

2nd Table:

𝒖 𝒗 𝒘 𝒙 𝒚 𝒑 Constant
1 ¼ 1/8 1/40 0 0 3/20
10 15 15 0 1 0 8
-2400 -2100 -1500 0 0 1 0

3rd Table:

𝒖 𝒗 𝒘 𝒙 𝒚 𝒑 Constant Ratio
1 ¼ 1/8 1/40 0 0 3/20 .6
0 25/2 55/4 -1/4 1 0 13/25 .04
0 -1500 -1200 60 0 1 360 0

4th Table:

𝒖 𝒗 𝒘 𝒙 𝒚 𝒑 Constant
1 1/4 1/8 1/40 0 0 3/20
0 1 11/10 -1/50 2/25 0 13/25
0 -1500 -1200 60 0 1 360
5th Table:

𝒖 𝒗 𝒘 𝒙 𝒚 𝒑 Constant
1 0 -3/20 3/100 -1/50 0 1/50
0 1 11/10 -1/50 2/25 0 13/25
0 0 450 30 120 1 1140

Since it is a maximization problem and there is no –ve term left, optimal solution has been reached.

Hence x=30, y=120, max. p=1140.