《管理運(yùn)籌學(xué)（第二版）》全套教學(xué)課件

1、第一章緒論1決策、定量分析與管理運(yùn)籌學(xué)2運(yùn)籌學(xué)的分支3運(yùn)籌學(xué)在工商管理中的應(yīng)用4學(xué)習(xí)運(yùn)籌學(xué)必須使用相應(yīng)的計(jì)算機(jī) 軟件，必須注重于學(xué)以致用的原則1第一章緒論 運(yùn)籌學(xué)（Operational Research) 直譯為“運(yùn)作研究”。 運(yùn)籌學(xué)是應(yīng)用分析、試驗(yàn)、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中的人力、物力、財(cái)力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。 運(yùn)籌學(xué)的產(chǎn)生和發(fā)展 運(yùn)籌學(xué)產(chǎn)生于第二次世界大戰(zhàn)，主要用于解決如何在與德軍的對(duì)抗中最大限度地殺傷敵人，減少損失。二戰(zhàn)以后，運(yùn)籌學(xué)得到了快速的發(fā)展，形成了許多分支，并且計(jì)算機(jī)的應(yīng)用極大地推動(dòng)了運(yùn)籌學(xué)的應(yīng)用與普及。運(yùn)籌學(xué)有廣泛應(yīng)用 運(yùn)

2、籌學(xué)不僅在軍事上，而且在生產(chǎn)、決策、運(yùn)輸、存儲(chǔ)等經(jīng)濟(jì)管理領(lǐng)域有著廣泛的應(yīng)用。21決策、定量分析與管理運(yùn)籌學(xué)決策過程（問題解決的過程）：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)成決策。 32運(yùn)籌學(xué)的分支4線性規(guī)劃整數(shù)線性規(guī)劃動(dòng)態(tài)規(guī)劃圖與網(wǎng)絡(luò)模型存儲(chǔ)論排隊(duì)論排序與統(tǒng)籌方法決策分析對(duì)策論預(yù)測(cè)* 多目標(biāo)規(guī)劃、隨機(jī)規(guī)劃、模糊規(guī)劃等3運(yùn)籌學(xué)在工商管理中的應(yīng)用生產(chǎn)計(jì)劃

3、：生產(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ì)與管理等53運(yùn)籌學(xué)在工商管理中的應(yīng)用由國(guó)際運(yùn)籌與管理科學(xué)協(xié)會(huì)（INFORMS）和它的管理科學(xué)實(shí)踐學(xué)會(huì)（College

4、 for the Practice of the Management Sciences）主持評(píng)獎(jiǎng)的負(fù)有盛名的弗蘭茨厄德曼（Frany Edlman）獎(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)目。63運(yùn)籌學(xué)在工商管理中的應(yīng)用組織應(yīng)用Interface期刊號(hào) 每年節(jié)支（美元）聯(lián)合航空公司滿足乘客需求前提下,以最低成本進(jìn)行訂票及安排機(jī)場(chǎng)工作班次1-2/1986600萬Citgo

5、石油優(yōu)化煉油程序及產(chǎn)品供應(yīng)、配送及營(yíng)銷1-2/19877000萬荷馬特發(fā)展公司（Homart Development Co.）優(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/1998

6、1500萬更多年收入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ù)7運(yùn)籌學(xué)方法使用情況(美1983)8運(yùn)籌學(xué)方法在中國(guó)使用情況(隨機(jī)抽樣)94 學(xué)習(xí)管理運(yùn)籌學(xué)必須使用相應(yīng)的計(jì)算機(jī)軟件，必須注重于學(xué)以致用的原則學(xué)習(xí)運(yùn)籌學(xué)要結(jié)合實(shí)際的應(yīng)用，不要被一些概念、理論的困難嚇倒。學(xué)習(xí)運(yùn)籌學(xué)要把注意力放在“結(jié)合實(shí)際問題建立運(yùn)籌學(xué)模型”和“解決問題的方案或模型的解”兩頭，中間的計(jì)算過程盡可能讓計(jì)算機(jī)

7、軟件去完成。本書附有運(yùn)籌學(xué)教學(xué)軟件，使用方法很簡(jiǎn)單。學(xué)員必須盡快學(xué)會(huì)使用這個(gè)運(yùn)籌學(xué)教學(xué)軟件，并借助它來學(xué)好本課程。學(xué)習(xí)運(yùn)籌學(xué)是為了用于實(shí)踐，解決實(shí)際問題。以前重視人工計(jì)算是因?yàn)闆]有計(jì)算機(jī)，現(xiàn)在有了就應(yīng)該好好利用。104 學(xué)習(xí)管理運(yùn)籌學(xué)必須使用相應(yīng)的計(jì)算機(jī)軟件，必須注重于學(xué)以致用的原則例如，有人要從北京去烏魯木齊。在一百多年以前，我們應(yīng)該告訴他如何配備糧草、銀兩、衣物，如何選購(gòu)馬匹、馬車，挑選馬夫和保鏢，如何根據(jù)天氣、地理?xiàng)l件和社會(huì)諸因素來確定行車路線和行程，更重要的是如何在幾個(gè)月的行程中處理吃穿住行，應(yīng)付突發(fā)事件等問題；但是現(xiàn)在我們只需告訴他如何去北京飛機(jī)場(chǎng)，如何在烏魯木齊下飛機(jī)后提取行李和坐

8、車就可以了，其余的問題交給航空公司和機(jī)組人員就行了。完全沒有必要為了一次旅行攻讀空氣動(dòng)力學(xué)、噴氣發(fā)動(dòng)機(jī)設(shè)計(jì)和制造、飛行器駕駛手冊(cè)等厚厚的教科書?！八街梢怨ビ瘛?。本書配套的計(jì)算機(jī)軟件如同上例中的“飛機(jī)”，它可以為你節(jié)省出大量的時(shí)間和精力用在問題建模，以及解決方案的分析和完善上。11第二章線性規(guī)劃的圖解法1問題的提出2圖解法3圖解法的靈敏度分析12第二章線性規(guī)劃的圖解法在管理中一些典型的線性規(guī)劃應(yīng)用合理利用線材問題：如何在保證生產(chǎn)的條件下，下料最少配料問題：在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)投資問題：從投資項(xiàng)目中選取方案，使投資回報(bào)最大產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、財(cái)力等，使獲利最大

9、勞動(dòng)力安排：用最少的勞動(dòng)力來滿足工作的需要運(yùn)輸問題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小13線性規(guī)劃的組成：目標(biāo)函數(shù) Max F 或 Min F約束條件 s.t. (subject to) 滿足于決策變量 用符號(hào)來表示可控制的因素1問題的提出14例1. 某工廠在計(jì)劃期內(nèi)要安排、兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗、資源的限制，如下表：?jiǎn)栴}：工廠應(yīng)分別生產(chǎn)多少單位、產(chǎn)品才能使工廠獲利最多？線性規(guī)劃模型： 目標(biāo)函數(shù)：Max z = 50 x1 + 100 x2 約束條件：s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 01問題

10、的提出建模過程1.理解要解決的問題，了解解題的目標(biāo)和條件；2.定義決策變量（ x1 ，x2 ， ，xn ），每一組值表示一個(gè)方案；3.用決策變量的線性函數(shù)形式寫出目標(biāo)函數(shù)，確定最大化或最小化目標(biāo)；4.用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件一般形式目標(biāo)函數(shù)： Max （Min） z = c1 x1 + c2 x2 + + cn xn 約束條件： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x

11、1 ，x2 ， ，xn 0 15例1.目標(biāo)函數(shù)： Max z = 50 x1 + 100 x2 約束條件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E)得到最優(yōu)解： x1 = 50， x2 = 250 最優(yōu)目標(biāo)值 z = 27500162圖 解 法 對(duì)于只有兩個(gè)決策變量的線性規(guī)劃問題，可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問題的有關(guān)概念，并求解。 下面通過例1詳細(xì)講解其方法：2圖 解 法 (1)分別取決策變量X1 , X2 為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)系里，圖上任意一點(diǎn)的坐標(biāo)代表了決策變量的一組值

12、，例1的每個(gè)約束條件都代表一個(gè)半平面。17x2x1X20X2=0 x2x1X10X1=02圖 解 法（2）對(duì)每個(gè)不等式(約束條件)，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。18100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=4003002003004002圖 解 法（3）把五個(gè)圖合并成一個(gè)圖，取各約束條件的公共部分，如圖2-1所示。19100100 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400圖2-12圖 解 法（4

13、）目標(biāo)函數(shù)z=50 x1+100 x2，當(dāng)z取某一固定值時(shí)得到一條直線，直線上的每一點(diǎn)都具有相同的目標(biāo)函數(shù)值，稱之為“等值線”。平行移動(dòng)等值線，當(dāng)移動(dòng)到B點(diǎn)時(shí)，z在可行域內(nèi)實(shí)現(xiàn)了最大化。A，B，C，D，E是可行域的頂點(diǎn)，對(duì)有限個(gè)約束條件則其可行域的頂點(diǎn)也是有限的。20 x1x2z=20000=50 x1+100 x2圖2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE2圖 解 法線性規(guī)劃的標(biāo)準(zhǔn)化內(nèi)容之一：引入松馳變量（含義是資源的剩余量） 例1 中引入 s1， s2， s3 模型化為 目標(biāo)函數(shù)：Max z = 50

14、x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3 約束條件：s.t. x1 + x2 + s1 = 300 2 x1 + x2 + s2 = 400 x2 + s3 = 250 x1 , x2 , s1 , s2 , s3 0 對(duì)于最優(yōu)解 x1 =50 x2 = 250 ， s1 = 0 s2 =50 s3 = 0 說明：生產(chǎn)50單位產(chǎn)品和250單位產(chǎn)品將消耗完所有可能的設(shè)備臺(tái)時(shí)數(shù)及原料B，但對(duì)原料A則還剩余50千克。212圖 解 法重要結(jié)論：如果線性規(guī)劃有最優(yōu)解，則一定有一個(gè)可行域的頂點(diǎn)對(duì)應(yīng)一個(gè)最優(yōu)解；無窮多個(gè)最優(yōu)解。若將例1中的目標(biāo)函數(shù)變?yōu)閙ax z=50 x1+50 x2

15、，則線段BC上的所有點(diǎn)都代表了最優(yōu)解；無界解。即可行域的范圍延伸到無窮遠(yuǎn)，目標(biāo)函數(shù)值可以無窮大或無窮小。一般來說，這說明模型有錯(cuò)，忽略了一些必要的約束條件；無可行解。若在例1的數(shù)學(xué)模型中再增加一個(gè)約束條件4x1+3x21200，則可行域?yàn)榭沼?，不存在滿足約束條件的解，當(dāng)然也就不存在最優(yōu)解了。22進(jìn) 一 步 討 論 例2 某公司由于生產(chǎn)需要，共需要A，B兩種原料至少350噸（A，B兩種材料有一定替代性），其中A原料至少購(gòu)進(jìn)125噸。但由于A，B兩種原料的規(guī)格不同，各自所需的加工時(shí)間也是不同的，加工每噸A原料需要2個(gè)小時(shí)，加工每噸B原料需要1小時(shí)，而公司總共有600個(gè)加工小時(shí)。又知道每噸A原料的價(jià)

16、格為2萬元，每噸B原料的價(jià)格為3萬元，試問在滿足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購(gòu)買A，B兩種原料，使得購(gòu)進(jìn)成本最低？23進(jìn) 一 步 討 論解：目標(biāo)函數(shù)： Min f = 2x1 + 3 x2 約束條件：s.t. x1 + x2 350 x1 125 2 x1 + x2 600 x1 , x2 0 采用圖解法。如下圖：得Q點(diǎn)坐標(biāo)（250，100）為最優(yōu)解。24100200300400500600100200300400600500 x1 =125x1+x2 =3502x1+3x2 =8002x1+3x2 =9002x1+x2 =6002x1+3x2 =1200 x1 x2 Q3圖

17、解法的靈敏度分析線性規(guī)劃的標(biāo)準(zhǔn)化一般形式目標(biāo)函數(shù)： Max （Min） z = c1 x1 + c2 x2 + + cn xn 約束條件： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0 標(biāo)準(zhǔn)形式目標(biāo)函數(shù)： Max z = c1 x1 + c2 x2 + + cn xn 約束條件： s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 +

18、 + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0，bi 0253圖解法的靈敏度分析 可以看出，線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個(gè)特點(diǎn)：目標(biāo)最大化；約束為等式；決策變量均非負(fù)；右端項(xiàng)非負(fù)。 對(duì)于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式:263圖解法的靈敏度分析1.極小化目標(biāo)函數(shù)的問題： 設(shè)目標(biāo)函數(shù)為 Min f = c1x1 + c2x2 + + cnxn (可以)令 z -f ， 則該極小化問題與下面的極大化問題有相同的最優(yōu)解，即 Max z = - c1x1 - c2x2 - - cnxn 但

19、必須注意，盡管以上兩個(gè)問題的最優(yōu)解相同，但它們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào)，即 Min f - Max z273圖解法的靈敏度分析2、約束條件不是等式的問題： 設(shè)約束條件為 ai1 x1+ai2 x2+ +ain xn bi 可以引進(jìn)一個(gè)新的變量s ，使它等于約束右邊與左邊之差 s=bi(ai1 x1 + ai2 x2 + + ain xn )顯然，s 也具有非負(fù)約束，即s0， 這時(shí)新的約束條件成為 ai1 x1+ai2 x2+ +ain xn+s = bi283圖解法的靈敏度分析 當(dāng)約束條件為 ai1 x1+ai2 x2+ +ain xn bi 時(shí)， 類似地令 s=(ai1 x1+ai2

20、 x2+ +ain xn)- bi 顯然，s 也具有非負(fù)約束，即s0，這時(shí)新的約束條件成為 ai1 x1+ai2 x2+ +ain xn-s = bi293圖解法的靈敏度分析 為了使約束由不等式成為等式而引進(jìn)的變量s,當(dāng)不等式為“小于等于”時(shí)稱為“松弛變量”；當(dāng)不等式為“大于等于”時(shí)稱為“剩余變量”。如果原問題中有若干個(gè)非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，必須對(duì)各個(gè)約束引進(jìn)不同的松弛變量。 303.右端項(xiàng)有負(fù)值的問題： 在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個(gè)分量非負(fù)。當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí)，如 bi“程序”- “管理運(yùn)籌學(xué)2.0”，彈出主窗口。39例1.目標(biāo)函數(shù)： Max z = 50 x1 +

21、 100 x2 約束條件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E)1“管理運(yùn)籌學(xué)”軟件的操作方法第二步：選擇所需子模塊，點(diǎn)擊主窗口中的相應(yīng)按鈕。本題中選用“線性規(guī)劃”方法。點(diǎn)擊按鈕彈出如下界面：401“管理運(yùn)籌學(xué)”軟件的操作方法第三步：點(diǎn)擊“新建”按鈕，輸入數(shù)據(jù)。本題中共有2個(gè)變量，4個(gè)約束條件，目標(biāo)函數(shù)取MAX。點(diǎn)擊“確定”后，在表中輸入Cj,bi和aij等值，并確定變量的正負(fù)約束。輸入數(shù)值后的界面如下。411“管理運(yùn)籌學(xué)”軟件的操作方法第四步：點(diǎn)擊“解決”按鈕，得出計(jì)算結(jié)果。本題的運(yùn)行結(jié)果界面如

22、下。422“管理運(yùn)籌學(xué)”軟件的輸出信息分析第五步：分析運(yùn)行結(jié)果。本題中目標(biāo)函數(shù)的最優(yōu)值是27500，x1=50, x2=250。相差值表示相應(yīng)的決策變量的目標(biāo)系數(shù)需要改進(jìn)的數(shù)量，使得決策變量為正值，當(dāng)決策變量已為正數(shù)時(shí)，相差數(shù)為零。松弛/剩余變量的數(shù)值表示還有多少資源沒有被使用。如果為零，則表示與之相對(duì)應(yīng)的資源已經(jīng)全部用上。對(duì)偶價(jià)格表示其對(duì)應(yīng)的資源每增加一個(gè)單位，將增加多少個(gè)單位的最優(yōu)值。目標(biāo)函數(shù)系數(shù)范圍表示最優(yōu)解不變的情況下，目標(biāo)函數(shù)的決策變量系數(shù)的變化范圍。當(dāng)前值是指當(dāng)前的最優(yōu)解中的系數(shù)取值。常數(shù)項(xiàng)范圍是指約束條件的右端常量。上限值和下限值是指當(dāng)約束條件的右端常量在此范圍內(nèi)變化時(shí)，與其對(duì)應(yīng)

23、的約束條件的對(duì)偶價(jià)格不變。當(dāng)前值是指現(xiàn)在的取值。 以上計(jì)算機(jī)輸出的目標(biāo)函數(shù)系數(shù)和約束條件右邊值的靈敏度分析都是在其他系數(shù)值不變，只有一個(gè)系數(shù)變化的基礎(chǔ)上得出的！ 432“管理運(yùn)籌學(xué)”軟件的輸出信息分析2.當(dāng)有多個(gè)系數(shù)變化時(shí)，需要進(jìn)一步討論。 百分之一百法則：對(duì)于所有變化的目標(biāo)函數(shù)決策系數(shù)（約束條件右邊常數(shù)值），當(dāng)其所有允許增加的百分比與允許減少的百分比之和不超過100%時(shí)，最優(yōu)解不變（對(duì)偶價(jià)格不變，最優(yōu)解仍是原來幾個(gè)線性方程的解）。 * 允許增加量 = 上限 - 現(xiàn)在值 c1 的允許增加量為 100 - 50 = 50 b1 的允許增加量為 325 - 300 = 25 * 允許減少量 = 現(xiàn)

24、在值 - 下限 c2 的允許減少量為 100 - 50 = 50 b3 的允許減少量為 250 - 200 = 50 * 允許增加的百分比 = 增加量 / 允許增加量 * 允許減少的百分比 = 減少量 / 允許減少量 442“管理運(yùn)籌學(xué)”軟件的輸出信息分析 例： c1 變?yōu)?74 , c2 變?yōu)?78, 則 (74 - 50) / 50 + (100 - 78 ) / 50 = 92%，故最優(yōu)解不變。 b1 變?yōu)?315 , b3 變?yōu)?240, 則 (315 - 50) / 25 + (250 - 240 ) / 50 = 80%，故對(duì)偶價(jià)格不變（最優(yōu)解仍是原來幾個(gè)線性方程的解）。在使用百分

25、之一百法則進(jìn)行靈敏度分析時(shí)，要注意：1）當(dāng)允許增加量（允許減少量）為無窮大時(shí)，則對(duì)任意增加量（減少量），其允許增加（減少）百分比均看作0；2）百分之一百法則是充分條件，但非必要條件；也就是說超過100%并不一定變化；3）百分之一百法則不能用于目標(biāo)函數(shù)決策變量系數(shù)和約束條件右邊常數(shù)值同時(shí)變化的情況。這種情況下，只有重新求解。452“管理運(yùn)籌學(xué)”軟件的輸出信息分析下面用“管理運(yùn)籌學(xué)”軟件來分析第二章的例2，其數(shù)學(xué)模型如下： 目標(biāo)函數(shù)： Min f = 2x1 + 3 x2約束條件： s.t. x1 + x2 350 x1 125 2 x1 + x2 600 x1 , x2 0 從上圖可知，當(dāng)購(gòu)進(jìn)原

26、材料A 250t，原料B 100t時(shí)，購(gòu)進(jìn)成本最低，為800萬元。46在松弛/剩余變量欄中，約束條件2的值為125，它表示對(duì)原料A的最低需求，即對(duì)A的剩余變量值為125；同理可知約束條件1的剩余變量值為0；約束條件3的松弛變量值為0。在對(duì)偶價(jià)格欄中，約束條件3的對(duì)偶價(jià)格為1萬元，也就是說如果把加工時(shí)數(shù)從600小時(shí)增加到601小時(shí)，則總成本將得到改進(jìn)，由800萬減少到799萬。也可知約束條件1的對(duì)偶條件為-4萬元，也就是說如果把購(gòu)進(jìn)原料A的下限從125t增加到126t，那么總成本將加大，由800萬增加到804萬。當(dāng)然如果減少對(duì)原料A的下限，那么總成本將得到改進(jìn)。在常數(shù)項(xiàng)范圍一欄中，知道當(dāng)約束條件

27、1的常數(shù)項(xiàng)在300475范圍內(nèi)變化，且其他約束條件不變時(shí)，約束條件1的對(duì)偶價(jià)格不變；當(dāng)約束條件2的常數(shù)項(xiàng)在負(fù)無窮到250范圍內(nèi)變化，而其他約束條件的常數(shù)項(xiàng)不變時(shí)，約束條件2的對(duì)偶價(jià)格不變，仍為0；當(dāng)約束條件3的常數(shù)項(xiàng)在475700內(nèi)變化，而其他約束條件的常數(shù)項(xiàng)不變時(shí)，約束條件3的對(duì)偶價(jià)格不變，仍為1。472“管理運(yùn)籌學(xué)”軟件的輸出信息分析注意：當(dāng)約束條件中的常數(shù)項(xiàng)增加一個(gè)單位時(shí)，最優(yōu)目標(biāo)函數(shù)值增加的數(shù)量稱之為影子價(jià)格。在求目標(biāo)函數(shù)最大時(shí)，當(dāng)約束條件中的常數(shù)項(xiàng)增加一個(gè)單位時(shí)，目標(biāo)函數(shù)值增加的數(shù)量就為改進(jìn)的數(shù)量，所以影子價(jià)格等于對(duì)偶價(jià)格；在求目標(biāo)函數(shù)值最小時(shí)，改進(jìn)的數(shù)量就是減少的數(shù)量，所以影子價(jià)格

28、即為負(fù)的對(duì)偶價(jià)格?！肮芾磉\(yùn)籌學(xué)”軟件可以解決含有100個(gè)變量50個(gè)約束方程的線性規(guī)劃問題，可以解決工商管理中大量的問題。如果想要解決更大的線性規(guī)劃問題，可以使用由芝加哥大學(xué)的L.E.Schrage開發(fā)的Lindo計(jì)算機(jī)軟件包的微型計(jì)算機(jī)版本Lindo/PC。482“管理運(yùn)籌學(xué)”軟件的輸出信息分析第四章 線性規(guī)劃在工商管理中的應(yīng)用1 人力資源分配的問題2 生產(chǎn)計(jì)劃的問題3 套裁下料問題4 配料問題5 投資問題491人力資源分配的問題 50 例1某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下： 設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段一開始時(shí)上班，并連續(xù)工作八小時(shí)，問該公交線路怎樣安排司機(jī)和乘務(wù)

29、人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員?1人力資源分配的問題 解：設(shè) xi 表示第i班次時(shí)開始上班的司機(jī)和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。 目標(biāo)函數(shù)： Min x1 + x2 + x3 + x4 + x5 + x6 約束條件：s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 0511人力資源分配的問題 例2一家中型的百貨商場(chǎng)，它對(duì)售貨員的需求經(jīng)過統(tǒng)計(jì)分析如下表所示。為了保證售貨人員充分休息，售貨人員每周工作5天，休息兩天，并要求休息的兩天是連續(xù)的。問

30、應(yīng)該如何安排售貨人員的作息，既滿足工作需要，又使配備的售貨人員的人數(shù)最少？521人力資源分配的問題 解：設(shè) xi ( i = 1,2,7)表示星期一至日開始休息的人數(shù),這樣我們建立如下的數(shù)學(xué)模型。 目標(biāo)函數(shù)： Min x1 + x2 + x3 + x4 + x5 + x6 + x7 約束條件：s.t. x1 + x2 + x3 + x4 + x5 28 x2 + x3 + x4 + x5 + x6 15 x3 + x4 + x5 + x6 + x7 24 x4 + x5 + x6 + x7 + x1 25 x5 + x6 + x7 + x1 + x2 19 x6 + x7 + x1 + x2

31、+ x3 31 x7 + x1 + x2 + x3 + x4 28 x1,x2,x3,x4,x5,x6,x7 0532生產(chǎn)計(jì)劃的問題 例3某公司面臨一個(gè)是外包協(xié)作還是自行生產(chǎn)的問題。該公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機(jī)加工和裝配三個(gè)車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如表。問：公司為了獲得最大利潤(rùn)，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？542生產(chǎn)計(jì)劃的問題 解：設(shè) x1,x2,x3 分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，x4,x5 分別為由外協(xié)鑄造再由本

32、公司加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。 求 xi 的利潤(rùn)：利潤(rùn) = 售價(jià) - 各成本之和 產(chǎn)品甲全部自制的利潤(rùn) =23-(3+2+3)=15 產(chǎn)品甲鑄造外協(xié)，其余自制的利潤(rùn) =23-(5+2+3)=13 產(chǎn)品乙全部自制的利潤(rùn) =18-(5+1+2)=10 產(chǎn)品乙鑄造外協(xié)，其余自制的利潤(rùn) =18-(6+1+2)=9 產(chǎn)品丙的利潤(rùn) =16-(4+3+2)=7 可得到 xi （i = 1,2,3,4,5） 的利潤(rùn)分別為 15、10、7、13、9 元。552生產(chǎn)計(jì)劃的問題通過以上分析,可建立如下的數(shù)學(xué)模型:目標(biāo)函數(shù)： Max 15x1 + 10 x2 + 7x3 + 13x4 + 9x5 約束條件：

33、5x1 + 10 x2 + 7x3 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 10000 x1,x2,x3,x4,x5 0562生產(chǎn)計(jì)劃的問題例4永久機(jī)械廠生產(chǎn)、三種產(chǎn)品，均要經(jīng)過A、B兩 道工序加工。設(shè)有兩種規(guī)格的設(shè)備A1、A2能完成 A 工序；有三種規(guī)格的設(shè)備B1、B2、B3能完成 B 工序?？稍贏、B的任何規(guī)格的設(shè)備上加工； 可在任意規(guī)格的A設(shè)備上加工，但對(duì)B工序，只能在B1設(shè)備上加工；只能在A2與B2設(shè)備上加工。數(shù)據(jù)如表。問：為使該廠獲得最大利潤(rùn)，應(yīng)如何制定產(chǎn)品加工方案？572生產(chǎn)計(jì)劃的問題解：

34、設(shè) xijk 表示第 i 種產(chǎn)品，在第 j 種工序上的第 k 種設(shè)備上加工的數(shù)量。建立如下的數(shù)學(xué)模型: s.t. 5x111 + 10 x211 6000 （ 設(shè)備 A1 ） 7x112 + 9x212 + 12x312 10000 （ 設(shè)備 A2 ） 6x121 + 8x221 4000 （ 設(shè)備 B1 ） 4x122 + 11x322 7000 （ 設(shè)備 B2 ） 7x123 4000 （ 設(shè)備 B3 ） x111+ x112- x121- x122- x123 = 0 （產(chǎn)品在A、B工序加工的數(shù)量相等） x211+ x212- x221 = 0 （產(chǎn)品在A、B工序加工的數(shù)量相等） x31

35、2 - x322 = 0 （產(chǎn)品在A、B工序加工的數(shù)量相等） xijk 0 , i = 1,2,3; j = 1,2; k = 1,2,3582生產(chǎn)計(jì)劃的問題目標(biāo)函數(shù)為計(jì)算利潤(rùn)最大化，利潤(rùn)的計(jì)算公式為： 利潤(rùn) = （銷售單價(jià) - 原料單價(jià)）* 產(chǎn)品件數(shù)之和 -（每臺(tái)時(shí)的設(shè)備費(fèi)用*設(shè)備實(shí)際使用的總臺(tái)時(shí)數(shù)）之和。這樣得到目標(biāo)函數(shù)： Max(1.25-0.25)(x111+x112)+(2-0.35)x221+(2.80-0.5)x312 300/6000(5x111+10 x211)-321/10000(7x112+9x212+12x312)- 250/4000(6x121+8x221)-783/

36、7000(4x122+11x322)-200/4000(7x123).經(jīng)整理可得： Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123593套裁下料問題 60 例5某工廠要做100套鋼架，每套用長(zhǎng)為2.9 m,2.1 m,1.5 m的圓鋼各一根。已知原料每根長(zhǎng)7.4 m，問：應(yīng)如何下料，可使所用原料最??？ 解： 共可設(shè)計(jì)下列5 種下料方案，見下表 設(shè) x1,x2,x3,x4,x5 分別為上面 5 種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學(xué)

37、模型。 目標(biāo)函數(shù)： Min x1 + x2 + x3 + x4 + x5 約束條件： s.t. x1 + 2x2 + x4 100 2x3 + 2x4 + x5 100 3x1 + x2 + 2x3 + 3x5 100 x1,x2,x3,x4,x5 03套裁下料問題用“管理運(yùn)籌學(xué)”軟件計(jì)算得出最優(yōu)下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。 即 x1=30; x2=10； x3=0； x4=50； x5=0； 只需90根原材料就可制造出100套鋼架。注意：在建立此類型數(shù)學(xué)模型時(shí)，約束條件用大于等于號(hào)比用等于號(hào)要好。因?yàn)橛袝r(shí)在套用一些下料方案時(shí)可能會(huì)多出一根某種規(guī)格的圓

38、鋼，但它可能是最優(yōu)方案。如果用等于號(hào)，這一方案就不是可行解了。614配料問題 62 例6某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如右表。問：該廠應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大？ 解：設(shè) xij 表示第 i 種（甲、乙、丙）產(chǎn)品中原料 j 的含量。這樣我們建立數(shù)學(xué)模型時(shí)，要考慮： 對(duì)于甲： x11，x12，x13； 對(duì)于乙： x21，x22，x23； 對(duì)于丙： x31，x32，x33； 對(duì)于原料1： x11，x21，x31； 對(duì)于原料2： x12，x22，x32； 對(duì)于原料3： x13，x23，x33； 目標(biāo)函數(shù)： 利潤(rùn)最大，利潤(rùn) = 收入 - 原料支出 約束條

