Models of integer linear programming, Statement of the integer...

Models of integer linear programming

Statement of the integer programming problem

In terms of a significant part of economic problems related to linear programming problems, the solution components must be expressed in integers, i.e. be integer. These include, for example, tasks in which variables mean the number of units of indivisible products, the number of machines for loading equipment, the number of ships in line distributions, the number of turbines in the power system, the number of computers in the control complex, and many others.

The problem of linear integer programming is formulated as follows: find such a solution (plan) i, linear function

(8.1)

takes a maximum or minimum value under constraints

(8.2)

(8.3)

are integers. (8.4)

It should be noted that the classic transport task and some other transport-type tasks "automatically" provide the solution of the problem in integers (if, of course, the parameters of the conditions are integral). However, in the general case, the integer condition (8.4) added to the ordinary problems of linear programming significantly complicates its solution.

A number of methods are used to solve the problems of linear integer programming. The simplest of them is the usual method of linear programming. If the components of the optimal solution turn out to be non-integer, they are rounded to the nearest integers. This method is used when the individual unit of the population constitutes a small part of the volume of the whole population. Otherwise, rounding can lead to a far from optimal integer solution, therefore use specially developed methods.

The methods of integer optimization can be divided into three main groups: a) clipping methods; b) combinatorial methods; c) approximate methods. Let us dwell in more detail on clipping methods.

Clipping methods. The Homori Method

The essence of the clipping methods is that first the problem is solved without the integer condition. If the resulting plan is integer, the problem is solved. Otherwise, a new restriction is added to the constraints of the task, having the following properties:

it must be linear;

should cut the found optimal non-integer plan;

• Do not cut off any integer plan.

An additional constraint with the specified properties is called correct clipping .

Next, the problem is solved taking into account the new constraint. Then, if necessary, one more restriction is added, etc.

Geometrically, the addition of each linear constraint corresponds to the implementation of a straight line (hyperplane), which cuts off some of the polygon (polyhedron) of solutions together with the optimal point with non-integer coordinates, but does not affect any of the integer points of this polyhedron. As a result, the new decision polytope contains all integer points that are contained

Fig. 8.1

in the original polyhedron of solutions, and the optimal solution obtained for this polyhedron will be an integer-valued solution (Figure 8.1).

One of the algorithms for solving the linear integer programming problem (8.1) - (8.4), proposed by R. Gomori, is based on the simplex method and uses a fairly simple method of constructing the correct clipping.

Suppose that the linear programming problem (8.1) - (8.3) has a finite optimum, and at the last step of its solution the following equations are obtained by the simplex method, expressing the main variables through the non-primary variables the optimal solution:

(8.5)

so that the optimal solution of the problem (8.1) - (8.3) is i, in which, for example, β; Is not an integral component. In this case, we can prove that the inequality formed by the i - equation of the system (8.5) has all the proper cut-off properties.

The following algorithm is used to solve the integer linear programming problem (8.1) - (8.4) by Gomory's method.

1. By the simplex method, solve the problem (8.1) - (8.3) without taking into account the integrability condition. If all the components of the optimal plan are integers, then it is optimal for the integer programming problem (8.1) - (8.4). If the first problem (8.1) - (8.3) is unsolvable (that is, nc has a finite optimum or its conditions are contradictory), then the second problem (8.1) - (8.4) is also unsolvable.

2. If there are noninteger components among the components of the optimal solution, then choose the component with the largest integer part and form the correct clipping (8.6) with respect to the corresponding equation of system (8.5).

3. Inequality (8.6) is transformed into an equivalent equation by introducing an additional nonnegative integer variable and included in the constraint system (8.2).

4. The extended problem can be solved by the simplex method. If the optimal plan is found to be integer, then the integer programming problem (8.1) - (8.4) is solved. Otherwise, return to step 2 of the algorithm.

If the problem is solvable in integers, then after a finite number of steps (iterations) the optimal integer plan will be found.

! 1 In the inequality (8.6) there is a symbol {}, which means the fractional part of the number. The integer part of the number a is the largest integer [b] that does not exceed a, the fractional part of the number is the number {a}, equal to the difference between this number and its integer part, t .e. {a} = a- [c].

