Linear Programming corresponds to an algorithm trough which real situations can be solved in which the goal is to identify and resolve difficulties to rise productivity about resources (mainly limited and expensive resources), raising like this the benefits. The main goal of Linear Programming is to optimize (minimize or maximize) linear functions in many real variables with linear constraints (linear inequality systems), optimizing a goal function, also linear.
The results and process optimization process become a decisions quantitative backup, about general situations. Decisions on which it would be important to have many administrative criteria just as:
- Facts
- Experience
- Intuition.
- Authority.
¿How to resolve a problem trough linear programming?
The first step consists in the identification of the basic elements of a mathematical model, like:
- Objective Function.
- Variables.
- Constraints
The next step consists in de determination of those, for which the recommendation is to follow:
Objective function
The Objective Function has a close relationship with the general question to answer. If a model has many questions to resolve, the Objective Function is related with the higher-level question, that is to say, the fundamental question. For example, if in a situation the objective is to minimize costs, is very likely that the higher question is related with raising the profitableness instead of a question that looks for a way to minimize expenses.
Decision Variables
Similar to the relation that exists between specific objectives and the general objective, the decision variables behave with respect to the Objective Function, given that these ones are identified starting from a series of questions derived from the Fundamental Question. The decision variables, are in theory, controllable factors of the system that is being modeled, and as such, this one can have many possible values, of which is necessary to know their optimal value, that helps with the consecution of the objective of the general function of the problem.
Constraints
When we talk about constraints in a linear organization problem, we refer an everything that limits freedom of the values that the decision variables can have.
The best way to find them consists in to think in a hypothetical case on which we decide to give an infinite value to our decision variables, for example, ¿what would happen if in a problem that needs to maximize its profits on a shoe production system we decide to produce an infinite quantity of shoes? Surely now we would have many questions, such as:
- ¿How many raw materials do I have to make them?
- ¿How many workforces do I have to make them?
- ¿Can my facilities handle that product quantity?
- ¿Can my marketing handle sell all those shoes?
- ¿Can I finance such company?
Well, then we would have discovered that our system presents constraints, as much as physical, as context, in a such a way that the values that in a given moment could take our decision variable are conditioned by a series of constraints.
Example of linear programming problem solving
The Yarn factory “SALAZAR” needs to manufacture two weaves of different quality T and T’; it has 500Kg of yarn A, 300Kg of yarn B and 108 Kg of yarn C. In order to manufacture a meter of T daily its required 125gr of A, 150gr of B and 75 of C; in order to manufacture a meter of T’ its required 200gr of A, 100gr of B and 27gr of C. T is sold to $4000 per meter and T’ is sold $5000 per meter. If you need to get the most benefit out of it, ¿how many meters of T and T’ must be manufactured?
Is recommended to read the problem more than once, so the variables can be remembered clearly.
Step 1: Setting the problem
We start of the main question of the problem:
¿How many meters of T and T’ must be manufactured?
And the setting would be:
To determine the daily manufactured meter of T and T’, having into account the optimal profit.
Step 2: Determine the Decision Variables
Based on the information of the problem our decision variables are:
XT: Quantity of daily meters of typo T fabric.
XT’: Quantity of daily meters of type T’ fabric.
Step 3: Determine the constraints of the problem
In this step we determine the functions that limit the problem, these are given by capacity, availability, proportion, not negativity among others.
Raw materials availability:
0,125XT + 0,200XT’ <= 500 Yarn “A”
0,150XT + 0,100XT’ <= 300 Yarn “B”
0,072XT + 0,027XT’ <= 108 Yarn “C”
No negativity:
XT,XT’ >= 0
Step 4: Determine an Objective Function:
In this step is vital to stablish the operative context of the problem so you can determine if it is Maximization or Minimization. In this case approach the context of profitability, thus the ideal is Maximization.
.
Objective Function
ZMAX = 4000XT + 5000XT’
Step 5: Resolve the model using software or manually
Often the linear programming problems are built by innumerable variables, which difficult their manual resolution, this is why we use specialized software like: WinQSB, TORA, Lingo or for less complex models are more useful Solver Excel.
The past exercise was solved through Solver Excel, and the result was:
A comment