39、件： 規(guī)格要求 4 個(gè)； 供應(yīng)量限制 3 個(gè)。4配料問題利潤(rùn)=總收入-總成本=甲乙丙三種產(chǎn)品的銷售單價(jià)*產(chǎn)品數(shù)量-甲乙丙使用的原料單價(jià)*原料數(shù)量，故有目標(biāo)函數(shù)Max 50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）-65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33）= -15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 約束條件： 從第1個(gè)表中有： x110.5(x11+x12+x13) x120.25(x11+x12+x13) x210.25(x21+x22+x

40、23) x220.5(x21+x22+x23)634配料問題 從第2個(gè)表中，生產(chǎn)甲乙丙的原材料不能超過原材料的供應(yīng)限額，故有 (x11+x21+x31)100 (x12+x22+x32)100 (x13+x23+x33)60 通過整理，得到以下模型：644配料問題例6（續(xù)）目標(biāo)函數(shù)：Max z = -15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 約束條件： s.t. 0.5 x11-0.5 x12 -0.5 x13 0 （原材料1不少于50%） -0.25x11+0.75x12 -0.25x13 0 （原材料2不超過25%） 0.75x21-0.2

41、5x22 -0.25x23 0 （原材料1不少于25%） -0.5 x21+0.5 x22 -0.5 x23 0 （原材料2不超過50%） x11+ x21 + x31 100 (供應(yīng)量限制） x12+ x22 + x32 100 (供應(yīng)量限制） x13+ x23 + x33 60 (供應(yīng)量限制） xij 0 , i = 1,2,3; j = 1,2,3654配料問題 標(biāo)準(zhǔn)汽油辛烷數(shù)蒸汽壓力(g/cm2)庫(kù)存量(L)1107.57.1110-2380000293.011.38 10-2265200387.05.6910-24081004108.028.45 10-2130100飛機(jī)汽油辛烷數(shù)蒸

42、汽壓力(g/cm2)產(chǎn)量需求1不小于91不大于9.96 10-2越多越好2不小于100不大于9.96 10-2不少于25000066例7.汽油混合問題。一種汽油的特性可用兩種指標(biāo)描述，用“辛烷數(shù)”來定量描述其點(diǎn)火特性，用“蒸汽壓力”來定量描述其揮發(fā)性。某煉油廠有1、2、3、4種標(biāo)準(zhǔn)汽油，其特性和庫(kù)存量列于表4-6中，將這四種標(biāo)準(zhǔn)汽油混合，可得到標(biāo)號(hào)為1，2的兩種飛機(jī)汽油，這兩種汽油的性能指標(biāo)及產(chǎn)量需求列于表4-7中。問應(yīng)如何根據(jù)庫(kù)存情況適量混合各種標(biāo)準(zhǔn)汽油，既滿足飛機(jī)汽油的性能指標(biāo)，又使2號(hào)汽油滿足需求，并使得1號(hào)汽油產(chǎn)量最高？表4-6表4-74配料問題 67解：設(shè)xij為飛機(jī)汽油i中所用標(biāo)準(zhǔn)

43、汽油j的數(shù)量(L)。 目標(biāo)函數(shù)為飛機(jī)汽油1的總產(chǎn)量：庫(kù)存量約束為：產(chǎn)量約束為飛機(jī)汽油2的產(chǎn)量：由物理中的分壓定律， 可得有關(guān)蒸汽壓力的約束條件：同樣可得有關(guān)辛烷數(shù)的約束條件為：4配料問題 68綜上所述，得該問題的數(shù)學(xué)模型為：4配料問題 69由管理運(yùn)籌學(xué)軟件求解得：5投資問題 70例8某部門現(xiàn)有資金200萬元，今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：項(xiàng)目A：從第一年到第五年每年年初都可投資，當(dāng)年末能收回本利110%；項(xiàng)目B：從第一年到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不能超過30萬元；項(xiàng)目C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超

44、過80萬元；項(xiàng)目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過100萬元。 據(jù)測(cè)定每萬元每次投資的風(fēng)險(xiǎn)指數(shù)如右表：?jiǎn)枺篴）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利金額為最大？b）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利在330萬元的基礎(chǔ)上使得其投資總的風(fēng)險(xiǎn)系數(shù)為最小？ 解： 1）確定決策變量：連續(xù)投資問題 設(shè) xij ( i = 15，j = 14)表示第 i 年初投資于A(j=1)、B(j=2)、C(j=3)、D(j=4)項(xiàng)目的金額。這樣我們建立如下的決策變量： A x11 x21 x31 x41 x51 B x12 x2

45、2 x32 x42 C x33 D x245投資問題2）約束條件：第一年：A當(dāng)年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是 x11+ x12 = 200；第二年：B次年末才可收回投資，故第二年年初有資金1.1 x11，于是 x21 + x22+ x24 = 1.1x11；第三年：年初有資金 1.1x21+ 1.25x12，于是 x31 + x32+ x33 = 1.1x21+ 1.25x12；第四年：年初有資金 1.1x31+ 1.25x22，于是 x41 + x42 = 1.1x31+ 1.25x22；第五年：年初有資金 1.1x41+ 1.25x32，于是 x51 = 1.1x41

46、+ 1.25x32； B、C、D的投資限制： xi2 30 ( i =1、2、3、4 )，x33 80，x24 100 3）目標(biāo)函數(shù)及模型：a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32； xi2 30 ( i =1、2、3、4 )，x33 80，x24 100 xij 0 ( i = 1、2、3

47、、4、5；j = 1、2、3、4） 71b)所設(shè)變量與問題a相同，目標(biāo)函數(shù)為風(fēng)險(xiǎn)最小，有 Min f =x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24 在問題a的約束條件中加上“第五年末擁有資金本利在330萬元”的條件，于是模型如下：Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x

48、31+ 1.25x22； x51 = 1.1x41+ 1.25x32； xi2 30 ( i =1、2、3、4 )，x33 80，x24 100 1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 330 xij 0 ( i = 1、2、3、4、5；j = 1、2、3、4）725投資問題第五章 單 純 形 法1單純形法的基本思路和原理2單純形法的表格形式3求目標(biāo)函數(shù)值最小的線性規(guī)劃的問題的 單純形表解法4幾種特殊情況731單純形法的基本思路和原理 單純形法的基本思路：從可行域中某一個(gè)頂點(diǎn)開始，判斷此頂點(diǎn)是否是最優(yōu)解，如不是,則再找另一個(gè)使得其目標(biāo)函數(shù)值更優(yōu)的頂點(diǎn)，稱之為迭代，再

49、判斷此點(diǎn)是否是最優(yōu)解。直到找到一個(gè)頂點(diǎn)為其最優(yōu)解，就是使得其目標(biāo)函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問題無最優(yōu)解為止。 通過第二章例1的求解來介紹單純形法: 在加上松弛變量之后我們可得到標(biāo)準(zhǔn)型如下： 目標(biāo)函數(shù)： max 50 x1+100 x2 約束條件：x1+x2+s1300， 2x1+x2+s2400， x2+s3250. xj0 （j=1，2）,sj0 （j=1，2,3）741單純形法的基本思路和原理它的系數(shù)矩陣 , 其中pj為系數(shù)矩陣A第j列的向量。A的秩為3,A的秩m小于此方程組的變量的個(gè)數(shù)n，為了找到一個(gè)初始基本可行解，先介紹以下幾個(gè)線性規(guī)劃的基本概念。 基： 已知A是約束條件的m

50、n系數(shù)矩陣，其秩為m。若B是A中mm階非奇異子矩陣（即可逆矩陣），則稱B是線性規(guī)劃問題中的一個(gè)基?；蛄浚夯鵅中的一列即稱為一個(gè)基向量?；鵅中共有m個(gè)基向量。 非基向量：在A中除了基B之外的一列則稱之為基B的非基向量?；兞浚号c基向量pi相應(yīng)的變量xi叫基變量，基變量有m個(gè)。751單純形法的基本思路和原理非基變量：與非基向量pj相應(yīng)的變量xj叫非基變量，非基變量有nm個(gè)。 由線性代數(shù)的知識(shí)知道，如果我們?cè)诩s束方程組系數(shù)矩陣中找到一個(gè)基，令這個(gè)基的非基變量為零，再求解這個(gè)m元線性方程組就可得到唯一的解了，這個(gè)解我們稱之為線性規(guī)劃的基本解。 在此例中我們不妨找到了 為A的一個(gè)基，令這個(gè)基的 非基變

51、量x，s2為零。這時(shí)約束方程就變?yōu)榛兞康募s束方程： 761單純形法的基本思路和原理 x2+s1300， x2=400， x2+s3=250. 求解得到此線性規(guī)劃的一個(gè)基本解：x1=0，x2=400，s1=100，s2=0，s3=150 由于在這個(gè)基本解中s1=100，s3=150，不滿足該線性規(guī)劃s10，s30的約束條件，顯然不是此線性規(guī)劃的可行解，一個(gè)基本解可以是可行解，也可以是非可行解，它們之間的主要區(qū)別在于其所有變量的解是否滿足非負(fù)的條件。我們把滿足非負(fù)條件的一個(gè)基本解叫做基本可行解，并把這樣的基叫做可行基。771單純形法的基本思路和原理 一般來說判斷一個(gè)基是否是可行基，只有在求出其基

52、本解以后，當(dāng)其基本解所有變量的解都是大于等于零，才能斷定這個(gè)解是基本可行解，這個(gè)基是可行基。那么我們能否在求解之前，就找到一個(gè)可行基呢？也就是說我們找到的一個(gè)基能保證在求解之后得到的解一定是基本可行解呢？由于在線性規(guī)劃的標(biāo)準(zhǔn)型中要求bj都大于等于零，如果我們能找到一個(gè)基是單位矩陣，或者說一個(gè)基是由單位矩陣的各列向量所組成（至于各列向量的前后順序是無關(guān)緊要的事）例如，那么顯然所求得的基本解一定是基本可行解，這個(gè)單位矩陣或由單位矩陣各列向量組成的基一定是可行基。實(shí)際上這個(gè)基本可行解中的各個(gè)變量或等于某個(gè)bj或等于零。 781單純形法的基本思路和原理 在本例題中我們就找到了一個(gè)基是單位矩陣。 在第一

53、次找可行基時(shí)，所找到的基或?yàn)閱挝痪仃嚮驗(yàn)橛蓡挝痪仃嚨母髁邢蛄克M成，稱之為初始可行基，其相應(yīng)的基本可行解叫初始基本可行解。如果找不到單位矩陣或由單位矩陣的各列向量組成的基作為初始可行基，我們將構(gòu)造初始可行基，具體做法在以后詳細(xì)講述。791單純形法的基本思路和原理二、 最優(yōu)性檢驗(yàn) 所謂最優(yōu)性檢驗(yàn)就是判斷已求得的基本可行解是否是最優(yōu)解。1. 最優(yōu)性檢驗(yàn)的依據(jù)檢驗(yàn)數(shù)j 一般來說目標(biāo)函數(shù)中既包括基變量，又包括非基變量。現(xiàn)在我們要求只用非基變量來表示目標(biāo)函數(shù)，這只要在約束等式中通過移項(xiàng)等處理就可以用非基變量來表示基變量，然后用非基變量的表示式代替目標(biāo)函數(shù)中基變量，這樣目標(biāo)函數(shù)中只含有非基變量了，或者說目

