UNIT - I Notes

 

Operation Research - Definition

Operations research is essentially a collection of mathematical techniques and tools which in conjunction with a system’s approach, are applied to solve practical decision problems of an economic or engineering nature.

 

General Structure of an LP Model

The general structure of an LP model consists of the following three basic components (or parts).

·        Decision variables (activities)

·        The objective function

·        The constraints

 

Decision Variables

To arrive at the optimal value of the objective function, certain activities (also called decision variables) usually denoted by x1, x2, . . ., xn are conducted. In an LP model, all decision variables are continuous, controllable and non-negative. That is, x1 ≥ 0, x2 ≥ 0, . . ., xn ≥ 0.

 

Objective Function

The objective function of each LP problem is expressed in terms of decision variables to optimize the criterion of optimality (also called measure-of-performance) such as profit, cost, revenue, distance etc.

In its general form, it is represented as:

Optimize (Maximize or Minimize) Z = c₁x₁ + c₂x₂ + . . . + c_nx_n

 The Constraints

There are always certain limitations (or constraints) on the use of resources, such as: labour, machine, raw material, space, money, etc. Such constraints must be expressed as linear equalities or inequalities in terms of decision variables. The solution of an LP model must satisfy these constraints.

 

IMPORTANT DEFINITIONS

Solution

The set of values of decision variables xj (j = 1, 2, . . ., n) that satisfy the constraints of an LP problem is said to constitute the solution to that LP problem.

 

Feasible solution

The set of values of decision variables xj (j = 1, 2, . . ., n) that satisfy all the constraints and non-negativity conditions of an LP problem simultaneously is said to be the feasible solution of the LPP.

 

Infeasible solution

The set of values of decision variables xj ( j = 1, 2, . . ., n) that do not satisfy all the constraints and non-negativity conditions of an LP problem simultaneously is said to be the infeasible solution of the LPP.

 

Basic solution

For a set of m simultaneous equations in n variables (n > m) in an LP problem, a solution obtained by setting (n – m) variables equal to zero and solving for remaining m equations in m variables is called a basic solution of that LP problem.

  The (n – m) variables whose value did not appear in the basic solution are called non-basic variables and the remaining m variables are called basic variables.

 

 Basic feasible solution

A feasible solution to an LP problem which is also the basic solution is called the basic feasible solution. That is, all basic variables assume non-negative values.

The basic feasible solution is of two types:

 (a) Degenerate A basic feasible solution is called degenerate if the value of at least one basic variable is zero.

 (b) Non-degenerate A basic feasible solution is called non-degenerate if the value of all m basic

 variables are non-zero and positive.

 

 Optimum basic feasible solution

A basic feasible solution that optimizes (maximizes or minimizes) the objective function value of the given LP problem is called an optimum basic feasible solution.

 

 Unbounded solution

A solution that can increase or decrease infinitely the value of the objective function of the LP problem is called an unbounded solution.

 

Definition of Linear Programming

Linear programming is a mathematical technique for determining the optimal allocation of resources among alternative uses of the resources to achieve a particular objective. The objective includes profit maximization or cost minimization.

 

Optimal condition

For maximization problems if all Cj - Zj are less than equal to 0, then the optimal condition is reached otherwise select the variable with the maximum Cj - Zj as the entering variable.

 

For minimization problems if all Cj - Zj are greater than equal to 0, then the optimal condition is reached; otherwise, select the variable with the most negative value as the entering variable.

 

The canonical form of LPP

The given LPP can be written in a canonical form as follows;

1)  The objective function is of maximization type. If the given objective function is of minimization type, convert it into maximization type by multiplying throughout by -1.

2)  All the constraints are of ≤ type. The inequalities of ≥ type are converted to ≤ type by multiplying both sides of the inequality by -1.

3)  All the variables are non-negative.

If a variable is unrestricted in sign, replace it with the difference between two positive variables. For example, if x_i is unrestricted in sign, replace it with x_i' - x_i''

  

 

  

Standard form of LPP

1)  All constrains / inequalities are written as equations.

To convert a ≤ inequality to an equation add a variable to the left-hand side of the constraint. This variable is called a slack variable.

To convert a ≥ inequality to an equation subtract a variable from the left-hand side of the constraint. This variable is called a surplus variable.

 2)  The right-hand side of the inequalities must be non-negative.

If the right-hand side is negative, then multiply both sides of the constraint by -1 in which case the ≤ inequality will be changed to ≥ and vice-versa.

 

