Integer linear programming branch and bound method. Example solutions to the traveling salesman problem using the branch and bound method

The following problem needs to be solved:

max 2x 1 + x 2

5x 1 + 2x 2 10

3x 1 + 8x 2 13

First, let's solve this problem graphically without integer restrictions. The solution can be found either using the simplex method or graphically. Let's find it graphically (Figure 4). The coordinates of the optimum point can be found by solving the system of equations: 5x 1 + 2x 2 = 10 x 1 = 27/17

3x 1 + 8x 2 = 13 x 2 =35/34

X G = (27/17;35/34), z G =143/34

Figure 4 - Graphical solution to the problem without integrity restrictions

Let's start building a tree, the first vertex of which will correspond to the entire ODP of the non-integer problem (G), and its estimate will be equal to z G (Fig. 5).

Figure 5 - Diagram of the branch and bound method

The resulting plan is not integer, so we take its arbitrary non-integer component, for example, the first one (x 1 Z; [x 1 ] = 1) and divide the ODP into two parts as follows:

G 1 = (XG: x 1 1)

G 2 =(XG: x 1 2)

This means that the region G 1 will include all points from G whose abscissa is no more than 1, and in G 2 - where it is not less than 2. Points with fractional abscissa values from 1 to 2 are excluded from consideration.

Let's depict these areas on a graph (Figure 6).

From Figure 6 it is clear that G 2 represents one point X G 2 = (2;0), therefore, on this set the optimum of the problem is 4 ( 2 = 4).

The plan X G 2 is integer, therefore, a solution to the integer problem may have already been found. However, we still need to find an estimate for the set G 1 |. It may be at least 4 (but definitely no more than 143/34). If this is so, then you need to check whether the solution to the problem on G 1 is an integer. If it is an integer, then it is a solution to the problem, and if not, then the solution process must be continued, splitting G 1

Figure 6 - Splitting the set into parts

On G 1 the optimum point can be found by solving the system of equations:

x 1 = 1 x 1 =1

3x 1 + 8x 2 = 13 x 2 =5/4

X G 1 = (1; 5/4), z G =13/4

The score is less than 4, therefore, the solution to the problem is X * =X G 2 =(2;0),z * =4.

3.4 Solving an integer linear programming problem using the branch-and-bound method using the “Business Problem System” subsystem

ZTsLP can be solved using the application package “Quantitative Systems for Business” (“Business Problem System”) . The corresponding program is launched by the file intlprog.exe. It solves both partial and full integer linear programming problems with up to 20 variables and constraints using the branch and bound method. This includes solving problems with Boolean variables (i.e., with variables that can take one of two values - 0 or 1; as, for example, in the assignment problem). By default, all variables are non-negative. The program allows you to enter integer limits for variables without including them in the total number of limits. By default, the lower limit is 0 and the upper limit is 32000. If non-integer limits need to be set, they are entered as normal limits.

If a problem has several optimal plans, only one of them is found. Information about the presence of a multiple solution is not displayed.

Mode 2 (input new task) includes three stages. At the first stage, information about the dimension of the problem, the direction of extremization and variable names is entered (by default XI, X2,..., Xn).

The second step is to determine whether all variables are integers, whether all variables are Boolean, and whether bounds will be introduced on the variables. If you answer “no” to the first question or “yes” to the third, a table is displayed (Figure 7):

Enter limit and bounds for variables

(Default values lower limit 0 and upper limit 32000)

AC no. Name Limit (I/C) Lower Gr. Upper gr.

1 x 1 <0 > <0 >

2 X 2 <0 > <0 >

Figure 7 - Definition of limits and boundaries

By setting I (integer) in the Limit column, an integer constraint is imposed on the variable. Otherwise, the (C, continuous) variable can also take non-integer values, i.e. is continuous.

Boundary values are rounded to whole numbers. If the lower one is greater than the upper one, an error message is displayed.

