運(yùn)籌學(xué)-第01章-線(xiàn)性規(guī)劃問(wèn)題

運(yùn)籌學(xué)

第一章線(xiàn)性規(guī)劃問(wèn)題本章重點(diǎn)線(xiàn)性規(guī)劃建模線(xiàn)性規(guī)劃的圖解法線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)形式單純形法兩階段法大M法線(xiàn)性規(guī)劃的概念對(duì)于求取變量xj(j=1,2,…,n)，使之既滿(mǎn)足線(xiàn)性約束條件，又使線(xiàn)性的目標(biāo)函數(shù)取得極值的一類(lèi)最優(yōu)化問(wèn)題稱(chēng)為線(xiàn)性規(guī)劃問(wèn)題xj(j=1,2,…,n)表示解決問(wèn)題的方案，稱(chēng)為決策變量約束條件表示要解決的問(wèn)題的限制條件，用一組決策變量的線(xiàn)性等式或線(xiàn)性不等式來(lái)表示目標(biāo)函數(shù)表示要解決的問(wèn)題要求達(dá)到的目標(biāo)，用決策變量的線(xiàn)性函數(shù)表示線(xiàn)性規(guī)劃建模步驟設(shè)定決策變量明確約束條件并用決策變量的線(xiàn)性等式或不等式表示用變量的線(xiàn)性函數(shù)表示要達(dá)到的目標(biāo)，并確定是求極小還是求極大根據(jù)變量的物理性質(zhì)確定變量是否具有非負(fù)性注：其中最關(guān)鍵是設(shè)定決策變量這一步生產(chǎn)計(jì)劃問(wèn)題(1)某工廠(chǎng)用三種原料生產(chǎn)三種產(chǎn)品，已知的條件如下表所示，試制訂總利潤(rùn)最大的日生產(chǎn)計(jì)劃產(chǎn)品所需原料數(shù)量（公斤/件）產(chǎn)品Q(chēng)1（件）產(chǎn)品Q(chēng)2（件）產(chǎn)品Q(chēng)3（件）原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000產(chǎn)品的利潤(rùn)（千元/件）354生產(chǎn)計(jì)劃問(wèn)題(2)設(shè)每天生產(chǎn)三種產(chǎn)品的件數(shù)分別為x1、x2、x3其中，max是maximize的縮寫(xiě)，含義為“最大化”；s.t.是subjectto的縮寫(xiě)，其含義是“受限制于……”配料問(wèn)題(1)養(yǎng)海貍鼠，飼料營(yíng)養(yǎng)要求：VA每天至少700克，VB每天至少30克，VC每天剛好200克?，F(xiàn)有五種飼料，搭配使用，飼料成分如下表。問(wèn)如何購(gòu)買(mǎi)飼料，使得花費(fèi)最少？飼料Va(g)Vb(g)Vc(g)價(jià)格(元/kg)I(kg)II(kg)III(kg)IV(kg)V(kg)32161810.50.220.50.510.220.827495營(yíng)養(yǎng)要求(g)70030200配料問(wèn)題(2)設(shè)購(gòu)買(mǎi)飼料分別為x1、x2、x3、x4、x5

kg目標(biāo)函數(shù)為：花費(fèi)最少，則有其中，min是minimize的縮寫(xiě)，含義為“最小化”；合理下料問(wèn)題(1)現(xiàn)需要2.9m、2.1m、1.5m長(zhǎng)的棒料各100根，問(wèn)要怎樣切割7.4m長(zhǎng)的原料才能使零料最少？總共有以下6種切割方案，設(shè)xj分別代表采用切割方案j使用的原料數(shù)量合理下料問(wèn)題(2)目標(biāo)函數(shù)為：使裁剪后零料最少，則有人員安排問(wèn)題(1)醫(yī)院護(hù)士24小時(shí)值班，不同時(shí)段需要的護(hù)士人數(shù)不等（見(jiàn)下表）。每個(gè)護(hù)士每天連續(xù)值班8小時(shí)，在各時(shí)段開(kāi)始時(shí)上班。問(wèn)最少需要多少護(hù)士？序號(hào)時(shí)段最少人數(shù)106—1060210—1470314—1860418—2250522—0220602—0630人員安排問(wèn)題(2)設(shè)xj為第j時(shí)段開(kāi)始值班的護(hù)士人數(shù)目標(biāo)函數(shù)為：使人數(shù)最少，則有運(yùn)輸問(wèn)題(1)某廠(chǎng)要把若干單位的產(chǎn)品從兩個(gè)倉(cāng)庫(kù)Ai(i=1,2)發(fā)送到零售點(diǎn)Bj(j=1,2,3,4)，倉(cāng)庫(kù)Ai能供應(yīng)的產(chǎn)品數(shù)量為ai，零售點(diǎn)Bj所需的產(chǎn)品的數(shù)量為bj。假設(shè)供給總量和需求總量相等，且已知從Ai運(yùn)一個(gè)單位產(chǎn)品往Bj的運(yùn)價(jià)為cij。問(wèn)應(yīng)如何組織運(yùn)輸才能使總運(yùn)費(fèi)最??？運(yùn)輸問(wèn)題(2)設(shè)從倉(cāng)庫(kù)Ai運(yùn)往的零售點(diǎn)Bj產(chǎn)品數(shù)量為xij目標(biāo)函數(shù)為：使總運(yùn)費(fèi)最少，則有最大流量問(wèn)題(1)某油田通過(guò)輸油管道向港口輸送原油，中間有5個(gè)泵站（泵站不存儲(chǔ)原油），每段管道上的輸送能力如下圖所示，求這個(gè)系統(tǒng)的最大輸送能力。

最大流量問(wèn)題(2)設(shè)各點(diǎn)往其他點(diǎn)的輸送量如下表所示

最大流量問(wèn)題(3)可得線(xiàn)性規(guī)劃模型線(xiàn)性規(guī)劃的一般形式(和式)線(xiàn)性規(guī)劃的一般形式(矩陣式)作業(yè)(1)書(shū)上68頁(yè)1-1書(shū)上72-73頁(yè)的1-8、1-9、1-10線(xiàn)性規(guī)劃的圖解法f(x)=36圖解法一般只用有于1-3個(gè)決策變量的線(xiàn)性規(guī)劃作業(yè)(2)書(shū)上70頁(yè)1-3的②線(xiàn)性規(guī)劃問(wèn)題的單純形解法為了使線(xiàn)性規(guī)劃問(wèn)題的解法標(biāo)準(zhǔn)，就要把一般形式化為標(biāo)準(zhǔn)形式線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)形式(和式)線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)形式(矩陣式)非標(biāo)準(zhǔn)形式的轉(zhuǎn)換(1)目標(biāo)函數(shù)為min型，價(jià)值系數(shù)一律反號(hào)令f

(X)=-f(X)=-CX則minf(X)=-max[-f(X)]=-maxf

(X)第i個(gè)約束的bi為負(fù)值則該行左右兩端系數(shù)同時(shí)反號(hào)，同時(shí)不等號(hào)也要反向m>n或m≤n,rankA≠m可以去掉m-rankA個(gè)等式約束非標(biāo)準(zhǔn)形式的轉(zhuǎn)換(2)第i個(gè)約束為型在不等式左邊加上一個(gè)非負(fù)的變量xn+i，稱(chēng)為松弛變量；同時(shí)令cn+i=0第i個(gè)約束為型在不等式左邊減去一個(gè)非負(fù)的變量xn+i

，也稱(chēng)為松弛變量；同時(shí)令cn+i

=0若xj0令xj=-xj

，代入非標(biāo)準(zhǔn)型，則有xj

0若xj不限符號(hào)令xj=xj

-xj

，xj

0，xj

0，代入非標(biāo)準(zhǔn)型示例(1.1-1)作業(yè)(3)書(shū)上69頁(yè)1-2的①線(xiàn)性規(guī)劃問(wèn)題解的有關(guān)概念(1)可行解：滿(mǎn)足所有約束條件的一組變量的取值。所有可行解構(gòu)成的集合稱(chēng)為可行解集?？尚杏颍河捎谝话憔€(xiàn)性規(guī)劃問(wèn)題的可行解集構(gòu)成n維空間的區(qū)域，因此可行解集也稱(chēng)為可行域。最優(yōu)解：使目標(biāo)函數(shù)取到最大值(max)或最小值(min)的可行解稱(chēng)為線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)解。最優(yōu)值：最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)的取值稱(chēng)為最優(yōu)值基：設(shè)A為線(xiàn)性規(guī)劃模型中約束方程的系數(shù)矩陣(m

n，且m<n)，而B(niǎo)為其m

