8.3. Определение ограничений на управляемые переменные

В реальных условиях на выбор значений управляемых переменных, как правило, наложены ограничения, связанные с ограниченностью имеющихся ресурсов, мощностей и других возможностей. При построе­нии математической модели эти ограничения обычно записывают в виде равенств и неравенств или указывают множества, которым должны при­надлежать значения управляемых переменных.

Например, если месячный объем выпуска продукции цехом является управляемой переменной, то ее значения не могут быть отрицательными и ограничены сверху максимальной производительностью оборудования цеха V_max, т.е. если V - объем месячного выпуска, то 0<=V<=V_max..

8.4. Выбор общей модели расчета параметров состояния

При выборе модели расчета параметров состояния системы исполь­зуется одна из известных общих моделей: управления запасами, общая линейная модель распределения, модель задачи о назначениях, модель за­дачи о размещениях (транспортная задача), динамического программирования,"продавца газет", "дерево решений".

Для управления запасами наиболее простая общая модель расчета параметра состояния системы у, представляемого в виде издержек, зави­сящих от:

• расходов, связанных с размещением заказа и поставок партии - к;

• издержек на содержание единицы продукции в единицу времени - S;

• спроса - V;

• размера партии поставок q, имеет вид

y = L = + ,

где L - издержки на содержание запаса в единицу времени.

Эта модель справедлива при условиях, что:

- уровень запаса снижается равномерно в соответствии с равномерно

поступающими требованиями V (спросом), который может быть опреде­лен как:

V = ,

где Q - общий объем поставок;

Т - время обеспечения запасом в объеме Q.

- заказ на поставку партии подается, когда запас исчерпан и выполняется мгновенно.

- расходы, связанные с размещением заказа и поставок партии не за­ висят от объема партии и равны постоянной величине "к".

Если в качестве параметра процесса взять время t, то издержки от начала процесса (момента t_o=0 поставки первой партии q) будут рассчитываться по формуле:

L(t) = ( + ) t ,

Эта модель может использоваться как для определения «фактического» состояния по истечении некоторого интервала времени, меньшего или равного Т, так и прогнозирования издержек на поддержа­ние запаса в оставшейся до момента Т временной отрезок. Так, положив t равным Т, получим прогноз общих издержек при работе с принятой пар­тией q, вычисляемых по формуле:

L(t) = + s T ,

Подставляя вместо Vего значение V = получим:

L(t) = kn + S T ,

где п = есть количество произведенных циклов поставки.

Для прогнозирования издержек в произвольный момент времени t₁ (0< t₁ < Т) определим оставшийся отрезок времени (Т – t₁) и объем по­ставки Q(T-t₁).

Тогда расчет параметра состояния L (издержек) в зависимости от не­управляемых (постоянных) параметров k, S, V и управляемой перемен­ной q в любой момент времени t₁ будет осуществляться по формуле:

L(k, S, Q(t), T(t), q) = + S (T-t₁)

В распределительных задачах модель определения состояния связы­вает параметры состояния - величину получаемой прибыли, убытка, вре­мени выполнения работ, издержек материалов, трудовых ресурсов и т.д. - со значениями распределяемых величин через постоянные параметры, ха­рактеризующие "вклад" каждой распределяемой величины в данную ха­рактеристику состояния.

Например, в цехе имеется три группы взаимозаменяемого оборудования с мощностями M₁, M₂, M₃ норма-часов в месяц. Цеху необходимо выпустить 5 видов продукции в объемах П₁, П₂, П₃, П₄, П₅. Время изго­товления единицы каждого вида продукции j на i - оборудовании со­ставляет t_ij. Например, время изготовления единицы продукции П₂ на первом виде оборудования t₁₂ ⁼ 0,6 часа. Известны денежные затраты на изготовление единицы продукции j на каждом i-виде оборудования. Например, затраты на изготовление единицы П₃ на втором виде обору­дования составляют Z₂₃ = 40 рублей. Известна отпускная цена C₁ каждо­го вида продукции C₁, C₂, С₃, C₄, C₅.

Процесс распределения состоит в размещении заказов по видам обо­рудования, т.е. определении доли xij объема продукции П_j на каждом ви­де оборудования i.

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

1. Состояние по загрузке мощностей y₁.

2. Состояние по выполнению объема у₂.

3. Состояние по прибыли у₃.

Состояние y₁ включает три компонента у₁₁, у₁₂, у₁₃ , определяющие загрузку групп оборудования:

y₁₁ = t₁₁ x₁₁ + t₁₂x₁₂ + t₁₃x₁₃ + t₁₄x₁₄ + t₁₅x₁₅

y₁₂ = t₂₁x₁₁ + t₂₂x₂₂ + t₂₃x₂₃ + t₂₄x₂₄ + t₂₅x₂₅

y₁₃ = t₃₁ x₃₁ + t₃₂x₃₂ + t₃₃x₃₃ + t₃₄x₃₄ + t₃₅x₃₅

Состояние у₂ включает пять компонентов y₂₁……y₂₅ , определяю­щих выполнение заданий по изделиям при их изготовлении на различных группах оборудования:

y₂₁ = x₁₁ + x₂₁ + x₃₁

y₂₂ = x₁₁ + x₂₂ + x₃₂

………………………..

