Abstract: Graphical method and simplex method for solving linear programming problems. Simplex method. The main idea, stages of searching for solutions, algorithm of the method

Finding the optimal plan. This method is universal, it allows you to solve problems linear programming any dimension in the general setting. However, this method requires a reduction original problem To canonical form.

The main idea of the simplex method is to move from one vertex of the ODR to another so that with each transition the value of the CF decreases. This is how you can get from any vertex to the optimal one and get the optimal plan.

For example: let the reference plan X =(x1,x2,…,xm,0,0,…,0) and the associated system of linearly independent vectors: A1,A2,…,Am be known, then for this reference plan you can calculate the value CF Z=(c1x1+c2x2+…+cmxm) and write down the limitation conditions in the following form x1A1+x2A2+…+xmAm=b

Since the vectors A1, A2,…, Am are linearly independent, any vector Aj can be expanded into these vectors: Aj=x1jA1+x2jA2+…+xmjAm (*) Let us introduce the values Zj Zj=x1jc1+x2jc2+…+xmjcm, where xij is the coefficient corresponding to Ai in the expansion vector Aj by basis vectors

Theorem 1: Improvement of the reference plan

If for some index j the condition Zj-Cj>0 is satisfied, then the value of the CF can be reduced and:

· if the CF is limited from below, then it is possible to construct a reference plan with a smaller CF value, the same previous

· if the TF is not limited from below, then it is possible to construct a plan corresponding to an arbitrarily small value of the TF

Theorem 2: optimality criterion for the reference plan

If for some index j in the reference plan the inequality Zj-Cj0. Let this minimum be achieved for the vector Ak, then it is this vector that must be derived from the basis. The line corresponding to this vector is called a guide and is denoted “à”.

4. After defining the column and row guides, fill out a new simplex table. In such a table, Ai will appear in place of the guide line. Filling new table starts with a guide line. As a component of the reference plan, the value Ө0 X'l=Ө0=Xk/Xkl is written there, the remaining elements of this line are determined by the formula X'lj X'lj=Xkj/Xkl where Xkl is the element located at the intersection of the row and column guides, specifically on it all former elements of the guide line are divided, and a unit automatically appears in the place of the former Xkl element. General rule to recalculate the guide line, you can write it like this: Ak (new element of the guide line) = (old element of the guide line)/(element standing at the intersection of the guide column and row)

5. All elements of the remaining rows of the table are recalculated, including the additional bottom row. Recalculation is carried out according to the formulas

· for components of the reference plan X’i=Xi-Ө0Xil=Xi-(Xk/Xkl)*Xil

· for components expanded over the basis X’ij=Xij-(Xkj/Xkl)*Xil

· For additional line Z’j-Cj=(Zj-Cj)-(Xkj/Xkl)*(Zl-Cl)

All these formulas are built according to one rule:

(new email)=(old email)-(new row direction email)*(column direction email in the corresponding row)

After filling out the new simplex table, the transition to the second stage of the algorithm occurs.

Methods of natural and artificial basis. Basic concepts, algorithms of methods.

For most linear programming problems, difficulties arise in solving them associated with determining the initial reference plan and the initial simplex table from which all iterations begin. This is due to the fact that in real problems among the vectors Ai there are no vectors containing only one non-zero component, i.e. vectors of the form (0,0,0,…,0,1,0,…,0) or their number is not enough to form a basis. That is, it is not possible to form a natural basis.

The artificial basis method is based on artificial introduction into a mathematical model of the problem of such vectors.

Let a ZLP of canonical form be given

F: C1X1=C2X2+…+CnXnàmin

a11x1+a21x2+…+an1xn=b1

a12x1+a22x2+…+an2xn=b2

…………………………

a1mx1+a2mx2+…+anmxn=bm

Then it is converted to the form

F: C1X1+C2X2+…+CnXn+MXn=1+MXn+2+…+MXn+màmin

a11x1+a21x2+…+an1xn+xn+1=b1

a12x1+a22x2+…+an2xn+xn+2=b2

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

a1mx1+a2mx2+…+anmxn+xn+m=bm

Where M is infinite big numbers. In the resulting problem, the initial basis is immediately visible; the vectors with the artificially introduced variables xn+1, xn+2,…, xn+m should be taken as it. Since these vectors will have the form: (1,0,0,…,0),(0,1,0,…,0),(0,0,…,1). The transformed problem is then solved using the simplex method algorithm. The initial reference plan of the transformed problem has the form (0,0,…,0,xn+1,xn+2,…,xn+m)=(0,0,…,0,b1,b2,…,bm). The original simplex table looks like this:

Basis	coefficient CF	Plan	C1	C2	…	Cn	M	M	…	M
Basis	coefficient CF	Plan	A1	A2	…	An	An+1	An+2	…	An+m
An+1	M	b1	a11	a21	…	an1	1	0	…	0
An+2	M	b2	a12	a22	…	an2	0	1	…	0
…	…	…	…	…	…	…	…	…	…	…
An+m	M	bm	a1m	a2m	…	anm	0	0	…	1
			Z0

We determine the elements of the additional line using the formulas Z0=Mb1+Mb2+…+Mbm=∑mi=1Mbi=M∑ni=1bi

To determine the differences Zj=a11M+Ma12+…+Ma1m=M∑mj=1aij V i=1,n

Zj-Cj=M∑mj=1aij-Cj

After receiving the original simplex table, it is transformed, trying to derive from the basis vectors corresponding to the introduced additional variables.

Since M is very big number, then among the differences Zj-Cj there will be many positive numbers. That is, there will be many candidates for inclusion in the basis among the vectors A1,A2,…,An

If some vector corresponds to the artificially introduced variables xn+1,xn+2,…,xn+m, then the corresponding vector is derived from the basis, and the simplex column of the table with this vector is crossed out and is not returned to it again. At the end of the simplex table transformation, two options are possible:

· all vectors corresponding to artificial variables have been derived from the basis, in this case all columns of the simplex table corresponding to additional variables will disappear, and the original problem will be solved

· the resulting optimal plan will still contain some additional variable, this means that the ODD of the original problem is empty, i.e., its restrictions are contradictory, therefore the original problem has no solutions at all.

Dual linear programming problems. Statement of problems, their properties.

Symmetric dual problems:

First standard form

f(x)=c1x1+c2x2+…+cnxnàmin

a11x1+a21x2+…+an1xn>=b1

a12x1+a22x2+…+an2xn>=b2

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

a1mx1+a2mx2+…+anmxn>=bm

Dual problem

d(y)=b1y1+b2y2+…+bmymàmax

a11y1+a12y2+…+a1mym=0, V j=1,m

Non-septenary pair of dual problems

The original problem in canonical form

f(x)=c1x1+c2x2+…+cnxnàmin

a11x1+a21x2+..+an1xn=b1

a12x1+a22x2+..+an2xn=b2

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

INTRODUCTION

The topic of my work concerns solving problems arising in economics. This raises the question of choosing the best, in a sense, solution option. And to search possible option Often influenced by various factors that narrow the scope of choice. In other words, it is necessary to solve the optimization problem, which consists in the need to choose the best option decisions among a certain, usually limited set of possible options.

