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 the 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 it be known reference plan X =(x1,x2,…,xm,0,0,…,0) and the associated system of linearly independent vectors: A1,A2,…,Am, then for this reference plan you can calculate the value of the CF Z=(c1x1+ c2x2+…+cmxm) and write 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 in place former element Xkl automatically appears unit. 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 the artificial introduction of such vectors into the mathematical model of the problem.

Let it be given ZLP canonical forms

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
			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

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

• Previously, it was shown that if a linear programming problem has an optimal solution, then one of the optimal solutions is an admissible basic solution to its system of constraints, 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 admissible basic solutions and sharply reduce the number of enumerated solutions if each subsequent admissible basic solution is chosen so that the corresponding value objective function improved or at least did not worsen. 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 feasible solutions of the PLP with two variables, and let the vector N be 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 feasible basic solution of the problem corresponding to the corner point B be determined.

• With a complete search of all feasible 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 N, 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 – the simplex method.

Geometric meaning The simplex method consists in performing a sequential transition from one vertex of the polyhedron admissible solutions task to a neighboring one, in which the objective function takes a value no worse than in 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 of organizing and planning production.”

The simplex method consists of three main elements:

• determining some initial feasible basic solution to the problem;

• rules for transition to the next non-worst admissible basic solution;

• checking the optimality of the solution found.

• The simplex method is applied to a linear programming problem written in canonical form.

Simplex transformations of a system of linear equations

• Let us consider the ZLP in canonical form. Let a system of linear equations be given:

• We need to find a non-negative solution to this system that minimizes the linear function

• Let us denote – the matrix of the system of equations (1),

• – extended matrix of this system.

We will consider the case when the ranks of matrices A and B are equal: , i.e. when system (1) has an infinite number of solutions. Our task is to find out whether there are optimal solutions to the problem in this case and how to find them.

• For definiteness, we assume that the first r columns of matrix A are linearly independent, then system (1) can be transformed, using the Gaussian elimination method, to the form:

• This system is equivalent to system of equations (1). Odds Columns

• form the basis of the system of columns of the matrix of system (2) and therefore the variables are basic, and the set is a basic set.

• For brevity, we will also call the basis set of variables a basis, meaning the corresponding basis of the coefficient columns. The remaining variables are free.

Let us express the basic variables in system (3) in terms of free ones, and obtain system (4):

• (4)

• It is customary to say that (4) is a general solution to the system of equations (1). By assigning zero values ​​to the free variables, we determine the values ​​of the basic variables and construct a basic solution corresponding to the constructed basic set of variables.

• So, the basic solution of system (1).

• In what follows it will be shown that if system (1) has admissible solutions, then it can be transformed to form (3) such that condition (5) is satisfied

• Therefore, we will assume that condition (5) is satisfied. Then the basic solution is a feasible basic solution.

Using equalities (4), we can express the function f in terms of free variables: (6) Now we can calculate the value of the function f corresponding to the basic solution

• Implementing the idea of ​​the simplex method, we will learn to move from one feasible basic solution to another. To do this, one of the basic variables xi is removed from the basis and replaced by some free variable xj.

• With this change in the basis, the system of equations (4) and the linear function (6) are transformed. To do this, the i-th equation of system (3) must be resolved with respect to xj.

• The resulting equation is:

• Substituting instead of xj its expression from (7) into the remaining equations of system (4) and into function (6), we obtain a new system equivalent to system (1), which will be resolved with respect to the new basis

The coefficient aij, indicating that in the basis xi is replaced by a free variable xj, is called the resolving element of the simplex table. From equality (7) it follows that

• Since the new basis solution must be admissible (non-negative),

• then the condition must be satisfied, which means . In other words, the resolving element aij (xi is a free variable) in the jth column must be chosen positive. We will call the described transformation simplex if the resolving element aij is chosen according to the following rule:

• 1. Element aij choose from the jth column that contains positive elements.

• 2. If there are several positive elements in this column, then we will compose the ratios of the free terms bk to the coefficients akj>0.

• Of all the ratios, we choose the smallest one. Let it be :

• (8)

• We choose the denominator of this fraction as the resolving element. If several of these ratios are minimal (equal), then we will choose any of these denominators.

Theorem. If in the system of linear equations (4) all free terms are non-negative, then after applying the simplex transformation they will remain non-negative.

• Proof. Let us denote the new free terms after the simplex transformation in (4) by

• Then at

• If akj>0, then from (8) it follows that

• If akj

• If akj =0, then

• Consequence. Using a simplex transformation, you can go from one admissible basic solution of the ZLP to another admissible basic solution of this problem.

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 to solve 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.

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 linearly independent columns condition matrices. These linearly independent columns form a non-singular basis matrix.

Iterating over all corner points is computationally expensive and therefore ineffective. In 1947, J. Dantzig proposed an orderly procedure for enumerating corner points, in which to find optimal solution it is enough to examine only a small part of them. 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 (neighboring) one associated with previous point 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 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.

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: the right-hand sides of the equations; the condition matrix contains a unit size submatrix.

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.

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. We'll find maximum value a new basic variable that does not violate the constraints of the problem, that is, satisfies 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

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 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. 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 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 basis variables x 3, x 4 write in the second column. Finally, in the first column we write 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

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 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 .

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 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, we will 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 line by the leading element and write them in the same line as a new one simplex tables.

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
estimates ? 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 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"" = "", 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
estimates ? 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

mathematical model always poorer than 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 was possible to choose a model that best suits it.

LIST OF REFERENCES USED

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

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) - 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.

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 some special form.

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, 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 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.