Solve the simplex method and perform a graphical interpretation. Linear programming. Simplex method

Liked? Add to bookmarks

Solving problems using the simplex method: online examples

Task 1. The company produces bathroom shelves in two sizes - A and B. Sales agents estimate that up to 550 shelves can be sold on the market per week. Each type A shelf requires 2 m2 of material, and each type B shelf requires 3 m2 of material. The company can receive up to 1200 m2 of material per week. To manufacture one shelf of type A, 12 minutes of machine time are required, and to manufacture one shelf of type B - 30 minutes; The machine can be used 160 hours a week. If the profit from the sale of shelves of type A is 3 monetary units, and from shelves of type B - 4 monetary units. units, then how many shelves of each type should be produced per week?

Task 2. Solve a problem linear programming simplex method.

Task 3. The company produces 3 types of products: A1, A2, A3, using two types of raw materials. The costs of each type of raw material per unit of production, the reserves of raw materials for the planning period, as well as the profit from a unit of production of each type are known.

1. How many items of each type must be produced to maximize profit?
2. Determine the status of each type of raw material and its specific value.
3. Determine the maximum interval for changes in inventories of each type of raw material, within which the structure of the optimal plan, i.e. The production nomenclature will not change.
4. Determine the quantity of products produced and the profit from production when increasing the stock of one of the scarce types of raw materials to the maximum possible (within the given range of output) value.
5. Determine the intervals of change in profit from a unit of production of each type at which the resulting optimal plan will not change.

Task 4. Solve a linear programming problem simplex method:

Task 5. Solve a linear programming problem using the simplex method:

Task 6. Solve the problem using the simplex method, considering as the initial reference plan the plan given in the condition:

Task 7. Solve the problem using the modified simplex method.
To produce two types of products A and B, three types of technological equipment are used. To produce a unit of product A, equipment of the first type uses a1=4 hours, equipment of the second type a2=8 hours, and equipment of the third type a3=9 hours. To produce a unit of product B, equipment of the first type uses b1=7 hours, equipment of the second type b2=3 hours, and equipment of the third type b3=5 hours.
Equipment of the first type can work for the production of these products for no more than t1=49 hours, equipment of the second type for no more than t2=51 hours, equipment of the third type for no more than t3=45 hours.
The profit from the sale of a unit of finished product A is ALPHA = 6 rubles, and product B is BETTA = 5 rubles.
Draw up a production plan for products A and B, ensuring maximum profit from their sale.

Task 8. Find optimal solution dual simplex method

The main algorithm for solving the ZLP is the simplex method. It can be used if the optimization problem is written in a special canonical form. In this case, all restrictions have the form of equalities and each basic variable occurs with a coefficient of 1 only in one equation, and in others the coefficient of the basic variable is equal to 0. Analytical expression for objective function should not contain basic variables, but be expressed only through free variables. If at the same time b i≥ 0, then we speak of an admissible canonical form.

The essence of the simplex method is a directed search of the vertices of the ODD in order to determine the coordinates of the vertex at which the objective function reaches an extremum. Let us introduce several definitions.

The reference solution of the system constraints is a solution when, for a system of constraints in an admissible canonical form, all free variables are equal to zero.

Degenerate support solutionreference solution in which one or more basic variables are equal to zero.

Valid reference solutionreference solution in which all basic variables ≥ 0.

The optimal solution of the ZLP will correspond to one of the admissible reference solutions. In the simplex method, starting from an admissible reference solution located at the vertex of the ODR polyhedron, they move to the neighboring vertex, maintaining the admissibility of the solution.

For the convenience of formulating the rules of the method, we write down the admissible canonical PAP form in another form called standard form. For example:

To simplify the implementation of the simplex method on a computer, it is presented in tabular form. In this case, each support solution corresponds to a new simplex table. Each row of the table corresponds to either a row of the objective function or a row of one of the constraints. An example table for the case of seven variables for the standard notation is given below.

In the simplex method, it is required to have an initial feasible support solution. Sometimes such a solution is easy to obtain. For example, if there is a constraint of the form with positive right side, then the additional variables used when writing constraints in the form of equalities form an admissible reference solution in which all design variables are equal to zero, and the additional variables are basic. However, in many problems there are constraints of the form 0 and = 0, for which the initial reference solution may be unacceptable. Therefore, the application of the simplex method in the general case must be preceded by the stage of searching for an acceptable solution. Let's consider one of the variants of the simplex method algorithm, taking into account the stage of searching for an acceptable solution.

