Краткий экскурс в теорию

М, А. Кораблин

К66 Информатика поиска управленческих решений. — М.: СОЛОН-Пресс,

2003. — 192 с: ил. — (Серия «Библиотека студента»).

ISBN 5-98003-082-4

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

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

В качестве информационных систем поддержки принятия управленче­ских решений используются Solver (поиск решения на электронных таблицах EXCEL) и Micro Saint (имитационное моделирование).

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

Для быстрого и качественного освоения материалов к книге при­лагается CD-диск.

ББК 32.882 УДК 621.339

Книги издательства «СОЛОН-Пресс» можно заказать наложенным платежом по фиксированной цене. Оформить заказ можно одним из двух способов:

1) послать открытку или письмо по адресу: 123242,Москва,а/я 20;

2) передать заказ по электронной почте (e-mail) на адрес: magazin@soton-r.ru.

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

Через Интернет Вы можете в любое время получить свежий каталог издательства «СОЛОН-Пресск Дли этого надо послать пустое письмо на робот-автоответчик по ад­ресу: katatog@soton-r.ru.

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

Tt J_______________

Введение

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

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

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

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

Введение

Введение

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

Процессы принятия решений

Процессы принятия управленческих решений относятся к катего­рии интеллектуальных процессов, непременным участником которых является носитель естественного интеллекта — человек. С другой сто­роны, информатика поиска управленческих решений — одно из на­правлений искусственного интеллекта — связана с использованием новых информационных технологий и компьютерных моделей, вы­полняющих роль «советчика» в процессе принятия решений. Развитие таких технологий показывает, что подобный симбиоз естественного и искусственного не только все чаще используется в управленческой деятельности, но и в отдельных случаях является необходимым для принятия решения. Если естественный интеллект связан в первую очередь с интуицией и искусством принятия решений, то искусствен­ный обладает особыми качествами, не свойственными человеку. Это в первую очередь способность анализа большого количества вариантов решения и выбора наилучшего в том или ином смысле.

В сфере информационных технологий хорошо известен класс сис­тем поддержки принятия решений (Decision Support System — DSS). Системы этого класса основаны на использовании так называемых решателей задач (Problem Solvers — PS) — пакетов программ, способ­ных решить прикладную задачу. В этом контексте общая структура процесса принятия решения может быть проиллюстрирована рис. 1.1, отражающим вложенности сред принятия решений. Верхний уровень (собственно принятия решений) — уровень взаимодействия лица, принимающего решение (ЛПР), со средой DSS, которая в свою оче­редь использует среду PS. Интерактивность взаимодействий предлага­ет ЛПР наиболее подходящий и со всех сторон «просчитанный» вари­ант решения.

Рис. 1.1. Отношения между DSS, PS и лицом, принимающим решение

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

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

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

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

Введение

Введение

