Linear Programming
Linear programming is a mathematical method used to optimize a specific process by either maximizing or minimizing an outcome while adhering to certain constraints. It is commonly employed by businesses to enhance productivity, profitability, and resource management, such as minimizing costs for labor and materials. The method gained prominence during World War II, thanks to mathematician George B. Dantzig, who developed it to solve logistical problems in military operations. Dantzig's innovations led to the creation of the simplex algorithm, which facilitated complex calculations that were initially done manually and later transitioned to computer-based solutions.
Linear programming involves defining variables and writing equations that reflect the constraints of a problem. These constraints can include factors such as budget limits or resource availability, which delineate a feasible region where solutions can be found. The ultimate solutions are typically located at the corners of this feasible region, determining the best ways to allocate resources or make decisions. Today, various industries, including airlines, agriculture, and healthcare, utilize computer programs to implement linear programming, enabling efficient solutions to real-world challenges like ticket pricing and dietary planning.
Linear Programming
Linear programming is a mathematical method for determining how to maximize or minimize a specific process when one or more restrictions on the process outcome exist. It is sometimes called "linear maximization." Linear programming is frequently used by businesses that want to determine important factors such as how to maximize output or profit or how to minimize labor and materials costs. Linear programming has been in use since the mid-twentieth century. In the decades since, it has been enhanced with computer programs that allow for more complicated processes to be examined with relative ease.
Background
The process of linear programming began as a largely manual operation during World War II (1939–1945). George B. Dantzig was an American mathematician working in the Pentagon during the latter part of the war. He used his mathematical skills to design programs and plans for operations that made the most sense in terms of the time, manpower, and other available resources.
After the war ended, Dantzig continued to serve at the Pentagon as the mathematical adviser to the comptroller for the US Air Force. He was asked to plan ways to maximize training, deployment, and supply logistics. Dantzig's first efforts were accomplished using analog calculators and other manual devices, as computers capable of doing such calculations had not yet been invented.
Dantzig determined that his model for accomplishing the tasks he was assigned needed to be general enough to be used for multiple purposes and easy enough to adapt and modify to meet changing needs. It needed to accommodate several variables and had to be able to handle the large-scale variables inherent to moving and supplying military units. The process had to be capable of not only determining values for the variables but also determining the best way to maximize or minimize certain specific aspects of it.
Consider the following example. The army receives one hundred new recruits and has to assign them to new positions among four units. Of the one hundred recruits, fifty are very good with artillery, twenty-five are good mechanics, and twenty-five are of average skill in both. The linear programming process provides a way to determine how to assign the recruits to one of the units to make the best use of each one's skills.
Between 1947 and 1949, Dantzig worked on his programming until he developed what came to be known as the simplex algorithm. One of the first problems he solved was for the Bureau of National Standards, which wanted a diet with the lowest possible food cost. The programming, which had nine equations with seventy-seven variables, took nine workers four months to solve on calculators. A similar algorithm is now built into the standard Excel spreadsheet and can be solved almost instantly.
By 1946, computers were beginning to be available, and Dantzig's office in the Pentagon was equipped with one by the early 1950s. At that point, linear programming switched from a manual operation to a computerized function. The oil industry was among the first to use linear programming; industry leaders wanted to know the best way to blend petroleum products to provide a product that met specific performance requirements at the lowest possible cost.
Overview
While nearly all linear programming problems are handled by computers today, the steps are similar to the process Dantzig used in the 1940s and 1950s. The first step to manually solving the problem is to define the variables. For example, if a coat manufacturer wants to sell a coat for no more than $100 and make a 40 percent profit, he or she may use linear programming to determine the maximum cost to make the coat. The manufacturer would need to know the labor cost to make each coat and how much material the coat pattern requires. The variable would be the amount of material. Next, it's necessary to write an equation defining the linear problem, or the specific function to be maximized or minimized and the conditions that are related to this. These are called linear inequalities. Some of these linear inequalities place limits on the final outcome. In this case, the limits would be the maximum price of the coat minus the labor cost, materials, and profit margin. These are called problem constraints. One of the problem constraints in this example would be the maximum price of the coat, and it would be written ≤100 (less than or equal to 100).
When computed manually, linear programming uses a graph to chart the equation and its solution. The points that define the answers on this chart define an area known as the feasible region. Once this is known, the fundamental theorem of linear programming can be applied. The theorem says that when a linear programming problem can be solved, the solution will be at a corner point of the feasible region or on a line between these two corner points. When used to find a maximum value, the larger corner point value is the answer. When used to find a minimum value, the lower corner point value provides the solution. This provides a geometric solution to the problem. Linear programming problems can also be solved using algebraic equations.
In the twenty-first century, real-world linear programming questions are generally resolved with the assistance of computer programs designed to perform specific functions. For instance, the airline industry uses linear programming to determine how many tickets to sell in advance, how many to hold for last-minute purchases, and how much each ticket should cost. The multimillion-dollar diet industry uses linear programming to determine how much of each type of food a person should eat within the other parameters of a diet (high protein, low gluten, low sugar, low fat, etc.) to meet a certain calorie requirement and lose a certain amount of weight each week. The military and other government agencies use linear programming for budgeting, supply acquisition, and other purposes. Other industries that make use of linear programming include mass transportation, agriculture, and amusement parks.
Bibliography
Adelgren, Nathan, and Akshay Gupte. "Branch-and-Bound for Biobjective Mixed-Integer Linear Programming." INFORMS Journal on Computing, vol. 34, no. 2, 21 Oct. 2021, DOI: 10.1287/ijoc.2021.1092. Accessed 19 Jan. 2023.
Ferguson, Thomas S. "Linear Programming: A Concise Introduction." University of California Los Angeles, www.math.ucla.edu/~tom/LP.pdf. Accessed 27 Jan. 2017.
"George Dantzig, 90; Created Linear Programming." Los Angeles Times, 22 May 2005, articles.latimes.com/2005/may/22/local/me-dantzig22. Accessed 27 Jan. 2017.
Golden, Bruce. "The Unexpected Power of Linear Programming: An Updated Collection of Surprising Applications." Annals of Operation Research, 21 Sept. 2024,
doi.org/10.1007/s10479-024-06245-5. Accessed 18 Nov. 2024.
Glydon, Natasha. "Linear Programming." Regina University, mathcentral.uregina.ca/beyond/articles/LinearProgramming/linearprogram.html. Accessed 27 Jan. 2017.
Kulkarni-Thaker, Shefali. "The Diet Problem." The OR Café, University of Toronto, 14 Jan. 2013, org.mie.utoronto.ca/blog/?p=45. Accessed 27 Jan. 2017.
"Linear Programming." High School Operations Research, www.hsor.org/what‗is‗or.cfm?name=linear‗programming. Accessed 27 Jan. 2017.
"Linear Programming." IBM, www-01.ibm.com/software/commerce/optimization/linear-programming/. Accessed 27 Jan. 2017.
"Linear Programming." Richland University, people.richland.edu/james/lecture/m116/systems/linear.html. Accessed 27 Jan. 2017.