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 = c_{1}x_{1 }+ c_{2}x_{2} + ˇˇˇ + cnxn

a_{11}x_{1} + a_{12}x_{2} + ˇˇˇ + a_{1}nxn = b_{1}

...

am_{1}x_{1 }+ am_{2}x_{2} + ˇˇˇ + amnxn = bm

x_{i} ≥ 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 a_{i1}x_{1} + a_{i2}x_{2 }+ ˇˇˇ + a_{in}x_{n} ≤ b_{i }into an equality constraint by adding a slack variable si to the left-hand side of the constraint and adding the sign restriction s_{i} ≥ 0: a_{i1}x_{1} + a_{i2}x_{2} + ˇˇˇ + a_{in}x_{n }+ s_{i }= b_{i}, s_{i }≥ 0.

2. We convert (≥) constraint a_{i1}x_{1} + a_{i2}x_{2} + ˇˇˇ + a_{in}x_{n} ≥ b_{i} into an equality constraint by subtracting a surplus variable si from the left-hand side of the constraint and adding the sign restriction s_{i }≥ 0: a_{i1}x_{1} +a_{i2}x_{2} +ˇˇˇ+a_{in}x_{n} − s_{i} = b_{i}, s_{i }≥ 0.

3. (Dealing with unrestricted variables) If variable xi can take both negative and nonnegative values, we use the substitution: x_{i }= u_{i }− v_{i} and add two non-negativity constraints u_{i }≥ 0, v_{i} ≥ 0.

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

max z = 2x_{1} + 3x_{2} − x_{3}

x_{1 }− 2x_{2} ≤ 5

x_{2 }+ 3x_{3} ≥ 3

x_{1 }+ x_{2} − 2x_{3} = 20

x_{1},x_{2} ≥ 0

After converting constraints 1 and 2, we obtain:

max z = 2x_{1} + 3x_{2} − x_{3}

x_{1} − 2x_{2} + s_{1} = 5

x_{2} + 3x_{3} − s_{2} = 3

x_{1} + x_{2} − 2x_{3} = 20

x_{1},x_{2},s_{1},s_{2} ≥ 0

Next, we make the substitution x_{3} = u_{3} − v_{3} and obtain the standard form of the problem:

max z = 2x_{1} + 3x_{2} − u_{3} + v_{3}

x_{1} − 2x_{2} + s_{1} = 5

x_{2} + 3u_{3} + 3v_{3} − s_{2} = 3

x_{1} + x_{2} − 2u_{3} + 2v_{3} = 20

x_{1},x_{2},s_{1},s_{2},u_{3},v_{3} ≥ 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_{1 }+ x_{2} + 2x_{4} = 3

2x_{1 }− x_{2} − x_{3} + 4x_{4} = 1

We begin by choosing BV = {x_{1},x_{2}} to be basic variables and NBV = {x_{3},x_{4}} to be nonbasic variables. Setting x_{3 }= x_{4} = 0, we obtain the following linear system:

x_{1} + x_{2} = 3

2x_{1} − x_{2} = 1

These equations lead to the unique (feasible) basic solution: x_{1} = 4

3 , x_{2} = 12 3 ,

x_{3} = 0, x_{4} = 0.

Next we choose BV = {x_{2},x_{3}} as our basic variables and set the nonbasic variables NBV = {x_{1},x_{4}} equal to zero, i.e. x_{1 }= x_{4} = 0. We have the following system:

x_{2} = 3

−x_{2 }− x_{3} = 1

Solving the above system we obtain the (unfeasible) basic solution : x_{1 }= 0, x_{2} = 3,

x_{3} = −4, x_{4} = 0. If we choose BV = {x_{1},x_{4}} and NBV = {x_{2},x_{3}}, we obtain the following system of linear equations:

x_{1} + 2x_{4} = 3

2x_{1} + 4x_{4 }= 1

This system is inconsistent so the variables x_{1},x_{4} 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 X_{1} = (x_{1 }= 4

3 ,x_{2} = 5

3 ,x_{3 }= 0,x_{4} = 0) (feasible basic solution - FBS) and X_{2} = (x_{1} = 0,x_{2} = 3,x_{3} = −4,x_{4} = 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!

122 videos|142 docs

- Transportation Problems - Elements of Operation research, Business Mathematics and Statistics
- Transportation Problems - Elements of Operation research, Business Mathematics and Statistics
- Vogel’s Approximation Method (VAM) - Business Mathematics and Statistics
- Vogel’s Approximation Method (VAM) - Business Mathematics and Statistics
- PPT - Elements of Operation research