Файл: Лекции_по_дисциплине.pdf

Тарова Инна Николаевна

7.3. РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ В EXCEL

7.3.1. Задачи оптимизации

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

решение уравнений с одним неизвестным,

задачи линейного программирования;

аппроксимация функций.

Постановка задачи оптимизации

Взадачах оптимизации требуется найти значения параметров или функций, реализующих максимум или минимум некоторой завися-

щей от них величины, например: Z=f(x1, x2,…, xn) (7.4) часто при дополнительных условиях-неравенствах:

φ(x1, x2,…, xn) <=0 (i=1,2,…,n) (7.5)

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

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

Впростейшем случае одной независимой переменной х локальные максимум и минимум функции определяются следующим образом. Действительная функция f(x), определенная при х=а, имеет в точке а (локальный) минимум или (локальный) максимум f(a), если сущест-

вует такое положительное число δ, что при всех x = х - а, для кото-

f f (a x) f ( f ) 0

Максимум и минимум функции объединяются общим названием

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

116

Компьютерное моделирование

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

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

7.3.2. Решение уравнений с одним неизвестным

Одним из приложений задач оптимизации является численное решение систем уравнений с одним или несколькими неизвестными

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

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

Процесс решения с помощью процедуры Подбор параметра распадается на два этапа:

117

Тарова Инна Николаевна

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

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

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

7.3.3 Линейное программирование

В случае, когда оптимизируемая целевая функция (7.4) и ограничения (7.5) линейны, задача оптимизации решается методами линейного программирования и обычно называется задачей линейного программирования. Задача линейного программирования заключается в нахождении n переменных x1, х2,..., хn, минимизирующих данную линейную функцию (целевую функцию):

Z=f(x1, x2,…, xn)=c1x1+c2x2+…+cnxn (7.7)

(или максимизирующую — Z) при линейных ограничениях-

Часто задачу линейного программирования (7.7.-7.9) сводят путем введения в случае необходимости вспомогательных переменных к стандартной форме (основной задаче линейного программирования). При этом требуется минимизировать целевую функцию:

Z=f(x1, x2,…, xn)≡c1x1+c2x2+…+cnxn (7.10)

118

Компьютерное моделирование

Допустимым решением (планом) задачи линейного программирования является упорядоченное множество чисел (x1, x2,…, xn), удовлетворяющих ограничениям (7.11) и (7.12). Это точка в n-мерном пространстве. Допустимое решение, минимизирующее целевую функцию (7.10), называется оптимальным решением (оптимальным планом).

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

1-й этап: осмысление задачи, выделение наиболее важных качеств, свойств, величин, параметров. Это можно делать, составляя схемы, таблицы, графики и т. п.;

2-й этап: введение обозначений (неизвестных). Желательно ограничиваться как можно меньшим количеством неизвестных, выражая по возможности одни величины через другие;

3-й этап: создание целевой функции. Обычно в качестве цели могут выступать максимальная стоимость всего объема продукции, максимальная прибыль, минимальные затраты и т. п. Целевая функция записывается в виде (7.7) или (7.10).

4-й этап: составление системы ограничений, которым должны удовлетворять введенные величины (7.8), (7.9) или (7.11), (7.12).

5-й этап: решение задачи на компьютере.

Инструментом для поиска решений задач оптимизации в Excel служит процедура Поиск решения (Сервис > Поиск решения). При этом открывается диалоговое окно Поиск решения. Оно содержит следующие рабочие поля:

Установить целевую ячейку — служит для указания целевой ячейки, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. Эта ячейка должна содержать формулу;

Равной — служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или подбор задан-

119

Тарова Инна Николаевна

ного числа). Чтобы установить число, необходимо ввести его в поле;

Изменяя ячейки — служит для указания ячеек, значения которых изменяются в процессе поиска решения до тех пор, пока не будут выполнены наложенные ограничения и условие оптимизации значения ячейки, указанной в поле Установить целевую ячейку;

Предположить — используется для автоматического поиска ячеек, влияющих на формулу, ссылка на которую дана в поле Установить целевую ячейку. Результат поиска отображается в поле

Изменяя ячейки;

Ограничения — служит для отображения списка граничных условий поставленной задачи;

Добавить — используется для отображения диалогового окна До-

бавить ограничение;

Изменить — применяется для отображения диалогового окна Из-

менить ограничение;

Удалить — служит для снятия указанного ограничения;

Выполнить — используется для запуска поиска решения поставленной задачи;

Закрыть — служит для выхода из окна диалога без запуска поиска решения поставленной задачи. При этом сохраняются установки, сделанные в окнах диалога, появлявшихся после нажатий на кнопки Параметры, Добавить, Изменить или Удалить;

Параметры — применяется для отображения диалогового окна Параметры поиска решения, в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения;

Восстановить — служит для очистки полей окна диалога и восстановления значений параметров поиска решения, используе-

мых по умолчанию.

Другими типовыми примерами задач линейного программирования являются задачи:

О рационе питания.

Об оптимальных перевозках.

120

Компьютерное моделирование

Об оптимальном плане пошивочной мастерской.

О рациональном использовании сырья.

7.3.4. Аппроксимация экспериментальных данных Одна независимая переменная

На практике часто приходится сталкиваться с задачей о сглаживании экспериментальных зависимостей или задачей аппроксимации. Аппроксимацией называется процесс подбора эмпирической формулы φ(x) для установленной из опыта функциональной зависимости y=f(x). Эмпирические формулы служат для аналитического представления опытных данных.

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

После выбора вида формулы определяют ее параметры. Для наилучшего выбора параметров задают меру близости аппроксимации экспериментальных данных. Во многих случаях, в особенности, если функция f(x) задана графиком или таблицей (на дискретном множестве точек), для оценки степени приближения рассматривают разности f(xi) - φ(xi) для точек x0, x1,..., xn. Существуют различные меры близости и, соответственно, способы решения этой задачи. Некоторые из них очень просты, быстро приводят к результату, но результат этот является сильно приближенным. Другие более точные, но и более сложные. Обычно определение параметров при известном виде зависимости осуществляют по методу наименьших квадратов. При этом функция φ(x) считается наилучшим приближением к f(x), если для нее сумма квадратов невязок δi или отклонений «теоретических»

121