The optimization problem can be formulated in mathematical language if the set available options can be described using mathematical relationships (equalities, inequalities, equations), and each solution can be assessed quantitatively using some indicator called the optimality criterion or objective function. Then the best solution will be the one that delivers objective function the largest or smallest value, depending on the meaningful meaning of the problem. For example, when investing a limited amount of funds in several projects, the natural task is to select those projects that can bring the greatest profit in the future. When delivering products from various suppliers to stores, the task of minimizing transportation costs arises.

The process of formalizing a problem is called constructing its mathematical model. It consists of three stages.

1. Selecting the parameters of the problem on which the solution depends. These parameters are called control variables and are denoted by forming a vector from them . Making a decision means setting specific values for variables.

2. Construction of a numerical criterion by which you can compare various options decisions. Such a criterion is usually called the objective function and is denoted by .

3. Description of the entire set X permissible values of variables - restrictions associated with the presence material resources, financial resources, technological capabilities, etc.

The mathematical optimization problem is to find such a feasible solution , which gives the objective function the largest or smallest value among all possible solutions.

1. Geometric method for solving LP problems

This method is often used to solve problems in which there are only two unknown quantities. Let's look at it using the following examples:

Example 1.1. (Problem about the production of paints).

A small factory produces two types of paints: INT- For interior works And EXT- for outdoor work. In the production of paints, two starting products are used A And IN. Due to the small warehouse area, the maximum possible daily stocks of these products are 6 tons and 8 tons, respectively. To produce 1 ton of paint INT 1 ton of product is consumed A and 2 tons of product IN, and for the production of 1 ton of paint EXT there are 2 tons of product A and 1 ton of product IN. The factory sells paint at a price of 3 thousand. dollars per ton of paint INT and 2 thousand dollars per ton of paint EXT. It is convenient to summarize the initial data in a table:

A study of the sales market showed that the daily demand for paint EXT never exceeds the demand for paint INT, more than 1 ton. How much paint of each type should the factory produce per day in order to maximize income from product sales?

Let's build a mathematical model of the problem. To do this, it is necessary to determine the problem variables, the objective function and the constraints that the variables satisfy. Let us denote by x 1- the planned daily production volume of INT paint, and after x 2- daily production volume of EXT paint. Objective function f(x) will express the daily income from the sale of paint equal to 3x 1 + 2x 2(thousand dollars). This income must be maximized

f( x)= 3 x 1 + 2 x 2 ® max.

Let us construct the constraints of the problem associated with limited supplies of products A And IN. For paint production INT in quantity x 1(t) will be used 1x 1(t) of product A, and for paint production EXT in volume x 2(t) will be spent 2x2(t) of product A. Since the daily supply of the product A is 6 tons, then the product consumption A for the production of two types of paints cannot exceed this amount per day: 1x 1 + 2x 2 £6. Similarly, we obtain the constraint associated with the product stock IN : 2x 1 +1x 2 £8. The constraint on the ratio of demand for paints can be described by the inequality: x 2 - x 1 £1. Taking into account the natural conditions for the non-negativity of production volumes, we finally obtain the following linear programming problem

f(x) = 3 x 1 + 2 x 2 ® max (1.1)

1 x 1 + 2 x 2 £ 6 , (1.2)

2 x 1 + 1 x 2 £ 8 , (1.3)

- x 1 + x 2 £1 , (1.4)

x 1 ³ 0, x 2 ³ 0 . (1.5)

Let us construct a set of problem plans described by constraints (1.2)-(1.5). Let's consider the first inequality. It specifies a certain half-plane located on one side of the boundary line

p 1 : 1x 1 +2x 2 =6

Let's construct this straight line on a plane with coordinate axes x 1 And x 2. To draw a line, it is enough to know its two points. The easiest way is to find the intersection points of a straight line with the coordinate axes. Believing x 1 = 0, from the equation of the straight line we get x 2 = 3, and when x 2 = 0 we'll find x 1 = 6. Thus straight p 1 will pass through the points (0,3) And ( 6,0) . To determine on which side of the line the desired half-plane is located, it is enough to substitute the coordinates of any point of the plane into inequality (1.2). If the straight line does not pass through the origin, then it is most convenient to take the point (0, 0) . Obviously, at this point inequality (1.2) is strictly satisfied (1* 0 + 2* 0 < 6) , which means the half-plane defined by this inequality lies below the straight line p1, including the origin. We mark the desired half-plane with shading ( Fig.1.1).

Let us similarly construct the half-plane defined by inequality (1.3) . To do this, draw a boundary line on the coordinate plane

p2 : 2x 1 +x 2 =8 ,

finding its intersection points with the coordinate axes: (0,8) And (4,0) .

Substituting point coordinates (0,0) into inequality (2.3), we see that the origin of coordinates lies in the desired half-plane (2* 0 + 1* 0 < 8) , which means all points satisfying inequality (2.3) are located to the left of the straight line p2. Let's mark this area with shading ( Fig.1.1).

Points defined by the constraint ( 4 ), are below the straight line

p 3 : -x 1 +x 2 =1,

passing through points (0, 1) And (-1, 0) .

Finally, the non-negativity conditions: x 1 ³ 0, x 2³0 set all the points of the first quarter, which we also mark with shading.

Now selecting points of the plane that satisfy all the constraints of problem (1.1)-(1.5), that is, located simultaneously in all shaded half-planes, we obtain a set of plans X. It is a polygon (in this problem, a pentagon). Its sides lie on straight lines, the equations of which are obtained from original system inequalities (1.2)-(1.5) by replacing inequality signs with strict equalities.

For graphical representation of the objective function, we introduce the concept of a level line (function isoline).

Definition. Function level line (isoline) f(x) is called a set of points x = (x 1, x2), in which it takes the same constant value f(x) = h, Where h- a certain number. For linear function two variables f(x) = c 1 x 1 + c 2 x 2 level line corresponding to the number h, will represent a straight line with the equation

c 1 x 1 + c 2 x 2 = h (1.6)

When the number changes h we will obtain a family of level lines (parallel straight lines) with the same direction vector c = =(c 1 , c 2), perpendicular to all lines. It is known that the vector c = (c 1 , c 2) for linear function f(x) = c 1 x 1 +c 2 x 2 indicates the direction of its increase. Geometrically, this means that with parallel movement of straight line (1.6) in the direction of the target vector c the value of the objective function increases.

Let's construct the level lines of the objective function f(x) = 3x 1 + 2 x 2 in our task. Their equations will look like 3x 1 + 2 x 2 = h. They define a family of parallel lines depending on the parameter h. All lines are perpendicular to the target vector c = (3, 2), composed of the coefficients of the objective function, therefore, to construct a family of lines of the level of the objective function, it is enough to construct its target vector and draw several straight lines perpendicular to this vector. We will draw level lines on many plans X, remembering that when moving parallel lines in the direction of the target vector c = (3, 2) function value f(x)= 3x 1 + 2x 2 will increase. Since in the problem the optimal plan must deliver the maximum possible value to the objective function, then to solve the problem graphically it is necessary among all points x = (x 1, x2) many plans X find such a point x* = (x 1 * , x 2 *), through which the last level line will pass in the direction of the target vector c = (3,2). From Figure 1.2 it is clear that the required point will be the point lying at the top of the set X, formed by the intersection of lines p 1 And p2. Solving the system of equations describing these lines we find optimal plan x 1 * = 3 1/3, x 2 * = 1 1/3. In this case, the maximum value of the objective function will be equal to f(x*) = 12 2 / 3 . Thus, every day the factory must produce 3 1 / 3 tons of paint INT And 1 1 / 3 tons of paint EXT while receiving income 12 2 / 3 thousand dollars.

