=Paper=
{{Paper
|id=Vol-2387/20190231
|storemode=property
|title=The Maple ® Symbolic Mathematics System in the Method of Projections for Discrete Optimization Problems
|pdfUrl=https://ceur-ws.org/Vol-2387/20190231.pdf
|volume=Vol-2387
|authors=Serhii Chernov,Serhii Titov,Liubava Chernova,Nataliia Kunanets
|dblpUrl=https://dblp.org/rec/conf/icteri/ChernovTCK19
}}
==The Maple ® Symbolic Mathematics System in the Method of Projections for Discrete Optimization Problems==
https://ceur-ws.org/Vol-2387/20190231.pdf
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 An1 An
An1 n
a B
j 1
j [cn1 , an1 ] [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 ]mn . 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 am1,n xn bm1,
m1,1 1 m1, 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 ]mn 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 ]mn
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 xni bi , xni 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
01
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).