Доброго времени суток. Поставили решить задачу о назначениях, когда имеется n работников и m мест и известна производительность работника на каждом рабочем месте. Собственно, найти нужно оптимальное распределение работников по рабочим местам. Может, у кого-нибудь имеются алгоритмы, наиболее удобные для реализации? (решать нужно в делфи)
В праздники не выкроил времени, увы.. Если считать, что целевая функция - это просто сумма производительностей на местах, то задача решается простым перебором в цикле с рекурсией. Метод, наверняка, не оптимальный, но про оптимизацию можно подумать потом . По крайней мере, это решение может служить для проверки оптимизированных алгоритмов.
{оптимизация размещения работников по рабочим местам} {for .helga by Lapp} const Nx=100; {максимум человек} Mx=100; {максимум рабочих мест}
var P:array[1..Nx,1..Mx]of real; {сведения о производительности} Chart,Cx:array[1..Mx]of integer; {карта назначений - текущая и оптимальная} f:text; i,j,m,n:integer; Product,Px:real;
{рекурсивная процедура суммирования производительности} procedure Productivity(k:integer); var P0:real; i:integer; begin for i:=1 to m do if Chart[i]=0 then begin Chart[i]:=k; {занимаем рабочее место в табеле} P0:=Product; {запоминаем текущую производительность} Product:=Product+P[k,i]; {прибавляем производительность k-го рабочего на i-том месте} if k<n then Productivity(k+1) {если не все люди опробованы то продолжаем рекурсию} else if Product>Px then begin {.. в противнгом случае - смотрим суммарную производительность..} Px:=Product; {.. если она больше получившейся раньше,..} Cx:=Chart {.. то запоминаем ее и табель} end; Chart[i]:=0; {очищаем табель} Product:=P0 {возвращаемся к старой производительности} end end;
begin Assign(f,'manpower.dat'); {читаем файл сведений о рабочей силе..} ReSet(f); ReadLn(f,n); ReadLn(f,m); for j:=1 to n do begin for i:=1 to m do Read(f,P[j,i]); ReadLn(f) end; for i:=1 to m do Chart[i]:=0; {очищаем карту назначений} Product:=0; {очищаем суммарную производительность} Px:=0; {очищаем максимальную произмодительность} Productivity(1); {вызываем рекурсивный процесс подсчета производительности} WriteLn('Maximum productivity: ',Px:6:4); {печатаем результаты..} WriteLn('Positions chart:'); for i:=1 to m do Write(Cx[i]:4); WriteLn; ReadLn end.
Программа берет данные из файла: первая строчка - n, количество человек; вторая строчка - m, количество рабочих мест; потом идет n строк по m элементов, i-ый элемент j-ой строки есть производительность j-го человека на i-ом месте. Пример файла manpower.dat :
Код
3 4 1 1.2 2 0.5 0 3 1.5 1 0 2 1.8 0
Этот вариант годится только для случая, когда нет безработицы , то есть кол-во рабочих мест больше либо равно кол-ва людей. Распространить программу на общий случай довольно легко: надо ввести недостающие рабочие места, то есть дополнить m до n, положив производительность каждого работника на этих местах равной нулю. Если нужно, я внесу необходимые изменения в прогу..
--------------------
я - ветер, я северный холодный ветер я час расставанья, я год возвращенья домой
Ну, не знаю.. Мне кажется, что без этого решение не полное. Короче, вот полный вариант:
{оптимизация размещения работников по рабочим местам} {включая случай n>m } {for .helga by Lapp} const Nx=100; {максимум человек} Mx=100; {максимум рабочих мест}
var P:array[1..Nx,1..Mx]of real; {сведения о производительности} Chart,Cx:array[1..Mx]of integer; {карта назначений - текущая и оптимальная} f:text; i,j,m,m1,n:integer; Product,Px:real;
{рекурсивная процедура суммирования производительности} procedure Productivity(k:integer); var P0:real; i:integer; begin for i:=1 to m1 do if Chart[i]=0 then begin Chart[i]:=k; {занимаем рабочее место в табеле} P0:=Product; {запоминаем текущую производительность} Product:=Product+P[k,i]; {прибавляем производительность k-го рабочего на i-том месте} if k<n then Productivity(k+1) {если не все люди опробованы то продолжаем рекурсию} else if Product>Px then begin {.. в противнгом случае - смотрим суммарную производительность..} Px:=Product; {.. если она больше получившейся раньше,..} Cx:=Chart {.. то запоминаем ее и табель} end; Chart[i]:=0; {очищаем табель} Product:=P0 {возвращаемся к старой производительности} end end;
begin Assign(f,'manpower.dat'); {читаем файл сведений о рабочей силе..} ReSet(f); ReadLn(f,n); ReadLn(f,m); m1:=m; if n>m then m1:=n; {вводим фиктивные рабочие места..} for j:=1 to n do begin for i:=1 to m do Read(f,P[j,i]); ReadLn(f); for i:=m+1 to m1 do P[j,i]:=0 {.. и заполняем их нулями} end; for i:=1 to m1 do Chart[i]:=0; {очищаем карту назначений} Product:=0; {очищаем суммарную производительность} Px:=0; {очищаем максимальную произмодительность} Productivity(1); {вызываем рекурсивный процесс подсчета производительности} WriteLn('Maximum productivity: ',Px:6:4); {печатаем результаты..} WriteLn('Positions chart:'); for i:=1 to m do Write(Cx[i]:4); WriteLn; ReadLn end.
И, соответственно, пример файла данных к ней:
Код
3 2 1 1.2 0 3 1.5 2
--------------------
я - ветер, я северный холодный ветер я час расставанья, я год возвращенья домой