The Gomori constraint has the following form. Drawing up an additional constraint (Gomori section)

Gomori's method for solving integer programming problems is cut-off method .

The essence of the method is to construct restrictions that cut off non-integer solutions to the problem linear programming, but not cutting off any integer plan. To do this, first decide weakened task linear programming without taking into account the condition of integer variables.

If received the solution of the problem linear programming is integer, then the problem integer programming is also solved and the solution found is optimal for it too. If in the found solution of the linear programming problem there is one or larger number variables are not integer, then to find an integer solution to the problem, a new linear constraint is added, which cuts off non-integer solutions. When continuing to solve the extended problem with the dual simplex method taking this constraint into account, an integer plan is obtained.

To find an integer solution to the problem using the Gomori method, the following algorithm is used.

It should be linear;

Should cut off the found optimal non-integer plan;

Should not truncate any integer plan.

If there are several non-integer basis variables, then to create a constraint we select a component of the optimal plan with the largest fractional part (if there are several such variables, then select any one).

This variable corresponds to a simplex table row called line that performs the cut (generating line ).

To present the method, we introduce the following concepts. Let a– real number.

Under whole part some number A is understood as the maximum integer [ a], not exceeding this.

Under fractional part some number A means the smallest non-negative number
such that the difference between it and A There is [ a] – whole part numbers).

For the selected basis variable with the largest fractional part we find fractional part
this variable and the fractional parts of all coefficients for the variables i th line of the system of restrictions
(producing line).

Let's denote
And
whole parts of numbers And . Fractional values
And
(
) are defined as follows

To do this, an equation is written down from the generating row of the simplex table, assuming that the first m variables are basic for a given optimal plan

or

We move all the integer parts of the coefficients in one direction, leaving all the fractional parts in the other:

Because
<1, то заменяя в правой части
, we obtain the strict inequality

Since the left side of the inequality must take integer values, therefore, the necessary condition for its integerity can only be written in the following form:

The inequality is converted into an equation by introducing an additional non-negative variable and included in the optimal simplex table.

We solve the problem using the dual simplex method. If the new optimal plan for the extended problem is integer, then the problem is solved. If the solution is non-integer, then you need to repeat the Gomori method algorithm until an integer solution is obtained.

Example. Using the Gomori method, find a solution to an integer programming problem consisting of determining the maximum value of a function
given that

Solution. Leveling Inequalities Using Auxiliary Variables X 3 , X 4, we obtain the linear programming problem in canonical form:

We solve the linear programming problem using the simplex method, using a step-by-step transition from one basis to another. The progress of solving the problem and the resulting optimal solution are presented in the tables.

In the found optimal plan, the value of the variable X 2 is equal to a fractional number. We find its fractional part and the fractional parts of all elements of the line containing the variable X 2, namely:

Now we compose the Gomori inequality for the found values ​​of the fractional parts:

.

X 5, we move the free term of the equation to the right side and get a new constraint:

.

We add a row containing a new constraint and a column containing a new variable to the simplex table, and continue to solve the problem using the dual simplex method, since the pseudoplan is now written in the table.

The resulting optimal solution to the extended problem contains a non-integer value of the variable X 1, so we find for this line the fractional parts of all non-integer numbers, namely:

and the new Gomory inequality has the form:

We equalize Gomori's inequality using a new auxiliary variable X 6, we move the free term of the equation to the right side and get a new constraint:
.

We add it to the problem being solved, align it using an auxiliary variable and solve the extended problem

Thus, the optimal solution to the integer programming problem has been found: Z max=11 at
.

Notes :

If in the process of solving simplex table an equation with a non-integer component will appear and integer coefficients in the corresponding line of the system of restrictions
, then this problem does not have an integer solution.

Introduction

A large class of applied optimization problems reduces to integer linear programming problems. To solve these problems, cutting methods are widely used, designed to solve a general integer problem, matching it with some non-integer problem, the solution of which allows one to find a solution.

The first method for solving an integer linear programming problem by pruning was proposed by Gomori and was called the Gomori algorithm.

1. Statement of the problem

The Gomori method is designed for solving integer linear programming problems. When considering the Gomori method, we will solve this problem in canonical form.

1.1 Canonical form

We will consider the canonical integer programming problem with n variables and m conditions, supplemented by the integer condition:

Where c = (c 1 , c 2 , … , c n), x = (x 1 , x 2 , … , x n)- dimension vector n, - their scalar product (), also called the objective function, A- dimension matrix n´ m, b- dimension column vector m.

The integer condition significantly complicates the linear programming problem (1.1), (1.2). It may happen that problem (1.1)-(1.3) has admissible (integer) plans, the objective function is limited on the admissible set, but its maximum is not achieved. For example in the task:

there are no integer solutions, while without this condition any vector of the form can serve as a solution

.

In connection with the above, when justifying numerical algorithms for solving problems of type (1.1)-(1.3), it is necessary to impose various additional conditions. We assume that the set X plans of problem (1.1), (1.2) (without the integer condition) is bounded, that is, it is a polyhedron.

From this condition it follows that the set X* all integer plans of problem (1.1)-(1.3) are finite.. We will assume that all coefficients c j, j=1, 2 , …, n, target functions are integers.

From condition II it follows that for any integer plan xÎ X* meaning<c, x>maximizable linear shape- an integer. In this case we say that integerity is guaranteed objective function.

Although conditions I and II for problem (1.1) - (1.3) are quite strict, it is possible to weaken them only slightly to obtain the necessary results.

1.2 Reduction to canonical form

The problem of integer linear programming can be formulated somewhat differently than it was given above. So, for example, instead of condition (1.2), there may be another form of writing restrictions

We can move from such a notation to (1.2) by adding one new variable to each equation, then the restrictions will take the form

The added variables will have zero weight in the target function.

Note that to obtain, depending on the type of inequality, one should not only add, but also subtract a variable depending on the sign of the inequality, taking into account condition (1.3).

If in the original problem not for some variable x i the positivity condition is not met, then it should be replaced by the difference of two new, positive variables.

2. General ideas of clipping methods

There is a fundamental possibility of reducing the solution of problem (1.1) - (1.3) to finding the optimal plan for some linear programming problem (without the condition that the variables are integer). Let X- a polyhedral set defined by conditions (1.1), (1.2). Through X* denote the set of all integer vectors x*, lying in X. In other words X* is given by conditions (1.1)-(1.3), i.e.

A-priory X*Í X. We will denote by X z convex hull of the set X*. Then X zÍ X.

Thus, we have associated with the polyhedral set X some convex set X zÍ X according to the following rule: X z is the minimal convex set containing all integer vectors from X.

According to Assumption I, X is a polyhedron, hence the set X* Certainly. Then the convex set X z is also a polyhedron, and therefore we have that X z can be specified by a finite number of linear inequalities.

To highlight the main difference between the set X z from many X, let us give the following definition.

Definition 1. A polyhedron all of whose extreme points are integers (that is, all their coordinates are integers) is called an integer polyhedron.

Obviously, the polyhedron X z- integer, since its extreme points are only points of the set X* integer plans.

Justification for studying compliance X® X z is the following simple fact.

Theorem 1. Any optimal reference plan for a linear programming problem is a solution to problem (1.1)-(1.3).

