Дискретные задачи размещения  Библиотека тестовых задач

  Главная страница библиотеки 

Задача размещения с ограничениями на мощности

Оптимизационные алгоритмы   Генераторы исходных данных   Тестовые примеры

Задача размещения с ограничениями на мощности предприятий является обобщением простейшей задачи размещения. В отличие от последней в ней предполагается, что каждое предприятие может производить продукцию только в ограниченных количествах. Такое естественное и важное предположение слегка меняет математическую модель и сильно усложняет методы решения оптимизационной задачи. Идеи тупиковых матриц [1], столь эффективные в простейшей задаче, оказываются малопригодными, и наиболее продуктивными подходами оказываются метод Лагранжевых релаксаций [2] и метод генерации столбцов [3].

Приведем математическую постановку задачи в терминах целочисленного линейного программирования. Пусть множество I ={1,…, I} задает перечень возможных пунктов размещения предприятий по производству некоторого однородного продукта. Величина c_i0 задает стоимость открытия предприятия в пункте iI , а величина V_i0 определяет максимально возможный объем производства в данном пункте.

Перечень потребителей задается множеством J ={1,…,J}. Для каждой пары (ij) известна величина g_ij0 затрат на производство и доставку продукции потребителю, а также величина p_ij0  — объем продукции i-го предприятия, необходимый для удовлетворения потребностей  j-го потребителя.

Введем следующие переменные:

С использованием введенных обозначений оптимизационная постановка задачи записывается следующим образом

x_ij ,  y_i {0, 1},  iI ,   jJ.  

Целевая функция имеет смысл суммарных затрат на открытие предприятий и обслуживание потребителей. Первое ограничение требует удовлетворения потребностей всех потребителей. Второе ограничение несет сразу две функции. Оно позволяет обслуживать потребителей только с открытых предприятий, а также ограничивает сверху возможные объемы поставок продукции с каждого предприятия.

В англоязычной литературе широко известен частный случай этой задачи, когда p_ij = 1 для всех i j. Обзор результатов по такой модели можно найти в [3, 4]. В общем случае задача подробно описана в монографии [1], где вместо размещения производства используется терминалогия системы технических средств.

Литература

1. Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978.

2. Diaz J.A., Fernandez E. Column generation for the single source capacitated plant location problem. Technical report DR 2000/17, UPC Barcelona, 2000.

3. Sridharan R. The capacitated plant location problem. European Journal of Operational Research. v87 (1995), pp 203-213.

4. Holmberg K., Ronnqvist M., Yuan D. An exact algorithm for the capacitated facility location problems with single sourcing. European Journal of Operational Research. v113 (1999), pp 544-559.

Главная страница библиотеки