x 1 + 2 x 2 = 6,

2 x 1 + x 2 = 8,

Example 1.2. The medical enterprise purchases two types of multivitamin complexes “Health” and “Longevity” containing three types of vitamins. The number of units of these vitamins in one gram of multicomplexes, their required norm for preventive use and the cost of one gram of the “Health” and “Longevity” complexes are reflected in the table

How many grams of multivitamin complexes of each type are required for one preventive dose so that all vitamins are received at least as required, and at the same time their total cost is minimal.

Let's create a mathematical model of the problem. To do this, we introduce variables: x 1– quantity of the “Health” complex (gr.) , x 2– quantity of the “Longevity” complex (gr.) necessary for prophylactic use. The objective function expresses the total cost of vitamin complexes, which should be as low as possible

f( x)= 5 x 1 + 4 x 2 ® min (1.7)

The restrictions describing the fulfillment of vitamin standards are as follows:

By vitamin V 1 : 3x 1 + x 2 ³ 9 , (1.8)

By vitamin V 2 : x 1 + 2x 2 ³ 8, (1.9)

By vitamin V 3 : x 1 + 6x 2 ³ 12 . (1.10)

In this case, the variables must be non-negative: x j ³ 0, j = 1, 2.

Let's start the solution again by constructing many plans X, for which we draw boundary straight lines, the equations of which are obtained by replacing the inequality signs in the restrictions with equalities

p 1 : 3 x 1 + x 2 = 9,

p2 : x 1 + 2 x 2 = 8,

p 3 : x 1 + 6 x 2 = 12.

Substituting point coordinates (0,0) in inequalities (1.8)-(1.10) we see that the origin of coordinates does not satisfy them and, therefore, is not included in the set of plans X. Therefore, the hatching is directed above and to the right of the boundary lines. By identifying points that satisfy all inequalities and non-negativity conditions, we obtain the set of plans shown in Fig. 1.2. IN in this example it is not limited.

Let us depict the objective function (1.7) using level lines. To do this, it is enough to construct the target vector c = (5, 4) and draw several lines perpendicular to it on the set X. Since the target vector indicates the direction of increase of the target function, and in the diet problem it is required to find its minimum, then to find optimal solution we will move the level line parallel to itself along the set X in the direction opposite to the target vector.

The last point of the set of plans through which the level line still passes will be the point of intersection of the lines p 1 And p2. Solving the system of uranias (Fig. 1.3).

3 x 1 + x 2 = 9

x 1 + 2 x 2 = 8

we get the optimal plan x 1 * = 2, x 2 * = 3. The minimum value of the objective function will be equal to

f(x*) = 5∙2 + 4∙3 = 22.

Therefore, the cheapest prophylactic kit consists of 2 g. complex A and 3 g. complex IN, and its cost is 22 rub.

Now it is easy to formulate a geometric solution standard tasks LP with two variables:

· an admissible polygon is depicted - the intersection of half-planes that are solutions to the corresponding inequalities;

· the target vector is depicted;

· a perpendicular to the target vector is drawn through the admissible set - this is the level line of the target function;

· by moving the level line parallel to itself in the direction of the target vector until it is on one side of the moved straight line, the maximum point (or points) is visually determined;

· the coordinates of the maximum point are calculated (by solving the corresponding system of equations defining straight lines, the intersection point of which is the desired point) and the maximum value of the objective function.

Comment. To determine the minimum point, move the isoline against the direction of the target vector.

In the examples analyzed, the optimal plan was located at the only vertex of the polygon of feasible plans. However, when solving LP problems, other cases may also arise.

An infinite number of optimal plans. On Fig.1.4 the objective function takes the same maximum value at any point on the segment AB connecting two vertices of a set of plans X. This situation occurs if the level lines are parallel to the boundary line.

No limited solution. On Fig.1.5 The case is depicted when the objective function is not bounded from above on the set of plans and a solution to the maximum problem does not exist. In this case, a solution to the minimum problem may exist (as in the problem of vitamins).

Lack of valid plans. On Fig.1.6 The areas allowed under each of the restrictions do not have common points. In this case, they say that the constraints are inconsistent, the set of plans is empty, and the LP problem has no solution.

Rice. 1.4 Fig. 1.5 Fig. 1.6

2. Simplex method

2.1 The idea of the simplex method

Let's consider universal method solving the canonical linear programming problem

, , ,

With n variables and m equality constraints, known as the simplex method.

The set of plans for a canonical problem is a convex polyhedral set with a finite number of corner points. And if this problem has an optimal solution, then it is achieved at least at one corner point.

Any corner point is associated with a basic plan of the problem, in which the variables are equal to zero, and the remaining variables correspond to linearly independent columns of the condition matrix. These linearly independent columns form a non-singular basis matrix.

Iterating over all corner points is computationally expensive and therefore ineffective. In 1947, J. Danzig proposed an orderly procedure for enumerating corner points, in which it is enough to examine only a small part of them to find the optimal solution. This procedure is called simplex method .

J. Dantzig proposed replacing only one vector in the basis matrix when moving from one extreme point to another. This means that during such a transition we must exclude one of the basic variables - make it non-basic ( equal to zero), and in its place introduce a new variable from among the non-basic (zero) ones - make it basic (positive).

It turns out that geometrically such a replacement leads to a transition from one corner point to an adjacent one, connected to the previous point by a common edge.

Of all the neighboring points, the one at which the objective function increases the most is selected. Since the number of corner points is finite, through a finite number of transitions the vertex with highest value objective function, or the unboundedness of the objective function will be established on an unlimited set of plans.

General scheme The simplex method consists of the following basic steps.

· step 0. Determination of the initial basis and the corresponding initial corner point (baseline).

· step 1. Checking the current baseline for optimality . If the optimality criterion is met, the plan is optimal and the solution is complete. Otherwise go to step 2.

· step 2. Finding the variable introduced into the basic ones. (From the condition of increasing the objective function).

· step 3. Finding a variable excluded from the basic variables (From the condition of preserving the constraints of the problem).

· step 4 . Finding the coordinates of the new baseline (adjacent corner point). Go to step 1.

Repeated steps 1–4 form one iteration of the simplex method.

From this diagram it follows that, firstly, to start the simplex method, you need to have some kind of corner point - an initial basic plan, and secondly, you need to be able to examine the current corner point for optimality without calculating all adjacent vertices. These problems are easily solved if the canonical LP problem has a certain special type.

Definition. We will say that the canonical LP problem has a “preferred form” if

1. right-hand sides of the equations , .

2. the condition matrix contains a unit submatrix of size

In other words, in any equation there is a variable with a coefficient equal to one, missing from the other equations. The first condition is not burdensome, since in the case of a negative right-hand side of some equation, it is enough to multiply it by (–1). In a preferential type problem, finding the initial baseline is very simple.

Example 2.1.

Condition Matrix A and the vector of the right-hand sides of the constraints b look like

, ,

and target vector c = (1, -3, 0, 4, 2).

One basis matrix is immediately obvious: with unit vectors of conditions.

Therefore, choosing as basic variables x 1 , x 3 ,x 5 and putting in the system of equations x 2 = x 4 = 0 (non-basic variables) , we find it immediately x 1 = 10,x 3 = 20,x 5 = 8, so the initial baseline x 0= (10, 0, 20, 0, 8). We see that the values of the basic variables are equal to the right-hand sides of the constraints. From this it is clear that the right-hand sides must be positive b i.

In the future, we will combine the basic variables into a vector x B.

Thus, in the canonical problem of the preferred form, the identity submatrix is taken as the initial basis matrix A B = E, and the corresponding basis variables are equal to the right-hand sides of the constraints:

x B = b .

For a basic plan of this type, an optimality criterion can be formulated that is simple enough to test. Let's introduce the quantities

∆ j =< с Б, A j >– c j , j = 1,...,n, (2.1)

Where with B– vector of coefficients of the objective function for basic variables x B , A j – j- column of the condition matrix, c j – j- th coefficient of the objective function. Differences ∆ j are called simplex differences or simplex estimates.

Optimality criterion for the basic plan. If for a basic plan with a unit basis matrix all simplex estimates are non-negative, then this plan is optimal.

Let us apply this criterion to check the optimality of the basic plan x 0= (10, 0, 20, 0, 8) from example 2.1.

Since in this regard the vector of basic variables x B =(x 1 , x 3 ,x 5), That with B = (c 1 , c 3 ,c 5) = (1, 0, 2).

Hence,

∆ 1 = < с Б, A 1 >– from 1 =1∙1 + 0∙0 + 2∙0 – 1= 0,

∆ 2 = < с Б, A 2 >– c 2 =1∙3 + 0∙1 + 2∙2 – (-3) = 10,

∆ 3 = < с Б, A 3 >– c 3 =1∙0 + 0∙1 + 2∙0 – 0= 0,

∆ 4 = < с Б, A 4 >– c 4 =1∙(-1) + 0∙5 + 2∙1 – 4= -3,

∆ 5 = < с Б, A 5 >– from 5 =1∙0 + 0∙0 + 2∙1 – 2= 0.

Since the assessment ∆ 4 < 0, то базисный план x 0 not optimal. Note that the simplex estimates corresponding to the basic variables are always equal to zero, so it is sufficient to check only the non-basic estimates.

2.2 Implementation of the simplex method using an example

Let us demonstrate the use of the simplex method with an example. Let's consider canonical problem LP

f(x) = x 1 + 2x 2 + 0x 3 + 0x 4 →max	(2.2)
–x 1 + 2x 2 +x 3 = 4,	(2.3)
3x 1 + 2x 2 +x 4 = 12,	(2.4)
x j ≥ 0, j = 1,2,3,4.	(2.5)

Condition Matrix A = (A 1 , A 2 , A 3 , A 4), where

Target vector c =(c 1, c2, c 3, c 4) = (1, 2, 0, 0); vector of right parts b =(b 1 , b 2) = (4, 12).

Step 0. Finding the starting corner point (baseline).

The problem has a preferable form, since the right-hand sides of the equations are positive, and the columns of the condition matrix A 3, A 4 form a unit submatrix. This means the initial basis matrix = (A 3 ,A 4); x 3 and x 4 – basic variables x 1 and x 2 - non-basic variables, c B = (c 3, c 4) = = (0, 0).

The initial baseline looks like x 0 = (0, 0, x 3 , x 4) = (0, 0, 4, 12); f( xo)= 0.

Step 1. Checking the basic plan for optimality.

Let's calculate simplex estimates for non-basic variables using formula (5.1)

 1 = < c B, A 1 > – c 1 = 0 ·(–1) + 0 ·3 – 1 = –1 .

 2 = < c B, A 2 > – c 2 = 0 2 + 0 2 – 2 = –2 .

Since the estimates are negative, the plan x – not optimal. We will look for a new baseline (adjacent corner point) with a larger value of the objective function.

Step 2. Finding the variable introduced into the basis.

The objective function can be increased by introducing one of the non-basic variables into the basic variables (making it positive) x 1 or x 2, since both estimates  j < 0. Обычно в состав базисных вводят небазисную переменную с наибольшей по модулю отрицательной оценкой, поэтому будем вводить в базис переменную x 2.

Step 3. Definition of a variable derived from the basis.

After entering the variable into the basis x 2 the new plan will look like

x" = (0, x 2, x 3 , x 4).

This plan is not a basic one, since it contains only one zero coordinate, which means it is necessary to make one of the variables zero (exclude from the basis) x 3 or x 4 . Let's substitute the coordinates of the plan x" = (0, x 2, x 3 ,x 4) in the constraints of the problem. We get

2x 2 + x 3 = 4,

2x 2 + x 4 = 12.

Let us express the basic variables from here x 3 and x 4 via variable x 2 , entered into the basis.

How more value x 2 , the more the objective function increases. Let us find the maximum value of the new basis variable that does not violate the constraints of the problem, that is, satisfying conditions (2.8), (2.9).

Let us rewrite the last inequalities in the form

2x 2 ≤ 4,

2x 2 ≤ 12,

where does the maximum value come from? x 2 = min ( 4/2, 12/2 ) = 2. Substituting this value into expressions (2.6), (2.7) for x 3 and x 4, we get x 3 = 0. Therefore x 3 derived from the basis .

Step 4. Determining the coordinates of the new baseline.

The new baseline (adjacent corner point) is:

x" = (0, x 2, 0, x 4)

The basis of this point consists of columns A 2 and A 4 , so =( A 2, A 4). This basis is not unitary, since the vector A 2 = (2,2), and therefore problem (2.2)–(2.5) does not have a preferred form with respect to the new basis. Let us transform the conditions of problem (2.3), (2.4) so that it takes the preferred form with respect to the new basic variables x 2, x 4, that is, so that the variable x 2 was included in the first equation with a coefficient equal to one, and was not present in the second equation. Let's rewrite the equations of the problem

– x 1 + 2 x 2 + x 3 = 4, (p 1)

3x 1 +2 x 2 + x 4 = 12. (p 2)

Let's divide the first equation by the coefficient at x 2. Let's get a new equation = p 1/2 equivalent to original

– 1/2 x 1 + x 2 + 1/2 x 3 = 2. ( )

We use this equation, which we call resolving, to eliminate the variable x 2 from the second equation. For this we need the equation multiply by 2 and subtract from p 2 . We get = p 2 – 2= p 2 -p 1:

4 x 1 – x 3 + x 4 = 8. ( )

As a result, we obtained a new “preferred” representation of the original problem with respect to new basic variables x 2 , x 4:

f (x) = x 1 + 2 x 2 + 0 x 3 + 0 x 4  max

– 1/2 x 1 + x 2 + 1/2 x 3 = 2 ( )

4 x 1 – x 3 + x 4 = 8 ( )

x j 0, j = 1,2,3,4

Substituting here the representation of the new baseline x 1 = (0, x 2, 0, x 4), we will immediately find its coordinates, since the values of the basic variables are equal to the right sides of the equations

x" = (0, 2, 0, 8); f (x 1)=4.

This completes the first iteration simplex method. Next, the process of solving the problem continues from step 1, which consists of checking the found plan for optimality. The solution ends when all simplex estimates of the current basic plan turn out to be non-negative.

We will not carry out the second iteration according to the scheme of the first, since it is more convenient to carry out all calculations of the simplex method in tabular form.

2.3 Tabular implementation of a simple simplex method

We will demonstrate the tabular implementation using the same example (2.2)–(2.5).

Step 0. The solution begins by constructing an initial simplex table. Filled in first right part tables from the third column. In two top lines names are recorded problem variables (x 1, ...,x 4) and coefficients of the objective function for these variables. Below are the coefficients of the equations - elements of the matrix of conditions A, so under the variable x 1 is located column A 1, under variable x 2 – column A 2, etc. The right-hand sides of the constraints (numbers) are entered in the right column b i > 0).

Then we find the columns of the condition matrix that form the unit basis - in our example this is A 3 and A 4 and the corresponding basic variables x 3, x 4 is written in the second column. Finally, in the first column we write down the coefficients of the objective function for the basic variables.

Table 1 - Initial simplex table

S B	Basic Variables	with 1 =1	with 2 =2	with 3 =0	with 4 =0	Basic variable values ( x B = b)
S B	Basic Variables	*x 1*	*x 2*	*x 3*	*x 4*	Basic variable values ( x B = b)
c 3 =0	*x 3*	a 11 =-1	a 12 =2	a 13 =1	a 14 =0	b 1 =4
c 4 =0	*x 4*	a 21 =3	a 22 =2	a 23 =0	a 24 =1	b 2 =12
Rating line  j		 1 = -1	 2 = -2	 3 = 0	 4 = 0	f(x)= 0

Since the problem has a preferred form, the values of the basic variables are equal to the right-hand sides of the equations located in the last column. Since the non-basis variables are zero, the initial baseline is

x o = (0, 0, x 3 , x 4) = (0, 0, 4, 12).

Step 1. To check the plan x o for optimality we calculate simplex estimates for non-basic variables x 1 and x 2 by formula

 j =< c Б , A j > – c j .

 1 = < c Б , A 1 > – c 1 = 0 ·(–1) + 0 ·3 – 1 = –1 .

With a tabular implementation for calculating the score  1 we need to find the sum of the products of the elements of the first column ( c B) to the corresponding column elements A 1 for non-basic variable x 1 . The score is calculated in the same way  2 , as the scalar product of the first column ( c B) per column at variable x 2 .

 2 = < c B, A 2 > – c 2 = 0 2 + 0 2 – 2 = –2 .

Simplex estimates are written in the last row of the simplex table, which is called the delta row. In this case, not only the cells for non-basic variables are filled, but also the basic cells. It is easy to check that for the basic unit columns of the condition matrix the simplex estimates are equal to zero. In the last cell of the evaluation line we write the value of the objective function at the point xo. Note that since the non-basic coordinates of the basic plan are equal to zero, it is convenient to calculate the objective function using the formula

f (x)= < c B ,x B >,

scalarly multiplying the first and last columns of the table.

Since among the estimates  j there are negative , then the plan x o is not optimal, and it is necessary to find a new basic plan by replacing one of the basic variables with a new one from among the non-basic ones.

Step 2. Since both estimates  1 and  2 < 0,то в базис можно включить любую из переменных x 1, x 2 . Let us introduce into the basis the variable with the largest absolute negative estimate, that is x 2 .

The column of the simplex table in which the variable entered into the basis is located is called the leading column .

In the example, the leading column will be at x 2 .

Step 3. If all elements in the leading column are negative, then there is no solution to the problem and max f (x) . In the example, all elements of the leading column are positive, therefore, we can find the maximum value x 2 , at which one of the old basic variables goes to zero. Recall that the maximum value x 2 = min(4/2, 12/2)=2.

According to the table, this value is calculated as the smallest of the ratios of the components of the baseline (from the last column) to the corresponding positive elements of the leading column.

The smallest ratio is in the row with the basis variable x 3. So the variable x 3 excluded from the basic variables ( x 3 = 0).

The line containing the variable to be excluded from the basis is called the leading line.

In the example, the leading line will be the first line.

The element located at the intersection of the leading row and leading column is called the leading element.

In our case, the leading element a 12 = 2.

Table 2 - Initial simplex table with leading row and column

c B	Basic changes.	with 1 =1	with 2 =2	with 3 =0	C 4 =0	Basic variable values	Equations
c B	Basic changes.	x 1	*x 2*	x 3	x 4	Basic variable values	Equations
*c 3 =0*	x 3	–1	2	1	0	4	p 1
c 4 =0	x 4	3	2	0	1	12	p2
Rating line  j		 1 = –1	 2 = –2	 3 = 0	 4 = 0	f(x)= 0

Step 4. To obtain a new basic plan, we reduce the problem to a new preferred form with respect to the new basic variables.

To do this, let's build a new simplex table, in the second column of which instead of the excluded variable x 3 let's write a new basic variable x 2, and in the first column ( with B) instead of from 3 Let's write down the coefficient of the objective function at x 2 : c 2 =2. In the new simplex table, the column at x 2 must become one (the leading element must be equal to one, and all other elements must become zero). This is achieved by the following table row transformations.

a. We divide all elements of the leading row by the leading element and write them in the same row of the new simplex table.

The resulting string p 1" Let's call it permissive.

b. To the remaining second line we add the resolving line, multiplied by such a number that the element in the leading column becomes zero.

p 2 "= p 2 + (- 2) p 1 "= p 2 - p 1.

c. Let's fill in the last line by calculating the estimates  j " =< c Б ", A j " >- - c j,Where c B ", A j " - the corresponding columns of the new simplex table, and the value of the objective function f(x)=< c Б ", x Б " >.

We obtain a second simplex table with a new basis.

Table 3 - Result of the first iteration

c B "	Basic changes.	with 1 =1	with 2 =2	with 3 =0	with 4 =0	Basic variable values	Equations
c B "	Basic changes.	x 1	x 2	x 3	x 4	Basic variable values	Equations
c 2 =2	x 2	*–1/2*	1	1/2	0	2	p 1 " =p 1 /2
c 4 =0	*x 4*	4	0	-1	1	8	p 2 " =p 2 - p 1
assessments  j "		–2	0	1	0	f(x")=4

New baseline x " = (0, x 2, 0, x 4) = (0, 2, 0, 8 ).

Since the assessment  1 = -2 < 0, then the plan x " not optimal. To move to a new basic plan (of the neighboring corner point), we will carry out another iteration of the simplex method.

Because  1 < 0, then a variable is introduced into the basis x 1 . The first column containing x 1 - leading.

We find the relationships between the components of the basic plan and the corresponding positive elements of the leading column and take the row with the smallest ratio as the leading row. In Table 2, in the leading column only the second element is greater than zero (= 4), hence the second line will be the leading one, and the basis located in it variable x 4 subject to exclusion from basis .

We select the leading column and leading row and at their intersection we find leading element (= 4) .

We build a new (third) simplex table, replacing the basic variable in it x 4 on x 1 , and again transforming the table rows so that the leading element becomes equal to one, and the remaining elements of the leading column become zero. To do this, divide the leading (second) line by 4, and add the resulting second line divided by 2 to the first line. Last line calculate using formulas for simplex estimates  j "" = < c Б "", A j ""> - c j,Where c B "", A j "" - the corresponding columns of the new simplex table. The value of the objective function on the new baseline is found using the formula f(x "")= < c Б "", x B "" >.

