運(yùn)籌學(xué)第一章線性規(guī)劃及單純形法

LinearProgramming（LP）

線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型

線性規(guī)劃問(wèn)題的求解方法

線性規(guī)劃的圖解法

線性規(guī)劃的單純形法

線性規(guī)劃模型的應(yīng)用第一章線性規(guī)劃及單純形法

線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型第一章線性規(guī)劃及單純形法LinearProgramming（LP）

線性規(guī)劃問(wèn)題的求解方法

線性規(guī)劃的圖解法

線性規(guī)劃的單純形法

線性規(guī)劃模型的應(yīng)用一、問(wèn)題的提出

為了完成一項(xiàng)任務(wù)或達(dá)到一定的目的，怎樣用最少的人力、物力去完成或者用最少的資源去完成較多的任務(wù)或達(dá)到一定的目的，這個(gè)過(guò)程就是規(guī)劃。例1、有一正方形鐵皮，應(yīng)如何裁剪能使容積最大？xa

無(wú)約束的極值問(wèn)題例2、如何安排生產(chǎn)才能使利潤(rùn)最大？資料如圖

設(shè)備產(chǎn)品ABCD利潤(rùn)（元）

Ⅰ21402

Ⅱ22043

有效臺(tái)時(shí)1281612目標(biāo)max

x1≥0,x2≥0s.t.2x1+2x2≤12

帶約束的極值問(wèn)題x1x2z=2x1+3x2

約束條件x1+2x2≤84x1≤164x2≤12subjectto函數(shù)數(shù)學(xué)模型例3、合理配料問(wèn)題數(shù)學(xué)模型x1x2

x3

x4

x5

x6z=4x1+3x2+6x3+5x4+2.7x5+2.2x6mins.t.x1+0x2+2x3+2x4+x5+2x6≥9

0x1+x2+3x3+x4+3x5+2x6≥19

x1,x2,…,x6≥0

每天服用這六種營(yíng)養(yǎng)物各多少克，才能既獲得每日最少所需又使花費(fèi)最??？二、數(shù)學(xué)模型組成要素：

決策變量

約束條件

目標(biāo)函數(shù)線性規(guī)劃：連續(xù)的（數(shù)值取實(shí)數(shù)）關(guān)于變量的線性等式或不等式關(guān)于變量的線性函數(shù)（一次方）

問(wèn)題中有未知的變量，需要我們?nèi)デ蠼?，此外有目?biāo)函數(shù)及約束條件，一般有非負(fù)條件存在，由此組成規(guī)劃問(wèn)題的數(shù)學(xué)模型。線性規(guī)劃數(shù)學(xué)模型的一般形式s.t.s.t.向量形式s.t.s.t.向量形式矩陣形式s.t.s.t.線性規(guī)劃問(wèn)題的數(shù)學(xué)模型s.t.s.t.s.t.s.t.三、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式s.t.s.t.s.t.s.t.標(biāo)準(zhǔn)形式的主要特征s.t.③決策變量xj取值非負(fù)④約束條件右端常數(shù)項(xiàng)bi為非負(fù)值①目標(biāo)函數(shù)為求極大值（也可用求極小值）②所有約束條件都是等式（非負(fù)條件除外）

√非標(biāo)準(zhǔn)形式化為標(biāo)準(zhǔn)形式的方法⑴目標(biāo)函數(shù)的轉(zhuǎn)換⑵約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式⑶變量的變換稱(chēng)為松弛變量稱(chēng)為剩余變量x1+x24x1+x2－

x3=4⑷

約束條件右端常數(shù)項(xiàng)的變換：bi﹤0x1+x23x1+x2+x3=3例1、將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式+0x5+0x4maxz

=－2x1

+

x2

－

3x3

maxz

=－2x1

+

(x2

－

x2)

+3x3

+0x4+0x53x1

－

2(x2

－

x2)－

x3

=－4－3x1

+2(x2

－

x2)+

x3

=4解：設(shè)min

x1≥0,x2取值無(wú)約束,x3≤0s.t.x1+2x2+4x3≤6z=2x1

－x2

+3x3

3x1

－

2x2+x3=－4

2x1

－

x2－

3x3≥

