Linear Programming Problems (LPP) via Simplex Method, Business Mathematics and Statistics | Business Mathematics and Statistics - B Com PDF Download

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₁x₁ + c₂x₂ + ˇˇˇ + cnxn

a₁₁x₁ + a₁₂x₂ + ˇˇˇ + a₁nxn = b₁

...

am₁x₁ + am₂x₂ + ˇˇˇ + 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_i1x₁ + a_i2x₂ + ˇˇˇ + a_inx_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_i1x₁ + a_i2x₂ + ˇˇˇ + a_inx_n + s_i = b_i, s_i ≥ 0.

2. We convert (≥) constraint a_i1x₁ + a_i2x₂ + ˇˇˇ + a_inx_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_i1x₁ +a_i2x₂ +ˇˇˇ+a_inx_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₁ + 3x₂ − x₃

x₁ − 2x₂ ≤ 5

x₂ + 3x₃ ≥ 3

x₁ + x₂ − 2x₃ = 20

x₁,x₂ ≥ 0

After converting constraints 1 and 2, we obtain:

max z = 2x₁ + 3x₂ − x₃

x₁ − 2x₂ + s₁ = 5

x₂ + 3x₃ − s₂ = 3

x₁ + x₂ − 2x₃ = 20

x₁,x₂,s₁,s₂ ≥ 0

Next, we make the substitution x₃ = u₃ − v₃ and obtain the standard form of the problem:

max z = 2x₁ + 3x₂ − u₃ + v₃

x₁ − 2x₂ + s₁ = 5

x₂ + 3u₃ + 3v₃ − s₂ = 3

x₁ + x₂ − 2u₃ + 2v₃ = 20

x₁,x₂,s₁,s₂,u₃,v₃ ≥ 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₁ + x₂ + 2x₄ = 3

2x₁ − x₂ − x₃ + 4x₄ = 1

We begin by choosing BV = {x₁,x₂} to be basic variables and NBV = {x₃,x₄} to be nonbasic variables. Setting x₃ = x₄ = 0, we obtain the following linear system:

x₁ + x₂ = 3

2x₁ − x₂ = 1

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

3 , x₂ = 12            3 ,

x₃ = 0, x₄ = 0.

Next we choose BV = {x₂,x₃} as our basic variables and set the nonbasic variables NBV = {x₁,x₄} equal to zero, i.e. x₁ = x₄ = 0. We have the following system:

x₂ = 3

−x₂ − x₃ = 1

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

x₃ = −4, x₄ = 0. If we choose BV = {x₁,x₄} and NBV = {x₂,x₃}, we obtain the following system of linear equations:

x₁ + 2x₄ = 3

2x₁ + 4x₄ = 1

This system is inconsistent so the variables x₁,x₄ 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₁ = (x₁ = 4

3 ,x₂ = 5

3 ,x₃ = 0,x₄ = 0) (feasible basic solution - FBS) and X₂ = (x₁ = 0,x₂ = 3,x₃ = −4,x₄ = 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.