По курсу «Теория принятия решений»

Теоретическая часть

Поиск управленческих решений на электронных таблицах

Использование электронных таблиц широко распространено для решения многочисленных и разнообразных задач, связанных с учетом и контролем результатов управленческой деятельности: торгово-заку­почных операций, производственных планов, бухучета и т. п. Вместе с тем форма электронной таблицы оказывается очень удобной при ре­шении многих аналитических задач управления деятельностью, и в частности задач исследования операций и поиска оптимальных реше­ний. Для решения таких задач в рамках наиболее распространенной системы электронных таблиц EXCEL используется пакет программ поиска решения (Solver). Этот пакет основан на использовании алго­ритмов и методов математического программирования — одного из основных направлений теории исследования операций.

Процесс исследования системы на электронных таблицах можно рассматривать как естественное продолжение обычной ежедневной практической деятельности, связанной с вычислениями на таблицах. Для этого нужно просто посмотреть на эту деятельность под другим углом зрения и задаться вопросом: «А что, если?..» Что если изменить условия оплаты товара, что если увеличить площади складских поме­щений и т. п. К каким изменения это приведет? Ответ на такой во­прос тесно связан с размышлениями на тему какова оптимальная стратегия и тактика использования производственных ресурсов, как достигнуть «точки оптимума» и как поддерживать баланс «в ее окрест­ности». Ответы на эти вопросы и определяют основную цель исследования любой системы. Здесь же нам важно подчеркнуть естественную связь между обычными вычислениями на электронных таблицах и поиском оптимальных управленческих решений на тех же таблицах.

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

Пример

Задача о красках

Данный пример предназначен для ознакомления со всеми этапами исследований систем управления на электронных таблицах.

Условие задачи. Фабрика изготовляет два вида красок: для внут­ренних (В) и наружных работ (Н). Продукция обоих видов поступает в оптовую продажу. Для производства красок используются два ис­ходных продукта — П1 и П2. Максимально возможные суточные за­пасы этих продуктов составляют 6 и 8 т, соответственно. Расходы продуктов П1 и П2 на одну тонну соответствующих красок приведены в таблице.

Исходный продукт	Расход исходных продуктов в тоннах на тонну краски	Максимальный запас исходных продуктов (т)
	Краска Н	Краска В
П1		2
П2

Изучение рынка сбыта показало, что суточный спрос на краску В никогда не превышает спроса на краску Н более чем на 1 т. Кроме того, установлено, что спрос на краску В никогда не превышает 2 т в сутки. Оптовые цены одной тонны красок равны: 3 тыс. долл. для краски Н и 2 тыс. долл. для краски В.

Какое количество красок каждого вида должна производить фаб­рика, чтобы доход от реализации продукции был максимальным?

Приступая к решению этой задачи, предположим, что нам при­мерно известно, сколько краски нужно производить (например, 4 т краски Н и 2 т краски В).

Аналогичное предположение целесообразно делать при решении лю­бой оптимизационной задачи, поскольку оно значительно упрощает про­цесс разработки структуры электронной таблицы (ЭТ).

Сделав такое предположение, составим ЭТ, которая позволяет рассчитать расходы продуктов на производство красок и получаемый доход (см. табл. 1, 2).

Анализируя табл. 1, замечаем, что расходы продуктов П1 и П2, необходимые для производства красок в соответствии с нашим пред­положением, превышают максимальный суточный запас. Следовате­льно, получить 16 тыс. долл. дохода невозможно.

Таблица 1

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

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

Таблица 2

В этом смысле усложнение задачи связано с увеличением ее раз­мерности (количества изменяемых ячеек) и числа ограничений. Прак­тические задачи оптимизации включают в себя десятки и даже сотни изменяемых ячеек и ограничений. В таких случаях на помощь прихо­дят специальные программы — решатели оптимизационных задач. Одна изтаких программ — Solver — включена в систему Microsoft Ex­cel как дополнение Поиск решения(раздел меню Сервис).

Поиск решения

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

В поле Установить целевую(ячейку) окна Поиск решениянеобхо­димо ввести имя (адрес) соответствующей ячейки. Для нашего приме­ра это ячейка Е24. Затем указывается вид оптимизации путем «нажа­тия» соответствующей кнопки, расположенной непосредственно под полем целевой ячейки.

В поле Изменяя ячейкиуказываются имена (адреса) ячеек, содер­жимое которых подбирается программой поиска решения таким обра­зом, чтобы обеспечить требуемое значение целевой ячейки. Для на­шего примера изменяемыми ячейками являются В23, B24, содержа­щие объемы суточного производства красок.

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

