Министерство общего и профессионального образования Российской Федерации

Сибирский государственный индустриальный университет

Кафедра информационных технологий в металлургии

Технологии реализации алгоритмов методов и решения задач оптимизации средствами Excel

Методические указания к выполнению практических занятий по курсу “Информационные технологии в металлургии”. Специальности: “Металлургия черных металлов” (110100), специализации “Информационные технологии и предпринимательство в металлургии” (110107), “Математическое обеспечение и применение ЭВМ в металлургии” (110104)

Новокузнецк

1999

УДК 681.3.06

Технологии реализации алгоритмов методов и решения задач оптимизации средствами Excel: Метод. указ. / Сост.: С.П. Мочалов, В.И. Кожемяченко: СибГИУ. - Новокузнецк, 1999. - 29 с., ил.

Рассмотрены технологии реализации алгоритмов методов и решения задач оптимизации в табличном процессоре Microsoft Excel 97. Приведены примеры для методов половинного деления, симплекс, градиентного и решение задач линейного и нелинейного программирования.

Практические задания ориентированы на усвоение навыков решения задач в среде Excel путем реализации алгоритмов методов оптимизации стандартными элементарными средствами и решения оптимизационных задач с применением инструмента “Поиск решения”.

Предназначены для студентов специальности “Металлургия черных металлов” (110100), специализации “Информационные технологии и предпринимательство в металлургии” (110107), “Матема­тическое обеспечение и применение ЭВМ в металлургии” (110104).

Рецензент – кафедра систем автоматизации (зав. каф. С.М. Кулаков)

Печатается по решению редакционно-издательского совета университета

1.Общие положения

В настоящее время одной из самых популярных и широко применяемых программ, работающих с электронными таблицами, является Microsoft Excel 97. Это объясняется удобством интерфейса пользователя и наличием многочисленных функций, позволяющих осуществлять реализацию различных по сложности и профессиональной ориентации задач [1]. Термин “электронная таблица” является общим термином. В электронных таблицах используются ссылки на данные, расположенные в столбцах и строках. В программе Excel традиционная электронная таблица называется рабочим листом. Однако можно создавать рабочие листы Excel, которые не имеют ничего общего с традиционными электронными таблицами. Рабочий лист в Excel может содержать игру, текст, графику и другие виды информации.

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

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

Другими средствами, которые предоставляет пользователю программа Excel, являются инструменты “Подбор параметра” (Coal Steek) и “Поиск решения” (Solver), позволяющие решать соответственно задачи одномерной и многомерной оптимизации. Инструмент “Поиск решения” использует численный алгоритм “встроенный оптимизатор”, позволяющий решать задачи безусловной и условной оптимизации с определенной точностью [2].

В пакете Excel имеется файл “solvsamp.xls”, где рассмотрены примеры практического применения данного инструмента. Эти примеры демонстрируют возможности и дают представления о том, в каких случаях стоит использовать данную программу.

В методическом плане инструмент “Поиск решения” оперирует со следующими категориями:

• целевые ячейки (Target cells), в которых содержатся значения критериев оптимизации;

• изменяемые ячейки (Change cells), значения переменных в которых изменяются программой до получения заданного решения;

• ячейки ограничения (Constrains), необходимые для наложения условий (положительности, целочисленности или нахождения в интервале) на переменные.

После проведения вычислений инструмент “Поиск решения” может создать три типа отчетов:

• результаты (Answers), в котором отражено начальное и конечное значения в целевой и изменяемых ячейках, а также данные об ограничениях;

• устойчивость (Sensitivity), где содержатся сведения о устойчивости решения к малым изменениям в формулах;

• пределы (Limits), в котором указаны верхний и нижний пределы для целевой функции и изменяемых ячеек, начальное и целевое значения.

Для создания отчета достаточно выбрать любой из них из списка “Тип отчета” (Reports) в диалоговом окне “Результаты поиска решения” (Solver Results).

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

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

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

Перечень сведений и знаний программы Excel, необходимых для решения задач оптимизации. При реализации алгоритмов одномерной и многомерной оптимизации как с помощью элементарных программных средств, так и с помощью “инструментариев”, требуется: наличие навыков работы с ячейками рабочих листов Excel; знание понятий “абсолютные” и “относительные” ссылки; умение работать со встроенными функциями; знание функций категорий “математичес­кие”, “статистические”, “логические”, “ссылки и массивы”; умение работать с диалоговыми окнами [1].

Построение алгоритма метода оптимизации. Реализация алгоритма с помощью набора “стандартных” средств программы Excel предполагает построение структуры логической схемы, приводящей к конечному оптимальному решению. Алгоритмы методов оптимизации, которые в соответствии с заданиями данных методических рекомендаций необходимо будет реализовывать, можно найти в литературе [3, 4]. Здесь мы приводим общую структуру, которая характерна для алгоритмов методов оптимизации. Эту структуру следует использовать при реализации конкретных алгоритмов.

Структура алгоритма должна включать следующие этапы.

1. Начальный этап.

Задание начального приближения X⁽⁰⁾, исходных параметров алгоритма ⁽⁰⁾, требуемой точности ; начальных значений счетчика количества итераций k = 0 и количества расчетов целевой функции N = 0; значение параметра верхней границы N^max, при достижении которой в случае “зацикливания” программа должна завершить свою работу.

2. Основной этап.

   1. Расчет новой координаты в соответствии с математической сущностью метода

X^(k+1) = X^(k) + [X^(k), f(X^(k)), P(f(X^(k)))],

где , P - операторы метода оптимизации.

2. Проверка условия нахождения оптимума и достижения верхних границ параметра N.

Если   , то перейти к этапу 3.

Если N  N^max, то перейти к этапу 3.

 – оценка текущей точности.

3. Выдача полученных значений переменных и параметров k, X^(k), f(X^(k)), .

4. Адаптация параметров алгоритма ^(k).

5. Наращивание номера итерации k = k + 1 и переход к этапу 2.

1. Завершение процесса нахождения оптимума. Выдача полученных результатов.

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

• группа ячеек с исходными данными, не изменяемыми в ходе работы метода (например, точность);

• строка, содержащая данные по “нулевой итерации”, т.е. исходные значения параметров, изменяемых в ходе процесса оптимизации (например, начальные границы интервала, начальный шаг и т.д.);

• строки, содержащие изменение параметров, указанных в строке “нулевой итерации” строки.

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