Overview
![](/assets/images/picto-drapeau-france-3a76576a5d60a512053b4612ab58dae5.png)
ABSTRACT
This paper presents the basic concepts of linear programming, which consists in minimizing or maximizing a linear objective function with linear inequality or equality constraints on the variables of the system. The properties of solutions of a linear programming problem are established and the simplex method for solving a linear programming problem is presented in detail. Throughout the paper, a simple example of a production problem serves as a reference to illustrate the various concepts and methods developed. A MATLAB code of the simplex method is supplied, and some linear programming solvers are listed with an example of use. The data sensitivity of the solution of a linear program is analyzed, and the concept of linear programming duality is introduced.
Read this article from a comprehensive knowledge base, updated and supplemented with articles reviewed by scientific committees.
Read the articleAUTHOR
-
Jean-François SCHEID: Senior Lecturer in Applied Mathematics - Institut Elie Cartan de Lorraine & TELECOM Nancy - University of Lorraine, Nancy, France
INTRODUCTION
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.
Exclusive to subscribers. 97% yet to be discovered!
You do not have access to this resource.
Click here to request your free trial access!
Already subscribed? Log in!
![](/assets/images/logo-eti-286623ed91fa802ce039246e516e5852.png)
The Ultimate Scientific and Technical Reference
KEYWORDS
linear programming | simplex method | MATLAB
This article is included in
Mathematics
This offer includes:
Knowledge Base
Updated and enriched with articles validated by our scientific committees
Services
A set of exclusive tools to complement the resources
Practical Path
Operational and didactic, to guarantee the acquisition of transversal skills
Doc & Quiz
Interactive articles with quizzes, for constructive reading
Linear programming
Bibliography
Software tools
GLPK – Gnu Linear Programming Kit (Linux version) [Software]
LPSOLVE, (multi-platform version under LGPL license)
IBM ILOG CPLEX Optimization Studio (multi-platform version)
MATLAB – Optimization toolbox
CMPL –
Websites
COIN-OR: COmputational INfrastructure for Operations Research
ROADEF: French Society for Operational Research and Decision Support
http://www.roadef.org/content/index.htm
ENSTA Operations...
Exclusive to subscribers. 97% yet to be discovered!
You do not have access to this resource.
Click here to request your free trial access!
Already subscribed? Log in!
![](/assets/images/logo-eti-286623ed91fa802ce039246e516e5852.png)
The Ultimate Scientific and Technical Reference