Статьи

Версия для печати

Все статьи | Статьи за 2007 год | Статьи из номера N5 / 2007

Адаптивный подход к распределению ограниченных ресурсов в производственных системах

Вилисов В.Я.,

Производственные предприятия часто сталкиваются с проблемой распределения дефицитных позиций материалов, комплектующих, ингредиентов при запуске партий изделий в производство. Эта задача решается менеджерами на основе их собственного опыта и интуиции. Строй оценке возможных вариантов распределения и выбору наилучших из них препятствует большие размерности задачи и то обстоятельство, что учитываемых критериальных показателей бывает несколько, они часто не формализованы, а иногда даже и не вербализуемы.
Таким образом, существует задача оптимального распределения ограниченных ресурсов, когда на момент запуска в производство очередной партии изделий некоторые материалы оказываются в дефиците. В общей оптимизационной постановке эта задача многократно рассматривалась в литературе [1]. В большинстве случаев подобные задачи сводятся к моделям линейного программирования, где в качестве целевой функцией (ЦФ) выбирается показатель, который, с точки зрения постановщика, представляется наиболее существенным. Обычно подобные технологии оказываются нежизнеспособными в силу их неадекватности предпочтениям конкретного лица, принимающего решение (ЛПР), ибо предпочтения в модель закладывает постановщик, а за принятые решения отвечает ЛПР. Открыт вопрос о том, в каком же смысле оптимальным является решение, полученное на основе такой модели. Подобные несоответствия приводят к дискредитации использования оптимизационных моделей в практике принятия управленческих решений.
В практических ситуациях для подобных моделей, при их структурной адекватности, существует параметрическая критериальная неопределенность, которая и не позволяет получить решение, оптимальное в смысле реальных предпочтений ЛПР. Я предлагаю адаптивный подход к построению целевой функции, адекватной текущим предпочтениям ЛПР. Построенные алгоритмы фактически реализуют контур обратной связи, обеспечивающий постоянную подстройку параметров ЦФ под текущие предпочтения ЛПР.
Традиционный же подход представляет схему управления без обратной связи.

Постановка задачи

Объект

Объектом управления для рассматриваемого класса прикладных задач можно считать границу «склад – производство». При этом выработка управляющего воздействия заключается в определении состава и количества продукции, запускаемой в производство, что однозначно определяет и те материалы, которые необходимо передать со склада в производство. Воздействие внешней среды заключается в генерировании заказчиками заявок на изделия, которые и необходимо запустить в производство после их полной или частичной оплаты. Цель управления – запуск в производство такого количества изделий и в таком ассортименте, чтобы удовлетворить предпочтениям ЛПР при текущих ограничениях.
К моменту решения задачи запуска партии изделий в производство имеется множество счетов (заказов), для обеспечения выпуска по которым, согласно спецификаций на изделия, необходимо определенное количество материалов. Если потребное количество материалов не превышает наличия на складе, то ситуация, требующая принятия решения (СТПР) не возникает и бизнес-процесс протекает по стандартной схеме – на основе спецификаций выделяется и передается в производство весь объем материалов, необходимый для выпуска требуемого количества продукции. Если же по некоторым позициям текущее количество материалов на складе меньше необходимого, то возникает СТПР.

Критерии

В практике решения рассматриваемого круга задач используются частные критерии:
максимум прибыли от продажи партии изделий, запускаемых в производство;
минимум себестоимости партии изделий;
максимум себестоимости партии изделий (предполагая, что себестоимость связана с прибылью нормой рентабельности)<*>1;
максимум загрузки производственных мощностей.

<*> Этот критерий можно считать косвенным вариантом первого. Однако его проще оценивать, если в качестве себестоимости иметь в виду среднюю себестоимость (за некоторый период) для каждого вида изделий.

Без потери общности будем считать, что каждый критерий можно представить как экстремум (max или min) некоторой линейной формы (целевой функции - ЦФ) на множестве переменных:

