Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Применение Microsoft Excel для решения задач оптимизации

Покупка
Артикул: 792750.01.99
Доступ онлайн
500 ₽
В корзину
Представлены четыре раздела учебного курса «Методы оптимизации». В каждом разделе изложены необходимые теоретические сведения, рассмотрены реализации алгоритмов численных методов оптимизации на примерах, приведены способы решения или проверки решений в программе Microsoft Excel. Предназначено для студентов, обучающихся по направлениям подготовки 09.03.02 «Информационные системы и технологии», 10.03.01 «Информационная безопасность», 10.05.05 «Безопасность информационных технологий в правоохранительной сфере». Подготовлено на кафедре информатики и прикладной математики.
Шайдуллина, Н. К. Применение Microsoft Excel для решения задач оптимизации : учебное пособие / Н. К. Шайдуллина. - Казань : КНИТУ, 2019. - 92 с. - ISBN 978-5-7882-2738-2. - Текст : электронный. - URL: https://znanium.com/catalog/product/1904865 (дата обращения: 28.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
 

Министерство науки и высшего образования Российской Федерации 

Федеральное государственное бюджетное 

образовательное учреждение высшего образования 

«Казанский национальный исследовательский 

технологический университет» 

 
 
 
 
 
 

Н. К. Шайдуллина 

 
 
ПРИМЕНЕНИЕ MICROSOFT EXCEL  

ДЛЯ РЕШЕНИЯ ЗАДАЧ  

ОПТИМИЗАЦИИ 

 

Учебное пособие 

 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

Казань 

Издательство КНИТУ 

2019 

УДК 519.85:004.67(075) 
ББК 22.18:32.97я7

Ш00

 

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

Казанского национального исследовательского технологического университета 

 

Рецензенты: 

д-р. физ.-мат. наук, проф. М. Р. Тимербаев  
канд. физ.-мат. наук, доц. Р. Ф. Марданов 

 
 

 
 

 

 
 
 

 
Ш00 

Шайдуллина Н. К. 
Применение Microsoft Excel для решения задач оптимизации : учеб-
ное пособие / Н. К. Шайдуллина; Минобрнауки России, Казан. нац. 
исслед. технол. ун-т. – Казань : Изд-во КНИТУ, 2019. – 92 с. 
 
ISBN 978-5-7882-2738-2
 
Представлены четыре раздела учебного курса «Методы оптимизации». 

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

Предназначено для студентов, обучающихся по направлениям подго-

товки 09.03.02 «Информационные системы и технологии», 10.03.01 «Инфор-
мационная безопасность», 10.05.05 «Безопасность информационных техноло-
гий в правоохранительной сфере». 

Подготовлено на кафедре информатики и прикладной математики. 
 

 
ISBN 978-5-7882-2738-2
© Шайдуллина Н. К., 2019
© Казанский национальный исследовательский 

технологический университет, 2019

УДК 519.85:004.67(075) 
ББК 22.18:32.97я7

1 .  П Р Я М Ы Е  М Е Т О Д Ы  П О И С К А  Б Е З У С Л О В Н О Г О  

Э К С Т Р Е М У М А  

1 . 1 .  О с н о в н ы е  о п р е д е л е н и я  

Оптимизация – процесс нахождения оптимального варианта из 

возможных. 

Постановка задачи оптимизации: 
Пусть заданы X – некоторое подмножество R! и функция 

f(x), x ∈ X. Требуется найти такой вектор x∗ ∈ X, которому соответ-
ствует минимальное значение функции на этом множестве: 

f(x∗) = min

#∈% f(x). 

Функция f(x) называется целевой, множество X – множеством 

допустимых решений. 

Решением задачи оптимизации является пара (x∗, f(x∗)). 
Задача поиска максимума сводится к задаче поиска минимума: 

max f(x) = −min (−f(x)). 

Задачей поиска экстремума функции называется задача поиска 

минимума и максимума функции. 

Классификация методов оптимизации: 
– однокритериальные и многокритериальные – по числу целевых 
функций ; 

– одномерные и многомерные – по размерности вектора x; 
– условные и безусловные – по наличию ограничений на область 

X; 

– линейные и нелинейные – по видам целевой функции и ограничений; 

– 
прямые – нулевого порядка, градиентные – первого и второго 

порядков – по порядку старшей производной, используемой в методе. 

Точка x∗ ∈ X называется точкой глобального минимума, если 

в этой точке функция достигает своего наименьшего значения на X:  

f(x∗) ≤ f(x), ∀x ∈ X. 

Точка x∗ ∈ X называется точкой локального минимума, если  

∃ε > 0, f(x∗) ≤ f(x), ∀ x ∈ X: ‖x − x∗‖ < ε. 

Здесь ‖x‖ = :x&' + x'' + ⋯ + x!' – норма вектора х. 
На риc. 1.1 изображен график функции f(x) = x( + 5x) − 10x. 
 

 

 

Рис. 1.1 

 

По графику видно, что у функции две точки локального минимума – 
min1 и min2, причем min1 является точкой глобального минимума, 
одна точка локального максимума – max, точек глобального 
максимума нет. 

Отрезок, на котором существует один локальный экстремум, 

называется начальным интервалом неопределенности. 

У функции, изображенной на рис. 1.1, можно выбрать начальные 
интервалы неопределенности так: 

для min1 – [–4; –3], max – [–2; 0], min2 – [0; 1]. 

Локализовать экстремум функции – значит, найти начальный 

интервал неопределенности. 

 
Пример 1 
Сформулировать задачу математически и найти экстремум 

функции с помощью надстройки Microsoft Excel Поиск решения. Имеется 
множество прямоугольных треугольников, у которых сумма одного 
катета и гипотенузы равна 1. Найти среди них треугольник 
с наибольшей площадью. 

Решение 
Найдем максимум полученной площади с помощью надстройки 

Microsoft Excel Поиск решения. 

-40

-20

0

20

40

60

-5
-4
-3
-2
-1
0
1
2

min

min

max

Откроем программу Microsoft Excel. В ячейках A1,B1 и C1 запишем 
нули (это первоначальные значения сторон треугольника). 
В ячейку D1 введем формулу площади =A1*B1/2. В ячейку A3 введем 
формулу =A1+C1. В ячейку B3 введем число 1. В ячейку A4 введем 
формулу =A1^2+B1^2. В ячейку B4 введем формулу =C1^2. 

На рис. 1.2 показано, как выглядит документ Microsoft Excel на 

этом этапе решения. 

 

 

 

Рис. 1.2 

 

Откроем вкладку Данные. В разделе Анализ найдем процедуру 

Поиск решения. Если такой процедуры нет, то на вкладке Файл выбираем 
команду Параметры, в меню Надстройки выделяем Пакет анализа 
и нажимаем кнопку Перейти (рис. 1.3). 

 

 

 

Рис. 1.3 

В открывшемся окне Надстройки выбираем Поиск решения и 

нажимаем кнопку ОК (рис. 1.4). 

 

 

 

Рис. 1.4 

 

Итак, выделяем ячейку D1, в которой записана целевая функция 

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

В графе Изменяя ячейки переменных нужно указать адреса ячеек, 
в которых лежат начальные значения сторон треугольника: 
$A$1:$C$1. Записать ограничения в окно В соответствии с ограничениями 
нужно с помощью кнопки Добавить (рис. 1.5). 

 

 

 

Рис. 1.5 

 

Активизируем опцию Сделать переменные без ограничений 

неотрицательными, выбираем метод решения: Поиск решения нелинейных 
задач методом ОПГ, нажимаем кнопку Найти решение 
(рис. 1.6). 

 

 

 

Рис. 1.6 

 

Выбираем опцию Сохранить найденное решение и нажимаем 

ОК. На рис. 1.7 показано, как выглядит документ Microsoft Excel на 
этом этапе решения. 

 

 

 

Рис. 1.7 

Ответ: 
1) ячейка A1 – значение переменной a = 0,333327 = 1/3. 
2) ячейка B1 – значение переменной b = 0,577361 = √3/3. 
3) ячейка C1 – значение переменной c = 0,666673 = 2/3. 
4) ячейка D1 – максимальное значение переменной  

S = 0,096225 = √3/18. 

 

Пример 2. Локализовать минимум функции y = x' + 10 sinx 

с помощью Microsoft Excel. 

Решение 
Построим график функции. Для этого выполним табулирование 

функции на отрезке [–5; 5] с шагом 0,2. 

В ячейке A1 запишем число -5, в ячейке A2 - число -4,8. Выделим 
ячейки А1 и А2 вместе и протянем вниз до ячейки A51, в которой 
появится число 5. Тем самым мы задали диапазон значений аргумента. 
В ячейке В1 запишем функцию, в которой вместо аргумента укажем 
ссылку на ячейку А1: =A1^2+10*SIN(A1). 

В ячейке В1 получим значение 34,58924. Тиражируем ячейку В1 

до В51. Тем самым мы получили ряд значений нашей функции на отрезке [–
5; 5] с шагом 0,2. 

Выделим диапазон ячеек B1:В51 и на вкладке Вставка в разделе 

Диаграммы выберем График. Построенный график представлен на 
рис. 1.8. 

 

 

 

Рис. 1.8 

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

 

 

 

Рис. 1.9 

 

В графе Диапазон подписей осей укажем =Лист1!$A$1:$A$51 

(проще всего выделить мышкой диапазон А1:А51). Нажмем кнопку 
ОК, получим график, изображенный на рис. 1.10. 

 

 

 

Рис. 1.10 

 

Ответ: по графику видно, два минимума функции локализованы 

на интервалах [–2; –0,8] и [3,4; 4,6], максимум – на интервале [1,6; 
2,2]. 

Простейшей математической моделью оптимизации является 

минимизация функции одной переменной f(x) на промежутке [a; b]. 
При рассмотрении этой модели ограничимся классом унимодальных 
на промежутке функций. 

Функция f(x) называется унимодальной на промежутке [a; b], 

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

Это единственное минимальное значение может достигаться 

только в одной точке промежутка, внутренней или граничной, или на 
некоторой части промежутка [a; b]. Примеры графиков унимодальных 
на промежутке [a; b] функций приведены на рис. 1.11. 

 

 

 

Рис. 1.11 

 

Из определения унимодальной на отрезке [a; b] функции следуют ее 
свойства: 

1. Унимодальная на отрезке [a; b] функция является унимодальной 

на любой меньшей части этого отрезка [c; d]⊂[a; b]. 

2. Пусть f(x) унимодальная на отрезке [a; b] функция, x∗ – ее точка 

минимума и a ≤ x& ≤ x' ≤ b. Тогда: 

если f(x&) ≤ f(x'), то x∗ ∈ [a; x']; 
если f(x&) > f(x'), то x∗ ∈ [x&; b]. 

Прежде чем применять методы оптимизации, необходимо лока-

лизовать экстремум функции, т. е. найти отрезок [a; b], на котором 
функция унимодальна. Это можно сделать графически или с помощью 
табулирования целевой функции. 

Доступ онлайн
500 ₽
В корзину