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

---

Многостадийная задача размещения на содержательном уровне формулируется следующим образом. Заданы множества предприятий и потребителей, которым необходима их продукция. Для производства продукции предприятия объединяются в технологические цепочки. Таким образом продукция проходит несколько стадий обработки.  Множество допустимых технологических цепочек известно. Для каждого предприятия задана стоимость его открытия. Для каждого потребителя заданы производственно-транспортные расходы на удовлетворение его спроса каждой технологической цепочкой. Требуется найти такой набор предприятий, который с минимальными суммарными затратами позволил бы удовлетворить спрос всех потребителей.

На рис.1 изображен пример иерархической многостадийной производственной системы. Черным цветом выделено одно из допустимых решений задачи, в котором функционируют две производственные цепочки.

Рис.1 Допустимое решение задачи

Многостадийная задача размещения относится к числу NP-трудных в сильном смысле задач дискретной оптимизации. Простейшая задача размещения является ее частным случаем. Задача выбора оптимального набора строк пары матриц [1], двухуровневая задача размещения предприятий [2], задача выбора оптимальных рядов изделий и комплектующих узлов [1, 3], задача минимизации полиномов от булевых переменных [4] и задача выбора индексов базы данных [7] могут быть представлены в виде многостадийной задачи размещения.

Приведем математическую постановку задачи в терминах целочисленного линейного программирования. Введем следующие обозначения:

J = {1, ... , J} — множество потребителей;
I = {1, ... , I} — множество предприятий;
L = {1, ... , L} — множество технологических цепочек;

L_i Ì L — множество цепочек, в которые входит i-е предприятие;

 f_i ³ 0  — стоимость открытия i-го предприятия;
c_lj ³ 0 — стоимость удовлетворения спроса j-го потребителя l-й цепочкой.

Переменные задачи:   

С использованием введенных обозначений многостадийная задача размещения может быть записана следующим
образом [5, 6]:

                                                   (1)

                                                               (2)

                                                     (3)

                      x_lj, y_iÎ{0,1}, lÎL,  jÎJ,  iÎI                   (4)

Целевая функция (1) имеет смысл суммарных затрат на открытие предприятий и удовлетворение спроса потребителей. Равенства (2) гарантируют удовлетворение спроса всех потребителей. Условия (3) требуют внесения затрат на открытие предприятий, если они участвуют в удовлетворении спроса.

Литература

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

2. Горбачевская Л.Е., Дементьев В.Т., Шамардин Ю.В. Двухуровневая задача стандартизации с условием единственности оптимального потребительского выбора. Дискретный анализ и исследование операций. Сер.2, т6 (1999), №2, с.3-11.

3. Береснев В.Л. О задаче выбора оптимальных рядов изделий и комплектующих узлов. Управляемые системы. Вып.16 (1977), с. 35-46.

4. Береснев В.Л. Алгоритмы минимизации полиномов от булевых переменных. Проблемы кибернетики. Вып.36 (1979), с. 225-246.

5. Береснев В.Л., Гончаров Е.Н. Приближенный алгоритм для задачи минимизации полиномов от булевых переменных. Дискретный анализ и исследование операций. Сер.2, т5 (1998), №2, с. 3-19.

6. Гончаров Е.Н., Кочетов Ю.А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения. Дискретный анализ и исследование операций. Сер.2, т6 (1999), №1, с.12-32.

7. S. Finkelstein, M. Schkolnik, and P. Tiberio Physical database design for relational databases. ACM Transactions on Database Systems, v.13 (1988), pp.91-128. 

---