Operations Research :- Unit I Linear Programming

Unit I Linear Programming

Syllabus:

Introduction, Modeling with Liner Programming, Two variable LP model, Graphical LP solutions for both maximization and minimization models with various application examples, LP model in equation form, simplex method, special case in simplex method, artificial starting solution, Degeneracy in LPP, Unbounded and Infeasible solutions.

1.1 Introduction

Operations Research is the science of rational decision-making and the study, design and integration of complex situations and systems with the goal of predicting system behavior and improving or optimizing system performance.

The first formal activities of Operations Research (OR) were initiated in England during World War II, when a team of British scientists set out to make scientifically based decisions regarding the best utilization of war materiel. After the war, the ideas advanced in military operations were adapted to improve efficiency and productivity in the civilian sector.

OPERATIONS RESEARCH MODELS

Imagine that you have a 5-week business commitment between Fayetteville (FYV) and Denver (DEN). You fly out of Fayetteville on Mondays and return on Wednesdays. A regular round-trip ticket costs $400, but a 20% discount is granted if the dates of the ticket span a weekend. A one-way ticket in either direction costs 75% of the regular price. How should you buy the tickets for the 5-week period?

We can look at the situation as a decision-making problem whose solution requires answering three questions:

1. What are the decision alternatives?

2. Under what restrictions is the decision made?

3. What is an appropriate objective criterion for evaluating the alternatives?

Three alternatives are considered:

1.     Buy five regular FYV-DEN-FYV for departure on Monday and return on Wednesday of the same week.

2.     Buy one FYV-DEN, four DEN-FYV-DEN that span weekends, and one DENFYV.

3.     Buy one FYV-DEN-FYV to cover Monday of the first week and Wednesday of the last week and four DEN-FYV-DEN to cover the remaining legs. All tickets in this alternative span at least one weekend.

The restriction on these options is that you should be able to leave FYV on Monday and return on Wednesday of the same week.

An obvious objective criterion for evaluating the proposed alternative is the price of the tickets. The alternative that yields the smallest cost is the best. Specifically, we have

Alternative 1 cost = 5 X 400 = $2000

Alternative 2 cost = .75 X 400 + 4 X (.8 X 400) + .75 X 400 = $1880

Alternative 3 cost = 5 X (.8 X 400) = $1600

Thus, you should choose alternative 3.

Though the preceding example illustrates the three main components of an OR model-alternatives, objective criterion, and constraints-situations differ in the details of how each component is developed and constructed. To illustrate this point, consider forming a maximum-area rectangle out of a piece of wire of length L inches. What should be the width and height of the rectangle?

In contrast with the tickets example, the number of alternatives in the present example is not finite; namely, the width and height of the rectangle can assume an infinite number of values. To formalize this observation, the alternatives of the problem are identified by defining the width and height as continuous (algebraic) variables.

Let

w = width of the rectangle in inches

h = height of the rectangle in inches

Based on these definitions, the restrictions of the situation can be expressed verbally as

1. Width of rectangle + Height of rectangle = Half the length of the wire

2. Width and height cannot be negative

These restrictions are translated algebraically as

1.     2(w + h) = L

2.     w ≥ 0, h ≥  0

The only remaining component now is the objective of the problem; namely, maximization of the area of the rectangle. Let z be the area of the rectangle, then the complete model becomes

Maximize                z = wh

subject to               2(w + h) = L

w, h ≥ 0

The optimal solution of this model is w = h = , which calls for constructing a square

shape. Based on the preceding two examples, the general OR model can be organized in

the following general format:

A solution of the mode is feasible if it satisfies all the constraints. It is optimal if, in addition to being feasible, it yields the best (maximum or minimum) value of the objective

function. In the tickets example, the problem presents three feasible alternatives, with the third alternative yielding the optimal solution. In the rectangle problem, a feasible alternative must satisfy the condition w + h =  with w and h assuming nonnegative values. This leads to an infinite number of feasible solutions and, unlike the tickets problem, the optimum solution is determined by an appropriate mathematical tool (in this case, differential calculus).

