Linear Programming Formulation
The most critical step in LP is the formulation – just like any analysis, if you don’t have the problem correctly stated then you will be solving the wrong problem.
At this step one of the biggest challenges is to not try to solve the problem, we just want the mathematical formulation.

Start by reading the problem completely and carefully.

1.  Decision variables
Determine what the question is, what do you need to decide.  Is it how many of each product to produce, how many ounces (lbs, gms, cups….) of each ingredient to put in a mixture, how many people to assign to a shift???

Elements that you will NOT likely have to decide:
•    profit or cost per item – it’s a given(or the information will be given for you to calculate it)
•    TOTAL profit or cost will be an output of the solution (again NOT a decision to be made)
•    resource usage – hours per item, hours available – those will be given…
•    nutrients required
•    nutrients delivered by the ingredients

What you must decide will be written out as the decision variables.  Decision variables represent the choices that must be made.  This is the first formal part of the LP formulation.  Decision variable definitions must be specific and explicit.
It’s not good enough to say:
A = the amount of ingredient A to put in mix.
If A has a cost per ounce, a contribution per ounce, etc…. Then the definition must say
A = the number of ounces of ingredient A to put in the mix.
If you are doing a product mix problem to determine weekly production, the definition should say:
B = the number of product B to produce per week

Note:  you do not have to use X, Y or X1, X2 as variable names – use letters that help you remember what’s going on in the problem.
See Flair Furniture example in text pg 252– the problem is about tables and chairs so we use
T = number of tables to be produced per week
C = number of chairs to be produced per week

Once you have the decision variables defined, it may be helpful to organize the data in a table – put the decision variables across the top (column for each) and organize known parameters in table
– see Table 7.2 pg 252.
If you look at Table 7.2 and then across to pg 253 where the complete problem is stated, you should be able to see how the numbers in the table have been “peeled off” to write the mathematical functions for the objective function and the constraints.

2.  Objective function
Once you have defined variables, you must write a mathematical function that can be used to calculate the objective.  LP problems will only have one objective function.
This mathematical function must use the decision variables that you have defined in step 1.
In most of our problems, the objective will be to maximize profit or minimize cost.
Remember again, that we are not trying to solve the problem at this stage.

It might help some of you to think of it this way:
I know you could figure profit if we said we are selling apples that give a profit of $1.00 and oranges that give a profit of $1.50 and we sold 3 apples and 4 oranges   (Total profit = 1.00*3 + 1.50*4 = $900)
That is         Profit =              profit per apple * number of apples + profit per orange * number of oranges.

For the LP formulation, we don’t know the numbers of fruits yet so we use variables to hold the place
A = number of apples,
R= number of oranges (don’t like to use O as a variable name, looks too much like the number 0)
Profit = 1.00*A + 1.50*R

In the LP formulation the objective would be         Maximize Profit = 1.00*A + 1.50*R

3.  Constraints
Constraints are written similarly to the objective function – they are linear functions written in terms of the decision variables (and you must use the decision variables that you have defined.)
Each constraint will have a right hand side (rhs), that is the limit or requirement stated in the problem.  (rhs is an established item in LP terminology)

Your text gives the general idea of a resource constraint as:
Amount used <= Amount available
Other types of constraints might be:
Nutrient requirements in an ingredient mix problem
Amount provided >= Amount required
Contract requirement for a certain product
Number of item A’s produced >= Contract for number of A’s
Demand limit for a certain product
Number of item B’s produced <= Demand for item B
All of these will be written as mathematical functions using the numerical parameters given in the problem description and the decision variables that you have defined.

Study the examples in Chapters 7 & 8 for a wide variety of constraints.  A couple of examples are shown below.

Examples

1.  Blue Ridge Hot Tubs produces two types of hot tubs: Aqua-Spas & Hydro-Luxes.  Each tub requires one pump.  The Aqua-Spa requires 9 hours of labor to produce, while the Hydro-Lux requires 6 hours.  The only limited material is tubing, the Aqua-Spa requires 12 feet , while the Hydro-Lux requires 16 feet.
There are 200 pumps, 1566 hours of labor, and 2880 feet of tubing available weekly.  The profit contribution for each Aqua-Spa is $350 and for each Hydro-Lux is $300.
Formulate as a linear programming problem to determine how many of each tub Blue Ridge should produce.

