How many optimal values can the objective function have? Standard LP problem. I. Registration of initial data

Objective function is a function with some variables on which the achievement of optimality directly depends. It can also act as several variables that characterize a particular object. We can say that, in essence, it shows how we have progressed towards achieving our goal.

An example of such functions is the calculation of the strength and weight of the structure, installation capacity, production volume, transportation costs, and others.

The objective function allows you to answer several questions:

Whether this or that event is beneficial or not;

Is the movement going in the right direction?

How correct was the choice made, etc.

If we do not have the opportunity to influence the parameters of the function, then we can say that we cannot do anything, except perhaps just analyze everything. But to be able to change something, there are usually mutable function parameters. the main task- this is to change the values to those at which the function becomes optimal.

Objective functions cannot always be presented in the form of a formula. This could be a table, for example. Also, the condition can be in the form of several objective functions. For example, if you want to ensure maximum reliability, minimum costs and minimal material consumption.

Optimization problems must have the most important initial condition - an objective function. If we do, then we can assume that optimization does not exist. In other words, if there is no goal, then there are no ways to achieve it, much less favorable conditions.

Optimization tasks can be conditional or unconditional. The first type involves restrictions, that is, certain conditions when setting the problem. The second type is to find the maximum or at existing parameters. Often such problems involve searching for a minimum.

In the classical understanding of optimization, such parameter values are selected for which the objective function satisfies the desired results. It can also be defined as the process of selecting the best possible option. For example, choosing the best resource allocation, design option, etc.

There is such a thing as incomplete optimization. It can form for several reasons. For example:

The number of systems that reach the maximum point is limited (a monopoly or oligopoly has already been established);

There is no monopoly, but there are no resources (lack of qualifications in any competition);

The absence of itself, or rather “ignorance” of it (a man dreams of a certain beautiful woman, but it is unknown whether such a thing exists in nature), etc.

In the conditions of market relations for managing the sales and production activities of firms and enterprises, the basis for decision-making is information about the market, and the validity of this decision is checked when entering the market with the corresponding product or service. In this case, the starting point is to study consumer demand. To find solutions, a consumption target function is established. It shows the amount of goods consumed and the degree of satisfaction of consumer needs, as well as the relationship between them.

In the conditions of a market system for managing the production and sales activities of enterprises and firms, the basis for making business decisions is market information, and the validity of decisions is verified by the market during the sale of goods and services. With this approach, the starting point of the entire cycle of entrepreneurial activity is the study of consumer demand. Let's consider some issues of modeling demand and consumption.

Consider a consumer who, as a result of his existence, consumes some goods. The level of satisfaction of consumer needs will be denoted by U.Assume that there is n types of goods B 1, B 2,…, B n. Benefits may include:

· foodstuffs;

· essential goods;

· luxuries;

· paid services, etc.

Let the quantity of consumption of each good be equal X 1 , X 2 ,…, x n. Target consumption function is called the relationship between the degree (level) of needs satisfaction U and the amount of goods consumed: X 1 , X 2 , …, x n. This function looks like .

In the space of consumer goods, each equation corresponds to a certain surface of equivalent, or indifferent, sets of goods, which is called surface of indifference. The hypersurface of such a curve, called a multidimensional indifference surface, can be represented as , where WITH- constant. For clarity, let us consider the space of two goods, for example, in the form of two aggregated groups of goods: food B 1 and non-food goods, including paid services B 2. Then the levels of the consumption objective function can be depicted on the plane in the form of indifference curves corresponding to different values of the constant WITH.To do this, express the amount of consumption of one good X 1 through another X 2. Let's look at an example.

Example 6.3. The target consumption function has the form . Find indifference curves.

Solution. Indifference curves look like or , or (it should be noted that must be performed).

Each consumer strives to maximize the level of satisfaction of needs, that is. However, maximizing the degree of satisfaction of needs will be hampered by the consumer's capabilities. Let us denote the price per unit of each good by R 1 , R 2 ,…, р n, and consumer income through D.Then it should be executed budget constraint , which has the meaning of the law, according to which consumer costs should not exceed the amount of income:

As a result, to find the optimal set of goods it is necessary to solve the problem optimal programming:

(6.3)

Consider a two-factor consumption function, where X 1 - volume of food consumption and X 2 - consumption of non-food products and paid services. In addition, let us assume that the consumer uses all his income to satisfy his needs. In this case, the budget constraint will contain only two terms, and inequality will turn into equality. The optimal programming problem then takes the form:

(6.4)

Geometrically optimal solution has the meaning of the tangency point of the indifference curve to the line corresponding to the budget constraint.

X 2

From the budget constraint of the system (6.4), we can express the variable . Substituting this expression into the objective function, we obtain a function of one variable

, the maximum of which can be found from the equation by equating the derivative to zero: .

Example 6.4. The consumption target function has the form . Price for good B 1 equals 20, the price of the good B 2 is equal to 50. The consumer's income is 1800 units. Find indifference curves, the optimal set of consumer goods, the demand function for the first good by price, the demand function for the first good by income.

Solution. Indifference curves look like:

We obtain a set of hyperbolas located in the first coordinate quarter on at different distances from the origin depending on the value of the constant WITH.

We find the optimal set of goods. The optimal programming problem has the form:

To solve it, we express one variable from the budget constraint in terms of another: . Substitute into the target function

Find the derivative and equate it to zero

We get.

Thus, the optimal set of goods is 30.5 and 23.8 units. We now find the demand function for the first good based on its price. To do this, in the budget constraint instead fixed value we enter the price of the first good, obtaining the equation: . We express

or , from where we find the demand function for the first good at price: .

We now find the demand function for the first good in terms of income. To do this, we express from the budget constraint one variable through another: . Substitute into the target function:

We find the derivative and equate it to zero:

From here we find the demand function for the first good by income

7. Model
intersectoral balance

Balance models are designed for analysis and planning of production and distribution of products various levels- from an individual enterprise to the national economy as a whole. If we recall the history of the national economy as Soviet Union both Russia and other developed countries, it can be observed that in the economies of many countries in different time There have been economic crises of various extremes, from crises of overproduction (USA, mid-twentieth century) to shortages (Russia, late twentieth century). All these economic crises are associated with an imbalance between production and consumption. From these facts it is clear that the balance between production and consumption is important criterion for both macroeconomics and microeconomics.

Many economists and mathematicians tried to build economic and mathematical balance models from the very beginning of the problem, however, the most complete balance model was built in 1936 by the American economist V. Leontiev (who emigrated to the USA after the revolution and received the Nobel Prize in the field for his model economy). This model made it possible to calculate the balance between several interacting industries, although it can be easily generalized for microeconomic organizations, for example, to calculate the balance between several interacting enterprises or between divisions of one enterprise (for example, workshops of the same plant).

The purpose of balance analysis is to answer the question that arises in macroeconomics and is related to the efficiency of running a diversified economy: what should be the volume of production of each of the P industries to satisfy all the product needs of that industry? Moreover, each industry acts, on the one hand, as a producer of certain products; and on the other hand, as a consumer of products both their own and those produced by other industries.

Let us assume that we are considering P industries, each of which produces its own products. Let the total volume of products produced i th industry is equal to . The total cost of products produced i th industry, we will call the gross product of this industry. Now let's look at what the products produced by the industry are spent on. Part of the production is used for internal consumption by this industry and consumption by other industries related to this industry. Number of products i-th industry intended for final consumption (outside the sphere material production) personal and public j denote the th industry by . The remaining part is intended for implementation in the external sphere. This part is called the final product. Let i-I industry produces the final product.

Consider the production process over a certain period of time (for example, a year). Since the gross volume of production is any i- industry is equal to the total volume of products consumed n industries, and the final product, then the balance equation between production and consumption will have the form

, (i= 1, 2, …, n). (7.1)

Equations (7.1) are called balance relations.

. (7.2)

All previously discussed indicators can be recorded in the main balance sheet:

Industry	Consumption of industries,	Final product,	Gross product,
		…	n
			…
			…
…		…		…	…
n			…
Clean product			…