Though OR models are designed to "optimize" a specific objective criterion subject to a set of constraints, the quality of the resulting solution depends on the completeness of the model in representing the real system. Take, for example, the tickets model. If one is not able to identify all the dominant alternatives for purchasing the tickets, then the resulting solution is optimum only relative to the choices represented in the model. To be specific, if alternative 3 is left out of the model, and then the resulting "optimum" solution would call for purchasing the tickets for $1880, which is a suboptimal solution. The conclusion is that "the" optimum solution of a model is best only for that model. If the model happens to represent the real system reasonably well, then its solution is optimum also for the real situation.

---------------------------------------------------------------------------------------------------

1.2 Modeling with Liner Programming

Modeling a problem using linear programming involves writing it in the language of linear programming. There are rules about what you can and cannot do within linear programming. These rules are in place to make certain that the remaining steps of the process (solving and interpreting) can be successful. Key to a linear program are the decision variables, objective, and constraints.

Decision Variables. The decision variables represent (unknown) decisions to be made. This

is in contrast to problem data, which are values that are either given or can be simply calculated from what is given. For this problem, the decision variables are the number of notebooks to produce and the number of desktops to produce. We will represent these unknown values by x₁ and x₂ respectively. To make the numbers more manageable, we will let x₁ be the number of 1000 notebooks produced (so x₁ = 5 means a decision to produce 5000 notebooks) and x₂ be the number of 1000 desktops. Note that a value like the quarterly profit is not (in this model) a decision variable: it is an outcome of decisions x₁ and x₂.

Objective. Every linear program has an objective. This objective is to be either minimized

or maximized. This objective has to be linear in the decision variables, which means it must be the sum of constants times decision variables. 3x1 􀀀 10x2 is a linear function. x1x2 is not a linear function. In this case, our objective is to maximize the function 750x1 +1000x2 (what units is this in?).

Constraints.  Every linear program also has constraints limiting feasible decisions. Here we

have four types of constraints: Processing Chips, Memory Sets, Assembly, and Non-negativity.

---------------------------------------------------------------------------------------------------

1.3 Two variable LP model

This section deals with the graphical solution of a two-variable LP. Though two-variable problems hardly exist in practice, the treatment provides concrete foundations for the development of the general simplex algorithm

Example 2.1-1 (The Reddy Mikks Company)

Reddy Mikks produces both interior and exterior paints from two raw materials, Ml and M2.

The following table provides the basic data of the problem:

A market survey indicates that the daily demand for interior paint cannot exceed that for exterior paint by more than 1 ton. Also, the maximum daily demand for interior paint is 2 tons. Reddy Mikks wants to determine the optimum (best) product mix of interior and exterior paints that maximizes the total daily profit.

The LP model, as in any OR model has three basic components.

1. Decision variables that we seek to determine.

2. Objective (goal) that we need to optimize (maximize or minimize).

3. Constraints that the solution must satisfy.

The proper definition of the decision variables is an essential first step in the development of the model. Once done, the task of constructing the objective function and the constraints becomes more straightforward.

For the Reddy Mikks problem, we need to determine the daily amounts to be produced of exterior and interior paints. Thus the variables of the model are defined as

X₁ = Tons produced daily of exterior paint

X₂ = Tons produced daily of interior paint

To construct the objective function, note that the company wants to maximize (i.e., increase as much as possible) the total daily profit of both paints. Given that the profits per ton of exterior and interior paints are 5 and 4 (thousand) dollars, respectively, it follows that

Total profit from exterior paint = 5x₁ (thousand) dollars

Total profit from interior paint = 4x₂ (thousand) dollars

Letting z represent the total daily profit (in thousands of dollars), the objective of the company

is

Maximize z = 5x₁ + 4x₂

Next, we construct the constraints that restrict raw material usage and product demand. The

raw material restrictions are expressed verbally as

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1.4 Graphical LP solutions for both maximization and minimization models with various application examples

GRAPHICAL LP SOLUTION:

The graphical procedure includes two steps:

1.     Determination of the feasible solution space.

2.     Determination of the optimum solution from among all the feasible points in the solution space.

The procedure uses two examples to show how maximization and minimization

objective functions are handled.

1.4.1 Solution of a Maximization Model

1.4.2 Solution of a Minimization Model

feasible solution (verify with TORA!). On the other hand, the use of the inequality is inclusive

of the equality case, and hence its use does not prevent the model from producing exactly 800 lb of feed mix, should the remaining constraints allow it. The conclusion is that we should not "preguess" the solution by imposing the additional equality restriction, and we should always use inequalities unless the situation explicitly stipulates the use of equalities.

