SOLVING OF RADIOELECTRONIC SYSTEMS COMBINATORIAL OPTIMIZATION PROBLEMS WITH MS EXCEL SOLVER
Journal Title: Вісник Національного університету "Львівська політехніка", серія "Радіоелектроніка та телекомунікації" - Year 2013, Vol 766, Issue 2013
Abstract
Possibilities of modelling optimization design problems as the extreme combinatorial graph problems and solving them in MS Excel Solver are studied. Drawbacks of existing models from considering their realization in MS Excel Solver are analyzed. As a result it is concluded that for forming a mathematical model of the optimization problem, suitable for realization in the environment of MS Excel Solver it is necessary to develop analytical presentation of an initial graph and minimum path between its arbitrary nodes, which, on the one hand, would adequately reflect the structure of initial graph and its minimum path, and, on the other hand, would satisfy the demands of problem presentation in the environment of MS Excel Solver of all versions, what requires to refuse the utilizing of function IF as well as other discontinuous functions. As a result, problem model based on graph incidence matrix is proposed. These model is in fact the graph enhanced incidence matrix, extension of which consists in including to the matrix a row corresponding to a base node. It is proved that in case of reflecting in this matrix a structure of any graph path the matrix content has to meet several conditions, namely: the sum of the modules of values for every matrix column, corresponding graph ribs included in a path, amounts 2; the sum of the modules of values for every matrix column, corresponding graph ribs out of a path, amounts 0; a sum of the modules of values in any matrix row equals to the degree of the node corresponding the row, and will take a value of 1 for initial and terminal vertexes, 2 – for the intermediate vertexes of the path and 0 for vertexes which don’t belong to the path. These features enable to set the objective function and constraints as sums of products of certain matrix cell values and sums of values in the rows or columns. Conversion of the absolute values of matrix cell values to real values of incidence matrix cells by multiplying the table of changing cells by incidence matrix as well as conversion of real values of incidence matrix cell to absolute one by squaring them allows to apply the constraint of Boolean variable to changing cells without exploiting the discontinuous function ABS. The objective function and all constraints are presented by linear functions what makes the problem model extremely simple for solving by MS Excel Solver. The incidence matrix properties make it easy to set the technological constraint for number of wires (represented by graph ribs) to any lead (represented by graph vertex) by imposing the constraints on maximum value of corresponding node degree. Offered problem models based on graph incidence matrix enable to find extreme paths, either minimal or maximal, for directed and undirected graphs of any complexity.
Authors and Affiliations
Larysa Hlinenko, Volodymyr Fast
Keywords
Related Articles
- EP ID EP461005
- DOI -
- Views 130
- Downloads 0
DEVELOPMENT THE PROCESS OPTIMIZATION METHOD OF MANUFACTURING THE RADIO-ELECTRONIC EQUIPMENT WITH USING OPTIMIZATION PARETO-REGIONS
At the department of theoretical radioengineering and radiomeasurements of Lviv Polytechnic National university the theory and methods of modeling and a process optimization the quality assurance processes of the radio-e...
THE EXPANSION OF THE POSSIBILITIES OF THE SYSTEM PROGRAM FUNCTIONS MAOPCs FOR THE STUDY OF LINEAR PERIODICALLY-TIME-VARIABLE CIRCUITS
The system program function MAOPCs is designed to study multivariate analysis and optimization of state linear periodically-time-variable circuits. The architecture of the system MAOPCs is based on the principles of soft...
METHOD OF MULTIPLEXING OF TIMER SIGNAL STRUCTURES BASED ON OFDM TECHNOLOGY
The method of multiplexing of timer signal structures. based on OFDM technology was considered. This technology is used in many data transmission standards, both in wired channels - asymmetric digital subscriber line (AD...
ANALYSIS OF THE ENERGY BALANCE OF OPTICAL TRANSPORT NETWORK BASED ON THE TECHNOLOGICAL AND ARCHITECTURAL APPROACHES
In this paper presents the main approaches to improve energy efficiency of telecommunications network. The main attention is focused on technological and architectural approaches to reduce power consumption. Shown the co...
MODELLING OF THE PLASMONIC PROPERTIES OF NANOCOMPOSITE MATERIALS BASED ON DIAMOND-LIKE CARBON FILM AND SILVER NANOPARTICLES
Optical characteristics of nanocomposite materials have been modeled depends on materials of the nanoparticles and the matrix, the size and shape of nanoparticles. The optical constants of diamond-like carbon films doped...