As a result, the main balance sheet contains four matrices: matrix of intersectoral production links

; gross output matrix; final product matrix and net product matrix .

One of the tasks of balance analysis is to determine the gross product if the distribution of the final product is known. To do this, we introduce direct cost coefficients

They are obtained by dividing all elements of each column of the matrix by the corresponding element of the matrix of intersectoral production links X.Direct cost coefficients have the meaning of the quantity of product consumption j-th industry required to produce a unit of output i th industry. From expression (7.3) we can obtain: . Substituting the last expression into the balance relation (7.1), we obtain

. (7.4)

If we denote the matrix of direct cost coefficients as , then the balance relation (7.4) in matrix form can be written as

From the last expression you can find the value of the final product with a known value of the gross

Where - identity matrix of the same size as A.

Example 7.1. The balance of four industries for the previous period has a matrix of intersectoral production relations of the form and a matrix of gross output of the form . It is necessary to define the final product Y and pure product C every industry.

Final product Y is obtained by subtracting from each element of the gross output matrix the sum of the elements of the corresponding rows of the matrix. For example, the first value is 100 – (10 + 20 + 15 + 10) = 45. Pure product WITH is obtained by subtracting gross output from each element of the matrix X the sum of the elements of the corresponding columns of the matrix. For example, the first value is 100 – (10 + 5 + 25 + 20) = 40. As a result, we get the main balance sheet:

Industry	Consumption of industries,	Final product,	Gross product,





Pure product				S=210	S = 400

Let us now set another task: we will calculate the final product of each industry for the future period if the gross product turns out to be equal . To solve this problem, let's find the coefficients of direct costs: i -th industry.

Example 7.2. In a certain region there are two main sectors of the national economy: mechanical engineering (m/s) and Agriculture(agricultural). The balance of these industries for the reporting period is determined by the matrices , . Let's calculate the remaining indicators and fill out the main balance sheet

Let us assume that final products in volumes are planned for the future period. It is necessary to determine what gross product needs to be planned. Let's find the direct cost coefficients:

The following reasons can be identified why economic systems are stochastic:

1) the system is complex, multi-criteria, described by a multi-level hierarchical structure;

2) the system is influenced large number uncontrollable external factors (weather, foreign policy, social factors etc.);

3) deliberate distortion of information, concealment of information and targeted economic sabotage.

Based on this, for modeling many economic systems use mathematical methods, based on the application of the laws of probability theory, which are called stochastic methods.

When using stochastic methods, the optimization of the objective function is carried out according to the average value, that is, when given parameters it is necessary to find a solution when the value of the objective function average will be maximum.

Stochastic systems in economics are described by the Markov apparatus, which is based on Markov random processes. They are used in cases where the model cannot be formalized (described by an analytical expression) and in the case when the system is a multi-parameter probabilistic economic system.

August 27, 2017 at 2:20 pm

The solution is direct and dual problem linear programming using Python

Introduction

It should be noted that methods for solving linear programming problems include not to economics, but to mathematics and computer technology. At the same time, the economist needs to provide the most comfortable conditions for dialogue with the appropriate software. In turn, such conditions can only be provided by dynamically developing and interactive development environments that have in their arsenal a set of libraries necessary for solving such problems. One of which development environments software is definitely Python.

Formulation of the problem

The publications considered solutions to direct optimization problems using the linear programming method and proposed a reasonable choice of the scipy solver. optimize.

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

Considering high level mathematical training of the vast majority of users of this resource I will not present balance equations with upper and lower restrictions and the introduction of additional variables for the transition to equalities. Therefore, I will immediately give the designations of the variables used in the solution:
N – number of types of products produced;
m – number of types of raw materials used;
b_ub - vector of available resources of dimension m;
A_ub is a matrix of dimension m×N, each element of which is the consumption of a resource of type i for the production of a unit of product of type j;
c is the vector of profit from the production of a unit of each type of product;
x – the required volumes of produced products of each type (optimal production plan) ensuring maximum profit.

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)

Results of solving the problem
nit 3
status 0

