Задачи дискретной оптимизации с размещением

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

Модератор: Admin

Alex_cs_gsp
Сообщения: 30
Зарегистрирован: Чт май 11, 2006 9:22 pm
Откуда: Днепропетровск (УКРАИНА)

Задачи дискретной оптимизации с размещением

Сообщение Alex_cs_gsp » Вт мар 02, 2010 9:25 am

Подскажите пожалуйста как решать такие задачи, когда количество возможных перестановок велико. Например, такая задача, расфасовать 100 арбузов в 20 бочек, чтобы вес каждой бочки был примерно одинаков. Если тупой перебор, то это 100! перестановок, машина не потянет.

Admin
Site Admin
Сообщения: 543
Зарегистрирован: Пт янв 25, 2002 4:05 pm

Сообщение Admin » Вт мар 02, 2010 8:34 pm

Есть много всяких формул для приближенных расчетов. Например, "асимптотики и оценки" http://ru.wikipedia.org/wiki/%D0%9F%D0% ... 0.BB.D1.8F

Хотя условие Ваше задачи "чтобы вес каждой бочки был примерно одинаков" не формализовано.

Alex_cs_gsp
Сообщения: 30
Зарегистрирован: Чт май 11, 2006 9:22 pm
Откуда: Днепропетровск (УКРАИНА)

Сообщение Alex_cs_gsp » Вт мар 02, 2010 10:24 pm

Спасибо за ответ. Формализовать задачу можно многими способами, например, вариация масс бочек не более чем 5% или как-то так. (априори средней вес бочки определяется количество арбузов/количество бочек).
Если не трудно, дайте более расширенный ответ, какие формулы мне могут помочь в задаче размещения, я не понял причем тут "Асимптотика и оценки".

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

Re: Задачи дискретной оптимизации с размещением

Сообщение Kitonum » Вт мар 16, 2010 12:27 am

Alex_cs_gsp писал(а):Подскажите пожалуйста как решать такие задачи, когда количество возможных перестановок велико. Например, такая задача, расфасовать 100 арбузов в 20 бочек, чтобы вес каждой бочки был примерно одинаков. Если тупой перебор, то это 100! перестановок, машина не потянет.

Очень интересная задача! Написал 2 процедуры в Maple для её решения. Первая процедура Sorting1 основана на полных переборах соответствующих подмножеств и сортирует очень точно: максимальное отклонение от среднего веса бочки обычно не превышает нескольких грамм. Число арбузов и число бочек могут быть любыми (бочек, конечно, меньше чем арбузов), но реально применять можно, когда арбузов не более 30, иначе время вычислений может быть слишком большим. Вторая процедура Sorting2 считает приблихенно, погрешность обычно колеблется в диапазоне 100-300 граммов, но применима практически к любому числу арбузов. Единственное условие - число арбузов должно делиться на число бочек. Привожу коды этих процедур. Формальные аргументы: L - список масс арбузов, N - число бочек.
Sorting1:=proc(L,N)
local w,m,M,M1,M2,F,K,n,i,j,S,T,f,e;
w:=sum(L[i],i=1..nops(L))/N;
if type(nops(L)/N,integer) then m:=nops(L)/N-1..nops(L)/N+1 else
m:=floor(nops(L)/N-1)..ceil(nops(L)/N+1);fi;
M:=[seq(op(combinat[choose](L,k)),k=m)];
M1:=[seq([M[i],abs(sum(M[i][j],j=1..nops(M[i]))-w)],i=1..nops(M))];
F:=(a,b)->is(a[2]<=b[2]);
M2:=sort(M1,F);
K:=[M2[1]];
n:=nops(M2[1][1]);
for i from 2 while nops(K)<N do
if convert([seq(is(`intersect`({op(M2[i][1])},{op(K[k][1])})={}),k=1..nops(K))],`and`) then
K:=[op(K),M2[i]]; fi;od;
print(`Порядок заполнения бочек арбузами`);
print(seq(K[i][1],i=1..nops(K)));
print(`Массы бочек в кг`);
print(seq(add(K[i][1][j],j=1..nops(K[i][1])),i=1..nops(K)));
print(`Средняя масса арбузов в одной бочке в кг`);
print(evalf(w,5));
print(`Максимальное отклонение от средней массы в граммах`);
print(evalf[5](max(seq(abs(add(K[i][1][j],j=1..nops(K[i][1]))-w)*1000,i=1..nops(K)))));
end proc:

