In the 1940s, during World War II, the British government enlisted the help of experts and mathematicians to study how to distribute military resources to achieve the best possible air and ground defense posture. This team of experts was initially named the Operations Research team, a term which later expanded to encompass all research and studies dealing with distribution issues and decision-making.
These studies and research are a form of mathematical programming that links problems of organization, management, industry, agriculture, and transportation with mathematical variables. Specifically, linear programming is a subset of mathematical programming where data is expressed using linear inequalities (first-degree relative to the variables) and assists researchers in making the right decision when aiming for the highest profit or lowest cost, known as the optimal solution.
How is the optimal solution obtained?
The conditions necessary for a mathematical problem to be considered a linear programming
- problem include having a specific objective (maximum profit or minimum loss), expressed through a linear function called the objective function.
- There are decision variables, a large set of variables whose values need to be determined.
- All variables are linked through linear relationship constraints, with the consideration that all variables are positive (non-negativity condition).
Formulating a Linear Programming
Problem A linear programming problem is represented in a table format with rows and columns as follows:
- Determine the number of variables (number of rows), with variables being X1, X2, X3, … Xn.
- Determine the type of objective function (max for maximum profit, or min for minimum loss) and form the objective function using the variables.
- Determine the number of constraints (number of columns), which are linear inequalities relative to the variables, including the non-negativity constraint.
The Simplex Method
The simplex method is the primary technique for solving linear programming problems. It relies on identifying the intersection points between variables and constraints to find the optimal solution. This method requires all constraints to be less than or equal to a certain amount.
Steps to Solve a Linear Programming Problem Using the Simplex Method
1- Convert the problem into standard form by adding slack variables to turn inequalities into equalities.
2- Set the objective function to zero (move all terms to one side).
3- Form an initial table for the objective function and constraints with columns for:
- The First Column: Basic Variables Column (B.V.) This column includes the slack variables that are introduced to the problem’s constraints as part of the solution process. The number of slack variables equals the number of constraints. At the bottom of this column, the objective function is placed.
- The Second Column: The upper part of this column contains all the symbols of the objective function’s variables, while the coefficients of the constraints are placed in the middle part of this column. The coefficients of the objective function variables are placed in the lower part of this column.
- The Third Column: Right Hand Side (RHS) Coefficients Column This column contains all the constraints of the problem and the zero value of the objective function.
- The Fourth Column: Ratio Column This column is used to determine the leaving variable in the simplex method by calculating the ratio of the RHS values to the coefficients of the entering variable.
4- Identify the entering variable: the variable in the column called the pivot column, taking the highest negative value for max objective functions and the highest positive value for min objective functions.
5- Identify the leaving variable: this variable is in the row called the pivot row, obtained by dividing RHS coefficients by the coefficients of the pivot column, then selecting the smallest non-negative number resulting from this division.
6- Determine the pivot element: the number resulting from the intersection of the pivot row and pivot column.
Form a new table, replacing the leaving variable with the entering variable in the basic variables column. The coefficients of the new row are obtained by dividing each coefficient in this row by the pivot element, and the coefficients of the remaining rows are obtained by subtracting the product of the pivot element and the coefficients of the new pivot row, aiming to zero out elements above or below the pivot element.
7- Extract the optimal solution: obtained from the last table
- when, for a max objective function, all z values are either zero or positive,
- and for a min objective function, all z values are either zero or negative.
If the last table does not yield the optimal solution, repeat steps 4 through 7 until the optimal solution is achieved.
Linear programming is utilized in all economic problems aimed at finding the values of economic variables to achieve optimal usage in the presence of financial or technical constraints, or both. Hence, the simplex method, through a series of steps in table form requiring a number of arithmetic operations following a specific methodology, improves the solution until reaching the optimal solution.
Author: Abdel Hamid Al-Diban, Mathematics Teacher at Masarat Initiative