success True
x [ 0. 0. 18.18181818 22.72727273 150. ]
A_ub*x
b_ub-A_ub*x [0. 0. 0. 90.90909091]
fun -5863.63636364
slack [0. 0. 0. 90.90909091]

conclusions

The optimal plan for product types was found
Found actual resource usage
The remainder of the unused fourth type of resource was found [ 0. 0 0.0 0.0 90.909]
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

The fourth type of resource in the direct task is not fully used. Then the value of this resource for the enterprise turns out to be lower compared to resources that limit production, and the enterprise is willing to pay more high price for the acquisition of resources to increase profits.

Let us introduce a new purpose for the desired variable x as a certain “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 initial 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)

Results of solving the problem
nit 7
message Optimization terminated successfully.
fun 5863.63636364
x [ 2.27272727 1.81818182 6.36363636 0. ]
slack [5.45454545 2.27272727 0. 0. 0. ]
status 0
success True

conclusions

The third type of resource has the greatest value for the manufacturer, therefore this type resources must be purchased first, then the first and second types. The fourth type of resource has zero value for the manufacturer and is purchased last.

Results of comparison of direct and dual problems

The dual problem expands the capabilities of product planning, but using scipy. optimize is solved in twice the number of direct iterations.
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.
The direct problem is a maximization problem, and the dual problem is a minimization problem, and vice versa.
The coefficients of the objective function in the direct problem are constraints in the dual problem.
Constraints in the direct problem become coefficients of the objective function in the dual one.
The signs of inequalities in restrictions are reversed.
The matrix of the system of equalities is transposed.

Links

To find the maximum of the objective function, use the maximize function, the format of which is maximize(<функция>, <система ограничений>, <опции>);

In this case, it is convenient to specify the condition for non-negativity of variables using the NONNEGATIVE option.

> optimum:=maximize(f,syst_ogr,NONNEGATIVE);

Use the subs command, which allows you to substitute variable values x 1 and x 2 per function f.

> fmax:=subs(x1=83/17,x2=19/17,f);

Use the evalf function to represent the response in a form real number with 4 significant figures.

> fmax:=evalf(fmax,4);

You can get acquainted with the solution to the LP problem without explanation in the appendix.

Solving optimization problems in a specialized package SimplexWin. Http://www.Simplexwin.Narod.Ru/

This program is designed to solve linear programming problems using the simplex method.

Task. Find variable values x 1 And x 2 , at which

under restrictions

Work order:

Launch the SimplexWin program and set the required size of the constraint matrix by selecting the menu command Settings – Matrix size (Fig. 13).

Rice. 13. Determining the matrix size.

Enter the data (Fig. 14). If the task is not entered in canonical form, then additional variables and artificial bases(as well as the corresponding objective function coefficients) are added automatically.

Fig.14. Data input.

II. Finding the optimal plan and the optimal value of the objective function.

Rice. 15. Results form.

In the Results form, click the Result button, which allows you to solve the problem in automatic mode and display the latest simplex table and the result (Fig. 16).

Rice. 16. The solution of the problem.

Solving optimization problems inExcel

Let's look at an example of finding the following linear programming problem.

Task. Find variable values x 1 And x 2 , at which

under restrictions

Work order:

I. Registration of initial data.

Create a screen form for entering the conditions of the problem (variables, objective function, constraints) and enter the initial data into it (coefficients of the objective function, coefficients of variables in constraints, right-hand sides of constraints) (Fig. 17).

Rice. 17. Screen form of the task (cursor in cell D6).

Comment: IN screen form in Fig. 17 Each variable and each coefficient of the problem is assigned a specific cell in Excel. So, for example, the task variables correspond to cells B3 ( ), C3 ( ), the coefficients of the objective function correspond to cells B6 (
), C6 (
), the right sides of the restrictions correspond to cells F10 (
), F11 (
),F12 (
)etc.

Enter the dependencies from the mathematical model into the screen form, i.e. Enter the formula for calculating the objective function and the formula for calculating the values of the left-hand sides of the constraints.

According to the conditions of the problem, the value of the objective function is determined by the expression
. Using the designations of the corresponding cells in Excel, the formula for calculating the objective function can be written as sum of products each of the cells allocated for the values of the task variables (B3, C3) to the corresponding cells allocated for the coefficients of the objective function (B6, C6).

