What do additional bases mean in the simplex method? Solve a linear programming problem using the simplex method

Linear programming is a mathematical modeling technique designed to optimize the use of limited resources. LP is successfully used in the military field, industry, agriculture, the transport industry, economics, the healthcare system and even in the social sciences. The widespread use of this method is also supported by highly efficient computer algorithms that implement this method. Optimization algorithms for other, more complex types of models and operations research (OR) problems, including integer, nonlinear and stochastic programming, are based on linear programming algorithms.

Optimization problem is an economic and mathematical problem that consists of finding the optimal (maximum or minimum) value objective function, and the values ​​of the variables must belong to a certain range of acceptable values.

In its most general form, the task linear programming mathematically written as follows:

Where X = (x 1 , x 2 , ... , x n ) ; W– range of permissible values ​​of variables x 1 , x 2 , ... , x n ;f(X)– objective function.

In order to solve an optimization problem, it is enough to find its optimal solution, i.e. indicate that in any case.

An optimization problem is unsolvable if it does not have an optimal solution. In particular, the maximization problem will be unsolvable if the objective function f(X) is not bounded from above on the admissible set W.

Methods for solving optimization problems depend both on the type of objective function f(X), and from the structure of the admissible set W. If the target function in the problem is a function n variables, then the solution methods are called mathematical programming methods.

The characteristic features of linear programming problems are as follows:

optimality index f(X) is a linear function of the solution elements X = (x 1 , x 2 , ... , x n ) ;

restrictive conditions imposed on possible solutions take the form of linear equalities or inequalities.

Linear programming problem called an operations research problem, mathematical model which has the form:

(2) (3)(4)(5)

At the same time, the system linear equations(3) and inequalities (4), (5), which determines the admissible set of solutions to the problem W, called system of restrictions linear programming problems, and a linear function f(X) called target function or optimality criterion .

Valid solution is a collection of numbers ( plan ) X = (x 1 , x 2 , ... , x n ) , satisfying the constraints of the problem. Optimal solution – this is a plan in which the objective function takes its maximum (minimum) value.

If the mathematical model of a linear programming problem has the form:

then they say that the problem is presented in canonical form .

Any linear programming problem can be reduced to a linear programming problem in canonical form. To do this, in the general case, you need to be able to reduce the maximization problem to the minimization problem; move from inequality constraints to equality constraints and replace variables that do not obey the non-negativity condition. Maximizing a certain function is equivalent to minimizing the same function taken with the opposite sign, and vice versa.

The rule for bringing a linear programming problem to canonical form is as follows:

if the original problem requires determining the maximum linear function, then you should change the sign and look for the minimum of this function;

if there are restrictions right side is negative, then this limit should be multiplied by -1;

if there are inequalities among the restrictions, then by introducing additional non-negative variables they are transformed into equalities;

if some variable x j has no sign restrictions, then it is replaced (in the objective function and in all restrictions) by the difference between two new non-negative variables: x 3 = x 3 + -x 3 - , Where x 3 + , x 3 - ≥ 0 .

Example 1. Reducing the linear programming problem to canonical form:

min L = 2x 1 +x 2 -x 3 ; 2x 2 -x 3 ≤ 5; x 1 +x 2 -x 3 ≥ -1; 2x 1 -x 2 ≤ -3; x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.

Let us introduce leveling variables into each equation of the system of constraints x 4 , x 5 , x 6 . The system will be written in the form of equalities, and in the first and third equations of the system of constraints the variables x 4 , x 6 are entered into left side with a "+" sign, and in the second equation the variable x 5 is entered with a "-" sign.

2x 2 -x 3 +x 4 = 5; x 1 +x 2 -x 3 -x 5 = -1; 2x 1 -x 2 +x 6 = -3; x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.

The free terms in the canonical form must be positive; to do this, multiply the last two equations by -1:

2x 2 -x 3 +x 4 = 5; -x 1 -x 2 +x 3 +x 5 = 1; -2x 1 +x 2 -x 6 = 3.

Simplex method for solving linear programming problems.

The simplex method algorithm finds the optimal solution by considering a limited number of feasible basic solutions. The simplex method algorithm always starts with some feasible basis solution and then tries to find another feasible basis solution that “improves” the value of the objective function. This is only possible if an increase in any zero (non-basic) variable leads to an improvement in the value of the objective function. But in order for a non-basic variable to become positive, one of the current basic variables must be made zero, i.e. convert to non-basic. This is necessary so that the new solution contains exactly m basic variables. In accordance with the terminology of the simplex method, the selected zero variable is called input (to the basis), and the basis variable to be deleted is excluded (from the basis).