(1)

 

Ограничения

Согласно спецификациям на виды продукции, можно составить систему ограничений с учетом текущих ограничений по видам материалов  – матрица спецификаций (аij – означает, сколько единиц i - го материала используется в единице j - го продукта), m – общее количество материалов (строки матрицы); n – количество продуктов (столбцы матрицы);  – вектор переменных (количество j - го вида продукции);  = – вектор ограничений по количеству материалов i- го вида (текущие остатки на складе).
Производственная программа представлена следующими ограничениями  – вектор количества изделий (по каждому j-му виду), которое необходимо выпустить согласно текущему набору заявок.
Кроме того, в число ограничений следует добавить условия физической реализуемости (неотрицательности переменных) x >= 0 (4).
В дальнейшем, без потери общности, будем считать, что ограничения (2) и (3) вошли в общую систему неравенств вида (2). А при решении модельного примера все три типа ограничений будем включать в единую систему неравенств, поменяв знак неравенства в ограничениях (4).

Адаптивная модель

Задачу разобьем на две: прямую задачу линейного программирования (ПЗЛП) и обратную задачу линейного программирования (ОЗЛП). Под прямой будем понимать традиционную [1] постановку задачи линейного программирования, где отыскивается оптимальное значение вектора переменных, удовлетворяющее условиям (1) – (4). В обратной задаче [2] (не следует путать с двойственной) необходимо по ограничениям (2) – (4) и оптимальным значениям вектора переменных определить коэффициенты ЦФ (1).
Тогда адаптивный подход будет заключаться в следующем. По некоторому количеству СТПР лицо, принимающее решение, производит распределение «вручную», тем самым проецируя свои предпочтения на принятые решения. Обработка данных о его (ЛПР) выборе после каждой СТПР выполняется по алгоритмам решения ОЗЛП, в результате чего получаются оценки коэффициентов целевой функции , которые от шага к шагу все точнее отражают предпочтения ЛПР. Если даже реальные предпочтения ЛПР были многокритериальными, то в результате решения ОЗЛП будет получена их однокритериальная аппроксимация, которая в дальнейшем и может быть использована для решения прямой однокритериальной задачи линейного программирования. Таким образом, на начальном этапе использования настраиваемых моделей необходимо несколько раз решить ОЗЛП, а когда оценки j c.
будут уже слабо меняться, можно решать ПЗЛП. Алгоритмы решения ОЗЛП построены с учетом того, что решения ЛПР совпадают с крайними точками ОДР, а ситуация стационарна. Однако и отклонения от этих предпосылок могут быть учтены [2].
Каждому k-му набору данных (СТПР) соответствует пучок гиперплоскостей L(x), расположенный между теми гиперплоскостями ограничений, которые образуют оптимальную крайнюю точку k-го набора данных. Каждому очередному набору данных из последовательности наблюдений можно поставить в соответствие одну (среднюю в некотором смысле [2]) гиперплоскость либо весь пучок гиперплоскостей. Тогда средней гиперплоскости будет соответствовать одна точка в пространстве параметров, а пучку – некоторая область (интервал). Исходя из этих представлений, можно говорить о точечном алгоритме и об интервальном. Точечные оценки j c.
в ходе итераций сходятся к фактическому вектору c , а интервальные стягиваются к нему. Если по текущим оценкам решать ПЗЛП, то на основании точечной оценки будет получено единственное решение в новой СТПР, а по интервальной оценке – набор решений. В тех случаях, когда оценки еще не достаточно настроены, решения, полученные по модели могут служить ЛПР основой для выбора окончательного решения.
Рассмотрим сущность точечного алгоритма решения ОЗЛП [2]. Он построен следующим образом. Для каждого k-го набора данных по принятому ЛПР решению xk из системы неравенств выделяется mk неравенств, обратившихся в точке xk в равенства. В дальнейшем в наборах данных будем рассматривать именно такие системы равенств:

