TY - JOUR

T1 - Solution of mathematical programming problems using tropical optimization methods

AU - Кривулин, Николай Кимович

AU - Романовский, Иосиф Владимирович

PY - 2017/7/1

Y1 - 2017/7/1

N2 - This paper deals with a class of mathematical programming problems that includes linear and nonlinear programming problems in a particular form. First, a linear programming problem is considered, and the possibility of deriving its direct complete solution in terms of traditional mathematics without using known iterative computational procedures and algorithms of linear programming, such as the simplex method, is studied. Direct solutions to the problem in the case of minimal dimension with a reduced set of constraints are proposed. It is shown that the derivation of such solutions, as dimension increases, becomes a very complicated problem with increasing dimension and, therefore, is hardly feasible. Some examples of other linear and nonlinear programming problems, which can be obtained from the above-considered problem by means of isomorphic transformations, are presented. The main definitions and preliminary results of tropical mathematics, which are required for the subsequent description and application of tropical optimization methods, are then outlined. A tropical optimization problem is formulated, and direct complete solutions of this problem and of its special cases are given. The above-formulated linear and nonlinear programming problems are reduced to a tropical optimization problem to provide their direct complete solution in terms of tropical mathematics. The solution of the linear programming problem with a reduced set of constraints is written in terms of traditional mathematics.

AB - This paper deals with a class of mathematical programming problems that includes linear and nonlinear programming problems in a particular form. First, a linear programming problem is considered, and the possibility of deriving its direct complete solution in terms of traditional mathematics without using known iterative computational procedures and algorithms of linear programming, such as the simplex method, is studied. Direct solutions to the problem in the case of minimal dimension with a reduced set of constraints are proposed. It is shown that the derivation of such solutions, as dimension increases, becomes a very complicated problem with increasing dimension and, therefore, is hardly feasible. Some examples of other linear and nonlinear programming problems, which can be obtained from the above-considered problem by means of isomorphic transformations, are presented. The main definitions and preliminary results of tropical mathematics, which are required for the subsequent description and application of tropical optimization methods, are then outlined. A tropical optimization problem is formulated, and direct complete solutions of this problem and of its special cases are given. The above-formulated linear and nonlinear programming problems are reduced to a tropical optimization problem to provide their direct complete solution in terms of tropical mathematics. The solution of the linear programming problem with a reduced set of constraints is written in terms of traditional mathematics.

KW - mathematical programming

KW - linear programming

KW - tropical mathematics

KW - idempotent semifield

KW - tropical optimization

U2 - 10.3103/S1063454117030104

DO - 10.3103/S1063454117030104

M3 - Article

VL - 50

SP - 274

EP - 281

JO - Vestnik St. Petersburg University: Mathematics

JF - Vestnik St. Petersburg University: Mathematics

SN - 1063-4541

IS - 3

ER -