A complete explanation of linear programming

There are many methods for making decisions, such as qualitative qualitative methods, which depend on estimation and experience, and quantitative methods, which depend on data and equations. The appropriate method for decision-making depends on the nature of the problem and the data that is available or that can be provided at an appropriate time and cost, and qualitative and quantitative methods are often involved at the same time. Personal. There are many quantitative methods such as simulation, inventory models, forecasting, and linear programming.

The word model has many uses, all of which mean that we use something simple to express the original problem. A miniature model of a large machine is called a model, a laboratory model of a large problem is called a model, a computer simulation model of a complex factory is called a model, and mathematical equations that express something are called a model. The model may be mathematical, physical, electronic, and so on. For example, we can use the following model to express the profitability of the enterprise:

Enterprise profitability = number of pieces sold x profitability of the piece

This is a simple form that we can use to decide which lots we want to sell for a minimum profit. Sometimes the influencing factors are not known, and in this case we are working to develop a model by using some tools such as determining the regression analysis or using laboratory experiments to link the variables together and reach a mathematical model.

linear programming

There is a quality of decisions aimed at either maximizing a variable such as profitability or minimizing a variable such as cost or time. in a specified quantity. If all these things can be expressed in linear equations, then this issue can be solved by solving a set of equations, which is known as Linear Programming.

What does linear equation mean? A linear equation is an equation that does not contain a variable multiplied by itself or another variable. The following equations are considered linear equations:

x + y = 500

Q < 1000

3h + 2y + 5p > 300

All of these equations, when drawn, express a straight line, and this is the meaning of Lineare

The following equations are nonlinear:

x y +1 = 100

x 2 < 100

3 x 2 + x 2 = 950

These equations express curved lines and are therefore called “non-linear”.

Linear programming is a decision-making technique used when the problem can be expressed through a set of linear equations, which consist of an equation that aims to maximize or minimize one or more variables and an equation or equations that express some constraints. Linear programming is currently being solved using simple programs such as Microsoft Excel, which makes it an easy way. Despite this, many organizations that need to use linear programming on an ongoing basis do not use it for several reasons, such as: Managers’ desire to make decisions based on personal discretion This is due to the maximization of their role (theoretically), and the lack of knowledge of many managers about linear programming, and the difficulty of applying linear programming in some practical problems because it requires non-linear programming.

Example: A company produces two products, A and B, and the profitability of each product is 100 and 120, respectively, and both products are manufactured using two machines, and the available time on each of them is 1500 hours annually, and it takes 2 hours and 4 hours to manufacture product A and B on the first machine, respectively. , and it takes 2 and a half hours and 3 hours to manufacture product A and B on the second machine, respectively. It is required to determine the quantity of production of each product in order to achieve the highest profitability. It is noted that we implicitly assume that there is a high demand for each product.

We can formulate the problem as follows:

Profitability = 100 x + 120 y

Limitations:

Running the first machine: 2h + 4h <= 1500

Second machine run: 2.5h + 3y <= 1500

The profitability rate is called the Objective Function, and it aims here to maximize profitability. As for the other equations, they are equations or functions (plural of functions) Constraints, as x and y are called decision variables, which are the variables that the decision-maker wants to determine their value. This is a linear programming issue, and this issue has many similarities.

How can these equations be solved to determine the values of x and y? There are two ways, the first is graphic, which is to draw these equations to determine the values of x and y, and the second is to solve by computer using any program such as Excel. The second method is suitable for solving all linear programming problems, whether easy or more complex. The first method is suitable for simple problems only. Therefore, we will focus on how to use Excel, knowing that using other programs will not differ much.

You can put the problem in Excel in any form that makes you comfortable, and I will present the form that I see as simple because it is similar to the form of equations.

I recorded each equation on a line. On line No. 44, I recorded the profitability of each product. On line No. 7 and 8, I recorded the formula for the operating hours of each machine. But where are x and y which are the decision variables? We will assume that x is cell B5 and y is cell C5. Now we have to complete the equations using a function from Excel called sumproduct, which sums the product of multiplying several cells together. In column F, we record the multiplication of x and y in its coefficients in all equations. In F5 we record the sum of 100x + 120y, in F7 we record the sum of 2x + 4y, and in F8 we record the sum of 2.5x + 3y. Note that B5:C5 represents x and y, and B4:C4 represents the profitability of each product, which is 100 and 120. We could have used =B5*B4+C5*C4 and so on, but using sumproduct is easier, especially when there are many variables, as it makes us multiply a group of cells As it corresponds to it, we do not write the names of all the cells, but we write only the first and the last cell.

We now have to make these numbers transform

For a linear programming problem in Excel, and therefore we have to use the so-called Solver method, which may not be added to Excel, and you can add it as follows:

1- Microsoft 2007 and 2010: File…..Options……Add-ins, then choose Go at the bottom of the page next to Manage Excel Add-ins

Then choose the Solver Add-in and I advise you to choose the Analysis Toolpak because you will need it for some statistical methods.

2- Pre-2007 Microsoft: From the Tools menu, select Add-ins, then Solver Add-in.