Пример работы этой процедуры:
Сначала с помощью генератора случайных чисел задаём список масс арбузов и число бочек:
print(`Список масс арбузов в кг`);
L:=sort( [seq(RandomTools[Generate](float(range=2.00..5.00, digits=4)), i=1..20)] );
print(`Число бочек`);
N:=3;

Список масс арбузов в кг

L := [2.200, 2.269, 2.444, 2.473, 2.480, 2.820, 2.924, 2.927, 3.013,

3.065, 3.149, 3.423, 4.186, 4.297, 4.415, 4.568, 4.643, 4.737,

4.901, 4.916]

Число бочек

N := 3


Запускаем программу:
Sorting1(L,N);

Порядок заполнения бочек арбузами

[2.200, 3.013, 4.186, 4.415, 4.568, 4.901],

[2.269, 2.444, 2.924, 2.927, 3.065, 4.737, 4.916],

[2.473, 2.480, 2.820, 3.149, 3.423, 4.297, 4.643]

Массы бочек в кг

23.283, 23.282, 23.285

Средняя масса арбузов в одной бочке в кг

23.283

Максимальное отклонение от средней массы в граммах

2.000



Код второй процедуры:
Sorting2:=proc(L,N)
local w,m,K,i,j,K1,F;
w:=add(L[i],i=1..nops(L))/N; m:=nops(L)/N;
K:=[seq([],i=1..N)];
for i from 1 to floor(nops(L)/2/N)*N do
for j from 1 to N do
if irem(i-1,N)=j-1 then K[j]:=[op(K[j]),L[i],L[nops(L)-i+1]] fi;
od;od;
if type(nops(L)/2/N,integer) then K:=seq(K[i],i=1..N) else
K1:=[seq([K[i],add(K[i][j],j=1..m-1)],i=1..N)];
F:=(a,b)->is(a[2]>=b[2]);
K1:=sort(K1,F);
for i from 1 to N do
K[i]:=[op(K1[i][1]),L[floor(nops(L)/2/N)*N+i]];od;
K:=seq(K[i],i=1..N);
fi;
print(`Порядок заполнения бочек арбузами`);
print(K);
print(`Массы бочек в кг`);
print(seq(add(K[i][j],j=1..m),i=1..N));
print(`Средняя масса арбузов в одной бочке в кг`);
print(evalf(w,5));
print(`Максимальное отклонение от средней массы в граммах`);
print(evalf[5](max(seq(abs(add(K[i][j],j=1..m)-w)*1000,i=1..N))));
end proc;


Пример работы:
Задаём параметры:
print(`Список масс арбузов в кг`);
L:=sort( [seq(RandomTools[Generate](float(range=2.00..5.00, digits=4)), i=1..100)] );
print(`Число бочек`);
N:=20;

Список масс арбузов в кг

L := [2.008, 2.100, 2.230, 2.251, 2.256, 2.298, 2.340, 2.435, 2.450,

2.455, 2.462, 2.526, 2.538, 2.558, 2.641, 2.644, 2.650, 2.650,

2.657, 2.752, 2.779, 2.800, 2.801, 2.893, 2.932, 2.937, 3.081,

3.156, 3.209, 3.209, 3.235, 3.245, 3.270, 3.307, 3.424, 3.434,

3.440, 3.471, 3.495, 3.500, 3.501, 3.525, 3.526, 3.542, 3.573,

3.609, 3.685, 3.686, 3.698, 3.702, 3.706, 3.716, 3.746, 3.768,

3.780, 3.799, 3.840, 3.870, 3.883, 3.914, 3.930, 4.003, 4.004,

4.007, 4.009, 4.069, 4.090, 4.199, 4.217, 4.229, 4.244, 4.335,

4.345, 4.362, 4.378, 4.389, 4.391, 4.415, 4.433, 4.452, 4.466,

4.515, 4.541, 4.564, 4.565, 4.572, 4.583, 4.584, 4.662, 4.692,

4.695, 4.829, 4.836, 4.860, 4.869, 4.906, 4.918, 4.930, 4.966,

4.967]

Число бочек

N := 20


Запускаем программу:
Sorting2(L,N);
Порядок заполнения бочек арбузами

[2.450, 4.829, 3.209, 4.335, 3.501],

[2.435, 4.836, 3.156, 4.345, 3.525],

