運(yùn)籌學(xué)第二章-線性規(guī)劃

1、2020/7/15,.,1,Chapter2 線性規(guī)劃及單純形法 (Linear Programming),LP的數(shù)學(xué)模型 圖解法 單純形法 單純形法的進(jìn)一步討論人工變量法 LP模型的應(yīng)用,本章主要內(nèi)容：,2020/7/15,.,2,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,1. 規(guī)劃問(wèn)題,生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問(wèn)題。,線性規(guī)劃通常解決下列兩類(lèi)問(wèn)題：,（1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源 （如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo),（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)

2、濟(jì)效益（如產(chǎn)品量最多 、利潤(rùn)最大.）,2020/7/15,.,3,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,例1.1 如圖所示，如何截取x使鐵皮所圍成的容積最大？,2020/7/15,.,4,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,例1.2 某廠生產(chǎn)兩種產(chǎn)品，下表給出了單位產(chǎn)品所需資源及單位產(chǎn)品利潤(rùn),問(wèn)：應(yīng)如何安排生產(chǎn)計(jì)劃，才能使總利潤(rùn)最大？,解：,1.決策變量：設(shè)產(chǎn)品I、II的產(chǎn)量 分別為 x1、x2,2.目標(biāo)函數(shù)：設(shè)總利潤(rùn)為z，則有： max z = 2 x1 + x2,3.約束條件：,2020/7/15,.,5,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,例1.3 已知資料如下表所示，問(wèn)如何安排生產(chǎn)才能使利潤(rùn)最大？,解：,1.決策變量：設(shè)產(chǎn)

3、品I、II的產(chǎn)量分別為 x1、x2,2.目標(biāo)函數(shù)：設(shè)總利潤(rùn)為z，則有： max z = 2 x1 + 3x2,3.約束條件：,2020/7/15,.,6,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,例1.4 某廠生產(chǎn)三種藥物，這些藥物可以從四種不同的原料中提取。下表給出了單位原料可提取的藥物量,解：,要求：生產(chǎn)A種藥物至少160單位；B種藥物恰好200單位，C種藥物不超過(guò)180單位，且使原料總成本最小。,1.決策變量：設(shè)四種原料的使用 量分別為：x1、x2 、x3 、x4,2.目標(biāo)函數(shù)：設(shè)總成本為z min z = 5 x1 + 6 x2 + 7 x3 + 8 x4,3.約束條件：,2020/7/15,.,7,例

4、1.5 某航運(yùn)局現(xiàn)有船只種類(lèi)、數(shù)量以及計(jì)劃期內(nèi)各條航線的貨運(yùn)量、貨運(yùn)成本如下表所示：,問(wèn)：應(yīng)如何編隊(duì)，才能既完成合同任務(wù)，又使總貨運(yùn)成本為最小？,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,2020/7/15,.,8,解：,設(shè)：xj為第j號(hào)類(lèi)型船隊(duì)的隊(duì)數(shù)（j = 1，2，3，4）， z 為總貨運(yùn)成本,則： min z = 36x1 + 36x2 + 72x3 + 27x4,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,2020/7/15,.,9,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,2. 線性規(guī)劃的數(shù)學(xué)模型由三個(gè)要素構(gòu)成,決策變量 Decision variables 目標(biāo)函數(shù) Objective function 約束條件 Constraints

5、,其特征是： （1）問(wèn)題的目標(biāo)函數(shù)是多個(gè)決策變量的線性函數(shù)，通常是求最大值或最小值； （2）問(wèn)題的約束條件是一組多個(gè)決策變量的線性不等式或等式。,怎樣辨別一個(gè)模型是線性規(guī)劃模型？,2020/7/15,.,10,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,3. 建模條件,(1) 優(yōu)化條件：?jiǎn)栴}所要達(dá)到的目標(biāo)能用線型函數(shù)描述，且能夠用極值（max 或 min）來(lái)表示；,(2) 限定條件：達(dá)到目標(biāo)受到一定的限制，且這些限制能夠用決策變量的線性等式或線性不等式表示；,(3) 選擇條件：有多種可選擇的方案供決策者選擇，以便找出最優(yōu)方案。,2020/7/15,.,11,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,4. 建模步驟,(1) 確定決策

