運籌學實驗指導書(第1部分)匯總

1、預備知識WinQSB軟件操作指南WinQSB軟件簡介QSB是QuantitativeSystemsforBusiness勺縮寫，早期的版本是在DOS操作系統(tǒng)下運行的，后來發(fā)展成力在Windows操作系統(tǒng)下運行的WinQSB軟件，目前已經(jīng)有2.0版。該軟件是由美籍華人Yih-LongChang和KiranDesai共同開發(fā)，可廣泛應(yīng)用于解決管理科學、決策科學、運籌學及生產(chǎn)管理等領(lǐng)域的問題。該軟件界面設(shè)計友好，使用簡單，使用者很容易學會并用它來解決管理和商務(wù)問題，表格形式的數(shù)據(jù)錄入以及表格與圖形的輸出結(jié)果都給使用者帶來極大的方便，同時使用者只需要借助于軟件中的幫助文件就可以學會每一步的操作。Win

2、QSB應(yīng)用軟件包可求解如下19類問題：號序程序縮寫、文件名名稱應(yīng)用范圍1AcceptanceSamplingA抽樣分析管種抽樣分析、抽任方案設(shè)AnalysisSA計、假設(shè)分析具有多時期正常、加班、分時、轉(zhuǎn)包生產(chǎn)量，需求量，儲2AggregatePlanningPA綜合計劃編制存費用，生產(chǎn)費用等復雜的整體綜合生產(chǎn)計劃的編制方法。將問題歸結(jié)到求解線性規(guī)劃模型或運輸模型D確定型與風險型決策、貝葉斯3decisionanalysisA決策分析決策、決策樹、二人零和對策、蒙特卡羅模擬。4DynamicProgrammingPD動態(tài)規(guī)劃最短路問題、背包問題、生產(chǎn)與儲存問題sFacilityLocation

3、andLayoutLLF設(shè)備場地布局設(shè)備場地設(shè)計、功能布局、線路均衡布局ForecastingandLinearF預測與線性回簡單平均、移動平均、加權(quán)移6regressionC歸動平均、線性趨勢移動平均、指數(shù)平滑、多元線性回歸、Holt-Winters季節(jié)迭加與乘積算法GoalProgrammingandG目標規(guī)劃與整G數(shù)線性目標規(guī)多目標線性規(guī)劃、線性目標規(guī)7IntegerLinearGoalPIGP戈上變量可以取整、連續(xù)、0Programming劃1或無限制經(jīng)濟訂貨批量、批量折扣、單8InventoryTheoryandSystemsI存儲論與存儲時期隨機模型，多時期動態(tài)儲TS控制系統(tǒng)存模型

4、，儲存控制系統(tǒng)（各種儲存策略）9JobSchedulingJ作業(yè)調(diào)度，編機器加工排序、流水線車間加OB制工作進度表工排序LinearprogrammingandL線性規(guī)劃與整線性規(guī)劃、整數(shù)規(guī)劃、寫對0integerlinearP-ILP數(shù)線性規(guī)劃偶、靈敏度分析、參數(shù)分析programming11MarKovProcessKPM馬耳科夫過程轉(zhuǎn)移概率，穩(wěn)態(tài)概率21MaterialrequirementsRPM物料需求計劃物料需求計劃的編制，成本核planning算31NetworkModelingetN網(wǎng)絡(luò)模型運輸、指派、最大流、最短路、最小支撐樹、貨郎擔等問題，有（無）條件約束、目標函數(shù)1NT或

5、約束條件非線性、目標函數(shù)4NonLinearProgrammingLP非線性規(guī)劃與約束條件都非線性等規(guī)劃的求解與分析1.ProjectSchedulingP1網(wǎng)絡(luò)計劃關(guān)鍵路徑法、計劃評審技術(shù)、5ERT-CPM網(wǎng)絡(luò)的優(yōu)化、工程完工時間模Quadraticprogramming6QueuingAnalysis1QueuingSystem8Simulation19QualitycontrolchartsP二次規(guī)劃Q排隊分析AQQQ排隊系統(tǒng)模擬SSQ質(zhì)量管理控制CC圖求解線性約束、目標函數(shù)是二次型的一種非線性規(guī)劃問題，變量可以取整數(shù)各種排隊模型的求解與性能分析、15種分布模型求解、靈敏度分析、服務(wù)能力

