一．指派问题
在生活中经常遇见这样的问题，有n项任务要求n个人完成，这n个人完成各项任务的效率（或所需时间）不同，于是产生指派哪个人去完成哪项任务的问题，这类问题称为指派问题或分派问题。
1．指派问题的数学模型
引入变量Xij，其取值只能是1或0，并令Xij=1表示指派第i人完成第j项任务 Xij=0表示不指派第i人完成第j项任务；当问题要求极小化时，数学模型是： Min z=  ①
 ② ③
 ④
约束条件②说明第j项任务只能由1人完成；约束条件③说明第i人只能完成1项任务。满足约束条件②--④的解，可以用矩阵来表示，此矩阵称为解矩阵。
当问题要求极大化时，可令bij=M-Cij把问题转换成极小化模型。
二．指派问题的解法
指派问题是0-1规划的特例，也是运输问题的特例，可以用整数规划、0-1规划、运输问题的解法去求解，但因忽略指派问题的特殊性，因而不能达到好的解题效率。
指派问题的最优解具有这样的性质，若从系数矩阵（bij）的一行（列）各元素中分别减去该行（列）的最小元素，得到新矩阵（bij’），那么以（bij’）为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。
库恩于1955年提出了指派问题的解法，其中引用了康尼格一个关于矩阵中0元素的定理：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。
三．程序实现
依照上述方法，编制Assignment类，以实现对任意规模的指派问题的解决。
class Assignment
{
public:
Assignment(int n, int * eff);
~Assignment();
int * getAssignment(bool isMin=true);
private:
bool hasAssigned(int * eff);
bool hasZero(int * eff);
void changeMinToMax();
void getRowColZero(int * eff);
void assignAndGetoff(int * eff);
void changeEfficiency(int * eff);
void getTaskAssignment(int * eff);
void assignCore(int * eff);
void resetZero (int * eff);
int getLineNum(int *eff);
private:
bool allAssigned;
int * task;
int * efficiency;
int scale;
int * rowTicked;
int * colTicked;
public: // 定义的几个常数
const int MAXVALUE ;
const bool MAXASSIGN;
const bool MINASSIGN;
const int ASSIGNED ;
const int GETOFFED ;
};
Assignment类说明
1.Assignment类实现任务指派；
2.使用示例
Assignment assignment = Assignment(n, eff);
int * Task = assignment.getTaskAssignment(isMin);
其中，n表示指派任务个数；
eff 效率系数，以一维数组传递；
isMin 是否取最小代价指派；isMin=true时，表示为最小代价指派，缺省情况下，isMin=true；
Task 指派结果，若Task[i]=j, 表示第i个人完成第j项任务(以0为第一序数)；
3.应用举例：
int main()
{
int scale, *eff, * task;
int i, j;
// Get Scale
cout<<"\nThe Scale Of Problem: ";
cin>>scale;
// Construct eff
eff = new int[scale*scale];
// Get Efficiency
for(i=0; i<scale; i++)
for(j=0; j<scale; j++)
{
cout<<"\nThe Efficiency Of The "<<i+1<<"th Person Doing The "
<<j+1<<"th Task Is (Natural Number): ";
cin>>eff[i*scale+j];
}
// Get minormax
bool isMin= true;
char isY;
cout<<"\nIs a min cost assignment ?(Y for yes, & others for no): ";
cin>>isY;
isMin= (isY=='Y' || isY=='y');
// List the Efficiency
cout<<"\n" <<"The Effienciency:";
for(i=0; i<scale; i++)
{
cout<<"\nThe " <<i+1 <<"th person: ";
for(j=0; j<scale; j++)
cout<<eff[i*scale+j] <<" ";
}
// Assignment Type
if (isMin)
cout<<"\n\nMin Cost Assignment.\n";
else
cout<<"\n\nMax Effect Assignment.\n";
Assignment assignment = Assignment(scale, (int *)eff);
task = assignment.getAssignment(isMin);
// Output the result
for(i=0; i<scale; i++)
cout<<"\nThe " <<i+1 <<"th person do the " <<task[i]+1 <<"th task;" ;
cout<<"\n";
return 0;
}
按照提示输入问题规模、相应的效率矩阵、求解方式（最大效率或最小代价）后程序就可以输出结果。
以下是assignment.cpp的内容,assignment.h的内容即类的定义部分.
#include "assignment.h"
Assignment::Assignment(int n, int * eff):
MAXVALUE(65532), MAXASSIGN(false), MINASSIGN(true),
ASSIGNED(-1), GETOFFED(-2)
{
scale = n;
efficiency = new int[scale*scale];
for(int i=0; i<scale; i++)
for(int j=0; j<scale; j++)
efficiency[i*scale+j] = eff[i*scale+j];
rowTicked = new int[scale];
colTicked = new int[scale];
task = new int[scale];
}
Assignment::~Assignment()
{
delete [] efficiency;
delete [] rowTicked;
delete [] colTicked;
delete [] task;
}
int * Assignment::getAssignment(bool isMin)
{
if (!isMin)
changeMinToMax();
allAssigned = false;
getRowColZero(efficiency);
assignAndGetoff(efficiency);
assignCore(efficiency);
return task; // Task is set by assignCore()
}
void Assignment::changeMinToMax()
{
int max = 0, i,j;
// Get Max
for(i=0; i<scale; i++)
for(j=0; j<scale; j++)
if (efficiency[i*scale+j] > max)
max = efficiency[i*scale+j];
// Change
for(i=0; i<scale; i++)
for(j=0; j<scale; j++)
efficiency[i*scale+j] -= max;
}
void Assignment::getRowColZero(int * eff)
{
int i,j , min;
// Zero in Row
for(i=0; i<scale; i++)
{
min = MAXVALUE; // Get Min
for(j=0; j<scale; j++)
if (eff[i*scale+j] < min)
min = eff[i*scale+j];
if (min==0) continue;
for(j=0; j<scale; j++)
eff[i*scale+j] -= min;
}
// Zero in Col
for(j=0; j<scale; j++)
{
min = MAXVALUE; // Get Min
for(i=0; i<scale; i++)
if (eff[i*scale+j] < min)
min = eff[i*scale+j];
if (min ==0) continue;
for(i=0; i<scale; i++)
eff[i*scale+j] -= min;
}
}
void Assignment::assignAndGetoff(int * eff)
{
int i,j,k, rowZero, colZero, zeroPos;
bool isOver = false;
while (!isOver)
{
isOver = true;
// From row which has only one zero
for(i=0; i<scale; i++)
{
rowZero = 0;
for(j=0; j<scale; j++)
if (eff[i*scale+j] == 0)
{
rowZero++;
zeroPos = j; // Write down the col number
}
// Only one zero in row
if (rowZero == 1)
{
isOver = false;
eff[i*scale+zeroPos] = ASSIGNED;
for(k=0; k<scale; k++) // Zero in the column maked by GETOFFED
if (eff[k*scale+zeroPos]==0)
eff[k*scale+zeroPos] = GETOFFED;
}
} // End for____Row
// Column process
for(j=0; j<scale; j++)
{
colZero = 0;
for(i=0; i<scale; i++)
if (eff[i*scale+j]==0)
{
colZero++;
zeroPos = i; // Write down the row number
}
if (colZero==1)
{
isOver = true;
eff[zeroPos*scale+j] = ASSIGNED;
for(k=0; k<scale; k++)
if (eff[zeroPos*scale+k]==0)
eff[zeroPos*scale+k] = GETOFFED;
} // End If
} // End for____Column
} // End while
return;
}
/*void Assignment::assignWithStart(int * eff, int row, int col)
{
int i,j;
if (allAssigned)
return;
if (hasZero(eff))
{
for(i=0; i<scale; i++)
{
if (allAssigned)
return;
for(j=0; j<scale; j++)
{
if (allAssigned)
return;
if (eff[i*scale+j]==0)
{
int * tempEff = new int[scale*scale];
int k,m;
for(k=0; k<scale; k++)
for(m=0; m<scale; m++)
tempEff[k*scale+m] = eff[k*scale+m];
tempEff[row*scale+col] = ASSIGNED;
for(k=0; k<scale; k++)
if (tempEff[k*scale+col]==0)
tempEff[k*scale+col] = GETOFFED;
for(k=0; k<scale; k++)
if (tempEff[row*scale+k]==0)
tempEff[row*scale+k] = GETOFFED;
// Get new row, col Start
for(k=0; k<scale; k++)
for(m=0; m<scale; m++)
if (tempEff[k*scale+m]==0)
assignWithStart(tempEff, k, m);
delete [] tempEff;
} // End if
}
}
}
else // No zero
{
while (getLineNum(eff) < scale)
{
changeEfficiency(eff);
if (hasAssigned(eff)) break;
}
if (hasAssigned(eff))
{
allAssigned = true;
getTaskAssignment(eff);
return;
}
} // End else
}*/
int Assignment::getLineNum(int * eff)
{
int i,j, lineNum=0;
bool hasMore = true;
// Initiate rowTicked & colTicked
for(i=0; i<scale; i++)
{
rowTicked[i] = colTicked[i] = 0;
}
// Get rows that has no ASSIGNED
for(i=0; i<scale; i++)
{
rowTicked[i] = 1;
for(j=0; j<scale; j++)
if (eff[i*scale+j]==ASSIGNED)
{
rowTicked[i] = 0;
break;
}
}
int time=0;
while ( (hasMore)&& (time++<scale) )
{
hasMore = false;
// Column
for(i=0; i<scale; i++)
if (rowTicked[i]==1)
for(j=0; j<scale; j++)
if ( (eff[i*scale+j]==ASSIGNED) ||
(eff[i*scale+j]==GETOFFED) )
{
colTicked[j] = 1;
hasMore = true;
break;
}
// Row
for(j=0; j<scale; j++)
if (colTicked[j])
for(i=0; i<scale; i++)
if (eff[i*scale+j]==ASSIGNED)
{
rowTicked[i] = 1;
hasMore = true;
break;
}
} // End while
for(i=0; i<scale; i++)
{
if (rowTicked[i]==0)
lineNum++;
if (colTicked[j]==1)
lineNum++;
}
return lineNum;
}
void Assignment::changeEfficiency(int * eff)
{
int i,j, minValue = MAXVALUE;
// Get minValue in where lines donot cover
for(i=0; i<scale; i++)
{
if (rowTicked[i]==0) continue;
for(j=0; j<scale; j++)
{
if (colTicked[j]==1) continue;
if (eff[i*scale+j] < minValue)
minValue = eff[i*scale+j];
}
}
// To get more zero
for(i=0; i<scale; i++)
if (rowTicked[i]==1)
for(j=0; j<scale; j++)
eff[i*scale+j] -= minValue;
for(j=0; j<scale; j++)
if (colTicked[j]==1)
for(i=0; i<scale; i++)
eff[i*scale+j] += minValue;
}
void Assignment::getTaskAssignment(int * eff)
{
for(int i=0; i<scale; i++)
for(int j=0; j<scale; j++)
if (eff[i*scale+j]==ASSIGNED)
{
task[i] = j; // Person i do the task j
break;
}
}
bool Assignment::hasZero(int * eff)
{
for(int i=0; i<scale; i++)
for(int j=0; j<scale; j++)
if (eff[i*scale+j]==0) return true;
return false;
}
bool Assignment::hasAssigned(int * eff)
{
int i, j;
for(i=0; i<scale; i++)
{
for(j=0; j<scale; j++)
if (eff[i*scale+j]==ASSIGNED)
break;
if (j==scale) return false;
}
return true;
}
void Assignment::assignCore(int * eff)
{
if (hasAssigned(eff))
{
getTaskAssignment(eff);
allAssigned = true;
return;
}
else
{
// Zero not Assigned ?
if (hasZero(eff))
{
// Not All Assigned & has Zero
for(int i=0; i<scale; i++)
{
if (allAssigned) break;
for(int j=0; j<scale; j++)
{
if (allAssigned) break;
// Get the first zero, for getting the best zero is so difficult.
if (eff[i*scale+j]==0)
{
int m;
int * tempEff = new int [scale*scale];
// Keep the copy
for(m=0; m<scale*scale; m++)
tempEff[m] = eff[m];
tempEff[i*scale + j] = ASSIGNED; // Marked as Assigned
for(m=0; m<scale; m++)
{
// Marked Zero in the same col As GETOFFED
if (tempEff[m*scale + j]==0) tempEff[m*scale+j] = GETOFFED;
// Marked Zero in the same row As GETOFFED
if (tempEff[i*scale + m]==0) tempEff[i*scale+m] = GETOFFED;
} // End for___m
//if (! allAssigned)
assignCore(tempEff); // Nested Call
delete [] tempEff;
}
} // End for___j
} // End for___i(To get rid of Dependent Zero
} // End if____(hasZero(eff))
// Not All Assigned & has No Zero
else
{
if (getLineNum(eff)<scale) // l<n
{
changeEfficiency(eff); // Change Efficiency Matrix
resetZero(eff);
getRowColZero(eff);
assignAndGetoff(eff);
assignCore(eff);
}
else // l=n
return;
}
} // End else
return;
}
void Assignment::resetZero(int * eff)
{
for(int i=0; i<scale*scale; i++)
if ((eff[i]==ASSIGNED)||(eff[i]==GETOFFED))
eff[i]=0;
}
|
本类阅读TOP10