Let us call two rules for selecting input and exclusion variables in the simplex method optimality condition And admissibility condition . Let us formulate these rules and also consider the sequence of actions performed when implementing the simplex method.

Optimality condition. The input variable in the maximization (minimization) problem is a non-basic variable that has the largest negative (positive) coefficient in target-line. If in target-line contains several such coefficients, then the choice of the entered variable is made arbitrarily. The optimal solution is achieved when target-line, all coefficients for non-basic variables will be non-negative (non-positive).

Admissibility condition. In both the maximization and minimization problems, the basis variable for which the ratio of the value of the right side of the constraint to the positive coefficient of the leading column is minimal is selected as the excluded one. If there are several basic variables with this property, then the choice of the excluded variable is arbitrary.

Let us present an algorithm for solving a linear programming problem of finding a maximum using simplex tables.

F = с 1 x 1 +с 2 x 2 +…+с n x n max

x 1 0, x 2 0,…, x n 0.

1st step. We introduce additional variables and write the resulting system of equations and linear function in the form of an extended system.

F–c 1 x 1 –c 2 x 2 –…–c n x n =0=c p.

2nd step. We compose the initial simplex table.

3rd step. We check the fulfillment of the optimality criterion - the presence in last line negative coefficients. If there are none, then the solution is optimal and F * =c o, the basic variables are equal to the corresponding coefficients b j, the non-basic variables are equal to zero, i.e. X * =(b 1,b 2,…, b m, 0,…, 0).

4th step. If the optimality criterion is not met, then the largest absolute negative coefficient in the last (estimated) row determines the resolving column s.

To determine the resolution line, we calculate the evaluation ratios and fill in the last column of the table.

The estimated ratio of the i-th row is

 if b i and a is have different signs;

 if b i =0 and a is<0;

 if a is =0;

0 if b i =0 and a is >0;

In the column of evaluative relations we find the minimum element min which defines the enabling stringg.

If there is no minimum, then the problem does not have a final optimum I and is unsolvable.

At the intersection of the resolving row and column there is a resolving element a gs.

5th step. Let's build the following table. For this

Let's move on to the third step.

M-method Sometimes with decision of the PPP in the matrix of coefficients for the unknowns of the constraint system there are no unit columns from which one can compose a unit matrix, i.e. a problem arises in choosing the basis variables, or the initial solution is unacceptable. In such cases use artificial basis method (M - method). In all restrictions where there are no basic variables, artificial variables. Artificial variables are introduced into the objective function with a coefficient (- M) for problems with max and with a coefficient (+ M) for problems with min, where M is a sufficiently large positive number. Then the extended problem is solved using the rules of the simplex method. If all artificial variables are equal to zero, i.e. are excluded from the basis, then either an optimal solution to the original problem will be obtained, or the original problem is solved further and its optimal solution is found or its unsolvability is established. If at least one of the artificial variables turns out to be different from zero, then the original problem has no solution

Let's consider simplex method for solving linear programming (LP) problems. It is based on the transition from one reference plan to another, during which the value of the objective function increases.

The simplex method algorithm is as follows:

1. We transform the original problem into canonical form by introducing additional variables. For inequalities of the form ≤, additional variables are introduced with a sign (+), but if of the form ≥, then with a sign (-). Additional variables are introduced into the objective function with corresponding signs with a coefficient equal to 0 , because the target function should not change its economic meaning.
2. Vectors are written out P i from the coefficients of the variables and the column of free terms. This action determines the number of unit vectors. The rule is that there should be as many unit vectors as there are inequalities in the system of constraints.
3. After this, the source data is entered into a simplex table. Unit vectors are introduced into the basis, and by excluding them from the basis, the optimal solution is found. The coefficients of the objective function are written with the opposite sign.
4. An optimality sign for an LP problem is that the solution is optimal if in f– in the row all coefficients are positive. Rule for finding the enabling column - viewed f– a string and among its negative elements the smallest one is selected. Vector P i its containing becomes permissive. The rule for choosing a resolving element - the ratios of the positive elements of the resolving column to the elements of the vector are compiled P 0 and the number that gives the smallest ratio becomes the resolving element with respect to which the simplex table will be recalculated. The line containing this element is called the enable line. If there are no positive elements in the resolution column, then the problem has no solution. After determining the resolving element, they proceed to recalculation of a new simplex table.
5. Rules for filling out a new simplex table. Unit is put in place of the resolving element, and other elements are assumed to be equal 0 . The resolving vector is added to the basis, from which the corresponding zero vector is excluded, and the remaining basis vectors are written without changes. The elements of the resolution string are divided by the resolution element, and the remaining elements are recalculated according to the rectangle rule.
6. This is done until f– all elements of the string will not become positive.

