Modified simplex method

In the modified method the matrix

is not recalculated, only the matrix is ​​stored and recalculated. The rest of the algorithm is similar to the one described above.

1. Calculate dual variables

2. Optimality check. is converted to.

The check consists of a calculation for all columns. Column with value< 0 можно вводить в базис.

Often chosen minimum value, but to do this you need to iterate over all the columns.

More often a value less than a certain specified value is chosen

If such a column is not found, the maximum absolute value found is taken as and the corresponding column is entered into the basis.

3. Definition of output.

Let be the input column corresponding to the variable Basic plan is the solution of the system Increase.

Let's multiply from the left by, i.e.

Here is the basic plan, and is the decomposition of the input column according to the basis.

We find maximum value, in which all values ​​are not negative. If it can be taken as large as desired, the solution is not limited. Otherwise, one of the elements will go to null value. We derive the corresponding column from the basis.

4. Recalculation of the reference (basic) plan.

Calculate new reference plan according to the formula already given with the found value.

5. We recalculate the inverse to the basic one.

Let be the output column.

Matrix B can be represented as

Where - basis matrix no output column.

After replacing the column, the basis matrix will look like

We need to find a matrix such that

Comment.

When recalculating the matrix, rounding errors accumulate. To avoid large errors, the matrix is ​​recalculated completely from time to time. This process is called "repetition".

Multiplicative version of the simplex method

In the multiplicative version, the matrix is ​​not stored, only the factors are stored

When deciding economic tasks often the constraint matrix is ​​sparse, in which case the multiplicative version gets additional benefits- you can store multipliers in a compressed form (do not store zeros).

Other options for the simplex method

To avoid the accumulation of rounding errors, LU decomposition of the matrix can be used.

With an overwhelming number of restrictions of the “inequality” type, it can be used variable basis method.

The method is based on the fact that the basis matrix can be represented in the form

Its inverse has the form

With relatively small matrix sizes, the rest of the matrix may not be stored.

This approach can solve problems with tens of millions of lines of constraints (for example, from game theory).

Dual simplex method

For implementation dual method it is necessary to move from the minimum problem to the maximum problem (or vice versa) by transposing the coefficient matrix. When moving from the problem to the minimum, the objective function takes the form:

under restrictions

Duality theorem. If one of a pair of dual problems has an optimal plan, then the other has a solution, and the extreme values ​​of the linear functions of these problems are equal.

If linear function one of the problems is not limited, then the other has no solution.

The main idea of ​​the modified simplex method is to use the current inverse matrix(and the source data of the problem) when performing the calculations necessary to determine the variables to include and exclude. Representing an inverse matrix in multiplicative form allows you to calculate a sequence of inverse matrices directly from the source data without using multiple inversion operations for each basis. As in the usual simplex method, in this case the initial basis is always the identity matrix I, the inverse of which is this matrix itself. Therefore, if
- sequence of inverse matrices corresponding to iterations 1, 2,…,i, and
is the sequence of matrices corresponding to them, then

The sequence of substitutions leads to the following formula:

(2.23)

It should be emphasized that the multiplicative representation of the inverse matrix is ​​not necessary procedure to implement the computational scheme of the modified simplex method, and at each iteration you can use any of the methods for inverting the current basis. When using the modified simplex method, it is important that the inverse matrices are calculated in a way that reduces the impact of machine rounding errors.

The steps of the modified simplex method algorithm are essentially the same as those of the conventional simplex method algorithm. After finding the initial basis I, the corresponding vector of coefficients is determined objective function, the elements of which are formed depending on whether the initial basic variables are residual (redundant) or artificial.

1. 2.7.2. Multiplicative representation of an inverse matrix

In the multiplicative representation of the inverse matrix, a matrix algebra operation is used to calculate the elements of the matrix inverse to the new matrix of basis vectors from the known inverse matrix of the previous basis, provided that the two bases under consideration differ in only one column vector. This method of representing the inverse matrix is ​​convenient to use in the computational scheme of the simplex method, since the bases corresponding to each two successive iterations differ in only one column (as a result of replacing the eliminated column vector of the current basis with a new column vector). In other words, the current basis matrix and a new basis matrix
, corresponding to the next iteration, differ in only one column. With the multiplicative representation of the inverse matrix
corresponding to the new basis, it is calculated by multiplying on the left the inverse of the current matrix
into a matrix formed according to certain rules .

