Кусочно-линейное программирование.

[Сомик]

Имеется следующая задача
$|\sum_{i=1}^{n}a_{1,i}x_i|+ \dots + |\sum_{i=1}^{n}a_{k,i}x_i| \rightarrow max$ при $0 \leq x_i \leq 1$
Где бы можно было посмотреть алгоритмы ее решения ?

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

[ddn]

Сомик писал(а):

Имеется следующая задача
$|\sum\limits_{i=1}^{n}a_{1,i}x_i|+ \dots + |\sum\limits_{i=1}^{n}a_{k,i}x_i|\rightarrow max$ при $0 \leq x_i \leq 1$
Где бы можно было посмотреть алгоритмы ее решения?

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

Можно делать тоже, что и в симплекс-методе: искать решения, с все более возрастающим значением целевой функции. Но даже в задачах ЛП максимальное число итераций оценивается сверху как $C^m_n$ - что растет экспоненциально от числа равенств $m$. Есть правда полиномиальные алгоритмы решения ЗЛП, но они сложны.

При фиксированном значении всех переменных, кроме одной $x_i$, целевая функция принимает вид
$z=\sum\limits_{j=1}^{k}|b_{j,i}+a_{j,i}x_i|$, где $b_{j,i}=\sum\limits_{_{(i'\not=i)}^{i'=1}}^{n}a_{j,i'}x_{i'}$
Значит, график целевой функции от одной из переменных $x_i$ представляет собой ломаную линию и достигает максимума, либо в крайней точке $x_i=0;1$, либо в одной из точек точке излома $x_i=-\frac{b_{j,i}}{a_{j,i}}$ ($a_{j,i}\not=0$), то есть в некой точке $x_i^*$. Сменяем значение (на $x_i^*$) той переменной $x_i$, которая дает наибольшее увеличение целевой функции $\Delta z_i^*$, при условии, что оно больше нуля. И так повторяем итерации, пока это наибольшее увеличение целевой функции не станет равным нулю $\Delta z_i^*=0$. Значит, мы достигли локального максимума. Если между любыми двумя допустимыми точками $\vec x$ и $\vec x'$ существует ограниченный условиями $0\leq x_i \leq 1$ ломаный путь с отрезками параллельными осям $Ox_i$ и монотонный по значениям целевой функции (это некий аналог условия выпуклости задачи), то локальный максимум является и глобальным.
Увы, не могу сформулировать для этой задачи понятие крайней точки по аналогии с ЗЛП, тогда можно было бы сформулировать условие выпуклости с произвольно направленными отрезками, и, вероятно, доказать выпуклость задачи для общего случая.

Вот процедура, написанная в Мапле 8, от аргументов:
число переменных $n$, число модулей в целевой функции $k$, матрица коэффициентов A=[seq([seq(A[j,i],i=1..n)],j=1..k)];
и дающая: число итераций $r$ от начальных значений переменных $x_i=0$ до локально-максимального решения, решение $\vec x=(x_i|_{i=1}^n)$, значение максимума целевой функции $m$:

> zklp:=proc(n,k,A)
> local a,b,c,i,j,l,m,r,u,v,x,y,z;
> a:=[seq([seq(convert(A[j,i],rational,exact),i=1..n)],j=1..k),seq([seq(1,i=1..n)],j=1..2)]; c:=[seq(0,i=1..k+2)]; x:=[seq(0,i=1..n)]; y:=[seq(0,i=1..n)]; z:=[seq(0,i=1..n)]; m:=0; r:=0;
> b:=false; for i to n do for j to k do if a[j,i]<>0 then b:=true; j:=k; i:=n fi od od;
> while b do for i to n do c[k+1]:=x[i]; c[k+2]:=x[i]-1; y[i]:=0; z[i]:=0; for j to k+2 do if a[j,i]<>0 then u:=-c[j]/a[j,i]; if 0<=u and u<=1 then v:=add(abs(c[l]+a[l,i]*u),l=1..k); if v>z[i] then y[i]:=u+x[i]; z[i]:=v fi fi fi od od; l:=0; v:=0; for i to n do if z[i]>v then l:=i; v:=z[i] fi od; if z[l]>m then for j to k do c[j]:=c[j]+a[j,l]*(y[l]-x[l]) od; x[l]:=y[l]; m:=z[l]; r:=r+1 else b:=false fi od;
> RETURN(r,x,m)
> end:

прим: функция $convert(a,rational,exact)$ преобразует числа $a$ вещественного типа в рациональную десятичную дробь, а рационального и целого типа не изменяет; использована, чтобы пресечь округления.

[Vassil]

Простите, если вопрос со стороны будет немного наивным.

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

Известно тогда, можно использовать программы для квадратичного программирования, как для простейших научных случаях, например, скажем функции quapro или qld в свободном пакeте scilab.

[Сомик]

ddn, спасибо, буду разбираться.

Vassil, надо подумать. Может быть и можно. Вообще это задача возникла из социологии. Искомые переменные - это веса, которые присваиваются ответам в социологическом опросе. Необходимо так подобрать эти веса, чтобы респонденты "как можно лучше" распределились на группы.

[mserg]

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

[mserg]

Немного не так. Требуется максимизировать
$\sum\limits_{i=1}^{k}z_j$
При условиях
$y_j=\sum\limits_{i=1}^{n}a_{j,i}x_i$
$z_j\leq$ y_j
$z_j\leq$ -y_j
Где $z_j - неотрицательные переменные; $y_j - переменные, которые могут принимать любые значения.

[Сомик]

mserg в сообщении #152863 писал(а):

$z_j\leq$ y_j
$z_j\leq$ -y_j
Где $z_j$ - неотрицательные переменные;

Не очень понятно...
Если z_j - неотрицательные, т.е. 0 \leq z_j
то 0 \leq y_jи 0 \leq -y_j, откуда y_j = 0

[mserg]

Тогда так: максимизировать
$\sum\limits_{i=1}^{k}z_j$
При условиях
$y_j=\sum\limits_{i=1}^{n}a_{j,i}x_i$
$z_j\leq$ y_j+{b_j}M$
$z_j\leq$ -y_j+(1-b_j)M$
Где $z_j$ - неотрицательные переменные; $y_j$ - переменные, которые могут принимать любые значения; $b_j$ - это псевдобулева переменная, M - достаточно большое число. Это частично-целочисленная линейная задача.

А есть данные? С ними я уж точно не ошибусь

[Сомик]

mserg в сообщении #152926 писал(а):

А есть данные? С ними я уж точно не ошибусь

Данные там страшные, модулей штук 300, переменных - 87

Спасибо за помощь. Но я уже все численно посчитал.

[mserg]

Т.е. данные не представляется возможным выложить? Проверили бы, что Вы там "численно посчитали".

[Сомик]

mserg писал(а):

Т.е. данные не представляется возможным выложить? Проверили бы, что Вы там "численно посчитали".

Проверили "на глаз". Нужно было проанализировать выборку и отдать результат эксперту (социологу). Он сказал что его устраивает Не требовалось найти абсолютный максимум, требовалось лишь найти такую точку, чтобы выборка "выстроилась" по определением правилам. Это визуально видно, когда она "выстраивается".

Хотя, наверно, на будущее, надо будет изменить метод чтобы там сводилось все к задаче квадратичного программирования. Тогда все проще будет.

[mserg]

Если модули в сумме заменить на возведение в квадраты, то задача станет еще сложнее. Квадратичное программирование подразумевает минимизацию неотрицательно определенной квадратичной формы, либо максимизацию неположительно определенной формы. Для вашей задачи не имеет место ни один из этих случаев, значит задача не выпукла и она является труднорешаемой (эффективный алгоритм решения неизвестен)... Вот такой маленький нюанс.
Честно говоря, я думаю, что линейное программирование в очередной раз посрамит все прочие методы и алгоритмы.