運(yùn)籌學(xué)01線性規(guī)劃

線性規(guī)劃及單純形法第一章1、LP的數(shù)學(xué)模型

2、圖解法

3、單純形法

4、單純形法的進(jìn)一步討論－人工變量法

5、LP模型的應(yīng)用本章主要內(nèi)容：2023/1/313一線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.規(guī)劃問(wèn)題生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問(wèn)題。線性規(guī)劃通常解決下列兩類問(wèn)題：（1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo)（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多、利潤(rùn)最大.）2023/1/314例1.1如圖所示，如何截取x使鐵皮所圍成的容積最大？xa一元函數(shù)極值問(wèn)題，高等數(shù)學(xué)微分解決。多元呢？2023/1/315例1.2某廠生產(chǎn)兩種產(chǎn)品，下表給出了單位產(chǎn)品所需資源及單位產(chǎn)品利潤(rùn)問(wèn)：應(yīng)如何安排每天的生產(chǎn)計(jì)劃，使總利潤(rùn)最大？解：1.決策變量：設(shè)產(chǎn)品I、II的產(chǎn)量分別為x1、x22.目標(biāo)函數(shù)：設(shè)總利潤(rùn)為z，則有：

maxz=2x1+x23.約束條件：

5x2≤156x1+2x2≤24x1+x2≤5

x1，x2≥0生產(chǎn)問(wèn)題2023/1/316例1.3養(yǎng)海貍鼠飼料中營(yíng)養(yǎng)要求：VA每天至少700克，VB每天至少30克，VC每天剛好200克，每種飼料不能超過(guò)用量要求。現(xiàn)有五種飼料，搭配使用，飼料成分如下表。問(wèn)如何搭配使用飼料使總成本最低？飼料VaVbVc價(jià)格元/KG用量要求IIIIIIIVV32161810.50.220.50.510.220.8274955060507040營(yíng)養(yǎng)要求70030200配方問(wèn)題2023/1/317例題1.3建模設(shè)抓取飼料Ix1kg;飼料IIx2kg;飼料IIIx3kg……目標(biāo)函數(shù)（最省錢）：minZ=2x1+7x2+4x3+9x4+5x5約束條件（營(yíng)養(yǎng)要求）：3x1+2x2+x3+6x4+18x5

≥700x1+0.5x2+0.2x3+2x4+0.5x5≥300.5x1+x2+0.2x3+2x4+0.8x5=200用量要求：x1

≤50,x2≤60,x3≤50,x4≤70,x5≤40非負(fù)性要求：x1

≥0,x2≥0,x3≥0,x4≥0,x5≥02023/1/318例1.4醫(yī)院護(hù)士24小時(shí)值班，每次值班8小時(shí)。不同時(shí)段需要的護(hù)士人數(shù)不等。據(jù)統(tǒng)計(jì)：解：1.決策變量：2.目標(biāo)函數(shù)：

minZ=x1+x2+x3+x4+x5+x63.約束條件：

序號(hào)時(shí)段最少人數(shù)安排人數(shù)106—1060X1210—1470X2314—1860X3418—2250X4522—0220X5602—0630x6x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30

x6+x1≥60非負(fù)性約束：xj

≥0,j=1,2,…6決策變量人力資源問(wèn)題2023/1/319例1.5靠近某河流有兩個(gè)化工廠，流經(jīng)第一化工廠的河流流量為每天500萬(wàn)m3，兩工廠之間有一條流量為每天200萬(wàn)m3的支流（見(jiàn)圖）。

第一化工廠每天排放污水2萬(wàn)m3，第二化工廠每天排放污水1.4萬(wàn)m3。污水從工廠1流到工廠2前會(huì)有20%自然凈化。根據(jù)環(huán)保要求，河水中污水的含量應(yīng)不大于0.2%。而工廠1和工廠2處理污水的成本分別為1000元/萬(wàn)m3和800元/萬(wàn)m3。問(wèn)兩工廠各應(yīng)處理多少污水才能使處理污水的總費(fèi)用最低？環(huán)保問(wèn)題2023/1/3110這個(gè)問(wèn)題可用數(shù)學(xué)模型來(lái)描述。設(shè)第一化工廠每天處理工業(yè)污水量為x1萬(wàn)m3，第二化工廠每天處理工業(yè)污水量為x2萬(wàn)m3。問(wèn)題的目標(biāo)是要求兩廠用于處理工業(yè)污水的總費(fèi)用最小，則目標(biāo)函數(shù)為從第一化工廠到第二化工廠之間，河流中工業(yè)污水含量要不大于0.2%，由此可得近似關(guān)系式流經(jīng)第二化工廠后，河流中的工業(yè)污水量仍要不大于0.2%，這時(shí)有近似關(guān)系式由于每個(gè)工廠每天處理工業(yè)污水量不會(huì)大于每天的排放量，故有2023/1/3111例題1.5建模綜合上述，這個(gè)環(huán)保問(wèn)題可以數(shù)學(xué)模型表示為：

目標(biāo)函數(shù)：

約束條件：2023/1/3112

例1.6

某航運(yùn)局現(xiàn)有船只種類、數(shù)量以及計(jì)劃期內(nèi)各條航線的貨運(yùn)量、貨運(yùn)成本如下表所示：航線號(hào)船隊(duì)類型編隊(duì)形式貨運(yùn)成本（千元／隊(duì)）貨運(yùn)量（千噸）拖輪A型駁船B型駁船1112—362521—4362023224724041—42720船只種類船只數(shù)拖輪30A型駁船34B型駁船52航線號(hào)合同貨運(yùn)量12002400問(wèn)：應(yīng)如何編隊(duì)，才能既完成合同任務(wù)，又使總貨運(yùn)成本為最??？運(yùn)輸問(wèn)題2023/1/3113

解：設(shè)：xj為第j號(hào)類型船隊(duì)的隊(duì)數(shù)（j=1，2，3，4），

z為總貨運(yùn)成本則：

minz=36x1+36x2+72x3+27x4

x1+x2+2x3+x4≤302x1+2x3≤344x2+4x3+4x4≤5225x1+20x2

＝20040x3+20x4＝400

xj

≥0（j=1,2,3,4）2023/1/3114線性規(guī)劃問(wèn)題的數(shù)學(xué)模型2.線性規(guī)劃的數(shù)學(xué)模型由三個(gè)要素構(gòu)成決策變量Decisionvariables目標(biāo)函數(shù)Objectivefunction約束條件Constraints其特征是：（1）問(wèn)題的目標(biāo)函數(shù)是多個(gè)決策變量的線性函數(shù)，通常是求最大值或最小值；（2）問(wèn)題的約束條件是一組多個(gè)決策變量的線性不等式或等式。

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

2023/1/3115線性規(guī)劃問(wèn)題的數(shù)學(xué)模型3.建模條件(1)

優(yōu)化條件：?jiǎn)栴}所要達(dá)到的目標(biāo)能用線型函數(shù)描述，且能夠用極值

（max或min）來(lái)表示；(2)

限定條件：達(dá)到目標(biāo)受到一定的限制，且這些限制能夠用決策變量的

線性等式或線性不等式表示；(3)

選擇條件：有多種可選擇的方案供決策者選擇，以便找出最優(yōu)方案。2023/1/3116線性規(guī)劃問(wèn)題的數(shù)學(xué)模型4.建模步驟(1)

確定決策變量：即需要我們作出決策或選擇的量。一般情況下，題目問(wèn)什么就設(shè)什么為決策變量；(2)

找出所有限定條件：即決策變量受到的所有的約束；(3)

寫出目標(biāo)函數(shù)：即問(wèn)題所要達(dá)到的目標(biāo)，并明確是max還是min。2023/1/3117線性規(guī)劃問(wèn)題的數(shù)學(xué)模型5.線性規(guī)劃的概念對(duì)于求取一組變量xj(j=1,2,…..,n)，使之既滿足線性約束條件，又使具有線性的目標(biāo)函數(shù)取得極值的一類最優(yōu)化問(wèn)題稱為線性規(guī)劃問(wèn)題。LinearProgramming簡(jiǎn)記為L(zhǎng)P2023/1/3118一般形式：max（或min）

目標(biāo)函數(shù)約束條件非負(fù)約束稱為決策變量

稱為價(jià)值系數(shù)

稱為資源常數(shù)或約束右端常數(shù)稱為技術(shù)系數(shù)或約束系數(shù)

2023/1/3119緊縮形式：max（或min）

i=1,2,…..,m

“s.t.”是“subjectto”的縮寫，表示“滿足于……”。2023/1/3120矩陣形式：max（或min）

稱為決策變量向量

稱為價(jià)值系數(shù)向量

稱為資源常數(shù)向量或約束右端常數(shù)向量稱為技術(shù)系數(shù)或約束系數(shù)矩陣

2023/1/31216.線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式特點(diǎn)：(1)目標(biāo)函數(shù)求最大值（有時(shí)求最小值）(2)約束條件都為等式方程，且右端常數(shù)項(xiàng)bi都大于或等于零(3)決策變量xj為非負(fù)。線性規(guī)劃問(wèn)題的數(shù)學(xué)模型2023/1/3122（2）如何化標(biāo)準(zhǔn)形式

目標(biāo)函數(shù)的轉(zhuǎn)換

如果是求極小值即，則可將目標(biāo)函數(shù)乘以(-1)，可化為求極大值問(wèn)題。也就是：令，可得到上式。即

若存在取值無(wú)約束的變量，可令其中：

變量的變換

若存在取值變量≤0

，可令其中：2023/1/3123

約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。稱為松弛變量稱為剩余變量

常量bi＜0

的變換:約束方程兩邊乘以（－1）i=1,2,…..,m

i=1,2,…..,m

2023/1/3124例1.7

將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式用替換，且解:（１）因?yàn)閤3無(wú)符號(hào)要求，即x3取正值也可取負(fù)值也可，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以2023/1/3125(2)第一個(gè)約束條件是“≤”號(hào)，在“≤”左端加入松馳變量x4，x4≥0,化為等式；(3)第二個(gè)約束條件是“≥”號(hào)，在“≥”左端減去剩余變量x5，x5≥0；(4)第3個(gè)約束方程右端常數(shù)項(xiàng)為-5，方程兩邊同乘以(-1),將右端常數(shù)項(xiàng)化為正數(shù)；(5)目標(biāo)函數(shù)是最小值，為了化為求最大值，令z′=-z,得到maxz′=-z，即當(dāng)z達(dá)到最小值時(shí)z′達(dá)到最大值，反之亦然;2023/1/3126標(biāo)準(zhǔn)形式如下：2023/1/3127

例1.8將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式為無(wú)約束（無(wú)非負(fù)限制）2023/1/3128

解:用替換，且，將第3個(gè)約束方程兩邊乘以（－1）將極小值問(wèn)題反號(hào)，變?yōu)榍髽O大值標(biāo)準(zhǔn)形式如下：引入變量2023/1/3129

例1.9將線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型解：2023/1/3130

例1.10將線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型解：Minz=-3x1

+5x2+8x3

-7x4s.t.2x1

-3x2+5x3+6x4

≤284x1

+2x2+3x3-9x4

≥396x2+2x3+3x4≤-58

x1,x3,x4

≥0；x2無(wú)約束

Maxz=3x1–5x2’+5x2”–8x3+7x4

s.t.2x1–3x2’+3x2”+5x3+6x4+x5=284x1+2x2’-2x2”+3x3-9x4-x6=39-6x2’+6x2”-2x3-3x4-x7

=58

x1,x2’,x2”,x3,x4,x5,x6,x7

≥0

2023/1/3131線性規(guī)劃問(wèn)題的數(shù)學(xué)模型7.線性規(guī)劃問(wèn)題的解求解線性規(guī)劃問(wèn)題，就是從滿足約束條件(2)、(3)的方程組中找出一個(gè)解，使目標(biāo)函數(shù)(1)達(dá)到最大值。

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

最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。2023/1/3132二圖解法線性規(guī)劃問(wèn)題的求解方法一般有兩種方法圖解法單純形法兩個(gè)變量、直角坐標(biāo)三個(gè)變量、立體坐標(biāo)適用于任意變量、但必需將一般形式變成標(biāo)準(zhǔn)形式下面我們分析一下簡(jiǎn)單的情況——

只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題，這時(shí)可以通過(guò)圖解的方法來(lái)求解。圖解法具有簡(jiǎn)單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點(diǎn)。2023/1/3133

解題步驟4將最優(yōu)解代入目標(biāo)函數(shù)，求出最優(yōu)值。1在直角平面坐標(biāo)系中畫出所有的約束等式，并找出所有約束條件的公共部分，稱為可行域，可行域中的點(diǎn)稱為可行解。2標(biāo)出目標(biāo)函數(shù)值增加或者減小的方向。3若求最大（?。┲?，則令目標(biāo)函數(shù)等值線沿（逆）目標(biāo)函數(shù)值增加的方向平行移動(dòng)，找與可行域最后相交的點(diǎn)，該點(diǎn)就是最優(yōu)解。二圖解法2023/1/3134maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0例1.11用圖解法求解線性規(guī)劃問(wèn)題2023/1/3135x1x2oX1-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）RmaxZminZ此點(diǎn)是唯一最優(yōu)解，且最優(yōu)目標(biāo)函數(shù)值

maxZ=17.2可行域maxZ=2X1+X22023/1/3136maxZ=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）RL0：0=3X1+5.7X2

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

藍(lán)色線段上的所有點(diǎn)都是最優(yōu)解這種情形為有無(wú)窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值maxZ=34.2是唯一的?？尚杏?023/1/3137minZ=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1+1.9X2=10.2(≤)RL0：0=5X1+4X2

maxZminZ8=5X1+4X2

43=5X1+4X2

（0，2）可行域此點(diǎn)是唯一最優(yōu)解2023/1/3138246x1x2246無(wú)界解(無(wú)最優(yōu)解)maxZ=x1+2x2例1.6x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZ2023/1/3139x1x2O10203040102030405050無(wú)可行解(即無(wú)最優(yōu)解)maxZ=3x1+4x2例1.72023/1/3140分析解的情況：（1）可行域?yàn)榉忾]有界區(qū)域

Ox2x1第一種情況：有無(wú)窮最優(yōu)解第二種情況：有唯一最優(yōu)解2023/1/3141（2）可行域?yàn)榉欠忾]區(qū)域Ox2x1唯一最優(yōu)解無(wú)界解無(wú)窮最優(yōu)解

可能在建模過(guò)程中，忽略了必要的約束條件。2023/1/3142（3）可行域?yàn)榭占痻1Ox2沒(méi)有可行解，原問(wèn)題無(wú)最優(yōu)解

可能在建模過(guò)程中，約束條件自相矛盾的錯(cuò)誤。2023/1/3143凸集：如果集合C中任意兩個(gè)點(diǎn)X1、X2，其連線上的所有點(diǎn)也都是集合C中的點(diǎn)，稱C為凸集。凸集凸集不是凸集頂點(diǎn)

頂點(diǎn)：凸集C中不存在任何兩個(gè)不同的點(diǎn)X1，X2，使X成為這兩個(gè)點(diǎn)連線上的一個(gè)點(diǎn)凸集的概念2023/1/3144

由圖解法得到的啟示(1)線性規(guī)劃問(wèn)題解的情況：唯一最優(yōu)解；無(wú)窮多最優(yōu)解；無(wú)界解；無(wú)可行解(3)最優(yōu)解一定是在凸集的某個(gè)頂點(diǎn)(2)線性規(guī)劃問(wèn)題的可行域是凸集（若有兩點(diǎn)在該區(qū)域中，則連線上的所有點(diǎn)也在其中，這樣的集合稱為凸集）；(4)解題思路是，先找出凸集的任一頂點(diǎn)，計(jì)算其目標(biāo)函數(shù)值，再與周圍頂點(diǎn)的目標(biāo)函數(shù)值比較，如不是最大，繼續(xù)比較，直到找出最大為止。2023/1/3145LP解的概念可行解：滿足約束條件的解稱為線性規(guī)劃問(wèn)題的可行解，而使目標(biāo)函數(shù)達(dá)到最大值的可行解叫最優(yōu)解?；涸O(shè)A是約束方程組的m×n維系數(shù)矩陣，其秩為m。B是矩陣A的m階滿秩子陣（),則稱B是線性規(guī)劃問(wèn)題的一組基。這就是說(shuō)，矩陣B是由m個(gè)線性無(wú)關(guān)的列向量組成。2023/1/3146為不失一般性，假設(shè)前m個(gè)變量的系數(shù)列向量是線性無(wú)關(guān)的稱Pj(j=1,2,…,m)為基向量，與基向量Pj相應(yīng)的變量xj(j=Pj(j=1,2,…,m)為基變量。否則稱為非基變量。2023/1/3147

下面研究約束方程組的求解問(wèn)題假設(shè)該方程組系數(shù)矩陣A的秩為m,因m<n，故它有無(wú)窮多個(gè)解。假設(shè)前m個(gè)變量的系數(shù)列向量是線性無(wú)關(guān)的。這時(shí)約束方程可寫成（1.1）2023/1/3148或方程組（1.1）的一個(gè)基是（1.2）2023/1/3149設(shè)XB是對(duì)應(yīng)于這個(gè)基的基變量現(xiàn)若令（1.1）的非基變量并用高斯消元法，可以求出一個(gè)解這個(gè)解的非零分量的數(shù)目不大于方程個(gè)數(shù)m，稱X為基本解。由此可見(jiàn)，有一個(gè)基，就可以求出一個(gè)基本解。2023/1/3150基可行解：滿足非負(fù)條件的基本解，稱為基可行解?？梢?jiàn)，基可行解的非零分量的數(shù)目也不大于m,并且都是非負(fù)的?？尚薪猓杭s束方程組的解，并滿足非負(fù)條件?？梢?jiàn)，約束方程組具有基本解的數(shù)目最多是個(gè)。【基可行解】≤【基本解】≤說(shuō)明：基本解中的非零分量的個(gè)數(shù)小于m個(gè)時(shí)，這基本解是退化解。在以下討論時(shí)，假設(shè)不出現(xiàn)退化的情況。2023/1/3151B基N非基基變量非基變量基向量非基向量2023/1/3152當(dāng)取XN=0，這時(shí)有XB=B-1b?；窘獾木仃嚤磉_(dá)形式2023/1/3153例題1.12

求解線性規(guī)劃模型請(qǐng)列出其所有的基、基本解和相應(yīng)的基變量。提示：本例中一共有幾個(gè)基？一般地，m×n

階矩陣A中基的個(gè)數(shù)最多有多少個(gè)？2023/1/3154②-①×5不是基???è?--=12100402001-580800121A2023/1/3155Q4Q3Q2Q1Ox2x112345123452023/1/3156系數(shù)陣A中可找出若干個(gè)基B每個(gè)基B都對(duì)應(yīng)于一個(gè)基本解非負(fù)的基本解就是基可行解幾種解之間的關(guān)系：可行解基本解非可行解基本可行解問(wèn)題：基可行解是可行域中的哪些點(diǎn)？2023/1/3157定理1：若線性規(guī)劃問(wèn)題存在可行解，則該問(wèn)題的可行域是凸集。定理2：線性規(guī)劃問(wèn)題的基可行解X對(duì)應(yīng)可行域(凸集)的頂點(diǎn)。定理3：若問(wèn)題存在最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解。LP解的性質(zhì)2023/1/3158例題1.13

求線性規(guī)劃問(wèn)題的基本解和基可行解2023/1/31592023/1/3160

對(duì)應(yīng)的非基變量2023/1/3161

2023/1/3162

2023/1/3163例題1.142023/1/3164例1.142023/1/3165雖然頂點(diǎn)的數(shù)目是有限的（≤），若采用“枚舉法”找所有基可行解，然后一一比較，最終可能得到最優(yōu)解。但當(dāng)n,m的數(shù)較大時(shí)，這種辦法是行不通的，所以要繼續(xù)討論，如何有效的找到最優(yōu)解的方法，下面要介紹的單純形法。2023/1/3166三單純形法單純形法的思路找出一個(gè)初始基可行解是否最優(yōu)轉(zhuǎn)移到另一個(gè)基可行解（找出更大的目標(biāo)函數(shù)值）最優(yōu)解是否循環(huán)核心是：變量迭代結(jié)束例：某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，主要消耗A、B、C這3種原料，已知單位產(chǎn)品的原料消耗數(shù)量等資料如下表所示。ⅠⅡ原料總量/噸A128B5220C0412產(chǎn)品單價(jià)2萬(wàn)元5萬(wàn)元2023/1/31672023/1/31683.1

單

純形法引例（1.3）（1.4）約束方程組（1.4）的系數(shù)矩陣2023/1/3169從（1.4）中可以看到x3,x4,x5的系數(shù)列向量是線性無(wú)關(guān)的，這些向量構(gòu)成一個(gè)基2023/1/3170對(duì)應(yīng)于B的變量x3,x4,x5為基變量，從（1.4）中可以得到（1.5）將X(0)代人（1.3），得z=2x1+5x2

（1.6）=0令非基變量x1=x2=0，這時(shí)得到一個(gè)基可行解這個(gè)基可行解表示：

工廠沒(méi)有安排生產(chǎn)產(chǎn)品Ⅰ、Ⅱ；資源都沒(méi)有被利用，所以工廠的利潤(rùn)指標(biāo)z=0。2023/1/3171從分析目標(biāo)函數(shù)的表達(dá)式（1.6）可以看到：非基變量x1,x2（即沒(méi)有安排生產(chǎn)的產(chǎn)品Ⅰ、Ⅱ）的系數(shù)都是正數(shù)，因此將非基變量變換基變量，目標(biāo)函數(shù)的值就可能增大。從經(jīng)濟(jì)意義上講，安排生產(chǎn)產(chǎn)品Ⅰ或Ⅱ，就可以使工廠的利潤(rùn)指標(biāo)增加。所以只要在目標(biāo)函數(shù)（1.6）的表達(dá)式中還存在有正系數(shù)的非基變量，這表示目標(biāo)函數(shù)值還有增加的可能，就需要將它換入到基變量中去，同時(shí)還要確定基變量中有一個(gè)要換出來(lái)的非基變量，可以按以下方法來(lái)確定換出基變量。2023/1/3172現(xiàn)分析（1.5）當(dāng)將x2定為換入變量后，必須從x3,x4,x5中換出一個(gè)，并保證x3,x4,x5≥0。當(dāng)x1=0時(shí)，由（1.5）式得到（1.7）從（1.7）可以看出2023/1/3173只有選擇x2=3時(shí)，才能即保證（1.7）成立，又使目標(biāo)函數(shù)值達(dá)到最大。因當(dāng)x2=3時(shí)，x5=0，這就決定用x2去替換x5，使x5成為非基變量。以上數(shù)學(xué)描述說(shuō)明了每生產(chǎn)一件產(chǎn)品Ⅱ，需要用掉各種資源數(shù)為（2，2，4）。由這些資源中的薄弱環(huán)節(jié)，就確定了產(chǎn)品Ⅱ的產(chǎn)量。就是由原材料C的數(shù)量確定了產(chǎn)品Ⅱ的產(chǎn)量x2=12/4=3噸。2023/1/3174為了求得以x3,x4,x2為基變量的一個(gè)基可行解和進(jìn)一步分析問(wèn)題，需將（1.5）中x2的位置與x5的位置對(duì)換（1）（2）（3）（1.5）（1.8）用高斯消元法將（1.8）式中x2的系數(shù)列向量變換為單位列向量，得到（1）`（2）`（3）`（1.9）2023/1/3175再將（1.9）代入目標(biāo)函數(shù)（1.3）得到令非基變量x1=x5=0，得到z=15,并得到另一個(gè)基可行解X(1)從目標(biāo)函數(shù)的表達(dá)式（1.10）中可以看到，非基變量x1的系數(shù)是正的，說(shuō)明目標(biāo)函數(shù)值還可以增大，X(1)不一定是最優(yōu)解。于是再用上述方法，確定換入、換出變量，繼續(xù)迭代，再得到另一個(gè)基可行解X(2)（1.10）2023/1/3176選擇x1入基，在x2,x3,x4中找出退出基，x5=0，則式（1.9）成為可知x1的值應(yīng)滿足條件取x1=2，則x3=0，x3退出基。方程組（1.9）變換為x1,x2,x4的解出形式（1.11）2023/1/3177將（1.11）代入（1.3）中，得到（1.12）非基變量x3=x5=0,z=19,并得到另一個(gè)基可行解X（2）由式（1.12）可見(jiàn)所有非基變量x3,x5的系數(shù)都是負(fù)數(shù)。這說(shuō)明若要用剩余資源x3,x5，就必須支付附加費(fèi)用。所以當(dāng)x3=x5=0時(shí)，即不再利用這些資源時(shí)，目標(biāo)函數(shù)達(dá)到最大值。所以X（2）是最優(yōu)解。即應(yīng)當(dāng)產(chǎn)品Ⅰ生產(chǎn)2噸，產(chǎn)品Ⅱ生產(chǎn)3噸，工廠才能得到最大利潤(rùn)19萬(wàn)元。2023/1/3178單純形方法的基本思想從可行域的一個(gè)基可行解(極點(diǎn))出發(fā)，判別它是否已是最優(yōu)解，如果不是，尋找下一個(gè)基可行解，并使目標(biāo)函數(shù)得到改進(jìn)，如此迭代下去，直到找到最優(yōu)解或判定問(wèn)題無(wú)界為止。將每步迭代得到的結(jié)果與圖解法作對(duì)比，其幾何意義就很清楚了。2023/1/31793.2單純形法的要點(diǎn)和單純形表

1.檢驗(yàn)數(shù)的意義和計(jì)算公式Em（1.15）假定所有b1,…,bm≥0。顯然得到一個(gè)m×m單位矩陣2023/1/3180得出基可行解和相應(yīng)目標(biāo)函數(shù)值以B作為可行基，將（1.15）每個(gè)等式移項(xiàng)得（1.16）令2023/1/3181如果令：目標(biāo)函數(shù)Max，檢驗(yàn)數(shù)≤0，當(dāng)前目標(biāo)函數(shù)值為最大值。如果目標(biāo)函數(shù)Min??（1.18）檢驗(yàn)數(shù)（1.17）2023/1/3182θ2.單純形表2023/1/31833.單純形法的基本法則法則1-1最優(yōu)性判定法則若對(duì)于基可行解Xj,所有檢驗(yàn)數(shù)j≤0

，則Xj,為最優(yōu)解。證:由公式可知,當(dāng)所有檢驗(yàn)數(shù)j≤0

，總有而當(dāng)則為X1為最優(yōu)解。2023/1/3184法則1-2換入變量確定法則原則上，換入變量可在具有正檢驗(yàn)數(shù)的非基變量中任意選取，但通常的方法是選取一個(gè)具有正檢驗(yàn)數(shù)最大的非基變量作為換入變量，稱之為最大σ準(zhǔn)則。其目的是使目標(biāo)函數(shù)值增加的較快，以有可能減少迭代次數(shù)。法則1-3換出變量確定法則為保證新基為可行基，換出變量不能任意選取，按最小θ準(zhǔn)則。法則1-4換基疊代運(yùn)算法則2023/1/31853.3單純形法的計(jì)算步驟例1.15用單純形法求下列線性規(guī)劃的最優(yōu)解解：1）將問(wèn)題化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4則標(biāo)準(zhǔn)型為:2023/1/31862）求出線性規(guī)劃的初始基可行解，列出初始單純形表。cj3400θicBXBbx1x2x3x40x34021100x43013013400檢驗(yàn)數(shù)2023/1/31873）進(jìn)行最優(yōu)性檢驗(yàn)如果表中所有檢驗(yàn)數(shù)，則表中的基可行解就是問(wèn)題的最優(yōu)解，計(jì)算停止。否則繼續(xù)下一步。4）從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)值更大的基可行解，列出新的單純形表確定換入基的變量。選擇，對(duì)應(yīng)的變量xj作為換入變量，當(dāng)有一個(gè)以上檢驗(yàn)數(shù)大于0時(shí)，一般選擇最大的一個(gè)檢驗(yàn)數(shù)，即：，其對(duì)應(yīng)的xk作為換入變量。確定換出變量。根據(jù)下式計(jì)算并選擇θ

，選最小的θ對(duì)應(yīng)的基變量XL作為換出變量。 2023/1/3188用換入變量XK替換原基變量中的換出變量XL，得到一個(gè)新的基。把約束方程組變換為對(duì)新基變量的解出形式，使得變量XK的系數(shù)列向量成為單位向量。對(duì)單純形表的CB列和XB列作適當(dāng)調(diào)整，再計(jì)算檢驗(yàn)數(shù)，就得到下一張單純形表。5）重復(fù)3）、4）步直到計(jì)算結(jié)束為止。 2023/1/3189cj3400θicBXBbx1x2x3x40x34021100x430130134000x34x23x14x2換入列bi/ai2，ai2>04010換出行將3化為15/311801/301/3101－1/3303005/30－4/3乘以3/5后得到103/5－1/51801－1/52/5400－1－170該行不變，減去同倍系數(shù)基準(zhǔn)行！2023/1/3190例1.16

用單純形法求解解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：不難看出x4、x5可作為初始基變量，列單純形表計(jì)算。2023/1/3191單純形法的計(jì)算步驟cj12100θicB基變量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220－x221/3150120753017131/30－90－22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/32023/1/31923.4單純形法的矩陣描述考慮標(biāo)準(zhǔn)形式的線性規(guī)劃：maxz=CXAX=bX≥0設(shè)B為一個(gè)基，占據(jù)A的前m列，其它n-m列組成的子矩陣用N表示，A=（BN）。對(duì)于列向量X與行向量C做對(duì)應(yīng)的分塊：X=（XBXN）T，C=（CBCN）。XB，XN分別是由基變量與非基變量組成的向量，CB與CN是對(duì)應(yīng)的系數(shù)向量。2023/1/3193代入目標(biāo)函數(shù)中，得到

z

=（

cB

cN

）=

cB

XB

+

cN

xN

=cB（B-1b–B-1NxN

）+

cN

xN

=

cBB-1b+(cN

-cBB-1N)xN

XB

xN設(shè)B為可行基，于是有基可行解對(duì)應(yīng)目標(biāo)函數(shù)值

z1

=cBB-1b

（1.19）由式（1.19）可知，非基變量的檢驗(yàn)數(shù)為N=(cN

-cBB-1N)對(duì)于基變量XB，檢驗(yàn)數(shù)

B=0，而cB

-cBB-1B=0，故所有變量的檢驗(yàn)數(shù)可以統(tǒng)一在一個(gè)公式中：

A=(c

-cBB-1A)寫成分量形式，任意變量Xj的檢驗(yàn)數(shù)

j=

cj

-cBB-1pj2023/1/3194考慮初始基變量是松弛變量的特殊情形2023/1/3195cjCBCN0系數(shù)基變量解向量XBXNXS0XSbBNEjCBCN0......CBXBB-1bEB-1NB-1j0CN-CBB-1N-CBB-13.5單純形法解的判定

唯一最優(yōu)解：所有非基變量的檢驗(yàn)數(shù)j<0無(wú)窮多最優(yōu)解：所有檢驗(yàn)數(shù)j0，且有一個(gè)非基變量xk的檢驗(yàn)數(shù)等于零。

無(wú)界解：若對(duì)基可行解X1，存在非基變量xk的檢驗(yàn)數(shù)j>0，但aik0，即xk的系數(shù)列向量無(wú)正分量，則問(wèn)題無(wú)最優(yōu)解。2023/1/31962023/1/3197無(wú)窮多最優(yōu)解情況第一表的解為最優(yōu)解X1*=(4,2,0,0,4)T，Z*=16；第二表的解也為最優(yōu)解X1*=(2,3,0,8,0)T，Z*=16；2023/1/3198無(wú)界解情況例用單純形表求下列線性規(guī)劃：

max

z=4x1+x2

s.t.

x1+x2

2

x1

4x2

4

x1

2x2

8

x1,x2

02023/1/3199

c41000

cB

xB

bx1x2x3x4x50x32-11100 0x441-401040x581-20018

j

041000 2023/1/31100

c41000

cB

xB

bx1x2x3x4x50x360-3110 4x141-40100x54020-112

j

160170-40 2023/1/31101

c41000

cB

xB

bx1x2x3x4x50x312001-1/23/2 4x112100-121x22010-1/21/2

j

500009/2-17/2由此，此題為無(wú)界解。2023/1/31102284610-224x1

x2x1-2x2

8-x1+x2

2z=4x1+x2-4-2x1-4x2

42023/1/311033.6求minz的情況兩種處理方式：

一、令z1=-z1,轉(zhuǎn)化為求maxz1；

二、直接計(jì)算

最優(yōu)性檢驗(yàn)條件改為：所有j≥0；

換人變量確定法則改為：min{j|j<0}；

單純形法的其他要點(diǎn)完全相同。2023/1/31104

如果線性規(guī)劃的約束都是約束，右端常數(shù)都大于等于零，其初始可行解很容易找到，松弛變量對(duì)應(yīng)的單位矩陣即是一個(gè)初始可行基；一般線性規(guī)劃問(wèn)題的初始可行解不一定很容易找到；這時(shí)需要引如人工變量，并使用特殊的方法找到初始可行解。四初始可行基的求法——人工變量2023/1/31105加入人工變量構(gòu)造初始基：把所有約束方程的右端常數(shù)調(diào)整為大于等于零。對(duì)

約束,引入松弛變量。對(duì)約束,引入一剩余變量和一人工變量。對(duì)=

約束，引入一人工變量。2023/1/31106例題1.17：

maxz=3x1–x2–x3s.t.x1–2x2+x3

（）11 -4x1+x2+2x3

（

）3 -2x1+x3

（=）1

x1,x2,0=+x7

=+x4–

x5+x6=大M法通過(guò)引入人工變量構(gòu)成初始基，從而找到一個(gè)初始基可行解；在目標(biāo)函數(shù)中人工變量的系數(shù)是任意大正數(shù)M的相反數(shù)-M；用線性規(guī)劃的優(yōu)化機(jī)制迫使人工變量出基；如果無(wú)法使人工變量出基，原問(wèn)題無(wú)可行解。–Mx6–Mx7x3,x4,x5,x6,x7cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70X4111-211000-MX63-4120-110-MX71-2010001j0X4103-20100-1-MX610100-11-2-1X31-2010001j2023/1/311073-6M-1+M-1+3M0-M001-1+M00-M0-3M+1cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70X4123001-22-5-1X210100-11-2-1X31-2010001j3X141001/3-2/32/3-5/3-1X210100-11-2-1X390012/3-4/34/3-7/3j2023/1/311081000-1-M+1-M-1000-1/3-1/3-M+1/3-M+2/32023/1/31109例題：

minz=2x1+3x2

s.t. 2x1+x2

（）16

x1+3x2

（

）20

x1+x2

（=）10

x1,x2

0=+x6=+x4-x3+x5=,x3,x4,x5,x6

0+Mx5+Mx6通過(guò)引入人工變量構(gòu)成初始基，從而找到一個(gè)初始基可行解；在目標(biāo)函數(shù)中賦予人工變量任意大的正系數(shù)M；用線性規(guī)劃的優(yōu)化機(jī)制迫使人工變量出基；如果無(wú)法使人工變量出基，原問(wèn)題無(wú)可行解。2023/1/311102-2M3-4M1-2/3M1-1/3M4/3M-12023/1/31111Cj

-3-2-1000-M-M

CB

XB

b

x1x2x3x4x5x6x7x8

θ

0-M-M

x4x7x8

643

1111000010-10-101001-100-101

6/1-3/1

j

-7M

-6-4M

-15-M

-3+M-2+M-1-2M0-M-M00

0-M-2

x4x7x2

343

1021010-110-10-101001-100-101

3/14/1-

j

j

-3+M0-3-M0-M-202-M

-3-M-2

x1x7x2

313

1021010-100-3-1-1

-11101-100-101

003-3M3-M-M1-M0-1

例運(yùn)算到檢驗(yàn)數(shù)全負(fù)為止，仍含有人工變量，無(wú)可行解。大M法下無(wú)可行解情況2023/1/31112

無(wú)最優(yōu)解

與

無(wú)可行解

是兩個(gè)不同的概念。無(wú)可行解是指原規(guī)劃不存在可行解，從幾何的角度解釋是指線性規(guī)劃問(wèn)題的可行域?yàn)榭占?；無(wú)最優(yōu)解則是指線性規(guī)劃問(wèn)題存在可行解，但是可行解的目標(biāo)函數(shù)達(dá)不到最優(yōu)值，即目標(biāo)函數(shù)在可行域內(nèi)可以趨于無(wú)窮大（或者無(wú)窮小）。無(wú)最優(yōu)解也稱為有限最優(yōu)解，或無(wú)界解。

判別方法：無(wú)最優(yōu)解判別定理

在求解極大化的線性規(guī)劃問(wèn)題過(guò)程中，若某單純形表的檢驗(yàn)行存在某個(gè)大于零的檢驗(yàn)數(shù)，但是該檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零，則該線性規(guī)劃問(wèn)題無(wú)最優(yōu)解2023/1/31113C2-200θ

CXB

B

x1

x2

x3

x4

0X3

1-11100X4

2-1/2101Z02-200因但所以原問(wèn)題無(wú)最優(yōu)解2023/1/31114五線性規(guī)劃應(yīng)用線性規(guī)劃建模①設(shè)立決策變量；②明確約束條件并用變量的線性等式或不等式表示；③用變量的線性函數(shù)表示目標(biāo)，并確定是求極小還是極大；④根據(jù)變量的物理性質(zhì)研究變量是否有非負(fù)性有時(shí)根本無(wú)法用變量的線性函數(shù)來(lái)描述目標(biāo)函數(shù)或約束條件，在這種情況下，可以嘗試增加一些變量或重新設(shè)定變量2023/1/31115合理利用線材問(wèn)題：如何下料使用材最少。配料問(wèn)題：在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)。投資問(wèn)題：從投資項(xiàng)目中選取方案，使投資回報(bào)最大。產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、財(cái)力等，使獲利最大。勞動(dòng)力安排：用最少的勞動(dòng)力來(lái)滿足工作的需要。運(yùn)輸問(wèn)題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小。常見(jiàn)問(wèn)題2023/1/31116生產(chǎn)計(jì)劃問(wèn)題用若干種原材料（資源）生產(chǎn)某幾種產(chǎn)品，原材料（或某種資源）供應(yīng)有一定的限制，要求制定一個(gè)產(chǎn)品生產(chǎn)計(jì)劃，使其在給定資源限制條件下能得到最大收益。

單耗產(chǎn)品資源A1……..An資源可供量B1a11……a1nb1B2a21……a2nb2…………………………Bmam1……amnbm單件利潤(rùn)C(jī)1……Cn2023/1/31117解設(shè)生產(chǎn)產(chǎn)品Aj的數(shù)量為xj2023/1/31118生產(chǎn)計(jì)劃問(wèn)題例題1.20

每生產(chǎn)一噸B，可得到兩噸產(chǎn)品C銷售一噸C盈利300元報(bào)廢每噸C損失200元市場(chǎng)預(yù)測(cè)，C最大銷量為5噸決定A，B的產(chǎn)量，使工廠總的盈利最大。AB工序一（小時(shí)）2315工序二（小時(shí)）3425元/（噸）400元800元2023/1/31119例1.20設(shè)A，B產(chǎn)品的生產(chǎn)量分別為x1和x2工序1工時(shí)2x1＋3x2≤15工序2工時(shí)3x1＋4x2≤25C產(chǎn)品數(shù)量2x2C產(chǎn)品銷量x3,報(bào)廢量x4C產(chǎn)品銷售量x3≤5利潤(rùn)總值Z=400x1+800x2+300x3-200x4-x3-x4=0非負(fù)約束x1，x2，x3，x4≥０2023/1/31120例1.20最優(yōu)解x1=3.75，x2=2.5，x3=5,x4=0最優(yōu)值Ｚ=50002023/1/31121例題1.21

產(chǎn)品＝2個(gè)零件1+3個(gè)零件2車間總工時(shí)生產(chǎn)效率（件／小時(shí)）零件1零件212310050758101661521車間生產(chǎn)工時(shí)數(shù)零件1零件2123x11x21x31x12x22x32生產(chǎn)計(jì)劃問(wèn)題2023/1/31122例1.21車間1工時(shí)約束x11＋x12≤100車間2工時(shí)約束x21＋x22≤50車間3工時(shí)約束x31＋x32≤75零件1生產(chǎn)數(shù)量8x11+10x21+16x31零件2生產(chǎn)數(shù)量6x12+15x22+21x32非負(fù)約束x

ij

≥0產(chǎn)品數(shù)量:min{4x11+5x21+8x31,2x12+5x22+7x32}y2y≤8x11+10x21+16x313y≤6x12+15x22+21x32目標(biāo)函數(shù)maxZ=y2023/1/31123例1.21最優(yōu)解x11=100，x12=0x21=0,x22=50x31=25,x32=50最優(yōu)值y=6002023/1/31124合理下料問(wèn)題從給定尺寸的材料中，按需要的尺寸截取給定數(shù)量的零件，使殘余廢料總量最小的問(wèn)題。三維（積材）下料問(wèn)題長(zhǎng)、寬、高二維（面料）下料問(wèn)題長(zhǎng)、寬一維（線材）下料問(wèn)題長(zhǎng)2023/1/31125合理下料問(wèn)題例題1.22

用長(zhǎng)9米的原料截取

3.1米200根

2.5米100根

1.7米300根方案1234567893.1米2211100002.5米1021032101.7米010230235廢料長(zhǎng)0.31.10.900.81.50.61.40.52023/1/31126例1.22設(shè)用第j種方案下料xj根任務(wù)：2x1+2x2+x3+x4+x5=（≥）200

x1+2x3+x4+3x6+2x7+x8=（≥）

100

x2+2x4+3x5+2x7+3x8+5x9=（≥）

300目標(biāo)：廢料最少或用料根數(shù)最少用料根數(shù)*9=用料長(zhǎng)度+廢料長(zhǎng)度廢料：Z=0.3x1+1.1x2+0.9x3

+0.8x5+1.5x6+0.6x7+1.4x8+0.5x9

用料：Z`=x1+x2+x3+x4+x5+x6+x7+x8+x9

非負(fù)約束xj≥０j=1,2……,92023/1/31127例1.22maxZ`=-x1-x2-x3-x4-x5-x6-x7-x8-x92x1+2x2+x3+x4+x5=200①x1+2x3+x4+3x6+2x7+x8=100②

x2+2x4+3x5+2x7+3x8+5x9=300③s.t.xj≥０j=1,2……,9①-②=①’,②’=②-①’,③’=(③-2②’)/5,得x1+2x2-x3+x5-3x6-2x7-x8=100①’-2x2+3x3+x4-x5+6x6+4x7+2x8=0②’

x2-6/5x3+x5-12/5x6-6/5x7-2x8+x9=60③’s.t.xj≥０j=1,2……,92023/1/31128CBXB

cj-1-1-1-1-1-1-1-1-1

xj

bx1x2x3x4x5x6x7x8x9-1x110012-101-3-2-1050-1x400-231-16420∞-1x96001-6/501-12/5-6/5-2160－Ｚ16000-1/500-2/5-1/5-20-1x2501/21-1/201/2-3/2-1-1/20-1x4100102103210-1x910-1/20-0.701/2-0.9-1/5-3/21－Ｚ16000-1/500-2/5-1/5-202023/1/31129合理配料問(wèn)題（飲食問(wèn)題）由多種原料制成含有m種成份的產(chǎn)品，已知產(chǎn)品中所含各種成份的比例要求，并且知道各種原料所含成份的數(shù)量，問(wèn)應(yīng)如何配料，才能使產(chǎn)品的成本最低。飼料、藥品、工業(yè)制品等飲料、食品等2023/1/31130合理配料問(wèn)題例題1.23

根據(jù)對(duì)四種食物所含的3種營(yíng)養(yǎng)素：維生素A、維生素B與維生素C的成份及食物的市場(chǎng)價(jià)格調(diào)查，按照醫(yī)生所提出的對(duì)每個(gè)人每天所需的營(yíng)養(yǎng)要求，可得表食

物每天的最低需要量營(yíng)養(yǎng)成份ABCD維生素A（國(guó)際單）10001500175032504000維生B（毫克）0.60.270.680.31維生素C（毫克）17.57.503030單

價(jià)（元）0.80.50.91.52023/1/31131

例