LINEAR PROGRAMMING: WHAT IS IT FOR, MODELS, CONSTRAINTS, APPLICATIONS - MATHS - 2025

The linear programming is a mathematical method that is used to optimize (maximize or minimize as appropriate) a function whose variables are restricted, as long as the function and constraints are linearly dependent variables.

Generally, the function to be optimized models a practical situation, such as the profit of a manufacturer whose inputs, labor or machinery are limited.

Figure 1. Linear programming is widely used to optimize profits. Source: Piqsels.

One of the simplest cases is that of a linear function to be maximized, which only depends on two variables, called decision variables. It can be of the form:

Z = k ₁ x + k ₂ y

With k ₁ and k ₂ constant. This function is known as the objective function. Of course, there are situations that merit more than two variables for study, being more complex:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

And the constraints are also mathematically modeled by a system of equations or inequalities, equally linear in x and y.

The set of solutions in this system is called feasible solutions or feasible points. And among the feasible points there is at least one, which optimizes the objective function.

Linear programming was independently developed by the American physicist and mathematician George Dantzig (1914-2005) and the Russian mathematician and economist Leonid Kantorovich (1912-1986) shortly after World War II.

The problem-solving method known as the simplex method is the brainchild of Dantzig, who worked for the US Air Force, Berkeley University and Stanford University.

Figure 2. Mathematicians George Dantzig (left) and Leonid Kantorovich (right). Source: F. Zapata.

Linear programming models

The elements necessary to establish a linear programming model, suitable for a practical situation, are:

-Objective Function

-Decision variables

-Restrictions

In the objective function you define what you want to achieve. For example, suppose you want to maximize the profits made from the manufacture of certain products. Then the "profit" function is established, according to the price at which the products are sold.

In mathematical terms, this function can be expressed abbreviated using the summation notation:

Z = ∑k _i x _i

In this equation, k _i are coefficients and x _i are the decision variables.

The decision variables are the elements of the system whose control is had and their values ​​are positive real numbers. In the proposed example, the decision variables are the quantity of each product to be manufactured to obtain the maximum profit.

Finally, we have the constraints, which are linear equations or inequalities in terms of the decision variables. They describe the limitations to the problem, which are known and can be, for example, the amounts of raw material available in manufacture.

Types of restrictions

You can have a number M of limitations, starting from j = 1 to j = M. Mathematically the restrictions are of three types:

1. A _j = ∑ a _ij. x _i
2. B _j ≥ ∑ b _ij. x _i
3. C _j ≤ ∑ c _ij. x _i

The first restriction is of the linear equation type and means that the value A _j, which is known, has to be respected.

The two remaining restrictions are linear inequalities and it means that the known values ​​B _j and C _j can be respected or exceeded, when the symbol that appears is ≥ (greater than or equal to) or respected or not exceeded, if the symbol is ≤ (less than or equal to).

Model example

The fields of application are very diverse, ranging from business administration to nutrition, but to understand the method, a simple model of a practical situation with two variables is proposed below.

A local patisserie is known for two specialties: black forest cake and sacripantine cake.

In its preparation they require eggs and sugar. For the black forest you need 9 eggs and 500 g of sugar, while for the sacripantine you need 8 eggs and 800 g of sugar. The respective sale prices are $ 8 and $ 10.

The problem is: How many cakes of each type must the bakery make to maximize its profit, knowing that it has 10 kilos of sugar and 144 eggs?

Decision variables

The decision variables are "x" and "y", which take real values:

-x: the number of black forest cakes

-y: sacripantine type cakes.

Restrictions

The restrictions are given by the fact that the number of cakes is a positive quantity and there are limited quantities of raw material to prepare them.

Therefore, in mathematical form, these restrictions take the form:

1. x ≥ 0
2. and ≥0
3. 9x + 8y ≤ 144
4. 0.5 x + 0.8y ≤ 10

Constraints 1 and 2 constitute the condition of non-negativity previously exposed, and all the inequalities raised are linear. In restrictions 3 and 4 are the values ​​that must not be exceeded: 144 eggs and 10 kg of sugar.

Objective Function

Finally, the objective function is the profit obtained when manufacturing “x” quantity of black forest cakes plus “y” quantity of sacripantines. It is built by multiplying the price by the quantity of cakes made and adding for each type. It is a linear function that we will call G (x, y):

G = 8x + 10y

Solution methods

The various solution methodologies include graphical methods, the simplex algorithm, and the interior point method, to name a few.

- Graphic or geometric method

When you have a two-variable problem like the one in the previous section, the constraints determine a polygonal region in the xy plane, called the feasible region or viability region.

Figure 3. The feasible region, where the solution of the optimization problem is found. Source: Wikimedia Commons.

This region is constructed using the restriction lines, which are the lines obtained from the inequalities of the restrictions, working only with the equality sign.

