Linear Programming

United Kingdom/Great Britain:

• Operation research was established prior to and during World War 2

  • Due to resource shortage military leaders invited multidisciplinary teams of scientists and mathematicians + physicists and biologists.

United States:

• The success of the UK OR’s urged the US military to create their own operations analysis groups.

  • Scientific methodology was used for warfare, troop deployment, and supply chains

What was solved?

• Radar & Early warning: OR studied placement and deployment of early warning radar systems on Britain's coasts (to determine which gave the most advanced warning of incoming aircraft)

• Anti Submarine & Convoy Routing: minimize u-boat attacks analyzing depth charge patterns and submarine search strategies, saving supply ships.

• Air Defense & Resource Allocation: OR’s calculated allocating limited firefighter aircraft and anti-aircraft guns across British cities maximizing overall civilian protection under resource constraints. 

Genesis of Linear Programming (Early Precursors)

1. George Stigler (1945) - economist creating the “diet problem” = cheapest combination of food to meet minimum nutritional requirements, VERY FIRST recorded LP-style problems

1. Leonid Kantorovich (1939) - soviet mathematician proposing a solution for resource allocation and production planning using linear equations = developed core LP ideas

1. George Dantzig’s Breakthrough (1947) - Serving as a mathematical advisor for the US airforce mechanized logistical planning; recognizing these situations can be solved through linear equations and inequalities. 

Simplex Method - at LP scale

• Simplex Algorithm: developed by dantzig, finding the optimal solution of any LP problem by moving between corner points (vertices) of the feasible region until the best value is found. 

  • This algorithm made it possible to handle massive logistic problems of the USM.

Evolution of the LP and OR’s

1. Post WW2 Boom: OR methodology spilled to the civil section as businesses and economics recognized maximizing profit or minimizing costs could be modeled using LP.

2. Computing Era: Development of digital computers allowed LP to handle thousands of variables and constraints

3. Modern Day: Now considered foundation across supply chain logistics, finance, manufacturing, healthcare and city planning.

Linear Programming

Meant to determine the best possible outcome, such as maximizing profit  or minimizing cost given a set of limitations represented using linear inequalities.

LP Variables

• Decision Variables: quantities you can actively control or choose

• Objective Function: Equations representing your main goal

• Constraints: real world limitations your solution must satisfy

Steps to solve LP problems (SGIS)

1. Set up the LP model - define decision variables, write objective function, listing constraints as inequalities

2. Graph constraints - plot inequalities.

3. Identify Corner points - locate the vertices following the corner point principle; OS always occurs at a vertex!

4. State your conclusion - plug each corner point into the objective function

Feasible region

• Set of all possible points or combinations of decision variables satisfying every single constraint simultaneously