- Also known as:
- mathematical programming
- Key People:
- Richard Karp
optimization
-
What is optimization in mathematics?
Optimization in mathematics is a collection of principles and methods used to solve quantitative problems across various disciplines. It grew from the recognition that different disciplines share common mathematical elements, allowing problems to be formulated and solved using a unified approach.
Optimization problems consist of:
* An objective function to be maximized or minimized
* Variables that can be manipulated to optimize the objective
* Constraints that restrict the values of the variablesAn important class of optimization is linear programming, where a linear function is maximized or minimized subject to constraints expressed as inequalities. Another class is nonlinear programming, where the objective or some constraints are nonlinear functions. The simplex method is a standard algorithm used to solve optimization problems on computers.
3 Britannica SourcesCreated from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles. -
What is an objective function in optimization?
In optimization, an objective function is a single numerical quantity that you want to maximize or minimize. This could be anything from a company's profits or production costs to the arrival time of a vehicle or the vote share of a political candidate.
For example, a factory produces (x_1) of a commodity of the first type and (x_2) of the second type. If the profit on the second type is twice that on the first, then the objective function is (x_1 + 2x_2).
Constraints are restrictions on the values that variables can take, like not using more resources than available. The goal is to find the values of the variables that optimize the objective function while satisfying all constraints.
1 Britannica SourceCreated from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles. -
What are constraints in mathematical optimization?
In mathematical optimization, constraints are restrictions on the values that variables can assume within an optimization problem. These constraints define the feasible region within which the solution must lie. For example, a manufacturing process cannot use more resources than are available.
Optimization problems involve maximizing or minimizing an objective function, which represents a numerical quantity, using variables whose values can be manipulated. Constraints are a fundamental element, setting boundaries based on real-world limitations.
An important class of optimization is linear programming, where a linear function is optimized subject to constraints expressed as inequalities. In nonlinear programming, either the objective or some of the constraints are nonlinear functions.
2 Britannica SourcesCreated from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles. -
What are the different types of optimization problems?
In mathematics, optimization problems involve maximizing or minimizing a numerical quantity called an objective function. This is achieved by manipulating variables within a set of constraints.
Optimization problems can be categorized based on their mathematical properties:
* Linear Programming (LP) LP is used to optimize a linear objective function, where the variables are real numbers constrained by linear equalities and inequalities.
* Nonlinear Programming In nonlinear programming, the variables are real numbers, but the objective or constraints are nonlinear functions.
* Stochastic Programming The objective function or constraints depend on random variables.
* Network Optimization Optimizes the flow through a network.
* Combinatorial Optimization Solutions are found from a finite set of possible values.2 Britannica SourcesCreated from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles. -
How does linear programming solve optimization problems?
Linear programming is a mathematical modeling technique used to maximize or minimize a linear function subject to constraints. The goal is to find the optimal value (largest or smallest) of a linear expression, known as the objective function, while adhering to a set of constraints expressed as inequalities.
This method assumes linear relationships between demand and availability, meaning variables are not raised to powers other than 1. Linear programming is effective for resource allocation problems, especially in industrial production systems. It provides algebraic techniques using equations or inequalities to optimize the objective function.
2 Britannica SourcesCreated from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles. -
How is optimization used in real-life situations?
Optimization is a collection of mathematical methods and principles used to solve quantitative problems across various disciplines. It identifies the best possible solution from all feasible solutions.
Optimization is used to maximize or minimize a single numerical quantity called the objective function. The objective function may be profit, cost, time of arrival, or vote share. The values of variables are manipulated to optimize the objective within a set of constraints. For example, logistics staff use optimization for production scheduling to balance product demand with plant capacity and the availability of inputs.
2 Britannica SourcesCreated from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles.
optimization, collection of mathematical principles and methods used for solving quantitative problems in many disciplines, including physics, biology, engineering, economics, and business. The subject grew from a realization that quantitative problems in manifestly different disciplines have important mathematical elements in common. Because of this commonality, many problems can be formulated and solved by using the unified set of ideas and methods that make up the field of optimization.
The historical term mathematical programming, broadly synonymous with optimization, was coined in the 1940s before programming became equated with computer programming. Mathematical programming includes the study of the mathematical structure of optimization problems, the invention of methods for solving these problems, the study of the mathematical properties of these methods, and the implementation of these methods on computers. Faster computers have greatly expanded the size and complexity of optimization problems that can be solved. The development of optimization techniques has paralleled advances not only in computer science but also in operations research, numerical analysis, game theory, mathematical economics, control theory, and combinatorics.
Optimization problems typically have three fundamental elements. The first is a single numerical quantity, or objective function, that is to be maximized or minimized. The objective may be the expected return on a stock portfolio, a company’s production costs or profits, the time of arrival of a vehicle at a specified destination, or the vote share of a political candidate. The second element is a collection of variables, which are quantities whose values can be manipulated in order to optimize the objective. Examples include the quantities of stock to be bought or sold, the amounts of various resources to be allocated to different production activities, the route to be followed by a vehicle through a traffic network, or the policies to be advocated by a candidate. The third element of an optimization problem is a set of constraints, which are restrictions on the values that the variables can take. For instance, a manufacturing process cannot require more resources than are available, nor can it employ less than zero resources. Within this broad framework, optimization problems can have different mathematical properties. Problems in which the variables are continuous quantities (as in the resource allocation example) require a different approach from problems in which the variables are discrete or combinatorial quantities (as in the selection of a vehicle route from among a predefined set of possibilities).
" height="20" alt="HEW Logo">
An important class of optimization is known as linear programming. Linear indicates that no variables are raised to higher powers, such as squares. For this class, the problems involve minimizing (or maximizing) a linear objective function whose variables are real numbers that are constrained to satisfy a system of linear equalities and inequalities. Another important class of optimization is known as nonlinear programming. In nonlinear programming the variables are real numbers, and the objective or some of the constraints are nonlinear functions (possibly involving squares, square roots, trigonometric functions, or products of the variables). Both linear and nonlinear programming are discussed in this article. Other important classes of optimization problems not covered in this article include stochastic programming, in which the objective function or the constraints depend on random variables, so that the optimum is found in some “expected,” or probabilistic, sense; network optimization, which involves optimization of some property of a flow through a network, such as the maximization of the amount of material that can be transported between two given locations in the network; and combinatorial optimization, in which the solution must be found among a finite but very large set of possible values, such as the many possible ways to assign 20 manufacturing plants to 20 locations.
Linear programming
Origins and influences
Although widely used now to solve everyday decision problems, linear programming was comparatively unknown before 1947. No work of any significance was carried out before this date, even though the French mathematician Joseph Fourier seemed to be aware of the subject’s potential as early as 1823. In 1939 a Russian mathematician, Leonid Vitalyevich Kantorovich, published an extensive monograph, Matematicheskie metody organizatsi i planirovaniya proizvodstva (“Mathematical Methods for Organization and Planning of Production”), which is now credited with being the first treatise to recognize that certain important broad classes of scheduling problems had well-defined mathematical structures. Unfortunately, Kantorovich’s proposals remained mostly unknown both in the Soviet Union and elsewhere for nearly two decades. Meanwhile, linear programming had developed considerably in the United States and Western Europe. In the period following World War II, officials in the United States government came to believe that efficient coordination of the energies and resources of a whole nation in the event of nuclear war would require the use of scientific planning techniques. The advent of the computer made such an approach feasible.
Intensive work began in 1947 in the U.S. Air Force. The linear programming model was proposed because it was relatively simple from a mathematical viewpoint, and yet it provided a sufficiently general and practical framework for representing interdependent activities that share scarce resources. In the linear programming model, the modeler views the system to be optimized as being made up of various activities that are assumed to require a flow of inputs (e.g., labour and raw materials) and outputs (e.g., finished goods and services) of various types proportional to the level of the activity. Activity levels are assumed to be representable by nonnegative numbers. The revolutionary feature of the approach lies in expressing the goal of the decision process in terms of minimizing or maximizing a linear objective function—for example, maximizing possible sorties in the case of the air force, or maximizing profits in industry. Before 1947 all practical planning was characterized by a series of authoritatively imposed rules of procedure and priorities. General objectives were never stated, probably because of the impossibility of performing the calculations necessary to minimize an objective function under constraints. In 1947 a method (described in the section The simplex method) was introduced that turned out to solve practical problems efficiently. Interest in linear programming grew rapidly, and by 1951 its use spread to industry. Today it is almost impossible to name an industry that is not using mathematical programming in some form, although the applications and the extent to which it is used vary greatly, even within the same industry.
Interest in linear programming has also extended to economics. In 1937 the Hungarian-born mathematician John von Neumann analyzed a steadily expanding economy based on alternative methods of production and fixed technological coefficients. As far as mathematical history is concerned, the study of linear inequality systems excited virtually no interest before 1936. In 1911 a vertex-to-vertex movement along edges of a polyhedron (as is done in the simplex method) was suggested as a way to solve a problem that involved optimization, and in 1941 movement along edges was proposed for a problem involving transportation. Credit for laying much of the mathematical foundations should probably go to von Neumann. In 1928 he published his famous paper on game theory, and his work culminated in 1944 with the publication, in collaboration with the Austrian economist Oskar Morgenstern, of the classic Theory of Games and Economic Behaviour. In 1947 von Neumann conjectured the equivalence of linear programs and matrix games, introduced the important concept of duality, and made several proposals for the numerical solution of linear programming and game problems. Serious interest by other mathematicians began in 1948 with the rigorous development of duality and related matters.
The trusted destination for professionals, college students, and lifelong learners.
SUBSCRIBE
The general simplex method was first programmed in 1951 for the United States Bureau of Standards SEAC computer. Starting in 1952, the simplex method was programmed for use on various IBM computers and later for those of other companies. As a result, commercial applications of linear programs in industry and government grew rapidly. New computational techniques and variations of older techniques continued to be developed.
More recently there has been much interest in solving large linear problems with special structures—for example, corporate models and national planning models that are multistaged, are dynamic, and exhibit a hierarchical structure. It is estimated that certain developing countries will have the potential of increasing their gross national product (GNP) by 10 to 15 percent per year if detailed growth models of the economy can be constructed, optimized, and implemented.