[2.641, 4.572, 3.424, 4.069, 3.526],

[2.657, 4.515, 3.495, 4.003, 3.542],

[2.650, 4.541, 3.471, 4.004, 3.573],

[2.650, 4.564, 3.440, 4.007, 3.609],

[2.644, 4.565, 3.434, 4.009, 3.685],

[2.526, 4.662, 3.245, 4.217, 3.686],

[2.752, 4.466, 3.500, 3.930, 3.698],

[2.340, 4.860, 3.081, 4.362, 3.702],

[2.462, 4.692, 3.235, 4.229, 3.706],

[2.455, 4.695, 3.209, 4.244, 3.716],

[2.538, 4.584, 3.270, 4.199, 3.746],

[2.558, 4.583, 3.307, 4.090, 3.768],

[2.256, 4.906, 2.932, 4.389, 3.780],

[2.298, 4.869, 2.937, 4.378, 3.799],

[2.251, 4.918, 2.893, 4.391, 3.840],

[2.230, 4.930, 2.801, 4.415, 3.870],

[2.100, 4.966, 2.800, 4.433, 3.883],

[2.008, 4.967, 2.779, 4.452, 3.914]


Массы бочек в кг

18.324, 18.297, 18.232, 18.212, 18.239, 18.270, 18.337, 18.336,

18.346, 18.345, 18.324, 18.319, 18.337, 18.306, 18.263,

18.281, 18.293, 18.246, 18.182, 18.120


Средняя масса арбузов в одной бочке в кг

18.280

Максимальное отклонение от средней массы в граммах

160.00


YuK
Сообщения: 698
Зарегистрирован: Вт дек 09, 2003 7:42 pm

Сообщение YuK » Ср мар 17, 2010 4:55 am

Похоже пример с равномерным распределением, а если взять нормальное распределение - интересно какие наборы получатся?

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

Сообщение Kitonum » Ср мар 17, 2010 2:26 pm

YuK писал(а):Похоже пример с равномерным распределением, а если взять нормальное распределение - интересно какие наборы получатся?

Хороший вопрос! Конечно, если брать арбузы одного сорта и собранные с одного поля, то распределение масс будет нормальным. Привожу те же примеры (с таким же числом арбузов и бочек) для нормального распределения масс. Принял a=3.5 кг, sigma=0.4 кг.

Исходные данные для первой процедуры:
print(`Список масс арбузов в кг`);
L:=sort(evalf[4](RandomTools[Generate](list(distribution(Normal(3.5,0.4)),20))) );
print(`Число бочек`);
N:=3;

Список масс арбузов в кг

L := [2.466, 2.484, 2.827, 2.966, 3.029, 3.176, 3.219, 3.230, 3.280,

3.320, 3.348, 3.427, 3.503, 3.616, 3.697, 3.715, 3.781, 3.863,

3.888, 4.109]

Число бочек

N := 3


Результат работы первой процедуры:
Sorting1(L,N);

Порядок заполнения бочек арбузами

[2.466, 2.484, 3.029, 3.230, 3.503, 3.715, 3.888],

[2.827, 2.966, 3.176, 3.280, 3.320, 3.348, 3.427],

[3.219, 3.616, 3.697, 3.781, 3.863, 4.109]


Массы бочек в кг

22.315, 22.344, 22.285

Средняя масса арбузов в одной бочке в кг

22.315

Максимальное отклонение от средней массы в граммах

30.000


Исходные данные для второй процедуры:
print(`Список масс арбузов в кг`);
L:=sort(evalf[4](RandomTools[Generate](list(distribution(Normal(3.5,0.4)),100))) );print(`Число бочек`);
N:=20;

Список масс арбузов в кг

L := [2.231, 2.561, 2.586, 2.631, 2.692, 2.745, 2.822, 2.826, 2.918,

2.940, 2.950, 2.974, 3.018, 3.032, 3.039, 3.052, 3.075, 3.130,

3.155, 3.160, 3.161, 3.175, 3.224, 3.258, 3.272, 3.284, 3.299,

3.311, 3.322, 3.376, 3.389, 3.404, 3.412, 3.417, 3.446, 3.456,

3.484, 3.487, 3.491, 3.519, 3.529, 3.531, 3.567, 3.580, 3.594,

3.598, 3.605, 3.606, 3.609, 3.610, 3.614, 3.620, 3.625, 3.660,

3.664, 3.666, 3.673, 3.681, 3.691, 3.707, 3.716, 3.720, 3.726,

3.727, 3.729, 3.735, 3.736, 3.750, 3.755, 3.763, 3.765, 3.766,

3.789, 3.798, 3.803, 3.806, 3.815, 3.825, 3.840, 3.857, 3.863,

3.868, 3.886, 3.887, 3.892, 3.933, 3.946, 3.946, 3.954, 3.959,

3.965, 3.995, 4.060, 4.063, 4.101, 4.152, 4.164, 4.355, 4.436,

4.555]

