Methods optimal solutions

CONTENT

The main provisions of the discipline “Methods of optimal solutions” are the foundation of the mathematical education of a certified specialist who has important for the successful study of special disciplines that are provided for in the main educational program for this specialty.

For effective absorption educational material and obtaining final certification is necessary within the time limits stipulated curriculum, execute control tasks and provide them for checking by the teacher according to e-mail. The schedule for studying and reporting by discipline is shown in Table 1.

Table 1.Graph independent work in the discipline "Methods of optimal solutions"

1. INTRODUCTION. GENERAL FORMULATION OF THE PROBLEM

Decision-making processes are at the core of all purposeful activities. In economics, they precede the creation of production and business organizations and ensure their optimal functioning and interaction. IN scientific research– make it possible to identify the most important scientific problems, find ways to study them, and predetermine the development of the experimental base and theoretical apparatus. While creating new technology– constitute important stage in the design of machines, devices, instruments, complexes, buildings, in the development of technology for their construction and operation; V social sphere– are used to organize the functioning and development of social processes, their coordination with economic and economic processes. Optimal (effective) solutions allow you to achieve goals with minimum costs labor, material and raw materials resources.

In classical mathematics, methods for finding optimal solutions are considered in sections related to the study of extrema of functions in mathematical programming.

Optimal decision methods is one of the branches of operations research - applied direction cybernetics, used to solve practical organizational problems. Mathematical programming problems are used in various areas human activity, where it is necessary to choose one of the possible courses of action (programs of action).

A significant number of problems arising in society are associated with controlled phenomena, that is, with phenomena regulated on the basis of consciously made decisions. With the limited amount of information that was available on early stages development of society, the optimal decision was made based on intuition and experience, and then, with an increase in the amount of information about the phenomenon being studied, using a series of direct calculations. This happened, for example, in the creation of work schedules for industrial enterprises.

A completely different picture arises, for example, in a modern industrial enterprise with multi-batch and multi-item production, when the volume of input information is so large that its processing for the purpose of acceptance definite decision impossible without the use of modern electronic computers. Even greater difficulties arise in connection with the problem of making the best decision.

In the “Optimal Decision Methods” course, decision-making is understood as a complex process in which the following main stages can be distinguished:

1st stage. Construction quality model the problem under consideration, i.e., identifying the factors that seem to be the most important and establishing the patterns to which they obey. Usually this stage goes beyond mathematics.

2nd stage. Construction of a mathematical model of the problem under consideration, i.e. writing a qualitative model in mathematical terms. Thus, the mathematical model is written in mathematical symbols an abstraction of a real phenomenon, so constructed that its analysis makes it possible to penetrate into the essence of the phenomenon. A mathematical model establishes relationships between a set of variables—the parameters for controlling a phenomenon. This stage also includes the construction of a target function of variables, i.e., a numerical characteristic whose larger (or smaller) value corresponds to the best situation from the point of view of the decision being made.

So, as a result of these two stages, the corresponding math problem. Moreover, the second stage already requires the use of mathematical knowledge.

3rd stage. Study of the influence of variables on the value of the objective function. This stage involves mastering the mathematical apparatus for solving mathematical problems that arise at the second stage of the decision-making process.

A wide class of control problems consists of such extremal problems, in whose mathematical models the conditions on the variables are specified by equalities and inequalities. The theory and methods for solving these problems are precisely the content of mathematical programming. At the third stage, using mathematical tools, a solution to the corresponding extremal problems is found. Let us draw attention to the fact that mathematical programming problems associated with solving practical problems, as a rule, have big number variables and restrictions. The volume of computational work to find appropriate solutions is so great that the entire process is inconceivable without the use of modern electronic computers (computers), and therefore requires either the creation of computer programs that implement certain algorithms, or the use of already existing standard programs.

4th stage. Comparison of the calculation results obtained at the 3rd stage with the modeled object, i.e. expert verification of the results (practice criterion). Thus, at this stage, the degree of adequacy of the model and the modeled object is established within the accuracy of the initial information. There are two possible cases here:

1st case. If the comparison results are unsatisfactory (a common situation in initial stage modeling process), then proceed to the second cycle of the process. At the same time, the input information about the modeled object is clarified and, if necessary, the problem statement is clarified (stage 1); the mathematical model is refined or rebuilt (stage 2); the corresponding mathematical problem is solved (3rd stage) and finally the comparison is carried out again (4th stage).