5

x1,x2

,x2

,x3

,x4,x5≥0

x1+2x2+4x3+x4

=6s.t.

2x1

－

x2－

3x3－

x5

=5引入變量令x1

+

2(x2

－

x2)－

4x3

+

x4=6第二個(gè)約束方程兩邊乘(－1),從而得到標(biāo)準(zhǔn)形式2x1

－

(x2

－

x2)＋

3x3

－

x5

=5－3x1

+2x2

－

2x2

+

x3

=4

x1,x2

,x2

,x3

,x4,x5≥0s.t.x1

+2x2

－

2x2

－

4x3

+

x4=62x1

－

x2

＋

x2

＋

3x3

－

x5

=5maxz

=－2x1

+

x2

－

x2

+3x3

+0x4+0x5例2、將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式x1

＋

2(x2

－

x2)＋

x3

＋

x4

=5x1,x2

,x2

,x3

,x4,

x5,

x6

≥0x1

＋

(x2

－

x2)＋

x3

＋

x6

=2maxz=x1

+2(x2

－

x2)

+3x3

+0x4+0x5+

0x6解：max

x1≥0,x2取值無(wú)約束,x3≤0s.t.x1+2x2－

x3≤5z=x1+2x2

－

3x3

2x1+

3x2－

x3≥6

－x1

－

x2+

x3≥

－2引入變量令第三個(gè)約束方程兩邊乘(－1),從而得到標(biāo)準(zhǔn)形式2x1

＋

3(x2

－

x2)＋

x3

－

x5

=6s.t.x1

＋

2x2

－

2x2

＋

x3

＋

x4

=5x1,x2

,x2

,x3

,x4,x5,x6≥0x1

＋

x2

－

x2

＋

x3

＋

x6

=2maxz=x1

+2x2

－

2x2

+3x3

+0x4+0x5+

0x62x1

＋

3x2

－

3x2

＋

x3

－

x5

=6練習(xí)：將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式min

x1,x2≥0,x3取值無(wú)約束s.t.x1

－

x2+x3≤10z=－2x1+3x2

－

x3

3x1+

2x2－

x3≥8x1

－

3x2+

x3=－1－x1

＋

3x2

－

x3

＋

x3

=1maxz

=2x1

－3x2+

x3

－

x3

+0x4+0x53x1

＋

2x2

－

x3

＋

x3

－

x5

=8

x1,x2,x3

,x3

,x4,x5≥0s.t.x1

－

x2

＋

x3

－

x3

＋

x4

=10解：設(shè)引入變量令第三個(gè)約束方程兩邊乘(－1),從而得到標(biāo)準(zhǔn)形式即：系數(shù)矩陣的秩為m且小于n，則根據(jù)線性代數(shù)定理可知，②若有解則必有無(wú)窮多解，這是線性規(guī)劃問(wèn)題能尋求最優(yōu)解的余地所在。

四、線性規(guī)劃問(wèn)題的解s.t.③②①

可行解：滿足約束條件②、③的解

最優(yōu)解：使目標(biāo)函數(shù)①達(dá)到最大值的可行解方程組②中：通常m＜n，且m個(gè)方程線性無(wú)關(guān)。

可行域：所有可行解構(gòu)成的集合思考題：

某部門(mén)有一批資金用于甲、乙、丙、丁、戊五個(gè)工程項(xiàng)目的投資，由于某種原因，決定用于項(xiàng)目甲的投資不大于其他各項(xiàng)投資之和；而用于項(xiàng)目乙和戊的投資之和不小于項(xiàng)目丙的投資。已知用于各個(gè)工程項(xiàng)目時(shí)所得的凈收益(投入資金的百分比)如上表所示。試確定使該部門(mén)收益最大的投資分配方案。要求：建立線性規(guī)劃模型，并化為標(biāo)準(zhǔn)形式。工程項(xiàng)目甲乙丙丁戊收益（%）108659分析：z=0.1x1+0.08x2+0.06x3+0.05x4+0.09x5maxs.t.x1+x2+x3+x4+x5=1

x1－

x2－

x3－

x4－

x5≤0

x1,x2,…,x5≥0

