Розв’язання задач комбінаторної оптимізації радіоелектронних систем у середовищі MS EXCEL SOLVER

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 ofMS 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. Розглянуті можливості моделювання оптимізаційних задач проектування як екстремальних комбінаторних задач на графах та їх розв’язання у MS Excel Solver. Запропоновані моделі задач на основі аналітичного представлення графа його матрицею інциденцій, які забезпечують знаходження за допомогою MS Excel Solver екстремальних шляхів для орієнтованих та неорієнтованих графів довільної складності.