A linear programming tutorial is a guide tool that can provide solutions when you are dealing with linear programming. Linear programming is used because the human brain is limited to thinking about several constraints at the same time. If you are one of those who feel confused by the formula in linear programming, take a good look at the explanation and tutorial of linear programming in this article.
As a first step, I give you an illustration: if you have 1000 dollars, Then there is a choice of products that you will buy, namely product A at a price of 100 and product B at a price of 200. How many products A and B should you buy if you want to buy them in large quantities? Of course, you will buy 10 pieces of product A. The answer will be different if there is an additional condition that the minimum of product B is 2 pieces.
The problem is basically very simple and can be solved easily. However, if we encounter the value of the product above 10 variables, with each variable having its own constraints, of course we must use a tool to help solve it. One tool that is often used is linear programming.
Linear programming can be used in various institutions. For example, companies that want to maximize profits, companies that want to reduce costs, governments that want to increase the planting area, what is the optimal selling price of a product, and others
Basic concept Linear Programming
The basic concept of linear programming problems was actually given to us when we attended school at the senior high school level. You must have heard of math inequalities with X and Y variables, right? For example:
Determine the value of x that corresponds to the following inequality:
X2 + x -2 >0,
X2 + x -2 >0
(x+2) (X-1) >0
X = -2, x = 1
-2<x<1
There are many other examples that I don’t need to discuss here. The example above is a math inequality that is often not understood by students during school. Because they are too focused on thinking about how to solve it. In fact, after college, the reason why using inequalities becomes more important is because the detailed calculations are already assisted by calculating tools or computers.
Another basic concept that I think is very close to linear programming is graphs. Basically, the answer to a linear programming problem is the most optimal point of several intersecting graphs. The intersecting graphs form a shaded area. The area is a choice of Y values that are in accordance with the constraints of the problem.
Take a look at the following graph:
Figure 1 shows that there is a line y < 3. The area corresponding to the inequality is the shaded area. This shaded area is still large if you extend it to the right and left sides.
The shaded area in figure 1 starts to be restricted by the second inequality, with inequality x < 5. The shaded area becomes slightly narrower. However, there are still many choices that correspond to both inequalities. For example, points (1,1), (2,2), (2,1), etc. are still within the shaded area.
In the third picture, the intended point begins to appear, because in this picture there is a graph of the third inequality, X < Y. The shaded area is getting narrower. The shaded area is the answer to the third math inequality. Now it depends on the goal of the problem—whether you want to maximize the value of Y or maximize the value of X.
If the goal or purpose of the three inequalities is to maximize the value of X, then points B and C are the upper limit points that can maximize the value of X. However, if the goal is to maximize the value of Y, then points A and B are the choices for the upper limit to maximize the value of Y according to the goal.
If you understand the illustration of the example problem above, then I am sure you will understand how linear programming works in solving problems. That’s right. Linear programming, as the name implies, always uses straight lines. These straight lines limit a shaded area, and then LP (linear programming) determines which point is the most ideal according to our desired goal.
Requirements for linear programming
Linear programming has a requirement for the problem to be solved properly. These conditions are:
The objective of the problem must be clear.
Define the objective of the problem as clearly as possible. LP usually has two choices of objectives: max and min. Max stands for maximal, meaning you want the maximum value of the constraints you have. Min stands for minimum, meaning you want the minimum value of the constraints you have. The easiest example is to maximize profit or minimize cost.
Have several alternatives.
If you have a profit maximization goal, then you need to have several products as options to increase that profit. LP will not work well if you only want to make a profit from one product. Of course, the answer is “just sell as many as you can”.
LP requires a combination. The simplest example is in the intro above. You have 1000 dollars and want to buy two products. These two products are alternatives. For example, in the cost minimization example, the alternatives you need are the amount of labor, the amount of materials to be purchased, or the number of goods to be produced according to their respective COGS.
There are resource constraints.
Once there are alternatives and objectives, you have to formulate constraints. By constraints, I mean inequalities—inequalities that are like the examples I’ve described. Usually, I notice that if your objective is maximized, then the inequality is dominated by a less than or less than sign.
Example: maximize profit from three products (x, y, and z). x gives a profit of 300, y gives a profit of 400/product, and z gives a profit of 500/product. Then the inequality can be started with the maximum limits of X, Y, and Z that should be sold. Because if you don’t set this maximum limit, LP will give input to maximize profit with the highest profit value of the three products, i.e., LP will definitely give advice to sell as many Z products as possible. Even the x and y values might be 0.
However, if you give a limitation that the value of z cannot exceed a certain number due to production capacity and products x and y must also be produced due to product sustainability and cooperation agreements, for example, then LP will provide more varied results. At the end of this article, as usual, we will practice together.
Note: maximum limit means Z < constant (smaller or less than sign).
Furthermore, if your objective is a minimization objective, then you should multiply the inequality with the more than or greater than sign…
For example, minimize costs. Then the inequality that you have to think about first is what the minimum of each production factor that you use is. Because if there is no minimum limit, LP will not work well because LP will give 0 input for each production factor.
Note: minimum limit means x > constant (greater or more than sign).
Please understand this trick of creating resource boundaries, because there are a lot of LP problems from poorly creating resource boundaries.
There is a relationship between variables.
The alternatives that have been prepared above must have a relationship. You don’t need to worry about multicollinearity issues as discussed in regression in the classical assumption test because they are not used in LP.
For example, x = 2Y; X+Y >15; and others. The aforementioned alternatives, in addition to having restrictions, must also have a hub with each other so that there are values that can be explained by LP.
It can be made into equations or inequalities.
LP is one of the quantitative analyses. Thus, all problems, objectives, and problem boundaries must be quantitatively described. In LP, there are no statements of agreement, disagreement, or doubt allowed. The trick to overcome this is to use a larger or smaller limit or a certain range if you cannot be sure what the limit value of an alternative is.
Linear Programming Main Problem
When you are in college or school, you are usually given a story problem, then you summarize it into an equation and solve it. Or even the problems are already in the form of inequalities and equations, and you are assigned to solve them.
The main problem when you face the real world is finding the story and converting it into an equation. When you decide to do research, there isn’t a single word you’re ready to read. You will be faced with a reality that doesn’t respond if you don’t ask the questions.
This is the most difficult part of LP. How can you record an event with your eyes, ears, and other senses to make it a goal and a problem in several inequalities? The problem of calculating and solving these inequalities can be entrusted with the help of a computer that will help you calculate without any errors.
So what are the tips for dealing with these problems? Start with the proposed requirements that I have described above. What is the purpose of the research? Mention the alternatives, determine the limitations of the alternatives, determine the relationship between the alternatives, and make it in the form of equations or inequalities.
Linear Programming Exercises and Tutorials
I think this is enough for the LP explanation. Let’s practice linear programming. I used the software Lindo, version 6.1. Take a good look at the example problems in the following linear programming tutorial.
AGUNGMASUKSURGA company wants to maximize profits. The products produced are five items. a, b, c, d, and e. The profit from each product is 200, 150, 180, 300, and 100. If a and b are produced at the same time, the output of a is twice as much as that of b. Due to the raw material factor, products c and d (combined) cannot exceed 200. The same problem exists for product A, which cannot exceed 150. The amount of e must be the same as a because product e is a by-product of product a. Because there is a customer agreement, product C must be at least 10.
Determine the value of how many products the AGUNGMASUKSURGA company must make.
Let’s go through them one by one.
- Profit maximization: objective
- The profit of each product is 200, 150, 180, 300, and 100; the goal model is 200a + 150b + 180c + 300d + 100e.
- a output is 2 times of b, meaning a -2b = 0.
- Raw material factors c and d are not more than 200; that is, c+d < 200.
- raw material factor, a cannot exceed 150, meaning a < 150.
- e must be equal to a, meaning e = a or e – a = 0.
- consumer agreement, c is at least 10, meaning c > 10.
- The number in question must be an integer, so it is necessary to add a>0, b>0, d>0, and e>0.
Look at the example above before we put it into Lindo. To maximize the goal, we need constraints, which in this case are limited raw materials. The constraining inequality is generally
Let’s open lindo
Then we write the command:
max
200a + 150b + 180c + 300d + 100e
subject to
a>0
b>0
c>10
d>0
e>0
a-2b=0
c+d<200
e-a=0
a<150
endthe word max describes the goal, subject to is the set of constraints and end states the command has been terminated.
Then select solve – solve. When you are asked “do range analysis?” just click yes.
Wait for the output to come out. The following is the output
From the figure above, it can be determined that LP gives advice to the company:
- The maximum profit value that can be obtained is 115,050.
- This value is obtained by producing a = 150 units, b = 75 units, c = 10 units, D = 190 units, and E = 150 units.
- The reduced cost is 0; it means that the value of the maximization reduction is 0 if a reduction is made in the variable. In this example, I cannot explain the details because everything is worth 0. In principle, reduced cost in maximization is a reduction that must be paid for reducing the value of one unit. In minimization, it is the addition that must be received due to reducing the value of one unit of slack or surplus.
- slack or surplus. The way to read slck or surplus is: the value of more or less constraints given with the results. For example, in this example, a constraint or limit is 0, b = 0, c = 10, d = 0, and e = 0. Because what is produced is a = 150, b = 75, c = 10, d = 190, and E = 150, then all variables other than c are worth a surplus of the value. Meanwhile, variable c is worth 0 because it is in accordance with the limit, meaning that LP takes it according to the specified limit.
- Dual prices: how much additional objective function exists if the constraint is increased by one unit? In this dual price, it can be seen that the c variable is -120. This means that if we increase the constraint variable c by one unit to C > 11, it will lose 120 units of profit.
It does not stop there; Linear Programming in this lindo also gives advice on how much the coefficient value in this case is, which is the profit or product that can be changed. It can be seen that LP wants an increase in profit in all products except variable or product C, because the smallest profit is actually Lindo’s suggestion to decrease (allowable decrease). As we know, Lindo issued 10 units for C because of the constraints that required it (C < 10).
RHS, commonly called the right-hand side, is the term for the value of each constraint in the bottom table. It includes the range or change value that is still allowed to increase (allowable increase) or decrease (allowable decrease). If it has infinity information, it means that the constraint can change any number.
That’s my explanation of the linear programming tutorial. Next time, I hope I can make an example of minimization. Also, open the article about linear programming examples.
Thank you for visiting.
Leave a Reply