Let's define the identity matrix in the following way:

(2.24)

Where - unit column vector with the i-th element, equal to one, and other elements, equal to zero. Let us assume that the matrices are known And
, and vector matrices is replaced by a new vector ; as is customary when describing the simplex method, the vector is defined as included in the basis, and the vector - as excluded from the basis. To simplify the writing of mathematical relationships, we use the following definition
,wherein will represent the kth element
. Then the new inverse matrix
can be calculated using the following formula:

(2.25)

provided that
. If
, matrices
does not exist. Note that the matrix obtained from the matrix by replacing its r-th column vector column .

3. Modified simplex method

This type of simplex method is based on features of linear algebra that allow one to work with part of the constraint matrix when solving a problem. Sometimes the method is called the inverse matrix method.

During the operation of the algorithm, the constraint matrix is ​​spontaneously inverted in parts corresponding to the current basis vectors. This ability makes the machine implementation of calculations very attractive due to the saving of memory for intermediate variables and a significant reduction in calculation time. This ability is good for situations where the number of variables n significantly exceeds the number of constraints m.

In general, the method reflects the traditional features of the general approach to problem solving linear programming, which includes canonization of the problem conditions, calculation of simplex differences, verification of optimality conditions, decision-making on basis correction and Jordan-Gauss elimination. Features include the presence of two tables - the main and auxiliary ones, the order in which they are filled out and some specificity of the calculation formulas.

Knowing the optimal plan for this problem, based on the relations we obtain the optimal plan original problem.

Thus, the process of finding a solution to a nonlinear programming problem includes the following steps:

1. The original problem is reduced to a linear programming problem.

2. Find a solution linear problem

Using the relationships, the optimal plan for the original problem is determined and the maximum value of the objective function of the nonlinear problem is found.

First stage: Receiving assignments for coursework

1. All numerical data relating to the proposed production and economic processes are taken based on a six-digit code:

Under each number the letters a, b, c, d, e, f are written in the following form:

from last line tables of individual tasks, we find the columns corresponding to the letters a, b, c, d, e, f. Then the numerical data necessary to complete this course work will be the data located in a - that column in line 9, b - that column in line 5, c - that column in line 5, d - that column in line 8, e - that column in line 7 and f – that column in line 2.

According to the table of initial tasks for any variant of tasks in column a, the executor receives the variant of the task being performed. In my case, the number 9 corresponds to option 9.

A certain plant produces three types of product and consumes two types of resources. The production function of each type of product at the enterprise is described by the equalities:

where C i and are constant values, i = 1, 2, 3;

X 1 – labor resources in man-days;

X 2 – monetary and material resources, in tenge;

Y i is the resulting product

X 1 = a 1 x 1 + b 1 x 2 + c 1 x 3

X 2 = a 2 x 1 + b 2 x 2 + c 2 x 3

Find all non-negative basic solutions and determine the optimal plan F = y 1 + y 2 + y 3 .

It is known that for the production of j – that type of product, a ij units of i – that resource are spent. These costs are given in tables 3.9.1. – 3.9.10

Subsequent numerical data are taken only from the source data table of the selected task option, i.e. from table No. 3.9.11.

2. According to table column No. 3.9.11 for line 8, the initial table of costs of resource units will be table No. 3.9.4 i.e. following table:

Products resources
I	8	4	6
II	160	240	200

3. Using column c – on line 3 we find with 1 =6, α 1 =0.6

4. Using column d – on line 5 we determine with 2 =5, α 2 =0.5

5. Using column e – line 4, we establish that c 3 =8, α 3 =0.4.

6. And finally, using column f - in line 1 we find T person days = 1000, P tenge = 280000

For production there are labor resources T man days and monetary resources P tenge.

It is required to find the optimal production plan at which the output product will be the largest.

The second stage is drawing up mathematical model tasks

1. Based on the initial data obtained in the first stage and the description of the given production process, the following table is compiled:

Products resources
I	8	4	6	1000
II	160	240	200	280000

Let X 1 denote resources of the first type.

Let X 2 denote resources of type II.

