Доброго времени суток. Поставили решить задачу о назначениях, когда имеется n работников и m мест и известна производительность работника на каждом рабочем месте. Собственно, найти нужно оптимальное распределение работников по рабочим местам. Может, у кого-нибудь имеются алгоритмы, наиболее удобные для реализации? (решать нужно в делфи)
Ну, не знаю.. Мне кажется, что без этого решение не полное. Короче, вот полный вариант:
{оптимизация размещения работников по рабочим местам} {включая случай 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
--------------------
я - ветер, я северный холодный ветер я час расставанья, я год возвращенья домой