Linear programming

Linear optimization in a 2-dimensional polytope

3dpoly

Leonid Kantorovich 1975

JohnvonNeumann-LosAlamos

linear programming feasible region farmer example

Linear Programming Feasible Region

Linear programming (LP) is a method to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships. It is a special case of mathematical optimization. Linear programming is a way to optimize operations within certain constraints. It involves making the best possible allocation of resources to achieve a desired outcome, such as minimizing costs or maximizing profits, under given constraints.

Overview

Linear programming involves two key components: the objective function and the constraints. The objective function is a linear equation that represents the goal of the problem, such as maximizing profit or minimizing cost. The constraints are a series of inequalities that represent the limitations or requirements of the problem. These constraints could include resource limitations, budgetary constraints, or any other restrictions that need to be considered.

Mathematical Formulation

The general form of a linear programming problem can be expressed as:

Maximize (or Minimize): \(Z = c_1x_1 + c_2x_2 + \cdots + c_nx_n\)

Subject to: \[ \begin{align*} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n &\leq b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n &\leq b_2 \\ &\vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n &\leq b_m \\ \end{align*} \] and \(x_1, x_2, \ldots, x_n \geq 0\).

Here, \(Z\) is the objective function to be maximized or minimized, \(c_1, c_2, \ldots, c_n\) are the coefficients of the objective function, \(a_{11}, a_{12}, \ldots, a_{mn}\) are the coefficients of the constraints, and \(b_1, b_2, \ldots, b_m\) are the right-hand side values of the constraints.

Solving Methods

The most common method for solving linear programming problems is the Simplex algorithm, developed by George Dantzig in 1947. The Simplex algorithm is an iterative procedure that systematically tries vertices of the feasible region defined by the constraints, to find the optimal value of the objective function. Other methods include the Interior Point Method, which is more efficient for some large-scale linear programming problems.

Applications

Linear programming is widely used in various fields such as business, economics, engineering, transportation, and military operations for decision making, resource allocation, production planning, scheduling, and logistics.

History

The development of linear programming has been attributed to the work of George B. Dantzig in the 1940s. However, the concept of linear programming was also independently studied by Leonid Kantorovich in the Soviet Union during the same period. Their work laid the foundation for the widespread application of linear programming in economics, military, and planning.

See Also

• Mathematical optimization
• Simplex algorithm
• Interior Point Method
• Dual linear programming