Target function. Solving optimization control problems using linear programming method

Solving direct and dual linear programming problems using Python

Introduction

Statement of the problem

However, it is known that each linear programming problem corresponds to a so-called distinguished (dual) problem. In it, compared to the direct problem, rows turn into columns, inequalities change sign, instead of a maximum, a minimum is sought (or vice versa, instead of a minimum, a maximum is sought). The task dual to the dual is the original task itself.

Solving the dual problem is very important for analyzing resource use. In this publication, it will be proven that the optimal values ​​of the objective functions in the original and dual problems coincide (i.e., the maximum in the original problem coincides with the minimum in the dual).

The optimal values ​​of material and labor costs will be assessed by their contribution to the objective function. The result will be “objectively determined estimates” of raw materials and labor that do not coincide with market prices.

Solution of the direct problem of the optimal production program

Goal function
maxF(x)=c×x

Restrictions
A×x≤b

Numerical values ​​of variables:
N=5; m=4; b_ub = ; A_ub = [, , ,]; c = .

Tasks
1. Find x to ensure maximum profit
2. Find the resources used when performing step 1
3. Find the remaining resources (if any) when performing step 1

To determine the maximum (by default, the minimum is determined, the coefficients of the objective function must be written with a negative sign c = [-25, -35,-25,-40,-30] and ignore the minus sign in front of the profit.

Notations used to display the results:
x– an array of variable values ​​that provide the minimum (maximum) of the target function;
slack– values ​​of additional variables. Each variable corresponds to an inequality constraint. A variable value of zero means that the corresponding constraint is active;
success– True, if the function managed to find the optimal solution;
status– decision status:
0 – the search for the optimal solution was completed successfully;
1 – the limit on the number of iterations has been reached;
2 – the problem has no solutions;
3 – the objective function is not limited.
nit– number of iterations performed.

Listing of the solution to the direct optimization problem

#!/usr/bin/python # -*- coding: utf-8 -*- import scipy from scipy.optimize import linprog # loading LP library c = [-25, -35,-25,-40,-30] # list of coefficients of the goal function b_ub = # list of resource volumes A_ub = [, # matrix of specific resource values ​​, , ] d=linprog(c, A_ub, b_ub) # search for a solution for key,val in d.items(): print(key ,val) # solution output if key=="x": q=#used resources print("A_ub*x",q) q1= scipy.array(b_ub)-scipy.array(q) #remaining resources print(" b_ub-A_ub*x", q1)

Conclusions

1. The optimal plan for product types was found
2. Found actual resource usage
3. The remainder of the unused fourth type of resource was found [ 0. 0 0.0 0.0 90.909]
4. There is no need for calculations according to step 3, since the same result is displayed in the slack variable

Solution of the dual problem on the optimal production program

Let us introduce a new purpose for the desired variable x as some “shadow” price that determines the value of a given resource in relation to profit from the sale of manufactured products.

C – vector of available resources;
b_ub is the vector of profit from the production of a unit of each type of product;
A_ub_T – transposed matrix A_ub.

Goal function
minF(x)=c×x

Restrictions
A_ub_T ×x≥ b_ub

Numerical values ​​and relationships for variables:
c = ; A_ub_T transpose(A_ub); b_ub = .

Task:
Find x indicating the value for the producer of each type of resource.

Features of the solution with the scipy library. optimize
To replace restrictions from above with restrictions from below, it is necessary to multiply both parts of the constraint by minus one – A_ub_T ×x≥ b_ub... To do this, write the original data in the form: b_ub = [-25, -35,-25,-40,-30]; A_ub_T =- scipy.transpose(A_ub).

Listing of the solution to the dual optimization problem

#!/usr/bin/python # -*- coding: utf-8 -*- import scipy from scipy.optimize import linprog A_ub = [, , , ] c= b_ub = [-25, -35,-25,- 40,-30] A_ub_T =-scipy.transpose(A_ub) d=linprog(c, A_ub_T, b_ub) for key,val in d.items(): print(key,val)

Conclusions

Results of comparison of direct and dual problems

1. The dual problem expands the capabilities of product planning, but using scipy. optimize is solved in twice the number of direct iterations.
2. The slack variable displays information about the activity of constraints in the form of inequalities, which can be used, for example, to analyze raw material balances.
3. The direct problem is a maximization problem, and the dual problem is a minimization problem, and vice versa.
4. The coefficients of the objective function in the direct problem are constraints in the dual problem.
5. Constraints in the direct problem become coefficients of the objective function in the dual one.
6. The signs of inequalities in restrictions are reversed.
7. The matrix of the system of equalities is transposed.

Objective function

A function that relates the goal (the variable being optimized) to the controlled variables in an optimization problem.

It is important that the criterion is always introduced from the outside, and only after that a decision rule is sought that minimizes or maximizes the objective function.

See also

• Burak Ya. I., Ogirko I. V. Optimal heating of a cylindrical shell with temperature-dependent material characteristics // Mat. methods and physical-mechanical fields. - 1977. - Issue. 5. - P.26-30

Wikimedia Foundation. 2010.

• Central Research Institute of Robotics and Technical Cybernetics
• 1885 in the theater

See what “Objective function” is in other dictionaries:

objective function- - [Ya.N.Luginsky, M.S.Fezi Zhilinskaya, Yu.S.Kabirov. English-Russian dictionary of electrical engineering and power engineering, Moscow, 1999] objective function In extremal problems, a function whose minimum or maximum is required to be found. This… …

Objective function- in extremal problems, a function whose minimum or maximum needs to be found. This is a key concept in optimal programming. Having found the extremum of C.f. and, therefore, having determined the values ​​of the controlled variables that go to it... ...

objective function- 3.1.8 business function: A set of processes that ensure the achievement of a specific business goal. Source: R 50.1.041 2002: Infor... Dictionary-reference book of terms of normative and technical documentation

objective function- tikslo funkcija statusas T sritis automatika atitikmenys: engl. objective function vok. Zielfunktion, f rus. goal function, f; objective function, f pranc. fonction de cible, f … Automatikos terminų žodynas

Objective function- a function whose extreme value is sought on an admissible set in mathematical programming problems (See Mathematical programming) ... Great Soviet Encyclopedia

TARGET FUNCTION- goal function the name of the function being optimized in mathematical programming problems... Mathematical Encyclopedia

Objective function- (a conventional name that can relatively correctly be applied only to systems created for a specific purpose by man), does not exist in the objective world, a system-forming factor takes place there... Theoretical aspects and foundations of the environmental problem: interpreter of words and ideomatic expressions

Consumption objective function- 1. This term, as well as several equivalent or almost equivalent ones (standard of living function, welfare function, social utility function, consumption function, etc.) denote in ... ... Economic and mathematical dictionary

consumption objective function- 1. This term, as well as several equivalent or almost equivalent ones (standard of living function, welfare function, social utility function, consumption function, etc.) designate the target function in theoretical studies... ... Technical Translator's Guide

target function of an automated medical system- AMS target function A set of actions of an automated medical system that ensures the effective implementation of a given medical program. [GOST 27878 88] Topics of medical systems and complexes General terms of systems and... ... Technical Translator's Guide

Books

• An approach to organizing an adaptive learning management system based on the use of information technology, A. V. Anastasin. The issue of using information technology in the educational process of higher educational institutions has long been constantly discussed at various levels. This is due to the fast...

where are fixed costs that do not depend on the processing mode, min;

Here - preparatory - final time for the operation, min;

Batch size of processed parts;

Auxiliary operation time, min;

Maintenance time excluding tool replacement time, min;

Worker's rest time, min;

Time costs associated with replacing a dull tool and corresponding adjustment of the technological system;

where is the time to replace the tool and the corresponding dimensional adjustment;

Diameter and length of the processed shaft;

Coefficient for calculating cutting speed;

Cutting speed;

Depth of cut;

Here are the exponents in the formulas for calculating cutting conditions.

Analysis of the time objective function makes it possible to reveal reserves for additional productivity increases and determine optimal cutting conditions that ensure minimal costs for the operation.

Objective cost function using the example of shaft processing, it looks like:

Here are the costs of the material;

Expenses per unit of time, respectively, for the operation of equipment, devices, wages, taking into account overhead costs;

Time for tool replacement and appropriate dimensional adjustment;

The cost of the tool over the period of its operation.

The first member of the expression determines the fixed costs of the material, costs associated with preparatory and final time and service time. The second term of the expression determines the cost of the cutting tool and downtime when replacing it. The third term of the expression determines the costs associated directly with the cutting process.

Volume planning of technological machine systems

This and all subsequent lectures are devoted to the issues of mathematical modeling and optimization of technological machine tools.

Volumetric planning of the work of the mechanical section when the maximum load of technological equipment is reached

Statement of the problem. Available m– machines ( m– groups of machines) on which they can be manufactured n– types of parts. Processing complexity j- details on i– m machine is , hour. Funds of operating time of each machine (group of machines) are known - B i. The initial data for solving the problem are presented in Table 14.1.

Table 14.1. Initial data for solving the problem, presented in general form

Need to determine the number of parts of each type, during the processing of which the maximum load of the site equipment is achieved.

Mathematical model to solve the problem we will write:

Restrictions:

The problem is solved using the linear programming method. The following should be kept in mind. The number of constraints of the form (14.1) - (14.3) in the mathematical model must be strictly equal to the number of machines (groups of machines) of the site. When solving a problem using a computer, the number of machines (groups of machines), as well as types of parts, is practically unlimited and is determined only by the capabilities of the computer and the corresponding program. When solving a problem manually using the graphic-analytical method, the number of types of machines (groups of machines) is also not limited, but increasing them will naturally lead to an increase in calculation time. The number of types of parts should not exceed two, because otherwise, it will be impossible to perform the necessary graphical constructions on the plane.

Example. The source data for the example is given in Table 14.2.

Table 14.2. Initial data for solving the problem

Let us denote by the number of parts of type D 1, by the number of parts of type D 2.

Mathematical model to solve this problem will be written as follows:

Restrictions(according to the operating time of the equipment):

It is required to find values ​​and that satisfy the given restrictions (14.6) – (14.10) and ensure the maximum of the objective function (14.11). The parameters are controlled parameters in a mathematical model.

Let's solve the problem using the grapho-analytical method (see lecture 6). A graphical illustration of the solution to the problem is shown in Fig. 14.1.

Fig. 14.1. Graphic illustration of the problem solution

Calculations for constructing restrictions (14.6) – (14.8):

By drawing a straight line parallel to this one, we find the point of contact with its boundary ODR - this is point A. To find its coordinates (the intersection points of constraints 14.7 and 14.8), we solve the following system of equations:

Those. finally

The maximum value of the objective function (maximum load of the site equipment) with optimal values ​​of the required parameters will be:

Minimum equipment load problem

This and subsequent problems in this lecture are presented at the level of setting the problem and forming a mathematical model for solving it. All of them are solved using linear programming methods.

Available m machines on which they can be manufactured n types of parts. Performance i- th machine when manufacturing a part j- type is C ij. Values ​​of planned tasks A j for production j- details and time resource B i work i- th machine are given in Table 14.3.

Table 14.3 Initial data for solving the problem

It is required, taking into account the operating time resources of each machine, to distribute tasks between the machines in such a way that the total operating time of all machines is minimal.

Let t ij- production time j- oh details i- m machine. Let’s draw up time resource limitations for each machine:

The solution to the problem is to minimize the linear objective function (total time)

(14.14)

under restrictions (14.12), (14.13) and the condition that all variables .

The problem of optimal distribution of parts among machine tools

Let some machine consist of different types of parts, which we number with numbers. There are different types of machines, and the number of machines of the type is equal to . Parts can be produced on different types of machines. The productivity of the th type of machine in the production of the th part is . After production, the parts are sent for assembly. It is required to attach machines to parts in such a way as to obtain the maximum number of machines per unit of time.

Let be the number of machines of the th type on which the th part can be produced. Obviously, the number of machines of the type that produce parts of these types should not exceed a given number:

The total number of sets of parts required to assemble a machine is equal to the total number of any one part, having, for example, number 1. Therefore, the solution to the problem is to maximize the linear function

(14.17)

under restrictions (14.15), (14.16) with the additional condition that all variables .

The optimal values ​​found for this problem are not necessarily integers. For example, it means that two machines of the first type will produce part number 1 within a unit of time, while a third machine of the same type will work only half of the specified time.

The problem of producing products with limited supplies of raw materials

Various types of products are produced from types of raw materials. The cost of selling manufactured products of the th type is . The stock of raw materials of the th type for the planning period is equal to . The need for raw materials of this type is . The initial data for solving the problem are given in Table 14.4.

Table 14.4 Initial data for solving the problem

It is required for each type of product to determine such a production volume to ensure the maximum cost of sales of manufactured products, provided that the reserves of available raw materials are not exceeded.

Limitations on raw material reserves are as follows:

(14.18)

The task is to determine the optimal values ​​of parameters (variables) that maximize the cost of production, i.e. target function

under restrictions (14.18) and additional conditions.

Basics of queuing theory

Queuing theory is one of the branches of probability theory. This theory considers probabilistic problems and mathematical models (before that we considered deterministic mathematical models). Let us remind you that:

Deterministic mathematical model reflects the behavior of an object (system, process) from the perspective full certainty in the present and future.

Probabilistic mathematical model takes into account the influence of random factors on the behavior of an object (system, process) and, therefore, evaluates the future from the standpoint of the probability of certain events.

Those. here, as, for example, in game theory problems are considered in conditions of uncertainty.

Let us first consider some concepts that characterize “stochastic uncertainty,” when the uncertain factors included in the problem are random variables (or random functions), the probabilistic characteristics of which are either known or can be obtained from experience. Such uncertainty is also called “favorable”, “benign”.

The concept of a random process

Strictly speaking, random disturbances are inherent in any process. It is easier to give examples of a random process than a “non-random” process. Even, for example, the process of running a clock (it seems to be a strictly calibrated work - “works like a clock”) is subject to random changes (moving forward, lagging behind, stopping). But as long as these disturbances are insignificant and have little effect on the parameters of interest to us, we can neglect them and consider the process as deterministic, non-random.

Let there be some system S(technical device, group of such devices, technological system - machine, site, workshop, enterprise, industry, etc.). In the system S leaks random process, if it changes its state over time (passes from one state to another), moreover, in a previously unknown random manner.

Examples: 1. System S– technological system (machine section). Machines break down from time to time and are repaired. The process taking place in this system is random.

2. System S- an aircraft flying at a given altitude along a specific route. Disturbing factors - weather conditions, crew errors, etc., consequences - bumpiness, violation of the flight schedule, etc.

Markov random process

A random process occurring in a system is called Markovsky, if for any moment of time t 0 probabilistic characteristics of a process in the future depend only on its state at the moment t 0 and do not depend on when and how the system reached this state.

Let the system be in a certain state at the moment t 0 S 0 . We know the characteristics of the state of the system in the present and everything that happened during t < t 0 (process history). Can we predict (predict) the future, i.e. what will happen when t > t 0 ? Not exactly, but some probabilistic characteristics of the process can be found in the future. For example, the probability that after some time the system S will be able S 1 or will remain in state S 0, etc.

Example. System S- a group of aircraft participating in air combat. Let x– number of “red” planes, y– number of “blue” aircraft. By the time t 0 number of surviving (not shot down) aircraft, respectively – x 0 , y 0 . We are interested in the probability that at a moment in time the numerical superiority will be on the side of the “reds”. This probability depends on what state the system was in at the time t 0, and not on when and in what sequence those shot down died until the moment t 0 planes.

In practice, Markov processes in their pure form are usually not encountered. But there are processes for which the influence of “prehistory” can be neglected. And when studying such processes, Markov models can be used (queuing theory does not consider Markov queuing systems, but the mathematical apparatus that describes them is much more complex).

In operations research, Markov random processes with discrete states and continuous time are of great importance.

The process is called discrete state process, if its possible states S 1 , S 2, ... can be determined in advance, and the transition of the system from state to state occurs “in a jump,” almost instantly.

The process is called continuous time process, if the moments of possible transitions from state to state are not fixed in advance, but are uncertain, random and can occur at any moment.

Example. Technological system (section) S consists of two machines, each of which can fail (fail) at a random moment in time, after which the repair of the unit immediately begins, which also continues for an unknown, random time. The following system states are possible:

S 0 - both machines are working;

S 1 - the first machine is being repaired, the second is working;

S 2 - the second machine is being repaired, the first one is working;

S 3 - both machines are being repaired.

System transitions S from state to state occur almost instantly, at random moments when a particular machine fails or a repair is completed.

When analyzing random processes with discrete states, it is convenient to use a geometric scheme - state graph. The vertices of the graph are the states of the system. Graph arcs – possible transitions from state to

Fig. 15.1. System state graph

state. For our example, the state graph is shown in Fig. 15.1.

Note. Transition from state S 0 in S 3 is not indicated in the figure, because it is assumed that the machines fail independently of each other. We neglect the possibility of simultaneous failure of both machines.

Event Streams

Event stream– a sequence of homogeneous events following one after another at some random moments in time.

In the previous example, this is a flow of failures and a flow of restorations. Other examples: the flow of calls at a telephone exchange, the flow of customers in a store, etc.

The flow of events can be visually represented by a series of points on the time axis Ot- rice. 15.2.

Fig. 15.2. Representation of the flow of events on the time axis

The position of each point is random, and only one implementation of the flow is depicted here.

Event flow intensity () is the average number of events per unit of time.

Let's look at some properties (types) of event streams.

The stream of events is called stationary, if its probabilistic characteristics do not depend on time.

In particular, the intensity of the stationary flow is constant. The flow of events inevitably has condensations or rarefactions, but they are not of a regular nature, and the average number of events per unit of time is constant and does not depend on time.

The stream of events is called flow without consequences, if for any two non-overlapping sections of time and (see Fig. 15.2) the number of events that fall on one of them does not depend on how many events fall on the other. In other words, this means that the events that form the flow appear at certain points in time independently of each other and are each caused by its own causes.

The stream of events is called ordinary, if events appear in it one by one, and not in groups of several at once.

The stream of events is called simplest (or stationary Poisson), if it has three properties at once: 1) stationary, 2) ordinary, 3) has no consequences.