другого решения и т. д. Подобная итерационная технология, извест­ная как технология «что если» (what if, свойственна всем системам класса DSS.

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

• математическое программирование;

• имитационное моделирование;

• эвристическое программирование.

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

Решение любой задачи поиска с помощью DSS-технологий требу­ет формального описания проблемной ситуации. Такое описание выпол­няется с использованием формальных понятий, составляющих основу информационной технологии. Например, в электронных таблицах та­кими понятиями являются: клеточная формула, изменяемая ячейка, граф зависимостей и т. п. Составить описание проблемной ситуации с использованием этих и им подобных понятий не всегда просто. Ино­гда для этого не хватает знаний в области информационной техноло­гии, иногда в предметной области, а иногда даже при наличии таких знаний не удается установить адекватное соответствие между пробле­мной ситуацией и формальной моделью. В этом заключается пробле­ма априорной неопределенности. Ситуация усугубляется еще и тем, что составление описания проблемной ситуации требует использования двух областей знаний: предметной области и формальной (собственно информационной технологии). Как правило, носителями этих знаний являются люди разных специальностей: менеджеры с одной стороны и системные аналитики, программисты, математики с другой сторо­ны, поэтому формализация проблемы требует выработки общего по­нимания, общего языка для описания ситуации. Рисунок 1.2 иллюст­рирует процесс взаимодействия носителей различных знаний — лиц, участвующих в составлении формальных описаний проблемной ситу­ации. Разумеется, что в общем случае круг таких лиц может расширя­ться, при этом взаимодействие между ними в среде DSS определяет новый круг вопросов инженерии знаний.

Рис. 1.2. Формализация проблемной ситуации

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

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

Введение

кое ранжирование может выполняться несколькими функциями, вы­ражающими разные точки зрения на проблему. Возможно, что эти точки зрения принадлежат разным ЛПР. Например, продавец и поку­патель одного и того же товара руководствуются разными критериями и по-разному понимают его оптимальность.

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

В данной монографии излагаются две наиболее распространенные технологии поддержки принятия управленческих решений: поиск ре­шения на электронных таблицах и имитационное моделирование. Первая освещается с использованием широко распространенного па­кета SOLVER (в среде EXCEL), вторая — с использованием учебной версии сравнительно мало известной в России системы Micro Saint [8], широко используемой в университетах США.

Часть 1

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

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

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

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

10

Часть 1. Поиск решений на электронных таблицах

Быстрое начало

11

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

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

Быстрое начало

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

Эта задача была приведена в [1]. В первой части монографии она будет использоваться как сквозной пример для ознакомления со всеми этапами исследований систем управления на электронных таблицах.

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

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

Какое количество красок каждого вида должна производить фабрика,

чтобы доход от реализации продукции был максимальным?

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

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

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

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

Таблица 1

12

Часть 1. Поиск решений на электронных таблицах

Быстрое начало

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

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

Таблица 2

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

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

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

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

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

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

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

Часть 1. Поиск решений на электронных таблицах

Быстрое начало

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

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

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

• ограничения спроса на краски: В23 >= D29; В24 <= СЗО.
Добавление, изменение и удаление ограничений осуществляется с

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

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

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

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

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

• объем производства краски В (ячейка В24) — 1,33 т.
Оптимальное значение целевой ячейки Е24 (при выполнении всех

ограничений) составит 12,65 тыс. долл.

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

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

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

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

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

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

Таблица 3

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

16

Часть 1. Поиск решений на электронных таблицах

Быстрое начало

17

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

Краткий экскурс в теорию

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

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

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

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

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

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

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

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

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

lim_n->~(X_n+1-X_n) = 0.

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

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

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

Контрольные вопросы

1. Какое предположение целесообразно сделать перед разработкой структуры

ЭТ для решения оптимизационной задачи?

2. Что такое размерность оптимизационной задай?

3. Что такое целевая ячейка?

4. Что такое изменяемые ячейки?.

5. Чем отличаются зависимые ячейки от ячеек исходных данных?

\

18

Часть 1. Поиск решений на электронных таблицах

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

19

6. Чем отличаются изменяемые ячейки от ячеек исходных данных?

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

8. Какие ограничения относятся к естественным?

9. Чем полезна структура графа зависимостей для ЭТ, связанной с решением
оптимизационной задачи?

10. В каких ячейках ЭТ программа поиска размещает оптимальное решение
задачи?

11. В какой ячейке размещается оптимальное значение целевой функции?

12. Назовите и охарактеризуйте основные виды задач математического про­
граммирования.

13. Какие задачи математического программирования имеют наиболее эффек­
тивную реализацию на ЭТ?

14. Чем характеризуется итерационный процесс решения задачи?

15. Можно ли рассматривать целевую ячейку как разновидность зависимой?
Почему?

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

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

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

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

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

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

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

ну целевой. Хорошо структурированная таблица характеризуется на-глядным графом зависимостей.

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

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

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

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

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

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

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

20

Часть 1. Поиск решений на электронных таблицах

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

21

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

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

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

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

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

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

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

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

и пленяемых ячеек и «почувствовать» тенденции приближения к опти­муму. Запомните, чем ближе начальные значения к точке оптимума,

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

В этом отношении может может оказаться полезным специальное

средство системы EXCEL — Подбор параметра (меню Сервис).

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

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

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

Управление процессом поиска решения

Нажатие кнопки Выполнить окна Поиск решения приводит к запу­ску процесса поиска решения задачи оптимизации. При невозможно­сти запустить поиск решения система может вывести следующие со­общения:

Недостаточно памяти для решения задачи. Это означает, что ЕXCEL не смог выделить память для поиска решения. Закройте не­нужные файлы или приложения и попытайтесь запустить программу снова.

Часть 1. Поиск решений на электронных таблицах

В другом сеансе EXCEL используется SOLVER. Запущено несколь­ко сеансов работы с EXCEL, в одном из которых используется SOLVER — программа поиска решения. Попробуйте завершить или закрыть окна, связанные с этими сеансами.

Управление процессом поиска решения связано с использовани­ем диалогового окна Параметры поиска решения, которое открывается при нажатии кнопки Параметры окна Поиск решения.

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

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

Группа параметров, определяющих время процесса поиска

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

К настройке этих параметров целесообразно обратиться при полу­чении следующих сообщений о неудачном окончании процесса поис-1 ка решения:

• поиск решения не может улучшить текущее решение. Все огра­
ничения выполнены;

• остановка при исчерпании лимита времени;

• остановка при выполнении максимального числа итераций.

Поиск по сайту: