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

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

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

3、節(jié)線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型第一節(jié)線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型一、什么是線(xiàn)性規(guī)劃一、什么是線(xiàn)性規(guī)劃例例1.某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種兩種原材料的消耗，如表原材料的消耗，如表1-1所示。所示。該工廠每生產(chǎn)一件產(chǎn)品該工廠每生產(chǎn)一件產(chǎn)品可獲利可獲利2元，每生產(chǎn)元，每生產(chǎn)一件產(chǎn)品一件產(chǎn)品可獲利可獲利3元，元，問(wèn)應(yīng)如何安排計(jì)劃使該問(wèn)應(yīng)如何安排計(jì)劃使該工廠獲利最多？工廠獲利最多？表表1-1第一節(jié)線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型第一節(jié)線(xiàn)性規(guī)劃問(wèn)題及其數(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é)線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型第一節(jié)線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型例例2.捷運(yùn)公司在下一年度的捷運(yùn)公司在下一年度的14月的月的4個(gè)月內(nèi)擬租用倉(cāng)庫(kù)堆放物資。已知個(gè)月內(nèi)擬租用倉(cāng)庫(kù)堆放物資。已知各月份所需倉(cāng)庫(kù)面積見(jiàn)表各月份所需倉(cāng)庫(kù)面積見(jiàn)表1。倉(cāng)庫(kù)租借費(fèi)用隨合同期而定，期限越長(zhǎng)，折扣越。倉(cāng)庫(kù)租借費(fèi)用隨合同期而定，期限越長(zhǎng)，折扣越大，具體數(shù)字見(jiàn)表大，具體數(shù)字見(jiàn)表2。租借倉(cāng)庫(kù)的合同每月初都可加辦理，每份合同具體規(guī)定。租借倉(cāng)庫(kù)的合同每月初都可加辦理，每份合同具

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

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

7、%，73%，85%和和92%的的硫酸出售，每噸價(jià)格分別為硫酸出售，每噸價(jià)格分別為400，700，1400，1900和和2500元，問(wèn)應(yīng)購(gòu)買(mǎi)各種硫酸各多少，才能滿(mǎn)足生產(chǎn)要求，并元，問(wèn)應(yīng)購(gòu)買(mǎi)各種硫酸各多少，才能滿(mǎn)足生產(chǎn)要求，并使得所花費(fèi)用最??？使得所花費(fèi)用最?。康谝还?jié)線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型第一節(jié)線(xiàn)性規(guī)劃問(wèn)題及其數(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é)一下什么是線(xiàn)性規(guī)劃？思考：從數(shù)學(xué)模型的角度總結(jié)一下什么是線(xiàn)性規(guī)劃？第一節(jié)線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型第一節(jié)線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型1、每個(gè)問(wèn)題都有一組未知變量（、每個(gè)問(wèn)題都有一組未知變量（X1，X2，Xn）表示）表示某一方案，這組未知變量的一組定值就代表一個(gè)具體方案，某一方案，這組未知變量的一組定值就代表一個(gè)具體方案，通常要求這些未知變量取值是非負(fù)的。我們稱(chēng)未知變量為通常要求這些未知變量取值是非負(fù)的。我們稱(chēng)未知變量為變變量量 ,或稱(chēng)或稱(chēng)決策變量決策變量。2、存在一定的、存在一定的約束條件約

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

10、學(xué)模型第一節(jié)線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型0 x,x,x)b (xaxaxa)b (xaxaxa)b (xaxaxast.xcxcxcMax(Min)Zn21mnmn2m21m12n2n2221211n1n212111nn2211或或或三、線(xiàn)性規(guī)劃數(shù)學(xué)模型的一般形式：三、線(xiàn)性規(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é)線(xiàn)性規(guī)

11、劃問(wèn)題及其數(shù)學(xué)模第一節(jié)線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型型四、線(xiàn)性規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)形式：四、線(xiàn)性規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)形式：0b0 x,x,xbxaxaxab xaxaxab xaxaxast.xcxcxcMaxZin21mnmn2m21m12n2n2221211n1n212111nn2211第一節(jié)線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型第一節(jié)線(xiàn)性規(guī)劃問(wèn)題及其數(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ù)決策變量取值無(wú)約束決策變量取值無(wú)約束第一節(jié)線(xiàn)性規(guī)

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

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

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

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

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

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

18、線(xiàn)性規(guī)劃問(wèn)題的一個(gè)基。B中的每一個(gè)中的每一個(gè)列向量列向量Pj稱(chēng)為稱(chēng)為基向量基向量，與基向量，與基向量Pj對(duì)應(yīng)的變量對(duì)應(yīng)的變量xj稱(chēng)為稱(chēng)為基基變量變量。線(xiàn)性規(guī)劃中除基變量以外的變量稱(chēng)為。線(xiàn)性規(guī)劃中除基變量以外的變量稱(chēng)為非基變量非基變量。基解基解：在約束方程組中，令所有的非基變量為零，在約束方程組中，令所有的非基變量為零，則此時(shí)可得到一個(gè)唯一解則此時(shí)可得到一個(gè)唯一解X(x1, xm ,0,0)T。稱(chēng)。稱(chēng)X為線(xiàn)性規(guī)劃問(wèn)題的基解。為線(xiàn)性規(guī)劃問(wèn)題的基解?；尚薪猓夯尚薪猓簼M(mǎn)足變量非負(fù)約束條件的基解稱(chēng)為基滿(mǎn)足變量非負(fù)約束條件的基解稱(chēng)為基可行解?？尚薪狻？尚谢尚谢簩?duì)應(yīng)于基可行解的基稱(chēng)為可行基。對(duì)應(yīng)于基

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

20、哪些是基可行解求出下列線(xiàn)性規(guī)劃模型的基解，并指出哪些是基可行解第二節(jié)線(xiàn)性規(guī)劃問(wèn)題解的概念及性質(zhì)第二節(jié)線(xiàn)性規(guī)劃問(wèn)題解的概念及性質(zhì)0 x,x124x 16 4x82x xst.3x2xMaxZ21212121第二節(jié)線(xiàn)性規(guī)劃問(wèn)題解的概念及性質(zhì)第二節(jié)線(xiàn)性規(guī)劃問(wèn)題解的概念及性質(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求線(xiàn)性規(guī)劃問(wèn)題的基解，基本可行解，最優(yōu)解0 x,x,x,x3x2xx22x7x4x3x2xst.x23xx2x5

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

23、正分量所對(duì)應(yīng)的系數(shù)列向量線(xiàn)性獨(dú)立。量線(xiàn)性獨(dú)立。2.3單純形法單純形法單純形跌代的基本思路是：?jiǎn)渭冃蔚幕舅悸肥牵?先找出一個(gè)基可行解，判斷其是否先找出一個(gè)基可行解，判斷其是否為最優(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用單純形法求解下列問(wèn)題用單純形法求解下列問(wèn)題解：標(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)解，計(jì)算結(jié)

25、束。v若檢驗(yàn)數(shù)0時(shí)，有Pj0，則問(wèn)題為無(wú)界解，計(jì)算結(jié)束，v否則轉(zhuǎn)下一步，找出新的基可行解x3x4x1x2x530230XBCBb171011140139x4x5003023039/4 Cj-zj0 x,x,x97x4xx3 x xxst.3x3x2xMaxZ321321321321用單純形法求解下列問(wèn)題用單純形法求解下列問(wèn)題解：標(biāo)準(zhǔn)化得解：標(biāo)準(zhǔn)化得0 x,x,x,x,x9x 7x4xx3 x x xxst.3x3x2xMaxZ5432153214321321單純形法計(jì)算步驟v3、確定換入基變量，非負(fù)檢驗(yàn)數(shù)中最大的對(duì)應(yīng)的變量。v4、確定換出基變量。比值最小的。v5、對(duì)應(yīng)這個(gè)基找出新的基可行解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用單純形法求解下列問(wèn)題用單純形法求解下列問(wèn)題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單純形法計(jì)算步驟v1、將非標(biāo)準(zhǔn)型的線(xiàn)性規(guī)劃問(wèn)題轉(zhuǎn)化成標(biāo)準(zhǔn)型，設(shè)法使約束方程的系數(shù)矩陣中包含單位矩陣，以此作為求出問(wèn)題的初始基可行解v2、檢驗(yàn)是否最優(yōu)，用Xj上面的Cj值減去CB與Xj中數(shù)字乘積之和得到檢驗(yàn)數(shù)，若檢驗(yàn)數(shù)0且基變量中不含人工變量，表中基可行解為最優(yōu)解，計(jì)算結(jié)束。若檢驗(yàn)數(shù)0時(shí)，有Pj0，則問(wèn)題為無(wú)界解，計(jì)算結(jié)束，否則轉(zhuǎn)下一步v3、確定換入基變量，非負(fù)檢驗(yàn)數(shù)中最大的對(duì)應(yīng)的變量。v4、確定換出基變量。v5、對(duì)應(yīng)這個(gè)基找出新的基可行解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例：用單純形法求解下列問(wèn)題例：用單純形法求解下列問(wèn)題解：標(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法和兩階段法求解線(xiàn)性規(guī)劃問(wèn)題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、：用單純形法求解下列問(wèn)題例：用單純形法求解下列問(wèn)題解：標(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法和兩階段法求解線(xiàn)性規(guī)劃問(wèn)題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、對(duì)主元素行（第、對(duì)主元素行（第l行）行） 令令bi/ aikbl;alj/alk ajl3、對(duì)主元素列（第、對(duì)主元素列（第k列）列） 令令1 alk;0 其它元素其它元素4、表中其它

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

38、大值線(xiàn)性規(guī)劃問(wèn)題的初始單純形表及迭代后的表，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; 下表為用單純形法計(jì)算時(shí)某一步的表格，已知該線(xiàn)性規(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é)線(xiàn)性規(guī)劃應(yīng)用節(jié)線(xiàn)性規(guī)劃應(yīng)用一、什么樣的問(wèn)題可以建立線(xiàn)性規(guī)劃模型？一、什么樣的問(wèn)題可以建立線(xiàn)性規(guī)劃模型？一般講，一個(gè)經(jīng)濟(jì)、管理問(wèn)題凡滿(mǎn)足以下條件時(shí)，才能建立線(xiàn)性規(guī)劃一般講，一個(gè)經(jīng)濟(jì)、管理問(wèn)題凡滿(mǎn)足以下條件時(shí)，才能建立線(xiàn)性規(guī)劃模型模型（1）要求解問(wèn)題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來(lái)反映，且為線(xiàn)性函數(shù)；）要求解問(wèn)題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來(lái)反映，且為線(xiàn)性函數(shù)；（2）存在著多種方案；）存在著多種方案；（3）要求達(dá)到的目標(biāo)是在一定的約束條件下實(shí)現(xiàn)的，這些約束條件）要求達(dá)到的目標(biāo)是在一定的約束條件下實(shí)現(xiàn)的，這些約束條件可用線(xiàn)性等式或不等式來(lái)描述。可用

40、線(xiàn)性等式或不等式來(lái)描述。二、建立模型的步驟二、建立模型的步驟（1）設(shè)變量）設(shè)變量（2）定目標(biāo)）定目標(biāo)（3）列約束）列約束第第4節(jié)線(xiàn)性規(guī)劃應(yīng)用節(jié)線(xiàn)性規(guī)劃應(yīng)用例例.（生產(chǎn)計(jì)劃問(wèn)題）（生產(chǎn)計(jì)劃問(wè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工序工序時(shí)，只能在時(shí)，只能在B1設(shè)備上加工；產(chǎn)品設(shè)備上加工