The simplest flow has the simplest mathematical description. It plays the same special role among flows as the law of normal distribution does among other distribution laws. Namely, when superimposing a sufficiently large number of independent, stationary and ordinary flows (comparable to each other in intensity), a flow close to the simplest is obtained.

For the simplest flow with intensity interval T between neighboring events has a so-called exponential distribution with density

Being centralized, it performs the following functions: the function of regulating prices between new and serial products; the function of targeted and constant support of the process of production of new equipment with funds; the function of redistributing funds for the development of new equipment between enterprises that are involved to varying degrees in the development of new equipment.  

As for state expenditures, they represent trust funds of funds allocated and actually used by the state to implement its functions. The main functions of targeted spending include  

Let us now move on to the description of the objective functions. PM objective function  

Target function. The objective function defines the problem that must be solved during the optimization process. For example, in this chapter we are concerned with minimizing the risk of an asset portfolio. A typical objective function for a portfolio of risky assets would be  

OBJECTIVE FUNCTION is a function that connects the goal (the variable being optimized) and the controlled variables in the optimization problem.  

The first expression is called the objective function (equal to the product of profit per unit of product c, - by the output of this product Xj). The remaining equations constitute linear constraints, which mean that the consumption of raw materials, semi-finished products, product quality, power, i.e., initial resources, should not exceed predetermined values ​​/ /. Coefficients a,7 are constant values ​​showing the resource consumption for / and product. The problem can be solved if the variables are non-negative and the number of unknowns is greater than the number of constraints. If the last condition is not satisfied, then the problem is inconsistent.  

