Linear programs. Linear programs - abstract Drawing up the simplest programs

1.2 Briefly about linear programming.

What is linear programming? This is one of the first and most thoroughly studied areas of mathematical programming. It was linear programming that was the section from which the very discipline of "mathematical programming" began to develop. The term "programming" in the name of the discipline has nothing to do with the term "programming (ie writing programs) for a computer", since the discipline "linear programming" arose even before the time when computers began to be widely used in solving mathematical, engineering , economic and other tasks. The term "linear programming" arose from an inaccurate translation of the English "linear programming". One of the meanings of the word "programming" is making plans, planning. Therefore, the correct translation of "linear programming" would not be "linear programming", but "linear planning", which more accurately reflects the content of the discipline. However, the term linear programming, non-linear programming, etc. in our literature have become generally accepted.

So, linear programming emerged after the Second World War and began to develop rapidly, attracting the attention of mathematicians, economists and engineers due to the possibility of 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, control and planning problems, optimal equipment placement, etc.

Problems of linear programming are those in which both the objective function and 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 a linear objective function under m constraints in the form of linear equalities or inequalities.

Linear programming is the most commonly used optimization technique. The tasks of linear programming include:

· Rational use of raw materials and materials; cutting optimization tasks;

· Optimization of the production program of enterprises;

· Optimal location and concentration of production;

· Drawing up an optimal transportation plan, transport work;

· Management of production stocks;

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

Thus, according to the estimates of American experts, about 75% of the total number of applied optimization methods is accounted for by 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 statements 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 research methods and finding the highest and lowest values. linear function, on whose unknowns are superimposed linear constraints... Thus, linear programming problems are related to problems for the conditional extremum of a function.

1.3 The main task of linear programming

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

{1.1}

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

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

Any set of variables that satisfies Eqs. (1.1) is called a feasible solution to the OZLP.

The optimal solution is that 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, you can go to the main task of linear programming.

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 that are also non-negative.

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

The coefficients in the 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. Solution of the linear programming problem using the simplex method. Direct task. The problem of linear programming for any vertex in a compact form can be represented as follows: To obtain, we use the algorithm given in ...

Rays emanating from one point is called a polyhedral convex cone with apex at a given point. 1.4 Mathematical foundations of solving a linear programming problem in a graphical way 1.4.1 Mathematical apparatus To understand everything that follows, 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 = ...

Tasks f1 (x) = max = g1 (x) - for the first enterprise; - for other enterprises. Solution of the problem of optimal distribution of funds between enterprises by the method of dynamic programming Table 12 Funds with, 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 ...

Put in such a simplex table the current basic variables equal to Ai, 0, and free ones equal to zero, then the optimal solution will be obtained. 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, computations according to the rules of the simplex method turn into a straight line ...

If in a program all statements are executed sequentially, one after another, such a program is called linear. Consider, as an example, a program that calculates the result using a given formula.

Task 1.1. Formula calculation

Write a program that converts temperature in degrees Fahrenheit to degrees Celsius using the formula:

where C is Celsius temperature and F is Fahrenheit temperature.

Before writing any program, it is necessary to clearly define what needs to be entered into it and what we should get as a result.

In this case:

The initial data is one real number, which is the temperature in Celsius,

The result is another real number.

Before writing the program, let's open the integrated Visual C ++ environment:

Start / Programs / Microsoft Visual Studio / Microsoft Visual C ++ 6.00

1) File> New ...

2) In the window that opens:

Select the type Win32 Console Application;

Enter a name for the project in the Project Name text box;

Enter (select using the ... button) the name of the directory where the project files are located in the Location text box, for example G: / ASOIZ /

Left-click on the OK button.

3) the Win32 Console Application - Stepl of 1 dialog opens and in it:

Select the type An empty project;

Click on the Finish button.

4) After clicking, the New Project window will appear, in which click on the OK button.

1) File > New .... This will open the New dialog box.

2) On the Files tab:

Select the file type (in this case: C ++ Source File);

In the File Name text box, enter the desired file name;

The Add to project checkbox must be enabled;

Click the OK button.

We type the following program text:

Let's consider each line of the program separately.

At the beginning of the program, a preprocessor directive is written, according to which the header file is connected to the source code of the program ... This is the file that contains the descriptions of the cin and cout I / O operators.

