Solving the OR Model

Lecture 1

OPERATION RESEARCH in TRANSPORT SYSTEMS

OR Model.

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?

A solution of the decision-making problem 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?

The alternatives of the problem are identified by defining the width and height as continuous variables (can assume an infinite number of values).

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 objectiveof the problem; namely, maximization of the area of the rectangle. Let z be the area of the rectangle, then the complete model becomes

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

Based on this example, the general OR model can be organized in the following general format:

A solution of the mode is feasibleif 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 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 the optimum solution is determined by differential calculus.

PROBLEM SET 1.

1. In the rectangle problem, identify two feasible solutions and determine which one is better.

2. Determine the optimal solution of the rectangle problem. (Hint: Use the constraint to express the objective function in terms of one variable, then use differential calculus.)

3. Amy, Jim, John, and Kelly are standing on the east bank of a river and wish to cross to the west side using a canoe. The canoe can hold at most two people at a time. Amy, being the most athletic, can row across the river in 1 minute. Jim, John, and Kelly would take 2, 5, and 10 minutes, respectively. If two people are in the canoe, the slower person dictates the crossing time. The objective is for all four people to be on the other side of the river in the shortest time possible.

(a) Identify at least two feasible plans for crossing the river (remember, the canoe is the only mode of transportation and it cannot be shuttled empty).

(b ) Define the criterion for evaluating the alternatives.

(c) What is the smallest time for moving all four people to the other side of the river?

Solving the OR Model

In OR, we do not have a single general technique to solve all mathematical models that can arise in practice. Instead, the type and complexity of the mathematical model dictate the nature of the solution method.

The most prominent OR technique is linear programming. It is designed for models with linear objective and constraint functions. Other techniques include integer programming (in which the variables assume integer values), dynamic programming(in which the original model can be decomposed into more manageable subproblems), network programming (in which the problem can be modeled as a network), and programming (in which functions of the model are nonlinear). These are only a few among many available OR tools.

A peculiarity of most OR techniques is that solutions are not generally obtained in (formulalike) closed forms. Instead, they are determined by algorithms.An algorithm provides fixed computational rules that are applied repetitively to the problem, with each repetition (called iteration) moving the solution closer to the optimum.

Some mathematical models may be so complex that it is impossible to solve them by any of the available optimization algorithms. In such cases, it may be necessary toabandon the search for the optimal solution and simply seek a good solution usingheuristics or rules of thumb.

Date: 2016-03-03; view: 2053