As the objective function we take the production of A-76 gasoline  

The objective function has the form  

Since variable costs depend on production volume, the difference between price and variable costs must be maximized. Conditionally fixed expenses (depreciation, expenses for current repairs, wages with accruals, general shop and plant expenses) are not included in the model and are subtracted from the objective function obtained on the computer. If the duration of operation of the installation for each option is taken as unknowns, then the variable costs are calculated for one day of its operation.  

Condition (4.56) characterizes the objective function, the maximum difference between the wholesale price and the cost of commercial gasoline.  

The objective function for solving this problem can be either the maximum profit for the enterprise (4.52) or the maximum volume of production of marketable products in value terms (4.53)  

The given model for calculating the cost is at the same time a model for calculating the profit of the enterprise. However, the main effect of implementing cost calculations on a computer is the ability to use the results of this calculation to optimize the enterprise's production program. In this case, the maximum profit from product sales can be taken as the objective function. When optimizing a production program, it is necessary to maximize a function of the form  

The advantages and disadvantages of a customer-centric structure are generally the same as those of a product structure, given the differences associated with different objective functions.  

Since the integral energy intensity is determined taking into account direct and indirect energy costs (through material, technical and labor resources), the reduction in the energy intensity of each of the consumed and used resources is also taken into account in the total economic savings. The energy intensity of each target effect (product, service) is calculated as the sum of energy intensity at the stages of its formation. For example, the energy intensity of a pipe consists of the energy intensity of ore mining, steel smelting, sheet rolling and the pipe manufacturing itself and is measured in kilograms of standard fuel per 1 ruble. its value. Existing forms of accounting and the proposed methodology make it possible to determine these indicators for any product, service, etc. Thus, to save energy it is necessary to reduce the consumption of production resources of all types while achieving a given target effect. These resources and the final target effect are measured in monetary terms. The costs of them depend on the scale of the technology used, the level of sophistication of the technical means in which the main target function is implemented - the target technological process, the number of scales and ramifications of the auxiliary functions that ensure the implementation of the main function, as well as the level of technology and equipment used.  

