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

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

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

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

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

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

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

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

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

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

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

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

  1. Графически построить зависимость коэффициента восстановления полного давления σΣ от углов ступеней клина β1 и β2, построить её графически. Угол β3 фиксирован. В каждой точке зависимости система скачков должна существовать (не должно быть отошедших скачков).

  2. Определить углы β1 и β2, соответствующие максимальному значению коэффициента восстановления полного давления, то есть

(5)#{β1,β2}=arg max0<β1,β2<2πσΣ(β1,β2)

Исходные данные: известна скорость набегающего потока M1=3 и угол 3-й ступени клина β3=33. Показатель адиабаты воздуха k=1.4.

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

(6)#tanΔβi=sin2νi1Mi2k+12(sin2νi1Mi2)cotνi;
(7)#Δβi=βiβi1;
(8)#λi+1=λicosνicos(νiΔβi);
(9)#σi=p0,i+1p0,i==(k+12)k+1k1(1Mi2sin2νi+k12)kk1(kMi2sin2νik12)1k1;
(10)#σΣ=i=13σi.

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

(11)#M(λ)=λ2k+11k1k+1λ2;
λ(M)=Mk+121+k12M2;

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

_images/clin-scheme.png

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

_images/avulsion.png

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

Important

На Условие отрыва скачка уплотнения βiΔβi и νi - угол СУ.

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

  1. Из уравнения (6) при известном согласно (7) угле Δβ1 и по исходному M1 численно ищется значение угла СУ ν1 на первой ступени клина.

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

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

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

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

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

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

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

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

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

Требуется:

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

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

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

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

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

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

Important

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

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

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

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

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

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

(12)#f(x,y)=(x+2y7)2+(2x+y5)2.

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

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

f(x1,x2,x3)=i=12[100(xi+1xi2)2+(xi1)2].

Область определения аргументов: x1,x2,x3. Показать, что f(1,1,1)=0 есть минимум.

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

(13)#f(x,y)=20exp[0.2x2+y22]exp[cos(2πx)+cos(2πy)2]+e+20.

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

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

(14)#f(x,y)=sin(y)exp[(1cosx)2]+cos(x)exp[(1siny)2]+(xy)2

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

(x+5)2+(y+5)2<25.

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

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