1、第5講 目 錄,CH1 線性規(guī)劃及單純形法 1.1 線性規(guī)劃問題及其數(shù)學模型 1.2 線性規(guī)劃問題的解 1.3 線性規(guī)劃的單純形法 1.3.1 單純形法的基本思路 1.3.2 確定初始基可行解 1.3.3 最優(yōu)性檢驗 1.3.4 基可行解的轉換 1.3.5 單純形法的步驟 1.4 單純形表 1.5 單純形法應用的幾個問題 1.6 線性規(guī)劃建模舉例,小結：線性規(guī)劃求解流程圖（P35),1.5 單純形法應用的幾個問題,1.5.1 大M法和兩階段單純形法 1.5.2 退化,1.5.2退化,若用規(guī)則確定換出變量時，有時存在兩個以上的最小比值，這樣在下一次迭代中就有一個或幾個基變量等于零，這就出現(xiàn)退化解

2、。當出現(xiàn)退化解時，會出現(xiàn)循環(huán)。 1974年勃蘭特(Bland)提出了一種簡便規(guī)則： (1) 選取j0中下標最小的非基變量xk為換入變量k=min(j| j0) (2)當按規(guī)則計算存在兩個和兩個以上最小比值時，始終選取下標最小的基變量換出變量。,1.6 線性規(guī)劃建模舉例,線性規(guī)劃技術應用廣泛：軍事、工業(yè)、農業(yè) 財富500強公司中，有85%使用線性規(guī)劃技術幫助決策企業(yè)決策：生產計劃、運輸、財務、營銷 建模步驟： 1.理解要解決的問題，了解解題的目標和條件； 2.定義決策變量（ x1 ，x2 ， ，xn ），每一組值表示一個方案； 3.用決策變量的線性函數(shù)形式寫出目標函數(shù)，確定最大化或最小化目標；

3、4.用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件,線性規(guī)劃求解工具簡介,Excel Solver Lindo Linear Interactive and Discrete Optimizer字首的縮寫，即“交互式的線性和離散優(yōu)化求解器” Lingo Linear Interactive and General Optimizer字首的縮寫，即“交互式的線性和通用優(yōu)化求解器” Matlab ,LINDO,可以用來求解線性規(guī)劃(LP-Linear Programming )、整數(shù)規(guī)劃( IP -Integer Programming )和 二次規(guī)劃(QP-Quadratic

4、Programming )問題. 這套軟件包由美國芝加哥大學的Linus Scharge教授于1980年前后開發(fā)，專門用于求解最優(yōu)化問題，后經不斷完善和擴充，并成立LINDO公司進行商業(yè)化運作，取得了巨大的成功。全球財富雜志500強的企業(yè)中，一半以上使用該公司產品，其中前25強企業(yè)中有23家使用該產品。 該軟件包功能強大，版本也很多，而我們 使用的只是演示版（試用版），演示版與正式版功能基本上是 類似的，只是能夠求解問題的規(guī)模受到限制，總變量數(shù)不超過30個，這在我們目前的使用過程中，基本上是足夠。,初試 LINDO,LINDO 中己假設所有的變量都是非負的,所以非負約束條件不必再輸入到計算機中

5、; LINDO 也不區(qū)分變量中的大小寫字符 ; 約束條件中的“=” 可用“” 代替.,解決一個簡單的線性規(guī)劃（LP）問題,其Lindo程序為：,例,現(xiàn)在我們用Lindo軟件來求解這個模型，單擊工具欄中的 圖標，便得到以下運行狀態(tài)窗口：,添加Lindo求解器,顯示結果如下,單純行法迭代兩次得到最優(yōu)解,最優(yōu)目 標值,最優(yōu)解各變量 的值,對偶價格,影子價格： 表示該非基變量增加一個單位而其他變量不變時目標函數(shù)減少的量（對max型問題）,松弛變量的值【緊約束】,單純行法進行兩次迭代,變量以字母開頭、不區(qū)分大小寫，變量名可不超過8個字符； 變量不能出現(xiàn)在約束條件的右端，右端只能是常數(shù)；變量與系數(shù)之間可以