m階非奇異子矩陣（即|B|≠0），則稱(chēng)B為該線(xiàn)性規(guī)劃模型的一個(gè)基?；兞浚夯忻總€(gè)列向量所對(duì)應(yīng)的變量稱(chēng)為基變量。非基變量：模型中基變量之外的變量稱(chēng)為非基變量。線(xiàn)性規(guī)劃問(wèn)題解的有關(guān)概念(2)基本解：令模型中所有非基變量的值等于零后，由模型的約束方程組得到的一組解?；究尚薪猓簼M(mǎn)足非負(fù)條件的基本解稱(chēng)為基本可行解。可行基：對(duì)應(yīng)于基本可行解的基稱(chēng)為可行基。退化解：基本可行解的非零分量個(gè)數(shù)小于m時(shí)，稱(chēng)為退化解。最優(yōu)基：若對(duì)應(yīng)于基B的基本可行解X是線(xiàn)性規(guī)劃的最優(yōu)解，則稱(chēng)B為線(xiàn)性規(guī)劃的最優(yōu)基線(xiàn)性規(guī)劃問(wèn)題解的有關(guān)概念(3)線(xiàn)性規(guī)劃問(wèn)題解的關(guān)系約束方程的解空間基本解可行解基本可行解退化解Rn示例(1.2-1)可行解、基本解和基本可行解舉例線(xiàn)性規(guī)劃問(wèn)題解的特點(diǎn)(1)凸集：設(shè)S為n維歐氏空間En

中一個(gè)集合，若對(duì)任意兩點(diǎn)x∈S，y∈S及任一實(shí)數(shù)λ∈[0,1]，都有λx+(1-λ)y∈S，則稱(chēng)S是En

中的凸集。λx+(1-λ)y稱(chēng)為x和y的凸組合。凸集中任意兩點(diǎn)連線(xiàn)上的點(diǎn)都在該凸集中凸集的頂點(diǎn)：設(shè)S為非空凸集，z∈S，若z不能表示成S中兩個(gè)不同點(diǎn)的凸組合（即假設(shè)z=λx+(1-λ)y，x∈S，y∈S，λ∈(0,1)，必推得z=x=y），則稱(chēng)z是凸集S的頂點(diǎn)。凸集的頂點(diǎn)的個(gè)數(shù)一般是有限的(無(wú)限凸集和曲邊界凸集除外)線(xiàn)性規(guī)劃問(wèn)題解的特點(diǎn)(2)線(xiàn)性規(guī)劃問(wèn)題的可行域是凸集線(xiàn)性規(guī)劃問(wèn)題解的特點(diǎn)(3)線(xiàn)性規(guī)劃問(wèn)題的基本可行解對(duì)應(yīng)于凸集的頂點(diǎn)最優(yōu)解只可能在凸集的頂點(diǎn)或邊界上，而不可能發(fā)生在凸集的內(nèi)部線(xiàn)性規(guī)劃問(wèn)題解的特點(diǎn)(4)若有兩個(gè)最優(yōu)解，則其連線(xiàn)上的點(diǎn)也是最優(yōu)解，即最優(yōu)解有無(wú)窮多個(gè)頂點(diǎn)個(gè)數(shù)=基本可行解個(gè)數(shù)≤基的個(gè)數(shù)≤線(xiàn)性規(guī)劃解的情況下面的求解方法考慮三種情況：有有界解、有無(wú)界解、無(wú)解以2個(gè)變量的線(xiàn)性規(guī)劃為例單純形法求解的基本原理從可行域的某個(gè)頂點(diǎn)出發(fā)，設(shè)法求取使目標(biāo)改善的另一個(gè)頂點(diǎn)，直至確定某個(gè)頂點(diǎn)使目標(biāo)最優(yōu)或者有無(wú)界解為止。確定初始基本可行解求最優(yōu)解的目標(biāo)函數(shù)值確定改善方向求新的基本可行解檢查是否為最優(yōu)解？是否原線(xiàn)性規(guī)劃問(wèn)題單純形法應(yīng)用的前提如何換基確定初始基本可行解(1)bAZCb1a11a12…a1nb2a21a22…a2n…………bmam1am2…amnZc1c2c3c4下面是線(xiàn)性規(guī)劃問(wèn)題標(biāo)準(zhǔn)形式的參數(shù)表Z表示目標(biāo)函數(shù)確定初始基本可行解(2)具體如何得到一組初始基本可行解不是單純形法考慮的內(nèi)容，在兩階段法/大M法中說(shuō)明下面介紹在確定了一個(gè)可行基（或一組基變量）后，如何由參數(shù)表得到單純形表根據(jù)等式約束，把基變量用非基變量表達(dá)把基變量的表達(dá)式代入目標(biāo)函數(shù)，用非基變量表示目標(biāo)函數(shù)把基變量的表達(dá)式按等式約束的形式寫(xiě)出，這m個(gè)等式約束和用非基變量表示的目標(biāo)函數(shù)以及非負(fù)約束構(gòu)成一個(gè)新的線(xiàn)性規(guī)劃，這個(gè)線(xiàn)性規(guī)劃和原線(xiàn)性規(guī)劃等價(jià)這個(gè)線(xiàn)性規(guī)劃的參數(shù)表即為原線(xiàn)性規(guī)劃的一個(gè)單純形表確定初始基本可行解(3)B-1bB-1BB-1NZ-CBB-1bCB-CBB-1BCN-CBB-1NB-1bIB-1NZ-CBB-1b0CN-CBB-1NbAZCbBNZCBCNB-1bB-1BB-1NZCBCN用矩陣表示如下：等式變換用非基變量表示目標(biāo)函數(shù)為了方便矩陣運(yùn)算，通常將目標(biāo)Z記為0下面的單純形表中，B-1b是基變量的解值，非基變量的解值均為0，對(duì)應(yīng)的目標(biāo)函數(shù)值為CBB-1b，σN=CN-CBB-1N稱(chēng)為非基變量的檢驗(yàn)數(shù)示例(1.3-1)試列出下面線(xiàn)性規(guī)劃問(wèn)題的初始單純形表1002311012033201040452400注：該問(wèn)題添加了兩個(gè)松弛變量，標(biāo)準(zhǔn)形式的參數(shù)表就是初始單純形表判斷是否最優(yōu)在用非基變量表示的目標(biāo)函數(shù)中，σN=CN-CBB-1N稱(chēng)為非基變量的檢驗(yàn)數(shù)，它們是目標(biāo)函數(shù)中非基變量的系數(shù)假設(shè)非基變量xj的檢驗(yàn)數(shù)為σj，若xj