6、變量：即需要我們作出決策或選擇的量。一般情況下，題目問(wèn)什么就設(shè)什么為決策變量；,(2) 找出所有限定條件：即決策變量受到的所有的約束；,(3) 寫(xiě)出目標(biāo)函數(shù)：即問(wèn)題所要達(dá)到的目標(biāo)，并明確是max 還是 min。,2020/7/15,.,12,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,目標(biāo)函數(shù)：,約束條件：,5. 線性規(guī)劃數(shù)學(xué)模型的一般形式,簡(jiǎn)寫(xiě)為：,2020/7/15,.,13,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,向量形式：,其中：,2020/7/15,.,14,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,矩陣形式：,其中：,2020/7/15,.,15,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,6. 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式,特點(diǎn)： 目標(biāo)函數(shù)求最大值； (2)

7、 約束條件為等式方程，且右端常數(shù)項(xiàng)bi都大于或等于零； (3) 決策變量xj為非負(fù)。,2020/7/15,.,16,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,（2）如何化標(biāo)準(zhǔn)形式,目標(biāo)函數(shù)的轉(zhuǎn)換,如果是求極小值即 ，則可將目標(biāo)函數(shù)乘以 (-1)，可化為求極大值問(wèn)題。,也就是：令 ，可得到上式。,即,若存在取值無(wú)約束的變量 ，可令 其中：,變量的變換,2020/7/15,.,17,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。,稱(chēng)為松弛變量,稱(chēng)為剩余變量,常量 bi0 的變換:約束方程兩邊乘以（1）,2020/7/15,.,18,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,例1.6 將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式,用

8、替換 ，且,解:（）因?yàn)閤3無(wú)符號(hào)要求 ，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以,2020/7/15,.,19,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,(2) 第一個(gè)約束條件是“”號(hào)，在“”左端加入松馳變量x4，x40,化為等式； (3) 第二個(gè)約束條件是“”號(hào)，在“”左端減去剩余變量x5，x50； (4) 第3個(gè)約束方程右端常數(shù)項(xiàng)為-5，方程兩邊同乘以(-1),將右端常數(shù)項(xiàng)化為正數(shù)； (5) 目標(biāo)函數(shù)是最小值，為了化為求最大值，令z=-z,得到max z=-z，即當(dāng)z達(dá)到最小值時(shí)z達(dá)到最大值，反之亦然;,2020/7/15,.,20,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,標(biāo)準(zhǔn)形式如下：,2020/7/15,.

9、,21,例1.7 將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式,為無(wú)約束（無(wú)非負(fù)限制）,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,2020/7/15,.,22,解:,標(biāo)準(zhǔn)形式如下：,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,2020/7/15,.,23,例1.8 將線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型,解：,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,無(wú)約束,2020/7/15,.,24,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,7. 線性規(guī)劃問(wèn)題的解,線性規(guī)劃問(wèn)題,求解線性規(guī)劃問(wèn)題，就是從滿足約束條件(2)、(3)的方程組中找出一個(gè)解，使目標(biāo)函數(shù)(1)達(dá)到最大值。,2020/7/15,.,25,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,可行解：滿足約束條件、的解為可行解。所有可行解的集合為可行域。 最優(yōu)解：使

10、目標(biāo)函數(shù)達(dá)到最大值的可行解。 基：設(shè)A為約束條件的mn階系數(shù)矩陣(mn)，其秩為m，B是矩陣A中m階滿秩子矩陣（B0），稱(chēng)B是規(guī)劃問(wèn)題的一個(gè)基矩陣，簡(jiǎn)稱(chēng)基。設(shè)：,稱(chēng) B中每個(gè)列向量Pj ( j = 1 2 m) 為基向量。與基向量Pj 對(duì)應(yīng)的變量xj 為基變量。除基變量以外的變量為非基變量。,2020/7/15,.,26,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,基解：某一確定的基B，令非基變量等于零，由約束條件方程解出基變量，稱(chēng)這組解為基解。在基解中變量取非0值的個(gè)數(shù)不大于方程數(shù)m，基解的總數(shù)不超過(guò) 基可行解：滿足變量非負(fù)約束條件的基本解，簡(jiǎn)稱(chēng)基可行解。 可行基：對(duì)應(yīng)于基可行解的基稱(chēng)為可行基。,2020/7/

11、15,.,27,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,例1.10 求線性規(guī)劃問(wèn)題的所有基矩陣。,解: 約束方程的系數(shù)矩陣為25矩陣,r(A)=2，2階子矩陣有10個(gè)，其中基矩陣只有9個(gè)，即,2020/7/15,.,28,圖解法,線性規(guī)劃問(wèn)題的求解方法,一 般 有 兩種方法,圖 解 法 單純形法,兩個(gè)變量、直角坐標(biāo) 三個(gè)變量、立體坐標(biāo),適用于任意變量、但必需將 一般形式變成標(biāo)準(zhǔn)形式,下面我們分析一下簡(jiǎn)單的情況 只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題，這時(shí)可以通過(guò)圖解的方法來(lái)求解。圖解法具有簡(jiǎn)單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點(diǎn)。,2020/7/15,.,29,解題步驟,4. 確定目標(biāo)函數(shù)值增大（或

12、減?。┓较颍?1. 作出平面直角平面坐標(biāo)系；,2. 根據(jù)約束條件找出可行域；,3. 作出目標(biāo)函數(shù)線；,圖解法,5. 讓目標(biāo)函數(shù)線沿著增大（或減?。┓较蚱叫幸苿?dòng)，與 可行域相交且有最大（或最小）目標(biāo)函數(shù)值的頂點(diǎn)，即為最優(yōu)值。,2020/7/15,.,30,圖解法,max Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8 s.t. X1 + 1.9X2 10.2 X1 - 1.9X2 -3.8 X1 ，X2 0,例1.11 用圖解法求解線性規(guī)劃問(wèn)題,2020/7/15,.,31,圖解法,x1,x2,o,X1 - 1.9X2 = 3.8(),X1 + 1.9X2

13、= 3.8(),X1 - 1.9X2 = -3.8 (),X1 + 1.9X2 = 10.2(),4 = 2X1 + X2,20 = 2X1 + X2,17.2 = 2X1 + X2,11 = 2X1 + X2,Lo： 0 = 2X1 + X2,（7.6，2）,D,max Z,min Z,此點(diǎn)是唯一最優(yōu)解， 且最優(yōu)目標(biāo)函數(shù)值 max Z=17.2,可行域,max Z = 2X1 + X2,2020/7/15,.,32,圖解法,max Z=3X1+5.7X2,x1,x2,o,X1 - 1.9X2 = 3.8 (),X1 + 1.9X2 = 3.8(),X1 - 1.9X2 = -3.8(),X1

14、 + 1.9X2 = 10.2 (),（7.6，2）,D,L0： 0=3X1+5.7X2,max Z,（3.8，4）,34.2 = 3X1+5.7X2,藍(lán)色線段上的所有點(diǎn)都是最 優(yōu)解這種情形為有無(wú)窮多最 優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值 max Z=34.2是唯一的。,可行域,2020/7/15,.,33,圖解法,min Z=5X1+4X2,x1,x2,o,X1 - 1.9X2 = 3.8 (),X1 + 1.9X2 = 3.8(),X1 + 1.9X2 = 10.2 (),D,L0： 0=5X1+4X2,max Z,min Z,8=5X1+4X2,43=5X1+4X2,（0，2）,可行域,此點(diǎn)是唯一

15、最優(yōu)解,2020/7/15,.,34,圖解法,2,4,6,x1,x2,2,4,6,無(wú)界解(無(wú)最優(yōu)解),max Z=x1+2x2,例1.12,x1+x2=4(),x1+3x2=6(),3x1+x2=6(),max Z,min Z,x1,x2,O,10,20,30,40,10,20,30,40,50,50,無(wú)可行解(即無(wú)最優(yōu)解),max Z=3x1+4x2,例1.13,2020/7/15,.,36,由圖解法得到的啟示,(1) 線性規(guī)劃問(wèn)題解的情況：唯一最優(yōu)解；無(wú)窮多最優(yōu)解；無(wú)界解；無(wú)可行解,(3) 最優(yōu)解或最優(yōu)解之一一定是在凸集的某個(gè)頂點(diǎn),(2) 線性規(guī)劃問(wèn)題的可行域是凸集,(4) 解題思路是，先

16、找出凸集的任一頂點(diǎn)，計(jì)算其目標(biāo)函數(shù)值，再與周?chē)旤c(diǎn)的目標(biāo)函數(shù)值比較，如不是最大，繼續(xù)比較，直到找出最大為止。,圖解法,2020/7/15,.,37,圖解法,學(xué)習(xí)要點(diǎn)： 1. 通過(guò)圖解法了解線性規(guī)劃有幾種解的形式 （唯一最優(yōu)解；無(wú)窮多最優(yōu)解；無(wú)界解；無(wú)可行解） 2. 作圖的關(guān)鍵有三點(diǎn)： (1) 可行解區(qū)域要畫(huà)正確 (2) 目標(biāo)函數(shù)增大(或減小)的方向不能畫(huà)錯(cuò) (3) 目標(biāo)函數(shù)的直線怎樣平行移動(dòng),2020/7/15,.,38,連接幾何形體中任意兩點(diǎn)的線段仍完全在該幾何形體之中。 有限個(gè)凸集的交集仍然是凸集。,單純形法基本原理,2020/7/15,.,39,單純形法基本原理,凸集：如果集合C中任意兩

17、個(gè)點(diǎn)X1、X2，其連線上的所有點(diǎn)也都是集合C中的點(diǎn)，稱(chēng)C為凸集。,頂點(diǎn)：如果凸集C中不存在任何兩個(gè)不同的點(diǎn)X1，X2，使X成為這兩個(gè)點(diǎn)連線上的一個(gè)點(diǎn),2020/7/15,.,40,單純形法基本原理,定理1：若線性規(guī)劃問(wèn)題存在可行解，則該問(wèn)題的可行域是凸集。 定理2：線性規(guī)劃問(wèn)題的基可行解X對(duì)應(yīng)可行域(凸集)的頂點(diǎn)。 定理3：若問(wèn)題存在最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解。（或在某個(gè)頂點(diǎn)取得）,2020/7/15,.,41,單純形法的計(jì)算步驟,單純形法的思路,找出一個(gè)初始基可行解,是否最優(yōu),轉(zhuǎn)移到另一個(gè)基可行解 （找出更大的目標(biāo)函數(shù)值）,最優(yōu)解,是,否,循 環(huán),核心是：變量迭代,結(jié)束,單純形舉例

18、.ppt,2020/7/15,.,42,單純形法的計(jì)算步驟,例1.12 用單純形法求下列線性規(guī)劃的最優(yōu)解,解：1）將問(wèn)題化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4則標(biāo)準(zhǔn)型為:,2020/7/15,.,43,單純形法的計(jì)算步驟,2）求出線性規(guī)劃的初始基可行解，列出初始單純形表。,檢驗(yàn)數(shù),2020/7/15,.,44,單純形法的計(jì)算步驟,3）進(jìn)行最優(yōu)性檢驗(yàn),如果表中所有檢驗(yàn)數(shù) ，則表中的基可行解就是問(wèn)題的最優(yōu)解，計(jì)算停止。否則繼續(xù)下一步。,4）從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)值更大的基可行解，列出新的單純形表,確定換入基的變量。 一般選擇最大的一個(gè)檢驗(yàn)數(shù)，即： ，其對(duì)應(yīng)的xk作為換入變量。 確定換出變量。根

19、據(jù)下式計(jì)算并選擇 ，選最小的對(duì)應(yīng)基變量作為換出變量。,2020/7/15,.,45,單純形法的計(jì)算步驟,用換入變量xk替換基變量中的換出變量，得到一個(gè)新的基。對(duì)應(yīng)新的基可以找出一個(gè)新的基可行解，并相應(yīng)地可以畫(huà)出一個(gè)新的單純形表。 5）重復(fù)3）、4）步直到計(jì)算結(jié)束為止。,2020/7/15,.,46,單純形法的計(jì)算步驟,入基,bi /ai2，ai20,40,10,出基,將3化為1,5/3,1,18,0,1/3,0,1/3,10,1,1/3,30,30,0,5/3,0,4/3,乘以1/3后得到,1,0,3/5,1/5,18,0,1,1/5,2/5,4,0,0,1,1,2020/7/15,.,47,

20、單純形法的計(jì)算步驟,例1.13 用單純形法求解,解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：,不難看出x4、x5可作為初始基變量，列單純形表計(jì)算。,2020/7/15,.,48,單純形法的計(jì)算步驟,20,x2,2,1/3,1,5,0,1,20,75,3,0,17,1,3,1/3,0,9,0,2,25,60,x1,1,1,0,17/3,1/3,1,25,0,1,28/9,-1/9,2/3,35/3,0,0,-98/9,-1/9,-7/3,2020/7/15,.,49,變成標(biāo)準(zhǔn)型,單純形法的計(jì)算步驟,例1.14 用單純形法求解,2020/7/15,.,50,約束方程的系數(shù)矩陣,為基變量,為非基變量,I 為單位矩陣

21、且線性獨(dú)立,單純形法的計(jì)算步驟,2020/7/15,.,51,2020/7/15,.,52,2020/7/15,.,53,2020/7/15,.,54,單純形法的計(jì)算步驟,學(xué)習(xí)要點(diǎn)： 1. 線性規(guī)劃解的概念以及3個(gè)基本定理 2. 熟練掌握線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)化 3.熟練掌握單純形法的解題思路及求解步驟,2020/7/15,.,55,單純形法的進(jìn)一步討論人工變量法,人工變量法： 前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實(shí)際問(wèn)題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱(chēng)為人工變量，構(gòu)成的

22、可行基稱(chēng)為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱(chēng)為人工變量法。,2020/7/15,.,56,單純形法的進(jìn)一步討論人工變量法,例1.10 用大M法解下列線性規(guī)劃,解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式,系數(shù)矩陣中不存在單位矩陣，無(wú)法建立初始單純形表。,2020/7/15,.,57,單純形法的進(jìn)一步討論人工變量法,故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：,其中：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見(jiàn)下表。,2020/7/15,.,58,單純形法的進(jìn)一步討論人工變量法,20

23、20/7/15,.,59,單純形法的進(jìn)一步討論人工變量法,例1.11 用大M法解下列線性規(guī)劃,解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式,系數(shù)矩陣中不存在單位矩陣，無(wú)法建立初始單純形表。,2020/7/15,.,60,單純形法的進(jìn)一步討論人工變量法,故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：,其中：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見(jiàn)下表。,2020/7/15,.,61,單純形法的進(jìn)一步討論人工變量法,2020/7/15,.,62,單純形法的進(jìn)一步討論人工變量法,2020/7/15,.,63,單純形

24、法的進(jìn)一步討論,通過(guò)大法或兩階段法求初始的基本可行解。但是如果在大法的最優(yōu)單純形表的基變量中仍含有人工變量，那么該線性規(guī)劃就不存在可行解。,無(wú)可行解,2020/7/15,.,64,C,-3 -2 -1 0 0 0 -M -M,CB,XB,b,x1 x2 x3 x4 x5 x6 x7 x8,0 -M -M,x4 x7 x8,6 4 3,1 1 1 1 0 0 0 0 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1,6/1 - 3/1,Z,-7M,-6-4M,-15-M,-3+M -2+M -1-2M 0 -M -M 0 0,0 -M -2,x4 x7 x2,3 4 3,1