6、分析、成本分析未知到達和服務(wù)時間分布、般排隊系統(tǒng)模擬計算建立各種質(zhì)量控制圖和質(zhì)量分析WinQSB軟件的基本操作1 .安裝與啟動點擊WinQSB安裝程序的Setup,指定安裝目錄后，軟件自動完成安裝。讀者在使用該軟件時，只需要根據(jù)不同的問題，調(diào)用程序當中的不同模塊，操作簡單方便。進入某個模塊以后，第一項工作就是建立新問題或者打開已經(jīng)存盤的數(shù)據(jù)文件。在WinQSB軟件安裝完成后，每一個模塊都提供了一些典型的例題數(shù)據(jù)文件，使用者可以先打開已有的數(shù)據(jù)文件，了解數(shù)據(jù)的輸入格式，系統(tǒng)能夠解決什么問題，結(jié)果的輸出格式等內(nèi)容。2 .數(shù)據(jù)的錄入與保存數(shù)據(jù)的錄入可以直接錄入，同時也可以從Excel或Word文檔中

7、復制數(shù)據(jù)到WinQSB0首先選中要復制的電子表格中單元格的數(shù)據(jù)，點擊復制，然后在WinQSB的電子表格編輯狀態(tài)下選擇要粘貼的單元格，點擊粘貼即可。如果要把WinQSB中的數(shù)據(jù)復制到office文檔中，選中WinQSB表格中要復制的單元格，點擊Edit/Copy,toclipboard即可。數(shù)據(jù)的保存，只需要點擊File/Saveas即可，計算結(jié)果的保存亦相同，只是注意系統(tǒng)以文本格式（*.txt）保存結(jié)果，使用者可以編輯該文本文件。實驗1線性規(guī)劃問題的WinQSB應(yīng)用實驗?zāi)康? .了解WinQSB件的集成環(huán)境，掌握WinQS既成環(huán)境的基本操作方法；2 .掌握利用WinQSBJjLP問題的最優(yōu)解，

8、并進行靈敏度分析；3 .學會對利用WinQS球得結(jié)果的解釋。實驗內(nèi)容上機實習教材P9例2,并將求解結(jié)果與P15相應(yīng)的圖解法結(jié)果、P26的例5的單純形解法相比較，并看P61-62的影子價格、P65-70靈敏度分析的例題6-9。實驗要求1 .首先給出P9例2的理論求解（圖解法、單純行法、靈敏度分析。2 .完成【實現(xiàn)提示】中的所有操作，并合理組織寫出實驗報告。實現(xiàn)提示例求解下列LP問題AMC公司用兩種機器制造兩種產(chǎn)品A和B,有關(guān)數(shù)據(jù)見表1-1所示，當前市場對產(chǎn)品A和B的需求為供不應(yīng)求，它們的市場價格分別為產(chǎn)品A每個50元，產(chǎn)品B每個60元，請問如何安排生產(chǎn)可使其月收入最高？機器A機器B每月可用工時1

9、23180232150maxz=50+60巧2$+3毛<1803演i2M<150可之0,之。1.求解步驟Step1啟動程序。開始程序/WinQSB/LinearandIntegerProgramming,則彈出如下界面Step2將問題輸入系統(tǒng)。點擊NewProblem,在彈出的界面中填入或選中參數(shù)，如其中ProblemTitle:問題名；NumberofVariables：變量數(shù)；NumberofConstraint:約束條件數(shù)ObjectiveCriterion:目標函數(shù)標準（最大、最?。〥efaultVariableType:默認變量類型（非負連續(xù)、非負整數(shù)、二進制、無符號/無

10、限制）DataEntryFormat:數(shù)據(jù)輸入格式（表格矩陣形式、常規(guī)模型形式）參數(shù)設(shè)置完后按“OK”，在彈出的表中輸入數(shù)據(jù)，如下Step3求解問題。點擊SolveandAnalyze,如下圖:（1點擊“SoketheProblem”，其作用是求解不顯示迭代過程，結(jié)果如下:從此表可以看出：最優(yōu)解為（18,48）T,目標函數(shù)最優(yōu)值（最大值）為3780;變量x1的系數(shù)在40,90內(nèi)變化時，最優(yōu)解不變，但最優(yōu)值隨之改變；變量x2的系數(shù)在33.33,75內(nèi)變化時，最優(yōu)解不變，但最優(yōu)值隨之改變。從此表可以看出：第一臺機器的約束（180）和第二臺機器的約束（150）都是緊約束；第一臺機器的生產(chǎn)能力在100

11、,225內(nèi)變化時，其影子價格為16元，第二臺機器的生產(chǎn)能力在120,270內(nèi)變化時，其影子價格為6元。（2點擊SolveandDisplaysteps,其作用是求解并顯示單純形法迭代步驟，結(jié)果如下:AlSimplexTableauIteTation1XIX2Slack_C1Slnck_C2BasisG(j)50.0000EO.QQOdQ0FLH.S.Slack_C102.00003.00001.00000180.0000Slock_C203.00002.000001-0000150.0000c(j)-zu)50.000060,0000000按菜單SimplexIteration/NextIte

12、ration,彈出如下界面SimplexTableau-Iteration2X1Slock_C1siociTeFBasis50,000060000000RH.SX2GO.OOOO；06S671.00000.3333Q60.000ISlack_CZ01.66670-D.6667kOOOO3D.0QQIc（j）-如11).0000020.000003.600.0001按菜單SimplexIteration/NextIteration,彈出如下界面SimplexTableau-Iteration3XIX2Slack_C1Slack_C2B口sisCO)50.000060,0000Q0R.H.X260

13、.0000O.OOOOl1.0000O.BOOO-0.-400048.XI5000001.00000.0000-040000.600010.0016JOQ0-6.00003.780即為最終單純形表。（3點擊GraphicMethod,其作用使用圖解法進行求解.結(jié)果如下:2.補充說明(1修改變量類型：系統(tǒng)給出了非負連續(xù)、非負整數(shù)、0-1型和無符號限制或者無約束4種變量類型選項，當選擇了某一種類型后系統(tǒng)默認所有變量都屬于該種類型。例如，在上例中，10救1<20直接將x1中的下界(LowerBound)改為10,(UpperBound)上界改為20。x2設(shè)定為無約束(Unrestricted)

14、,貝Ux2中的下界(LowerBound)改為-M,(UpperBound)上界改為+M,M是一個任意大的正數(shù)。(2)修改變量名和約束名：系統(tǒng)默認變量名為X1,X2,，Xn,約束名為C1,C2,，Cm默認名可以修改，點擊菜單欄Edit后，下拉菜單有四個修改選項：修改標題名(ProblemName、變量名(VariableName、約束名(ConstraintName和目標函數(shù)準則(max或min。3.靈敏度分析點擊菜單欄result或者點擊快捷方式圖標，下拉菜單有若干選項只顯示最優(yōu)解(SolutionSummary。約束條件摘要(ConstraintSummary,比較約束條件兩端的值。對目標

15、函數(shù)進行靈敏度分析(SensitivityAnalysisofOBJ。對約束條件右端常數(shù)進行靈敏度分析(SensitivityAnalysisofRHS求解結(jié)果組合報告(CombinedReport,顯示詳細綜合分析報告。進行參數(shù)分析(PerformParametricAnalysis,某個目標函數(shù)系數(shù)或約束條件右端常數(shù)帶有參數(shù)，計算出參數(shù)的變化區(qū)間及其對應(yīng)的最優(yōu)解，屬于參數(shù)規(guī)劃內(nèi)容。顯示最后一張單純性表（FinalSimplexTableau。顯示另一個基本最優(yōu)解（ObtainAlternateOptimal,存在多重解時，系統(tǒng)顯示另一個基本最優(yōu)解，然后考慮對基本最優(yōu)解進行組合可以得到最優(yōu)解

16、的通解。顯示系統(tǒng)運算時間和迭代次數(shù)（ShowRunTimeandItration。不可行性分析（InfeasibilityAnalysis,線性規(guī)劃問題無可行解時，系統(tǒng)指出存在無可行解的原因，無界性分析（UnboundednessAnalysis線性規(guī)劃問題存在無界解時，系統(tǒng)指出存在無界解的可能原因?！締栴}1】對目標系數(shù)c2進行靈敏度分析點擊Results/PerformParametricAnalysis;彈出對話框，選擇分析目標系數(shù)及決策變量，如下圖單擊OK得結(jié)果如下:分析如下:（1c2從60增加到75,目標函數(shù)值從3780增力口至I4500,斜率48,出基變量x1,進基變量Slack_c

17、2;（2c2從75增加到工，目標函數(shù)值從4500增力口至：工，斜率60;（3c2從60減少到33.33,目標函數(shù)值從3780減少到2500,斜率48,出基變量x2,進基變量Slack_c1;(4c2從33.33減少到到-力，目標函數(shù)值保持2500不變。點擊Results/GraphicParametricAnalysis,4c2變化的參數(shù)分析圖ijS-【問題2】對右端項b2進行靈敏度分析點擊Results/PerformParametricAnalysis;彈出對話框，選擇選項，如下圖單擊OK得結(jié)果如下:分析如下：(1b2從150增力口至IJ270,目標函數(shù)值從3780增加到4500,斜率6,

18、出基變量x2,進基變量Slack_c2;(2b2從270增加到工:，目標函數(shù)值保持4500不變（3b2從150減少到120,目標函數(shù)值從3780減少到3600,斜率6,出基變量x1,進基變量Slack_c1;（4b2從120減少到到0,目標函數(shù)值從3600減少到0,斜率30,出基變量x2。點擊Results/GraphicParametricAnalysis,4b2變化的參數(shù)分析圖4 .寫出對偶模型點擊菜單欄Format/SwitchtoDualForm,系統(tǒng)自動給出線性規(guī)劃的對偶模型，冉點擊一次給出原問題模型。5 .點擊Edit/InsertaContraint（插入一個約束）求解。6 .點

19、擊Edit/InsertaVariable；（插入一個變量）求解。7 .點擊Edit/DeleteaContraint（刪除一個約束）求解。8 .注意每一個問題都是針對原線性規(guī)化問題分析求解，每一步都必須回到原模型。操作技巧是，做完一個問題后退出所有活動窗口，打開存儲的原文件。實驗2整數(shù)規(guī)劃問題的WinQSB應(yīng)用實驗?zāi)康? .掌握利用WinQSB求解整數(shù)規(guī)劃（純整數(shù)、混合整數(shù)、0-1規(guī)劃；2 .掌握利用WinQSB求解分配問題的方法；3 .學會對利用WinQSB求得結(jié)果的解釋。實驗內(nèi)容1 .上機實習教材P106例1;并理解P114分支定界法、P116割平面法的求解過程。2 .上機實習教材P11

20、0例2;并理解匈牙利法的求解過程。實驗要求1 .給出P106例1的理論求解（分支定界法、割平面法。2 .給出P110例2的匈牙利法求解過程3 .完成【實現(xiàn)提示】中的所有操作，并合理組織寫出實驗報告。實現(xiàn)提示【提示1】WinQSB求解整數(shù)規(guī)劃的步驟例2-1某企業(yè)接受某項產(chǎn)品訂貨，需求量為每日3500千克，現(xiàn)有3種生成過程供選擇，各生產(chǎn)過程所需固定成本（投資、生產(chǎn)成本、最大日產(chǎn)量如下表生產(chǎn)過程的種類固定投資/元生產(chǎn)成本（兀/千克最大日產(chǎn)量（千克甲100052000乙200043000丙300034000問如何安排生產(chǎn)？1,采用第附4:產(chǎn)過程；設(shè).0,小采用第/種生產(chǎn)過程，xi為采用第i種生產(chǎn)過程生

21、產(chǎn)的數(shù)量，i=1,2,3.minz=I(KM)J,十2000y十3000M+5A+3a,*/x二+/>3500.£2000vt.<3000%<44KX)內(nèi)M-3拉y2&內(nèi)£加公/1,3=0,l;x(_3之0這是6個變量，7個約束的混合ILP問題。Step1啟動程序。開始程序/WinQSB/LinearandIntegerProgramming/File/NewProblem,選擇參數(shù)，則彈出如下界面按“OK”，在彈出的表中輸入數(shù)據(jù)，如下(1更改變量名。將x4、x5、x6改為y1、y2、y3。單擊Edit/VarivbleNames,在彈出的窗口更改

22、，結(jié)果如下：(2修改變量類型。按“OK”，在彈出的輸入數(shù)據(jù)表中雙擊y1,則y1的變量類型由連續(xù)型(Continnuous變?yōu)檎麛?shù)型(Integer,再雙擊一次則變?yōu)槎M制型(Binary。同樣將y2,y3變?yōu)槎M制。按模型要求，雙擊相應(yīng)的不等號，修改Direction。Step2將問題輸入系統(tǒng)。注意模型中的M用較大的數(shù)代替，如-9999.Step3求解問題。點擊SolveandAnalyze/SolvetheProblem果如下:由結(jié)果知:(1雖y2=1，但x2=0.0001所以最優(yōu)生產(chǎn)方式應(yīng)選第3種(y3=1，生產(chǎn)3500千克(x3=3500,總成本13500元(15500-2000=135

23、0。其中生產(chǎn)成本10500元，固定成本3000元。(2x1的縮減成本為2.5元，若增加使用第1種生產(chǎn)方式，每件增加變動成本2.5元，并增加固定成本1000元。若增加使用第2種生產(chǎn)方式，增加固定成本2000元。若增加使用第3種生產(chǎn)方式，將再增加固定成本3000元。(3由松弛變量可知，第3種生產(chǎn)方式生產(chǎn)能力尚有500千克剩余。若產(chǎn)量在增加500千克以內(nèi)時，固定成本不會發(fā)生變化。【提示2WinQSB求解分配問題的步驟例2-2有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、Do現(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所示，問如何分派任務(wù)，可使總時間

24、最少？任務(wù)ABC人員甲6711乙459丙3110丁598D2842Step1啟動程序。開始程序/WinQSB/NetworkModeling/File/NewProblem,選擇參數(shù)，則彈出如下界面選擇第3個問題類型，輸入任務(wù)和人員數(shù)。由于效率矩陣中行、列代表的是任務(wù)或人員可能不同，故NumberofObjects代表的是行數(shù)，NumberofAssignments代表的是列數(shù)。輸入相應(yīng)的值，并選取目標要求，單擊OK,彈出數(shù)據(jù)編輯窗口。Step2將問題輸入系統(tǒng)。(1修改人員、任務(wù)名稱：Edit/NodeNames在彈出的窗口操作，結(jié)果如下:(2輸入效率矩陣。單擊OK,輸入效率矩陣，如下:r-J

25、Step3求解問題。點擊SolveandAnalyze/SolvetheProblem,結(jié)果如下:即最優(yōu)的安排是甲完成任務(wù)D,乙完成任務(wù)A,丙完成任務(wù)B,丁完成任務(wù)C,總時間為15.說明：(1WinQsb求解分配問題，目標可以是最大化，也可以是最小化。人員數(shù)與任務(wù)數(shù)可以相等，也可不等。(2)點擊點擊SolveandAnalyze/SolvetheDisplaySteps-TableaU寸,系統(tǒng)輸出匈牙利解法的每一步迭代結(jié)果。(3點擊菜單欄Results/GraphicSolution,以網(wǎng)絡(luò)圖的形式顯示結(jié)果。實驗3動態(tài)規(guī)劃問題的WinQS而用實驗?zāi)康? .理解最短路問題、背包問題、生產(chǎn)與存儲問

26、題的動態(tài)規(guī)劃算法；2 .掌握利用WinQSB求解以上3類問題的方法；3 .學會對利用WinQSB求得結(jié)果的解釋。實驗內(nèi)容1 .上機實習教材P198例1;并理解動態(tài)規(guī)劃問題的解題思路。2 .上機實習教材P213例8;并掌握動態(tài)規(guī)劃求解背包問題的求解方法。3 .上機實習教材P210例6;并掌握動態(tài)規(guī)劃求解生產(chǎn)問題的求解方法。實驗要求1 .給出以上3個例題的理論求解。2 .完成【實現(xiàn)提示】中的所有操作，并合理組織寫出實驗報告。實現(xiàn)提示【提示1】WinQSB求解最短路問題的步驟Step1啟動程序。開始程序/WinQSB/DynamicProgramming/File/NewProblem,選擇參數(shù)最短

27、路問題（StagecoachShortestRouteProblem節(jié)點數(shù)（NumberofNodes,單擊OK。Step2單擊Edit/NodeNames,修改節(jié)點名稱，單擊OK,在彈出的數(shù)據(jù)窗口輸入數(shù)據(jù)（l鄰接矩陣。Step3點擊SolveandAnalyze/SolvetheProblem,求解該問題?！咎崾?】WinQSB求解背包問題的步驟【例3-1】一商販擬用一10噸載重量的大卡車裝載3種貨物，如下表，問如何組織裝載，可使總價值最大。貨物編號123單位重量（噸單位價值Step1啟動程序。開始程序/WinQSB/DynamicProgramming/File/NewProblem,選擇參數(shù)背包問題（KnapsackProblem,輸入