6、有空格，但絕對不能有任何運算符； Lindo中不接受”（）“和逗號 ”，“等任何運算符號（除非在注釋語句中）； 模型中的表達式應當經過化，如不能出現(xiàn) （X+1）2 + 2X2 + 3Y，而應該寫成3X2+2X+3Y+1； 模型中已假定所有變量非負，可在模型的 ”end“語句后面用命令”free“取消變量的非負假定，其用法是在”free“后面跟變量名； 在模型的 ”end“語句后面可以用命令”SUB“設定變量的上界，用命令”SLB“設定變量的下界； Lindo中以“！”開始的是說明語句，說明語句也以“ ;” 結束。,使用Lindo軟件的一些注意事項：,例 有一家具制造車間,制造書桌(DESK)、

7、桌子(TABLE)、 椅子(CHAIR), 所用原料及木工、漆工的數(shù)據(jù)如表1所示 .,表 1,若要求桌子的生產量不超過 5 件,問如何安排三種產品的 產量可使收入最大 ?,用 分別表示書桌、桌子、椅子的生產量.建立LP 模型 :,LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 280.00000 VARIABLE VALUE REDUCED COST XI 2.000000 .000000 X2 .000000 5.000000 X3 8.000000 .000000 ROW SLACK OR SURPLUS DUAL PRICES

8、 2) 24.000000 .000000 3) .000000 10.000000 4) .000000 10.000000 5) 5.000000 .000000,LINDO在2次迭代后得到最優(yōu)解。,最優(yōu)目標值,最優(yōu)解,帶有松弛變量的最優(yōu)解,檢驗數(shù),例1某晝夜服務的公交線路每天各時間段內所需司機和乘務人員數(shù)如下： 設司機和乘務人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務人員，既能滿足工作需要，又配備最少司機和乘務人員?, 人力資源分配的問題,解：設 xi 表示第i班次時開始上班的司機和乘務人員數(shù),這樣建立如下的數(shù)學模型。 目標函數(shù)： Min x1 + x

9、2 + x3 + x4 + x5 + x6 約束條件：s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 0,例2一家中型的百貨商場，它對售貨員的需求經過統(tǒng)計分析如下表所示。為了保證售貨人員充分休息，售貨人員每周工作5天，休息兩天，并要求休息的兩天是連續(xù)的。問應該如何安排售貨人員的作息，既滿足工作需要，又使配備的售貨人員的人數(shù)最少？,解：設 xi ( i = 1,2,7)表示星期一至日開始休息的人數(shù),這樣我們建立如下的數(shù)學模型。 目標函數(shù)： Min x1 + x2 +

10、x3 + x4 + x5 + x6 + x7 約束條件： s.t. x1 + x2 + x3 + x4 + x5 28 x2 + x3 + x4 + x5 + x6 15 x3 + x4 + x5 + x6 + x7 24 x4 + x5 + x6 + x7 + x1 25 x5 + x6 + x7 + x1 + x2 19 x6 + x7 + x1 + x2 + x3 31 x7 + x1 + x2 + x3 + x4 28 x1,x2,x3,x4,x5,x6,x7 0,例3某公司面臨一個是外包協(xié)作還是自行生產的問題。該公司生產甲、乙、丙三種產品，都需要經過鑄造、機加工和裝配三個車間。甲、乙

11、兩種產品的鑄件可以外包協(xié)作，亦可以自行生產，但產品丙必須本廠鑄造才能保證質量。數(shù)據(jù)如表。問：公司為了獲得最大利潤，甲、乙、丙三種產品各生產多少件？甲、乙兩種產品的鑄造中，由本公司鑄造和由外包協(xié)作各應多少件？,生產計劃的問題,解：設 x1,x2,x3 分別為三道工序都由本公司加工的甲、乙、丙三種產品的件數(shù)，x4,x5 分別為由外協(xié)鑄造再由本公司加工和裝配的甲、乙兩種產品的件數(shù)。求 xi 的利潤：利潤 = 售價 - 各成本之和: 產品甲全部自制的利潤=23-(3+2+3)=15 產品甲鑄造外協(xié)，其余自制的利潤 =23-(5+2+3)=13 產品乙全部自制的利潤 =18-(5+1+2)=10 產品乙

12、鑄造外協(xié)，其余自制的利潤 =18-(6+1+2)=9 產品丙的利潤=16-(4+3+2)=7 可得到 xi （i = 1,2,3,4,5） 的利潤分別為 15、10、7、13、9 元。,通過以上分析,可建立如下的數(shù)學模型: 目標函數(shù)： Max 15x1 + 10 x2 + 7x3 + 13x4 + 9x5 約束條件： 5x1 + 10 x2 + 7x3 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 10000 x1,x2,x3,x4,x5 0,例4 某工廠要做100套鋼架，每套用長為2.9 m,2.1 m,

13、1.5 m的圓鋼各一根。已知原料每根長7.4 m，問：應如何下料，可使所用原料最?。?解： 共可設計下列5 種下料方案，見下表,設 x1,x2,x3,x4,x5 分別為上面 5 種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學模型。 目標函數(shù)： Min x1 + x2 + x3 + x4 + x5 約束條件： s.t. x1 + 2x2 + x4 100 2x3 + 2x4 + x5 100 3x1 + x2 + 2x3 + 3x5 100 x1,x2,x3,x4,x5 0,套裁下料問題,用“運籌學”軟件計算得出最優(yōu)下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。 即 x1

14、=30; x2=10； x3=0； x4=50； x5=0； 只需90根原材料就可制造出100套鋼架。 注意：在建立此類型數(shù)學模型時，約束條件用大于等于號比用等于號要好。因為有時在套用一些下料方案時可能會多出一根某種規(guī)格的圓鋼，但它可能是最優(yōu)方案。如果用等于號，這一方案就不是可行解了。,投資問題,例5 某部門現(xiàn)有資金200萬元，今后五年內考慮給以下的項目投資。已知：項 目A：從第一年到第五年每年年初都可投資，當年末能收回本利110%；項目B：從第 一年到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額 不能超過30萬元；項目C：需在第三年年初投資，第五年末能收回本利140

15、%，但規(guī) 定最大投資額不能超過80萬元；項目D：需在第二年年初投資，第五年末能收回本 利155%，但規(guī)定最大投資額不能超過100萬元。 據(jù)測定每萬元每次投資的風險指數(shù)如右表： 問： a）應如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利金額為最大？ b）應如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利在330萬元的基礎上使得其投資總的風險系數(shù)為最?。?解： 1）確定決策變量：連續(xù)投資問題 設 xij ( i = 15，j = 14)表示第 i 年初投資于A(j=1)、B(j=2)、C(j=3)、D(j=4)項目的金額。這樣我們建立如下的決策變量： A x11 x21 x3

16、1 x41 x51 B x12 x22 x32 x42 C x33 D x24,2）約束條件： 第一年：A當年末可收回投資，故第一年年初應把全部資金投出去，于是 x11+ x12 = 200； 第二年：B次年末才可收回投資，故第二年年初有資金1.1 x11，于是 x21 + x22+ x24 = 1.1x11； 第三年：年初有資金 1.1x21+ 1.25x12，于是 x31 + x32+ x33 = 1.1x21+ 1.25x12； 第四年：年初有資金 1.1x31+ 1.25x22，于是 x41 + x42 = 1.1x31+ 1.25x22； 第五年：年初有資金 1.1x41+ 1.25

17、x32，于是 x51 = 1.1x41+ 1.25x32； B、C、D的投資限制： xi2 30 ( i =1、2、3、4 )，x33 80，x24 100 3）目標函數(shù)及模型： a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32； xi2 30 ( i =1、2、3、4 )，x33 80，x24 1

18、00 xij 0 ( i = 1、2、3、4、5；j = 1、2、3、4）,投資問題,b)所設變量與問題a相同，目標函數(shù)為風險最小，有 Min f =x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24 在問題a的約束條件中加上“第五年末擁有資金本利在330萬元”的條件， 于是模型如下： Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+

19、1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32； xi2 30 ( i =1、2、3、4 )，x33 80，x24 100 1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 330 xij 0 ( i = 1、2、3、4、5；j = 1、2、3、4）,投資問題,教材例題:P40P42 配料問題 生產存貯問題,第1章 線性規(guī)劃與單純形法 （小結）,1.線性規(guī)劃的概念 （1）線性規(guī)劃模型的構成 決策變量 目標函數(shù)：max(min) Z(是決策變量的線性函數(shù)） 約束條件：s.t. （滿足于含決策變量的線性等式或不等式）,（2）一般形式：,max =c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn=b1 a21x1+a22