SELECTED LP APPLICATIONS

This section presents realistic LP models in which the definition of the variables and the construction of the objective function and constraints are not as straightforward as in the case of the two-variable model. The areas covered by these applications include the following:

1. Urban planning.

2. Currency arbitrage.

3. Investment.

4. Production planning and inventory control.

S. Blending and oil refining.

6. Manpower planning.

Each model is fully developed and its optimum solution is analyzed and interpreted.

---------------------------------------------------------------------------------------------------

1.5 LP model in equation form

The development of the simplex method computations is facilitated by imposing two

requirements on the constraints of the problem:

1.     All the constraints (with the exception of the non-negativity of the variables) are equations with nonnegative right-hand side.

2.     All the variables are nonnegative.

These two requirements are imposed here primarily to standardize and streamline the simplex method calculations. It is important to know that all commercial packages (and TORA) directly accept inequality constraints, nonnegative right-hand side, and unrestricted variables. Any necessary preconditioning of the model is done internally in the software before the simplex method solves the problem.

1.5.1 Converting Inequalities into Equations with Nonnegative Right-Hand Side

In (≤) constraints, the right-hand side can be thought of as representing the limit on the availability of a resource, in which case the left-hand side would represent the usage of this limited resource by the activities (variables) of the model. The difference between the right-hand side and the left-hand side of the (≤) constraint thus yields the unused or slack amount of the resource.

To convert a (≤)-inequality to an equation, a nonnegative slack variable is added to the left-hand side of the constraint. For example, in the Reddy Mikks model (Example 2.1-1), the constraint associated with the use of raw material M1 is given as

6x₁ + 4x₂ ≤ 24

Defining s₁ as the slack or unused amount of M1, the constraint can be converted to the following equation:

6x₁ + 4x₂ + s₁₌24, s₁ ≥ 0

Next, a (≥)-constraint sets a lower limit on the activities of the LP model, so that the amount by which the left-hand side exceeds the minimum limit represents a surplus. The conversion from (≥) to (=) is achieved by subtracting a nonnegative surplus variable from the left-hand side of the inequality. For example, in the diet model (Example 2.2-2), the constraint representing the minimum feed requirements is

x₁ + x₂  ≥ 800

Defining S₁ as the surplus variable, the constraint can be converted to the following equation

x₁ + x₂ – S₁=800, S₁ ≥ 0

The only remaining requirement is for the right-hand side of the resulting equation to be nonnegative. The condition can always be satisfied by multiplying both sides of the resulting equation by -1, where necessary. For example, the constraint

-x₁ + x₂  ≤  -3

is equivalent to the equation

-x₁ + x₂  +s₁=-3, s₁ ≥ 0

Now, multiplying both sides by -1 will render a nonnegative right-hand side, as desired- that is,                 

x₁ - x₂  - s₁ = 3

1.5.2 Dealing with Unrestricted Variables

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1.6 Simplex method

Rather than enumerating all the basic solutions (corner points) of the LP problem , the simplex method investigates only a "select few" of these solutions.

Section 1.6.1 describes the iterative nature of the method, and Section 1.6.2 provides the computational details of the simplex algorithm.

1.6.1 Iterative Nature of the Simplex Method

Figure 3.3 provides the solution space of the LP of Example 3.2-1. Normally, the simplex

method starts at the origin (point A) where x₁ = x₂ = 0. At this starting point, the value of the objective function, z, is zero, and the logical question is whether an increase in non-basic x₁ and/or x₂ above their current zero values can improve (increase) the value of z. We answer this question by investigating the objective function:

Maximize z = 2x₁ + 3x₂

The function shows that an increase in either x₁ or x₂ (or both) above their current zero values will improve the value of z. The design of the simplex method calls for increasing one variable at a time, with the selected variable being the one with the largest

rate of improvement in z. In the present example, the value of z will increase by 2 for each unit increase in x₁ and by 3 for each unit increase in x₂. This means that the rate of improvement in the value of z is 2 for x₁ and 3 for x₂. We thus elect to increase x₂, the variable with the largest rate of improvement. Figure 3.3 shows that the value of x₂ must be increased until corner point B is reached (recall that stopping short of reaching corner point B is not optimal because a candidate for the optimum must be a corner point). At point B, the simplex method will then increase the value of x₁ to reach the improved corner point C, which is the optimum. The path of the simplex algorithm is thus defined as A      B      C. Each corner point along the path is associated with an iteration. It is important to note that the simplex method moves alongside the edges of the solution space, which means that the method cannot cut across the solution space, going from A to C directly.