54、標(biāo)函數(shù)中基變量的系數(shù)都為零了。此時(shí)目標(biāo)函數(shù)中所有變量的系數(shù)即為各變量的檢驗(yàn)數(shù)，把變量xi的檢驗(yàn)數(shù)記為i。顯然所有基變量的檢驗(yàn)數(shù)必為零。在本例題中目標(biāo)函數(shù)為50 x1+100 x2。由于初始可行解中x1，x2為非基變量，所以此目標(biāo)函數(shù)已經(jīng)用非基變量表示了，不需要再代換出基變量了。這樣我們可知1=50，2=100，3=0，4=0，5=0。801單純形法的基本思路和原理2.最優(yōu)解判別定理 對(duì)于求最大目標(biāo)函數(shù)的問題中，對(duì)于某個(gè)基本可行解，如果所有檢驗(yàn)數(shù) 0，則這個(gè)基本可行解是最優(yōu)解。下面我們用通俗的說法來解釋最優(yōu)解判別定理。設(shè)用非基變量表示的目標(biāo)函數(shù)為如下形式 由于所有的xj的取值范圍為大于等于零，當(dāng)

55、所有的 都小 于等于零時(shí)，可知 是一個(gè)小于等于零的數(shù)，要使z 的值最大，顯然 只有為零。我們把這些xj取為非基 變量(即令這些xj的值為零)，所求得的基本可行解就使目標(biāo)函數(shù)值最大為z0。*對(duì)于求目標(biāo)函數(shù)最小值的情況，只需把 0改為 0811單純形法的基本思路和原理三、 基變換 通過檢驗(yàn)，我們知道這個(gè)初始基本可行解不是最優(yōu)解。下面介紹如何進(jìn)行基變換找到一個(gè)新的可行基，具體的做法是從可行基中換一個(gè)列向量，得到一個(gè)新的可行基，使得求解得到的新的基本可行解，其目標(biāo)函數(shù)值更優(yōu)。為了換基就要確定換入變量與換出變量。1. 入基變量的確定 從最優(yōu)解判別定理知道，當(dāng)某個(gè)j0時(shí)，非基變量xj變?yōu)榛兞坎蝗×阒悼梢?/p>

