廣工管理運(yùn)籌學(xué)運(yùn)籌學(xué)緒論及

廣工管理運(yùn)籌學(xué)運(yùn)籌學(xué)緒論及第1頁(yè)/共113頁(yè)2緒論什么是運(yùn)籌學(xué)運(yùn)籌學(xué)研究的基本特征和基本方法運(yùn)籌學(xué)的主要分支運(yùn)籌學(xué)與管理科學(xué)第2頁(yè)/共113頁(yè)3什么是運(yùn)籌學(xué)（不同的定義）《大英百科全書》《中國(guó)大百科全書》《辭?！贰吨袊?guó)企業(yè)管理百科全書》第3頁(yè)/共113頁(yè)4《大英百科全書》的定義運(yùn)籌學(xué)是一門應(yīng)用于管理有組織系統(tǒng)的科學(xué)。運(yùn)籌學(xué)為掌管這類系統(tǒng)的人提供決策目標(biāo)和數(shù)量分析的工具。第4頁(yè)/共113頁(yè)5《中國(guó)大百科全書》的定義運(yùn)籌學(xué)用數(shù)學(xué)方法研究經(jīng)濟(jì)、民政和國(guó)防等部門在內(nèi)外的約束條件下合理分配人力、物力、財(cái)力等資源，是實(shí)際系統(tǒng)有效運(yùn)行的技術(shù)科學(xué)，它可以用來預(yù)測(cè)發(fā)展趨勢(shì)，制訂行動(dòng)規(guī)劃或優(yōu)選可行方案。第5頁(yè)/共113頁(yè)6《辭海》的定義運(yùn)籌學(xué)主要研究經(jīng)濟(jì)活動(dòng)與軍事活動(dòng)中能用數(shù)量來表達(dá)有關(guān)運(yùn)用、籌劃與管理方面的問題，它根據(jù)問題的要求，通過數(shù)學(xué)的分析與運(yùn)算，作出綜合性的合理安排，以達(dá)到經(jīng)濟(jì)有效地使用人力物力。第6頁(yè)/共113頁(yè)7《中國(guó)企業(yè)管理百科全書》的定義運(yùn)籌學(xué)應(yīng)用分析、實(shí)驗(yàn)、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中人財(cái)物等有限資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。第7頁(yè)/共113頁(yè)8英國(guó)——Operationalresearch美國(guó)——Operationsresearch夫運(yùn)籌帷幄之中，決勝千里之外?！酚淉R王賽馬丁渭修宮二戰(zhàn)時(shí)英國(guó)的防空雷達(dá)系統(tǒng)第8頁(yè)/共113頁(yè)9運(yùn)籌學(xué)的發(fā)展大致可分三個(gè)階段:運(yùn)籌學(xué)誕生的三個(gè)來源：軍事、管理和經(jīng)濟(jì)1945---1950年代,創(chuàng)建時(shí)期;1950年代,成長(zhǎng)時(shí)期;1960年代至今,普及和發(fā)展時(shí)期.第9頁(yè)/共113頁(yè)10運(yùn)籌學(xué)的基本特征系統(tǒng)的整體觀念多學(xué)科的綜合應(yīng)用模型技術(shù)第10頁(yè)/共113頁(yè)11運(yùn)籌學(xué)能夠?qū)?jīng)濟(jì)管理系統(tǒng)中的人力、物力、財(cái)力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。通常以最優(yōu)、最佳等作為決策目標(biāo)，避開最劣的方案。第11頁(yè)/共113頁(yè)12運(yùn)籌學(xué)的基本方法

——模型化的方法應(yīng)用步驟：分析與表述問題建立模型求解模型與優(yōu)化方案測(cè)試模型及對(duì)模型進(jìn)行必要的修正建立對(duì)解的有效控制方案的實(shí)施第12頁(yè)/共113頁(yè)13決策過程（問題解決的過程）：1）認(rèn)清問題；2）找出一些可供選擇的方案；3）確定目標(biāo)或評(píng)估方案的標(biāo)準(zhǔn)；4）評(píng)估各個(gè)方案：解的檢驗(yàn)、靈敏性分析等；5）選出一個(gè)最優(yōu)的方案：決策；6）執(zhí)行此方案：回到實(shí)踐中；7）進(jìn)行后評(píng)估：考察問題是否得到完滿解決；

1）2）3）：形成問題；

4）5）：分析問題：定性分析與定量分析。構(gòu)成決策。

