運(yùn)籌學(xué)全冊(cè)配套完整課件2

1、本章知識(shí)結(jié)構(gòu)本章知識(shí)結(jié)構(gòu)第第 2 章章 線性規(guī)劃線性規(guī)劃本章教學(xué)目標(biāo)與要求本章教學(xué)目標(biāo)與要求 n n掌握線性規(guī)劃模型基本概念，熟悉線性規(guī)劃的標(biāo)準(zhǔn)型掌握線性規(guī)劃模型基本概念，熟悉線性規(guī)劃的標(biāo)準(zhǔn)型并能將一般線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)型；并能將一般線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)型； n n理解單純形法的基本原理，掌握應(yīng)用單純形表求解線性理解單純形法的基本原理，掌握應(yīng)用單純形表求解線性規(guī)劃的方法；規(guī)劃的方法； n n對(duì)給定的線性規(guī)劃問(wèn)題，能熟練寫出其對(duì)偶問(wèn)題，掌握對(duì)給定的線性規(guī)劃問(wèn)題，能熟練寫出其對(duì)偶問(wèn)題，掌握對(duì)偶單純形算法，能對(duì)線性規(guī)劃的解進(jìn)行靈敏度分析；對(duì)偶單純形算法，能對(duì)線性規(guī)劃的解進(jìn)行靈敏度分析； n n

2、能熟練地建立實(shí)際問(wèn)題的線性規(guī)劃模型。能熟練地建立實(shí)際問(wèn)題的線性規(guī)劃模型。2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法2.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型【例例2.1】（生產(chǎn)計(jì)劃問(wèn)題）某企業(yè)生產(chǎn)（生產(chǎn)計(jì)劃問(wèn)題）某企業(yè)生產(chǎn)I、II和和III三種產(chǎn)品三種產(chǎn)品，每種產(chǎn)品需經(jīng)過(guò)三道工序，每種產(chǎn)品需經(jīng)過(guò)三道工序A、B、C，每件產(chǎn)品在每道工序中，每件產(chǎn)品在每道工序中的工時(shí)定額、每道工序在每周可利用的有效工時(shí)和每件產(chǎn)品的的工時(shí)定額、每道工序在每周可利用的有效工時(shí)和每件產(chǎn)品的利潤(rùn)見下表。問(wèn)每種產(chǎn)品各生產(chǎn)多少利潤(rùn)見下表。問(wèn)每種產(chǎn)品各生產(chǎn)多少,可使這一周內(nèi)生產(chǎn)的產(chǎn)品可使這一周內(nèi)生產(chǎn)的產(chǎn)品所獲利潤(rùn)

3、最大？所獲利潤(rùn)最大？定額定額( (工時(shí)工時(shí)/ /件件) )產(chǎn)品型號(hào)產(chǎn)品型號(hào)每周可利用每周可利用的有效工時(shí)的有效工時(shí)IIIIII工序工序A1.21.01.15400B0.70.90.62800C0.90.81.03600利潤(rùn)（元利潤(rùn)（元/ /件）件）1015122.1.1問(wèn)題的引入問(wèn)題的引入2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法設(shè)一周內(nèi)企業(yè)各產(chǎn)品的生產(chǎn)件數(shù)為設(shè)一周內(nèi)企業(yè)各產(chǎn)品的生產(chǎn)件數(shù)為xj( ( j=1,2,3) ) 生產(chǎn)計(jì)劃問(wèn)題的生產(chǎn)計(jì)劃問(wèn)題的數(shù)學(xué)模型數(shù)學(xué)模型： 其中其中s.t.是英文是英文“subjectto”（受約束于）的縮寫。（受約束于）的縮寫。定額定額( (工時(shí)工時(shí)/ /件件

4、) )產(chǎn)品型號(hào)產(chǎn)品型號(hào)每周可利用每周可利用的有效工時(shí)的有效工時(shí)IIIIII工序工序A1.21.01.15400B0.70.90.62800C0.90.81.03600利潤(rùn)（元利潤(rùn)（元/ /件）件）101512123123123123max1015121.11.01.154000.70.90.62800. .0.90.81.0360001, 2, 3jzxxxxxxxxxs txxxxj2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 【例例2.22.2】 （營(yíng)養(yǎng)配餐問(wèn)題）假定一個(gè)成年人每天需要從（營(yíng)養(yǎng)配餐問(wèn)題）假定一個(gè)成年人每天需要從食物中獲取食物中獲取30003000卡路里熱量，卡路里熱量，5

5、555克蛋白質(zhì)和克蛋白質(zhì)和800800毫克鈣。如果毫克鈣。如果市場(chǎng)上只有四種食品可選，它們每千克所含熱量和營(yíng)養(yǎng)成份以市場(chǎng)上只有四種食品可選，它們每千克所含熱量和營(yíng)養(yǎng)成份以及市場(chǎng)價(jià)格如下表所示。問(wèn)如何選擇才能滿足營(yíng)養(yǎng)的前提下使及市場(chǎng)價(jià)格如下表所示。問(wèn)如何選擇才能滿足營(yíng)養(yǎng)的前提下使購(gòu)買食品的費(fèi)用最?。抠?gòu)買食品的費(fèi)用最??？ 食品的營(yíng)養(yǎng)構(gòu)成表食品的營(yíng)養(yǎng)構(gòu)成表序號(hào)序號(hào) 食品名稱食品名稱 熱量熱量(卡路里卡路里)蛋白質(zhì)蛋白質(zhì)(g)鈣鈣(mg)價(jià)格價(jià)格(元元)1豬肉豬肉100050400102雞蛋雞蛋8006020063大米大米9002030034白菜白菜200105002則該問(wèn)題的數(shù)學(xué)模型為：則該問(wèn)題的數(shù)

6、學(xué)模型為：2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法設(shè)設(shè)xj( ( j=1,2,3,4) )為第為第 j 種食品每天的購(gòu)買量，種食品每天的購(gòu)買量，1234123412341234min10632100080090020030005060201055.4002003005008000,(1,2,3,4)jzxxxxxxxxxxxxstxxxxxj2.1.2線性規(guī)劃問(wèn)題及其模型線性規(guī)劃問(wèn)題及其模型上面所建立的數(shù)學(xué)模型中有三個(gè)要素：上面所建立的數(shù)學(xué)模型中有三個(gè)要素：l）決策變量決策變量 這些決策變量的一組定值代表所給問(wèn)題的一個(gè)這些決策變量的一組定值代表所給問(wèn)題的一個(gè)具體解決方案、措施等。具體解決

7、方案、措施等。2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法2）目標(biāo)函數(shù)目標(biāo)函數(shù)一個(gè)決策問(wèn)題總有一個(gè)試圖達(dá)到的目標(biāo)，數(shù)學(xué)上一個(gè)決策問(wèn)題總有一個(gè)試圖達(dá)到的目標(biāo)，數(shù)學(xué)上表示為決策變量的函數(shù)，稱為目標(biāo)函數(shù)。表示為決策變量的函數(shù)，稱為目標(biāo)函數(shù)。3）約束條件約束條件決策變量取值時(shí)受到的各種資源限制，通常表決策變量取值時(shí)受到的各種資源限制，通常表示成決策變量的等式或不等式。示成決策變量的等式或不等式。由這三個(gè)要素組成的問(wèn)題，在數(shù)學(xué)上叫作規(guī)劃問(wèn)題，一般稱由這三個(gè)要素組成的問(wèn)題，在數(shù)學(xué)上叫作規(guī)劃問(wèn)題，一般稱為為數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃。如果目標(biāo)函數(shù)及約束條件均為決策變量的如果目標(biāo)函數(shù)及約束條件均為決策變量的線性函線性