Table 4 - Result of the second iteration

c B ""	Basic change	with 1 =1	with 2 =2	with 3 =0	with 4 =0	Basic variable values	equations
c B ""	Basic change	x 1	x 2	x 3	x 4	Basic variable values	equations
c 2 =2	x 2	0	1	3/8	1/8	3	p 1 "" = p 1 "+p 2 ""/2
c 1 =1	x 1	1	0	-1/4	1/4	2	p 2 "" = p 2 "/4
assessments  j ""		0	0	1/2	1/2	f(x "")= 8

New baseline x "" = (x 1 , x 2 , 0, 0) = (2, 3, 0, 0 ). Since all estimates are non-negative, then the plan x ""- optimal plan.

Thus, x* = (2, 3, 0, 0 ), f(x*) = 8.

CONCLUSION

The considered methods for solving linear programming problems are widely used in practice. However, it should be noted that the mathematical model is always poorer than the real one economic system. It describes this system only approximately, highlighting some properties and neglecting others. To compensate for this shortcoming in mathematical economics, several types of models are being developed, each of which is designed to reflect one specific aspect of economic reality so that when solving a specific economic problem it was possible to choose a model that best suits it.

LIST OF REFERENCES USED

1. Ashmanov S.A. Linear programming. – M.: Nauka, 1981.

2. Kuznetsov Yu.N., Kuzubov V.I., Voloshchenko A.B. Mathematical programming. – M.: graduate School, 1980.

3. Kalikhman I.L. Linear algebra and programming. – M.: Higher School, 1967.

4. Nit I.V. Linear programming. – M.: Moscow State University Publishing House, 1978.

5. Yudin D.B., Golshtein E.G. Linear programming. Theory and final methods. – M.: Fizmatiz, 1963.

6. Tarasenko N.V. Mathematics-2. Linear programming: a course of lectures. – Irkutsk: publishing house BGUEP, 2003.

7. Mathematical programming in examples and problems: Proc. allowance. – 2nd ed., rev. and additional – M.: Higher. school, 1993. – 336 p.

8. www.yandex.ru

9. www.mathematica.ru

The idea of the simplex method

Simplex method

In the previous section it was shown that if a linear programming problem has an optimal solution, then one of the optimal solutions is the admissible basic solution its system of restrictions, which corresponds to a certain corner point of the polyhedron of admissible solutions of the system. It was shown how to find this optimal solution using a finite search of basic solutions to the system of constraints of the problem. However, as the dimension n of the problem constraint system increases, the volume of calculations for solving the problem by the method of exhaustive enumeration of basic solutions grows exponentially and becomes unsuitable in practice. It is possible to organize an enumeration of only feasible basic solutions and sharply reduce the number of enumerated solutions if each subsequent admissible basic solution is chosen so that the corresponding value of the objective function improves or at least does not deteriorate. This approach allows you to reduce the number of steps when finding the optimal basic solution. Let us explain this idea graphically.

Let the polygon ABCDEFGH represent the set of admissible solutions of the PLP with two variables, and the vector – gradient of the objective function.

We need to find the point of this polygon at which the objective function takes on the smallest value. Let the initial admissible basic solution of the problem corresponding to the corner point B be determined. After a complete search of all admissible basic solutions, it will be necessary to examine eight such solutions corresponding to the eight corner points of the polygon. However, it is clear from the figure that, taking into account the direction of the gradient, it is more profitable to go to the neighboring vertex C, then to the neighboring vertex D, which corresponds to the optimal basic solution of the problem. Thus, instead of eight solutions, only three feasible basic solutions will have to be considered.

The idea of sequential improvement of the solution forms the basis of the universal method for solving linear programming problems – simplex method.

The geometric meaning of the simplex method is that a sequential transition is performed from one vertex of the polyhedron of feasible solutions to the problem to the neighboring one, in which the objective function takes a value no worse than at the previous vertex. This transition continues until an optimal solution is found or it is discovered that the problem does not have one.

The simplex method and its name were first proposed by the American mathematician John Danzig in 1947, although the ideas of the method were published by the Russian mathematician L.V. Kantorovich back in 1939 in the article “ Mathematical methods organization and production planning."

The simplex method consists of three main elements.

Let's consider a universal method for solving the canonical linear programming problem

With n variables and m equality constraints, known as the simplex method.

J. Dantzig proposed replacing only one vector in the basis matrix when moving from one extreme point to another. This means that during such a transition we must exclude one of the basic variables - make it non-basic (equal to zero), and in its place introduce a new variable from among the non-basic (zero) - make it basic (positive).

It turns out that geometrically such a replacement leads to a transition from one corner point to an adjacent one, connected to the previous point by a common edge.

Of all the neighboring points, the one at which the objective function increases the most is selected. Since the number of corner points is finite, through a finite number of transitions the vertex with the largest value of the objective function will be found, or the unboundedness of the objective function will be established on an unlimited set of plans.

The general scheme of the simplex method consists of the following main steps.

· step 0. Determination of the initial basis and the corresponding initial corner point (baseline).

· step 1. Checking the current baseline for optimality . If the optimality criterion is satisfied, That the plan is optimal and the solution is complete. Otherwise go to step 2.

· step 2. Finding the variable introduced into the basic ones. (From the condition of increasing the objective function).

· step 3. Finding a variable excluded from the basic variables (From the condition of preserving the constraints of the problem).

· step 4 . Finding the coordinates of the new baseline (adjacent corner point). Go to step 1.

Repeated steps 1-4 form one iteration of the simplex method.

Definition. We will say that the canonical LP problem has a “preferred form” if

1. right sides of the equations, .

2. the condition matrix contains a unit submatrix of size

In other words, in any equation there is a variable with a coefficient equal to one, which is absent in the other equations. The first condition is not burdensome, since in the case of a negative right-hand side of some equation, it is enough to multiply it by (-1). In a preferential type problem, finding the initial baseline is very simple.

Example 2.1.

Condition Matrix A and the vector of the right-hand sides of the constraints b look like

and target vector c = (1, -3, 0, 4, 2).

One basis matrix is immediately obvious: with unit vectors of conditions.

Therefore, choosing as basic variables x 1 , x 3 ,x 5 , and putting in the system of equations x 2 = x 4 = 0 (non-basic variables) , we find it immediately x 1 = 10,x 3 = 20,x 5 = 8, so the initial baseline x 0 = (10, 0, 20, 0, 8). We see that the values of the basic variables are equal to the right-hand sides of the constraints. From this it is clear that the right-hand sides must be positive b i .

In the future, we will combine the basic variables into a vector x B.

Thus, in the canonical problem of the preferred form, the identity submatrix is taken as the initial basis matrix A B = E, and the corresponding basis variables are equal to the right-hand sides of the constraints:

x B = b.

For a basic plan of this type, an optimality criterion can be formulated that is simple enough to test. Let's introduce the quantities

? j = < с B , A j > - c j , j = 1,...,n,(2.1)

Where With B- vector of coefficients of the objective function for basic variables x B , A j -j- th condition matrix column, c j -j- th coefficient of the objective function. Differences ? j are called simplex differences or simplex estimates.

Optimality criterion for the basic plan. If for a basic plan with a unit basis matrix all simplex estimates are non-negative, then this plan is optimal.

