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

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

裝配線平衡模型（I）（H）（G）（J）（K）（F）（B）（A）（C）（E）（D）第2頁，共36頁，2023年，2月20日，星期日

MODEL:

!裝配線平衡模型;SETS:

!任務(wù)集合，有一個完成時間屬性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的一個屬性。如果X（I，K）＝1，則表示第I個任務(wù)指派給第K個工作站完成;ENDSETSDATA:

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

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

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

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

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

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

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

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

n=@size(city);data:!距離矩陣，它并不需要是對稱的;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頁，共36頁，2023年，2月20日，星期日給定N個點(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)?，F(xiàn)指定一個終點(diǎn)pN，求從pi點(diǎn)出發(fā)到pN的最短路線。用動態(tài)規(guī)劃方法做：點(diǎn)pi表示狀態(tài)，決策集合是除pi以外點(diǎn)，選定一個點(diǎn)pj以后，得到cij并轉(zhuǎn)入新狀態(tài)效益pj

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

鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏5.265.194.214.002.952.742.461.900.641.27倒裝場Ⅰ1.900.991.901.131.272.251.482.043.093.51巖場5.895.615.614.563.513.652.462.461.060.57巖石漏0.641.761.271.832.742.604.213.725.056.10倒裝場Ⅱ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頁，共36頁，2023年，2月20日，星期日第16頁，共36頁，2023年，2月20日，星期日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頁，共36頁，2023年，2月20日，星期日!目標(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頁，共36頁，2023年，2月20日，星期日@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)));!每一條路線上的最大總車次的計算;@for(link(i,j):lsubject(i,j)=(@floor((distance(i,j)/28*60*2+3+5)/5))*b(i,j));!計算各個鏟位的總產(chǎn)量;@for(cai(j):cnum(j)=@sum(xie(i):number(i,j)));!計算各個卸點(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頁，共36頁，2023年，2月20日，星期日!卸點(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));!各個路線所需卡車數(shù)簡單加和;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頁，共36頁，2023年，2月20日，星期日求解最小生成樹的方法雖然很多，但是利用LINGO建立相應(yīng)的整數(shù)規(guī)劃模型是一種新的嘗試。這對于處理非標(biāo)準(zhǔn)的MST問題非常方便。我們主要參考了文[7]。在圖論中，稱無圈的連通圖為樹。在一個連通圖G中，稱包含圖G全部頂點(diǎn)的樹為圖G的生成樹。生成樹上各邊的權(quán)之和稱為該生成樹的權(quán)。連通圖G的權(quán)最小的生成樹稱為圖G的最小生成樹。許多實際問題都可以歸結(jié)為最小生成樹。如,如何修筑一些公路把若干個城鎮(zhèn)連接起來；如何架設(shè)通訊網(wǎng)絡(luò)將若干個地區(qū)連接起來；如何修筑水渠將水源和若干塊待灌溉的土地連接起來等等。為說明問題,以下面的問題作為范例。范例：假設(shè)某電話公司計劃在六個村莊架設(shè)電話線，各村莊之間的距離如圖所示。試求出使電話線總長度最小的架線方案。為了便于計算機(jī)求解，特作如下規(guī)定：（1）節(jié)點(diǎn)V1表示樹根；（2）兩個節(jié)點(diǎn)之間沒有線路時，規(guī)定兩節(jié)點(diǎn)之間距離為M（較大的值）

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

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

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

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

!每個工人只能有一份工作;

@for(workers(I):

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

!每份工作只能有一個工人;

@for(jobs(J):

@sum(workers(I):volume(I,J))=1;);data:cost=6267425495385852197437673927239572655228114923124510;enddataend第24頁，共36頁，2023年，2月20日，星期日1.背景

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

5個班級安排到5個教室里上課，班級人數(shù)和教室容量如下。例7.8排課模型PKMX教室AlA2A3A4A5教室容量406O80120100班級BlB2B3B4B5班級人數(shù)30406080120試求出一個可行、合理、高效的排課方案。第25頁，共36頁，2023年，2月20日，星期日3.排課規(guī)則及排課“費(fèi)用”三個規(guī)則：排課規(guī)則1：班級人數(shù)小于等于教室容量。排課規(guī)則2：如果教室總數(shù)大于班級總數(shù)，要盡可能空出大教室。排課規(guī)則3：離差(離差=教室容量一班級人數(shù))和相同情況下，選擇離差平方和最小的排課方案。滿足上面三個規(guī)則的排課方案就是可行、合理、高效的排課方案。為說明排課規(guī)則3，請看下面兩個排課方案：方案1：班級B1一教室A1，班級B2一教室A2方案2：班級Bl一教室A2，班級B2一教室A1兩個方案的離差和都是30。方案1使每個教室都留有一定空間，增加少量學(xué)生聽課不會有問題方案2中教室A1滿員，不能增加任何人。方案1比較合理。兩個方案的離差平方和分別是500和900。按照排課規(guī)則3，我們就會選擇方案1。第26頁，共36頁，2023年，2月20日，星期日4.定義排課“費(fèi)用”：定義假設(shè)第i個班級人數(shù)為ai；第j個教室容量為bi(i,j=1,2,3,4,5)。Cij表示第i個班級指定到第i個教室上課的“費(fèi)用”。則注意：實際問題中，常常會出現(xiàn)班級總數(shù)小于教室總數(shù)情況。此時可虛設(shè)幾個班級，令其人數(shù)為零，使班級總數(shù)等于教室總數(shù)。根據(jù)以上規(guī)則和定義，原問題就成了求解“費(fèi)用”最小的指派問題。5.模型：排課模型PKMX第27頁，共36頁，2023年，2月20日，星期日6.集合定義了兩個基本集合A、B。A表示教室，B表示班級。用A、B產(chǎn)生派生集合AB。7.變量在AB上定義了兩個屬性C、X。C存放排課“費(fèi)用”，X是決策變量。若x(i‘j)=1，則第i個班級指派到第j個教室上課；若x(i'j)=0，則第i個班級不指派到第j個教室上課。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)它限制一個班級只能到一個教室上課。第二種：@for(B(j)：@sum(A(i)：X(i,j))=1)它限制一個教室只能安排一個班級上課。第三種：.@for(A(i)：@for(B(j)：@BIN(X(i,j))))它限制x只取0／1兩個值。第28頁，共36頁，2023年，2月20日，星期日10.數(shù)據(jù)與解答數(shù)據(jù)來自文件排課數(shù)據(jù).xls，解答也輸出到此文件中。排課數(shù)據(jù).xls中定義了兩個域：“排課數(shù)據(jù)”域，范圍：Sheetl!$c$4：$G$8；“排課方案”域，范圍：Sheetl!$C$15：$G$19?！芭耪n數(shù)據(jù)”域中每個單元的數(shù)據(jù)是按定義1計算的，具有相類似的計算格式。如：

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

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

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

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

[RET]@SUM(ASSET：RATE}X)>=GROWTH；左邊是期望利潤率，各項投資利潤率與投資比率相乘相加的結(jié)果。第33頁，共36頁，2023年，2月20日，星期日8.