2020, issue 4, p. 5-14
Received 21.10.2020; Revised 05.12.2020; Accepted 17.12.2020
Published 31.12.2020; First Online 22.01.2021
On Linear and Quadratic Two-Stage Transportation Problem
1 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
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.
Keywords: transportation problem, linear programming problem, AMPL modeling language, Gurobi program, quadratic programming problem.
Cite as: Stetsyuk P., Lykhovyd O., Suprun A. On Linear and Quadratic Two-Stage Transportation Problem. Cybernetics and Computer Technologies. 2020. 4. P. 5–14. (in Ukrainian) https://doi.org/10.34229/2707-451X.20.4.1
1. Karagodova O.O., Kigel V.R., Rozhok V.D. Operations Research: Navch. Posib. К.: Centr uchbovoi literatury, 2007. 256 p. (in Ukrainian)
2. Nakonechnyi C.I., Savina C.C. Mathematical programming: Navch. Posib. К.:KNEU, 2003. 452 p. (in Ukrainian)
3. Stetsyuk P.I., Liashko V.I., Mazutynetz G.V. Two-stage transportation problem and its AMPL-implementation. Naukovi zapysky NaUKMA. Kompiuterni nauky. 2018. 1. P. 14–20. (in Ukrainian) https://doi.org/10.18523/2617-3808.2018.14-20
4. Fourer R., Gay D., Kernighan B. AMPL, A Modeling Language for Mathematical Programming. Belmont: Duxburry Press, 2003. 517 p.
5. NEOS Solver. https://neos-server.org/neos/solvers/ (last accessed: 01.12.2020)
6. Gurobi Optimization, Inc., Gurobi Optimizer Reference Manual, 2014. https://www.gurobi.com/ (last accessed: 06.09.2020)
7. Grygorak M.Yu. Intellectualization of the logistics services market: concept, methodology, competence: monograph. Kyiv: Sik Grup Ukraine, 2017. 513 p. (in Ukrainian)
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)