正文
运筹学问题java代码,运筹学问题类型及解决方法
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
运筹学 表上作业法求运输问题
定义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中答案吻合。
相关问答
Q1: 谁帮忙给个运筹学任务指派问题的JAVA算法阿！不需要C或者C++语言,也不要和我说看着C++就能改,我不会改!!!!!
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;
}
}
Q2: 运筹学的问题
你好！
这道题是清华大学06年的真题，答案在我空间里。用的是动态规划的方法。有不懂可以追问哦
Q3: 运筹学资源分配问题lingo代码
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;
Q4: 《运筹学》中的单纯形方法求线性规划问题用C语言怎么算？求代码，谢谢！
#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");
}
