Двоетапна транспортна задача з невідомими потребами споживачів
Loading...
Date
2022
Authors
Стецюк, Петро
Хом'як, Ольга
Ляшко, Володимир
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Досліджено математичну модель двоетапної транспортної задачі з невідомими потребами споживачів та заданими їхніми нижніми й верхніми межами. Її частковим випадком є класична двоетапна транспортна задача, яка визначає найбільш економічний план перевезення продукції від постачальників до споживачів через проміжні пункти. Наведено умови сумісності систем лінійних обмежень відповідних задач лінійного програмування. Розглянуто модельну задачу оптимального розбиття множини та наведено результати обчислювальних експериментів із використанням солвера Gurobi.
Description
The work investigates a mathematical model of a two-stage transportation problem for finding the most
economical plan for the transportation of homogeneous products from suppliers to consumers, where the
demands of consumers are unknown, taking into account constraints on their lower and upper bounds. It is
an extension of the classic two-stage transportation problem, where products are transported from suppliers
to consumers only through intermediate points. Intermediary firms and various storage facilities (warehouses)
can be such intermediate points.
The relationship of the developed mathematical model with the two-stage continuous-discrete problem
of optimal partitioning-distribution, which is characterized by the presence of two stages, is investigated.
The problem consists in determining the areas of collection of the continuously distributed resource (raw
material) by enterprises of the first stage and the volumes of transportation of the processed product from
the enterprises of the first stage to consumers (points of the second stage), in order to minimize the total
costs of transportation of the resource from suppliers to consumers through processing points (collection
points, storage points).
The material of the article is presented in two sections. Section 1 describes the mathematical model of
the two-stage transportation problem with unknown consumer demands and provides the necessary and
sufficient conditions for the compatibility of the system of linear constraints. It is shown that its special case
coincides with the classic two-stage transportation problem.
Section 2 provides a description of the model problem of optimal partitioning-distribution for the continuous
area Ω and the discrete analog of the model problem. The results of computational experiments for
a rectangular area Ω = {x = (x(1), x(2)) : 0 ≤ x(1) ≤ 1, 0 ≤ x(2) ≤ 1} with discretizations by grids 31 × 31 and
500 × 500 are presented. Optimal plans for transportation of processed product from points of the first stage
to points of the second stage for both grids were found. The average time spent by the Gurobi solver to solve
problems for the second grid, where the number of variables equals 250018 and the number of constraints
equals 250009, is a few seconds on modern PCs.
Keywords
двоетапна транспортна задача, задача лінійного програмування, Gurobi, оптимальне розбиття множини, стаття, two-stage transportation problem, linear programming problem, Gurobi, optimal set partition
Citation
Стецюк П. І. Двоетапна транспортна задача з невідомими потребами споживачів / Стецюк П. І., Хом'як О. М., Ляшко В. І. // Наукові записки НаУКМА. Комп'ютерні науки. - 2022. - Т. 5. - С. 92-96. - https://doi.org/10.18523/2617-3808.2022.5.92-96