數(shù)據(jù)、模型與決策課程解題思路

數(shù)據(jù)、模型與決策課程解題思路一、不確定性決策收益矩陣的格式 ——橫表頭為市場情況，列表頭為方案；樂觀準(zhǔn)則 ——最大最大：按行找出各方案中最大收益，選擇最大收益最大的方案；悲觀準(zhǔn)則 ——最大最?。喊葱姓页龈鞣桨钢凶钚∈找?，選擇最小收益最大的方案；等可能準(zhǔn)則 ——最大平均：按行計算出各方案的平均收益，選擇平均收益最大的方案；后悔值準(zhǔn)則 ——最小最大后悔：按列找出各種市場情況下最大收益值，用最大收益值減去本列的各個收益得其后悔值，按行找出各方案的最大后悔值，選擇后悔值最小的方案；樂觀系數(shù)準(zhǔn)則 ——最大加權(quán)平均：按行找出各方案中最大和最小收益值，以“樂觀系數(shù)”和“1－樂觀系數(shù)”為權(quán)計算最大和最小收益值的加權(quán)平均值，選擇加權(quán)平均值最大的方案。以課堂作業(yè)1舉例如下：市場需求量樂觀準(zhǔn)則悲觀準(zhǔn)則等可能準(zhǔn)則樂觀系數(shù)準(zhǔn)則大中小失敗最大最大最大最小最大平均最大加權(quán)平均擴(kuò)建502510-1550-1517.530.5新建7030-10-4070-4012.537外包3015-5-1030-107.518市場需求量后悔值準(zhǔn)則大中小失敗后悔值最小最大擴(kuò)建502510-152050520新建7030-10-4000203030外包3015-5-10401515040二、規(guī)劃模型的標(biāo)準(zhǔn)化解題思路：標(biāo)準(zhǔn)形式的約束條件有三個要件，一是常數(shù)項非負(fù)；二是只能有等式；三是定義域非負(fù)。根據(jù)上述要件，分四步操作：A、判斷常數(shù)項是否非負(fù)，如有負(fù)值則兩邊同乘（-1），并相應(yīng)改變不等號方向；B、判斷是否有不等式，如有則設(shè)松弛或剩余變量xi≥0，大于號減、小于號加xi變等式；C、判斷各變量的定義域是否非負(fù)，如為負(fù)值，則設(shè)xj=（-xi）≥0，代入模型；如為-∞≤xk≤∞，則設(shè)xk=（xm－xn），xm、xn≥0，代入模型；D、整理變量下標(biāo)后，得到標(biāo)準(zhǔn)形式。三、線性規(guī)劃模型的解法及敏感性分析A、圖解步驟如下：1、以x1為橫軸、x2為縱軸建立直角坐標(biāo)系，標(biāo)出各約束條件和目標(biāo)函數(shù)的直線；2、在第一象限找出可行域；3、目測目標(biāo)函數(shù)平移后最可能與可行域的哪個頂點相切，則該點為最優(yōu)解點；4、解方程得到該點坐標(biāo)，即得最優(yōu)解，代入目標(biāo)函數(shù)得最優(yōu)值。5、小技巧：(1)作圖時，對約束條件，可分別令x1和x2為零，得到其與縱軸和橫軸的交點，連接即可；對目標(biāo)函數(shù)，令x1為一特殊值，得出x2，再與原點相連，可得函數(shù)直線，再沿橫軸平移到合適位置即；(2)各條直線斜率絕對值越大的，越接近垂直于x1軸；(3)確定可行域時，要考慮坐標(biāo)軸和原點；(4)目測判斷最優(yōu)點不易時，可將相鄰數(shù)點的坐標(biāo)解出代入目標(biāo)函數(shù)進(jìn)行比較。B、松弛變量和剩余變量1、約束條件為“≤”的存在松弛變量，為“≥”的存在剩余變量；2、將最優(yōu)解代入各約束條件即得各自的松弛或剩余變量；3、構(gòu)成最優(yōu)解的約束條件的松弛或剩余變量為零。C、對偶價格1、不構(gòu)成最優(yōu)解的約束條件的對偶價格為零；2、構(gòu)成最優(yōu)解的約束條件存在對偶價格，求解時令其中一個約束條件的常數(shù)項增加1，另一個約束條件不變，重新解出交點坐標(biāo)，代回目標(biāo)函數(shù)計算目標(biāo)值，再與原最優(yōu)值相差即得；3、對偶價格的討論均在各約束條件常數(shù)項的上、下限范圍內(nèi)進(jìn)行，超范圍時對偶價格可能發(fā)生變化；4、已知對偶價格和最優(yōu)值求常數(shù)項變化時，目標(biāo)函數(shù)求Max時，增加目標(biāo)值的，常數(shù)項同向變化，即增大；求Min時，增加目標(biāo)值的，常數(shù)項反向變化，即減少；反之亦然。D、目標(biāo)函數(shù)系數(shù)上、下限1、目標(biāo)函數(shù)系數(shù)的變化，在圖解時可視為目標(biāo)函數(shù)直線斜率的變動，即該直線以最優(yōu)解點為支點旋轉(zhuǎn)；其取值范圍為最優(yōu)解不變的范圍，即不突破構(gòu)成最優(yōu)解的兩條直線斜率kmin和kmax的范圍。2、求解時，將目標(biāo)函數(shù)變換為x2=(-c1/c2)*x1的形式，通過kmin≤(-c1/c2)≤kmax，分別代入c1或c2，可得c2或c1的上、下限。E、約束條件常數(shù)項的上、下限1、約束條件常數(shù)項的變化，在圖解時可視為約束條件直線在縱軸上截距的變動，即該直線沿橫軸平移，不會與另兩條約束條件直線交點相交的范圍，也就是不會改變可行域的結(jié)構(gòu)、不會減少可行域邊數(shù)（坐標(biāo)軸不算）的范圍；其取值范圍為對偶價格不變的范圍，但有可能會改變最優(yōu)解和最優(yōu)值。2、求解時，找到該約束條件相鄰的兩個可行域的頂點坐標(biāo)(xa,xb)，根據(jù)x2-xb=k*(x1-xa)點斜式方程，分別求出約束條件平移至該兩個頂點的在橫軸上的截距、即變化后的常數(shù)項上、下限。 F、百分之一百法則1、增加率和減少率之和不超過100%；2、增加（減少）率＝增加（減少）值/允許增加（減少）值；增減值以當(dāng)前值為基數(shù)計算，允許增減值以當(dāng)前值為基數(shù)、各值取值范圍的上、下限計算；3、多個目標(biāo)函數(shù)系數(shù)變動時，其意義為最優(yōu)解不變；多個約束條件常數(shù)項變動時，其意義為對偶價格不變；不適用目標(biāo)函數(shù)系數(shù)和約束條件常數(shù)項同時變動的情況，也不適用于相關(guān)系數(shù)和常數(shù)項同步增減（即有增無減、或在減無增）的情況。G、相差值1、最優(yōu)解中為零的變量，其系數(shù)變化到不為零時的差值；2、最優(yōu)解中不為零的變量，其相差值必為零；3、目標(biāo)函數(shù)求Max時，其相差值為其上限值減去當(dāng)前值，且該系數(shù)無下限；目標(biāo)函數(shù)求Min時，其相差值為其下限值減去當(dāng)前值，且該系數(shù)無上限；四、線性規(guī)劃模型的建立A、問題的實質(zhì)——在某些資源限制下，求利潤最大或成本最小。這些資源限制包括資金、物料、工時的最高或最低要求等，關(guān)鍵是找到合適的變量，將目標(biāo)和限制聯(lián)系起來。B、人力資源問題——按循環(huán)周期計算當(dāng)天（單位時間）內(nèi)上班或休息的人數(shù)并與限制條件相比較xi為每天（單位時間）上班或休息的人數(shù)；Min配備的總?cè)藬?shù)、上班或休息的人員（成本最低）S.T.滿足每天（單位時間）上班或休息人數(shù)的限制xi≥0C、生產(chǎn)計劃問題——按不同生產(chǎn)車間或工序生產(chǎn)產(chǎn)品的件數(shù)及其所需的物料、設(shè)備或工時與限制相比較xi為每個車間或工序生產(chǎn)產(chǎn)品的件數(shù)；Max利潤或Min成本S.T.1、滿足物料、設(shè)備或工時的限制2、各工序生產(chǎn)的產(chǎn)品數(shù)量應(yīng)相等xi≥0D、套裁下料問題——列出一根整料所有可行的裁料方案，不同裁料方案運用的次數(shù)及其所得不同規(guī)格工件的總數(shù)與總需求量相比較xi為每種裁料方案的運用次數(shù)，最終整料的使用量為xi之和；Min裁料方案運用次數(shù)之和；S.T.各種裁料方案裁得的不同規(guī)格的工件必須不少于其總需求量；xi≥0E、配料問題——每種產(chǎn)品中各原料的比例應(yīng)滿足要求，且各原料的總使用量不得超過限制xi為每種產(chǎn)品中各原料的使用量；Max利潤或Min成本；S.T.1、每種產(chǎn)品中各原料的比例；2、各原料的使用量少于限制量；xi≥0F、連續(xù)投資問題——根據(jù)項目回收期不同列出各年各種方案可能的投資表，總收益為各項目最后一期投資的和，各期的投資應(yīng)等于期初資金（也就是上一期投資的收入）xi為每項目在各年的投資額；Max總收益或Min總風(fēng)險；S.T.1、各期的投資等于期初資金（也就是上一期投資的收入）；2、滿足各期投資限制xi≥0五、運輸模型A、產(chǎn)銷表的基本形式銷地產(chǎn)地銷地1銷地2銷地……產(chǎn)量產(chǎn)地1產(chǎn)地2產(chǎn)地……銷量總產(chǎn)量總銷量B、基本運輸問題的線性規(guī)劃求解令各產(chǎn)地運往各銷地的貨物量為xi，則：Min運費（xi乘以運價）S.T.每個產(chǎn)地的產(chǎn)量等于運往各銷地的貨物量每個銷地的銷量等于運往該地的貨物量xi≥0C、產(chǎn)銷不平衡問題——轉(zhuǎn)化為產(chǎn)銷平衡問題產(chǎn)大于銷時，增加虛擬銷地，即增加一列，該列的運費為“0”，銷量為差額；銷大于產(chǎn)時，增加虛擬產(chǎn)地，即增加一行，該行的運費為“0”，產(chǎn)量為差額；D、有條件的產(chǎn)銷不平衡問題——轉(zhuǎn)化為產(chǎn)銷平衡問題當(dāng)銷大于產(chǎn)，且部分銷地的產(chǎn)銷量可在一定范圍內(nèi)變化時：1、將該銷地的銷售拆分為兩地，即一列變兩列，其中一列的銷量為該銷地的基數(shù)，另一列的銷量為其可變數(shù)，各產(chǎn)地至該兩個銷地的運費不變；2、增加虛擬產(chǎn)地，即增加一行，該行中到基數(shù)銷地的運費為M（意為足夠大），到可變數(shù)銷地的運費為“0”，該行的產(chǎn)量為產(chǎn)銷的差額；3、當(dāng)存在銷量不限的銷地時，各真實產(chǎn)地到該銷地的運費為M，虛擬產(chǎn)地到該銷地的運費為“0”，虛擬產(chǎn)地的產(chǎn)量為各銷地可變數(shù)之和。E、生產(chǎn)存儲問題——將各期視為產(chǎn)銷地，各期的生產(chǎn)量和交貨量分別視為產(chǎn)量和銷費，各期生產(chǎn)的產(chǎn)品其生產(chǎn)成本與至交貨期的存儲成本之和視為運費，其中按時間順序不存在交貨的運費為M，轉(zhuǎn)化運輸問題。銷地產(chǎn)地第一季度第二季度第三季度第四季度生產(chǎn)量（產(chǎn)量）第一季度生產(chǎn)成本1生產(chǎn)成本1+存儲成本生產(chǎn)成本1+存儲成本×2生產(chǎn)成本1+存儲成本×3第二季度M生產(chǎn)成本2生產(chǎn)成本2+存儲成本生產(chǎn)成本2+存儲成本×2第三季度MM…………第四季度MMM……交付量（銷量）總產(chǎn)量總銷量F、轉(zhuǎn)運問題——將中轉(zhuǎn)站既視為銷地、也視為產(chǎn)地，轉(zhuǎn)化為運輸問題運輸模型表中產(chǎn)地由原產(chǎn)地加中轉(zhuǎn)地構(gòu)成，銷地為最終銷地加中轉(zhuǎn)地構(gòu)成，直接相連的路線運費按各地間運費填列，不直接相連的路線運費為M（意為足夠大），本地到本地的運費為“0”。六、整數(shù)規(guī)劃模型整數(shù)規(guī)劃——可行解為非負(fù)整數(shù)的集合，可行域表現(xiàn)為某一區(qū)域內(nèi)的可行點A、圖解法1、按常規(guī)方法標(biāo)出該模型的可行域，并在可行域中標(biāo)出橫、縱坐標(biāo)為整數(shù)的可行點；2、標(biāo)出目標(biāo)函數(shù)直線，按求Max或Min分別從可行域的右邊或左邊沿x1軸平移，最先接觸的可行點即為最優(yōu)解，代入目標(biāo)函數(shù)得最優(yōu)值；3、標(biāo)定可行點時應(yīng)充分注意坐標(biāo)軸上的整數(shù)點（包括原點）和約束函數(shù)直線上的整數(shù)點；B、0－1規(guī)劃問題1、0或1為某一現(xiàn)象的狀態(tài)，0表示非、即不發(fā)生、不指派、不分配、不選用等，1則相反；2、通過設(shè)定0－1變量與某一現(xiàn)象的后果相乘，表示該現(xiàn)象發(fā)生或不發(fā)生帶來的后果，同時，0－1變量的和可以限制某類現(xiàn)象共同發(fā)生或不發(fā)生的次數(shù)；3、投資場所選擇問題令各投資場所被選擇的情況xi(i＝1,2…n)為0－1變量，0表示不被選擇，1表示被選擇，則：Max利潤或Min成本（xi乘以各投資場所的利潤或成本）S.T.必須選擇或可以同時選擇的投資場的xi值之和與限制相比較xi為0－1變量3、固定成本問題令各產(chǎn)品的產(chǎn)量xi(i＝1,2…m)為非負(fù)整數(shù)變量，生產(chǎn)該產(chǎn)品所需投入固定資產(chǎn)發(fā)生狀態(tài)xm+j(j＝1,2…n)為0－1變量，0表示某產(chǎn)品不被選擇，1表示被選擇，則：Max利潤（各產(chǎn)品的營業(yè)利潤之和減去為生產(chǎn)其所投入的固定資產(chǎn)之和）S.T.(1)生產(chǎn)產(chǎn)品所需的物料、設(shè)備和工時與限制條件相比較(2)xi≤Mxm+j（M為足夠大的數(shù)，應(yīng)遠(yuǎn)大于該組產(chǎn)品可能的最大產(chǎn)量，此約束條件是為排除不投入生產(chǎn)某產(chǎn)品所需的固定資產(chǎn)、但卻有xi存在的情況——當(dāng)xm+j為零時，此時xi必為零；當(dāng)xm+j為1時，此時xi可為實際值且不受M的限制）xi(i＝1,2…m)為非負(fù)整數(shù)變量，xm+j(j＝1,2…n)為0－1變量4、指派問題令指派某人從事某項工作的狀態(tài)xi(i＝1,2…n)為0－1變量，0表示不指派某人從事某項工作，1表示指派，則：Min成本、費用或工時（某人從事某項工作的成本、費用或工時乘以xi后之和）S.T.(1)各人被指派從事某項工作的狀態(tài)之和為1(2)各項工作有人被指派的狀態(tài)之和也為1xi(i＝1,2…n)為0－1變量指派問題可用運輸模型解決，其基本形式為：工作人員工作1工作2工作…被指派人員數(shù)量人員11人員21人員…1工作量111總?cè)肆靠偣ぷ髁窟\輸模型中有關(guān)產(chǎn)銷不平衡的處理也可用于指派問題。5、分布系統(tǒng)設(shè)計問題該問題涉及不同生產(chǎn)地到銷售地的運費和不同生產(chǎn)地的建設(shè)費用（固定成本）。令各生產(chǎn)地的產(chǎn)量xi（i=1,2,…m）為非負(fù)整數(shù)，選擇某一生產(chǎn)地的可能xm+j（j=1,2…n）為0－1變量，0表示不選擇、1表示選擇，則：Min成本（成本為各生產(chǎn)地產(chǎn)量xi乘以成本與各生產(chǎn)地建設(shè)費用乘以xm+j之和）S.T.(1)各生產(chǎn)地銷往各銷售地的銷量與產(chǎn)量限制相比較（其中已建成生產(chǎn)地的限制條件直接用當(dāng)前產(chǎn)量，待建生產(chǎn)地的限制條件用預(yù)計產(chǎn)量乘xm+j）(2)各銷售地中各生產(chǎn)地的產(chǎn)量與銷量限制相比較xi（i=1,2,…m）為非負(fù)整數(shù)，xm+j（j=1,2…n）為0－1變量分布系統(tǒng)設(shè)計問題可用運輸模型解決。6、投資問題與線性規(guī)劃中連續(xù)投資問題相類似，只是各期的投資量存在限制、投資與否也不確定。因此，用０－１變量表示投資的可能性，根據(jù)項目回收期不同列出各年各種方案可能的投資表，其中總收益為各項目最后一期投資的和，各期的投資應(yīng)等于期初資金（也就是上一期投資的收入）。目標(biāo)為求總收益最大，約束條件包括各期的投資應(yīng)等于期初資金（也就是上一期投資的收入），以及各期投資的限制。七、目標(biāo)規(guī)劃模型目標(biāo)規(guī)劃問題——指不能同時滿足所有約束條件的情況下，求最大限度滿足各級目標(biāo)的最優(yōu)解A、目標(biāo)規(guī)劃問題不存在滿足所有約束條件的解——在圖形上表現(xiàn)為至少有一個限制條件的可行區(qū)域與其它不相交、不存在滿足所有約束條件的共同可行域；B、目標(biāo)規(guī)劃問題存在分級目標(biāo)，即優(yōu)先保證目標(biāo)實現(xiàn)的等級，優(yōu)先滿足等級高的目標(biāo)——在圖形上表現(xiàn)為從第一級目標(biāo)的可行域中找滿足第二級目標(biāo)偏差值最小的點、即到第二級限制條件直線距離最短的點；并依此類推；C、目標(biāo)規(guī)劃問題引入了偏差變量di+、di-，分別表示超過或少于約束條件常數(shù)項的值——在圖形上表現(xiàn)為約束條件直線（k<0）上di+＝0、di-＝0（無偏差），右上方區(qū)域為為di+≥0、di-＝0（超過常數(shù)項），左下方區(qū)域為di+＝0、di-≥0（少于常數(shù)項）；D、列出分級目標(biāo)規(guī)劃模型的步驟：（1）選定各目標(biāo)的優(yōu)先等級，按優(yōu)先次序排列各約束條件——必須予以滿足的條件為絕對約束，其等級最高，有一定浮動空間的條件為條件約束，分優(yōu)先等級；（2）條件約束為“≤”的，求mindi+（方向相后、表示超出的最少），條件約束為“≥”的，求mindi-（同樣方向相后、表示低于的最少）（3）在條件約束中參考引入松弛、剩余變量化標(biāo)準(zhǔn)規(guī)劃模型的做法，在式子左邊加上“-di++di-”，將不等號轉(zhuǎn)換為等號，此時不用考慮正負(fù)符號，直接加上即可；（4）第一級目標(biāo)規(guī)劃模型為：Mind1+/d1-+d2+/d2-+…（不一定唯一，多個照排）S.T.絕對約束第一級條件約束（不一定唯一，多個照排）xi,di≥0第二級及以下各級目標(biāo)規(guī)劃模型為：Mind3+/d3-+d4+/d4-+…（不一定唯一，多個照排）S.T.絕對約束第一級條件約束（不一定唯一，多個照排）第二級條件約束（不一定唯一，多個照排）第…級條件約束（不一定唯一，多個照排）增加上一級條件約束的計算結(jié)果增加上…級條件約束的計算結(jié)果xi,di≥0E、列出總目標(biāo)規(guī)劃模型minz=P1（d1+/d1-+d2+/d2-+…）+P2（d3+/d3-+d4+/d4-+…）+…（P1、P2代表優(yōu)先等級，同一優(yōu)先級目標(biāo)列在一起，具體是di+或di-根據(jù)約束條件確定）S.T.絕對約束第一級條件約束第二級條件約束第…級條件約束xi,di≥0F、總目標(biāo)規(guī)劃模型與分級目標(biāo)模型之間的相互轉(zhuǎn)換——參考兩類模型的做法即可。G、加權(quán)目標(biāo)規(guī)劃——當(dāng)目標(biāo)存在權(quán)重時，在目標(biāo)函數(shù)的di+或di-上直接加上權(quán)重即可，約束條件不變。H、目標(biāo)規(guī)劃模型的圖解——找兩條約束條件直線劃定的可行域中距離最短的點1、建立坐標(biāo)系，做出各約束條件的可行域，并將絕對約束視為第零級約束，首先予以保證；2、兩級約束條件的最優(yōu)解——如兩條直線相交，則可同時滿足，最優(yōu)解為交點；如不相交，則本級約束條件可行域中距下一級約束條件直線距離最近的點為最優(yōu)解；3、找到最優(yōu)解后，代入目標(biāo)函數(shù)，即得最優(yōu)值，再分別計算各約束條件距要求的差值；4、一般情況下，圖解法不便于解超過兩級的目標(biāo)規(guī)劃。八、網(wǎng)絡(luò)最優(yōu)化模型網(wǎng)絡(luò)最優(yōu)化問題——選擇最優(yōu)路線A、有方向的問題——有明確的起點和終點，求從起點到終點費用最省、流量最大的問題，包括最短路問題、最小費用問題、最大流問題、最小費用最大流問題1、狹克斯屈拉法解最短路問題——從起點開始，依次計算路程中各節(jié)點之前的費用和步數(shù)，最終計算出到終點所有可能路徑所需的費用和步數(shù)，選擇費用最低的路徑；2、搬箱子理念——設(shè)想運送一個箱子從起點到終點，除起點和終點外，無論路徑中哪一個中間節(jié)點，只有一個箱子進(jìn)、一個箱子出，各節(jié)點進(jìn)出平衡，而起點只有一個箱子出，終點只有一個箱子進(jìn)；——通過某節(jié)點的流入量和流出量相等，保證了路徑內(nèi)各節(jié)點流量平衡、前后銜接，也建立了線性規(guī)劃模型的約束條件；——實際使用時，起點各條路徑的流出量合計為1，終點各條路徑的流入量合計為1，中間節(jié)點各流入路徑合計量減去流出路徑合計量為零；3、線性規(guī)劃模型的建立令各條路徑的選擇可能性為xi（最短路問題），或流量為xi（費用和流量問題）Min路程/成本（各路徑距離或成本乘以xi）或max流量（起點各路徑流出量之和）S.T.起點：流出量之和（最大流量問題不計算此點）中間點：1、各點流入量減流出量為零2、各路徑流量限制終點：流入量之和（最大流量問題不計算此點）xi≥