2nd case. If the comparison results are satisfactory, then the model is accepted. When it comes to repeated use of calculation results in practice, the task of preparing the model for operation arises. Suppose, for example, that the purpose of modeling is to create calendar plans for the production activities of an enterprise. Then the operation of the model includes the collection and processing of information, entering the processed information into a computer, calculations based on developed schedule programs and, finally, issuing calculation results (in a user-friendly form) for their use in the field of production activities.

There are two directions in mathematical programming.

The first, already well-established direction - mathematical programming itself - includes deterministic problems that assume that all initial information is completely defined.

The second direction - the so-called stochastic programming - includes problems in which the initial information contains elements of uncertainty, or when some parameters of the problem are random in nature with known probabilistic characteristics. Thus, planning of production activities is often carried out in conditions of incomplete information about the real situation in which the plan will be implemented. Or, say, when an extreme problem simulates the work automatic devices, which is accompanied by random interference. Note that one of the main difficulties of stochastic programming lies in the formulation of the problems itself, mainly due to the complexity of analyzing the initial information.

Traditionally, mathematical programming is divided into the following main sections:

Linear programming – the objective function is linear, and the set on which the extremum of the objective function is sought is specified by a system of linear equalities and inequalities. In turn, in linear programming there are classes of problems, the structure of which allows you to create special methods for solving them, which compare favorably with methods for solving problems general. Thus, a section of transport problems appeared in linear programming.

Nonlinear programming – the objective function and constraints are nonlinear. Nonlinear programming is usually divided as follows:

Convex programming – the objective function is convex (if the problem of minimizing it is considered) and the set on which the extremal problem is solved is convex.

Quadratic programming – the objective function is quadratic, and the constraints are linear equalities and inequalities.

Multiextremal problems. Here, specialized classes of problems that are often encountered in applications are usually distinguished, for example, problems of minimizing concave functions on a convex set.

An important branch of mathematical programming is integer programming, when integer conditions are imposed on the variables.

The goal of mathematical programming is to create, where possible, analytical methods determining the solution, and in the absence of such methods, creating effective computational methods for obtaining an approximate solution.

Finally, we note that the name of the subject – “methods of optimal solutions” – is due to the fact that the goal of solving problems is to choose a program of action. Let's take a closer look at the linear programming problem

2. GEOMETRICAL INTERPRETATION OF THE LINEAR PROGRAMMING PROBLEM

Linear programming problem (LPP):

find the vector X = (x 1 ,x 2 ,...,x n) that maximizes the linear form

F = Σ c j x j → max (2.1)

J=1

and satisfying the conditions:

Σa ij x j ≤ b i (2.2)

J=1

x j ≥0 , j = 1,…,n (2.3)

The linear function F is called the objective function of the problem.

Let's rewrite this problem in vector form:

Let's find the functions:

F = c 1 x 1 + c 2 x 2 + … + c n x n (2.4)

x 1 P 1 + x 2 P 2 + … + x n P n = P 0 , (2.5)

x j ≥0 , j = 1,…,n (2.6)

where P 1, ..., P n and P 0 are m-dimensional vector columns, from the coefficients of the unknowns and free terms of the system of equations of the problem:

B 1 a 11 a 12 a 1n

P 0 = (b 2) ; P 1 = (a 21) ; P 2 = (a 22) ;……. P n = (a 2n) ; (2.7)

… … … …

B n a m1 a m2 a mn

The plan X = (x 1 ,x 2 ,...,x n) is called the reference plan of the main ZLP if the positive coefficients x j are at linearly independent vectors P j .

A solution polyhedron is any non-empty set of plans for the main linear programming problem, and any corner point of a solution polyhedron is called a vertex.

Theorem

If the main PPP has an optimal plan, maximum value the objective function of the problem takes at one of the vertices of the solution polyhedron.

If the objective function of a problem takes its maximum value at more than one vertex, then it takes it at any point that is a convex linear combination of these vertices.

Conclusions:

The non-empty set of plans of the main ZLP forms a convex polyhedron;

Each vertex of this polyhedron defines a reference plan;

At one of the vertices of the polyhedron, the value of the objective function is maximum.

Two-dimensional case of ZLP

Let us find a solution to the problem, which consists in determining the maximum value of the function

F = c 1 x 1 + c 2 x 2 (2.8)

under conditions

