---

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

найти минимум функции		(1)
при условиях		(2)
		(3)
		(4)

где n — число поставщиков; m — число потребителей; A_j — минимальное количество продукта, требуемое потребителю j; m_ij — минимальное количество продукта,  которое поставщик i готов доставить потребителю j; M_i — максимальное количество продукта, которое поставщик i может доставить. Переменная x_ij обозначает размер поставки от поставщика i потребителю j.

Стоимость доставки

Параметры a_ij,  b_ij,  m_ij,  M_i,   A_j  предполагаются целочисленными и неотрицательными при всех i, j.

Стоимость решения x = (x_ij), заданную выражением (1), будем обозначать через f(x).

Эта задача является ослабленной версией задачи управления поставками с вогнутой целевой функцией, рассмотренной в [2, 4]: в них в условии (2) требуется  равенство, а функции стоимости неотрицательные и вогнутые. Нахождение любого допустимого решения задачи в постановке из [4] является NP–трудной задачей даже при одном потребителе, хотя существует псевдополиномиальный точный алгоритм ее решения [2].

Задача (1) – (4) является NP–трудной, так как она содержит задачу о рюкзаке как частный случай. Кроме того, сведение задачи разбиения показывает, что задача нахождения допустимого решения, удовлетворяющего ограничениям (2) – (4), является NP–трудной даже в случае m = 2. Кроме того, задача (1) – (4) и задача нахождения p(n, m)–приближенного решения при любом полиноме p(n, m) с положительными коэффициентами являются NP–трудными в сильном смысле [1].

ЛИТЕРАТУРА

1. Еремеев А.В., Романова А.А., Сервах В.В., Чаухан С.С. Приближенное решение одной задачи управления поставками // Дискретн. анализ и исслед. операций. Серия 2. 2006.  Т. 13, № 1. С. 27–39.

2. Chauhan S.S., Eremeev A.V., Kolokolov A.A., Servakh V.V. Concave cost supply management for single manufacturing unit // Supply chain optimisation. Product/process design, factory location and flow control. New York : Springer. Applied Optimization 2005. V. 94.  P. 167–174.

3. Chauhan S.S., Eremeev A.V., Romanova A.A., Servakh V.V., Woeginger G.J. Approximation of the supply scheduling problem // Oper. Res. Lett. 2005. V. 33, N 3. P. 249–254.

4. Chauhan S.S., Proth J.–M. The concave cost supply problem // European J. of Oper. Res. 2003. V. 148, N 2. P. 374–383.

На главную