Задачи о покрытии множества
Одним из вариантов задачи размещения производства является задача о покрытии множества, т.е. определении мест размещения производств и их числа. Например, задача размещения складов, при котором расстояние от склада до каждого потребителя не превышает 100 км, может быть сформулирована как задача о покрытии множества. Другим примером задачи о покрытии множества является определение числа и размещения на территории города студенческих общежитий, при котором каждый студент тратит на дорогу до учебного заведения не более одного часа, или размещения пожарных команд, при котором расстояние до любой точки города покрывается за 5 мин.
Задача о покрытии множества может быть сформулирована следующим образом:найти
при ограничениях
Величины 
называются коэффициентами покрытия и принимают значения, равные единице, если потребитель находится в пределах 
-й области (т.е. покрывается -й областью), в противном случае равны нулю. Аналогично 
принимает значение, равное единице, если -й области расположен некоторый объект, и равное нулю в противном случае. Ограничения в задаче требуют, чтобы каждый из 
потребителей был «покрыт», по крайней мере, одним из объектов. Цель в этом случае состоит в том, чтобы «покрыть» потребителей с минимальными затратами, причем 
— стоимость помещения объекта в -ю область.
Поясним смысл термина «покрывать». Если имеется ряд жилых строений и решается задача размещения пожарных команд, то 
-е жилое строение считается покрытым, когда пожарная команда находится в пределах 5 минут езды от этого строения; аналогично, если существует -й потребитель и речь идет о размещении заводов, один из которых должен удовлетворять потребителя, то последний считается «покрытым» при условии, что завод расположен, например, в местах 1, 2 или 3. Таким образом,
и все остальные
Поскольку (2.7) является и задачей целочисленноголинейного программирования, то любой приемлемый для ее решения метод может быть использован для решения задачи (2.7). Однако из-за особой структуры данной задачи специально для ее решения были разработаны методы: неявного перебора, секущей плоскости, отсечения, эвристические.
Обычно задача о покрытии множества при решении проблемы размещения состоит в определении минимального числа объектов, необходимых для удовлетворения (покрытия) некоторого множества потребителей. В подобной ситуации задача (2.7) сводится к так называемой задаче о полном покрытии, которая получается, если в (2.7) положить все 
равными единице. Ряд задач размещения экстренных служб может быть сформулирован как задачи о полном покрытии.
Помимо задачи о полном покрытии возможна постановка задачи о частичном покрытии. Если задача о полном покрытии состоит в определении мест расположения объектов и их минимального числа, при котором удовлетворяются все потребители, то задача о частичном покрытии связана с определением размещения заданного числа объектов, при котором удовлетворяется максимальное число потребителей. Практически не всегда можно обеспечить такое число объектов, которое полностью удовлетворяло бы всех потребителей. Обычно число имеющихся в распоряжении объектов достаточно только для частичного «покрытия» множества потребностей. В таких ситуациях целесообразно задачу размещения свести к задаче о частичном покрытии.
Математически задача о частичном покрытии может быть сформулирована следующим образом: найти
при ограничениях
где 
— максимальное число объектов, подлежащих размещению, величины и те же, что и в задаче (2.7).
Из вида функционала 
, используемого в целевой функции задачи (2.8), следует, что если некоторое место расположения потребителя покрывается более чем одним размещаемым объектом, то при вычислении 
учитывается только максимальная величина . Ограничение в задаче (2.8) показывает, что в лучшем случае имеется объектов для размещения. Заметим, что если равно — числу потребителей, то это значит, что достаточно велико, чтобы полностью удовлетворить всех потребителей.
Таким образом, задача о полном покрытии может быть сведена к задаче о частичном покрытии (2.8) для различных значений , и решение задачи (2.8) при наименьшем значении , для которого 
, будет оптимальным решением задачи о полном покрытии. Однако обычно задачу о полном покрытии не решают таким способом, поскольку существуют более эффективные методы ее решения.
Точное решение задачи (2.8) может быть получено с помощью методов динамического программирования, метода ветвей и границ и двойственных методов. Но они не приемлемы с вычислительной точки зрения при
поэтому для решения задачи (2.8) был разработан ряд эвристических методов.
Эта теория взята со страницы лекций по предмету «математическое программирование»:
Предмет математическое программирование
Возможно эти страницы вам будут полезны:
