運籌學課程設計指導書

1、課程設計指導書【預備實驗】一 LINDO的基本操作一實驗目的1.熟悉LINDO軟件的操作界面。2.掌握LINDO中的基本語法。二實驗原理本實驗使用LINDO 6.01進行操作。LINDO（Linear Interactive and Discrete Optimizer）是一種專門用于求解數學規(guī)劃問題的軟件包。由于LINDO執(zhí)行速度很快、易于方便輸入、求解和分析數學規(guī)劃問題，因此在數學、科研和工業(yè)界得到廣泛應用。LINDO主要用于解線性規(guī)劃、非線性規(guī)劃、二次規(guī)劃和整數規(guī)劃等問題。也可以用于一些非線性和線性方程組的求解以及代數方程求根等。LINDO中包含了一種建模語言和許多常用的數學函數（包括大

2、量概論函數），可供使用者建立規(guī)劃問題時調用。一般用LINDO解決線性規(guī)劃（LPLinear Programming），整數規(guī)劃（IPInteger Programming）問題。其中LINDO 6 .01 學生版至多可求解多達100個變量和50個約束的規(guī)劃問題。其正式版（標準版）則可求解的變量和約束在104量級以上。要學好用這個軟件最好的辦法就是學習它自帶的HELP文件。三實驗設備與器件1.安裝win98系統以上的計算機。2.LINDO 6.01或更高版本的軟件。四實驗預習要求1.在網上下載LINDO軟件。2.自學LINDO軟件help文檔中的操作界面部分。五、實驗內容及實驗步驟1.安裝LIN

3、DO軟件到D:LINDO。2.LINDO的基本語法。與MATLAB等工具一樣，LINDO對所求解問題的描述也有自身的一套規(guī)則。LINDO的基本程序架構如下：MAX 目標函數表達ST 變量約束1 變量約束2 變量約束3 END3.簡單的示例假設現在一個計算機廠商要生產兩種型號的PC：標準型(standard)和增強型(turbo)，由于生產線和勞動力工作時間的約束，使得標準型PC最多生產100臺。增強型PC最多生產120臺；一共耗時勞動力時間不能超過160小時。已知每臺標準型PC可獲利潤$100，耗掉1小時勞動力工作時間；每臺增強型PC可獲利潤$150，耗掉2小時勞動力工作時間。請問：該如何規(guī)劃

4、這兩種計算機的生產量才能夠使得最后獲利最大？這個問題是標準的線性規(guī)劃，目標函數是100*standard+150*turbo最大！lindo的程序如下：max 100 standard+150 turbost standard<=100 turbo<=120 standard+2 turbo<=160end然后再按運算符鍵即可得結果。運行結果如下：LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 14500. VARIABLE VALUE REDUCED COST STANDARD 100.000000 0.0000

5、00 TURBO 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 25.000000 3) 90.000000 0.00000 4) 0.000000 75.000000 NO. ITERATIONS= 2注解：第一行告知線性優(yōu)化步數為2，下面是目標函數值=14500，在standard=100/turbo=30時取到；下面是對偶值。六實驗報告要求（可選）1.將實驗中對例子求解的步驟詳細寫在報告里。二 線性規(guī)劃問題一實驗目的1. 掌握對線性規(guī)劃問題的數學模型抽象。2. 掌握對線性規(guī)劃問題的求解方法。3. 掌握用LI

6、NDO求解該問題的基本步驟。4. 學會分析LINDO的計算結果。二實驗原理線性規(guī)劃常見可以解決資源分配問題，成本效益平衡問題。在求解線性規(guī)劃時，常用的方法有圖解法和單純形法。單純形法基本思路是：先找出一個基本可行解,判斷其是否為最優(yōu)解,如果不是最優(yōu)解，則轉換到相鄰的基本可行解,并使目標函數值不斷增大,直到找出最優(yōu)解或判斷有無界解、無解為止。三實驗預習要求1 復習解線性規(guī)劃問題的步驟。2 了解線性規(guī)劃問題的基本寫法。四實驗內容與實驗步驟利用所學知識，利用LINDO求解下列兩個問題：問題1 試驗一中的實例。問題2 一個企業(yè)需要同一種原材料生產甲乙兩種產品，他們的單位產品所需要的原材料的數量，以及所

7、消耗的加工時間各不相同，從而所獲得的利潤也不相同，如下表所示。那么，該企業(yè)應如何安排生產計劃，才能使獲得的利潤最大？表 2.1產品/資源甲乙可利用的資源原材料（t）23100加工時間（h）42120單位利潤（×100元）64求解步驟：1 抽象出數學表達式，照標準格式書寫。2 將表達式按LINDO的語法規(guī)則輸入到該軟件中。3 進行求解。4 對實驗數據進行分析。五實驗報告要求（可選）1 寫出問題2的常規(guī)數學表達式和在LINDO中的語法表達。2 將LINDO的求解結果寫在實驗報告里。三 靈敏度分析一實驗目的1掌握靈敏度分析原理和方法，能夠對目標函數系數和右邊常數進行靈敏度分析。2掌握增加一

8、個變量，增加一個約束后求新的最優(yōu)解的方法。二實驗原理靈敏度分析是要在求得最優(yōu)解以后，解決以下幾方面的問題：1 線性規(guī)劃問題中的各系數在什么范圍內變化，不會影響已獲得的最優(yōu)基。2 如果系數的變化超過以上范圍，如何在原來最優(yōu)解的基礎上求得新的最優(yōu)解3 當線性規(guī)劃問題增加一個新的變量或新的約束，如何在原來最優(yōu)解的基礎上獲得新的最優(yōu)解。三實驗內容本次實驗將分別討論下列數據或條件變化時對于最優(yōu)基（最優(yōu)解）的靈敏度分析：l 目標函數的變化；l 右端常數的變化；l 增加新變量或新的約束條件的變化；l 目標系數或右端項包含參數的變化。依次針對上面的四個條件對下面的幾個例子進行靈敏度分析：例3.1 線性規(guī)劃問題