第13頁(yè)/共113頁(yè)14運(yùn)籌學(xué)的主要分支線性規(guī)劃(linearprogramming)非線性規(guī)劃(nonlinearprogramming)動(dòng)態(tài)規(guī)劃(dynamicprogramming)圖與網(wǎng)絡(luò)分析(graphtheoryandnetworkanalysis)存貯論(inventorytheory)排隊(duì)論(queueingtheory)對(duì)策論(gametheory)決策論(decisiontheory)第14頁(yè)/共113頁(yè)15第四節(jié)運(yùn)籌學(xué)與管理科學(xué)國(guó)際上目前通行的說法：“運(yùn)籌學(xué)”與“管理科學(xué)(managementsciences)”在許多場(chǎng)合實(shí)際是指同一學(xué)科，不過前者強(qiáng)調(diào)方法而后者強(qiáng)調(diào)應(yīng)用。因此運(yùn)籌學(xué)是現(xiàn)代科學(xué)管理的基礎(chǔ)，從而在管理中有非常廣泛的應(yīng)用。第15頁(yè)/共113頁(yè)16生產(chǎn)計(jì)劃：生產(chǎn)作業(yè)的計(jì)劃、日程表的編排、合理下料、配料問題、物料管理等，追求利潤(rùn)最大化和成本最小化庫(kù)存管理：多種物資庫(kù)存量的管理，庫(kù)存方式、庫(kù)存量等運(yùn)輸問題：確定最小成本的運(yùn)輸線路、物資的調(diào)撥、運(yùn)輸工具的調(diào)度以及建廠地址的選擇等人事管理：對(duì)人員的需求和使用的預(yù)測(cè)，確定人員編制、人員合理分配，建立人才評(píng)價(jià)體系等市場(chǎng)營(yíng)銷：廣告預(yù)算、媒介選擇、定價(jià)、產(chǎn)品開發(fā)與銷售計(jì)劃制定等財(cái)務(wù)和會(huì)計(jì)：預(yù)測(cè)、貸款、成本分析、定價(jià)、證券管理、現(xiàn)金管理等***設(shè)備維修、更新，項(xiàng)目選擇、評(píng)價(jià)，工程優(yōu)化設(shè)計(jì)與管理等第16頁(yè)/共113頁(yè)17運(yùn)籌學(xué)方法使用情況(美1983)第17頁(yè)/共113頁(yè)18

運(yùn)籌學(xué)方法在中國(guó)使用情況

(隨機(jī)抽樣)第18頁(yè)/共113頁(yè)19運(yùn)籌學(xué)在國(guó)內(nèi)或國(guó)外的推廣應(yīng)用前景是非常廣闊的。工商企業(yè)對(duì)運(yùn)籌學(xué)應(yīng)用的需求是很大的。在工商企業(yè)推廣運(yùn)籌學(xué)方面有大量的工作要做。第19頁(yè)/共113頁(yè)20由國(guó)際運(yùn)籌與管理科學(xué)協(xié)會(huì)（INFORMS）和它的管理科學(xué)實(shí)踐學(xué)會(huì)（CollegeforthePracticeoftheManagementSciences）主持評(píng)獎(jiǎng)的負(fù)有盛名的弗蘭茨·厄德曼（FranyEdlman）獎(jiǎng)，就是為獎(jiǎng)勵(lì)優(yōu)秀的運(yùn)籌學(xué)在管理中的應(yīng)用的成就設(shè)立的，該獎(jiǎng)每年舉行一次，在對(duì)大量富有競(jìng)爭(zhēng)力的入圍者進(jìn)行艱苦的評(píng)審后，一般有六位優(yōu)勝者獲獎(jiǎng)。關(guān)于這些獲獎(jiǎng)項(xiàng)目的文章都在第二年發(fā)表在著名刊物Interface的第一期上，下面列表就是發(fā)表在Interface期刊的一些獲獎(jiǎng)項(xiàng)目。第20頁(yè)/共113頁(yè)21組織應(yīng)用Interface期刊號(hào)

每年節(jié)支（美元）聯(lián)合航空公司滿足乘客需求前提下,以最低成本進(jìn)行訂票及安排機(jī)場(chǎng)工作班次1-2/1986600萬Citgo石油優(yōu)化煉油程序及產(chǎn)品供應(yīng)、配送及營(yíng)銷1-2/19877000萬荷馬特發(fā)展公司（HomartDevelopmentCo.）優(yōu)化商業(yè)區(qū)和辦公樓銷售程序1-2/19874000萬AT&T優(yōu)化商業(yè)用戶的電話銷售中心選址1-2/19904.06億，更多銷售標(biāo)準(zhǔn)品牌公司控制成品庫(kù)存（制定最優(yōu)再訂購(gòu)點(diǎn)和訂購(gòu)量，確保安全庫(kù)存）12/1981380萬施樂公司通過戰(zhàn)略調(diào)整，縮短維修機(jī)器的反應(yīng)時(shí)間和改進(jìn)維修人員的生產(chǎn)率11/1975第二部分生產(chǎn)率提高50%以上寶潔公司重新設(shè)計(jì)北美生產(chǎn)和分銷系統(tǒng)以降低成本并加快了市場(chǎng)進(jìn)入速度1-2/19972億法國(guó)國(guó)家鐵路制定最優(yōu)鐵路時(shí)刻表并調(diào)整鐵路日運(yùn)營(yíng)量1-2/19981500萬更多年收入Delta航空公司進(jìn)行上千個(gè)國(guó)內(nèi)航線的飛機(jī)優(yōu)化配置來最大化利潤(rùn)1-2/19941億IBM重組全球供應(yīng)鏈，保持最小庫(kù)存的同時(shí)滿足客戶需求1-2/2000第一年7.5億Merit青銅制品公司安裝統(tǒng)計(jì)銷售預(yù)測(cè)和成品庫(kù)存管理系統(tǒng)，改進(jìn)客戶服務(wù)1-2/1993更優(yōu)的服務(wù)第21頁(yè)/共113頁(yè)22第二章線性規(guī)劃線性規(guī)劃問題及其數(shù)學(xué)模型圖解法單純形法原理單純形法計(jì)算步驟單純形法的進(jìn)一步討論應(yīng)用舉例第22頁(yè)/共113頁(yè)23第一節(jié)線性規(guī)劃及其數(shù)學(xué)模型問題的提出線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的標(biāo)準(zhǔn)形式第23頁(yè)/共113頁(yè)24例1

