Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,931

LOCATION OF THE ENTERPRISES ON A GEOGRAPHICAL TERRITORY WITH THE HELP OF DICHOTOMOUS PROGRAMMING

Dulesov A.S. 1 Kazaeva M.A. 1
1 Katanov State University of Khakassia
В статье рассмотрена проблема решения задачи о размещении нескольких предприятий на выделенной географической территории. На основе существующих методов решения данной задачи предложен алгоритм нахождения оптимального месторасположения нескольких предприятий с помощью дихотомического программирования в комплексе с инструментами геоинформационных систем. Алгоритмом предусмотрено соблюдение ряда экономических критериев. Представлено использование данного алгоритма на примере размещения энергосбытовых компаний. С помощью рассмотренного примера проанализированы его основные возможности, а также выделены достоинства и недостатки. К числу достоинств отнесена точность искомого результата. Правильно выбранное месторасположение предприятия позволит снизить транспортные расходы, издержки на эксплуатацию, а также повысить доступность предприятия для клиентов. Алгоритм применим для предприятий различных сфер деятельности. С целью удобства применения данного алгоритма предполагается создание программного средства для ЭВМ.
The article suggests a solution to the problem of location of several enterprises on a single site. Having analysed the existing methods of solving such problems the author has set forward an algorithm of optimum locating of several enterprises using dichotomy software technology and GIS tools. Some economic criteria are included into the algorithm. The application of this algorithm is illustrated by the example of locating of some retail energy sales companies. This example helps to analyse main capabilities of the algorithm, its advantages and disadvantages. One of the advantages, for example, is that the desired result is accurate. The right location will cut down transport and operating expenses, and make enterprises immediately available for customers. This algorithm can be used for enterprises of other business branches too. To make it more usable a new software tool will be created.
geoinformation technologies.
dichotomous programming
geographical location
Введение. Существует множество факторов, влияющих на эффективную деятельность предприятий. Одним из таких факторов является территориальное размещение предприятий. Правильно выбранное месторасположение позволит снизить транспортные расходы, повысить доступность предприятия для клиента, реализовать структуру распределения ресурсов между предприятиями одной сферы деятельности [5].

Для нахождения эффективных мест территориального размещения предприятий применяют различные методы: логистические, дискретной математики, имитационного моделирования, а также используют различные технологии пространственного представления данных, например, геоинформационные системы [1]. Ни один метод не обладает достаточной универсальностью, так как выбор зависит от решающего оптимизационного критерия: минимальное время транспортировки товара, максимальное время доступности для клиентов, минимальное расстояние и др. [7]. Для получения оптимального результата желательно использовать комплекс методов, например, когда необходимо разместить несколько предприятий одной сферы деятельности. Применение логистических методов для решения задачи размещения нескольких предприятий не дает эффективного решения, в отличие от методов дискретной математики, в частности, метода дихотомического программирования [3].  Покажем возможности использования этого метода в комплексе с инструментами геоинформационных систем.

Постановка задачи. На некоторой географической территории (населенный пункт, район) необходимо разместить k предприятий, принадлежащих одной сфере деятельности. Предприятия занимаются реализацией продукции клиентам. Имеются данные о потреблении товара клиентами. В качестве возможных месторасположений дано m предприятий. Необходимо выбрать k наиболее оптимальных месторасположений из m.

Алгоритм решения задачи размещения с помощью метода дихотомического программирования и геоинформационных технологий заключается в выполнении следующей последовательности действий:

1. Для каждого возможного месторасположения вычисляются: эффект от деятельности (ai) и затраты на размещение (bi). Эффект от размещения будет состоять из доходов предприятия от деятельности в определенном месте. Зона обслуживания предприятия ограничена буфером с некоторым радиусом. С помощью геоинформационной системы выбираются все клиенты из зоны обслуживания, затем рассчитывается доход [2]. В затраты на размещение предприятия включается стоимость аренды. Должно соблюдаться условие: , т.е. сумма затрат на размещение m предприятий не должна превышать заданной величины расходов (B) [6]. В зависимости от района, в котором расположено возможное место размещения предприятия, вычисляются затраты на аренду.

2. Строится дихотомическое дерево (рисунок 1).

Рисунок 1.  Дихотомическое дерево

3. Рассчитываются различные варианты размещения предприятий в каждой вершине дихотомического дерева. В вершине Si существует 3 варианта размещения: в пункте i; в пункте m-(i-1); в этих двух пунктах одновременно. Для расчета эффекта от размещения одновременно в двух пунктах складываются эффекты в каждом пункте в отдельности. Аналогично вычисляются затраты. Расчеты удобно представлять в виде таблицы, где пересечение строки и столбца - это размещение предприятия в этих двух пунктах одновременно (таблица 1) [6].

Таблица 1

Расчет параметров вершин дихотомического дерева

m-(i-1)

i

Далее рассчитывается каждая вершина, убираются следующие значения: 1) у которых не выполняется условие ; 2) которые при затрачивании большего количества средств дают меньший эффект.

