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

Методические указания

Для выполнения лабораторных работ

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

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

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

Использование электронных таблиц широко распространено для решения многочисленных и разнообразных задач, связанных с учетом и контролем результатов управленческой деятельности: торгово-заку­почных операций, производственных планов, бухучета и т. п. Вместе с тем форма электронной таблицы оказывается очень удобной при ре­шении многих аналитических задач управления деятельностью, и в частности задач исследования операций и поиска оптимальных реше­ний. Для решения таких задач в рамках наиболее распространенной системы электронных таблиц 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.

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

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