To set the dependency formula for the objective function, do the following: :

– place the cursor in the cell D6;

– call window Function Wizard - Step 1 of 2 by pressing the button on standard panel tools;

- in the window Function select function SUMPRODUCT;

- in the window that appears SUMPRODUCT to line Array 1 enter expression B$3:C$3, and to the line Array 2- expression B6:C6;

– press the button OK.

Rice. 18. Entering a formula for calculating the CF in the Function Wizard window.

After entering cells into rows Array 1 And Array 2 in the window SUMPRODUCT will appear numeric values entered arrays (Fig. 18), and the current value calculated using the entered formula, that is, 0 (since at the moment the formula is entered, the values of the task variables are zero) will appear in the screen form (Fig. 19).

Comment: The $ symbol before the row number means that when you copy this formula to other places in the Excel worksheet, the row number 3 will not change. Symbol : means that the formula uses all the cells between the cells to the left and right of the colon.

The left sides of the problem constraints are sum of products each of the cells allocated for the values of the problem variables (B3, C3) to the corresponding cell allocated for the coefficients of a specific constraint (B10, C10 – 1st constraint; B11, C11 – 2nd constraint; B12, C12 – 3rd constraint).

The formulas that specify the left sides of the problem constraints differ from each other and from the formula in the target cell D6 only the line number in the second array. This number is determined by the line in which the restriction is written in the screen form. Therefore, to specify dependencies for the left parts of the constraint, it is enough to copy the formula from the target cell to the cells of the left parts of the constraints.

To calculate the values of the left sides of the constraints, do the following:

– place the cursor in the cell D6 and copy the contents of the cell to the clipboard (using the Ctrl+C keys);

– place the cursor in turn in the fields of the left side of each of the restrictions, that is D10 ,D11 , D12 , and paste the contents of the buffer into these fields (using the Ctrl+V keys) (in this case, the number of cells in the second array of the formula will change to the number of the row into which the paste was made from the buffer).

After entering on the screen in the fields D10 ,D11 , D12 0 (zero value) will appear (Fig. 19).

Rice. 19. Screen form of the task after water

all necessary formulas.

Check that the formulas are entered correctly.

For this:

- do it one by one double tap left mouse button on cells with formulas, while the cells used in the formula will be highlighted on the screen with a frame (Fig. 20 and Fig. 21).

Rice. 20

formulas to target cell D6.

Rice. 20. Checking the correct insertion

formulas in cell D10 for the left side of the constraints.

Specify the objective function and enter constraints in the window Finding a solution(Fig. 21).

For this:

– place the cursor in the cell D6;

– call window Finding a solution by selecting on the toolbar Data - Finding a solution;

– place the cursor in the field Set target cell;

– enter the address of the target cell $D$6 or make one click with the left mouse button on the target cell in the screen form, which will be equivalent to entering the address from the keyboard;

– indicate the direction of optimization of the objective function by clicking once with the left mouse button on the selector button maximum value;

- in the window Searching of decisions in field Changing cells enter cells with variable values $B$3:$C$3, selecting them in the screen form while holding the left mouse button;

Rice. 21. Window Search for a solution.

– press the button Add;

– in accordance with the conditions of the task, select the required sign in the sign field, for example, for 1 constraint this is the sign ;

- in field Limitation enter the cell address of the right-hand side of the constraint in question, for example $F$10;

– similarly establish relationships between the right and left parts of other restrictions ( $D$11$F$11 , $D$12$F$12) ;

– confirm the entry of all listed conditions by pressing the button OK(Fig. 22 and Fig. 23).

Rice. 22. Adding a condition.

Comment: If, when entering a task condition, there is a need to change or delete the restrictions entered, this can be done by clicking on the buttons Change or Delete.