At the third stage, coefficients for variables and signs in restrictions are introduced.

In the solutions menu there is an option to correct the integer error (by default it is 0.001).

Solving the problem using the branch and bound method is not accompanied by a graphical illustration (an image of a tree) in the program, but to explain the algorithm, we present such an illustration in Figure 8.

The algorithm of the branch and bound method implemented in this program is somewhat different from that discussed above in the guidelines and is less effective in the sense that it may require more iterations. However, it is useful to review it to clearly illustrate the difference in approaches. In addition, in many textbooks, the application of the branch and bound method is discussed specifically using this modification as an example.

The main difference is that the most “promising” subset is not selected at each stage. After the next subset is divided into two parts, the score of both parts is not immediately calculated, but instead each branch of the tree is sequentially considered to the end. The original ODP is divided into subsets according to the first non-integer variable in the optimal plan of the non-integer problem. Then they consider the vertex to which the sign corresponds, split the corresponding subset in the same way as the original ODP, again consider the vertex to which the sign corresponds, etc. until an integer plan is obtained, or the problem turns out to be unsolvable. Only after this do they return to considering the vertices to which the sign corresponded.

At the same time, at each iteration, information is displayed about the current integer boundaries (defining the subset under consideration), the optimal plan of the non-integer problem, whether it is integer, and the value objective function(CF) on it and about the values of ZL or ZU. For a task, the value of the lower limit ZL is displayed at the maximum, and the value of the upper limit ZU is displayed at the minimum. Until some integer solution is found, ZL = -1*10 20 and ZU = 1*10 20.

After finding an integer plan, it is impossible to immediately judge whether it is optimal, since not the most promising vertices were considered. But we can confidently say that the desired maximum is not less (and the minimum is not greater) than the value of the objective function in the integer plan. Therefore, the values of the boundaries ZL and ZU change (unless an integer plan with a no less (not more) value of the objective function was previously found).

Branches with a score less than ZL or greater than ZU are not considered. The plan corresponding to the boundary is remembered. Once all subsets have been considered or excluded from consideration, this plan can be considered optimal.

Let us explain this with an example (Fig. 8):

max 3x 1 + 2x 2

7x 1 + 5x 2 35

9x 1 + 4x 2 36

At the first iteration, a non-integer solution X = (2.353, 3.706) was found. The entire ODP (set G) is divided into two subsets - G 1 and G 2 as follows:

G 1 = (XG: x 1 3)

G 2 = (XG: x 1 2).

At the second iteration, the problem is solved on the subset G 1 . The resulting solution is also non-integer. Next, instead of considering a subset of G 2, we continue to consider G 1. In the appropriate plan, select the first non-integer component (this is x 2) and divide G 1 into G 3 and G 4. At the third iteration, G 3 is considered - there are no admissible plans on this subset. Only after this, at the fourth iteration, is the second branch coming out of G 1 - a subset of G 4 - considered. Further similar.

At the fifth iteration, an integer solution was found on the subset G 5, which corresponds to the value of the objective function 12. At the next iteration, this value is assigned to the value ZL, which was previously equal to -1*10 20 . The corresponding plan is remembered - it may turn out to be optimal. But at the sixth iteration, an integer plan is again obtained, the objective function of which is equal to 13 (more than 12) - ZL changes again, the new plan is remembered.

After this, at the seventh iteration, they move on to considering the subset G 2, which is divided into G 7 and G 8.

At the thirteenth iteration (subset G 14), an integer solution X = (0; 7) is found again, the objective function on it is equal to 14. ZL is changed again and the corresponding plan is remembered.

The plan found at the fourteenth iteration is also an integer, but it is not remembered, since 13<14 (ZL=14). План, найденный на пятнадцатой итерации, тоже, к сожалению, не запоминается, так как 1414, а программа ставит своей целью найти хотя бы одно решение.

The presence of other optimal plans is ignored here.

Thus, the solution X = (0; 7) was obtained in 15 iterations.

