Linear Programming explained

Article by: Patty Mulder

Last update: August 31, 2023

Linear Programming: this article explains Linear Programming in a practical way. Next to what it is, highlights this article also the origin, the algorithms, steps of the process, and a calculation example. After reading it, you will understand the basics of this mathematical based decision making tool. Enjoy reading!

What is Linear Programming?

Linear programming is a mathematical method to determine the optimal scenario. The theory of linear programming can also be an important part of operational research. It’s frequently used in business, but it can be used to resolve certain technical problems as well.

For example, you can use it to see which combination is most profitable or which mode of transport is cheapest. That’s how linear programming leads to optimisation.

In mathematics, linear programming is also a method for solving so-called linear programming or optimisation problems, in which both the final goal and the conditions are all linear. The term ‘programming’ has nothing to do with computer programs by the way; it has to do with planning.

Origin

Linear programming was first mentioned in 1939 by Russian mathematician (and later Nobel Prize winner) Leonid Kantorovich in his publication ‘The Mathematical Method of Production Planning and Organisation’.

In 1947, American mathematician George Dantzig further expanded on it. He used the linear goal function for solving planning problems. In doing so, he introduced a clear separation between the optimisation goal and the means to resolve the planning problem.

The American Air Force was one of the ones to apply Dantzig’s theory to improve logistics and the use of military resources.

Linear Programming Algorithms

Algorithms are used frequently in linear programming. An algorithm is a finite set of consecutive instructions that lead to an intended goal from a given starting condition and that are used to solve a problem. The objective of an algorithm can be anything with a clear result.

In general, algorithms contain steps that are repeated (iteration) or that require decisions in order to complete the task. Linear programming uses algorithms to optimise the result based on a number of limitations.

These linear limitations often lead to the feasible region, which is also referred to as a convex polyhedron. This feasible region is where the optimal options can be found that have been created by mathematical calculations.

In addition, the linear objective function implies that the optimal solution can only occur on the edges of the feasible region.

Steps of the Linear Programming model

In order to apply the linear model, it’s a good idea to use the following step-by-step plan:

Step 1 – define the decision variables

Which choices and/or possibilities (variables) exist that decisions can be based on?

Step 2 – define the objective function

What’s the objective that you want to achieve? This could be the highest possible turnover or the lowest possible investment, for instance.

Step 3 – define the limiting conditions

These are all the limitations that influence the decisions that can be made. It helps to put the limiting conditions in a table to create a visual overview.

Step 4 – draw the feasible region

This is the region in which all previously set conditions are met. If you stay within this feasible area, the objective will have been achieved and you can make the optimal profit, for instance.

Step 5 – calculate the combination for optimal turnover

In this part, the optimal turnover is mathematically calculated. It can be found on one of the points on the edges of the feasible region. This can be calculated based on a system of mathematical equations.

Step 6 – draw the profit line

With this last step, you can calculate exactly what the total maximum turnover or profit is when choosing a specific option.

Linear Programming calculation example

Say a wine salesman has the following products to create nice gift baskets: 50 bottles of red wine, 80 bottles of white wine and 80 bottles of rosé. With these, he can create two kinds of baskets that will generate significant turnover for him.

The first gift basket is the rosé basket with 10 bottles of red wine, 10 bottles of white and 20 of rosé. This basket can be sold for € 140.
The second basket is the white wine basket with 10 bottles of red wine, 20 white and 10 rosé for € 150.

The objective is to make the highest possible profit from the sale, so the salesman has to know how many baskets he has to sell of each type. He follows the previously mentioned step-by-step plan:

1. the decision variables are X = number of rosé baskets and Y = number of white wine baskets.

2. his objective is to make as much profit as possible. This is called the profit function. Turnover = 140 X (€ 140 per rosé basket) + 150 Y (€ 150 per white wine basket). In a mathematical formula that is P (Profit function) = 140X + 150Y

3. the limiting conditions are the number of bottles of wine that the wine salesman has available and the following:

4. the limiting conditions are drawn on a Y axis and an X axis in a graph, showing the feasible region. This is the final region in which all the previously set conditions are met.

5. finally, the combination of white wine baskets and rosé baskets for optimal turnover is calculated. This can be found on one of the points of the feasible area, based on a series of equations.

6. in the final step, the profit line is drawn in the graph that shows the maximum turnover that can be achieved with the sales of the white wine baskets and the rosé baskets.

It’s Your Turn

What do you think? Is Linear Programming applicable in your personal or professional environment? Do you recognize the practical explanation or do you have more suggestions? What are your success factors for good decision making?

Share your experience and knowledge in the comments box below.

More information

Dahleh, M. A., & Diaz-Bobillo, I. J. (1995). Control of uncertain systems: a linear programming approach. Englewood Cliffs: Prentice Hall.
Dantzig, G. B. (1955). Upper bounds, secondary constraints, and block triangularity in linear programming. Econometrica: Journal of the Econometric Society, 174-183.
Kantorovich, L. V. (1960, 1939). Mathematical methods of organizing and planning production. Management Science, 6(4), 366-422.
Murty, K. G. (1983). Linear programming (Vol. 57). New York: Wiley.

How to cite this article:
Mulder, P. (2018). Linear Programming. Retrieved [insert date] from Toolshero: https://www.toolshero.com/decision-making/linear-programming/

Original publication date: 06/18/2018 | Last update: 08/31/2023

Add a link to this page on your website:
<a href=”https://www.toolshero.com/decision-making/linear-programming/”>Toolshero: Linear Programming</a>

Did you find this article interesting?

Your rating is more than welcome or share this article via Social media!

Average rating 4 / 5. Vote count: 4

No votes so far! Be the first to rate this post.

Article by:

Patty Mulder

Patty Mulder is an Dutch expert on Management Skills, Personal Effectiveness and Business Communication. She is also a Content writer, Business Coach and Company Trainer and lives in the Netherlands (Europe).
Note: all her articles are written in Dutch and we translated her articles to English!