Реферат: Решение уравнений средствами Excel

2.1.Циклические ссылки

2.2.Подбор параметра

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

/>2.1.Циклические ссылки

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

Рассмотримзадачу нахождения корня уравнения методом Ньютона с использованием циклическихссылок. Возьмем для примера квадратное уравнение: х2 — 5х + 6=0, графическое представлениекоторого приведено на рис. 8. Найти корень этого (и любого другого) уравненияможно, используя всего одну ячейку Excel.

Длявключения режима циклических вычислений в менюСервис/Параметры/вкладка Вычисления включаем флажок Итерации, при необходимости изменяемчисло повторений цикла в поле Предельноечисло итераций и точность вычислений в поле Относительная погрешность (по умолчаниюих значения равны 100 и 0,0001 соответственно). Кроме этих установок выбираемвариант ведения вычислений: автоматическиили вручную. При автоматическом вычислении Excel выдаетсразу конечный результат, при вычислениях, производимых вручную, можно наблюдать результат каждойитерации.

/>

Рис. 8. График функции

Выберемпроизвольную ячейку, присвоим ей новое имя, скажем, Х, и введем в нее рекуррентную формулу, задающую вычисленияпо методу Ньютона:

/>,

где F и F1задают соответственно выражения для вычисления значений функции и еепроизводной. Для нашего квадратного уравнения после ввода формулы в ячейкепоявится значение 2,соответствующее одному из корней уравнения (рис. 8). В нашем случае начальноеприближение не задавалось, итерационный вычислительный процесс начинался созначения, по умолчанию хранимого в ячейке Хи равного нулю. А как получить второй корень? Обычно это можно сделатьизменением начального приближения. Решать проблему задания начальных установокв каждом случае можно по-разному. Мы продемонстрируем один прием, основанный наиспользовании функции ЕСЛИ. С целью повышения наглядности вычислений ячейкамбыли присвоены содержательные имена (рис. 9).

В ячейку Хнач (В4) заносим начальное приближение — 5.

·          В ячейку Хтекущ (С4) записываем формулу: =ЕСЛИ(Хтекущ=0; Хнач;Хтекущ-(Хтекущ^2-5*Хтекущ+6)/(2*Хтекущ-5)).

·          В ячейку D4помещаем формулу, задающую вычисление значения функции в точке Хтекущ, что позволит следить за процессомрешения.

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

·          Чтобы сменитьначальное приближение, недостаточно изменить содержимое ячейки Хнач и запустить процесс вычислений. Вэтом случае вычисления будут продолжены, начиная с последнего вычисленного

/>

Рис. 9. Определение начальных установок

значения. Чтобы обнулить значение,хранящееся в ячейке Хтекущ,нужно заново записать туда формулу. Для этого достаточно для редактированиявыбрать ячейку, содержащую формулу, дважды щелкнув мышью на ней (при этомсодержимое ячейки отобразится в строке формул). Щелчок по кнопке (нажатиеклавиши) Enter запуститвычисления с новым начальным приближением.

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

Возьмемв качестве примера все то же квадратное уравнение х2-5х+6=0. Для нахождения корней уравнениявыполним следующие действия:

В ячейку С3 (рис. 10) введем формулудля вычисления значения функции, стоящей в уравнении слева от знака равенства.В качестве аргумента используем ссылку на ячейку С2, т.е. =С2^2-5*C2+6.

/>

Рис. 10. Окно диалога Подбор параметра

·          В окне диалога Подбор параметра (рис. 10) в поле Установить в ячейке введем ссылку наячейку с формулой, в поле Значение — ожидаемый результат, в поле Изменяя значенияячейки — ссылку на ячейку, в которой будет храниться значениеподбираемого параметра (содержимое этой ячейки не может быть формулой).

·          После нажатия накнопку Ok Excel выведет окнодиалога Результат подбора параметра.Если подобранное значение необходимо сохранить, то нажмите на Оk, и результат будет сохранен в ячейке,заданной ранее в поле Изменяя значенияячейки. Для восстановления значения, которое было в ячейке С2 доиспользования команды Подбор параметра,нажмите кнопку Отмена.