美佳公司計(jì)劃制造I、II兩種家電產(chǎn)品，已知各制造一件分別占用的設(shè)備A、B的臺(tái)時(shí)、調(diào)試時(shí)間、調(diào)試工序每天可用于這兩種家電的能力、各售出一件的獲利情況如下表所示。III每天可用能力設(shè)備A（h）設(shè)備B（h）調(diào)試工序（h）06152115245利潤(rùn)（元）21問該公司應(yīng)每天制造兩種家電各多少件，使獲取的利潤(rùn)最大。第24頁(yè)/共113頁(yè)25例2捷運(yùn)公司租借倉(cāng)庫(kù)的問題捷運(yùn)公司在下一年度的1-4月的4個(gè)月內(nèi)擬租用倉(cāng)庫(kù)堆放物資。已知各月份所需倉(cāng)庫(kù)面積如下表所示。倉(cāng)庫(kù)租借費(fèi)用隨合同期而定，期限越長(zhǎng)，折扣越大，具體數(shù)字見表。租借倉(cāng)庫(kù)的合同每月初都可辦理，每份合同具體規(guī)定租用面積和期限。因此，該廠可根據(jù)需要，在任何一個(gè)月初辦理租借合同。每次辦理時(shí)可簽一份合同，也可簽若干份租用面積和租期不同的合同。試確定該公司簽訂租借合同的最優(yōu)決策，目的是使所付租借費(fèi)用最小。第25頁(yè)/共113頁(yè)26月份1234所需倉(cāng)庫(kù)面積(100m2)15102012合同租借期限1個(gè)月2個(gè)月3個(gè)月4個(gè)月合同期內(nèi)的租費(fèi)(元/100m2)2800450060007300第26頁(yè)/共113頁(yè)27例1、例2的共同點(diǎn)

在現(xiàn)有各項(xiàng)資源條件的限制或約束下，如何確定方案，使預(yù)期目標(biāo)達(dá)到最優(yōu)。例1的資源限制：設(shè)備A、B與調(diào)試工序每天可用時(shí)數(shù)。目標(biāo)：總利潤(rùn)最大例2的資源約束：租期內(nèi)每月所需的倉(cāng)庫(kù)面積數(shù)。目標(biāo)：總租金最小第27頁(yè)/共113頁(yè)28線性規(guī)劃研究的問題大體上可歸為兩類：1、給出一定量的人力、物力、財(cái)力等資源，如何統(tǒng)籌規(guī)劃這些有限資源完成最大任務(wù)；2、對(duì)于給定的任務(wù)，如何運(yùn)籌規(guī)劃，合理安排，以最少資源來完成它。第28頁(yè)/共113頁(yè)29線性規(guī)劃要研究的兩類問題中都包含有限制或約束條件：第一類問題的約束條件是“給出一定量的人力、物力和財(cái)務(wù)等資源”；第二類問題是“給定的任務(wù)”。在線性規(guī)劃中，我們常要求這種約束條件可以用一組線性方程或線性不等式來描述。在約束滿足的條件下，所要達(dá)到的結(jié)果稱“目標(biāo)”，第一類問題的目標(biāo)是利用有限資源完成最大任務(wù)，第二類問題的目標(biāo)是要用最少資源完成給定任務(wù)。在線性規(guī)劃中，要求可以用一個(gè)線性函數(shù)來描述這種目標(biāo)，并稱這個(gè)線性函數(shù)為目標(biāo)函數(shù)。線性規(guī)劃研究的各種實(shí)際問題盡管約束條件與目標(biāo)不相同，但規(guī)劃的目的就是使這些資源發(fā)揮最大限度的作用，從而完成最多最大的任務(wù)。換句話說，也就是資源的最優(yōu)利用問題。用數(shù)學(xué)的方式描述，規(guī)劃的目的就是在給定的限制條件（或稱約束條件）下，求目標(biāo)函數(shù)的極值問題（包括極小值和極大值）。第29頁(yè)/共113頁(yè)30模型——數(shù)學(xué)規(guī)劃問題第30頁(yè)/共113頁(yè)31例1的數(shù)學(xué)模型第31頁(yè)/共113頁(yè)32第32頁(yè)/共113頁(yè)33例2的數(shù)學(xué)模型第33頁(yè)/共113頁(yè)34例1

穗羊公司要加工兩種產(chǎn)品I、II，需要使用兩種原材料及某專用生產(chǎn)設(shè)備等三種資源，分別記為A、B、C。生產(chǎn)這兩種產(chǎn)品的單位資源消耗、這些資源的每周可使用量及每單位產(chǎn)品可獲利潤(rùn)見下表：III每周可使用量A（千克）125B（噸）214C（百工時(shí)）439單位產(chǎn)品利潤(rùn)（萬元）32問該公司每周應(yīng)生產(chǎn)產(chǎn)品I與產(chǎn)品II各多少單位，才能使每周的獲利達(dá)到最大？第34頁(yè)/共113頁(yè)35根據(jù)問題所給數(shù)據(jù)，當(dāng)產(chǎn)品I、II每周的產(chǎn)量分別是x1和x2時(shí)，總利潤(rùn)為因此我們的目標(biāo)就是再考慮資源的限制:因此關(guān)于A原材料，我們有約束條件：關(guān)于B原材料，有約束條件：關(guān)于設(shè)備，有約束條件：此外產(chǎn)品I和II每周的產(chǎn)量不可能是負(fù)數(shù)，因此關(guān)于這兩個(gè)變量，還有約束：第35頁(yè)/共113頁(yè)36將上述數(shù)學(xué)表達(dá)式合起來，就得到這個(gè)問題的數(shù)學(xué)模型為：其中s.t.是英文詞組subjectto的縮寫，表示“受限制于”的意思，有時(shí)也約去不寫出來。例1中的問題常稱為生產(chǎn)計(jì)劃問題或產(chǎn)品組合（productmix）問題。第36頁(yè)/共113頁(yè)37例2

