Linear Programming Formulation
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