1.2 Briefly about linear programming.

What is linear programming? This is one of the first and most thoroughly studied sections of mathematical programming. It was linear programming that was the section from which the discipline of “mathematical programming” itself began to develop. The term “programming” in the name of the discipline has nothing in common with the term “programming (i.e., compiling programs) for a computer”, since the discipline “linear programming” arose even before the time when computers began to be widely used in solving mathematical and engineering problems. , economic and other problems. The term “linear programming” arose as a result of an inaccurate translation of the English “linear programming”. One of the meanings of the word “programming” is making plans, planning. Hence, correct translation“linear programming” would not be “linear programming”, but “linear planning”, which more accurately reflects the content of the discipline. However, the term linear programming, nonlinear programming, etc. have become generally accepted in our literature.

So, linear programming arose after the Second World War and began to develop rapidly, attracting the attention of mathematicians, economists and engineers due to the possibility of a wide practical application, as well as mathematical “harmony”.
We can say that linear programming is applicable to construct mathematical models those processes that can be based on the hypothesis of a linear representation of the real world: economic problems, management and planning problems, optimal placement of equipment, etc.

Linear programming problems are problems in which both the objective function and the constraints in the form of equalities and inequalities are linear. Briefly, the linear programming problem can be formulated as follows: find a vector of values ​​of variables that deliver the extremum of the linear objective function under m constraints in the form of linear equalities or inequalities.

Linear programming is the most commonly used optimization method. Linear programming problems include the following:

· rational use of raw materials and materials; cutting optimization problems;

· optimization of the production program of enterprises;

· optimal placement and concentration of production;

· drawing up an optimal transportation plan and transport operation;

· inventory management;

· and many others belonging to the field of optimal planning.

Thus, according to American experts, about 75% of the total number of optimization methods used are linear programming. About a quarter of the computer time spent in recent years on scientific research has been devoted to solving linear programming problems and their numerous modifications.

The first formulations of linear programming problems were formulated by the famous Soviet mathematician L.V. Kantorovich, who was awarded the Nobel Prize in Economics for these works.

Currently, linear programming is one of the most commonly used tools in the mathematical theory of optimal decision making.

So, linear programming is the science of methods for studying and finding the largest and smallest values ​​of a linear function, the unknowns of which are subject to linear constraints. Thus, linear programming problems relate to problems on the conditional extremum of a function.

1.3 The main problem of linear programming

The main linear programming problem (LPP) is stated as follows: There are a number of variables. It is required to find their non-negative values ​​that would satisfy the system of linear equations:

{1.1}

and, in addition, would minimize the linear objective function (OB)

Obviously, the case when the digital function needs to be turned not to the minimum, but to the maximum, can easily be reduced to the previous one, if we change the sign of the function and consider the function instead

An admissible solution of the OLP is any set of variables satisfying equations (1.1).

The optimal solution is that one of the feasible solutions at which the CF turns to a minimum.

In practice, constraints in a linear programming problem are often specified not by equations, but by inequalities. In this case, we can move on to the main linear programming problem.

Let us consider a linear programming problem with inequality constraints that have the form

{1.2}

and are linearly independent. The latter means that none of them can be represented as a linear combination of the others. It is required to find , which satisfy the inequalities and minimize

Let's introduce the equations:

{1.3}

Where are additional variables, which are also non-negative.

Thus we have common task linear programming - find non-negative , so that they satisfy the system of equations (1.3) and reduce to a minimum.

The coefficients in formula (1.3) before are equal to zero.

1.3. Construction of constraints and gradient of the objective function: 1.4. The region of feasible solutions is the segment AB. 1.5. Point A is optimal. Point A coordinates: ; ; . 2. Solving a linear programming problem using the simplex method. Direct task. The linear programming problem for any vertex in a compact form can be represented as: To obtain, we use the algorithm given in...

Rays emanating from one point are called a polyhedral convex cone with a vertex at a given point. 1.4 Mathematical foundations for solving a linear programming problem graphically 1.4.1 Mathematical apparatus To understand everything further, it is useful to know and imagine the geometric interpretation of linear programming problems, which can be given for the cases n = 2 and n = ...

Problems f1(x)=max=g1(x) – for the first enterprise; - for other enterprises. Solution of the problem of optimal distribution of funds between enterprises using the dynamic programming method Table 12 Funds s, thousand gr. Enterprise 1 2 3 4 G1(x) G2(x) G3(x) G4(x) 20 11 13 12 10 40 21 20 22 27 60 40 42 34 33 80 54 45 55 57 100 62 62 ...

