public class AssignWorkProblem {
public static void main(String[] args) {
/*
*测试
**/
}
* 费用矩阵costMatrix,由于要改变costMatrix的值,clone方法只能对基本类型;
* pnum即为几个人,也是costMatrix的行数,wnum是几个任务,也是costMatrix的列数
*/
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;
int cmin=costC[0][j];//记录每列最小的
for(i=1;ipnum;i++)
cmin=cmincostC[i][j]?costC[i][j]:cmin;
if(cmin==0)continue;
costC[i][j]-=cmin;
int[] rzerop;
int whilenum=0;
while(true){
boolean[] lzerob=new boolean[pnum];//记录某行是否查找过
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元素所在的列做标记
if(coverLC[i]!=-1){
if(costC[coverLC[i]][j]==0)
coverLC[pnum+j]=j;
//对已经标记的列上的已经选中的0元素所在的行做标记
if(coverLC[pnum+j]!=-1){
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;
if(coverLC[i]==-1)continue;
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个数的数组作相应变化
if(coverLC[pnum+j]==-1){
if(costC[i][j]==0)lzeroa[i]-=1;
costC[i][j]+=nmin;
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元素个数最少的行
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元素所在的行列
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做相应的变化
if(i!=lzeroa[pnum]costC[i][j]==0)
lzeroa[i]-=1;
//找到的0元素是否被划去
//如果被划去则找该行下一个0元素
if(irzeropi)continue;
lzerob[lzeroa[pnum]]=true;
return true;
运筹学|运筹学真题解析|清华大学运筹学 ?
链接: ?
运筹学|运筹学真题解析|清华大学运筹学百度网盘?
运筹学基础试题
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内.错选、多选或未选均无分.
①.．单纯形法作为一种常用解法,适合于求解线性规划( )
A．多变量模型B.两变量模型
C.最大化模型D.最小化模型
A．微观经济预测B.宏观经济预测
C.科技预测D.社会预测
A．长期预测B.中期预测
C.短期预测D.定性预测
A．不知道将要面对哪些自然状况
B.知道所面对的部分自然状况
C.面对的只有一种自然状况,即关于未来的状态是完全确定的
D.所面对的是,存在一个以上的自然状况,而决策者不了解其它状态,甚至不完全了解如何把概率（可能性）分配给自然状态
A．最大最大决策标准B.最大期望收益值标准
C.最大最小决策标准D.最小最大遗憾值决策标准
A．再订货点B.前置时间
C.前置时间内的需求量D.经济订货量
C.含有多个变量的线性规划问题D.任何情况
A．可行解B.最优解
C.特解D.可行基解
A．m个B.n个
C.n-m个D.0个
①.0．网络计划技术是解决哪类管理问题的科学方法?( )
A．组织生产和进行计划管理B.环境条件不确定问题
C.具有对抗性局势竞争问题D.订货与库存问题
①.1.在网络计划技术中,以结点代表活动,以箭线表示活动之间的先后承接关系,这种图称之为( )
A．箭线式网络图B.结点式网络图
C.最短路线图D.最大流量图
A．作业时间B.最乐观时间
C.最保守时间D.最可能时间
A．点的问题B.线的问题
C.树的问题D.最小枝叉树问题
A．固定概率矩阵B.马尔柯夫向量
C.概率向量D.概率矩阵
A．模拟是不精确的,它既不是一个最优化过程,也不能得到一个答案
B.实际观察一个系统可能费用过于昂贵
C.不可能有足够的时间来实际广泛地操作该系统
D.由于难于观察到实际环境,模拟可能是惟一可以利用的方法
第二段：填空题(本大题共10小题,每小题1分,共10分)
请在每小题的空格中填上正确答案.错填、不填均无分.
写出下列每小题的计算过程,否则只给结果分.
①.10
交货时间（周）频率（%）累计概率分布（%）随机数分布
产品甲乙资源限量
工序名称ABCDEFG
紧前工序--ABABBCDE
线性规划出现的下面语句,options=optimoptions('linprog','algorithm','simplex')是什么意思?
首先,我们对这个语句中的各内容进行说明：
optimoptions——是优化选项函数,对于不同的优化函数,其控制内容是略有区别的
linprog——线性规划求解函数名；
algorithm——选择优化算法；系统默认'dual-simplex'（对偶单纯形法算法）,'interior-point-legacy'（内点传统算法）,它是基于Mehrotra 预测-校正算法 的变体.'interior-point'（内点算法）
simplex——选择单纯形法
所以,这个options优化选项的意思是采用对偶单纯形法算法进行线性规划最优化计算.
根据开始时间分类就行了
model:
sets:
time/1..11/:d;
endsets
data:
enddata
@for(temp:@gin(n1));
end