Search

In the article, a modification of the r(α)-algorithm with adaptive line search which implements accelerated space dilation operation is considered. In classical r(α)-algorithm with adaptive line search, space is dilated along the difference of the two successive subgradients. In its modified variant, space is dilated along the direction which is determined by the largest absolute value components of the vector of difference of the two successive subgradients. The number of such components varies at each iteration of the algorithm and depends on a control parameter. Thus, at each iteration only corresponding subspace of a smaller dimension is dilated and the number of multiplication operations used for this decreases from 2n2 + 3n to 2nm + 2m + n, where n is the dimension of the space, m is the number of non-zero components of the space dilation direction. Description of the modified r(α)-algorithm with adaptive line search which implements accelerated space dilation operation is given. Results of the numerical experiments of minimization of the two classes of convex piecewise linear functions and quadratic strongly convex functions are presented. To solve the problems C++ implementations of the classical r(α)-algorithm with an adaptive line search ralgb5a and its modified version with accelerated space dilation ralgb5at were used. Obtained results show that for minimization of the piecewise linear functions compared with the classical r(α)-algorithm its modified version requires approximately the same number of iterations to converge but uses a significantly smaller number of multiplication operations. For minimization of the quadratic strongly convex functions modified r(α)-algorithm requires a smaller number of iterations to converge and as a result has a smaller execution time. Therefore, it is concluded that the variants of the r-algorithm that implements accelerated space dilation operation along directions which approximate the difference of the two successive subgradients may be quite promising since for some classes of functions they might better take into account the shape of the function’s ravines and with appropriate software implementation have a smaller execution time.

Introduction. When formulating the classical two-stage transportation problem, it is assumed that the product is transported from suppliers to consumers through intermediate points. Intermediary firms and various kinds of storage facilities (warehouses) can act as intermediate points. The article discusses two mathematical models for two-stage transportation problem (linear programming problem and quadratic programming problem) and a fairly universal way to solve them using modern software. It uses the description of the problem in the modeling language AMPL (A Mathematical Programming Language) and depends on which of the known programs is chosen to solve the problem of linear or quadratic programming. The purpose of the article is to propose the use of AMPL code for solving a linear programming two-stage transportation problem using modern software for linear programming problems, to formulate a mathematical model of a quadratic programming two-stage transportation problem and to investigate its properties. Results. The properties of two variants of a two-stage transportation problem are described: a linear programming problem and a quadratic programming problem. An AMPL code for solving a linear programming two-stage transportation problem using modern software for linear programming problems is given. The results of the calculation using Gurobi program for a linear programming two-stage transportation problem, which has many solutions, are presented and analyzed. A quadratic programming two-stage transportation problem was formulated and conditions were found under which it has unique solution. Conclusions. The developed AMPL-code for a linear programming two-stage transportation problem and its modification for a quadratic programming two-stage transportation problem can be used to solve various logistics transportation problems using modern software for solving mathematical programming problems. The developed AMPL code can be easily adapted to take into account the lower and upper bounds for the quantity of products transported from suppliers to intermediate points and from intermediate points to consumers.