Note that if a more efficient version of the branch and bound method were used, the scheme of which is described in the guidelines, then after the second iteration there would be a direct transition to the seventh. In fact, if we consider the values of the objective function on the corresponding plans as an estimate of subsets, then the estimate of G 2 is higher. Therefore, iterations from 3 to 6 are redundant, and the total number of iterations could be 11.

The branch and bound method is one of the combinatorial methods. Its essence lies in an orderly selection of options and consideration of only those of them that turn out to be promising according to certain criteria, and discarding unpromising options.

The branch and bound method consists of the following: the set of feasible solutions (plans) is divided in some way into subsets, each of which is again divided into subsets in the same way. The process continues until the optimal integer solution is obtained original problem.

Solution algorithm:

Initially, we find the optimal plan of the problem using the simplex method or the artificial basis method without taking into account the integer number of variables. Let it be plan X 0 . If there are no fractional numbers among the components of this plan, then the desired solution to this problem has been found and

If among the components of plan X 0 there are fractional numbers, then X 0 does not satisfy the integer condition and it is necessary to carry out an orderly transition to new plans until a solution to the problem is found. Let us show how this can be done, first noting that F(X 0) F(X) for any subsequent plan X.

Assuming that the found optimal plan X 0 does not satisfy the condition of integer variables, we thereby assume that among its components there are fractional numbers. Let, for example, the variable take on a fractional value in terms of X 0. Then, in the optimal integer plan, its value will be at least either less than or equal to the nearest smaller integer, or greater than or equal to the nearest larger integer. By determining these numbers, we use the simplex method to find a solution to two linear programming problems:

Let's find a solution to linear programming problems (I) and (II). Obviously, one of the following four cases is possible here:

1. One of the problems is unsolvable, and the other has an integer optimal plan. Then this plan and the value of the objective function on it provide the solution to the original problem.
2. One of the problems is unsolvable, and the other has an optimal plan, among the components of which are fractional numbers. Then we consider the second problem and in its optimal plan we select one of the components, the value of which is equal to a fractional number, and we construct two problems similar to problems (I) and (II).
3. Both problems are solvable. One of the problems has an optimal integer plan, and the other problem's optimal plan has fractional numbers. Then we calculate the values of the objective function on these plans and compare them with each other. If on an integer optimal plan the value of the objective function is greater than or equal to its value on the plan, among the components of which there are fractional numbers, then this integer plan is optimal for the original problem and it, together with the value of the objective function on it, gives the desired solution.

If the value of the objective function is greater in the plan, among the components of which there are fractional numbers, then one of these numbers should be taken and for the problem whose plan is being considered, it is necessary to construct two problems similar to (I) and (II).

4. Both problems are solvable, and the optimal plans for both problems include fractional numbers. Then we calculate the value of the objective function on these optimal plans and consider the problem for which the value of the objective function is the largest. In the optimal plan for this problem, we choose one of the components whose value is fractional number, and construct two problems similar to (I) and (II).

Thus, the iterative process described above can be represented in the form of a tree on which the initial vertex corresponds to the optimal plan X 0 of problem (1)-(3), and each vertex connected to it by a branch corresponds to the optimal plans of problems (I) and (II ). Each of these vertices has its own branches. In this case, at each step, the vertex for which the function value is the largest is selected. If at some step a plan is obtained that has integer components, and the value of the function on it turns out to be greater than or equal to the value of the function at other vertices possible for branching, then this plan is the optimal plan for the original integer programming problem and the value of the objective function on it is maximum .

So, the process of finding a solution to the integer programming problem (1)-(4) using the branch and bound method includes the following main stages:

1. Find a solution to the linear programming problem (1)-(3).
2. Make up additional restrictions for one of the variables, the value of which in the optimal plan of problem (1)-(3) is a fractional number.
3. Find a solution to problems (I) and (II), which are obtained from problem (1)-(3) as a result of adding additional restrictions.
4. If necessary, create additional restrictions for a variable whose value is fractional, formulate problems similar to problems (I) and (II), and find their solution. The iterative process continues until a vertex is found that corresponds to the integer plan of problem (1)-(3) and such that the value of the function at this vertex is greater than or equal to the value of the function at other vertices possible for branching.

The branch and bound method described above has a simpler logic circuit calculations than the Gomori method. Therefore, in most cases, to find a solution specific tasks This method is used for integer programming using a computer.

integer programming problem traveling salesman backpack

A traveling salesman (wandering merchant) wants to visit a number of cities and return to the original city, minimizing the total length (cost) of travel. This problem is formulated in mathematical form as the problem of finding a Hamiltonian cycle of minimum length in a weighted graph and is called the traveling salesman problem.

The following can be mentioned as its practical application. Let there be a machine capable of performing several operations. Its reconfiguration from one operation to another requires certain costs. It is required to use the machine in cyclic mode, minimizing the total costs of reconfiguration.

In a given problem, reconfiguration from one operation to another and reverse reconfiguration may require, generally speaking, different costs. Therefore, in the general case, the traveling salesman problem considers a weighted directed graph, the arcs of which in the forward and backward directions can have different weights.

To solve the traveling salesman problem, you can try to use the “greedy algorithm” that was successfully used in the minimum spanning tree problem. Let us first order the arcs by weights and include arcs of minimum weight, making sure that no vertices arise whose half-degree of outgoing or incoming values exceeds one, and no non-Hamiltonian cycles appear. However, as is easy to see, this approach does not guarantee an optimal solution. As a simple counterexample, we can consider the following graph.

Here, each edge corresponds to two arcs of the same weight.

The “greedy algorithm” will first include the edge in the loop
, as having minimal weight. The inclusion of this edge, as can be directly verified, necessarily leads to a Hamiltonian cycle
weight 29. Optimal

is the Hamiltonian cycle
has a weight of 12. Therefore, the "greedy algorithm" does not guarantee an optimal solution, although it can be used in practice as a useful heuristic, in many cases leading to solutions close to optimal.

No efficient algorithm is known for the traveling salesman problem. It is very likely that such an algorithm does not exist, although this has not yet been proven. Such problems are not uncommon in discrete mathematics. In the case of small dimensions, their exact solutions can be obtained on a computer using the “branch and bound” method.

The “branch and bound” method refers to a wide class of reduced search methods, the essence of which boils down to the following. The set of feasible solutions A is divided into two subsets A 0 and A 1, then each of the subsets is also divided into two subsets, etc. Schematically, this can be represented as a tree starting with the set of all solutions and ending with its singleton subsets, i.e. admissible solutions, which in our case are Hamiltonian cycles.

Among the feasible solutions, the one that is optimal in terms of the quality functional is selected, which in our case is the length of the Hamiltonian cycle. The point of the branch-and-bound method, however, is not to look at all feasible solutions, but to cut off most branches as early as possible. To do this, using heuristic considerations, they try to immediately follow the branch leading to a solution that is close in quality to the optimal one. After this, most of the other branches are cut off using boundaries for the quality functional, when it can be shown that the subset of solutions does not contain a solution that is better in quality than the existing one.

Let's look at the branch-and-bound method using the traveling salesman problem as an example. Let a weighted digraph be given by a distance matrix. If some arc is missing in the graph, then the corresponding element of the matrix will be assumed to be equal to ∞. Note that if the lengths of all arcs included in a certain vertex are reduced by the same number, then the length of the optimal Hamiltonian cycle will be reduced by the same number. The same applies to the many outgoing arcs. We will sequentially subtract positive numbers from the rows and columns of the distance matrix so that the matrix elements remain non-negative. Since the length of the optimal Hamiltonian cycle for a graph with a non-negative distance matrix is also non-negative, the sum of the subtracted quantities will be a lower bound for the length of the optimal cycle of the original graph.