Expression (I) is usually called the original system of equations and inequalities, and expression (II) - the functional of the linear programming problem or the target function. The objective function is an optimality criterion. The first group of inequalities of the system (I) makes it possible to take into account in the calculation the limitations in the existing capacities of fuel production enterprises at the beginning of the planning period. The second group of inequalities takes into account  

To M. m. in the west. And. include the following, sections of applied mathematics, mathematical programming, game theory, queuing theory, scheduling theory, inventory management theory and the theory of wear and tear and replacement of equipment. Mathematics (or optimal) programming develops the theory and methods for solving conditional extremal problems, is the main thing. part of the formal apparatus for analyzing various management, planning and design problems. Plays a special role in optimization problems of outdoor planning. kh-va and management nronz-vom. Problems of economic planning and technology management usually come down to choosing a set of numbers (the so-called control parameters) that provide the optimum of a specific function (objective function or solution quality indicator) under restrictions of the type of equalities and inequalities determined by the operating conditions of the system. Depending on the properties of the functions that determine the quality indicator and the limitations of the problem, mathematic. programming is divided into linear and nonlinear. Problems in which the objective function is linear, and the conditions are written in the form of linear equalities and inequalities, constitute the subject of a linear program. Problems in which the quality indicator of the solution or some of the functions that determine the constraints are nonlinear, belong to nonlinear programs [) onan p go. Nonlinear programming, in turn, is divided into convex and non-convex programming. Depending on whether the initial parameters characterizing the conditions of the problem are well-defined numbers or random variables, in mathematics. programming, there are differences in management and planning methods under conditions of complete and incomplete information. Methods for setting and solving conditional extremal problems, the conditions of which contain random parameters, are the subject of stochastic programming.  

