《管理運(yùn)籌學(xué)》02-1線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念ppt課件

1、一、現(xiàn)實(shí)中的線性規(guī)劃問題及數(shù)學(xué)模型一、現(xiàn)實(shí)中的線性規(guī)劃問題及數(shù)學(xué)模型二、線性規(guī)劃的規(guī)范方式二、線性規(guī)劃的規(guī)范方式三、線性規(guī)劃的幾何解釋三、線性規(guī)劃的幾何解釋 四、線性規(guī)劃的基及根本可行解四、線性規(guī)劃的基及根本可行解第第1節(jié)節(jié) 線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念一一 現(xiàn)實(shí)中的線性規(guī)劃問題及模型現(xiàn)實(shí)中的線性規(guī)劃問題及模型例例2-1 2-1 消費(fèi)方案問題消費(fèi)方案問題某工廠擁有某工廠擁有A A、B B、C C三種類型的設(shè)備，消費(fèi)甲、乙、三種類型的設(shè)備，消費(fèi)甲、乙、丙、丁四種產(chǎn)品。每件產(chǎn)品在消費(fèi)中需求占用的設(shè)備丙、丁四種產(chǎn)品。每件產(chǎn)品在消費(fèi)中需求占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的

2、利潤(rùn)以及三種設(shè)備可利機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三種設(shè)備可利用的時(shí)數(shù)如表用的時(shí)數(shù)如表2-12-1所示，試用線性規(guī)劃制定使總利潤(rùn)所示，試用線性規(guī)劃制定使總利潤(rùn)最大的消費(fèi)方案。最大的消費(fèi)方案。第1節(jié) 線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念產(chǎn)品甲產(chǎn)品甲 產(chǎn)品乙產(chǎn)品乙 產(chǎn)品丙產(chǎn)品丙 產(chǎn)品丁產(chǎn)品丁1.51.01.52000 8000 5000設(shè)備設(shè)備A 設(shè)備設(shè)備B 設(shè)備設(shè)備C單位產(chǎn)品耗單位產(chǎn)品耗費(fèi)的機(jī)時(shí)數(shù)費(fèi)的機(jī)時(shí)數(shù)產(chǎn)品產(chǎn)品設(shè)備才干設(shè)備才干小時(shí)小時(shí)利潤(rùn)利潤(rùn)元元/ /件件 5.24 7.30 8.34 4.181.05.03.02.41.03.51.03.51.0一一 現(xiàn)實(shí)中的線性規(guī)劃問題及模型現(xiàn)實(shí)中的線性規(guī)劃

3、問題及模型 x1 x2 x3 x4 決策變量決策變量0目的函數(shù)目的函數(shù)1.5x1 + 1.0 x2 + 2.4x3 + 1.0 x4 2000 函數(shù)約束函數(shù)約束非負(fù)性約束非負(fù)性約束1.0 x1 + 5.0 x2 + 1.0 x3 + 3.5x4 8000 1.5x1 + 3.0 x2 + 3.5x3 + 1.0 x4 8000 x1 ， x2 ， x3 ， x4 0 產(chǎn)品甲產(chǎn)品甲 產(chǎn)品乙產(chǎn)品乙 產(chǎn)品丙產(chǎn)品丙 產(chǎn)品丁產(chǎn)品丁1.51.01.52000 8000 5000設(shè)備設(shè)備A 設(shè)備設(shè)備B 設(shè)備設(shè)備C單位產(chǎn)品耗單位產(chǎn)品耗費(fèi)的機(jī)時(shí)數(shù)費(fèi)的機(jī)時(shí)數(shù)產(chǎn)品產(chǎn)品設(shè)備才干設(shè)備才干小時(shí)小時(shí)利潤(rùn)利潤(rùn)元元/ /件件

4、5.24 7.30 8.34 4.181.05.03.02.41.03.51.03.51.0一一 現(xiàn)實(shí)中的線性規(guī)劃問題及模型現(xiàn)實(shí)中的線性規(guī)劃問題及模型求解這個(gè)線性規(guī)劃，可以得到最優(yōu)解為：求解這個(gè)線性規(guī)劃，可以得到最優(yōu)解為：x1=294.12x1=294.12件件 x2=1500 x2=1500 件件 x3=0 x3=0件件 x4=58.82 x4=58.82 件件 最大利潤(rùn)為最大利潤(rùn)為z=12737.06z=12737.06元元 請(qǐng)留意最優(yōu)解中利潤(rùn)率最高的產(chǎn)品丙在最優(yōu)消費(fèi)請(qǐng)留意最優(yōu)解中利潤(rùn)率最高的產(chǎn)品丙在最優(yōu)消費(fèi)方案中不安排消費(fèi)。闡明按產(chǎn)品利潤(rùn)率大小為優(yōu)先次方案中不安排消費(fèi)。闡明按產(chǎn)品利潤(rùn)率大