Приподборе параметра Excel использует итерационный (циклический) процесс.Количество итераций и точность устанавливаются в меню Сервис/Параметры/вкладка Вычисления. ЕслиExcel выполняет сложную задачу подбора параметра, можно нажать кнопку Пауза в окне диалога Результат подбора параметра и прерватьвычисление, а затем нажать кнопку Шаг,чтобы выполнить очередную итерацию и просмотреть результат. При решении задачив пошаговом режиме появляется кнопка Продолжить — для возврата в обычный режим подбора параметра.

Вернемсяк примеру. Опять возникает вопрос: как получить второй корень? Как и впредыдущем случае необходимо задать начальное приближение. Это можно сделатьследующим образом (рис. 11, а):

/>

а

/>

б

Рис. 11. Поиск второго корня

·          В ячейку Х (С2) вводим начальное приближение.

·          В ячейку Хi (С3) вводим формулу длявычисления очередного приближения к корню, т.е. =X-(X^2-5*X+6)/(2*X-5).

·          В ячейку С4 поместимформулу, задающую вычисление значения функции, стоящей в левой части исходногоуравнения, в точке Хi.

·          После этоговыбираем команду Подбор параметра,где в качестве изменяемой ячейки принимаем ячейку С2. Результат вычисленийизображен на рис. 11, б (в ячейке С2 — конечное значение, а в ячейке С3 — предыдущее).

Однаковсе это можно сделать и несколько проще. Для того чтобы найти второй корень,достаточно в качестве начального приближения (рис. 10) в ячейку C2 поместитьконстанту 5 и после этогозапустить процесс Подбор параметра.

/>2.3.Поиск решения

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

Задачи,которые можно решать с помощью Поискарешения, в общей постановке формулируются так:

Найти:х1, х2, …, хnтакие, что: F(х1, х2,…, хn) > {Max; Min; = Value} при ограничениях: G(х1, х2, …, хn)> { Value;  Value; = Value}

Искомыепеременные — ячейки рабочего листа Excel — называются регулируемыми ячейками.Целевая функция F(х1, х2,…, хn), называемая иногда просто целью, должназадаваться в виде формулы в ячейке рабочего листа. Эта формула может содержать функции,определенные пользователем, и должна зависеть (ссылаться) от регулируемыхячеек. В момент постановки задачи определяется, что делать с целевой функцией.Возможен выбор одного из вариантов:

·          найти максимумцелевой функции F(х1, х2,…, хn);

·          найти минимумцелевой функции F(х1, х2,…, хn);

·          добиться того,чтобы целевая функция F(х1, х2,…, хn) имела фиксированное значение: F(х1, х2, …, хn) =a.

ФункцииG(х1, х2, …, хn)называются ограничениями. Их можно задать как в виде равенств, так и неравенств.На регулируемые ячейки можно наложить дополнительные ограничения:неотрицательности и/или целочисленности, тогда искомое решение ищется в областиположительных и/или целых чисел.

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

Вышедля нахождения корней квадратного уравнения был применен метод Ньютона (п. 1.4)с использованием циклических ссылок (п. 2.1) и средство Подбор параметра (п. 2.2). Рассмотрим,как воспользоваться Поиском решенияна примере того же квадратного уравнения.

/>

Рис. 12. Окно диалога Поиск решения

Послеоткрытия диалога Поиск решения(рис. 12) необходимо выполнить следующие действия:

1.        в поле Установить целевую ячейку ввести адресячейки, содержащей формулу для вычисления значений оптимизируемой функции, внашем примере целевая ячейка — это С4, а формула в ней имеет вид: =C3^2 — 5*C3 + 6;

2.        для максимизациизначения целевой ячейки, установить переключатель максимальному значению в положение , дляминимизации используется переключатель минимальномузначению, в нашем случае устанавливаем переключатель в положениезначению и вводим значение ;