a i1 x 1 + a i2 x 2 ≤ b i , (i=1,…,k) (2.9)

x j ≥0 (j=1.2) (2.10)

The linear programming problem is to find a point in the solution polygon at which the objective function F takes on the maximum value. This point exists when the solution polygon is not empty and the objective function on it is bounded from above.

To determine this vertex, we will construct a level line c 1 x 1 +c 2 x 2 =h, (where h is some constant) passing through the solution polygon, and we will move it in the direction of the vector C = (c 1,c 2) until until it passes through its last common point with the solution polygon. The coordinates of the specified point determine the optimal plan for this task.

Stages PPP decisions geometric method:

1. Construct straight lines using equations (2.9), (2.10).

2. Find the half-planes defined by each of the constraints of the problem.

3. Find the solution polygon.

4. Construct vector C.

5. Construct a straight line c 1 x 1 +c 2 x 2 =h passing through the solution polygon.

6. Move the straight line c 1 x 1 +c 2 x 2 =h in the direction of vector C.

7. Determine the coordinates of the maximum point of the function and calculate the value of the objective function at this point.

Example 1.

To produce two types of products A and B, the company uses three types of raw materials. The consumption rates of each type of raw material for the manufacture of a unit of product of this type are given in Table 2.1. It also indicates the profit from the sale of one product of each type and the total amount of raw materials of this type that can be used by the enterprise.

Table 2.1

Considering that products A and B can be produced in any rationias (sales are ensured), it is necessary to draw up a plan for their release in whichThe maximum profit of the enterprise from the sale of all products is small

Solution:

x1 – production of products of type A

x2 – production of products of type B

Then the problem constraints:

The total profit from the sale of products of type A and B will be: F = 30x 1 + 40x 2

Let's find a solution to the problem using its geometric interpretation.

To do this, in the inequalities of the system of restrictions, let’s move on to equalities and construct the corresponding straight lines:

Let's find the coordinates of point B - the intersection of lines:

Having solved this system of equations, we get: x 1 = 12; x 2 = 18

Therefore, if an enterprise produces 12 products of type A and 18 products of type B, then it will receive a maximum profit equal to

F max = 30·12+40·18 = 1080 rub.

Example 2.

Solve the ZLP

max(min)F = 2x 1 +3x 2 ;

Solution. To build an area admissible solutions We construct boundary straight lines in the system x 1 Ox 2 that correspond to these inequality constraints:

x 1 +x 2 ≤ 6, x 1 +4x 2 ≥ 4, 2x 1 -x 2 ≥ 0.

We find half-planes in which these inequalities hold. To do this, due to the convexity of any half-plane, it is enough to take an arbitrary point through which the corresponding boundary straight line does not pass, and check whether this test point satisfies the inequality constraint. If it satisfies, then this inequality is satisfied in the half-plane containing the trial point. Otherwise, a half-plane is taken that does not contain a test point. It is often convenient to take the origin of coordinates O(0; 0) as a test point. For our example, the region of feasible solutions is the set of points of the quadrilateral ABCD (Fig. 6).

We construct a vector c = (c 1; c 2) = (2; 3). Since it is necessary only to clarify the direction of increase of the objective function, sometimes for greater clarity it is convenient to construct λc(λ > 0). Perpendicular to the vector c we draw a level line F=0. By parallel movement of the straight line F=0 we find the extreme point B at which the objective function takes the maximum value and point A at which the minimum value is achieved.

The coordinates of point B are determined by the system

Where does Fmax = F (A) = 32/9

TASKS FOR INDEPENDENT SOLUTION

Solve problems 1.1-1.10 graphically.

Problem with many variables

Consider the following linear programming problem

In order to solve it graphically, it is necessary to transform the system of restrictions in such a way that in the form of the main problem the system includes no more than 2 variables.

This can be done sequentially, excluding variables, or using the Jordan-Gauss method. Let's consider the Jordan-Gauss method.

Table 1

(-3) 1 , (-1) 3,4

table 2

(2) 1 , (-1) 2 ,(1) 3

Table 3

(-1) 2 , (1) 3 ,(2) 4

Table 4

(-1) 2 , (1) 3 ,(2) 4

Let us discard non-negative allowed unknowns in the constraint equations

x 2 , x 4 , x 5 and replace the equal sign with inequality signs, we get auxiliary task linear programming with two variables:

F (x) = 2 x 3 +2 → max