Эти соотношения представляют гиперплоскости в n-мерном пространстве, пересекающиеся в точке xk. Каждому k-му набору данных поставим в соответствие k-ю оценку целевой функции в виде вектора . Гиперплоскость , соответствующая оценке целевой функции, строится как средняя по пучку гиперплоскостей (5). Для удобства дальнейших построений заменим гиперплоскости их нормальными векторами единичной длины (НВЕД). Сумму НВЕД каждого пучка также пронормируем. То же сделаем и для суммы векторов множества наблюдений (пучков). С учетом этого j -я координата НВЕД i e , соответствующего i-ой гиперплоскости пучка (5), определится как .

Отсюда, после некоторых преобразований, координаты итогового НВЕД, с учетом информационного веса  k-го набора данных определятся как

В итоге по K наборам данных вектор оценок параметров  примет вид , тогда оценка целевой функции может быть представлена как

При достаточной точности оценок  , целевая функция  может быть использована для решения ПЗЛП. В качестве меры точности восстановленных оценок коэффициентов целевой функции используется стандартная для подобных случаев величина объема эллипсоида рассеяния [4] относительно скользящего среднего.
Установлено [2], что скорость сходимости повышается, если использовать отличные от единицы весовые коэффициенты вk, отражающий размеры углов при вершине xk (чем меньше угол, тем больше вес).
Процесс адаптивной настройки модели, при необходимости, может быть ускорен [2] на основе использования методологии планирования оптимальных экспериментов [4].
Кроме приведенного точечного алгоритма в некоторых практических случаях могут оказаться более удобными и стохастические алгоритмы [2, 3], построенные на основе методов стохастического рекуррентного оценивания [5].

Моделирование

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

Предметы производства

Производственная фирма выпускает два типа продуктов:
1. Рулет (x1 – количество рулетов, запускаемых в производство).
2. Бисквит (x2 – количество бисквитов, запускаемых в производство).
Переменные принимают не только целочисленные, но и любые непрерывные значения, так как продукция может быть реализована и по весу. Калькуляция (спецификация) рулета – это вектор-столбец , бисквита – . Тогда .
Список материалов, используемых для производства этих видов изделий, приведен в табл. 1.

Таблица 1

Калькуляция и цены

№ п/п

Материал

Ед. изм.

Цена, руб.

Рулет

Бисквит

1

Вода

л

4

0.1

0.05

2

Молоко

л

22

0.02

0.15

3

Мука

кг

22

0.5

0.3

4

Яйцо

шт

3

4

4

5

Сахар

кг

25

0.4

0.05

6

Сахарная пудра

кг

35

0.1

0.2

7

Сливочное масло

кг

180

0.05

0.08

8

Варенье

кг

200

0

0.03

9

Орехи фундук

кг

150

0.05

0.08

10

Сметана

кг

150

0.25

0.05

Закупочная цена материалов, руб.

91.34

70.25

Отпускная цена изделий, руб.  

120

90

 

Исходные данные для моделирования

Ежесменно формируется комплект материалов для выполнения всего пакета заявок на поставку изделий. Если материалов на складе достаточно для производства всей партии заказанных изделий, то СТПР не возникает. В противном случае решается задача распределения ограниченных ресурсов.
Рассмотрим 20 шагов моделирования (СТПР), которые отличаются остатками материалов на складе и объемами заявок. При этом будем считать, что ситуация стационарна, целевая функция, калькуляции и цена материалов остается неизменной от шага к шагу.

Калькуляция

В таблице 1 представлена калькуляция (на единицу изделия) и соответствующие цены ингредиентов. Рассчитана цена материалов, входящих в единицу продукта (в штуках) и приведена отпускная цена за единицу продукта.

Целевая функция ЛПР

