OPTIMIZATION PROBLEMS

What is an optimization problem? It's a type of mathematical problem where you want to find the best value of something (called an objective function), given certain facts (called constraints). Usually what you're looking for is the maximum of something (for example, profit), or the minimum of something (for example, cost).

An example will help make things clearer. Let's say you run a company which can make two objects, call them ProductA and ProductB. How many of each should you make? Obviously, if you had unlimited time, you would make as many as could of each. But since your time is limited, which should you make more of, and how many more? Of course, you want to maximize your profit; that's the objective function here. Let's say you profit $1 for each ProductA that is sold, and $2 for each ProductB that is sold. Furthermore, you make a (an arbitrary number) of ProductA and b of ProductB. Then the objective function is given by a + 2b. Upon looking at this, it seems it profits you more to make all ProductB; this may not be the case, however, if it takes longer to produce. To decide for sure we need more information (in the form of constraints). Two obvious constraints are a ³ 0 and b ³ 0.

Let's assume (for the sake of example) your business has two departments, department #1 and department #2. Each ProductA you produce takes 5 labor-hours a day in department #1 and 18 labor-hours a day in department #2. Each ProductB you produce takes 10 labor-hours a day in department #1 and 4 labor-hours a day in department #2. In each department you have a total of 50 labor-hours each day (say, 5 people working 10 hours each). Now we have two new constraints:

Now we have a statement of our problem:
Maximize a + 2b given the constraints a ³ 0, b ³ 0, 5a + 10b £ 50, and
18a + 4b £ 50.

How do we solve this?
Read the next section, Linear Programming