Лабораторная работа №3. Задачи дискретной и непрерывной оптимизации#

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

Ниже приведены варианты заданий для подгрупп. Каждая подгруппа выбирает конкретный вариант и договаривается с другими подгруппами, чтобы не было пересечений между подгруппами.

Вариант 1 - Задача о рюкзаке#

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

Задача - рассмотреть и проанализировать различные подходы к решению задачи о рюкзаке, являющейся задачей дискретной оптимизации.

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

В отчёте также отразить особенности, достоинства и недостатки каждого из указанных подходов к решению задачи и сравнить их вычислительную эффективность.

Вариант 2 - Оптимизация трёхступенчатого клина#

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

Задача - решить задачу непрерывной оптимизации с ограничениями.

Трёхступенчатый клин обтекается сверхзвуковым потоком воздуха.

  1. Графически построить зависимость коэффициента восстановления полного давления \(\sigma_\Sigma\) от углов ступеней клина \(\beta_1\) и \(\beta_2\), построить её графически. Угол \(\beta_3\) фиксирован. В каждой точке зависимости система скачков должна существовать (не должно быть отошедших скачков).

  2. Определить углы \(\beta_1^*\) и \(\beta_2^*\), соответствующие максимальному значению коэффициента восстановления полного давления, то есть

(5)#\[ \{\beta_1^*, \beta_2^*\} = \underset{0 < \beta_1, \beta_2 < 2\pi}{\mathrm{arg\ max}}{\sigma_\Sigma(\beta_1, \beta_2)} \]

Исходные данные: известна скорость набегающего потока \(\mathrm{M}_1 = 3\) и угол 3-й ступени клина \(\beta_3 = 33^\circ\). Показатель адиабаты воздуха \(k = 1.4\).

Ниже приведены расчётные формулы.

(6)#\[ \tan{\Delta\beta_i} = \cfrac {\sin^2{\nu_i} - \cfrac{1}{\mathrm{M}_i^2}} {\cfrac{k+1}{2} - \left( \sin^2{\nu_i} - \cfrac{1}{\mathrm{M}_i^2} \right)} \cot{\nu_i}; \]
(7)#\[ \Delta\beta_i = \beta_i - \beta_{i-1}; \]
(8)#\[ \lambda_{i+1} = \lambda_i \cdot \cfrac{\cos{\nu_i}}{\cos{(\nu_i - \Delta\beta_i)}}; \]
(9)#\[\begin{split} \begin{split} \sigma_i &= \cfrac{p_{0, i+1}}{p_{0, i}} = \\ &= \cfrac {\left( \cfrac{k+1}{2} \right)^{\cfrac{k+1}{k-1}}} { \left( \cfrac{1}{\mathrm{M}_i^2 \sin^2{\nu_i}} + \cfrac{k-1}{2} \right)^{\cfrac{k}{k-1}} \left( k \mathrm{M}_i^2 \sin^2{\nu_i} - \cfrac{k-1}{2} \right)^{\cfrac{1}{k-1}} }; \end{split} \end{split}\]
(10)#\[ \sigma_\Sigma = \prod_{i=1}^3{\sigma_i}. \]

Вспомогательные формулы:

(11)#\[ \mathrm{M}(\lambda) = \lambda \cdot \sqrt{ \cfrac{\cfrac{2}{k+1}}{1 - \cfrac{k-1}{k+1} \lambda^2} }; \]
\[ \lambda(\mathrm{M}) = \mathrm{M} \cdot \sqrt{ \cfrac{\cfrac{k+1}{2}}{1 + \cfrac{k-1}{2} \mathrm{M}^2} }; \]

На рисунках ниже представлены расчётная схема и условие отрыва скачка уплотнения (СУ) от обтекаемого тела (зависимость угла СУ от угла поворота потока).

_images/clin-scheme.png

Fig. 1 Расчётная схема#

_images/avulsion.png

Fig. 2 Условие отрыва скачка уплотнения#

Important

