Про одну задачу розміщення p-центрів

Abstract

У практичній діяльності постійно виникають задачі «найкращого» розміщення обладнання (або засобів обслуговування) на мережах чи графах. Ці завдання розміщення пов’язані з пошуком найкращого розташування таких систем обслуговування як торгові центри, пожежні частини, фабрики, аеропорти, склади тощо. При цьому в ряді задач про розміщення пунктів обслуговування потрібно так розташувати пункт обслуговування на графі, щоб була мінімальною серед максимальних відстань від пункту обслуговування до будинку. Отримане під час вирішення цієї задачі місце розташування пункту обслуговування називається р-центром графа. Однією з життєво необхідних проблем в даний час є питання протипожежного водопостачання міст і населених пунктів. Як правило, ці питання забезпечуються шляхом будівництва на території міст, населених пунктів водопроводів з установкою на них пожежних гідрантів для забору води пожежними машинами. З метою розробки обґрунтованого методу визначення оптимальних параметрів систем протипожежного водопостачання, побудовано математичну модель задачі раціонального розміщення пожежних гідрантів на мережі водопостачання. Досліджено і проаналізовано особливості математичної моделі, показано, що вона відноситься до класу задач геометричного проектування, а саме до знаходження раціональної кількості та місць розміщення пожежних гідрантів (р-центрів графа) на мережі. Показано, що задача має дискретно-неперервну структуру, тобто встановлений взаємозв’язок між задачею покриття дискретної множини системою дискретних підмножин і неперервною задачею моделювання розміщення пожежних гідрантів на області допустимих розв’язків задачі, що враховує обмеження задачі. По запропонованому методу створено алгоритмічне і програмне забезпечення. Програма написана мовою Visual C++. У якості прикладу здійснено комп’ютерне моделювання розміщення гідрантів в одному з районів м. Харкова. Показано, що ефективність запропонованого метода, в середньому, складає 20%.