public class AssignWorkProblem {
創(chuàng)新互聯(lián)是一家專注于做網(wǎng)站、成都網(wǎng)站制作與策劃設(shè)計,翁源網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)十余年,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:翁源等地區(qū)。翁源做網(wǎng)站價格咨詢:13518219792
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的行數(shù)，wnum是幾個任務(wù)，也是costMatrix的列數(shù)
* 返回值：沒兩個數(shù)字為一組，表示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的個數(shù),lzero[pnum]記錄0最少的行標(biāo)
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;
//下面調(diào)整矩陣
int[] coverLC=new int[pnum+wnum]; //要被標(biāo)記的行列，0-pnum-1為行，pnum以后為列
Arrays.fill(coverLC, -1);
//沒有找到合適0元素的行做標(biāo)記
for(i=0;ipnum;i++)
if(lzerob[i]==false)coverLC[i]=i;
//對已經(jīng)標(biāo)記的行上的0元素所在的列做標(biāo)記
for(i=0;ipnum;i++)
if(coverLC[i]!=-1){
for(j=0;jwnum;j++){
if(costC[coverLC[i]][j]==0)
coverLC[pnum+j]=j;
}
}
//對已經(jīng)標(biāo)記的列上的已經(jīng)選中的0元素所在的行做標(biāo)記
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];
}
}
}
//確定能找出新最小值的區(qū)域，直線覆蓋掉沒有打勾的行，打勾的列,最終coverLC[x]!=-1就是能選擇的數(shù)
for(i=0;iwnum;i++){
if(coverLC[pnum+i]!=-1)coverLC[pnum+i]=-1;
else coverLC[pnum+i]=i;
}
//從區(qū)域中找出最小元素
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個數(shù)的數(shù)組作相應(yīng)變化
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次之內(nèi)矩陣調(diào)整沒有找到");
return null;
}
}
return rzerop;
}
/*
* 測試矩陣costC是否有解，已經(jīng)通過變換或者調(diào)整得到的矩陣
*/
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元素個數(shù)最少的行
for(i=0;ipnum;i++){
if(lzerob[i]||lzeroa[i]1)continue; //如果某行已經(jīng)查找過或者沒有0元素，可能被劃去了
if(lzeroa[pnum]!=-1lzeroa[i]lzeroa[lzeroa[pnum]])lzeroa[pnum]=i;
else if(lzeroa[pnum]==-1) lzeroa[pnum]=i;
}
//沒有找到足夠的不在同一行同一列的0元素，需要對矩陣進行調(diào)整，如果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做相應(yīng)的變化
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;
}
}
運籌學(xué)|運籌學(xué)真題解析|清華大學(xué)運籌學(xué) ?
鏈接: ?
?pwd=a3dh 提取碼: a3dh
運籌學(xué)|運籌學(xué)真題解析|清華大學(xué)運籌學(xué)百度網(wǎng)盤?
全國2009年4月高等教育自學(xué)考試
運籌學(xué)基礎(chǔ)試題
課程代碼：02375
一、單項選擇題(本大題共15小題，每小題1分，共15分)
在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。
1．單純形法作為一種常用解法，適合于求解線性規(guī)劃( )
A．多變量模型 B.兩變量模型
C.最大化模型 D.最小化模型
2．對科學(xué)發(fā)展趨勢的預(yù)測屬于( )
A．微觀經(jīng)濟預(yù)測 B.宏觀經(jīng)濟預(yù)測
C.科技預(yù)測 D.社會預(yù)測
3．一般而論，1年內(nèi)的經(jīng)濟預(yù)測屬于( )
A．長期預(yù)測 B.中期預(yù)測
C.短期預(yù)測 D.定性預(yù)測
4．所謂確定條件下的決策，決策者( )
A．不知道將要面對哪些自然狀況
B.知道所面對的部分自然狀況
C.面對的只有一種自然狀況，即關(guān)于未來的狀態(tài)是完全確定的
D.所面對的是，存在一個以上的自然狀況，而決策者不了解其它狀態(tài)，甚至不完全了解如何把概率（可能性）分配給自然狀態(tài)
5．可用于風(fēng)險條件下決策類型的是( )
A．最大最大決策標(biāo)準(zhǔn) B.最大期望收益值標(biāo)準(zhǔn)
C.最大最小決策標(biāo)準(zhǔn) D.最小最大遺憾值決策標(biāo)準(zhǔn)
6．在庫存管理中，“訂貨提前期”，亦可稱為( )
A．再訂貨點 B.前置時間
C.前置時間內(nèi)的需求量 D.經(jīng)濟訂貨量
7．線性規(guī)劃的圖解法適用于( )
A．只含有一個變量的線性規(guī)劃問題 B.只含有2～3個變量的線性規(guī)劃問題
C.含有多個變量的線性規(guī)劃問題 D.任何情況
8．單純形法求解時，若求得的基礎(chǔ)解滿足非負(fù)要求，則該基礎(chǔ)解為( )
A．可行解 B.最優(yōu)解
C.特解 D.可行基解
9．在線性規(guī)劃中，設(shè)約束方程的個數(shù)為m,變量個數(shù)為n，m＜n時，可以把變量分為基變量和非基變量兩部分，基變量的個數(shù)為m個，非基變量的個數(shù)為( )
A．m個 B.n個
C.n-m個 D.0個
10．網(wǎng)絡(luò)計劃技術(shù)是解決哪類管理問題的科學(xué)方法？( )
A．組織生產(chǎn)和進行計劃管理 B.環(huán)境條件不確定問題
C.具有對抗性局勢競爭問題 D.訂貨與庫存問題
11.在網(wǎng)絡(luò)計劃技術(shù)中，以結(jié)點代表活動，以箭線表示活動之間的先后承接關(guān)系，這種圖稱之為( )
A．箭線式網(wǎng)絡(luò)圖 B.結(jié)點式網(wǎng)絡(luò)圖
C.最短路線圖 D.最大流量圖
12.網(wǎng)絡(luò)圖中，完成一項活動可能最短的時間，稱為( )
A．作業(yè)時間 B.最樂觀時間
C.最保守時間 D.最可能時間
13.在一個網(wǎng)絡(luò)中，如果從一個起點出發(fā)到所有的點，找出一條或幾條路線，以使在這樣一些路線中所采用的全部支線的總長度最小，這種方法稱之為( )
A．點的問題 B.線的問題
C.樹的問題 D.最小枝叉樹問題
14．任意一個方陣，如果其各行都是概率向量，則該方陣稱之為( )
A．固定概率矩陣 B.馬爾柯夫向量
C.概率向量 D.概率矩陣
15．反映模擬的不足之處的表述是( )
A．模擬是不精確的，它既不是一個最優(yōu)化過程，也不能得到一個答案
B.實際觀察一個系統(tǒng)可能費用過于昂貴
C.不可能有足夠的時間來實際廣泛地操作該系統(tǒng)
D.由于難于觀察到實際環(huán)境，模擬可能是惟一可以利用的方法
二、填空題(本大題共10小題，每小題1分，共10分)
請在每小題的空格中填上正確答案。錯填、不填均無分。
16．運籌學(xué)是一門研究如何有效地組織和管理________的科學(xué)。
17．預(yù)測就是對未來的不確定的事件進行________或判斷。
18．決策就是針對具有明確目標(biāo)的決策問題，經(jīng)過調(diào)查研究，根據(jù)實際與可能，擬定多個________，然后運用統(tǒng)一的標(biāo)準(zhǔn)，選定最佳（或滿意）方案的全過程。
19．庫存的作用最基本的一個方面，就是保證工業(yè)企業(yè)的生產(chǎn)能夠正常地、________、均衡地進行。
20．線性規(guī)劃是一種合理利用資源、合理調(diào)配資源的應(yīng)用數(shù)學(xué)方法，其基本特點是模型中的目標(biāo)函數(shù)和約束方程都是________。
21．運輸問題是線性規(guī)劃問題中一類具有特殊性質(zhì)的問題，它通過選擇________的運輸方案，以達(dá)到總的運輸費用最低或獲得的利潤最大等目標(biāo)。
22．最小枝杈樹算法是按把最近的未接點連接到那些________上去的辦法來進行的。
23．馬爾柯夫研究發(fā)現(xiàn)：許多事物未來的發(fā)展或演變，往往受該事物________所支配或影響。
24．盈虧平衡分析是一種管理決策工具，它用來說明在________水平上總銷量與總成本因素之間的關(guān)系。
25．模擬又稱________，它的基本思想是構(gòu)造一個試驗的模型，通過對這個模型的運行，獲得要研究的系統(tǒng)的必要信息和結(jié)果。
三、名詞解釋題(本大題共5小題，每小題3分，共15分)
26．定性預(yù)測
27．后悔值
28．線性規(guī)劃的目標(biāo)函數(shù)
29．階石法中的改進指數(shù)
30．活動的極限費用
四、計算題Ⅰ (本大題共3小題，每小題5分，共15分)
寫出下列每小題的計算過程，否則只給結(jié)果分。
31．某木材公司銷售房架構(gòu)件，其中一種構(gòu)件的銷售數(shù)據(jù)如題31表。試計算：3個月的滑動平均預(yù)測值（直接填在表中相應(yīng)空欄）。
題31表 某木材公司房架構(gòu)件的銷售數(shù)據(jù)
月份 實際銷售額（萬元） 3個月滑動平均預(yù)測值
1 10
2 12
3 13
4 16
5 19
6 23
32．某唱片公司計劃錄制一位新歌星的唱片。擬定的價格有A1、A2、A3三個方案，預(yù)計唱片進入市場后可能的銷售狀況（自然狀態(tài)）也有三種，收益值如題32表。試以最大最大決策標(biāo)準(zhǔn)作出唱片價格的決策選擇。
題32表 某唱片公司錄制新唱片的收益值表 （單位：元）
33．某公司平均每周需求某配件3900臺套，每臺套存貯一年費用為6元，每次訂貨費25元，試求該公司年度最優(yōu)經(jīng)濟訂貨批量和全年最佳訂貨次數(shù)。
五、計算題 Ⅱ(本大題共3小題，每小題5分，共15分)
寫出下列每小題的計算過程，否則只給結(jié)果分。
34．若某工序A由i、j兩結(jié)點順序相聯(lián)，i結(jié)點的最早時間為60（小時），j結(jié)點的最遲時間為120（小時），工序A本身需要40小時才能完成。試畫出該工序的箭線式網(wǎng)絡(luò)圖，并在圖上填寫出i結(jié)點的最遲時間、j結(jié)點的最早時間，以及工序A的最早開始和最遲開始時間。
35．某公司擬對新產(chǎn)品生產(chǎn)批量作出決策，現(xiàn)有三種備選方案，未來市場對該產(chǎn)品的需求有兩種可能的自然狀態(tài)N1、N2，收益矩陣如題35表。試畫出該問題的決策樹，并以決策樹法作出最優(yōu)生產(chǎn)決策。
題35表 某公司新產(chǎn)品生產(chǎn)收益矩陣表 （單位：萬元）
36．某公司對過去一年中某種配件的交貨時間統(tǒng)計如題36表，試在表中填寫出累計概率分布和隨機數(shù)分布。
題36表 公司交貨時間（周）的累計概率分布及隨機數(shù)分布表
交貨時間（周） 頻率（%） 累計概率分布（%） 隨機數(shù)分布
1 23
2 45
3 17
4 9
5 6
六、計算題 Ⅲ(本大題共2小題，每小題7分，共14分)
寫出下列每小題的計算過程，否則只給結(jié)果分。
37．某企業(yè)計劃期內(nèi)要安排生產(chǎn)甲、乙兩種產(chǎn)品，有關(guān)資源消耗及可獲利潤如題37表。該廠要獲得利潤最大化，應(yīng)如何安排二種產(chǎn)品的生產(chǎn)？建立該問題的線性規(guī)劃數(shù)學(xué)模型并用圖解法求出最優(yōu)解。
題37表 某企業(yè)產(chǎn)品生產(chǎn)的資源消耗與可獲利潤表
產(chǎn)品 甲 乙 資源限量
設(shè)備臺時 1臺時/件 1臺時/件 300臺時
原料A 2千克/件 1千克/件 400千克
原料B 0 1千克/件 250千克
預(yù)計獲利（元/件） 50 100
38．將題37的線性規(guī)劃問題轉(zhuǎn)換為標(biāo)準(zhǔn)形式，以原點為基礎(chǔ)求出基礎(chǔ)可行解，并建立初始單純形表。
七、計算題Ⅳ(本大題共2小題，每小題8分，共16分)
寫出下列每小題的計算過程，否則只給結(jié)果分。
39．某工程有7道工序，工序銜接與有關(guān)時間數(shù)據(jù)如題39表，試?yán)L制網(wǎng)絡(luò)圖。
題39表 某工程施工工序資料表
工序名稱 A B C D E F G
緊前工序 - - AB AB B C DE
工序時間 2 4 5 4 3 2 4
40．在你為題39所繪制的網(wǎng)絡(luò)圖上標(biāo)出各結(jié)點的時間參數(shù)，確定關(guān)鍵路線并用雙線（或粗黑線）表示。指明總工期以及A、B、C、D四項活動的最早開始時間。
線性規(guī)劃出現(xiàn)的下面語句，options=optimoptions('linprog','algorithm','simplex')是什么意思？
首先，我們對這個語句中的各內(nèi)容進行說明：
optimoptions——是優(yōu)化選項函數(shù)，對于不同的優(yōu)化函數(shù)，其控制內(nèi)容是略有區(qū)別的
linprog——線性規(guī)劃求解函數(shù)名；
algorithm——選擇優(yōu)化算法；系統(tǒng)默認(rèn)'dual-simplex'（對偶單純形法算法），'interior-point-legacy'（內(nèi)點傳統(tǒng)算法），它是基于Mehrotra 預(yù)測-校正算法 的變體。'interior-point'（內(nèi)點算法）
simplex——選擇單純形法
所以，這個options優(yōu)化選項的意思是采用對偶單純形法算法進行線性規(guī)劃最優(yōu)化計算。
根據(jù)開始時間分類就行了
model:
sets:
time/1..11/:d;
temp/1..8/:n1;
full/1..3/:n2;
endsets
data:
d=9 9 9 3 3 3 6 12 12 7 7;
enddata
min=@sum(temp:n1);
@sum(full:n2)=4;
@for(temp:@gin(n1));
@for(full:@gin(n2));
@for(time(i):@sum(temp(j)|j#gt#(i-4) #and# j#le#i:n1(j))+@sum(full(k)|k#gt#(i-9) #and# k#ne#(i-4) #and# k#le#i:n2(k))=d(i));
end
重慶分公司
重慶分公司