Let's look at an example. Let a graph G be given with a symmetric distance matrix.

The “∞” icons on the diagonal correspond to the absence of loops in the graph - arcs leading from a vertex to the same vertex. Let us first obtain a lower bound for the length of the shortest Hamiltonian cycle. You can subtract one from the first, second, third and fourth rows, two from the fifth row, and another one from the fifth column. This gives a lower bound of 7, and the distance matrix becomes

Now let's select an arc for branching, i.e. Let us divide the set of Hamiltonian cycles into two subsets: those that include and those that do not include this arc. We expect that this arc will be part of an optimal or close to optimal cycle. To do this, we will follow the following heuristic rule: from the set of arcs of zero length, select the one whose exclusion leads to the maximum increase in the lower estimate. In our case, such an arc is the arc (1,2). Inhibiting this arc results in the matrix

from the first row and second column of which you can subtract one each, which increases the lower limit by 2 and makes it equal to 9.

The inclusion of the arc (1,2) leads to the fact that all other arcs leading to vertex 2, and all other arcs leaving vertex 1 are excluded. Therefore, the first row and second column of the matrix can no longer be considered, and they are deleted from the matrix . In addition, the arc (2,1) is excluded. The matrix takes the form

One can be subtracted from its first row and first column, resulting in the matrix

The lower score here increases by 2 and also becomes equal to 9.

The lower bound for the optimal cycle length remains unchanged.

Arc (2.5) should be forbidden, as leading to the appearance of a non-Hamiltonian cycle, and the matrix takes the form

The lower bound for the length of a Hamiltonian cycle remains equal to 9.

Let us schematically represent the analysis carried out in the form of a tree, where the circles contain lower bounds for the length of the Hamiltonian cycle.

Looking at this tree, we immediately see that the resulting Hamiltonian cycle is the shortest, because moving along any other branch of the tree cannot lead to a shorter cycle.

Is there an efficient algorithm to solve the traveling salesman problem? a) yes; b) no; c) unknown.

Is the described branch and bound method an efficient algorithm for solving the traveling salesman problem? a) yes; b) no; c) unknown.

INTRODUCTION........................................................ ................................................... 3

1. ..…………….4

2. BRANCH AND BOUND METHOD………………………………………..6

2.1 Branch and Edge Method Algorithmc…………………………………....10

CONCLUSION……………………………………………………….14

BIBLIOGRAPHY…………………………………………………….15

INTRODUCTION

The branch and bound method was first proposed by Land and Doig in 1960 to solve a general integer linear programming problem. Interest in this method and, in fact, its “rebirth” is associated with the work of Little, Murthy, Sweeney and Carell on the traveling salesman problem. Since then, a large number of works have appeared devoted to the branch and bound method and its various modifications. Such great success is explained by the fact that the authors were the first to pay attention to the breadth of possibilities of the method, noted the importance of using the specifics of the problem, and themselves took advantage of the specifics of the traveling salesman problem.

The branch and bound method is based on the idea of sequentially partitioning the set of feasible solutions into subsets (the “divide and conquer” strategy). At each step of the method, the partition elements are checked to determine whether a given subset contains optimal solution or not. Verification is carried out by calculating a lower estimate for the objective function on a given subset. If the lower estimate is not less than record- the best solution found, then the subset can be discarded. The checked subset can also be discarded if the best solution can be found in it. If the value of the objective function on the found solution is less than the record, then the record changes. At the end of the algorithm, the record is the result of its work.

If it is possible to discard all elements of the partition, then the record is the optimal solution to the problem. Otherwise, the most promising one is selected from the non-discarded subsets (for example, with the lowest lower bound value), and it is split. New subsets are checked again, etc.

1. BRANCH AND BOUND METHOD OF INTEGER PROGRAMMING. BASIC CONCEPTS

Integer (sometimes also called discrete) programming is a branch of mathematical programming that studies extremal problems in which the integer condition is imposed on the desired variables, and the range of feasible solutions is finite.

