第一線性規(guī)劃

第一線性規(guī)劃第1頁，共71頁，2023年，2月20日，星期一Chapter1線性規(guī)劃

(LinearProgramming)

LP的數(shù)學(xué)模型圖解法單純形法單純形法的進一步討論－人工變量法

LP模型的應(yīng)用本章主要內(nèi)容：第2頁，共71頁，2023年，2月20日，星期一線性規(guī)劃LinearProgramming（LP）

引言

解決有限資源在有競爭的使用方向中如何進行最佳分配。

線性規(guī)劃是運籌學(xué)的一個重要分支，也是運籌學(xué)中應(yīng)用最廣泛的方法之一。自1947年旦茨基（G.B.Dantzig）提出了一般線性規(guī)劃問題求解的方法——單純形法（simplexmethod）之后，線性規(guī)劃已被廣泛應(yīng)用于解決經(jīng)濟管理和工業(yè)生產(chǎn)中遇到的實際問題。調(diào)查表明，在世界500家最大的企業(yè)中，有85%的企業(yè)都曾使用過線性規(guī)劃解決經(jīng)營管理中遇到的復(fù)雜問題。線性規(guī)劃的使用為應(yīng)用者節(jié)約了數(shù)以億萬計的資金。本講中我們將討論什么是線性規(guī)劃問題，線性規(guī)劃問題的數(shù)學(xué)表示，基本理論、概念和求解方法。線性規(guī)劃問題是什么樣的一類問題呢？請看案例------第3頁，共71頁，2023年，2月20日，星期一線性規(guī)劃LinearProgramming（LP）

案例1河流污染治理規(guī)劃問題

曾幾何時長江水，哺育華夏代代人，誰知后代疏珍惜，清清江水黑如泥。第4頁，共71頁，2023年，2月20日，星期一線性規(guī)劃LinearProgramming（LP）

案例1河流污染治理規(guī)劃問題

曾幾何時長江水，哺育華夏代代人，誰知后代疏珍惜，清清江水黑如泥。工廠2工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠7第5頁，共71頁，2023年，2月20日，星期一線性規(guī)劃LinearProgramming（LP）

案例1河流污染治理規(guī)劃問題

曾幾何時長江水，哺育華夏代代人，誰知后代疏珍惜，清清江水黑如泥。今日認識未為晚，吾輩齊心治環(huán)境，線性規(guī)劃大有用，定讓江水綠如藍。工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠2工廠7第6頁，共71頁，2023年，2月20日，星期一線性規(guī)劃LinearProgramming（LP）

案例1河流污染治理規(guī)劃問題

今日認識未為晚，吾輩齊心治環(huán)境，線性規(guī)劃大有用，定讓江水綠如藍。曾幾何時長江水，哺育華夏代代人，誰知后代疏珍惜，清清江水黑如泥。工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠2工廠7第7頁，共71頁，2023年，2月20日，星期一985714263線性規(guī)劃LinearProgramming（LP）

案例1河流污染治理規(guī)劃問題化工廠1化工廠2化工廠3化工廠4化工廠6化工廠9化工廠8

500300180012006004001200200700化工廠1化工廠2化工廠3化工廠4化工廠5化工廠6化工廠9化工廠8化工廠7352456123化工廠5化工廠7表-2流經(jīng)各化工廠的河流流量單位：萬m3

表-3治理工業(yè)污水的成本單位：百萬元/萬m3

第8頁，共71頁，2023年，2月20日，星期一419582637線性規(guī)劃LinearProgramming（LP）

案例1河流污染治理規(guī)劃問題化工廠1化工廠2化工廠3化工廠4化工廠5化工廠6化工廠9化工廠8化工廠71.21

3

1

1

20.81.5

2背景資料:

長江流域某區(qū)域內(nèi)有9化工廠，各廠每月產(chǎn)生的工業(yè)污水量如表-1，流經(jīng)各化工廠的河流流量如表-2，各化工廠治理工業(yè)污水的成本如表-3。上游廠排放的污水流到相鄰下游廠以前，有20%可自然凈化。根據(jù)環(huán)保標準河流中此種工業(yè)污水的含量不應(yīng)超過0.2%。從該區(qū)域整體考慮，各化工廠應(yīng)該分別處理多少工業(yè)污水才能既滿足環(huán)保要求，又使9化工廠治理工業(yè)污水的總費用最少。表-1污水排放量單位：萬m3第9頁，共71頁，2023年，2月20日，星期一線性規(guī)劃LinearProgramming（LP）

案例1河流污染治理規(guī)劃問題問題分析：區(qū)域污染治理的決策——各個化工廠應(yīng)處理的工業(yè)污水量（或應(yīng)排放的工業(yè)污水量）。區(qū)域污染治理的約束——即滿足環(huán)保要求排放工業(yè)污水（區(qū)域內(nèi)河流中任何點檢測都應(yīng)符合環(huán)保標準）。區(qū)域污染治理的目標——總治理成本最少。第10頁，共71頁，2023年，2月20日，星期一線性規(guī)劃LinearProgramming（LP）

案例1河流污染治理規(guī)劃問題模型描述：設(shè)第i個化工廠應(yīng)處理的工業(yè)污水量為Xi萬m3，則根據(jù)問題描述的情況以化工廠1、2、…、9加以分析則可得如下近似關(guān)系式對化工廠2應(yīng)有---（1-X2）/300≦0.2%對化工廠8應(yīng)有---（2-X8）/200≦0.2%對化工廠1應(yīng)有---（3-X1）+0.8（1-X2）+（2-X8）/500≦0.2%對化工廠9應(yīng)有---（1.5-X9）/700≦0.2%對化工廠7應(yīng)有---（2-X7）+0.8（1.5-X9）/1200≦0.2%對化工廠4應(yīng)有---（2-X4）+0.8（2-X7）+0.8（1.5-X9）/1200≦

0.2%對化工廠6應(yīng)有---（1-X6）/400≦0.2%對化工廠5應(yīng)有---（1-X5）+0.8（1-X6）/600≦0.2%第11頁，共71頁，2023年，2月20日，星期一線性規(guī)劃LinearProgramming（LP）

案例1河流污染治理規(guī)劃問題對化工廠3應(yīng)有---（3-X3）+0.8（1-X5）+0.8（1-X6）+0.8（2-X4）+0.8（2-X7）+0.8（1.5-X9）/1800≦0.2%此外顯然Xi≧0（i=1，2，3…8，9）綜上所述決策者所需考慮的區(qū)域內(nèi)各個化工廠應(yīng)處理的工業(yè)污水量Xi應(yīng)滿足上述所有不等式方程。我們將這些不等式方程構(gòu)成的方程組稱為污水治理的約束條件。另一方面污水治理的總成本可表示為ZZ=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9而決策者的目標是確定滿足約束條件的Xi使得Z取得最小值。將上述分析歸納后即可得如下數(shù)學(xué)符合模型：第12頁，共71頁，2023年，2月20日，星期一線性規(guī)劃LinearProgramming（LP）

案例1河流污染治理規(guī)劃問題s.t.MinZ=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9

（1-X2）/300≦0.2%

（2-X8）/200≦0.2%

（3-X1）+0.8（1-X2）+（2-X8）/500≦0.2%

（1.5-X9）/700≦0.2%

（2-X7）+0.8（1.5-X9）/1200≦0.2%

（2-X4）+0.8（2-X7）+0.8（1.5-X9）/1200≦0.2%

（1-X6）/400≦0.2%

（1-X5）+0.8（1-X6）/600≦0.2%

（3-X3）+0.8（1-X5）+0.8（1-X6）+0.8（2-X4）+0.8（2-X7）

+0.8（1.5-X9）/1800≦0.2%

Xi≧0（i=1，2，3，4，5，6，7，8，9）*s.t.——subjectto第13頁，共71頁，2023年，2月20日，星期一線性規(guī)劃LinearProgramming（LP）

案例1河流污染治理規(guī)劃問題s.t.整理后模型：

MinZ=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9

X2≧0.4X8≧1.6X1+0.8X2+0.8X8≧4.4X9≧0.1X7+0.8X9≧0.8X4+0.8X7+0.64X9≧2.16X6≧0.2X5+0.8X6≧0.6X3+0.8X4+0.8X5+0.64X6+0.64X7+5.12X9≧9.4Xi≧0（i=1，2，3，4，5，6，7，8，9）此模型稱為線性規(guī)劃模型LinearProgrammingModel第14頁，共71頁，2023年，2月20日，星期一線性規(guī)劃問題的數(shù)學(xué)模型1.規(guī)劃問題生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。線性規(guī)劃通常解決下列兩類問題：（1）當(dāng)任務(wù)或目標確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè)備、原標材料、人工、時間等）去完成確定的任務(wù)或目標（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟效益（如產(chǎn)品量最多、利潤最大.）第15頁，共71頁，2023年，2月20日，星期一線性規(guī)劃問題的數(shù)學(xué)模型例1.1如圖所示，如何截取x使鐵皮所圍成的容積最大？xa第16頁，共71頁，2023年，2月20日，星期一線性規(guī)劃問題的數(shù)學(xué)模型例1.2

某企業(yè)計劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分別要在A、B、C、D、四種不同的設(shè)備上加工。按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺時如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計劃，使企業(yè)總的利潤最大？設(shè)備產(chǎn)品

A

B

C

D利潤（元）甲

2

1

4

0

2乙

2

2

0

4

3有效臺時

12

8

16

12第17頁，共71頁，2023年，2月20日，星期一線性規(guī)劃問題的數(shù)學(xué)模型解：設(shè)x1、x2分別為甲、乙兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為：maxZ=2x1+3x2

x1≥0,x2≥0s.t.

2x1+2x2≤12x1+2x2≤84x1≤164x2≤12第18頁，共71頁，2023年，2月20日，星期一線性規(guī)劃問題的數(shù)學(xué)模型2.線性規(guī)劃的數(shù)學(xué)模型由三個要素構(gòu)成決策變量Decisionvariables目標函數(shù)Objectivefunction約束條件Constraints其特征是：（1）問題的目標函數(shù)是多個決策變量的線性函數(shù)，通常是求最大值或最小值；（2）問題的約束條件是一組多個決策變量的線性不等式或等式。

怎樣辨別一個模型是線性規(guī)劃模型？

第19頁，共71頁，2023年，2月20日，星期一線性規(guī)劃問題的數(shù)學(xué)模型目標函數(shù)：約束條件：3.線性規(guī)劃數(shù)學(xué)模型的一般形式簡寫為：第20頁，共71頁，2023年，2月20日，星期一線性規(guī)劃問題的數(shù)學(xué)模型向量形式：其中：第21頁，共71頁，2023年，2月20日，星期一線性規(guī)劃問題的數(shù)學(xué)模型矩陣形式：其中：第22頁，共71頁，2023年，2月20日，星期一線性規(guī)劃問題的數(shù)學(xué)模型3.線性規(guī)劃問題的標準形式特點：(1)目標函數(shù)求最大值（有時求最小值）(2)約束條件都為等式方程，且右端常數(shù)項bi都大于或等于零(3)決策變量xj為非負。第23頁，共71頁，2023年，2月20日，星期一線性規(guī)劃問題的數(shù)學(xué)模型（2）如何化標準形式目標函數(shù)的轉(zhuǎn)換如果是求極小值即，則可將目標函數(shù)乘以(-1)，可化為求極大值問題。也就是：令，可得到上式。即

若存在取值無約束的變量，可令其中：變量的變換第24頁，共71頁，2023年，2月20日，星期一線性規(guī)劃問題的數(shù)學(xué)模型約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。稱為松弛變量稱為剩余變量變量的變換可令，顯然第25頁，共71頁，2023年，2月20日，星期一線性規(guī)劃問題的數(shù)學(xué)模型例1.3將下列線性規(guī)劃問題化為標準形式用替換，且解:（１）因為x3無符號要求，即x3取正值也可取負值，標準型中要求變量非負，所以第26頁，共71頁，2023年，2月20日，星期一線性規(guī)劃問題的數(shù)學(xué)模型(2)第一個約束條件是“≤”號，在“≤”左端加入松馳變量x4，x4≥0,化為等式；(3)第二個約束條件是“≥”號，在“≥”左端減去剩余變量x5，x5≥0；(4)第3個約束方程右端常數(shù)項為-5，方程兩邊同乘以(-1),將右端常數(shù)項化為正數(shù)；(5)目標函數(shù)是最小值，為了化為求最大值，令z′=-z,得到maxz′=-z，即當(dāng)z達到最小值時z′達到最大值，反之亦然;第27頁，共71頁，2023年，2月20日，星期一線性規(guī)劃問題的數(shù)學(xué)模型標準形式如下：第28頁，共71頁，2023年，2月20日，星期一線性規(guī)劃問題的數(shù)學(xué)模型4.線性規(guī)劃問題的解線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組中找出一個解，使目標函數(shù)(1)達到最大值。第29頁，共71頁，2023年，2月20日，星期一線性規(guī)劃問題的數(shù)學(xué)模型

可行解：滿足約束條件②、③的解為可行解。所有可行解的集合為可行域。

最優(yōu)解：使目標函數(shù)達到最大值的可行解。

基：設(shè)A為約束條件②的m×n階系數(shù)矩陣(m<n)，其秩為m，B是矩陣A中m階滿秩子矩陣（∣B∣≠0），稱B是規(guī)劃問題的一個基。設(shè)：稱B中每個列向量Pj(j=12…

…m)

為基向量。與基向量Pj

對應(yīng)的變量xj

為基變量。除基變量以外的變量為非基變量。第30頁，共71頁，2023年，2月20日，星期一線性規(guī)劃問題的數(shù)學(xué)模型

基解：某一確定的基B，令非基變量等于零，由約束條件方程②解出基變量，稱這組解為基解。在基解中變量取非0值的個數(shù)不大于方程數(shù)m，基解的總數(shù)不超過

基可行解：滿足變量非負約束條件的基本解，簡稱基可行解。可行基：對應(yīng)于基可行解的基稱為可行基。非可行解可行解基解基可行解第31頁，共71頁，2023年，2月20日，星期一線性規(guī)劃問題的數(shù)學(xué)模型例1.4求線性規(guī)劃問題的所有基矩陣。解:約束方程的系數(shù)矩陣為2×5矩陣r(A)=2，2階子矩陣有10個，其中基矩陣只有9個，即第32頁，共71頁，2023年，2月20日，星期一圖解法線性規(guī)劃問題的求解方法一般有兩種方法圖解法單純形法兩個變量、直角坐標三個變量、立體坐標適用于任意變量、但必需將一般形式變成標準形式下面我們分析一下簡單的情況——

只有兩個決策變量的線性規(guī)劃問題，這時可以通過圖解的方法來求解。圖解法具有簡單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點。第33頁，共71頁，2023年，2月20日，星期一圖解法maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0例1.5用圖解法求解線性規(guī)劃問題第34頁，共71頁，2023年，2月20日，星期一圖解法x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)4=2X1+X2

20=2X1+X2

17.2=2X1+X2

11=2X1+X2

Lo：0=2X1+X2

（7.6，2）DmaxZminZ此點是唯一最優(yōu)解，且最優(yōu)目標函數(shù)值

maxZ=17.2可行域maxZ=2X1+X2第35頁，共71頁，2023年，2月20日，星期一圖解法maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)（7.6，2）DL0：0=3X1+5.7X2

maxZ（3.8，4）34.2=3X1+5.7X2

藍色線段上的所有點都是最優(yōu)解這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標函數(shù)值maxZ=34.2是唯一的?？尚杏虻?6頁，共71頁，2023年，2月20日，星期一圖解法minZ=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1+1.9X2=10.2(≤)DL0：0=5X1+4X2

maxZ

minZ

8=5X1+4X2

43=5X1+4X2

（0，2）可行域此點是唯一最優(yōu)解第37頁，共71頁，2023年，2月20日，星期一圖解法246x1x2246無界解(無最優(yōu)解)maxZ=x1+2x2例1.6x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)

maxZ

minZ第38頁，共71頁，2023年，2月20日，星期一x1x2O10203040102030405050無可行解(即無最優(yōu)解)maxZ=3x1+4x2例1.7第39頁，共71頁，2023年，2月20日，星期一圖解法 學(xué)習(xí)要點：

1.通過圖解法了解線性規(guī)劃有幾種解的形式（唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解）

2.作圖的關(guān)鍵有三點：

(1)可行解區(qū)域要畫正確

(2)目標函數(shù)增加的方向不能畫錯

(3)目標函數(shù)的直線怎樣平行移動第40頁，共71頁，2023年，2月20日，星期一單純形法基本原理凸集：如果集合C中任意兩個點X1、X2，其連線上的所有點也都是集合C中的點，稱C為凸集。凸集凸集不是凸集頂點第41頁，共71頁，2023年，2月20日，星期一單純形法基本原理定理1：若線性規(guī)劃問題存在可行解，則該問題的可行域是凸集。定理2：線性規(guī)劃問題的基可行解X對應(yīng)可行域(凸集)的頂點。定理3：若問題存在最優(yōu)解，一定存在一個基可行解是最優(yōu)解。（或在某個頂點取得）第42頁，共71頁，2023年，2月20日，星期一單純形法的計算步驟單純形法的思路找出一個初始可行解是否最優(yōu)轉(zhuǎn)移到另一個基本可行解（找出更大的目標函數(shù)值）最優(yōu)解是否循環(huán)核心是：變量迭代結(jié)束第43頁，共71頁，2023年，2月20日，星期一單純形法的計算步驟單純形表第44頁，共71頁，2023年，2月20日，星期一單純形法的計算步驟例1.8用單純形法求下列線性規(guī)劃的最優(yōu)解解：1）將問題化為標準型，加入松馳變量x3、x4則標準型為:第45頁，共71頁，2023年，2月20日，星期一單純形法的計算步驟2）求出線性規(guī)劃的初始基可行解，列出初始單純形表。cj3400θicB基bx1x2x3x40x34021100x43013013400檢驗數(shù)第46頁，共71頁，2023年，2月20日，星期一單純形法的計算步驟3）進行最優(yōu)性檢驗如果表中所有檢驗數(shù)，則表中的基可行解就是問題的最優(yōu)解，計算停止。否則繼續(xù)下一步。4）從一個基可行解轉(zhuǎn)換到另一個目標值更大的基可行解，列出新的單純形表確定換入基的變量。選擇，對應(yīng)的變量xj作為換入變量，當(dāng)有一個以上檢驗數(shù)大于0時，一般選擇最大的一個檢驗數(shù)，即：，其對應(yīng)的xk作為換入變量。確定換出變量。根據(jù)下式計算并選擇θ

，選最小的θ對應(yīng)基變量作為換出變量。 第47頁，共71頁，2023年，2月20日，星期一單純形法的計算步驟用換入變量xk替換基變量中的換出變量，得到一個新的基。對應(yīng)新的基可以找出一個新的基可行解，并相應(yīng)地可以畫出一個新的單純形表。5）重復(fù)3）、4）步直到計算結(jié)束為止。 第48頁，共71頁，2023年，2月20日，星期一單純形法的計算步驟cj3400θicB基變量bx1x2x3x40x34021100x430130134000x34x23x14x2換入列bi/ai2，ai2>04010換出行將3化為15/311801/301/3101－1/3303005/30－4/3乘以1/3后得到103/5－1/51801－1/5－2/5400－1－1第49頁，共71頁，2023年，2月20日，星期一單純形法的計算步驟例1.9用單純形法求解解：將數(shù)學(xué)模型化為標準形式：不難看出x4、x5可作為初始基變量，列單純形表計算。第50頁，共71頁，2023年，2月20日，星期一單純形法的計算步驟cj12100θicB基變量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220－x221/3150120753017131/30－90－22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3第51頁，共71頁，2023年，2月20日，星期一單純形法的計算步驟 學(xué)習(xí)要點：

