運籌學B線性規(guī)劃課件

1、第1章 線性規(guī)劃7/29/20221第1章 線性規(guī)劃Sub title內容提要第一節(jié) 線性規(guī)劃的一般模型一、線性規(guī)劃模型的舉例二、LP模型的要素及特征三、線性規(guī)劃的圖解方法四、線性規(guī)劃解的可能性第二節(jié) 線性規(guī)劃的單純形法一、線性規(guī)劃的標準型式二、線性規(guī)劃之解的概念三、單純形法的基本原理7/29/20222第一節(jié) 線性規(guī)劃的一般模型 線性規(guī)劃(Linear Programming，LP)是運籌學的重要分支之一，研究較早、發(fā)展較快、方法較成熟，而且是眾多分支的基礎，借助計算機計算更方便，應用更廣泛。 線性規(guī)劃通常研究資源的最優(yōu)利用、設備最佳運行以及費用最低等問題。例如，當任務或目標確定后，如何統(tǒng)籌

2、兼顧，合理安排，用最少的資源 （如資金、設備、原標材料、人工、時間等）去完成確定的任務或目標；企業(yè)在一定的資源條件限制下，如何組織安排生產獲得最好的經濟效益（如產品量最多 、利潤最大）。7/29/20223【例】生產計劃問題。 某企業(yè)在計劃期內計劃生產甲、乙、丙三種產品。這些產品分別需要在設備A、B上加工，需要消耗材料C、D，按工藝資料規(guī)定，單件產品在不同設備上加工及所需要的資源如表1.1所示。已知在計劃期內設備的加工能力各為200小時，可供材料分別為360、300公斤；每生產一件甲、乙、丙三種產品，企業(yè)可獲得利潤分別為40、30、50元，假定市場需求無限制。問：企業(yè)決策者應如何安排生產計劃，

3、使企業(yè)在計劃期內總的利潤最大？第一節(jié) 線性規(guī)劃的一般模型 一、線性規(guī)劃模型的舉例 7/29/20224 產品 資源 甲 乙丙現有資源設備A 3 1 2 200(h)設備B 2 2 4 200(h)材料C 4 5 1 360(kg)材料D 2 3 5 300(kg)利潤（元/件） 40 30 50表1.1 某企業(yè)單位產品資源消耗及利潤x1x1x1x1x1x2x2x2x2x2x3x3x3x3x37/29/20225【解】設x1、x2、x3 為甲、乙、丙三種產品的產量，則該線性規(guī)劃問題的數學模型為： 產品 資源 甲 乙 丙現有資源設備A 3 1 2 200設備B 2 2 4 200材料C 4 5 1

4、 360材料D 2 3 5 300利潤（元/件） 40 30 50最優(yōu)解：X*=(50, 30, 10)T，Z*=3400，即在計劃期內甲、乙、丙產量分別為50、30和10件，利潤最大，為3400元。注意：最優(yōu)解的表達方式！7/29/20226二、線性規(guī)劃的三個要素 第一節(jié) 線性規(guī)劃的一般模型 決策變量（一組）決策問題待定的量值取值要求非負約束條件（一組）任何管理決策問題都是限定在一定的條件下求解把各種限制條件表示為一組等式或不等式稱約束條件約束條件是決策方案可行的保障約束條件是決策變量的線性函數目標函數（一個）衡量決策優(yōu)劣的準則，如時間最省、利潤最大、成本最低目標函數是決策變量的線性函數有的

5、目標要實現極大，有的則要求極小7/29/20227 練習1.1 某廠生產甲、乙兩種產品，生產工藝路線為：各自的零部件分別在設備A、B加工，最后都需在設備C上裝配。經測算得到相關數據如下表所示，單位甲、乙產品的銷售價格分別為73和75元。問應如何制定生產計劃，才能使總利潤為最大？ 產品設備工時消耗甲 乙工時成本(元/h)生產能力(h)ABC 2 0 0 2 3 4 20 15 10161032x1x1x1x2 x2x22030247/29/20228(1)決策變量：設x1為甲產品的產量，x2為乙產品的產量。(2)約束條件：生產受設備能力制約，不能突破有效供給量。設備A的約束條件表達為 2x1 1

6、6同理，設備B的加工能力約束條件表達為 2x2 10設備C的裝配能力也有限，其約束條件為 3x1+ 4x2 32(3)目標函數：目標是企業(yè)利潤最大化 max Z = 3x1 + 5x2 (4)非負約束：甲乙產品的產量為非負 x1 0， x2 0LP模型：s.t. (subject to) 使?jié)M足，使服從7/29/20229練習1.2：某廠生產甲、乙兩種產品，均需在A、B、C三種不同的設備上加工，單位產品加工所需工時、銷售后能獲得的利潤及設備有效工時數見下表。問：如何安排生產計劃，才能使該廠獲得總利潤最大？ 解: 設甲、乙產品產量分別 為x1、x2 公斤， 設總利潤為Z，則： max Z = 7

7、0 x130 x2 設備產品 ABC利潤甲 乙3955937030限時 540450720 設備可用工時數限制 3x1 + 9x2 540 5x1 + 5x2 450 9x1 + 3x2 720max Z = 70 x130 x2 3x1 + 9x2 540 s.t. 5x1 + 5x2 450 9x1 + 3x2 720 x1 , x2 07/29/202210線性規(guī)劃的數學模型由決策變量 Decision variables 目標函數 Objective function 構成，稱為三要素。約束條件 Constraints其主要特征是：1. 解決的問題是規(guī)劃問題；2解決問題的目標函數是多個

8、決策變量的 線性函數，通常是求最大值或最小值；3解決問題的約束條件是多個決策變量 的線性不等式或等式。怎樣辨別一個模型是線性規(guī)劃模型？7/29/202211二、線性規(guī)劃模型的舉例 2、物資運輸問題例：某產品商有三個供貨源A1、A2、A3，其經銷商有4個（需求市場）B1、B2、B3、B4。已知各廠的產量、各經銷商的銷售量及從 Ai 到 Bj 的單位運費為Cij。問如何調配運輸方案，使總運費最??？ 銷地產地B1B2B3B4產量A16 32550A27 5 8 4 20A33 2 9 7 30銷量20301040 x11x12x13x14x21x22x23x24x31x32x33x34產銷平衡(產量

9、等于銷量)7/29/202212(1)決策變量：設從 Ai 到 Bj 的運輸量為 xij ，(2)目標函數：運費最小的目標函數為：minZ = 6x11 + 3x12 + 2x13 + 5x14 + 7x21 + 5x22 + 8x23 + 4x24 + 3x31 + 2x32 + 9x33 + 7x34 (3)約束條件：產量之和等于銷量之和，故要滿足：供應平衡條件x11+x12+x13+x14=50 x21+x22+x23+x24=20 x31+x32+x33+x34 =30銷售平衡條件x11+x21+x31=20 x12+x22+x32=30 x13+x23+x33=10 x14+x24+

10、x34=40非負約束 xij0 (i=1,2,3；j=1,2,3,4) 4.5 線性規(guī)劃的數學模型由三個要素組成：7/29/202213【練習】現有A1，A2，A3三個產糧區(qū)，可供應糧食分別為10，8，5(萬噸)，現將糧食運往B1，B2，B3，B4四個地區(qū)，其需求量分別為5，7，8，3(萬噸)。產糧地到需求地的運價(元/噸)如下表所示，問如何安排一個運輸計劃，使總的運輸費用最少？地區(qū)產糧區(qū)B1B2B3B4產量A1326310A253828A341295需求量578323/237/29/202214解：設 xij (i=1,2,3；j=1,2,3,4)為 i 個產糧地運往第 j 個需求地的運輸量

11、，這樣得到下列運輸問題的數學模型：運輸量應大于或等于零（非負)B1B2B3B4產量A1326310A253828A341295需要量5783237/29/2022153、產品配比問題 例：用濃度45%和92%的硫酸配置100噸濃度80%的硫酸，已經兩種濃度硫酸的單價為每噸30和80元，問如何配置費用最??？決策變量：需要45%和92%的硫酸分別為 x1 和 x2 噸目標函數：min Z = 30 x1 + 80 x2約束條件：非負約束： x1 0， x2 07/29/202216 若有5種不同濃度的硫酸可選(30%,45%,73%,85%,92%)會如何呢？5種硫酸數量分別為 x1、x2、x3、

12、x4、x5 ，有：若5種硫酸價格分別為400, 700, 1400, 1900, 2500元/t，則：7/29/202217練習：某糖果廠用原料A，B，C加工成三種不同牌號的糖果甲、乙、丙。已知各種糖果的中A，B，C的含量要求，原料成本，各種原料每月的限制用量，三種牌號糖果的單位加工費及售價如下表所示。問該廠每月生產這三種牌號糖果各多少kg，利潤最大？甲乙丙原料成本 (元/kg)每月限制用量 (kg)A60%30%2.002000B1.502500C20%50%60%1.001200加工費 (元/kg)0.500.400.30售價 (元/kg)3.402.852.257/29/202218解：

13、設xij為生產第j種糖果使用的第i種原料的數量，則該問題的數學模型為： 最優(yōu)解：即該廠每月應生產甲種牌號糖果906.67kg，乙種牌號糖果4793.33kg，利潤最大為5450元。7/29/202219練習：生產某一機床需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是2.9、2.1和1.5m，這些軸需要用同一種圓鋼切割而成，圓鋼長度為7.4m?，F在要制造100臺機床，問：最少要用多少圓鋼來生產這些軸？(假設切割損失不計)解：1、設一根圓鋼切割成甲、乙、丙三種軸的根數分別為y1, y2, y3, 則切割方式可用不等式2.9y1+2.1y2+1.5y37.4表示，求這個不等式關于y1，y2，

14、y3的非負整數解。例如：y1=2， y2=0 ，則 y3 只能為1，余料為0.1。像這樣的非負整數解共有8組，也就是有8種下料方式，如表1.4所示。 2、建立線性規(guī)劃數學模型。設xj (j=1,2,8)為第 j 種下料方案所用圓鋼的根數。4、合理下料問題7/29/202220 方案規(guī)格12345678需求量y1(2.9m)21110000100y2(2.1m)02103210100y3(1.5m)10130234100總長7.4m0.10.30.90.01.10.20.81.4余料min Z = x1+x2+x3 +x4+x5 +x6+x7 +x82x1+x2+x3 +x4 1002x2+x3

15、+3x5 +2x6 +x7 100 x1+x3 +3x4 +2x6 +3x7 +4x8 100 xj 0, j =1, 2, , 8 (x1=10, x2=50, x4=30, 16m)7/29/2022215、投資問題 某投資公司在第一年初有100萬元資金，假設每年都有如下的投資方案：第一年初投入一筆資金，第二年初又繼續(xù)投入此資金的50%，第三年初就可回收第一年初投入資金的兩倍。問：該投資公司應如何確定投資策略才能使第六年初所擁有的資金最多？解：設x1為第一年的投資，x2為第一年的保留資金，則：x1 + x2 = 100第二年： 設x3為第二年新的投資，x4為第二年的保留資金，則：7/29/

16、202222第三年：設 x5 為新的投資，x6 為第三年的保留資金；第四年：設新的投資 x7 ，第四年的保留資金 x8 ；第五年：設 x9 為第五年的保留資金。根據題意，第五年初不再進行新的投資，因為這筆投資要到第七年初才能收回。 約束條件 每年應滿足如下的關系：追加投資金額 + 新投資金額 + 保留資金=可利用的資金總額 7/29/202223X*(27.64, 72.36, 58.54, 0, 26.02, 0, 104.06, 0, 0)T，Z*208.12。 到第六年初，實有資金總額為x9 + 2x7，整理后得到下列線性規(guī)劃模型： max Z = 2x7 + x9 第一年新投資27.6

17、4萬元、第二年新投資58.54萬元、第三年新投資26.02萬元、第四年新投資104.06萬元，才能使第六年初擁有資金最多，為208.12萬元。7/29/202224思考題：某人有30萬元資金，在今后的三年內有以下4個 投資項目可供參考，假設有錢就會用于投資。 1.三年內的每年年初均可投資，每年獲利為投資額的20%，其本利可一起用于下一年的投資； 2.只允許第一年年初投入，第二年末可收回，本利合計為投資額的150%，但此類投資額不超過15萬元； 3.第二年初允許投資，可于第三年末收回，本利合計為投資額的160%，這類投資限額20萬元； 4. 第三年初允許投資，一年回收，可獲利40%，投資限額為1

18、0萬元。 試確定一個第三年末本利和為最大的投資計劃？7/29/202225 項目投資時間1234第1年初x11x12第2年初x21x23第3年初x31x34對于約束條件：第1年，可用于項目1和2投資： x11 + x12 = 300000第2年，可用于項目1和3投資，投資額為x11的本利和：x21 + x23 = 1.2 x11第3年，可用于項目1和4投資，投資額x21和x12有關： x31 + x34 = 1.2 x21 + 1.5 x12投資限額： x12 150000; x23 200000; x34 10000非負約束： xij 0 ( i = 1,2,3; j = 1,2,3,4 )

19、對于目標函數，只需考慮第3年末：項目1：x31 1.2 x31 (本利和)；項目2：0；項目3：x23 1.6 x23 (本利和)；項目4：x34 1.4x34 (本利和)；maxZ = 1.2 x31 + 1.6 x23 + 1.4 x34 7/29/202226解：設xij為第 i 年初投放到 j 項目的資金額(元)，其數學模型為：maxZ = 1.2 x31 + 1.6 x23 + 1.4 x34 注意本題條件：有錢就會用于投資，即：可利用的資金 = 投資金額，據此建立約束等式。x11 + x12 = 300000 x21 + x23 = 1.2 x11x31 + x34 = 1.2 x

20、21 + 1.5 x12x12 150000 x23 200000 x34 10000 xij 0 (i = 1,2,3; j = 1,2,3,4)7/29/2022277/29/202228第一節(jié) 線性規(guī)劃的一般模型 用一組非負決策變量表示的一個決策問題； 存在一組等式或不等式的線性約束條件； 有一個希望達到的目標，可表示成決策變量的極值線性函數。為了書寫方便，上式也可簡寫： 7/29/202229一般地，xj0，但有時xj0或xj無符號限制。7/29/202230線性規(guī)劃圖解法 1、概念： 利用幾何圖形求解兩個變量線性規(guī)劃問題的方法。 3、求解步驟： 第一步：建立平面直角坐標系； 第三步：

21、在可行域內平移目標函數等值線， 確定最優(yōu)解及最優(yōu)目標函數值。 2、特點： 簡單、直觀，但只適用于兩個變量的LP問題。 第二步：根據約束條件畫出可行域；7/29/2022311、線性規(guī)劃的可行域可行域：滿足所有約束條件的解的集合，即由所有約束條件共同圍成的區(qū)域。maxZ= 3x1 + 5x2 2x1 16 2x2 10 3x1+4x2 32 x10, x20s.t.2x1 =162x2 =103x1 +4 x2 =32x1x24810359OABCD7/29/2022322x1 =162x2 =10 x1x28103583x1 + 4x2 =320ABCD2、線性規(guī)劃的最優(yōu)解目標函數 Z = 3

22、x1 + 5x2 代表以 Z 為參數的一族平行線。Z=25Z=37Z=15(4, 5)X*=(4, 5)TZ*=377/29/202233x1x2O1020304010203040(15,10)最優(yōu)解 X* = (15,10)T最優(yōu)值 Z* = 857/29/202234246x1x2246最優(yōu)解 X* = (3,1)T最優(yōu)值 Z* = 5(3,1)min Z = x1 + 2x27/29/2022353、線性規(guī)劃解的特性abcd由線性不等式組成的可行域是凸多邊形(凸集)凸集：對于某一集合內部任意兩點連線上的點都屬于這個集合，我們就稱這個集合為凸集。線性規(guī)劃問題的可行域具有有限個頂點。 目標函

23、數最優(yōu)值一定在可行域的邊界(頂點)達到，而不可能在其區(qū)域的內部。7/29/202236凸集的概念設K為n維歐氏空間的一個點集，若K中任意兩個點X1和X2連線上的所有點都屬于K，則稱K為凸集。X2X1X設X(x1,x2,xn); X1(u1,u2,un); X2(v1,v2,vn)7/29/202237四、線性規(guī)劃解的可能性1、唯一最優(yōu)解2、多重最優(yōu)解/無窮多最優(yōu)解當乙產品市場價格從75元下降到74元時，模型變?yōu)椋?2x1 =162x2 =103x1+4x2=32x1x248102580ABCDZ=24Z=32Z=127/29/202238246x1x2246X(2) (3, 1)TX(1) (

24、1, 3)T(5,5)min Z=5x1+5x2具有無窮多最優(yōu)解，即多重最優(yōu)解, 通解為： 01 例如：當=0.5時 = (x1,x2)T = 0.5(1,3)T + 0.5(3,1)T = (2,2)T 7/29/2022393、無界解可行域無界，目標值無限增大(缺乏必要約束)7/29/202240246x1x2246(1,2)無界解max Z=x1+2x27/29/2022414、無可行解：線性規(guī)劃問題的可行域是空集 (約束條件相互矛盾)7/29/202242x1x2O10203040102030405050無可行解max Z=10 x1+4x27/29/20224320130312 作業(yè)

25、：用圖解法求解以下問題（1）（2）（3）（4）7/29/202244一、線性規(guī)劃的標準型 1、標準型表達方式(1)代數式： (2)向量式： (3)矩陣式： A：技術系數矩陣，簡稱系數矩陣；b：可用的資源量，稱資源向量；C：決策變量對目標的貢獻，稱價值向量；X：決策變量。第二節(jié) 線性規(guī)劃問題模型 7/29/202245通常X記為： ，其中，為約束方程的系數矩陣，m是約束方程的個數，n是決策變量的個數，一般情況mn，且r()m。其中:7/29/2022462、標準型轉換方法(1) “目標函數求最大值”。如果極小化原問題minZ = CX，則令 Z = Z，轉為求 maxZ = CX 。 注意：求解

26、后還原。 （2） (2) “資源限量非負”。若某個 bi 0，則將該約束兩端同乘 “1” ，以滿足非負性的要求。 （4） (3) “約束條件為等式”。對于 “”型約束，則在“”左端加上一個非負松弛變量(slack variable) ，使其為等式。 對于“”型約束，則在“”左端減去一個非負剩余變量(Surplus variable) ，使其為等式。 （3） (4) “決策變量非負”。若某決策變量 xk 為“取值無約束”(無符號限制)，令：xk = xk xk ，(xk0, xk 0) 。 （1） 7/29/202247【例】將下列線性規(guī)劃轉化為標準型(標準形式)？ 【解】(1)決策變量取值 x

27、3 無符號要求(取值無約束) ，即x3取正值也可取負值，標準型中要求變量取值為非負，所以可令：7/29/202248 (3) 第二個約束條件是“號”，在“號”左端減去剩余變量x5，x50， x5也稱松馳變量 (2) 第一個約束條件是“號”，在“”左端加入松馳變量 x4，x40，即化為等式； (4) 第三個約束條件是“號”且常數項為負數，因此在“”左邊加入松馳變量x6，x60，同時不等式兩端同乘以“1”。 (5) 目標函數是最小值，令Z=Z,得到max Z= max(Z)，即當Z達到最小值時Z達到最大值，反之亦然。 (1) x3 取值無約束 ，令 x3 = x3 x3，x3, x3 0。7/29

28、/202249標準型為： 7/29/202250將例1.1的線性規(guī)劃問題的一般形式化為標準型？ 第二節(jié) 線性規(guī)劃問題模型 7/29/202251第二節(jié) 線性規(guī)劃問題模型 7/29/202252練習：將下列線性規(guī)劃模型轉化為標準型？ min Z = 3x1 x24x3 x1 2x2+ 5x3 0 2x1 + x2 3x3 450 3x1 x2 0 x10 , x20 , x3 無約束解：令Z= Z, x2 = x2, x3 = x3 x3, 其中：x2, x3, x3 0， 約束引入剩余變量 x4，約束引入松弛變量 x5，則標準型：max Z = 3x1 x2 4(x3 x3) + 0 x4 +

29、 0 x5 x1 + 2x2 + 5(x3 x3 ) x4 = 0 2x1 x2 3(x3 3x3) + x5 = 450 3x1 + x2 = 0 x1, x2, x3, x3, x4, x5 0作業(yè)：教材42頁,第8題 7/29/202253二、線性規(guī)劃之解的概念 基矩陣：一個非奇異的子矩陣（向量線性無關）。矩陣A 中任意一個 m 列的線性無關子矩陣 B ，稱為一個基(矩陣)。組成基的列向量稱為基向量，用 Pj 表示 ( i = 1 , 2 , , m ) 。基變量：與基向量 Pj 相對應的變量 xj 稱為基變量。其余的 n m 個變量稱為非基變量(基矩陣以外的列向量對應變量)。1、線性規(guī)

30、劃解之關系 基(本)解：令所有非基變量等于零，得出的唯一解。x3x4x5基變量是x3 , x4 , x5非基變量是x1 , x2令非基變量 x1 = x2 = 0，基變量取值唯一確定：x3= 16，x4= 10，x5= 32得到一個基解： X = (0 , 0 , 16 , 10 , 32)T7/29/202254重要概念 可行解：滿足約束條件AX=b和X0的解。基(本)解：令所有非基變量等于零，得出的唯一解。基(本)可行解：滿足X0的基解。可行基：基可行解對應的基矩陣。最優(yōu)解：使目標函數最優(yōu)的基可行解，稱為最優(yōu)解。最優(yōu)基：最優(yōu)解對應的基矩陣，稱為最優(yōu)基。7/29/202255基的概念假設線性

31、規(guī)劃問題模型系數矩陣為m行、n列(mn)，則系數矩陣中秩為m的m行m列子矩陣，稱為基矩陣，簡稱基。 基中的列向量對應的變量稱為基變量，決策變量中基變量以外的變量稱為非基變量。 7/29/202256基本解 對于某一確定的基，令所有非基變量為0，由約束方程組AX=b可解出m個基變量的唯一解，稱為一個基本解。 7/29/202257基本可行解 滿足非負條件的基本解，稱為基本可行解，基本可行解對應于凸多邊形的項點。 7/29/202258練習：已知線性規(guī)劃問題問：中哪一個是基本可行解？7/29/202259二、線性規(guī)劃之解的概念 2、線性規(guī)劃問題基本定理定理1. 若線性規(guī)劃問題存在可行域，則其可行域

32、一定 是凸集。定理2. 線性規(guī)劃問題的基可行解對應可行域的頂點。定理3. 若可行域有界，線性規(guī)劃的目標函數一定可以 在可行域的頂點上達到最優(yōu)。定理4. 線性規(guī)劃如果有可行解，則一定有基可行解； 如果有最優(yōu)解，則一定有基可行解是最優(yōu)解。7/29/202260二、線性規(guī)劃之解的概念 3、線性規(guī)劃問題的解題思路 首先，找到一個初始基可行解，也就是找到一個初始可行基，想辦法判斷這個基可行解是不是最優(yōu)解。 如果是最優(yōu)解，就得到這個線性規(guī)劃問題的最優(yōu)解； 如果判斷出不是最優(yōu)解，就想法由這個可行基按一定規(guī)則變化到下一個可行基，然后再判斷新得到的基可行解是不是最優(yōu)解； 如果還不是，再接著進行下一個可行基變化，

33、直到得到最優(yōu)解。 7/29/202261求解線性規(guī)劃問題的思路單純形法求初始基本可行解判斷該可行解是否最優(yōu)尋找新的基本可行解結束是否1947年，美國斯坦福大學丹捷格教授發(fā)明單純形法。7/29/202262一、線性規(guī)劃問題的代數解法（教材第32頁例題）解：(一)標準化：(二)求初始基可行解7/29/202263 令非基變量：x1=x2=0，得到初始基可行解： X(0)=(0,0,16,10,32)T 此時，目標函數值： Z(0) = 3x1 + 5x2 + 0 = 0目標函數用非基變量表示。(三)判優(yōu) 對于Z(0) = 3x1 + 5x2 ，若x1或x2從0變?yōu)檎龜?，則目標函數值會增加，因此可判

34、斷X(0)一定不是最優(yōu)解。(X(0) X*)7/29/202264Z(0) = 3x1 + 5x2(四)方案調整(換基) 尋找一個新的基可行解，使目標函數值得到改善。 選擇入基變量 尋找使目標函數增加量最大的非基變量入基，即目標函數中系數最大的變量。(x2) 選擇出基變量 為什么要選擇原基變量出基？要求決策變量非負，因此有： 說明x2最大取值是5，且當x2=5時，x4=0，即x4出基。 ( x4) 7/29/202265(五)求新的基可行解 此時，基變量為x3、x2和x5，非基變量為x1和x4。 用非基變量表示基變量：用x4表示x2，x2 = 5 (x4/2) ，用x4表示x5，x5 = 12

35、 3x1 + 2x4 。 令非基變量 x1 = x4 = 0，則 X(1) = (0, 5, 16, 0, 12)T 。7/29/202266(六)判優(yōu)(檢驗) 將式(4)代入目標函數，目的：用非基變量表示目標函數，得到新的目標函數值： Z(1) = 3x1 + 5x2 = 3x1 + 5(5 x4/2) = 3x1 5x4 / 2 + 25 非基變量x1的系數為3，大于零，可見，如果x1 能從非基變量變?yōu)榛兞?，即變?yōu)檎龜?，則目標函數值會增加，因此X(1) = (0, 5, 16, 0, 12)T 不是最優(yōu)解。7/29/202267Z(1) = 3x1 5x4/2 + 25(七)換基 當x1

36、 = 4時，x5 = 0 即：當x1 入基，x5 出基。7/29/202268(八)求新的基可行解 此時，基變量為x3、x2和x1，非基變量為x4和x5。 用非基變量表示基變量： x1 = 4 + 2x4 /3 x5/3 ， x3 = 8 4x4/3 + 2x5/3 。 令非基變量 x4 = x5 = 0，則 X(2) = (4, 5, 8, 0, 0)T 。7/29/202269 松弛變量x3 = 8 說明第一項資源有剩余，資源相對寬松，這就是松馳變量的經濟含義。(九)判優(yōu)(檢驗) 非基變量x4和x5的系數均為負值，如果x4 和x5從非基變量變?yōu)榛兞浚磸牧阕優(yōu)檎龜?，則目標函數值會減少，因

37、此X(2) = (4, 5, 8, 0, 0)T 是最優(yōu)解，目標函數最優(yōu)值Z* = 37。7/29/202270求解過程(換基迭代過程)初始基初始基可行解：X(0)=(0,0,16,10,32)T Z(0) =0新的可行基新的基可行解：X(1)=(0,5,6,0,12)T Z(1) =25最優(yōu)基最優(yōu)解：X* = (4,5,8,0,0)T Z* =377/29/202271 單純形法求解線性規(guī)劃問題的步驟： (1)求出初始基本可行解(標準化、單位基)； (2)最優(yōu)性檢驗(非基變量檢驗數非正時停止，否則進入下一步)； (3)換基(迭代)： 確定入基變量 確定出基變量 初等變換，求出新的基本可行解；

38、 (4)重復步驟(2)、(3)，直到求出最優(yōu)解。7/29/202272單純形法求解步驟舉例 maxZ = 3x1 + 5x2 +0 x3 +0 x4+0 x5 2x1 + x3 = 16 2x2 + x4 = 10 3x1 +4x2 + x5 = 32 Cj比值CBXBb檢驗數jx1x2x3x4x535000162010010020103234001x3x4x5000035000-10/2=532/4=87/29/202273162010050101/2012300-21x3x2x5050300-5/205-4Cj比值CBXBb檢驗數jx1x2x3x4x535000檢驗數j80014/3-2/

39、350101/204100-2/31/3x3x2x1053000-1/2-1最優(yōu)解: X*=(4,5,8,0,0)T，Z*=377/29/202274單純形法的管理啟示2x1=162x2 =103x1 + 4x2 =32x1x24812590ABC(4,5)DX0=(0,0,10,10,32)TX1=(0,5,16,0,12)TX1=(4,5,8,0,0)T 在管理過程中，把現有方案作為初始方案，找到最急需要改進的某個問題和改進方向，一次做好某個主要問題的解決與改進；一次只解決和改進一個問題的難度最小；解決之后，再尋求可以改進的其它地方，再次改進，不斷地追求更優(yōu)。7/29/202275單純形法

40、原理(1) 舉例說明ppt52頁7/29/202276單純形法原理(2)非基變量檢驗數 令非基變量等于0，則7/29/202277CjCBCNCBXBbXBXN0XBbBNjCBCNCBXBbXBXNCBXBB-1bEB-1Nj0CN CBB-1N單純形法原理(單純形表)7/29/202278例 求解下列線性規(guī)劃問題解：引入松馳變量x3, x4 , x5 ，化為標準形式：7/29/202279 cj 2 5 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 4 3 8 1 0 1 0 0 0 1 0 1 0 1 2 0 0 1 j 0 2 5 0 0 0

41、由于x1，x2的檢驗數均為正，且x2的檢驗數k最大，選取x2為入基變量；再按最小比值= min(-, 3/1, 8/2) = 3，選取x4為出基變量。 cj 2 5 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 x3 x5 4 3 1 0 1 0 0 0 1 0 1 0 j x252100-21200-50157/29/202280 cj 2 5 0 0 0 CB XB b x1 x2 x3 x4 x5 0 5 0 x3 x2 x5 4 3 2 1 0 1 0 0 0 1 0 1 0 1 0 0 -2 1 j 15 2 0 0 -5 0 由于x1檢驗數為正，選取x1為入基變

42、量；再按最小比值 = min（4/1, -, 2/1）=2，選取x5為出基變量。 cj 2 5 0 0 0 CB XB b x1 x2 x3 x4 x5 0 5 x3 x2 3 2 0 1 0 1 0 1 0 0 -2 1 j x122001 2-1000-1-2197/29/202281 初始基本可行解：X(0) = (0, 0, 4, 3, 8)T，Z(0) = 0 新的基本可行解：X(1) = (0, 3, 4, 0, 2)T，Z(1) = 15 新的基本可行解：X(2) = (2, 3, 2, 0, 0)T，Z(2) = 19 判別定理 1：在單純形表中（目標函數求max），若所有非基

43、變量的檢驗數小于零，且XB取值非負，則線性規(guī)劃問題具有唯一最優(yōu)解。7/29/202282圖解法求解結果：x1x1 = 4x2 = 3x1 + 2x2 = 8x2(2, 3)x2 = -(2/5)x1 +Z/5 A (0, 0)A：X(0) = (0, 0, 4, 3, 8)T，Z(0) = 0 B (0, 3)B：X(1) = (0, 3, 4, 0, 2)T，Z(1) = 15 C C：X * = (2, 3, 2, 0, 0)T，Z* = 19 D (4, 2) E (4, 0) 07/29/202283例 求解下列線性規(guī)劃問題解：引進松馳變量x3, x4, x5，化為標準形式：7/29/

44、202284 cj 2 4 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 4 10 2 -1 2 1 0 0 1 2 0 1 0 1 -1 0 0 1 j 0 2 4 0 0 0 cj 2 4 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 x4 x5 j x242-1/21 1/200620-11041/201/20140-20087/29/202285 cj 2 4 0 0 0 CB XB b x1 x2 x3 x4 x5 4 0 0 x2 x4 x5 2 6 4 -1/2 1 1/2 0 0 2 0 -1 1 0 1/2 0 1

45、/2 0 1 j 8 4 0 -2 0 0 cj 2 4 0 0 0 CB XB b x1 x2 x3 x4 x5 4 0 x2 x5 j x12310-1/2 1/20011/41/407/2003/4-1/415/2000-20207/29/202286 cj 2 4 0 0 0 CB XB b x1 x2 x3 x4 x5 4 2 0 x2 x1 x5 7/2 3 5/2 0 1 1/4 1/4 0 1 0 -1/2 1/2 0 0 0 3/4 -1/4 1 j 20 0 0 0 -2 0 cj 2 4 0 0 0 CB XB b x1 x2 x3 x4 x5 4 2 x2 x1 j x

46、3010/3001 -1/34/38/30101/3-1/314/31001/32/3000-20207/29/202287 初始基本可行解：X(0) = (0, 0, 4, 10, 2)T，Z(0) = 0 新的基本可行解：X(1) = (0, 2, 0, 6, 4)T，Z(1) = 8 新的基本可行解：X(2) = (3, 7/2, 0, 0, 5/2)T，Z(2) = 20 新的基本可行解：X(3) = (14/3, 8/3, 10/3, 0, 0)T，Z(3) = 20 判別定理 2：在單純形表中，若所有非基變量的檢驗數小于等于零，其中某個檢驗數等于零，則線性規(guī)劃問題具有無窮多最優(yōu)解(

47、多重最優(yōu)解)。7/29/202288圖解法求解結果： A (0, 0)A：X(0) = (0, 0, 4, 10, 2)T，Z(0) = 0 B (0, 2)B：X(1) = (0, 2, 0, 6, 4)T，Z(1) = 8 C (3,7/2)C：X* = (3, 7/2, 0, 0, 5/2)T，Z* = 20D (14/3, 8/3)E (2, 0) D：X* = (14/3, 8/3, 10/3, 0, 0)T，Z* = 207/29/202289例 求解下列線性規(guī)劃問題解：引入松馳變量x3, x4，標準化：7/29/202290 cj -2 3 0 0 CB XB b x1 x2 x

48、3 x4 0 0 x3 x4 2 4 4 -2 1 0 2 -3 0 1 j 0 -2 3 0 0 不滿足出基變量確定法則：雖然，不能確定x3和x4哪個變量出基，但無論哪個變量出基，都必須滿足： x30，x40。因x2入基，所以一定滿足： x20。說明x2可以無限增大，所以目標函數值可以無限增大。無界解7/29/202291圖解法求解結果： A (0, 0)無界解7/29/202292練習 求解下列線性規(guī)劃問題解：引進松馳變量x3, x4，化為標準形式： 從標準形中可看出存在可行基B=(P3，P4)=E，基變量為X3，X4；非基變量為X1，X2。建立初始單純形表得：7/29/202293cj

49、4 3 0 0CBXBb x1 x2 x3 x400 x3x42426 2 3 1 0 3 2 0 1 0 4 3 0 0 由于x1，x2的檢驗數均為非負，且x1的檢驗數絕對值最大，選取x1為進基變量；再按最小比值=min（24/2，26/3）=26/3，選取x4為出基變量，進行換基迭代。cj 4 3 0 0CBXBb x1 x2 x3 x404x3x120/326/3 0 5/ 3 1 -2/3 1 2/3 0 1/3 104/3 0 1/3 0 -4/37/29/202294cj 4 3 0 0CBXBb x1 x2 x3 x434x2x146 0 1 3/5 -2/5 1 0 -2/5

50、3/5 36 0 0 -1/5 -6/5 表中最后一行的所有檢驗數均為非正，表明目標函數已達到最大值，上表為最優(yōu)單純形表。從表中可得到最優(yōu)解為：X*=(x1, x2, x3, x4)T = (6, 4, 0, 0)T，最優(yōu)值為：Z*=36。7/29/20229520130319 作業(yè)：用單純形法求解以下問題（1）（2）（3）（4）7/29/202296cj 2 -1 1 0 0 0CBXBb x1 x2 x3 x4 x5 x6000 x4x5x6601020 3 1 1 1 0 0 1 -1 2 0 1 0 1 1 -1 0 0 1 -2 1 -1 0 0 0 練習：已知某線性規(guī)劃用單純形法求

51、得的某兩步迭代表如下，請將表中空白處填上適當的數字。Cj 0 0 0 0 1 1CBXBb x1 x2 x3 x4 x5 x602-1x4x1x2 1 -1 -2 0 1/2 1/2 0 -1/2 1/2 cj 0 0 0 0 1 1CBXBb x1 x2 x3 x4 x5 x602-1x4x1x210155 0 0 1 1 -1 -2 1 0 1/2 0 1/2 1/2 0 1 -3/2 0 -1/2 1/2 25 0 0 -3/2 0 -3/2 -1/27/29/202297思考題 已知線性規(guī)劃問題：其中b1, b2是常數，且已知此問題的最終單純形表如下。試確定表中所有的參數？cj 5 2

52、 3 0 0CBXBb x1 x2 x3 x4 x5 50 x1x53010 1 b 2 1 0 0 c -8 -1 1 150 0 a -7 d e e = 0, d = 5, b = 5, c = 10, a = 23, b1= 30, b2= 407/29/202298思考：某極大化線性規(guī)劃問題的單純形表如下，問表中參數 a1, a2, a3, d, 1, 2 為何取值范圍時，下列結論成立？ cj 0 0 0 0 1 1 CB XB b x1 x2 x3 x4 x5 x6 3 0 0 x3 x4 x6 d 2 3 4 a1 1 0 a2 0 -1 -3 0 1 -1 0 a3 -5 0

53、0 -4 1 j 1 2 0 0 -3 0 (1)表中解為唯一最優(yōu)解：(2)表中解為無窮多最優(yōu)解：(3)該問題具有無界解：(4)表中解為退化的基解：(5)表中解為不可行解：(6) x1入基，x6出基：10, 20, 12 = 0, d 01 0, 2 0, a1 0, d 01 0, 2 0, d = 0 d 0, d 0, d /43/a3 , a3 07/29/202299已知線性規(guī)劃問題的最優(yōu)單純形表如下，求初始單純形表中的參數C, A, b 以及最優(yōu)基B ？cj c1 c2 c3 c4 c5 CB XB b x1 x2 x3 x4 x5 c1 c2 x1 x2 6 2 1 0 4 1/

54、6 1/15 0 1 -3 0 1/5 j 0 0 -1 -2 -3 7/29/2022100求解結果：7/29/2022101大M法（大M單純形法） 通過添加人工變量構成單位基，進而求解線性規(guī)劃問題的方法。7/29/2022102例 求解下列線性規(guī)劃問題解：引進松馳變量x4, x5，化為標準形式：7/29/2022103加入變量x6, x7，加入參數M，M為任意大的正數7/29/2022104 cj 3 -1 -1 0 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 0 -M -M x4 x6 x7 11 3 1 1 -2 1 1 0 0 0 -4 1 2 0 -1 1 0 -2 0 1