Let us apply this criterion to check the optimality of the basic plan x 0 = (10, 0, 20, 0, 8) from example 2.1.

Since in this regard the vector of basic variables x B =(x 1 , x 3 ,x 5 ), That With B = (c 1 , c 3 ,c 5 ) = (1, 0, 2).

Hence,

? 1 = < с B , A 1 > - c 1 = 1 1 + 0 0 + 2 0 - 1= 0,

2 = < сБ, A2 >- c2 = 1 3 + 0 1 + 2 2 - (-3) = 10,

? 3 = < с B , A 3 > - c 3 = 1 0 + 0 1 + 2 0 - 0= 0,

? 4 = < с B , A 4 > - c 4 = 1 (-1) + 0 5 + 2 1 - 4= -3,

? 5 = < с B , A 5 > - c 5 = 1 0 + 0 0 + 2 1 - 2= 0.

Since the assessment ? 4 < 0, то базисный план x 0 not optimal. Note that the simplex estimates corresponding to the basic variables are always equal to zero, so it is sufficient to check only the non-basic estimates.

Kursk Academy of State and Municipal Service

Department of Information and Technosphere Security

Essay

by discipline "Methods of optimal solutions"

on the topic "The idea of the simplex method"

Completed by: 2nd year student

Specialties "Economics"

Moskaleva O. S.

Checked by: Ph.D., Associate Professor Pogosyan S. L.

Kursk – 2012

Introduction………………………………………………………………………………..3

1. The idea of the simplex method…………………………………………….…4

2. Implementation of the simplex method using the example……………………..……6

3. Tabular implementation of a simple simplex method……………….10

Conclusion………………………………………………………………………………….15

List of used literature……………………………..…….16

Introduction.

The Simplex method is a typical example of iterative calculations used in solving most optimization problems.

In the computational scheme of the simplex method, an ordered process is implemented in which, starting from some initial admissible corner point (usually the origin), successive transitions are made from one admissible extreme point to another until a point corresponding to the optimal solution is found.

The idea of the simplex method

Let's consider a universal method for solving the canonical linear programming problem, with n variables and m equality constraints, known as the simplex method.

J. Dantzig proposed replacing only one vector in the basis matrix when moving from one extreme point to another. This means that during such a transition we must exclude one of the basic variables - make it non-basic (equal to zero), and in its place introduce a new variable from among the non-basic (zero) - make it basic (positive).

It turns out that geometrically such a replacement leads to a transition from one corner point to an adjacent one, connected to the previous point by a common edge.

Of all the neighboring points, the one at which the objective function increases the most is selected. Since the number of corner points is finite, through a finite number of transitions the vertex with the largest value of the objective function will be found, or the unboundedness of the objective function will be established on an unlimited set of plans.

The general scheme of the simplex method consists of the following main steps: step 0. Determination of the initial basis and the corresponding initial corner point (baseline).

step 1. Checking the current baseline for optimality . If the optimality criterion is satisfied, That the plan is optimal and the solution is complete. Otherwise go to step 2.

step 2. Finding the variable introduced into the basic ones. (From the condition of increasing the objective function).

step 3. Finding a variable excluded from the basic variables (From the condition of preserving the constraints of the problem).

step 4 . Finding the coordinates of the new baseline (adjacent corner point). Go to step 1.

Repeated steps 1-4 form one iteration of the simplex method.

Definition. We will say that the canonical LP problem has a “preferred form” if: the right-hand sides of the equations; the condition matrix contains a unit size submatrix.

Implementation of the simplex method using an example

Let us demonstrate the use of the simplex method with an example. Consider the canonical LP problem


f(x) = x 1 + 2x 2 + 0x 3 + 0x 4 > max
-x 1 + 2x 2 +x 3 = 4,
3x 1 + 2x 2 +x 4 = 12,
x j? 0, j = 1,2,3,4.

Condition Matrix A = (A 1 , A 2 , A 3 , A 4), where

Target vector c =(c 1, c 2, c 3, c 4) = (1, 2, 0, 0); vector of right parts b=(b 1 ,b 2) = (4, 12).

Step 0. Finding the starting corner point (baseline).

The problem has a preferable form, since the right-hand sides of the equations are positive, and the columns of the condition matrix A 3, A 4 form a unit submatrix. This means the initial basis matrix = (A 3 ,A 4); x 3 And x 4 - basic variables x 1 And x 2 - non-basic variables, c B = (c 3, c 4) = = (0, 0).

The initial baseline looks like x 0 =(0, 0, x 3 , x 4) = (0, 0, 4, 12); f(x o) = 0.

Step 1. Checking the basic plan for optimality.

Let's calculate simplex estimates for non-basic variables using formula (5.1)

? 1 = 1 > - c 1 = 0·(-1) + 0 ·3 - 1 = -1 .

? 2 = 2 > - c 2 = 0 2 + 0 2 - 2 = -2 .

Since the estimates are negative, the plan x- not optimal. We will look for a new baseline (adjacent corner point) with a larger value of the objective function.

Step 2. Finding the variable introduced into the basis.

The objective function can be increased by introducing one of the non-basic variables into the basic variables (making it positive) x 1 or x 2, since both estimates ? j x 2.

Step 3. Definition of a variable derived from the basis.

After entering the variable into the basis x 2 the new plan will look like

x" =(0, x 2, x 3 , x 4).

This plan is not a basic one, since it contains only one zero coordinate, which means it is necessary to make one of the variables zero (exclude from the basis) x 3 or x 4 . Let's substitute the coordinates of the plan x" =(0, x 2, x 3 ,x 4) in the constraints of the problem. We get

2x 2 +x 3 = 4,

2x 2 + x 4 = 12.

Let us express the basic variables from here x 3 And x 4 via variable x 2 , entered into the basis.


x 3 = 4 - 2x 2,
x 4 = 12 - 2x 2 .

So variables x 3 And x 4 must be non-negative, we obtain a system of inequalities


4 - 2x 2 ? 0,
12 - 2x 2 ? 0.

The higher the value x 2 , the more the objective function increases. Let us find the maximum value of the new basis variable that does not violate the constraints of the problem, that is, satisfying conditions (2.8), (2.9).

Let us rewrite the last inequalities in the form

2x 2 ? 4,

2x 2 ? 12,

where does the maximum value come from? x 2 = min ( 4/2, 12/2 ) = 2. Substituting this value into expressions (2.6), (2.7) for x 3 And x 4 , we get x 3 = 0. Therefore x 3 derived from the basis .

Step 4. Determining the coordinates of the new baseline.

The new baseline (adjacent corner point) is:

x" = (0, x 2, 0, x 4)

The basis of this point consists of columns A 2 and A 4 , so =( A 2, A 4). This basis is not unitary, since the vector A 2 = (2,2), and therefore problem (2.2)-(2.5) does not have a preferred form with respect to the new basis. Let us transform the conditions of problem (2.3), (2.4) so that it takes the preferred form with respect to the new basic variables x 2, x 4, that is, so that the variable x 2 was included in the first equation with a coefficient equal to one, and was not present in the second equation. Let's rewrite the equations of the problem

- x 1 + 2 x 2 + x 3 = 4, (p 1)

3x 1 +2 x 2 + x 4 = 12. (p 2)

Let's divide the first equation by the coefficient at x 2 . We get a new equation = p 1/2 equivalent to original

1/2 x 1 + x 2 + 1/2 x 3 = 2. ()

We use this equation, which we call resolving, to eliminate the variable x 2 from the second equation. To do this, you need to multiply the equation by 2 and subtract from p 2 . We get = p 2 - 2= p 2 -p 1:

4 x 1 - x 3 + x 4 = 8. ()

As a result, we obtained a new “preferred” representation of the original problem with respect to new basic variables x 2 , x 4:

f(x) = x 1 + 2 x 2 + 0 x 3 + 0 x 4 ? max

1/2 x 1 + x 2 + 1/2 x 3 = 2 ()

4 x 1 - x 3 + x 4 = 8 ()

x j? 0, j = 1,2,3,4

x" = (0, 2, 0, 8); f(x 1)=4.

This completes the first iteration of the simplex method. Next, the process of solving the problem continues from step 1, which consists of checking the found plan for optimality. The solution ends when all simplex estimates of the current basic plan turn out to be non-negative.

We will not carry out the second iteration according to the scheme of the first, since it is more convenient to carry out all calculations of the simplex method in tabular form.

Tabular implementation of a simple simplex method

We will demonstrate the tabular implementation using the same example (2.2)-(2.5).

Step 0. The solution begins by constructing an initial simplex table. First, the right side of the table is filled in from the third column. The top two lines contain the names of the task variables ( x 1, ...,x 4) and coefficients of the objective function for these variables. Below are the coefficients of the equations - elements of the condition matrix A, so under the variable x 1 located column A 1, under variable x 2 - column A 2 etc. The right-hand sides of the constraints (numbers) are entered in the right column b i > 0).

Then we find the columns of the condition matrix that form the unit basis - in our example this is A 3 and A 4 - and their corresponding basic variables x 3, x 4 write in the second column. Finally, in the first column we write down the coefficients of the objective function for the basic variables.

Table 1- Initial simplex table

	Basic Variables					Basic variable values ( x B =b)
		*x 1*	*x 2*	*x 3*	*x 4*
	*x 3*	a 11 =-1
	*x 4*
Rating line ? j	? 1 = -1	? 2 = -2

x o = (0, 0, x 3 , x 4) = (0, 0, 4, 12).

Step 1. To check the plan x o for optimality we calculate simplex estimates for non-basic variables x 1 And x 2 according to the formula

? j = B, A j > - c j .

? 1 = B, A 1 > - c 1 = 0·(-1) + 0 ·3 - 1 = -1 .

With a tabular implementation for calculating the score ? 1 we need to find the sum of the products of the elements of the first column ( c B) to the corresponding column elements A 1 for a non-basic variable x 1 . The score is calculated in the same way ? 2 , as the scalar product of the first column ( c B) per column at variable x 2.

? 2 = 2 > - c 2 = 0 2 + 0 2 - 2 = -2 .

f(x)= c B, x B >,

scalarly multiplying the first and last columns of the table.

Since among the estimates ? j There is negative , then the plan x o is not optimal, and it is necessary to find a new basic plan by replacing one of the basic variables with a new one from among the non-basic ones.

Step 2. Since both estimates ? 1 And ? 2 then any of the variables can be included in the basis x 1, x 2 . Let us introduce into the basis the variable with the largest absolute negative estimate, that is x 2 .

The column of the simplex table in which the variable entered into the basis is located is called the leading column.

In the example, the leading column will be at x 2 .

Step 3. If all elements in the leading column are negative, then there is no solution to the problem and max f(x) ???. In the example, all elements of the leading column are positive, therefore, we can find the maximum value x 2 , at which one of the old basic variables goes to zero. Recall that the maximum value x 2 = min(4/2, 12/2)=2.

According to the table, this value is calculated as the smallest of the ratios of the components of the baseline (from the last column) to the corresponding positive elements of the leading column.

The smallest ratio is in the row with the basis variable x 3. So the variable x 3 excluded from the basic variables ( x 3 = 0).

The line containing the variable to be excluded from the basis is called the leading line.

In the example, the leading line will be the first line.

The element located at the intersection of the leading row and leading column is called the leading element.

In our case, the leading element a 12 = 2.

Table 2- Initial simplex table with leading row and column


	Basic changes.					Basic variable values	Equations
			*x 2*
*c 3 =0*	*x 3*	-1	2	1	0	4
			2
Rating line ? j	? 1 = -1	? 2 = -2

Step 4. To obtain a new basic plan, we reduce the problem to a new preferred form with respect to the new basic variables.

To do this, let's build a new simplex table, in the second column of which instead of the excluded variable x 3 let's write a new basic variable x 2, and in the first column ( with B) instead of from 3 Let's write down the coefficient of the objective function at x 2: c 2 =2. In the new simplex table, the column at x 2 must become one (the leading element must be equal to one, and all other elements must become zero). This is achieved by the following table row transformations.

a. We divide all elements of the leading row by the leading element and write them in the same row of the new simplex table.

The resulting string p 1" Let's call it permissive.

b. To the remaining second line we add the resolving line, multiplied by such a number that the element in the leading column becomes zero.

p 2 " = p 2 + (- 2) p 1 " = p 2 - p 1.

c. Let's fill in the last line by calculating the estimates ? j " = - - c j, Where c B ", A j " - the corresponding columns of the new simplex table, and the value of the objective function f(x)= .

We obtain a second simplex table with a new basis.

Table 3- Result of the first iteration


	Basic changes.					Basic variable values	Equations

		-*1/2*
	*x 4*	4	0	-1	1	8	p 2 " =p 2 - p 1
assessments ? j"	-2

New baseline x " = (0, x 2, 0, x 4) = (0, 2, 0, 8 ). Since the assessment ? 1 = -2 then plan x " not optimal. To move to a new basic plan (of the neighboring corner point), we will carry out another iteration of the simplex method.

Because? 1 then a variable is introduced into the basis x 1. The first column containing x 1 - leading.

We select the leading column and leading row and at their intersection we find leading element (= 4).

We build a new (third) simplex table, replacing the basic variable in it x 4 on x 1 , and again transforming the table rows so that the leading element becomes equal to one, and the remaining elements of the leading column become zero. To do this, divide the leading (second) line by 4, and to the first line add the resulting second line, divided by 2. We calculate the last line using the formulas for simplex estimates ? j"" = "", A j""> - c j, Where c B"", A j"" - the corresponding columns of the new simplex table. The value of the objective function on the new baseline is found using the formula f(x"")= "", x B"" >.

Table 4- Result of the second iteration


	Basic change		Basic variable values	equations

				p 1 "" = p 1 "+p 2 ""/2
				p 2 "" = p 2 "/4
assessments ? j ""		f(x"")= 8

New baseline x "" = (x 1 , x 2 , 0, 0) = (2, 3, 0, 0 ). Since all estimates are non-negative, then the plan x ""- optimal plan.

Thus, x* = (2, 3, 0, 0 ), f(x*) = 8.

CONCLUSION

The considered methods for solving linear programming problems are widely used in practice. However, it should be noted that

a mathematical model is always poorer than a real economic system. It describes this system only approximately, highlighting some properties and neglecting others. To compensate for this shortcoming in mathematical economics, several types of models are being developed, each of which is designed to reflect one specific aspect of economic reality so that when solving a specific economic problem, it is possible to select a model that best suits it.