《運籌學教程》胡云權(quán) 第五版 運籌學--線性規(guī)劃--3excel 線性規(guī)劃及應(yīng)用.pptx

1、,第一章 線性規(guī)劃,主要內(nèi)容,線性規(guī)劃問題及其數(shù)學模型 線性規(guī)劃解的概念、圖解法 單純形法原理及步驟 Excel求解和線性規(guī)劃應(yīng)用,線性規(guī)劃數(shù)學模型標準型矩陣式：,可行解：滿足約束條件(1.2)和非負條件(1.3)的解稱為可行解。 可行域：可行解的集合。 最優(yōu)解：滿足條件(1.1)的可行解。,(1.1),(1.2),(1.3),線性規(guī)劃標準型解的概念,基矩陣（基）：設(shè)A是 階系數(shù)矩陣( )，秩A=m，則A中一定存在m個線性無關(guān)的列向量，稱由m個線性無關(guān)的列向量構(gòu)成的可逆矩陣 為問題L的一個基，L最多有 個基。系數(shù)矩陣A中的m階可逆子陣，記為B。其余為非基矩陣，記為N。 基向量：基矩陣B中的列，

2、其余為非基向量。 基變量：與基矩陣B中列向量所對應(yīng)的變量為基變量，記為 ，其余變量為非基變量，記為 。,線性規(guī)劃標準型解的概念,線性規(guī)劃標準型解的概念,基解：當A中的基B取定后，不妨設(shè)B表示A中的前m列，則可 記 ，相應(yīng)地 , 約束條件AX=b可表示為 ，即 ，當取 時，則 為線性規(guī)劃問題LP的基解。P20 基解的非零分量個數(shù) m，當m時，則此基解是退化解，這種現(xiàn)象不多。 一個基解是由一個基來決定的，并未要求非負，因此未必可行。 基可行解：若B對應(yīng)的基解中滿足 ，則稱該解為基本可 行解，稱B為可行基。,線性規(guī)劃問題的可行域為凸集（定理1）； 凸集的每個頂點對應(yīng)一個基可行解（定理2），基可行解的

3、個數(shù)是有限的，當然凸集的頂點個數(shù)也是有限的； 若線性規(guī)劃有最優(yōu)解，必在可行域某頂點上達到，（定理3）亦即在有限個基可行解中間存在最優(yōu)解。,基本定理,，,由于基可行解數(shù)目有限（ ），因此，經(jīng)過有限次迭代即可找到最優(yōu)解。 前提：線性規(guī)劃為標準型。,單純形法基本步驟,求初始基可行解 確定換入變量的最優(yōu)性條件 確定換出變量的可行性條件 運用初等行變換求出新的基 可行解,例2 用單純形法求解線性規(guī)劃問題,單純形法求解,解：（1）轉(zhuǎn)化為標準型, ,主元素,線性規(guī)劃最優(yōu)解的幾種情況,定理4：（無界解）若對某可行基B，若存 在 ，則該線性規(guī)劃問題無有限最 優(yōu)解（或稱無最優(yōu)解、無界解）。 證明： 設(shè)此時對應(yīng)的目

4、標函數(shù)值為Z0，基可行解為 , 則有 即二者乘積所得列向量的每個元素 小于 等于0，,構(gòu)造新的解 ,其分量為：,驗證它滿足等式約束：,又因為： 所以：,再驗證它滿足非負約束 由于 所以對于任意的 ， 都是可行解。 把 帶入目標函數(shù)中得：,由于 大于0，故 ， 即該問題得目標函數(shù)無界。,教材P35,單純形法小結(jié),作 業(yè),使用EXCEL求解線性規(guī)劃,一個簡單的例子,某工廠計劃生產(chǎn)兩種產(chǎn)品，利潤分別為2和3，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時和A、B兩種原材料的消耗，如表,目標是不超過資源限制的情況下，確定兩產(chǎn)品產(chǎn)量，得到最大利潤。,建立數(shù)學公式（步驟一）,在工作表的頂部輸入數(shù)據(jù) 確定每個決策變量所對應(yīng)

5、的單元格位置 選擇單元格輸入公式，找到目標函數(shù)的值 確定約束單元格輸入公式，計算每個約束條件左邊的值 確定約束單元格輸入公式，計算每個約束條件右邊的值,可采用 復制粘貼 或 直接輸入 的方式導入數(shù)據(jù)。,在工作表的頂部輸入數(shù)據(jù) 確定每個決策變量所對應(yīng)的單元格位置 選擇單元格輸入公式，找到目標函數(shù)的值 選擇一個單元格輸入公式，計算每個約束條件左邊的值 選擇一個單元格輸入公式，計算每個約束條件右邊的值,圖中，規(guī)定B12、C12為可變單元格,可變單元格存放決策變量的取值，可變單元格數(shù)目等于決策變量個數(shù),建立數(shù)學公式（步驟二）,在工作表的頂部輸入數(shù)據(jù) 確定每個決策變量所對應(yīng)的單元格位置 選擇單元格輸入公