4. После вычисления вершины S(m-1), все значения располагаются в порядке возрастания эффекта от размещения, затем выбирается наибольше значение.

5. Находится вершина, в которой было получено наибольшее  значение эффекта от размещения, затем рассматриваются вершины, в результате сложения которых был получен такой результат. После этого получаем k конкретных месторасположений из m возможных.

6. Полученные оптимальные места расположения объектов отображаются на карте. Затем с помощью инструмента буферизации определяются зоны обслуживания для каждого предприятия, что позволит наглядно отразить результаты решения задачи размещения [2].

Пример. Пусть имеется три энергосбытовые компании, занимающиеся реализацией электроэнергии, база данных клиентов, десять возможных месторасположений компаний. Условие: расходы на размещение трех предприятий не должны превышать 240 000 рублей. Необходимо найти оптимальное место размещения трех компаний на выделенной территории.

1. Вычислим для каждого возможного месторасположения эффект от деятельности (ai) и затраты на размещение (bi). Доступность предприятия ограничим буфером с радиусом 1 км. Исходя из этой зоны, и будем считать эффект от деятельности для компании. Фрагмент карты поделен на районы, каждый район обладает определенной стоимостью аренды 1 кв.м. Затраты на размещение - это стоимость аренды в данном месте. Предположим, что для компании достаточно иметь помещение в размере 100 кв. м. Стоимость аренды по микрорайонам составляет: первый район - 800 рублей 1 кв.м, второй район - 600 рублей 1 кв.м, третий район - 1000 рублей 1 кв.м.

Рассмотрим определение параметров для одного месторасположения. С помощью геоинформационной системы установим буферную зону с радиусом 1 км и вычислим максимальное электропотребление клиентов в данной зоне. Оно составляет 3 432 652 кВт. Возьмем тариф электроэнергии 0,8 рублей за 1 кВт. Тогда эффект от размещения будет равен 2 746 122 рублей. Затраты на аренду помещения в данном районе  составят 60 000 рублей. Далее рассчитываем  эти параметры для оставшихся мест (таблица 2).

Таблица 2 Параметры возможных мест размещения компаний

№ п/п

ID

Эффект от размещения (руб.)

Затраты (руб.)

1

2813

2 746 122

60 000

2

3865

5 033 782

80 000

3

3885

1 904 300

80 000

4

4751

4 980 148

100 000

5

4766

4 574 333

100 000

6

5219

4 146 416

100 000

7

6176

2 010 966

100 000

8

6225

4 158 626

100 000

9

10378

3 570 556

100 000

10

13744

3 553 096

100 000

2. Построим дихотомическое дерево (рисунок 2).

Рисунок 2.  Дихотомическое дерево решаемой задачи

3. Рассчитаем различные варианты размещения предприятий в каждой вершине дихотомического дерева. Рассмотрим вершину S1. При размещении предприятия в 1 и 10 местах одновременно получим эффект от деятельности, равный 6 299 218 рублей, и затраты на размещения - 160 000 рублей.

Таблица 3 Расчетные значения параметров вершин дихотомического дерева

      10

1

Аналогично вычисляем эффекты от размещения объектов и затраты на их размещение  для других вершин.


4. Наибольше значение эффекта от деятельности равно 12 760 052 рублей при общих затратах 240 000 рублей. Данное значение было получено в вершине S8 на пересечении значений из S6 и S7. Значение из S6 получено на пересечении значений из S1 и S2, а из S7 получено из S4 и составляет эффект от размещения и затраты в пункте 4. Значение из S1 составляет эффект от размещения и затраты в пункте 1, а из S2 в пункте 2. Таким образом, предприятия необходимо разместить в пунктах 1, 2 и 4.

5. Представим полученные результаты на карте с использованием геоинформационной системы (рисунок 3). С помощью операции буферизации выделена зона обслуживания каждого предприятия.

Рисунок 3.  Результат размещения предприятий

Заключение. Для размещения нескольких предприятий представлен алгоритм использования дихотомического программирования в совокупности с инструментами геоинформационной системы. Он позволяет найти оптимальное решение при ограниченном значении затрат. Использование метода дихотомического программирования повышает точность решения задачи с помощью геоинформационных технологий. Сложность реализации алгоритма заключается в  необходимости определения эффекта от деятельности объектов и затрат на их размещение. В целом алгоритм применим для предприятий различных сфер деятельности. С целью обеспечения простоты использования данной методики рекомендуется создание программного средства, реализующего процедуру нахождения пунктов размещения предприятий.

Рецензенты:

  • Нагрузова Любовь Петровна, доктор технических наук, доцент, профессор  кафедры «Строительство» Хакасского технического института - филиала Сибирского федерального университета, г. Абакан.
  • Булакина Елена Николаевна, доктор технических наук, доцент, профессор  кафедры «Автомобили и автомобильное хозяйство» Хакасского технического института - филиала Сибирского федерального университета, г. Абакан.