8、函數(shù)，數(shù)，則稱這樣的數(shù)學(xué)規(guī)劃為則稱這樣的數(shù)學(xué)規(guī)劃為線性規(guī)劃線性規(guī)劃，否則稱為，否則稱為非線性規(guī)劃非線性規(guī)劃。2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法線性規(guī)劃的數(shù)學(xué)模型的一般形式為：線性規(guī)劃的數(shù)學(xué)模型的一般形式為： 112211212211212222221222max()( ,)( ,). .( ,)0,1,2,.min nnnnnnmmmnnmjzc xc xc xa xa xaxbaxaxaxbs taxaxaxbxjn或 2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 矩陣形式：矩陣形式： 0XbAX),(. .)max(mintsCXz或向量形式：向量形式： njxxtsCXzj

9、jnj, 2, 10),(. .min)max(1bPj或 其中：其中：C=(=(c1,c2,cn) )是是n 維行向量維行向量，稱為價(jià)值系數(shù)向量，簡(jiǎn)稱為價(jià)值系數(shù)向量，簡(jiǎn)稱為稱為價(jià)值向量?jī)r(jià)值向量；b=(=(b1,b2,bm) )T是是m 維列向量維列向量, ,稱為稱為資源向量資源向量；X=(=(x1,x2,xn) )T稱為稱為決策向量決策向量；A為技術(shù)系數(shù)矩陣（也稱為消耗為技術(shù)系數(shù)矩陣（也稱為消耗系數(shù)矩陣），簡(jiǎn)稱為系數(shù)矩陣），簡(jiǎn)稱為技術(shù)矩陣技術(shù)矩陣，)(212222111211n21PPPAmnmmnnaaaaaaaaamiiiaaa21iP2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法2.1

10、.3線性規(guī)劃模型的標(biāo)準(zhǔn)型線性規(guī)劃模型的標(biāo)準(zhǔn)型 為了求解方便，通常規(guī)定線性規(guī)劃的某種形式為標(biāo)準(zhǔn)形。為了求解方便，通常規(guī)定線性規(guī)劃的某種形式為標(biāo)準(zhǔn)形。0XbAXCXzmax 線性規(guī)劃的線性規(guī)劃的標(biāo)準(zhǔn)型的特點(diǎn)標(biāo)準(zhǔn)型的特點(diǎn)：目標(biāo)函目標(biāo)函數(shù)是最大化；數(shù)是最大化；b0；約束條件均由等式；約束條件均由等式組成；組成；決策變量均為非負(fù)。決策變量均為非負(fù)。 不滿足上述不滿足上述4 4個(gè)特點(diǎn)的個(gè)特點(diǎn)的LPLP問(wèn)題，稱為非標(biāo)準(zhǔn)形。對(duì)于非標(biāo)準(zhǔn)問(wèn)題，稱為非標(biāo)準(zhǔn)形。對(duì)于非標(biāo)準(zhǔn)形式的線性規(guī)劃，都可以形式的線性規(guī)劃，都可以通過(guò)適當(dāng)?shù)淖儞Q轉(zhuǎn)化為等價(jià)的標(biāo)準(zhǔn)型問(wèn)通過(guò)適當(dāng)?shù)淖儞Q轉(zhuǎn)化為等價(jià)的標(biāo)準(zhǔn)型問(wèn)題。題。njxbxaxaxabxax

11、axabxaxaxatsxcxcxczjmnmnmmnnnnnn,2,1,0.max2211222221211121211122112.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法【例例2.3】將下列線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)型將下列線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)型無(wú)約束321321321321321,0,0632442392.32minxxxxxxxxxxxxtsxxxz 解解 1）引入變量）引入變量 33311331, 0,xxxxxxxx ，使0,0,0,063324422392.332min33213321332133213321xxxxxxxxxxxxxxxxtsxxxxz2.1線性規(guī)劃模型與圖解法線

12、性規(guī)劃模型與圖解法2）第一個(gè)約束引入松弛變量）第一個(gè)約束引入松弛變量x4,第二個(gè)約束引入剩余變量第二個(gè)約束引入剩余變量x5; ; 0, 0, 0, 0, 0, 063324422392. .00332min54332133215332143321543321xxxxxxxxxxxxxxxxxxxxtsxxxxxxz3）目標(biāo)函數(shù)）目標(biāo)函數(shù)min變?yōu)楦淖優(yōu)樽優(yōu)楦淖優(yōu)閙ax0, 0, 0, 0, 0, 063324422392. .00332max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxtsxxxxxxz2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解

13、法4）將第三個(gè)等式約束兩邊同乘以）將第三個(gè)等式約束兩邊同乘以1。最后得到該問(wèn)題的標(biāo)準(zhǔn)形式為：最后得到該問(wèn)題的標(biāo)準(zhǔn)形式為：0, 0, 0, 0, 0, 063324422392. .00332max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxtsxxxxxxz星期所需人數(shù)一300二300三350四400五480六600日5507654321minxxxxxxxz7.,2,1,0550600480350300300765436543254321763217652176541jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxj某產(chǎn)品由2件

14、甲零件和3件乙零件組成。2種零件均須在設(shè)備A、B上加工，每件甲零件在2種設(shè)備上的加工時(shí)間分別為5分鐘和9分鐘；每件乙零件在2種設(shè)備上加工時(shí)間分別為4分鐘和10分鐘。現(xiàn)有設(shè)備A 2臺(tái)，設(shè)備B 3臺(tái)，每臺(tái)設(shè)備可供加工的時(shí)間為每天8小時(shí)。為了保持兩種設(shè)備負(fù)荷均衡，要求一種設(shè)備的加工總時(shí)間不超過(guò)另一種的加工總時(shí)間1小時(shí)。問(wèn)每天加工2種零件各多少，能使總產(chǎn)量最大？ 21,xx)31,21min(21xxy 設(shè)備加工時(shí)間的限制為 96028604521xx1440386010921xx60)109()45(2121xxxx設(shè)備負(fù)荷均衡約束：寫成線性形式： 60)109()45(2121xxxx60)109