Proof. Let` x*- optimal reference plan of the problem (2.1), x*- some solution to the original problem (1.1)-(1.3). ` x*Î X zÍ X, That

<c,`x*> £ <c, x*>.

On the other hand, since x* is an integer plan, then x*Î X*Í X z, and therefore

<c,`x*> ³ <c, x*>,

where

<c,`x*> = <c, x*>.

The proof of the theorem is complete.

We emphasize that Theorem 1 states only the fundamental possibility of reducing the solution of an integer linear programming problem to the search for reference plans of a linear programming problem of the form (2.1). The main difficulty in using this feature is the explicit definition of the polyhedron X z system of linear inequalities in order to then apply numerical methods of linear programming to solve problem (2.1). It is likely that this problem is computationally as difficult as the original problem of finding the optimal integer design.

Despite this, the idea of ​​“narrowing” the set X turned out to be useful and led to the creation of several algorithms for solving integer linear programming problems, called “pruning methods”.

Let us present the idea of ​​pruning methods. Let's assume that we managed to construct the sequence ( Lr}, r = 0, 1 , 2 , ..., linear programming problems, each of which is determined by its own polyhedron X r and one objective function for all<c, x>:

Moreover, this sequence of tasks has the following properties:

) X 0 =X, i.e. as X 0 take the set of plans for problem (1.1), (1.2);

) X r z = X z , r=1,2, …;

) if when solving a problem Lr the resulting optimal vector x r * does not satisfy the integer condition, then it is not a task plan L r+1, i.e. x r *Ï X r+1.

Note that if at some step r vector x r *- the solution of the problem Lr- turns out to be an integer, then it is a solution original problem(1.1)-(1.3) due to property 2) of the sequence Lr.

It is intuitively clear that the sequential construction of tasks Lr, r=1.2,..., gives in a sense an approximation of the set X z with the help of many X r.

Methods for constructing a sequence ( Lr), ensure the finiteness of the process of solving problem (1.1)-(1.3), were first proposed by Gomori.

3. Description of the Gomori method

Let us now consider Gomori's algorithm for solving integer linear programming problems. This method belongs to the cutting methods and implements the ideas outlined in the previous paragraph.

3.1 The concept of correct cutting and the simplest way to construct it

Homer's algorithm linear programming

Let us introduce the correct cutoff, which underlies many numerical methods for solving integer linear programming problems.

Definition 2. Let x* be the optimal plan for problem (1.1), (1.2), which is not an integer. Inequality

where g = (g 1 , g 2 , …, g n), is called a correct cut if it satisfies the requirements:

a) for a vector x* the inequality does not hold, i.e. x*> > g 0 (cut-off condition).

b) if x is the integer plan of problem (1.1), (1.2) (i.e. the plan of problem (1.1)-(1.3)), then x- satisfies (3.1) (correctness condition).

It is clear that adding inequality (3.1) to conditions (1.1), (1.2) narrows the admissible set X, while preserving all of its integer points. Thus, the consistent application of this technique gives a multi-stage approximation of the polyhedron X z using linear constraints.

There are two problems with the concept of proper clipping. The first of these is to formulate general algorithm cuts for an arbitrary integer linear programming problem. The second problem is to construct a correct cutoff in such a way as to ensure the solution of problem (1.1)-(1.3) in a finite number of steps, i.e. so that from the multitude X each time sufficiently large areas were cut off.

Note that the second requirement is quite subtle. As confirmation, consider the method of constructing a correct cutoff proposed by Danzig.

Let x*- supporting optimal plan of problem (1.1), (1.2), s and w - lists of numbers of basic and non-basic variables, respectively, corresponding to some basis of the plan x*. Then x j *= 0 at jÎw. Taking this property into account, it is not difficult to construct a correct cutoff for the design x* if it is not an integer: the inequality can serve as such

Indeed, the cutoff condition is trivially satisfied, since . The correctness condition is also satisfied, since if x = (x 1,x 2 , …,x n) is the integer plan of problem (1.1), (1.2), then the value taking into account the conditions x j ³ 0, jÎ w, can be less than unity only in the case when x j= 0 for all jÎ w. But in that case the plan x- reference, and the plan basis can be taken as its basis x*. The reference plan is uniquely determined by its basis, from which we obtain that the inequality implies x=x *. The latter, however, is impossible, since x is an integer vector, and x* it is not.

This method of constructing a correct cut, despite its simplicity, turned out to be ineffective, since the finiteness of the solution process is ensured only for a narrow class of integer linear programming problems.

Let us describe the method for constructing a correct cutoff proposed by Gomori. For an arbitrary number a, through [ a] we will denote its entire part, i.e. [ a] is the largest integer k non-exceeding number a.

Fractional part ( a) numbers a called the number ( a} = a - [a]. Let us note the obvious property of the fractional part of an arbitrary number: 0 £ ( a}<1, причем {a) = 0 if and only if a - an integer.

Let x*- reference solution of problem (1.1), (1.2), which is not integer, - its basis and B- the corresponding simplex table in coordinate form.

Let us consider the reduced system of equations corresponding to this basis (and the table B) plan

x*:

Because the x j *= 0 at jÎw, then only the quantities can be non-integer x 0 * = <c, x*>, x i *, iÎs.

Let s- such an index (0 £ s £ n) that the number xs*- not whole. Let's consider s th row in a simplex table B (s th equation in system (3.2), (3.3)) and compose the expression

Theorem 2. If xÎ X* is the integer plan of problem (1.1), (1.2), then

Proof. Using the relation

asj = [asj] + {asj }, j = 0, 1, 2, … , n, from (3.3) with i= s we get

where

The left side of this inequality contains an integer, therefore the number

also whole. From what x j ³ 0, jÎw, using the property of the fractional part, we obtain

those. - z s(x) < 1, или z s(x) > -1. Considering that z s(x) - integer, we will finally accept z s(x) ³ 0.

Consequence. If xs*(= as0) - non-integer number and Set X* plans of the integer problem (1.1)-(1.3) are non-empty, then among the numbers ( asj}, j=1, 2, …, n, there are positive ones.

In fact, all numbers ( asj), are obviously non-negative. Let's assume that ( asj} = 0, j = 1, 2, …, n.

If X* non-empty and x* Î X*, That z s(x*)= - {as0), that z s(x*) is an integer, since 0< {as0} < 1.

Comment. In the proof of Theorem 2, we used Assumption II that the objective function is guaranteed to be integer. Valid in case s= 0 value

is integer (provided that xÎ X*) only when the number x 0 = < c, x> - whole.

It follows from this

Theorem 3. If the number xs*- is not an integer, then inequality

is the correct cutoff.

Proof. Let's check the cutoff condition in Definition 2. Since xs* = as0, then from the fact that xs*- is not an integer, we get the inequality ( as0) > 0. Since x j *= 0 at jО w, then

and therefore the vector x* does not satisfy inequality (3.5). The correctness condition follows from the statement z s(x) ³ 0 in Theorem 2.

3.3 Gomory's first algorithm

Let's move on to the presentation of the first Gomori algorithm.

Let us denote problem (1.1), (1.2) by L 0 . Gomori proposed to find the lexicographic maximum of the problem at the first stage of his algorithm L 0 . We will denote by

x(0) = (x 0 (0), x 1 (0), …, x n(0))

(n+1)-dimensional vector such that ( x 1 (0), x 2 (0), …, x n (0)) - solution to the lexicographic problem L 0 , a x 0 (0) = - linear form value. In cases where this does not cause misunderstanding, we will call x(0) - optimal plan for the lexicographic problem L 0 (although according to generally accepted terminology, a plan is a vector composed of the last n vector coordinates x(0)).

Note also that x(0) will be a reference plan, as well as a strictly admissible pseudo-plan of the problem L 0 .

If x(0) is an integer vector, then it is obviously a solution to problem (1.1) - (1.3).

Otherwise, we find the minimum index s, 0 £ s £ n, for which the value xs(0) is not an integer. Let B(0) - simplex table in coordinate form corresponding to the vector x(0). Using coefficients s th row of this table (i.e., the coefficients of the reduced system (3.2), (3.3)), using the technique described above, the correct cutoff is constructed.

An auxiliary variable is introduced x n+1 and the task is considered L 1:

The next stage is to find the lexicographic maximum of the problem L 1 . An important advantage of the Gomori algorithm is the fact that the initial admissible strict pseudo-plan for application dual simplex-method to the problem L 1 is found without difficulty. Indeed, it is easy to see that as such a pseudoplan we can take the vector

In fact, it is obvious that y(1) satisfies (together with vectorform x(0)) restrictions (3.6), (3.7) problems L 1, and only one of the restrictions (3.8) is violated: x n+1 (0)= - (a s 0 } < 0. Кроме того, y(1) is the reference for the system of equations (3.6), (3.7), because if - plan basis x(0) then the system

is linearly independent and serves as a basis for y(1). Let's show that y(1) is a strictly admissible pseudoplan. For this purpose, we will construct a simplex table corresponding to the specified vector basis y(1). To do this, you just need to add below to the table B(0) line

Where w = ( j 1 , j 2 , …, jn -m) - list of numbers of non-basic variables corresponding to the table B(0) reference plan x(0). Because the x(0) is a strictly admissible pseudoplan, then every column b j, jÎw, tables B(0) lexicographically positive: b j > 0, jÎw. It follows from this that in the simplex table in coordinate form corresponding to the support vector y(1), every column (except the first, coinciding with y(1)) is lexicographically positive:

Thus, having at our disposal a solution x(0) lexicographic task L 0 and the corresponding simplex table in coordinate form B(0), without any additional calculations we find the initial strictly admissible pseudoplan y(1) for the task L 1 and construct the corresponding simplex table in coordinate form.

It may happen that the lexicographic task L 1 has no solution. In this case, the solution to the integer problem (1.1) - (1.3) should be stopped since

Theorem 4. If in the problem L 1 there is no lexicographic maximum, then the set X* integer points of problem (1.1) - (1.3) are empty.

Proof. Since many X vectors satisfying the conditions Ax = b, x³ 0, according to assumption I is bounded, then the set of plans for the problem is also bounded L 1 . Therefore, the only reason why this problem may not have a lexicographic minimum is that its set of plans is empty. Let us show that in this case the set X* also empty.

Let's assume the opposite, i.e. What X* ¹ Æ, and let x* = (x 1 * , x 2 * , …, x n*) О X*. By Theorem 2 we find that the quantity

non-negative. But this means that vector = ( x 1 * , x 2 * , …, x n * , x n+1 *) is the task plan L 1, in contradiction with the above. The theorem has been proven.

Let x(1) = (x 0 (1), x 1 (1), …, x n(1), x n+1 (1)) - solution to the lexicographic problem L 1 . Departing from the task L 1 and vector x(1), problems are constructed in a similar way Lr, r= 2, 3, …, and solutions x(r) Î Â n +1+r corresponding lexicographic tasks.

Note that Gomori's algorithm uniquely determines the sequence x(r), r= 0, 1, 2, …, which follows from the uniqueness of the choice s. Let us also pay attention to the fact that the index s always does not exceed n: 0 s n. In fact, if everything x j(r) at j= 0, 1, 2, …, n are integers, then it follows from Theorem 2 that x n +1 (r), x n +2 (r), … - also integers.

If at some step r vector

x(r) = (x 0 (r), x 1 (r), …, x n(r), …, x n +r (r))

turns out to be an integer, then the vector ( x 0 (r), x 1 (r), …, x n(r)) is a solution to problem (1.1) - (1.3). The proof of this statement is obvious.

Transition from vector x(r) to the vector x(r+1) using the described Gomori algorithm is called a large iteration, as opposed to intermediate iterations dual simplex method, which are called small.

The main question related to Gomori's first algorithm is: is it always possible to obtain an integer vector in a finite number of large iterations? x(r).

Let us prove the finiteness of the first Gomory Algorithm. We will use the following notation:

x(0) = (x 0 (0), x 1 (0), …, x n(0));

Where ( x 1 (0), …, x n(0)) is the solution to the lexicographic problem L0, and x(0) = - the corresponding value of the linear form (objective function).

y(1) = (x 0 (0), x 1 (0), …, x n(0), x n +1),

the vector y(1) serves as the initial strictly admissible pseudoplan when solving Problem L1 using the dual simplex method in coordinate form: ` y(1) = (`y 0 (1), `y 1 (1), …, `y n(1), `y n+1 (1)) is the vector resulting from y(1) as a result of the first (small) iteration of the dual simplex method in coordinate form.