The goal of the model is to maximize the total discounted net income (up to profit) for a set of fields and gas pipeline systems under given technological and economic restrictions. The model allows the use of alternative criteria - minimizing the weighted sum of deviations from a given value of the objective function (target programming); calculations can be carried out for a given level of investment, for a given level of production, for a given value of the DPV.  

The success of such a business woman depends on how well the administration recognizes possible fields that can provide job satisfaction. It has been noticed that women cope well with functions that require communication with people, but if this is also an intellectual activity - teacher, journalist, tour guide, etc. - then the high efficiency of their work and their positive assessment will almost certainly coincide. In Japan, women are rarely able to obtain an engineering and natural science education, especially in modern, most promising specialties, however, their inclusion in the widespread mobile target groups for solving non-standard problems turns out to be productive. The ingenuity of the female mind has been noticed for a long time and in all countries. In Japan, when they want to provide clear proof of this, they remember the competition announced by the famous company “Aji no Moto”. She offered a large cash prize for tips on how to increase sales of her condiment, which looks like salt and is sold in the likeness of salt shakers. People wrote treatises and brought in all kinds of scientific knowledge. But the winner was a housewife, whose answer fit in one line: “Make the holes in the salt shaker larger.”  

) in order to solve some optimization problem. The term is used in mathematical programming, operations research, linear programming, statistical decision theory, and other areas of mathematics primarily of an applied nature, although the goal of optimization may also be the solution of a mathematical problem itself. In addition to the objective function in the optimization problem, restrictions can be specified for variables in the form of a system of equalities or inequalities. In general, the arguments of the objective function can be specified on arbitrary sets.

