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

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

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

3、使企業(yè)在計劃期內(nèi)總的利潤最大？第一節(jié) 線性規(guī)劃的一般模型 一、線性規(guī)劃模型的舉例 7/29/20224 產(chǎn)品 資源 甲 乙丙現(xiàn)有資源設(shè)備A 3 1 2 200(h)設(shè)備B 2 2 4 200(h)材料C 4 5 1 360(kg)材料D 2 3 5 300(kg)利潤（元/件） 40 30 50表1.1 某企業(yè)單位產(chǎn)品資源消耗及利潤x1x1x1x1x1x2x2x2x2x2x3x3x3x3x37/29/20225【解】設(shè)x1、x2、x3 為甲、乙、丙三種產(chǎn)品的產(chǎn)量，則該線性規(guī)劃問題的數(shù)學模型為： 產(chǎn)品 資源 甲 乙 丙現(xiàn)有資源設(shè)備A 3 1 2 200設(shè)備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，即在計劃期內(nèi)甲、乙、丙產(chǎn)量分別為50、30和10件，利潤最大，為3400元。注意：最優(yōu)解的表達方式！7/29/20226二、線性規(guī)劃的三個要素 第一節(jié) 線性規(guī)劃的一般模型 決策變量（一組）決策問題待定的量值取值要求非負約束條件（一組）任何管理決策問題都是限定在一定的條件下求解把各種限制條件表示為一組等式或不等式稱約束條件約束條件是決策方案可行的保障約束條件是決策變量的線性函數(shù)目標函數(shù)（一個）衡量決策優(yōu)劣的準則，如時間最省、利潤最大、成本最低目標函數(shù)是決策變量的線性函數(shù)有的

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

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

7、0 x130 x2 設(shè)備產(chǎn)品 ABC利潤甲 乙3955937030限時 540450720 設(shè)備可用工時數(shù)限制 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ī)劃的數(shù)學模型由決策變量 Decision variables 目標函數(shù) Objective function 構(gòu)成，稱為三要素。約束條件 Constraints其主要特征是：1. 解決的問題是規(guī)劃問題；2解決問題的目標函數(shù)是多個

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

9、等于銷量)7/29/202212(1)決策變量：設(shè)從 Ai 到 Bj 的運輸量為 xij ，(2)目標函數(shù)：運費最小的目標函數(shù)為：minZ = 6x11 + 3x12 + 2x13 + 5x14 + 7x21 + 5x22 + 8x23 + 4x24 + 3x31 + 2x32 + 9x33 + 7x34 (3)約束條件：產(chǎn)量之和等于銷量之和，故要滿足：供應(yīng)平衡條件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ī)劃的數(shù)學模型由三個要素組成：7/29/202213【練習】現(xiàn)有A1，A2，A3三個產(chǎn)糧區(qū)，可供應(yīng)糧食分別為10，8，5(萬噸)，現(xiàn)將糧食運往B1，B2，B3，B4四個地區(qū)，其需求量分別為5，7，8，3(萬噸)。產(chǎn)糧地到需求地的運價(元/噸)如下表所示，問如何安排一個運輸計劃，使總的運輸費用最少？地區(qū)產(chǎn)糧區(qū)B1B2B3B4產(chǎn)量A1326310A253828A341295需求量578323/237/29/202214解：設(shè) xij (i=1,2,3；j=1,2,3,4)為 i 個產(chǎn)糧地運往第 j 個需求地的運輸量

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