Any C ++ program consists of functions, one of which must have the name main, indicating that it is from this function that the program starts. The body of the function is written after the parentheses in curly braces (), i.e. those statements that you want to execute.

When writing a program, any template looks like this:

#include<…>

declaration of variables;

input of initial data;

calculation of the result;

output of the result;

To store the initial data and results, you need to allocate enough space in random access memory... Operator 2 is used for this. In our program, we need to store two values: temperature in Celsius and temperature in Fahrenheit, so two variables are defined in the operator. One, for keeping the temperature in Fahrenheit, is called fahr, the other (in Celsius) - cels. The names of the variables are given by the programmer, based on their purpose. The name can only consist of Latin letters, numbers and underscore and must not start with a number.

When describing any variable, you must specify it a type. Since the temperature can take on not only integer values, the real type is chosen for the variables float.

Basic types:

int (short, unsigned) - integers,

float (double, long double) - real

char - character

bool - boolean

In order for the user of the program to know at what moment it is required to enter data from the keyboard, the so-called prompt for input (operator 3) is applied. The specified in the operator is displayed on the screen. cout a string of characters, and the cursor moves to the next line. To move to the next line, use endl.

In statement 4, one number is entered from the keyboard into a variable fahr... For this, the standard object is used cin and the extract (read) operation >>. If more than one value is required, the chain of operations >> is used.

Statement 5 evaluates the expression written to the right of assignment operations(denoted by the = sign), and the result is assigned to the cels variable, that is, it is stored in the memory allocated to this variable. First whole constant 5 will be divided by kiss constant 9, then the result of this operation is multiplied by the result of subtracting 32 from the variable fahr.

To display the result in statement 6, the object is used cout. A chain of five elements is displayed. This is the line "Fahrenheit:", the value of the variable fahr, line ", in degrees Celsius:", the value of the variable cels and the transition operator to new line endl.

The last operator (operator 7) of this program is intended to return from it and transfer the value to the external environment.

Next, we compile the program. To do this, press the button on the toolbar or the key combination Ctrl + F7. The output window (at the bottom of the screen) should display the message 0 error (s), 0 warning (s) (0 errors, 0 warnings). If there are errors, check with the original.

To start the program, press the button on the toolbar or the key combination Ctrl + F5.

When starting the program, instead of Russian characters, we see ???, which is caused by different standards for encoding Cyrillic characters in operating systems MS DOS and Windows. To fix it, add the CharToOem function to the program (additions are highlighted in red for clarity)

#include

char * RUS (const char * text)

CharToOem (text, buf);

float fahr, cels;

cout<

cels = 5/9 * (fahr - 32);

cout<

Function Rus () cannot be used more than once in a chain of operations<< для одного объекта cout so we split it in two.

As you can see, the result of executing the program with stability is zero! This is due to the way the expression is evaluated. Let's look at operator 4 again. Constants 5 and 9 are of integer type, so the result of their division is also integer. Naturally, the result of further calculations cannot be anything other than zero. It is easy to fix this error - it is enough to write at least one of the constants as a real number, for example:

cels = 5. / 9 * (fahr - 32);

A linear program is a program, all the statements of which are executed sequentially, in the order in which they are written. This is the simplest kind of program.

Variables

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

change its value. All variables used in the program must be described in the section describing variables, beginning with the service word var.

Each variable is assigned its name and type, for example:

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

The variable name defines the location in memory where the value of the variable 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 precision of data representation.

When declaring, you can assign some initial value to a variable, i.e. initialize her. Initialization means setting a value before the program starts running. Initialized variables are described after the const keyword:

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

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

Expressions

An expression is a rule for evaluating a value. The expression involved -

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

The result of an expression is always a value of a specific 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. Operations like multiplication: * / div mod and shl shr.
3. Operations such as addition: + - or xor.
4. Operations of the relation: = o = in.

Functions used in an 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 PASKAL program consists of an optional title, description sections and a statement section:

program name; (title) description sections begin statement section end. (* program ends with a dot *)

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

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

The statements section records the executable statements of the program. The begin and end keywords are not operators, but are used to combine them into a so-called compound operator, or block. The block can be written anywhere in the program where an ordinary operator is allowed.

Description sections are of 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 the modules connected to the program, both standard and custom-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 using it. The end of the description section is the beginning of the next section. A program can have several description sections of the same type, but to simplify the structure of the program, it is recommended to group all descriptions of the same type into one section.

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

