Lecture_5_Introduction to simplex method

5.1 Introduction

General Linear Programming Problem (GLPP)
Maximize / Minimize Z = c1x1 + c2x2 + c3x3 +……………..+ cnxn Subject to constraints
a11x1 + a12x2 + …..........+a1nxn (? or ?) b1
a21x1 + a22x2 + ………..+a2nxn (? or ?) b2
.
.
.
am1x1 + am2x2 + ……….+amnxn (? or ?) bm

and


x1 ? 0, x2 ? 0,…, xn ? 0


Where constraints may be in the form of any inequality (? or ?) or even in the form of an
equation (=) and finally satisfy the non-negativity restrictions.



5.2 Steps to convert GLPP to SLPP (Standard LPP)

Step 1 – Write the objective function in the maximization form. If the given objective function is of minimization form then multiply throughout by -1 and write Max z? = Min (-z)

Step 2 – Convert all inequalities as equations.
o If an equality of ‘?’ appears then by adding a variable called Slack variable. We can convert it to an equation. For example x1 +2x2 ? 12, we can write as
x1 +2x2 + s1 = 12.
o If the constraint is of ‘?’ type, we subtract a variable called Surplus variable and convert it to an equation. For example
2x1 +x2 ? 15
2x1 +x2 – s2 = 15
Step 3 – The right side element of each constraint should be made non-negative 2x1 +x2 – s2 = -15
-2x1 - x2 + s2 = 15 (That is multiplying throughout by -1)
Step 4 – All variables must have non-negative values.
For example: x1 +x2 ? 3
x1 > 0, x2 is unrestricted in sign
Then x2 is written as x2 = x2? – x2?? where x2?, x2?? ? 0
Therefore the inequality takes the form of equation as x1 + (x2? – x2??) + s1 = 3 Using the above steps, we can write the GLPP in the form of SLPP.
1





Write the Standard LPP (SLPP) of the following

Example 1
Maximize Z = 3x1 + x2 Subject to
2 x1 + x2 ? 2
3 x1 + 4 x2 ? 12
and x1 ? 0, x2 ? 0

SLPP
Maximize Z = 3x1 + x2 Subject to
2 x1 + x2 + s1 = 2
3 x1 + 4 x2 – s2 = 12
x1 ? 0, x2 ? 0, s1 ? 0, s2 ? 0


Example 2
Minimize Z = 4x1 + 2 x2 Subject to
3x1 + x2 ? 2 x1 + x2 ? 21 x1 + 2x2 ? 30
and x1 ? 0, x2 ? 0

SLPP
Maximize Z? = – 4x1 – 2 x2 Subject to
3x1 + x2 – s1 = 2 x1 + x2 – s2 = 21 x1 + 2x2 – s3 = 30
x1 ? 0, x2 ? 0, s1 ? 0, s2 ? 0, s3 ? 0

Example 3
Minimize Z = x1 + 2 x2 + 3x3 Subject to


2x1 + 3x2 + 3x3 ? – 4
3x1 + 5x2 + 2x3 ? 7
and x1 ? 0, x2 ? 0, x3 is unrestricted in sign


SLPP



?? ?

Maximize Z? = – x1 – 2 x2 – 3(x3 – x3 ) Subject to
–2x1 – 3x2 – 3(x3? – x3??) + s1= 4 3x1 + 5x2 + 2(x3? – x3??) + s2 = 7
??

x1 ? 0, x2 ? 0, x3? ? 0, x3

? 0, s1 ? 0, s2 ? 0






2





5.3 Some Basic Definitions

Solution of LPP
Any set of variable (x1, x2… xn) which satisfies the given constraint is called solution of LPP.

Basic solution
Is a solution obtained by setting any ‘n’ variable equal to zero and solving remaining ‘m’ variables. Such ‘m’ variables are called Basic variables and ‘n’ variables are called Non-basic variables.

Basic feasible solution
A basic solution that is feasible (all basic variables are non negative) is called basic feasible solution. There are two types of basic feasible solution.
1. Degenerate basic feasible solution
If any of the basic variable of a basic feasible solution is zero than it is said to be degenerate basic feasible solution.
2. Non-degenerate basic feasible solution
It is a basic feasible solution which has exactly ‘m’ positive xi, where i=1, 2, … m. In other words all ‘m’ basic variables are positive and remaining ‘n’ variables are zero.

Optimum basic feasible solution
A basic feasible solution is said to be optimum if it optimizes (max / min) the objective function.



5.4 Introduction to Simplex Method

It was developed by G. Danztig in 1947. The simplex method provides an algorithm (a rule of procedure usually involving repetitive application of a prescribed operation) which is based on the fundamental theorem of linear programming.

The Simplex algorithm is an iterative procedure for solving LP problems in a finite number of steps. It consists of
• Having a trial basic feasible solution to constraint-equations
• Testing whether it is an optimal solution

• Improving the first trial solution by a set of rules and repeating the process till an optimal solution is obtained

Advantages
• Simple to solve the problems
• The solution of LPP of more than two variables can be obtained.