Linear programming
Linear programming (LP) is a field of mathematical programming and a widely used method in operations research, dedicated to the theory and methods for solving problems of finding the extremum (maximum or minimum) of a linear function subject to linear constraints.
LP is one of the most powerful and frequently used tools for solving optimization problems in economics, management, planning, logistics, and other fields.
Subject and Purpose
The primary goal of linear programming is to find the best (optimal) way to allocate limited resources to achieve a certain objective, when both the objective and the constraints on resource use can be expressed as linear relationships.
- Linear programming allows for solving such practical problems as:
- Optimal production planning.
- Optimization of transportation flows (the transportation problem).
- Optimal allocation of investments.
- Optimal cutting of materials (the cutting stock problem) and the assignment problem.
Mathematical Formulation of an LP Problem
A standard linear programming problem is formulated as follows:
The goal is to find the values of decision variables that maximize or minimize a linear objective function. These decision variables are subject to constraints in the form of a system of linear equalities and/or linear inequalities. As a rule, a non-negativity condition is added for the decision variables (their values must be greater than or equal to zero), which is often dictated by the physical or economic context of the problem.
Mathematically, this involves working with linear functions and systems of linear equations/inequalities.
Basic Concepts of LP
- Decision Variables (Controllable Variables): The quantities whose values must be determined while solving the problem (e.g., production volumes of different products, the amount of resources allocated to various goals).
- Objective Function: A linear function of the decision variables whose value needs to be maximized or minimized. It quantitatively expresses the problem's goal (e.g., total profit, total costs).
- Constraints: A system of linear equalities and/or inequalities that the decision variables must satisfy. Constraints reflect resource limits, technological requirements, production targets, and other conditions of the problem.
- Feasible Region: The set of all combinations of values for the decision variables that satisfy all the problem's constraints. Geometrically, in a multidimensional space, the feasible region is a convex polyhedron, which may be unbounded or empty.
- Feasible Solution: Any set of variable values that belongs to the feasible region.
- Optimal Solution: A feasible solution at which the objective function reaches its extreme (maximum or minimum) value. If an optimal solution exists, it is always located on the boundary of the feasible region, at one or more of the vertices of the feasible region's convex polyhedron (the fundamental theorem of LP).
Methods for Solving LP Problems
There are several primary methods for solving linear programming problems:
- Graphical Method: Used for problems with two decision variables. It allows for a visual representation of the feasible region and the objective function on a plane and for finding the optimal solution by analyzing the vertices of the feasible region or by moving the level set of the objective function.
- Simplex Method: A universal iterative algorithm developed by George Dantzig. The method sequentially moves from one vertex of the feasible region to an adjacent one, improving the objective function's value at each step until an optimal solution is found. It is the classic and most well-known method for solving LP problems.
- Interior-Point Methods: An alternative class of algorithms that appeared after the simplex method. They move toward the optimal solution through the interior of the feasible region, rather than along its boundaries. These methods are particularly effective for solving very large-scale LP problems.
Duality in Linear Programming
Every linear programming problem (called the primal problem) can be associated with another LP problem, called the dual problem. The primal and dual problems are closely related:
The solution to one problem provides information about the solution to the other. The optimal values of the objective functions in both problems are equal (if they exist). The variables of the dual problem have an important economic interpretation—they correspond to shadow prices (or dual values) of the resources, showing how much the optimal value of the primal problem's objective function would change with a small change in the constraint on the corresponding resource.
Applications of LP
Linear programming has wide applications in:
- Economics and business (production planning, logistics, finance, marketing).
- Industry (optimization of technological processes, inventory management, material cutting).
- Transportation (route and schedule optimization). Agriculture (optimization of crop areas, feed rations).
- The energy sector (optimization of the load on generating capacities).
External links
See also
Literature
- Dantzig, George B. Linear Programming and Extensions. — Princeton University Press, 1963.
- Taha, Hamdy A. Operations Research: An Introduction. — 10th ed. Pearson, 2017.
- Hillier, Frederick S., and Lieberman, Gerald J. Introduction to Operations Research. — 11th ed. McGraw-Hill Education, 2021.