If we put the current basic variables in such a simplex table equal to Ai,0, and the free ones equal to zero, we will get optimal solution. The practice of using the simplex method has shown that the number of iterations required to solve a linear programming problem usually ranges from 2m to 3m, although for some specially constructed problems, calculations according to the rules of the simplex method turn into direct...

Programs consisting of simple commands (operators) are called linear.
Simple commands (simple instructions of the algorithm) are commands that do not use conditions during their execution. To the number simple operators include commands (operators) of assignment, input and output, calling an auxiliary algorithm (subroutine).

Assignment operator. It sets or changes the current value of some variable. This changes the content of a specific memory element allocated for this variable. Since the goal of any algorithm is to obtain the desired value in a certain memory location, almost any program contains this operator. I/O operators. Standard data entry procedures are used to determine the initial values ​​of certain variables and consist of a procedure name and an input list containing the names of the variables whose values ​​will be entered from the keyboard or from a file, i.e. Variables will be assigned specific values.
More often, to determine the initial values, it is more convenient to use the input command rather than the assignment command, because if you need to use the program with different initial data, you do not have to change the program text.
If the algorithm record contains an input command, then its execution is interrupted and control is transferred to a program that can enter data. After entering the data, control is transferred to the next command of the algorithm.
In Pascal, the data entry procedure looks like this:
READ(input list);
READLN (input list).
When the READ and READLN procedures are executed, the program enters the state of waiting for data input. If several variables are specified in the input list, then they can be entered on one line, separated from each other by a space character, or in separate lines (in a column), completing the entry of each value with the Enter key.
The procedure will not complete until values ​​have been entered for all the variables in the list. The type of entered values ​​must match that of the corresponding variable.
The READLN statement differs from the READ statement in that after entering the required amount of data, the cursor moves to the next line.
If data is entered from the keyboard, then the input list is a list of variables, i.e. a sequence of variable names separated by commas. If input is from a file, then the first variable in the input list is the file variable, associated with the name of the real file.
Standard procedures for outputting calculation results are used to display their values ​​on a screen, printer, or file. In Pascal, the inference procedures look like this:
WRITE(output list);
WRITELN (output list).
The list of output elements is much wider than in input procedures. This may include:
identifiers of quantities whose values ​​will be output to the corresponding device or file;
expressions whose value will first be calculated and then output to the device;
became values ​​(numeric, symbolic, string).
The difference between WRITE and WRITELN is that the output of the WRITE statement starts from the current location of the cursor on the monitor screen and the cursor remains on the same line after the output ends. The WRITELN statement prints the values ​​from the current position, and then the cursor moves to the next line. You can use the WRITELN statement without an output list to move the cursor to a new line.
If output is to a monitor screen, then the output list is a list of variables, or a sequence of variable names, constants, or expressions separated by commas. If the output is to a file, then the first variable in the output list is the file variable, associated with the name of the real file.
In the output command, after the output list element, you can specify the output format, separated by a colon, i.e. the width of the screen on which the values ​​will be located. When displaying real data, you can also specify the number of decimal digits in the fractional part that you want to display.
Example: write(A: 10: 3, B: 8).
Operator for calling an auxiliary algorithm. Pascal implements procedure subroutines and function subroutines. A subroutine is called by its name, indicating the actual parameters. In this case, in place of actual arguments there can be specific values, names of actual variables, expressions, and in place of results - only names of actual variables. In this case, the number, types and purpose of formal and actual parameters in the corresponding lists of parameters must match.

Linear is a program that is a recording of a linear algorithm. In such a program, all statements are executed strictly sequentially, i.e. after executing each of them (except END), the computer automatically proceeds to executing the next statement.

Drawing up simple programs

The simplest we will call linear programs that do not contain arrays. The compilation of such programs requires knowledge of the previously discussed operators, an understanding of their correspondence to the blocks of the algorithm diagram, and is carried out according to this simple rule:

consider the blocks of the algorithm diagram (we think, that it is given) in order, starting from the first one, and for each of them we write the corresponding operator BASIC, i.e.

for block Start- REM statement with the program name;

for block Enter - input operator;

for block Process - assignment operator;

for block Conclusion - output operator;

for block Stop- END operator.

That's the whole rule!

Now we give examples of specific programs of the type under consideration.

Problem 12.2

Calculate the perimeter of a right triangle given the lengths of its legs.

Problem 12.3

Rearrange the values ​​of quantities A and B.

