задача о назначаниях Опции

[.helga]

Доброго времени суток.
Поставили решить задачу о назначениях, когда имеется n работников и m мест и известна производительность работника на каждом рабочем месте.
Собственно, найти нужно оптимальное распределение работников по рабочим местам.
Может, у кого-нибудь имеются алгоритмы, наиболее удобные для реализации?
(решать нужно в делфи)

Заранее спасибо.

[Lapp]

Напиши вид целевой функции для оптимизации.

[.helga]

честно, я понятия не имею.
было дано только это условие, а как и что с ним делать, я не знаю.

Сообщение отредактировано: .helga - 23.12.2006 0:45

[.helga]

Люди, неужели никто не знает? Хелп!

[Lapp]

Люди, неужели никто не знает? Хелп!

В праздники не выкроил времени, увы..
Если считать, что целевая функция - это просто сумма производительностей на местах, то задача решается простым перебором в цикле с рекурсией. Метод, наверняка, не оптимальный, но про оптимизацию можно подумать потом . По крайней мере, это решение может служить для проверки оптимизированных алгоритмов.

{оптимизация размещения работников по рабочим местам}
{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, положив производительность каждого работника на этих местах равной нулю. Если нужно, я внесу необходимые изменения в прогу..

[.helga]

По идее, задача о назначениях - частный случай транспортной задачи, когда n=m. Так что в этих задачах всегда полная занятость

спасибо. буду смотреть/думать.

[Lapp]

в этих задачах всегда полная занятость

Ну, не знаю.. Мне кажется, что без этого решение не полное.
Короче, вот полный вариант:

{оптимизация размещения работников по рабочим местам}
{включая случай 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