3.        в поле Изменяя ячейки ввести адреса изменяемыхячеек, т.е. аргументов целевой функции (С3), разделяя их знаком ";"(или щелкая мышью при нажатой клавише Сtrlна соответствующих ячейках), для автоматического поиска всех влияющих нарешение ячеек используется кнопка Предположить;

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

5.        для запускапроцесса поиска решения нажать кнопку Выполнить.

/>

Рис. 13. Результаты поиска

Длясохранения полученного решения необходимо использовать переключатель Сохранить найденное решение в открывшемсяокне диалога Результаты поиска решения.После чего рабочий лист примет вид, представленный на рис. 13. Полученноерешение зависит от выбора начального приближения, которое задается в ячейке С4(аргумент функции). Если в качестве начального приближения в ячейку С4 ввестизначение, равное 1,0, то спомощью Поиска решения найдемвторой корень, равный 2,0.

Опции,управляющие работой Поиска решения,задаваемые в окне Параметры(окно появляется, если нажать на кнопку Параметрыокна Поиск решения), следующие(рис. 14):

/>

Рис. 14. Настройка параметров Решателя

·          Максимальное время — ограничивает время, отведенное на процесс поиска решения (по умолчаниюзадано 100 секунд, что достаточно для задач, имеющих около 10 ограничений, еслизадача большой размерности, то время необходимо увеличить).

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

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

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

·          Сходимость — когда относительное изменение значения в целевой ячейке за последние пятьитераций становится меньше числа (дробь из интервала от 0 до 1), указанного вданном параметре, поиск прекращается.

·          Линейная модель — этот флажок следует включать, когда целевая функция и ограничения — линейные функции. Это ускоряет процесс поиска решения.

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

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

·          Показывать результаты итераций — этот флажок позволяет включить пошаговый процесс поиска,показывая на экране результаты каждой итерации.

·          Оценки — эта группа служит для указания метода экстраполяции — линейная иликвадратичная, — используемого для получения исходных оценок значений переменныхв каждом одномерном поиске. Линейнаяслужит для использования линейной экстраполяции вдоль касательного вектора. Квадратичная служит для использованияквадратичной экстраполяции, которая дает лучшие результаты при решениинелинейных задач.

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

·          Метод поиска — служит для выбора алгоритма оптимизации. МетодНьютона был рассмотрен ранее. В Методесопряженных градиентов запрашивается меньше памяти, но выполняетсябольше итераций, чем в методе Ньютона. Данный метод следует использовать, еслизадача достаточно велика и необходимо экономить память, а также, если итерациидают слишком малое отличие в последовательных приближениях.

Сохранитьмодель поиска решения можно следующими способами:

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

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

3.        еще один способсохранения параметров поиска — сохранение их в виде именованных сценариев. Дляэтого необходимо нажать на кнопку Сохранитьсценарий диалогового окна Результатыпоиска решений.

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

/>

Рис. 15. Отчет по устойчивости

Отчетпо устойчивости (рис.15) содержит информацию о том, насколько целевая ячейкачувствительна к изменениям ограничений и переменных. Этот отчет имеет двараздела: один для изменяемых ячеек, а второй для ограничений. Правый столбец вкаждом разделе содержит информацию о чувствительности. Каждая изменяемая ячейкаи ограничения приводятся в отдельной строке. Раздел для изменяемых ячеексодержит значение нормированного градиента, которое показывает, как целаяячейка реагирует на увеличение значения в соответствующей изменяемой ячейке наодну единицу. Подобным образом, множитель Лагранжа в разделе для ограниченийпоказывает, как целевая ячейка реагирует на увеличение соответствующегозначения ограничения на одну единицу. При использовании целочисленныхограничений Excel выводит сообщение Отчетыустойчивость и Пределы не применимы для задач с целочисленными ограничениями.Если в окне диалога Параметры поискарешения установлен флажок Линейнаямодель, то отчет по устойчивости содержит несколько дополнительныхстолбцов информации.

/>

Рис. 16. Отчет по результатам

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

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