При моделировании будем считать, что реальная цель ЛПР отражена смесью двух целевых функций с весами соответственно 1 и 0.4 L1 = 120x1 + 90x2 (9), L2 = 91.34x1 + 70.25x2 (10), или с учетом весовых коэффициентов L = L1 + 0.4 L2 = 156.54x1 + 118.10x2 (11).
Моделируемые как реальные коэффициенты целевой функции ЛПР имеют значения:
с1=156.54; с2=118.10.
Поскольку на выбор оптимального решения абсолютные значения коэффициентов целевой функции (ЦФ) влияния не оказывают, то в дальнейшем для удобства сравнения с получаемыми оценками будем использовать их в нормированном виде как НВЕД. При этом вектор коэффициентов ЦФ (11), как НВЕД, примет вид: .
Будем считать, что ЛПР интуитивно чувствует весовую смесь (11) и согласно ей может безошибочно (с абсолютной разрешающей способностью [2]) принимать решения.
Критерий (1) для рассматриваемой задачи имеет вид  (12), где  . – область допустимых решений (ОДР).

Заявки от покупателей и остатки материалов на складе

Данные для моделирования были сформированы с помощью генератора случайных чисел (в среде MS Excel средствами модуля Анализ данных) в диапазонах варьирования, близких к реальным. Часть наблюдений были отброшены, как не несущие дополнительной информации о предпочтениях ЛПР – это те, в которых сочетание значений Огр.1, Огр.2 (табл. 4) уже встречалось в одном из предыдущих наблюдений. В результате такого отсева из 20 наблюдений для настройки модели осталось лишь 14 (табл. 2), по которым и выполнялись все действия. Здесь номер шага соответствует номеру предъявления данных для выбора решения. Для каждого из материалов приведены остатки на складе на момент распределения ограниченных ресурсов (в единицах измерения таблицы 1), а по изделиям – текущая потребность, сформированная по заявкам покупателей (в штуках).
Решения на каждом шаге получены в среде MS Excel с помощью модуля Поиск решения с целевой функцией (11) и приведены в табл. 3.
Те активные ограничения, которые в оптимальной крайней точке ОДР обращаются в равенства, представлены в табл. 4. Поскольку, в случае двух переменных каждая крайняя точка образуется двумя линиями ограничений, то в табл. 4 и приведены пары номеров соответствующих ограничений. Множество ограничений в рассматриваемой задаче состоит из трех групп: ограничения по материалам (с 1-го по 10-е); ограничения по видам готовой продукции (с 11-го по 12-е), соответствующие заказам; ограничения неотрицательности переменных (с 13-го по 14-е). Коэффициенты правых частей активных ограничений в табл. 2 выделены жирным шрифтом.

Таблица 2

Шаги настройки


шага (к)

Материалы (ai0, i = 1,10)

Объем заказа
(ai0, i = 11,12)

 

1

2

3

4

5

6

7

8

9

10

Рулет

Бисквит

1

0.69

12.44

35.09

347.00

0.16

15.60

5.03

1.41

3.16

8.93

66

47

2

1.83

11.99

12.90

158.00

17.57

7.20

2.60

2.89

7.81

10.63

43

51

3

0.75

9.37

32.12

340.00

18.62

1.73

7.61

1.40

1.11

13.10

54

0

4

0.67

14.13

13.00

253.00

2.98

1.51

5.02

1.11

6.75

15.15

6

73

5

4.56

10.65

17.73

52.00

6.56

6.09

6.83

2.56

1.54

15.61

25

95

6

4.85

10.21

39.45

336.00

5.33

3.24

1.76

2.70

8.28

11.49

59

32

7

0.97

7.00

9.93

44.00

39.40

9.89

3.88

1.44

9.50

19.40

80

27

8

1.00

2.99

26.85

280.00

27.05

17.45

7.60

0.55

5.04

6.13

68

56

9

2.14

0.07

24.40

87.00

35.13

19.18

2.78

0.76

9.78

3.20

41

1

10

1.10

7.74

14.47