Examples

Smooth functions and systems of equations

can be formulated as a problem of minimizing the objective function

$S\; =\; \backslash sum\_(j=1)^N\; F\_j^2(x\_1,\; x\_2,\; \backslash ldots,\; x\_M)\; \backslash qquad\; (1)$

If the functions are smooth, then the minimization problem can be solved using gradient methods.

For any smooth objective function can be equated to $0$ partial derivatives with respect to all variables. The optimum of the objective function will be one of the solutions to such a system of equations. In case of function $(1)$ this will be a system of least squares (LSM) equations. Every solution of the original system is a solution of the least squares system. If the original system is inconsistent, then the least squares system, which always has a solution, allows us to obtain an approximate solution of the original system. The number of equations in the least squares system coincides with the number of unknowns, which sometimes facilitates the solution of joint initial systems.

Linear programming

Another well-known example of an objective function is a linear function, which arises in linear programming problems. In contrast to the quadratic objective function, optimization of a linear function is possible only if there are restrictions in the form of a system of linear equalities or inequalities.

Combinatorial optimization

A typical example of a combinatorial objective function is the objective function of the traveling salesman problem. This function is equal to the length of the Hamiltonian cycle on the graph. It is defined on a set of permutations $n-1$ vertices of the graph and is determined by the matrix of edge lengths of the graph. The exact solution to such problems often comes down to enumerating options.

Write a review about the article "Objective function"

Notes

See also

Literature

• Burak Ya. I., Ogirko I. V. Optimal heating of a cylindrical shell with temperature-dependent material characteristics // Mat. methods and physical-mechanical fields. - 1977. - Issue. 5. - P.26-30

An excerpt characterizing the objective function