In the case of the bakery that wants to optimize profits, the constraint lines are:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0.5 x + 0.8y = 10

All points in the region enclosed by these lines are possible solutions, so there are infinitely many of them. Except in the case where the feasible region turns out to be empty, in which case the problem posed has no solution.

Fortunately, for the pastry problem the feasible region is not empty, we have it below.

Figure 4. The feasible region of the pastry problem. The line with gain 0 crosses the origin. Source: F. Zapata with Geogebra.

The optimal solution, if it exists, is found with the help of the objective function. For example, when trying to find the maximum profit G, we have the following line, which is called the iso-profit line:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

With this line we obtain all the pairs (x, y) that provide a given gain G, so there is a family of lines according to the value of G, but all with the same slope -k ₁ / k ₂, so they are parallel lines.

The optimal solution

Now, it can be shown that the optimal solution of a linear problem is always an extreme point or vertex of the feasible region. So:

If the line closest to the origin has an entire segment in common with the feasible region, it is said that there are infinite solutions. This case occurs if the slope of the iso-profit line is equal to that of any of the other lines that limit the region.

For our pastry, the candidate vertices are A, B, and C.

- Dantzig's simplex method

The graphical or geometric method is applicable for two variables. However, it is more complicated when there are three variables, and impossible to use for a larger number of variables.

When dealing with problems with more than two variables, the simplex method is used, which consists of a series of algorithms to optimize the objective functions. Matrices and simple arithmetic are often used to carry out the calculations.

The simplex method begins by choosing a feasible solution and checking whether it is optimal. If it is, we have already solved the problem, but if it is not, we continue towards a solution closer to optimization. If the solution exists, the algorithm finds it in a few tries.

Applications

Linear and non-linear programming are applied in many fields to make the best decisions in terms of reducing costs and increasing profits, which are not always monetary, since they can be measured in time, for example, if you want to minimize the time necessary to carry out a series of operations.

Here are some fields:

-In marketing it is used to find the best combination of media (social networks, television, press and others) to advertise a certain product.

-For the assignment of adequate tasks to the personnel of a company or factory or schedules to them.

-In the selection of the most nutritious food and at the lowest cost in the livestock and poultry industries.

Solved exercises

- Exercise 1

Graphically solve the linear programming model raised in the preceding sections.

Solution

It is necessary to graph the set of values ​​determined by the system of restrictions specified in the problem:

1. x ≥ 0
2. and ≥0
3. 9x + 8y ≤ 144
4. 0.5 x + 0.8y ≤ 10

The region given by inequalities 1 and 2 corresponds to the first quadrant of the Cartesian plane. Regarding inequalities 3 and 4, we begin by finding the restriction lines:

9x + 8y = 144

0.5 x + 0.8y = 10 → 5x + 8y = 100

The feasible region is a quadrilateral whose vertices are points A, B, C, and D.

The minimum profit is 0, therefore the line 8x + 10y = 0 is the lower limit and the iso-profit lines have slope -8/10 = - 0.8.

This value is different from the slopes of the other restriction lines and since the feasible region is bounded, the unique solution exists.

Figure 5. Graphical solution of exercise 1, showing the feasible region and the solution point C at one of the vertices of said region. Source: F. Zapata.

This solution corresponds to a line of slope -0.8 that passes through any of the points A, B or C, whose coordinates are:

A (11; 5.625)

B (0; 12.5)

C (16, 0)

Optimal solution

We calculate the value of G for each of these points:

- (11; 5.625): G _A = 8 x 11 + 10 x 5.625 = 144.25

- (0; 12.5): G _B = 8 x 0 + 10 x 12.5 = 125

- (16, 0): G _C = 8 x 16 + 10 x 0 = 128

The highest profit is found manufacturing 11 black forest cakes and 5,625 sacripantine cakes. This solution agrees with the one found through the software.

- Exercise 2

Verify the result of the previous exercise by using the Solver function available in most spreadsheets such as Excel or LibreOffice Calc, which incorporate the Simplex algorithm for optimization in linear programming.

Solution

Figure 6. Detail of the solution from exercise 1 through the Libre Office Calc spreadsheet. Source: F. Zapata.

Figure 7. Detail of the solution from exercise 1 through the Libre Office Calc spreadsheet. Source: F. Zapata.

References

1. Brilliant. Linear Programming. Recovered from: brilliant.org.
2. Eppen, G. 2000. Operations Research in Administrative Science. 5th. Edition. Prentice Hall.
3. Haeussler, E. 1992. Mathematics for Management and Economics. 2nd. Edition. Grupo Editorial Iberoamericana.
4. Hiru.eus. Linear programming. Recovered from: hiru.eus.
5. Wikipedia. Linear programming. Recovered from: es. wikipedia.org.