126.00

26.80

19.53

3.60

2.55

0.21

18.63

69

91

11

4.36

9.55

38.14

71.00

11.96

11.16

5.66

2.44

1.03

16.52

6

91

12

1.70

1.65

38.51

275.00

16.19

3.22

0.06

2.09

8.84

14.59

3

19

13

3.39

6.14

36.61

380.00

35.63

3.30

3.77

1.84

8.78

11.04

34

52

14

2.39

6.50

23.68

122.00

6.42

7.02

5.46

0.02

3.40

5.07

99

38

Полигон

11.18

15.13

58.31

566.00

40.31

22.36

9.43

3.00

9.43

25.50

100

100

Таблица 3

Пошаговые решения

№ шага

1

2

3

4

5

6

7

8

9

10

11

12

13

14

x1

0

3.02

7.51

3.94

13

12.06

8.47

0.85

3.66

4.26

6

1.18

32.97

15.97

x2

3.17

30.64

0

5.6

0

10.15

2.53

18.38

0

0

9.11

0

0

0.67

 

Таблица 4

Активные ограничения

№ шага

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Огр.1

5

1

1

1

4

5

1

1

2

9

9

7

6

5

Огр.2

13

7

12

6

14

6

4

8

14

14

11

14

14

8

 

Решение обратной задачи

В соответствии с приведенным адаптивным алгоритмом вычислим оценки коэффициентов целевой функции по данным моделирования. На каждом шагу целевая функция представлена координатами НВЕД.
Весы наблюдений k &rc; и оценки k i c. коэффициентов целевой функции (в виде НВЕД) на каждом k-ом шагу наблюдений приведены в табл. 5, на рис. 1 и рис. 2.

Таблица 5

Весы наблюдений

№ шага

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Вес

0.062

0.963

0.851

0.949

0.383

0.882

0.987

0.851

0.066

0.276

0.875

0.276

0.230

0.750

-0.062

0.706

0.628

0.656

0.744

0.762

0.772

0.740

0.746

0.772

0.787

0.807

0.821

0.808

0.998

0.708

0.778

0.755

0.668

0.648

0.635

0.672

0.666

0.636

0.617

0.591

0.571

0.589

 

Рис. 1. Весы наблюдений

Рис. 2. Оценки С1, С2 и шаги

Поскольку для поиска решения (оптимального вектора ) абсолютные значения вектора коэффициентов ЦФ не играют роли, а важно лишь положение этого вектора в пространстве переменных, можно использовать вектор его оценок  построенный по всем измерениям (в данном примере - по 14 измерениям и соответствующим им настройкам коэффициентов ЦФ). Таким образом, для поиска решений на основе модели в новых ситуациях (СТПР) следует использовать ЦФ с вектором коэффициентов (см. табл. 5).

Анализ и обсуждение результатов

Сходимость оценок и решений

Вопрос о том, насколько быстро настраивается модель предпочтений ЛПР по наблюдениям за его решениями в последовательности предъявленных СТПР, можно рассматривать различно [2]. Как изменяются оценки коэффициентов ЦФ и насколько  быстро они приближаются к их истинным значениям, видно на рис.2. Однако отображение изменений каждого из коэффициентов ЦФ, особенно в случае большой размерности пространства переменных, не дает полной картины сходимости процесса. На рис.3 приведена невязка вектора оценок коэффициентов ЦФ и вектора фактической (модельной) ЦФ. Использование этих векторов в виде НВЕД дает возможность интерпретировать текущую невязку как процент точности настройки. Такая интегральная характеристика не зависит от размерности пространства переменных и может служить индикатором сходимости в режиме имитационного моделирования. В реальной практике невязка не может быть сформирована, поскольку истинная ЦФ неизвестна. Однако в этом случае показателем сходимости [2, 3] может служить оценка скользящей дисперсии (или среднеквадратического отклонения) НВЕД оценки ЦФ.
Однако и по невязке (рис.3) трудно судить о том, какой ее уровень можно считать допустимым. Невязка решений полнее отражает качество сходимости. Так, для рассматриваемой модельной задачи выполнено сравнение решений на основе полигона (табл.
1). Данные такого сравнения, по мере настройки модели, приведены на рис. 4, где по оси ординат отложены номера упорядоченных крайних точек ОДР полигона (табл. 4). На диаграмме видно, что, начиная с 5-го шага, модель дает решения, полностью совпадающие с решениями ЛПР в тех же ситуациях выбора (СТПР).