На Условие отрыва скачка уплотнения \(\beta_i \equiv \Delta\beta_i\) и \(\nu_i\) - угол СУ.

Алгоритм расчёта следующий:

  1. Из уравнения (6) при известном согласно (7) угле \(\Delta\beta_1\) и по исходному \(\mathrm{M}_1\) численно ищется значение угла СУ \(\nu_1\) на первой ступени клина.

  2. По формуле (9) рассчитывается \(\sigma_1\) для первого СУ.

  3. Скорость потока за текущим СУ рассчитывается по формулам (8) и (11).

  4. Алгоритм начинается заново для следующей ступени с учётом (7).

В итоге по формуле (10) рассчитывается коэффициент восстановления полного давления \(\sigma_\Sigma\).

Для решения задачи оптимизации (5) необходимо выбрать метод, например, из модуля optimize библиотеки научных расчётов SciPy.

Вариант 3 - Безопасное размещение склада боеприпасов#

Цель - рассмотреть возможные подходы к решению поставленной задачи поисковой непрерывной оптимизации.

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

Имеется \(n\) городов, заданных координатами на плоскости. Военным необходимо разместить большой (а потому опасный) склад боеприпасов в районе этих городов для надёжной защиты государства.

Требуется:

  1. Сформулировать понятие “место безопасного размещения” склада боеприпасов.

  2. Придумать или выбрать алгоритмом решения задачи.

  3. Определить координаты места безопасного размещения склада боеприпасов для всех заданных количеств городов \(n_i \in N = \{25, 50, 100, 250, 500\}\).

  4. Визуализировать полученные результаты.

Города генерировать случайным образом с помощью равномерного распределения. При этом необходимо обеспечить возможность воспроизведения расчёта настройкой параметра seed у используемого генератора случайных чисел.

Размер пространства принять 100 на 100 км.

Important

Никаких других - «дополнительных», «удобных», «авторских» - условий в задаче не требуется.

Вариант 4 - Условная и безусловная оптимизация#

Цель - закрепить навыки численной оптимизации математических функций одного, двух и многих переменных.

Задача - рассмотреть и проанализировать способы (методы) оптимизации математических функций одного, двух и многих переменных.

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

  1. Функцию Бута:

(12)#\[ f(x, y) = (x + 2 y - 7)^2 + (2 x + y - 5)^2. \]

Область определения аргументов: \(-10 \le x, y \le 10\). Показать, что \(f(1, 3) = 0\) есть минимум.

  1. Функцию Розенброка от трёх параметров:

\[ f(x_1, x_2, x_3) = \sum\limits_{i=1}^{2}{ \left[ 100 \left( x_{i+1} - x_i^2 \right)^2 + (x_i - 1)^2 \right] }. \]

Область определения аргументов: \(-\infty \le x_1, x_2, x_3 \le \infty\). Показать, что \(f(1,1,1) = 0\) есть минимум.

  1. Функцию Экли:

(13)#\[ f(x, y) = -20 \exp{\left[ -0.2 \sqrt{\cfrac{x^2 + y^2}{2}} \right]} - \exp{\left[ \cfrac{\cos(2 \pi x) + \cos(2 \pi y)}{2} \right]} + e + 20. \]

Область определения аргументов: \(-5 \le x, y \le 5\). Показать, что \(f(0, 0) = 0\) есть минимум.

  1. Ограниченную функцию Мишры-Бёрда:

(14)#\[ f(x, y) = \sin{(y)} \exp{\left[ (1 - \cos{x})^2 \right]} + \cos{(x)} \exp{\left[ (1 - \sin{y})^2 \right]} + (x - y)^2 \]

при ограничении

\[ (x + 5)^2 + (y + 5)^2 < 25. \]

Область определения аргументов: \(-10 \le x \le 0\) и \(-6.5 \le y \le 0\). Показать, что \(f(-3.1302468, -1.5821422) = -106.7645367\) есть минимум.

Постройте графики функций (12), (13) и (14).