І Г Дейнека - Аналіз теоретичних основ про вивчення впливу агресивних середовищ на матеріали з полімерним покриттям - страница 20
normal n = (c\, c 2,..., c'q) from the relation
\m\ • гц
or the calculation of the algebraic projection
- (n ^n і) /Д\
of the vector n on the vector n ,. The maximal value of these ratios corresponds to the main hyperplane.
The volume of calculations of cos^, or prnn is insignificant; so the basic problem consists in the elimination of superfluous constraints. The choice a superfluous constraint as the main hyperplane does system of constraints inconsistent.
Thus, the problem of the optimal plan search is reduced to the problem of the exception of superfluous constraints, which can be solved by various means of the convex analysis depending on the chosen approach to its solution, namely:
1. Definition whether the constraint system is inconsistent or exception of dependent inequalities by known ways [5, 6].
2. The use of duality or the geometrical properties of the main hyperplanes, for example, the partial order of angles between their normals, and of the objective normal arrangement: it is nested inside the convex cone, spanned positively by main hy-perplane normals, etc.
3. Reducing the inequality system to homogeneous by substitution of the first main hyperplane equation in other constraints. Geometrically such transform means the construction of the set of nested cones (pyramids) having apex in the origin. For pyramids the superfluous constraint normals usually have smaller values of projection (5) and do not influence upon a choice of the main hyperplanes that allows determining a vertex in the main hyperplane for n iterations. It can serve as the initial basic plan for the simplex-method algorithm, reducing the volume of calculations.
4. As on each iteration the next main facet is found among intersections of the projected facet and its adjacent facets, the definition of these adjacent facets solves the problem of the elimination of superfluous constraints.
Offered method is effective as from iteration to iteration the number of inequalities is reduced. At such approach it is expedient to use the topological transformations of an initial polytope keeping neighborhood relations between facets, such as its representations polar polytopes for which face lattices are inversely isomorphous .
The general algorithm of the adjacent facet determination is not developed and as a consequence of this there is the practical interest in classes of the polytopes equivalent to the n-dimensional cube with the number of the problem constraints (2) smaller or equal n . This condition can be satisfied, if it is necessary, by the transition to the dual LP problem.
The cube is defined by constraints x, < 1, x, > 0,і = 1,n , all set of facets is broken
into pairs not adjacent: xt = 0 and x, = 1. Two polytopes are considered equivalent if
there is an isomorphism between their facets, which does not break their neighborhood relations. All n -dimensional n -facet cones are equivalent. The n -dimensional cube is a intersection of two cones K0 and KM with vertices in the origin and the
point M(1,1,...1), and each edge of the cone K0 has the vertex on only one of the facets of the cone KM . Such formal description of the n -dimensional cube allows to formulate the properties of the equivalence of a polytope and the cube: each hyperplane Ц of the problem constraint of a polytope cuts on one of coordinate axes j a segment of the minimal length concerning segments cut by other hyperplanes. In this case the pair not adjacent facets is simply defined as a pair: L, = 0 and = 0 . Practically it means that every decision variable is major among others in one of problem constraints.
It is obvious, that following transformations - the translation of coordinate axes, the change of the scale on axes, the rotation of axes of coordinates - do not break the neighborhood relations between facets (boundary points are converted in equivalent boundary, internal - in internal points), that is the polytope remains in the equivalence class.
3. Application for a solution of the integer programming problem
The method of the sequential definition of the main facets allows constructing simple algorithm of the integer solution.
Let constraints (2), (3) are renumbered in the order of the definition of the main
facets. Then the subset of main hyperplanes Lk = 0,k = 1,n , intersecting in the optimum point X', produces n edges with directing vectors pk,k = 1,n and forms in each q -dimensional main facet Mq a q -faced angle (a cone Kq with the vertex in the point X*). Let p is the directing vector of the edge formed by intersecting of all hyperplanes, except for the hyperplane Ц = 0 . Then the cone Kn-1 of the main facet Mn-1 is spanned positively by vectors p2,p3...pn , the cone Kn-2 of the main facet Mn-2 is spanned by vectors p3,...pn , etc., the cone K2 spanned by vectors pn-1, pn , the cone K1 will be a straight half-line with the directing vector pn .
Each subsequent cone in this sequence is formed by exception of one vector p of the set of vectors (ph...pn), so that the angle of an inclination of the cone K(p/+1,...pn) (its affine hull aff K), that is a facet of the cone K(p,p/+1,...pn), to the objective hyperplane Z(,) = 0 will be the least.
The transformed constraints - inequalities Lk < 0,k =i +1,n on each iteration define the projection of the cone of the main facet with vertex X* (q -faced angle), that is set a q -dimensional part of boundary near the point X*, having the minimal distance from the objective hyperplane Z = Z*. Considering these cone projections on reverse order iterations, it is possible to find the good enough integer approximation of
the point X * by any criterion (example).
More detailed consideration of this section questions is beyond this paper.
4. Example. Resource allocation problem
This example represents the special case of the final point determination, which differs from optimal point by two hyperplanes.
It is supposed that the original system of inequalities is consistent and does not contain superfluous constraints.
Maximize z = 3x1 + 4x2 + 8x3 + 5x4 + 12x5 + 2x6 , n = (3,4,8,5,12,2), subject to:
L = 3x1 + 2x2 - x3 + 6x4 + x5 + x6 < 24 , n1 = (3,2,-1,6,1,1); L2 = x1 + 6x2 + x3 + 2x6 < 18, n2 = (1,6,1,0,0,2);
L3 = x4 + 2x5 < 12, n3 = (0,0,0,1,2,0);
L4 = 3x4 + x5 < 12, n4 = (0,0,0,3,1,0);
L5 = 2x1 + x2 + x3 < 24 , n5 = (2,1,1,0,0,0);
L6 = 2x3 + x5 + 3x6 < 36 , n6 = (0,0,2,0,13);
L6 + j =-xj < 0, j =1,6
1. Using properties of the polar polytopes for which the edge between the vertices means the adjacent relation between the corresponding facets of the original polytope , find pairs of not adjacent facets: (L1,L6), (L4,L5), (L5,L6), (L7,L5), (L9,L6),
(L10, L4), (L11, L3).
2. Find the first main hyperplane by computing the projections. The maximal
_ 5 + 24 29
value produces pr-рг n =—!^ = -!= and the first main hyperplane is n3 V5 V5
L3 : x4 + 2x5 = 12. Not adjacent facet x5 = 0 is excluded from the constraint system.
3. Find the second main hyperplane, substituting from the equation for L3 : x4 = 12 - x5 in other inequalities. The problem in 5-dimensional space becomes:
maximize z = 3x1 + 4x2 + 8x3 + 2x5 + 2x6 , n = (3,4,8,2,2),