What is a linear program. Briefly about linear programming. Linear programs with arrays

Above, we have considered various practical tasks that come down to the scheme linear programming... In one of these tasks linear constraints looked like inequality, in others - equalities, in others - both.

Here we will consider a linear programming problem with equality constraints - the so-called basic linear programming problem (0PLP).

In what follows, we will show how one can go from a problem with inequality constraints to an LPLP, and vice versa.

The main task of linear programming is as follows.

There are a number of variables

It is required to find such non-negative values of these variables that would satisfy the system linear equations:

and, moreover, would minimize linear function

Obviously, the case when a linear function 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

Let us agree to call any set of variables

satisfying equations (2.1).

The optimal solution is that of the feasible solutions for which the linear function (2.2) becomes a minimum.

The basic linear programming problem does not have to have a solution.

It may turn out that equations (2.1) contradict each other; it may turn out that they have a solution, but not in the region of non-negative values. Then the OZLP has no feasible solutions. Finally, it may turn out that feasible solutions of the DLP exist, but among them there is no optimal one: the function L in the region of feasible solutions is unbounded from below.

We will get acquainted with examples of such features of the OZLP in the future.

Let us consider, first of all, the question of the existence of admissible solutions to the LPLP.

When solving this question, we can exclude from consideration the linear function L, which must be minimized - the presence of feasible solutions is determined only by equations (2.1).

So, let there be a system of equations (2.1). Are there non-negative values that satisfy this system? This question is considered in a special section of mathematics - linear algebra.

Let us give a brief summary of some statements of linear algebra, without dwelling on the proofs of the corresponding theorems

The matrix of the system of linear equations

is called a table composed of coefficients at

The extended matrix of a system of linear equations is the same matrix, supplemented by a column of free terms:

The rank of a matrix is the greatest order of a nonzero determinant that can be obtained by deleting some rows and some columns from the matrix.

In linear algebra, it is proved that for the system of linear equations (2.1) to be compatible, it is necessary and sufficient that the rank of the matrix of the system be equal to the rank of its extended matrix.

Example 1. A system of three equations with four unknowns is given:

Determine if the system is collaborative?

Solution. System Matrix:

Extended Matrix:

Let us determine the rank of the first matrix. It cannot be more than 3 (since the number of rows is 3). Let's compose some determinant by deleting some column from the matrix, for example, the last one. We get

Calculating this determinant according to the well-known rule, we get:

This determinant is not equal to zero, which means that the rank of the matrix of the system is 3. Obviously, the rank of the extended matrix is also equal to 3, since the same determinant can be made from the elements of the extended matrix. It follows from the equality of the ranks of the matrices that the system of equations is consistent.

Example 2. To investigate the compatibility of the system of two equations with three unknowns:

Solution. Extended system matrix:

(its left side is the system matrix).

Let us find the rank of the matrix of the system by composing all possible second-order determinants:

So, all possible determinants of the second order, composed of the elements of the matrix of the system, are equal to zero; hence, the rank of this matrix of the system

Find the rank of the extended matrix. Determinant

Hence, the rank of the extended matrix is not equal to the rank of the matrix of the system: Грфг, therefore, the system of equations is inconsistent.

Example 3. To investigate the consistency of the system of three equations with four unknowns:

Solution Extended system matrix (together with system matrix):

Let's find the rank of the matrix of the system. Take a third-order determinant composed of its elements, for example:

It is known that if any row of the determinant is a linear combination of two of its other rows, then the determinant is equal to zero. In our case, the third row is a linear combination of the first two: to get it, it is enough to add the first row with the doubled second. Therefore.

It is easy to verify that any third-order determinant composed of the elements of the system matrix has the same property. Consequently, the rank of the system matrix.

Since there is a nonzero determinant of the second order, for example,

then the rank of the matrix of the system is

Using the same reasoning, we will make sure that the rank of the extended matrix is equal to two: Consequently, the system of equations is consistent

Note that the three equations this example are not independent: the third can be obtained from the first two by multiplying the second by two and adding to the first. Hence, the third equation is a simple consequence of the first two. There are only two independent equations in the system: this is reflected by the fact that the rank of the matrix of the system

So, if the system of equations-constraints of the LPLP is consistent, then the matrix of the system and its extended matrix have the same rank.

This overall rank is called the rank of the system; it is nothing more than the number of linearly independent equations among the constraints imposed.

Obviously, the rank of the system cannot be more than the number of equations:

It is also obvious that the rank of the system cannot be greater than the total number of variables:

Indeed, the rank of the matrix of the system is defined as the largest order of the determinant composed of the elements of the matrix; since the number of its lines is equal, then; since the number of its columns is equal, then.

The structure of the linear programming problem essentially depends on the rank of the constraint system (2.1).

Consider, first of all, the case when, that is, when the number of linearly independent equations included in system (2.1) is equal to the number of variables n. We discard the "unnecessary" equations that are linear combinations of others. The system of equations-constraints of the LPLP takes the form:

Since the determinant, composed of coefficients,

is not zero. It is known from algebra that in this case system (2.4) has a unique solution. To find the value, it is enough to replace the column in the determinant with the column of free members and divide by.

So, for the system of equations-constraints, the LPLP has a unique solution:

If in this solution at least one of the quantities is negative, this means that the resulting solution is unacceptable and, therefore, the ZZLP has no solution.

If all quantities are non-negative, then the found solution is admissible. It is, obviously, also optimal (because there are no others).

Obviously, this trivial case cannot interest us.

Therefore, in what follows we will consider only the case when, i.e., when the number of independent equations that must be satisfied by the variable numbers of the variables themselves. Then, if the system is compatible, it has countless solutions. In this case, we can assign arbitrary values to the variables (the so-called free variables), and the rest of the variables will be expressed through them (we will call these variables basic).

Linear programs are programs that consist of simple commands (operators).
Simple commands (simple instructions of the algorithm) are called commands that do not use conditions in their execution. Simple operators include assignment, input and output commands (operators), 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 get at a specific location in memory desired value, 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 some specific values.
More often, it is more convenient to use the input command to determine the initial values, rather than the assignment command, because if you need to use the program with other source data, you do not have to change the program text.
If there is an input command in the algorithm record, then its execution is interrupted and control is transferred to the program that can perform data input. After entering the data, control is transferred to the next command of the algorithm.
In Pascal, the data entry procedure is:
READ (entry list);
READLN (Entry List).
When the READ and READLN procedures are executed, the program goes into a state of waiting for data input. If several variables are specified in the entry list, then they can be entered in 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 end until values are entered for all the variables in the list. The type of input 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 the input is from a file, then the first variable in the input list is file, associated with the name of the real file.
Standard procedures for outputting the results of calculations are used to output their values to a screen, printer or file. In Pascal, inference procedures are:
WRITE (output list);
WRITELN (output list).
The list of output elements is much wider than in input procedures. It may include:
identifiers of quantities, the values of which will be output to the corresponding device or to a file;
expressions, the value of which will first be calculated and then output to the device;
have become quantities (numeric, character, string).
The difference between WRITE and WRITELN is that the WRITE statement starts at the current location of the cursor on the monitor screen, and the cursor remains on the same line after the end of the output. The WRITELN statement prints the values from the current location, 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 the output is performed on a monitor screen, then the output list is a list of variables, or a sequence of names of variables, constants, or expressions, separated by commas. If the output is carried out to a file, then the first variable in the output list is a file variable associated with the name of the real file.
In the output command, after the element of the output list, separated by a colon, you can specify the output format, i.e. the width of the screen on which the values will be located. When displaying valid data, you can also specify the number of decimal digits in the fractional part to be displayed.
Example: write (A: 10: 3, B: 8).
Operator for calling an auxiliary algorithm. In Pascal, routines-procedures and routines-functions are implemented. The subroutine is called by its name with 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 parameter lists must be the same.

Laboratory work No. 1

Topic: "Programming linear algorithms... Working with the debugger "

purpose of work

1.1 Mastering the simplest structure of a C program.

1.2 Getting skills in organizing input-output in the C language.

Technical support

2.1 Personal computer

2.2 Keyboard.

2.3 Display.

2.4 Printing device.

Software

3.1 Operating room Windows system

3.2 The programming system Visual C ++ version 6.0 or Borland C ++ version 3.1 and later.

Formulation of the problem

Writing the simplest program with data processing.

5.1 Theme and purpose of the work.

5.2 Statement of the problem.

5.3 Program text.

5.4 Program execution results.

5.5 Schemes of the algorithm of programs.

General information

Linear program

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. Calculation by formula

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 represents 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 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 begins. After the parentheses, the body of the function is written 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 (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 type of. 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 line of characters and the cursor moves to the next line. To move to the next line, use endl.

Statement 4 performs keyboard input

For this, a 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 items 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 line break operator endl.

The last statement (statement 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 various 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 go back to Operator 4. 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);