15、()45(2121xxxxyz max121xy 231xy ， 于是得到本問(wèn)題的數(shù)學(xué)模型為： yz max0,606460641440109960453121.212121212121xxyxxxxxxxxxyxyts11221 121 22112 122 22221222m ax ()(,)(,). .(,)0,1, 2,.m in nnnnnnmmm nnmjzc xc xc xaxaxaxbaxaxaxbs taxaxaxbxjn 或0XbAX),(. .)max(mintsCXz或njxxtsCXzjjnj, 2, 10),(. .min)max(1bPj或0XbAXCXzmax 線

16、性規(guī)劃的線性規(guī)劃的標(biāo)準(zhǔn)型的特點(diǎn)標(biāo)準(zhǔn)型的特點(diǎn)：目標(biāo)函目標(biāo)函數(shù)是最大化；數(shù)是最大化；b0；約束條件均由等式約束條件均由等式組成；組成；決策變量均為非負(fù)。決策變量均為非負(fù)。 njxbxaxaxabxaxaxabxaxaxatsxcxcxczjmnmnmmnnnnnn,2, 1,0.max2211222221211121211122112.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法2.1.4線性規(guī)劃的圖解法線性規(guī)劃的圖解法 對(duì)于只有兩個(gè)變量的線性規(guī)劃問(wèn)題，可以直接使用圖解法對(duì)于只有兩個(gè)變量的線性規(guī)劃問(wèn)題，可以直接使用圖解法求解。圖解法簡(jiǎn)單直觀，對(duì)一般線性規(guī)劃問(wèn)題的求解富有啟發(fā)求解。圖解法簡(jiǎn)單直觀，對(duì)一

17、般線性規(guī)劃問(wèn)題的求解富有啟發(fā)作用。作用。 圖解法可分三步進(jìn)行：圖解法可分三步進(jìn)行：1）在平面上建立直角坐標(biāo)系；在平面上建立直角坐標(biāo)系；2）根據(jù)約束條件畫出相應(yīng)的半平面，由這些半平面共同確根據(jù)約束條件畫出相應(yīng)的半平面，由這些半平面共同確定的區(qū)域即為定的區(qū)域即為可行域可行域；3）畫出目標(biāo)函數(shù)的等值線，然后沿目標(biāo)函數(shù)要求的方向平畫出目標(biāo)函數(shù)的等值線，然后沿目標(biāo)函數(shù)要求的方向平移至與可行域邊界相切的點(diǎn)，該點(diǎn)就是最優(yōu)解，相應(yīng)的坐標(biāo)即為移至與可行域邊界相切的點(diǎn)，該點(diǎn)就是最優(yōu)解，相應(yīng)的坐標(biāo)即為最優(yōu)解。最優(yōu)解。2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 【例例2.42.4】 求解線性規(guī)劃問(wèn)題求解線性規(guī)劃問(wèn)

18、題 0, 02426023302. .5040max212212121xxxxxxxtsxxz解解應(yīng)用圖解法求解線性規(guī)劃，應(yīng)用圖解法求解線性規(guī)劃，分下面三步求解。分下面三步求解。1）建立直角坐標(biāo)系）建立直角坐標(biāo)系1x2xo2）確定可行域）確定可行域令令3個(gè)約束條件為等式，得到個(gè)約束條件為等式，得到3條直線，畫條直線，畫出第一象限的三個(gè)不等式區(qū)域，他們的交集出第一象限的三個(gè)不等式區(qū)域，他們的交集就是可行域，亦即區(qū)域就是可行域，亦即區(qū)域OABCD，其內(nèi)部及，其內(nèi)部及邊界上的每一個(gè)點(diǎn)都是線性規(guī)劃的解。邊界上的每一個(gè)點(diǎn)都是線性規(guī)劃的解。301530221 xx3020602321 xx122422xA

19、BCD3）確定最優(yōu)解）確定最優(yōu)解目標(biāo)函數(shù)的等值線目標(biāo)函數(shù)的等值線z=40 x1+50 x2( (z z取定某取定某一個(gè)常值一個(gè)常值) ) 。沿著函數(shù)的梯度方向移動(dòng)，。沿著函數(shù)的梯度方向移動(dòng)，函數(shù)值會(huì)增大，當(dāng)移動(dòng)到點(diǎn)頂點(diǎn)函數(shù)值會(huì)增大，當(dāng)移動(dòng)到點(diǎn)頂點(diǎn)( (15,15/2) ) ，再繼續(xù)移動(dòng)就離開區(qū)域了。于是點(diǎn)再繼續(xù)移動(dòng)就離開區(qū)域了。于是點(diǎn)C就就是最優(yōu)解，最優(yōu)值為是最優(yōu)解，最優(yōu)值為z=40z=4015+5015+5015/2=97515/2=975 2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 【例例2.52.5】 求解線性規(guī)劃問(wèn)題求解線性規(guī)劃問(wèn)題 0

20、, 02426023302. .8040max212212121xxxxxxxtsxxz解解該題將例該題將例2.4中的目標(biāo)中的目標(biāo)函數(shù)變?yōu)楹瘮?shù)變?yōu)閦=40 x1+80 x2,可行域不可行域不變。變。由于目標(biāo)函數(shù)等直線由于目標(biāo)函數(shù)等直線z=40 x1+80 x2與直線與直線x1+2x2=30平行，平行， 當(dāng)目標(biāo)函數(shù)的等值線與直線當(dāng)目標(biāo)函數(shù)的等值線與直線x1+2x2=30重合時(shí)，重合時(shí)，目標(biāo)函數(shù)目標(biāo)函數(shù)z=40 x1+80 x2z=40 x1+80 x2達(dá)到最大值達(dá)到最大值12001200。于是線段。于是線段BCBC上的每一個(gè)點(diǎn)均為上的每一個(gè)點(diǎn)均為該問(wèn)題的最優(yōu)解。該問(wèn)題的最優(yōu)解。 1x2xo301

21、530221 xx3020602321 xx2422xABCD2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 【例例2.62.6】 求解線性規(guī)劃問(wèn)題求解線性規(guī)劃問(wèn)題 0,2282. .42max21212121xxxxxxtsxxz1x2xo88221 xx42221xx2解解 由于可行域無(wú)界由于可行域無(wú)界, , 目標(biāo)函目標(biāo)函數(shù)數(shù)z=2x1+4x2z=2x1+4x2沿著它的法線方沿著它的法線方向向(2,4)(2,4)移動(dòng)，移動(dòng)可以無(wú)限移動(dòng)，移動(dòng)可以無(wú)限制下去，而目標(biāo)函數(shù)值一直制下去，而目標(biāo)函數(shù)值一直增加。增加。 所以該線性規(guī)劃問(wèn)所以該線性規(guī)劃問(wèn)題無(wú)有限最優(yōu)解，有題無(wú)有限最優(yōu)解，有無(wú)界解無(wú)界解。

22、2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 【例例2.72.7】 求解線性規(guī)劃問(wèn)題求解線性規(guī)劃問(wèn)題 0,22. .24max212121xxxxtsxxz 解解 約束條件互不相容，沒(méi)有約束條件互不相容，沒(méi)有公共交點(diǎn)，可行域是一個(gè)空集，不存在滿足條件的公共交點(diǎn)，可行域是一個(gè)空集，不存在滿足條件的解，說(shuō)明線性規(guī)劃問(wèn)題無(wú)解，當(dāng)然更沒(méi)有最優(yōu)解，如圖所示。解，說(shuō)明線性規(guī)劃問(wèn)題無(wú)解，當(dāng)然更沒(méi)有最優(yōu)解，如圖所示。 1x2xo12221xx22）有無(wú)窮多最優(yōu)解3）有無(wú)界解4）無(wú)可行解幾點(diǎn)啟示：幾點(diǎn)啟示： 1）線性規(guī)劃若存在可行解，則其的可行域是若干個(gè)半平面）線性規(guī)劃若存在可行解，則其的可行域是若干個(gè)半平面

23、的相交形成的一個(gè)多面凸集（可能是空集的相交形成的一個(gè)多面凸集（可能是空集）。）。 2）線性規(guī)劃問(wèn)題若存在最優(yōu)解，則其最優(yōu)解（或最優(yōu)解）線性規(guī)劃問(wèn)題若存在最優(yōu)解，則其最優(yōu)解（或最優(yōu)解之一）總可以之一）總可以在可行域的某個(gè)頂點(diǎn)上達(dá)到在可行域的某個(gè)頂點(diǎn)上達(dá)到。2.2單純形法單純形法 單純形法是解決線性規(guī)劃問(wèn)題的基本方法。單純形法是解決線性規(guī)劃問(wèn)題的基本方法。2.2.1線性規(guī)劃的解的基本概念線性規(guī)劃的解的基本概念 設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型為設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型為 ）（2) 1 (max0XbAXCXz 其中其中A是是mn矩陣矩陣( (n m ，？，？),),設(shè)設(shè)A A的秩的秩r( (A)=)=m，亦即，亦即A

24、中至少有中至少有一個(gè)滿秩一個(gè)滿秩mm子矩陣。子矩陣。 解解 滿足系統(tǒng)約束條件（滿足系統(tǒng)約束條件（1 1）的決策向量）的決策向量X=(=(x1,x2,xn) )T稱稱為線性規(guī)劃的解為線性規(guī)劃的解。 可行解可行解 滿足符號(hào)約束條件（滿足符號(hào)約束條件（2 2）的解）的解X=(=(x1,x2,xn) )T稱為稱為線性規(guī)劃的線性規(guī)劃的可行解可行解。 2.2單純形法單純形法可行域可行域全體可行解的集合稱為線性規(guī)劃的全體可行解的集合稱為線性規(guī)劃的可行域可行域，一般，一般記作記作D=X|AX=b,X0。最優(yōu)解最優(yōu)解使目標(biāo)函數(shù)達(dá)到最小值（或最大值）的可行解使目標(biāo)函數(shù)達(dá)到最小值（或最大值）的可行解X*=(=(x1

25、*,x2*,xn*) )T稱為線性規(guī)劃的最優(yōu)解。稱為線性規(guī)劃的最優(yōu)解。 最優(yōu)值最優(yōu)值 最優(yōu)解的目標(biāo)函數(shù)值稱為線性規(guī)劃的最優(yōu)值。最優(yōu)解的目標(biāo)函數(shù)值稱為線性規(guī)劃的最優(yōu)值。 基基若若B為為A的滿秩子方陣，即的滿秩子方陣，即r(B)=m,則，稱則，稱B是線性規(guī)劃是線性規(guī)劃問(wèn)題的一個(gè)基。也就是說(shuō)，矩陣問(wèn)題的一個(gè)基。也就是說(shuō)，矩陣B是由是由A的的m個(gè)線性無(wú)關(guān)列向量個(gè)線性無(wú)關(guān)列向量所構(gòu)成，不妨設(shè)為：所構(gòu)成，不妨設(shè)為：mmmmmmmPPPaaaaaaaaaB21212222111211稱稱Pj( (j=1,2,m) )為為基向量基向量。 2.2單純形法單純形法 基變量、非基變量基變量、非基變量 與其基向量與其

26、基向量Pj( (j=1,2,m) )相對(duì)應(yīng)的變相對(duì)應(yīng)的變量量xj( (j=1,2,m) )為為基變量基變量，其他決策變量稱為，其他決策變量稱為非基變量非基變量。 基解基解 記基變量為記基變量為XB=(=(x1,x2,xn) )T ，非基變量為，非基變量為XN= =( (xm+1,xm+2,xn) )T ，稱滿足方程，稱滿足方程(1)(1)的解的解X（XB，XN）為）為L(zhǎng)PLP的基解，其中的基解，其中XB=B-1-1b，XN= =0。 基可行解基可行解 若基解滿足非負(fù)約若基解滿足非負(fù)約束（束（2 2），即），即XB=B-1-1b0 ，則稱該，則稱該其解為基可行解。稱相應(yīng)的基其解為基可行解。稱相應(yīng)

27、的基B為為可行基可行基。 解基解可行解基可行解【例例2.8】求出下面線性規(guī)劃的所有基解求出下面線性規(guī)劃的所有基解,并指出那些是基可行解并指出那些是基可行解.2.2單純形法單純形法04102532max515242131321xxxxxxxxxxxz解解 其系數(shù)矩陣為：其系數(shù)矩陣為： 521,.,100100102100101PPPA易知，其易知，其3 3階子方陣共有階子方陣共有1010個(gè)?？梢则?yàn)證：其中有個(gè)。可以驗(yàn)證：其中有2 2個(gè)子方個(gè)子方陣為奇異的即：陣為奇異的即：0,00010101194319BPPPB0,1010120001054210BPPPB而另外的而另外的8 8個(gè)個(gè)3 3階子方

28、陣均為非奇異的，即該階子方陣均為非奇異的，即該LPLP問(wèn)題共有問(wèn)題共有8 8個(gè)個(gè)基?；?。2.2單純形法單純形法分別將這分別將這8 8個(gè)基對(duì)應(yīng)的基解求出，例如：個(gè)基對(duì)應(yīng)的基解求出，例如： ,1000100015431PPPB則基變量為則基變量為x3,x4,x5，令非基變量，令非基變量x1=x2=0，代入原約束方程，代入原約束方程，x1x2x3x4x5是否基可行解005104是04520是50054是05501否100504否55/2003/2是54030否24300是04102532max515242131321xxxxxxxxxxxz立即可得基解立即可得基解 X1 1（0,0,5,10,4)T

29、。類似地求出其它基解，見下表類似地求出其它基解，見下表2.2單純形法單純形法2.2.2單純形法的基本原理單純形法的基本原理 基本概念基本概念凸集凸集設(shè)設(shè)D是是n維空間的一個(gè)點(diǎn)集，若對(duì)任意兩點(diǎn)維空間的一個(gè)點(diǎn)集，若對(duì)任意兩點(diǎn)均有均有；則稱；則稱D為凸集。為凸集。 ,) 1 (DxDx)2( 1 , 0,)1 ()2() 1 (Dxx幾何意義：幾何意義：凸集凸集D中的任意兩點(diǎn)間的連線仍然在中的任意兩點(diǎn)間的連線仍然在D中。中。頂點(diǎn)頂點(diǎn)設(shè)設(shè)D是凸集，若是凸集，若且且x 不能用不能用D中不同的兩點(diǎn)中不同的兩點(diǎn)的凸組合表示為的凸組合表示為，則稱，則稱x為為D的的一個(gè)頂點(diǎn)（或極點(diǎn)）。一個(gè)頂點(diǎn)（或極點(diǎn)）。 Dx

30、)2()1(,xx) 10( ,)1 ()2() 1 (DxxxS1S2S32.2單純形法單純形法 基本定理基本定理定理定理2.1若線性規(guī)劃問(wèn)題存在可行域，則可行域是凸集。若線性規(guī)劃問(wèn)題存在可行域，則可行域是凸集。定理定理2.2線性規(guī)劃可行域線性規(guī)劃可行域D中的點(diǎn)中的點(diǎn)X是頂點(diǎn)的充要條件為是頂點(diǎn)的充要條件為X是基可行解。是基可行解。定理定理2.3若線性規(guī)劃有最優(yōu)解，則最優(yōu)解一定可以在可行若線性規(guī)劃有最優(yōu)解，則最優(yōu)解一定可以在可行域的頂點(diǎn)上得到。域的頂點(diǎn)上得到。 引理引理線性規(guī)劃可行解線性規(guī)劃可行解X（x1,x2, xn ）為基可行解的充分）為基可行解的充分必要條件為必要條件為X的正分量對(duì)應(yīng)的系

31、數(shù)列向量線性無(wú)關(guān)。的正分量對(duì)應(yīng)的系數(shù)列向量線性無(wú)關(guān)。 11221 121 22112 122 22221222m ax ()(,)(,). .(,)0,1, 2,.m in nnnnnnmmm nnmjzc xc xc xaxaxaxbaxaxaxbs taxaxaxbxjn 或0XbAX),(. .)max(mintsCXz或njxxtsCXzjjnj, 2, 10),(. .min)max(1bPj或0XbAXCXzmax 線性規(guī)劃的線性規(guī)劃的標(biāo)準(zhǔn)型的特點(diǎn)標(biāo)準(zhǔn)型的特點(diǎn)：目標(biāo)函目標(biāo)函數(shù)是最大化；數(shù)是最大化；b0；約束條件均由等式約束條件均由等式組成；組成；決策變量均為非負(fù)。決策變量均為非負(fù)。

32、 njxbxaxaxabxaxaxabxaxaxatsxcxcxczjmnmnmmnnnnnn,2, 1,0.max2211222221211121211122112.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法2.1.4線性規(guī)劃的圖解法線性規(guī)劃的圖解法 對(duì)于只有兩個(gè)變量的線性規(guī)劃問(wèn)題，可以直接使用圖解法對(duì)于只有兩個(gè)變量的線性規(guī)劃問(wèn)題，可以直接使用圖解法求解。圖解法簡(jiǎn)單直觀，對(duì)一般線性規(guī)劃問(wèn)題的求解富有啟發(fā)求解。圖解法簡(jiǎn)單直觀，對(duì)一般線性規(guī)劃問(wèn)題的求解富有啟發(fā)作用。作用。 圖解法可分三步進(jìn)行：圖解法可分三步進(jìn)行：1）在平面上建立直角坐標(biāo)系；在平面上建立直角坐標(biāo)系；2）根據(jù)約束條件畫出相應(yīng)的半平面

33、，由這些半平面共同確根據(jù)約束條件畫出相應(yīng)的半平面，由這些半平面共同確定的區(qū)域即為定的區(qū)域即為可行域可行域；3）畫出目標(biāo)函數(shù)的等值線，然后沿目標(biāo)函數(shù)要求的方向平畫出目標(biāo)函數(shù)的等值線，然后沿目標(biāo)函數(shù)要求的方向平移至與可行域邊界相切的點(diǎn)，該點(diǎn)就是最優(yōu)解，相應(yīng)的坐標(biāo)即為移至與可行域邊界相切的點(diǎn)，該點(diǎn)就是最優(yōu)解，相應(yīng)的坐標(biāo)即為最優(yōu)解。最優(yōu)解。2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 【例例2.42.4】 求解線性規(guī)劃問(wèn)題求解線性規(guī)劃問(wèn)題 0, 02426023302. .5040max212212121xxxxxxxtsxxz解解應(yīng)用圖解法求解線性規(guī)劃，應(yīng)用圖解法求解線性規(guī)劃，分下面三步求解。分下

34、面三步求解。1）建立直角坐標(biāo)系）建立直角坐標(biāo)系1x2xo2）確定可行域）確定可行域令令3個(gè)約束條件為等式，得到個(gè)約束條件為等式，得到3條直線，畫條直線，畫出第一象限的三個(gè)不等式區(qū)域，他們的交集出第一象限的三個(gè)不等式區(qū)域，他們的交集就是可行域，亦即區(qū)域就是可行域，亦即區(qū)域OABCD，其內(nèi)部及，其內(nèi)部及邊界上的每一個(gè)點(diǎn)都是線性規(guī)劃的解。邊界上的每一個(gè)點(diǎn)都是線性規(guī)劃的解。301530221 xx3020602321 xx122422xABCD3）確定最優(yōu)解）確定最優(yōu)解目標(biāo)函數(shù)的等值線目標(biāo)函數(shù)的等值線z=40 x1+50 x2( (z z取定某取定某一個(gè)常值一個(gè)常值) ) 。沿著函數(shù)的梯度方向移動(dòng)，。

35、沿著函數(shù)的梯度方向移動(dòng)，函數(shù)值會(huì)增大，當(dāng)移動(dòng)到點(diǎn)頂點(diǎn)函數(shù)值會(huì)增大，當(dāng)移動(dòng)到點(diǎn)頂點(diǎn)( (15,15/2) ) ，再繼續(xù)移動(dòng)就離開區(qū)域了。于是點(diǎn)再繼續(xù)移動(dòng)就離開區(qū)域了。于是點(diǎn)C就就是最優(yōu)解，最優(yōu)值為是最優(yōu)解，最優(yōu)值為z=40z=4015+5015+5015/2=97515/2=975 2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 【例例2.52.5】 求解線性規(guī)劃問(wèn)題求解線性規(guī)劃問(wèn)題 0, 02426023302. .8040max212212121xxxxxxxtsxxz解解該題將例該題將例2.4中的目標(biāo)中的目標(biāo)函數(shù)變?yōu)楹瘮?shù)變?yōu)閦=40 x1+80

36、 x2,可行域不可行域不變。變。由于目標(biāo)函數(shù)等直線由于目標(biāo)函數(shù)等直線z=40 x1+80 x2與直線與直線x1+2x2=30平行，平行， 當(dāng)目標(biāo)函數(shù)的等值線與直線當(dāng)目標(biāo)函數(shù)的等值線與直線x1+2x2=30重合時(shí)，重合時(shí)，目標(biāo)函數(shù)目標(biāo)函數(shù)z=40 x1+80 x2z=40 x1+80 x2達(dá)到最大值達(dá)到最大值12001200。于是線段。于是線段BCBC上的每一個(gè)點(diǎn)均為上的每一個(gè)點(diǎn)均為該問(wèn)題的最優(yōu)解。該問(wèn)題的最優(yōu)解。 1x2xo301530221 xx3020602321 xx2422xABCD2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 【例例2.62.6】 求解線性規(guī)劃問(wèn)題求解線性規(guī)劃問(wèn)題

37、0,2282. .42max21212121xxxxxxtsxxz1x2xo88221 xx42221xx2解解 由于可行域無(wú)界由于可行域無(wú)界, , 目標(biāo)函目標(biāo)函數(shù)數(shù)z=2x1+4x2z=2x1+4x2沿著它的法線方沿著它的法線方向向(2,4)(2,4)移動(dòng)，移動(dòng)可以無(wú)限移動(dòng)，移動(dòng)可以無(wú)限制下去，而目標(biāo)函數(shù)值一直制下去，而目標(biāo)函數(shù)值一直增加。增加。 所以該線性規(guī)劃問(wèn)所以該線性規(guī)劃問(wèn)題無(wú)有限最優(yōu)解，有題無(wú)有限最優(yōu)解，有無(wú)界解無(wú)界解。2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 【例例2.72.7】 求解線性規(guī)劃問(wèn)題求解線性規(guī)劃問(wèn)題 0,22. .24max212121xxxxtsxxz 解解