Simplex Method

Step 1: Rewrite the given LPP in the standard form.

a)    Check whether the objective function is of maximization type.

b)    Check whether all the right-hand side values of the constraints are non-negative.

c)  Convert all the inequalities into equations.

Step 2: Obtain an initial basic feasible solution and put it under the Basic Variable(BV) column of the initial Simplex table.

Step 3: Compute the net evaluations zj = ∑(C_Bi - y_ij). Then calculate C_j-Z_j

Step 4: Check for optimal conditions. If at least one (C_j-Z_j) is negative, then choose the most negative of them and the corresponding column variable is taken as the entering column variable.

Step 5 : To find the leaving variable, find the ratio of bi / x_i (xi positive values in the entering column).

Step 6: The minimum ratio is taken as the leaving variable. This variable in the BV column will be replaced with the entering column variable.

Step 7 : The element at the intersection of the Key column and key row is called the pivot element.

Step 8: Construct the next simplex table in such a way that the pivot element must be 1 and the other elements in the key column must be 0.

Step 9 : Repeat steps 3 to 8, till the optimal condition is obtained.

 

Artificial Variable

While converting ≥ inequality to an equation, a variable called surplus variable is subtracted from the left-hand side of the equation. The addition of this variable will not satisfy the feasibility condition. Hence, to find the optimal solution using the Simplex method, a variable called an Artificial Variable is added to the left-hand side of the equation.

While using the Simplex method to find the optimal solution to the LPP, the artificial variables must be removed.

 There are two methods for removing artificial variables from the solution.

•   Two-Phase Method

•   Big-M Method or Method of Penalties

 

Two Phase Simplex Method

Phase I 

Step 1 (a):

If the constraints in the given LP problem are (≥) type, then the necessary number of surplus and artificial variables are added to convert constraints into equality constraints.

(b) If the given LP problem is of minimization, then convert it to maximization 

   Step 2: Assign zero coefficient to each of the decision variables (xj ) and the slack

and surplus variables; and assign – 1 coefficient to each of the artificial variables. This yields the following auxiliary LP problem.

Step 3: Apply the simplex algorithm to solve this auxiliary LP problem.

             The following three cases may arise at optimality.

(a)  Max Z * = 0 and at least one artificial variable is present in the basis with a positive value. This means that no feasible solution exists for the original LP problem.

(b)  Max Z * = 0 and no artificial variable is present in the basis. This means that only decision variables (xj ’s) are present in the basis and hence proceed to Phase II to obtain an optimal basic feasible solution on the original LP problem.

(c)  Max Z * = 0 and at least one artificial variable is present in the basis at zero value. This means that a feasible solution exists and proceed directly to Phase II or else eliminate the artificial basic variable and then proceed to Phase II.

 

Phase II:

Assign actual coefficients to the variables in the objective function and zero coefficient to the artificial variables which appear at zero value in the basis at the end of Phase I.

The last simplex table of Phase I can be used as the initial simplex table for Phase II.

Then apply the usual simplex algorithm to the modified simplex table to get the optimal solution to the original problem.

Artificial variables that do not appear in the basis column can be removed from the table.

 

 Big-M Method

Big-M method is another method of removing artificial variables from the basis.

 

In this method, a large penalty (M) is added as coefficient to artificial variables in the objective function. The penalty is supposed to be designated by – M, for a maximization problem, and + M, for a minimization problem, where M > 0.

The Big-M method for solving an LP problem can be summarized in the following steps:

 Step 1:

Express the LP problem in the standard form by adding slack variables, surplus variables and artificial variables.

Assign a zero coefficient to both slack and surplus variables.

Then assign a very large coefficient + M (minimization case) and – M (maximization case) to artificial variable in the objective function.

Step 2:

The initial basic feasible solution is obtained by assigning zero value to decision variables, x1, x2, ..., etc.

Step 3:

Calculate the values of cj – zj in last row of the simplex table and examine these values.

(i)  If all cj – zj ≥ 0, then the current basic feasible solution is optimal.

(ii)  If for a column, k, c_k – z_k is most negative and all entries in this column are negative, then the problem has an unbounded optimal solution.

(iii) If one or more cj – zj < 0 (minimization case), then select the variable with the largest negative cj – zj value (largest value) as the entering variable.

 

Step 4: Determine the key row and key element in the same manner as done in the simplex algorithm for the maximization case.

Step 5: Continue with the procedure to update solution at each iteration till the optimal solution is obtained.