運(yùn)籌學(xué)第一章線性規(guī)劃PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1 運(yùn)籌學(xué)第一章線性規(guī)劃運(yùn)籌學(xué)第一章線性規(guī)劃 2 授課教材：黨耀國(guó)等授課教材：黨耀國(guó)等,運(yùn)籌學(xué)運(yùn)籌學(xué), ,科學(xué)出版社科學(xué)出版社 緒論緒論 第一章第一章 線性規(guī)劃的數(shù)學(xué)模型與單純形法線性規(guī)劃的數(shù)學(xué)模型與單純形法 第二章第二章 線性規(guī)劃的對(duì)偶理論與靈敏度分析線性規(guī)劃的對(duì)偶理論與靈敏度分析 第三章第三章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 第四章第四章 整數(shù)規(guī)劃整數(shù)規(guī)劃 第五章第五章 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 第六章第六章 圖論與網(wǎng)絡(luò)計(jì)劃圖論與網(wǎng)絡(luò)計(jì)劃 第七章第七章 存儲(chǔ)論存儲(chǔ)論 第八章第八章 決策分析決策分析 第1頁(yè)/共87頁(yè) 3 第2頁(yè)/共87頁(yè) 4 第3頁(yè)/共87頁(yè) 5 人事管理：對(duì)人員的需求和使 用的預(yù)測(cè)，確定

2、人員編制、人員合 理分配，建立人才評(píng)價(jià)體系等。 市場(chǎng)營(yíng)銷：廣告預(yù)算、媒介選 擇、定價(jià)、產(chǎn)品開(kāi)發(fā)與銷售計(jì)劃制 定等。 O.R.O.R.在工商管理中的應(yīng)用在工商管理中的應(yīng)用 第4頁(yè)/共87頁(yè) 6 財(cái)務(wù)和會(huì)計(jì)：包括預(yù)測(cè)、貸款 、成本分析、定價(jià)、證券管理、現(xiàn) 金管理等。 其他： 設(shè)備維修、更新，項(xiàng) 目選擇、評(píng)價(jià)，工程優(yōu)化設(shè)計(jì)與管 理等。 O.R.O.R.在工商管理中的應(yīng)用在工商管理中的應(yīng)用 第5頁(yè)/共87頁(yè) 7 一、線性規(guī)劃問(wèn)題的數(shù)學(xué)模型一、線性規(guī)劃問(wèn)題的數(shù)學(xué)模型 主要解決以下兩類問(wèn)題： 1、任務(wù)確定后，如何統(tǒng)籌安排，做到應(yīng)用盡量少的人力和物力資源來(lái)完成任務(wù)； 2、在一定量的人力、物力資源的條件下，如

3、何安排、使用他們，使完成的任務(wù)最多。 第6頁(yè)/共87頁(yè) 8 I II 資源總量資源總量 設(shè)備設(shè)備A(h) 0 3 15 設(shè)備設(shè)備B(h) 4 0 12 原材料原材料(公斤公斤) 2 2 14 利潤(rùn)利潤(rùn)(萬(wàn)元）萬(wàn)元） 2 3 I,II生產(chǎn)多少生產(chǎn)多少, 可獲最大利潤(rùn)可獲最大利潤(rùn)? 解解:設(shè)設(shè) 計(jì)劃期內(nèi)生產(chǎn)產(chǎn)品計(jì)劃期內(nèi)生產(chǎn)產(chǎn)品I、II的數(shù)量的數(shù)量x1、x2 則該問(wèn)題的數(shù)學(xué)模型為：則該問(wèn)題的數(shù)學(xué)模型為： 3x2 15 4x1 12 2x1+2x2 14 x1， ，x2 0 max S= 2x1 +3x2 第7頁(yè)/共87頁(yè) 9 油品來(lái)源油品來(lái)源 成分成分 AB 汽油汽油15%50 % 煤油煤油20%3

4、0 % 重油重油50%15 % 其它其它15%5% 12 12 12 12 12 min S200 x290 x 0.15x0.50 x15 0.20 x0.30 x12 0.50 x0.15x12 x0,x0 某煉油廠根據(jù)每季度需供應(yīng)給合同單位汽油某煉油廠根據(jù)每季度需供應(yīng)給合同單位汽油15萬(wàn)噸、萬(wàn)噸、 煤油煤油12萬(wàn)噸、重油萬(wàn)噸、重油12萬(wàn)噸。該廠計(jì)劃從萬(wàn)噸。該廠計(jì)劃從A，B兩處運(yùn)回兩處運(yùn)回 原油提煉，已知兩處的原油成分含量見(jiàn)表原油提煉，已知兩處的原油成分含量見(jiàn)表12；又已；又已 知從知從A處采購(gòu)的原油價(jià)格為每噸（包括運(yùn)費(fèi)）處采購(gòu)的原油價(jià)格為每噸（包括運(yùn)費(fèi)）200元，元， B處采購(gòu)的原油價(jià)格

5、為每噸（包括運(yùn)費(fèi)）處采購(gòu)的原油價(jià)格為每噸（包括運(yùn)費(fèi)）290元元, 問(wèn)：?jiǎn)枺?該煉油廠該如何從該煉油廠該如何從A，B兩處采購(gòu)原油，在滿足供應(yīng)合兩處采購(gòu)原油，在滿足供應(yīng)合 同的條件下，使購(gòu)買成本最小。同的條件下，使購(gòu)買成本最小。 第8頁(yè)/共87頁(yè) 10 滿足以上三個(gè)條件的數(shù)學(xué)模型稱為滿足以上三個(gè)條件的數(shù)學(xué)模型稱為 -線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型 第9頁(yè)/共87頁(yè) 11 I II 每天現(xiàn)有工每天現(xiàn)有工 時(shí)時(shí) 攪拌機(jī)攪拌機(jī) 3 5 15 成型機(jī)成型機(jī) 2 1 5 烘烘 箱箱 2 2 11 利潤(rùn)利潤(rùn)(千元千元/噸）噸） 5 4 某食品廠主要生產(chǎn)某食品廠主要生產(chǎn)I型餅干和型餅干和I I型餅干。根據(jù)銷售

6、部門提供型餅干。根據(jù)銷售部門提供 的信息可知，目前這兩種餅干在市場(chǎng)上都很暢銷，該廠能的信息可知，目前這兩種餅干在市場(chǎng)上都很暢銷，該廠能 生產(chǎn)多少，市場(chǎng)就能賣出多少。但從生產(chǎn)部門得知，有三生產(chǎn)多少，市場(chǎng)就能賣出多少。但從生產(chǎn)部門得知，有三 種關(guān)鍵設(shè)備即攪拌機(jī)、成型機(jī)、烘箱的生產(chǎn)能力限制了該種關(guān)鍵設(shè)備即攪拌機(jī)、成型機(jī)、烘箱的生產(chǎn)能力限制了該 廠的餅干生產(chǎn)。因?yàn)閮煞N餅干的生產(chǎn)都要共用這三種設(shè)備廠的餅干生產(chǎn)。因?yàn)閮煞N餅干的生產(chǎn)都要共用這三種設(shè)備 ，所以每種餅干究竟應(yīng)該生產(chǎn)多少才能充分利用現(xiàn)有設(shè)備，所以每種餅干究竟應(yīng)該生產(chǎn)多少才能充分利用現(xiàn)有設(shè)備 資源，這是一個(gè)值得認(rèn)真研究的重要問(wèn)題。資源，這是一個(gè)值得

7、認(rèn)真研究的重要問(wèn)題。 第10頁(yè)/共87頁(yè) 12 甲甲 乙乙 丙丙 柑橘林產(chǎn)量（千蒲式耳柑橘林產(chǎn)量（千蒲式耳 ） 柑橘林柑橘林I 21 50 40 275 柑橘林柑橘林II 35 30 22 400 柑橘林柑橘林III 55 20 25 300 加工廠的加工能力加工廠的加工能力 200 600 225 （千蒲式耳）（千蒲式耳） 某企業(yè)是一家新鮮柑橘產(chǎn)品的種植商和經(jīng)營(yíng)商，有某企業(yè)是一家新鮮柑橘產(chǎn)品的種植商和經(jīng)營(yíng)商，有I、II、II塊塊 大的柑橘林及甲乙丙三個(gè)柑橘加工廠（柑橘林到加工廠的距離大的柑橘林及甲乙丙三個(gè)柑橘加工廠（柑橘林到加工廠的距離 公里信息如紅色字體數(shù)據(jù)）?，F(xiàn)該企業(yè)與一家地方貨車運(yùn)輸公

8、公里信息如紅色字體數(shù)據(jù)）?，F(xiàn)該企業(yè)與一家地方貨車運(yùn)輸公 司聯(lián)系，從柑橘林向加工廠運(yùn)輸柑橘。運(yùn)輸公司按照每蒲式耳司聯(lián)系，從柑橘林向加工廠運(yùn)輸柑橘。運(yùn)輸公司按照每蒲式耳 柑橘運(yùn)輸每公里（記為蒲式耳柑橘運(yùn)輸每公里（記為蒲式耳-公里）的統(tǒng)一價(jià)格收費(fèi)，該企業(yè)公里）的統(tǒng)一價(jià)格收費(fèi)，該企業(yè) 希望確定從各個(gè)柑橘林到各個(gè)加工廠運(yùn)輸多少蒲式耳，以使所希望確定從各個(gè)柑橘林到各個(gè)加工廠運(yùn)輸多少蒲式耳，以使所 運(yùn)輸?shù)母涕倨咽蕉\(yùn)輸?shù)母涕倨咽蕉?公里的總數(shù)最小。公里的總數(shù)最小。 第11頁(yè)/共87頁(yè) 13 max(min) Z=c1x1+ c2x2+cnxn x1 X= x2 xn b1 b= b2 bm C=(C1 C2

9、 Cn ) a11 a12 a1n 令令 A= A= a21 a22 a2n am1 am2 amn mn a11x1+ a12x2+ a1nxn (=, (=, )b)b1 1 a21x1+ a22x2+ a2nxn (=, (=, )b)b2 2 am1x1+ am2x2+ amnxn (=, (=, )b)bm m xj j 0( 0(j=1,n) ) s.t. () ( , ) . . max min ZCX AXb st XO 第12頁(yè)/共87頁(yè) 14 1 122 11 112211 21 122222 1 122 12 max (1.4) ,0 nn nn nn mmmnnm n

10、Zc xc xc x a xa xa xb a xa xa xb a xa xa xb x xx 目標(biāo)函數(shù)目標(biāo)函數(shù) max 變量變量 非負(fù)非負(fù) 約束條件約束條件 等式等式 約束常數(shù)約束常數(shù) 非負(fù)非負(fù) 第13頁(yè)/共87頁(yè) 15 解：引進(jìn)3個(gè)新非負(fù)變量x3，x4，x5使不等式變?yōu)榈仁?，?biāo)準(zhǔn)型為： max Z=2x1+3x2+0 x3+0 x4+0 x5 3x2+x3=15 4x1+x4 =12 2x1+2x2+x5=14 x1，x2，x3，x4，x50 max Z=2x1+3x2 3x2 15 4x1 12 2x1+2x2 14 x1，x20 第14頁(yè)/共87頁(yè) 16 解：解： 令令x3 =x4

11、- x5 添加松弛變量添加松弛變量x6 添加剩余變量添加剩余變量x7 令令S= -S maxS= x1 2x2 +3x4 3x5 x1 +x2 +x4 -x5 +x6=7 x1 -x2 +x4 -x5 -x7 =2 x1 , x2 , x4 , , x7 0 0 將將 min S = -x1+2x2 3x3 x1+x2 +x3 7 x1 -x2 +x3 2 2 x1，x2 0 0，x3無(wú)限制無(wú)限制 化為標(biāo)準(zhǔn)型?；癁闃?biāo)準(zhǔn)型。 第15頁(yè)/共87頁(yè) 17 將將 min S = x1+2x2 +3x3 -2x1+x2 +x3 9 -3x1 +x2 +2x3 4 4 4x1 -2x2 -3x3 4 x1

12、 0，x2 0 0，x3無(wú)限制無(wú)限制 化為標(biāo)準(zhǔn)型?；癁闃?biāo)準(zhǔn)型。 第16頁(yè)/共87頁(yè) 18 0 10 20 30 x2 D AB C max S=40 x1+ 50 x2 x1+2x2 30 3x1+2x2 60 2x2 24 x1 , x2 0 0 解：解：(1) 確定可行域確定可行域 x1 0 0 x1 =0=0 ( (橫軸橫軸 ) ) x2 0 0 x2=0=0 ( (縱軸縱軸 ) ) x1+2x2 30 x1+2x2 =30 l1 (0,15) (30,0) 3x1+2x2 =60 l2 (0,30) (20,0) 2x2 =24203 0 10 x1 1.2 線性規(guī)劃問(wèn)題的圖解法及幾何

13、意義線性規(guī)劃問(wèn)題的圖解法及幾何意義 第17頁(yè)/共87頁(yè) 19 (2) 求最優(yōu)解求最優(yōu)解“等值線法等值線法” 解：解：X* = (15 7.5) Smax =975 0 203010 10 20 30 x1 x2 D A B C 截距截距S=40 x1+50 x2 =x2 = 0.8x10.02 S C點(diǎn)點(diǎn)：使：使截距最大截距最大 x1+2x2 =30 l1 3x1+2x2 =60 l2 0=40 x1+50 x2 過(guò)原點(diǎn)過(guò)原點(diǎn) 第18頁(yè)/共87頁(yè) 20 max Z = 2x1 +3x2 2 1 12 12 315 412 . . 2214 ,0 x x st xx xx 解得：最優(yōu)解解得：最優(yōu)

14、解B點(diǎn)（點(diǎn)（2，5）。）。 最優(yōu)值最優(yōu)值 Z=22+35=19 唯一最優(yōu)解唯一最優(yōu)解 第19頁(yè)/共87頁(yè) 21 用圖解法求解線性規(guī)劃問(wèn)題 maxZ=40 x1+ 80 x2 s.t. x1+2x2 30 3x1+2x2 60 2x2 24 x1 , x2 0 解：最優(yōu)解：BC線段 B點(diǎn) X(1)= (6,12)； C點(diǎn) X(2)= (15,7.5) X= X(1)+(1-) X(2) (0 1) maxZ=1200 整理得：x1 =15-9 x2 =7.5+4.5 (0 1) 0 203010 10 20 30 x1 x2 D A B C 無(wú)窮多解無(wú)窮多解 第20頁(yè)/共87頁(yè) 22 maxZ=

15、2x1+ 4x2 s.t. 2x1+x2 8 -2 x1+ x2 2 x1，x2 0 若目標(biāo)函數(shù)由若目標(biāo)函數(shù)由 min Z =2 x1 +4 x2 , 最優(yōu)解最優(yōu)解 x1 = 4，x2 = 0 ，即，即 (4,0)點(diǎn)點(diǎn) 無(wú)界解無(wú)界解=可行域無(wú)界可行域無(wú)界 = 解：由于可行域無(wú)界 無(wú)有限最優(yōu)解-無(wú)界解 Z=0 2x1+ x2=8 -2x1+ x2=2 8 2 4 6 x 2 4 0 x1 第21頁(yè)/共87頁(yè) 23 max S=3x1+2x2 -x1 -x2 1 1 x1 , x2 0 0 無(wú)可行解無(wú)可行解 -1 x2 -1 x1 0 總結(jié)總結(jié) 唯一解唯一解 無(wú)窮多解無(wú)窮多解 無(wú)有限最優(yōu)無(wú)有限最優(yōu)

16、 解解 無(wú)可行解無(wú)可行解 有解有解 無(wú)解無(wú)解 第22頁(yè)/共87頁(yè) 24 通過(guò)以上各題圖解法所得結(jié)論可以看出： （1）線性規(guī)劃的所有可行解構(gòu)成的可行域一般是凸多 邊形，有些可行域可能是無(wú)界的； （2）若存在最優(yōu)解，則一定在可行域的某頂點(diǎn)得到； （3）若在兩個(gè)頂點(diǎn)上同時(shí)得到最優(yōu)解，則在這兩點(diǎn)的 連線上的任一點(diǎn)都是最優(yōu)解。 （4）若可行域無(wú)界，則可能發(fā)生最優(yōu)解無(wú)界的情況； （5）若可行域是空集，此時(shí)無(wú)最優(yōu)解。 上述理論具有普遍意義，對(duì)于兩個(gè)以上變量的線性規(guī)劃 問(wèn)題都是成立。 第23頁(yè)/共87頁(yè) 25 1 max (1.8) n jj j Zc x 1 (1 2) (1.9) 0 (1,2, ) (1

17、.10) n ijji j j a xbi, ,m xjn 1.2 線性規(guī)劃問(wèn)題的圖解法及幾何意義線性規(guī)劃問(wèn)題的圖解法及幾何意義 第24頁(yè)/共87頁(yè) 26 (m n) r(A)=m , 至少有一個(gè)至少有一個(gè)m 階子式不為階子式不為0 不失一般性不失一般性,不妨假設(shè)不妨假設(shè)P1 Pm線性無(wú)關(guān)線性無(wú)關(guān) max S=CX AX =b X 0 0 A Amn 滿秩滿秩 基陣基陣A中一個(gè)子矩陣中一個(gè)子矩陣B是可逆矩是可逆矩 陣，陣， 則方陣則方陣B稱為稱為L(zhǎng)P問(wèn)題的一個(gè)基陣。問(wèn)題的一個(gè)基陣。 a11 a1m a1m+1 a1n a21 a2m a2m+1 a2n am1 amm amm+1 amn Pm

18、+1 Pn P1 Pm BNA= B N 第25頁(yè)/共87頁(yè) 27 A= (P1 Pm Pm+1 Pn ) =(B N ) X= x1 xm xm+1 xn 定義：定義：基向量基向量 非基向量非基向量 =(XB XN)T 有：有：AX=P1 x1+ P2 x2 + +Pn xn=b 定義：定義：基變量基變量 非基變量非基變量 BXB +NXN=b BXB =b-NXN XB = B-1 b - B-1N XN AX=b 求解過(guò)程求解過(guò)程 ： A=(B N) X=(XB XN )T XB XN (BN) = b T T 目標(biāo)函數(shù)：目標(biāo)函數(shù)：S=CX=CB B-1 b+(CN -CB B-1 N)

19、XN 第26頁(yè)/共87頁(yè) 28 1. 可行解可行解: 滿足約束條件的解 X = ( x1, x2, , xn) 稱為線性規(guī)劃問(wèn) 題的可行解；所有可行解的集合稱為可行解集或可行域。 2. 最優(yōu)解最優(yōu)解: 滿足約束條件及目標(biāo)函數(shù)的可行解稱為線性規(guī)劃 問(wèn)題的最優(yōu)解。 最優(yōu)值最優(yōu)值 3. 基陣基陣: 假設(shè) A 是約束方程組的系數(shù)矩陣，其秩數(shù)為 m ，B 是矩陣 A 中由 m 列構(gòu)成的非奇異子矩陣(B的行列式的值不為0) ，則稱 B 是線性規(guī)劃問(wèn)題的一個(gè)基。這就是說(shuō)，矩陣 B 是由 m 個(gè)線性無(wú)關(guān)的列向量組成，不失一般性，可假設(shè): 稱 Pj ( j = 1,2,m )為基向量，與基向量 Pj 相對(duì)應(yīng)的變

20、量xj ( j = 1,2,m )稱為基變量，否則稱為非基變量。 11121 12 12 ( ,) m m mmmm aaa BP PP aaa T 若令非基變量若令非基變量 xm+1 = = xn = 0 ,用高斯消元法用高斯消元法 可求出可求出LP標(biāo)準(zhǔn)型的一個(gè)解標(biāo)準(zhǔn)型的一個(gè)解 X = ( x1 x2 xm 0 0 )T 稱稱 X 為為基本解基本解. 第27頁(yè)/共87頁(yè) 29 為了進(jìn)一步討論線性規(guī)劃問(wèn)題的解，下面研究約束方程 組(1.7)的求解問(wèn)題。假設(shè)該方程組系數(shù)矩陣 A 的秩為 m，因 m n，所以它有無(wú)窮多個(gè)解。假設(shè)前 m 個(gè)變量的系數(shù)列向 量是線性無(wú)關(guān)的，這時(shí)(1.7)式可改寫(xiě)為：

21、方程組(1.9)的一個(gè)基是B=(P1, P2, ,Pm), Pj=(a1j, ,amj), (j = 1,2, , m )，設(shè) XB 是對(duì)應(yīng)于這個(gè)基的基變量，即： XB = ( x1, x2, , xm ) 現(xiàn)若令(1.9)式中的非基變量xm+1= =xn=0，并用高斯消 去法求出一個(gè)解X=(x1,x2, ,xm,0, , 0 ) ，這個(gè)解的非0分量 的數(shù)目不大于方程的個(gè)數(shù)m，這時(shí)稱X為基本解。 111111 11 11 11 :(1.9) mmn mmn mm mm mm n mn jjjj jjm aaaa xxbxx aaaa P xbP x 或 T T T 第28頁(yè)/共87頁(yè) 30 4

22、. 基本可行解基本可行解 : 滿足非負(fù)條件(1.8)的基本解稱為基本可 行解。由此可見(jiàn)，基本可行解的非0分量的數(shù)目不大于m， 并且都是非負(fù)的。 5. 可行基陣可行基陣: 對(duì)應(yīng)于基本可行解的基稱為可行基。由此 可見(jiàn)，滿足約束方程組(1.7)的基本解的數(shù)目至多是 Cnm 個(gè)。 一般地講，基本可行解的數(shù)目要小于基本解的數(shù)目，至多 相等。 以上提到的幾種解的概念，可用圖14來(lái)表示： 基解 可行解 基本可行解 第29頁(yè)/共87頁(yè) 31 1. 凸集：假設(shè)凸集：假設(shè)K是是n維歐氏空間的一個(gè)點(diǎn)集，若對(duì)于維歐氏空間的一個(gè)點(diǎn)集，若對(duì)于K中的任中的任 意兩點(diǎn)意兩點(diǎn)X1、X2，其連線上的所有點(diǎn)，其連線上的所有點(diǎn) X1

23、+(1- )X2，( 0 1)都在都在 集合集合K中，即：中，即： X1+(1- )X2 K ( 0 1) 則稱則稱K為凸集。為凸集。 從直觀上講，凸集無(wú)凹入部分，其內(nèi)部沒(méi)有洞。從直觀上講，凸集無(wú)凹入部分，其內(nèi)部沒(méi)有洞。 如實(shí)心圓、實(shí)心球、實(shí)心立方體等都是凸集。兩個(gè)凸集的交集仍如實(shí)心圓、實(shí)心球、實(shí)心立方體等都是凸集。兩個(gè)凸集的交集仍 是凸集。是凸集。 2. 凸組合：設(shè)凸組合：設(shè)X1，X2，Xk是是n維歐氏空間維歐氏空間En中的中的k個(gè)點(diǎn)，個(gè)點(diǎn)， 若存在若存在 1， 2， k，且，且0 i 1，i = 1,2, , k， i = 1，使，使X = 1X1 + 2X2 + + kXk，則稱，則稱X

24、為由為由X1，X2，Xk所構(gòu)成的凸所構(gòu)成的凸 組合。組合。 按照定義，凡是由按照定義，凡是由x，y的凸組合表示的點(diǎn)都在的凸組合表示的點(diǎn)都在x，y的連線上，而的連線上，而 且反之亦然。且反之亦然。 3. 頂點(diǎn)：頂點(diǎn)： 假設(shè)假設(shè)K是凸集，是凸集，X K；X若不能用不同的兩個(gè)點(diǎn)若不能用不同的兩個(gè)點(diǎn)X1、 X2 K的線性組合表示為：的線性組合表示為： X = X1+(1- )X2 ， ( 0 1) 則稱則稱X為凸集為凸集K的一個(gè)頂點(diǎn)（或稱為極點(diǎn)）。的一個(gè)頂點(diǎn)（或稱為極點(diǎn)）。 頂點(diǎn)不位于凸集頂點(diǎn)不位于凸集K中的任意不同兩點(diǎn)的連線內(nèi)。中的任意不同兩點(diǎn)的連線內(nèi)。 第30頁(yè)/共87頁(yè) 32 定理定理1.1 若

25、線性規(guī)劃問(wèn)題存在可行域，則其可 行域： D = X | AX = b , X 0 ，是凸集。 引理引理1.1 線性規(guī)劃問(wèn)題的可行解X為基本可行解 的充要條件是X的正分量所對(duì)應(yīng)的系數(shù)列向量是線性 無(wú)關(guān)的。 定理定理1.2 線性規(guī)劃問(wèn)題的基本可行解對(duì)應(yīng)于可 行域的頂點(diǎn)。 定理定理1.3 若可行域有界，則線性規(guī)劃問(wèn)題的目 標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)上達(dá)到最優(yōu)解。 定理定理1.4 若線性規(guī)劃問(wèn)題在k個(gè)頂點(diǎn)上達(dá)到最優(yōu) 解 （k2），則在這些頂點(diǎn)的凸組合上也達(dá)到最優(yōu) 解。 第31頁(yè)/共87頁(yè) 33 根據(jù)圖解法圖解法得到如下的結(jié)論： （1）線性規(guī)劃問(wèn)題的所有可行解的集合一般是凸集， 它可以是有界的，也可

26、以是無(wú)界的區(qū)域；僅有有限個(gè) 頂點(diǎn)。1 (2) 線性規(guī)劃問(wèn)題的每一個(gè)基本可行解對(duì)應(yīng)于可行域的 一個(gè)頂點(diǎn)。若線性規(guī)劃問(wèn)題有最優(yōu)解，必定可在某頂 點(diǎn)處取到。 (3) 如果一個(gè)線性規(guī)劃問(wèn)題存在多個(gè)最優(yōu)解，那么至少 有兩個(gè)相鄰的頂點(diǎn)處是線性規(guī)劃的最優(yōu)解。 雖然可行域的頂點(diǎn)個(gè)數(shù)是有限的(它們不超過(guò) Cnm 個(gè))，采 用“枚舉法”可以找出所有基本可行解，然后一一比 較它們的目標(biāo)函數(shù)值的大小，最終可以找到最優(yōu)解。 但當(dāng)m、n的數(shù)目相當(dāng)大時(shí)，這種辦法實(shí)際上是行不通 的。因此，我們還要繼續(xù)討論一種方法，通過(guò)逐步迭 代保證能逐步改進(jìn)并最終求出最優(yōu)解。 第32頁(yè)/共87頁(yè) 34 A= (P1 Pm Pm+1 Pn )

27、 =(B N ) X=(x1 xm xm+1 xn)T 基向量基向量 | 非基向量非基向量 =(XB XN)T 約束方程組：約束方程組：AX=P1 x1+ P2 x2 + +Pn xn=b BXB +N XN =b BXB =b-NXN XB = B-1 b - B-1N XN 約束方程：約束方程：AX=b A=(B N) X=(XB XN )T XB XN (B N) = b 目標(biāo)函數(shù)方程：目標(biāo)函數(shù)方程：S=CX=CB B-1 b+(CN -CB B-1 N)XN 基基變變量量 非非變變向量向量 第33頁(yè)/共87頁(yè) 35 單純形算法的基本思路是：根據(jù)問(wèn)題的標(biāo)準(zhǔn)型，從可行域單純形算法的基本思路

28、是：根據(jù)問(wèn)題的標(biāo)準(zhǔn)型，從可行域 中某個(gè)基本可行解中某個(gè)基本可行解(頂點(diǎn)頂點(diǎn))開(kāi)始，轉(zhuǎn)換到另一個(gè)基本可行解開(kāi)始，轉(zhuǎn)換到另一個(gè)基本可行解(頂點(diǎn)頂點(diǎn)) ，并使得每次的轉(zhuǎn)換，目標(biāo)函數(shù)值均有所改善，最終達(dá)到最大，并使得每次的轉(zhuǎn)換，目標(biāo)函數(shù)值均有所改善，最終達(dá)到最大 值時(shí)就得到最優(yōu)解。值時(shí)就得到最優(yōu)解。 現(xiàn)在需要解決的問(wèn)題是：現(xiàn)在需要解決的問(wèn)題是： (1) 為了使目標(biāo)函數(shù)逐步變優(yōu)，應(yīng)如何從可行域的一個(gè)頂點(diǎn)為了使目標(biāo)函數(shù)逐步變優(yōu)，應(yīng)如何從可行域的一個(gè)頂點(diǎn) 轉(zhuǎn)移到可行域的另一個(gè)頂點(diǎn)？轉(zhuǎn)移到可行域的另一個(gè)頂點(diǎn)？ （2）目標(biāo)函數(shù)何時(shí)達(dá)到最優(yōu)值？判斷標(biāo)準(zhǔn)是什么？）目標(biāo)函數(shù)何時(shí)達(dá)到最優(yōu)值？判斷標(biāo)準(zhǔn)是什么？ 第34頁(yè)/

29、共87頁(yè) 36 1確定初始基本可行解確定初始基本可行解 對(duì)于標(biāo)準(zhǔn)型的線性規(guī)劃問(wèn)題(簡(jiǎn)寫(xiě)為 LP)： 或 （1.9） 這里 A = ( aij)mn ，Rank(A )= m 。 1 max(1.6) n jj j Zc x )8 . 1 (), 2 , 1(0 )7 . 1 (), 2 , 1( 1 njx njbxa j n j jjij max 0 T ZC X AXb X 第35頁(yè)/共87頁(yè) 37 從中一般可以直接觀察到存在一個(gè)初始可行基 B = ( P1, P2, Pm )= （1.10） 當(dāng)線性規(guī)劃的約束條件均為“=”形式的不等式或等式時(shí)，若不存在單位矩陣，就采用構(gòu) 造人造基的辦法，

30、即對(duì)不等式約束減去一個(gè)非負(fù)的剩余變量后 ，再加上一個(gè)非負(fù)的人工變量；對(duì)于等式約束，加上一個(gè)非負(fù) 的人工變量。這樣總可以找到一個(gè)單位矩陣，關(guān)于這個(gè)方法將 在本章第四節(jié)討論。 100 010 001 第36頁(yè)/共87頁(yè) 38 （1.10）式中的P1,P2, Pm稱為基向量，其對(duì)應(yīng)的變量 稱為基變量，模型中其它變量稱為非基變量。在約束條件中 把非基變量項(xiàng)移到等式的右邊得： 111,111 222,112 ,11 mmnn mmnn mmm mmmnn xbaxa x xbaxa x xbaxax （1.11） 令所有非基變量 ，得 X = ( b1,b2, , bm, 0, , 0 ) 又由于，故X

31、滿足約束條件，所以它是一個(gè)基可行解。 式(1.11)就是基變量用非基變量表示的形式。 12 0 mmn xxx T 第37頁(yè)/共87頁(yè) 39 cjc1ckcm cm+1 cjcn CBXBb*x1xkxm xm+1 xjxn c1x1b1*100 a1m+1 a1ja1n ClXlbl*010 alm+1 aljaln cmxmbm*001 amm+1 amjamn CN - CBB-1A000 m+1 j n 表13 初始單純形表 第38頁(yè)/共87頁(yè) 40 利用單純形算法求解例利用單純形算法求解例11的線性規(guī)劃問(wèn)題。的線性規(guī)劃問(wèn)題。 Max Z=2x1+3x2+0 x3+0 x4+0 x5

32、3x2+x3=15 s.t. 4x1+x4=12 2x1+2x2x5=14 x1，x2，x3，x4，x50 cj23000 i XBbx1x2x3x4x5 x315031005 x41240010 x514220017 -Z023000 解：解： （1）由標(biāo)準(zhǔn)型得到初始單純形表：）由標(biāo)準(zhǔn)型得到初始單純形表： 3x2+x3 =15 4x1+ x4 =12 2x1+2x2 x5=14 第39頁(yè)/共87頁(yè) 41 假定已求得(LP)的一個(gè)基本可行解 X(0) ， 為敘述方便, 不失一般性，假設(shè)： 令所有非基變量 ，得 把式(1.12)代入目標(biāo)函數(shù)得： 式（1.14）就是目標(biāo)函數(shù)用非基變量表示的形式。

33、111,111 222,112 ,11 mmnn mmnn mmm mmmnn xbaxa x xbaxa x xbaxax (1.12) 12 0 mmn xxx 111 () mnm i ijiijj ij mi zcbcca x （1.13） （1.14） (0) 12 ( ,0,0)T m Xb bb 第40頁(yè)/共87頁(yè) 42 令 ， ， 于是 再令 ，則得： （1.15） 在式（1.15）中，非基變量的系數(shù) ，稱為各非基變量 （ ）的檢驗(yàn)數(shù)檢驗(yàn)數(shù)。 0 1 m ii i zcb 1 m jiij i zc a 1,jmn 0 1 () n jjj j m zzczx jjj cz1,

34、jmn 0 1 n jj j m zzx j j x 1,jmn 第41頁(yè)/共87頁(yè) 43 若 為對(duì)應(yīng)于基 B 的基本可行解，且對(duì)于一切 ，有 j 0，則 X 為線性規(guī)劃問(wèn)題的最優(yōu)解。 定理定理1.6 無(wú)窮多最優(yōu)解判別定理無(wú)窮多最優(yōu)解判別定理:若 為對(duì) 應(yīng)于基 B 的基本可行解，且對(duì)于一切 ，有 j 0， 又存在某個(gè)非基變量的檢驗(yàn)數(shù) ，則線性規(guī)劃問(wèn)題有無(wú)窮 多最優(yōu)解。 定理定理1.7 無(wú)有限最優(yōu)解判別定理無(wú)有限最優(yōu)解判別定理： 若 為對(duì) 應(yīng)于基 B 的基本可行解，有一個(gè) ，而對(duì)于 有 ，則線性規(guī)劃問(wèn)題無(wú)有限最優(yōu)解(也稱為無(wú)最優(yōu)解)。 以上討論的都是針對(duì)標(biāo)準(zhǔn)型的，即求目標(biāo)函數(shù)極大化問(wèn)題。 當(dāng)求目

35、標(biāo)函數(shù)極小化時(shí)，一種情況如前所述，將其化為標(biāo)準(zhǔn)型； 另一種情況是將判別定理中的檢驗(yàn)數(shù)j 0改為 即可。 (0) 12 ( ,0,0)T m Xb bb 1,jmn （0） (0) 12 ( ,0,0)T m Xb bb 1,jmn 0 m k (0) 12 ( ,0,0)T m Xb bb 0 m k 1,2,im , 0 i m k a 0 j 第42頁(yè)/共87頁(yè) 44 由式由式(1.15)可知，當(dāng)某些非基變量的檢驗(yàn)數(shù)可知，當(dāng)某些非基變量的檢驗(yàn)數(shù) j 0 時(shí)，如果時(shí)，如果xj增加，則目標(biāo)函數(shù)值還可以增加。當(dāng)有增加，則目標(biāo)函數(shù)值還可以增加。當(dāng)有 兩個(gè)或兩個(gè)以上兩個(gè)或兩個(gè)以上 j 0時(shí)，那么選哪

36、個(gè)非基變量作時(shí)，那么選哪個(gè)非基變量作 為換入變量呢？為了使目標(biāo)函數(shù)值增加的最快，為換入變量呢？為了使目標(biāo)函數(shù)值增加的最快， 我們一般選擇我們一般選擇 j 0中的最大者，即：中的最大者，即： j = max l l 0 j所對(duì)應(yīng)的變量所對(duì)應(yīng)的變量xj為換入變量為換入變量(就是下一個(gè)基的基變就是下一個(gè)基的基變 量量)。 第43頁(yè)/共87頁(yè) 45 因?yàn)榛兞總€(gè)數(shù)總是為m，所以換入一個(gè)變量之后 還必須換出一個(gè)變量。下面我們來(lái)考慮如何選擇換出變 量。 確定換出變量的原則是保持解的可行性。這就是說(shuō) ，要使原基本可行解的某一個(gè)正分量xj變?yōu)?，同時(shí)保持 其余分量均非負(fù)。具體實(shí)現(xiàn)是按“最小比例原則”進(jìn)行 ，也

37、稱原則。 若 則選基變量xl為換出變量。 （3）旋轉(zhuǎn)運(yùn)算（迭代運(yùn)算） 在確定了換入變量xj與換出變量xl之后，要把xj和xl 的位置對(duì)換，就是說(shuō)，要把xj 所對(duì)應(yīng)的列向量pj變成單 位向量。這時(shí)只需對(duì)系數(shù)矩陣的增廣矩陣進(jìn)行變換即可 ，稱alj為旋轉(zhuǎn)元。 min|0 il ijl i ijil bb a aa 第44頁(yè)/共87頁(yè) 46 在確定了換入變量xj與換出變量xl之后，要把xj和xl 的位置對(duì)換，就是說(shuō)，要把xj 所對(duì)應(yīng)的列向量pj變成單 位向量。這時(shí)只需對(duì)系數(shù)矩陣的增廣矩陣進(jìn)行變換即可 ，稱alj為旋轉(zhuǎn)元。 第45頁(yè)/共87頁(yè) 47 cjc1ckcm cm+1 cjcn CBXBb*x1

38、xkxm xm+1 xjxn c1x1b1*100 a1m+1 a1ja1n ClXlbl*010 alm+1 aljaln cmxmbm*001 amm+1 amjamn CN - CBB-1A000 m+1 j n 表13 初始單純形表 第46頁(yè)/共87頁(yè) 48 以表13中的元素alj (稱為主元素或旋轉(zhuǎn)元素)進(jìn)行基變換： 將第l行每個(gè)元素除以 alj，再將第 l行每個(gè)元素乘以 aij / alj 加到 第 i 行( i = 1,2, ,m , i l )，將第 l 行每個(gè)元素乘以 j / alj 加 到檢驗(yàn)數(shù)行，對(duì)應(yīng)的新的目標(biāo)函數(shù)值即為： 經(jīng)過(guò)基變換之后，針對(duì)于新基 B1 的基本可行解為

39、： * 10 (1.16) l j lj b ZZ a * * * (1) 1,2, ()(1.17) 0 l ji lj l ij lj b bbim il a b xbijl a il 即為原來(lái)的 的位置 第47頁(yè)/共87頁(yè) 49 第一步：找出初始可行基，確定初始基本可行解，建立初 始單純形表； 第二步：檢查對(duì)應(yīng)于非基變量的檢驗(yàn)數(shù) k ，kIN ，(IN為 非基變量指標(biāo)集)，若所有 k 0 ，kIN ，則已得到最優(yōu) 解，停止計(jì)算，否則轉(zhuǎn)入下一步； 第三步：在所有k 0，kIN 中，若有一個(gè)j 對(duì)應(yīng)的系數(shù) 列向量 aij 0，則此問(wèn)題沒(méi)有有限最優(yōu)解，停止計(jì)算，否 則轉(zhuǎn)入下一步； 第四步：根據(jù)

40、 max kk 0，kIN = j，確定 xj 為換 入變量(即為新基的基變量)，再根據(jù)： 確定 xl為換出變量(即為新基的非基變量)，轉(zhuǎn)下一步； 第五步：以 alj 為主元素進(jìn)行基變換，轉(zhuǎn)回第二步。 * min0,1 li lij ljij bb aim aa 第48頁(yè)/共87頁(yè) 50 利用單純形算法求解例利用單純形算法求解例11的線性規(guī)劃問(wèn)題。的線性規(guī)劃問(wèn)題。 Max Z=2x1+3x2+0 x3+0 x4+0 x5 3x2+x3=15 s.t. 4x1+x4=12 2x1+2x2x5=14 x1，x2，x3，x4，x50 cj23000 i XBbx1x2x3x4x5 x31503100

41、5 x41240010 x514220017 -Z023000 解：解： （1）由標(biāo)準(zhǔn)型得到初始單純形表：）由標(biāo)準(zhǔn)型得到初始單純形表： 3x2+x3 =15 4x1+ x4 =12 2x1+2x2 x5=14 第49頁(yè)/共87頁(yè) 51 (2) max1, 2=3=2，所以x2為換入變量。 (3) 因?yàn)?=2，2=3都大于0，且p1,p2的坐標(biāo)有正分量存在 因?yàn)?與x3那一行相對(duì)應(yīng)，所以x3為換出變量； 故x2對(duì)應(yīng)列與x3對(duì)應(yīng)行的相交處的3為主元素； (4) 以“3”為主元素進(jìn)行旋轉(zhuǎn)計(jì)算，進(jìn)行行初等變換，得表15 ： 表15 min|0min 5,75 il ik i iklk bb a aa

42、cj23000 i XBbx1x2x3x4x5 x2 5011/300 x412400103 x5420-2/3012 -Z-1520-100 第50頁(yè)/共87頁(yè) 52 重復(fù)以上步驟得表16。 表16 這時(shí)，檢驗(yàn)數(shù)全部小于等于0，即目標(biāo)函數(shù)已不可能再增大，于 是得到最優(yōu)解： X*=(2,5,0,4,0) 目標(biāo)函數(shù)的最大值為： Z*=19 cj23000 i XBBx1x2x3x4x5 x25011/300 x44004/31-2 x1210-1/301/2 -Z-1900-1/30-1 T 第51頁(yè)/共87頁(yè) 53 利用單純形算法求解線性規(guī)劃問(wèn)題。 Max Z=4x1+3x2+0 x3+0 x

43、4+0 x5 2x1+2x2+ x3=1600 5x1+2.5x2+x4=2500 x1+x5 =400 x1, x2, x3, x4, x50 解： （1）由標(biāo)準(zhǔn)型得到初始單純形表17： 表表17 cj43000 i XBbx1x2x3x4x5 x3160022100800 x4250052.5010500 x540010001400 -Z043000 第52頁(yè)/共87頁(yè) 54 表18 cj43000 i XBbx1x2x3x4x5 x38000210-2400 x450002.501-5200 x140010001- -Z - 16000300-4 表19 cj43000 i XBbx1x

44、2x3x4x5 x3400001-0.82200 x22000100.4-2- x140010001400 -Z - 2200000-1.22 第53頁(yè)/共87頁(yè) 55 表110 cj43000 i XBbx1x2x3x4x5 x5200000.5-0.41 x2600011-0.40- x120010-0.50.40 -Z - 260000-1-0.40 這時(shí)，檢驗(yàn)數(shù)全部小于等于0，即目標(biāo)函數(shù)已達(dá)到最大， 因此得到最優(yōu)解： X=(200,600,0,0,200) 目標(biāo)函數(shù)的最大值為： Z=2600 T 第54頁(yè)/共87頁(yè) 56 利用單純形算法求解線性規(guī)劃問(wèn)題。 Max Z=2x1+3x2+0

45、 x3+0 x4+0 x5+0 x6 2x1+2x2+x3=12 s.t. x1+2x2+x4=8 4x1+x5=16 4x2+x6=12 x1，x2，x3，x4，x5, x60 解： （1）由標(biāo)準(zhǔn)型得到初始單純形表： 表111 cj230000i XBbx1x2x3x4x5x6 x3122210006 x481201004 x516400010 x6120400013 -Z0230000 第55頁(yè)/共87頁(yè) 57 表112 cj230000i XBbx1x2x3x4x5x6 x3620100-1/23 x4210010-1/22 x5164000104 x23010001/4 -Z-9200

46、00-3/4 表113 cj230000i XBbx1x2x3x4x5x6 x32001-201/24 x1210010-1/2 x58000-4124 x23010001/412 -Z-13000-201/4 第56頁(yè)/共87頁(yè) 58 在相同 對(duì)應(yīng)的變量中選擇下標(biāo)最大的那個(gè)基變量-換出變量； 同時(shí)如果出現(xiàn)有兩個(gè)或更多的檢驗(yàn)數(shù)大于零且相同時(shí)，在相同 對(duì)應(yīng)的變量中選擇下標(biāo)最小的那個(gè)基變量為進(jìn)入變量， -避免出現(xiàn)“死循環(huán)” 表114 cj230000i XBbx1x2x3x4x5x6 x30001-1-1/40 x1410011/40 x64000-21/21 x220101/2-1/80 -Z-

47、14000-3/2 -1/80 最優(yōu)解： X*=(4,2,0,0,0,4) 目標(biāo)函數(shù)的最大值為： Z*=14 T 第57頁(yè)/共87頁(yè) 59 (一一)、大、大M法法 (二二)、兩階段法、兩階段法 初始基本可行解的求法初始基本可行解的求法 第58頁(yè)/共87頁(yè) 60 解解: 令令S= - S 加入松弛變量加入松弛變量x4, 剩余變量剩余變量x5 求解求解L.P.的最優(yōu)解的最優(yōu)解: x1 -2x2 + x3 11 11 -4x1 + x2 + 2x3 3 3 -2x1 +x3= = 1 1 x1 , x2 , x3 0 minS= -3x1 + x2 + x3 +x6 +x7 ,x6 ,x7 -M x

48、6-M x7 再加入再加入人工變量人工變量x6 ,x7 s. t. x1 -2x2 + x3 +x4 = =1111 -4x1 + x2 + 2x3 -x5 = =3 3 -2x1 +x3 = =1 1 x1 , x2 , ,x5 , 0 max S= 3x1 - x2 -x3 s. t. 第59頁(yè)/共87頁(yè) 61 x4111-211000 x63-4120-110 x71-2010001 表表1 3-6MM-13M-10-M00 cj3-1-100-M-M XBb*x1x2x3x4x5x6x7 x4111-211000 x63-4120-110 x71-2010001 -S03-1-100-

49、M-M 第60頁(yè)/共87頁(yè) 62 cj3-1-100-M-M XBb*x1x2x3x4x5x6x7 x4111-211000 x63-4120-110 x71-2010001 表表1 3-6MM-13M-10-M00 x4103-20100-1 x610100-11-2 x31-2010001 表表21M-100-M0 1-3M 第61頁(yè)/共87頁(yè) 63 cj3-1-100-M-M XBb*x1x2x3x4x5x6x7 x4123001-22-5 x210100-11-2 x31-2010001 表表31000-11-M-1-M x14100 1/3-2/32/3-5/3 x21010 0-1

50、1-2 x39001 2/3-4/34/3-7/3 表表4000 -1/3-1/31/3-M2/3-M 所有所有 j 0，X* = ( 4, 1, 9, 0, 0, 0, 0 )T S = 2 S= -2 第62頁(yè)/共87頁(yè) 64 判定判定無(wú)解無(wú)解條件：條件： 當(dāng)進(jìn)行到最優(yōu)表時(shí)，仍有人工變量在當(dāng)進(jìn)行到最優(yōu)表時(shí)，仍有人工變量在 基中，且基中，且0，則說(shuō)明原問(wèn)題無(wú)可行解則說(shuō)明原問(wèn)題無(wú)可行解 。 第63頁(yè)/共87頁(yè) 65 用兩階段法求解用兩階段法求解L.P的最優(yōu)解的最優(yōu)解: 解解:加入松弛變量、剩余變量、加入松弛變量、剩余變量、 人工變量：人工變量： x6 , x7 第一階段的問(wèn)題第一階段的問(wèn)題 m

51、in W= x6 +x7 = max W= - x6 - x7 x1 -2x2 + x3 11 11 -4x1 + x2 + 2x3 3 3 -2x1 +x3= =1 1 x1 , x2 , x3 0 maxS= 3x1 -x2 -x3 x1 -2x2 + x3 +x4 = =1111 -4x1 + x2 + 2x3 -x5 = =3 3 -2x1 +x3 = =1 1 x1 , x2 , ,x5 , 0 +x6 +x7 ,x6 ,x7 s. t. s. t. 第64頁(yè)/共87頁(yè) 66 cj00000-1-1 XBb*x1x2x3x4x5x6x7 x4111-211000非非 單單 純純 形形

52、 表表 x63-4120-110 x71-2010001 - W 000000-1-1 XBb*x1x2x3x4x5x6x7 x4111-211000 x63-4120-110 x71-2010001 -W4-6130-100 第65頁(yè)/共87頁(yè) 67 cj00000-1-1 XBb*x1x2x3x4x5x6x7 x4111-211000 x63-4120-110 x71-2010001 -W4-6130-100 x4103-20100-1 x610100-11-2 x31-2010001 -W10100-10-3 x4123001-22-5 x210100-11-2 x31-2010001

53、最優(yōu)表最優(yōu)表000000-1-1 第66頁(yè)/共87頁(yè) 68 第二階段的計(jì)算問(wèn)題第二階段的計(jì)算問(wèn)題 x1 -2x2 + x3 +x4 = =1111 -4x1 + x2 + 2x3 -x5 = =3 3 -2x1 +x3 = =1 1 x1 , x2 , ,x5 0 max S= 3x1 -x2 -x3 cj3-1-100 XBb*x1x2x3x4x5 x4123001-2 x210100-1 x31-20100 -S03-1-100 s. t. 第67頁(yè)/共87頁(yè) 69 x141001/3-2/3 x210100-1 x390012/3-4/3 表表2-2000-1/3 -1/3 cj3-1-

54、100 XBb*x1x2x3x4x5 x4123001-2 x210100-1 x31-20100 表表121000-1 第68頁(yè)/共87頁(yè) 70 原問(wèn)題原問(wèn)題 max S= Cj xj j=1 n xj 0 j=1 n aij xj =bi ( i=1,2, ,m) 作作輔助問(wèn)題輔助問(wèn)題 min W= yi i=1 m xj ， ， x人人 0 j=1 n aij xj + x人 人 =bi ( i=1,2, ,m) 第一階段：解輔助問(wèn)題，當(dāng)進(jìn)行到最優(yōu)表時(shí)第一階段：解輔助問(wèn)題，當(dāng)進(jìn)行到最優(yōu)表時(shí) 、若若W=0, 則得到原問(wèn)題的一個(gè)基本可行則得到原問(wèn)題的一個(gè)基本可行 解，轉(zhuǎn)入第解，轉(zhuǎn)入第2階段。

55、階段。 第二階段：用求出的初始基本可行解求最優(yōu)解。第二階段：用求出的初始基本可行解求最優(yōu)解。 、若、若W0, 則判定原問(wèn)題無(wú)可行解則判定原問(wèn)題無(wú)可行解 第69頁(yè)/共87頁(yè) 71 max S= 2x1 +x2 5x1 +10 x2 8 2x1 +2x2 1 x1 ，x2 0 第第(1)(1)階段：階段： min W= x5 5x1 +10 x2 -x3 +x5 =8 2x1 +2x2 +x4 = =1 x1 x5 0 x2 x1 O 無(wú)可行解無(wú)可行解 s. t. 第70頁(yè)/共87頁(yè) 72 0 0 0 0 1 0 0 0 0 1 b XB x1 x2 x3 x4 x5 8 x5 5 10 -1 0

56、 1 1 x4 2 (2) 0 1 0 -5 -10 1 0 0 3 x5 -5 0 -1 -5 1 1/2 x2 1 1 0 1/2 0 最優(yōu)表最優(yōu)表 5 0 1 5 0 原問(wèn)題無(wú)可行解原問(wèn)題無(wú)可行解 第71頁(yè)/共87頁(yè) 73 (1)(1)、L.PL.P數(shù)學(xué)模型及標(biāo)準(zhǔn)型數(shù)學(xué)模型及標(biāo)準(zhǔn)型 maxS=CX AX=b (b 0) ) X 0 (2)(2)、L.PL.P問(wèn)題解的性質(zhì)：圖解法問(wèn)題解的性質(zhì)：圖解法 (3)(3)、單純形法：、單純形法： 1)1)、標(biāo)準(zhǔn)型中有單位基。、標(biāo)準(zhǔn)型中有單位基。 2)2)、標(biāo)準(zhǔn)型中沒(méi)有單位基，用大、標(biāo)準(zhǔn)型中沒(méi)有單位基，用大M M法加人工變法加人工變 量，使之構(gòu)成單位

57、基。量，使之構(gòu)成單位基。 求求max S時(shí)，目標(biāo)中時(shí)，目標(biāo)中M MXj 求求min S時(shí)，目標(biāo)中時(shí)，目標(biāo)中M MXj 3)3)、判定最優(yōu)解定理：、判定最優(yōu)解定理：maxS問(wèn)題，檢驗(yàn)數(shù)問(wèn)題，檢驗(yàn)數(shù) j 0 minS問(wèn)題，檢驗(yàn)數(shù)問(wèn)題，檢驗(yàn)數(shù) j 0 第72頁(yè)/共87頁(yè) 74 建模有問(wèn)題建模有問(wèn)題 5)5)、退化解問(wèn)題、退化解問(wèn)題 4)4)、解的幾種情況：、解的幾種情況： 唯一解唯一解 無(wú)窮多解最優(yōu)表中無(wú)窮多解最優(yōu)表中非非基變量檢驗(yàn)數(shù)有為基變量檢驗(yàn)數(shù)有為0 0者。者。 無(wú)界解無(wú)界解 max, j 0 但但Pj 0 min, j 0 但但Pj 0 無(wú)可行解最優(yōu)表中人工變量基變量中，且無(wú)可行解最優(yōu)表中人

58、工變量基變量中，且0 0。 第73頁(yè)/共87頁(yè) 75 我們以我們以 作為標(biāo)準(zhǔn)型，以作為標(biāo)準(zhǔn)型，以 作為最優(yōu)解的判別準(zhǔn)則。還有其它形式作為最優(yōu)解的判別準(zhǔn)則。還有其它形式 ，下面把幾種檢驗(yàn)數(shù)的表示方法及判別準(zhǔn)則匯總于表，下面把幾種檢驗(yàn)數(shù)的表示方法及判別準(zhǔn)則匯總于表126 。 max,0 T ZC X AXb X 0 jjj cz 表126 Max Z=CTX AX=b,X00 Min Z=CTX AX=b,X00 cj-zj0000 zj-cj0000 標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型 檢驗(yàn)數(shù)檢驗(yàn)數(shù) 對(duì)于目標(biāo)函數(shù)求極小值的問(wèn)題采用上述任何一種處理方 法，其單純形法的步驟與求極大值的方法相同。 這里提醒注意，在閱讀其它

59、有關(guān)線性規(guī)劃的教科書(shū)時(shí)， 一定要注意該書(shū)規(guī)定的標(biāo)準(zhǔn)型是目標(biāo)函數(shù)求極大值還是求極 小值，檢驗(yàn)數(shù)是cj-zj還是zj-cj，不同的組合會(huì)使判別準(zhǔn)則不同 ，但單純形的計(jì)算步驟是不變的。 第74頁(yè)/共87頁(yè) 76 現(xiàn)要做現(xiàn)要做100套鋼架，每套用長(zhǎng)為套鋼架，每套用長(zhǎng)為2.9m,2.1m和和1.5m的圓鋼各一的圓鋼各一 根。已知原材料長(zhǎng)根。已知原材料長(zhǎng)7.4m，問(wèn)應(yīng)如何下料，使用的總原材料最，問(wèn)應(yīng)如何下料，使用的總原材料最 ?。菏。?IIIIIIIVV 121 221 3123 7.47.37.27.16.6 00.10.20.30.8 合計(jì)用料合計(jì)用料 料頭料頭 2.9m 2.1m 1.5m 第75頁(yè)

60、/共87頁(yè) 77 解解:設(shè)設(shè)xi表示第表示第 i項(xiàng)目的投資額項(xiàng)目的投資額 i =1,2,3,4,5，目標(biāo)是投資風(fēng)險(xiǎn)最小化，目標(biāo)是投資風(fēng)險(xiǎn)最小化 ，因此目標(biāo)函數(shù)為：，因此目標(biāo)函數(shù)為： min Z= ( 0.1x1 + 0.06x2 +0.18x3 + 0.12x4+ 0.04x5 ) 約束條件為：約束條件為： x1 + x2 + x3 + x4+ x5 = 1,000,000 0.05 x1 + 0.08 x2 + 0.07 x3 + 0.06 x4+ 0.1 x5 80,000 0.1x1 + 0.17 x2 + 0.14 x3 + 0.22 x4+0.07 x5140,000 (11 x1