Design parameters. This term refers to independent variable parameters, which completely and unambiguously define the design problem being solved. Design parameters are unknown quantities whose values are calculated during the optimization process. Any basic or derived quantities that serve to quantitatively describe the system can serve as design parameters. So, these can be unknown values of length, mass, time, temperature. The number of design parameters characterizes the degree of complexity of a given design problem. Usually the number of design parameters is denoted by n, and the design parameters themselves by x with the corresponding indices. Thus, n design parameters of this problem will be denoted by

X1, X2, X3,...Xp.

It should be noted that design parameters may be referred to as internal controllable parameters in some sources.

Target function. This is an expression whose value the engineer strives to make maximum or minimum. The objective function allows you to quantitatively compare two alternative solutions. From a mathematical point of view, the objective function describes some (n+1)-dimensional surface. Its value is determined by the design parameters

M = M (x1,x2,…,xn).

Examples of objective functions often found in engineering practice are cost, weight, strength, dimensions, efficiency. If there is only one design parameter, then the objective function can be represented by a curve on the plane (Fig. 1). If there are two design parameters, then the objective function will be depicted as a surface in three-dimensional space (Fig. 2). With three or more design parameters, the surfaces specified by the objective function are called hypersurfaces and cannot be imaged by ordinary means. The topological properties of the surface of the objective function play a big role in the optimization process, since the choice of the most efficient algorithm depends on them.

Figure 1. One-dimensional objective function.

Figure 2. Two-dimensional objective function.

The objective function in some cases can take the most unexpected forms. For example, it cannot always be expressed in a closed mathematical form; in other cases, it can be a piecewise linear function. Specifying an objective function may sometimes require a table of technical data (for example, a table of the state of water vapor) or may require an experiment. In some cases, design parameters take only integer values. An example would be the number of teeth in a gear train or the number of bolts in a flange. Sometimes design parameters have only two meanings - yes or no. Qualitative parameters, such as the satisfaction experienced by the buyer who purchased the product, reliability, aesthetics, are difficult to take into account in the optimization process, since they are almost impossible to characterize quantitatively. However, in whatever form the objective function is presented, it must be an unambiguous function of the design parameters.

A number of optimization problems require the introduction of more than one objective function. Sometimes one of them may be incompatible with the other. An example is aircraft design, where maximum strength, minimum weight and minimum cost are simultaneously required. In such cases, the designer must introduce a system of priorities and assign a certain dimensionless factor to each objective function. As a result, a “compromise function” appears, which allows the use of one composite objective function during the optimization process.

Search for minimum and maximum. Some optimization algorithms are designed to find the maximum, others - to find the minimum. However, regardless of the type of extremum problem being solved, you can use the same algorithm, since the minimization problem can easily be turned into a maximum search problem by reversing the sign of the objective function. This technique is illustrated in Fig. 3.

Figure 3. When the sign of the objective function changes to the opposite in a minimum problem, it turns it into a maximum problem.

Design space. This is the name of the area defined by all n design parameters. The design space is not as large as it may seem, since it is usually limited by a number of conditions related to the physical nature of the problem. The restrictions may be so strong that the problem will not have a single satisfactory solution. Constraints are divided into two groups: constraints - equality and constraints - inequality.

Equality constraints are dependencies between design parameters that must be taken into account when finding a solution. They reflect the laws of nature, economics, law, prevailing tastes and availability necessary materials. The number of constraints - equalities can be any. They look like

C1 (X1, X2, X3, . . ., Xn) = 0,

C2 (X1, X2, X3, . . ., X n) = 0,

..……………………………..

Cj(X1, X2, X 3,..., Xn) = 0.

Inequality constraints are a special type of constraint expressed by inequalities. IN general case there can be as many of them as you like, and they all have the form

z1 ?r1(X1, X2, X3, . . ., Xn) ?Z1

z2 ?r2(X1, X2, X3, . . ., Xn) ?Z2

………………………………………

zk ?rk(X1, X2, X3, . . ., Xn) ?Zk

It should be noted that very often, due to restrictions, the optimal value of the objective function is not achieved where its surface has a zero gradient. Often The best decision corresponds to one of the boundaries of the design area.

Direct and functional restrictions. Direct restrictions have the form

xнi? xi? xвi at i? ,