5、小為優(yōu)先次序來安排消費(fèi)方案的方法有很大局限性。尤其當(dāng)產(chǎn)品序來安排消費(fèi)方案的方法有很大局限性。尤其當(dāng)產(chǎn)品種類很多，設(shè)備類型很多的情況下，用手工方法安排種類很多，設(shè)備類型很多的情況下，用手工方法安排消費(fèi)方案很難獲得稱心的結(jié)果。消費(fèi)方案很難獲得稱心的結(jié)果。一一 現(xiàn)實(shí)中的線性規(guī)劃問題及模型現(xiàn)實(shí)中的線性規(guī)劃問題及模型例例2-2 2-2 配料問題配料問題某工廠要用四種合金某工廠要用四種合金T1T1，T2T2，T3T3和和T4T4為原料，經(jīng)熔煉為原料，經(jīng)熔煉成為一種新的不銹鋼成為一種新的不銹鋼G G。這四種原料含元素鉻。這四種原料含元素鉻CrCr，錳錳MnMn和鎳和鎳NiNi的含量的含量% %，這四種原料的

6、單，這四種原料的單價(jià)以及新的不銹鋼資料價(jià)以及新的不銹鋼資料G G所要求的所要求的CrCr，MnMn和和NiNi的最低的最低含量含量% %如下表所示：如下表所示：設(shè)熔煉時(shí)分量沒有損耗，要熔煉成設(shè)熔煉時(shí)分量沒有損耗，要熔煉成100100公斤不銹鋼公斤不銹鋼G G，應(yīng)選用原料應(yīng)選用原料T1T1，T2T2，T3T3和和T4T4各多少公斤，使本錢最小。各多少公斤，使本錢最小。第1節(jié) 線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念T1 T2 T3 T1 T2 T3 T4T43.212.045.823.20 2.10 4.30CrMnNiG G單價(jià)元單價(jià)元/ /公斤公斤 115 97 82 764.531.123.06 2.

7、193.574.271.764.332.73 x1 x2 x3 x4 0.0321x1 + 0.0453x2 + 0.0219x3 + 0.0176x4 3.20 x1 ， x2 ， x3 ， x4 00.0204x1 + 0.0112x2 + 0.0357x3 + 0.0433x4 2.100.0582x1 + 0.0306x2 + 0.0427x3 + 0.0273x4 4.30 x1 + x2 + x3 + x4 = 100求解這個(gè)線性規(guī)劃，可以得到最優(yōu)解為：求解這個(gè)線性規(guī)劃，可以得到最優(yōu)解為：x1=26.58 x2=31.57 x3=41.84 x4=0 x1=26.58 x2=31.

8、57 x3=41.84 x4=0 最大利潤(rùn)為最大利潤(rùn)為z=9549.87z=9549.87元元一一 現(xiàn)實(shí)中的線性規(guī)劃問題及模型現(xiàn)實(shí)中的線性規(guī)劃問題及模型一一 現(xiàn)實(shí)中的線性規(guī)劃問題及模型現(xiàn)實(shí)中的線性規(guī)劃問題及模型例例2-3 2-3 背包問題背包問題一只背包最大裝載分量為一只背包最大裝載分量為5050公斤?，F(xiàn)有三種物品，每公斤?，F(xiàn)有三種物品，每種物品數(shù)量無限。每種物品每件的分量、價(jià)值如下表種物品數(shù)量無限。每種物品每件的分量、價(jià)值如下表所示：所示： 要在背包中裝入這三種物品各多少件，使背包中的要在背包中裝入這三種物品各多少件，使背包中的物品價(jià)值最高。物品價(jià)值最高。第1節(jié) 線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念

9、物品物品1 1 物品物品2 2 物品物品3 3 1017分量公斤分量公斤/件件價(jià)值元價(jià)值元 / 件件4172 2035 x1 x2 x310 x1 + 41x2 + 20 x3 50 x1 ， x2 ， x3 0 且為整數(shù)且為整數(shù)求解這個(gè)線性規(guī)劃，可以得到最優(yōu)解為：求解這個(gè)線性規(guī)劃，可以得到最優(yōu)解為：x1=1 x2=0 x3=2 x1=1 x2=0 x3=2 最高價(jià)值為最高價(jià)值為 z= 87 z= 87元元一一 現(xiàn)實(shí)中的線性規(guī)劃問題及模型現(xiàn)實(shí)中的線性規(guī)劃問題及模型一一 現(xiàn)實(shí)中的線性規(guī)劃問題及模型現(xiàn)實(shí)中的線性規(guī)劃問題及模型例例2-4 2-4 最小費(fèi)用流問題最小費(fèi)用流問題 某公司下設(shè)兩個(gè)分工廠，兩

10、個(gè)倉(cāng)庫(kù)及一個(gè)配某公司下設(shè)兩個(gè)分工廠，兩個(gè)倉(cāng)庫(kù)及一個(gè)配送中心。其中送中心。其中F1F1和和F2F2是兩個(gè)工廠，是兩個(gè)工廠，W1W1和和W2W2是兩個(gè)倉(cāng)庫(kù)。是兩個(gè)倉(cāng)庫(kù)。D D是一個(gè)分銷中心。由工廠消費(fèi)的產(chǎn)品經(jīng)由圖所示的是一個(gè)分銷中心。由工廠消費(fèi)的產(chǎn)品經(jīng)由圖所示的運(yùn)輸網(wǎng)絡(luò)運(yùn)往倉(cāng)庫(kù)。每一條道路運(yùn)輸?shù)膯挝槐惧X在線運(yùn)輸網(wǎng)絡(luò)運(yùn)往倉(cāng)庫(kù)。每一條道路運(yùn)輸?shù)膯挝槐惧X在線段上給出，其中，段上給出，其中，F(xiàn)1F2F1F2與與DW2DW2道路由于遭到道路道路由于遭到道路中的橋梁承重上限的要求，因此有最大運(yùn)輸量限制。中的橋梁承重上限的要求，因此有最大運(yùn)輸量限制。其他道路有足夠的運(yùn)輸才干來運(yùn)輸兩個(gè)工廠消費(fèi)的貨其他道路有足夠的

11、運(yùn)輸才干來運(yùn)輸兩個(gè)工廠消費(fèi)的貨物。需求制定的決策是關(guān)于每一條道路應(yīng)該運(yùn)輸多少，物。需求制定的決策是關(guān)于每一條道路應(yīng)該運(yùn)輸多少，目的是總體的運(yùn)輸本錢最小化。目的是總體的運(yùn)輸本錢最小化。第1節(jié) 線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念一一 現(xiàn)實(shí)中的線性規(guī)劃問題及模型現(xiàn)實(shí)中的線性規(guī)劃問題及模型例例2-4 2-4 最小費(fèi)用流問題最小費(fèi)用流問題 第1節(jié) 線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念900元元/單位單位x6100元元/單位單位x7最多最多80單位單位x4x5x2x3x1300元元/單位單位300元元/單位單位F1需求需求30單單位位W1消費(fèi)消費(fèi)40單單位位F2需求需求60單單位位W2200元元/單位單位D最多最多10

12、單位單位200元元/單位單位400元元/單位單位圖圖2-1公司的配送網(wǎng)絡(luò)公司的配送網(wǎng)絡(luò)消費(fèi)消費(fèi)50單位單位x1 + x2 + x3 =50 x1 ， ， x7 0- x1 +x4 =40 -x2 - x4 +x5 = 0 -x3 + x6 x7 = -30求解這個(gè)線性規(guī)劃，可以得到最優(yōu)解為：求解這個(gè)線性規(guī)劃，可以得到最優(yōu)解為：x1 x1 ， x2 x2 ， x3 x3 ， x4 x4 ， x5 x5 ， x6 x6 ， x7 x7 = = 0 0，4040，1010，4040，8080，0 0，2020z=49000z=49000元元一一 現(xiàn)實(shí)中的線性規(guī)劃問題及模型現(xiàn)實(shí)中的線性規(guī)劃問題及模型

13、-x5 - x6 + x7 = -60 x1 10， x5 80線性規(guī)劃的普通方式線性規(guī)劃的普通方式 普通普通LP模型的三類參數(shù)：模型的三類參數(shù)：價(jià)值系數(shù)價(jià)值系數(shù)c j，耗費(fèi)系數(shù)，耗費(fèi)系數(shù)a ij，右端常數(shù)，右端常數(shù)b i . LP模型的三要素：決策變量，目的函數(shù)，約束條件模型的三要素：決策變量，目的函數(shù)，約束條件.s.t.max(min) z = c1 x1+c2 x2+c3 x3+cn xn a11x1 +a12 x2+a1n xn (= ) b1 a21x1 +a22 x2+a2n xn (= ) b2 am1x1+am2x2+amn xn (= ) bm xj(或或) 0, 或自在或自

14、在, j=1,2,n 一一 現(xiàn)實(shí)中的線性規(guī)劃問題及模型現(xiàn)實(shí)中的線性規(guī)劃問題及模型線性規(guī)劃的向量和矩陣的表達(dá)方式線性規(guī)劃的向量和矩陣的表達(dá)方式記向量和矩陣記向量和矩陣一一 現(xiàn)實(shí)中的線性規(guī)劃問題及模型現(xiàn)實(shí)中的線性規(guī)劃問題及模型mnmmnnmnTnaaaaaaaaaAbbbbxxxXcccC212222111211212121,那么線性規(guī)劃問題可以表示為：那么線性規(guī)劃問題可以表示為：maxmin) z =CX s.t.AX (= ) b X 0二、線性規(guī)劃的規(guī)范方式二、線性規(guī)劃的規(guī)范方式稱以下線性規(guī)劃的方式為規(guī)范方式稱以下線性規(guī)劃的方式為規(guī)范方式max z=c1x1+c2x2+c3x3+cnxns.

15、t.a11x1 +a12x2+ +a1nxn = b1 (0)a21x1 +a22x2+ +a2nxn = b2 (0) am1x1+am2x2+amnxn = bm (0) x1 , x2 , , xn 0簡(jiǎn)記為：簡(jiǎn)記為：max z =CX s.t.AX = b X 0(M1): (M2): 非規(guī)范形非規(guī)范形LP問題的規(guī)范化問題的規(guī)范化 一、極小化目的函數(shù)的問題一、極小化目的函數(shù)的問題 min z = CX 令令 z= z max z= CX 例：例：min z = 3x1 2x2 max z= 3x1 2x2 二、約束條件不是等式的問題二、約束條件不是等式的問題 bi0 兩邊同時(shí)乘以兩邊同

16、時(shí)乘以 -1 約束為約束為方式方式 加上松弛變量加上松弛變量 約束為約束為方式方式 減去剩余變量減去剩余變量 三、變量符號(hào)無限制或小于等于零的問題三、變量符號(hào)無限制或小于等于零的問題 假設(shè)假設(shè)xk為自在變量為自在變量, 令令 xk = xk xk且且 xk,xk 0 假設(shè)假設(shè)xk 0, 令令 xk = xk,那么那么 xk 0 二、線性規(guī)劃的規(guī)范方式二、線性規(guī)劃的規(guī)范方式xzzzminz = - zz maxx*min z = 2x1 3 x2 x3 x1 x2 2 x3 3 2x1 3 x2 x3 5 x1 x2 x3 = 4 x1 0, x2 無約束，無約束， x3 0s.t.解：令解：令

17、z= -z ， x2= x2 x2 ，x3= -x3 s.t.二、線性規(guī)劃的規(guī)范方式二、線性規(guī)劃的規(guī)范方式min z = x1 2 x2 3 x3 x1 2 x2 x3 5 2x1 3 x2 x3 6 x1 x2 x3 2 x1 0, x3 0s.t.解:max z= x1 2x2 3x3s.t. x1 2x2 x3 + x4 = 5 2x1 3x2 x3 - x5 = 6 x1 x2 x3 +x6 = 2 x1 , x4 , x5 , x6 0 , x3 0練習(xí)：將下述練習(xí)：將下述LP問題化成規(guī)范形問題化成規(guī)范形二、線性規(guī)劃的規(guī)范方式二、線性規(guī)劃的規(guī)范方式令令x2 = x2 x2 ，且，且

