Operational research primer

Intro to operational research

Introduction🔗

I love to improve things. But in order to move things forward, it is needed to change things. The trick is, to know 'what' things need to change and how much to change them.

Fortunately there are plenty of tools are available: pen and paper, whiteboards, excel, computers, ...

I started looking further into 'operational research', when my needs outgrew the standard 'solver' functionality of excel.

Enter Operational research🔗

Operational Research: A method of mathematically based analysis for providing a quantitive basis for management decisions.

Operational research is basically a method to describe a model where you can find the optimal solution for certain conditions.

Here are a few common/interesting problems:

  • the allocation and assignment problems.
  • the determining of optimal prices.
  • the blending of raw materials in oil refineries.
  • the wide array of scheduling problems (Personnel staffing, Manufacturing steps, Project tasks, Network data traffic, Sports events).
  • the identification of the processes in a complex project which affect the overall duration of the project.
  • the design of the layout of equipment in a factory or components on a computer chip to reduce manufacturing time (therefore reducing cost).
  • the setup of telecommunications networks to maintain quality of service during outages.
  • the determination of the routes of buses so that as few buses are needed as possible.
  • the managing of the flow of raw materials and products based on uncertain demand for the finished products.
  • the managing of the flow of work activities in a capital project in response to system variability through operations research tools..
  • the efficient messaging and customer response tactics.
  • the automating or integrating of robotic systems in human-driven operations processes.
  • the globalizing operations processes in order to take advantage of cheaper materials, labor, land or other productivity inputs.
  • the managing of freight transportation and delivery systems.
  • ..

Theory🔗

There are lots and lots of technical papers. They start 'simple' and after a few pages the change into something with a lot of formula's.

wtf

A classic example🔗

The most classic example of operational research is the 'Airbridge to Berlin' problem.

What are the facts?

  • Berlin surrendered to the Russian army on May 2, 1945.
  • During the following weeks the Russians shipped most of the city's industrial goods to Russia.
  • The American, British, and French troops did not arrive until July 1945.
  • Even before the war ended the allies decided to divide the city into four sectors, each country occupying one.
  • Berlin lay deep in the Russian sector of the country, but the Western powers assumed that the Soviets would allow them free access to the city.
  • However, on June 24, 1948 the Soviets blocked all land and water routes through East Germany to Berlin. They hoped to drive the Western powers from East Germany.
  • The problem facing the Western Allies was how to keep West Berlin supplied during the Russian blockade.

What is the problem?

How to organize a gigantic airlift to supply more than 2 million people in West Berlin?

or:

Maximize the cargo capacity of the planes subject to the restrictions:

  • The number of planes is limited to 44.
  • The American planes are larger than the British planes and therefore need twice the number of personnel per flight.
  • The cost of an American flight is $9000 and the cost of a British flight is $5000.
  • The cargo capacity of an American plane is 30,000 cubic feet and the cargo capacity of a British plane is 20,000 cubic feet.
  • The total cost per week is limited to $300,000.
  • The number of crews for an American flight available is 64.

How many American and British planes should be used to maximize the cargo capacity?

How to solve this?🔗

One of my strength is the ability to structure and organize data into clear information.

Let's take the constraints and look at them closely:

Variables🔗

One variable is the number of flights.

  • There is a limit to them (44).
  • The unit is probably 'per one', but let's call it 'Planes'.

Another limitation could be the number of crew members.

  • The limit is only on the American side, but there is also a relation between the american crewmembers and the britisch crew members.
  • We could take a 'person' as its unit.

Another limitation would be the costs.

  • There are different cost for American and Britisch crew.
  • The unit is obvious: '$'.

Another variable is cargo.

  • That is what needs to be maximized.
  • There are different cost for American and Britisch crew.
  • The unit would be 'qubic feet'. (Long live the metric system...)

If we write this in a nice overview, things are much more clearer.

  Constraints Unit American British
Flights <44 Planes    
Crew   Persons <=64  
Cost <300000 $ 9000 5000
Cargo   qubic feet 30000 20000

Further rules:

American crew = 2 * British crew

The question:

To Maximize capacity, how many American and British flights are needed?

How to start?🔗

So if we know how many American and how many British planes are used, we can calculate the crewmembers, the costs and the cargo load. We could fiddle around with both numbers of both types of planes and see if we are still with in the constraints. If so, .. then we need to find out the values that yielded the maximum cargo.

We could start with finding the boundaries:

  • When we take 0 American planes, and we use all 44 Britisch planes, have we still some money left? Yep.
  • When we take 0 British planes, can we use all 44 American planes before we run out of money or crew? Nope.

This gives us some upper limits. From there we can iterate further.

Tools🔗

There are many tools that can help with this. Some of them are open source, a lot of them have 'freemium' licenses. Most of these tools have a special syntax/language to describe the problems and the constraints. Some tools are specialised to describe the problem in a model in a nice way. These tools can use the various solvers to calculate the solution.

Summary🔗

  • A solver can help you find the optimal situation based on constraints.
  • Describe the 'real world' into a model. (* this is the difficult part *)
  • Figure out what solver to use (* this is depends on your situation *)
  • Turn the model into a 'script'.. (* this is another difficult part *)
  • Run the script in a solver.
  • ..
  • Profit.