F (x) = 0: 2 x 3 +2 -0 (0;-1) ;(5;-1)

F max = 2 at x 1 = 0; x 3 = 0

3. SIMPLEX METHOD FOR SOLVING A LINEAR PROGRAMMING PROBLEM

3.1. Geometric interpretation of the simplex method

If a linear programming problem is optimized, then the optimum corresponds to the corner point (at least one) of the O.D.R. and coincides with at least one of the non-negative basic solutions. Thus, sorting through final number non-negative basic solutions of the system, we select from them the one that corresponds to the extreme value of the objective function. Graphically, this means that we go through the corner points of the solution polyhedron, improving the value of the objective function.

The simplex method consists of:

1) determining the initial acceptable basic solution tasks;

2) moving to a better solution;

3) checking the optimal feasible solution.

3.2. Tabular interpretation of the simplex method

The simplex method is used to solve linear programming problems written in canonical form:

Find the optimal solution

X = (x 1 ,x 2 ,...,x n) (3.1)

satisfying the system of constraints (equations)

Σa ij x j = b i (i=1,m) (3.2)

j=1

and conditions x j ≥ 0 (j=1,n)

and giving the extreme value of the objective function

Z(x) = Σ c j x j (3.3)

j=1

Let the initial non-negative basic solution of system (3.2) be found, where x 1, x 2, x 3 ... x m are the basic unknowns, and x m+1, x m+2, ..., x n are free unknowns.

Then system (3.2) turns into an allowed system

(3.4)

This system corresponds to a non-negative basic solution of the form

X 0 = (b 1 ,b 2 ,...,b m ,0,0...0)

Let us substitute the resulting solution into the objective function

Δ 0 = L(X 0) = Σ C j B j (3.5)

J=1

and transform it in such a way that it depends only on the free unknowns x m+1, x m+2, ... x n

All basic unknowns x 1, x 2, x 3 ... x m can be expressed in terms of free x m+1, x m+2, … x n and substitute it into the objective function.

Then the objective function will take the form (3.6)

Let us introduce the concept of estimating Δ j of free unknowns

(3.7)

Then the objective function will take the form

(3.8)

Let us introduce into consideration the vectors C = (c 1 , c 2 , …, c m) and B = (a 1j , a 2j , …, a mj) (j=m+1,n) , then equality (3.7) can be written in vector form

Δ j =CB j -c j(3.9)

Equality (3.8) is not different in character from the equations of the system, so we add it to this system and get an extended system:

The results of the transformations carried out, recorded as a system, can be entered into the following simplex table:

the first column contains the basic unknowns x 1 , x 2 , ..., x m ; Column C contains the coefficients from the objective function corresponding to these basic unknowns; in column B - free terms of the system equations, coinciding with the positive components of the initial non-negative basic solution X 0 . Under the unknowns x 1 , x 2 , …, x n the coefficients from the system are written in the columns.

The last row of this table, called the evaluation or index, p calculated using formulas. When moving from one basic solution to For another, the estimated line can also be calculated directly according to the rule square (Jordan-Gauss method).

In the evaluation line, the inequality Δ j ≥0 means the optimality criterion for the reference plan.

Algorithm for solving ZLP using the simplex method.

1. Find the reference plan.

2. Create a simplex table.

3. Find out if there is at least one a negative numberΔj

If not, then the found reference plan is optimal. If among the numbers there are Δ j negative ones, then either the unsolvability of the problem is established chi, or move on to a new reference plan.

4. Find the guide column and row. The largest column is determined by the largest negative number Δ j in absolute value , and the guide line is the minimum of the ratios of the column components of the vector P 0 to the positive components of the guide column.

5. Using formulas (3.7) – (3.9), determine the positive components new reference plan, coefficients of decomposition of vectors P j into vectors new basis and number. All these numbers are written in the new simplex table.

6. Check the found plan for optimality. If the plan is not optimal and it is necessary to move to a new reference plan, then return to point 4, and if an optimal plan is obtained or more than one time is established With determination, the process of solving the problem is completed.

Example 3.1.

To manufacture various products A, B and C, the company uses three various types raw materials. Rates of raw material consumption for the production of one product of each type, the price of one product A, B and C, as well as the total quantity raw materials of each type that can be used by the enterprise we eat, at are shown in the table.

Draw up a production plan for products in which the total cost of all products produced will be maximum.

Solution:

Let's create a mathematical model. Let's denote:

x 1 – production of products of type A;

x 2 – production of products of type B;

x3 – production of products of type C.

Let's write down the system of restrictions:

The total cost of goods produced is:

F = 9x 1 +10x 2 +16x 3

According to the economic content, the variables x 1, x 2, x 3 can only take non-negative values:

x 1 ,x 2 ,x 3 ≥0

Let's write this problem in the form of the main ZLP, for this we move from the system of inequalities to equalities, for this we introduce three additional variables:

The economic meaning of the new variables is the quantity of raw materials of one type or another that is not used in a given production plan.

Let's write the transformed system of equations in vector form:

x 1 P 1 +x 2 P 2 +x 3 P 3 +x 4 P 4 +x 5 P 5 +x 6 P 6 =P 0

Where

Since among the vectors Pj there are three unit vectors, then for this problem we can write the reference plan X = (0, 0, 0, 360, 192, 180) defined by the system of unit vectors P 4, P 5, P 6, which form the basis of three-dimensional space.

We compile a simplex table of iteration I and calculate the values ​​of F 0, z j -c j.

We check the original plan for optimality:

F 0 = (C,P 0) = 0; z 1 =(C,P 1)=0; z 2 =(C,P 2)=0; z 3 =(C,P 3)=0;

z 1 -c 1 = 0-9 = -9; z 2 -c 2 = 0-10 = -10; z 3 -c 3 = 0-16 = -16;

For basis vectors z j -c j = 0 (j=4,5,6).

The maximum negative number Δ j is in the 4th row of column P 3. Consequently, we introduce the vector P 3 into the basis. Let us define the vector to be exception from the basis, for this we find Θ 0 = min(b i /a ij) for a i3 >0 i.e. Θ = min (360/12; 192/8; 180/3) =192/8 =24.

Those. the limiting factor for the production of products C is available volume of raw materials of type II. Taking into account its availability, the enterprise can produce 24 products C, while raw materials of type II will be completely consumed vano.

Consequently, the vector P 5 must be excluded from the basis. Column vectors P 3 and 2nd row are guides.

Let's create a table for iteration II. First, we fill the line of the vector newly introduced into the basis, i.e. guide line 2. The elements of this line are obtained by dividing the corresponding elements of table 1 by enabling element (i.e. 8). At the same time, in column C b we write the coefficient patient C 3 =16, standing in the column of the vector P 3 introduced into the basis

To determine the remaining elements of Table II, we apply the triangle rule.

Let's calculate the elements of Table II in the P 0 column.

First element - find three numbers

1) the number in line 1 at the intersection of column P0 and the 1st line (360);

2) the number in point 1 at the intersection of column P3 and the 1st line (12);

3) the number in point 2 at the intersection of column P0 and the 2nd line (24).

360-12 24 = 72

The second element was calculated earlier (Θ 0 = 192/8 =24)

Third element -

1) the number in line 1 at the intersection of column P0 and the 3rd line (180);

2) the number in line 1 at the intersection of column P3 and the 3rd line (3);

3) the number in point 2 at the intersection of column P0 and the 2nd line (24).

180-3·24 =108

The value of F 0 in the 4th row of the same column can be found in two waysbami:

1) according to the formula F 0 =(C,P 0) =0·72+16·24+0·108 = 384;

2) according to the triangle rule:

Let's calculate the elements of the vector P 1 t.2. We take the first two numbers from the columntsov R 1 and R 3 v.1,

and the third number is from point 2 at the intersection of the 2nd row and column P1.

18-12 (3/ 4) = 9; 5-3 (3/ 4)=11/ 4.

Number z 1 -c 1 in the 4th row of the column of vector P 1 in table 2

can be found in two ways:

1) according to the formula z 1 -с 1 =(C,P 1)-c 1 we have:

0·9+16·3/ 4+0·11/ 4-9 =3

2) according to the triangle rule we get:

-9-(-16) 3/ 4 = 3

Similarly, we find the elements of the column of the vector P 2.

The elements of the column of the vector P 5 are calculated using the triangle rule.

look different. However, the triangles constructed to define these elements

When calculating the element of the 1st row of the specified column, the result istriangle formed by the numbers 0;12 and 1/8. Therefore, the desiredelement is equal

0 – 12 (1/8) = -3/2.

The element on the 3rd line of this column, is equal

0 - 3 (1 /8) = -3/8.

