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

Форум для обсуждения вопросов математики

Модератор: Admin

gratix
Сообщения: 1
Зарегистрирован: Сб апр 13, 2013 2:25 pm

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

Сообщение gratix » Сб апр 13, 2013 2:39 pm

Есть задача оптимизации
Изображение

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

Вопрос с классификацией. Это задача целочисленного нелинейного программирования?
И далее вопрос как можно такое решать? Основную сложность составляет функция взятия целой части. Можно ли как-то от нее избавится не теряя точности и не вводя дополнительных переменных?
По поводу выбора метода решения. Как я понимаю функция не выпуклая, поэтому сразу много методов не подходит, потому что будут находить локальный экстремум.
Поэтому решать можно только переборными методами, методом ветвей и границ, эвристическими методами, например, с помощью генетеического алгоритма и т.д. Так ли это?
Может есть какие-то пакеты для решения таких задач?

Kitonum
Сообщения: 2084
Зарегистрирован: Ср дек 31, 2008 1:55 pm
Откуда: г. Пенза

Re: Решить задачу оптмизации

Сообщение Kitonum » Сб апр 13, 2013 7:57 pm

gratix писал(а):Есть задача оптимизации
Изображение

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

Вопрос с классификацией. Это задача целочисленного нелинейного программирования?
И далее вопрос как можно такое решать? Основную сложность составляет функция взятия целой части. Можно ли как-то от нее избавится не теряя точности и не вводя дополнительных переменных?
По поводу выбора метода решения. Как я понимаю функция не выпуклая, поэтому сразу много методов не подходит, потому что будут находить локальный экстремум.
Поэтому решать можно только переборными методами, методом ветвей и границ, эвристическими методами, например, с помощью генетеического алгоритма и т.д. Так ли это?
Может есть какие-то пакеты для решения таких задач?

Так как у Вас одномерная дискретная оптимизация, то задача легко решается простейшим перебором в любом матпакете. Вот решение в Maple:

1) Сначала зададим значения всех параметров (возьмём все a[i]=1 , b[i] от 1000 до 1999, C=1/2 ) и посмотрим на график Вашей функции:

a:=[1$1000]: b:=[seq(i, i=1000..1999)]:
C:=1/2:
F:=x->add(a[i]/floor(b[i]/x)/x-a[i]/b[i], i=1..1000)+C/x;
plot(F, 1..1000, thickness=2);

Изображение

2) Видим, что минимум достигается для x где-то между 1 и 100. В цикле находим точное значение x0:

x0:=1:
for x from 2 to 1000 do
if F(x)<F(x0) then x0:=x fi:
od:
[x0, evalf(F(x0))];


[42, 0.02232744211]

Markiyan Hirnyk
Сообщения: 1366
Зарегистрирован: Вс дек 04, 2011 11:07 pm

Неточность

Сообщение Markiyan Hirnyk » Сб апр 13, 2013 8:05 pm

Не учтено условие x <= b[1].

Kitonum
Сообщения: 2084
Зарегистрирован: Ср дек 31, 2008 1:55 pm
Откуда: г. Пенза

Re: Неточность

Сообщение Kitonum » Сб апр 13, 2013 8:16 pm

Markiyan Hirnyk писал(а):Не учтено условие x <= b[1].

В условии написано, что x принадлежит [1; b[1]] . Это учтено, т.к. b[1]=1000, а x в цикле пробегает от 1 до 1000 .

Markiyan Hirnyk
Сообщения: 1366
Зарегистрирован: Вс дек 04, 2011 11:07 pm

Re: Неточность

Сообщение Markiyan Hirnyk » Сб апр 13, 2013 8:36 pm

Kitonum писал(а):
Markiyan Hirnyk писал(а):Не учтено условие x <= b[1].

В условии написано, что x принадлежит [1; b[1]] . Это учтено, т.к. b[1]=1000, а x в цикле пробегает от 1 до 1000 .

Вы правы.