1.線性規(guī)劃解的概念以及3個基本定理

2.熟練掌握單純形法的解題思路及求解步驟第52頁，共71頁，2023年，2月20日，星期一單純形法的進一步討論－人工變量法人工變量法： 前面討論了在標準型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。第53頁，共71頁，2023年，2月20日，星期一單純形法的進一步討論－人工變量法例1.10用大M法解下列線性規(guī)劃解：首先將數(shù)學(xué)模型化為標準形式系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。第54頁，共71頁，2023年，2月20日，星期一單純形法的進一步討論－人工變量法故人為添加兩個單位向量，得到人工變量單純形法數(shù)學(xué)模型：其中：M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介紹的單純形法求解該模型，計算結(jié)果見下表。第55頁，共71頁，2023年，2月20日，星期一單純形法的進一步討論－人工變量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7θi0x64-431-10104-Mx5101-1201005-Mx712-21000113-2M2+M-1+2M↑-M0x63-650-1013/5-Mx58-3300108/3-1x312-21000——5-6M5M↑0-M002x23/5－6/510－1/50——-Mx531/53/5003/5131/3-1x311/5－2/501－2/50——5↑00002x213010123x131/310015/3-1x319/300102/3000-5-25/3→→→第56頁，共71頁，2023年，2月20日，星期一單純形法的進一步討論－人工變量法 解的判別：1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗數(shù)非零,則線規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解（或無窮多最優(yōu)解）。3）無界解判別：某個λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無界解。4）無可行解的判斷：當(dāng)用大M單純形法計算得到最優(yōu)解并且存在Ri>0時，則表明原線性規(guī)劃無可行解。5）退化解的判別：存在某個基變量為零的基本可行解。第57頁，共71頁，2023年，2月20日，星期一單純形法的進一步討論－人工變量法單純性法小結(jié):建立模型個數(shù)取值右端項等式或不等式極大或極小新加變量系數(shù)兩個三個以上xj≥0xj無約束xj≤0

bi

≥0bi<0≤=≥maxZminZxs

xa求解圖解法、單純形法單純形法不處理令xj=

xj′

-xj″

xj′

≥0xj″

≥0令

xj’

=-xj不處理約束條件兩端同乘以-1加松弛變量xs加入人工變量xa減去xs加入xa不處理令z′=-ZminZ=－maxz′0-M第58頁，共71頁，2023年，2月20日，星期一A第59頁，共71頁，2023年，2月20日，星期一線性規(guī)劃模型的應(yīng)用 一般而言，一個經(jīng)濟、管理問題凡是滿足以下條件時，才能建立線性規(guī)劃模型。要求解問題的目標函數(shù)能用數(shù)值指標來反映，且為線性函數(shù)存在著多種方案要求達到的目標是在一定條件下實現(xiàn)的，這些約束可用線性等式或不等式描述第60頁，共71頁，2023年，2月20日，星期一線性規(guī)劃在管理中的應(yīng)用人力資源分配問題例1.11某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員人數(shù)如下表所示：班次時間所需人員16:00——10:0060210:00——14:0070314:00——18:0060418:00——22:0050522:00——2:002062:00——6:0030設(shè)司機和乘務(wù)人員分別在各時間段開始時上班，并連續(xù)工作8小時，問該公交線路應(yīng)怎樣安排司機和乘務(wù)人員，即能滿足工作需要，又使配備司機和乘務(wù)人員的人數(shù)減少?第61頁，共71頁，2023年，2月20日，星期一線性規(guī)劃在管理中的應(yīng)用解：設(shè)xi表示第i班次時開始上班的司機和乘務(wù)人員人數(shù)。此問題最優(yōu)解：x1＝50，x2