2. Turning to the conditions of the problem, we determine everything possible restrictions, combining them into a system of restrictions.

8Х 1 + 4Х 2 + 6Х 3 ≤ 1000

240Х 1 + 200Х 2 + 160Х 3 ≤ 280000

Thus, we got a nonlinear programming problem. Such problems are called nonlinear programming problems.

Nonlinear programming problems are solved by reducing them to linear programming problems.

To solve the linear programming problem, the simplex method is used.

The third stage is the choice of a method for solving the obtained mathematical problem

1. To solve linear programming problems using the simplex method, the problem is reduced to canonical form:

8X 1 + 4X 2 + 6X 3 + X 4 = 1000

240Х 1 + 200Х 2 + 160Х 3 + Х 5 = 280000

Methods are being developed for finding extreme values ​​of the objective function among the set of its possible values ​​determined by constraints. The presence of restrictions makes tasks mathematical programming fundamentally different from classical problems mathematical analysis to find extreme values ​​of a function. Methods of mathematical analysis for searching for the extremum of a function in problems...

Finding the Kuhn-Tucker point provides an optimal solution to the nonlinear programming problem. Theorem 2 can also be used to prove the optimality this decision nonlinear programming problems. To illustrate, consider the example again: Minimize under constraints Using Theorem 2, we prove that the solution is optimal. We have So...

Rays emanating from one point are called a polyhedral convex cone with a vertex at a given point. 1.4 Mathematical foundations for solving a linear programming problem graphically 1.4.1 Mathematical apparatus To understand everything further, it is useful to know and imagine the geometric interpretation of linear programming problems, which can be given for the cases n = 2 and n = ...

If we put the current basic variables in such a simplex table equal to Ai,0, and the free ones equal to zero, we will get optimal solution. The practice of using the simplex method has shown that the number of iterations required to solve a linear programming problem usually ranges from 2m to 3m, although for some specially constructed problems, calculations according to the rules of the simplex method turn into direct...

Send your good work in the knowledge base is simple. Use the form below

Good work to the site">

Students, graduate students, young scientists who use the knowledge base in their studies and work will be very grateful to you.

Similar documents

Geometric solution standard tasks linear programming with two variables. Universal method solutions to the canonical problem. The main idea of ​​the simplex method, implementation using an example. Tabular implementation of a simple simplex method.

abstract, added 06/15/2010


Types of linear programming problems and problem formulation. The essence of optimization as a branch of mathematics and characteristics of the main methods for solving problems. The concept of the simplex method, real applied problems. Algorithm and stages of solving the transport problem.

course work, added 02/17/2010


Solving linear programming problems using graphical and simplex methods. Solution of the problem dual to the original one. Determining the optimal plan for assigning consumers to suppliers of homogeneous cargo, subject to minimizing the total vehicle mileage.

test, added 08/15/2012


Using the simplex method for solving linear programming problems to calculate the daily volume of production. Checking the plan for optimality. Recalculation simplex table Jordan-Gauss method. Drawing up a model of a transport problem.

test, added 02/18/2014


Economic and mathematical model of obtaining maximum profit, her decision graphical method. Algorithm for solving a linear programming problem using the simplex method. Compilation dual problems and and her graphic solution. Payment matrix solution.

test, added 05/11/2014


Basics mathematical modeling economic processes. General characteristics of graphical and simplex methods for solving direct and dual linear programming problems. Features of the formulation and methodology for solving the transport problem.

course work, added 11/12/2010


Drawing up a mathematical model of the problem. Calculation of the optimal transportation plan with minimum cost using the potential method. The best option special mobile equipment for technical support production management.

test, added 06/01/2014