В поле Ограничениядолжны быть введены все ограничения, свя­занные с решаемой задачей. В нашем примере такие ограничения де­лятся на три группы:

• естественные ограничения: В23:В24 >= 0 (они вводятся путем нажатия на кнопку Параметры, а затем кнопку Неотрицатель­ные значения);

• ограничения по запасам исходных продуктов: E16:E17<=D16:D17;

• ограничения спроса на краски: В23 >= D29; В24 <= СЗ0.

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

Нажатие кнопки ДобавитьилиИзменитьприводит к вызову до­полнительного окна определения ограничений. В поле Ссылка на ячейкувводится левая часть ограничения. Список Ограничениевклю­чает в себя отношение равенства, «больше или равно», «меньше или равно», отношение цел, которое означает, что левая часть ограниче­ния должна быть целым числом, отношение двоич,означающее, что левая часть ограничения должна быть двоичным числом (т. е. прини­мающим значения 0 или 1). При использовании отношений цели двоичполе справа от списка ограничений остается пустым. При испо­льзовании любого другого отношения в этом поле размещается пра­вая часть ограничения.

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

Для нашей задачи о красках оптимальное решение будет опреде­ляться следующими значениями изменяемых ячеек:

• объем производства краски Н (ячейка В23) — 3,33 т;

• объем производства краски В (ячейка В24) — 1,33 т.

Оптимальное значение целевой ячейки Е24 (при выполнении всех ограничений) составит 12,65 тыс. долл.

Виды ячеек и зависимости

Выше мы уже использовали понятия изменяемой ячейки и целевой ячейки. Изменяемые ячейки всегда содержат числовую информацию, которая подбирается в процессе поиска решения таким образом, что­бы обеспечить оптимальное значение целевой ячейки. Кроме того, в процессе поиска используются еще два вида ячеек:

• ячейки исходных данных;

• зависимые ячейки.

Ячейки исходных данных содержат числа, которые не меняются программой поиска решения (Solver), зависимые ячейки содержат формулы, которые неоднократно перевычисляются в процессе поиска решения.

Наличие зависимостей между ячейками разных видов в среде EXCEL может быть проиллюстрировано графом зависимостей, по­строенным непосредственно на структуре таблицы (см. табл. 3). По­строение такого графа связано с использованием меню Сервис(Зави­симости, Панель зависимостей).

Таблица 3

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

Основы теории

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

Любая переменная (изменяемая ячейка в ЭТ) обычно интерпре­тируется как некоторый ресурс (например, ресурс времени, материа­ла, продукта, валюты), выраженный в количественном измерении (минуты, тонны, штуки, рубли). Задача оптимизации состоит в том, чтобы подобрать такие значения переменных, при которых целевая функция (целевая ячейка ЭТ) принимает максимальное, минималь­ное или заданное значение (оптимальное значение), при этом най­денные значения переменных в совокупности составляют оптималь­ное решение задачи.

В классическом исследовании операций задачи матема­тического программирования делятся на несколько различных типов в зависимости от вида целевой функции и ограничений. К основным типам относятся задачи линейного и нелинейного программирования. Для первого типа характерна целевая функция, линейно зависящая от пе­ременных (ресурсов) исследуемой системы, и такие же линейные ограничения. Если же целевая функция или хотя бы одно из ограни­чений нелинейно зависит от переменной (хотя бы одной), задача от­носится к типу нелинейного программирования. В качестве примеров нелинейностей можно привести зависимости видов Xi*Xj, Xi/Xj, log(Xi) (вычисление логарифма от Xi), MIN(Xi,Xj,Xk), Xj² (квадрат Xj) и т. д. Здесь Xi, Xj — переменные задачи.

Если оптимизационная задача должна решаться в целых числах, когда хотя бы одна из переменных модели должна измеряться в шту­ках (станках, автобусах и т. п.), говорят о целочисленном программиро­вании. Наконец, если хотя бы одна из переменных может принимать только одно из двух значений (0 или 1), говорят о булевском програм­мировании.

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

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

Итерационные процессы поиска должны обладать свойством схо­димости вычислений. Это свойство заключается в том, что разность результатов, получаемых на n-ом и (n+1)-ом шаге вычислений, дол­жна с ростом n стремиться к нулю:

Здесь - значения изменяемых ячеек на n-ой и (n + 1)-ой итерации. Практически п ограничивается конкретным значением N — количеством итераций. Количество итераций определяет число шагов в последовательности приближений текущего решения задачи к опти­мальному, при этом время, затраченное на реализацию такой после­довательности, определяет время поиска оптимального решения. По умолчанию в программе Solver: N = 100.

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