Число бочек

N := 20


Результат работы второй процедуры:
Sorting2(L,N);
Порядок заполнения бочек арбузами

[3.160, 3.863, 3.519, 3.716, 3.529],

[3.155, 3.868, 3.491, 3.720, 3.531],

[3.130, 3.886, 3.487, 3.726, 3.567],

[3.075, 3.887, 3.484, 3.727, 3.580],

[3.039, 3.933, 3.446, 3.735, 3.594],

[3.032, 3.946, 3.417, 3.736, 3.598],

[3.052, 3.892, 3.456, 3.729, 3.605],

[3.018, 3.946, 3.412, 3.750, 3.606],

[2.974, 3.954, 3.404, 3.755, 3.609],

[2.950, 3.959, 3.389, 3.763, 3.610],

[2.940, 3.965, 3.376, 3.765, 3.614],

[2.561, 4.436, 3.175, 3.840, 3.620],

[2.918, 3.995, 3.322, 3.766, 3.625],

[2.586, 4.355, 3.224, 3.825, 3.660],

[2.826, 4.060, 3.311, 3.789, 3.664],

[2.822, 4.063, 3.299, 3.798, 3.666],

[2.745, 4.101, 3.284, 3.803, 3.673],

[2.692, 4.152, 3.272, 3.806, 3.681],

[2.631, 4.164, 3.258, 3.815, 3.691],

[2.231, 4.555, 3.161, 3.857, 3.707]


Массы бочек в кг

17.787, 17.765, 17.796, 17.753, 17.747, 17.729, 17.734, 17.732,

17.696, 17.671, 17.660, 17.632, 17.626, 17.650, 17.650,

17.648, 17.606, 17.603, 17.559, 17.511

Средняя масса арбузов в одной бочке

17.678

Максимальное отклонение от средней массы в граммах

167.00

YuK
Сообщения: 698
Зарегистрирован: Вт дек 09, 2003 7:42 pm

Сообщение YuK » Ср мар 17, 2010 5:07 pm

А здесь что делается полный перебор C(100,5)? И сколько времени тратится на решение?

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

Сообщение Kitonum » Ср мар 17, 2010 9:53 pm

YuK писал(а):А здесь что делается полный перебор C(100,5)? И сколько времени тратится на решение?

Нет, конечно! Если перебирать все подмножества по 5 из 100, то счёт может продолжаться несколько часов. Здесь идея совсем другая (в отличии от первой процедуры). Если Вы заметили, то список масс арбузов сортирован по возрастанию. В первую бочку кладём первый и последний арбуз, во вторую бочку - второй и предпоследний и т.д. с небольшой вариацией в конце (разбирайте код!). Время вычисления меньше секунды.

Alex_cs_gsp
Сообщения: 30
Зарегистрирован: Чт май 11, 2006 9:22 pm
Откуда: Днепропетровск (УКРАИНА)

Сообщение Alex_cs_gsp » Пн мар 22, 2010 8:28 pm

Спасибо за проявленный интерес. В действительности, это я интерпретировал реальную техническую задачу в такую комбинаторную. Другой программист, также решал прямым перебором, и то в конце-концов после двух суток вычислений, оставались не раскиданные "арбузы". Если полный перебор, выйдем на пару месяцев вычислений.
Возникла идея использовать алгоритмы кластеризации, таким образом получится определить группы "арбузов". Затем раскидывать из каждого кластера поровну в каждую бочку., т.е не арбузы на бочки делим а наоборот бочки на арбузы. Например, сначала вроде бы две бочки, в эти две бочки запихиваем поровну арбузы из каждого кластера, затем задача сводится к разделению этих двух бочек на 4 и т.п., пока не будет достигнута средняя масса + % на вариацию. Осталась додумать алгоритм, до каких пор на кластеры разбивать, никак времени не найду.