6、式，找到目標函數(shù)的值 確定約束單元格輸入公式，計算每個約束條件左邊的值 確定約束單元格輸入公式，計算每個約束條件右邊的值,在目標單元格中，需要填入計算目標函數(shù)值的公式。,建立數(shù)學公式（步驟三）,在工作表的頂部輸入數(shù)據(jù) 確定每個決策變量所對應(yīng)的單元格位置 選擇單元格輸入公式，找到目標函數(shù)的值 確定約束單元格輸入公式，計算每個約束條件左邊的值 確定約束單元格輸入公式，計算每個約束條件右邊的值,在約束單元格中，需要填入計算約束函數(shù)值的公式。,建立數(shù)學公式（步驟四）,在工作表的頂部輸入數(shù)據(jù) 確定每個決策變量所對應(yīng)的單元格位置 選擇單元格輸入公式，找到目標函數(shù)的值 確定約束單元格輸入公式，計算每個約束條

7、件左邊的值 確定約束單元格輸入公式，計算每個約束條件右邊的值,建立數(shù)學公式（步驟五）,調(diào)用 “規(guī)劃求解” 模塊,選擇工具下拉菜單 選擇規(guī)劃求解選項（事先需用Office安裝盤安裝規(guī)劃求解的功能）,填寫目標單元格和可變單元格,出現(xiàn)規(guī)劃求解參數(shù)對話框 在目標單元格中輸入B14 在等于選擇最大 在可變單元格中輸入B12:C12 選擇添加,在上圖顯示的界面中，需要輸入目標單元格、可變單元格，添加約束條件，另外還可能需要進行選項設(shè)置。,添加約束,在添加約束對話框中，在單元格引用位置中輸入B17，選擇=，在約束值中輸入D17。選擇添加 第三個條件添加完畢后，選擇確定 當規(guī)劃求解參數(shù)對話框重新出現(xiàn)時，選擇選

8、項,“選項”設(shè)置,當選項對話框出現(xiàn)時，選擇假設(shè)非負。選擇確定,用Excel求解,出現(xiàn)規(guī)劃求解參數(shù)對話框，選擇求解。,保存求解結(jié)果,當求解結(jié)果對話框出現(xiàn)時，選擇保存規(guī)劃求解結(jié)果。選擇確定。,線性規(guī)劃應(yīng)用,線性規(guī)劃可以應(yīng)用在管理、經(jīng)濟、金融、戰(zhàn)爭、通訊、工程設(shè)計等各個領(lǐng)域。很多決策問題可以抽象為線性規(guī)劃模型。線性規(guī)劃方法的應(yīng)用為社會帶來了無法估量的巨大效益。 材料利用、混合配料、產(chǎn)品計劃、 連續(xù)投資、人員安排 ,30,1、材料利用問題,現(xiàn)要做100 套鋼架,每套用長為2.9m , 2.1m 和1.5m的元鋼各一根制成。已知原料長7.4米，問應(yīng)如何下料，使用的原材料最省？,1、材料利用問題,2、生產(chǎn)

9、存儲問題,電扇廠每月最多可生產(chǎn)3000臺電扇，每臺成本100元。如果當月銷售不了，那么每臺每月要支付10元的存儲費。設(shè)4、5、6月的銷售量預(yù)計為1000臺、2500臺和4000臺。已知4月初沒留有存貨，也不要求6月底留下存貨。問如何安排4、5、6月的生產(chǎn)計劃，可使得總的生產(chǎn)、存儲費最低？,【解】設(shè)4、5、6月份分別生產(chǎn)x1、x2、x3臺,2、生產(chǎn)存儲問題,某晝夜服務(wù)的公交線路每天各時間區(qū)段內(nèi)所需四級和乘務(wù)人員數(shù)如下表所示。問該公交線路至少配備多少名司機和乘務(wù)人員？,3、人員分配問題,【解】設(shè)xi (i=1，2，6)名司機和乘務(wù)員第i班次開始上班，則,3、人員分配問題,設(shè)有A1，A2，A3三個產(chǎn)

10、地，生產(chǎn)某種物質(zhì)，其產(chǎn)量分別為7，5，7，B1，B2，B3，B4四個銷地，需要該物資，銷量分別為2，3，4，6，又已知各產(chǎn)銷地之間的運價如下表，確定總運費最少的調(diào)運方案。,單位運價表,4、運輸問題,A1,A2,A3,B1,B2,B3,B4,銷地,產(chǎn)地,運輸問題示意圖,4、運輸問題,5、動態(tài)投資問題（1）,5、動態(tài)投資問題（1）,5、動態(tài)投資問題（2）,某部門現(xiàn)有資金200萬元，今后五年內(nèi)考慮給以下的項目投資。已知： 項目A：從第一年到第五年每年年初都可投資，當年末能收回本利110%； 項目B：從第一年到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不能超過30萬元； 項