This process is done once and does not need to be repeated as the solver remains available on your device.

We go back to the problem, so we choose the data menu, and we find the solver on the right.

We choose solver and a window appears in which we can enter equations:

Then we enter the cell that contains the objective function, which is here F5, and then select the cells that Excel will change to maximize the objective function, which is here B5 and C5, i.e. x and y,

Then we enter the constraint equations by clicking on Add on the right, and a window appears that we fill in as follows:

Then select Simplex in the Select Solving Method. Then we press Solve, and the solution appears to us like this:

We press OK, and all the data appears as follows:

This means that we can achieve the highest profitability if we produce 375 pieces of product A and 187 pieces of product B.

The steps in Excel may seem long and difficult, but when they are repeated, it will take a few seconds, so the matter is easy, and the difficulty in using linear programming is in forming the model, that is, the equations, and not in using the computer.

Learn more about the benefits of linear programming, as well as its uses in business.

Example: A person owns a shop and trades in only three commodities A, B, and C. And he wants to decide the quantity that he buys of each commodity in the light of the following:

1- The purchase price of each commodity, respectively: 10, 12, 9

2- The current stock of each commodity, respectively: 30, 20, 70

3- The owner specified the maximum stock for each commodity according to market demand as follows: 200, 220, 270

4- There is a relationship between the sales of A and B, so their sum should not exceed 350

5- The owner wants the stock of any commodity after purchase not to be less than 70 pieces in order to remain competitive in the three products

6- The liquidity available for purchase is: 5,500 pounds

7- The selling price of each commodity, respectively: 14, 15, 12

We begin by formulating the problem as follows:

Q: The number of pieces that he will buy from the product a

Y: The number of pieces that he will buy from the product b

A: The number of pieces he will buy from the product c

The objective function is to maximize profitability as follows:

Profit = profitability of each piece x number of pieces = 4 x + 3 p + 3 p

Note that profitability = selling price – buying price ……. (neglecting expenses for simplicity)

Limitations:

Minimum purchase A = 70 -30 = 40

Maximum purchase A = 200 – 30 = 170

40 => x =< 170

Minimum purchase b = 70 -20 = 50

Maximum buy b = 220 – 20 = 200

50 => p =< 200

Minimum purchase c = 70 -70 = 0

Maximum buy c = 270 – 70 = 200

0 => p =< 200

The sum of producers A and B should not be more than 350. That is, (X + stock A + Y + stock B) should not be more than 350

x + 30 + y + 20 =< 350

any

x + y =< 300

The purchase price of each product should not exceed 5,500 pounds

10h + 12h + 9h =< 5500

We begin to put the problem in Excel as follows:

Note that cells B5, C5, D5 are X, Y, Z. The minimum and maximum purchase for each item has been set in two steps for clarity and so that the equations do not get mixed up. Column G shows the equations used, using the Show Equations feature, but their value will initially be zero.

We start with the solution using Solver, and if it is not visible on the screen when choosing the Data menu, you must add it as in the previous article.

Note that the restrictions are put together as we can combine several entries if they are consecutive in order and they all contain the same comparison such as > or <. Each one can be set separately as you like.

We get the solution as follows:

The best solution is to buy 170 from A, 130 from B, and 200 from C. Note that all restrictions are met. Thus, we have obtained the optimal solution.

We assume that we had another limitation, which is the storage capacity that does not exceed 600 cubic meters, noting that the volume of all goods, respectively, is: 1, 1.2, and 1.1 cubic meters.

We can add this constraint as follows: (x + 30) + 1.2 (y + 20) + 1.1 (p + 70) <= 650

any:

x + 1.2 p + 1.1 p <= 519

Thus, the problem and solution becomes as follows:

Note that the quantity of p has decreased to 107, while x and p have remained the same as in the first case. Why? In order for the storage capacity to be used to achieve the highest profit, note that B has a larger storage volume than C, while their profitability is equal. You might ask why not buy more than one p? Because the limit is 200. As you can see, linear programming helps us to choose the optimal solution, taking into account many and various constraints.

What are the limitations of this solution? That is, if it changes, the solution changes? Are all restrictions or some of them? We can find out by choosing the solution report Answer as follows:

The report appears to us on a separate page called Answer Report 1, as follows:

The equations in rows: 7, 9, 15 are the Binding ruler and are the equations: maximum x, z and storage space. Is this correct? Yes, we will buy the maximum amount of storage space, and we will use all the storage space. This means that any change in these conditions, even by an integer amount, means a direct change in the solution.

What about the rest of the conditions? It is not ruling, meaning that if it changes, the solution will not be affected, but within certain limits. If the change increases, it will become influential in the solution. What is the meaning of this? Look at the column on the far right, it is labeled Slack which means not serious or it is neglected, and the value in front of each condition means that this condition is not effective until it is changed by this value. For example, the minimum condition for p in row 11 is ineffective unless it is increased by more than 57.5, and if you try to change it by less than that, the solution will not be affected, but try to increase it by 59, for example, and you will find the value of p has become 109And p will change to 198. Likewise, liquidity does not affect unless it is reduced by more than 710 pounds. This is another characteristic of linear programming.