Upon completion of the calculation of all elements in Table II, it obtained butbasic plan and coefficients of expansion of vectors Р j through basicvectors P 4, P 3, P 6 and values ​​F 0 "Δ j".

As can be seen from this table, the new reference plan for the problem isplan X=(0; 0; 24; 72; 0; 108).

The problem plan found at iteration II is not optimal.

this line contains a negative number - 2. This can also be seen from the 4th line of table 2, since in the column of the vector P 2 .

This means that the vector P 2 should be entered into the basis, i.e., the new plan should provide for the production of products B.

When determining the possible number of production of products B, one should take into account the available quantity of raw materials of each type, namely: possible the output of products B is determined by min (b i "/a i 2") for a i2 ">0 i.e. we find Θ 0 = min(72/9; 24 2/1; 108 2/3) = 72/9= 8.

Consequently, vector P4 is subject to exclusion from the basis; in other words, the production of products B is limited by the raw materials of type I available to the enterprise. Taking into account the available volumes of this raw material, the enterprise should produce 8 products B. The number 9 is the resolving element, and the column of the vector P2 and the 1st row of table 2 are the guides.

Let's create a table for iteration III.

In Table III, we first fill in the elements of the 1st row, which is the row of the vector P2 newly introduced into the basis. The elements of this row are obtained from the elements of the 1st row of Table 2 by dividing the latter by the resolving element (i.e. by 9).

At the same time, in column C b of this row we write c 2 = 10.

Then we fill in the elements of the columns of the basis vectors and, using the triangle rule, calculate the elements of the remaining columns.

As a result, in Table III we obtain a new reference plan X = (0; 8; 20; 0; 0; 96) and expansion coefficients of vectors P j through the basis vectors P 1, P 2 and P 3 corresponding values ​​F 0 "" and Δ j .

We check whether the given reference plan is optimal or not. To do this, consider the 4th row, table 3. There are no negative numbers among the numbers in this line. This means that the found reference plan is optimal and F max =400.

Therefore, a production plan that includes the production of 8 products B and 20 products C is optimal. With this product production plan, raw materials of types I and II are fully used and 96 kg of raw materials of type III remain unused, and the cost of the products produced is 400 €.

The optimal production plan does not provide for the production of products A. The introduction of products of type A into the production plan would lead to a decrease in the indicated total cost. This can be seen from the 4th row of the column of vector P1, where the number 5 shows that for a given plan, including the release of a unit of product A in it only leads to a decrease in the total cost by 5 €.

Example 3.2

Fill in the initial simplex table for the following PPP:

Solution:

Let's do it next steps in this order:

-in the second line we write the unknowns x 1, x 2, ..., x 5;

- in the first line above them are the corresponding coefficients 3, -2, 1,4, -1 from the objective function;

-under the unknowns x 1 , x 2 , …, x 5 , fill in the columns composed of the corresponding coefficients of the left-hand sides of the equations of the original system;

- in the column we write down the free terms of equations 3,1,5;

-in the first column B.p. let's put the unknowns x 2 ,x 3 , x 5 , since there are unit columns under them, and therefore we will consider them basic; the basic unknowns are arranged in such an order that the units in the columns are at the intersection of identical unknowns;

-in the column we write the coefficients -2,1,-1, from the objective function for the selected basic unknowns x 2 ,x 3 , x 5 ;

- fill in the evaluation line as follows: under column B we place the number Δ 0, calculated using formula (3.5); under basic unknowns x 2 ,x 3 , x 5 - zeros, which can also be obtained from equality (3.9); under free variables x 1 , x 4 - write down the values ​​obtained from equality (3.9).

We record the results of these actions in the following table:

Let us choose the x 4 column as the resolving column, as the “badest” one (it corresponds to the largest negative estimate in absolute value). Next, we introduce the resolving line as follows: for positive coefficients of the x 4 column, we calculate the ratios b i /a i4 and write them in the column θ.

The smallest number will determine the resolution string. We do not consider negative and zero coefficients due to the non-negativity of the right-hand side of the system equations and the requirement that the objective function be at least non-decreasing.

At the intersection of the permitting row and the permitting column, select the permitting element. Let’s ensure that the resolving element is equal to one, for which we divide the entire first line by two. Next, we transform the table using the Jordan-Gauss method.

Thus, already in the table of the second step the optimality criterion is satisfied. We received the optimal plan X(0;0;11/2;3/2;13/2), max L(X) =5.