Simplex method algorithm

1st stage: finding an acceptable reference solution.

Step 1. Inequality constraints are reduced to the form of equality constraints. The task is written in a standard form.

Step 2. For each constraint that has a negative free term, the signs of the coefficients of the free variables are examined. If at least one negative coefficient is missing, then the restrictions are inconsistent. If the free terms in all constraints are non-negative, then the reference solution is admissible and it is necessary to move on to the second stage (the stage of finding the optimal solution).

Step 3. For a constraint that has a negative free term, the free variable with a negative coefficient is selected. This variable will be the new basis variable. If there is more than one negative coefficient, then any one with a negative coefficient can be chosen as a new basis variable (the choice of variable in this case will affect the number of basis changes, but not the final result). Let it be a variable x l. If there is more than one constraint with a negative free term, then you can choose any one to analyze the coefficients.

Step 4. To select a new free variable, the relation is considered b j /a jl for all restrictions, and b j And a jl must have the same sign. The minimum ratio is found. The new free variable will be the basic variable for which the constraint is b j /a jl turned out to be minimal. In this case, the resolving element of the table will be located at the intersection of the column corresponding to the variable x l and a line corresponding to the constraint for which the minimum ratio was obtained.

Step 5. The basis is replaced. To recalculate the values ​​of elements of the simplex table after changing the basis, we introduce the following notation into the table:

at q=r; s=p,iteration number (basis change);

at q=r;sp,s=
;

at q r; s=p;q=
;

for other elements.

Step 6. Let's go back to step 2.

2nd stage: finding the optimal solution.

Step 1. The sign of optimality of the solution is checked.

Signs of an optimal solution:

a) the objective function will have a maximum value in the case when in the line (expression) of the objective function in the standard form of notation all the coefficients of the free variables are positive (the free term is not considered);

b) the objective function will have minimum value in the event that in the line of the objective function in standard form all the coefficients of the free variables are negative;

c) if in the expression of the target function in standard form all the coefficients of the variables are of the same sign and there is at least one zero coefficient, then the resulting solution is alternative, i.e. there will be another set of variables that deliver the same value to the target function.

If the optimality criterion is satisfied, then a solution has been found. The values ​​of free variables are equal to zero, the values ​​of basic variables are equal to the free terms of the corresponding constraints, the value of the objective function is equal to the free term of the objective function. If the optimality criterion is not satisfied, then go to step 2.

Step 2. In accordance with the rule for choosing a new basic variable, we transfer one of the free variables to basic ones.

The rule for choosing a free variable to be converted into a basis

When searching for the maximum (minimum) of a function written in standard form, a variable that has a negative (positive) coefficient in the expression of the objective function in standard form must be transferred to the basis. If there is more than one negative (positive) coefficient c j, then choose a variable that has a larger absolute value negative (positive) coefficient c j .

Step 3. In accordance with the rule for choosing a variable transferred from basic to free, we define a new free variable.

Let's formulate rule for choosing a variable to be converted from basic to free.

To select a new free variable x i attitude needs to be considered b j /a ij for all restrictions (
), (
), from these relations select the minimum, and as a new free variable select the basic variable for which the minimum relation was obtained to limit b j /a ij. Attitude b j /a ij should only be considered for positive a ij. If the minimum is reached for more than one index j, then any of the variables corresponding to j-th restrictions.

If none of a ij is not positive, then obtaining a new feasible solution is impossible, i.e. when searching for a minimum, the objective function is not limited from below, and when searching for a maximum, it is not limited from above ( sign of unboundedness of the objective function).

Step 4. The basis is replaced similarly to step 5 of the first stage.

Step 5. Let's move on to step 1.

Example 2. Find under restrictions

Let's write the problem in standard form and present it in the form of a simplex table:

The sign of inconsistency of restrictions is not satisfied. An admissible solution was not found, since the free term for the constraint x 5 is equal to -5. To obtain an admissible solution, we change the basis. Let's choose as the resolving column x 1 ; permission line - x 6 (since 2/1<5/2). Разрешающий элемент подчеркнут. Строим новую симплекс-таблицу.

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) 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 we again have negative numbers in the last line, 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

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