y₂₅ = x₁₅ + x₂₅+ x₃₅

Состояние у_з характеризуется числовым значением прибыли, определяемой как сумма произведений прибыли от одной единицы продукции на ее количество х_ij:

y₃ = ,

или y₃ = (C₁ – Z₁₁) x_n + (C₂ – Z₁₂) x₁₂ + …..+ (C₅ – Z₁₅) x₁₅ + (C₁ – Z₂₁) x₂₁ + ……..+ (C₅ – Z₂₅) x₂₅ + (C₅ – Z₃₁) x₃₁ + …. + (C₅ – Z₃₅) x₃₅

Параметром процесса в распределительных задачах являются момен­ты поступления входных данных.

Расчет параметров состояния в модели динамического программиро­вания производится путем разбивки процесса принятия решения на ряд однотипных этапов, каждый из которых планируется отдельно, но с уче­том состояния системы на начало этапа и последствий принятого решения в будущем. Последний этап изучается отдельно и планируется наилучшим образом.

Состояние системы на каждом этапе определяется набором характе­ристик x₁, x₂, х_n. Дальнейшее изменение ее состояния зависит только от данного состояния и не зависит от того, каким путем система пришла в него. На каждом шаге выбирается одно решение, под действием которого система переходит из предыдущего состояния в новое, причем это реше­ние связано с выигрышем или потерей, которые зависят от состояния на начало этапа и принятого решения. Программирование разворачивается от конца к началу. Оно осуществляется на основе предложений об ожи­даемых исходах предшествующего, еще неисследованного состояния. На­ходится наилучшее управление, зависящее от возможных исходах (характеристик состояния) предыдущего этапа. Завершив анализ конеч­ного этапа, рассматривают аналогичную задачу для предпоследнего эта­па, требуя, чтобы функция цели достигла экстремального значения на двух последних этапах вместе. Проделав такой процесс определения наи­лучших (условно-оптимальных) управлений для каждого шага от конца к началу, а затем от начала к концу находят оптимальное управление (стратегию) для каждого шага с точки зрения всего процесса.

Рассмотрим простейший пример применения модели расчета пара­метров состояния методом динамического программирования.

Пусть задана транспортная железнодорожная сеть (рис. 8), на кото­рой указаны пункт отправления А, пункт назначения В и расстояние меж­ду пунктами. Требуется составить маршрут из пункта А в пункт В мини­мальной длины.

Рис. 8. Транспортная сеть.

Для использования модели динамического программирования разо­бьем расстояние между А и В на этапы как показано на рис. 9 . Оценим отрезки, на которые делят участки сети этапы 2-2 и 3-3. Например, этап 2-2 делит участок длиной 5 на два участка длиной 2,5. Последний этап 2-2 характеризуется состоянием, включающем три точки (D₁, D2 и D3). Выбор кратчайшего пути начнем с конца. Определим точку состояния, соответ­ствующую минимальному пути до точки В. Для точки D₁ min (10; 8+4; 8+3+5) = 10; для D₂ min (5+4; 5+3+5) = 9; для D₃ min (2,5+3+4; 2,5+5) - 7,5. (Эти расстояния указаны в скобках). Далее рассматриваем состояние второго этапа, включающие точки C₁, С₂, С₃. Кратчайшее расстояние от этих точек до пункта В показаны в скобках. Наконец находим длину ми­нимального пути, ведущего из А в В. Это расстояние равно 23 единицам. Затем проходим этапы в обратном порядке и находим кратчайший путь. Он выделен жирной линией.

Рис. 9. Этапы решения задачи. . ..

Эта задача находит применение для определения значений C_ij -удельных затрат на перевозку (тарифов) - в транспортной задаче.

Для того чтобы использовать модель "дерево решений" необходимо отразить процесс принятия решения в виде перехода системы из одного состояния в другое. Он включает последовательность состояний и связей между ними и изображается в виде графа, моделирующего варианты воз­можного перехода системы из исходного события в завершающее. Узлы отражают состояния, в которых возникает необходимость выбора (принятия решения), а ветви - события, которые могут иметь место после принятия решения.

При этом существует два вида решений, выбираемых ними и осу­ществляемых "природой" и "рынком". Такой подход можно использо­вать для решения задач, связанных с неопределенностью развития систем, перехода из одного состояния в другое в условиях неопределенности.

Например, пусть модель, представленная на рис. 10, отражает фраг­мент модели организации студентами мероприятия "Элегант - шоу".

а) -200р

Рис. 10. Граф состояний

Блок 1 отражает исходное состояние, ветвь А - заключение договора с- ДК "Интеграл", ветвь В - отказ от договора.

В случае заключения договора (ветвь А) вероятность "решения" при­родой того, что будет найдено необходимое количество команд (ветвь N) равная 0,3, а не найдено (ветвь М) равна 0,7. В блоках 3 и 4 принимаются решения: проводить рекламную компанию (ветвь С) или не проводить (ветвь D). В случае проведения компании природа может обеспечить осу­ществление "Элегант - шоу" и обеспечить получение выручки 5 тыс. руб­лей или не проведение и убыток в 200 рублей. Для определения "иены" узлов 5, 6, 3 и 4 используются условные вероятности, а для нахождения оптимальной стратегии - метод динамического программирования.