工程項(xiàng)目甲乙丙丁戊收益（%）108659設(shè)xj表示用于第j個(gè)項(xiàng)目的投資百分比。目標(biāo)函數(shù)約束條件

用于甲的投資不大于其他各項(xiàng)投資之和；而用于乙和戊的投資之和不小于丙的投資。x2－

x3+x5≥0

總投資的要求對(duì)甲的要求對(duì)乙、戊的要求非負(fù)要求標(biāo)準(zhǔn)形式z=0.1x1+0.08x2+0.06x3+0.05x4+0.09x5+0x6+0x7

maxs.t.x1+x2+x3+x4+x5=1

x1－

x2－

x3－

x4－

x5+0x6

=0

x1,x2,…,x5,x6,

x7≥0

x2－

x3+x5+x7

=0

線性規(guī)劃問(wèn)題的求解方法第一章線性規(guī)劃及單純形法LinearProgramming（LP）

線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型

線性規(guī)劃的圖解法

線性規(guī)劃的單純形法

線性規(guī)劃模型的應(yīng)用一、預(yù)備知識(shí)：解的概念

可行解：滿足約束條件的解

最優(yōu)解：使目標(biāo)函數(shù)達(dá)到極值的可行解

可行域：所有可行解構(gòu)成的集合s.t.一、預(yù)備知識(shí)：凸集與頂點(diǎn)x1x2x2x1x1x2x1x2x1x2x1x2凸集：集合C中任意兩點(diǎn)連線上的所有點(diǎn)還在C內(nèi)

任給x1,x2

C,x=

x1+(1－

)x2

C(0<

<1)頂點(diǎn)：凸集C中不在任意兩不同點(diǎn)連線上的點(diǎn)

對(duì)x,任給x1,x2

C,不存在x=

x1+(1－

)x2(0<

<1)凸集非凸集二、圖解法步驟：將約束條件在圖上表示建立直角坐標(biāo)系確立滿足約束條件的解的范圍(可行域)繪制出目標(biāo)函數(shù)的圖形在可行域中確定最優(yōu)解定義：用圖示的方法求解線性規(guī)劃問(wèn)題的最優(yōu)解優(yōu)點(diǎn)：直觀性強(qiáng)，計(jì)算方便缺點(diǎn)：只適用于問(wèn)題中是兩(三)個(gè)變量的情況123456781234562x1+2x2=12x1+2x2=84x1=164x2=12唯一最優(yōu)解此時(shí)z=14。(4,2)示例1：s.t.①②③④0x2

x1z=0x1=4,x2=2,

123456781234563x1+2x2=12x1+2x2=6x2=2無(wú)窮多最優(yōu)解示例2：0x2

x1s.t.①②③x1－x2=－1x1+2x2=2無(wú)界解(無(wú)最優(yōu)解)示例3：s.t.①②x1x2

0思考：若目標(biāo)函數(shù)改為minz=x1+x2呢？

若改為minz=x1+

2x2呢？無(wú)可行解示例4：s.t.①②x1+x2=1x1x2

02x1+3x2=62x2=12練習(xí)：s.t.x1=83x1+4x2

=36(4,6)x1812x243690唯一最優(yōu)解此時(shí)z=42。x1=4,x2=6,

（4）無(wú)可行解：無(wú)可行域，模型約束條件矛盾圖解法的幾點(diǎn)啟示線性規(guī)劃問(wèn)題解的情況有：（1）唯一最優(yōu)解：只有一點(diǎn)為最優(yōu)解點(diǎn)（2）無(wú)窮多最優(yōu)解：有許多點(diǎn)為最優(yōu)解點(diǎn)（3）無(wú)界解：最優(yōu)解取值無(wú)界，無(wú)最優(yōu)解LP問(wèn)題的可行域若存在則一定是凸集(有限個(gè)頂點(diǎn))LP問(wèn)題若有最優(yōu)解，則定能在可行域某頂點(diǎn)達(dá)到LP問(wèn)題的解題思路：頂點(diǎn)→相鄰頂點(diǎn)→……三、單純形法（SimplexMethod）美國(guó)數(shù)學(xué)家丹齊格(G.B.Dantzig)1947年創(chuàng)建簡(jiǎn)捷、規(guī)范，是舉世公認(rèn)的解決線性規(guī)劃問(wèn)題行之有效的方法。