We need to make the transition from the graphical solution to the algebraic solution by showing how the points A, B, and C are represented by their basic and non-basic variables. The following table summarizes these representations:

Notice the change pattern in the basic and non-basic variables as the solution moves along the path A     B     C. From A to B, non-basic x₂ at A becomes basic at B and basic s₂ at A becomes non-basic at B. In the terminology of the simplex method, we say that x₂ is the entering variable (because it enters the basic solution) and s₂ is the leaving variable (because it leaves the basic solution). In a similar manner, at point B, x₁ enters (the basic solution) and s₁ leaves, thus leading to point C.

1.6.2 Computational Details of the Simplex Algorithm

This section provides the computational details of a simplex iteration, including the rules for determining the entering and leaving variables as well as for stopping the computations when the optimum solution has been reached. The vehicle of explanation is a numerical example.

Fig. Graphical interpretation of the simplex method ralios in the Reddy Mikks model

Summary of the simplex method

---------------------------------------------------------------------------------------------------

1.7 Special case in simplex method

This section considers four special cases that arise in the use of the simplex method

1.     Degeneracy

2.     Alternative Optima

3.     Unbounded Solution

4.     Infeasible(Nonexisting) Solution

Our interest in studying these special cases is twofold: (1) to present a theoretical explanation of these situations and (2) to provide a practical interpretation of what these special results could mean in a real-life problem.

1.7.1 Degeneracy

In the application of the feasibility condition of the simplex method, a tie for the minimum

ratio may occur and can be broken arbitrarily. When this happens, at least one basic

variable will be zero in the next iteration and the new solution is said to be degenerate.

There is nothing alarming about a degenerate solution, with the exception of a

small theoretical inconvenience, called cycling or circling, which we shall discuss shortly.

From the practical standpoint, the condition reveals that the model has at least one

redundant constraint. To provide more insight into the practical and theoretical impacts

of degeneracy, a numeric example is used.

Example 3.5-1 (Degenerate Optimal Solution)

1.7.2 Alternative Optima

When the objective function is parallel to a non-redundant binding constraint (i.e., a constraint that is satisfied as an equation at the optimal solution), the objective function can assume the same optimal value at more than one solution point, thus giving rise to alternative optima. The next example shows that there is an infinite number of such solutions. It also demonstrates the practical significance of encountering such solutions.

1.7.3 Unbounded Solution

In some LP models, the values of the variables may be increased indefinitely without violating any of the constraints-meaning that the solution space is unbounded in at least one variable. As a result, the objective value may increase (maximization case) or decrease (minimization case) indefinitely. In this case, both the solution space and the optimum objective value are unbounded.

Unboundedness points to the possibility that the model is poorly constructed. The most likely irregularity in such models is that one or more non redundant constraints have not been accounted for, and the parameters (constants) of some constraints may not have been estimated correctly.

The following examples show how unboundedness, in both the solution space and the objective value, can be recognized in the simplex tableau.

1.7.4 Infeasible Solution

LP models with inconsistent constraints have no feasible solution. This situation can never occur if all the constraints are of the type ≤ with nonnegative right-hand sides because the slacks provide a feasible solution. For other types of constraints, we use artificial variables. Although the artificial variables are penalized in the objective function to force them to zero at the optimum, this can occur only if the model has a feasible space. Otherwise, at least one artificial variable will be positive in the optimum iteration. From the practical standpoint, an infeasible space points to the possibility that the model is not formulated correctly.

1.8 Artificial starting solution

As demonstrated in Example 3.3-1, LPs in which all the constraints are (≤) with nonnegative right-hand sides offer a convenient all-slack starting basic feasible solution. Models involving (=) and/or (≥) constraints do not.

The procedure for starting "ill-behaved" LPs with (=) and (≥) constraints is to use artificial variables that play the role of slacks at the first iteration, and then dispose of them legitimately at a later iteration. Two closely related methods are introduced here: the M-method and the two-phase method.

