An introduction to Operations Research

Summary: A small example to show what Operations Research is all about and how it can be simple yet very powerful.

Let's face a problem that maybe some of you encountered in primary school or as a game on a magazine.

The problem: assemblage of mobile phones

We have an assemblage kit containing pieces of different colors and dimensions, each corresponding to a specific component of a mobile phone. We have: 10 display modules (blue-colored); 16 memory modules (green-colored); 21 six-key keypads (red-colored); 8 navigation keyboards (white-colored).

components Fig. 1: the components available to assemble the mobile phones

Appropriately combining these elements, we can assemble mobile phones of two different models, as shown below:

models Fig. 2: the two models of mobile phones to be assembled

Each phone of type A brings 3 points; each phone of type B brings 8 points. The game consists in assembling the pieces that we have, trying to make the highest possible score.

So try to find the best solution by yourself. Experiment with several combinations and, eventually, try to find out a good method to follow.

Keeping the various components at our disposal, it is not difficult to generate feasible solutions, that is combinations of pieces satisfying the "recipes" of mobile phones, and it can be easy to quickly detect among all possible combinations the one making the highest score. But it is certainly not so easy to certify that the chosen solution is the very best – something we can efficiently do only by using mathematical tools – or to quantify the intrinsic value of resources (for example: how much are we ready to pay for one more keyboard?), or to assess the solution stability in case of variations of the granted points.

The 'Operations Research' approach

There are 3 key points to define precisely in order to solve the problem.

Decisions
What decisions did you take? How do you characterize your solution?
Rules
How do you combine components to obtain a product?
Goal
What do you have to optimize?

Decisions = Variables

x = how many phones of type A
y = how many phones of type B

Rules = Constraints

The number of used components cannot exceed the available ones

x + 2y ≤ 10 display
x + 4y ≤ 16 memory
2x + 3y ≤ 21 keyboard
1x ≤ 8 navigation
x , y ≥ 0 non negativity

Goal = Objective function

max 3x + 8y

Solution

By looking at the model we just created, we can realize that there are linear relations between 2 variables. Thus we can give a geometric representation on the Cartesian plane.

plot Fig. 3: geometric representation of the problem

The edge of each constraint corresponds to a straight line: it indicates a situation in which we are using all the available pieces of that particular component. Each constraint detects a half-plane, that is an area where the constraint is satisfied (x and y make the inequality true). By combining all the constraints we can outline the feasible region of the problem. Note that every integer point in the region is a solution. Intuitively we can guess that the optimal solution has to be found on the edge of the feasible region. One more reasoning step and we restrict our search to the vertexes only. So it is just a matter of calculating the objective function on every vertex and select the one that gives the highest value.