4551
правка
Задача о размещении объектов: различия между версиями
Перейти к навигации
Перейти к поиску
Задача о размещении объектов (посмотреть исходный код)
Версия от 12:17, 27 апреля 2018
, 27 апреля 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 31: | Строка 31: | ||
'''Варианты и родственные задачи''' | '''Варианты и родственные задачи''' | ||
Вариант задачи о размещении объектов без ограничений на пропускную способность был получен в результате рассмотрения коэффициентов целевой функции <math>c_{ij} \;</math> как прибыли в пересчете на элемент, полученной в результате обслуживания клиента j из объекта i. Вариант с ''максимизацией'' UFL, названный max-UFL, ориентирован на максимизацию прибыли за вычетом стоимости открытия объекта, т. е. <math>max \sum_{i \in \mathcal{F}} \sum_{j \in C} c_{ij} x_{ij} - \sum_{i \in \mathcal{F}} f_i y_i</math>. Этот вариант предложили Корнюжо, Фишер и Немхаузер [15]. | |||
В задаче о k-медианах стоимость открытия объекта не включается в целевую функцию (1), в результате чего она имеет вид min Pi2M Pj2N cijxij, плюс добавляется ограничение k на количество объектов, которые могут быть открыты, Pi2M yi - k. В задаче о k-центрах ограничение Pi2M yi - k учитывается, а целью является минимизация максимального расстояния по соединению между открытым объектом и клиентом. | |||
В задаче с ограничениями для всех i 2 F добавляется ограничение на пропускную способность Pj2C xij — uiyi. Важно различать случаи с возможностью разделения и с его невозможностью, а также случаи с мягким и жестким ограничением на пропускную способность. В случае возможностью разделения имеем x > 0, что позволяет обслуживать клиента при помощи нескольких депо; в случае с невозможностью разделения необходимо выполнение x 2 f0;1}"/X"c. Если каждый объект может быть открыт не более одного раза (т.е. yi 2 f0; 1g), ограничения называются жесткими; если в задаче допускается открытие объекта i любое количество r раз для обслуживания rui клиентов, ограничения называются мягкими. | |||