Решение задач оптимизации

Способы использования компьютера для решения задач оптимизации рассмотрим на примере.

Пусть имеется объект с двумя входными параметрами x1, x2 и выходным параметром y. Требуется определить оптимальные значения x1 и x2, которые обеспечивают минимум целевой функции y = f(x1, x2) и удовлетворяют ограничениям:

a1 <= x1<= b1, a2 <= x2<= b2, g(x1, x2) > 0.

Метод сканирования заключается в нахождении значений x1 из интервала [a1, b1] с шагом h1 и значений x2 из интервала [a2, b2] с шагом h2. Для всех значений x1 и x2, удовлетворяющих ограничениям g(x1, x2)>0, нужно вычислить значения целевой функции y = f(x1, x2). Те x1 и x2, для которых значение целевой функции минимально, являются решением задачи.

Алгоритм метода сканирования

Программа метода сканирования

1. Ввод a1, b1, h1, a2, b2, h2 и некоторого числа A. 2. Вычисление yopt = A, x1opt = a1, x2opt = a2. 3. x1 = a1. 4. x2 = a2. 5. Если g(x1, x2) > 0, то переход к 6, иначе – переход к 8. 6. Вычисление целевой функции y = f(x1, x2). 7. Если y<yopt, то yopt = y, x1opt = x1, x2opt = x2, иначе – переход к следующему пункту. 8. Вычисление x2 = x2 + h2. 9. Если x2 <= b2, то переход к 5, иначе – переход к 10. 10. Вычисление x1 = x1 + h1. 11. Если x1 <= b1, то переход к 4, иначе – переход к 12. 12. Вывод x1opt, x2opt и yopt.

SubCommandButton1_Click() A1 = Cells(1,1) : B1 = Cells(2,1) : H1 = Cells(3,1) A2 = Cells(1,2) : B1 = Cells(2,2) : H2 = Cells(3,2) A = Cells(4,1) Yopt = A : X1opt = A1 : X2opt = A2 For X1 = A1 To B1 Step H1 For X1 = A2 To B2 Step H2 If G(X1, X2) > 0 Then Y = F(X1, X2) If Y<Yopt Then Yopt = Y: X1opt = X1 : X2opt = X2 End If Cells(6,1) = X1opt : Cells(6,2) = X2opt : Cells(6,3) = Yopt End Sub

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

Функция пользователя для вычисления целевой функции	Функция пользователя для вычисления ограничения (если оно присутствует)
Function F(X1, X2) F = End Function	Function G(X1, X2) G = End Function

Метод случайного поиска рассмотрим на том же примере. Идея метода основана на многократном (N раз) вычислении целевой функции y для значений x1 и x2, выбранных из отрезков [a1, b1] и [a2, b2] случайным образом. Те значения x1 и x2, при которых целевая функция минимальна и удовлетворяются ограничения, являются решением задачи.

Для определения некоторого случайного числа x на отрезке [a, b] можно использовать встроенную функцию Rnd. Тогда x = (b – a)Rnd(1) + a.

Алгоритм метода случайного поиска

1. Ввод исходных данных: a1, b1, a2, b2, количества опытов N и числа A, заведомо большего, чем значение целевой функции.

2. Вычисление yopt = A, x1opt = a1, x2opt = a2.

3. i = 1.

4. Вычисление x1 = (b1 – a1) Rnd(1) + a1, x2 = (b2 – a2) Rnd(1) + a2.

5. Проверка ограничения: если g(x1, x2) <= 0 , то переход к пункту 8, иначе – переход к следующему пункту.

6. Вычисление целевой функции y = f(x1, x2).

7. Если y < yopt, то yopt = y, x1opt = x1, x2opt = x2, иначе – переход к следующему пункту.

8. i = i + 1.

9. Если i <= N, то переход к пункту 4, иначе – переход к пункту 10.

10. Вывод оптимальных значений x1opt, x2opt и минимального значения целевой функции yopt.

Решение задач оптимизации в приложении Excel. В приложении Excel имеется специальная команда, с помощью которой можно решать задачи оптимизации. Например, чтобы решить предыдущий пример, следует произвести следующие действия

– на рабочем листе, в ячейке, например, А1 записать значение левой границы для первого ограничения (число 3);

– в ячейке В1 записать значение левой границы для второго ограничения (число 0);

– в ячейке С1 записать целевую функцию:

=1,7 + 4,56 ∙ А1 – 3 ∙ В1 – 0,69 ∙ А1 ∙ В1 –0,44 ∙ В1^2

– выполнить Данные / Анализ / Поиск решения (если данной команды нет, то её нужно добавить, для чего выполнить Файл / Надстройки, в появившемся окне выбрать Поиск решения и нажать кнопку Перейти.)

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

Решение задачи можно посмотреть и проанализировать на отдельном листе.

Решение задач оптимизации в приложении Mathcad. В приложении Mathcad имеются встроенные функции, с помощью которых можно решать задачи оптимизации. Рассмотрим пример.

Пусть требуется определить оптимальные значения x1 и x2, которые обеспечивали бы максимум целевой функции

y = 1,7 + 4,56x1 – 3x2 – 0,69x1x2 – 0,44x2²

и удовлетворяли ограничениям:

3 <= x1<= 4, 0,1 <= x2 <= 0,9.

В рабочей области приложения Mathcad требуется записать:

f(x1, x2):= 1.7 + 4.56∙x1 – 3∙x2 – 0.69∙x1∙x2 – 0.44∙x2²

x1:= 3 x2:=0.1

Given

4 ≥ x1 ≥ 3

0.9 ≥ x2 ≥ 0.1

R:= maximize(f, x1, x2)

R =

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

Назад