11、目C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超過80萬元； 項目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過100萬元； 如何確定這些項目每年投資額，使得第五年年末本利金額最大？,【解】 設(shè) xij ( i = 1 - 5，j = 1、2、3、4)表示第 i 年初投資于A(j=1)、B(j=2)、C(j=3)、D(j=4)項目的金額。這樣我們建立如下的決策變量： A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x24,5、動態(tài)投資問題（2）,目標函數(shù)： Max z = 1.1x51+

12、1.25x42+ 1.4x33 + 1.55x24,第一年：A當年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是 x11+ x12 = 200； 第二年：B次年末才可收回投資故第二年年初的資金為 1.1x11，于是 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.25x32，于是 x51 = 1.1x41+ 1

13、.25x32； B、C、D的投資限制： xi2 30 ( I =1、2、3、4 )，x33 80，x24 100 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 100 xij 0 ( i = 1、2、3、4、5；j = 1、2、3、4）,5、動態(tài)投資問題（2）,6、混合配料問題,6、混合配料問題,45,6、混合配料問題,46,

14、7、種植計劃問題,【解】設(shè)種植大豆、玉米、小麥分別為x1、x2、x3畝，飼養(yǎng)奶牛x4頭、雞x5只，春夏季和秋冬季外出幫工分別x6、 x7為工時。,Max Z =50 x1 +80 x2+40 x3+400 x4+10 x5 +0.5x6+0.4 x7 x1 + x2 + x3+ 1.5x4 40 (土地約束) 400 x4+3x5 2500 (資金約束) 20 x1 +35x2+10 x3+50 x4 +0.3x5 +x6 =4000 (春夏勞力) 50 x1 +75x2+40 x3+100 x4+0.6x5 +x7 =3500 (秋冬勞力) x4 8 (牛舍約束) x5 300 (雞舍約束)

15、 x1,x2,x3,x4,x5,x6 ，x7 0,7、種植計劃問題,8、購銷倉儲問題,8、購銷倉儲問題,【解】設(shè)冬季購進冬、春、夏、秋季售出的木材數(shù)量分別為x11、 x12、 x13 、x14萬立米, 春季購進春、夏、秋季售出的木材數(shù)量分別為 x22、 x23 、x24萬立米, 夏季購進夏、秋季售出的木材數(shù)量分別為 x33 、x34萬立米, 秋季購進秋季售出的木材數(shù)量為x44萬立米。,Max Z= (321-310)x11 + (333-310-17)x12 + (352-310-27)x13 + (344-310-37)x14 + (333-325)x22 + (352-325-17)x23

16、 + (344-325-27)x24 + (353-348)x33 + (344-348-17)x34 + (344-340)x44,50,x12 + x13 + x14 20 (冬季存貯約束) x13 + x14 + x23 + x24 20 (春季存貯約束) x14 + x24 + x34 20 (夏季存貯約束) x1110 (冬季銷售約束) x12 + x22 14 (春季銷售約束) x13 + x23 + x33 20 (夏季銷售約束) x14 + x24 + x34 + x44 16 (秋季銷售約束) xij 0 , i=1,2,3,4, j=1,2,3,4,8、購銷倉儲問題,9、年

17、度生產(chǎn)計劃問題,某公司生產(chǎn)某種產(chǎn)品，他們每年要對下一年的市場需求做出預(yù)測，并據(jù)此做出明年每個月的生產(chǎn)和存貯計劃。根據(jù)調(diào)查，明年的市場需求如下表： 該公司認為市場需求必須滿足。在安排生產(chǎn)時，公司可采取以下措施 正常生產(chǎn)和加班生產(chǎn)： 每個工人每月的正常產(chǎn)量為20件； 每個工人每月的加班產(chǎn)量不超過6件，每加班生產(chǎn)一件要增加費用20美元。,增加和減少工人： 通過增加或減少工人調(diào)節(jié)產(chǎn)量，相鄰兩月工人增加或減少不能超過40人； 每次增加一個工人要支付300美元費用； 每次減少一個工人要支付420美元費用。 存貯： 倉儲產(chǎn)品和當月生產(chǎn)的產(chǎn)品可供市場，剩余產(chǎn)品可存貯在倉庫里； 每月每件產(chǎn)品的存貯費用為8美元，

18、以月底的存貯量結(jié)算存貯費用。 現(xiàn)預(yù)計今年年底的工人數(shù)為290人，倉庫存貯量為0件，并要求明年年底倉庫存貯量也為0件。公司希望以總費用最低為目標，作一個明年的生產(chǎn)和存貯計劃。,9、年度生產(chǎn)計劃問題,記明年j月份的需求量為d j件。 設(shè)明年j月份的正常產(chǎn)量為xj件，加班產(chǎn)量為yj件，倉庫存貯量為zj，工人數(shù)為sj人，增加或減少工人的費用為tj美元。 總費用：Cost = j=1,2,12 (20yj + 8zj + tj) 正常產(chǎn)量：xj = 20sj (j=1,2,12) 加班產(chǎn)量：yj 6sj(j=1,2,12) 工人數(shù)增減：sj sj-1 40(j=1,2,12) sj-1 sj 40(j=1,2,12) 工人數(shù)增減費用：tj 300(sj sj-1)(j=1,2,12)