12、x4、x5 ，有：若5種硫酸價格分別為400, 700, 1400, 1900, 2500元/t，則：7/29/202217練習：某糖果廠用原料A，B，C加工成三種不同牌號的糖果甲、乙、丙。已知各種糖果的中A，B，C的含量要求，原料成本，各種原料每月的限制用量，三種牌號糖果的單位加工費及售價如下表所示。問該廠每月生產(chǎn)這三種牌號糖果各多少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、設(shè)xij為生產(chǎn)第j種糖果使用的第i種原料的數(shù)量，則該問題的數(shù)學模型為： 最優(yōu)解：即該廠每月應(yīng)生產(chǎn)甲種牌號糖果906.67kg，乙種牌號糖果4793.33kg，利潤最大為5450元。7/29/202219練習：生產(chǎn)某一機床需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是2.9、2.1和1.5m，這些軸需要用同一種圓鋼切割而成，圓鋼長度為7.4m?，F(xiàn)在要制造100臺機床，問：最少要用多少圓鋼來生產(chǎn)這些軸？(假設(shè)切割損失不計)解：1、設(shè)一根圓鋼切割成甲、乙、丙三種軸的根數(shù)分別為y1, y2, y3, 則切割方式可用不等式2.9y1+2.1y2+1.5y37.4表示，求這個不等式關(guān)于y1，y2，

14、y3的非負整數(shù)解。例如：y1=2， y2=0 ，則 y3 只能為1，余料為0.1。像這樣的非負整數(shù)解共有8組，也就是有8種下料方式，如表1.4所示。 2、建立線性規(guī)劃數(shù)學模型。設(shè)xj (j=1,2,8)為第 j 種下料方案所用圓鋼的根數(shù)。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萬元資金，假設(shè)每年都有如下的投資方案：第一年初投入一筆資金，第二年初又繼續(xù)投入此資金的50%，第三年初就可回收第一年初投入資金的兩倍。問：該投資公司應(yīng)如何確定投資策略才能使第六年初所擁有的資金最多？解：設(shè)x1為第一年的投資，x2為第一年的保留資金，則：x1 + x2 = 100第二年： 設(shè)x3為第二年新的投資，x4為第二年的保留資金，則：7/29/

16、202222第三年：設(shè) x5 為新的投資，x6 為第三年的保留資金；第四年：設(shè)新的投資 x7 ，第四年的保留資金 x8 ；第五年：設(shè) x9 為第五年的保留資金。根據(jù)題意，第五年初不再進行新的投資，因為這筆投資要到第七年初才能收回。 約束條件 每年應(yīng)滿足如下的關(guān)系：追加投資金額 + 新投資金額 + 保留資金=可利用的資金總額 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萬元資金，在今后的三年內(nèi)有以下4個 投資項目可供參考，假設(shè)有錢就會用于投資。 1.三年內(nèi)的每年年初均可投資，每年獲利為投資額的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有關(guān)： 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、對于目標函數(shù)，只需考慮第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解：設(shè)xij為第 i 年初投放到 j 項目的資金額(元)，其數(shù)學模型為：maxZ = 1.2 x31 + 1.6 x23 + 1.4 x34 注意本題條件：有錢就會用于投資，即：可利用的資金 = 投資金額，據(jù)此建立約束等式。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ī)劃的一般模型 用一組非負決策變量表示的一個決策問題； 存在一組等式或不等式的線性約束條件； 有一個希望達到的目標，可表示成決策變量的極值線性函數(shù)。為了書寫方便，上式也可簡寫： 7/29/202229一般地，xj0，但有時xj0或xj無符號限制。7/29/202230線性規(guī)劃圖解法 1、概念： 利用幾何圖形求解兩個變量線性規(guī)劃問題的方法。 3、求解步驟： 第一步：建立平面直角坐標系； 第三步：

21、在可行域內(nèi)平移目標函數(shù)等值線， 確定最優(yōu)解及最優(yōu)目標函數(shù)值。 2、特點： 簡單、直觀，但只適用于兩個變量的LP問題。 第二步：根據(jù)約束條件畫出可行域；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)解目標函數(shù) Z = 3

22、x1 + 5x2 代表以 Z 為參數(shù)的一族平行線。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由線性不等式組成的可行域是凸多邊形(凸集)凸集：對于某一集合內(nèi)部任意兩點連線上的點都屬于這個集合，我們就稱這個集合為凸集。線性規(guī)劃問題的可行域具有有限個頂點。 目標函