Great amount economic tasks is discrete, most often integer in nature, which is usually associated with the physical indivisibility of many elements of the calculation: for example, you cannot build two and a half factories, buy one and a half cars, etc. In some cases, such problems are solved by conventional methods, for example, the simplex method , followed by rounding to whole numbers.

However, this approach is justified when a single unit represents a very small part of the total volume (for example, inventory); otherwise, it may introduce significant distortions into the truly optimal solution. Therefore, special methods have been developed for solving integer problems.

1. Reduce the number of integer variables as much as possible. For example, integer variables whose values must be at least 20 can be treated as continuous.

2. Unlike general LP problems, adding new constraints, especially those involving integer variables, usually reduces the time needed to solve CPU problems.

3. If there is no urgent need to find the exact optimal integer solution that differs from the continuous solution, for example, 3%. Then the implementation of the branch and bound method for the maximization problem can be completed if the ratio of the difference between the upper and lower bounds to the upper bound is less than 0.03.

The branch and bound method can be used to solve nonlinear programming problems.

2. BRANCH AND BOUND METHOD

One of the widely used methods for solving integer problems is the branch and bound method, which can be used both for linear programming problems and for problems that are not reducible to linear programming problems. Let's consider the idea of the branch and bound method using the example of a general discrete programming problem

f(X) -> max,

Х€D,

where D is a finite set.

First, we find the estimate £(D) (boundary) of the function f(X), X е D: f(X) ≤ £(D) for V X е D. If for some plan X° of the problem the equality f(X0) = £(D ), then X° = X* is a solution to the problem. If the specified condition is not met, then it is possible to partition (branch) the set D into a finite number of disjoint subsets D1i: ỤD1i. = D, ∩D1i = Ө, and calculation of the estimate £(D1i) (boundaries), 1≤i≤m (Figure 2.1)

Figure 2. 1

If for some plan X1i е Di1, 1 ≤ / ≤ m the condition f(Xkl)= £(D1k)≥ £(D1i), 1≤i≤m is satisfied then Xk1=X* is the optimal plan (solution) of problem (7.9) -(7.10).

If there is no such plan, then the subset Dkl with the highest estimate £(D1i) is selected and divided into a finite number of disjoint subsets D2kj: UD2kj=D1k, ∩D2kj=Ө. For each subset the estimate £(D2kj), 1≤j≤n is found (Figure 2.2)

Figure 2.2

If in this case there is a plan X2j е D2kJ, 1 ≤j ≤n, such that f(X2r)= £(D2kr)≥ £(D2kj), 1≤j≤n, then X2r= X* is a solution to the problem. If there is no such plan, then the branching procedure is carried out for the set D2kj with the highest estimate £(D2kj) , 1≤j≤n. The branching method is determined by the specifics of a particular task.

Let's consider a problem that can be reduced to an integer linear programming problem.

Example.

A container with a volume of 5 m3 is placed on a container ship with a carrying capacity of 12 tons. The container must be filled with two types of cargo. Mass of a cargo unit mj (in tons), volume of a cargo unit Vj (in m3), cost Cj (in conventional monetary units) are given in Table 2.1.

Table 2.1

Type of cargo			C j

It is required to load the container in such a way that the cost of the transported cargo is maximum.

Solution. Mathematical model the problem has the form

Z(X) = 10x1+12x2→max,

3x1+x2≤12,

x1+2x2≤5

x1≥0

x2≥0

x1, x2 are integers

where x1, x2 are the number of units of the first and second loads, respectively.

We denote the set of plans for this problem by D - this is the set of integer points of the OABC polyhedron (Figure 2.3).

Figure 2.3

First, we solve the problem without the integer condition and obtain an estimate of the set D - the value of the function Z(X) on the optimal plan X° = (19/5, 3/5).