1.8.1 M-Method

The M-method starts with the LP in equation form (Section 3.1). If equation i does not have a slack (or a variable that can play the role of a slack), an artificial variable, R_i , is added to form a starting solution similar to the convenient all-slack basic solution. However, because the artificial variables are not part of the original LP model, they are assigned a very high penalty in the objective function, thus forcing them (eventually) to equal zero in the optimum solution. This will always be the case if the problem has a feasible solution. The following rule shows how the penalty is assigned in the cases of maximization and minimization:

Example 3.4-1

1.8.2 Two-Phase Method

In the M-method, the use of the penalty M, which by definition must be large relative to the actual objective coefficients of the model, can result in round off error that may impair the accuracy of the simplex calculations. The two-phase method alleviates this difficulty by eliminating the constant M altogether. As the name suggests, the method solves the LP in two phases: Phase I attempts to find a starting basic feasible solution, and, if one is found, Phase II is invoked to solve the original problem.

Summary of the Two-Phase Method

Phase I. Put the problem in equation form, and add the necessary artificial variables to the constraints (exactly as in the M-method) to secure a starting basic solution. Next, find a basic solution of the resulting equations that, regardless of whether the LP is maximization or minimization, always minimizes the sum of the artificial variables. If the minimum value of the sum is positive, the LP problem has no feasible solution, which ends the process (recall that a positive artificial variable signifies that an original constraint is not satisfied). Otherwise, proceed to Phase II.

Phase II. Use the feasible solution from Phase I as a starting basic feasible solution for the original problem.

1.9 Degeneracy in LPP

One of the more conceptually mysterious aspects of linear programming is the problem of degeneracy-the breaking down of the simplex calculation method under certain circumstances. Degeneracy in applying the simplex method for solving a linear programming problem is said to occur when the usual rules for the choice of a pivot row or column (depending on whether the primal or the dual simplex method is being discussed) become ambiguous.

In other words, two or more values in the minimum ratio column are the same. To resolve degeneracy, the following method is used. Divide the key column values (of the tied rows) by the corresponding values of columns on the right side. This makes the values unequal and the row with minimum ratio is the key row.

Example : Consider the following LPP,

Maximize Z = 2x₁+ x₂

Subject to constraints,
4x₁ + 3x₂≤ 12 ...................(i)
4x₁+x₂≤ 8 ...................(ii)
4x₁– x₂≤ 8 ...................(iii)

Solution: Converting the inequality constraints by introducing the slack variables,

Maximize Z=2x₁+ x₂

Subject to constraints,
4x₁+ 3x₂+ s₃ = 12 ...................(iv)
4x₁+ x₂ + s₄ = 8 ...................(v)
4x₁– x₂+ s₅ = 8 ...................(vi)
Equating x₁, x₂ = 0, we get
s₃ = 12
s₄ = 8
s₅ = 8

Illustrating Degeneracy

After entering all the values in the first iteration table, the key column is -2, variable corresponding is x₁.To identify the key row there is tie between row s₄ and row s₅ with same values of 2, which means degeneracy in solution. To break or to resolve this, consider the column right side and divide the values of the key column values. We shall consider column x₂, the values corresponding to the tie values 1, –1.

Divide the key column values with these values, i.e., 1/4, –1/4 which is 0.25 and – 0.25. Now in selecting the key row, always the minimum positive value is chosen i.e., row s₄. Now, s₄ is the leaving variable and x₁ is an entering variable of the next iteration table. The problem is solved. Using computer and the solution is given in the following figure.

-----------------------------------------------------------------------------------------------------------------

1.10 Unbounded and infeasible solutions

UNBOUNDED SOLUTIONS IN LPP

In a linear programming problem, when a situation exists that the value objective function can be increased infinitely, the problem is said to have an 'unbounded' solution. This can be identified when all the values of key column are negative and hence minimum ratio values cannot be found.

Illustrating Unbounded Solution

Unbounded Solution

When the feasible region is unbounded, a maximization problem may don’t have optimal solution, since the values of the decision variables may be increased arbitrarily. This is illustrated with the help of the following problem

       

Infeasible Solution

A linear programming problem is said to be infeasible if no feasible solution of the problem exists. This section describes infeasible solution of the linear programming problem with the help of the following Example 2.8.

Example 2.8: