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

1、2021-12-41Chapter2 線性規(guī)劃及單純形法線性規(guī)劃及單純形法 (Linear Programming) LP的數(shù)學(xué)模型的數(shù)學(xué)模型 圖解法圖解法 單純形法單純形法 單純形法的進(jìn)一步討論人工變量法單純形法的進(jìn)一步討論人工變量法 LP模型的應(yīng)用模型的應(yīng)用2021-12-421. 規(guī)劃問題規(guī)劃問題生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合理安排，使人力、生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。這就是規(guī)劃問題。（1 1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)

2、籌兼顧，合理安排，用最少的資源最少的資源 （如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）（如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo)去完成確定的任務(wù)或目標(biāo)（2 2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多好的經(jīng)濟(jì)效益（如產(chǎn)品量最多 、利潤(rùn)最大、利潤(rùn)最大. .）2021-12-43例例1.1 如圖所示，如何截取如圖所示，如何截取x使鐵皮所圍成的容積最使鐵皮所圍成的容積最大？大？ x xa a xxav 220 dxdv0)2()2()2(22 xaxxa6ax 2021-12-44例例1.2 某廠生產(chǎn)兩種

3、產(chǎn)品，某廠生產(chǎn)兩種產(chǎn)品，下表給出了單位產(chǎn)品所需資下表給出了單位產(chǎn)品所需資源及單位產(chǎn)品利潤(rùn)源及單位產(chǎn)品利潤(rùn) 問：應(yīng)如何安排生產(chǎn)計(jì)劃，才問：應(yīng)如何安排生產(chǎn)計(jì)劃，才能使總利潤(rùn)最大？能使總利潤(rùn)最大？ 解：解：1.1.決策變量：設(shè)產(chǎn)品決策變量：設(shè)產(chǎn)品I I、IIII的產(chǎn)量的產(chǎn)量 分別為分別為 x1、x22.2.目標(biāo)函數(shù)：設(shè)總利潤(rùn)為目標(biāo)函數(shù)：設(shè)總利潤(rùn)為z z，則有：，則有： max z = 2 x1 + x23.3.約束條件：約束條件： 5x2 15 6x1+ 2x2 24 x1+ x2 5 x1， x202021-12-45例例1.3 已知資料如下表所示，已知資料如下表所示，問如何安排生產(chǎn)才能使利潤(rùn)問如

4、何安排生產(chǎn)才能使利潤(rùn)最大？最大？ 設(shè)設(shè) 備備產(chǎn)產(chǎn) 品品 A B C D利潤(rùn)利潤(rùn)（元）（元） 2 1 4 0 2 2 2 0 4 3 有有 效效 臺(tái)臺(tái) 時(shí)時(shí)12 8 16 12解：解：1.1.決策變量：設(shè)產(chǎn)品決策變量：設(shè)產(chǎn)品I I、IIII的產(chǎn)量的產(chǎn)量分別為分別為 x1、x22.2.目標(biāo)函數(shù)：設(shè)總利潤(rùn)為目標(biāo)函數(shù)：設(shè)總利潤(rùn)為z z，則，則有：有： max z = 2 x1 + 3x23.3.約束條件：約束條件： x1 0 , x2 0 2x1 + 2x2 12 x1 + 2x2 8 4x1 16 4x2 122021-12-46例例1.4 某廠生產(chǎn)三種藥物，某廠生產(chǎn)三種藥物，這些藥物可以從四種不同

5、的這些藥物可以從四種不同的原料中提取。下表給出了單原料中提取。下表給出了單位原料可提取的藥物量位原料可提取的藥物量 解：解：要求：生產(chǎn)要求：生產(chǎn)A種藥物至少種藥物至少160單位；單位；B種藥物恰好種藥物恰好200單位，單位，C種藥物不超過(guò)種藥物不超過(guò)180單位，且單位，且使原料總成本最小。使原料總成本最小。1.1.決策變量：設(shè)四種原料的使用決策變量：設(shè)四種原料的使用 量分別為：量分別為：x1、x2 、x3 、x42.2.目標(biāo)函數(shù)：設(shè)總成本為目標(biāo)函數(shù)：設(shè)總成本為z min z = 5 x1 + 6 x2 + 7 x3 + 8 x43.3.約束條件：約束條件： x1 + 2x2 + x3 + x4

6、 160 2x1 +4 x3 +2 x4 200 3x1 x2 +x3 +2 x4 180 x1、x2 、x3 、x4 02021-12-47 例例1.5 某航運(yùn)局現(xiàn)有船只種類、數(shù)量以及計(jì)劃期內(nèi)各條航某航運(yùn)局現(xiàn)有船只種類、數(shù)量以及計(jì)劃期內(nèi)各條航線的貨運(yùn)量、貨運(yùn)成本如下表所示：線的貨運(yùn)量、貨運(yùn)成本如下表所示：航線號(hào)航線號(hào)船隊(duì)船隊(duì)類型類型編隊(duì)形式編隊(duì)形式貨運(yùn)成本貨運(yùn)成本（千元隊(duì)）（千元隊(duì)）貨運(yùn)量貨運(yùn)量（千噸）（千噸）拖輪拖輪A型型駁船駁船B型型駁船駁船1112362521436202322472404142720船只種類船只種類船只數(shù)船只數(shù)拖拖 輪輪30A型駁船型駁船34B型駁船型駁船52航線號(hào)航

7、線號(hào)合同貨運(yùn)量合同貨運(yùn)量12002400問：應(yīng)如何編隊(duì)，才能既完成合同任務(wù)，又使總貨運(yùn)成本為最??？問：應(yīng)如何編隊(duì)，才能既完成合同任務(wù)，又使總貨運(yùn)成本為最?。?021-12-48 解：解：設(shè)：設(shè)：x xj j為第為第j j號(hào)類型船隊(duì)的隊(duì)數(shù)（號(hào)類型船隊(duì)的隊(duì)數(shù)（j = 1j = 1，2 2，3 3，4 4），）， z z 為總貨運(yùn)成本為總貨運(yùn)成本則：則： min z = 36x1 + 36x2 + 72x3 + 27x4 x1 + x2 + 2x3 + x4 30 2x1 + 2x3 34 4x2 + 4x3 + 4x4 5225x1+20 x2 200 40 x3+20 x4 400 xj 0 （

8、 j = 1,2,3,4）2021-12-492021-12-4102021-12-4112021-12-41200 )( )( (min) max12211112121112211 nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz)21(j 0 )21(i )( Z (min)max 11nxmbxaxcjnjijijnjjj 簡(jiǎn)寫為：簡(jiǎn)寫為：2021-12-413) (21ncccC nxxX1 mjjjaaP1 mbbB1 0 )( (min) maxXBxpCXzjj其中：其中：2021-12-414 mnmnaaaaA1111 0 )( (min) maxXBAX

9、CXZ其中：其中：) (21ncccC nxxX1 mbbB12021-12-4156. 線性規(guī)劃問題的標(biāo)準(zhǔn)形式線性規(guī)劃問題的標(biāo)準(zhǔn)形式11max,1,2,.0,1,2,njjjnijjijjZc xa xb imstxjn特點(diǎn)：特點(diǎn)：(1) 目標(biāo)函數(shù)求最大值；目標(biāo)函數(shù)求最大值；(2) 約束條件為等式方程，約束條件為等式方程，且右端常數(shù)項(xiàng)且右端常數(shù)項(xiàng)bi都大于都大于或等于零；或等于零；(3) 決策變量決策變量xj為非負(fù)。為非負(fù)。2021-12-416 目標(biāo)函數(shù)的轉(zhuǎn)換目標(biāo)函數(shù)的轉(zhuǎn)換 如果是求極小值即如果是求極小值即 ，則可將目標(biāo)函數(shù)乘以，則可將目標(biāo)函數(shù)乘以(-1)，可化為求極大值問題。，可化為求極

10、大值問題。 jjxczmin也就是：令也就是：令 ，可得到上式。，可得到上式。zz jjxczzmax即即 若存在取值無(wú)約束的變量若存在取值無(wú)約束的變量 ，可令，可令 其中：其中：jxjjjxxx 0, jjxx 變量的變換變量的變換2021-12-417 約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。 ijijbxa0 iniinjijxbxxa稱為松弛變量稱為松弛變量 ijijbxa0 iniinjijxbxxa稱為剩余變量稱為剩余變量 常量常量 bi0 的變換的變換: :約束方程兩邊乘以約束方程兩邊乘以（1）2021-12-418例例1.6 將下列線性規(guī)劃問題化

11、為標(biāo)準(zhǔn)形式將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式 ,0,52324 7 532min321321321321321無(wú)無(wú)約約束束xxxxxxxxxxxxxxxZ用用 替換替換 ，且，且 解解:（）因?yàn)椋ǎ┮驗(yàn)閤3無(wú)符號(hào)要求無(wú)符號(hào)要求 ，即，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以型中要求變量非負(fù)，所以33xx 3x0,33 xx2021-12-419(2) 第一個(gè)約束條件是第一個(gè)約束條件是“”號(hào)，在號(hào)，在“”左端加入松馳變量左端加入松馳變量x4，x40,化為等式；化為等式；(3) 第二個(gè)約束條件是第二個(gè)約束條件是“”號(hào)，在號(hào)，在“”左端減去剩余變量左端減去剩余變量x5，x

12、50；(4) 第第3個(gè)約束方程右端常數(shù)項(xiàng)為個(gè)約束方程右端常數(shù)項(xiàng)為-5，方程兩邊同乘以，方程兩邊同乘以(-1),將右將右端常數(shù)項(xiàng)化為正數(shù)；端常數(shù)項(xiàng)化為正數(shù)； (5) 目標(biāo)函數(shù)是最小值，為了化為求最大值，令目標(biāo)函數(shù)是最小值，為了化為求最大值，令z=-z,得到得到max z=-z，即當(dāng)，即當(dāng)z達(dá)到最小值時(shí)達(dá)到最小值時(shí)z達(dá)到最大值，反之亦然達(dá)到最大值，反之亦然;2021-12-42012334512334123351233123345max23()005() 7 () 252() 5,0 Zxxxxxxxxxxxxxxxxxxxxx xxxxx標(biāo)準(zhǔn)形式如下：標(biāo)準(zhǔn)形式如下：2021-12-421 例例1

13、.7 將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式12312312312123m in52623521 00 ,0 , Zxxxxxxxxxxxxxx 為無(wú)約束（無(wú)非負(fù)限制）為無(wú)約束（無(wú)非負(fù)限制）2021-12-422 解解: : 標(biāo)準(zhǔn)形式如下：標(biāo)準(zhǔn)形式如下：123345123341233512123345max5()2()00()() 6 2()3() 52() 10,0 Zxxxxxxxxxxxxxxxxxxx xxxxx 2021-12-423 12121212m in Z2385340 ,xxxxxxxx 1341345134613456maxZ2()38()53()4

14、,0 xxxxxxxxxxxx x x x x 例例1.8 將線性規(guī)劃問題化為標(biāo)準(zhǔn)型將線性規(guī)劃問題化為標(biāo)準(zhǔn)型解：解：無(wú)約束無(wú)約束2021-12-4247. 7. 線性規(guī)劃問題的解線性規(guī)劃問題的解 )3(, 2 , 1, 0)2(), 2 , 1(.) 1 (max11njxmibxatsxcZjnjijijnjjj線性規(guī)劃問題線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組的方程組中找出一個(gè)解，使目標(biāo)函數(shù)中找出一個(gè)解，使目標(biāo)函數(shù)(1)達(dá)到最大值。達(dá)到最大值。2021-12-425 可行解可行解：滿足約束條件：滿足約束條件、的解為可行解。

15、所有可行解的解為可行解。所有可行解的集合為可行域。的集合為可行域。 最優(yōu)解最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。：使目標(biāo)函數(shù)達(dá)到最大值的可行解。 基：基：設(shè)設(shè)A為約束條件為約束條件的的mn階系數(shù)矩陣階系數(shù)矩陣(m04010出出基基將將3化為化為15/311801/301/31011/3303005/304/3乘乘以以1/3后后得得到到103/51/518011/5 2/5400112021-12-447例例1.13 用單純形法求解用單純形法求解 02053115232.2max321321321321xxxxxxxxxtsxxxZ、解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式： 5

16、, 2 , 1, 02053115232.2max53214321321jxxxxxxxxxtsxxxZj不難看出不難看出x4、x5可作為初始基變量，列單純形表計(jì)算?？勺鳛槌跏蓟兞?，列單純形表計(jì)算。2021-12-448cj12100icB基變量基變量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x2j 2021/3150120753017131/30902j 256011017/31/31250128/9-1/92/335/300-98/9 -1/9 -7/3j 2021-12-449 0,124 16 482122232max21212121

17、21xxxxxxxxxxZ變成標(biāo)準(zhǔn)型變成標(biāo)準(zhǔn)型 0, 12 4 16 4 8 2 21 22000032max6543216251421321654321xxxxxxxxxxxxxxxxxxxxxxZ例例1.14 用單純形法求解用單純形法求解2021-12-450約束方程的系數(shù)矩陣約束方程的系數(shù)矩陣 654321100040010004001021000122ppppppA IppppB100001000010000165436543 xxxx,21xx ,為基變量為基變量為非基變量為非基變量I I 為單位矩陣且線性獨(dú)立為單位矩陣且線性獨(dú)立2021-12-4512021-12-4522021-

18、12-4532021-12-454學(xué)習(xí)要點(diǎn)：學(xué)習(xí)要點(diǎn)：1. 線性規(guī)劃解的概念以及線性規(guī)劃解的概念以及3個(gè)基本定理個(gè)基本定理2. 熟練掌握線性規(guī)劃問題的標(biāo)準(zhǔn)化熟練掌握線性規(guī)劃問題的標(biāo)準(zhǔn)化 3.熟練掌握單純形法的解題思路及求解步驟熟練掌握單純形法的解題思路及求解步驟2021-12-455人工變量法：人工變量法：前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實(shí)際問題中有些模型并不含有單位確定一組基可行解。在實(shí)際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的矩陣，為了得到一組基向量和初基可行解，在約束條件的

19、等式左端加一組虛擬變量，得到一組基變量。這種人為加等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為的變量稱為人工變量人工變量，構(gòu)成的可行基稱為，構(gòu)成的可行基稱為人工基人工基，用，用大大MM法法或或兩階段法兩階段法求解，這種用人工變量作橋梁的求解方法稱求解，這種用人工變量作橋梁的求解方法稱為為人工變量法人工變量法。2021-12-456例例1.10 用大用大M法解下列線性規(guī)劃法解下列線性規(guī)劃 012210243423max321321321321321xxxxxxxxxxxxxxxZ、解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式 5 , 2 , 1, 01221024

20、3423max32153214321321jxxxxxxxxxxxxxxxZj系數(shù)矩陣中不存在系數(shù)矩陣中不存在單位矩陣，無(wú)法建單位矩陣，無(wú)法建立初始單純形表。立初始單純形表。2021-12-457故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：12345671234612351237max320043 4 2 10 22 10,1,2,7jZxxxxxMxMxxxxxxxxxxxxxxxj其中：其中：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用

21、前面介可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見下表。紹的單純形法求解該模型，計(jì)算結(jié)果見下表。 2021-12-458cj32-100-M-MCBXBbx1x2x3x4x5x6x7i-Mx64-431-101040 x5101-1201005-Mx712-21000113-2M2+M-1+2M-M-Mx63-650-1013/50 x58-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/500 x531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/

22、310015/3-1x319/300102/3000-5-25/3j j j j 2021-12-459例例1.11 用大用大M法解下列線性規(guī)劃法解下列線性規(guī)劃12312312313123max3 2114232 +10Zxxxxxxxxxxxxxx、 、解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式1231234123513max3 2114232 10,1,2,5jZxxxxxxxxxxxxxxj系數(shù)矩陣中不存在系數(shù)矩陣中不存在單位矩陣，無(wú)法建單位矩陣，無(wú)法建立初始單純形表。立初始單純形表。2021-12-460故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：故人為添加

23、兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：+0+01234567123412356137max3 3 11 -4 2 + 3 2 10,1,2,7jZxxxxxMxMxxxxxxxxxxxxxxj其中：其中：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見下表。紹的單純形法求解該模型，計(jì)算結(jié)果見下表。 2021-12-461Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70 x4111-211000

24、11-Mx63-4120-1103/2-Mx71-20100011Z-4M3-6M-1+M-1+3M0-M000 x4103-20100-1-Mx610100-11-21-1x31-2010001Z-M-11-1+M00-M0-3M+12021-12-462Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70 x4123001-22-54-1x210100-11-2-1x31-2010001Z-21000-1-M+1-M-13x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3Z2000-1/3-1/3-M+1/3-M+

25、2/32021-12-463 通過(guò)大法或兩階段法求初始的基本可行解。但是通過(guò)大法或兩階段法求初始的基本可行解。但是如果在大法的最優(yōu)單純形表的基變量中仍含有人工變?nèi)绻诖蠓ǖ淖顑?yōu)單純形表的基變量中仍含有人工變量，那么該線性規(guī)劃就不存在可行解。量，那么該線性規(guī)劃就不存在可行解。 無(wú)可行解無(wú)可行解 2021-12-464C -3 -2 -1 0 0 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 x8 0-M-M x4x7x8 643 1 1 1 1 0 0 0 01 0 -1 0 -1 0 1 00 1 -1 0 0 -1 0 1 6/1-3/1 Z -7M -6-4M

26、-15-M -3+M -2+M -1-2M 0 -M -M 0 0 0-M-2 x4x7x2 343 1 0 2 1 0 1 0 -11 0 -1 0 -1 0 1 00 1 -1 0 0 -1 0 1 3/14/1- Z Z -3+M 0 -3-M 0 -M -2 0 2-M -3-M-2 x1x7x2 313 1 0 2 1 0 1 0 -10 0 -3 -1 -1 -1 1 10 1 -1 0 0 -1 0 1 0 0 3-3M 3-M -M 1-M 0 -1 例例運(yùn)算到檢驗(yàn)數(shù)全負(fù)為止，仍含有人工變量，無(wú)可行解。運(yùn)算到檢驗(yàn)數(shù)全負(fù)為止，仍含有人工變量，無(wú)可行解。2021-12-465 無(wú)可

27、行解無(wú)可行解是指原規(guī)劃不存在可行解，從幾何的角度解釋是指是指原規(guī)劃不存在可行解，從幾何的角度解釋是指 線性規(guī)劃問題的可行域?yàn)榭占?；線性規(guī)劃問題的可行域?yàn)榭占?無(wú)界解無(wú)界解則是指線性規(guī)劃問題存在可行解，但是可行解的目則是指線性規(guī)劃問題存在可行解，但是可行解的目 標(biāo)函數(shù)達(dá)不到最優(yōu)值，即目標(biāo)函數(shù)在可行域內(nèi)趨于無(wú)窮大。標(biāo)函數(shù)達(dá)不到最優(yōu)值，即目標(biāo)函數(shù)在可行域內(nèi)趨于無(wú)窮大。 判別方法：無(wú)界解判定定理判別方法：無(wú)界解判定定理 在求解極大化的線性規(guī)劃問題過(guò)程中，若某單純形表的檢驗(yàn)在求解極大化的線性規(guī)劃問題過(guò)程中，若某單純形表的檢驗(yàn) 行存在某個(gè)大于零的檢驗(yàn)數(shù)，但是該檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量行存在某個(gè)大于零的檢驗(yàn)

28、數(shù)，但是該檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量 的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零，則該線性規(guī)劃問題的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零，則該線性規(guī)劃問題 無(wú)界解無(wú)界解 無(wú)界解無(wú)界解2021-12-466C 2 2 0 0 CXB B x1 x2 x3 x4 0X3 1-11100X4 2-1/2101Z022001= 20因因 但但 所以原問題無(wú)界解所以原問題無(wú)界解1-1P=01-22021-12-467 退化退化 即計(jì)算出的即計(jì)算出的 （用于確定換出變量）存在有兩個(gè)以上相同的最?。ㄓ糜诖_定換出變量）存在有兩個(gè)以上相同的最小比值，會(huì)造成下一次迭代中由一個(gè)或幾個(gè)基變量等于零，這就是比值，會(huì)造成下一次迭代中由一

29、個(gè)或幾個(gè)基變量等于零，這就是退退化化（會(huì)產(chǎn)生退化解）。（會(huì)產(chǎn)生退化解）。 為避免出現(xiàn)計(jì)算的循環(huán)，勃蘭特為避免出現(xiàn)計(jì)算的循環(huán)，勃蘭特(Bland)提出一個(gè)簡(jiǎn)便有效的規(guī)提出一個(gè)簡(jiǎn)便有效的規(guī)則（攝動(dòng)法原理）：則（攝動(dòng)法原理）： 當(dāng)存在多個(gè)當(dāng)存在多個(gè) 時(shí)，選下標(biāo)最小的非基變量為換入變量；時(shí)，選下標(biāo)最小的非基變量為換入變量；(2) 當(dāng)當(dāng)值出現(xiàn)兩個(gè)以上相同的最小值時(shí)，選下標(biāo)最小的基變量為換值出現(xiàn)兩個(gè)以上相同的最小值時(shí)，選下標(biāo)最小的基變量為換出變量。出變量。0j2021-12-468 無(wú)窮多最優(yōu)解無(wú)窮多最優(yōu)解 若線性規(guī)劃問題某個(gè)基本可行解所有的非基變量檢驗(yàn)若線性規(guī)劃問題某個(gè)基本可行解所有的非基變量檢驗(yàn)數(shù)都小

30、于等于零，但其中存在一個(gè)檢驗(yàn)數(shù)等于零，那么該數(shù)都小于等于零，但其中存在一個(gè)檢驗(yàn)數(shù)等于零，那么該線性規(guī)劃問題有無(wú)窮多最優(yōu)解。線性規(guī)劃問題有無(wú)窮多最優(yōu)解。例：最優(yōu)表：例：最優(yōu)表：非基變量檢驗(yàn)非基變量檢驗(yàn)數(shù)，數(shù)，所以有無(wú)窮多所以有無(wú)窮多最優(yōu)解。最優(yōu)解。C 1 2 0 0 0CBXBb x1 x2 x3 x4 x5021x3x2x12320 0 1 2 -10 1 0 1 01 0 0 -2 12/23/1-Z8 0 0 0 0 -14= 02021-12-469單純性法小結(jié)單純性法小結(jié):建建立立模模型型個(gè)個(gè) 數(shù)數(shù)取取 值值右右 端端 項(xiàng)項(xiàng)等式或等式或不等式不等式極大或極小極大或極小新加變新加變量系數(shù)

31、量系數(shù)兩兩個(gè)個(gè)三個(gè)三個(gè)以上以上xj0 xj無(wú)無(wú)約束約束xj 0 bi 0bi 0=max Zmin Zxs xa求求解解圖圖解解 法法、單單純純形形法法單單純純形形法法不不處處理理令令xj = xj - xj xj 0 xj 0令令 xj =- xj不不處處理理約束約束條件條件兩端兩端同乘同乘以以-1-1加加松松弛弛變變量量xs加加入入人人工工變變量量xa減減去去xs加加入入xa不不處處理理令令z=- ZminZ=max z0-M2021-12-470一般而言，一個(gè)經(jīng)濟(jì)、管理問題凡是滿足以下條一般而言，一個(gè)經(jīng)濟(jì)、管理問題凡是滿足以下條件時(shí)，才能建立線性規(guī)劃模型。件時(shí)，才能建立線性規(guī)劃模型。 要

32、求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來(lái)反映，且要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來(lái)反映，且為線性函數(shù)為線性函數(shù) 存在著多種方案存在著多種方案 要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些約要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些約束可用線性等式或不等式描述束可用線性等式或不等式描述2021-12-471常見問題常見問題合理利用線材問題：如何下料使用材最少。合理利用線材問題：如何下料使用材最少。配料問題：在原料供應(yīng)量的限制下如何獲取最大配料問題：在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)。利潤(rùn)。投資問題：從投資項(xiàng)目中選取方案，使投資回報(bào)投資問題：從投資項(xiàng)目中選取方案，使投資回報(bào)最大。最大。產(chǎn)品生產(chǎn)計(jì)劃：合理利用人

33、力、物力、財(cái)力等，產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、財(cái)力等，使獲利最大。使獲利最大。勞動(dòng)力安排：用最少的勞動(dòng)力來(lái)滿足工作的需要。勞動(dòng)力安排：用最少的勞動(dòng)力來(lái)滿足工作的需要。運(yùn)輸問題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小。運(yùn)輸問題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小。2021-12-472 (1)設(shè)立決策變量；設(shè)立決策變量； (2)明確約束條件并用決策變量的線性等式或不等式表明確約束條件并用決策變量的線性等式或不等式表示；示； (3)用決策變量的線性函數(shù)表示目標(biāo)，并確定是求極大用決策變量的線性函數(shù)表示目標(biāo)，并確定是求極大（Max）還是極小（）還是極?。∕in）；）； (4)根據(jù)決策變量的物理性質(zhì)研究變量是

34、否有非負(fù)性。根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性。建立線性規(guī)劃模型的過(guò)程可以分為四個(gè)步驟：建立線性規(guī)劃模型的過(guò)程可以分為四個(gè)步驟：2021-12-473例：現(xiàn)有一批某種型號(hào)的圓鋼長(zhǎng)例：現(xiàn)有一批某種型號(hào)的圓鋼長(zhǎng)8米，需要截取米，需要截取2.5米米長(zhǎng)的毛坯長(zhǎng)的毛坯100根，長(zhǎng)根，長(zhǎng)1.3米的毛坯米的毛坯200根。問如何才能根。問如何才能既滿足需要，又能使總的用料最少？既滿足需要，又能使總的用料最少？解：為了找到一個(gè)省料的套裁方案，必須先設(shè)計(jì)出較好的幾解：為了找到一個(gè)省料的套裁方案，必須先設(shè)計(jì)出較好的幾個(gè)下料方案。其次要求這些方案的總體能裁下所有各種規(guī)格個(gè)下料方案。其次要求這些方案的總體能裁下所有各種規(guī)格的圓鋼，以滿足對(duì)各種不同規(guī)格圓鋼的需要并達(dá)到省料的目的圓鋼，以滿足對(duì)各種不同規(guī)格圓鋼的需要并達(dá)到省料的目的，為此可以設(shè)計(jì)出的，為此可以設(shè)計(jì)出4種下料方案以供套裁用。種下料方案以供套裁用。2.5m32101.3m0246料頭料頭0.50.40.30.21. 合理下料問題合理下料問題2021-12-474 )4.3.2.1(020064210023min4323214321jxxxxxxxxxxxZj設(shè)按方案設(shè)按方案、下料的原材料根數(shù)分別為下料的原材料根數(shù)分別為xj (j=1，2,3,4)，可列出下面的數(shù)學(xué)模型：，可列出下面的數(shù)學(xué)模型：2021-1