The notation is introduced similarly

x(r), y(r + 1), `y(r + 1), r = 1, 2, …

From the properties of the dual simplex method in coordinate form it follows

y(r) >`y(r) ³ x(r).

Lemma 1. Let s- the minimum index for which the number xs(0) is not an integer. Then

Proof. Since from (3.9) it follows y(1) >`y(1), then two cases are possible:

In case 1, the statement of the lemma is satisfied trivially by the definition of lexicographic order.

Consider case 2. According to the rules of the dual simplex method, at the first (small) iteration of solving the problem L 1 variable is subject to derivation from among the basic ones x n+1 because in the vector y(1) x j(0) ³ 0, jО w, x n +1 < 0. Пусть kО w is an index such that

For anyone jО w, if -(a sj} < 0. По правилам симплексного метода в число базисных вводится переменная x k.

Case 2 is possible only under the condition b ik = 0, i = 0, 1, 2, …, s- 1. Because x(0) - strictly admissible pseudo-plan of the task L 0 , then all its columns b j, jО w, simplex table B(0) lexicographically positive; in particular b k> 0 . Therefore, the coordinate b sk of this column must be non-negative. Note that b sk= a sk(i.e. 0 £ s £ n And sО w), by condition (3.10) the number a sk- not zero. That's why

a sk> 0 and a sk³(a sk}

According to the simplex table transformation formula, we have

Remembering that xs(0) = as0, we get:

.

Taking (3.11) into account, we obtain the following estimate:

The lemma is proven.

Comment. If the original problem (1.1) - (1.3) is admissible, then, according to the corollary of Theorem 2, the index k satisfying condition (3.10) exists.

Consequence. Fair ratio

Valid at r= 1, this inequality follows from the lemma and the second inequality (3.9). To obtain this statement for an arbitrary r, you need to take advantage of the fact that y j(r) = x j(r) at 0 £ j £ n, and inequality y(r) ³ x(r) in (3.9).

Theorem 5. If Assumptions I and II are satisfied, then Gomori's first algorithm requires only a finite number of large iterations.

To verify the truth of the theorem, it is necessary to show that for some r vector x(r) = (x 0 (r), x 1 (r), …, x n +r (r)) - integer. To do this, in turn, it is enough to prove the integer nature of the vector ( x 0 (r), x 1 (r), …, x n(r)), since from Theorem 2 it then follows that all numbers x n +1 (r), x n +2 (r), …, x n +r (r) are also whole. Let us also recall that the minimum index s for which the number xs(r) is non-integer always does not exceed n: 0 £ s £ n. Before moving on to the main proof, we prove the following lemma:

Lemma 2. For anyone j, 0 £ j £ n, there is such a number R j, that at r ³ R j all numbers x j(r) - integers and equal to the same integer x j(R j).

Proof. Let s, 0 £ s £ n, - the minimum index for which the statement of the Lemma does not hold. Let's denote

In the case when s= 0, let's put R = 0.

Let r, l- such indices that R £ r£ l, and numbers xs(r), xs(l) - not whole. Let us show that then [ xs(r)] > [xs(l)]. Valid by definition s we have

In this case s- the minimum index for which the number xs(r) - integer. By corollary to Lemma 1 we have [ xs(r)] ³ xs(l).

Considering that xs(l) is not an integer, we have xs(l) > [xs(l)], from which we obtain the desired statement. Since many X plans of problem (1.1) - (1.3) is limited, then any value is limited xs(r), 0 £ s £ n, r= 1, 2, … . Therefore, an infinite chain of inequalities of the form [ xs(r)] > [xs(l)] > ... cannot exist, and, therefore, in the sequence xs(r), r= 0, 1, …, there cannot be an infinite number of non-integer numbers. It is similarly proven that there cannot be infinitely many different integers in this sequence.

The lemma is proven.

Let's return to the proof of the theorem. Let

where are the numbers R j appear in the formulation of Lemma 2. Then, according to this lemma, all numbers x j(R), 0 £ j £ n, - whole. From Theorem 2 we obtain that the vector x(R) - integer. Therefore, Gomory's algorithm requires no more than R iterations.

The theorem has been proven.

3.5 Notes on the practical implementation of the first Gomori algorithm

At practical implementation In the first Gomori algorithm, an important problem is the increase in the number of restrictions, which leads to an increase in the size of simplex tables. Gomori proposed a way to eliminate this drawback of the algorithm, which is as follows.

) During the solution of the problem Lr using the dual simplex method, at each small iteration, you should use a refined rule of inference from the number of basis vectors to solve linear programming problems using the simplex method: if the first column of the simplex table has several negative elements b i 0 (= x i), i =1, 2, …, n, …, n + r, then the variable with the minimum number must be removed from among the basic ones.

) If during the next small iteration when implementing the task Lr all main variables x 1 , x 2 , …, x n turned out to be non-negative, then further application of the dual simplex method to the problem Lr should be stopped, despite the fact that its lexicographic maximum may not yet have been reached. If all the variables x j, j = 1, 2, …, n, turned out to be integer, then by Theorem 2 all auxiliary variables x n +k , k = 1, 2, …, r, are integer and non-negative. This means, as is already known, that the vector ( x 0 , x 1 , x 2 , … , x n) is a solution to the original integer problem. Otherwise, we move on to a new large iteration.

) Simplex table row corresponding to the auxiliary variable x n +r, is removed as soon as the variable x n +r is declared non-basic. Let us recall that this happens at the very first small iteration of solving the problem Lr.

) If in the course of solving the problem Lr variable x n +r again falls into the number of basic ones, then the corresponding row is not restored.

It is clear that when rules 3), 4) are followed, the dimensions of the simplex table in the first Gomori algorithm do not increase - each table contains n+ 2 lines corresponding to the main variables x 0 , x 1 , … , x n and the current auxiliary variable x n +r at the time of its introduction) and n - m+1 columns (since the number n - m non-basic variables does not change).

) At the first small iteration of solving the problem Lr+1 is chosen as the variable derived from the basis x n +r+1, despite the fact that the values ​​of other auxiliary variables at this moment can also be negative.

Note that rule 5) is actually redundant, since when rules 3) and 4) are fulfilled, we know nothing about the value of the remaining variables x n +1 , …, x n +r at the moment of transition to the task Lr +1 . This rule highlighted only to highlight the difference between the algorithms under consideration.

Note that when using rule 2) the resulting sequence x ’ (r) may not be the lexicographic maximum of the problem Lr, since the values ​​of some of the auxiliary variables may be negative.

However, for consistency x ’ (r), r= 0, 1, 2, …, obtained using rules 1) and 2), an important property is preserved: this sequence is unique.

It remains only to prove that when using rules 1) - 4) the Gomori algorithm remains finite, since its finiteness will mean that it leads to the goal - finding an integer solution to problem (1.1) - (1.3). Indeed, the finiteness of the number R large iterations means that the vector x ’ (R) integer.

Let us note, firstly, that when using rule 2) the number of small iterations of solving the problem Lr of course - no more than is required to find its lexicographic maximum.

Theorem 6. The sequence x’(r) arising in the process of applying the Gomori algorithm, the refined rule 1) - 4), is finite.

Proof. Note that in the proof of Theorem 5 on the finiteness of the sequence x(r), only two circumstances were used that regulate the occurrence of this sequence: the method of constructing the correct cut and the fact that in any current simplex table all columns b j, jÎw, are lexicographically positive. Thus, deleting the line corresponding to the auxiliary variable can only affect the latter circumstance. This, however, cannot be the case, as shown in the following lemma.

Lemma 3. In any simplex table arising during the Gomori algorithm, refined by rules 1) - 4), for any column

there is inequality

Proof. Let us assume that the statement of the lemma does not hold for some kО w. Since b k, then this assumption means that

By the definition of a simplex table in coordinate form, we have

For anyone x Î Rn +1+r, if the statement of the lemma is violated during the solution of the problem Lr. Formula (3.13) taking into account (3.12) means that a change in the value of the variable x k does not affect the value x i, i = 0, 1, 2, …, n. In other words, for the same set of values x i, 0£ i£ n, variable x k can take an arbitrary value. It follows, firstly, that k ³ n+ 1, and secondly, that the accepted assumption (3.13) is incorrect, since since the value of any auxiliary variable x k, k ³ n+ 1, as follows from (3.7), is uniquely determined by the values ​​of the main variables.

Because deleting rows corresponding to auxiliary variables does not affect the property of the b columns j, jÎ w, be lexicographically positive, then these lines are not needed at all. Indeed, taking into account rules 1) - 2) variable x n +r, having become one of the basic ones, remains basic until the end of the calculations, and its line is not required to determine the variable introduced into the basis according to the rules of the simplex method.

Thus, the row elements corresponding to the variable x n +r, do not participate in the formulas of the dual simplex method for calculating the values ​​of all other variables.

Since, as noted, the index s regulating the formation of the correct cut-off does not exceed n, 0 £ s £ n, then auxiliary variables are not required for these purposes.

4. Computer implementation

In this course project The program is designed to find a solution to an integer linear programming problem using the Gomori method.

The software module uses the algorithm described in the theoretical part, taking into account comments on practical application method made by Gomori.

Data entry into the program module is made from a file. The results of the program can be output to a file, to a display, or to a printer. Input file format:

…

…

…

…

Where n- number of variables, m- number of restrictions, c 1 , c 2 , … , c n- coefficients of the maximized linear form, a ij- matrix elements A, b j- vector components b. A, b - characterize restrictions [see. (1.2)].

Example input file:

2 5 0 0 0 0 0 0 0

3 1 0 0 0 0 0 0 12

2 5 0 1 0 0 0 0 0 30

3 2 0 0 1 0 0 0 0 22

2 -1 0 0 0 1 0 0 0 12

1 -3 0 0 0 0 1 0 0 0

2 5 0 0 0 0 0 -1 0 10

5 1 0 0 0 0 0 0 -1 5

Bibliography:

1. Abramov L.A., Kapustin V.F. Mathematical programming. - L.: Leningrad State University Publishing House, 1981. -328 p.

Belousova G.S. Linear programming. Tutorial. -Krasnoyarsk: Science, 1975. -107 p.

Kuznetsov Yu.N. and others. Mathematical programming: Textbook. - 2nd ed., revised. and additional -M.: graduate School, 1980. -300 p.

Ashmanov S.A., Linear programming. M.: Science. 1969. -240 s

Gabasov R.I. Kirillova F.M., Methods of linear programming. Minsk: Science. 1977. -174 s

Economic and geometric interpretation of the integer programming problem. An extreme problem whose variables take only integer values ​​is called an integer programming problem.

In the mathematical model of the integer problem programming both the objective function and the functions in the system of constraints can be linear, nonlinear and mixed. Let us restrict ourselves to the case when the objective function and system of constraints of the problem are linear.

Example 20.

It was decided to install additional equipment in the workshop of the enterprise, for which space was allocated. An enterprise can spend 10 thousand rubles on the purchase of equipment, and it can buy two types of equipment. A set of type I equipment costs 1,000 rubles, and type II – 3,000 rubles. The purchase of one set of type I equipment allows you to increase production output per shift by 2 units, and one set of type II equipment – ​​by 4 units. Knowing that installing one set of type I equipment requires 2 m 2 of area, and type II equipment requires 1 m 2 of area, determine such a set of additional equipment that makes it possible to maximize production output

Solution. Let's create a mathematical model of the problem. Let us assume that the enterprise will purchase x 1 sets of equipment of type I and sets of equipment of type II. Then the variables x 1 and must satisfy the following inequalities:

If the enterprise purchases the specified amount of equipment, then the total increase in output will be

According to their economic content, the variables x 1 and can only take non-negative integer values, i.e.

x 1 , – integers. (73)

Thus, we come to the following math problem: find the maximum value linear function(71) when conditions (70), (72), and (73) are met. Since unknowns can only take integer values, problem (70) – (73) is an integer programming problem. Since the number of unknowns in the problem is two, the solution to this problem can be found using its geometric interpretation. To do this, first of all, we will construct a polygon of solutions to the problem consisting of determining the maximum value of the linear function (71) when conditions (70) and (72) are met (Fig. 11). Coordinates of all points of the constructed solution polygon OAEVS satisfy the system of linear inequalities (70) and the condition non-negativity variables (72). At the same time, condition (73), i.e., condition integrity variables are satisfied by the coordinates of only 12 points marked in Fig. 11. To find the point whose coordinates determine the solution to the original problem, replace the polygon OABC polygon OKEMNF, containing all valid points with integer coordinates and such that the coordinates of each of the vertices are integer numbers. This means that if we find the maximum point of function (71) on the polygon OKEMNF, then the coordinates of this point will determine the optimal plan for the problem.

To do this, we will also construct a straight line passing through the solution polygon OKEMNF(the number 12 is taken arbitrarily). We move the constructed line in the direction of the vector until it passes through its last common point with the given polygon. The coordinates of this point determine the optimal plan, and the value of the objective function at it is the maximum.

IN in this case the required point is E(1; 3), in which the objective function takes the maximum value C, therefore, the coordinates of the point E determine the optimal plan for the problem (70) – (73). In accordance with this plan, the enterprise should purchase one set of type 1 equipment and three sets of type II equipment. This will provide the enterprise with its existing restrictions on production space and funds maximum magnification production output equal to 14 units. per shift.

Example 21.

To perform the work can be used P mechanisms. Performance i-th mechanism when executing j – th work is equal to . Assuming that each mechanism can be used only on one job and each job can be performed by only one mechanism, determine the assignment of mechanisms to jobs that ensure maximum productivity. Construct a mathematical model of the problem.

Solution. Let us introduce a variable x ij whose value is equal to 1 if, when executing i-th work used j – th mechanism, and equals 0 otherwise. Then the conditions for using each mechanism on only one job are expressed by the equalities

(74)

and the conditions for performing work by only one mechanism - equalities

(75)

Thus, the task is to determine such values ​​of the unknowns , satisfying systems of equations (74) and (75) and condition (76), under which the maximum value of the function is achieved

The formulated problem is an integer programming problem.

Determining the optimal plan for an integer programming problem. Let us consider integer programming problems in which both the objective function and the functions in the system of constraints are linear. In this regard, we formulate the basic linear programming problem in which variables can only take integer values. In general, this problem can be written as follows: find the maximum of the function

under conditions

(79)

– whole (81)

If you find a solution to problem (78) – (81) using the simplex method, then it may or may not be integer (an example, the solution of which is always integer, is transport problem). In the general case, to determine the optimal plan for problem (78) – (81) special methods are required. Currently, there are several such methods, of which the most famous is Gomori method, which is based on the simplex method described above.

Gomori method. Finding a solution to an integer programming problem using the Gomori method begins with determining the optimal plan of the problem (78) – (80) using the simplex method, without taking into account integrity variables. Once this plan is found, its components are reviewed. If there are no fractional numbers among the components, then the found plan is the optimal plan for the integer programming problem (78) – (81). If in the optimal plan of problem (78) – (80) the variable takes a fractional value, then the inequality is added to the system of equations (79)

(82)

and find a solution to problem (78) – (80), (82).

In inequality (82) and – transformed initial quantities and whose values ​​are taken from the last simplex table, and – fractional parts of numbers (the fractional part of a certain number a is the smallest non-negative number b such that the difference between A And b there is a whole). If in the optimal plan of problem (78) – (80) the fractional values ​​take on several variables, then the additional inequality (82) is determined largest fraction part.

If in the found plan of problem (78) – (80), (82) the variables take fractional values, then one additional constraint is added again and the calculation process is repeated. Carrying out a finite number of iterations, one either obtains the optimal plan for the integer programming problem (78) – (81) or establishes its unsolvability.

If the requirement integrity(81) applies only to some variables, then such problems are called partially integer. Their solution is also found by sequentially solving problems, each of which is obtained from the previous one using the introduction additional restriction. In this case, such a restriction has the form

where are determined from the following relations:

1) for , which can take non-integer values,

(84)

2) for , which can only take integer values,

(85)

From the above it follows that the process of determining the optimal plan for an integer programming problem using the Gomori method includes the following main stages:

1. Using the simplex method, find a solution to problem (78) – (80) without taking into account the requirement integrity variables.

2. Create an additional constraint for the variable, which in the optimal plan of problem (78) – (80) has maximum fractional value, and in the optimal plan, problem (78) – (81) should be integer.

3. Using the dual , find a solution to the problem resulting from problem (78) – (80) as a result of adding an additional constraint.

4. If necessary, create another additional constraint and continue the iterative process until an optimal plan for the problem (78) – (81) is obtained or its unsolvability is established.

Example 22.

Use the Gomori method to find the maximum value of the function

given that

(87)

– whole (89)

Solution. To determine the optimal plan for problem (86) – (89), we first find the optimal plan for problem (86) – (88) (Table 22).

Table 22

		C b	R 0

As can be seen from table. 22, optimal plan found problem (86) – (88) is not an optimal plan for problem (86) – (89), since two components and have non-integer values. Moreover, the fractional parts of these numbers are equal to each other. Therefore, an additional constraint is drawn up for one of these variables. Let us make, for example, such a constraint for the variable From the last simplex table (Table 22) we have

Thus, to the system of constraints of problem (86) – (89) we add the inequality

or

Table 23

		C b	R 0

We now find the maximum value of function (86) when conditions (87), (88) and (90) are met (Table 23).

From Table 23 it can be seen that the original integer programming problem has an optimal plan P In this plan, the value of the objective function is equal to . Let us give a geometric interpretation of the solution to the problem. The region of feasible solutions to problem (86) – (88) is a polygon OABCD(Fig. 12). From Fig. 12 it can be seen that the objective function takes its maximum value at the point WITH(19/2; 7/2), i.e. What X =(19/2; 7/2; 0; 0; 34) is the optimal plan. This is directly evident from Table 22. Since X= (19/2; 7/2; 0; 0; 34) is not the optimal plan for problem (86) – (89) (numbers and are fractional), then an additional constraint is introduced. Excluding from it and substituting instead the corresponding values ​​from the equations of the system of constraints (87), we obtain a cutoff from the polygon OABCD triangle EFC.

As can be seen from Fig. 12, the region of feasible solutions to the resulting problem is a polygon OABEFD. At the point E(9; 4) of this polygon, the objective function of this problem takes the maximum value. Since the coordinates of the point E are integer numbers and unknowns , and take on integer values ​​when substituting the values ​​and into equation (87), then is the optimal plan for problem (86) – (89). This also follows from Table 23.

Example 23.

Using the Gomori method, find a solution to the problem of determining the maximum value of a function

under conditions

- whole. (94)

Give a geometric interpretation of the solution to the problem.

Solution. Let us rewrite the formulated problem as follows: find the maximum value of the function

under conditions

(96)

- whole. (98)

Problem (95) – (98) is partially integer, since the variables and can take non-integer values.

Using the simplex method, we find the solution to problem (95) – (97) (Table 24).

Table 24

		C b	R 0
		C b	R 0
							–1/3 is not a plan for problem (95) – (98), since the variable

In integer programming problems, in contrast to linear programming problems, an additional restriction is introduced on variables: they can only take integer values.

In some problems, for example, transport type, this condition is satisfied automatically if the source data (amounts of goods sent and received) are expressed in integers. But in a general linear programming problem, conventional methods for solving integer values ​​do not guarantee whether the original quantities are integers or fractions.

In mathematical notation common task integer programming looks like this:

maximize

under conditions

x j≥ 0, x j - whole.

Economic linear programming problems most often require an integer solution. This applies to problems in which variables indicate the number of units of indivisible products, equipment, workers (problems of the best distribution of production tasks between enterprises, optimization problems production program individual enterprises, problems of optimal equipment loading, etc.). Often such problems are solved using the usual simplex method with subsequent rounding of the obtained values variables to whole numbers. But in this case, you can only get some approximation to the truly optimal integer plan.

In another group of linear programming problems, the quantities to be determined are the production capacities that most effectively satisfy a given need. Since the “carriers” of production capacity are individual enterprises, indivisible pieces of equipment, etc., these problems also reduce to integer linear programming problems.

Problems of rational cutting of dimensional material (tasks for minimizing waste) are also integer-valued, since the variables in them, as a rule, indicate the number of initial blanks cut in one way or another.

In all mentioned problems a solution can be found conventional methods linear programming with subsequent adjustment and obtaining an integer plan that is more or less close to the optimal one. But there are problems for which a non-integer solution makes no sense. These include choice problems in which the numerical values ​​of variables serve only to determine an alternative (“either-or”, “yes-no”).

Integer selection models include some operational scheduling problems, for example, problems about the optimal sequence of launching various products (parts) into production. Let's say you need to determine the startup order n parts, each of which is sequentially processed on several machines. Variables x ij equal to one if the part j must be run after the part i , and zero - in all other cases. For every fixed j , just like for everyone i , only one of n variables can be equal to one, so the constraints of the problem include the following:

The total processing time of all parts on machines of this group is minimized. A non-integer solution to such a problem makes no sense.

There are several methods for solving integer programming problems. Best known Gomori method, based on the use of the simplex method.

Let's consider mathematical concepts: congruence numbers, whole And fractional part of a number. Number A congruent to number b if and only if the difference a – b is an integer. Congruence is indicated by three horizontal lines ( ≡ ); Thus, A ≡ b , If a – b is an integer.

For example: 5 / 3 ≡ 2 / 3 , because 5 / 3 - 2 / 3 = 1;

- 1 / 3 ≡ 2 / 3 , because - 1 / 3 - 2 / 3 = 1.

All integers are congruent to each other and congruent to zero. Non-integer elements can be represented as the sum of the integer and fractional parts of the number A = [a ] + {a ). Square brackets mean taking the integer part of the number enclosed in them, curly brackets mean taking the fractional part of the number.

Integer part of a number A is called the largest integer [ a ], not exceeding A .

Fractional part of a number A is defined as the smallest non-negative number ( a ), congruent to the number A . Fractional part of a number A equal to the difference between the number A and the whole part of it: ( a }=A - [a ]

For example, for A = 2 1 / 3 [a ]= 2 (a) = 1 / 3

for a = - 2 1 / 3 [a ]= -3 (a) = 2 / 3

Properties of number congruence:

1. If A ≡ b , That ( A } = {b }.

2. {A +b } = {A } + {b }.

3. If n is an integer, then for any A

na ≡ {na } ≡ n {A }.

When solving integer programming problems using the Gomori method, the first stage coincides with the usual calculation using the simplex algorithm. The resulting solution in general view will satisfy all the conditions of the problem, except for the integer requirement (it is possible, of course, that an integer solution can be obtained already at the first stage). If among the values ​​of the variables in the optimal plan (point A in Fig. 13) there are fractional ones, then an additional constraint is drawn up, as if “cutting off” the fractional part of the solution (line 1 in Fig. 13), but leaving in force all the restrictions of the problem that should satisfy the optimal plan. An additional constraint is added to the original constraints of the problem and the simplex procedure is again applied to the extended system. If the optimal solution again turns out to be non-integer (point B in Fig. 13), then another additional constraint is added (line 2 in Fig. 13) and the calculation process is repeated. The algorithm allows us to arrive at an optimal integer solution (if it exists) in a finite number of steps (point C in Fig. 13).

Rice. 13. Gomori cutoff method

Example solving an integer programming problem. To purchase equipment for a new production site allocated 20 monetary units. The equipment must be placed on an area not exceeding 38 m2. An enterprise can order two types of equipment: more powerful type A machines costing 5 monetary units, requiring a production area of ​​8 m 2 (including passages) and providing a productivity of 7 thousand units of production per shift; less powerful machines of type B cost 2 monetary units, occupy an area of ​​4 m 2 and produce 3 thousand units of production per shift.

Let us denote by X 1 number of purchased cars A and through X 2 - the number of purchased cars B, we obtain the mathematical conditions of the problem:

maximize 7x 1 + 3x 2 → max

under conditions: 5x 1 + 2x 2 ≤ 20

8x 1 + 4x 2 ≤ 38

x 1, x 2 ≥ 0 (integers).

With the help of additional variables x 3 and x 4, the original inequalities are transformed into equations (reduced to canonical form):

5x 1 + 2x 2 + x 3 = 20

8x 1 + 4x 2 + x 4 = 38

If the main variables x 1 and x 2 are integers, then it immediately follows from the equations that the variables x 3 and x 4 can only take integer values.

The problem is solved first without taking into account the integer requirement.

A simplex table has next view:

Basis	WITH	Plan					θ
X 1	X 2	X 3	X 4
X 1 →X 3							20/5=4 min
X 4							38/8=4,75
f(x) = 0	-7	-3
X 1				2/5	1/5		4:2/5=10
X 2 →X 4				4/5	-8/5		6:4/5=7.5 min
f(x) =28		-1/5	7/5
X 1						-1/2
X 2		7,5			-2	5/4
f(x) =29.5				1/4

In the optimal plan, X 1 = 1, X 2 = 7.5; the maximum of the objective function is 29.5. Thus, it is necessary to buy one machine of type A and 7 machines of type B (there is not enough money or space for 8 machines), then the volume of production will be f(x) = 7 × 1 + 3 × 7 = 28 thousand units of production .

Let's find an integer solution using Gomori's method. For the variable X2, which has received a non-integer value in the plan, we compose the following equation, which directly follows from the given simplex table:

7.5 = X 2 – 2X 3 + 1.25X 4.

X 2 = 7.5 + 2X 3 – 1.25X 4.

This equation, obviously, must also be valid for an admissible integer solution to the problem.

Since X 2 is an integer, the expression on the right side of the equation is also an integer; therefore, the value of the right-hand side of this equation is congruent to zero:

7.5 + 2Х 3 – 1.25Х 4 ≡ 0,

–2Х 3 + 1.25Х 4 ≡ 7,5.

Given the above properties of congruence, and also the fact that X 3 and X 4 are integers, this expression can be transformed into the following:

(-2)X 3 + (1.25)X 4 ≡ {7,5} ;

from here we get:

0.25X 4 ≡ 0,5.

Since X 4 is a non-negative integer, we have:

0.25X 4 = 0.5, or 1.5, or 2.5, ...;

hence,

0.25X 4 ≥ 0.5.

The resulting inequality is converted into an equation and added to original system constraints, which now contains the following three equations:

5x 1 + 2x 2 + x 3 = 20

8x 1 + 4x 2 + x 4 = 38

0.25x 4 – x 5 = 0.5.

By repeating the solution process using the simplex method in relation to the extended system of constraints, we obtain a new optimal plan in which the values ​​of the variables included in the basis are equal to: X 1 = 2; X 2 = 5; X 4 = 2 (remaining free area).

Thus, an optimal integer solution to the problem has been obtained: under these restrictions, maximum productivity (29 thousand units of production) is ensured by purchasing 2 machines of type A and 5 machines of type B.

PRACTICAL LESSON

BRANCH AND BOUND METHOD

This method can be applied to solve both fully and partially integer discrete programming problems.

Consider the model

under restrictions

Let us assume that for each integer variable we can set an upper and lower limit, within which, of course, it is contained optimal values

H j ≤ X j ≤ V j ; j=1,2,…,k,…,n.

Usually Hj = 0, but this condition is not necessary. The problem is solved using the simplex method. If Xk takes fractional values, we believe that the optimal solution to the problem will satisfy the linear constraint X k ≤ D k , or linear constraint X k ≤ D k + 1 , Where Dk =[Xk ] – the nearest integer down from the value Xk ; Dk+1 – nearest whole in big side from Xk . Wherein H j ≤ D k ≤ V j – 1 . Then it is necessary to solve a couple of linear programming problems using the simplex method:

A.

IN.

We obtain an iterative process represented as a tree, the top of which corresponds to the solution of the original problem, and the two branches connected to it are solutions to a pair of linear programming problems A and B. The resulting values ​​of the objective functions can be less than or equal to the value of the objective function of the original problem f(X) A ≤ f(X)­ 0 ; f(X) B ≤ f(X)­ 0 . Each of the two new branch vertices obtained can have its own further branches.

1) The iterative branching process continues until an integer solution is obtained among the obtained plans, and the value of the objective function must be greater than or equal to the values ​​of the objective functions of other branching vertices.

2) If at the next iteration step both problems have non-integer solutions, then for further branching the vertex corresponding to the problem with great value goal functions. For one of the variables that has received fractional values, new constraints are drawn up for the following linear programming problems.

3) If at the next iteration step one of the problems has an integer solution, and among the values ​​of the variables in the second problem there are fractional ones, then the problem that has highest value goal functions. If this is a problem that has received an integer solution, then the process ends, but if this is a problem with fractional values ​​of variables, then further process branching.

4) If at the next iteration step one of the problems does not have a solution, and the second problem among the values ​​of the variables in the resulting solution has fractional values. Then, for the first problem, the branching process stops, and for further transformation of the second problem, one of the non-integer variables is selected, for which additional constraints are drawn up for a new pair of linear programming problems.

5) If at the next iteration step one of the problems does not have a solution, and for the other an integer solution is obtained, and there are no other options with a larger integer value of the goal function and for which branching can be continued, then the process ends and the solution found is optimal integer solution original task.

If the selected task leads to a break (deadlock) or the function value is less than in task B.1 f(X) A.4< f(X)­ В,1 ., then a return to task B.1 occurs and a new branch occurs.

Fig. 14. Branch and Bound Algorithm Flowchart

Rice. 15. Branch and bound method

MINISTRY OF EDUCATION OF THE RUSSIAN FEDERATION

KUZBASS STATE TECHNICAL UNIVERSITY

Department computer technology and information technology

SOLVING LINEAR INTEGER PROGRAMMING PROBLEMS USING THE GOMORI METHOD

Guidelines and assignments for practical classes at the rate

“Economic and mathematical methods” for students of economic specialties

Compiled by N.Yu. Kolomarova

Approved at a meeting of the department Minutes No. 5 of 11/30/99

An electronic copy is located in the library of the main building of KuzSTU

Kemerovo 2000

1. PROBLEM STATEMENT

There are a number of optimal planning problems in which variables can only take integer values. Such tasks are related to determining the number of units of indivisible products, the number of machines when loading equipment, the number of employees in the structural divisions of the enterprise, etc. Quite often, problems arise with so-called Boolean variables, the solutions of which are judgments of the “yes-no” type. If the function and constraints in such problems are linear, then we are talking about a linear integer programming problem.

The linear integer programming problem is formulated

is as follows: find such a solution (plan)

X = (x1, x2, ..., xn),

takes the maximum or minimum value under restrictions

2. GOMORI METHOD

One of the methods for solving linear integer programming problems is the Gomori method. The essence of the method is to construct constraints that cut off non-integer solutions to a linear programming problem, but do not cut off any integer plan.

Let's consider an algorithm for solving a linear integer programming problem using this method.

1. We solve the problem using the simplex method without taking into account the integer condition. If all components of an optimal plan are integers, then it is optimal for an integer programming problem. If a problem is found to be unsolvable, then the integer programming problem is also unsolvable.

2. If among the components optimal solution are non-integer, then to the constraints of the problem we add a new constraint that has the following properties:

It should be linear; - must cut off the found optimal non-integer

plan; - must not cut off any integer plan.

To construct a constraint, we select a component of the optimal plan with the largest fractional part and using the kth row of the simplex table corresponding to this component we write down the Gomori constraint.

		f k = ∑	f kj x j − S * ,S * ≥ 0 ,
where f k	Xj - ;
	Zkj - ;
		New variable;
The nearest integer not exceeding x j and z kj, respectively
		We add the created constraint to those available in the sim-

complex table, thereby obtaining an extended problem. To obtain the reference plan for this problem, you need to enter into the basis that

	a vector for which the quantity				∆ j		minimal. And if for this century -
					f kj
	torus value θ = min		it turns out according to additional line, then in
	z ij> 0

the following simplex table will produce the reference plan. If the value θ does not correspond to the additional line, then it is necessary

go to the M-problem (introduce an artificial variable into the Gomori constraint).

4. We solve the resulting problem using ordinary simplex transformations. If the solution to this problem leads to an integer optimal plan, then the desired problem is solved. If we get a non-integer solution, then we again add one additional constraint, and the calculation process is repeated. After completing a finite number of iterations, we either obtain an optimal plan for the integer programming problem or establish its unsolvability.

Notes:

1. If the additional variable S * is included in the basis, then after recalculating any subsequent plan, the corresponding row and column can be deleted (thereby reducing the dimension of the problem).

2. If for fractional x j it turns out that all the coefficients of the corresponding equation (row) are integers, then the problem does not have an integer solution.

3. EXAMPLES OF SOLVING PROBLEMS USING THE GOMORI METHOD

Task: To purchase new equipment, the company allocates 19 monetary units. The equipment must be placed on an area not exceeding 16 sq.m. An enterprise can order two types of equipment: machines of type “A” costing 2 monetary units, requiring a production area of ​​4 sq.m and providing a productivity of 8 tons of products per shift, and machines of type “B” costing 5 monetary units, occupying an area 1 sq.m and providing a productivity of 6 tons of products per shift.

It is required to draw up an optimal equipment acquisition plan that ensures maximum overall performance.

Solution: Let us denote by x 1 , x 2 the number of machines of type “A” and “B”, respectively, and by L - their total productivity. Then mathematical model tasks:

max L = 8 x1 +6 x2

with restrictions:

2x 1	5x2
4x 1
x 1≥		0, x2 ≥ 0

x1, x2 - integers

We solve the problem using the simplex method without taking into account integer values.

	∆ j
	∆ j
	∆ j

The optimal non-integer plan X opt = (61/18;22/9) was obtained.

Lmax = 376/9.

Because the plan component x 2 has a maximum fractional part: max(4/9;7/18) = 4/9, then we write an additional constraint on the first line.

22/9 - = (2/9 - )x 3 + (-1/9 - [-1/9])x 4 -S 1 , S 1 ≥0 22/9 - 2 = (2/9 - 0) x 3 + (-1/9 - (-1))x 4 -S 1 , S 1 ≥0

4/9 = 2/9x3 + 8/9x4 - S1, S1 ≥ 0 - first Gomori constraint

We add the created constraint to those existing in the simplex table.

After constructing an additional constraint we have new task linear programming, which has 3 restrictions. To obtain a reference plan for this problem, it is necessary to find the third basis

ny vector. To do this, we define: min
	f kj

basis we introduce the vector x 4.							4 / 9
We calculate the value θ =
	z ij> 0						8 / 9

Minimum valueθ was obtained from an additional line, which means that without resorting to an artificial variable, we obtain the reference plan of the extended problem.

	∆ j

The found plan is optimal, but non-integer. We are building a new Gomori constraint.

Because the maximum fractional part among the plan components is 1/2, write an additional restriction on the first line (you can also on the third).

5/2 - = (1/4 - )x 3 + (-1/8 - [-1/8])S 1 -S 2 , S 2 ≥0

1/2 = 1/4x3 + 7/8S1 - S2, S2 ≥ 0 - second Gomori constraint

We add this constraint to the last simplex table.

We received a problem in which there are 4 constraints, therefore, there should be 4 unit vectors in the basis.

								2. Can

enter either x 3 or S 1 . Let's introduce the vector S 1 .

1/ 2

4 / 7

corresponds to additional

7 / 8

limitation.

∆ j

We obtain a new optimal non-integer plan. Taking into account Remark 1, we cross out the row and column corresponding to the re-

variable S 1.

In the resulting plan, the component x2 has the maximum fractional part, so we write down an additional constraint on the first line.

	4/7 = 2/7x3 + 6/7S2 - S3, S3 ≥ 0	Gomori's third limitation.
	We determine the vector introduced into the basis:

vector x 3. The minimum value of θ = 2, which corresponds to an additional line.

After carrying out the next simplex transformations we got:

	∆ j

Plan X 5 is optimal non-integer. We write an additional restriction on the second line:

1/2 = 1/4S3 - S4, S4 ≥ 0

Gomori's fourth limitation.

Because the basis component can be S 3, we determine the value

0. The minimum value of θ was obtained at 3

line, and not along the Gomori line, therefore, we move on to the M-problem:

let's introduce an additional variable x 5							to the Gomori limitation.
C5'	B5 '	X5 '
	∆ j

∆ j

∆ j

Fractional part = max(1/3; 2/3) = 2/3

additional restriction

We write it down on the second line.

2/3 = 1/3x4 + 2/3S4 - S5

S5 ≥

Fifth limitation of Gomori.

16 / 3

2 enter x 4.

Vector entered into the basis: min

2 / 3

θ =

matches Gomori's line.

∆ j

Plan X 8 = (3; 2; 3; 2) - optimal integer. L max = 36.

Economic interpretation:According to the decision received, the company needs to purchase 3 machines of type “A” and 2 machines of type “B”. In this case it will be achieved maximum performance equipment operation equal to 36 tons of products per shift. Resulting savings Money in the amount of 3 den. units. can be sent to any other purposes, for example, for bonuses for workers who will debug the received equipment. You can put a box of flowers on the excess area of ​​2 sq.m.

Geometric interpretation of Gomori's method: we are building many

number of plans (see figure). At point 1 - the optimal non-integer plan.