The section describing constants is used so that instead of the values of constants, you can use their names in the program. There is one more use of the section describing constants: it describes variables that need to be assigned a value before starting the program:

const weight: real = 61.5; n = 10;

The label description section begins with the label keyword, followed by a comma-separated listing of all labels encountered 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 separated from it by a colon. An example of label descriptions: 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, when inputting initial data and outputting results, interacts with external devices. A set of standard input and output devices, i.e. keyboard and display screen is called console.

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

A comma-separated list of variable names is indicated in brackets. Square brackets indicate that the list may not be present. For instance:

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, tabulation, line feed).

Entering the value of each variable is done like this:

? the value of the variable is highlighted as a group of characters located between the delimiters;
? these characters are converted to an internal representation 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, switches to the next line of the original data. A readln routine with no parameters just waits for the Enter key to be pressed.

Character and string input feature consists in the fact that the whitespace characters in them are no different from all the others, therefore they cannot be delimiters.

Output on display. On output, the inverse conversion is performed: from the internal representation to the characters displayed on the screen. For this, the language defines the 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 display 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 displayed value, you can set it format, for example: writeln (a: 4, b: 6: 2);

After the variable name a the number of positions allocated for it is indicated, separated by a colon, within which the value is right-justified. For b there are two format specifications, meaning that only six positions are allocated for this variable, and two of them are for the fractional part.

15. Analytical methods. Linear programming methods.

15.1. Analytical methods

Throughout his evolution, a person, performing certain actions, has sought to behave in such a way that the result achieved as a result of a certain action is in a certain sense the best. Moving from one point to another, he tried to find the shortest possible path. When building a dwelling, he was looking for such a geometry of it, which, with the lowest fuel consumption, provided acceptably comfortable living conditions. While building ships, he tried to give them such a shape in which water would provide the least resistance. The list of similar examples can easily be continued.

In a certain sense, the best solutions to problems are called optimal... No more or less complex problem is currently not solved without the use of optimization principles. When formulating and solving optimization problems, two questions arise: what and how to optimize?

The answer to the first question is obtained as a result of a deep study of the problem to be solved. The parameter is identified that determines the degree of perfection of the solution to the problem that has arisen. This parameter is commonly referred to as target function or quality criterion... Next, a set of values is established that determine the objective function. Finally, all the constraints that must be taken into account when solving the problem are formulated. After that, a mathematical model is built, 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, they start looking for an answer to the second question.

So, let it be established as a result of the formalization of the applied problem that the objective function, where the set X is a generalization of constraints, is called the set of feasible solutions. The essence of the optimization problem lies in the search on the set X - the set of feasible solutions for such a solution
, at which the objective function f reaches the lowest or highest value.

Linear programming is an integral part of optimization methods.

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 his work "Mathematical Methods for Organization and Planning of Production" and practically applied the results obtained. The term "linear programming" was introduced by the American mathematicians J. Danzig and T. Koopmans in the late 1940s. J. Danzig 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 by linear equations. Moreover, linear equations describe both the objective function itself and the input parameters (variables) of the conditions of constraints on the input parameters. A necessary condition for linear programming problems is the mandatory presence of restrictions on resources (raw materials, materials, finances, demand for manufactured products, etc.). Another important condition for solving the problem is the choice of the criterion for stopping the algorithm, that is, the objective function must be optimal in a certain sense. The optimality of the objective function should be expressed quantitatively. If the objective function is represented by one or two equations, then in practice such problems are 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;

depend linearly on the input parameters.

Based on the foregoing, it is possible to formulate the linear programming problem in general form:

find the extremum of the objective function

under equality constraints:

(2.2)

under constraints in the form of inequalities:

(2.3)

and the conditions of non-negativity of the input parameters:

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

(2.5)

provided

where
- input variables;

The numbers are positive, negative, and zero.

In matrix form, this task 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 are developed specifically for the canonical problem.

15.4. General linear programming problem

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

with 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 for k= m, r= n; canonical - for k=0, r= n.

Example.

The confectionery factory produces several varieties of sweets. Let's call them conditionally "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 ensured), but raw materials are limited. It is necessary to determine what kind of sweets and how many tens of kilograms must be produced in order for the total profit from the sale to be maximum. The consumption rates of raw materials for the production of 10 kg of each type of candy are shown in Table 1.

Table 1. Rates of consumption of raw materials

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: