運(yùn)籌學(xué)課件2012-2

1、適用專業(yè)：信息管理授課教師：張鳳玲運(yùn) 籌 學(xué)第二章第二章 線性規(guī)劃及單純形法線性規(guī)劃及單純形法v 2.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型v 2.2 線性規(guī)劃問題的概念及性質(zhì)線性規(guī)劃問題的概念及性質(zhì)v 2.3 單純形法單純形法v 2.4 線性規(guī)劃應(yīng)用線性規(guī)劃應(yīng)用第二章線性規(guī)劃及單純形法第二章線性規(guī)劃及單純形法線性規(guī)劃：線性規(guī)劃：線性規(guī)劃（線性規(guī)劃（Linear Programming簡稱簡稱LP）是運(yùn)籌學(xué)的一個重要分支，也是運(yùn)籌學(xué)中理論最成熟，是運(yùn)籌學(xué)的一個重要分支，也是運(yùn)籌學(xué)中理論最成熟，應(yīng)用最廣泛的方法之一。自應(yīng)用最廣泛的方法之一。自1947年丹捷格提出一般線年丹捷格提出一

2、般線性規(guī)劃問題的求解方法單純形法之后，線性規(guī)劃性規(guī)劃問題的求解方法單純形法之后，線性規(guī)劃已被廣泛地應(yīng)用于解決經(jīng)濟(jì)管理和工業(yè)企業(yè)中的實(shí)際已被廣泛地應(yīng)用于解決經(jīng)濟(jì)管理和工業(yè)企業(yè)中的實(shí)際問題。問題。線性規(guī)劃所研究的問題有兩類：線性規(guī)劃所研究的問題有兩類：一類是已知一定數(shù)一類是已知一定數(shù)量的人力、物力和財力資源，研究如何充分和合理量的人力、物力和財力資源，研究如何充分和合理地利用這些資源，以取得最大的經(jīng)濟(jì)效益；另一類地利用這些資源，以取得最大的經(jīng)濟(jì)效益；另一類是已確定一項(xiàng)任務(wù)，研究怎樣統(tǒng)籌安排，才能以資是已確定一項(xiàng)任務(wù)，研究怎樣統(tǒng)籌安排，才能以資源的最少消耗完成這項(xiàng)任務(wù)。源的最少消耗完成這項(xiàng)任務(wù)。第一

3、節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型一、什么是線性規(guī)劃一、什么是線性規(guī)劃例例1.某工廠在計劃期內(nèi)要安排生產(chǎn)某工廠在計劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種兩種原材料的消耗，如表原材料的消耗，如表1-1所示。所示。該工廠每生產(chǎn)一件產(chǎn)品該工廠每生產(chǎn)一件產(chǎn)品可獲利可獲利2元，每生產(chǎn)元，每生產(chǎn)一件產(chǎn)品一件產(chǎn)品可獲利可獲利3元，元，問應(yīng)如何安排計劃使該問應(yīng)如何安排計劃使該工廠獲利最多？工廠獲利最多？表表1-1第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型解：設(shè)產(chǎn)品解：設(shè)產(chǎn)品的產(chǎn)量為的產(chǎn)量為x1噸，

4、產(chǎn)噸，產(chǎn)品品的產(chǎn)量為的產(chǎn)量為x2噸。建模如下：噸。建模如下：表表1-1x1x221x32xMaxZ st.82xx2161 4x1124x 20 x,x21第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型例例2.捷運(yùn)公司在下一年度的捷運(yùn)公司在下一年度的14月的月的4個月內(nèi)擬租用倉庫堆放物資。已知個月內(nèi)擬租用倉庫堆放物資。已知各月份所需倉庫面積見表各月份所需倉庫面積見表1。倉庫租借費(fèi)用隨合同期而定，期限越長，折扣越。倉庫租借費(fèi)用隨合同期而定，期限越長，折扣越大，具體數(shù)字見表大，具體數(shù)字見表2。租借倉庫的合同每月初都可加辦理，每份合同具體規(guī)定。租借倉庫的合同每月初都可加辦理，每份合同具

5、體規(guī)定租用面積和期限。因此該廠可根據(jù)需要，在任何一個月初辦理租借合同。每租用面積和期限。因此該廠可根據(jù)需要，在任何一個月初辦理租借合同。每次辦理時可簽一份合同，也可簽若干份租用面積和租借期限不同的合同，試次辦理時可簽一份合同，也可簽若干份租用面積和租借期限不同的合同，試確定該公司簽訂租借合同的最優(yōu)決策，目的是使所付費(fèi)用最小。確定該公司簽訂租借合同的最優(yōu)決策，目的是使所付費(fèi)用最小。表表1單位：單位：100平方米平方米表表2 單位：元單位：元/100平方米平方米第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型解：設(shè)捷運(yùn)公司在第解：設(shè)捷運(yùn)公司在第i（i=1,2,3,4）個月初簽訂的租借期

6、為）個月初簽訂的租借期為j（j1,2，3,4）個月的合同的倉儲面積為）個月的合同的倉儲面積為xij142313322212413121117300 x)x6000(x)xx (x4500)xxx(x2800MinZst.15xxxx1413121110 xxxxxx23222114131220 xxxxxx32312322141312xxxx413223141,.,4)j1,.,4;(i0 xij第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型例例3.某工廠在生產(chǎn)過程中需要濃度為某工廠在生產(chǎn)過程中需要濃度為80%的硫酸的硫酸100t，而市面上只有濃度為而市面上只有濃度為30%，45

7、%，73%，85%和和92%的的硫酸出售，每噸價格分別為硫酸出售，每噸價格分別為400，700，1400，1900和和2500元，問應(yīng)購買各種硫酸各多少，才能滿足生產(chǎn)要求，并元，問應(yīng)購買各種硫酸各多少，才能滿足生產(chǎn)要求，并使得所花費(fèi)用最?。渴沟盟ㄙM(fèi)用最?。康谝还?jié)線性規(guī)劃問題及其數(shù)學(xué)模型第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型解：設(shè)取濃度為解：設(shè)取濃度為30%，45%，73%，85%和和92%的硫酸的硫酸量分別為量分別為x1，x2，x3，x4和和x5t，根據(jù)題意建模得，根據(jù)題意建模得54321250019001400700400 xxxxxMinZ.st10054321xxxxx1008 . 092.

8、085. 073. 045. 03 . 054321xxxxx)5,2,1(0jxj思考：從數(shù)學(xué)模型的角度總結(jié)一下什么是線性規(guī)劃？思考：從數(shù)學(xué)模型的角度總結(jié)一下什么是線性規(guī)劃？第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型1、每個問題都有一組未知變量（、每個問題都有一組未知變量（X1，X2，Xn）表示）表示某一方案，這組未知變量的一組定值就代表一個具體方案，某一方案，這組未知變量的一組定值就代表一個具體方案，通常要求這些未知變量取值是非負(fù)的。我們稱未知變量為通常要求這些未知變量取值是非負(fù)的。我們稱未知變量為變變量量 ,或稱或稱決策變量決策變量。2、存在一定的、存在一定的約束條件約

9、束條件，這些約束條件可以用一組線性等，這些約束條件可以用一組線性等式或線性不等式來表達(dá)，它們體現(xiàn)了決策變量的相互依存關(guān)式或線性不等式來表達(dá)，它們體現(xiàn)了決策變量的相互依存關(guān)系。（決策變量取值時受到的各種資源條件的限制）。系。（決策變量取值時受到的各種資源條件的限制）。3、都有一個目標(biāo)要求，并且這個目標(biāo)可以表示為決策變、都有一個目標(biāo)要求，并且這個目標(biāo)可以表示為決策變量的線性函數(shù)（稱為量的線性函數(shù)（稱為目標(biāo)函數(shù)目標(biāo)函數(shù)），按優(yōu)化目標(biāo)的不同，要），按優(yōu)化目標(biāo)的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。二、線性規(guī)劃數(shù)學(xué)模型的特征二、線性規(guī)劃數(shù)學(xué)模型的特征第一節(jié)線性規(guī)劃問題及其數(shù)

10、學(xué)模型第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型0 x,x,x)b (xaxaxa)b (xaxaxa)b (xaxaxast.xcxcxcMax(Min)Zn21mnmn2m21m12n2n2221211n1n212111nn2211或或或三、線性規(guī)劃數(shù)學(xué)模型的一般形式：三、線性規(guī)劃數(shù)學(xué)模型的一般形式：n),1,2,(j 0 x)m,1,2,i ( )b(xast.xcMin)ZMax(jn1jijijn1jjj或或和的形式：和的形式：矩陣和向量形式矩陣和向量形式：0X)b(AXst.CXMin)ZMax(或或mnm2m12n22211n1211a a a a a aa a aA其中：其中：第一節(jié)線性規(guī)

11、劃問題及其數(shù)學(xué)模第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型型四、線性規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)形式：四、線性規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)形式：0b0 x,x,xbxaxaxab xaxaxab xaxaxast.xcxcxcMaxZin21mnmn2m21m12n2n2221211n1n212111nn2211第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型將非標(biāo)準(zhǔn)形式化為標(biāo)準(zhǔn)形（標(biāo)準(zhǔn)化）將非標(biāo)準(zhǔn)形式化為標(biāo)準(zhǔn)形（標(biāo)準(zhǔn)化）目標(biāo)函數(shù)求極小值目標(biāo)函數(shù)求極小值約束條件右端常數(shù)項(xiàng)小于約束條件右端常數(shù)項(xiàng)小于0約束條件為不等式約束條件為不等式?jīng)Q策變量取值為負(fù)數(shù)決策變量取值為負(fù)數(shù)決策變量取值無約束決策變量取值無約束第一節(jié)線性規(guī)

12、劃問題及其數(shù)學(xué)模型第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型例例.將下面線性規(guī)劃問題化為標(biāo)準(zhǔn)形式將下面線性規(guī)劃問題化為標(biāo)準(zhǔn)形式為自由變量321321321321321x0,x,x-43xx-2x-52xx3x7xxxst.3x2xxMinZ將下述線性規(guī)劃化為標(biāo)準(zhǔn)形無約束321321321321, 0, 06x422minxxxxxxxxxxxz無約束423143132143214321, 0, 0,12x285x327xx32axxxxxxxxxxxxxxxzm練 習(xí)0.42266432min) 1 (21212121xxxxxxxxz83105120106max) 2(212121xxxxxxz0 x,

13、x124x 16 4x82x xst.3x2xMaxZ21212121第二節(jié)線性規(guī)劃問題解的概念及性質(zhì)第二節(jié)線性規(guī)劃問題解的概念及性質(zhì)一、圖解法一、圖解法例例.用圖解法求下列線性規(guī)劃問題的解用圖解法求下列線性規(guī)劃問題的解1x2xOABCDEFG164x11242x8221 xx0 x,x124x 16 4x82x xst.3x2xMaxZ21212121可行解：可行解：滿足所有約束條件的解滿足所有約束條件的解X，稱為線性規(guī)劃問題的可行解。所有稱為線性規(guī)劃問題的可行解。所有可行解的集合稱為可行解的集合稱為可行域可行域。1x2xOABCDEFG164x11242x8221 xx0 x,x124x

14、16 4x82x xst.3x2xMaxZ212121212X1+3X28第二節(jié)線性規(guī)劃問題解的概念及性質(zhì)第二節(jié)線性規(guī)劃問題解的概念及性質(zhì)0 x, x3 x22xx-st.2xxMaxZ2112121例例.用圖解法求下列線性規(guī)劃問題的解用圖解法求下列線性規(guī)劃問題的解1x2xO0 x, x3 x22xx- st.2xxMaxZ21121213x12221xx第二節(jié)線性規(guī)劃問題解的概念及性質(zhì)第二節(jié)線性規(guī)劃問題解的概念及性質(zhì)0 x, x15 x53x2x xst.xx2MaxZ21212121例例.用圖解法求下列用圖解法求下列線性規(guī)劃線性規(guī)劃問題的解問題的解解的幾種可能情況：解的幾種可能情況：1.有

15、唯一最優(yōu)解；有唯一最優(yōu)解；2.有無窮多最優(yōu)解；有無窮多最優(yōu)解；3.無界解；無界解；4.無可行解。無可行解。第二節(jié)線性規(guī)劃問題解的概念及性質(zhì)第二節(jié)線性規(guī)劃問題解的概念及性質(zhì)用圖解法表示出下列線性規(guī)劃問題的可行域用圖解法表示出下列線性規(guī)劃問題的可行域0 x,x6xx2 2 x- xst.xxMaxZ21212121第二節(jié)線性規(guī)劃問題解的概念及性質(zhì)第二節(jié)線性規(guī)劃問題解的概念及性質(zhì)由圖解法得到的啟示：由圖解法得到的啟示：1.求解一線形規(guī)劃問題時，解的情況：唯一最優(yōu)解、無窮多求解一線形規(guī)劃問題時，解的情況：唯一最優(yōu)解、無窮多最優(yōu)解、無界解、無可行解；最優(yōu)解、無界解、無可行解；2.若線性規(guī)劃問題的可行域存

16、在，則可行域是一個凸多邊形若線性規(guī)劃問題的可行域存在，則可行域是一個凸多邊形（凸集）；（凸集）；3.若最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一是可行域的某個頂若最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一是可行域的某個頂點(diǎn)；點(diǎn)；4.解題思路，先找出凸集的任一頂點(diǎn)，計算在頂點(diǎn)處的目標(biāo)解題思路，先找出凸集的任一頂點(diǎn)，計算在頂點(diǎn)處的目標(biāo)函數(shù)值。比較周圍相鄰頂點(diǎn)的目標(biāo)函數(shù)值是否比這個值大，函數(shù)值。比較周圍相鄰頂點(diǎn)的目標(biāo)函數(shù)值是否比這個值大，如果為否，則該頂點(diǎn)就是最優(yōu)解的點(diǎn)或最優(yōu)解的點(diǎn)之一，否如果為否，則該頂點(diǎn)就是最優(yōu)解的點(diǎn)或最優(yōu)解的點(diǎn)之一，否則轉(zhuǎn)到比這個點(diǎn)的目標(biāo)函數(shù)值更大的另一個頂點(diǎn)，重復(fù)上述則轉(zhuǎn)到比這個點(diǎn)的目標(biāo)函數(shù)值更

17、大的另一個頂點(diǎn)，重復(fù)上述過程，一直到找出目標(biāo)函數(shù)值達(dá)到最大的頂點(diǎn)為止。過程，一直到找出目標(biāo)函數(shù)值達(dá)到最大的頂點(diǎn)為止。第二節(jié)線性規(guī)劃問題解的概念及性質(zhì)第二節(jié)線性規(guī)劃問題解的概念及性質(zhì)二、解的概念二、解的概念最優(yōu)解最優(yōu)解：滿足目標(biāo)函數(shù)的可行解稱為線性規(guī)滿足目標(biāo)函數(shù)的可行解稱為線性規(guī)劃問題的最優(yōu)解。最優(yōu)解對應(yīng)的目標(biāo)函數(shù)值稱為線性劃問題的最優(yōu)解。最優(yōu)解對應(yīng)的目標(biāo)函數(shù)值稱為線性規(guī)劃問題的規(guī)劃問題的最優(yōu)值最優(yōu)值。基基：設(shè)設(shè)A為約束方程組的為約束方程組的mn階系數(shù)矩陣（設(shè)階系數(shù)矩陣（設(shè)nm），其秩為），其秩為m，B是矩陣是矩陣A中的一個中的一個mm階的滿階的滿秩矩陣，稱秩矩陣，稱B是線性規(guī)劃問題的一個基。是

18、線性規(guī)劃問題的一個基。B中的每一個中的每一個列向量列向量Pj稱為稱為基向量基向量，與基向量，與基向量Pj對應(yīng)的變量對應(yīng)的變量xj稱為稱為基基變量變量。線性規(guī)劃中除基變量以外的變量稱為。線性規(guī)劃中除基變量以外的變量稱為非基變量非基變量。基解基解：在約束方程組中，令所有的非基變量為零，在約束方程組中，令所有的非基變量為零，則此時可得到一個唯一解則此時可得到一個唯一解X(x1, xm ,0,0)T。稱。稱X為線性規(guī)劃問題的基解。為線性規(guī)劃問題的基解。基可行解：基可行解：滿足變量非負(fù)約束條件的基解稱為基滿足變量非負(fù)約束條件的基解稱為基可行解。可行解。可行基可行基：對應(yīng)于基可行解的基稱為可行基。對應(yīng)于基

19、可行解的基稱為可行基。退化基本解：退化基本解：基解中非零分量個數(shù)小于基解中非零分量個數(shù)小于m?；咀顑?yōu)解基本最優(yōu)解：能使目標(biāo)函數(shù)達(dá)到最優(yōu)值的基可行能使目標(biāo)函數(shù)達(dá)到最優(yōu)值的基可行解稱為基本最優(yōu)解。解稱為基本最優(yōu)解。最優(yōu)基最優(yōu)基：基本最優(yōu)解對應(yīng)的基稱為最優(yōu)基?；咀顑?yōu)解對應(yīng)的基稱為最優(yōu)基。第二節(jié)線性規(guī)劃問題解的概念及性質(zhì)第二節(jié)線性規(guī)劃問題解的概念及性質(zhì) 求出下列線性規(guī)劃問題的全部基解，指出其中的求出下列線性規(guī)劃問題的全部基解，指出其中的基可行解，并確定最優(yōu)解基可行解，并確定最優(yōu)解0 x4x x10 x2xx5 xst.3x2xMaxZ12421121533-5xx求出下列線性規(guī)劃模型的基解，并指出

20、哪些是基可行解求出下列線性規(guī)劃模型的基解，并指出哪些是基可行解第二節(jié)線性規(guī)劃問題解的概念及性質(zhì)第二節(jié)線性規(guī)劃問題解的概念及性質(zhì)0 x,x124x 16 4x82x xst.3x2xMaxZ21212121第二節(jié)線性規(guī)劃問題解的概念及性質(zhì)第二節(jié)線性規(guī)劃問題解的概念及性質(zhì)(P1,P2,P3)=16B1 (P1,P2,P3)X（1）(4,3,-2,0,0)T(P1,P2,P4)=-4B2 (P1,P2,P4)X（2）(2,3, 0,8,0)T(P1,P2,P5)=-8B3 (P1,P2,P5)X（3）(4,2,0,0,4)T(P1,P3,P4)=0(P1,P3,P5)=-4B4 (P1,P3,P5)

21、X（4）(4,0,4,0,12)T(P1,P4,P5)= 1B5 (P1,P4,P5)X（5）(8,0,0,-16,12)T(P2,P3,P4)= 4B6 (P2,P3,P4)X（6）(0,3,2,16,0)T(P2,P3,P5)=0(P2,P4,P5)=2B7 (P2,P4,P5)X（7）(0,4,0,16,-4)T(P3,P4,P5)=1B8 (P3,P4,P5)X（8）(0,0,8,16,12)T0 x,x,x6x4x2x2xxxst.3xxx3MaxZ321321321321求線性規(guī)劃問題的基解，基本可行解，最優(yōu)解0 x,x,x,x3x2xx22x7x4x3x2xst.x23xx2x5

22、MinZ4321432143214321定理定理1若線性規(guī)劃問題存在可行域，則問題的可行若線性規(guī)劃問題存在可行域，則問題的可行域是凸集。域是凸集。定理定理2線性規(guī)劃問題的基可行解線性規(guī)劃問題的基可行解X對應(yīng)線性規(guī)劃問對應(yīng)線性規(guī)劃問題可行域的頂點(diǎn)。題可行域的頂點(diǎn)。定理定理3若線性規(guī)劃問題有最優(yōu)解，一定存在一個基若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解。可行解是最優(yōu)解。第二節(jié)線性規(guī)劃問題解的概念及性質(zhì)第二節(jié)線性規(guī)劃問題解的概念及性質(zhì)引理引理 線性規(guī)劃問題的可行解線性規(guī)劃問題的可行解X=(x1, x2, xn)T為基為基本可行解的充要條件是本可行解的充要條件是X的正分量所對應(yīng)的系數(shù)列向的

23、正分量所對應(yīng)的系數(shù)列向量線性獨(dú)立。量線性獨(dú)立。2.3單純形法單純形法單純形跌代的基本思路是：單純形跌代的基本思路是： 先找出一個基可行解，判斷其是否先找出一個基可行解，判斷其是否為最優(yōu)解，如為否，則轉(zhuǎn)換到相鄰的基為最優(yōu)解，如為否，則轉(zhuǎn)換到相鄰的基可行解，并使目標(biāo)函數(shù)值不斷增大，一可行解，并使目標(biāo)函數(shù)值不斷增大，一直找到最優(yōu)解為止。直找到最優(yōu)解為止。0 x,x,xxaxaxabxa xa xast.xCxCxCMaxZ32123232221211313212111332211b0 x,x,xxaxaxabxa xa xast.xCxCxCMaxZ3212532322212114313212111

24、332211bxx1001a 232221131211aaaaa2514bxbx是否為最優(yōu)解若約束條件為 添加人工變量x3x4x1x2x530230XBCBb171011140139x4x500 0 x,x,x97x4xx3 x xxst.3x3x2xMaxZ321321321321用單純形法求解下列問題用單純形法求解下列問題解：標(biāo)準(zhǔn)化得解：標(biāo)準(zhǔn)化得0 x,x,x,x,x9x 7x4xx3 x x xxst.3x3x2xMaxZ5432153214321321檢驗(yàn)是否最優(yōu)v 用Xj上面的Cj值減去CBTPj數(shù)字乘積之和得到檢驗(yàn)數(shù)，v若檢驗(yàn)數(shù)0且基變量中不含人工變量，表中基可行解為最優(yōu)解，計算結(jié)

25、束。v若檢驗(yàn)數(shù)0時，有Pj0，則問題為無界解，計算結(jié)束，v否則轉(zhuǎn)下一步，找出新的基可行解x3x4x1x2x530230XBCBb171011140139x4x5003023039/4 Cj-zj0 x,x,x97x4xx3 x xxst.3x3x2xMaxZ321321321321用單純形法求解下列問題用單純形法求解下列問題解：標(biāo)準(zhǔn)化得解：標(biāo)準(zhǔn)化得0 x,x,x,x,x9x 7x4xx3 x x xxst.3x3x2xMaxZ5432153214321321單純形法計算步驟v3、確定換入基變量，非負(fù)檢驗(yàn)數(shù)中最大的對應(yīng)的變量。v4、確定換出基變量。比值最小的。v5、對應(yīng)這個基找出新的基可行解x3

26、x4x1x2x530230XBCBb171011140139x4x50030230-3/47/4103/41/401-1/41/4-9/405/40-3/43/49/4x4x203-124/3-1/31001-1/31/3-1 -5/300-1/312x1x22339/4 19 Cj-zjCj-zjCj-zj0 x,x,x97x4xx3 x xxst.3x3x2xMaxZ321321321321用單純形法求解下列問題用單純形法求解下列問題X*=(1,2,0,0,0)T Z*=8解：標(biāo)準(zhǔn)化得解：標(biāo)準(zhǔn)化得0 x,x,x,x,x9x 7x4xx3 x x xxst.3x3x2xMaxZ5432153

27、214321321單純形法計算步驟v1、將非標(biāo)準(zhǔn)型的線性規(guī)劃問題轉(zhuǎn)化成標(biāo)準(zhǔn)型，設(shè)法使約束方程的系數(shù)矩陣中包含單位矩陣，以此作為求出問題的初始基可行解v2、檢驗(yàn)是否最優(yōu)，用Xj上面的Cj值減去CB與Xj中數(shù)字乘積之和得到檢驗(yàn)數(shù)，若檢驗(yàn)數(shù)0且基變量中不含人工變量，表中基可行解為最優(yōu)解，計算結(jié)束。若檢驗(yàn)數(shù)0時，有Pj0，則問題為無界解，計算結(jié)束，否則轉(zhuǎn)下一步v3、確定換入基變量，非負(fù)檢驗(yàn)數(shù)中最大的對應(yīng)的變量。v4、確定換出基變量。v5、對應(yīng)這個基找出新的基可行解3 4 0 0 0 x1 x2 x3 x4 x51020231000100013915x3x4x5000CBXBbCj-Zj3400059/

28、2x3x2x50409/20101/203101003/2200-3/21300-20Cj-Zj3/43Cj-Zjx3x2x10433/4100-3/41/29/40013/4-1/29/20101/200001/4-3/293練習(xí)0 x,x812x3x 122x 4 xst.5x3xMaxZ 1)212121210 x,x,x20 xxx10 x2xx60 x x3xst.xx2xMaxZ 2)3213213213213213x,2x, 1x17xx2x20 xx44x132x2x x-st.x4x6xMaxZ 3)3213213213213210 x,x,x,x,x15x26xx35x6x

29、3x x xst.x3xx2x45xMaxZ543215321432154321大M法人工變量不能夠影響目標(biāo)函數(shù)，必須取0 用M放大人工變量的影響0 x,x,x16x2x84x20 x42x42x 2x4xst.xx2xMaxZ321321 213213210 x16x2x84x20 x42x4-2x 2x4xst.000 xx2xMaxZ7- 17 3216 21543215764321xxxxMxxxx0 x,x,x6 2x3x82x4x xst.3x7x3xMinZ321213213210 x,x,x,x,x6x- 2x3x8 x-2x4x xst.3x7x3xMaxZ543215214

30、3213210 x,x,x,x,x,x,x6x x- 2x3x8 x x-2x4x xst.Mx-Mx-3x7x3xMaxZ765432175216432176321例：用單純形法求解下列問題例：用單純形法求解下列問題解：標(biāo)準(zhǔn)化得解：標(biāo)準(zhǔn)化得引入人工變量得引入人工變量得-3 -7 -3 0 0 -M -Mx1 x2 x3 x4 x5 x6 x74M-36M-7-M2M-3-M1 4 2 -1 0 1 03 2 0 0 -1 0 1001/411/2-1/401/405/20-11/2-1-1/2186 x6x7 -M-M 23x2x7 -7-M 22 -M04525-MM-214721-M0M

31、-234784/5x2x1 -7-3 9/5013/5-3/10 1/103/10-1/1010-2/51/5-2/5-1/52/54/5000-3/2-1/2M-23M-21CBXBbCj-ZjCj-ZjCj-Zj最優(yōu)解最優(yōu)解X（0.8，1.8，0，0，0，0，0）T最優(yōu)值最優(yōu)值Z15大大M法：法：兩階段法v分成兩階段0 x,x,x,x,x,x,x6x x- 2x3x8 x x-2x4x xst.Mx-Mx-3x7x3xMaxZ7654321752164321763210 x,x,x,x,x,x,x6x x- 2x3x8 x x-2x4x xst.xxMinW7654321752164321

32、760 x,x,x,x,x6x- 2x3x8 x-2x4x xst.3x7x3xMaxZ543215214321321第一階段：第一階段：第二階段：第二階段：0 0 0 0 0 -1 -1x1 x2 x3 x4 x5 x6 x7 4 6-1 2-11 4 2 -1 0 1 03 2 0 0 -1 0 1001/411/2-1/401/405/20-11/2-1-1/2186 x6x7 -1-1 23x2x7 0-1 22 -10251-21023-84/5x2x1 0 0 9/5013/5-3/10 1/103/10-1/1010-2/51/5-2/5-1/52/54/5000 0 01-1-

33、CBXBbCj-ZjCj-ZjCj-Zj0 0 0 0 0 -1 -1x1 x2 x3 x4 x5 x6 x746-12-11 4 2 -1 0 1 03 2 0 0 -1 0 10086 x6x7 -1-1 23 CBXBbCj-Zj1/411/2-1/401/405/20-11/2-1-1/21x2x7 0-1 2284/5 Cj-Zj5/20-11/2-1-3/20 x2x1 00 9/5013/5-3/10 1/103/10-1/1010-2/51/5-2/5-1/52/54/500000Cj-Zj-1-1兩階段法：兩階段法：x1 x2 x3 x4 x5 -3 -7 -3 0 00 x

34、,x,x,x,x6x- 2x3x8 x-2x4x xst.3x7x3xMaxZ543215214321321CBXBb-7-3 0 0 0 -3/2 -1/2用大M法和兩階段法求解線性規(guī)劃問題0 x,x,x5xx x4x2x18x2x 3xst.xx5x4MaxZ 1)321321 213213210 x,x,x,x,x5 xx x4x x2x81 x-x2x3xst.xx54xMaxZ543213 2152143213210 x,x,x,x,x,x,x5 x xx x4 x x2x81 x x-x2x3xst.Mx-Mx-x5xx4MaxZ765432173 215216432176321例

35、：用單純形法求解下列問題例：用單純形法求解下列問題解：標(biāo)準(zhǔn)化得解：標(biāo)準(zhǔn)化得引入人工變量得引入人工變量得0 x,x,x5xx x4x2x18x2x 3xst.xx5x4MaxZ 1)321321 21321321第一階段：第一階段：第二階段：第二階段：0 x,x,x,x,x,x,x5 x xx x4 x x2x81 x x-x2x3xst.xxMin w765432173 2152164321760 x,x,x,x,x5 xx x4 x x2x81 x-x2x3xst.x5xx4MaxZ543213 215214321321用大M法和兩階段法求解線性規(guī)劃問題0 x,x 42x 216x4x 42

36、 6x8x st.xxMaxZ 3)2122121210 x,x,x16x2x84x20 x42x42x 2x4xst.xx2xMaxZ 2)321321 213213210 x,x,x,x10 xxx2 x20 x5x2x153x 2x xst.x-x3x2xMaxZ 4)43214321 3 21 32 14321單純形法小結(jié)單純形法小結(jié) 迭迭 代代 運(yùn)運(yùn) 算算1、用非基變量替換基變量、用非基變量替換基變量2、對主元素行（第、對主元素行（第l行）行） 令令bi/ aikbl;alj/alk ajl3、對主元素列（第、對主元素列（第k列）列） 令令1 alk;0 其它元素其它元素4、表中其它

37、行列元素、表中其它行列元素 令令aij-ali/alkaik aij bi-bl/alkaik bi添加松弛變量、人工變量添加松弛變量、人工變量列出初始單純形表列出初始單純形表計算非基變量計算非基變量各列的檢驗(yàn)數(shù)各列的檢驗(yàn)數(shù)J所有所有J0基變量中有非基變量中有非零的人工變量零的人工變量某非基變量某非基變量檢驗(yàn)數(shù)為零檢驗(yàn)數(shù)為零唯一唯一最優(yōu)解最優(yōu)解對任一對任一J 0有有aik0令令KmaxJ 對所有對所有aik 0計算計算ibi/ aik令令lminixl為換出變量為換出變量aik為主元素為主元素?zé)o界解無界解無可行解無可行解無窮多最優(yōu)解無窮多最優(yōu)解是是否否否否是是否否是是是是否否i=5; 下為某極

38、大值線性規(guī)劃問題的初始單純形表及迭代后的表，X4、X5為松弛變量，試求表中al的值及各變量下標(biāo)mt的值X4X5X5X1Xm=X4，Xn=X5，Xs=X1，Xt=X5；g=1，h=0，L=0；100-21b=2，c=4，d=-2；24-2300077=1-2C1-0.i-3f=3;-3a=-3;52e=2;-53/2-3j=-5;k=3/2g=-5; 下表為用單純形法計算時某一步的表格，已知該線性規(guī)劃的目標(biāo)函數(shù)為 ，約束形式為，X3、X4為松弛變量，表中解代入后得z=10，求ag的值并判斷表中給出的解是否最優(yōu) c=1，d=0； b=0，f=0；013-5e=-10305e=4/5;2a=2;Z=

39、5X1+3X2=10213X5maxXz054/500-5第第4節(jié)線性規(guī)劃應(yīng)用節(jié)線性規(guī)劃應(yīng)用一、什么樣的問題可以建立線性規(guī)劃模型？一、什么樣的問題可以建立線性規(guī)劃模型？一般講，一個經(jīng)濟(jì)、管理問題凡滿足以下條件時，才能建立線性規(guī)劃一般講，一個經(jīng)濟(jì)、管理問題凡滿足以下條件時，才能建立線性規(guī)劃模型模型（1）要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且為線性函數(shù)；）要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且為線性函數(shù)；（2）存在著多種方案；）存在著多種方案；（3）要求達(dá)到的目標(biāo)是在一定的約束條件下實(shí)現(xiàn)的，這些約束條件）要求達(dá)到的目標(biāo)是在一定的約束條件下實(shí)現(xiàn)的，這些約束條件可用線性等式或不等式來描述?？捎?/p>

40、線性等式或不等式來描述。二、建立模型的步驟二、建立模型的步驟（1）設(shè)變量）設(shè)變量（2）定目標(biāo)）定目標(biāo)（3）列約束）列約束第第4節(jié)線性規(guī)劃應(yīng)用節(jié)線性規(guī)劃應(yīng)用例例.（生產(chǎn)計劃問題）（生產(chǎn)計劃問題）某廠生產(chǎn)某廠生產(chǎn)、三種產(chǎn)品，都分別經(jīng)三種產(chǎn)品，都分別經(jīng)A、B兩道工序兩道工序加工。設(shè)加工。設(shè)A工序可分別在設(shè)備工序可分別在設(shè)備A1或或A2上完成，有上完成，有B1，B2，B3三三種設(shè)備可用于完成種設(shè)備可用于完成B工序。已知產(chǎn)品工序。已知產(chǎn)品可在可在A，B任何一種設(shè)備任何一種設(shè)備上加工；產(chǎn)品上加工；產(chǎn)品可在任何規(guī)格的可在任何規(guī)格的A設(shè)備上加工，但完成設(shè)備上加工，但完成B工序工序時，只能在時，只能在B1設(shè)備上加工；產(chǎn)品設(shè)備上加工