Let's consider solving the problem using the algorithm discussed above.
Given:

We bring the problem to canonical form:

We compose the vectors:

Fill out the simplex table:

:
Let's recalculate the first element of the vector P 0, for which we make a rectangle of numbers: and we get: .

We perform similar calculations for all other elements of the simplex table:

In the received plan f– the line contains one negative element – ​​(-5/3), vector P 1. It contains in its column a single positive element, which will be the enabling element. Let's recalculate the table regarding this element:

No negative elements in f– line means found optimal plan:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).

• Ashmanov S. A. Linear programming, M: Nauka, 1998,
• Ventzel E.S. Operations Research, M: Soviet Radio, 2001,
• Kuznetsov Yu.N., Kuzubov V.I., Voloshenko A.B. Mathematical programming, M: Higher School, 1986.

Custom Linear Programming Solution

You can order any assignments in this discipline on our website. You can attach files and specify deadlines at

An example of solving a problem using the simplex method is considered, as well as an example of a solution dual problem.

Problem condition

To sell three groups of goods, a commercial enterprise has three types of limited material and monetary resources in the amount of b 1 = 240, b 2 = 200, b 3 = 160 units. At the same time, for the sale of 1 group of goods for 1 thousand rubles. commodity turnover, the resource of the first type is consumed in the amount of a 11 = 2 units, the resource of the second type in the amount of a 21 = 4 units, the resource of the third type in the amount of a 31 = 4 units. For the sale of 2 and 3 groups of goods for 1 thousand rubles. turnover is consumed according to the resource of the first type in the amount of a 12 = 3, a 13 = 6 units, the resource of the second type in the amount of a 22 = 2, a 23 = 4 units, the resource of the third type in the amount of a 32 = 6, a 33 = 8 units . Profit from the sale of three groups of goods for 1 thousand rubles. turnover is respectively c 1 = 4, c 2 = 5, c 3 = 4 (thousand rubles). Determine the planned volume and structure of trade turnover so that the profit of the trading enterprise is maximized.

To the direct problem of turnover planning, solved by simplex method, compose dual problem linear programming.
Install conjugate pairs of variables direct and dual problems.
According to conjugate pairs of variables, from the solution of the direct problem we obtain solution of the dual problem, in which it is produced resource assessment, spent on the sale of goods.

Solving the problem using the simplex method

F = 4 x 1 + 5 x 2 + 4 x 3 ->max