Point X is not the optimal plan for the problem. Therefore, in accordance with the branch and bound method, it is required to split the set D into disjoint subsets. Let's choose the first non-integer variable x1=19/5=34/5 and divide the set D into two disjoint subsets D11 and D22. Lines x1=3 (L3) and x4= (L3) are partition lines.

Figure 2.4

Let us find estimates for £(D11) and £(D12), for which we solve linear programming problems.

Z(X)=10x1+12x2→max,

3x1+x2≤12

x1+2x2≤5

x1≤3

x1≥0, x2 – integers

Z(X)=10x1+12x2→max,

3x1+ x2≤12

x1+2x2≤5

x1≥4

x1≥0, x2 – integers

For example, using the graphical method:

X11eD11→X01= (3,1); £(D11)=42; X12eD12→X02= (4,0); £(D12)=40.

The branching result is shown in Figure 2.5

Figure 2.5

Plan X01 satisfies the conditions of the problem, and the following condition is satisfied for it: Z(X11)= £(D11)=42 > £(/)/) = 42 > £(D12) = 40. Therefore, plan X°1= (3, 1) is a solution to problem (7.11)-(7.13), i.e., you need to take three units of the first load and one unit of the second load.

2.1 Branch and Bound Algorithm

· We find a solution to a linear programming problem without taking integer into account.

· Creates additional restrictions on the fractional component of the plan.

· We find solutions to two problems with restrictions on the component.

· If necessary, we construct additional restrictions, according to the possible four cases, we obtain an optimal integer plan or establish the unsolvability of the problem.

Algorithm for the branch and bound method

Initially, we find, for example, using the simplex method the optimal plan of the problem without taking into account the integer number of variables. Let it be plan X0. If there are no fractional numbers among the components of this plan, then the desired solution to this problem has been found and Fmax = F(X0).

If among the components of plan X0 there are fractional numbers, then X0 does not satisfy the integer condition and it is necessary to carry out an orderly transition to new plans until a solution to the problem is found. Let us show how this can be done, first noting that F(X0) ³ F(X) for any subsequent plan X due to an increase in the number of restrictions.

Assuming that the found optimal plan X0 does not satisfy the condition of integer variables, we thereby assume that among its components there are fractional numbers. Let, for example, the variable take on a fractional value in terms of X0. Then, in the optimal integer plan, its value will be at least either less than or equal to the nearest smaller integer, or greater than or equal to the nearest larger integer font-size:14.0pt">font-size:14.0pt">Find a solution to linear programming problems ( 5) and (6). Obviously, one of the following four cases is possible here:

1. One of the problems is unsolvable, and the other has an integer optimal plan. Then this plan and the value of the objective function on it provide the solution to the original problem.

2. One of the problems is unsolvable, and the other has an optimal plan, among the components of which are fractional numbers. Then we consider the second problem and in its optimal plan we select one of the components, the value of which is equal to a fractional number, and we construct two problems similar to problems (5) and (6).

3. Both problems are solvable. One of the problems has an optimal integer plan, and the other problem's optimal plan has fractional numbers. Then we calculate the values of the objective function on these plans and compare them with each other.

3.1. If on an integer optimal plan the value of the objective function is greater than or equal to its value on the plan, among the components of which there are fractional numbers, then this integer plan is optimal for the original problem and it, together with the value of the objective function on it, gives the desired solution.

3.2. If the value of the objective function is greater in the plan, among the components of which there are fractional numbers, then one of these numbers should be taken and for the problem whose plan is being considered, it is necessary to construct two problems similar to (5) and (6).

4. Both problems are solvable, and the optimal plans for both problems include fractional numbers. Then we calculate the value of the objective function on these optimal plans and consider the problem for which the value of the objective function is the largest. In the optimal plan for this problem, we select one of the components, the value of which is a fractional number, and construct two problems similar to (5) and (6).

General algorithm for solving problems using the boundary and branch method, its essence