MODIFIED SIMPLEX METHODThe simplex method is not the most effective
computer procedure, since it calculates and
stores information that is not needed for the current
iteration and may not be used at all for
making decisions during subsequent iterations. For
coefficients of non-main variables in the equation
(0), coefficients of the introduced main variables
in other equations and the right-hand sides of the equations at
Each iteration uses only the relevant one
information. Therefore, a procedure is needed that
can obtain this information efficiently, without
calculations and storage of all other coefficients
(That's what it is modified simplex method).

It calculates and stores only information
necessary for this moment, and important data
conveys in a more compact form.
It uses matrix operations, so
it is necessary to describe the problem using matrices.
CAPITAL letters, highlighted in bold
represent matrices, capital letters,
those in bold represent
vectors.
Italics are scalar quantities, highlighted zero
(0) denotes the zero vector (its elements are equal
zero, both rows and columns), zero (0)
represents the normal number 0. Using
matrices standard form of linear model
programming takes the form:

Maximize Z = c x,
according to
A x ≤ b and x ≥ 0,
where c is a row vector
x, b, and 0 column vectors

A - matrix
For augmented form, column vector
dummy variables:
Restrictions:
I = (m × m identity matrix)
0 = (n + m elements of the zero vector)

Finding a basic feasible solution
The general approach of the simplex method is to obtain
sequence of improving OA solutions up to
until the optimal one is found
solution. One of the key features
modified simplex method - how it
finds a new OD solution after defining it
main (basic) and non-basic (non-basic)
variables. Given these variables, the resulting
main solution – solution of m equations
In which n non-basic variables from n + m
elements
are set equal to zero.

Eliminating these n variables by setting them to zero,
we obtain a system of equations m with m variables
(main (basic) variables):
where is the vector of basic variables:
obtained by excluding non-basic (non-basic)
variables:

And the basis matrix
The result obtained by excluding the columns corresponding to
coefficients of non-basic variables from .
(In addition, xB elements and B columns are in different
okay). The simplex method introduces only basic
variables such that B is non-degenerate, so
the inverse matrix B-1 will always exist.
To solve B x B = b, both sides are multiplied by B-1:
B-1 B x B = B-1 b.

cB is a vector whose elements are coefficients
objective functions (including zeros for dummy
variables) for the corresponding xB elements.
The objective function for this basic solution is:

Example:
- Iteration 0
so
so

10.

- Iteration 1
so
so

11.

- Iteration 2
so
so

12. Matrix form for the current set of equations

Matrix form for a set of equations,
appearing in the simplex table for any iteration
the original simplex method. For source system
equations, the matrix form is:
Algebraic operations performed using the simplex method (multiply the equation by a constant and add
product of one equation by another) are expressed in
matrix form, after multiplying both parts
the original system of equations into the corresponding
matrices

13.

14.

This matrix will have the same elements as the identity matrix
matrix, except that each product
for a certain algebraic operation it will take
the space required to perform this operation,
using matrix multiplication. Even after the series
algebraic operations over several iterations,
we can still conclude that this matrix
should be for the whole series, using what we know about
right side new system equations. After any
iterations, xB = B-1b and Z = cB B-1b, so the right sides
the new system of equations took the form

15.

Since we perform the same series
algebraic operations with both sides
original set, to multiply the right and
on the left side, we use the same matrix.
Hence,
Desired matrix form of the system of equations
after any iteration:

16.

Example: matrix form obtained after iteration 2
for the glass factory problem using B-1 and cB:

17.

Using the quantities xB = B-1 b and Z = cB B-1 b:

18.

Only B-1 must be received for calculation
all numbers of the simplex table from the original
task parameters (A, b, cB). Any of these numbers
can be obtained individually as
As a rule, only vector multiplication is performed
(one row per column) instead of full
matrix multiplication. Required numbers for
performing iterations of the simplex method can be
receive as needed without spending
unnecessary calculations to get all the numbers.

19. Brief overview of the modified simplex method

1. Initialization: As in the original simplex method.
2. Iteration: Step 1 Determine the entered basic (main)
variables: As in the original simplex method.
Step 2 Determine the outgoing basis variables: As in the original
simplex method, with the exception of counting only those necessary for
of these numbers [coefficients of the introduced basic variables in
each equation except Eq. (0), and then, for each strictly
positive coefficient right part this equation].
Step 3 Determine a new OD solution: Obtain B-1 and set xB=B-1b.
3. Optimality analysis: As in the original simplex method, for
except for counting only the numbers necessary for this analysis,
i.e., coefficients of non-basic (non-basic) variables in
Equation (0).
At step 3 of the iteration, B-1 can be obtained each time using
standard computer program for reversal (inversion)
matrices. Since B (then B-1) changes little from one iteration to
another, it is more efficient to obtain a new B-1 (denoted B-1 new) from
B-1 in the previous iteration (B-1 old). (For the original OA solution).