38、約束條件互不相容，沒(méi)有約束條件互不相容，沒(méi)有公共交點(diǎn)，可行域是一個(gè)空集，不存在滿足條件的公共交點(diǎn)，可行域是一個(gè)空集，不存在滿足條件的解，說(shuō)明線性規(guī)劃問(wèn)題無(wú)解，當(dāng)然更沒(méi)有最優(yōu)解，如圖所示。解，說(shuō)明線性規(guī)劃問(wèn)題無(wú)解，當(dāng)然更沒(méi)有最優(yōu)解，如圖所示。 1x2xo12221xx22）有無(wú)窮多最優(yōu)解3）有無(wú)界解4）無(wú)可行解幾點(diǎn)啟示：幾點(diǎn)啟示： 1）線性規(guī)劃若存在可行解，則其的可行域是若干個(gè)半平面）線性規(guī)劃若存在可行解，則其的可行域是若干個(gè)半平面的相交形成的一個(gè)多面凸集（可能是空集的相交形成的一個(gè)多面凸集（可能是空集）。）。 2）線性規(guī)劃問(wèn)題若存在最優(yōu)解，則其最優(yōu)解（或最優(yōu)解）線性規(guī)劃問(wèn)題若存在最優(yōu)解，則其最

39、優(yōu)解（或最優(yōu)解之一）總可以之一）總可以在可行域的某個(gè)頂點(diǎn)上達(dá)到在可行域的某個(gè)頂點(diǎn)上達(dá)到。2.2單純形法單純形法 單純形法是解決線性規(guī)劃問(wèn)題的基本方法。單純形法是解決線性規(guī)劃問(wèn)題的基本方法。2.2.1線性規(guī)劃的解的基本概念線性規(guī)劃的解的基本概念 設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型為設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型為 ）（2) 1 (max0XbAXCXz 其中其中A是是mn矩陣矩陣( (n m ，？，？),),設(shè)設(shè)A A的秩的秩r( (A)=)=m，亦即，亦即A中至少有中至少有一個(gè)滿秩一個(gè)滿秩mm子矩陣。子矩陣。 解解 滿足系統(tǒng)約束條件（滿足系統(tǒng)約束條件（1 1）的決策向量）的決策向量X=(=(x1,x2,xn) )T稱稱為

40、線性規(guī)劃的解為線性規(guī)劃的解。 可行解可行解 滿足符號(hào)約束條件（滿足符號(hào)約束條件（2 2）的解）的解X=(=(x1,x2,xn) )T稱為稱為線性規(guī)劃的線性規(guī)劃的可行解可行解。 2.2單純形法單純形法可行域可行域全體可行解的集合稱為線性規(guī)劃的全體可行解的集合稱為線性規(guī)劃的可行域可行域，一般，一般記作記作D=X|AX=b,X0。最優(yōu)解最優(yōu)解使目標(biāo)函數(shù)達(dá)到最小值（或最大值）的可行解使目標(biāo)函數(shù)達(dá)到最小值（或最大值）的可行解X*=(=(x1*,x2*,xn*) )T稱為線性規(guī)劃的最優(yōu)解。稱為線性規(guī)劃的最優(yōu)解。 最優(yōu)值最優(yōu)值 最優(yōu)解的目標(biāo)函數(shù)值稱為線性規(guī)劃的最優(yōu)值。最優(yōu)解的目標(biāo)函數(shù)值稱為線性規(guī)劃的最優(yōu)值。

41、 基基若若B為為A的滿秩子方陣，即的滿秩子方陣，即r(B)=m,則，稱則，稱B是線性規(guī)劃是線性規(guī)劃問(wèn)題的一個(gè)基。也就是說(shuō)，矩陣問(wèn)題的一個(gè)基。也就是說(shuō)，矩陣B是由是由A的的m個(gè)線性無(wú)關(guān)列向量個(gè)線性無(wú)關(guān)列向量所構(gòu)成，不妨設(shè)為：所構(gòu)成，不妨設(shè)為：mmmmmmmPPPaaaaaaaaaB21212222111211稱稱Pj( (j=1,2,m) )為為基向量基向量。 2.2單純形法單純形法 基變量、非基變量基變量、非基變量 與其基向量與其基向量Pj( (j=1,2,m) )相對(duì)應(yīng)的變相對(duì)應(yīng)的變量量xj( (j=1,2,m) )為為基變量基變量，其他決策變量稱為，其他決策變量稱為非基變量非基變量。 基解

42、基解 記基變量為記基變量為XB=(=(x1,x2,xn) )T ，非基變量為，非基變量為XN= =( (xm+1,xm+2,xn) )T ，稱滿足方程，稱滿足方程(1)(1)的解的解X（XB，XN）為）為L(zhǎng)PLP的基解，其中的基解，其中XB=B-1-1b，XN= =0。 基可行解基可行解 若基解滿足非負(fù)約若基解滿足非負(fù)約束（束（2 2），即），即XB=B-1-1b0 ，則稱該，則稱該其解為基可行解。稱相應(yīng)的基其解為基可行解。稱相應(yīng)的基B為為可行基可行基。 解基解可行解基可行解【例例2.8】求出下面線性規(guī)劃的所有基解求出下面線性規(guī)劃的所有基解,并指出那些是基可行解并指出那些是基可行解.2.2單純

43、形法單純形法04102532max515242131321xxxxxxxxxxxz解解 其系數(shù)矩陣為：其系數(shù)矩陣為： 521,.,100100102100101PPPA易知，其易知，其3 3階子方陣共有階子方陣共有1010個(gè)。可以驗(yàn)證：其中有個(gè)。可以驗(yàn)證：其中有2 2個(gè)子方個(gè)子方陣為奇異的即：陣為奇異的即：0,00010101194319BPPPB0,1010120001054210BPPPB而另外的而另外的8 8個(gè)個(gè)3 3階子方陣均為非奇異的，即該階子方陣均為非奇異的，即該LPLP問(wèn)題共有問(wèn)題共有8 8個(gè)個(gè)基。基。2.2單純形法單純形法分別將這分別將這8 8個(gè)基對(duì)應(yīng)的基解求出，例如：個(gè)基對(duì)應(yīng)

44、的基解求出，例如： ,1000100015431PPPB則基變量為則基變量為x3,x4,x5，令非基變量，令非基變量x1=x2=0，代入原約束方程，代入原約束方程，x1x2x3x4x5是否基可行解005104是04520是50054是05501否100504否55/2003/2是54030否24300是04102532max515242131321xxxxxxxxxxxz立即可得基解立即可得基解 X1 1（0,0,5,10,4)T。類似地求出其它基解，見下表類似地求出其它基解，見下表2.2單純形法單純形法2.2.2單純形法的基本原理單純形法的基本原理 基本概念基本概念凸集凸集設(shè)設(shè)D是是n維空間