For example, for (note, it's -3, not -2) and

(8.6)

(8.7)

If an equation appears in the solution process (expressing the main variable through non-core variables) with a non-integer free term and with integer remaining coefficients, then the corresponding equation has no solution in integers. In this case, the given problem does not have an integer optimal solution.

!!! 8.1. For the purchase of equipment for sorting grain, the farmer allocates 34 den. units The equipment should be placed on an area not exceeding 60 square meters. The farmer can order two types of equipment: less powerful machines of the type A at a cost of 3 den. units, requiring a production area of ​​3 square meters. m (including passes), and productivity per shift of 2 tons of grain, and more powerful machines of the type B at a cost of 4 den. units, covering an area of ​​5 square meters. m, and productivity per shift of 3 tons of grain.

It is required to draw up an optimal plan for acquiring equipment that provides the maximum overall productivity, provided that the farmer can purchase no more than 8 machines of the type В.

Solution. Denote by the number of machines, respectively, of the type A and B, through Z - the overall performance. Then the mathematical model of the problem takes the form

(!!! 8.8)

under constraints:

(8.2)

(8.3)

are integers. (8.4)

We reduce the problem to the canonical form by introducing additional non-negative variables . We obtain a system of constraints:

(8.5)

We solve the problem by the simplex method. For clarity, the solution is illustrated graphically (Figure 8.2).

Fig. 8.2

In Fig. 8.2 OKLM is the domain of admissible solutions of problem (8.Γ) - (8.3 '), bounded by straight lines (1), (2), (3) and coordinate axes; L (2/3; 8) is the point of the optimal but non-integer solution of the problem (8.1 ') - (8.3'); (4) is a straight line that cuts off this non-integer solution; OKNM is the domain of admissible solutions of the extended problem (8.1 ') - (8.3'), (8.6 '); N ( 2; 7) is the point of the optimal integer solution.

I step. Main variables Non-basic variables

The first basic solution - Permission

Mine. The corresponding value of the linear function

We translate the variable into the main variables, which is included in the expression of the linear function with the largest positive coefficient. We find the maximum possible value of the variable , which "allows

adopt a system of constraints, from the condition of a minimum of the corresponding relations:

i.e. the third equation is the resolving one. x = 0, and the non-primary variable x 5 .

II step. Basic variables x 2 , x 3 , x 4 .

Non-basic variables .z, xy

After the transformations, we get

We translate into the main variable and into non-main x4.

Step III. Basic variables x, x 2 , x 3 .

Non-basic variables x4, x5.

After the transformations, we get

The basic solution X., is optimal for the problem (8.1 ') - (8.3') (), so as in the expression for a linear function

there are no non-basic variables with positive coefficients.

However, the solution X 3 does not satisfy the integer-valuedness condition (8.4 '). By the first equation with variable x, obtained non-integer value in the optimal solution (2/3), we make an additional constraint (8.6):

We draw attention to the fact that, according to (8.5) and (8.6), we take the fractional part of the free term with the same sign that it has in the equation, and the fractional parts of the coefficients for the non-basic variables x 4 and x- - with opposite signs.

Since the fractional parts ,

, the last inequality is written

in the form

(8.6 ')

Introducing an additional integer variable x6 0, we obtain the equation

, which is equivalent to (8.6 ')

(8.7 ')

Equation (8.7 ') must be included in the constraint system (8.5') of the original canonical problem, after which we repeat the process of solving the problem by the simplex method with respect to the extended problem. In order to reduce the number of steps (iterations), it is recommended to introduce an additional equation (8.7 ') into the system obtained at the last step of the solution of the problem (without the integer condition).

Step IV. Basic variables x v x 2, x3, xβ.

Non-basic variables x4, x5.

Basic decision - not allowed

Mine. (Note that once the additional equation corresponding to the correct clipping is included in the system, an unacceptable basic solution will always be obtained.)

In order to obtain an acceptable basic solution, it is necessary to translate into the main variable that enters with a positive coefficient into the equation in which the negative term is negative, i.e. x, or x. (at this stage we do not consider a linear function). We translate into basic, for example, variable x5.

V step. The main variables are x1, x2, x3, x5.

Non-basic variables x4, x6.

We get after the transformations

Since there are no basic variables with positive coefficients in the expression for a linear function, then X 5 is the optimal solution.

So, Zmax = 25 for the optimal integer solution X * = X 5 = (2; 7; 19; 0; 1; 0); the maximum productivity of 25 tons of grain per shift can be obtained by purchasing 2 machines of the type L and 7 machines of the type В while the unoccupied space of the premises will be 19 square meters. m, the cash balances from the allocated are zero, in the reserve for purchase - 1 machine of the type B (the sixth component has no meaningful meaning).

Remark. For the geometrical interpretation on the plane Ox, x2 (see Figure 8.2) of the clipping (8.6 '), it is necessary to express the variables x 4 and x - entering into it through the variables x, and x2. We obtain (see the second and third equations of the constraint system (8.5 '))

(see cutting off the straight line (4) in Figure 8.2). ►

8.2. There are a fairly large number of logs with a length of 3 m. Logs should be sawn into two types of billets: 1.2 and 0.9 m long, with blanks of each type to be obtained not less than 50 and 81 pieces. respectively. Each log can be sawn to the indicated blanks in several ways: 1) 2 blanks but 1.2 m; 2) 1 workpiece 1.2 m and 2 workpieces of 0.9 m each; 3) for 3 blanks of 0.9 m. Find the number of logs sawed in each way so that blanks of any kind are obtained from the smallest number of logs.

Solution. Let's denote by x {} x2, x3 the number of logs being sawed in 1, 2 and 3 ways, respectively. From them it is possible to obtain 2xj + x2 billets of 1.2 m and 2x x + 3x2 billets of 0.9 m. The total number of logs will be denoted Z. Then the mathematical model of the task will take view

(8.1 )

under constraints:

(8.2 )

(8.3 )

are integers. (8.4 )

By entering the additional variables with

we carry the system of inequalities to the equivalent system of equations:

(8.5 )

Solving the canonical problem obtained (without the integral condition) by the simplex method, at the last, III, step of the solution, we find the following expressions for the main variables and the linear function through the non-primary variables (we recommend students to obtain them independently).

Step III. Basic variables x v x 2.

Non-basic variables x y x A , x 5.

ie with the optimal solution

It turned out that the two components of the optimal solution do not satisfy the integer condition (8.4 "), and the large integral part has the component x 2. In accordance with Π. 2 of the algorithm for solving the integer programming problem (see page 166) for the second equation containing this variable x 2, we compose an additional constraint (8.6):

Find the fractional parts

and write the last inequality as

(8.6 )

By entering the additional variable we get

Equivalent to the inequality (8.6):

(8.7 )

We will express the additional variable x6 from (8.7) and introduce the resulting equation into the constraint system that we had at the last, III, step of the solution of the problem (8.1) - (8.3) (without the integer condition).

Step IV. The main variables are x (, x y x 6.

Non-basic variables x 3, x4, x 5.

Solving this expanded problem with a simplex method (we suggest that students do it themselves), we get the following.

V step. The main variables are x); x 2, x3.

Non-basic variables x4, x5, xb.

ie with the optimal solution

The resulting optimal solution of the extended problem (8.1) - (8.3), (8.6) does not again satisfy the integer condition (8.4). By the first equation with variable Xj, which received an integer value in the optimal

solution (), we provide the second additional constraint

(8.6):

which leads to the form

Using the additional variable privo

dim this inequality to the equivalent equation, which we include in the system of constraints obtained at the last, V, step of the solution of the extended problem (8.Γ ') - (8.3), (8.6) by the simplex method.

Step VI. The main variables are x v x 2 , x y x m

Non-basic variables x 4 , X-, x 6.

Omitting the further solution of the problem by the simplex method (we suggest that students do this themselves), at the final, VII, step, we get.

Step VII. The main variables are x v x m x3, x r

Non-basic variables x v x 6 , x m

ie with

Since there are no non-basic variables with negative coefficients in the linear function expression, then X 7 - is the optimal integer solution of the original problem.

Attention is drawn to the fact that in the obtained expression of the linear function Z there are no non-basic variables x D) and x 6. This means that, generally speaking, there exists an infinite set of optimal solutions (any, not necessarily integer) for which Z '= Zmjn = 46. These solutions are obtained for a non-main variable x 7 (included in expression for Z) equal to zero (i.e., for x 7 = 0), and for any the values ​​of the non-main variables x5 and x 6 ( not included in the expression for Z), which allows adopt the constraint system: 0 x 5 1 and 0 & lt; x (i ≤ 1. But by virtue of the integer condition, the variables x - and x (& gt; can only take values ​​0 or 1. Therefore, the problem will have four integer optimal solutions when x. and * 6 in any combination take the values ​​0 or 1, and x 7 = 0. Substituting these values ​​in the system of constraints at step VII, we find these optimal solutions:

The presence of alternative optimal integer solutions allows one to choose one of them, guided by additional criteria that are not taken into account in the mathematical model of the problem. For example, from the condition of the given problem it follows that sawing logs does not give waste only in the third way, so it is natural to give preference to the solution X ^ 3 when choosing one of the four optimal solutions, at which the maximum number of logs ( x 2 = 41) is sawed without waste.

Thus, Zmin = 46 for optimal integer solutions (5; 41; 0), (6; 39; 1); (7; 36; 3); (6; 38; 2). When writing the optimal solutions, we left only the first three components, expressing the number of logs, sawed in 1, 2 and 3 ways, respectively, and eliminated the last four components that do not have a semantic meaning. ►

The disadvantage of the Gomori method is the requirement of integer for all variables - both basic (expressing, for example, in the task of using unit resources), and additional (expressing the amount of unused resources, which can be fractional).

< center>

Also We Can Offer!

Other services that we offer

If you don’t see the necessary subject, paper type, or topic in our list of available services and examples, don’t worry! We have a number of other academic disciplines to suit the needs of anyone who visits this website looking for help.

How to ...

We made your life easier with putting together a big number of articles and guidelines on how to plan and write different types of assignments (Essay, Research Paper, Dissertation etc)