9、為minz=-2x1+x2-x3s.t.x1+x2+x36-x1+2x24x1,x2,x30求c2=1在什么范圍內變化，原來的最優(yōu)基保持不變；當c2=-3時，最優(yōu)基是否變化，如果變化，求新的最優(yōu)基和最優(yōu)解。例3.2 在線性規(guī)劃問題中，對c1=1進行靈敏度分析。minz=x1+x2-4x3s.t.x1+x2+2x39x1+x2-x32-x1+x2+x34x1,x2,x30例3.3 對以下線性規(guī)劃問題中第一個約束右邊常數b1=9進行靈敏度分析。minz=x1+x2-4x3s.t.x1+x2+2x39x1+x2-x32-x1+x2+x34x1,x2,x3³0例3.4 在例3.1minz=-

10、2x1+x2-x3s.t.x1+x2+x3£6-x1+2x2£4x1,x2,x3³0中，增加一個新的變量x6，它在目標函數中的系數c6=1，在約束條件中的系數向量為，求新的最優(yōu)基和最優(yōu)解。例3.5 設線性規(guī)劃問題為minz=-2x1+x2-x3s.t.x1+x2+x3£6-x1+2x2£4x1,x2,x3³0最優(yōu)單純形表為zx1x2x3x4x5RHSz10-3-1-20-12x10111106x500311110增加一個約束-x1+2x22，求新的最優(yōu)基和最優(yōu)解。四試驗報告要求（可選）將上述問題的LINDO求解結果寫在報告里。四 整數

11、規(guī)劃一實驗目的1.掌握整數規(guī)劃的基本數學模型。2.熟悉解的特點。3.能夠用LINDO求解一般整數規(guī)劃問題。4.培養(yǎng)對模型和解結果進行分析的能力。二實驗原理整數規(guī)劃簡介：整數線性規(guī)劃數學模型的一般形式為: 整數線性規(guī)劃問題可以分為下列幾種類型：1. 純整數線性規(guī)劃(Pure integer linear programming)：指全部決策變量都必須取整數值的整數線性規(guī)劃。有時，也稱為全整數規(guī)劃。2. 混合整數線性規(guī)劃(Mixed integer linear programming）：指決策變量中有一部分必須取整數值，另一部分可以不取整數值的整數線性規(guī)劃。3. 0-1型整數線性規(guī)劃(Zero-

12、one integer linear programming)：指決策變量只能了取值0或1的整數線性規(guī)劃。三實驗內容與步驟求解下面的整數規(guī)劃問題：1.某服務部門各時段（每2小時為一時段）需要的服務人數見表4-2。按規(guī)定，服務員連續(xù)工作8小時（即四個時段）為一班?，F要求安排服務員的工作時間，使服務部門服務員總數最少。表 4.1時 段12345678服務員最少數目108911138532.人力資源分配問題某個中型百貨商場對售貨人員（周工資200元）的需求經統計如下表:表 4.2星期一二三四五六七人數12151214161819為了保證銷售人員充分休息，銷售人員每周工作5天，休息2天。問應如何安排銷

13、售人員的工作時間，使得所配售貨人員的總費用最?。壳蠼獠襟E：1.弄清楚所求解的問題。2.抽象出數學模型。3.輸入到LINDO里求解。4.分析實驗結果。四實驗報告要求（可選）1.分別對所求的問題進行分析和建模，列出因素、方案、變量、約束條件、目標函數和計算模型2.用LINDO軟件對該計算模型進行求解并分析其結果?！揪C合實驗】（必做）一實驗目的鍛煉應用所學知識解決綜合性問題的能力二實驗內容任選一題，可4-5人組隊解決。A. 線材切割問題  在很多工程領域，都有線材切割問題。這一問題可表述為:設能購買到的不同長度的原線材有m種，長度分別為L1,.,Lm，這些原線材只是長度不同，其它都相同。某

14、工程中所要切割出的線材長度分別為li,i=1,2,.,n(這里 li < 所有Li)，對應數量分別為Ni,i=1,2,.,n。設計優(yōu)化計算方案，求出分別需要購買多少根不同長度的原線材,并能給出切割方案及線材利用率。 現假設某裝修工程中需要對鋁合金線材進行切割，工程能購買到的同一規(guī)格的鋁合金線材有二種長度，一種長度是8米，另一種是12米?，F在假設要切割長度和數量如下所示的鋁合金線材：表 5.1編號長度(單位:米)數量(單位:根)16.209023.6012032.8013641.8531050.7521560.55320應用所設計的計算方案，請問至少需要購買多少根8米和12米的線材，使浪費的線材比較少，并給出切割方案和計算線材利用率。B. 板材切割問題  設工程中能購買到的原板材的長、寬分別為X、Y；現要切割長度和寬度分別為xi,yi, i = 1,2,.,m 共m種大小的板材，每種板材的所需數量分別為N1,N2,.,Nm塊給出一個切割算法，盡量使購買的板材數量少，并給出切割方案和計算板材利用率。利用所設計計算方案，對下列假設數據，計算需要購買多少塊原板材，并給出切割方案和計算板材利用率。原板材長2.85米，寬1.55米。 所需板材: 表 5.2編號長度(單位:米)寬度(單位:米)數量(單位:塊)1