34. Классификация методов поддержки принятия ур (мппур)

МППУР можно разделить на три большие группы:

• методы формализованного представления объекта управления;

• методы активизации использования интуиции и опыта участников процесса принятия решения (эвристические);

• информационно-технологические методы поддержки принятия решений.

Мы поддерживаем мнение В.Н. Волковой о том, что такая классификация методов более целесообразна, чем их разделение на количественные и качественные, поскольку точнее отражает сущность методов / 3 /. Следует уточнить, что Волкова пишет о классификации моделей представления объектов управления. На наш взгляд, это не совсем точно, т.к. эти методы далеки от прямых аналогий с объектом управления, а представляют собой концептуализацию отношения к объекту управления необходимую для дальнейшего моделирования и принятия УР (См. раздел ).

Рис. Классификация методов поддержки принятия УР

10. Методы формального представления объекта управления.

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

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

Затем (2) идут статистические методы. Мы их рассматривали на примере принятия УР в условиях риска и неопределённости. Они используют теорию вероятностей, теорию игр и теорию статистических решений. Деревья решений – графический метод представления задач с риском, пример использования статистического метода (См. раздел … ).

Теоретико-множественные методы (3) имеют огромное значение на стадии проектирования систем. Они позволяют избежать неоправданных затрат в том случае, если без предварительных исследований принято неудачное решение. Их изучение выходит за рамки данного курса. В качестве примера можно привести SADT-моделирование (сокращение SADT переводится как системный анализ и технология проектирования), учебники по которому и необходимые программные продукты есть в Интернете.

Рис. Две взаимосвязанных SADT-модели

Примером использования математической логики (4) при ППУР являются бинарные деревья (см. выше).

Примерами использования графо-семиотических методов (5) при ППУР являются диаграммы Ганта и сетевые графики. (См. раздел … )

На рис. … , где представлены МППУР, перечень формальных методов заканчивается онтологическими моделями. Эти модели описаны в учебниках по искусственному интеллекту и представляют собой формальное описание так называемых «словесных» моделей (См. раздел …)

Само принятие решения выходит за рамки рассмотренных методов, а также исследования операций и относится к компетенции ЛПР.

Линейное программирование (ЛП) при РУР.

По мнению ряда авторов, этим методом решается около 75% практических задач менеджмента⁴. Однако, этот вывод сделан американскими исследователями, которые акцентируют своё внимание на формальных МППУР, и относится главным образом к задачам производственного менеджмента. Роль слабоструктурированных задач и эвристических методов ими существенно принижается. Более широкий взгляд на менеджмент свойственен российским учёным⁵. Поэтому трудно однозначно оценить роль ЛП при разработке УР. Очевидно, однако, что аналитическая проработка ряда проблем необходима для ЛПР и современный менеджер должен иметь о ней ясные представления.

Модели ЛП являются частью более широкого класса – моделей принятия решений в условиях ограничений. В моделях ЛП эти ограничения описываются линейными функциями.

Кроме того, рассматриваемые модели – это модели оптимизации, причём показатель эффективности, который надо максимизировать или минимизировать называется целевой функцией. Отметим, что математические описания целевой функции и объекта управления – также линейные.

Модель ЛП призвана так распределить ограниченные ресурсы, чтобы оптимизировать целевую функцию.

Возможные тематики задач ЛП:

• рациональное использование сырья и материалов;

• задачи оптимизации раскроя;

• оптимизации производственной программы предприятий;

• оптимального размещения и концентрации производства;

• на составление оптимального плана перевозок, работы транспорта;

• управления производственными запасами;

и многие другие, принадлежащие сфере оптимального планирования.

Рассмотрим простейшие приёмы решения задач ЛП. Этого достаточно, чтобы иметь общее представление о решении таких задач.

Графический метод решения задач ЛП с двумя переменными.

Рассмотрим простейшую модель ЛП с двумя переменными на следующем примере.

Компания производит краску для внутренних и наружных работ из сырья двух типов: M_l и М₂.

Следующая таблица представляет основные данные для задачи.

	Расход сырья (в тоннах) на тонну краски		Максимально возможный ежедневный расход сырья
	для наружных работ	для внутренних работ
Сырье М1	6	4	24
Сырье М2	1	2	6
Доход (в тыс. долл.) на тонну краски	5	4

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

Данная модель ЛП, как и любая аналогичная задача, включает три основных элемента.

1. Переменные, которые следует определить.

2. Целевую функцию, подлежащую оптимизации.

3. Ограничения, которым должны удовлетворять переменные.

Введём переменные для данной модели:

х₁ – ежедневный объем производства краски для наружных работ;

х₂ – ежедневный объем производства краски для внутренних работ.

В качестве целевой функции возьмём суммарный ежедневный доход. Обозначим её через z (она измеряется в тысячах долларов), тогда

