Chapter21線性規(guī)劃問題的數(shù)學(xué)模型及相關(guān)概念

1、“211211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)線性規(guī)劃線性規(guī)劃Chapter Two：LP“211211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)第一節(jié) 線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念 現(xiàn)實中的線性規(guī)劃問題及

2、數(shù)學(xué)模型 線性規(guī)劃的標(biāo)準(zhǔn)形式 線性規(guī)劃的幾何解釋 線性規(guī)劃的基及基本可行解“211211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)一 現(xiàn)實中的線性規(guī)劃問題及模型 例例2-12-1 生產(chǎn)計劃問題生產(chǎn)計劃問題某工廠擁有某工廠擁有A A、B B、C C三種類型的設(shè)備，生產(chǎn)甲、乙、丙、丁四三種類型的設(shè)備，生產(chǎn)甲、乙、丙、丁四種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時數(shù)，每件產(chǎn)品種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)

3、備機(jī)時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時數(shù)如表可以獲得的利潤以及三種設(shè)備可利用的時數(shù)如表2-12-1所示所示，試，試用線性規(guī)劃制訂使總利潤最大的生產(chǎn)計劃。用線性規(guī)劃制訂使總利潤最大的生產(chǎ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)品消耗的機(jī)時數(shù)耗的機(jī)時數(shù)產(chǎn)品產(chǎn)品設(shè)備能力設(shè)備能力（小時）（小時）利潤利潤（元（元/ /件）件） 5.24 7.30 8.34 4.181.05.03.02.41.03.51.03.51.0“211211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分

4、校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)一 現(xiàn)實中的線性規(guī)劃問題及模型產(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)品消耗的機(jī)時數(shù)耗的機(jī)時數(shù)產(chǎn)品產(chǎn)品設(shè)備能力設(shè)備能力（小時）（小時）利潤利潤（元（元/ /件）件） 5.24 7.30 8.34 4.181.05.03.02.41.03.51.03.51.0決策變量決策變量目標(biāo)函數(shù)目標(biāo)函數(shù)函數(shù)約束

5、函數(shù)約束非負(fù)性約束非負(fù)性約束 x1 x2 x3 x4 = 5.24x1 +7.30 x2 +8.34x3 +4.18x401.5x1 + 1.0 x2 + 2.4x3 + 1.0 x4 2000 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 “211211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)

6、則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)一 現(xiàn)實中的線性規(guī)劃問題及模型5求解這個線性規(guī)劃，可以得到最優(yōu)解為：求解這個線性規(guī)劃，可以得到最優(yōu)解為：x1=294.12（件）（件） x2=1500 （件）（件） x3=0 （件）（件） x4=58.82 （件）（件） 最大利潤為最大利潤為z=12737.06（元）（元） 請注意最優(yōu)解中利潤率最高的產(chǎn)品丙在最優(yōu)生產(chǎn)請注意最優(yōu)解中利潤率最高的產(chǎn)品丙在最優(yōu)生產(chǎn)計劃中不安排生產(chǎn)。說明按產(chǎn)品利潤率大小為優(yōu)先次計劃中不安排生產(chǎn)。說明按產(chǎn)品利潤率大小為優(yōu)先次序來安排生產(chǎn)計劃的方法有很大局限性。尤其當(dāng)產(chǎn)品序來安排生產(chǎn)計劃的方法有很大局限性。尤其當(dāng)產(chǎn)品品種很多，設(shè)備類型很多

7、的情況下，用手工方法安排品種很多，設(shè)備類型很多的情況下，用手工方法安排生產(chǎn)計劃很難獲得滿意的結(jié)果。生產(chǎn)計劃很難獲得滿意的結(jié)果?！?11211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)一 現(xiàn)實中的線性規(guī)劃問題及模型6例例2-22-2 配料問題配料問題某工廠要用四種合金某工廠要用四種合金T1，T2，T3和和T4為原料，經(jīng)熔煉成為一種為原料，經(jīng)熔煉成為一種新的不銹鋼新的不銹鋼G。這四種原料含元素鉻（。這四種原料

