Courses

Linear Programming Problems (LPP) via Simplex Method, Business Mathematics and Statistics B Com Notes | EduRev

B Com : Linear Programming Problems (LPP) via Simplex Method, Business Mathematics and Statistics B Com Notes | EduRev

The document Linear Programming Problems (LPP) via Simplex Method, Business Mathematics and Statistics B Com Notes | EduRev is a part of the B Com Course Business Mathematics and Statistics.
All you need of B Com at this link: B Com

PREVIEW OF THE SIMPLEX METHOD

Before the simplex algorithm can be used to solve any linear programming problem (LPP), it must be converted into an equivalent standard form of LPP in which all the constraints are equations and all the following variables are non-negative.:

max(min)z = c1x+ c2x2 + ˇˇˇ + cnxn

a11x1 + a12x2 + ˇˇˇ + a1nxn = b1

...

am1x+ am2x2 + ˇˇˇ + amnxn = bm

xi ≥ 0, i = 1,...,n

The system equations(constraints) can be written much more concisely in matrix form as follows: Ax = b, x ≥ 0. We assume, that the rank of matrix A equals m.

Any LPP can be converted into this standard form as follows:

1. We convert a (≤) constraint ai1x1 + ai2x+ ˇˇˇ + ainxn ≤ binto an equality constraint by adding a slack variable si to the left-hand side of the constraint and adding the sign restriction si ≥ 0: ai1x1 + ai2x2 + ˇˇˇ + ainx+ s= bi, s≥ 0.

2. We convert (≥) constraint ai1x1 + ai2x2 + ˇˇˇ + ainxn ≥ bi into an equality constraint by subtracting a surplus variable si from the left-hand side of the constraint and adding the sign restriction s≥ 0: ai1x1 +ai2x2 +ˇˇˇ+ainxn − si = bi, s≥ 0.

3. (Dealing with unrestricted variables) If variable xi can take both negative and nonnegative values, we use the substitution: x= u− vi and add two non-negativity constraints u≥ 0, vi ≥ 0.

Example. Convert the following linear programming problem into the standard form:

max z = 2x1 + 3x2 − x3

x− 2x2 ≤ 5

x+ 3x3 ≥ 3

x+ x2 − 2x3 = 20

x1,x2 ≥ 0

After converting constraints 1 and 2, we obtain:

max z = 2x1 + 3x2 − x3

x1 − 2x2 + s1 = 5

x2 + 3x3 − s2 = 3

x1 + x2 − 2x3 = 20

x1,x2,s1,s2 ≥ 0

Next, we make the substitution x3 = u3 − v3 and obtain the standard form of the problem:

max z = 2x1 + 3x2 − u3 + v3

x1 − 2x2 + s1 = 5

x2 + 3u3 + 3v3 − s2 = 3

x1 + x2 − 2u3 + 2v3 = 20

x1,x2,s1,s2,u3,v3 ≥ 0

Converting from the graphical to the algebraic method

Graphical Method:

1. Graph all the constraints, including the nonnegativity restrictions - Suppose the solution space consists of infinite number of feasible solutions.

2. Identify feasible corner points (extreme points) of the solution space - Candidates for the optimal solution are given by a finite number of corner points.

3. Use the objective function to determine the optimal corner point from among all the candidates.

Algebraic Method:

1. Represent the solution space by m equations in n variables and restrict all the variables to nonnegative values, suppose m ≤ n and the system has infinite number of feasible solutions.

2. Determine a feasible basic solution of the equations - Candidates for the optimal solution are given by a finite number of basic feasible solutions.

3. Use the objective function to determine the optimum basic feasible solution from among all the candidates.

Definition 1. Consider the set of equations Ax = b, if we set n − m variables to zero and then solve the m equations for the remaining m variables, the resulting solution, if unique, is called a basic solution and must correspond to a (feasible or infeasible) corner point (extreme point) of the solution space. The n − m variables set to zero are known as nonbasic variables (NBV) and the remaining m variables are called basic variables(BV).

Remark The set of columns of the matrix A that corresponds to the basic

variables is a linearly independent set of vectors. This set is called a basis and will

PREVIEW OF THE SIMPLEX METHOD

be denoted by B.

Example. Find a few basic solutions to the following system of two equations with four variables:

x+ x2 + 2x4 = 3

2x− x2 − x3 + 4x4 = 1

We begin by choosing BV = {x1,x2} to be basic variables and NBV = {x3,x4} to be nonbasic variables. Setting x= x4 = 0, we obtain the following linear system:

x1 + x2 = 3

2x1 − x2 = 1

These equations lead to the unique (feasible) basic solution: x1 = 4

3 , x2 = 12            3 ,

x3 = 0, x4 = 0.

Next we choose BV = {x2,x3} as our basic variables and set the nonbasic variables NBV = {x1,x4} equal to zero, i.e. x= x4 = 0. We have the following system:

x2 = 3

−x− x3 = 1

Solving the above system we obtain the (unfeasible) basic solution : x= 0, x2 = 3,

x3 = −4, x4 = 0. If we choose BV = {x1,x4} and NBV = {x2,x3}, we obtain the following system of linear equations:

x1 + 2x4 = 3

2x1 + 4x= 1

This system is inconsistent so the variables x1,x4 cannot simultaneously be basic variables!

Definition 2. For any linear programming problem with m constraints, two basic feasible solutions are called adjacent if their sets of basic variables have m−1 basic

variables in common.

For example, the following two basic solutions from the above example X1 = (x= 4

3 ,x2 = 5

3 ,x= 0,x4 = 0) (feasible basic solution - FBS) and X2 = (x1 = 0,x2 = 3,x3 = −4,x4 = 0) (infeasible basic solution - IBS) are adjacent.

Definition 3. Any basic solution to Ax = b in which all the variables are non-negative is a feasible basic solution(FBS).

Property 1. For any LPP there is a unique extreme point(corner point) of the feasible region corresponding to each basic feasible solution. Also, there is at least one FBS corresponding to each extreme point of the feasible region.

Theorem 1. The feasible region of any LPP is a convex set. Also, if the LPP has an optimal solution, there must be an extreme point of the feasible region that is

optimal.

From the above facts, we see that in searching for an optimal solution to an LPP we need only find the best basic feasible solution(largest Z - value in a max problem or smallest Z - value in a min problem) to Ax = b.

Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Business Mathematics and Statistics

122 videos|142 docs

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;