設(shè)有一批規(guī)格為10米長(zhǎng)的圓鋼筋，將它截成分別為3米，4米長(zhǎng)的預(yù)制構(gòu)件的短鋼筋各100根，問怎樣截取最省料。因?yàn)椋?0米長(zhǎng)的鋼筋截為3米或4米長(zhǎng)，共有三種截法：截法Ⅰ：3331米截法Ⅱ：3340米截法Ⅲ：4402米假設(shè)按截法Ⅰ，Ⅱ，Ⅲ各截取10米長(zhǎng)的鋼筋分別為x1,x2,x3根則可以獲得3米長(zhǎng)的短鋼筋的根數(shù)是4米長(zhǎng)短鋼筋的根數(shù)是按問題要求它們應(yīng)該不小于100根?？偣灿昧鲜且_(dá)到最省料的目的，就必須使總用料最小。第37頁(yè)/共113頁(yè)38例2的模型就是例2中的問題常稱為下料問題。第38頁(yè)/共113頁(yè)39模型的特征模型的三個(gè)要素（1）決策變量（2）目標(biāo)函數(shù)（3）約束條件線性規(guī)劃模型的特征（1）目標(biāo)函數(shù)是決策變量的線性函數(shù)（2）約束條件是含決策變量的線性等式或不等式第39頁(yè)/共113頁(yè)40線性規(guī)劃模型的一般形式第40頁(yè)/共113頁(yè)41線性規(guī)劃模型的一般形式（續(xù)1）決策變量：價(jià)值系數(shù)：資源常數(shù)：技術(shù)（工藝）系數(shù)：第41頁(yè)/共113頁(yè)42線性規(guī)劃模型的一般形式（續(xù)2）利用和號(hào)∑簡(jiǎn)化模型的表示第42頁(yè)/共113頁(yè)43線性規(guī)劃模型的一般形式（續(xù)3）向量形式：式中第43頁(yè)/共113頁(yè)44線性規(guī)劃模型的一般形式（續(xù)4）矩陣形式：其中第44頁(yè)/共113頁(yè)45線性規(guī)劃模型的一般形式（續(xù)5）注：決策變量通常是非負(fù)的，但從數(shù)學(xué)意義上決策變量可以取非正的值，或取任何實(shí)數(shù)。第45頁(yè)/共113頁(yè)46線性規(guī)劃問題的（模型）的標(biāo)準(zhǔn)形式第46頁(yè)/共113頁(yè)47標(biāo)準(zhǔn)形式的特征目標(biāo)函數(shù)為求最大值約束條件均為等式資源常數(shù)非負(fù)決策變量只能取非負(fù)值不具備上述所有特征的線性規(guī)劃問題稱為非標(biāo)準(zhǔn)形式的線性規(guī)劃問題第47頁(yè)/共113頁(yè)48化線性規(guī)劃問題為標(biāo)準(zhǔn)形式的方法（1）目標(biāo)函數(shù)為求最小值的，即將目標(biāo)函數(shù)用其相反數(shù)代替，得到新的目標(biāo)函數(shù)，即令則求原目標(biāo)函數(shù)的最小值問題等價(jià)于求新目標(biāo)函數(shù)的最大值問題第48頁(yè)/共113頁(yè)49化線性規(guī)劃問題為標(biāo)準(zhǔn)形式的方法（續(xù)1）（2）右端常數(shù)小于零，即將該約束條件兩端同乘（-1）（3）約束條件為不等式“”型，左端加上一個(gè)非負(fù)的松弛變量“”型，左端減去一個(gè)非負(fù)的剩余變量松弛變量和剩余變量在目標(biāo)函數(shù)中的系數(shù)為零第49頁(yè)/共113頁(yè)50化線性規(guī)劃問題為標(biāo)準(zhǔn)形式的方法（續(xù)2）（4）取值無約束的變量。用兩個(gè)非負(fù)變量的差表示該變量。（5）取非正值的變量。用其相反數(shù)代替該變量P15例3第50頁(yè)/共113頁(yè)51線性規(guī)劃問題要處理的內(nèi)容x1,x3右端常數(shù)不等式不等式最小化目標(biāo)處理后第51頁(yè)/共113頁(yè)52第二節(jié)圖解法有關(guān)概念滿足所有約束條件的一組決策變量x1,x2,…,xn稱為L(zhǎng)P問題的可行解所有可行解的集合稱為可行域使得目標(biāo)函數(shù)值達(dá)到最大的可行解稱為L(zhǎng)P問題的最優(yōu)解（對(duì)最大化問題而言）求解LP問題就是求出其最優(yōu)解第52頁(yè)/共113頁(yè)53