where xнi, xвi - minimum and maximum valid values i-th controlled parameter; n is the dimension of the space of controlled parameters. For example, for many objects, the parameters of elements cannot be negative: xнi ? 0 (geometric dimensions, electrical resistance, mass, etc.).

Functional restrictions, as a rule, represent conditions for the performance of output parameters that are not included in the target function. Functional restrictions may be:

1) type of equalities
w(X) = 0; (2.1)
2) type of inequalities

tz (X) › 0, (2.2)

where w(X) and q(X) are vector functions.

Direct and functional restrictions form the permissible search area:

ХД = (Х | w(Х) = 0, ц (Х)›0, xi › xнi ,

xi ‹ xвi for i ? ).

If restrictions (2.1) and (2.2) coincide with the performance conditions, then the permissible area is also called the XP performance area.

Any of the points X belonging to the CD is a feasible solution to the problem. Often parametric synthesis is posed as the problem of determining any of the feasible solutions. However, it is much more important to solve the optimization problem - to find the optimal solution among the feasible ones.

Local optimum. This is the name of the point in the design space at which the objective function has highest value compared to its values at all other points in its immediate vicinity. Figure 4 shows a one-dimensional objective function that has two local optima. Often the design space contains many local optima and care must be taken not to mistake the first one for the optimal solution to the problem.

Figure 4. An arbitrary objective function can have several local optima.

The global optimum is the optimal solution for the entire design space. It is better than all other solutions corresponding to local optima, and it is what the designer is looking for. It is possible that there are several equal global optima located in different parts design space. This allows you to select best option of equals optimal options by objective function. IN in this case the designer can choose an option intuitively or based on a comparison of the resulting options.

Selection of criteria. The main problem in setting extremal problems is the formulation of the objective function. The difficulty in choosing an objective function lies in the fact that any technical object initially has a vector nature of optimality criteria (multi-criteria). Moreover, an improvement in one of the output parameters, as a rule, leads to a deterioration in the other, since all output parameters are functions of the same controlled parameters and cannot change independently of each other. Such output parameters are called conflict parameters.

There must be one target function (uniqueness principle). Reducing a multi-criteria problem to a single-criteria problem is called convolution of a vector criterion. The task of finding its extremum is reduced to a problem of mathematical programming. Depending on how the output parameters are selected and combined in the scalar quality function, partial, additive, multiplicative, minimax, statistical criteria and other criteria are distinguished. IN terms of reference for the design of a technical object, requirements for the main output parameters are indicated. These requirements are expressed in the form of specific numerical data, the range of their variation, operating conditions and acceptable minimum or maximum values. The required relationships between output parameters and technical requirements (TR) are called performance conditions and are written in the form:

yi< TTi , i О ; yi >TTj, j O;

yr = TTr ± ?yr; r O .

where yi, yj, yr - set of output parameters;

TTi, TTj, TTr - required quantitative values of the corresponding output parameters according to the technical specifications;

Yr- tolerance r-th output parameter from the TTr value specified in the technical specifications.

Operating conditions are of decisive importance in development technical devices, since the design task is to select a design solution in which the best way all operating conditions are met throughout the entire range of changes external parameters and upon fulfillment of all requirements of the technical specifications.

Particular criteria can be used in cases where among the output parameters one main parameter yi(X) can be identified, which most fully reflects the effectiveness of the designed object. This parameter is taken as the objective function. Examples of such parameters are: for an energy facility - power, for a technological machine - productivity, for vehicle- load capacity. For many technical objects, this parameter is cost. The operating conditions of all other output parameters of the object are referred to as functional restrictions. Optimization based on such a formulation is called optimization according to a particular criterion.

The advantage of this approach is its simplicity; a significant drawback is that a large performance reserve can be obtained only for the main parameter, which is accepted as the objective function, and other output parameters will have no reserves at all.