Thus, the iterative process described above can be represented in the form of a tree on which the initial vertex corresponds to the optimal plan X0, and each vertex connected to it by a branch corresponds to the optimal plans of problems (5) and (6). Each of these vertices has its own branches. In this case, at each step, the vertex for which the function value is the largest is selected. If at some step a plan is obtained that has integer components, and the value of the function on it turns out to be greater than or equal to the value of the function at other vertices possible for branching, then this plan is the optimal plan for the original integer programming problem and the value of the objective function on it is maximum .

So, the process of finding a solution to an integer programming problem using the branch and bound method includes the following main steps:

1. Find a solution to a linear programming problem.

2. Create additional restrictions for one of the variables, the value of which in the optimal plan is a fractional number.

3. Find a solution to problems (5) and (6), which are obtained from problem (1)-(3) as a result of adding additional restrictions.

4. If necessary, create additional restrictions for a variable whose value is fractional, formulate problems similar to problems (5) and (6), and find their solution.

The iterative process is continued until a vertex is found that corresponds to the integer plan of problem (1)-(4) and such that the value of the function at this vertex is greater than or equal to the value of the function at other vertices possible for branching.

The branch and bound method described above has a simpler logical calculation scheme than the Gomori method. Therefore, in most cases, this method is used to find solutions to specific integer programming problems using a computer.

Example of using the branch and bound method

As an example of the branch and bound method, consider the function z=4x1+x2+1®max under the restrictions:

font-size:14.0pt">Let X0 = (0; 0), z0 = 1 - the “optimal” solution. Let’s complete the 1st stage general algorithm and find using the simplex method, and then dual simplex method(see Appendix 1) X1, based on restrictions So, X1 = (3; 0.5; 0; 1; 0; 2.5), z1 = 13.5. Since z1 is fractional, plan X0 remains “optimal”,

According to point 2 of our plan, we will create 2 new systems of restrictions for:

https://pandia.ru/text/79/453/images/image012_25.gif" alt="Description: http://*****/images/paper/93/79/4327993.png" width="108" height="98"> . !}

Let's carry out the 3rd point of the algorithm. To begin with, let's solve the problem using table processor Microsoft Excel (Appendix 2) and we get X2 = (2; 1) z2= 10. Since z2 ≥ z0, plan X0 becomes “optimal”.

Let's solve the problem. From the last equation it is obvious that x2 = 0. It follows that x1 = 3 (the maximum possible). Then X3 = (3; 0), z3 = 13, and therefore this plan is optimal (now without quotes).

We did not have to perform the 4th point of our algorithm due to the fact that the optimal solution was found, the variables are integer. An example in which things are not so simple is given in Appendix 3.

CONCLUSION

This paper examined the essence of integer programming. Special methods for solving integer problems are touched upon. Such problems arise when modeling a variety of production, economic, technical, military and other situations. At the same time, a number of problems in mathematics itself can be formulated as integer extremal problems.

Problems of this type are very relevant, since their solution involves analyzing various situations that arise in economics, technology, military affairs and other fields. These problems are also interesting from a mathematical point of view. With the advent of computers and the growth of their productivity, interest in problems of this type and in mathematics in general increased.

BIBLIOGRAPHY

1. A. Schreiver. Theory of linear and integer programming: in 2 volumes.; translation from English. 1991 360s.

2. T. Hu. Integer programming and flows in networks.; translation from English. 1974

3. , . Higher mathematics: Mathematical programming. The Apprentice - 2nd edition. 2001 351s.

4. . Mathematical programming: Tutorial- 5th edition, stereotype-M: FISMAT, 2001 - 264 p.

5. , .: Economic-mathematical methods and applied models: Textbook. manual for universities/UNITI, 1999 - 391 p.

6. , ; edited by Prof. . : Operations Research in Economics; textbook A manual for universities.

Appendix 2

Solution of the problem z = 4x1 + x2 +1 ® max under the restrictions:

using a table processor Microsoft Excel.