Z= 5x₁ + 4x₂.

Ограничения на сырье записываются в виде неравенств 1 – 6 (см. рис…). На том же рис. показана область допустимых значений, ограниченная линиями 1 – 6.

Рис. … Пространство допустимых решений

Для нахождения оптимального решения посмотрим, в какой точке пересечения прямой, соответствующей целевой функции и области решения значение Z=max (см. рис.)

Рис. Поиск оптимального решения

На рис. видно, что максимум целевой функции достигается в точке С (Z=21т.). В дальнейшем при Z>21т. прямая, соответствующая целевой функции, не пересекается с областью решений.

Метод решения задач ЛП с помощью специализированных программных средств.

Одно из самых доступных программных средств решения задач ЛП – это надстройка MS Excel «Поиск решения».

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

Чтобы решить задачу о том, сколько и каких стульев произвести за неделю для получения наибольшей прибыли, надо использовать следующую модель ЛП:

1. x и y – переменные – количество стульев 1-го 2-го типов, выпускаемых в неделю;

2. z= 56x + 40y – целевая функция, которую надо максимизировать (это сумма произведений соответствующего количества стульев на прибыль от продажи каждого стула;

3. Ограничения.

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

8x + 4y <= 1280;

4x + 12y <= 1600;

4x + 4y <= 760;

x <= 140;

y <= 120.

Затем идёт условие диктуемое рынком:

x + y >= 100.

Последнее необходимое физически условие не отрицательности:

x, y >= 0.

На 1-м слайде при помощи электронной таблицы запрограммирована данная задача; на 2-м при помощи указанной надстройки получено оптимальное решение. (См. рис. )

Рис.

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

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

Транспортные модели в задачах ЛП.

Транспортные модели (задачи) – специальный класс задач ЛП. Эти модели описывают перемещение (перевозку) какого-либо товара из пункта отправления (исходный пункт, например место производства) в пункт назначения (склад, магазин).

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

Рис. Схема транспортной задачи

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

Рассмотрим пример транспортной задачи, решённой методом ЛП.

У компании есть два завода и три магазина-склада. Первый завод может поставлять не больше 100 единиц определённой продукции, а второй – не более 200 единиц. В 1-м магазине-складе может храниться не более 150 единиц продукции, во 2-м – 200; в 3-м – 350 единиц продукции. Цена продажи единицы продукции составляет в 1-м магазине $12, во 2-м - $14, в 3-м - $15.

Суммарные затраты на производство единицы продукции на заводе i и доставку её в магазин-склад j содержатся в ячейках B11:D12 таблицы.

Модель ЛП описывается имеет следующий вид:

Целевая функция: Z=4x₁₁+5x₂₁+4x₁₂+5x₂₂+3x₁₃+4x₂₃.

Причём в этом выражении переменные x_ij умножаются на доход от продажи продукции, определяемой разностью цены товара и стоимости его перевозки (например, для 1-го товара 12-8=4).

Ограничения: x₁₁+x₁₂+x₁₃<=100;

x₂₁+x₂₂+x₂₃<=200;

x₁₁+x₂₁<=150;

x₁₂+x₂₂<=200;

x₁₃+x₂₃<=350;

xij>=0.

Решение задачи методом ЛП приведено на рис.

Рис. … Табличная запись транспортной задачи

Сетевые модели.

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

Рассмотрим, например, модель перевозок.

Предположим, что из пункта 1 (узел 1 сети) в пункты 3 и 4 должны быть перевезены крупногабаритные изделия. Их количество равно 10. Причём в пункт 3 должно быть доставлено три изделия, а в пункт 4 семь изделий. В соответствии с рассматриваемой задачей на рис. приведена сетевая диаграмма, на которой указаны возможные маршруты перевозки, а также данные о затратах Cij и пропускной способности Uij сети.

Рис. Сетевая диаграмма задачи о перевозках

Будем решать задачу методом ЛП.

Сначала надо определить целевую функцию. Она представляет собой стоимость перевозки груза, которую надо постараться минимизировать.

Z=c₁₂u₁₂+c₂₃u₂₃+c₂₄u₂₄+c₂₅u₂₅+c₃₄u₃₄+c₄₃u₄₃+c₅₄u₅₄+c₅₃u₅₃;

Ограничения определятся балансом привозимых и увозимых изделий. Причём число вывозимых изделий – положительное, а число привозимых – отрицательное. Тогда:

u₁₂=10;

-u₁₂+u₂₃+u₂₄+u₂₅=0;

-u₂₃-u₄₃-u₅₃+u₃₄=-3;

-u₂₄+u₄₃-u₃₄-u₅₄=-7;

-u₂₅+u₅₃+u₅₄=0.

Кроме того в ограничения входит условие не отрицательности для Uij и для Cij, т.е. Uij>=0 и Cij>=0.

Проведённого анализа достаточно, чтобы решить задачу средствами MS Excel.

Нелинейное программирование.

Рассмотрим нелинейное программирование на примере рекламной деятельности предприятий. Она связана в первую очередь с задачей выбора средств массовой информации (СМИ). Обычно вопрос заключается в том, сколько рекламных блоков следует приобрести фирме в каждом из возможных СМИ. Под СМИ имеются в виду радио, телевидение, газеты, журналы, средства Интернет.

Цель рекламной компании – её максимальная эффективность. Ограничения, с которыми приходится считаться при принятии решения, обычно связаны с бюджетом на рекламу и возможностями её размещения в различных СМИ. Могут быть специфические требования, например, на газетную рекламу должно быть потрачено не менее 30 тыс. руб., или, напротив, чтобы на один вид СМИ тратилось не более фиксированного процента бюджета.

Наконец, на решение может оказать влияние «закон снижения отдачи»: эффективность рекламного блока снижается с увеличением числа его показов в СМИ на протяжении определённого периода времени. Например, десятый показ рекламного ролика на телевидении в течении недели, как правило, не оказывает такого влияния на аудиторию, как первый и второй.

Таким образом, связь между спросом на продукт и рекламной компанией недостаточно чёткая, чтобы можно было на её основе построить объективную модель. Поэтому обычно используется следующий подход: отдача от определённой рекламы в данных СМИ оценивается в специальных единицах, так называемых единицах воздействия. Это субъективная мера, основанная на оценке менеджером определённой рекламной продукции, на основе восприимчивости потенциального рынка и т.д. Иными словами это некая мера ценных свойств конкретной рекламы. Единицу воздействия можно рассматривать как разновидность экономической единицы полезности (ютиля), а её зависимость от числа рекламных объявлений как разновидность функции полезности. В этом случае задача рекламной компании – максимизировать сумму единиц полезности (единиц воздействия) при заданных затратах на рекламу.

Рассмотрим пример. На рекламную компанию выделено $72 000. Известно, что реклама даёт следующий результат (См.табл.)

Как уже отмечалось, эффективность рекламы изменяется от её воздействия на целевую аудиторию. Это воздействие в общем случае нелинейно. На предприятии решили выбрать 100 бальную шкалу оценки эффективности каждого рекламного объявления. Для перехода от задачи нелинейного программирования к задаче ЛП решили следующим образом аппроксимировать зависимость эффективности рекламы от количества рекламных объявлений. Считается, что первые 10 объявлений имеют повышенную эффективность, а затем эта эффективность падает (см. табл.).

Размещение рекламы	Первые 10 объявлений	Последующие объявления
Дневное радио Вечернее ТВ Ежедневная газета	60 80 70	40 55 35

Руководство предприятия хочет, чтобы рекламная компания проводилась с определёнными критериями:

1. В каждом СМИ должно быть размещено не более 25 рекламных объявления;

2. Общими усилиями всех СМИ нужно добиться покупки 1 800 000 единиц товара;

3. Не менее одной четверти рекламных объявлений должно выйти на вечернем ТВ.

Формализуем модель выбора СМИ в виде задачи ЛП. Для этого введём следующие обозначения:

x₁ – число объявлений на дневном радио, если оно не превышает 10;

y₁ – число объявлений на дневном радио, превышающее 10;

x₂ – число объявлений на вечернем ТВ, если оно не превышает 10;

y₂ – число объявлений на вечернем ТВ, превышающее 10;

x₃ – число объявлений в ежедневной газете, если оно не превышает 10;

y₃ – число объявлений в ежедневной газете, превышающее 10.

Целевую функцию в этом случае надо максимизировать. Она имеет вид:

Z=60x₁+40y₁+80x₂+55x₂+70x₃+35y₃.

Ограничения:

Исходя из табл. … и учитывая деньги, отпущенные на рекламу, получаем 1700(x₁+y₁) + 2800(x₂+y₂) + 1200(x₃+y₃)<=72000;

Исходя из ограничений на количество объявлений: x₁+y₁<=25, x₂+y₂<=25, x₃+y₃<=25;

Исходя из количества проданных товаров

30 000(x₁+y₁) + 60 000(x₂+y₂) + 45 000(x₃+y₃)>=1 800 000;

Наконец, условие, касающееся объявлений на вечернем ТВ следующее

(x₂+y₂)/(x₁+y₁+x₂+y₂+x₃+y₃)>=1/4.

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

x₂+y₂>=0,25(x₁+y₁+x₂+y₂+x₃+y₃).

Остались только формальные ограничения на положительность переменных и задача может быть решена средствами ЛП, например, с помощью надстройки «Поиск решения».

Модели систем массового обслуживания; очереди.