從0開(kāi)始增大，其他非基變量的值不變，則基變量和目標(biāo)函數(shù)（用非基變量表示）要發(fā)生變化σj≤0時(shí)，目標(biāo)函數(shù)值減少，當(dāng)前基本可行解即為最優(yōu)解σj＞0時(shí)，目標(biāo)函數(shù)值增大，當(dāng)前基本可行解不是最優(yōu)解因此，若σN≤0，則當(dāng)前基本可行解是最優(yōu)解，算法結(jié)束，否則，需要進(jìn)行改善1002311012033201040452400確定改善方向(1)確定入基變量從不滿(mǎn)足σN≤0的非基變量中任選一個(gè)xj*，xj*稱(chēng)為入基變量，讓xj*增大可以改善目標(biāo)第j*+1列稱(chēng)為主列xj*的選擇可以任意，但有可能會(huì)造成解的退化，進(jìn)而產(chǎn)生循環(huán)計(jì)算。一般選擇下標(biāo)j最小的（或最大的）1002311012033201040452400確定改善方向(2)若找不到

，則算法結(jié)束，原問(wèn)題有無(wú)界解若所有的aij*≤0，則xj*在所有基變量的表達(dá)式中系數(shù)都為正，則xj*可以一直增大，使目標(biāo)函數(shù)趨向無(wú)窮若下標(biāo)i*(即第i*行)使

最小，則第i*行對(duì)應(yīng)的基變量稱(chēng)為出基變量，第i*行稱(chēng)為主行若有多個(gè)行同時(shí)使

最小，可以任意選擇其中之一為主行，但有可能會(huì)造成解的退化，進(jìn)而產(chǎn)生循環(huán)計(jì)算。一般選擇

i最小的(或最大的)行主行

i*行與主列

j*相交的元素ai*j*

稱(chēng)為主元確定出基變量為了保證不出基的基變量的取值在改善后仍為正值，按最小比例原則選擇出基變量1002311012033201040452400解的改善進(jìn)行換基運(yùn)算（也稱(chēng)為換主元運(yùn)算）對(duì)當(dāng)前的線(xiàn)性規(guī)劃，通過(guò)等式變換將主行所對(duì)應(yīng)的等式約束中xj*的系數(shù)變?yōu)?消去其它等式約束和目標(biāo)函數(shù)中的xj*（將其系數(shù)變?yōu)?）相當(dāng)于，在單純形表中，通過(guò)矩陣的初等行變換將主行的各元素乘上某一個(gè)數(shù)值，使得主元的值變?yōu)?將主行的各元素乘上某一個(gè)數(shù)值，再加到其他行上去，使得主列中除主元外的其它元素的值變?yōu)?得到了一個(gè)改善的基本可行解返回判斷解是否最優(yōu)示例(1.3-2)10023110120332010404524001002311040112/301/3040452400示例(1.3-3)2001-1/31-2/340112/301/3-160005-8/30-40/3檢驗(yàn)數(shù)σ2不滿(mǎn)足非正條件，需要調(diào)整2001-1/31-2/320101-11-170000-1-5-10檢驗(yàn)數(shù)全部滿(mǎn)足非正條件得最優(yōu)解為x1=20，x2=20，x3=0maxf(X)=1700下面給出該問(wèn)題的最優(yōu)基示例(1.3-4)將最優(yōu)表中m個(gè)基變量的約束方程系數(shù)列按單位矩陣Im

順序排列，同時(shí)相應(yīng)的調(diào)整參數(shù)表中基變量的約束方程系數(shù)列的順序由調(diào)整后的參數(shù)表中m個(gè)基變量的約束方程系數(shù)列組成的m階方陣就是最優(yōu)基2001-1/31-2/320101-11-170000-1-5-101002311012033201040452400作業(yè)(4)書(shū)上70頁(yè)1-5的②和④補(bǔ)充要求：寫(xiě)出最優(yōu)基確定初始基本可行解的方法(1)由原線(xiàn)性規(guī)劃問(wèn)題直接確定一組初始基本可行解很多時(shí)候是很困難的?？梢酝ㄟ^(guò)添加人工變量的方法來(lái)確定一組初始基本可行解確定初始基本可行解的方法(2)添加的變量xn+1,xn+2,…,xn+m稱(chēng)為人工變量添加了人工變量后，新問(wèn)題有了一個(gè)初始基本可行解，可以用單純形法迭代計(jì)算。若原線(xiàn)性規(guī)劃問(wèn)題第i個(gè)約束為型，則將其化為標(biāo)準(zhǔn)形式后再添加人工變量時(shí)，相應(yīng)的人工變量xn+i可以不用再添加了經(jīng)過(guò)若干次迭代，把人工變量全部替換出基，則原問(wèn)題的約束條件得到恢復(fù)，同時(shí)也就有了一個(gè)原問(wèn)題的基本可行解確定初始基本可行解的方法(3)這一方法的關(guān)鍵在于怎樣才能將人工變量盡快替換出基為了解決這個(gè)問(wèn)題，提出了兩種方法大M法兩階段法大M法(1)大M法也稱(chēng)為懲罰法M為任意大的正數(shù)大M法(2)對(duì)新的線(xiàn)性規(guī)劃使用單純形法，其解有兩種情況若有無(wú)界最優(yōu)解，則原問(wèn)題有無(wú)界最優(yōu)解若有有界最優(yōu)解，又有兩種情況若人工變量的值不全為0，則原問(wèn)題無(wú)可行解若人工變量取值均為0，則當(dāng)前最優(yōu)值就是原問(wèn)題的最優(yōu)值，當(dāng)前最優(yōu)解的前n個(gè)分量就是原問(wèn)題的最優(yōu)解若原問(wèn)題有可行解X=(x1,x2,…,xn)T，則X’=(x1,x2,…,xn,0,…,0)T是新的線(xiàn)性規(guī)劃的可行解，則g(X)有界。若人工變量的值不全為0，則g(X)趨向于負(fù)無(wú)窮。因此，原問(wèn)題無(wú)可行解。示例(1.4-1)用大M法求解下面的線(xiàn)性規(guī)劃先化為標(biāo)準(zhǔn)形式示例(1.4-2)改成大M法需要的線(xiàn)性規(guī)劃列出參數(shù)表6210-101041110-1010-10-8-700-M-M示例(1.4-3)調(diào)整得6210-101041110-10110M-10+3M-8+2M-7+M-M-M00311/20-1/201/20101/211/2-1-1/2130+M0-3+M/2-7+M-5+M/2-M5-3M/20示例(1.4-4)210-1-111-120121-2-123600-1-2-62-M6-M檢驗(yàn)數(shù)全部滿(mǎn)足非正條件得原問(wèn)題的最優(yōu)解為x1=2，x2=2，x3=0minf(X)=36兩階段法(1)兩階段法(2)對(duì)新的線(xiàn)性規(guī)劃使用單純形法，必定存在一個(gè)有界最優(yōu)解，在這個(gè)最優(yōu)解中若最優(yōu)值不為0

，則原問(wèn)題無(wú)可行解若最優(yōu)值為0，則原問(wèn)題有可行解人工變量均為非基變量對(duì)當(dāng)前的單純形表，去掉其中人工變量對(duì)應(yīng)的列，將最后一行（目標(biāo)函數(shù)系數(shù)對(duì)應(yīng)的行）的