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