IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> задача о назначаниях
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 26
Пол: Женский

Репутация: -  1  +


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

Заранее спасибо.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 26
Пол: Женский

Репутация: -  1  +


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

Сообщение отредактировано: .helga -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Новичок
*

Группа: Пользователи
Сообщений: 26
Пол: Женский

Репутация: -  1  +


Люди, неужели никто не знает? Хелп!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(.helga @ 24.12.2006 4:24) *

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

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

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

Этот вариант годится только для случая, когда нет безработицы smile.gif, то есть кол-во рабочих мест больше либо равно кол-ва людей. Распространить программу на общий случай довольно легко: надо ввести недостающие рабочие места, то есть дополнить m до n, положив производительность каждого работника на этих местах равной нулю. Если нужно, я внесу необходимые изменения в прогу..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Новичок
*

Группа: Пользователи
Сообщений: 26
Пол: Женский

Репутация: -  1  +


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

спасибо. буду смотреть/думать.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(.helga @ 3.01.2007 10:40) *

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

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



--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 15:51
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name