23、數(shù)最優(yōu)值一定在可行域的邊界(頂點)達到，而不可能在其區(qū)域的內(nèi)部。7/29/202236凸集的概念設(shè)K為n維歐氏空間的一個點集，若K中任意兩個點X1和X2連線上的所有點都屬于K，則稱K為凸集。X2X1X設(shè)X(x1,x2,xn); X1(u1,u2,un); X2(v1,v2,vn)7/29/202237四、線性規(guī)劃解的可能性1、唯一最優(yōu)解2、多重最優(yōu)解/無窮多最優(yōu)解當乙產(chǎn)品市場價格從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)代數(shù)式： (2)向量式： (3)矩陣式： A：技術(shù)系數(shù)矩陣，簡稱系數(shù)矩陣；b：可用的資源量，稱資源向量；C：決策變量對目標的貢獻，稱價值向量；X：決策變量。第二節(jié) 線性規(guī)劃問題模型 7/29/202245通常X記為： ，其中，為約束方程的系數(shù)矩陣，m是約束方程的個數(shù)，n是決策變量的個數(shù)，一般情況mn，且r()m。其中:7/29/2022462、標準型轉(zhuǎn)換方法(1) “目標函數(shù)求最大值”。如果極小化原問題minZ = CX，則令 Z = Z，轉(zhuǎn)為求 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ī)劃轉(zhuǎn)化為標準型(標準形式)？ 【解】(1)決策變量取值 x

27、3 無符號要求(取值無約束) ，即x3取正值也可取負值，標準型中要求變量取值為非負，所以可令：7/29/202248 (3) 第二個約束條件是“號”，在“號”左端減去剩余變量x5，x50， x5也稱松馳變量 (2) 第一個約束條件是“號”，在“”左端加入松馳變量 x4，x40，即化為等式； (4) 第三個約束條件是“號”且常數(shù)項為負數(shù)，因此在“”左邊加入松馳變量x6，x60，同時不等式兩端同乘以“1”。 (5) 目標函數(shù)是最小值，令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ī)劃模型轉(zhuǎn)化為標準型？ 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ī)劃之解的概念 基矩陣：一個非奇異的子矩陣（向量線性無關(guān)）。矩陣A 中任意一個 m 列的線性無關(guān)子矩陣 B ，稱為一個基(矩陣)。組成基的列向量稱為基向量，用 Pj 表示 ( i = 1 , 2 , , m ) ?；兞浚号c基向量 Pj 相對應(yīng)的變量 xj 稱為基變量。其余的 n m 個變量稱為非基變量(基矩陣以外的列向量對應(yīng)變量)。1、線性規(guī)

30、劃解之關(guān)系 基(本)解：令所有非基變量等于零，得出的唯一解。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īng)的基矩陣。最優(yōu)解：使目標函數(shù)最優(yōu)的基可行解，稱為最優(yōu)解。最優(yōu)基：最優(yōu)解對應(yīng)的基矩陣，稱為最優(yōu)基。7/29/202255基的概念假設(shè)線性

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

32、一定 是凸集。定理2. 線性規(guī)劃問題的基可行解對應(yīng)可行域的頂點。定理3. 若可行域有界，線性規(guī)劃的目標函數(shù)一定可以 在可行域的頂點上達到最優(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)尋找新的基本可行解結(jié)束是否1947年，美國斯坦福大學丹捷格教授發(fā)明單純形法。7/29/202262一、線性規(guī)劃問題的代數(shù)解法（教材第32頁例題）解：(一)標準化：(二)求初始基可行解7/29/202263 令非基變量：x1=x2=0，得到初始基可行解： X(0)=(0,0,16,10,32)T 此時，目標函數(shù)值： Z(0) = 3x1 + 5x2 + 0 = 0目標函數(shù)用非基變量表示。(三)判優(yōu) 對于Z(0) = 3x1 + 5x2 ，若x1或x2從0變?yōu)檎龜?shù)，則目標函數(shù)值會增加，因此可判

34、斷X(0)一定不是最優(yōu)解。(X(0) X*)7/29/202264Z(0) = 3x1 + 5x2(四)方案調(diào)整(換基) 尋找一個新的基可行解，使目標函數(shù)值得到改善。 選擇入基變量 尋找使目標函數(shù)增加量最大的非基變量入基，即目標函數(shù)中系數(shù)最大的變量。(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)代入目標函數(shù)，目的：用非基變量表示目標函數(shù)，得到新的目標函數(shù)值： Z(1) = 3x1 + 5x2 = 3x1 + 5(5 x4/2) = 3x1 5x4 / 2 + 25 非基變量x1的系數(shù)為3，大于零，可見，如果x1 能從非基變量變?yōu)榛兞浚醋優(yōu)檎龜?shù)，則目標函數(shù)值會增加，因此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 說明第一項資源有剩余，資源相對寬松，這就是松馳變量的經(jīng)濟含義。(九)判優(yōu)(檢驗) 非基變量x4和x5的系數(shù)均為負值，如果x4 和x5從非基變量變?yōu)榛兞?，即從零變?yōu)檎龜?shù)，則目標函數(shù)值會減少，因

37、此X(2) = (4, 5, 8, 0, 0)T 是最優(yōu)解，目標函數(shù)最優(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)性檢驗(非基變量檢驗數(shù)非正時停止，否則進入下一步)； (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檢驗數(shù)jx1x2x3x4x535000162010010020103234001x3x4x5000035000-10/2=532/4=87/29/202273162010050101/2012300-21x3x2x5050300-5/205-4Cj比值CBXBb檢驗數(shù)jx1x2x3x4x535000檢驗數(shù)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 在管理過程中，把現(xiàn)有方案作為初始方案，找到最急需要改進的某個問題和改進方向，一次做好某個主要問題的解決與改進；一次只解決和改進一個問題的難度最?。唤鉀Q之后，再尋求可以改進的其它地方，再次改進，不斷地追求更優(yōu)。7/29/202275單純形法

40、原理(1) 舉例說明ppt52頁7/29/202276單純形法原理(2)非基變量檢驗數(shù) 令非基變量等于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的檢驗數(shù)均為正，且x2的檢驗數(shù)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檢驗數(shù)為正，選取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：在單純形表中（目標函數(shù)求max），若所有非基

43、變量的檢驗數(shù)小于零，且XB取值非負，則線性規(guī)劃問題具有唯一最優(yōu)解。7/29/202282圖解法求解結(jié)果：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：在單純形表中，若所有非基變量的檢驗數(shù)小于等于零，其中某個檢驗數(shù)等于零，則線性規(guī)劃問題具有無窮多最優(yōu)解(

47、多重最優(yōu)解)。7/29/202288圖解法求解結(jié)果： 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可以無限增大，所以目標函數(shù)值可以無限增大。無界解7/29/202291圖解法求解結(jié)果： 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的檢驗數(shù)均為非負，且x1的檢驗數(shù)絕對值最大，選取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 表中最后一行的所有檢驗數(shù)均為非正，表明目標函數(shù)已達到最大值，上表為最優(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、得的某兩步迭代表如下，請將表中空白處填上適當?shù)臄?shù)字。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是常數(shù)，且已知此問題的最終單純形表如下。試確定表中所有的參數(shù)？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ī)劃問題的單純形表如下，問表中參數(shù) a1, a2, a3, d, 1, 2 為何取值范圍時，下列結(jié)論成立？ 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)單純形表如下，求初始單純形表中的參數(shù)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求解結(jié)果：7/29/2022101大M法（大M單純形法） 通過添加人工變量構(gòu)成單位基，進而求解線性規(guī)劃問題的方法。7/29/2022102例 求解下列線性規(guī)劃問題解：引進松馳變量x4, x5，化為標準形式：7/29/2022103加入變量x6, x7，加入?yún)?shù)M，M為任意大的正數(shù)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