25、 0 2 1 0 1 0 -1 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1,3/1 4/1 -,Z,Z,-3+M 0 -3-M 0 -M -2 0 2-M,-3 -M -2,x1 x7 x2,3 1 3,1 0 2 1 0 1 0 -1 0 0 -3 -1 -1 -1 1 1 0 1 -1 0 0 -1 0 1,0 0 3-3M 3-M -M 1-M 0 -1,例,單純形法的進(jìn)一步討論,運(yùn)算到檢驗(yàn)數(shù)全負(fù)為止，仍含有人工變量，無(wú)可行解。,2020/7/15,.,65,單純形法的進(jìn)一步討論,無(wú)可行解是指原規(guī)劃不存在可行解，從幾何的角度解釋是指 線性規(guī)劃問(wèn)題的可行域?yàn)榭占?/p>

26、； 無(wú)界解則是指線性規(guī)劃問(wèn)題存在可行解，但是可行解的目 標(biāo)函數(shù)達(dá)不到最優(yōu)值，即目標(biāo)函數(shù)在可行域內(nèi)趨于無(wú)窮大。 判別方法：無(wú)界解判定定理 在求解極大化的線性規(guī)劃問(wèn)題過(guò)程中，若某單純形表的檢驗(yàn) 行存在某個(gè)大于零的檢驗(yàn)數(shù)，但是該檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量 的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零，則該線性規(guī)劃問(wèn)題 無(wú)界解,無(wú)界解,2020/7/15,.,66,因 但 所以原問(wèn)題無(wú)界解,單純形法的進(jìn)一步討論,2020/7/15,.,67,退化,即計(jì)算出的 （用于確定換出變量）存在有兩個(gè)以上相同的最小比值，會(huì)造成下一次迭代中由一個(gè)或幾個(gè)基變量等于零，這就是退化（會(huì)產(chǎn)生退化解）。 為避免出現(xiàn)計(jì)算的循環(huán)，勃蘭特(Bl

27、and)提出一個(gè)簡(jiǎn)便有效的規(guī)則（攝動(dòng)法原理）： 當(dāng)存在多個(gè) 時(shí)，選下標(biāo)最小的非基變量為換入變量； (2) 當(dāng)值出現(xiàn)兩個(gè)以上相同的最小值時(shí)，選下標(biāo)最小的基變量為換出變量。,單純形法的進(jìn)一步討論,2020/7/15,.,68,無(wú)窮多最優(yōu)解,若線性規(guī)劃問(wèn)題某個(gè)基本可行解所有的非基變量檢驗(yàn)數(shù)都小于等于零，但其中存在一個(gè)檢驗(yàn)數(shù)等于零，那么該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。 例：最優(yōu)表： 非基變量檢驗(yàn) 數(shù)，所以有無(wú)窮多 最優(yōu)解。,單純形法的進(jìn)一步討論,2020/7/15,.,69,單純形法的進(jìn)一步討論,單純性法小結(jié):,2020/7/15,.,70,線性規(guī)劃模型的應(yīng)用,一般而言，一個(gè)經(jīng)濟(jì)、管理問(wèn)題凡是滿足以下條

28、件時(shí)，才能建立線性規(guī)劃模型。,要求解問(wèn)題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來(lái)反映，且為線性函數(shù) 存在著多種方案 要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些約束可用線性等式或不等式描述,2020/7/15,.,71,線性規(guī)劃模型的應(yīng)用,常見(jiàn)問(wèn)題,合理利用線材問(wèn)題：如何下料使用材最少。 配料問(wèn)題：在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)。 投資問(wèn)題：從投資項(xiàng)目中選取方案，使投資回報(bào)最大。 產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、財(cái)力等，使獲利最大。 勞動(dòng)力安排：用最少的勞動(dòng)力來(lái)滿足工作的需要。 運(yùn)輸問(wèn)題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小。,2020/7/15,.,72,線性規(guī)劃模型的應(yīng)用,(1)設(shè)立決策變量； (2)明確約束條件并用決策變量的線性等式或不等式表示； (3)用決策變量的線性函數(shù)表示目標(biāo)，并確定是求極大（Max）還是極?。∕in）； (4)根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性。,建立線性規(guī)劃模型的過(guò)程可以分為四個(gè)步驟：,20