1、會計學1線性規(guī)劃線性規(guī)劃(xin xn u hu)及單純形法及單純形法 新新第一頁，共190頁。2022-5-42第2頁/共190頁第二頁，共190頁。2022-5-43教學計劃教學計劃 以線性規(guī)劃和運輸問題為講以線性規(guī)劃和運輸問題為講授重點，其它部分授重點，其它部分(b fen)作為作為選講內(nèi)容。選講內(nèi)容。教學方法教學方法 以授課為主，案例分析與上以授課為主，案例分析與上機演示為輔。而講課中主要培機演示為輔。而講課中主要培養(yǎng)用最優(yōu)化方法解決實際問題養(yǎng)用最優(yōu)化方法解決實際問題的能力。的能力。教學計劃(jio xu j hu)與方法第3頁/共190頁第三頁，共190頁。2022-5-44求解(q

2、i ji)結(jié)果.求解結(jié)果.建立模型求解模型修改模型求解結(jié)果.修改模型實際問題數(shù)學模型第4頁/共190頁第四頁，共190頁。2022-5-45英文是Operational Research，在美國稱為Operations Research。第5頁/共190頁第五頁，共190頁。2022-5-46優(yōu)化、排隊論、決策理論、庫存理論等。在本課程中，結(jié)合管理學科的特點，主要介紹線性規(guī)劃和運輸問題。第6頁/共190頁第六頁，共190頁。2022-5-47線性規(guī)劃線性規(guī)劃(xin xn u hu)(xin xn u hu)數(shù)數(shù)學學規(guī)規(guī)劃劃非線性規(guī)劃非線性規(guī)劃(guhu)(guhu)整數(shù)整數(shù)(zhngsh)(

3、zhngsh)規(guī)劃規(guī)劃動態(tài)規(guī)劃動態(tài)規(guī)劃學學科科內(nèi)內(nèi)容容多目標規(guī)劃多目標規(guī)劃雙層規(guī)劃雙層規(guī)劃組組合合優(yōu)優(yōu)化化最優(yōu)計數(shù)問題最優(yōu)計數(shù)問題網(wǎng)絡優(yōu)化網(wǎng)絡優(yōu)化排序問題排序問題統(tǒng)籌圖統(tǒng)籌圖隨隨機機優(yōu)優(yōu)化化對策論對策論排隊論排隊論庫存論庫存論決策分析決策分析可靠性分析可靠性分析運籌學的主要內(nèi)容第7頁/共190頁第七頁，共190頁。2022-5-48第8頁/共190頁第八頁，共190頁。2022-5-49第9頁/共190頁第九頁，共190頁。2022-5-410第1節(jié)線性規(guī)劃(xin xn u hu)問題及其數(shù)學模型n生產(chǎn)計劃問題n配料問題n背包問題n運輸(ynsh)問題n指派問題1.1問題(wnt)的提出第1

4、0頁/共190頁第十頁，共190頁。2022-5-4111. 生產(chǎn)計劃(jhu)問題（Production Planning）產(chǎn)品甲產(chǎn)品乙產(chǎn)品丙產(chǎn)品丁設備能力（小時）設備A1.51.02.41.02000設備B1.05.01.03.58000設備C1.53.03.51.05000利潤（元/件）5.247.308.344.18某工廠擁有A、B、C三種類型的設備，生產(chǎn)甲、乙、丙、丁四種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占有的設備機時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設備可利用(lyng)的時數(shù)如下表所示：求使得總利潤最大的生產(chǎn)(shngchn)計劃。第11頁/共190頁第十一頁，共190頁。2022-5-

5、412產(chǎn)品甲產(chǎn)品乙產(chǎn)品丙產(chǎn)品丁設備能力（小時）設備A1.51.02.41.02000設備B1.05.01.03.58000設備C1.53.03.51.05000利潤（元/件）5.247.308.344.18設四種產(chǎn)品(chnpn)的產(chǎn)量分別為x1，x2，x3，x4，總利潤為z，線性規(guī)劃模型為：max z=5.24x1+7.30 x2+8.34x3+4.18x4s.t. 1.5x1+1.0 x2+2.4x3+1.0 x42000 1.0 x1+5.0 x2+1.0 x3+3.5x48000 1.5x1+3.0 x2+3.5x3+1.0 x45000 x1, x2, x3, x40目標(mbio)

6、函數(shù)約束條件變量(binling)非負約束這個問題的最優(yōu)解為：x1=294.12件，x2=1500件，x3=0，x4=58.82件最大利潤為：z=12737.06元。第12頁/共190頁第十二頁，共190頁。2022-5-4132. 配料(pi lio)問題（Material Blending）某工廠要用四種合金T1、T2、T3、T4為原料，經(jīng)熔煉成為新的不銹鋼G。這四種原料含鉻（Cr）、錳（Mn）和鎳（Ni）的含量（），這四種原料的單價以及(yj)新的不銹鋼G所要求的Cr、Mn、Ni的最低含量（）如下表：T1T2T3T4GCr3.214.532.191.763.20Mn2.041.123.5

7、74.332.10Ni5.823.064.272.734.30單價（元/公斤）115978276要求配100公斤不銹鋼G，并假定在配制過程中沒有損耗(snho)。求使得總成本最低的配料方案。第13頁/共190頁第十三頁，共190頁。2022-5-414T1T2T3T4GCr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.30單價（元/公斤）115978276min z=115x1+97x2+82x3+76x4s.t. 3.21x1+4.53x2+2.19x3+1.76x4320 Cr的含量下限(xixin)約束 2.0

8、4x1+1.12x2+3.57x3+4.33x4210 Mn的含量下限(xixin)約束 5.82x1+3.06x2+4.27x3+2.73x4430 Ni的含量下限(xixin)約束 x1+x2+x3+x4=100 物料平衡約束 x1, x2, x3, x40設四種原料(yunlio)分別選取x1，x2，x3，x4公斤，總成本為z。這個問題的最優(yōu)解為：x1=26.58, x2=31.57, x3=41.84，x4=0（公斤）, 最低成本為z=9549.87元。問題：如果某一種成分的含量(hnling)既有下限，又有上限怎么辦？第14頁/共190頁第十四頁，共190頁。2022-5-4153.

9、 背包(bibo)問題（Knapsack Problem）一只背包(bibo)最大裝載重量為50公斤。現(xiàn)有三種物品，每種物品數(shù)量無限。每種物品每件的重量、價格如下表：物品1物品2物品3重量（公斤/件）104120價值（元/件）177235求背包中裝入每種物品(wpn)各多少件，使背包中物品(wpn)總價值最高。第15頁/共190頁第十五頁，共190頁。2022-5-416設三種物品(wpn)的件數(shù)各為x1，x2，x3件，總價值為z。max z=17x1+72x2+35x3s.t. 10 x1+41x2+20 x350 x1，x2，x30 x1，x2，x3為整數(shù)這是一個整數(shù)規(guī)劃問題（Intege

10、r Programming）。這個問題的最優(yōu)解為： x1=1件，x2=0件，x3=2件，最高價值z=87元物品1物品2物品3重量（公斤/件）104120價值（元/件）177235第16頁/共190頁第十六頁，共190頁。2022-5-4174. 運輸(ynsh)問題（Transportation）某種物資從兩個(lin )供應地A1，A2運往三個需求地B1，B2，B3。各供應地的供應量、各需求地的需求量、每個供應地到每個需求地每噸物資的運輸價格如下表：運價（元/噸）B1B2B3供應量（噸）A123535A247825需求量（噸）10302060求總運費最低的運輸(ynsh)方案。第17頁/共1

11、90頁第十七頁，共190頁。2022-5-418運價（元/噸）B1B2B3供應量（噸）A123535A247825需求量（噸）10302060A1A2B3B2B135噸25噸10噸30噸20噸235478第18頁/共190頁第十八頁，共190頁。2022-5-419運價（元/噸）B1B2B3供應量（噸）A123535A247825需求量（噸）10302060設從兩個供應地到三個需求(xqi)地的運量（噸）如下表：B1B2B3A1x11x12x13A2x21x22x23第19頁/共190頁第十九頁，共190頁。2022-5-420運價（元/噸）B1B2B3供應量（噸）A123535A247825

12、需求量（噸）10302060min z=2x11+3x12+5x13+4x21+7x22+8x23s.t. x11+x12+x13 =35 供應地A1 x21+x22+x23 =25 供應地A2 x11 +x21 =10 需求(xqi)地B1 x12 +x22 =30 需求(xqi)地B2 x13 +x23 =20 需求(xqi)地B3 x11, x12, x13, x21, x22, x230 第20頁/共190頁第二十頁，共190頁。2022-5-421運量（噸）B1B2B3供應量（噸）A130535A2101525需求量（噸）10302060這個問題的最優(yōu)解表示(biosh)如下：最小總

13、運費(yn fi)為：z=330+55+410+815=275元A1A2B3B2B135噸25噸10噸30噸20噸23547830噸5噸10噸15噸第21頁/共190頁第二十一頁，共190頁。2022-5-4225. 指派(zhpi)問題（Assignment Problem）有n項任務由n個人完成(wn chng)，每項任務交給一個人，每人都有一項任務。由i個人完成(wn chng)j項任務的成本（或效益）為cij。求使總成本最小（或總效益最大）的分配方案。設：項任務個人被指派完成第第項任務個人不從事第第ji1ji0 xij1 , 0 xn,.,2 , 1i1xn,.,2 , 1j1x. t

14、 . sxczmax(min)ijn1jijn1iijn1in1jijij第22頁/共190頁第二十二頁，共190頁。2022-5-423張、王、李、趙四位老師被分配教語文、數(shù)學(shxu)、物理化學四門課程，每位老師教一門課，每門課由一位老師教。根據(jù)這四位老師以往教課的情況，他們分別教四這門課程的平均成績?nèi)缦卤怼Ｒ蟠_定哪一位老師上哪一門課，使四門課的平均總成績最高。語文數(shù)學物理化學張92688576王82917763李83907465趙93618375第23頁/共190頁第二十三頁，共190頁。2022-5-424門課個老師教第第門課個老師不教第第ji1ji0 xij設：語文數(shù)學物理化學張

15、x11x12x13x14王x21x22x23x24李x31x32x33x34趙x41x42x43x44max z=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+ 83x31+90 x32+74x33+65x34+93x41+61x42+83x43+75x44s.t. x11+x12+x13+x14=1 (1) x21+x22+x23+x24=1 (2) x31+x32+x33+x34=1 (3) x41+x42+x43+x44=1 (4) x11+x21+x31+x41=1 (5) x12+x22+x32+x42=1 (6) x13+x23+x

16、33+x43=1 (7) x14+x24+x34+x44=1 (8) xij=0,1第24頁/共190頁第二十四頁，共190頁。2022-5-425最優(yōu)解為：x14=1，x23=1，x32=1，x41=1，max z=336即張老師教化學(huxu)，王老師教語文，李老師教數(shù)學，趙老師教語文。語文數(shù)學物理化學張0001王0010李0100趙1000語文數(shù)學物理化學張92688576王82917763李83907465趙93618375四門(s mn)課的總分可以達到336分。第25頁/共190頁第二十五頁，共190頁。2022-5-426線性規(guī)劃(xin xn u hu)模型min(max)

17、z=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn (, )b1 a21x1+a22x2+a2nxn (, )b2 am1x1+am2x2+amnxn (, )bm x1, x2, , xn 0 (, Free)線性規(guī)劃模型的目標(mbio)函數(shù)必須是變量的線性函數(shù)，約束條件必須是變量的線性等式或不等式。如右的問題就不是線性規(guī)劃問題：0 x,x,x9x4+x+x8xx+x+x2. t . sxx2+x3=zmin32132113212121第26頁/共190頁第二十六頁，共190頁。2022-5-4271.2線性規(guī)劃(xin xn u hu)的標準形式目標函數(shù)為極大(

18、j d)化，約束條件全部為等號約束，右端常數(shù)項均為非負，所有變量全部是非負的，這樣的線性規(guī)劃模型稱為標準形式maxz=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0 第27頁/共190頁第二十七頁，共190頁。2022-5-428線性規(guī)劃模型用矩陣和向量(xingling)表示max z=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm

19、x1, x2, , xn 0 mn2m1mn22221n11211aaaaaaaaaAm21bbbbn21ccccn21xxxX第28頁/共190頁第二十八頁，共190頁。2022-5-429線性規(guī)劃模型用矩陣和向量(xingling)表示（續(xù)）nn2211n21n21TxcxcxcxxxcccXCznmn22m11mnn2222121nn1212111n21mn2m1mn22221n11211xaxaxaxaxaxaxaxaxaxxxaaaaaaaaaAX因此，線性規(guī)劃模型可以寫成如下矩陣(j zhn)和向量的形式MaxZ =CTXs.t. AX=b X0 第29頁/共190頁第二十九頁，共

20、190頁。2022-5-430線性規(guī)劃(xin xn u hu)模型總結(jié)線性規(guī)劃模型的結(jié)構(gòu)目標函數(shù) ：max，min約束條件：,=,變量(binling)符號：0, 0, Free線性規(guī)劃的標準形式目標函數(shù)：max約束條件：=右端常數(shù)項： 0變量(binling)符號：0Free0XbAXtsXCzT,)(),(. .max(min)MaxZ =CTXs.t. AX=b X0 第30頁/共190頁第三十頁，共190頁。2022-5-431線性規(guī)劃(xin xn u hu)問題的標準化n極小化目標函數(shù)轉(zhuǎn)化為極大(j d)化n小于等于約束條件轉(zhuǎn)化為等號約束n大于等于約束條件轉(zhuǎn)化為等號約束n右端常數(shù)

21、項小于等于0的標準化n變量小于等于0的標準化n變量沒有符號限制（Free）的標準化第31頁/共190頁第三十一頁，共190頁。2022-5-432非標準形式如何(rh)化為標準1) Min型化為Max型 CXMinzCXMaxz/加負號(f ho) 因為(yn wi)，求一個函數(shù)的極小點，等價于求該函數(shù)的負函數(shù)的極大點。)(xf)(xf*x注意： Min型化為Max型求解后，最優(yōu)解不變，但最優(yōu)值差負號。 第32頁/共190頁第三十二頁，共190頁。2022-5-433 min z=2x1-3x2+x3令 z=-z，z=-2x1+3x2-x3新的目標函數(shù) max z=-2x1+3x2-x3取得(

22、qd)極大化的最優(yōu)解時，這個最優(yōu)解同時使原目標函數(shù)值取得(qd)最小化的最優(yōu)解。但兩個問題最優(yōu)解的目標函數(shù)值相差一個負號。極小化目標(mbio)函數(shù)問題轉(zhuǎn)化為極大化目標(mbio)函數(shù)第33頁/共190頁第三十三頁，共190頁。2022-5-434例如，對于以下兩個(lin )線性規(guī)劃問題min z=2x1+3x2s.t. x1+x23 x21 (A) x1, x20max z=-2x1-3x2s.t. x1+x23 x21 (B) x1, x20它們(t men)的最優(yōu)解都是x1=2, x2=1，但(A)的最小化的目標函數(shù)值為min z=7，(B)的最大化的目標函數(shù)值為max z=-7第34

23、頁/共190頁第三十四頁，共190頁。2022-5-4352) 不等式約束(yush)化為等式約束(yush)分析：以下面(xi mian)約束為例3604921 xx之所以“不等”是因為左右兩邊有一個差額，稱為“松弛量”，若在左邊加上這個(zh ge)松弛量，則化為等式。而這個松弛量也是變量，記為 ，則有36049321xxx稱為松弛變量。問題：它的實際意義是什么？ 資源的“剩余”。3x3x第35頁/共190頁第三十五頁，共190頁。2022-5-436 2x1+3x2-4x35引進松弛(sn ch)變量(Slack variable) x4=5-(2x1+3x2-4x3)，把松弛(sn c

24、h)變量x4加在約束條件左邊，就可以將小于等于約束變?yōu)榈仁健?2x1+3x2-4x3+x4=5由此可以知道，松弛(sn ch)變量x40。如果有一個以上小于等于約束，要對于每一個約束引進不同的松弛(sn ch)變量。例如： 2x1+3x2-4x35 3x1-2x2+5x38在兩個約束中分別引進松弛(sn ch)變量x4，x50 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 +x5=8小于等于(dngy)約束條件轉(zhuǎn)化為等號約束第36頁/共190頁第三十六頁，共190頁。2022-5-437將不等式約束變?yōu)榈仁郊s束。例如： 2x1+3x2-4x35 3x1-2x2+5x38在兩個(l

25、in )約束的左邊分別減去剩余變量x4，x50 2x1+3x2-4x3-x4 =5 3x1-2x2+5x3 -x5=8大于等于(dngy)約束條件轉(zhuǎn)化為等號約束第37頁/共190頁第三十七頁，共190頁。2022-5-438練習(linx)：請將下列約束化為標準型0,3001032005436049.21212121解：增加(zngji)松弛變量則約束(yush)化為,543xxx0,300 10320054360 49.54321521421321易見，增加的松弛變量的系數(shù)恰構(gòu)成一個單位陣I。第38頁/共190頁第三十八頁，共190頁。2022-5-439一般(ybn)地，記松弛變量的向量為

26、 Xs，則0. .XbAXts0,. .ssXXbIXAXts0. .XbAXts0,. .ssXXbIXAXts問題(wnt)：松弛變量在目標中的系數(shù)為何？ 0。 3) 當模型中有某變量 xk 沒有非負要求(yoqi)，稱為自由變量, 則可令 0,/kkkkkxxxxx化為標準型。第39頁/共190頁第三十九頁，共190頁。2022-5-440沒有(mi yu)符號限制的變量，用兩個非負變量之差表示。例如：min z=x1+2x2-3x3s.t. 2x1+3x2-4x35 3x1-2x2+5x38 x10, x2:free, x30先將目標函數(shù)轉(zhuǎn)化為極大化，并在約束中引進松弛變量，把不等式約

27、束變?yōu)榈仁健ax z=-x1-2x2+3x3s.t. 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x10, x2:free, x3, x4, x50變量沒有(mi yu)符號限制(Free)的標準化第40頁/共190頁第四十頁，共190頁。2022-5-441Max z=-x1-2x2+3x3s.t. 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3-x5=8 x10, x2:free, x3, x4, x50然后，令x2=x2-x2”，其中x2,x2”0。代入模型，消去x2Max z=-x1-2(x2-x”2)+3x3s.t. 2x1+3(x2-x”2

28、)-4x3+x4 =5 3x1-2(x2-x”2)+5x3 -x5=8 x1, x2, x”2, x3, x4,x50整理，得到(d do)標準形式：Max z=-x1-2x2+x”2+3x3s.t. 2x1+3x2-3x”2-4x3+x4 =5 3x1-2x2+2x”2+5x3 -x5=8 x1, x2, x”2, x3, x4,x50第41頁/共190頁第四十一頁，共190頁。2022-5-442第42頁/共190頁第四十二頁，共190頁。2022-5-443min z=x1+2x2-3x3s.t. 2x1+3x2-4x35 3x1-2x2+5x38 x10, x20, x30max z=

29、-x1-2x2+3x3s.t. 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x10, x20, x3, x4, x50令 x2=-x2，x20, 代入模型(mxng)max z=-x1+2x2+3x3s.t. 2x1-3x2-4x3+x4 =5 3x1+2x2+5x3 -x5=8 x10, x20, x3, x4, x505）變量(binling)小于等于0的的標準化第43頁/共190頁第四十三頁，共190頁。2022-5-444第44頁/共190頁第四十四頁，共190頁。2022-5-445）（）（）（3, 0)(2),(. .1max(min)FreeXbAXt

30、sXCzT解值。相應的函數(shù)值稱為最優(yōu)劃的最優(yōu)解；到極值的可行解稱為規(guī)稱為可行域，使規(guī)劃達可行解，可行解的全體），則其是規(guī)劃的一個滿足（若解是規(guī)劃的一個解；），則稱滿足條件（維實向量若32xn21xxxxxn設線性規(guī)劃(xin xn u hu)第45頁/共190頁第四十五頁，共190頁。2022-5-4461234501134,01143XXXXX 第46頁/共190頁第四十六頁，共190頁。2022-5-447（1）可行(kxng)解與最優(yōu)解；的解，記為可行解：滿足全體約束X。，有解則對任可行的，記為最優(yōu)解：可行解中最優(yōu)* ,CXCXXX直觀(zhgun)上，可行解是可行域中的點，是一個可行的

31、方案； 最優(yōu)解是可行域的角點，是一個最優(yōu)的方案。第47頁/共190頁第四十七頁，共190頁。2022-5-448(mbio)函數(shù)為最優(yōu)的可行解為最優(yōu)解。圖解法的目的是判別線性規(guī)劃問題的求解結(jié)局和存在最優(yōu)解的條件下求出最優(yōu)解。第48頁/共190頁第四十八頁，共190頁。2022-5-449第49頁/共190頁第四十九頁，共190頁。2022-5-450線性規(guī)劃(xin xn u hu)的圖解max z=x1+3x2s.t. x1+ x26-x1+2x28x1 0, x20可行(kxng)域目標(mbio)函數(shù)等值線最優(yōu)解6543211 2 3 4 5 6-8 -7 -6 -5 -4 -3 -2

32、-1 0 x1x2z=6z=3z=9z=12問題：1、線性規(guī)劃的最優(yōu)解是否可能位于可行域的內(nèi)部？ 2、線性規(guī)劃的最優(yōu)解是否可能位于可行域的邊界上？第50頁/共190頁第五十頁，共190頁。2022-5-451 x1, x20無界解 3.maxZ=3x1+9x2 x1+3x2 22 -x1+x2 4 x1, x20無窮(wqing)多最優(yōu)解 4.maxZ=x1+ x2 x1+x2 1 2x1+2x24 x1, x20無解第51頁/共190頁第五十一頁，共190頁。2022-5-452線性規(guī)劃可行域和最優(yōu)解的幾種(j zhn)情況1、可行域封閉(fngb) 唯一最優(yōu)解2、可行域封閉(fngb) 多

33、個最優(yōu)解3、可行域開放 唯一最優(yōu)解4、可行域開放 多個最優(yōu)解5、可行域開放 目標函數(shù)無界6、無可行解第52頁/共190頁第五十二頁，共190頁。2022-5-453 標準化的線性規(guī)劃問題，有n個變量，m個約束。 maxz=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0 如果(rgu)m個變量的系數(shù)矩陣的行列式不等于0，這個mm的矩陣稱為線性規(guī)劃的一個基。其余的n-m個變量稱為非基變量，m個變量稱為基變量。1.5線性規(guī)劃的基本概念基、基解、基可行(kx

34、ng)解、極點第53頁/共190頁第五十三頁，共190頁。2022-5-454第54頁/共190頁第五十四頁，共190頁。2022-5-455基矩陣(簡稱(jinchng)基)：系數(shù)陣A中的m階可逆子陣，記 為B；其余部分稱為非基矩陣，記為N。基向量(xingling)：基B中的列；其余稱非基向量(xingling)。基變量：與基向量Pj對應的決策變量xj，記其組成的 向量為XB；與非基向量對應的變量稱非基變 量，記其組成的向量為XN。1231241432 12 3,0 xxxxxxxx例 ：下面為某線性規(guī)劃的約束請例舉出其基矩陣和相應的基向量、基變量。第55頁/共190頁第五十五頁，共190

35、頁。2022-5-4561231241432123,0 xxxxxxxx例 ：下面為某線性規(guī)劃的約束請例舉出其基矩陣和相應的基向量、基變量。階可逆子陣有中的，解：本例中，210011221AA 6個。一般(ybn)地，mn 階矩陣A中基的個數(shù)最多有多少個？個。mnC;,100143434311xxXxxPPBB，基變量為，其相應的基向量為。基變量為其相應的基向量為21212122,1221xxXxxPPBB問題(wnt)：本例的A中一共有幾個基？第56頁/共190頁第五十六頁，共190頁。2022-5-457基本(jbn)解與基本(jbn)可行解.0,0, ,1111bBXbBXXNXBbBX

36、bXXNBbAXXXXNBAmABBABNNBNBTNB時，有當取即可表示為約束中的相應地）（列，則可記中的前表示取定后，不妨設中的基當解；為線性規(guī)劃的一個基本的解稱0NbBXbAX可見：一個基本(jbn)解是由一個基決定的。注意：基本(jbn)解僅是資源約束的解，并未要求其非負，因此其未必可行。稱非負的基本(jbn)解為基本(jbn)可行解（簡稱基可行解）。第57頁/共190頁第五十七頁，共190頁。2022-5-458例4：在上例中0,321241421321xxxxxxxx 求相應(xingyng)于基B1和B2的基本解，它們是否基本可行解？,31311001,1001,1001111b

37、BBBNN解：是基本可行解。的基本解為相應于基,)3 ,1 ,0 ,0(NTXB,51-573151-525251,51-525251,1-221112bBBB22不是基本可行解。的基本解為相應于基,0,0)51,-57(2TXB第58頁/共190頁第五十八頁，共190頁。2022-5-459系數(shù)陣A中可找出若干個基B每個基B都對應于一個基本解非負的基本解就是基本可行解幾種(j zhn)解之間的關(guān)系：可行解基本解非可行解基本可行解問題：基本可行(kxng)解是可行(kxng)域中的哪些點？第59頁/共190頁第五十九頁，共190頁。2022-5-4603x第60頁/共190頁第六十頁，共190

38、頁。2022-5-461x1x2x3x4x5Z是否為基可行解1005104520452017350054104055012051005 0415652.5001.517.575403 02282430019最優(yōu)解為x1 2，x24， x3 3，Z19第61頁/共190頁第六十一頁，共190頁。2022-5-4621.6 解的可行性和松弛變量(binling)符號的關(guān)系A(1,2.5)B(2,1)C(1.5,3)max z=2x1+3x2s.t. x1+x24 (1) -x1+x21 (2) x1, x20max z=2x1+3x2s.t. x1+x2+x3 =4 -x1+x2 -x4=1 x1

39、, x2,x3,x40引進(ynjn)松弛變量約束條件(1)約束條件(2)D(3,2)A(1,2.5)滿足(mnz)所有約束條件，x3=0.5, x4=0.5B(2,1)滿足(mnz)(1)，不滿足(mnz)(2)，x3=1, x4=-2C(1.5,3)不滿足(mnz)(1),滿足(mnz)(2)，x3=-0.5, x4=0.5D(3,2)不滿足(mnz)(1)和(2)，x3=-1, x4=-2結(jié)論：如果一個解滿足(mnz)一個約束條件，相應的松弛變量大于等于0。如果一個解不滿足(mnz)一個約束條件，相應的松弛變量小于0。0 1 2 3 4-14321x2x1第62頁/共190頁第六十二頁，

40、共190頁。2022-5-463max z=x1+2x2s.t. x1+x23 x2 1 x1, x2 0max z=x1+2x2s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40 x1=0, x2=0 x3=3, x4=1基可行(kxng)解x1=0, x4=0 x2=1, x3=2基可行(kxng)解x2=0, x3=0 x1=3, x4=1基可行(kxng)解x3=0, x4=0 x1=2, x2=1基可行解x1=0, x3=0 x2=3, x4=-2是基解，但不是可行解OABx3=0 x4=0 x2=0 x1=0CD可行域第63頁/共190頁第六十三頁

41、，共190頁。2022-5-4642.1基本概念第64頁/共190頁第六十四頁，共190頁。2022-5-4653.凸組合(zh)P16第65頁/共190頁第六十五頁，共190頁。2022-5-466第66頁/共190頁第六十六頁，共190頁。2022-5-467maxZ=6x1+5x2 x1+3x290 2x1+x275 2x1+2x2 80 x1, x20maxZ=6x1+5x2 x1+3x2+x390 2x1+ x2 +x4 75 2x1+2x2 +x580 xi0找一個基可行(kxng)解，X（0，0，90，75，80），Z=01）Z6x1+5x2，x1的系數(shù)C16大于C2=5；選擇x

42、1為新的基變量。X3=90-(x1+3x2) 當x3=0，X2=0時，x1=90 選擇x4為X4=75-(2x1+x2) 當x4=0，X2=0時，x1=37.5 換出變量，X5=80-(2x1+2x2) 當x5=0，X2=0時，x1=40 即x4 0最小3.1舉例(j l)第67頁/共190頁第六十七頁，共190頁。2022-5-468最小則X（37.5，0，52.5，0，5）T，Z2252X2-3X42）仍然(rngrn)用非基變量表示基變量X3=52.5-(2.5x2-0.5x4)X1=75/2-(0.5x2+0.5x4)X5=5-(x2-x4)Z225+2x2-3x4第68頁/共190頁

43、第六十八頁，共190頁。2022-5-4694)用非基變量(binling)表示基變量(binling)X3=40-(1.5x4-2.5x5) X1=35-(x4-0.5x5) X2=5-(x5-x4) Z235-x4-2x5 則X（35，5，40，0，0）T，Z235-x4-2x5 為最優(yōu)解第69頁/共190頁第六十九頁，共190頁。2022-5-470（1）線性規(guī)劃模型為標準形式(xngsh)（2）約束條件系數(shù)矩陣中至少有一個單位子矩陣（3）目標函數(shù)中不含基變量這樣的線性規(guī)劃模型稱為規(guī)范型第70頁/共190頁第七十頁，共190頁。2022-5-471線性規(guī)劃(xin xn u hu)基本概

44、念練習（1）036x1x2OABCEFGHI46-2min z=-x1+2x2s.t. 3x1+2x212 (1) x1+2x2 6(2) -2x1+ x2 4(3) x1, x2 01、約束條件（1）對應的直線(zhxin)是（ ），對應的半平面是 約束條件（2）對應的直線(zhxin)是（ ），對應的半平面是 約束條件（3）對應的直線(zhxin)是（ ），對應的半平面是2、這個線性規(guī)劃的可行域是（ ）。3、對于z=2和4,分別畫出目標函數(shù)(hnsh)等值線。4、這個線性規(guī)劃的最優(yōu)解位于（ ）。ACEFBCDHEGHICDGEz=2z=4CD4第71頁/共190頁第七十一頁，共190頁。2

45、022-5-472 由于基可行解是由一個可行基決定(judng)的，因此，確定初始基可行解X0相當于確定一個初始可行基B0。方法：若A中含I，則B0=I； 若A中不含I，則可用人工(rngng)變量法構(gòu) 造一個I。問題：若B0=I，則X0=？可行。,000NMMbbBX3.2單純形法的步驟第72頁/共190頁第七十二頁，共190頁。2022-5-4732. 最優(yōu)性檢驗(jinyn)問題(wnt)：用什么檢驗？ 目標(mbio)。NBNBNNNBNbNBXNBCCbBCXCNXBbBCXXCCCXz)(NN)()(11而目標優(yōu)。時，當前基可行解為最，則當記 01NBCCBN問題：非最優(yōu)的特征為何

46、？。至少有某個檢驗數(shù)0第73頁/共190頁第七十三頁，共190頁。2022-5-474 由于基可行解與基對應(duyng)，即尋找一個新的基可行解，相當于從上一個基B0變換為下一個新的基B1，因此，本步驟也稱為基變換。（基變換(binhun)）0NNMNbBzz可行：改善：基變換的原則）變換的方法：（PPPP,N進基出基進基；對應的令保證“改善”進基P0可決定出基。由保證“可行”出基011NBNXBbBX 稱作檢驗比。第74頁/共190頁第七十四頁，共190頁。2022-5-475第75頁/共190頁第七十五頁，共190頁。2022-5-476 以下面(xi mian)模型為例，可按上述單純形

47、法的步驟求出其最優(yōu)解，其大致的過程如下。（1）先將模型(mxng)化為標準型0,3001032005436049.54321521421321xxxxxxxxxxxxxxts 21127xxMaxz(2) 確定初始(ch sh)基可行解、檢驗;00,300)(0,0,360,2,00)(360,200,3,0100TTXbBB111;,52PP向量為再計算檢驗比確定出基量為計算檢驗數(shù)確定進基向第76頁/共190頁第七十六頁，共190頁。2022-5-477（3）換基、計算下一個(y )基可行解、再檢驗，直至最優(yōu);50,0)(0,30,240,)(240,50,30,1051411111TTXb

48、BB;0,0)(20,24,84,(84,20,24),103544912122TTXbBB00;,41PP向量為再計算檢驗比確定出基量為計算檢驗數(shù)確定進基向前解為最優(yōu)。計算檢驗數(shù)均非正，當問題：當模型規(guī)模(gum)較大時，計算量很大。事實上，單純形法的實現(xiàn)(shxin)是在單純形表上完成的。第77頁/共190頁第七十七頁，共190頁。2022-5-478 單純形表是基于(jy)單純形法的步驟設計的計算格式，是單純形法的具體實現(xiàn)。110101100)()(000BmBbBmBCcbBuBBBm M回顧(hug)單純形法步驟bBN需計算ABN需計算,AbB1內(nèi)容是因此，單純形表的主體 12111

49、0AbBAbBAbB 即第78頁/共190頁第七十八頁，共190頁。2022-5-479單純形表的主要(zhyo)結(jié)構(gòu)： X CABNbBN問題(wnt)：第一張表的B-1=？單位(dnwi)陣I。檢驗數(shù)的公式是什么？BPBCcN在哪里？PBN列中的第jAB1 第79頁/共190頁第七十九頁，共190頁。2022-5-480maxZ=6x1+5x2 x1+3x290 2x1+x275 2x1+2x2 80 x1, x20maxZ=6x1+5x2 x1+3x2+x390 2x1+ x2 +x4 75 2x1+2x2 +x580 xi0第80頁/共190頁第八十頁，共190頁。2022-5-481

50、cj65000CBXBbx1x2x3x4x50 x390131000 x475210100 x58022001cj-zj65000第81頁/共190頁第八十一頁，共190頁。2022-5-482cj65000CBXBbx1x2x3x4x50 x390131000 x475210100 x58022001cj-zj65000第82頁/共190頁第八十二頁，共190頁。2022-5-483cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj65000所以(suy)把x4換出為非基變量，x1為換入變量即新的基

51、變量。第83頁/共190頁第八十三頁，共190頁。2022-5-484cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj650006x175/211/201/20第84頁/共190頁第八十四頁，共190頁。2022-5-485cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj650000 x3105/205/21-1/206x175/211/201/20第85頁/共190頁第八十五頁，共190頁。2022-5

52、-486cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj650000 x3105/205/21-1/206x175/211/201/200 x55010-11第86頁/共190頁第八十六頁，共190頁。2022-5-487cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj650000 x3105/205/21-1/206x175/211/201/200 x55010-11cj-zj020-30第87頁/共1

53、90頁第八十七頁，共190頁。2022-5-488cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj650000 x3105/205/21-1/20216x175/211/201/20750 x55010-115cj-zj020-30所以(suy)把x5換出為非基變量，x2為換入變量即新的基變量。第88頁/共190頁第八十八頁，共190頁。2022-5-489cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj

54、650000 x3105/205/21-1/20216x175/211/201/20750 x55010-115cj-zj020-305x25010-11第89頁/共190頁第八十九頁，共190頁。2022-5-490cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj650000 x3105/205/21-1/20216x175/211/201/20750 x55010-115cj-zj020-300 x3400012-5/25x25010-11第90頁/共190頁第九十頁，共190頁。2022-5-

55、491cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj650000 x3105/205/21-1/20216x175/211/201/20750 x55010-115cj-zj020-300 x3400012-5/26x1351001-1/25x25010-11第91頁/共190頁第九十一頁，共190頁。2022-5-492cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj650000 x3105/205/

56、21-1/20216x175/211/201/20750 x55010-115cj-zj020-300 x3400012-5/26x1351001-1/25x25010-11cj-zj000-1-2此時所有的檢驗(jinyn)數(shù)都小于等于0，所以該解為最優(yōu)解。最優(yōu)解為X（35，5，40，0，0）T，Z*235第92頁/共190頁第九十二頁，共190頁。2022-5-493練習(linx)：對于下面的線性規(guī)劃0,6222min2N2N2N2Nxxxxxxxxz（1）用圖解法求解；（2）將模型(mxng)化為標準型；（3）用單純形法步驟求出其最優(yōu)解，并指出求 解過程中每一個基可行解相當于可行域的

57、哪一個角點。第93頁/共190頁第九十三頁，共190頁。2022-5-494Step 0 獲得一個初始的單純形表，確定基變量和非基變量Step 1 檢查基變量在目標函數(shù)中的系數(shù)(xsh)是否等于0，在約束條件中的系數(shù)(xsh)是否是一個單位矩陣。Step 2 如果表中非基變量在目標函數(shù)中的系數(shù)(xsh)全為負數(shù)，則已得到最優(yōu)解。停止。否則選擇系數(shù)(xsh)為正數(shù)且絕對值最大的變量進基，轉(zhuǎn)step 3。Step 3 如果進基變量在約束條件中的系數(shù)(xsh)全為負數(shù)或0，則可行域開放，目標函數(shù)無界。停止。否則選取右邊常數(shù)和正的系數(shù)(xsh)的最小比值，對應的基變量離基，轉(zhuǎn)step 4。Step 4

58、 確定進基變量的列和離基變量的行交叉的元素為“主元”，對單純形表進行行變換，使主元變?yōu)?，主元所在列的其他元素變?yōu)?。將離基的基變量的位置用進基的非基變量代替。轉(zhuǎn)Step 2。單純形表的算法(sun f)描述第94頁/共190頁第九十四頁，共190頁。2022-5-4951.maxZ=3x1+9x2 x1+3x221 -x1+x24 x1, x20maxZ=3x1+9x2 x1+3x2+x321 -x1+ x2 +x4 4 xi0舉例(j l)cj3900CBXBbx1x2x3x40 x32113100 x44-1101cj-zj3900第95頁/共190頁第九十五頁，共190頁。2022-5

59、-496cj3900CBXBbx1x2x3x40 x321131070 x44-11014cj-zj3900所以(suy)把x4換出為非基變量，x2為換入變量即新的基變量。第96頁/共190頁第九十六頁，共190頁。2022-5-497cj3900CBXBbx1x2x3x40 x321131070 x44-11014cj-zj39009x24-11014第97頁/共190頁第九十七頁，共190頁。2022-5-498cj3900CBXBbx1x2x3x40 x321131070 x44-11014cj-zj39000 x39401-39x24-1101第98頁/共190頁第九十八頁，共190頁

60、。2022-5-499cj3900CBXBbx1x2x3x40 x321131070 x44-11014cj-zj39000 x39401-39x24-1101cj-zj1200-9第99頁/共190頁第九十九頁，共190頁。2022-5-4100cj3900CBXBbx1x2x3x40 x321131070 x44-11014cj-zj39000 x39401-39/49x24-1101-cj-zj1200-9所以(suy)把x3換出為非基變量，x1為換入變量即新的基變量。第100頁/共190頁第一百頁，共190頁。2022-5-4101cj3900CBXBbx1x2x3x40 x32113