13518219792
定义x(i,j)表示从产地i运往销地j的数量
让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：空间域名、雅安服务器托管、营销软件、网站建设、丹江口网站维护、网站推广。
a(i,j)表示运费。
建立如下模型：
3 3
min z= ∑ ∑a(i,j)*x(i,j);
i=1 j=1
s.t:
x(1,1)+x(1,2)+x(1,3)=20;
x(2,1)+x(2,2)+x(2,3)=16;
x(3,1)+x(3,2)+x(3,3)=4;
x(1,1)+x(2,1)+x(3,1)=10;
x(1,2)+x(2,2)+x(3,2)=14;
x(1,3)+x(2,3)+x(3,3)=16;
x(i,j)都为整数且大于零
用lingo求解的话代码如下：
sets:
row/1 2 3/:b;
col/1 2 3/:c;
link(row,col):a,x;
endsets
data:
a=6 5 13
10 7 16
8 2 4;
b=20 16 4;
c=10 14 16;
enddata
[OBJ]min=@sum(link(i,j):a(i,j)*x(i,j));
@for(row(i):@sum(col(j):x(i,j))=b(i));
@for(col(j):@sum(row(i):x(i,j))=c(j));
@for(link(i,j):x(i,j)=0;@gin(x(i,j)););
end
得出数据如下：
Variable Value Reduced Cost
X( 1, 1) 10.00000 6.000000
X( 1, 2) 0.000000 5.000000
X( 1, 3) 10.00000 13.00000
X( 2, 1) 0.000000 10.00000
X( 2, 2) 14.00000 7.000000
X( 2, 3) 2.000000 16.00000
X( 3, 1) 0.000000 8.000000
X( 3, 2) 0.000000 2.000000
X( 3, 3) 4.000000 4.000000
Row Slack or Surplus Dual Price
OBJ 336.0000 -1.000000
有数据可知与图2中答案吻合。
public class AssignWorkProblem {
public static void main(String[] args) {
/*
*测试
**/
int[][] cost=new int[][]{{2,15,13,4},{10,4,14,15},{9,14,16,13},{7,8,11,9}};
System.out.println(Arrays.toString(awpProcedure(cost, 4, 4)));
cost=new int[][]{{12,7,9,7,9},{8,9,6,6,6},{7,17,12,14,12},{15,14,6,6,10},{4,10,7,10,6}};
System.out.println(Arrays.toString(awpProcedure(cost, 5, 5)));
}
/*
* 费用矩阵costMatrix,由于要改变costMatrix的值，clone方法只能对基本类型;
* pnum即为几个人，也是costMatrix的行数，wnum是几个任务，也是costMatrix的列数
* 返回值：没两个数字为一组，表示i,j。如返回[1,1,2,0]表示costMatrix[1][1]、costMatrix[2][0]费用最低
*/
public static int[] awpProcedure(int[][] costMatrix,int pnum,int wnum){
if(pnum1||pnumwnum)
return null; //test n=m
int[][] costC=new int[pnum][]; //clone 一份costMatrix
for(int i=0;ipnum;i++){
costC[i]=costMatrix[i].clone();
}
//每行减去最小的元素
int[] lzeroa=new int[pnum+1]; //记录每行0的个数,lzero[pnum]记录0最少的行标
lzeroa[pnum]=-1;
int i,j;
for(i=0;ipnum;i++){
int lmin=costC[i][0]; //记录每行最小的
for(j=1;jwnum;j++)
lmin=lmincostC[i][j]?costC[i][j]:lmin;
for(j=0;jwnum;j++){
costC[i][j]-=lmin;
lzeroa[i]+=costC[i][j]==0?1:0;
}
}
for(j=0;jwnum;j++){
int cmin=costC[0][j]; //记录每列最小的
for(i=1;ipnum;i++)
cmin=cmincostC[i][j]?costC[i][j]:cmin;
if(cmin==0)continue;
for(i=0;ipnum;i++){
costC[i][j]-=cmin;
lzeroa[i]+=costC[i][j]==0?1:0;
}
}
int[] rzerop;
int whilenum=0;
while(true){
boolean[] lzerob=new boolean[pnum]; //记录某行是否查找过
rzerop=new int[pnum*2]; //记录0元素所在的行列
Arrays.fill(rzerop, -1);
if(awpIsSolution(costC,pnum,wnum,lzeroa.clone(),lzerob,rzerop))
break;
//下面调整矩阵
int[] coverLC=new int[pnum+wnum]; //要被标记的行列，0-pnum-1为行，pnum以后为列
Arrays.fill(coverLC, -1);
//没有找到合适0元素的行做标记
for(i=0;ipnum;i++)
if(lzerob[i]==false)coverLC[i]=i;
//对已经标记的行上的0元素所在的列做标记
for(i=0;ipnum;i++)
if(coverLC[i]!=-1){
for(j=0;jwnum;j++){
if(costC[coverLC[i]][j]==0)
coverLC[pnum+j]=j;
}
}
//对已经标记的列上的已经选中的0元素所在的行做标记
for(j=0;jwnum;j++){
if(coverLC[pnum+j]!=-1){
for(i=0;irzerop.lengthrzerop[i]!=-1;i+=2){
if(rzerop[i+1]==j)
coverLC[rzerop[i]]=rzerop[i];
}
}
}
//确定能找出新最小值的区域，直线覆盖掉没有打勾的行，打勾的列,最终coverLC[x]!=-1就是能选择的数
for(i=0;iwnum;i++){
if(coverLC[pnum+i]!=-1)coverLC[pnum+i]=-1;
else coverLC[pnum+i]=i;
}
//从区域中找出最小元素
int nmin=-1;
for(i=0;ipnum;i++){
if(coverLC[i]==-1)continue;
for(j=0;jwnum;j++){
if(coverLC[pnum+j]==-1)continue;
if(nmin==-1)nmin=costC[i][j];
else nmin=nmincostC[i][j]?costC[i][j]:nmin;
}
}
//打勾的列加上nmin,打勾的行减去nmin,记录0个数的数组作相应变化
for(j=0;jwnum;j++){
if(coverLC[pnum+j]==-1){
for(i=0;ipnum;i++){
if(costC[i][j]==0)lzeroa[i]-=1;
costC[i][j]+=nmin;
}
}
}
for(i=0;ipnum;i++){
if(coverLC[i]!=-1){
for(j=0;jwnum;j++){
costC[i][j]-=nmin;
if(costC[i][j]==0)lzeroa[i]+=1;
}
}
}
whilenum++;
if(whilenum==100){
System.out.println("100次之内矩阵调整没有找到");
return null;
}
}
return rzerop;
}
/*
* 测试矩阵costC是否有解，已经通过变换或者调整得到的矩阵
*/
public static boolean awpIsSolution(int[][] costC,int pnum,int wnum,int[] lzeroa,boolean[] lzerob,int[] rzerop){
int i,j,rzeropi=0;
for(int p=0;ppnum;p++){ //开始按照匈牙利法划去0所在的行列
//查找0元素个数最少的行
for(i=0;ipnum;i++){
if(lzerob[i]||lzeroa[i]1)continue; //如果某行已经查找过或者没有0元素，可能被划去了
if(lzeroa[pnum]!=-1lzeroa[i]lzeroa[lzeroa[pnum]])lzeroa[pnum]=i;
else if(lzeroa[pnum]==-1) lzeroa[pnum]=i;
}
//没有找到足够的不在同一行同一列的0元素，需要对矩阵进行调整，如果lzeroa[pnum]有值，则说明该行一定能找到
if(lzeroa[pnum]==-1){
return false;
}
//划去找到的行中没有被覆盖的0元素所在的行列
for(j=0;jwnum;j++){
if(costC[lzeroa[pnum]][j]!=0)continue;
//第一次找0元素最少的行
if(rzeropi==0){
rzerop[rzeropi++]=lzeroa[pnum];
rzerop[rzeropi++]=j;
lzerob[lzeroa[pnum]]=true; //找到第lzeroa[pnum]行，第j列0元素
//划去所在的行列时 lzeroa做相应的变化
for(i=0;ipnum;i++){
if(i!=lzeroa[pnum]costC[i][j]==0)
lzeroa[i]-=1;
}
lzeroa[pnum]=-1;
break;
}
//找到的0元素是否被划去
for(i=0;irzeropi(lzeroa[pnum]!=rzerop[i]j!=rzerop[i+1]);i+=2);
//如果被划去则找该行下一个0元素
if(irzeropi)continue;
rzerop[rzeropi++]=lzeroa[pnum];
rzerop[rzeropi++]=j;
lzerob[lzeroa[pnum]]=true;
for(i=0;ipnum;i++){
if(i!=lzeroa[pnum]costC[i][j]==0)
lzeroa[i]-=1;
}
lzeroa[pnum]=-1;
break;
}
}
return true;
}
}
你好！
这道题是清华大学06年的真题，答案在我空间里。用的是动态规划的方法。有不懂可以追问哦
max=0.5*X1+0.4*X2;
0.1*X1+0.1*X2=80;
0.075*X1+0.05*X2=30;
0.075*X1+0.1*X2=45;
#includestdio.h
#includemath.h
#includeiostream.h
float matrix[100][100],x[100]; /* 记录总方程的数组,解的数组 */
int a[100]; /* 记录基础,非基础的解的情况,0:非基础,1:基础 */
int m,n,s,type; /* 方程变量,约束数,求最大最小值的类型,0:最小 1:最大 */
int indexe,indexl,indexg; /* 剩余变量,松弛变量,人工变量 */
void Jckxj()
{
int i,j;
for(i=0;in;i++)
for(j=0;js;j++)
if(matrix[i][j]==1a[j]==1){
x[j]=matrix[i][s];
j=s;
}
for(i=0;is;i++)
if(a[i]==0) x[i]=0;
}
int Rj()
{
int i;
for(i=0;is;i++)
if(fabs(matrix[n][i])=0.000001)
if(matrix[n][i]0) return 0;
return 1;
}
int Min()
{
int i,temp=0;
float min=matrix[n][0];
for(i=1;is;i++)
if(minmatrix[n][i]){
min=matrix[n][i];
temp=i;
}
return temp;
}
void JustArtificial()
{
int i;
for(i=m+indexe+indexl;is;i++)
if(fabs(x[i])=0.000001){
printf("No Answer\n");
return;
}
}
int Check(int in)
{
int i;
float max1=-1;
for(i=0;in;i++)
if(fabs(matrix[i][in])=0.000001max1matrix[i][s]/matrix[i][in])
max1=matrix[i][s]/matrix[i][in];
if(max10)
return 1;
return 0;
}
int SearchOut(int *temp,int in)
{
int i;
float min=10000;
for(i=0;in;i++)
if(fabs(matrix[i][in])=0.000001(matrix[i][s]/matrix[i][in]=0)minmatrix[i][s]/matrix[i][in]){
min=matrix[i][s]/matrix[i][in];
*temp=i;
}
for(i=0;is;i++)
if(a[i]==1matrix[*temp][i]==1) return i;
}
void Mto(int in,int temp)
{
int i;
for(i=0;i=s;i++)
if(i!=in)
matrix[temp][i]=matrix[temp][i]/matrix[temp][in];
matrix[temp][in]=1;
}
void Be(int temp,int in)
{
int i,j;
float c;
for(i=0;i=n;i++){
c=matrix[i][in]/matrix[temp][in];
if(i!=temp)
for(j=0;j=s;j++)
matrix[i][j]=matrix[i][j]-matrix[temp][j]*c;
}
}
void Achange(int in,int out)
{
int temp=a[in];
a[in]=a[out];
a[out]=temp;
}
void Print()
{
int i,j,k,temp=0;
for(i=0;in;i++){
for(k=temp;ks;k++)
if(a[k]==1){
printf("X%d ",k);
temp=k+1;
k=s;
}
for(j=0;j=s;j++)
printf("%8.2f",matrix[i][j]);
printf("\n");
}
