利用開發(fā)高級(jí)模型選講

利用開發(fā)高級(jí)模型選講第1頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月一條裝配線含有一系列的工作站，在最終產(chǎn)品的加工過程中每個(gè)工作站執(zhí)行一種或幾種特定的任務(wù)。裝配線周期是指所有工作站完成分配給它們各自的任務(wù)所化費(fèi)時(shí)間中的最大值。平衡裝配線的目標(biāo)是為每個(gè)工作站分配加工任務(wù)，盡可能使每個(gè)工作站執(zhí)行相同數(shù)量的任務(wù)，其最終標(biāo)準(zhǔn)是裝配線周期最短。不適當(dāng)?shù)钠胶庋b配線將會(huì)產(chǎn)生瓶頸——有較少任務(wù)的工作站將被迫等待其前面分配了較多任務(wù)的工作站。問題會(huì)因?yàn)楸姸嗳蝿?wù)間存在優(yōu)先關(guān)系而變得更復(fù)雜，任務(wù)的分配必須服從這種優(yōu)先關(guān)系。這個(gè)模型的目標(biāo)是最小化裝配線周期。有2類約束：①要保證每件任務(wù)只能也必須分配至一個(gè)工作站來加工；②要保證滿足任務(wù)間的所有優(yōu)先關(guān)系。例有11件任務(wù)（A—K）分配到4個(gè)工作站（1—4），任務(wù)的優(yōu)先次序如下圖。每件任務(wù)所花費(fèi)的時(shí)間如下表。例7.2

裝配線平衡模型（I）（H）（G）（J）（K）（F）（B）（A）（C）（E）（D）第2頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月

MODEL:

!裝配線平衡模型;SETS:

!任務(wù)集合，有一個(gè)完成時(shí)間屬性T;TASK/ABCDEFGHIJK/:T;

!任務(wù)之間的優(yōu)先關(guān)系集合（A必須完成才能開始B，等等）;PRED(TASK,TASK)/A,BB,CC,FC,GF,JG,JJ,KD,EE,HE,IH,JI,J/;

!工作站集合;STATION/1..4/;TXS(TASK,STATION):X;

!X是派生集合TXS的一個(gè)屬性。如果X（I，K）＝1，則表示第I個(gè)任務(wù)指派給第K個(gè)工作站完成;ENDSETSDATA:

!任務(wù)ABCDEFGHIJK的完成時(shí)間估計(jì)如下;T=4511950151212121289;ENDDATA

!當(dāng)任務(wù)超過15個(gè)時(shí)，模型的求解將變得很慢;

!每一個(gè)作業(yè)必須指派到一個(gè)工作站，即滿足約束①;

@FOR(TASK(I):@SUM(STATION(K):X(I,K))=1);

!對(duì)于每一個(gè)存在優(yōu)先關(guān)系的作業(yè)對(duì)來說，前者對(duì)應(yīng)的工作站I必須小于后者對(duì)應(yīng)的工作站J，即滿足約束②;

@FOR(PRED(I,J):@SUM(STATION(K):K*X(J,K)-K*X(I,K))>=0);

!對(duì)于每一個(gè)工作站來說，其花費(fèi)時(shí)間必須不大于裝配線周期;

@FOR(STATION(K):

@SUM(TXS(I,K):T(I)*X(I,K))<=CYCTIME);

!目標(biāo)函數(shù)是最小化轉(zhuǎn)配線周期;

MIN=CYCTIME;

!指定X(I,J)為0/1變量;

@FOR(TXS:@BIN(X));END任務(wù)ABCDEFGHIJK時(shí)間4511950151212121289第3頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月有一個(gè)推銷員，從城市1出發(fā)，要遍訪城市2，3，…，n各一次，最后返回城市1。已知從城市i到j(luò)的旅費(fèi)為Cij，問他應(yīng)按怎樣的次序訪問這些城市，使得總旅費(fèi)最少？可以用多種方法把TSP表示成整數(shù)規(guī)劃模型。這里介紹的一種建立模型的方法，是把該問題的每個(gè)解（不一定是最優(yōu)的）看作是一次“巡回”。在下述意義下，引入一些0-1整數(shù)變量：例7.3旅行售貨員問題（又稱貨郎擔(dān)問題，TravelingSalesmanProblem）其目標(biāo)只是使為最小。第4頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月這里有兩個(gè)明顯的必須滿足的條件：訪問城市i后必須要有一個(gè)即將訪問的確切城市；訪問城市j前必須要有一個(gè)剛剛訪問過的確切城市。用下面的兩組約束分別實(shí)現(xiàn)上面的兩個(gè)條件。123456到此得到了一個(gè)模型，它是一個(gè)指派問題的整數(shù)規(guī)劃模型。但以上兩個(gè)條件對(duì)于TSP來說并不充分，僅僅是必要條件。例如：以上兩個(gè)條件都滿足，但它顯然不是TSP的解，它存在兩個(gè)子巡回。第5頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月這里，將敘述一種在原模型上附加充分的約束條件以避免產(chǎn)生子巡回的方法。把額外變量附加到問題中。可把這些變量看作是連續(xù)的（最然這些變量在最優(yōu)解中取普通的整數(shù)值）?，F(xiàn)在附加下面形式的約束條件為證明該約束條件有預(yù)期的效果，必須證明：（1）任何含子巡回的路線都不滿足該約束條件；（2）全部巡回都滿足該約束條件。首先證明（1），用反證法。假設(shè)還存在子巡回，也就是說至少有兩個(gè)子巡回。那么至少存在一個(gè)子巡回中不含城市1。把該子巡回記為，則必有第6頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月這k個(gè)式子相加，有：，矛盾！=訪問城市i的順序數(shù)，取值范圍為。因此，。下面來證明總巡回滿足該約束條件。，可取故假設(shè)不正確，結(jié)論（1）得證。下面證明（2），采用構(gòu)造法。對(duì)于任意的總巡回(ⅰ)總巡回上的邊第7頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月（ⅱ）非總巡回上的邊從而結(jié)論（2）得證。這樣我們把TSP轉(zhuǎn)化成了一個(gè)混合整數(shù)線性規(guī)劃問題。第8頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月第9頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月顯然，當(dāng)城市個(gè)數(shù)較大（大于30）時(shí)，該混合整數(shù)線性規(guī)劃問題的規(guī)模會(huì)很大，從而給求解帶來很大問題。TSP已被證明是NP難問題，目前還沒有發(fā)現(xiàn)多項(xiàng)式時(shí)間的算法。對(duì)小規(guī)模問題，求解這個(gè)混合整數(shù)線性規(guī)劃問題的方式還是有效的。TSP是一個(gè)重要的組合優(yōu)化問題，除了有直觀的應(yīng)用外，許多其它看似無聯(lián)系的優(yōu)化問題也可轉(zhuǎn)化為TSP。例如：?jiǎn)栴}1現(xiàn)需在一臺(tái)機(jī)器上加工n個(gè)零件（如燒瓷器），這些零件可按任意先后順序在機(jī)器上加工。我們希望加工完成所有零件的總時(shí)間盡可能少。由于加工工藝的要求，加工零件j時(shí)機(jī)器必須處于相應(yīng)狀態(tài)Sj（如爐溫）。設(shè)起始未加工任何零件時(shí)機(jī)器處于狀態(tài)S0，，且當(dāng)所有零件加工完成后需恢復(fù)到S0狀態(tài)。已知從狀態(tài)Si調(diào)整到狀態(tài)Sj(i≠j)需要時(shí)間Cij。零件j本身加工時(shí)間為pj。為方便起見，引入一個(gè)虛零件0，其加工時(shí)間為0，要求狀態(tài)為S0，，則{0，1，2，…，n}的一個(gè)圈置換π就表示對(duì)所有零件的一個(gè)加工順序，在此置換下，完成所有加工所需要的總時(shí)間為由于是一個(gè)常數(shù)，故該零件的加工順序問題變成TSP。第10頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月!旅行售貨員問題;model:sets:city/1..5/:u;link(city,city):dist,!距離矩陣;x;endsets

n=@size(city);data:!距離矩陣，它并不需要是對(duì)稱的;dist=@qrand(1);!隨機(jī)產(chǎn)生，這里可改為你要解決的問題的數(shù)據(jù);enddata

!目標(biāo)函數(shù);

min=@sum(link:dist*x);

@FOR(city(K):

!進(jìn)入城市K;

@sum(city(I)|I#ne#K:x(I,K))=1;

!離開城市K;

@sum(city(J)|J#ne#K:x(K,J))=1;);

!保證不出現(xiàn)子圈;

@for(city(I)|I#gt#1:

@for(city(J)|J#gt#1#and#I#ne#J:u(I)-u(J)+n*x(I,J)<=n-1););

!限制u的范圍以加速模型的求解，保證所加限制并不排除掉TSP問題的最優(yōu)解;

@for(city(I)|I#gt#1:u(I)<=n-2);

!定義X為0\1變量;

@for(link:@bin(x));end第11頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月給定N個(gè)點(diǎn)pi(i=1,2,…,N)組成集合{pi}。

cij表示任一點(diǎn)pi到另一點(diǎn)pj的距離，并作如下規(guī)定：若pi到pj沒有弧聯(lián)結(jié)，cij=+∞，cii=0(i=1,2,…,N)。現(xiàn)指定一個(gè)終點(diǎn)pN，求從pi點(diǎn)出發(fā)到pN的最短路線。用動(dòng)態(tài)規(guī)劃方法做：點(diǎn)pi表示狀態(tài)，決策集合是除pi以外點(diǎn)，選定一個(gè)點(diǎn)pj以后，得到cij并轉(zhuǎn)入新狀態(tài)效益pj

，當(dāng)狀態(tài)是pN時(shí)，過程停止。這是一個(gè)不定期多階段決策過程。定義f(i)：由點(diǎn)pi出發(fā)至終點(diǎn)pN最短路程，由最優(yōu)化原理得：函數(shù)方程，用LINGO可以方便的解決。例7.4最短路問題第12頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月!最短路問題;model:data:n=10;enddatasets:cities/1..n/:F;!10個(gè)城市;roads(cities,cities)/1,21,32,42,52,63,43,53,64,74,85,75,85,96,86,97,108,109,10/:D,P;endsetsdata:D=65369751191875410579;enddataF(n)=0;

@for(cities(i)|i#lt#n:F(i)=@min(roads(i,j):D(i,j)+F(j)););

!顯然，如果P(i,j)=1,則點(diǎn)i到點(diǎn)n的最短路徑的第一步是i-->j，否則就不是。

由此，我們就可方便的確定出最短路徑;

@for(roads(i,j):P(i,j)=@if(F(i)#eq#D(i,j)+F(j),1,0));end第13頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月例7.5露天礦生產(chǎn)的車輛安排（CMCM2003B）鋼鐵工業(yè)是國(guó)家工業(yè)的基礎(chǔ)之一，鐵礦是鋼鐵工業(yè)的主要原料基地。許多現(xiàn)代化鐵礦是露天開采的，它的生產(chǎn)主要是由電動(dòng)鏟車（以下簡(jiǎn)稱電鏟）裝車、電動(dòng)輪自卸卡車（以下簡(jiǎn)稱卡車）運(yùn)輸來完成。提高這些大型設(shè)備的利用率是增加露天礦經(jīng)濟(jì)效益的首要任務(wù)。露天礦里有若干個(gè)爆破生成的石料堆，每堆稱為一個(gè)鏟位，每個(gè)鏟位已預(yù)先根據(jù)鐵含量將石料分成礦石和巖石。一般來說，平均鐵含量不低于25%的為礦石，否則為巖石。每個(gè)鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個(gè)鏟位至多能安置一臺(tái)電鏟，電鏟的平均裝車時(shí)間為5分鐘。卸貨地點(diǎn)（以下簡(jiǎn)稱卸點(diǎn)）有卸礦石的礦石漏、2個(gè)鐵路倒裝場(chǎng)（以下簡(jiǎn)稱倒裝場(chǎng)）和卸巖石的巖石漏、巖場(chǎng)等，每個(gè)卸點(diǎn)都有各自的產(chǎn)量要求。從保護(hù)國(guó)家資源的角度及礦山的經(jīng)濟(jì)效益考慮，應(yīng)該盡量把礦石按礦石卸點(diǎn)需要的鐵含量（假設(shè)要求都為29.5%1%，稱為品位限制）搭配起來送到卸點(diǎn)，搭配的量在一個(gè)班次（8小時(shí)）內(nèi)滿足品位限制即可。從長(zhǎng)遠(yuǎn)看，卸點(diǎn)可以移動(dòng)，但一個(gè)班次內(nèi)不變?？ㄜ嚨钠骄盾嚂r(shí)間為3分鐘。所用卡車載重量為154噸，平均時(shí)速28?？ㄜ嚨暮挠土亢艽螅總€(gè)班次每臺(tái)車消耗近1噸柴油。發(fā)動(dòng)機(jī)點(diǎn)火時(shí)需要消耗相當(dāng)多的電瓶能量，故一個(gè)班次中只在開始工作時(shí)點(diǎn)火一次?？ㄜ囋诘却龝r(shí)所耗費(fèi)的能量也是相當(dāng)可觀的，原則上在安排時(shí)不應(yīng)發(fā)生卡車等待的情況。電鏟和卸點(diǎn)都不能同時(shí)為兩輛及兩輛以上卡車服務(wù)?？ㄜ嚸看味际菨M載運(yùn)輸。每個(gè)鏟位到每個(gè)卸點(diǎn)的道路都是專用的寬60??的雙向車道，不會(huì)出現(xiàn)堵車現(xiàn)象，每段道路的里程都是已知的。一個(gè)班次的生產(chǎn)計(jì)劃應(yīng)該包含以下內(nèi)容：出動(dòng)幾臺(tái)電鏟，分別在哪些鏟位上；出動(dòng)幾輛卡車，分別在哪些路線上各運(yùn)輸多少次（因?yàn)殡S機(jī)因素影響，裝卸時(shí)間與運(yùn)輸時(shí)間都不精確，所以排時(shí)計(jì)劃無效，只求出各條路線上的卡車數(shù)及安排即可）。一個(gè)合格的計(jì)劃要在卡車不等待條件下滿足產(chǎn)量和質(zhì)量（品位）要求，而一個(gè)好的計(jì)劃還應(yīng)該考慮下面兩條原則之一：1.總運(yùn)量（噸公里）最小，同時(shí)出動(dòng)最少的卡車，從而運(yùn)輸成本最小；2.利用現(xiàn)有車輛運(yùn)輸，獲得最大的產(chǎn)量（巖石產(chǎn)量?jī)?yōu)先；在產(chǎn)量相同的情況下，取總運(yùn)量最小的解）。請(qǐng)你就兩條原則分別建立數(shù)學(xué)模型，并給出一個(gè)班次生產(chǎn)計(jì)劃的快速算法。針對(duì)下面的實(shí)例，給出具體的生產(chǎn)計(jì)劃、相應(yīng)的總運(yùn)量及巖石和礦石產(chǎn)量。某露天礦有鏟位10個(gè)，卸點(diǎn)5個(gè)，現(xiàn)有鏟車7臺(tái)，卡車20輛。各卸點(diǎn)一個(gè)班次的產(chǎn)量要求：礦石漏1.2萬噸、倒裝場(chǎng)Ⅰ1.3萬噸、倒裝場(chǎng)Ⅱ1.3萬噸、巖石漏1.9萬噸、巖場(chǎng)1.3萬噸。鏟位和卸點(diǎn)位置二維示意圖如下，各鏟位和各卸點(diǎn)之間的距離（公里）如下表：第14頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月

鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏5.265.194.214.002.952.742.461.900.641.27倒裝場(chǎng)Ⅰ1.900.991.901.131.272.251.482.043.093.51巖場(chǎng)5.895.615.614.563.513.652.462.461.060.57巖石漏0.641.761.271.832.742.604.213.725.056.10倒裝場(chǎng)Ⅱ4.423.863.723.162.252.810.781.621.270.50各鏟位礦石、巖石數(shù)量(萬噸)和礦石的平均鐵含量如下表：

鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石量0.951.051.001.051.101.251.051.301.351.25巖石量1.251.101.351.051.151.351.051.151.351.25鐵含量30%28%29%32%31%33%32%31%33%31%各鏟位礦石、巖石數(shù)量(萬噸)和礦石的平均鐵含量如下表：第15頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月第16頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月model:titleCUMCM-2003B-01;sets:cai/1..10/:crate,cnum,cy,ck,flag;xie/1..5/:xsubject,xnum;link(xie,cai):distance,lsubject,number,che,b;endsetsdata:crate=30282932313332313331;xsubject=1.21.31.31.91.3;distance=5.265.194.214.002.952.742.461.900.641.271.900.991.901.131.272.251.482.043.093.515.895.615.614.563.513.652.462.461.060.570.641.761.271.832.742.604.213.725.056.104.423.863.723.162.252.810.781.621.270.50;cy=1.251.101.351.051.151.351.051.151.351.25;ck=0.951.051.001.051.101.251.051.301.351.25;enddata第17頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月!目標(biāo)函數(shù);min=@sum(cai(i):

@sum(xie(j):number(j,i)*154*distance(j,i)));!max=@sum(link(i,j):number(i,j));!max=xnum(3)+xnum(4)+xnum(1)+xnum(2)+xnum(5);!min=@sum(cai(i):!@sum(xie(j):!number(j,i)*154*distance(j,i)));!xnum(1)+xnum(2)+xnum(5)=340;!xnum(1)+xnum(2)+xnum(5)=341;!xnum(3)=160;!xnum(4)=160;!卡車每一條路線上最多可以運(yùn)行的次數(shù);第18頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月@for(link(i,j):b(i,j)=@floor((8*60-(@floor((distance(i,j)/28*60*2+3+5)/5)-1)*5)/(distance(i,j)/28*60*2+3+5)));!b(i,j)=@floor(8*60/(distance(i,j)/28*60*2+3+5)));!t(i,j)=@floor((distance(i,j)/28*60*2+3+5)/5);!b(i,j)=@floor((8*60-(@floor((distance(i,j)/28*60*2+3+5)/5))*5)/(distance(i,j)/28*60*2+3+5)));!每一條路線上的最大總車次的計(jì)算;@for(link(i,j):lsubject(i,j)=(@floor((distance(i,j)/28*60*2+3+5)/5))*b(i,j));!計(jì)算各個(gè)鏟位的總產(chǎn)量;@for(cai(j):cnum(j)=@sum(xie(i):number(i,j)));!計(jì)算各個(gè)卸點(diǎn)的總產(chǎn)量;@for(xie(i):xnum(i)=@sum(cai(j):number(i,j)));!道路能力約束;@for(link(i,j):number(i,j)<=lsubject(i,j));!電鏟能力約束;@for(cai(j):cnum(j)<=flag(j)*8*60/5);!電鏟數(shù)量約束

----addedbyXieJinxing,2003-09-07;@sum(cai(j):flag(j))<=7;第19頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月!卸點(diǎn)能力約束;@for(xie(i):xnum(i)<=8*20);!鏟位產(chǎn)量約束;@for(cai(i):number(1,i)+number(2,i)+number(5,i)<=ck(i)*10000/154);@for(cai(i):number(3,i)+number(4,i)<=cy(i)*10000/154);!產(chǎn)量任務(wù)約束;@for(xie(i):xnum(i)>=xsubject(i)*10000/154);!鐵含量約束;@sum(cai(j):number(1,j)*(crate(j)-30.5))<=0;@sum(cai(j):number(2,j)*(crate(j)-30.5))<=0;@sum(cai(j):number(5,j)*(crate(j)-30.5))<=0;@sum(cai(j):number(1,j)*(crate(j)-28.5))>=0;@sum(cai(j):number(2,j)*(crate(j)-28.5))>=0;@sum(cai(j):number(5,j)*(crate(j)-28.5))>=0;!關(guān)于車輛的具體分配;@for(link(i,j):che(i,j)=number(i,j)/b(i,j));!各個(gè)路線所需卡車數(shù)簡(jiǎn)單加和;hehe=@sum(link(i,j):che(i,j));!整數(shù)約束;@for(link(i,j):@gin(number(i,j)));@for(cai(j):@bin(flag(j)));!車輛能力約束;hehe<=20;ccnum=@sum(cai(j):cnum(j));end第20頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月求解最小生成樹的方法雖然很多，但是利用LINGO建立相應(yīng)的整數(shù)規(guī)劃模型是一種新的嘗試。這對(duì)于處理非標(biāo)準(zhǔn)的MST問題非常方便。我們主要參考了文[7]。在圖論中，稱無圈的連通圖為樹。在一個(gè)連通圖G中，稱包含圖G全部頂點(diǎn)的樹為圖G的生成樹。生成樹上各邊的權(quán)之和稱為該生成樹的權(quán)。連通圖G的權(quán)最小的生成樹稱為圖G的最小生成樹。許多實(shí)際問題都可以歸結(jié)為最小生成樹。如,如何修筑一些公路把若干個(gè)城鎮(zhèn)連接起來；如何架設(shè)通訊網(wǎng)絡(luò)將若干個(gè)地區(qū)連接起來；如何修筑水渠將水源和若干塊待灌溉的土地連接起來等等。為說明問題,以下面的問題作為范例。范例：假設(shè)某電話公司計(jì)劃在六個(gè)村莊架設(shè)電話線，各村莊之間的距離如圖所示。試求出使電話線總長(zhǎng)度最小的架線方案。為了便于計(jì)算機(jī)求解，特作如下規(guī)定：（1）節(jié)點(diǎn)V1表示樹根；（2）兩個(gè)節(jié)點(diǎn)之間沒有線路時(shí)，規(guī)定兩節(jié)點(diǎn)之間距離為M（較大的值）

MST的整數(shù)規(guī)劃模型如下：例7.6最小生成樹（MinimalSpanningTree，MST）問題V1V2V3V4V5V61122233345第21頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月這是個(gè)給n個(gè)人分配n項(xiàng)工作以獲得某個(gè)最高總效果的問題。第i個(gè)人完成第j項(xiàng)工作需要平均時(shí)間cij。要求給每個(gè)人分配一項(xiàng)工作，并要求分配完這些工作，以使完成全部任務(wù)的總時(shí)間為最小。該問題可表示如下：例7.7分配問題（指派問題，AssignmentProblem）第22頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月顯然，此問題可看作是運(yùn)輸問題的特殊情況?？蓪⒋藛栴}看作具有n個(gè)源和n個(gè)匯的問題，每個(gè)源有1單位的可獲量，而每個(gè)匯有1單位的需要量。從表面看，這問題要求用整數(shù)規(guī)劃以保證xij能取0或1。然而，幸運(yùn)的是，此問題是運(yùn)輸問題的特例，因此即使不限制xij取0或1，最優(yōu)解也將取0或1。如果把婚姻看作分配問題，丹茨證明，整數(shù)性質(zhì)證明一夫一妻會(huì)帶來最美滿幸福的生活！顯然，分配問題可以作為線性規(guī)劃問題來求解，盡管模型可能很大。例如，給100人分配100項(xiàng)工作將使所得的模型具有10000個(gè)變量。這時(shí)，如采用專門算法效果會(huì)更好。時(shí)間復(fù)雜度為O(n2)的匈牙利算法便是好選擇，這是由Kuhu（1955）提出的。第23頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月model:

!7個(gè)工人，7個(gè)工作的分配問題;sets:workers/w1..w7/;jobs/j1..j7/;links(workers,jobs):cost,volume;endsets

!目標(biāo)函數(shù);

min=@sum(links:cost*volume);

!每個(gè)工人只能有一份工作;

@for(workers(I):

@sum(jobs(J):volume(I,J))=1;);

!每份工作只能有一個(gè)工人;

@for(jobs(J):

@sum(workers(I):volume(I,J))=1;);data:cost=6267425495385852197437673927239572655228114923124510;enddataend第24頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月1.背景

排課問題是將n個(gè)班級(jí)快速、合理地安排在n個(gè)教室里上課。在現(xiàn)實(shí)生活中，這是一個(gè)普遍存在的問題。表面上看，這個(gè)問題似乎很簡(jiǎn)單，其實(shí)也不盡然。教室有大有小，班級(jí)也有大有小。當(dāng)班級(jí)總數(shù)和教室總數(shù)很大時(shí)，要想快速、合理、高效地排課也是很困難的。針對(duì)這一問題，提出了排課規(guī)則，定義了排課“費(fèi)用”，結(jié)合Excel，給出了排課問題的數(shù)學(xué)模型。利用它，可快速、合理、高效地完成排課任務(wù)。2.問題假設(shè)

5個(gè)班級(jí)安排到5個(gè)教室里上課，班級(jí)人數(shù)和教室容量如下。例7.8排課模型PKMX教室AlA2A3A4A5教室容量406O80120100班級(jí)BlB2B3B4B5班級(jí)人數(shù)30406080120試求出一個(gè)可行、合理、高效的排課方案。第25頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月3.排課規(guī)則及排課“費(fèi)用”三個(gè)規(guī)則：排課規(guī)則1：班級(jí)人數(shù)小于等于教室容量。排課規(guī)則2：如果教室總數(shù)大于班級(jí)總數(shù)，要盡可能空出大教室。排課規(guī)則3：離差(離差=教室容量一班級(jí)人數(shù))和相同情況下，選擇離差平方和最小的排課方案。滿足上面三個(gè)規(guī)則的排課方案就是可行、合理、高效的排課方案。為說明排課規(guī)則3，請(qǐng)看下面兩個(gè)排課方案：方案1：班級(jí)B1一教室A1，班級(jí)B2一教室A2方案2：班級(jí)Bl一教室A2，班級(jí)B2一教室A1兩個(gè)方案的離差和都是30。方案1使每個(gè)教室都留有一定空間，增加少量學(xué)生聽課不會(huì)有問題方案2中教室A1滿員，不能增加任何人。方案1比較合理。兩個(gè)方案的離差平方和分別是500和900。按照排課規(guī)則3，我們就會(huì)選擇方案1。第26頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月4.定義排課“費(fèi)用”：定義假設(shè)第i個(gè)班級(jí)人數(shù)為ai；第j個(gè)教室容量為bi(i,j=1,2,3,4,5)。Cij表示第i個(gè)班級(jí)指定到第i個(gè)教室上課的“費(fèi)用”。則注意：實(shí)際問題中，常常會(huì)出現(xiàn)班級(jí)總數(shù)小于教室總數(shù)情況。此時(shí)可虛設(shè)幾個(gè)班級(jí)，令其人數(shù)為零，使班級(jí)總數(shù)等于教室總數(shù)。根據(jù)以上規(guī)則和定義，原問題就成了求解“費(fèi)用”最小的指派問題。5.模型：排課模型PKMX第27頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月6.集合定義了兩個(gè)基本集合A、B。A表示教室，B表示班級(jí)。用A、B產(chǎn)生派生集合AB。7.變量在AB上定義了兩個(gè)屬性C、X。C存放排課“費(fèi)用”，X是決策變量。若x(i‘j)=1，則第i個(gè)班級(jí)指派到第j個(gè)教室上課；若x(i'j)=0，則第i個(gè)班級(jí)不指派到第j個(gè)教室上課。8.目標(biāo)求出“費(fèi)用”最小的排課方案，可用下式描述：

min=@sum(AB(i,j)：C(i,j)*X(i,j))9.約束：3種。第一種：@For(A(i)：@sum(B(j)：X(i,j))=1)它限制一個(gè)班級(jí)只能到一個(gè)教室上課。第二種：@for(B(j)：@sum(A(i)：X(i,j))=1)它限制一個(gè)教室只能安排一個(gè)班級(jí)上課。第三種：.@for(A(i)：@for(B(j)：@BIN(X(i,j))))它限制x只取0／1兩個(gè)值。第28頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月10.數(shù)據(jù)與解答數(shù)據(jù)來自文件排課數(shù)據(jù).xls，解答也輸出到此文件中。排課數(shù)據(jù).xls中定義了兩個(gè)域：“排課數(shù)據(jù)”域，范圍：Sheetl!$c$4：$G$8；“排課方案”域，范圍：Sheetl!$C$15：$G$19。“排課數(shù)據(jù)”域中每個(gè)單元的數(shù)據(jù)是按定義1計(jì)算的，具有相類似的計(jì)算格式。如：

C7=IF(AND(C2>=A7,A7>0)，(C2-A7)$(C2-A7)，100000)從“排課數(shù)據(jù)”域中輸入數(shù)據(jù)的語句：

C=@OLE(‘c：\rnydocuments＼排課數(shù)據(jù).xls’，‘排課數(shù)據(jù)’)解答輸出到“排課方案”域的語句：

@OLE('c\rnydocuments悄}課數(shù)據(jù).xls’，’排課方案’)：X第29頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月11.說明(1)模型中的教室總數(shù)是5，實(shí)際問題中往往教室總數(shù)要大得多。例如，假設(shè)教室總數(shù)是100。這時(shí)，只要5改成100即可。同時(shí)，文件排課數(shù)據(jù).XLS中的兩個(gè)域的范圍要做相應(yīng)變動(dòng)。(2當(dāng)教室總數(shù)和班級(jí)總數(shù)不相等時(shí)，可通過虛設(shè)教室(或班級(jí))實(shí)現(xiàn)相等。此時(shí)，虛設(shè)教室容量(或班級(jí)人數(shù))應(yīng)為0。例如，假設(shè)前面問題中的班級(jí)1不存在，可將其人數(shù)定為0，相應(yīng)的解答。由于班級(jí)l是虛設(shè)的，對(duì)應(yīng)的教室5空出，從表中可知它是可空出的最大教室。第30頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月GENPRT（Markowitz投資選擇模型）1.背景1952年3月在美國(guó)的《金融》雜志上，HarryM.Markowitz發(fā)表了題為“投資選擇”的文章。文章論證了如何通過選擇那些相關(guān)程度不大的投資來減少資產(chǎn)投資的風(fēng)險(xiǎn)。與此同時(shí)，為在風(fēng)險(xiǎn)和利潤(rùn)之間建立有利關(guān)系，還擬定了一個(gè)基本原則：投資多樣化。換句話說，就是不要將所有的“雞蛋”放在一個(gè)“籃子”里。理解模型的關(guān)鍵：統(tǒng)計(jì)量投資方差。數(shù)學(xué)上，投資方差：X：用于第i項(xiàng)投資的投資額，若i不等于j，則σij是第i項(xiàng)與第j項(xiàng)的協(xié)方差；如果i等于j，則σij是第i項(xiàng)投資的方差。方差：表示利潤(rùn)波動(dòng)的平均值。方差越大，投資風(fēng)險(xiǎn)就越大。協(xié)方差：表示一種股票利潤(rùn)波動(dòng)與另一種股票利潤(rùn)波動(dòng)的相關(guān)性。協(xié)方差較大，則表明一種股票利潤(rùn)的增加很可能會(huì)帶動(dòng)另一種股票利潤(rùn)的增加。協(xié)方差接近0，則意味著兩種股票的利潤(rùn)變化彼此獨(dú)立。一個(gè)負(fù)的協(xié)方差意味著一種股票利潤(rùn)的增加可能會(huì)導(dǎo)致另一種股票利潤(rùn)的減少。Markowitz模型是尋求最小投資方差的投資方案，同時(shí)使得所有期望利潤(rùn)總和達(dá)到一定水平。第31頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月2.問題假設(shè)你正在考慮向三種股票進(jìn)行投資。通過歷史資料，計(jì)算出了一個(gè)期望利潤(rùn)、利潤(rùn)方差、各種股票之間利潤(rùn)的協(xié)方差。希望通過向三種而不是一種股票投資來降低風(fēng)險(xiǎn)。計(jì)劃讓利潤(rùn)增加12％。則，為達(dá)到這一目標(biāo)并且使投資風(fēng)險(xiǎn)最小，你應(yīng)該如何分配你的資金向三種股票投資？作為一種安全上的考慮，你規(guī)定任何一項(xiàng)單獨(dú)的投資不得超過投資總額的75％。3.模型：Markowitz投資選擇模型GENPRT4.集合定義基本集合ASSETS，三種股票。利用其自乘，派生了一個(gè)密集COVMAT，定義協(xié)方差矩陣。5.屬性定義了4個(gè)屬性。前3個(gè)屬性RATE、UB、V存儲(chǔ)數(shù)據(jù)。RATE：存儲(chǔ)每一種投資的期望利潤(rùn)，UB：存儲(chǔ)投資中用于某一項(xiàng)投資的上限值，V：存儲(chǔ)協(xié)方差矩陣。注意：協(xié)方差矩陣對(duì)稱。只給出一半即可，為簡(jiǎn)單給出整個(gè)矩陣。X：決策變量。即，X(i)表示用于第i項(xiàng)投資的投資比例。第32頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月6.目標(biāo)函數(shù)：使得投資風(fēng)險(xiǎn)達(dá)到最小。用投資方差來表示投資風(fēng)險(xiǎn)。得到下面目標(biāo)函數(shù)：

[VAR]MIN=@SUM(COVMAT(I,J)：V(I,J){X(I)*X(J))；7.約束：三種：(1)必須將資金全部用于投資；使用下面表達(dá)式可將所有資金用于投資：

[FULL]@SUM(ASSET:X)=l；即，所有各項(xiàng)投資的比例之和必須等于1。如果沒有這個(gè)約束，系統(tǒng)將試圖尋求方差更低的投資方案。你可以將這個(gè)約束去掉，運(yùn)行模型試試結(jié)果。(2)不可能在某一項(xiàng)上投資過多；用下面表達(dá)式保證對(duì)某項(xiàng)目的投資不至于太多：

@FOR(ASSET：@BND(0，X，UB))；用@BND函數(shù)限制變量的界限是最有效的方法。(3)期望利潤(rùn)必須達(dá)到或超過目標(biāo)利潤(rùn)率，目標(biāo)利潤(rùn)率為12％。迫使投資的期望利潤(rùn)大于或等于目標(biāo)利潤(rùn)：

[RET]@SUM(ASSET：RATE}X)>=GROWTH；左邊是期望利潤(rùn)率，各項(xiàng)投資利潤(rùn)率與投資比率相乘相加的結(jié)果。第33頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月8.解