8、含元素鉻（Cr），錳（），錳（Mn）和鎳）和鎳（Ni）的含量（）的含量（%），這四種原料的單價以及新的不銹鋼材料），這四種原料的單價以及新的不銹鋼材料G所要求的所要求的Cr，Mn和和Ni的最低含量（的最低含量（%）如下表所示：）如下表所示：設(shè)熔煉時重量沒有損耗，要熔煉成設(shè)熔煉時重量沒有損耗，要熔煉成100公斤不銹鋼公斤不銹鋼G，應(yīng)選用，應(yīng)選用原料原料T1，T2，T3和和T4各多少公斤，使成本最小。各多少公斤，使成本最小。T T1 1 T T2 2 T T3 3 T T4 43.212.045.823.20 2.10 4.30CrMnNiG G單價（元單價（元/ /公斤）公斤） 115 97 8

9、2 764.531.123.06 2.193.574.271.764.332.73 x1 x2 x3 x4 “211211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)一 現(xiàn)實中的線性規(guī)劃問題及模型 = 115x1 +97x2 +82x3 +76x40.0321x1 + 0.0453x2 + 0.0219x3 + 0.0176x4 3.20 x1 ， x2 ， x3 ， x4 00.0204x1 + 0.01

10、12x2 + 0.0357x3 + 0.0433x4 2.100.0582x1 + 0.0306x2 + 0.0427x3 + 0.0273x4 4.30 x1 + x2 + x3 + x4 = 100求解這個線性規(guī)劃，可以得到最優(yōu)解為：求解這個線性規(guī)劃，可以得到最優(yōu)解為：x1=26.58 x2=31.57 x3=41.84 x4=0 最大利潤為最大利潤為z=9549.87（元）（元）“211211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證

11、規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)一 現(xiàn)實中的線性規(guī)劃問題及模型8例例2-32-3 背包問題背包問題一只背包最大裝載重量為一只背包最大裝載重量為50公斤?，F(xiàn)有三種物品，每種物品數(shù)公斤。現(xiàn)有三種物品，每種物品數(shù)量無限。每種物品每件的重量、價值如下表所示：量無限。每種物品每件的重量、價值如下表所示： 要在背包中裝入這三種物品各多少件，使背包中的物品價值最要在背包中裝入這三種物品各多少件，使背包中的物品價值最高高。物品物品1 1 物品物品2 2 物品物品3 3 1017重量（公斤重量（公斤/件）件）價值（元價值（元 / 件）件）4172 2035 x1 x2 x3“211211工程工程”重點建設(shè)大

12、學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)一 現(xiàn)實中的線性規(guī)劃問題及模型9 = 17x1 +72x2 +35x310 x1 + 41x2 + 20 x3 50 x1 ， x2 ， x3 0 且為整數(shù)且為整數(shù)求解這個線性規(guī)劃，可以得到最優(yōu)解為：求解這個線性規(guī)劃，可以得到最優(yōu)解為：x1=1 x2=0 x3=2 最最高價值高價值為為 z= 87（元）（元）“211211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界

13、海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)一 現(xiàn)實中的線性規(guī)劃問題及模型10例例2-4 2-4 最小費用流問題最小費用流問題 某公司下設(shè)兩個分工廠，兩個倉庫及一個配送中心。其中某公司下設(shè)兩個分工廠，兩個倉庫及一個配送中心。其中F1和和F2是兩個工廠，是兩個工廠，W1和和W2是兩個倉庫。是兩個倉庫。D是一個分銷中心。是一個分銷中心。由工廠生產(chǎn)的產(chǎn)品經(jīng)由圖所示的運輸網(wǎng)絡(luò)運往倉庫。每一條路由工廠生產(chǎn)的產(chǎn)品經(jīng)由圖所示的運輸網(wǎng)絡(luò)運往倉庫。每一條路線運輸?shù)膯挝怀杀驹诰€段上給出，

14、其中，線運輸?shù)膯挝怀杀驹诰€段上給出，其中，F(xiàn)1F2與與DW2路線路線由于受到路線中的橋梁承重上限的要求，因此有最大運輸量限由于受到路線中的橋梁承重上限的要求，因此有最大運輸量限制。其他路線有足夠的運輸能力來運輸兩個工廠生產(chǎn)的貨物。制。其他路線有足夠的運輸能力來運輸兩個工廠生產(chǎn)的貨物。需要制訂的決策是關(guān)于每一條路線應(yīng)該運輸多少，目標(biāo)是總體需要制訂的決策是關(guān)于每一條路線應(yīng)該運輸多少，目標(biāo)是總體的運輸成本最小化。的運輸成本最小化。“211211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)

15、量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)一 現(xiàn)實中的線性規(guī)劃問題及模型11例例2-4 2-4 最小費用流問題最小費用流問題 900元元/單位單位x6100元元/單位單位x7最多最多80單位單位x4x5x2x3x1300元元/單位單位300元元/單位單位F1需求需求30單單位位W1生產(chǎn)生產(chǎn)40單位單位F2需求需求60單位單位W2200元元/單位單位D最多最多10單位單位200元元/單位單位400元元/單位單位圖圖2-1公司的配送網(wǎng)絡(luò)公司的配送網(wǎng)絡(luò)生產(chǎn)生產(chǎn)50單位單位“211211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)

16、第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)一 現(xiàn)實中的線性規(guī)劃問題及模型12 = 200 x1 +400 x2 +900 x3 +300 x4 +100 x5 +3x6 +200 x7x1 + x2 + x3 =50 x1 ， ， x7 0- x1 +x4 =40 -x2 - x4 +x5 = 0 -x3 + x6 x7 = -30求解這個線性規(guī)劃，可以得到最優(yōu)解為：求解這個線性規(guī)劃，可以得到最優(yōu)解為：（x1 ， x2 ， x3 ， x4 ， x5 ， x6 ， x7 ）= （0，40

17、，10，40，80，0，20）z=49000（元）（元） -x5 - x6 + x7 = -60 x1 10， x5 80“211211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)一 現(xiàn)實中的線性規(guī)劃問題及模型 可用一些變量表示這類問題的待定方案，這些變量的一組定值就代表一個具體方案 這些變量稱為決策變量，并往往要求它們非負(fù) 有一個期望達(dá)到的目標(biāo)，這個目標(biāo)能以某種確定的數(shù)量指標(biāo)刻畫出來，而這種指標(biāo)可表示為關(guān)

18、于決策變量的線性函數(shù)，按所考慮的問題不同，要求該函數(shù)值最大化或最小化 存在一定的約束條件，這些約束條件都能用關(guān)于決策變量的線性不等式或等式來表示“211211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)一 現(xiàn)實中的線性規(guī)劃問題及模型 線性規(guī)劃模型的三要素： 決策變量：指模型中要求解的未知量，簡稱變量。 目標(biāo)函數(shù)：指模型中要達(dá)到的目標(biāo)的數(shù)學(xué)表達(dá)式。 約束條件：指模型中的變量取值所需要滿足的一切限制條件?！?1

19、1211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)一 現(xiàn)實中的線性規(guī)劃問題及模型線性規(guī)劃的一般形式線性規(guī)劃的一般形式 一般一般LP模型的模型的：，. 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(

20、或或) 0, , 或自由或自由, , j=1, ,2, , ,n “211211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)一 現(xiàn)實中的線性規(guī)劃問題及模型16線性規(guī)劃的向量和矩陣的表達(dá)形式線性規(guī)劃的向量和矩陣的表達(dá)形式記向量和矩陣記向量和矩陣mnmmnnmnTnaaaaaaaaaAbbbbxxxXcccC212222111211212121,則線性規(guī)劃問題可以表示為：則線性規(guī)劃問題可以表示為：max（min

21、) z =CX s.t.AX (= ) b X 0“211211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)二、線性規(guī)劃的標(biāo)準(zhǔn)形式稱以下線性規(guī)劃的形式為標(biāo)準(zhǔn)形式稱以下線性規(guī)劃的形式為標(biāo)準(zhǔn)形式max z=c1x1+c2x2+c3x3+cnxns.t.a11x1 +a12x2+ +a1nxn = b1 (0)a21x1 +a22x2+ +a2nxn = b2 (0) am1x1+am2x2+amnxn = bm

22、 (0) x1 , , x2 , , , , xn 0簡記為：簡記為：max z =CX s.t.AX = b X 0(M1): (M2): “211211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)二、線性規(guī)劃的標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式非標(biāo)準(zhǔn)形式非標(biāo)準(zhǔn)形式目標(biāo)函數(shù)maxmins.t.Xj0;bj0Xj0,X無約束;bj0約束方程為等式約束方程為不等式“211211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分

23、校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)二、線性規(guī)劃的標(biāo)準(zhǔn)形式非標(biāo)準(zhǔn)形非標(biāo)準(zhǔn)形LP問題的標(biāo)準(zhǔn)化問題的標(biāo)準(zhǔn)化 一、極小化目標(biāo)函數(shù)的問題一、極小化目標(biāo)函數(shù)的問題 min z = CX 令令 z= z max z= CX 例例：min z = 3x1 2x2 max z= 3x1 2x2 二、約束條件不是等式的問題二、約束條件不是等式的問題 bim），其秩為m，B是A矩陣中的一個非奇異的mm 階（滿秩）子矩陣，則稱B為線性規(guī)劃的一個基基。 與其中的列

24、向量所對應(yīng)的變量叫做基變量基變量，除基變量之外的變量稱為非基變量非基變量?！?11211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)四、線性規(guī)劃的基、基本可行解 定義定義2-5 基本解 令所有的非基變量等于零，根據(jù)Cramer Rule，將得到唯一解，稱為線性規(guī)劃的基本解。 基本可行解 滿足非負(fù)約束條件（XB=B-1b0）的基本解稱為基本可行解。相應(yīng)地，基本可行解對應(yīng)的基稱為可行基可行基。0bBXXX1NB

25、“211211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)-33-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

26、，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，X=(4,0,-1,0)T| B |=-10,非基本可行解非基本可行解基本可行解基本可行解標(biāo)準(zhǔn)化四、線性規(guī)劃的基、基本可行解“211211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證

27、規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)四、線性規(guī)劃的基、基本可行解 定理定理2-1 線性規(guī)劃的基本可行解就是可行域的極點。線性規(guī)劃的基本可行解就是可行域的極點。34Max z=2x1+3x2 s.t. x1+x2 3 x1+2x2 4 x1,x2 0 Max z=2x1+3x2 +0 x3 +0 x4 s.t. x1+x2 +x3 = 3 x1+2x2 +x4=4 x1, x2, x3 , x4 0例：例：標(biāo)準(zhǔn)化10210111,4321ppppAA矩陣包含以下六個矩陣包含以下六個22的子矩陣：的子矩陣：B1=p1，p2 B2=p1，p3 B3=p1，p4B4=p2，p3 B5=p2，p4 B6

28、=p3，p4其中所有的子矩陣行列式值均不等于其中所有的子矩陣行列式值均不等于0，均為非奇異方陣，因此，均為非奇異方陣，因此該問題共有該問題共有6個基。個基。 “211211工程工程”重點建設(shè)大學(xué)，世界海事大學(xué)中國分校重點建設(shè)大學(xué)，世界海事大學(xué)中國分校國內(nèi)第一所獲得國內(nèi)第一所獲得ISO9001ISO9001質(zhì)量管理體系認(rèn)證證書和質(zhì)量管理體系認(rèn)證證書和DNVDNV三個認(rèn)證規(guī)則證書的大學(xué)三個認(rèn)證規(guī)則證書的大學(xué)四、線性規(guī)劃的基、基本可行解35B6= 1 0 0 1，則 | B6 |=10,x3 x4基變量基本可行解 對應(yīng)O點令 x1=x2 =0，則 x3 =3, x4=4，X6=(0,0,3,4)T同

29、理同理可以求得可以求得B1、B2、B3、B4、B5對應(yīng)的基本解：對應(yīng)的基本解：X1=(x1，x2，x3，x4)T=(2，1，0，0)T 對應(yīng)對應(yīng)B點點X2=(x1，x2，x3，x4)T=(4，0，-1，0)T對應(yīng)對應(yīng)E點點X3=(x1，x2，x3，x4)T=(3，0，0，1)T對應(yīng)對應(yīng)C點點X4=(x1，x2，x3，x4)T=(0，2，1，0)T對應(yīng)對應(yīng)A點點X5=(x1，x2，x3，x4)T=(0，3，0，-2)T對應(yīng)對應(yīng)D點點其中其中X1， X3 ， X4 是是基本可行解基本可行解。O(0, ,0)x1x2B(2,1,1)E(4, ,0)C(3, ,0)A(0,2,2)D(0, ,3)“211211工程工程”重點建設(shè)大學(xué)，世界海事