56、使目標(biāo)函數(shù)值增大，故我們要選基檢驗(yàn)數(shù)大于0的非基變量換到基變量中去（稱之為入基變量）。若有兩個(gè)以上的j0，則為了使目標(biāo)函數(shù)增加得更大些，一般選其中的j最大者的非基變量為入基變量，在本例題中2=100是檢驗(yàn)數(shù)中最大的正數(shù)，故選x2為入基變量。821單純形法的基本思路和原理2. 出基變量的確定 在確定了x2為入基變量之后，我們要在原來的3個(gè)基變量s1，s2，s3中確定一個(gè)出基變量，也就是確定哪一個(gè)基變量變成非基變量呢？ 如果把s3作為出基變量，則新的基變量為x2，s1，s2，因?yàn)榉腔兞縳1=s3=0， 我們也可以從下式： x2 +s1=300， x2+s2=400， x2=250， 求出基本解：

57、x1=0，x2=250，s1=50，s2=150，s3=0。因?yàn)榇私鉂M足非負(fù)條件，是基本可行解，故s3可以確定為出基變量。 能否在求出基本解以前來確定出基變量呢？ 以下就來看在找出了初始基本可行解和確定了入基變量之后，怎么樣的基變量可以確定為出基變量呢？或者說出基變量要具有什么條件呢？ 831單純形法的基本思路和原理 我們把確定出基變量的方法概括如下：把已確定的入基變量在各約束方程中的正的系數(shù)除以其所在約束方程中的常數(shù)項(xiàng)的值，把其中最小比值所在的約束方程中的原基變量確定為出基變量。這樣在下一步迭代的矩陣變換中可以確保新得到的bj值都大于等于零。 在本例題中約束方程為 在第二步中已經(jīng)知道x2為入

58、基變量，我們把各約束方程中x2的為正的系數(shù)除對(duì)應(yīng)的常量，得841單純形法的基本思路和原理 其中 的值最小，所以可以知道在原基變量中系數(shù)向量為 的基變量s3為出基變量，這樣可知x2，s1，s2為基變量，x1，s3為非基變量。 令非基變量為零，得 x2+s1=300, x2+s2=400, x2=250. 求解得到新的基本可行解x1=0,x2=250,s1=50,s2=150. 這時(shí)目標(biāo)函數(shù)值為 50 x1+100 x2=500+100250=25000。 顯然比初始基本可行解x1=0,x2=0,s1=300,s3=250時(shí)的目標(biāo)函數(shù)值為0要好得多。 下面我們?cè)龠M(jìn)行檢驗(yàn)其最優(yōu)性，如果不是最優(yōu)解還要

59、繼續(xù)進(jìn)行基變換，直至找到最優(yōu)解，或者能夠判斷出線性規(guī)劃無最優(yōu)解為止。852單純形法的表格形式 在講解單純形法的表格形式之前，先從一般數(shù)學(xué)模型里推導(dǎo)出檢驗(yàn)數(shù) 的表達(dá)式。 可行基為m階單位矩陣的線性規(guī)劃模型如下（假設(shè)其系數(shù)矩陣的前m列是單位矩陣）： 以下用 表示基變量，用 表示非基變量。862單純形法的表格形式 把第i個(gè)約束方程移項(xiàng)，就可以用非基變量來表示基變量xi， 把以上的表達(dá)式帶入目標(biāo)函數(shù)，就有 其中：872單純形法的表格形式 上面假設(shè)x1,x2,xm是基變量，即第i行約束方程的基變量正好是xi，而經(jīng)過迭代后，基將發(fā)生變化，計(jì)算zj的式子也會(huì)發(fā)生變化。如果迭代后的第i行約束方程中的基變量為x

60、Bi，與xBi相應(yīng)的目標(biāo)函數(shù)系數(shù)為cBi，系數(shù)列向量為 則 其中，(cB)是由第1列第m行各約束方程中的基變量相應(yīng)的目標(biāo)函數(shù)依次組成的有序行向量。 單純形法的表格形式是把用單純形法求出基本可行解、檢驗(yàn)其最優(yōu)性、迭代某步驟都用表格的方式來計(jì)算求出，其表格的形式有些像增廣矩陣，而其計(jì)算的方法也大體上使用矩陣的行的初等變換。以下用單純形表格來求解第二章的例1。 max 50 x1+100 x2+0s1+0s2+0s3. x1+x2+s1=300， 2x1+x2+s2=400， x2+s3=250， x1, x2, s1, s2, s30. 把上面的數(shù)據(jù)填入如下的單純形表格882單純形法的表格形式按照