04-02-2013, 11:29 AM
Linear Programming Notes I: Introduction and Problem Formulation
1Linear Programming.pdf (Size: 93.39 KB / Downloads: 162)
Introduction to Operations Research
Economics 172 is a two quarter sequence in Operations Research. Management
Science majors are required to take the course. I do not know what Management
Science is. Most of you picked the major. I assume that you either know what
it is or do not care. You may not know what Operations Research is. I am
going to tell you, but it will leave you disappointed.
Operations Research is research into operations. The field began during
the Second World War. The military needed to solve a lot of different kinds
of resource allocation problems. A prototypical problem was a form of the
transportation problem that we’ll study later in the course. In this problem
the military had supplies available in several different locations (ammunition
factories), it had several different locations that needed the supplies (battle
fronts), it knew how much it cost to ship supplies from any factory to any front.
It knew how much was produced at each factory and how much was needed in
each front. It wanted to figure out how to minimize the cost of shipping the
supplies to the various locations while meeting two types of resource availability
constraints (that you do not send more ammunition from a factory than is
available and that you send as much as necessary to each battle front). Many
other resource allocation problems arose in the planning of military operations.
Operations Research was a field of study that tried to come up with practical
solutions to these problems.
Introduction to Problem Formulations
Problem formulation is the most important part of a Operations Research course
for a Management Science major. When you are the boss, you’ll hire a geeky
engineer to do some basic math and write software. You’ll earn big bucks by
identifying the important problems and translating them from a verbal identification
to a mathematical form. The engineer will then solve the mathematical
problem. You will interpret the solution and put it into practice. It is important
for you to know enough about the basic mathematics for you to be able
to frame questions that the engineer might be able to answer and to be able to
judge whether the answers provided are sensible. Formulation, however, is key.
Unfortunately, I have little useful to say on the topic. In order to formulate
problems, you need to be able to understand symbols, you need common sense,
and you need practice. I am not aware of a mechanical series of steps you can
take in order to complete a formulation.
Now I will got through a particular (and standard) linear programming
problem and formulate it.
The problem is called the Diet Problem. Here is the story.
You run a small institution (prison, junior high school, third world country).
People work in your institution and you must feed them. Your job is to meet
their basic requirements for nutrients at minimum cost. In order to do this, you
need to know several things. You must know what foods are available and the
cost of each food. You must also know which nutrients are necessary and the
nutritional content of each of the foods. With this information you can figure out
how much any combination of food costs and you can figure out the nutritional
content of any combination of food. You can decide which combinations of food
are sufficient to meet the nutritional requirements and then pick the cheapest
combination that meets the nutritional requirement. (Perhaps the story makes
more sense if you imagine that your job is to feed the animals on your farm.)