Задача размещения двухэтапного производства с ограничениями на мощности предприятий первого этапа

Abstract

Задачи оптимального размещения предприятий - благодатная почва для разработки новых методов моделирования, инновационных алгоритмов решения и интересных применений. В статье описывается задача размещения двухэтапного производства с ограничениями на мощности предприятий первого этапа. Такие задачи возникают, например, при стратегическом планировании развития региона, решении задач оптимального размещении предприятий и определении зон их влияния, и представляют практический интерес для коммерческих (размещение складов, магазинов, точек обслуживания и пр.) и государственных (школы, больницы, пожарные станции и пр.) компаний. Целью работы является построение математической модели двухэтапной задачи оптимального размещения-распределения при наличии ограничений на мощность предприятий первого этапа, краткое описание метода ее решения и формулирование алгоритма решения. В качестве критерия оптимальности решения задачи размещения была выбрана совокупная стоимость доставки продукта. Методы решения основаны на принципах бесконечномерной оптимизации и теории двойственности. Подход к решению такой задачи основан на решении задачи оптимального разбиения множеств и дискретной многоэтапной задачи размещения. Единый подход к решению задач оптимального разбиения множеств заключается в преобразовании исходных задач в задачи бесконечномерного математического программирования с помощью характеристических функций, а затем в конечномерную задачу оптимизации с использованием функционала Лагранжа. Разработан итерационный алгоритм решения задачи. Он объединяет метод потенциалов, применяемый для классической задачи линейного программирования транспортного типа и алгоритм Н.З. Шора, позволяющий решить задачу оптимизации негладкой функции. Был разработан программный продукт для решения двухэтапных задач оптимального размещения предприятий с непрерывно распределенным ресурсом. Результаты, полученные авторами, позволяют решать ряд практических задач, связанных со стратегическим планированием в сфере производственной и социально-экономической деятельности.Facility location problems are a fertile ground for the development of new modelling techniques, innovative solution algorithms and exciting applications. The article describes a problem of placing a two-stage production with restrictions on the capacity of the first stage enterprises. Such problems arise, for example, in strategic planning of development of the region. The problems of optimal placement companies and identifying areas of their influence are interesting for business (allocation of warehouses, shops, service outlets, etc.) and public companies (schools, hospitals, fire stations and so forth.) The tasks of research were to construct the mathematical model for a two-stage of optimal location-allocation problem considering the restrictions on the capacity of enterprises of the first stage; to describe the solution method and to formulate an algorithm. In this paper, authors gave the mathematical model of the problem, a brief description of the solution method and algorithm. Aggregate cost of product de livery was chosen as a criterion for optimal location problem. Solving methods are based on principles of infinite-dimensional optimization and duality theory. The approach to solution of this type of problem is based on the solution of the problem of optimal partitioning set and discrete multi-stage location problem. A unified approach to solving optimal partitioning set problems lies in the conversion of the initial problems into infinite-dimensional mathematical programming problems by means of the characteristic functions, and then into the finite optimization problem using Lagrangian functional. Iterative algorithm to solve the problem has been elab orated. The algorithm combines a method of potentials being applied for classical problem of linear programming of transportation type and N.Z. Shor’s algorithm making it possible to solve optimization problem of nonsmooth function. Software product has been developed to solve two-stage problems of optimal location of enterprises with continuously resources. The results obtained by authors make it possible to solve a range of practical problems connected with strategic planning in the sphere of production, social and economic activities.