圖解法及其目的圖解法即通過平面作圖的方法求解線性規(guī)劃，適用于只含兩個(gè)決策變量的簡(jiǎn)單LP問題。圖解法的目的有二，一是利用它來說明LP問題求解的可能結(jié)局。二是在LP問題最優(yōu)解存在時(shí)，求出最優(yōu)解。采用圖解法時(shí)通常無須將LP問題化為標(biāo)準(zhǔn)形式第53頁(yè)/共113頁(yè)54圖解法步驟：在平面上建立直角坐標(biāo)系圖示約束條件，找出可行域圖示目標(biāo)函數(shù)尋找最優(yōu)解第54頁(yè)/共113頁(yè)55例1Maxz=2x1+x2s.t.5x2≤156x1+2x2

≤24

x1+x2≤5x1,x2≥0x2=33x1+x2=12x1+x2=5最優(yōu)解可行域x1x2第55頁(yè)/共113頁(yè)56線性規(guī)劃問題幾種可能的結(jié)局有唯一的最優(yōu)解有無窮多個(gè)最優(yōu)解無界解4.無解（無可行解）第56頁(yè)/共113頁(yè)57由圖解法得到的啟示揭示了求LP問題的解的可能情況若可行域非空，則必為凸集若LP問題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一是可行域的頂點(diǎn)LP問題的求解思路（單純形法）先找出可行域的任一頂點(diǎn)，計(jì)算該頂點(diǎn)處的目標(biāo)函數(shù)值；比較周圍相鄰頂點(diǎn)的目標(biāo)函數(shù)值是否比這個(gè)值大，如果為否，則該頂點(diǎn)為最優(yōu)解（或最優(yōu)解之一）對(duì)應(yīng)的點(diǎn)，否則轉(zhuǎn)到比這個(gè)點(diǎn)目標(biāo)函數(shù)值更大的頂點(diǎn)，重復(fù)上述過程，直到找出目標(biāo)函數(shù)值最大的頂點(diǎn)為止。第57頁(yè)/共113頁(yè)58第三節(jié)單純形法原理線性規(guī)劃解的基本概念考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問題可行解——滿足所有約束條件的解X=(x1,x2,…,xn)T,稱為L(zhǎng)P問題的可行解。所有可行解的集合稱為可行域。最優(yōu)解——使得目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解。LP問題的可行域是一個(gè)凸集。第58頁(yè)/共113頁(yè)59基——設(shè)A為約束方程組的m╳n階系數(shù)矩陣（通?？偧俣╪>m，且A的秩=m），若B是A的一個(gè)m╳m階的滿秩子矩陣，則稱B是LP問題的一個(gè)基。若B是LP問題的一個(gè)基，則它的每一個(gè)列向量稱為基向量，與基向量對(duì)應(yīng)的變量稱為基變量LP問題的基本概念（續(xù)1）第59頁(yè)/共113頁(yè)60秩的概念如果矩陣A中有一個(gè)r階子式Dr不等于零，而所有r+1階子式（如果存在的話）的值全等于零，則稱Dr為矩陣A的一個(gè)最高階非零子式，其階數(shù)r稱為矩陣A的秩。注：Dr為行列式r的值。第60頁(yè)/共113頁(yè)61LP問題的基本概念（續(xù)2）基解在約束方程組 中令所有的非基變量xm+1=xm+2=…=xn=0,則由于剩下的變量（基變量）構(gòu)成的方程組的系數(shù)行列式|B|≠0，因此約束方程組此時(shí)有唯一的解XB=（x1,x2,…,xm,0,…,0)T這個(gè)解稱為L(zhǎng)P問題的（對(duì)應(yīng)基B的）基解。很明顯，對(duì)應(yīng)著不同的基，LP問題有不同的基解。因此LP問題的基解不是唯一的，但總數(shù)不超過 此外基解不一定是可行解。第61頁(yè)/共113頁(yè)62LP問題的基本概念（續(xù)3）基可行解——滿足非負(fù)約束條件的基解稱為基可行解可行基——對(duì)應(yīng)著基可行解的基稱為可行基很明顯LP問題的基可行解是有限的。并且每一個(gè)基可行解對(duì)應(yīng)著可行域的一個(gè)頂點(diǎn)。第62頁(yè)/共113頁(yè)63找出下述線性規(guī)劃問題的全部基解，指出其中的基可行解，并確定最優(yōu)解。第63頁(yè)/共113頁(yè)64序號(hào)x1x2x3x4x5z是否基可行解10051045是20452017是35005410是40550-120否5100-50415否652.5001.517.5是7540-3022否82430019*是第64頁(yè)/共113頁(yè)65凸集及其頂點(diǎn)凸集——如果一個(gè)非空集合中任意兩點(diǎn)的連線段上所有點(diǎn)仍屬于該集合，則稱該集合為凸集。凸集的頂點(diǎn)——若凸集中的一個(gè)點(diǎn)不是任何另外兩點(diǎn)連線段上的點(diǎn)，則稱該點(diǎn)為這個(gè)凸集的頂點(diǎn)。凸集凸集不是凸集頂點(diǎn)第65頁(yè)/共113頁(yè)66幾個(gè)基本定理定理1

若LP問題存在可行解，則問題的可行域?yàn)橥辜ɡ?LP問題的基可行解對(duì)應(yīng)著LP問題可行域的頂點(diǎn)定理3