1.  Define Decision variables
First step – what do we have to decide?   The problem does us a favor by telling us (always look for these hints) “determine how many of each tub.”  So we have to decide how many of each tub to make

AS = number of Aqua-Spa model tubs to produce per week
HL = number of Hydro-Lux model tubs to produce per week

If it helps you to put the data in a table – do it!!!

AS    HL    Available
Pumps per tub    1    1    200
Labor per tub    9    6    1566
Tubing per tub    12    16    2880
Profit per tub    350    300

2.  Write the objective function – even though the problem doesn’t tell us the objective specifically, we should be able to figure it out (we are business students after all)

Maximize profit = 250AS + 300HL

3.  Write the constraints – there are three limited resources, there will be three constraints.
Pumps          1AS + 1HL <= 200
Labor             9AS + 6HL <= 1566
Tubing            12AS + 16HL <= 2880

Always in an LP there will be non-negativity constraints.  You cannot have a negative solution.
We often take them for granted – the Solver in Excel has an option so we don’t have to explicitly add them when we solve in Excel – but don’t forget them!!!
AS >= 0
HL >= 0

If you are asked for an LP formulation, this is what should be presented:

AS = number of Aqua-Spa model tubs to produce per week
HL = number of Hydro-Lux model tubs to produce per week

Maximize profit = 250AS + 300HL
Subject to:
Pumps      1AS + 1HL <= 200
Labor         9AS + 6HL <= 1566
Tubing        12AS + 16HL <= 2880
AS >= 0
HL >= 0

2.  The Elixer Drug Company produces a drug from two ingredients.  Each ingredient contains the same three antibiotics in different proportions.  One gram of ingredient 1 contributes 3 units, and ingredient 2 contributes 1 unit of antibiotic A.  The drug requires 6 units.  At least 4 units of antibiotic B are required, ingredient 1 contributes 1 unit per gram and ingredient 2 contributes 1 unit per gram.
At least 12 units of antibiotic C are required; ingredient 1 contributes 2 units per gram and ingredient 2 contributes 6 units per gram.  The cost for a gram of ingredient 1 is $80 and the cost for a gram of ingredient 2 is $50.  The company wants to formulate a linear programming model to determine the number of grams of each ingredient that must go into the drug in order to meet the antibiotic requirements at the minimum cost.
Formulate as a linear programming model
1.  What do we need to decide?  “to determine the number of grams of each ingredient that must go into the drug”
X1 = number of grams of ingredient 1 to put in the drug
X2 = the number of grams of ingredient 2 to put in the drug

Note: It is VITAL that you put the units in the definition (grams).  Don’t be confused by the problem, read it carefully – we are told the units of antibiotic A per gram of ingredient, units of antibiotic B per gram of ingredient, units of antibiotic C per gram of ingredient and cost per gram of ingredient… all of this should lead you to define the variables as GRAMS of ingredient

Organize data in a table
Ing 1  X1    Ing 2 X2    Needed
Cost per gram    80    50
Vit A per gram    3    1    6
Vit B per gram    1    1    4
Vit C per gram    2    6    12

2.  Write the objective function – again the problem helps us out here “at the minimum cost.”

Minimize cost = 80X1 + 50X2
3.  Write the constraints
We have requirements for 3 different antibiotics: A, B, and C – we need three constraints

A        3X1 + 1X2 >=  6
B        1X1 + 1X2 >=  4
C        2X1 + 6X2 >= 12
X1 >= 0
X2 >= 0
Note: we must have at least xx units of each antibiotic, at least means greater than or equal to, >=

One thing that you can do to check your formulation (especially your variable definition) is check the units in the formulas…
For this objective function  we have

The grams will cancel out and we are left with $ + $
– that checks out – what we expect for cost is $$$$$$

So the finished formulation is:

X1 = number of grams of ingredient 1 to put in the drug
X2 = the number of grams of ingredient 2 to put in the drug

Minimize cost = 80X1 + 50X2
Subject to:
3X1 + 1X2 >=  6
1X1 + 1X2 >=  4
2X1 + 6X2 >= 12
X1 >= 0
X2 >= 0

3.  One type of constraint that always seems to be a problem is actually too simple for words.
Go back to the Blue Ridge hot tub example.  What if the marketing department has signed a contract that requires us to make at least 10 Aqua-Spa models for a certain client.   That requirement means another constraint has to be added.
The constraint simply has to ensure that we make at least 10 Aqua-Spas
Mathematically:
AS >= 10

Simple, right???