The weighted additive criterion is used when the performance conditions make it possible to distinguish two groups of output parameters. The first group includes output parameters, the values of which should be increased during the optimization process y+i(X) (performance, noise immunity, probability of failure-free operation, etc.), the second group includes output parameters, the values of which should be decreased y-i (X) ( fuel consumption, duration of the transient process, overshoot, displacement, etc.). Combining several output parameters, which generally have different physical dimensions, into one scalar objective function requires preliminary normalization of these parameters. Methods for normalizing parameters will be discussed below. For now, we will assume that all y(X) are dimensionless and among them there are no ones that correspond to performance conditions of the type of equality. Then, for the case of minimizing the objective function, the convolution of the vector criterion will have the form

where aj>0 is a weighting coefficient that determines the degree of importance of the j-th output parameter (usually aj is selected by the designer and remains constant during the optimization process).

The objective function in the form (2.1), expressing the additive criterion, can also be written in the case when all or the main performance conditions have the form of equalities. Then the objective function

determines the root-mean-square approximation of yj(X) to the given technical requirements TTj.

The multiplicative criterion can be used in cases where there are no equality-type performance conditions and the output parameters cannot accept zero values. Then the multiplicative objective function to be minimized has the form

One of the most significant drawbacks of both additive and multiplicative criteria is the failure to take into account the technical requirements for output parameters in the formulation of the problem.

The function form criterion is used when the task is set of the best match of a given (reference) characteristic yCT(X, y) with the corresponding output characteristic y(X, y) of the designed object, where y is some variable, for example, frequency, time, selected phase variable. These tasks include: designing an automatic control system that provides the required type of transient process for the controlled parameter; determining the parameters of the transistor model that give maximum agreement with its theoretical current-voltage characteristics with experimental ones; search for parameters of beam sections, the values of which lead to the best coincidence of the given stress diagram with the calculated one, etc.

The use of a particular optimization criterion in these cases comes down to replacing continuous characteristics with a finite set of nodal points and choosing one of the following objective functions to be minimized:

where p is the number of nodal points uj on the axis of the variable u; aj - weighting coefficients, the values of which are greater, the smaller the deviation y(X, φj) - yTT(X, φj) must be obtained at the j-th point.

Maximin (minimax) criteria allow one to achieve one of the goals of optimal design - the best satisfaction of performance conditions.

Let's introduce quantitative assessment degree of fulfillment of the j-th performance condition, we denote it by zj and call it the performance reserve of the parameter yj. The calculation of the margin for the jth output parameter can be performed in various ways, for example,

where аj is the weighting coefficient; yjnom - nominal value of the j-th output parameter; dj is a value characterizing the spread of the jth output parameter.

Here it is assumed that all relations are reduced to the form yi< TТj. Если yi >TTj, then -yj< -TТj . Следует принимать аj >1 (recommended values 5 ? aj ? 20), if it is desirable to achieve the j-th technical requirements with a given tolerance, i.e. yj = TTj ± ?yj; aj=l, if it is necessary to obtain the maximum possible estimate zj.

Performance quality technical system characterized by a vector of output parameters and, therefore, a vector Z=(zm,zm,…,zm). Therefore, the target function should be formed as a certain function μ(Z) of the evaluation vector. For example, if the target function considers the reserve of only that output parameter that at a given point X is the worst from the standpoint of meeting the requirements of the technical specifications, then

where m is the number of working capacity reserves.

It is natural now to pose the problem of choosing a search strategy X that would maximize the minimum of the reserves, i.e.

where HD is the searchable area.

The optimization criterion with objective function (2.6) is called the maximin criterion.

Statistical criteria. Optimization using statistical criteria is aimed at obtaining the maximum probability P of performance. This probability is taken as the objective function. Then we have the problem

Normalization of controlled and output parameters. The space of controlled parameters is metric. Therefore, when choosing the directions and values of search steps, it is necessary to introduce one or another norm, identified with the distance between two points. The latter assumes that all controlled parameters have the same dimension or are dimensionless.

Possible various ways rationing. As an example, consider the method of logarithmic normalization, the advantage of which is the transition from absolute increments of parameters to relative ones. In that case i controlled parameter ui is converted to dimensionless xi as follows:

where oi is the coefficient, numerically equal to one parameter ui .

Normalization of output parameters can be performed using weighting coefficients, as in the additive criterion, or by moving from уj to performance reserves zj according to (2.5).