Linear Programming. Methods and Applications

Many economic and industrial phenomena can be modeled by mathematical systems of linear inequalities and equalities, leading to linear optimization problems. In these linear optimization problems, the aim is to minimize or maximize a linear function under linear constraints on the problem variables. This is often referred to as linear programming (or linear program), the term referring to the idea of organization and planning associated with the nature of the phenomena being modeled. The term was introduced during the Second World War and systematically used from 1947 onwards, when G. Dantzig invented the simplex method for solving linear programming problems. Industrial applications of linear programming are widespread, for example in the oil industry (for oil extraction, refining and distribution), the food industry (optimal composition of ingredients for ready-made meals, etc.), the iron and steel industry (optimal composition of steels), the paper industry (cutting problems), transport (aircraft flight planning, minimizing transport costs, etc.) and networks (optimization of communication networks).

This article introduces the fundamental properties and concepts of linear programming and then presents the simplex algorithm for solving a linear program. The simplex algorithm is implemented using two methods: the dictionary method and the array method. The dictionary method provides a clear understanding of the simplex procedure, while the array method is more algebraic and leads to the actual implementation of the simplex algorithm. A MATLAB code based on the array method is provided in the appendix. An application of the simplex method to sensitivity analysis of a linear program is also presented, along with an introduction to duality in linear programming.