理論根據(jù)：基本思想：在凸集的有限個(gè)頂點(diǎn)上搜索最優(yōu)解該搜索策略可極大地減少訪問(wèn)頂點(diǎn)的數(shù)量。

由可行域的一個(gè)頂點(diǎn)出發(fā)，沿著凸集邊緣逐個(gè)計(jì)算與判定所遇到的頂點(diǎn)，直至找到最優(yōu)解所對(duì)應(yīng)的頂點(diǎn)為止。

線性規(guī)劃問(wèn)題的可行域是n維向量空間中的多面凸集，其最優(yōu)值如果存在則必在該凸集的某頂點(diǎn)處達(dá)到。s.t.(一)基解與基可行解系數(shù)矩陣A是m×n矩陣（設(shè)m<n），其秩R(A)=m。線性規(guī)劃問(wèn)題的基：矩陣A中的m×m階滿秩子矩陣B。(|B|≠0)基解：令非基變量為零，對(duì)m個(gè)基變量求解后合并所得的解。最多個(gè)基向量：B中的m個(gè)列向量Pr。基變量：與基向量對(duì)應(yīng)的m個(gè)變量xr。剩下n-m個(gè)非基變量。(一)基解與基可行解基解：令非基變量為零，對(duì)m個(gè)基變量求解后合并所得的解。設(shè)

，

令非基變量基變量為，|B|≠0基變量的唯一解基解最多個(gè)(一)基解與基可行解基解：令非基變量為零，對(duì)m個(gè)基變量求解后合并所得的解。基可行解：滿足變量非負(fù)約束條件xj≥0的基解。可行基：對(duì)應(yīng)于基可行解的基?；尚薪饪尚薪夥强尚薪饣饣馐欠窕尚薪饽繕?biāo)函數(shù)值例題：列出全部基、基解、基可行解和指出最優(yōu)解s.t.s.t.標(biāo)準(zhǔn)化系數(shù)矩陣:例題：用圖解法求最優(yōu)解s.t.x1+x2=3x1+2x2=4(2,1)12341230x2

x1基解對(duì)應(yīng)于各直線交點(diǎn)基可行解是可行域的頂點(diǎn)(二)單純形法的基本定理定理1：若線性規(guī)劃問(wèn)題存在可行解，則問(wèn)題的可行域是凸集。定理3：若線性規(guī)劃問(wèn)題有最優(yōu)解，則一定存在一個(gè)基可行解是最優(yōu)解。定理2：線性規(guī)劃問(wèn)題的基可行解對(duì)應(yīng)其可行域的頂點(diǎn)。理論根據(jù)：

線性規(guī)劃問(wèn)題的可行域是n維向量空間中的多面凸集，其最優(yōu)值如果存在則必在該凸集的某頂點(diǎn)處達(dá)到。在有限個(gè)基可行解中搜索最優(yōu)解（迭代）(三)單純形法的求解思路確定一個(gè)初始基可行解是否最優(yōu)改進(jìn)為新的基可行解最優(yōu)解是否循環(huán)結(jié)束化標(biāo)準(zhǔn)形1、確定初始基可行解s.t.s.t.標(biāo)準(zhǔn)化約束方程組的系數(shù)矩陣：基變量值：初始基可行解：記2、最優(yōu)性檢驗(yàn)s.t.初始基可行解：任一可行解：由約束方程組得代入目標(biāo)函數(shù)可得：則有：檢驗(yàn)數(shù)基變量的其中2、最優(yōu)性檢驗(yàn)當(dāng)前基可行解是最優(yōu)解若所有，則對(duì)任意可行解X，都有線性規(guī)劃問(wèn)題存在無(wú)界解（無(wú)最優(yōu)解）若存在某個(gè)，且所有令只需保證由所有顯然此時(shí)因找可行解X，使z無(wú)限大。線性規(guī)劃問(wèn)題無(wú)可行解2、最優(yōu)性檢驗(yàn)當(dāng)前基可行解是最優(yōu)解：所有線性規(guī)劃問(wèn)題有唯一最優(yōu)解′線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解′′線性規(guī)劃問(wèn)題存在無(wú)界解（無(wú)最優(yōu)解）若存在某個(gè)，且所有存在和當(dāng)前基可行解非最優(yōu)解，但LP問(wèn)題有最優(yōu)解其中所有；

或

有非基變量,且3、尋找改進(jìn)的基可行解

相鄰的基可行解：若兩個(gè)基可行解之間僅變換一個(gè)基變量。

將一個(gè)基變量變成非基變量（換出），一個(gè)非基變量變成基變量（換入），進(jìn)而找出一個(gè)目標(biāo)函數(shù)值更大的“相鄰”基可行解。入基變量的確定由和越大，值上升的可能性越大因此，一般取對(duì)應(yīng)的變量作為換入基的變量。3、尋找改進(jìn)的基可行解出基變量的確定令換入變量為得到基可行解，需保證且至少一個(gè)為0（換出）則只需取其余非基變量，存在此時(shí)換出。確定為換出變量，由稱(chēng)為主元素?？尚薪猓鹤C明是基可行解？§3-1引理3、尋找改進(jìn)的基可行解約束方程組的系數(shù)矩陣：初始基

，

變量換入,換出，新可行解對(duì)應(yīng)向量：是線性無(wú)關(guān)的，故是基可行解。s.t.單純形法的求解思路確定一個(gè)初始基可行解是否最優(yōu)改進(jìn)為新的基可行解最優(yōu)解是否循環(huán)結(jié)束化標(biāo)準(zhǔn)形？步驟簡(jiǎn)單總結(jié)經(jīng)過(guò)何種運(yùn)算可轉(zhuǎn)到第③步，實(shí)現(xiàn)循環(huán)迭代？①將線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)形式;②找出或構(gòu)造一個(gè)m階單位矩陣作初始可行基，得到初始基可行解;③計(jì)算各非基變量xj的檢驗(yàn)數(shù)

j，若所有

j≤0，則問(wèn)題已得到最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入下步;④若存在某個(gè)

s>0，且對(duì)應(yīng)的所有系數(shù)ais≤0，則此問(wèn)題是無(wú)界解，停止計(jì)算，否則轉(zhuǎn)入下步;⑤根據(jù)max{

j|

j＞0}=

k原則，確定xk為入基變量，再按

=min{bi/aik|aik＞0}=bl/alk規(guī)則，確定xl為出基變量，得到改進(jìn)的基可行解。將其化為單位矩陣，

則LP問(wèn)題形式為s.t.4、迭代運(yùn)算初始基

，

變量換入,換出，新可行基：s.t.4、迭代運(yùn)算①主元素所在行：②

其余行：4、迭代運(yùn)算新檢驗(yàn)數(shù)

s.t.整理后可得

①將線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)形式;②找出或構(gòu)造一個(gè)m階單位矩陣作初始可行基，得到初始基可行解;③計(jì)算各非基變量xj的檢驗(yàn)數(shù)

j，若所有

j≤0，則問(wèn)題已得到最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入下步;④若存在某個(gè)

s>0，且對(duì)應(yīng)的所有系數(shù)ais≤0，則此問(wèn)題是無(wú)界解，停止計(jì)算，否則轉(zhuǎn)入下步;⑤根據(jù)max{

j|

j＞0}=

k原則，確定xk為入基變量，再按

=min{bi/aik|aik＞0}=bl/alk規(guī)則，確定xl為出基變量；⑥以alk為主元素進(jìn)行迭代，利用初等行變換將xk所在列化為單位向量，即alk化為1，其它元素化為0，得到改進(jìn)的可行基，轉(zhuǎn)入第③步。計(jì)算步驟總結(jié)(四)單純形表格法——單純形表s.t.……max

x1,x2≥0s.t.

2x1+2x2≤12z=2x1+3x2

4x1

≤

165x2≤15例題：用單純形法求解線性規(guī)劃問(wèn)題+0x4+0x3maxz=2x1

+3x2s.t.引入變量得到標(biāo)準(zhǔn)形式解：+0x55x2+x5

=154x1

+

x4=162x1

+2x2+

x3=12x1,x2,x3,x4,x5≥0+0x4+0x3maxz=2x1

+3x2s.t.引入變量得到標(biāo)準(zhǔn)形式解：+0x55x2+x5

=154x1

+

x4=162x1

+2x2+

x3=12x1,x2,x3,x4,x5≥0此時(shí)所有檢驗(yàn)數(shù)得到最優(yōu)解最優(yōu)值為①將線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)形式;②找出或構(gòu)造一個(gè)單位矩陣作初始可行基，確定初始基可行解，建立初始單純形表;③檢驗(yàn)各非基變量xj的檢驗(yàn)數(shù)

j，若所有

j≤0，則問(wèn)題已得到最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入下步;④若存在某個(gè)

s>0，且對(duì)應(yīng)的所有系數(shù)ais≤0，則此問(wèn)題是無(wú)界解，停止計(jì)算，否則轉(zhuǎn)入下步;⑤根據(jù)max{

j|

j＞0}=

k原則，確定xk為入基變量，再按

=min{bi/aik|aik＞0}=bl/alk規(guī)則，確定xl為出基變量；⑥用xk替換基變量中的xl，利用初等行變換將xk所在列化為單位向量，得到新的單純形表，轉(zhuǎn)入第③步。單純形法計(jì)算步驟標(biāo)準(zhǔn)化系數(shù)矩陣(五)單純形法的進(jìn)一步討論

用單純形法解題時(shí)，需要有個(gè)單位矩陣作為初始可行基當(dāng)約束條件都是“≤”時(shí)，加入松弛變量就形成了初始基

但實(shí)際存在“≥”或“＝”型的約束，沒(méi)有現(xiàn)成的單位矩陣s.t.－2x1＋

x2－x3

－

x5

=1解：引入變量從而得到標(biāo)準(zhǔn)形式s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9maxz=－3x1

+

0x2

+

x3+0x4+0x5約束方程組的系數(shù)矩陣：maxz=－3x1

+

0x2

+

x3+0x4+0x5(五)單純形法的進(jìn)一步討論采用添加人工變量的方法

因是在等式中人為加進(jìn)的，為保證約束條件的意義，最優(yōu)解中人工變量只能等于0

在等式約束中加入若干人工變量，人為構(gòu)造一個(gè)單位矩陣

人工變量的添加不能影響最優(yōu)解的取值：－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9約束方程組的系數(shù)矩陣：兩種處理方法

大M法兩階段法＋

x6

=1

＋

x7

=9=4,x6,x7≥0如何處理？1、大M法maxz=－3x1

+

0x2

+

x3+0x4+0x5－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥0－Mx6－Mx7

為保證最優(yōu)解中人工變量取值為0，可令目標(biāo)函數(shù)中人工變量的系數(shù)為足夠大的一個(gè)負(fù)值，用“－M”代表。

由于系數(shù)是一個(gè)足夠大的負(fù)值，因此，只要人工變量的取值不為零，目標(biāo)函數(shù)就不可能實(shí)現(xiàn)最大化。

計(jì)算時(shí)，把M看做一個(gè)代數(shù)符號(hào)直接參加單純形法求解。

若最終單純形表中，人工變量仍是基變量且值不為零，則說(shuō)明該問(wèn)題求不到最優(yōu)解，即無(wú)可行解。－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥0maxz=－3x1

+

0x2

+

x3+0x4+0x5－Mx6－Mx7使人工變量盡快出基此時(shí)所有檢驗(yàn)數(shù)得到最優(yōu)解最優(yōu)值為－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥0maxz=－3x1

+0x2

+

x3+0x4+0x5

用大M法處理人工變量，用手工計(jì)算不會(huì)出現(xiàn)任何問(wèn)題。

但用計(jì)算機(jī)求解時(shí)，由于在程序中只能用很大的數(shù)代替M，有可能受計(jì)算機(jī)的誤差影響，導(dǎo)致結(jié)果發(fā)生錯(cuò)誤，使大M法失效。2、兩階段法

第一階段：構(gòu)造判斷是否存在可行解的模型

構(gòu)造僅含人工變量(系數(shù)為1)且要求極小化的目標(biāo)函數(shù)

用單純形法求解，若minw=0，說(shuō)明人工變量為0，問(wèn)題存在基可行解，進(jìn)入第二個(gè)階段；若minw≠0，說(shuō)明最優(yōu)解中人工變量非零，無(wú)可行解，停止。minw=x6+

x7minw=x6+

x72、兩階段法－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥02、兩階段法

第二階段：從上階段的最終單純形表出發(fā)，去掉人工變量，引入原來(lái)的目標(biāo)函數(shù)，繼續(xù)迭代，找出問(wèn)題的最終解maxz=－3x1

+

0x2

+

x3+0x4+0x5人工變量法總結(jié)約束方程組

在等式約束中加人工變量，人為構(gòu)造單位矩陣作初始可行基目標(biāo)函數(shù)

為保證原約束條件的意義，最優(yōu)解中人工變量只能是0大M法

令目標(biāo)函數(shù)中人工變量的系數(shù)為足夠大的一個(gè)負(fù)值“－M”兩階段法1、構(gòu)造僅含人工變量且求極小化的目標(biāo)函數(shù)，單純形法求解；2、去掉上階段最終單純形表中的人工變量，引入原目標(biāo)函數(shù)，繼續(xù)迭代，找出問(wèn)題的最終解。

若最終單純形表中，人工變量仍是基變量且值不為零，則說(shuō)明該問(wèn)題求不到最優(yōu)解，即無(wú)可行解。3、由單純形表判別解的類(lèi)別無(wú)可行解唯一最優(yōu)解所有無(wú)窮多最優(yōu)解無(wú)界解（無(wú)最優(yōu)解）最終單純形表的基變量中仍有非零人工變量存在某個(gè)，且所對(duì)應(yīng)的系數(shù)最優(yōu)解某非基變量至少一個(gè)且≤0≥0保證當(dāng)前的基可行解是最優(yōu)解

至少有一個(gè)等于0，如

至少有一個(gè)大于0，如

＞0

存在，保證當(dāng)xp入基時(shí)有xl出基說(shuō)明能得到另一個(gè)最優(yōu)基可行解兩個(gè)基可行解連線上的所有點(diǎn)都是最優(yōu)解無(wú)窮多最優(yōu)解示例1：s.t.標(biāo)準(zhǔn)化s.t.此時(shí)所有檢驗(yàn)數(shù)得到最優(yōu)解最優(yōu)值為此時(shí)所有檢驗(yàn)數(shù)得另一最優(yōu)解最優(yōu)值為無(wú)界解(無(wú)最優(yōu)解)示例2：s.t.標(biāo)準(zhǔn)化s.t.且所對(duì)應(yīng)系數(shù)取值無(wú)限制160x2

x14x1=16無(wú)可行解示例3：s.t.標(biāo)準(zhǔn)化s.t.此時(shí)所有檢驗(yàn)數(shù)但人工變量仍留在基變量中且不為零，問(wèn)題無(wú)可行解。單純形法小結(jié)

根據(jù)實(shí)際問(wèn)題給出數(shù)學(xué)模型，首先化為標(biāo)準(zhǔn)形式，構(gòu)造出單位矩陣作為基，列出初始單純形表.單純形法計(jì)算框圖唯一最優(yōu)解添加松弛變量、人工變量列出初始單純形表計(jì)算非基變量各列的檢驗(yàn)數(shù)бj所有бj

0基變量中有非零的人工變量

否某非基變量檢驗(yàn)數(shù)為零﹡

否無(wú)可行解無(wú)窮多最優(yōu)解對(duì)任一бj≥0有aik≤0無(wú)界解令бk=max{бj}xk為入基變量對(duì)所有aik>0計(jì)算θi=bi/aik

令θl=min{θi}xl為出基變量

alk為主元素迭代運(yùn)算1、用非基變量xk替換基變量xl2、對(duì)主元素行(第l行)

令bl/alk→bl；alj/alk→ajl3、對(duì)主元素列(第k列)

令1→alk;0→其它元素4、表中其它行令ri－rl/alk·aik→ri列出新的單純形表否否是是

是是循環(huán)補(bǔ)充說(shuō)明單純形法在計(jì)算中可能出現(xiàn)以下兩種情況：同時(shí)出現(xiàn)多個(gè)相同的最大

j值同時(shí)出現(xiàn)多個(gè)相同的最小θ值

理論上可能出現(xiàn)死循環(huán)，但實(shí)際很罕見(jiàn)，一般不需特殊處理，任選其中一個(gè)對(duì)應(yīng)的變量入基或出基即可。

若遇到極端情況，可利用勃蘭特(bland)規(guī)則：當(dāng)存在多個(gè)

j>0時(shí)，選取下標(biāo)值最小的變量入基；當(dāng)出現(xiàn)多個(gè)相同最小θ時(shí)，選取下標(biāo)值最小的變量出基。

線性規(guī)劃模型的應(yīng)用第一章線性規(guī)劃及單純形法LinearProgramming（LP）

線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型

線性規(guī)劃問(wèn)題的求解方法

線性規(guī)劃的圖解法

線性規(guī)劃的單純形法線性規(guī)劃問(wèn)題的建模

建模是運(yùn)籌學(xué)方法的核心和精髓，建立一個(gè)正確的數(shù)學(xué)模型，是問(wèn)題解決的關(guān)鍵，答案利用線性規(guī)劃程序可很快獲得。正確的建模要求建模者：理解生產(chǎn)和管理問(wèn)題的本質(zhì)，明確目標(biāo)和錯(cuò)綜復(fù)雜的約束條件，通過(guò)調(diào)查和統(tǒng)計(jì)資料獲取原始可靠的數(shù)據(jù)。建模過(guò)程的規(guī)律：①通過(guò)對(duì)實(shí)際問(wèn)題的分析、理解，明確那些是決策變量，目標(biāo)要求是什么，有哪些資源限制條件；②把變量、常數(shù)、約束條件、目標(biāo)要求的相互關(guān)系聯(lián)系起來(lái)列出相應(yīng)的方程式；③注意變量、系數(shù)、常數(shù)的計(jì)量單位要統(tǒng)一。線性規(guī)劃問(wèn)題的應(yīng)用

問(wèn)題需滿足的條件

①目標(biāo)函數(shù)能用數(shù)值指標(biāo)來(lái)反映，且為線性函數(shù)；

②存在多種方案及有關(guān)數(shù)據(jù)；

③要達(dá)到的目標(biāo)是在一定約束條件下實(shí)現(xiàn)的，這些條件可用線性等式或不等式描述。相關(guān)問(wèn)題生產(chǎn)計(jì)劃問(wèn)題（合理利用資源，使利潤(rùn)最高或完成計(jì)劃）合理配料問(wèn)題（保證飲食、藥品等效果前提下使成本最低）投資方案選擇問(wèn)題（固定資金投入時(shí)使效益最高）人員分派問(wèn)題（多項(xiàng)任務(wù)分配，使人數(shù)最少或效率最大）合理下料問(wèn)題（在給定材料中截取零件，使用料最?。┻\(yùn)輸問(wèn)題＊（多個(gè)產(chǎn)銷(xiāo)地及運(yùn)價(jià)限制，安排方案使運(yùn)費(fèi)最低）……生產(chǎn)計(jì)劃問(wèn)題：如何安排生產(chǎn)使利潤(rùn)最大？資料如圖

設(shè)備產(chǎn)品ABCD利潤(rùn)（元）

Ⅰ21402

Ⅱ22043

有效臺(tái)時(shí)1281612max

x1,x2≥0s.t.2x1+2x2≤12z=2x1+3x2

x1+2x2≤84x1≤164x2≤12設(shè)xj表示第j種產(chǎn)品在計(jì)劃期內(nèi)的產(chǎn)量合理配料問(wèn)題：資料如圖

設(shè)xj表示第j種營(yíng)養(yǎng)物所需克數(shù)z=4x1+3x2+6x3+5x4+2.7x5+2.2x6mins.t.x1+0x2+2x3+2x4+x5+2x6≥9

0x1+x2+3x3+x4+3x5+2x6≥19

x1,x2,…,x6≥0

每天服用6種營(yíng)養(yǎng)物各多少克，才能既獲得每日所需又使花費(fèi)最省？投資方案選擇問(wèn)