18、x2，x2 0 x3 = -x3代入上式中，得代入上式中，得s.t.二、線性規(guī)劃的規(guī)范方式二、線性規(guī)劃的規(guī)范方式只需兩個(gè)變量的線性規(guī)劃問題只需兩個(gè)變量的線性規(guī)劃問題 X*= (4, 6)Tz* = 42 1畫出可行域圖形畫出可行域圖形 2畫出目的函數(shù)的畫出目的函數(shù)的 等值線及其法線等值線及其法線 3確定最優(yōu)點(diǎn)確定最優(yōu)點(diǎn)例例 max z = 3x1+5x2 x1 8 2 x2 12 3x1+ 4 x2 36 x1, x2 0s.t.x1x2O(0,0)x1= 8A(8,0)2x2= 12D(0,6)3x1 + 4x2 = 36O(0,0)x1x2D(0,6)C(4,6)B(8,3)A(8,0)z

19、 = 15z = 30z 法向法向z* = 42三、線性規(guī)劃的幾何解釋三、線性規(guī)劃的幾何解釋幾點(diǎn)闡明幾點(diǎn)闡明實(shí)踐運(yùn)用時(shí)還須留意以下幾點(diǎn)實(shí)踐運(yùn)用時(shí)還須留意以下幾點(diǎn): :(1)(1)假設(shè)函數(shù)約束原型就是等式假設(shè)函數(shù)約束原型就是等式, ,那么其代表的區(qū)域僅那么其代表的區(qū)域僅為不斷線為不斷線, ,而且問而且問 題的整個(gè)可行域題的整個(gè)可行域R(R(假設(shè)存在的話假設(shè)存在的話) )也必然在此直線也必然在此直線上。上。(2)(2)在畫目的函數(shù)等值線時(shí)只須畫兩條就能確定其法在畫目的函數(shù)等值線時(shí)只須畫兩條就能確定其法線方向線方向, ,為此為此, , 只須賦給只須賦給z z 兩個(gè)適當(dāng)?shù)闹?。兩個(gè)適當(dāng)?shù)闹怠?3)(3)

20、在找出最優(yōu)點(diǎn)后在找出最優(yōu)點(diǎn)后, ,關(guān)于其坐標(biāo)值有兩種確定方法關(guān)于其坐標(biāo)值有兩種確定方法: : 在圖上觀測(cè)最優(yōu)點(diǎn)坐標(biāo)值在圖上觀測(cè)最優(yōu)點(diǎn)坐標(biāo)值 經(jīng)過解方程組得出最優(yōu)點(diǎn)坐標(biāo)值經(jīng)過解方程組得出最優(yōu)點(diǎn)坐標(biāo)值三、線性規(guī)劃的幾何解釋三、線性規(guī)劃的幾何解釋幾種能夠結(jié)果幾種能夠結(jié)果一、獨(dú)一解一、獨(dú)一解 如例如例1、例、例2都只需都只需一個(gè)一個(gè)最優(yōu)點(diǎn)，屬于獨(dú)一解的最優(yōu)點(diǎn)，屬于獨(dú)一解的情形。情形。s.t.max z = 3x1+4x2 x1 8 2x2 12 3x1 + 4x2 36 x1 ， x2 0 二、多重解二、多重解z = 12z* = 36線段線段BCBC上無窮多個(gè)上無窮多個(gè)點(diǎn)均為最優(yōu)解。點(diǎn)均為最優(yōu)解。O

21、(0,0)x1x2 D(0,6)C(4,6)B(8,3)A(8,0)三、線性規(guī)劃的幾何解釋三、線性規(guī)劃的幾何解釋x1x2z*三、無界解三、無界解3694812x1x2四、無可行解四、無可行解+三、線性規(guī)劃的幾何解釋三、線性規(guī)劃的幾何解釋相關(guān)定義相關(guān)定義定義定義2-1 可行域可行域在在n維空間中，滿足條件維空間中，滿足條件ai1x1+ai2x2+ain xn (= ) bi且且xj 0 的點(diǎn)集。的點(diǎn)集。O(0,0)x1x2 D(0,6)C(4,6)B(8,3)A(8,0)三、線性規(guī)劃的幾何解釋三、線性規(guī)劃的幾何解釋定義定義2-2 凸集凸集三、線性規(guī)劃的幾何解釋三、線性規(guī)劃的幾何解釋設(shè)設(shè)S是是n維

22、空間中的一個(gè)點(diǎn)集。假設(shè)對(duì)恣意維空間中的一個(gè)點(diǎn)集。假設(shè)對(duì)恣意n維向量維向量X1S，X2S，且，且X1X2，以及恣意實(shí)數(shù)，以及恣意實(shí)數(shù) 01，有，有X= X1+(1- )X2S那么稱那么稱S為為n維空間中的一個(gè)凸集維空間中的一個(gè)凸集Convex Set。點(diǎn)。點(diǎn)X稱稱為點(diǎn)為點(diǎn)X1和和X2的凸組合。的凸組合。凸集：凸集：非凸集：非凸集：定義定義2-3 凸集的極點(diǎn)凸集的極點(diǎn)三、線性規(guī)劃的幾何解釋三、線性規(guī)劃的幾何解釋設(shè)設(shè)S為一凸集，且為一凸集，且XS，假設(shè)，假設(shè)X不能用不同的兩點(diǎn)不能用不同的兩點(diǎn)X1S，X2S的線性組合表示為的線性組合表示為X= X1+(1- )X2 01那么稱那么稱X為為S的一個(gè)極點(diǎn)。

23、的一個(gè)極點(diǎn)。運(yùn)用以上的定義，線性規(guī)劃的可行域以及最優(yōu)解有以下性質(zhì)：運(yùn)用以上的定義，線性規(guī)劃的可行域以及最優(yōu)解有以下性質(zhì)：1假設(shè)線性規(guī)劃的可行域非空，那么可行域必定為一凸假設(shè)線性規(guī)劃的可行域非空，那么可行域必定為一凸集。集。2假設(shè)線性規(guī)劃有最優(yōu)解，那么最優(yōu)解一定可以在凸集的假設(shè)線性規(guī)劃有最優(yōu)解，那么最優(yōu)解一定可以在凸集的極點(diǎn)中找到。極點(diǎn)中找到。 這樣，求線性規(guī)劃最優(yōu)解的問題，從在可行域內(nèi)無限個(gè)可這樣，求線性規(guī)劃最優(yōu)解的問題，從在可行域內(nèi)無限個(gè)可行解中搜索的問題轉(zhuǎn)化為在其可行域的有限個(gè)極點(diǎn)上搜索的問行解中搜索的問題轉(zhuǎn)化為在其可行域的有限個(gè)極點(diǎn)上搜索的問題。題?；涸O(shè)基：設(shè)A為線性規(guī)劃模型約束條件系

24、數(shù)矩陣為線性規(guī)劃模型約束條件系數(shù)矩陣m n，mn，而，而B為其為其mm子矩陣，假設(shè)子矩陣，假設(shè)|B|0，那么稱，那么稱B為該線性規(guī)劃模型的一個(gè)基。為該線性規(guī)劃模型的一個(gè)基?；兞浚夯忻總€(gè)向量所對(duì)應(yīng)的變量稱為基變量?；兞浚夯忻總€(gè)向量所對(duì)應(yīng)的變量稱為基變量。非基變量：模型中基變量之外的變量稱為非基變量。非基變量：模型中基變量之外的變量稱為非基變量。根本解基解：令模型中一切非基變量根本解基解：令模型中一切非基變量X非基非基=0后，由模后，由模型約束方程組型約束方程組 n aijxj =bi (i=1,2,m)得到的一組解。得到的一組解。 j=1根本可行解基可行解：在根本解中，同時(shí)又是可行解的解

25、稱為根本根本可行解基可行解：在根本解中，同時(shí)又是可行解的解稱為根本可行解。可行解。可行基：對(duì)應(yīng)于根本可行解的基稱為可行基。可行基：對(duì)應(yīng)于根本可行解的基稱為可行基。四、線性規(guī)劃的基、根本可行解四、線性規(guī)劃的基、根本可行解Max z=2x1+3x2 st. x1+x2 3 x1+2x2 4 x1,x2 0 Max z=2x1+3x2 +0 x3 +0 x4 st. x1+x2+x3=3 x1+2x2+x4=4 x1, x2, x3 , x4 0A=x1 x2 x3 x41 1 1 01 2 0 1可行解：可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T 等。等。設(shè)B= 1 0 0 1，令，那么| B |=10,令 x1=x2 =0，那么 x3 =3, x4=4，X=(0,0,3,4)T例：例：x3 x4基變量基變量令 B=1 1 1 0 x1 x3 ，那么令 x2=x4 =0，那么 x3 =-1, x1=4，