若LP問題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解第66頁(yè)/共113頁(yè)67單純形法迭代原理單純形法迭代步驟：找出一個(gè)基可行解是否為最優(yōu)解停止（依據(jù)：LP問題的最優(yōu)解若存在，則一定有一個(gè)基可行解為最優(yōu)解。）轉(zhuǎn)換到相鄰的基可行解，并使目標(biāo)函數(shù)增大開始YN第67頁(yè)/共113頁(yè)681.求初始基可行解基可行解求基解求解線性方程組求基B或基變量第68頁(yè)/共113頁(yè)69求基可行解需要考慮的問題是否便于計(jì)算目標(biāo)函數(shù)值是否便于判斷其目標(biāo)函數(shù)值是否為最大是否便于轉(zhuǎn)換到目標(biāo)函數(shù)值更大的相鄰基可行解第69頁(yè)/共113頁(yè)70初始基可行解通常都是從一種特殊的基可行解出發(fā)求解LP問題，這一特殊的基可行解稱為初始基可行解。初始基可行解對(duì)應(yīng)的基，也稱初始可行基，它具有特定的形式，它是單位矩陣或者由單位矩陣經(jīng)過交換列以后得到的矩陣。相應(yīng)的基變量稱為初始基變量，它是一組變量，具有特點(diǎn)：共有m個(gè)變量，恰好每個(gè)約束方程包含一個(gè)變量，且該變量的系數(shù)為1。第70頁(yè)/共113頁(yè)71已知初始基變量，求初始基可行解以例1為例說明求法。添加松弛變量后例1可標(biāo)準(zhǔn)化為其中x3,x4,x5為初始基變量，初始基可行解為第71頁(yè)/共113頁(yè)722.判別最優(yōu)性不難發(fā)現(xiàn)這時(shí)每個(gè)初始基變量取的值恰好就是包含這個(gè)變量的約束方程的右端常數(shù)值，非基變量取的值為零。將這個(gè)解代入到目標(biāo)函數(shù)，就可得到這個(gè)解對(duì)應(yīng)的目標(biāo)函數(shù)值。目標(biāo)函數(shù)目前的值為零，很明顯如果能使的變量x1或x2取正值的話，目標(biāo)函數(shù)的值還可以增加。所以目標(biāo)函數(shù)還未達(dá)到其最大值。一般地，若目標(biāo)函數(shù)已經(jīng)表示成了非基變量的函數(shù)，且其中非基變量的系數(shù)中還有正數(shù)，則目標(biāo)函數(shù)還可能增大。這時(shí)目標(biāo)函數(shù)中各變量的系數(shù)稱為檢驗(yàn)數(shù)。這時(shí)目標(biāo)函數(shù)的表達(dá)式為第72頁(yè)/共113頁(yè)733.旋轉(zhuǎn)若基可行解不是最優(yōu)解，則需要轉(zhuǎn)到一個(gè)相鄰的基可行解，并使得目標(biāo)函數(shù)值增加。所謂相鄰的基可行解是指兩個(gè)基可行解只有一個(gè)基變量不同而其它的基變量都相同。要從一個(gè)基可行解轉(zhuǎn)到與它相鄰的基可行解，意味著需要將一個(gè)非基變量變成基變量，而且將一個(gè)原來的基變量變?yōu)榉腔兞?，前者稱為換入變量，后者稱為換出變量。第73頁(yè)/共113頁(yè)74確定換入變量目的：新的基變量換入后，會(huì)使目標(biāo)函數(shù)值增大（通常還希望增加的越大越好）因此選擇在目標(biāo)函數(shù)中系數(shù)為正值的非基變量作為換入變量，通常取在目標(biāo)函數(shù)中最大的正系數(shù)對(duì)應(yīng)的非基變量為換入變量，即取最大的正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量為換入變量。換入變量為x1對(duì)例1，這時(shí)目標(biāo)函數(shù)為第74頁(yè)/共113頁(yè)75確定換出變量由于基變量只有m個(gè)，因此將一個(gè)非基變量變?yōu)榛兞亢?，必須將一個(gè)原來的基變量變?yōu)榉腔兞?，這個(gè)變量就是所謂的換出變量。換出變量與換入變量是密切相關(guān)的。設(shè)xk是換入變量。若xk>0，則第i個(gè)約束條件可以寫成并且由于其余的非基變量保持零值，因此第75頁(yè)/共113頁(yè)76由此可見為保證xi≥0，就必須從而對(duì)所有的i，若aik>0，則第76頁(yè)/共113頁(yè)77若確定xk為換入變量，則可估計(jì)xk的取值，使得：其余的決策變量都取非負(fù)值；并且目標(biāo)函數(shù)得到盡可能的增加。對(duì)前者，只須對(duì)所有的i成立，即為了使目標(biāo)函數(shù)盡可能增加，顯然應(yīng)該有設(shè)i=l(1ln)時(shí)，上式右端達(dá)到最小值。由于因此xl=0。第77頁(yè)/共113頁(yè)78這意味著xl可以是非基變量。因此取xl為換出變量。也就是取使得成立的l對(duì)應(yīng)的基變量xl為換出變量。對(duì)例1由于已經(jīng)確定了x1是換入變量。而因此x4是換出變量24/65/1第78頁(yè)/共113頁(yè)79確定換出變量等價(jià)于確定了一組新的基變量，為了方便地求出相應(yīng)的基解，接下來將進(jìn)行如下的運(yùn)算：將這組新的基變量的系數(shù)矩陣化為單位矩陣（或單位矩陣交換列后得到的矩陣），這等價(jià)于使得這組基變量中每個(gè)變量只出現(xiàn)在一個(gè)方程中并且在該方程中的系數(shù)為1，這稱為旋轉(zhuǎn)運(yùn)算。旋轉(zhuǎn)運(yùn)算可以利用對(duì)約束方程組進(jìn)行加減消元法完成。第79頁(yè)/共113頁(yè)80對(duì)例1的約束方程組第2式6第3式–第2式第80頁(yè)/共113頁(yè)81由此可以立即得到新的基解為很明顯，它是基可行解。為了判斷這一新的基可行解是否為最優(yōu)解，需要將原目標(biāo)函數(shù)改寫為新的非基變量的函數(shù)。原目標(biāo)函數(shù)為但是代入目標(biāo)函數(shù)，得第81頁(yè)/共113頁(yè)82即其中系數(shù)1/3，-1/6分別是非基變量x2，x4的檢驗(yàn)數(shù)。因此對(duì)應(yīng)于這一新的基可行解，目標(biāo)函數(shù)值為z=8。問題是這一目標(biāo)函數(shù)值是否為最優(yōu)的目標(biāo)函數(shù)值。由于x2的系數(shù)（檢驗(yàn)數(shù)）為1/3，是正數(shù)，因此如果能使x2取正數(shù)，則目標(biāo)函數(shù)還能增加。因此該基可行解仍不是最優(yōu)解。一般地，對(duì)一個(gè)基可行解而言，若非基變量的檢驗(yàn)數(shù)中存在正數(shù)，則該解不是最優(yōu)解；否則它一定是最優(yōu)解。第82頁(yè)/共113頁(yè)83單純形法求解過程小結(jié)（1）求出初始基可行解（2）通過非基變量在目標(biāo)函數(shù)中的系數(shù)（檢驗(yàn)數(shù)）是否都小于或等于零，判別該基可行解是否為最優(yōu)解。若是，結(jié)束運(yùn)算；否則進(jìn)行下一步。（3）確定換入變量。取最大的正檢驗(yàn)數(shù)對(duì)應(yīng)的變量為換入變量。（4）確定換出變量。用換入變量在各方程中的正的系數(shù)去除該方程的右端常數(shù)，在除得的商中取最小者，該最小商所在方程中的基變量就是換出變量。由此得到一組新的基變量。（5）旋轉(zhuǎn)運(yùn)算。將新的基變量在約束方程中的系數(shù)矩陣化為單位矩陣（或單位矩陣交換列后的矩陣）?；氐降冢?）步。第83頁(yè)/共113頁(yè)84單純形表的方法單純形法的所有運(yùn)算實(shí)際上都可歸結(jié)為對(duì)LP模型的目標(biāo)函數(shù)系數(shù)以及約束方程組的系數(shù)（矩陣）的運(yùn)算。為了簡(jiǎn)化運(yùn)算過程，并使運(yùn)算過程程序化。人們構(gòu)造了單純形表來進(jìn)行運(yùn)算第84頁(yè)/共113頁(yè)850611000100011524552121x3x4x5x1x2x3x4x5bXb00021000Cb初始單純形表例1中的模型化為標(biāo)準(zhǔn)形式后為σj第85頁(yè)/共113頁(yè)8621000CbXbbx1x2x3x4x5000x3x4x515245051006201011001σj21000基變量目標(biāo)函數(shù)系數(shù)右端常數(shù)基變量在目標(biāo)函數(shù)中的系數(shù)約束方程組系數(shù)矩陣檢驗(yàn)數(shù)基可行解：目標(biāo)函數(shù)值為：z=0這個(gè)基可行解不是最優(yōu)解第86頁(yè)/共113頁(yè)8721000CbXbbx1x2x3x4x5000x3x4x515245051006201011001σj21000換入變量24/65/1換出變量主元旋轉(zhuǎn)運(yùn)算的目的：通過矩陣的初等行變換，使主元變?yōu)?，主元列的其他數(shù)變?yōu)?。變換后為21000CbXbbx1x2x3x4x5020x3x1x515410510011/301/6002/30-1/61σj01/30-1/30第87頁(yè)/共113頁(yè)8821000CbXbbx1x2x3x4x5020x3x1x515410510011/301/6002/30-1/6101/30-1/30基可行解為：目標(biāo)函數(shù)值為：z=815/54/(1/3)1/(2/3)21000CbXbbx1x2x3x4x5021x3x1x215/27/23/20015/4-5/21001/4-1/2010-1/43/2000-1/4-1/2第88頁(yè)/共113頁(yè)8921000CbXbbx1x2x3x4x5021x3x1x215/27/23/20015/4-15/21001/4-1/2010-1/43/2000-1/4-1/2最優(yōu)解為：最優(yōu)目標(biāo)函數(shù)值為：z=8.58?因此對(duì)例1中的問題，最優(yōu)的生產(chǎn)計(jì)劃安排是每天生產(chǎn)甲家電3.5件，乙家電1.5件，每天可以得到的最大利潤(rùn)為8.5元。（按此計(jì)劃安排生產(chǎn)，每天設(shè)備A可富余7.5臺(tái)時(shí)）第89頁(yè)/共113頁(yè)9021000CbXbbx1x2x3x4x5000x3x4x51524505100620101100124/65/1σj21000021x3x1x215/27/23/20015/415/21001/4-1/2010-1/43/28?000-1/4-1/2020x3x1x515410510011/301/6002/30-1/6115/54/(1/3)1/(2/3)σj01/30-1/30初始單純形表最終單純形表單純形表合并的表示第90頁(yè)/共113頁(yè)91無窮多個(gè)最優(yōu)解檢驗(yàn)數(shù)的實(shí)際意義：檢驗(yàn)數(shù)是非基變量每增加一個(gè)單位，目標(biāo)函數(shù)的增加值。因此如果在最終單純形表中，當(dāng)所有的檢驗(yàn)數(shù)都小于或等于零，并且存在非基變量的檢驗(yàn)數(shù)等于零的情況時(shí)，LP問題存在無窮多個(gè)最優(yōu)解。實(shí)際上，此時(shí)可選擇檢驗(yàn)數(shù)為零的非基變量為換入變量，迭代到一個(gè)新的基可行解，它的目標(biāo)函數(shù)值等于最優(yōu)解的目標(biāo)函數(shù)值，從而也是最優(yōu)解。因此有無窮多個(gè)最優(yōu)解。第91頁(yè)/共113頁(yè)92無界解若換入變量（或正檢驗(yàn)數(shù)）所在列的所有系數(shù)都小于或等于零，則LP問題為無界解。例如，如果單純形表為21000CbXbbx1x2x3x4x5000x3x4x51524505100-62010-11001σj21000則目標(biāo)函數(shù)無界。第92頁(yè)/共113頁(yè)93實(shí)際上換入變量為x1，相應(yīng)的約束方程組為由于x2仍是非基變量，因此由此可見，不管x1取什么樣的正數(shù)，x3、x4、x5都保持非負(fù)，這意味著x1的取值沒有任何限制，從而目標(biāo)函數(shù)值可以無限增加。第93頁(yè)/共113頁(yè)94最小化的線性規(guī)劃問題在關(guān)于LP問題模型的標(biāo)準(zhǔn)形式中，關(guān)于目標(biāo)函數(shù)的要求可以降低，即不必要求目標(biāo)函數(shù)是求最大值，而可以是求最小值。對(duì)最小化的LP問題，單純形法求解過程有兩處值得注意的修改。1.最優(yōu)解的判別：當(dāng)所有檢驗(yàn)數(shù)大于或等于0時(shí)，單純形表給出的解是最優(yōu)解2.換入變量的確定：最小的負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的變量為換入變量第94頁(yè)/共113頁(yè)95例求解如下的最小化LP問題第95頁(yè)/共113頁(yè)96第96頁(yè)/共113頁(yè)97單純形法的進(jìn)一步討論如果約束方程不存在前面所述的初始基變量，處理的方式是通過添加人工變量來得到所需要的初始基變量。添加人工變量的方法是，先化約束條件為標(biāo)準(zhǔn)形式。然后在不含初始基變量的方程的左邊人為地加上一個(gè)非負(fù)變量（人工變量），作為該方程的初始基變量，不同的方程添加的人工變量也不同。原來的條件分別為“”,“”和“”型，加人工變量的方法第97頁(yè)/共113頁(yè)98人工變量的處理人工變量是由于應(yīng)用單純形法求解的需要人為添加的變量，因此在最終單純形表的基變量中不應(yīng)包含人工變量。因此人工變量應(yīng)該逐個(gè)從基變量中換出來。為了使人工變量能從基變量中逐個(gè)換出，可采用如下兩種方法：大M法和兩階段法。第98頁(yè)/共113頁(yè)99大M法這種方法是（對(duì)最大化的LP問題）通過將人工變量在目標(biāo)函數(shù)中的系數(shù)取成絕對(duì)值充分大的負(fù)數(shù)，因而迫使其盡快從基變量中換出。這樣的負(fù)數(shù)通常寫成“-M”。具體的做法是對(duì)最大化的LP問題，人工變量在目標(biāo)函數(shù)中的系數(shù)取為“-M”對(duì)最小化的LP問題，人工變量在目標(biāo)函數(shù)中的系數(shù)取為“M”然后再用單純形法求解。若最優(yōu)解的基變量中仍含有人工變量，則LP問題為無可行解。第99頁(yè)/共113頁(yè)100p30例6給定LP問題化成標(biāo)準(zhǔn)形式后為不存在前面那種初始基變量，因此要添加人工變量第100頁(yè)/共113頁(yè)101添加人工變量，并用大M法處理人工變量，模型變?yōu)槿缓笥脝渭冃畏ㄇ蠼庠搯栴}第101頁(yè)/共113頁(yè)102-30100-M-MCbXbbx1x2x3x4x5x6x70-M-Mx4x6x74191111000-21-10-1100310001σj-2M-34M10-M0000-Mx4x2x731630211-10-21-10-11060403-31σj6M-304M+103M-4M0第102頁(yè)/共113頁(yè)103-30100-M-MCbXbbx1x2x3x4x5x6x700-3x4x2x10310001-1/2-1/2-1/2011/30001/3102/301/21/21/6σj00303/2-M-3/2-M+1/2001x4x2x305/23/20001-1/2-1/2-1/2-1/2100-1/41/41/43/20103/4-3/41/4σj-9/2000-3/4-M+3/4-M-1/4最優(yōu)解為最優(yōu)目標(biāo)函數(shù)值為第103頁(yè)/共113頁(yè)104兩階段法大M法的不足。兩階段法：添加了人工變量后，分兩個(gè)階段來求解LP問題。第一階段：求解輔助的LP問題。輔助的LP問題構(gòu)造如下：約束條件就是原來的（添加了人工變量后）條件，目標(biāo)函數(shù)是所有人工變量之和，對(duì)這樣的目標(biāo)函數(shù)求最小值。若第一階段的目標(biāo)函數(shù)的最優(yōu)值不等于零，則原LP問題無可行解，否則進(jìn)入第二階段。第104頁(yè)/共113頁(yè)105第二階段：將第一階