Задача комбинаторной оптимизации: поиск оптимального производственного и транспортного плана при организации производства на новых территориях

Abstract

The purpose of this article is to solve one of the tasks of production activities. A company aims to expand individual production facilities and to subsequently determine output and transportation volumes from each of the outlets (local production sites, warehouses, etc.). The hypothesis is that a solution to the production problems can be found in a set of five linear programming problems: the production problem, the center placement problem, the flow problem, the time minimization problem, and the transportation problem. The paper presents the main algorithms for finding optimal solutions, formulates a complex task, builds a model and implements an algorithm for finding optimal solutions. It was shown that such a problem can be formulated in the framework of a complex linear programming problem. The model test is produced on 38 vertices with 16 entry points, 3 exit points. It is shown that such a task can be solved and visualized by means of the Matlab package. Modifications of the model and possible solution algorithms depending on the data sample size are considered. The developed model can be applied at an enterprise or at any production facility where the main task is to search for the optimal combinatorial version of goods, provided that ,first, production costs and the costs of transportation of finished products are minimized and, second, profit is at a maximum. Third, the cost of launching opening new production facilities are kept at a minimum. Such a task corresponds exactly to the economic situation, when the enterprise has yet to expand (open new production sites), and it tries to decide where to produce items from its list of products and determine its output considering the available raw materials and decide on dispatch methods. Such a problem is non-trivial combinatorial in nature.

Целью данной статьи является решение одной из нетривиальных задач производственной деятельности, возникшее на предприятии лесной направленности. Предприятие ставит целью расширение отдельных пунктов производства с последующим определением: объемов производства и транспортировки с каждой из точек (мест производства, складов и т. д.). Гипотеза заключается в том, что решение такой производственной проблемы лежит в комплексном решении пяти задач линейного программирования: производственная задача (классическая постановка), задача размещения центров, задача максимального потока, задачи минимизации времени, транспортная задача. В работе представлены основные алгоритмы поиска оптимального решения, сформулирована комплексная задача, построена модель и реализован алгоритм поиска оптимального решения. Было показано, что такую задачу возможно сформулировать в рамках комплексной задачи линейного программирования. Тест модели произведен на 38 вершинах с 16 пунктами входа, 3 пунктами выхода. Показано, что такую задачу возможно решать и визуализировать средствами пакета Matlab. Рассмотрены модификации модели и возможные алгоритмы решения в зависимости от объема выборки данных. Разработанная модель может быть применена на предприятии любой производственной направленности, где стоит главной задачей поиск оптимального комбинаторного варианта вектора товаров при условии, во-первых, минимизации производственных издержек и затрат на транспортировку готовой продукции, во-вторых, получения максимальной прибыли, в-третьих, минимальных издержек при открытии новых пунктов производства. Такая задача в точности подходит к экономической ситуации, когда предприятию еще предстоит расшириться (открыть новые пункты производства), и оно осуществляет попытки по определению мест производства из рассматриваемого списка, объема производства из имеющегося в наличии сырья, способа отправки (как можно больше товара). Такая проблема носит характер нетривиально комбинаторный.