Efficient Algorithms of Linear Optimization Problems Solution Sergiy Chernova, Sergiy Titova, Ludmila Chernovaa, Nataliia Kunanetsb,c, Lubava Chernovaa, Varvara Piterskad, Yuriy Shcherbynaс and Lubomyr Petryshyne a Admiral Makarov National University of Shipbuilding, Heroiv Ukrainy ave 9, Mykolaiv, 54025, Ukraine b Lviv Polytechnic National University, Stepana Bandery Street 32-a, Lviv, 79013, Ukraine c Ivan Franko National University of Lviv, Universutetska Street 1, Lviv, 79000, Ukraine d Odesa National Maritime University, Mechnikova Street 34, Odesa, 65029, Ukraine e AGH University of Science and Technology, 30 Mickiewicza str., Cracow, 30-059, Poland Abstract The modern approaches to selection of a project lifecycle model are based in many cases on the use of iteration that can be reduced to linear optimization (LO) problems. For study and solution of such problems, researchers use the program library of such well-known software packages as Mathematica®, Maple® and MathCad®. Computer-aided calculations allow solving complicated types of combinatorial integer linear optimization problems and help to solve large-scale problems as well. The known methods of exact or approximate solution of such problems are studied with account taken of the fact that they belong to so-called P- or NP-class problems (polynomial or exponential solution algorithms). In view of this, the modern computer-based methods for practical solution of discrete linear optimization problems require development of algorithms that allow obtaining an approximate solution with guaranteed estimate of deviation from the target function optimum. For such problems, it is very important to improve (to simplify) the mathematic model itself, which has to be prepared before the beginning of computer calculation. This practical reasonability for a wide range of LO problems promotes developing new efficient and improving the existing algorithms of preparing for computer calculations. Application of such algorithms will considerably reduce the duration of computer calculation and hardware requirements to the computer. The subject of this research is development of a chain of efficient algorithms to simplify the initial mathematic model of problem and its computer calculation. Construction of efficient algorithms and general principles of preparing for computer solution of LO problems with their illustrations on various project management model problems is the objective of this research. Keywords 1 Linear optimization, polyhedron, target function, simplex method, basis vectors, primary plan, reference plan, polyhedron apex, reduction, duality. 1 Introduction The quality is managed during the whole project lifecycle. All of its stages and elements have to be analyzed. This process provides for availability of project, organizational and management decisions aimed at assurance of quality in fulfillment of processes in the course of project implementation. The management of quality is realized through compliance with specified requirements and international standards for quality of information systems, through the system of control and support of quality in the process of development. Efficient construction of a quality management model provides for use of various project management approaches [16-20]. Modern mathematic models of project management processes description can be reduced in many cases to linear optimization (LO) problems [1,2]. For study and solution of such problems, researchers Proceedings of the 2nd International Workshop IT Project Management (ITPM 2021), February 16-18, 2021, Slavsko, Lviv region, Ukraine EMAIL: 19chsk56@gmail.com (A.1); ss1-ss10@rambler.ru (A.2); lyudmylachernova@gmail.com (A.3); nek.lviv@gmail.com (A.4); 19chls92@gmail.com (A.5); varuwa@ukr.net (A.6); yshcherbyna@yahoo.com (A.7); l.b.petryshyn@gmail.com (A.8) ORCID: 0000-0002-9069-0409 (A.1); 0000-0001-8772-9889 (A.2); 0000-0002-0666-0742 (A.3); 0000-0003-3007-2462 (A.4); 0000-0001- 7846-9034 (A.5); 0000-0001-5849-9033 (A.6); 0000-0002-4942-2787 (A.7); 0000-0003-4168-3891 (A.8) ©️ 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings (CEUR-WS.org) use the subprogram library of such well-known software packages as Mathematica®, Maple® and MathCad®. Computer-aided calculations allow solving complicated types of combinatorial integer linear optimization problems and help to solve large-scale problems as well [10,12]. For such problems, it is very important to improve (to simplify) the mathematic model itself, which has to be prepared before the beginning of computer calculation. This practical reasonability for a wide range of LO problems promotes developing new efficient and improving the existing algorithms of preparing for computer calculations [15]. Application of such algorithms will considerably reduce the duration of computer calculation and hardware requirements to the computer. The subject of this research is development of a chain of efficient algorithms to simplify the initial mathematic model of problem and its computer calculation. 2 Research paper study and problem statement In multiple cases, mathematic models of active systems management are interpreted in the form of linear optimization problems [1–3,12,13]. Preparing for LO problems solution can be simplified based on using the notion of “duality”. A couple of dual problems formed according to certain rules allows a researcher to select one of them that is simpler in its computer calculation. Simplification algorithms provide an efficient method of searching for solution of an optimization problem. If we project a multidimensional process onto a two-dimensional plane, this method will enable graphic visualization of the problem solution sets. This research has proposed a method of simplifying the combinatorial solution of a discrete optimization problem. It is based on decomposition of the system representing a system of constraints of a five-dimensional initial problem into the two-dimensional coordinate plane. Such method allows obtaining a simple system of graphic solutions to a complicated linear discrete optimization problem. From the practical point of view, the method proposed allows simplifying the calculation complexity of optimization problems belonging to this class. Solution of linear optimization problems is based on algorithm of the classic or a common simplex method. It consists in intellectual iteration over polyhedron apexes  I (allowable area of optimization problem). The plan or an apex of polyhedron  I is specified by a system n of basis vectors a1 , a2 , , an . The number of possible apexes of polyhedron equals to the number of combinations Сnm (n – problem measurability, and m = rang ( I ) ). Real linear optimization problems that interpret models of management are characterized by big values of m. In view of this, we had to develop an algorithm ensuring ordered iteration over angular points of the polyhedron. Such a method was developed [1, 2] and is called simplex method. It allows obtaining the optimum optimization problem solution from the known primary reference plan X 0 , within a finite number of steps. Each iteration step of a simplex method corresponds to a new plan improving the target function value. The algorithmic process continues until finding the optimum value of target function or the absence of optimization problem solution. The number of simplex method iterations is determined by the primary reference plan X0 and the number of angular points  . As there are several “ways” of transition from X0 to the optimum Xopt , we I encounter the need to find the shortest (in terms of the number of apexes) “way” of iteration. Now there are not any publications with such assessments and their correlation to the classic simplex method algorithm. 3 The objective and the tasks of research The research objective provides for use and development of efficient algorithms and preparing mathematic models of the LO theory with further realization of their solution with the help of computer. For achievement of the objective stated, the following tasks were specified: • Provide the general problem statement for construction of efficient algorithms; • Give model examples illustrating the efficiency of algorithms at the stage of computer calculation. 4 General statement of a solution simplification problem. Use of the duality theory in Linear Optimization problems The intensity in development of modern information technologies results in complication of information systems for various sectors of public activities, implementation of IT projects on their development. Big IT projects are characterized by: • complexity of description, the need for thorough modeling and analysis of data and processes; • a big number of interlinks between the components (subsystems); • the impossibility to use typical project solutions; • the need for agreement with applications available in the market; • different levels of developers’ qualification and a wide range of tools and means of development; • growing project scale through involvement of developer teams. The modern approaches to construction of information systems are determined by complexity of defining the total scope of data and analytical tasks of the project. Developers use to define and analyze the requirements to an information system during the whole lifecycle of its development. Certainly, a project lifecycle model depends on complexity of the software product to be created. For development of complicated information systems, the most frequent use is found by the iteration model providing for division of the project lifecycle into a certain sequence of iterations each of which is presented as a “mini-project”. The objective of each iteration is to achieve getting a functional version of information system including supplements and realized modifications introduced at previous iterations. The final iteration result includes all necessary product functionality. After each iteration, the information system acquires some growth, i.e. some evolutional development. Projects on development of complicated information systems the architecture of which includes a set of components where each component can have several versions encounter the problem of studying their interrelation with the purpose of creating a unified structure and assuring development of the whole system. The said model contributes to systemic approach to information system development with due control and account taken of changes introduced at all stages of the lifecycle. Reduction in the number of iterations is provided by the use of linear optimization problems. Linear optimization that was already determined for a long time as a separate part of the optimization theory in most cases applies sustainable classic algorithms for solution of its problems [1–6]. Typical problems include such steps of a classic algorithm as: obtaining the primary reference plan, constructing a chain of reference plans, evaluation of their optimality, improving the plan and the target function value [7–11]. Each of the reference plans has a set of linearly independent basis vectors. Transition to a new basis that is nothing more than a transition to the neighbor polyhedron apex along its edge is affected within a rigorous algorithm. According to the simplex method algorithm theory, this transition is to be carried out in the direction of the best alteration of the target function values [12,13]. Such a “firm” calculation requirement to an algorithm results in some linear optimization problems in appearance of a too big number of iterations as compared to transition not to the neighbor apex but to another one that can be determined by additional requirements. Algorithms of preparing a LO problem for computer calculation can be essentially simplified through using the notion of “duality” in LO problems [9,10]. The existing patterns of transition from primal problem to a dual one enables easy creation of a dual problem couple. Formalizing the classic pattern of constructing a dual problem, we obtain couples of mutually dual problems. This, in its turn, allows selecting the simplest problem in terms of calculation for the further solution. Let us consider the most common case of presenting a primal LO problem in the form of a general LO problem WI = C X → max,  A  A12   X 1      B1  I:  I :  11       ,  A21 A22   X 2   =   B2   x j  0, j = 1, 2,..., l , (1) or in extended form of record n WI =  c j x j → max, j =1  n   a x  b , i = 1, 2, 3,...k , ij j i  j =1 I:  I :  n    a x = b , i = k + 1, k + 2, k + 3,...m, ij j i  j =1 x j  0, j = 1, 2,..., l. (2) A problem of the following form is called dual to it: WII = Y B → min,   A A12     C1  II:  II :  ( Y1 Y2 )  11     ,    A21 A22   =   C2  yi  0, i = 1, 2,..., k , (3) or in other form of record m WI I =  bi y i → min, i =1  m   y a  c , j = 1, 2, 3,...l , i =1 i ij j (4) II :  II :  m   y a = c , i = l + 1, l + 2, l + 3,...n,  i ij i i =1 y i  0, i = 1, 2,..., k . 4.1 Model Example No. 1 A dual problem is to be constructed for the following primal linear optimization problem: WI = x1 + 2 x2 − x3 + 7 x4 − x5 → max, 3 x1 + 2 x2 − x3 + 2 x4 + x5  12,  I:  I :  x1 − x2 + 8 x3 − x4 + 7 x5  1,  x + 4 x + x − 2 x − x = 8,  1 2 3 4 5 x1  0, x2  0, x3  0, x4  0, (5) S o l u t i o n . For the beginning of transition to dual problem, we prepare the system of constraints of a primal problem – for a maximization problem, we only need inequalities  . We reverse the sign of the first inequality. WI = x1 + 2 x2 − x3 + 7 x4 − x5 → max,  −3 x1 − 2 x2 + x3 − 2 x4 − x5  −12,  I:  I :  x1 − x2 + 8 x3 − x4 + 7 x5  1,  x + 4 x + x − 2 x − x = 8,  1 2 3 4 5 x1  0, x2  0, x3  0, x4  0. (6) Transition to dual problem is presented in Table 1. Table 1. Transition to dual problem for model example №1 Y\X x1  0 x2  0 x3  0 x4  0 x5 ? B y1  0 –3 –2 1 –2 –1  –12 y2  0 1 –1 8 –1 7  1 y3 1 4 1 –2 –1 = 8 ?     = C 1 2 –1 7 –1 The dual problem has the following form: WII = −12 y1 + y2 + 8 y3 → min, −3y1 − y2 + y3 − y4  1, −2y − y + 4 y  2,   1 2 3 II:  II :  y1 + 8 y2 + y3  −1, −2 y − y − 2 y  7,  1 2 3 − y1 + 7 y2 − y3 = −1,  y1  0, y2  0. (7) The dual problem can be reduced to a two-dimensional one. Actually, in case of excluding y3 from the system equation, we will only have two variables: y1 and y2 . Solution of the primal problem is to be found under condition of the known theorems of duality [4,5]. 4.2 Reduction in general Linear Optimization problems Let us have a general linear optimization problem in the form: n WI =  c j x j → max, j =1  a x b, n  j i i = 1,  , k ,  j =1 i j I :  n  ai j x j = bi , i = k + 1,  , m,  j =1 x j  0, j = 1,  , l. (8) We know that such a problem can always be reduced to the canonical form of record: 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, (9) We have to remember that linear optimization problems have equivalent forms – they reserve their set of solutions. This can be achieved under the condition of using transformation methods for transition from one form of problems to the other. Thus, the equation of system of constraints to a linear optimization problem is equivalent to the system of two inequalities:  n   ai j x j  bi , n  j =1  ai j x j = bi   n − a x  −b .   j =1 ij j i j =1 (10) Variables with arbitrary sign can be presented in the form of difference of 2 nonnegative variables: xj = uj −vj, u j  0, v j  0. (11) Transition from constraints – inequalities to constraints – equations is made by adding a nonnegative (balancing) variable: n n a x  b  a x + x j =1 ij j j j =1 ij j n +i = bi , xn+i  0, i = 1, , k . (12) For simplification of linear optimization problems transformation, we can also use the transition from maximization to minimization of the target function and vice versa: n n WI =  c j x j → max  WI = − c j x j → min j =1 j =1 (13) In view of this, without loss of generality, let us have a linear discrete optimization problem presented in canonical form: WI = CX → max  I : A X = B, X  0, (14) where the rank of the system of constraints coefficient matrix is equal to rang A = m . In this case, solving the system by Gauss-Jordan method with arbitrary basis combination of variables, we obtain a projection of n-dimensional initial problem to (n-m) – dimensional space. In case n - m = 2, we have projecting to the two-dimensional plane. Let us consider a model example of solving a five-dimensional linear optimization problem based on such projecting of a multidimensional space onto the two-dimensional one. 4.3 Model Example No. 3 Solution of the following linear optimization problem using the simplification algorithm WI = 13x1 + 7 x 2 + 2 x3 − x 4 + 2 x5 → max,  10 x1 + 10 x 2 + x3 + x 4 + x5 = 179,  (15)  I :  19 x1 + 14 x 2 + x3 + 2 x 4 + 2 x5 = 298,  4 x + 5 x + x = 69,  1 2 4 x1  0, x 2  0, x3  0, x 4  0, x5  0. S o l u t i o n . The system of constraints (15) consists of three independent equations. We move from the canonical problem presentation form to the standard one. Such transition is made by solving the system (15) by the Gauss-Jordan method (Table 2). As basis variables, we select the following three: x3, x4, x5. Table 2 Calculation under basis x3, x4, x5 x1 x2 x3 x4 x5 b ∑ 10 10 1 1 1 179 202 19 14 1 2 2 298 336 4 5 0 1 0 69 79 WI 13 7 2 -1 2 151 10 10 1 1 1 179 202 -1 −6 −1 0 0 −60 −68 4 5 0 1 0 69 79 WI -7 −13 0 −3 0 −207 9 4 0 1 1 119 134 1 6 1 0 0 60 68 4 5 0 1 0 69 79 WI -7 −13 0 −3 0 −207 5 −1 0 0 1 50 55 1 6 1 0 0 60 68 4 5 0 1 0 69 79 WI 5 2 0 0 0 0 From the last chain of Table 2, we obtain the solved system. 4 x1 + 5 x2 + x3 = 69,  5 x1 − x2 + x4 = 50, (16)  x + 6 x + x = 60. 1 2 5 Dropping the basis variables, we provide a transition to two-dimensional inequalities. Projection of the five-dimensional initial problem onto the coordinate plane Ox1x2 has the following form: WI = 4 x1 + 5 x2 → max, 4 x1 + 5 x2  69,   Ox1 x2 I : 5 x1 − x2  50,  x + 6 x  60,  1 2 x1  0, x2  0. (17) The graphic solution is given on Figure 1. Figure 1: Projection to Ox1x2. The extreme apex coordinates provide the solution of the system 4 x1 + 5 x2 = 69,  x = 11, max : ω1  ω 2   X opt  1 5 x1 − x2 = 50,  x2 = 5. (18) We can obtain the other coordinates from the solved system (17). Therefore, the optimum solution of the initial problem is equal to  max = 11, 5, 19, 0, 0 X opt . (19) The biggest value of the target function will be WImax = 65 . Note. Three variables can be selected from five by ten methods C 53 = 10 . We consider another combination from possible ones to reduce the problem. We select x2, x3, x4 to be our basis variables. Let us solve the initial system of constraints to variables x2, x3, x4 by Gauss-Jordan method (Table 3), but using system (17) equivalent to system (18). Table 3 Calculation under basis x2, x3, x4 x1 x2 x3 x4 x5 b ∑ 5 −1 0 0 1 50 55 1 6 1 0 0 60 68 4 5 0 1 0 69 79 WI 5 2 0 0 0 0 -5 1 0 0 −1 −50 −55 31 0 1 0 6 360 398 29 0 0 1 5 319 354 WI 15 0 0 0 2 100 Table 3 provides the solved system with basis variables x2, x3, x4, −5 x1 − x5 + x2 = −50,  31x1 + 6 x5 + x3 = 360, 29 x + 5 x + x = 319.  1 5 4 (20) Ignoring nonnegative basis variables x2, x3, x4 we perform a transition to constraints-inequalities. The projection of a five-dimensional polyhedron of initial problem (15) to coordinate plane Ox1x5, or an equivalent transition from the canonical form of LO problem to the standard one looks like: WI = 15 x1 + 2 x5 − 100 → max − 5 x1 − x5  −50,  IOx1 x5 : 31x1 + 6 x5  360, 29 x + 5 x  319,  1 5 0  x1 ,0  x5 . (21) Graphic solution of the problem is given on Figure 2, where ω1 : 5 x1 + x5 = 50 , ω 2 : 31x1 + 6 x5 = 360 , ω3 : 29x1 + 5x5 = 319 , ω 4 : x2 = 0 , ω5 : x1 = 0 . Figure 2: Projection to Ox1x5 The optimum apex has coordinates x1 = 11 , x5 = 0 . We calculate coordinates x2, x3, x4 from system (21). Finally, X max opt =  11, 5, 19, 0, 0  . The obtained optimum solution matches the previous ones, which confirms the calculations carried out to be correct. 4.4 Acceleration of the Linear Optimization problem solution convergence In most cases, solution of linear optimization problems is searched for by the simplex method. However, this classic algorithm of linear optimization problems solution may create additional iterations in the immediate process of calculation. If we break some components of the standard simplex method algorithm, we can accelerate the convergence of simplex calculation – reduce the number of simplex tables. For acceleration of the simplex method convergence, it is proposed to deviate from the canonical algorithm. It is required to choose not the neighbor apex as the next problem plan, but the verified apex selected according to evaluation of the biggest and the smallest target function values. We consider the general approach to solution of a linear optimization problem according to the classic simplex method algorithm [1,2,3]. Without loss of generality, let us have a linear optimization problem in the standard form of record 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, (22) where bi  0, i = 1, 2, , m. Adding a balancing nonnegative variable xi  0, i = n + 1, n + 2, , n + m to each inequality and recoding the problem in vector form allow obtaining the canonical form of an optimization problem record WI = (c, x) → max,  I : (a j , x) = b, x  0, (23) or in extended form of record: x1a1 + x2a 2 + + xma m + xm +1a m +1 + + xna n = b, (24) where x =  x1 , x2 , , xn  , X  R n , c =  c1 , c2 , , cn  , T a1 =  a11 , a21 , , am1  , a 2 =  a12 , a22 , , am 2  , , a n =  a1n , a2 n , , amn  , T T T a n+1 = e n+1 =  1, 0, , 0  , a n+ 2 = e n+ 2 =  0, 1, ,0 , , a n+ m = e n+ m =  0, 0, , 1  , b =  b1 , b2 , , bm  . T T T T Vectors a n +1 , a n + 2 , , a n + m are unit vectors. These vectors are linearly independent and constitute the basis. The right sides vector resolution of the optimization problem set of constraints has the following form: b = b1e n +1 + b2e n + 2 + + bme n + m (25) As all bi  0 , we obtain the allowable primary reference plan X0 . The following basis resolution corresponds to the primary plan. X0 = b1e n+1 + b2e n+ 2 + + bme n+ m = [0,0, ,0, b1 , b2 , , bm ] (26) n The main idea of using the simplex method algorithm is sequential iteration over allowable reference plans. One vector is excluded from and another included to the basis by the Gauss-Jordan method [14]. Subject to compliance with these criteria, we have to build a chain. The beginning of the chain is located at the starting apex X of polyhedron  I and corresponds to the first simplex table of 0 calculation. Moving to the next reference plan X1 by following the classic algorithm corresponds to transition to the neighbor apex. Actually, each table is a numeric description of apexes  I . The process is to be continued till finding the optimum apex Xopt or confirming its absence. At the arbitrary step of calculation by following the common simplex method algorithm, we have the possibility to move not to the neighbor apex, but to the arbitrary apex located around the optimum apex. Such an apex can be selected based on multiple evaluation methods, e.g. the half-interval method. For this selection, the alternative chain of simplex calculation may have a much smaller number of iterations. Let us consider a model example of a two-dimensional linear optimization problem solution to confirm this case, first by following the standard procedure and then by breaking the rule of basis vectors combination selection. 4.5 Model Example № 5 LO problem solution WI = 2 x1 + 3 x2 → max, 3x1 − 4 x2  6,  x + 2 x  12,  I :  1 2  1 2  3, − x + x  x2  4, x j  0, j = 1, , 4. (27) S o l u t i o n . Basis nonnegative unknowns are to be added to left sides of each inequality. As a x3, x4, x5, x6 result, we obtain the canonical form of a linear optimization problem: WI = 2 x1 + 3 x2 → max, 3x1 − 4 x2 + x3 = 6,  x + 2 x + x = 12,  1 I :  2 4  1 2 5 = 3, − x + x + x  x2 + x6 = 4, x j  0, j = 1, , 6. (28) We have the primary reference plan X0 =  0, 0, 6, 12, 3, 4    I . Let us draw the reference simplex table (Table 4). Table 4 Simplex table vertex X0 a1 a2 a3 a4 a5 a6 C B 2 3 0 0 0 0 Basis a3 0 6 3 −4 1 0 0 0 a4 0 12 1 2 0 1 0 0 a5 0 3 −1 1 0 0 1 0 a6 0 4 0 1 0 0 0 1 Dj WI = 0 -2 -3 0 0 0 0 Index row  j has two negative evaluations meaning that plan X0 =  0, 0, 6, 12, 3, 4    I is not optimum and can be improved. The pivot column can be found by the rule of selecting the smallest negative value of evaluations. This is column а 2 as min −2, −3 = −3 → a 2 . The pivot row is to be set by the rule of selecting the smallest simplex ratio for positive components of the pivot column. We have  bi   12 3 4   ai 2  0, i = 4, 5, 6  = min  , ,  = 3 → a5  i2a   2 1 1  (29) Our solving element is a52 = 1 . For it, we make a Gauss-Jordan transformation and by following the algorithm we select (Table 5): Table 5 Simplex table vertex X1 a1 a2 a3 a4 a5 a6 C B 2 3 0 0 0 0 Basis a3 0 18 −1 0 1 0 4 0 a4 0 6 3 0 0 1 -2 0 a2 3 3 −1 1 0 0 1 0 a6 0 1 1 0 0 0 −1 1 Dj WI = 9 -5 0 0 0 3 0 From the table (Table 5): X1 =  0, 3, 18, 6, 0, 1  , WI ( X1 ) = 9 (30) The index row  j has a negative evaluation. Plan X1 =  0, 3, 18, 6, 0, 1  is not optimum and it can be improved. The pivot column is а 2 , as only this column contains negative evaluation 1 = −5 . We select a pivot row from the condition of the smallest simplex ratio for positive components of the pivot column. We have  bi   6 1   ai1  0, i = 4, 6  = min  ,  =  2, 1  = 1 → а 6  ai1   3 1  (31) In the new basis, instead of а 6 we involve а1 . After respective calculation, we have the third simplex table (Table 6). Table 6. Simplex table vertex X2 a1 a2 a3 a4 a5 a6 Basis C B 2 3 0 0 0 0 a3 0 19 0 0 1 0 3 1 a4 0 3 0 0 0 1 1 −3 a2 3 4 0 1 0 0 0 1 a1 2 1 1 0 0 0 −1 1 Dj WI = 14 0 0 0 0 -2 5 From the table (Table 6): X 2 =  1, 4, 19, 3, 0, 0  WI ( X 2 ) = 14 , (32) The index row  j has a negative evaluation. Plan X2 =  1, 4, 19, 3, 0, 0  is not optimum and can be improved. The pivot column is а5 , as only this column contains negative evaluation 5 = −5 . We select the pivot row by the condition of the smallest simplex ratio for positive components of the pivot column. We have  bi   19 3   ai 5  0, i = 3, 4  = min  ,  = 3 → а4  ai 5   3 1  (33) In the new basis, instead of а 4 we involve а5 . After respective calculation, we have the fourth simplex table (Table 7). Table 7 Simplex table vertex X3 a1 a2 a3 a4 a5 a6 C B       Basis a3      −   a5        − a2         a1        − j WI =       − From the fourth table (Table 7): X3 =  4, 4, 10, 0, 3, 0  , WI ( X3 ) = 20 The index row  j has a negative evaluation. Plan X3 =  4, 4, 10, 0, 3, 0  is not optimum and can be improved. Our pivot column will be а 6 , as only this column contains negative evaluation  6 = −1. We select the pivot row by the condition of the smallest simplex ratio for positive components of the pivot column. We have  bi   4 10   ai 6  0, i = 2, 3  = min  ,  = 1 → а3  ai 6   1 10  (34) In the new basis, instead of а3 , we involve а 6 . After respective calculation, we have the fifth simplex table (Table 8). Table 8 Simplex table vertex Xopt a1 a2 a3 a4 a5 a6 C B 2 3 0 0 0 0 Basis a6 0 1 0 0 1/10 ̶ 3/10 0 1 a5 0 6 0 0 3/10 1/10 1 0 a2 3 3 0 1 ̶ 1/10 3/10 0 0 a1 2 6 1 0 1/5 2/5 0 0 Dj WI = 21 0 0 1/10 17/10 0 0 All evaluations are nonnegative  j  0 . This means that we have found the optimum solution. Xopt =  6, 3  WI ( Xopt ) = 21 , (35) Therefore, the calculation within the classis simplex calculus contains the following chain of sequential iteration over apexes  I : X0 → X1 → X 2 → X3 → Xopt . (36) Let us confirm that breaking the canonical simplex method algorithm can essentially reduce the length of the calculation chain – the number of simplex tables. We break the algorithm at the first step. We are not selecting the smallest evaluation like in the common simplex method, but the biggest one. Respective calculation is given in Table 9. Table 9 Alternative simplex algorithm a1 a2 a3 a4 a5 a6 Basis C B 2 3 0 0 0 0 a3 0 6 3 ̶4 1 0 0 0 a4 0 12 1 2 0 1 0 0 a5 0 3 ̶1 1 0 0 1 0 a6 0 4 0 1 0 0 0 1 Dj WI = 0 ̶2 ̶3 0 0 0 0 a3 0 ̶ 30 0 ̶ 10 1 -3 0 0 a1 2 12 1 2 0 1 0 0 a5 0 15 0 3 0 1 1 0 a6 0 4 0 1 0 0 0 1 Dj WI= 24 0 1 0 2 0 0 a2 3 3 0 1 ̶ 1/10 3/10 0 0 a1 2 6 1 0 1/5 2/5 0 0 a5 0 6 0 0 3/10 1/10 1 0 a6 0 1 0 0 1/10 ̶ 3/10 0 1 Dj WI = 21 0 0 1/10 17/10 0 0 The length of calculation chain has been almost twice reduced - X0 → X 4 → Xopt . The problem considered is two-dimensional. Therefore, we can perform a graphical solution providing us with geometric interpretation of the problem calculation chains. We set up an equation of limit lines ω1 : 3 x1 − 4 x2 = 6, ω2 : x1 + 2 x2 = 12, ω3: − x1 + x2 = 3, ω4 : x2 = 4, ω5 : x1 = 0, ω6 : x2 = 0 , and set semi- planes determined by respective inequalities of the set of constraints. As a result, we can draw polyhedron  I (Fig. 3). Figure 3: Interpretation of compliance with the classic simplex method algorithm and of breaking it At the coordinate origin point, we draw the gradient vector grad(WI ) =  2, 3  . Perpendicularly to it, we draw the level line. Moving the line in parallel to itself in the gradient direction, we set the maximum point Xopt - the apex of the level lines outreach (Figure 3). The coordinates of the extreme apex are found as coordinates of the crossing point of respective limit lines: 3 x − 4 x2 = 6,  x = 6, Xopt : ω1  ω2   1  1  x1 + 2 x2 = 12,  x2 = 3. (37) Therefore, the target function reaches its maximum value at the apex Xopt =  6, 3  and it is equal to WI ( Xopt ) = 21.The geometric interpretation of the classic simplex calculation consists in the fact that the first simplex table (Table 4) corresponds to apex X0 . The calculation up to the second table (Table 5) corresponds to transition to the neighbor apex X1 , in the direction of the biggest target function growth. The third, the fourth and the fifth simplex tables (Table 6, Table 7, Table 8) correspond to transition X1 → X 2 → X3 → X opt (Figure 3). Therefore, for solving the problem by following the classic algorithm, we need to set up five simplex tables. For reducing the number of iterations, we break this algorithm and select not the smallest but the biggest negative evaluation 1 = −2 in the initial simplex table. The further calculation is given in Table 9. As we can see, the number of simplex tables has been reduced from five to three. 5 Research results and summary The illustrative examples of searching for efficient algorithms of preparing for calculation of an optimization problem based on using the notion of “duality” problem reduction and the method of breaking the standard simplex algorithm have visually demonstrated the reasonability of such methods in solution of linear optimization problems. From the practical point of view, the proposed approaches allow simplifying the calculation complexity of problems belonging to this class. Based on comparative solutions of model problems, it has been shown that initial problems can be essentially simplified. The research result obtained allows arriving at the conclusion that in the common case, it is reasonable to search for breakage of the algorithm of standard algorithmic patterns currently created. The application value of the proposed approach consists in using the obtained scientific result for assurance of the possibility improve the canonical methods of optimization problems solution and, accordingly, simplifying the computer calculation using libraries of standard subprograms within the well-known mathematical packages. Conclusions It has been shown that there are classes of linear optimization problems for which it is reasonable to search for more efficient algorithms with the purpose of preparing Linear Optimization problems for computer calculation. It has been proved on the example of illustrative solution of typical model problems that the proposed approach allows us to essentially simplify the initial model for obtaining the solution of Linear Optimization problems in project management. References [1] J. Dantsig, Linear Programming and Extensions, Progress. Moscow, 1966. [2] L. Kantorovich, A. Gorstko, Optimum Solutions in Economics, Nauka, Moscow, 1972. [3] N. Unger, S. Dempe, Lineare Optimierung, Springer, Wiesbaden, 2010. [4] V. Hetmantsev, Linear Algebra and Linear Programming, Lybid, Kyiv, 2001. [5] I. Bahaienko, V. Hryhorkiv, M. Boichuk, M. Riumshyn, Mathematic Programming, Logos, Kyiv, 1996. [6] G. Teschl, Teschl Susanne, Mathematik für Informatiker. Band 1: Diskrete Mathematik und Lineare Algebra, Springer, Berlin, 2008. [7] M. Buhir, Linear Algebra, Linear Models, Akademia, Kyiv, 1998. [8] M. Gavurin, V. Malozemov, Extreme Problems with Linear Constraints, LGU, Leningrad, 1984. [9] S. Ashmanov, Linear Programming. Chief Ed. Board of Phys. & Math. Lit, Moscow, 1981. [10] I. Sigal, A. Ivanova, Introduction to Applied Discrete Programming: Models and Calculation Algorithms, Physmathlit, Moscow, 2003. [11] A. Rzheuskyi, N. Kunanets, V. Kut, Methodology of research the library information services: the case of USA university libraries. Advances in Intelligent Systems and Computing 689 (2018) 450–460. doi:10.1007/978-3-319-70581-1_32. [12] T. Romaniuk, T. Tereshchenko, H. Prysenko, I. Horodkova, Mathematic Programming, Kyiv State University of Economics, Kyiv, 1996. [13] V. Stepaniuk, Methods of Mathematic Programming, Vyshcha Shkola, Kyiv, 1984. [14] S. Titov, L. Chernova, Higher and Applied Mathematics: Training Manual: in 2 Parts, part 1, Fakt, Kharkiv, 2017. [15] S. Chernov, S. Titov, Ld. Chernova, V. Gogunskii, Lb. Chernova, K. Kolesnikova, Algorithm for the Simplification of Solution to Discrete Optimization Problems, East Europ. J. of Enterprise Technol. 3/4 (93) (2018) 34–43. [16] Bondar, A., Bushuyev, S., Onyshchenko, S., Hiroshi, H.: Entropy Paradigm of Project-Oriented Organizations Management. Proceedings of the 1st International Workshop IT Project Management (ITPM 2020) Volume 1, p. 233-243. Lviv, Ukraine, February 18-20, 2020, CEUR Workshop Proceedings (2020) [17] Bushuyev S., Kozyr B., Rusan N. Modeling of Empathy, Emotional Intelligence and Transformational Leadership to the Project Success. Mathematical Modelling and Simulation of Systems. Advances in Intelligent Systems and Computing Book Series. Springer AG. vol. 972, P. 209-222. (2020) [18] Rzheuskyi, H. Matsuik, N. Veretennikova, R. Vaskiv, Selective Dissemination of Information – Technology of Information Support of Scientific Research. Advances in Intelligent Systems and Computing 871 (2019) 235–245. [19] V. Tomashevskyi, A. Yatsyshyn, V. Pasichnyk, N. Kunanets, A. Rzheuskyi, Data Warhouses of Hybrid Type: Features of Construction. Advances in Intelligent Systems and Computing book series 938 (2019) 325–334. [20] H. Lypak, V. Lytvyn, O. Lozynska, R. Vovnyanka, Y. Bolyubash, A. Rzheuskyi, D. Dosyn, Formation of Efficient Pipeline Operation Procedures Based on Ontological Approach. Advances in Intelligent Systems and Computing 871 (2019) 571–581.