Solution problems 12.2 and 12.3. These problems were discussed in Chapter 10, so in Fig. 12.2 shows, without explanation, the diagram of the algorithm and the program of problem 10.2, and in Fig. 12.3 - the same for problem 10.3.

In Fig. 12.2 and 12.3, arrows show the correspondence of program statements to the blocks of the algorithm diagram.

Let us present programs for solving two more problems. The program for Problem 12.1 illustrates the use of different types of quantities. The program for Problem 12.2 demonstrates the organization of data output to a printing device.

Rice. 12.2

Problem 12.1

Calculate values U and Z according to the formulas:

Where IN And IN - whole quantities.

Solution

Initial data: E%, V%, C, X, A(a).

Result: Y,Z%.

The order of operations here is obvious, so let’s write the program right away:

• 10 REM TASK 1
• 20 PRINT "ENTER D%, B%, C, X, A"
• 30 INPUT D%,B%, C, X, A 40 R$="HBAH0B, 10A CL"
• 50 Z%=2*D%-3*B%
• 60 Y=(3*ABS(X)+C:(1/3)+SIN(A)/COS(A))*Z%
• 70 PRINT "Z%=";Z%; "Y="; Y 80 PRINT R$
• 90 END

Problem 12.2

Calculate the value of the function Y = L 2 + B 1 and print (output to a printer) the values ​​of the initial data and results.

Solution

Function calculation program Y:

• 20 REM PRINT OUTPUT 30 PRINT "ENTER A, B"
• 40 INPUT A, B 50 U=A L 2+V L 2
• 60 LPRINT "DATA:"," A=";A;" B=";B 70 LPRINT
• 80 LPRINT "RESULT:"," Y=";Y 90 END

The operator in the 30th line of this program displays text on the display screen, and operators 60-80 - on the printer. The operator on line 70 prints a blank line on a piece of paper.

Linear programs with arrays

Arrays in the BASIC language. Let's recall the definition of an array: array is an ordered collection of homogeneous quantities, each designated by the same name with different integer indices varying in order.

BASIC uses one- and two-dimensional arrays (even eight-dimensional ones are acceptable in QBASIC). They, like simple variables, can be various types: integer, real, text (string), etc.

Attention! In BASIC there are no operations for processing arrays in general, i.e. operations of the form “enter array P(1:99)”, which we are accustomed to using in Chapters 8 and 9. To perform an operation on an array, it is necessary to list the operations performed on each of its elements.

Let's consider general view array element in BASIC:

• - element of a one-dimensional array: (To);
• - element of a two-dimensional array: (i,j),

Where - the array name must follow the same rules as the name of a simple variable;

To - index(number) of an element of a one-dimensional array, k

i ,j - indices element of a two-dimensional array (the number of the row and column at the intersection of which it is located), i > 0, j > 0. In QBASIC, you can set the initial values ​​of k, i, j to 1. The indices k, i, j can be represented by any arithmetic expressions . When evaluating an expression representing an index in QBASIC, the result is rounded to the nearest integer.

Examples of writing array elements:

P$(0), C2(101) , X(4 b.5*K+1) , T%(N/2, M) .

In the algorithm diagram, the same elements would have the following designations: P 0,

S2yu1, X46.5?+i, T w /2>m-

Attention! If the program uses an array, it must be previously declared, i.e. The computer must be informed of the type and size of this array using the DIM statement.

Example: operator DIM Р$(6), i_iB% (4,8) reports the presence in the program

text P(0:6) and integer B(0:4, 0:8) arrays.

Based on the information contained in the DIM statement, the computer allocates (reserves) a memory area of ​​the required size for each array.

General view of the DIM operator:

In the case of a one-dimensional array:

DIM (d)

In the case of a two-dimensional array:

DIM (p, w)

where DIM is the name of the operator (from the word dimension - "dimension"); - array name; d, p, w- array dimensions, i.e. d- number of the last element of a one-dimensional array; n(m)- the number of the last row (last column) of a two-dimensional array.

The size of an array is expressed in most versions of BASIC (including QBASIC) as an integer or an integer variable.

Features of recording the DIM operator:

• 1) in one DIM statement you can declare any number of arrays (see example);
• 2) the DIM statement is recommended to be placed at the beginning of the program;
• 3) you should not use a simple variable and an array with the same name in the program.

Example: operator DIM D% (2), A (2,3), K$ (3) reports:

• array D% - one-dimensional integer containing elements D%(0), D%(1), D%(2);
• array K is a one-dimensional text array, includes elements K$(0), k$(1), K$(2), K$(3);
• array A is a two-dimensional real array, includes the following elements:

Drawing up linear programs with arrays. First of all, let's note the features of working with arrays in the program.

1. Array elements are assigned values ​​using input or assignment operators as simple variables. When inputting (outputting) arrays, input (output) statements list the names of all input (output) elements of the array.

Example: The input and output program for the array P (1:3) can look like this:

• 20 DIM P(3)
• 30 INPUT P(1), P(2), P(3)
• 40 PRINT P(1), P(2), P(3)
• 50 END
• 2. All arrays can be divided into two types:
  • constant size arrays(for example, P(1:7), B(1:4, 1:8)];
  • variable size arrays[for example, A(1:&); C(1 :T, 1: d). In Chapters 8 and 9 we used both types without distinguishing between them.

In some versions of BASIC, the DIM operator does not allow declaring arrays of variable size, so using them in a program requires some tricks. In the versions of BASIC discussed in the manual, there are no such restrictions; it is permissible to use arrays of any type.

You just have to remember: variables - array sizes must be determined before calling the DIM operator.

Example:

10 INPUT M 20 DIM X(M)

Linear programs with arrays are compiled in accordance with the previously discussed rule for composing the simplest programs, which can be supplemented with one point - “after the REM operator, the DIM operator should be written in the program.” In addition, you need to take into account the information just outlined about working with arrays.

Now we will show the construction of the programs in question using specific examples. First, let's return to problem 8.5. Its algorithm diagram is shown in Fig. 10.11. By replacing each block of this circuit with the corresponding operator according to the rule given in 12.2, and adding the DIM operator, we obtain the program below. After familiarizing yourself with this program, we recommend that the reader create a program for solving Problem 10.7 himself and compare it with the one below:

• 10 REM AMOUNT
• 20 DIM B(3, 3), S(2)
• 30 PRINT "ENTER MATER. IN(3, 3)"
• 4 0 INPUT B(1, 1), B(1, 2), B(1, 3)
• 50 INPUT V(2, 1), V(2, 2), V(2, 3)
• 60 INPUT V(3, 1), V(3, 2), V(3, 3)
• 70 S(l) =B (1, 1)+B(1, 2) +B (1, 3)
• 80 S (2) =B (1, 3) +B (2, 3)+B (3, 3)
• 90 PRINT "S(1)="; S(1); "S(2)=";
• S (2)
• 100 END
• 10 REM SHIFT 20 DIM B(4)
• 30 PRINT "ENTER ARRAY IN (4)"
• 40 INPUT B(1), B(2),

• 50 D=B(1)
• 60 V(1)=V(2)
• 70 V(2)=V(3)
• 80V(3)=V(4)
• 90 V(4)=D
• 100 PRINT "ARAY B=(";
• 110 PRINT B(1); B(2);

B (3) ; B (4); ") "

Security questions

• 1. Which operator in BASIC indicates the type and size of an array?
• 2. What is the notation for array elements in BASIC? What is the smallest index value of an array element?

Problems to solve independently

• 2. Calculate the arithmetic mean of the variables V, C I.
• 3. Workers Ivanov and Petrov produced parts A and B, respectively, during the shift, exceeding the norm. Determine the percentage of exceeding the norm (norm - From parts per shift).
• 4. Determine the difference in the age of brides for two brothers Petya and Dima. Their age A And b respectively. The bride's age is determined by the formula

where (7 is the age of the groom.

5. Calculate value y:

Where

Let's accept kf 0; g,f 0.

• 6. Calculate the volume and surface area of ​​a cylinder with a diameter ABOUT and height N.
• 7. Calculate the cost of a furniture set containing four chairs, two armchairs and one table. The cost of products is respectively A, B and C rub.
• 8. Determine the arithmetic mean of the elements of the array C(1:5).
• 9. Determine the product of the sums of the elements of each row of the matrix P(1:2, 1:3).
• 10. Rearrange the corresponding elements of the first and second rows of matrix A(1:2, 1:2).
• 11. Rearrange the elements of the array R(1: 6): 1st element and 6th, 2nd and 5th, 3rd and 4th.

A program is called linear if all its statements are executed sequentially, in the order in which they are written. This is the simplest type of program.

Variables

A variable is a value that, while the program is running, can -

change its meaning. All variables used in the program must be described in the variable description section, beginning with the function word var.

For each variable, its name and type are specified, for example:

var number: integer; x, y: real; option: char;

The variable name specifies the location in memory where the variable's value is located. The name is given by the programmer. It should reflect the meaning of the stored value and be easily recognizable.

The type of variables is selected based on the range and required accuracy of data representation.

When declaring, you can assign a variable an initial value, i.e. initialize her. Initialization means setting a value that is performed before the program starts running. Initialized variables are declared after keyword const:

const number: integer = 100; x: real = 0.02; option: char = "yu";

By default, all variables defined in the main program are set to zero.

Expressions

An expression is a rule for calculating a value. The expression involves -

operands, united by operation signs. The operands of an expression can be constants, variables, and function calls. Operations are performed in in a certain order in accordance with priorities, as in mathematics. To change the order of operations, use parentheses, the level of their nesting is practically unlimited.

The result of an expression is always a value of a certain type, which is determined by the types of the operands. The quantities involved in the expression must be compatible types.

• 1. Unary operation not, unary minus -, taking the address @.
• 2. Multiplication type operations:* / div mod and shl shr.
• 3. Operations like addition: + - or xor.
• 4. Relational operations: = o = in.

The functions used in the expression are evaluated first

Examples of expressions:

t + sin (x)/2 * x - the result is of real type; A

(x > 0) and (y

Program structure

A PASCAL program consists of an optional header, a description section, and a statement section:

program name; (heading) sections of descriptions begin section of statements end. (* program ends with a dot *)

The program may contain comments, enclosed in curly braces () or in brackets of the form (* *).

The general structure of the program is shown in Fig. 2.1.

The statements section contains the executable statements of the program. The keywords begin and end are not operators, but serve to combine them into the so-called compound operator or block. The block can be written anywhere in the program where a regular statement is acceptable.

Description sections come in several types: descriptions of modules, constants, types, variables, labels, procedures and functions.

A module is a library of resources (subroutines, constants, etc.) that is connected to the program.

Rice. 2.1.

The module description section, if present, should come first. The description begins with the keyword uses, followed by a comma-separated list of all modules connected to the program, both standard and self-made, for example: uses crt, graph, my_module;

The number and order of the remaining sections are arbitrary; there is only one limitation: any value must be described before its use. The end of a description section is indicated by the beginning of the next section. A program may have several description sections of the same type, but to simplify the program structure, it is recommended to group all similar descriptions into one section.

In the variable description section, you must define all the variables that will be used in the main program.

The constant description section is used so that instead of the values ​​of constants, their names can be used in the program. There is another use for the constant declaration section: it describes variables that need to be assigned a value before the program can run:

const weight: real = 61.5; n = 10;

The label description section begins with the keyword label, followed by a comma-separated list of all labels found in the program. A label is either a name or a positive number not exceeding 9999. The label is placed before any executable statement and is separated from it by a colon. Example of label description: label 1, 2, error;

Labels are used to organize the transition to a specific operator using unconditional jump operator goto.

Input-output procedures Any program interacts with external devices when inputting initial data and outputting results. A set of standard input and output devices, i.e. keyboard and display screen, called console.

Keyboard input. The following procedures are defined for keyboard input: read and readln: read(list); readln[(list)];

The list of variable names separated by commas is indicated in parentheses. Square brackets indicate that the list may not be present. For example:

read(a, b, c); readln(y); readln;

ATTENTION

You can enter integer, real, character and string values. Input values ​​must be separated by any number of whitespace characters (space, tab, newline).

Entering the value of each variable is done as follows:

• ? the value of the variable is highlighted as a group of characters located between delimiters;
• ? these symbols are converted into an internal representation form corresponding to the type of the variable;
• ? the value is written to the memory location identified by the variable name.

In addition, the readln procedure, after entering all the values, moves to the next line of the source data. The readln procedure without parameters simply waits for the Enter key to be pressed.

Features of entering characters and strings is that the whitespace characters in them are no different from all the others, so they cannot be delimiters.

Output to screen. When output is executed inverse conversion: from internal representation to characters displayed on the screen. For this purpose, the language defines standard procedures write and writeln: write (list); writeln[(list)];

The write procedure displays the values ​​specified in the list on the screen, and the writeln procedure, in addition to this, also moves the cursor to the next line. The writeln procedure without parameters simply moves the cursor to the next line.

You can output values ​​of logical, integer, real, character and string types. The list may contain not only variable names, but also expressions, as well as their special case- constants. In addition, for each output value you can set it format, for example: writeln(a:4, b:6:2);

After the variable name A The colon indicates the number of positions allocated for it, within which the value is aligned to the right. For b two format specifications are indicated, meaning that only six positions are allocated for this variable, two of them for the fractional part.

15. Analytical methods. Linear programming methods.

15.1. Analytical methods

Throughout his entire evolution, man, when performing certain actions, sought to behave in such a way that the result achieved as a consequence of some action turned out to be, in a certain sense, the best. Moving from one point to another, he sought to find the shortest possible path. When building a dwelling, he looked for a geometry that would provide acceptable living conditions with the least fuel consumption. While building ships, he tried to give them a shape in which the water would offer the least resistance. The list of similar examples can easily be continued.

The best solutions to problems in a certain sense are usually called optimal. Currently, no problem can be solved without the use of optimization principles. complex problem. When setting and solving optimization problems, two questions arise: what and how to optimize?

The answer to the first question is obtained as a result of an in-depth study of the problem to be solved. The parameter that determines the degree of perfection of the solution to the problem that has arisen is identified. This parameter is usually called target function or quality criterion. Next, a set of quantities is established that determine the objective function. Finally, all the constraints that must be taken into account when solving the problem are formulated. After this, a mathematical model is constructed, which consists in establishing the analytical dependence of the objective function on all arguments and the analytical formulation of the constraints associated with the problem. Next, we begin to search for an answer to the second question.

So, let, as a result of the formalization of the applied problem, it is established that the objective function is , where the set X is a generalization of constraints, it is called the set of admissible solutions. The essence of the optimization problem is to search for such a solution on the set X - the set of feasible solutions
, at which the target function f reaches its minimum or maximum value.

An integral part of optimization methods is linear programming.

15.2. Basic concepts of linear programming

The first mention (1938) of mathematical methods in effective production management belongs to the Soviet mathematician L. V. Kantorovich. A year later, in 1939, L. V. Kantorovich published the work “Mathematical methods of organizing and planning production” and practically applied the results obtained. The term “linear programming” was introduced by American mathematicians J. Danzig and T. Koopmans in the late 40s. J. Dantzig developed the mathematical apparatus of the simplex method for solving linear programming problems (1951). The simplex method is used to solve a wide range of linear programming problems and is still one of the main methods.

Linear programming is a branch of mathematics focused on finding an extremum (maximum or minimum) in problems that are described linear equations. Moreover, linear equations describe both the objective function itself and the input parameters (variables) and the conditions of restrictions on the input parameters. A necessary condition for linear programming problems is the obligatory presence of restrictions on resources (raw materials, materials, finance, demand for manufactured products, etc.). Another important condition for solving the problem is the choice of the criterion for stopping the algorithm, i.e. the objective function must be optimal in some sense. The optimality of the objective function must be expressed quantitatively. If the target function is represented by one or two equations, then in practice such problems can be solved quite easily. The algorithm stopping criterion (or optimality criterion) must satisfy the following requirements:

be the only one for a given task;

measured in units of quantity;

linearly depend on the input parameters.

Based on the above, we can formulate the linear programming problem in general form:

find the extremum of the objective function

under restrictions in the form of equalities:

(2.2)

under restrictions in the form of inequalities:

(2.3)

and conditions of non-negativity of input parameters:

In short form, the linear programming problem can be written as follows:

(2.5)

given that

Where
- input variables;

Numbers are positive, negative and equal to zero.

In matrix form, this problem can be written as follows:

Linear programming problems can be solved analytically and graphically.

15.3. Canonical linear programming problem

, i=1,…,m,

, j=1,…,n.

The main computational methods for solving linear programming problems were developed specifically for the canonical problem.

15.4. General linear programming problem

It is necessary to maximize (minimize) a linear function of n variables.

under restrictions

, i=1,…, k,

, i=1+ k,…, m,

, …,

Here k≤ m, r≤ n. The standard problem is obtained as a special case of the general one with k= m, r= n; canonical – at k=0, r= n.

Example.

The confectionery factory produces several types of sweets. Let's call them "A", "B" and "C". It is known that the sale of ten kilograms of sweets “A” gives a profit of 90 rubles, “B” - 100 rubles and “C” - 160 rubles. Candy can be produced in any quantity (sales are guaranteed), but supplies of raw materials are limited. It is necessary to determine what kind of sweets and how many tens of kilograms need to be produced so that the total profit from sales is maximized. The consumption rates of raw materials for the production of 10 kg of sweets of each type are given in Table 1.

Table 1. Raw material consumption rates

for production

The economic and mathematical formulation of the problem has the form

Find such variable values X=(x1, x2, x3), to

objective function

under conditions-restrictions:

Connection