45、的一個(gè)點(diǎn)集，若對(duì)任意兩點(diǎn)維空間的一個(gè)點(diǎn)集，若對(duì)任意兩點(diǎn)均有均有；則稱；則稱D為凸集。為凸集。 ,) 1 (DxDx)2( 1 , 0,)1 ()2() 1 (Dxx幾何意義：幾何意義：凸集凸集D中的任意兩點(diǎn)間的連線仍然在中的任意兩點(diǎn)間的連線仍然在D中。中。頂點(diǎn)頂點(diǎn)設(shè)設(shè)D是凸集，若是凸集，若且且x 不能用不能用D中不同的兩點(diǎn)中不同的兩點(diǎn)的凸組合表示為的凸組合表示為，則稱，則稱x為為D的的一個(gè)頂點(diǎn)（或極點(diǎn)）。一個(gè)頂點(diǎn)（或極點(diǎn)）。 Dx)2()1(,xx) 10( ,)1 ()2() 1 (DxxxS1S2S32.2單純形法單純形法 基本定理基本定理定理定理2.1若線性規(guī)劃問(wèn)題存在可行域，則可行域是

46、凸集。若線性規(guī)劃問(wèn)題存在可行域，則可行域是凸集。定理定理2.2線性規(guī)劃可行域線性規(guī)劃可行域D中的點(diǎn)中的點(diǎn)X是頂點(diǎn)的充要條件為是頂點(diǎn)的充要條件為X是基可行解。是基可行解。定理定理2.3若線性規(guī)劃有最優(yōu)解，則最優(yōu)解一定可以在可行若線性規(guī)劃有最優(yōu)解，則最優(yōu)解一定可以在可行域的頂點(diǎn)上得到。域的頂點(diǎn)上得到。 引理引理線性規(guī)劃可行解線性規(guī)劃可行解X（x1,x2, xn ）為基可行解的充分）為基可行解的充分必要條件為必要條件為X的正分量對(duì)應(yīng)的系數(shù)列向量線性無(wú)關(guān)。的正分量對(duì)應(yīng)的系數(shù)列向量線性無(wú)關(guān)。 線性規(guī)劃的線性規(guī)劃的解的四種可能情況解的四種可能情況：有唯一最優(yōu)解；有無(wú)窮多最優(yōu)解；有唯一最優(yōu)解；有無(wú)窮多最優(yōu)解

47、；有無(wú)界解；無(wú)可行解有無(wú)界解；無(wú)可行解基：基：系數(shù)矩陣系數(shù)矩陣A A的的m m階非奇異子方陣階非奇異子方陣基解：基解：令非基變量為令非基變量為0 0，求解由基變量構(gòu)成的線性方，求解由基變量構(gòu)成的線性方程組所得的解，該解與非基變量一起構(gòu)成的約束方程程組所得的解，該解與非基變量一起構(gòu)成的約束方程組的解組的解基可行解：基可行解：可行的基解，滿足變量非負(fù)約束的基解?？尚械幕?，滿足變量非負(fù)約束的基解。幾個(gè)幾個(gè)基本定理基本定理定理定理2.1若線性規(guī)劃問(wèn)題存在可行域，則可行域是凸集。若線性規(guī)劃問(wèn)題存在可行域，則可行域是凸集。定理定理2.2線性規(guī)劃可行域線性規(guī)劃可行域D中頂點(diǎn)的對(duì)應(yīng)于中頂點(diǎn)的對(duì)應(yīng)于LP的基可

48、行解。的基可行解。定理定理2.3若線性規(guī)劃有最優(yōu)解，則最優(yōu)解一定可以在可行若線性規(guī)劃有最優(yōu)解，則最優(yōu)解一定可以在可行域的頂點(diǎn)上得到。域的頂點(diǎn)上得到。 引理引理線性規(guī)劃可行解線性規(guī)劃可行解X（x1,x2,xn）為基可行解的充分）為基可行解的充分必要條件為必要條件為X的的正分量正分量對(duì)應(yīng)的系數(shù)列向量對(duì)應(yīng)的系數(shù)列向量線性無(wú)關(guān)線性無(wú)關(guān)。TmxxxX)0.0,0,.,(002001只考察基可行解。對(duì)于某一個(gè)基可行解，只需考察與其相鄰的基可行解， 看是否比它們均優(yōu)。（圖示說(shuō)明）設(shè)有基可行解TllmxxxxxX)0,.,0 , 0 ,., 0,.,(1111112111則它們是相鄰的。)2(,.2 , 1,

49、 0) 1 (max11njxxaxczjnjjijnjjjb2.2.4 2.2.4 單純形法的迭代原理單純形法的迭代原理單純形法的基本思想：?jiǎn)渭冃畏ǖ幕舅枷耄嚎疾炜疾霯PLP的基可行解，判斷其是否的基可行解，判斷其是否為最優(yōu)解，若不是，則轉(zhuǎn)到與其相鄰的可使目標(biāo)函數(shù)增為最優(yōu)解，若不是，則轉(zhuǎn)到與其相鄰的可使目標(biāo)函數(shù)增大的基可行解，直到找到最優(yōu)解。大的基可行解，直到找到最優(yōu)解。1.1.初始基可行解的確定初始基可行解的確定考察標(biāo)準(zhǔn)形的考察標(biāo)準(zhǔn)形的LPLP問(wèn)題：?jiǎn)栴}：通常在方程（通常在方程（1 1）的系數(shù)）的系數(shù)矩陣矩陣A A中，總存在中，總存在1 1個(gè)單位個(gè)單位矩陣，不妨設(shè)為：矩陣，不妨設(shè)為：10