Ускорение сходимости оценок модели

Данные, приведенные в табл. 2, были сформированы с помощью случайного механизма. Это соответствует большинству практических ситуаций, в которых СТПР носят случайный характер. Такие условия принято [2] называть режимом нормального функционирования. В управленческой практике модель может строиться в реальном масштабе времени, когда данные из учетной системы предприятия поступают для построения оценок целевой функции в том порядке, в котором возникают СТПР. Однако, если данные о прошлых ситуациях выбора решений хранятся в системе учета продолжительно, то их можно использовать и для ретроспективного оценивания ЦФ в любом удобном порядке следования СТПР. Оба эти режима соответствуют режиму нормального функционирования. В тех случаях, когда есть возможность зондировать ЛПР, формируя любые СТПР для выявления его предпочтений, можно говорить об управляемом эксперименте [4] над ЛПР. Таким образом, все эти варианты предъявлений делятся на 3 группы [2]:
1. Пассивный эксперимент, в котором поток данных (СТПР) поступает на обработку в естественном порядке.
2. Полуактивный эксперимент, когда множество реальных ретроспективных данных можно использовать в любом желаемом порядке.

Рис. 3. Невязка вектора оценки

Рис. 4. Сравнение решений

3. Активный эксперимент, в котором СТПР формируются в желаемом виде.
Все выполненные выше построения оценок ЦФ относятся к пассивному эксперименту над ЛПР. Настройка модели в режиме пассивного эксперимента самая медленная.
Второй вариант позволяет ускорить сходимость оценок, а третий - обеспечивает максимально возможную скорость сходимости оценок к их реальным значениям.
Данные по СТПР, приведенные в таблице 2, имеют информативность, представленную по шагам в виде весов на рисунке 1. Если в режиме полуактивного эксперимента выстроить СТПР в порядке убывания их весов, то уже после первого шага настройки модели сходимость по решениям (аналогично рис. 4) превратится в две совпадающие линии.
Активный эксперимент для рассмотренного модельного примера можно представить полигоном (см. последнюю строку табл. 2). Если такую СТПР предъявить ЛПР, то он с первого раза выберет крайнюю точку 6 (табл. 4). Таким образом, для рассматриваемого модельного примера уже после первого шага в активном эксперименте решения по модели будут совпадать с оптимальными решениями ЛПР. Однако при этом ЛПР должен обладать высокой разрешающей способностью [2].

Выводы

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

ЛИТЕРАТУРА

1. Таха Х.А. Введение в исследование операций. - М.: Изд. дом «Вильямс», 2005.
2. Вилисов В.Я. Методы выбора экономических решений. Адаптивные модели. - М.: Финансы и статистика, 2006.
3. Вилисов В.Я. Адаптивные модели исследования операций в экономике. - М.: Энит, 2007.
4. Федоров В.В. Теория оптимального эксперимента. - М.: Наука, 1971. - 312 с.
5. Ли Р. Оптимальные оценки, определение характеристик и управление. - М.: Наука, 1966.

 

 

Отдельные номера журналов Вы можете купить на сайте www.5B.ru
Оформление подписки на журнал: http://dis.ru/e-store/subscription/



Все права принадлежат Издательству «Финпресс» Полное или частичное воспроизведение или размножение каким-либо способом материалов допускается только с письменного разрешения Издательства «Финпресс».