0)))(~)" title="delim(lbrace)(matrix(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

We solve the simplex method.

We introduce additional variables x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 to transform the inequalities into equalities.

Let's take x 4 = 240 as a basis; x 5 = 200; x 6 = 160.

We enter the data into simplex table

Simplex table No. 1

Objective function:

0 240 + 0 200 + 0 160 = 0

We calculate estimates using the formula:

Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0

Since there are negative estimates, the plan is not optimal. Lowest score:

We introduce the variable x 2 into the basis.

We define a variable emerging from the basis. To do this, we find the smallest non-negative ratio for the x2 column.

= 26.667

Smallest non-negative: Q 3 = 26.667. We derive the variable x 6 from the basis

Divide the 3rd line by 6.
From the 1st line, subtract the 3rd line, multiplied by 3
From the 2nd line, subtract the 3rd line, multiplied by 2

We calculate:

We get a new table:

Simplex table No. 2

Objective function:

0 160 + 0 440/3 + 5 80/3 = 400/3

We calculate estimates using the formula:

Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6

Since there is a negative estimate Δ 1 = - 2/3, the plan is not optimal.

We introduce the variable x 1 into the basis.

We define a variable emerging from the basis. To do this, we find the smallest non-negative ratio for the column x 1.

Smallest non-negative: Q 3 = 40. We derive the variable x 2 from the basis

Divide the 3rd line by 2/3.
From the 2nd line, subtract the 3rd line, multiplied by 8/3

We calculate:

We get a new table:

Simplex table No. 3

Objective function:

0 160 + 0 40 + 4 40 = 160

We calculate estimates using the formula:

Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1

Since there are no negative ratings, the plan is optimal.

Solution to the problem:

Answer

That is, it is necessary to sell the first type of goods in the amount of 40 thousand rubles. There is no need to sell goods of types 2 and 3. In this case, the maximum profit will be F max = 160 thousand rubles.

Solution of the dual problem

The dual problem has the form:

Z = 240 y 1 + 200 y 2 + 160 y 3 ->min

Title="delim(lbrace)(matrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}

We introduce additional variables y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 to transform the inequalities into equalities.

Conjugate pairs of variables of the direct and dual problems have the form:

From the last simplex table No. 3 of the direct problem, we find the solution to the dual problem:

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;

The idea of ​​the simplex method is to move from one basis to another, obtaining a function value that is at least not less than the existing one (each basis corresponds to a single function value).
Obviously, the number of possible bases for any problem is finite (and not very large).
Therefore, sooner or later, the answer will be received.

How is the transition from one basis to another carried out?
It is more convenient to record the solution in the form of tables. Each line is equivalent to an equation of the system. The highlighted line consists of the coefficients of the function (compare for yourself). This allows you to avoid rewriting variables every time, which significantly saves time.
In the highlighted line, select the largest positive coefficient. This is necessary in order to obtain a function value that is at least no less than the existing one.
Column selected.
For positive coefficients of the selected column, we calculate the ratio Θ and select the smallest value. This is necessary so that after the transformation the column of free terms remains positive.
Row selected.
Therefore, the element that will be the basis has been determined. Next we count.

One of the methods for solving optimization problems ( usually associated with finding the minimum or maximum) linear programming is called . Simplex method includes a whole group of algorithms and methods for solving linear programming problems. One of these methods, which involves recording the source data and recalculating them in a special table, is called tabular simplex method.

Let us consider the algorithm of the tabular simplex method using the example of the solution production task , which boils down to finding a production plan that ensures maximum profit.

Input data for the simplex method problem

The company produces 4 types of products, processing them on 3 machines.

Time standards (min./piece) for processing products on machines are specified by matrix A:

The machine operating time fund (min.) is specified in matrix B:

Profit from the sale of each unit of product (RUB/piece) is given by matrix C:

Purpose of the production task

Draw up a production plan that will maximize the profit of the enterprise.

Solving the problem using the tabular simplex method

(1) Let us denote by X1, X2, X3, X4 the planned number of products of each type. Then the desired plan: ( X1, X2, X3, X4)

(2) Let's write down the plan constraints in the form of a system of equations:

(3) Then the target profit is:

That is, the profit from fulfilling the production plan should be maximum.

(4) To solve the resulting conditional extremum problem, we replace the system of inequalities with a system of linear equations by introducing additional non-negative variables into it ( X5, X6, X7).

(5) Let's accept the following reference plan:

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) Let's enter the data into simplex table:

In the last line we enter the coefficients of the objective function and its value itself with the opposite sign;

(7) Select in the last line greatest (modulo) is a negative number.

Let's calculate b = N / Items_of_the_selected_column

Among the calculated values ​​of b we choose least.

The intersection of the selected column and row will give us the resolving element. We change the basis to a variable corresponding to the resolving element ( X5 to X1).

• The resolving element itself turns to 1.
• For elements of the resolution line – a ij (*) = a ij / RE ( that is, we divide each element by the value of the resolving element and obtain new data).
• For elements of the resolution column, they are simply reset to zero.
• We recalculate the remaining elements of the table using the rectangle rule.

a ij (*) = a ij – (A * B / RE)

As you can see, we take the current cell being recalculated and the cell with the resolving element. They form opposite corners of the rectangle. Next, we multiply the values ​​from the cells of the other 2 corners of this rectangle. This work ( A * B) divide by the resolving element ( RE). And subtract from the current cell being recalculated ( a ij) what happened. We get a new value - a ij (*).

(9) Check the last line again ( c) on presence of negative numbers. If they are not there, the optimal plan has been found; we move on to the last stage of solving the problem. If there is, the plan is not yet optimal, and the simplex table needs to be recalculated again.

Since in the last line we again have negative numbers, we begin a new iteration of calculations.

(10) Since there are no negative elements in the last line, this means that we have found the optimal production plan! Namely: we will produce those products that have moved to the “Basis” column - X1 and X2. We know the profit from the production of each unit of output ( matrix C). It remains to multiply the found production volumes of products 1 and 2 with profit per 1 piece, we get the final ( maximum! ) profit for a given production plan.

ANSWER:

X1 = 32 pcs., X2 = 20 pcs., X3 = 0 pcs., X4 = 0 pcs.

P = 48 * 32 + 33 * 20 = 2,196 rub.

Galyautdinov R.R.

© Copying of material is permissible only if a direct hyperlink to