50、0010001).,(21mPPPB則則x1 1, ,x2 2,xm m為基變量，而為基變量，而xm+1,xm+2,xn為非基變量，令為非基變量，令非基變量非基變量0 0，則很容易得到一個(gè)基可行解：（，則很容易得到一個(gè)基可行解：（？）TmTnbbbxxxX)0.0 , 0 ,.,(),.,(21212.2.從一個(gè)基可行解轉(zhuǎn)到相鄰的另一個(gè)基可行解從一個(gè)基可行解轉(zhuǎn)到相鄰的另一個(gè)基可行解 按單純形法的思想，找到一個(gè)基可行解后，進(jìn)行檢驗(yàn)，看按單純形法的思想，找到一個(gè)基可行解后，進(jìn)行檢驗(yàn)，看它是否為最優(yōu)解，用什么辦法呢？就是將它和與其相鄰的基可它是否為最優(yōu)解，用什么辦法呢？就是將它和與其相鄰的基可行解比

51、較，為此須找到與它相鄰的基可行解。行解比較，為此須找到與它相鄰的基可行解。定義：定義：如果兩個(gè)基可行解只有一個(gè)基變量不相同，則稱這兩個(gè)基如果兩個(gè)基可行解只有一個(gè)基變量不相同，則稱這兩個(gè)基可行解相鄰可行解相鄰設(shè)已得到一個(gè)基可行解為設(shè)已得到一個(gè)基可行解為將其代入約束方程（將其代入約束方程（1），則得到：），則得到：TmxxxX)0.0 , 0 ,.,(002010) 3(10miiixPb因?yàn)橐驗(yàn)镻1,P2,Pm線性無(wú)關(guān)（？），則其它系數(shù)列向量線性無(wú)關(guān)（？），則其它系數(shù)列向量Pj可由它可由它們線性表示為們線性表示為:miiijjPaP1或?qū)懗桑夯驅(qū)懗桑?4(01miiijjPaP將（將（4）兩端同

52、時(shí)乘以）兩端同時(shí)乘以0，則得到：，則得到：)5(0)(1miiijjPaP（3 3）+ +（5 5）整理后得到：）整理后得到：則得到了約束方程（則得到了約束方程（1）的另一個(gè)解。）的另一個(gè)解。取取則則X1的所有分量均的所有分量均0 0！這樣！這樣X(jué)1就是就是LPLP的一個(gè)的一個(gè)可行解可行解。j jTmjmjjaxaxaxX)0,.0 , 0.0 , 0 ,.,(02021011（6）系數(shù)矩陣為：）系數(shù)矩陣為：)6()(10bjmiiijiPPax)7(0|min00ljlijijiaxaax10000010100001000001, 1, 121mjjlljjljjaaaaaa容易看出，它是非

53、奇異的，所容易看出，它是非奇異的，所以以X1為基可行解。為基可行解。注意到注意到X0與與X1只有一個(gè)分量只有一個(gè)分量不同，則它們是不同，則它們是相鄰相鄰的基可的基可行解。行解。3.3.最優(yōu)性檢驗(yàn)和解的叛別最優(yōu)性檢驗(yàn)和解的叛別當(dāng)當(dāng)稱為稱為xj的檢驗(yàn)數(shù)。的檢驗(yàn)數(shù)。miiixcz100)8()()()(10110101miijijmimiijijiijmiijiiacczaccxccaxcz0)(1miijijacc時(shí)，就有時(shí)，就有01zz jjmiijijjzcacc1記記解的判別解的判別（1）若所有）若所有，則表明，則表明z0比各相鄰的基可行解均優(yōu)，則比各相鄰的基可行解均優(yōu)，則z0即為即為L(zhǎng)P的

54、最優(yōu)值，的最優(yōu)值，X0即為即為L(zhǎng)P的最優(yōu)解。的最優(yōu)解。0j（2）若所有）若所有，且有某個(gè)，且有某個(gè)j,同時(shí)可按同時(shí)可按規(guī)則找到規(guī)則找到00，則存在，則存在X1 1，也為最優(yōu)解，且，也為最優(yōu)解，且 而對(duì)于而對(duì)于X0 0和和X1的凸的凸組合組合X，有，有0j0j01zz 00010)1 ()1 (zzzXXCCXz即即X亦為亦為L(zhǎng)P的最優(yōu)解，此時(shí)的最優(yōu)解，此時(shí)LP有有無(wú)窮多無(wú)窮多最優(yōu)解最優(yōu)解（3）若有）若有且且，則由，則由知，對(duì)任意的知，對(duì)任意的0，均有均有 , ,即即X1 1為可行解，而為可行解，而z1 1可以無(wú)限增大?？梢詿o(wú)限增大。此此時(shí)，時(shí)，LP有有無(wú)界解無(wú)界解。0j0jPijiiaxx01

55、001ijiiaxx2 2）容易看出其一個(gè)基為：）容易看出其一個(gè)基為： 0,24261553. .002max43214213214321xxxxxxxxxxtsxxxxz4.單純形法求解LP問(wèn)題的步驟例2.10 求解LP問(wèn)題0,24261553.2max21212121xxxxxxtsxxzStep1 確定初始基可行解，列初始單純形表10260153A1001B則得到初始基可行解：則得到初始基可行解： 1）標(biāo)準(zhǔn)化TX)24,15, 0, 0(03 3）列初始單純形表）列初始單純形表 cj x1 x2 x3 x4 3 5 1 0 2 1 0 0 C B X B B-1b 0 x3 15 0 x

56、4 24 6 2 0 1 Step2檢驗(yàn)檢驗(yàn) cj x1 x2 x3 x4 3 5 1 0 2 1 0 0 C B X B B-1b 0 x3 15 0 x4 24 6 2 0 1 j 2 1 0 0 1)計(jì)算計(jì)算檢驗(yàn)數(shù)檢驗(yàn)數(shù)jjmiijijjzcacc12)解的判別解的判別Step3基可行解的轉(zhuǎn)換基可行解的轉(zhuǎn)換1）入基變量的確定）入基變量的確定 2）出基變量的確定）出基變量的確定 5 4 6 ljlijijiaxaax000|min3）列新單純形表）列新單純形表 0 x3 2 x1 j 4 1 1/3 0 1/6 0 1 1/4 -1/8 1 x2 3/4 2 x1 15/4 1 0 -1/

57、12 5/24 j 0 0 -1/12 -7/24 3 0 4 1 -1/2 Step4重復(fù)重復(fù)step2-step3 0 1/3 0 -1/3 3 / 4 12 4 jjmiijijjzcacc1（1）若所有）若所有，X0即為即為L(zhǎng)P的最優(yōu)解。的最優(yōu)解。0j（2）若所有）若所有，且有某個(gè)，且有某個(gè)j,同時(shí)可按同時(shí)可按規(guī)則找到規(guī)則找到00，0j0j此時(shí)此時(shí)LP有有無(wú)窮多無(wú)窮多最優(yōu)解最優(yōu)解（3）若有）若有且且，則，則LP有有無(wú)界解無(wú)界解。0j0jPStep3基可行解的轉(zhuǎn)換基可行解的轉(zhuǎn)換1）入基變量的確定）入基變量的確定2）出基變量的確定）出基變量的確定ljlijijiaxaax000|min3）

58、列新單純形表）列新單純形表Step4重復(fù)重復(fù)step2-step32.2單純形法單純形法【例例2.13】用單純形法求解線性規(guī)劃用單純形法求解線性規(guī)劃0,21024242max2121212121xxxxxxxxxxz解解將線性規(guī)劃標(biāo)準(zhǔn)化，得將線性規(guī)劃標(biāo)準(zhǔn)化，得0,21024200042max5432152142132154321xxxxxxxxxxxxxxxxxxxz容易看出，其初始基可行容易看出，其初始基可行解為：解為：TX)2 ,10, 4 , 0 , 0(02.2單純形法單純形法初始基單純形表為：初始基單純形表為： 2 4 0 0 0 2 5 4 4 0 -2 0 0 4 3 8 0 0

59、 0 -2 0 至此，所有非基變量的檢驗(yàn)數(shù)均至此，所有非基變量的檢驗(yàn)數(shù)均不大于不大于0，于是得到最優(yōu)解為：，于是得到最優(yōu)解為：TX)2/5 , 0 , 0 , 2/7 , 3(*20*z注意：注意：在最終單純形表中，在最終單純形表中，非基變量非基變量x3的檢驗(yàn)數(shù)的檢驗(yàn)數(shù)0，而，而它的系數(shù)列向量中有它的系數(shù)列向量中有00的系的系數(shù)，因此，迭代仍可繼續(xù)。數(shù)，因此，迭代仍可繼續(xù)。 0 14 10/30/3 0 0 0 -2 0 得到另一最優(yōu)解得到另一最優(yōu)解TX) , 0 , 0 , 3/10, 3/8 , 3/14(*120*1z2.2.4單純形法的進(jìn)一步討論（大單純形法的進(jìn)一步討論（大M法）法）【

60、例例2.14】用單純形法求解線性規(guī)劃用單純形法求解線性規(guī)劃) 1 (0,2314242max21212121xxxxxxxxz解解將線性規(guī)劃標(biāo)準(zhǔn)化，得將線性規(guī)劃標(biāo)準(zhǔn)化，得與前兩例不同，本例中不存在明顯的與前兩例不同，本例中不存在明顯的2階單位子方陣，則初始基可行解的階單位子方陣，則初始基可行解的確定成問(wèn)題了！確定成問(wèn)題了！0,2314242max432142132121xxxxxxxxxxxxz引入引入人工變量人工變量x50,0,構(gòu)造輔助構(gòu)造輔助LPLP問(wèn)題問(wèn)題)2(0,2314242max43215421321521xxxxxxxxxxxMxxxz這樣初始基可行解就很容易確定了。這樣初始基可