The Maple ® Symbolic Mathematics System in the Method of Projections for Discrete Optimization Problems Serhii Chernov1, Serhii Titov1[0000-0001-8772-9889], Liubava Chernova1 and Nataliia Kunanets2 [0000-0003-3007-2462] 1Project Management Department Admiral Makarov National University of Shipbuilding Mykolaiv, Ukraine 2Lviv Polytechnic National University; 12, St. Bandera str., Lviv, Ukraine 19chsk56@gmail.com, ss1-ss10@ukr.net, nek.lviv@gmail.com Abstract. Successful project activities in the IT industry are determined by the extent of difficulty in the team formation and implementation of projects themselves. IT projects provide for fulfillment of a number of tasks that are interrelated. In formation of such a project, account should be taken of certain factors necessary for its successful implementation, determination of the technology for fulfilling intermediate tasks: consecutive or parallel, and for setting the priorities. This approach requires detailed calculation and scientifically grounded decisions. The authors have proposed an original approach to solving discrete optimization problems related to fundamental calculation difficulties in the process of an IT project formation. The known methods of exact or approximate solution of such problems are studied with account taken of their belonging to so-called P- and NP-class problems (the polynomial and the exponential solution algorithms). The modern combinatory and heuristic methods for solving practical discrete optimization problems require development of algorithms that allow obtaining approximate solution with guaranteed estimate of deviation from the optimum. Simplification algorithms provide an efficient method of searching for an optimization problem solution. Should a multidimensional process be projected onto the two- dimensional surface, this will enable graphical visualization of sets of the problem solutions. This research provides a way for simplifying the combinatory solution of a discrete optimization problem. It is based on decomposition of the system that represents the system constraining a multidimensional output problem to the two-dimensional coordinate plane. Such method allows obtaining a simple system of graphical solutions of a complicated linear discrete optimization problem. From the practical point of view, the proposed method allows reducing the calculation complicacy of optimization problems belonging to this class when the IT project solutions are complicated. The approach proposed can be applied in using the obtained research result for assuring the possibility to improve the class of problems presented by linear equation systems. The automation of calculations in the Maple® environment provides the basis for further development and improvement of such algorithms, and for using in teaching a number of disciplines in education programs on IT project management aimed at Master’s degree. Keywords: IT project management, education programs aimed at Master’s degree, linear optimization, discrete optimization, system of constraints, combinatory method, the gauss-jordan method, decomposition, reduction, graphical solution, Maple®. 1 Introduction Discrete optimization problems appear in many areas where models of current processes were formed and use mathematic methods[19,20,21,22] of their solution under the following additional conditions: the unknowns have to be integer in full or in part, or they have to be binary (0 or 1). The traveling salesman problem, the knapsack problem and the assignment problem are the most known problems of linear optimization. Nowadays, discrete optimization has been formed as an independent part of the theory of optimization. It uses modern combinatory methods and algorithms for solving practical problems. Their application results in primary bases of a problem, further assessment of their optimality, improvement of bases in case of their nonoptimality and bounds of the target function [1,2,3,4]. As the most discrete optimization problems belong to the NP class, it is reasonable to use problem simplification algorithms without losing the controlled accuracy of solution [5,6,7]. The procedure of simplification uses the known interrelation of linear algebraic equation systems with the system of linear algebraic inequalities and the classic linear algebra apparatus [8,9,10]. The principle of the method proposed consists in using the feature of convex polyhedral area  I provided by a system of linear algebraic inequalities or equations in the form of a direct sum of subspace and kernel.[11] Provided that the polyhedral kernel is two-dimensional, an optimization problem can be reduced to a two-dimensional one. Projections obtained enable easy finding of the optimum solution and evaluation of availability of an integer solution, and then of a binary solution as well. A direct calculation means of simplifying such class of discrete optimization problems is implemented by the Gauss-Jordan method in the Maple® computer mathematics environment [7,10,12,13]. 2 Literature Data Analysis and Problem Statement Mathematic models of active systems are interpreted in many cases as discrete optimization problems [1,2,14,15]. Development of discrete optimization problems is associated with fundamental difficulties [2]. The known modern methods and algorithms of exact and approximate solution of such problems are studied with account taken of their belonging to so-called P- and NP-class problems (the polynomial and the exponential solution algorithms). [5]. Combinatory and heuristic methods for exact and approximate solving practical discrete optimization problems take an essential place in obtaining optimum values of such problems [1]. Realization of such algorithms requires availability of the acceptable primary basis of a problem, an optimality assessment procedure and the basis improvement if nonoptimality is the case [5,6]. The methods of discrete optimization problems solution that have been developed by now require development of algorithms which allow obtaining an approximate solution with guaranteed estimate of deviation from the optimum. Simplification algorithms in discrete optimization problems provide an efficient method of searching for an optimization problem solution. [16,17,18]. Should a multidimensional process be projected onto the two-dimensional surface, this will enable visualization of the acceptable set (array) of the problem parameters. We can make a lower- and an upper-bound estimate of the problem target function values and dynamically evaluate the possibility to diversify basis optimum variables with guaranteed accuracy. Solving contradictions between requirements to completeness of modeling views in active systems and methods of obtaining solutions of their mathematic models is possible due to reasonable reduction of the algorithms of complicated equation systems solution [17]. Lack of problem solution as regards searching for solutions in discrete optimization problems consists in the need for developing and implementing the procedure of simplifying the combinatory solution of a discrete optimization problem. 3 The Research Objectives and Task The following objectives are determined for the research: involving and using linear algebra standard calculation procedures and certain linear optimization methods to simplify the solution of multidimensional discrete optimization problems with further visualizing of geometric interpretation of a linear discrete optimization problem solution. The following tasks were set to achieve the objectives determined:  to remove the class of problems that have to be simplified;  to provide calculations of a modeling example. 4 Development of Simplification of the Solution in Discrete Optimization Problems Successful project activities in the IT industry are determined by the extent of difficulty in the team formation and implementation of projects themselves. IT projects provide for fulfillment of a number of tasks that are interrelated. In formation of such a project, account should be taken of certain factors necessary for its successful implementation, determination of the technology for fulfilling intermediate tasks: consecutive or parallel, and for setting the priorities. To fulfill the task of a project content optimization, works are analyzed that have to be performed for creating a software. In this process, the project is analyzed for its content, period for each stage implementation, costs, risks and value. The value determining approach is based on comprehensive characteristic of the project results. This characteristic, in its turn, can be defined by quality of the software created as a result of the project implementation, as well as by economic, social and politic, environmental, technical and other effects. For efficient calculations and avoiding fundamental calculation difficulties in the process of an IT project formation, evaluation of project actions in all phases of the project lifecycle – from issuance of requirements specifications to software installation to the customer, the authors have developed a method reducing the calculation complicacy of optimization problems. This research proposed the system decomposition through projection of a multidimensional output problem onto two-dimensional coordinate planes. This method transforms the output problem into a group of subsystems, which enables obtaining the system of graphical solutions of a complicated linear discrete optimization problem. The Maple® software environment has been involved from the methodological and scientific points of view. Each of the problem stages has been associated with a subprogram for automation of calculations and visualization of solution results (Fig. 1). Information system of optimizing calculation Preparing output data for a discrete optimization problem. Adapting the system of constraints to canonical type. Optimization problem decomposition. Combinatory enumeration of basis and Gauss-Jordan calculations. Graphic representation of projection. Analysis of results obtained and determining the optimum solution. Fig. 1. Enlarged UML diagram of information system For the method use visualization, we formulate a problem on optimum placement of n - sets A j , j  1, ..., n on the universal set U . Let each set A j , j  1, ..., n be characterized by two scalar values: c j - value and a j - power or weight A j . At the same time, the condition is fulfilled that the cardinality of universal set U  B is smaller than the total cardinality of all A j . Such an optimization problem consists in the need to select a certain number of A j from the total aggregate of A j , for immersion into U , the total value of which is maximum. n The total power  a j  B is bigger than the cardinality of universal set, i.e. it is j 1 impossible to place the complete number of sets. U can only accommodate a part (a number) of sets A j . Let us enter n Boolean (dichotomic or binary) variables:  0, A j is not placed in U , xj   (1)  1, A j is placed in U , where j  1, ..., n . Entering binary unknowns (1) - x j  0  1 , j  1, ..., n allows formulating the target function WI and constraint I of the following optimization problem: WI  c1 x1  c2 x2    cn xn  max,  I : a1x1  a2 x2    an xn  B, (2) x j  0  1, j  1, 2,  , n. According to the problem statement, c j  0 , 0  a j  B , j  1, 2,  , n. Such problem (2) is called in the discrete optimization theory a one-dimensional knapsack problem. Solution of this problem means finding among 2 n n – dimensional vectors such vector X  [ x1, x2 , , xn ] , which meets the constraints I and provides the maximum value to the target function WI . (Fig. 2) U B [c1 , a1 ] [c2 , a2 ] U x 1 A1 A2 1 xk  1 A1 Ak Набір X  [ x1 , x2 , , xn ] xl  1 A3   Al xj  0  1 xn 1  1 An1 An An1 n a  B j 1 j [cn1 , an1 ] [cn , an ] Fig. 2. The problem on A j immersion into U . (one-dimensional knapsack) Let us consider the generalized one-dimensional knapsack problem statement. We divide the universal set into its own subsets U  U1 U2 Um with the m condition Ui  bi , i  1, 2,  , m , and B   bi The problem of immersion of sets i 1 A j , j  1, ..., n into U  U1 U2 Um is interpreting A j as a set not just with one feature a j , but with a whole range of ai j , i  1, 2,  , m . The features are provided by set A  [ai j ]mn . The mathematic form of such optimization problem on placement of A j into U  U1 U2 Um looks as follows: WI  c1x1  c2 x2    cn xn  max, a11x1  a12 x2    a1n xn  b1,  a21x1  a22 x2    a2n xn  b2 ,   I :     a x a x    am1,n xn  bm1,  m1,1 1 m1, 2 2 am1x1  am 2 x2    amn xn  bm , x j  0  1, j  1, 2,  , n. Account is to be taken of the fact that c j  0 , 0  ai j  B , i  1, 2,  , m , j  1, 2,  , n. For i [ 1, m] the following is to fulfill: ai1  ai 2  ain  bi . It means that it is not possible to place all sets A j , j  1, ..., n in any of the subsets U  U1 U2 Um . The number of n – measurable vectors X  [ x1, x2 , , xn ] is the solution of the problem. Such type of problem is used to be called one-dimensional knapsack problem. The formulated problem is interpreted as a problem on optimum selection in project management. For implementation of n projects ( A j , j  1, ..., n ), certain resources are provided that are represented in the form of a vector of resources b  [ b1, b2 , , bm ]T The set A  [ai j ]mn determines the rates of consuming resource b j for implementation of project A j . The profit from implementation of project A j is c j  0 . We need to choose the number of projects A j that allows gaining the maximum profit. Let us enter Boolean vector X  [ x1, x2 , , xn ] , where 0, project A j is not implemented, xj   1, project A j implemented, j  1, ..., n . We obtain the problem: WI  CX T  max,  I : AX  b, (4) x j  0  1, j  1, 2,  , n. The project management model (4) completely agrees with the multidimensional knapsack problem (3). At this time, we know that the given problems (3), (4) cannot be exactly resolved. We have performed exhaustive research of features of acceptable and optimum solutions of knapsack problems and proposed several algorithms [2,5] of gradual approximating to the optimum solution. Thus, the Danzig algorithm and so-called “greedy” procedures form the basis of heuristic algorithms.[18] The research has proposed and exactly grounded an approach to finding the optimum solution of a broad class of multidimensional knapsack problems. The principle of the method proposed consists in using the feature of convex polyhedral area I provided by a system of linear algebraic inequalities or equations in the form of a direct sum of subspace and kernel. [10, 17] Provided that the polyhedral kernel is two-dimensional, an optimization problem can be reduced to a two-dimensional one. Projections obtained enable easy finding of the optimum solution and evaluation of availability of an integer solution, and then of a binary solution as well. In other words, the research proposed projecting polyhedron I onto subsets of the set of basis vectors of a linear optimization problem system of constraints. For special case m  n  2 , where m - number of constraints I , n - rank A  [ai j ]mn projections are elementary because the are two-dimensional. It is not difficult to analyze the projection integer values array and to solve the problem. The first step in this algorithm is to prepare the system of constraints for reduction. Thus, let us have a general optimization problem in the following form: n WI   c j x j  max, j 1 n   ai j x j  bi , i  1,  , k ,  j 1 I :  n  a x b,  ij j i i  k  1,  , m,  j 1 x j  0, j  1,  , l. We know that such a problem can be reduced to the canonical form: n WI   c j x j  max, j 1 n  I :  ai j x j  bi , i  1,  , m, j 1 x j  0, j  1,  , n. The reduction is possible due to standard methods of transformation. Thus, the equation of system of constraints is equivalent to the system of two inequalities:  n   ai j x j  bi , n  j 1  ai j x j  bi   n j 1  a x  b .   ij j i  j 1 Values with arbitrary sign can be represented in the form of a difference of 2 nonnegative variables: xj  uj vj, u j  0, v j  0. Transition from inequality constraints to equation constraints is made by adding the nonnegative (balancing) variable: n n  ai j x j  b j   ai j x j  xni  bi , xni  0, i  1, , k. j 1 j 1 Transition from maximization to minimization of the target function and transition the other way round is used for simpler transformation: n n WI   c j x j  max  WI   c j x j  min . j 1 j 1 In view of this, without loss of considerations generality, let us have a linear optimization problem provided in canonical form: WI  CX  max  I : A X  B, X  0, where the matrix rank of factors of the system of constraints is equal to rank A = m. Solving the system with the Gauss-Jordan method under an arbitrary basis combination of variables, we obtain projection n - of measurable output problem onto (m  n) - measurable space. As we take into consideration a class of problems with condition m  n  2 , we have projecting of R n onto two-dimensional plane R 2 . Let us consider a modeling example of solution based on projecting a multidimensional process in R 6 onto two-dimensional space R 2 . 5 Modeling Example Tasks: solving the optimization problem with condition x j  0, j  1, , n. . Also obtaining a completely integer solution and the solution under condition x j  0  1, j  1, 2,  , n. WI  x1  8 x2  4 x3  x4  max,  2 x1  3x2  4 x3  3x4  7,   3x1  5 x2  2 x3  4 x4  8, I :  .  3x1  3x2  5 x3  4 x4  6,   3x1  5 x2  3x3  2 x4  8, x1  0, x2  0, x3  0, x4  0. We make a transition to canonical form of a linear optimization problem WI  x1  8 x2  4 x3  x4  max,  2 x1  3x2  4 x3  3x4  x5  7,   3x1  5 x2  2 x3  4 x4  8, I :  .  3x1  3x2  5 x3  4 x4  6,  3x1  5 x2  3x3  2 x4  x6  8, x j  0, j  1, ...,6. The system of constraints consists of four independent equations rank(A) = 4. We move from the canonical form of problem representation to the standard form. Such move (projecting) is made with solving the system by the Gauss-Jordan method. (Table 1) For the given problem of projection R6  R2 we can perform C64  15 ways. We choose randomized basis combination Ox3 x4 . 5.1 Projection onto Ox3 x4 . As basis variables, we choose the following quadruple: x1, x2, x5, x6. Table 1 Projection onto Ox3 x4 . x1 x2 x3 x4 x5 x6 b ∑ 2 3 4 3 1 0 7 20 3 5 2 4 0 0 8 22 3 3 5 4 0 0 6 21 3 5 3 2 0 1 8 22 WI 1 8 4 1 0 0 0 0 - 1/3 8/3 1/3 1 0 5/3 16/3 1 5/3 2/3 4/3 0 0 8/3 22/3 0 -2 3 0 0 0 -2 -1 0 0 1 -2 0 1 0 0 WI 0 19/3 10/3 - 1/3 0 0 - 8/3 0 0 13/6 1/3 1 0 2 11/2 1 0 19/6 4/3 0 0 1 13/2 0 1 - 3/2 0 0 0 1 1/2 0 0 1 -2 0 1 0 0 WI 0 0 77/6 - 1/3 0 0 -9 From the last transformation of Table 1, we have the solved system WI  x1  8 x2  4 x3  x4  max,  13 1  6 x3  3 x4  x5  2,   19 x  4 x  x  1,  I :  6 3 3 4 1 (5)  3  x3  x2  1,  2  x3  2 x4  x6  0, x j  0, j  1, ... ,6. Truncating the basis variables, we assure transition R6  R2 to two-dimensional inequalities. The projection of six-dimensional output problem onto coordinate plane Ox3 x4 has the following analytical form: WI  77 x3  1 x4  9  max, 6 3 WI  77 x3  1 x4  9  max,  13 1 6 3  6 x3  3 x4  2,   13x3  2 x4  12,  19  4 Ox3 x4  6 x3  3 x4  1,  19 x3  8 x4  6, I :  Ox3 x4 :   3x3  2, I  3  x3  1,  x3  2 x4  0,   2  x3  2 x4  0, x3  0, x4  0. x3  0, x4  0, The graphical solution is given on Fig. 3. x4 WI  x1  8 x2  4 x3  x4  max,  2 x1  3x2  4 x3  3x4  x5  7, ω2 1  3x  5 x  2 x  4 x  8, ω3 ω1  1 I :  2 3 4  3x1  3x2  5 x3  4 x4  6,  3x1  5 x2  3x3  2 x4  x6  8, x j  0, j  1, ... ,6. ω4  WI  77 x3  1 x4  9  max, 6 3  13 x3  2 x4  12, opt X max  19 x  8 x  6,  O Ox 3 4 x : 3 4  3x3  2, I x3 grad(WI )  x3  2 x4  0, x3  0, x4  0. Fig. 3 Projection onto Ox3x4 The solution of the system is provided in the extremal vertex coordinates  6 19 x3  8 x 4  6,  x3  23 , X max : ω 2  ω 4   opt  .  x3  2 x 4  0, x  3 .  4 23 Other coordinates are to obtain from the solved system (5) Therefore, the optimum solution of the output problem is equal to:   opt X max   0, 32 , 6 , 3 , 32 , 0  .  23 23 23 23  The biggest value of the target function is WImax  289 . 23 The represented OxI 3 x4 projection I onto Ox3x4 (Fig. 2) lets us state that point (0,0) is the only integer solution point of the problem. In view of this, we have the first integer optimum solution estimate X max   x1, x2 , 0, 0, . 5.2 Projection onto Ox1x2 . For calculation of x1, x2 values, we project I onto Ox1x2. As basis variables, we choose the following quadruple: x3, x4, x5, x6. We make calculations with the Gauss-Jordan method. (Table 2). Table 2 Projection onto Ox1x2 . x1 x2 x3 x4 x5 x6 b ∑ 2 3 4 3 1 0 7 20 3 5 2 4 0 0 8 22 3 3 5 4 0 0 6 21 3 5 3 2 0 1 8 22 WI 1 8 4 1 0 0 0 -4 -7 0 -5 1 0 -9 - 24 1,5 2,5 1 2 0 0 4 11 - 4,5 - 9,5 0 -6 0 0 - 14 - 34 - 1,5 - 2,5 0 -4 0 1 -4 - 11 WI -5 -2 0 -7 0 0 - 16 - 1/4 11/12 0 0 1 0 8/3 13/3 0 - 2/3 1 0 0 0 - 2/3 - 1/3 3/4 19/12 0 1 0 0 7/3 17/3 3/2 23/6 0 0 0 1 16/3 35/3 WI 1/4 109/12 0 0 0 0 1/3 From the last transformation of Table 2, we have the solved system WI  x1  8 x2  4 x3  x4  max,  1 11 8  4 x1  12 x2  x5  3 ,   2 x  x   2 ,  3 2 3 3 I :  (6)  3 x  19 x  x  7 ,  4 1 12 2 4 3   3 x1  23 x2  x6  16 ,  2 6 3 x j  0, j  1, ...,6. It should be mentioned that it is already enough just to have this only system for finding an integer solution. Indeed, we ascertained from the previous projecting that x3  0 and x4  0 . In view of this, the second system equation gives x2  1 , and the third equation gives x1  1 . Therefore, X max Z   1, 1, 0, 0, is the integer solution of the problem. We confirm these values through the graphical solution of the problem. Truncating the basis variables, we assure transition R6  R 2 to two-dimensional inequalities. The projection of six-dimensional output problem onto coordinate plane Ox1 x2 has the following analytical form: WI  1 x1  109 x2  1  max, 4 12 3  1 11 8 WI  1 x1  109 x2  1  max,   4 x1  12 x2  3 , 4 12 3    3x1  11x2  32,   2 x  2,  Ox1x2  Ox1x2  x2  1, 2 3 3  I I : :  3 x  19 x  7 ,  9 x1  19 x2  28,  4 1 12 2 3  9 x1  23x2  32,   3 x1  23 x2  16 , x1  0, x2  0.  2 6 3 x1  0, x2  0. x2 WI  x1  8 x2  4 x3  x4  max,  2 x1  3x2  4 x3  3x4  x5  7, ω3  3x  5 x  2 x  4 x  8,  1 I :  2 3 4  3x1  3x2  5 x3  4 x4  6,  3x1  5 x2  3x3  2 x4  x6  8, x j  0, j  1, ... ,6. opt X max Z X max  ω2 1 WI  1 x1  109 x2  1  max, 4 12 3 ω4 grad(WI )   3x1  11x2  32,  x  1,   Ox x 1 2 : 2  9 x1  19 x2  28, I  9 x1  23 x2  32, O x1  0, x2  0. 1 x1 Fig. 4. Projection onto Ox1x2 The solution of the system is the optimum vertex  x1  0,  x  0, opt X max : ω2  ω4   1  . 9 x1  23x2  32,  x2  32 .  23 We obtain the other coordinates from the solved system (6) The problem solution is equal to:   opt X max   0, 32 , 6 , 3 , 32 , 0  . The solution obtained completely agrees with the  23 23 23 23  one obtained previously, with projecting onto plane Ox3x4. The biggest target function value is WImax  289 . 23 The graphic representation shows that (1,1) is the only integer point. With account taken of the previous and the current projecting, we obtain the integer problem Z solution X max   1, 1, 0, 0, . In this problem, the binary solution agrees with the 01 integer solution X max   1, 1, 0, 0, . 5.3 Projection onto Ox1x6 . We project I onto Ox1x6 . In view of this, we take the following quadruple as basis variables: x2, x3, x4, x5. We make calculations with the Gauss-Jordan method. (Table 3). Table 3 Projection onto Ox1x6 x1 x2 x3 x4 x5 x6 b ∑ 2 3 4 3 1 0 7 20 3 5 2 4 0 0 8 22 3 3 5 4 0 0 6 21 3 5 3 2 0 1 8 22 WI 1 8 4 1 0 0 0 -4 -7 0 -5 1 0 -9 - 24 1,5 2,5 1 2 0 0 4 11 - 4,5 - 9,5 0 -6 0 0 - 14 - 34 - 1,5 - 2,5 0 -4 0 1 -4 - 11 WI -5 -2 0 -7 0 0 - 16 - 1/4 11/12 0 0 1 0 8/3 13/3 0 - 2/3 1 0 0 0 - 2/3 - 1/3 3/4 19/12 0 1 0 0 7/3 17/3 3/2 23/6 0 0 0 1 16/3 35/3 WI 1/4 109/12 0 0 0 0 1/3 - 14/23 0 0 0 1 - 11/46 32/23 71/46 6/23 0 1 0 0 4/23 6/23 39/23 3/23 0 0 1 0 - 19/46 3/23 39/46 9/23 1 0 0 0 6/23 32/23 70/23 WI - 76/23 0 0 0 0 - 109/46 - 283/23 From the last step of Table 3, we have the solved system WI  x1  8 x 2  4 x3  x 4  max,  14 11 32  - 23 x1  23 x6  x5  23 ,   6 4 6  23 x1  23 x6  x3  23 , I :  (7)  3 x  19 x  x  3 ,  23 1 46 6 4 23   9 x1  6 x6  x 2  32 ,  23 23 23 x1  0, x6  0. Truncating the basis variables, we assure the transition R6  R 2 to two-dimensional inequalities. The projection of six-dimensional problem onto coordinate plane Ox1x6 has the following form: WI  76 x1  109 x6  283  max, 23 46 23  14 11 32 , WI  76 x1  109 x6  283  max, -  23 x1  46 x6  x5  23 46 23 23   - 28 x1  11x6  64,  6 x  4 x x  6 ,   23 1 23 6 3 23 Ox1 x6  3 x1  2 x6  3, I :   I :  3 x  19 x  x  3 ,  6 x1  19 x6  6,  23 1 46 6 4 23  9 x1  6 x6  32,    9 x1  6 x x  , 32 x1  0, x6  0.  23 23 6 2 23 x1  0, x6  0, The graphical solution is given on Fig. 5. x6 WI  x1  8 x2  4 x3  x4  max,  2 x1  3x2  4 x3  3x4  x5  7,  3x  5 x  2 x  4 x  8,  1 I :  2 3 4  3x1  3x2  5 x3  4 x4  6,  3x1  5 x2  3x3  2 x4  x6  8, x j  0, j  1, ... ,6.  1 WI  76 x1  109 x6  283  max, 23 46 23  - 28 x1  11x6  64,  3x  2 x  3,  1  Ox 6 x 1 6 :  6 x1  19 x6  6, I ω4  9 x1  6 x6  32, opt X max x1  0, x6  0. O 1 x1 ω3 ω2 grad(WI ) Fig. 5. Projection onto Ox1x6 The optimum solution is in the point of origin of coordinates opt X max  [0,0]. The other coordinates can be obtained from the solved system (7). We have:   opt X max   0, 32 , 6 , 3 , 32 , 0  . The solution obtained is equal to the ones obtained  23 23 23 23  previously, projections onto plane Ox3x4 and Ox1x2. The biggest value of the target function is WImax  289 . 23 The software implementation of a linear optimization problem reduction is an important component of the algorithm of such reduction proposed. This step has been realized in the environment of the Maple® symbolic mathematics software package. A program has been developed that provides automation of calculations using the procedure proposed. The program includes two units: selection of a basis variables combination and solution of the system of constraints with the Gauss-Jordan method; three-level optimization calculation ( x j  0 and integers, x j  0  1, j  1, 2,  , n ) with using the standard subprogram library. A program code fragment is given below. # eq1:=2*x[1]+3*x[2]+4*x[3]+3*x[4]+x[5]=7: eq2:=3*x[1]+5*x[2]+2*x[3]+4*x[4]=8: eq3:=3*x[1]+3*x[2]+5*x[3]+4*x[4]=6: eq4:=3*x[1]+5*x[2]+3*x[3]+2*x[4]+x[6]=8: ######################################### ####### W[I]=zf-max; eq1;eq2;eq3;eq4; x[j]>=0; ww1:=solve({eq1,eq2,eq3,eq4},{x[3],x[4],x[5],x[6]}); om1:=-coeff(rhs(ww1[1]),x[1])*x[1]- coeff(rhs(ww1[1]),x[2])*x[2]<= rhs(ww1[1])+(-coeff(rhs(ww1[1]),x[1])*x[1]- coeff(rhs(ww1[1]),x[2])*x[2]): om2:=-coeff(rhs(ww1[2]),x[1])*x[1]- coeff(rhs(ww1[2]),x[2])*x[2]<= rhs(ww1[2])+(-coeff(rhs(ww1[2]),x[1])*x[1]- coeff(rhs(ww1[2]),x[2])*x[2]): om3:=-coeff(rhs(ww1[3]),x[1])*x[1]- coeff(rhs(ww1[3]),x[2])*x[2]<= rhs(ww1[3])+(-coeff(rhs(ww1[3]),x[1])*x[1]- coeff(rhs(ww1[3]),x[2])*x[2]): om4:=-coeff(rhs(ww1[4]),x[1])*x[1]- coeff(rhs(ww1[4]),x[2])*x[2]<= rhs(ww1[4])+(-coeff(rhs(ww1[4]),x[1])*x[1]- coeff(rhs(ww1[4]),x[2])*x[2]): zf:=subs({x[3]=rhs(ww1[1]),x[4]=rhs(ww1[2])},zf): W[I]=zf-max; om1;om2;om3;om4; sort(x[1]>=0),sort(x[2]>=0); p1:=inequal( [om1,om2,om3,om4,x[1]>=0,x[2]>=0], x[1]=- 1..7, x[2]=-1..7,optionsexcluded=(colour=white), op- tionsfeasible=(colour=green,thickness=1)): display( p1); The results obtained within the research have allowed widening the educational content of disciplines taught within the boundaries of the educational program “Project Management”. For instance, the content of discipline “Mathematic Models and Methods in Project Management” includes materials from such basic areas: linear models and linear optimization, discrete optimization, elements of the game theory. All the areas require computer modeling and IT projecting. In view of this, the proposed approach of automating optimization problems calculations is used in the educational process of training students aimed at Master’s degree. 6 Conclusions The proposed approach to simplification of combinatory solution of a discrete optimization problem has significant advantages over the known methods of the optimum solution determining – the simplex method or the artificial basis method. The actually performed decomposition of the system reduces the dimension of the equation system to be solved. Projection of multidimensional system of the output problem onto the two-dimensional coordinate plane allows obtaining a simple system of graphical solutions for a complicated linear discrete optimization problem. From the practical point of view, the approach proposed enables reduction of complicacy when calculating optimization problems of such class, and the software implementation allows including this class of problems into educational projects. The scientific result obtained makes researchers arriving at the conclusion that in the general case, it is not necessary to search for solution in all the projections. It is enough to find the solution just in one projection. The applied significance of the approach proposed consists in using the obtained result to assure the possibility of improving complicated systems described by linear equation systems with linear constraint systems included. Multivalued combinatory projections cause the possibility of changing the range of problem parameters. The research has proposed projecting a multidimensional optimization process onto the two-dimensional plane. Such method of simplification can only be applied to adapted classes of problems. The m rank of the matrix of factors of the system of constraints for a linear discrete optimization problem has to meet the condition n–m=2, where n – the problem dimension. It is reasonable to generalize such projecting onto three-dimensional space. 1. It has been shown that solving a linear optimization problem is possible due to simplifying through decomposition of the system by means of building projections of multidimensional system of the output problem onto two-dimensional coordinate planes. 2. It has been confirmed on the example of solving a standard model problem that the approach proposed enables obtaining a simple system of graphical solutions of a complicated linear discrete optimization problem. The result obtained allows the researchers to arrive at the conclusion that in the general case, it is not necessary to search for solution in all the projections. It is enough to find the solution just in one projection. References 1. Korbut, А. А., Finkelstein, Y. Y.: Discrete programming. Nauka, Moscow (1969). 2. Finkelstein, Y. Y.: Approximate methods and applied problems of discrete programming. Nauka, Moscow (1976). 3. Wagner, H.: Principles of Operations Research, vol. 2. Mir, Moscow (1973). 4. Burkov, V. N., Gorgidze, I. А., Lovetskiy, S. Е.: Applied problems of the theory of graphs. Computation Centre of Republican Adacemy of Science of Georgian SSR, Tbilisi (1974). 5. Sigal, I. K., Ivanova, A. P.: Introduction to applied discrete programming: models and calculation algorithms. Moscow (2003). 6. Nozicka, F., Guddat, J., Hollatz, H.: The Linear Optimization Theory. Berlin (1972). 7. Titov, S. D., Chernova, L. S. Higher and applied mathematics: Manual: In 2 parts, p 1. Fakt, Kharkiv (2017). 8. Lau, D.: Algebra and Discrete Mathematics 1. Basic Terms of Mathematics, Algebraic Structures 1, Linear Algebra and Analytic Geometry, Numeric Algebra. Second corrected and supplemented edition. Springer, Berlin (2007). 9. Jean Pierre, David: Low latency and division free Gauss-Jordan solver in floating point arithmetic. Journal of Parallel and Distributed Computing, 106, 185-193 (2017). 10. Lax Peter, D.: Linear algebra and application. 2nd edn. Wiley, New York (2007). 11. Yeremin, I. I., Astafiev, N. N.: Introduction to the theory of linear and convex programming. FIZMATLIT, Moscow (1976). 12. Tytov, S. D., Chernova, L. S.: Theory of determinants: Training and methodological manual. Torubara V. V., Mykolaiv (2016). 13. Teschl, Gerald, Tesch,l Susanne: Mathematics for Information Scientists, vol 1: Discrete Mathematics and Linear Algebra. Berlin, Springer (2008). 14. Buhir, M. K.: Mathematics for economists. Linear algebra, linear models. Kyiv (1998). 15. Buhir, M. K.: Mathematics for economists. Alma-matir Academia (2003). 16. Titov, S. D., Chernov, S. K., Chernova, L. S.: Reduction in Discrete Optimization Problem. In: 13th International Scientific and Technical Conference on Computer Sciences and Information Technologies CSIT (2018). 17. Chernov, S., Titov, S., Chernova, L., Chernova, L., Kolesnikova, K.: Algorithm for the simplification of solution to discrete optimization problems. Eastern-European Journal of Enterprise Technologies 3(4), 34–43, (2018). 18. Kovalev, М. М.: Discrete optimization. Byelorussian State University, Minsk (1977). 19. Tomashevskyi, V., Yatsyshyn, A., Pasichnyk, V., Kunanets, N., Rzheuskyi, A.: Data Warhouses of Hybrid Type: Features of Construction. Advances in Intelligent Systems and Computing II, 938, 325–334 (2019). 20. Kunanets, N., Lukasz, W., Pasichnyk, V., Duda, O., Matsiuk, O., Falat, P.: Cloud computing technologies in “smart city” projects. In: 9th International conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS), pp. 339–342. Romania, (2017). 21. Bomba, A., Nazaruk, M., Pasichnyk, V., Veretennikova, N., Kunanets, N.: Information technologies of modeling processes for preparation of professionals in smart cities. Advances in Intelligent Systems and Computing book series 754, 702–712 (2018). 22. Kazarian, A., Holoshchuk, R., Kunanets, N., Shestakevysh, T., Rzheuskyi, A.: Information support of scientific researches of virtual communities on the Platform of Cloud Services. Advances in Intelligent Systems and Computing III, vol.871, 301–311 (2018).