Итерационные процессы могут отличаться также методами реали­зации вычислений. Для линейных моделей используется главным об­разом так называемый симплекс-метод, для нелинейных — метод Ньютона и метод сопряженных градиентов. Они кратко комментиру­ются в разделе «Поиск решения».

Поиск решения

Общие рекомендации по разработке структур электронных таблиц

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

Необходимым условием корректной структуры ЭТ, используемой для решения оптимизационной задачи, является наличие изменяе­мых ячеек и целевой ячейки.

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

При оформлении оптимизационной задачи в структуре электрон­ных таблиц рекомендуется использовать во всех текстовых ячейках, содержащих названия столбцов и/или строк, определение размерно­сти содержимого ячейки. Например «т» (тонна), или «час», или «долл.» и т. п. Использование размерностей способствует выявлению грубых ошибок, связанных, например, с умножением «столов на сту­лья» и получением в результате «тонн в минуту».

Просмотрите разработанную структуру ЭТ с использованием гра­фа зависимостей: все стрелки должны быть направлены от изменяе­мых ячеек и ячеек исходных данных через зависимые ячейки в сторону целевой. Хорошо структурированная таблица характеризуется на­глядным графом зависимостей.

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

Старайтесь использовать в ЭТ числа по возможности одного по­рядка или близких порядков (например, 10 и 100). Это упрощает про­цесс поиска решения и позволяет избежать многих вычислительных ошибок. Например, в рассмотренной выше задаче о красках оптовая цена тонны краски выражается в тысячах долларов. Однако в таблице используются значения 3 (тыс. долл.) и 2 (тыс. долл.), а не 3000 долл. и 2000 долл. Это сделано специально в стиле этой рекомендации.

В процессе разработки ЭТ вы можете столкнуться с ситуацией, когда отдельные ограничения «не вписываются» в структуру таблицы. В этом случае такие ограничения целесообразно оформить в виде от­дельной таблицы, связанной с вашей задачей. В этом стиле оформле­на, например, таблица «Ограничения суточного спроса по видам кра­сок» (см. табл. 1).

Использование ЭТ для решения оптимизационной задачи будет более наглядным, если вы будете использовать именование ячеек. До­стоинства именования ячеек наглядно проявляются при работе с про­граммой поиска решения, при анализе отчетов по результатам моде­лирования и при построении сводных таблиц по результатам исследо­ваний системы.

Например, мы хотим назвать ячейку В23, в которой сохраняется суточный объем производства краски для наружных работ, именем Краска_Н, ячейку В24 с аналогичным содержимым — именем Краска_В, а целевую ячейку с общим доходом — именем Общий_доход. Для этого мы последовательно выделяем каждую из этих ячеек в таб­лице и обращаемся к меню Вставка, раздел Имя,оператор Присвоить, который открывает окно именования. В это окно вводится соответст­вующее имя, и в дальнейшем во всех отчетах поименованная ячейка будет идентифицироваться присвоенным ей именем.

Стиль оформления ограничений

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

Плохой стиль	Хороший стиль
В21<=С21;В22<=С22;	В21:B22<=С21:С22
Е4>=12;	E4>=G7; (В ячейке G7 размещено число 12)
G4+К4=N4;	L7=N4; (В ячейке L7 размещена формула =G4+K4)

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

Ниже приводятся некоторые рекомендации по оформлению огра­ничений на оптимальное решение задачи.

Старайтесь избегать избыточных ограничений. Тривиальный при­мер таких ограничений: В23<=16, В23<=20. Избыточные ограничения всегда «мешают» процессу поиска и в некоторых случаях могут приве­сти к зацикливанию вычислений.

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

Противоречивые ограничения делают процесс поиска бессмыслен­ным. Тривиальный пример таких ограничений: В24 <= СЗ0; В24 >= СЗ0+2. Такие ограничения всегда связаны с отсутствием ре­шения задачи. Основная проблема, связанная с противоречивыми ограничениями, заключается в том, что для сложных задач с большим числом ограничений весьма трудно выявить противоречия между от­дельными ограничениями.

Проблема начальных значений

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

В этом отношении может может оказаться полезным специальное средство системы EXCEL — Подбор параметра(меню Сервис).

В поле Установить в ячейкеуказывается адрес (имя) ячейки, со­держащей формулу (в нашем случае это целевая ячейка Е24), которая устанавливает зависимость от изменяемой ячейки (в нашем случае это В23). Подбор параметра позволяет подобрать такое значение из­меняемой ячейки, при котором целевая получит установленное нами значение (в этом примере 16).

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

Результат работы программы подбора параметра занесется в ячей­ку, указанную в поле Изменяя значение ячейки (в нашем примере В23).

.