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

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

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

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

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

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

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

Добавлено: Вт мар 16, 2010 12:27 am
Kitonum
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


Добавлено: Ср мар 17, 2010 4:55 am
YuK
Похоже пример с равномерным распределением, а если взять нормальное распределение - интересно какие наборы получатся?

Добавлено: Ср мар 17, 2010 2:26 pm
Kitonum
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

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

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

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

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