Страница 1 из 1

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

Добавлено: Сб апр 13, 2013 2:39 pm
gratix
Есть задача оптимизации
Изображение

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

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

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

Добавлено: Сб апр 13, 2013 7:57 pm
Kitonum
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]

Неточность

Добавлено: Сб апр 13, 2013 8:05 pm
Markiyan Hirnyk
Не учтено условие x <= b[1].

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

Добавлено: Сб апр 13, 2013 8:16 pm
Kitonum
Markiyan Hirnyk писал(а):Не учтено условие x <= b[1].

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

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

Добавлено: Сб апр 13, 2013 8:36 pm
Markiyan Hirnyk
Kitonum писал(а):
Markiyan Hirnyk писал(а):Не учтено условие x <= b[1].

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

Вы правы.