《運(yùn)籌學(xué)》第1章 線性規(guī)劃

1.1線性規(guī)劃問(wèn)題及數(shù)學(xué)模型1.2線性規(guī)劃的圖解法1.3單純形法原理1.4單純形法的計(jì)算步驟1.5單純形法的進(jìn)一步討論1.6應(yīng)用舉例第1章線性規(guī)劃1.1.1

問(wèn)題的提出

在生產(chǎn)經(jīng)營(yíng)管理工作中，常常需要進(jìn)行計(jì)劃或規(guī)劃。雖然不同行業(yè)計(jì)劃的內(nèi)容千差萬(wàn)別，但其共同點(diǎn)均可歸結(jié)為解決兩類(lèi)主要的問(wèn)題：一類(lèi)是在資源(人力、物力、財(cái)力……)一定的情況下，如何利用這些有限的資源來(lái)完成最多的任務(wù)；另一類(lèi)是在預(yù)期目標(biāo)確定的情況下，如何利用最少的資源來(lái)完成這個(gè)確定的任務(wù)。1.1線性規(guī)劃問(wèn)題及數(shù)學(xué)模型

例1-1某建筑公司的預(yù)制廠利用沙、石、水泥三種原料A1、A2、A3，來(lái)生產(chǎn)兩種產(chǎn)品B1和B2，已知該廠各種原料的現(xiàn)有數(shù)量、單位產(chǎn)品對(duì)各種原料的消耗量及單位利潤(rùn)如表1-1所示。在這些現(xiàn)有的資源的條件下，如何分配產(chǎn)品B1和B2的生產(chǎn)，才使公司取得最大利潤(rùn)。

1.1.1

問(wèn)題的提出表1-1生產(chǎn)消耗及現(xiàn)有原料B1

B1原料現(xiàn)有(M3)A1A2A3132111908045單位利潤(rùn)(百元)54產(chǎn)產(chǎn)品原料品的消耗單位分析：設(shè)x1表示產(chǎn)品B1的生產(chǎn)數(shù)量，x2為產(chǎn)品B2的生產(chǎn)數(shù)量。公司可以獲取的利潤(rùn)為(5x1+4x2

)百元，令z=5x1+4x2，因問(wèn)題中要求獲利最大，即maxz。又z是該公司能獲取的利潤(rùn)的目標(biāo)值，它是變量x1，x2的函數(shù)，其取值受到原材料A1、A2、A3的限制，由此例1-1的數(shù)學(xué)模型可表示為：1.1.1

問(wèn)題的提出

例1-2現(xiàn)需100套鋼架，每套用長(zhǎng)為3.5m，2.6m和1.6m的圓鋼各一根。原料長(zhǎng)8.8m，問(wèn)如何下料，使用的原材料最省。分析

現(xiàn)最簡(jiǎn)單做法是，在每一根原料上截取3.5m，2.6m和1.6m的圓鋼各一根組成一套，100套鋼架需用原料100根。若改為用套裁，就可以節(jié)約原材料。套裁方案見(jiàn)表1-2。1.1.1

問(wèn)題的提出表1-2套裁方案方案ⅠⅡⅢⅣⅤ3.52112.6221.61325合計(jì)8.68.78.38.48料頭0.20.10.50.40.8數(shù)長(zhǎng)k(m)下j根為了得到100套鋼架，需要混合使用各種下料方案。設(shè)按Ⅰ方案下料的原材料根數(shù)為x1，Ⅱ方案為x2，Ⅲ方案為x3，Ⅳ方案為x4，Ⅴ方案為x5。根據(jù)表1-2的方案，可列出以下數(shù)學(xué)模型：1.1.1

問(wèn)題的提出在從以上兩個(gè)例子可以看出，規(guī)劃問(wèn)題的數(shù)學(xué)模型包含三個(gè)要素組成：(1)變量，或稱決策變量，是問(wèn)題中要確定的未知量。每一個(gè)問(wèn)題都用一組決策變量(x1，x2，…，xn)表示某一方案，這組決策變量的值就代表一個(gè)具體的方案。(2)約束條件，指決策變量取值時(shí)受到的各種資源條件的限制，通?？捎靡唤M含決策變量的等式或不等式來(lái)表示。(3)目標(biāo)函數(shù)，它是決策變量的線性函數(shù)，按問(wèn)題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。1.1.2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型假定線性規(guī)劃問(wèn)題中含n個(gè)變量，分別用xj表示，在目標(biāo)函數(shù)中xj的系數(shù)為cj，xj的取值受m項(xiàng)資源的限制，用bi表示第i種資源的擁有量，用aij表示變量xj取值為1個(gè)單位時(shí)所消耗或含有的第i種資源的數(shù)量，則上述線性規(guī)劃問(wèn)題的數(shù)學(xué)模型可表示為：1.1.2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型上述模型(1-1)可簡(jiǎn)寫(xiě)為：1.1.2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型向量表示形式為：矩陣表示形式為：由于目標(biāo)函數(shù)和約束條件內(nèi)容和形式上的不同，線性規(guī)劃問(wèn)題可以有多種表達(dá)式。為了便于討論和制定統(tǒng)一的算法，規(guī)定線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式如下：1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式對(duì)不符合標(biāo)準(zhǔn)形式(或稱非標(biāo)準(zhǔn)形式)的線性規(guī)劃問(wèn)題，可分別通過(guò)下列方法化為標(biāo)準(zhǔn)形式。(1)目標(biāo)函數(shù)為求最小值，這時(shí)只需將目標(biāo)函數(shù)最小化變換求目標(biāo)函數(shù)最大化。(2)約束條件的右端項(xiàng)bi<0時(shí)，只需將等式或不等式兩端同乘(-1)，則約束條件右端項(xiàng)必大于零。(3)約束條件為不等式。這里有兩種情況：1)約束條件為“≤”形式。對(duì)這樣的約束，在“≤”不等式的左端加上一個(gè)非負(fù)的新變量即可以化為等式。新增的非負(fù)變量稱為松弛變量。2)約束條件為“≥”形式。對(duì)這樣的約束，在“≥”不等式的左端減去一個(gè)非負(fù)的新變量即可以化為等式。新增的非負(fù)變量稱為剩余變量，亦可以稱為松弛變量。1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式(4)決策變量，這時(shí)可能有以下情況：1)決策變量xj≤0，則令非負(fù)變量x′j=?xj，顯然x′j≥0。2)決策變量xj取值不受限制，可以用兩個(gè)非負(fù)的新變量之差來(lái)代替。如變量xj取值不受限制，則令xj=x′j?x″j，新變量x′j和x″j為非負(fù)變量，xj的符號(hào)由x′j和x″j來(lái)確定。3)決策變量有上下界。對(duì)這種情況，可將上下界分別處理。引進(jìn)新的變量使等于原變量減去下限值，如此則下限為零，滿足標(biāo)準(zhǔn)形式的非負(fù)性要求。如已知決策變量xj的限制為aj≤xj≤bj，則令x′j=xj?aj，從而得0≤x′j≤bj?aj，現(xiàn)時(shí)的x′j滿足了非負(fù)要求。用新變量x′j替換目標(biāo)函數(shù)和約束條件中所有的原變量xj，再將上限約束列為新的約束條件并化為等式。1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式

例1-3將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式。

1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式

解

(1)因?yàn)閤3符號(hào)不限，以x3=x′3?x″3代入目標(biāo)函數(shù)和所有約束條件中，其中x′3，x″3均為非負(fù)變量。(2)對(duì)第一個(gè)約束加上松弛變量x4化為等式。(3)對(duì)后兩個(gè)約束分別減去剩余變量x5和x6化為等式。(4)為了保持目標(biāo)函數(shù)不變，使x4，x5和x6的目標(biāo)系數(shù)均為零。得到的標(biāo)準(zhǔn)形式線性規(guī)劃為：1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式1.1.4

線性規(guī)劃問(wèn)題的解的概念(1)可行解，滿足線性規(guī)劃的約束條件(1-7)和(1-8)的解。(2)可行域，所有可行解組成的集合。(3)最優(yōu)解，使線性規(guī)劃目標(biāo)函數(shù)(1-6)達(dá)到最大值的可行解。(4)基，若B是約束方程組系數(shù)矩陣A中m×m階非奇異子陣(|B|≠0)，則稱B是線性規(guī)劃問(wèn)題的一個(gè)基。(5)基向量，B中的每一個(gè)列向量Pj(j=1,2,…,m)。(6)基變量，與基向量Pj對(duì)應(yīng)的決策變量，線性規(guī)劃中除基變量以外的其他變量稱為非基變量。假設(shè)系數(shù)矩陣A的秩m(m<n)，故方程組(1-7)有無(wú)窮多個(gè)解。不失一般性，不妨假設(shè)方程組的前m個(gè)變量的系數(shù)列向量的線性無(wú)關(guān)的，于是方程組(1-7)可改寫(xiě)為：

1.1.4

線性規(guī)劃問(wèn)題的解的概念(7)基解，若令(1-9)式的非基變量xm+1=xm+2=…=xn=0，由m個(gè)約束方程可解出個(gè)m基變量的惟一解XB，將這個(gè)解加上非基變量取0的值，得到(1-9)的一個(gè)解，稱X為線性規(guī)劃的基解。(8)基可行解，滿足變量非負(fù)約束條件(1-8)的基解。(9)可行基,對(duì)應(yīng)于基可行解的基。1.1.4

線性規(guī)劃問(wèn)題的解的概念

例1-5找出下述線性規(guī)劃問(wèn)題的全部基解，指出其中的基可行解，并確定最優(yōu)解。

表1-3線性規(guī)劃的基解基x1x2x3x4x5z是否基可行解P3P4P50051045是P2P3P40452017是P1P4P55005410是P2P3P40550-120否P1P3P5100-50415否P1P2P552.5001.517.5是P1P2P4540-3022否P1P2P32430019*是1-2線性規(guī)劃的圖解法圖解法是采用直角坐標(biāo)系及其基本原理設(shè)計(jì)出的一種求解方法，其步驟如下：第一步：在平面坐標(biāo)系中，給出各約束條件的圖形，并確定出可行域。第二步：畫(huà)出目標(biāo)函數(shù)直線束中穿過(guò)可行域的任一條直線，并將該直線沿目標(biāo)函數(shù)取優(yōu)(大或小)的方向平行移動(dòng)，當(dāng)直線離開(kāi)可行域時(shí)，最后接觸的可行域的頂點(diǎn)(極點(diǎn))為最優(yōu)點(diǎn)。第三步：聯(lián)立通過(guò)最優(yōu)點(diǎn)的方程得出最優(yōu)解。第四步：將最優(yōu)解代入目標(biāo)函數(shù)得出最優(yōu)值。1-2線性規(guī)劃的圖解法

例1-6

用圖解求解線性規(guī)劃

O圖1-1x1x2ABC2x1+3x2=122x1+x2=86x1+7x2=7最優(yōu)解X*=(3，2)T1-2線性規(guī)劃的圖解法

例1-7

用圖解求解線性規(guī)劃O圖1-2x1x2x1=4x1+2x2=8ADBCx2=3線段BC上的點(diǎn)都是最優(yōu)解1-2線性規(guī)劃的圖解法

例1-8

用圖解求解線性規(guī)劃O圖1-3x1x2圖1-3中的凸多邊形ABCD為線性規(guī)劃的可行域，它是無(wú)界的，因而可行解集也是無(wú)界集合。ADBCx1-x2=1-x1+2x2=01-2線性規(guī)劃的圖解法

例1-9

用圖解求解線性規(guī)劃O圖1-4x1x2由圖1-4可知，同時(shí)滿足四個(gè)不等式的點(diǎn)不存在，所以該線性規(guī)劃無(wú)可行解，即無(wú)可行域。x1+x2=-2-x1+x2=11-3單純形法原理1.3.1

線性規(guī)劃問(wèn)題的幾何意義

(1)凸集，設(shè)M是n維歐氏空間的一個(gè)點(diǎn)集。若M中任意兩點(diǎn)X(1)，X(2)的連線上的一切點(diǎn)αX(1)+(1-α)X(2)(0≤α≤1)仍在點(diǎn)集M中，則稱M為凸集。(2)頂點(diǎn)，設(shè)M是凸集，X∈M；若X不能用M中兩個(gè)不同點(diǎn)X(1)，X(2)的線性組合表示為X=αX(1)+(1-α)X(2)(0<α<1)，則稱為凸集M的一個(gè)頂點(diǎn)(或極點(diǎn))。(3)凸組合，設(shè)X(1),X(2),…,X(k)是n維歐氏空間中k個(gè)點(diǎn)，若存在λ1,λ2,…,λk，且0≤λi≤1(i=1,2,…,k)，∑λ=1，使得X=λ1X(1)+λ2X(2)+…+λkX(k)，則稱X為K個(gè)點(diǎn)X(1),X(2),…,

X(k)的凸組合。1.3.1線性規(guī)劃問(wèn)題的幾何意義定理1-1線性規(guī)劃問(wèn)題的所有可行解的集合(即可行域)。引理1

線性規(guī)劃問(wèn)題的可行解X=(x1，x2，…，xn)T是基可行解的充要條件是的正分量所對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的。定理1-2線性規(guī)劃問(wèn)題的基可行解X對(duì)應(yīng)于可行域S頂點(diǎn)。引理2

若M是有界凸集，則任何一點(diǎn)X∈M可表示為的M頂點(diǎn)的凸組合。定理1-3若可行域有界，線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)達(dá)到最優(yōu)。1.3.2確定初始基可行解為確定初始基可行解，首先確定初始可行基，方法如下：(1)若線性規(guī)劃問(wèn)題在約束條件式(1-13)的變量的系數(shù)矩陣中一般能直接觀察到存在一個(gè)初始可行基。1.3.2確定初始基可行解(2)若線性規(guī)劃問(wèn)題的約束條件全部為“≤”形式的不等式，可以利用化為標(biāo)準(zhǔn)形式的方法，在每個(gè)約束條件的左端加上一個(gè)松弛變量。由于這個(gè)系數(shù)矩陣中含有一個(gè)單位矩陣(P1，…，Pm)，以這個(gè)單位矩陣為基，可以解出基變量值xi=bi(i=1，…，m)，因?yàn)橛衎i≥0，由此X=(b1，…，bm，0，…，0)T就是一個(gè)基可行解。1.3.3最優(yōu)性檢驗(yàn)與解的判別線性規(guī)劃問(wèn)題的求解結(jié)果可能出現(xiàn)唯一最優(yōu)解、無(wú)窮多最優(yōu)解、無(wú)界解和無(wú)可行解四種情況。一般情況下，經(jīng)過(guò)迭代后(1-14)式變成:將(1-15)式代入目標(biāo)函數(shù)(1-12)式得:令:則:1.3.3最優(yōu)性檢驗(yàn)與解的判別最優(yōu)解判別定理

若X=(b′1,…,b′m,0,…,0)T為一個(gè)基可行解，且對(duì)于一切j=m+1,…,n，有λj≤0

，則X為最優(yōu)解。稱λ為檢驗(yàn)數(shù).無(wú)窮多最優(yōu)解判別定理

若X=(b′1,…,b′m,0,…,0)T為一個(gè)基可行解，且對(duì)于一切j=m+1,…,n，有λj≤0

，又存在某個(gè)非基變量的檢驗(yàn)數(shù)λm+k=0，則線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解.最優(yōu)解判別定理

若X=(b′1,…,b′m,0,…,0)T為一個(gè)基可行解，有一個(gè)非基變量的檢驗(yàn)數(shù)λm+k>0

，并且對(duì)i=1,…,m，有a′i,m+k≤0

，那么該線性規(guī)劃問(wèn)題有無(wú)界解.(1)換入變量的確定由式(1-18)可以看到，當(dāng)某些λj>0時(shí)，xj增加則目標(biāo)函數(shù)值還可以增大，這時(shí)需要將某個(gè)非基變量xj換到基變量中去(稱為換入變量)。即則對(duì)應(yīng)的xk為換入變量。(2)換出變量的確定若確定非基變量Pm+t為換入變量，必然可以找到一組不全為零的數(shù)，使得1.3.4基變換給式(1-20)兩邊同乘一個(gè)正數(shù)θ，將它加到(1-19)式，得到：當(dāng)θ取適當(dāng)值時(shí)，就能得到滿足約束條件的一個(gè)可行解(非零分量的數(shù)目不大于m個(gè))，就應(yīng)當(dāng)使(xi0-θβi,m+i)中的某一個(gè)為零，并保證其余的分量為非負(fù),同時(shí)因?yàn)棣缺仨毷钦龜?shù),即則對(duì)應(yīng)的xl為換出變量。按最小比值確定θ值，稱為最小比值規(guī)則。由X(0)轉(zhuǎn)換到X(1)的各分量的轉(zhuǎn)換公式為：1.3.4基變換1.4單純形法的計(jì)算步驟初始基初始基可行解是否最優(yōu)確定入基變量確定出基變量重新確定新基可行解基變換否是停止計(jì)算確保新的基本解仍然可行使目標(biāo)函數(shù)值可能的增大額最大1.4單純形法的計(jì)算步驟第一步：求初始基可行解，列出初始單純形表。第二步：最優(yōu)性檢驗(yàn)。如果表中所有檢驗(yàn)數(shù)λj≤0，則表中的基可行解就是問(wèn)題的最優(yōu)解，計(jì)算到此結(jié)束，否則轉(zhuǎn)入下一步。第三步：進(jìn)行基變換，列出新的單純形表。(1)確定換入變量。只要有檢驗(yàn)數(shù)λj>0，對(duì)應(yīng)的變量就可以作為換入變量，即則對(duì)應(yīng)的xk為換入變量。1.4單純形法的計(jì)算步驟(2)確定換出變量。根據(jù)θ規(guī)則計(jì)算，即對(duì)應(yīng)的xl為換出變量。元素alk決定了從一個(gè)基可行解到另一個(gè)基可行解的轉(zhuǎn)移方向，稱為主元素。(3)以alk為主元素進(jìn)行迭代，把xk所對(duì)應(yīng)的列向量第四步：重復(fù)第二、三步一直到計(jì)算終止。1.4單純形法的計(jì)算步驟為了計(jì)算上的方便和規(guī)格化，對(duì)單純形法的計(jì)算設(shè)計(jì)了一種專門(mén)表格，稱為單純形表(見(jiàn)表1-4)。迭代計(jì)算中每找出一個(gè)新的基可行解時(shí)，就構(gòu)造一個(gè)新單純形表。表1-4

單純形表cj→c1…cm…cj…cnθiCBXBbx1…xm…xj…xnc1x1b11…0…a1j…a1nθ1c2x2b20…0…a2j…a2nθ2cmxmbm0…1…amj…amnθmcj-zj0…0……1.4單純形法的計(jì)算步驟

例1-10用單純形法求解例1-1的線性規(guī)劃問(wèn)題。

解

給例1-1各約束條件添加松弛變量，將問(wèn)題化為標(biāo)準(zhǔn)形式。取松弛變量x3，x4，x5為基變量，它對(duì)應(yīng)的單位矩陣為基，這樣得到初始基可行解X=(0,0,90,80,45)T，列出初始單純形表(見(jiàn)表1-5)。表1-5初始單純形表cj→54000θCBXBbx1x2x3x4x50x39013100900x480[2]1010400x5451100145cj-zj540001.4單純形法的計(jì)算步驟表中有大于零的檢驗(yàn)數(shù)，故表中的基可行解不是最優(yōu)解，因?yàn)棣?>λ2，故確定x1為換入變量。為確定換出變量，將b列數(shù)字除以x1列同行數(shù)字得表1-6初始單純形表cj→54000θCBXBbx1x2x3x4x50x35005/21-1/20205x14011/201/20800x550[1/2]0-1/2110cj-zj03/20-5/20因此x4為換出變量。2為主元素，將其加上“[]”標(biāo)記。將換入變量x1替換基變量中的x4，畫(huà)出新的單純形表(見(jiàn)表1-6)1.4單純形法的計(jì)算步驟表中仍有大于零的檢驗(yàn)數(shù)λ2，故確定x2為換入變量。為確定換出變量，將b列數(shù)字除以x2列同行數(shù)字得表1-7初始單純形表cj→54000θCBXBbx1x2x3x4x50x3250012-55x1351001-14x210010-12cj-zj000-1-3因此x5為換出變量，得到新的單純形表(見(jiàn)表1-7)表1-7中所有檢驗(yàn)數(shù)λj≤0，說(shuō)明已找到問(wèn)題的最優(yōu)解X=(35,10,25,0,0)T，目標(biāo)函數(shù)值z(mì)=215。1.4單純形法的計(jì)算步驟

例1-11假如例1-1中生產(chǎn)單位產(chǎn)品B1利潤(rùn)由原來(lái)5百元降低至4百元，其他條件不變，應(yīng)如何安排生產(chǎn)獲利最多？

解

所求問(wèn)題的標(biāo)準(zhǔn)形式為：取松弛變量x3，x4，x5為基變量，確定初始基可行解并建立初始單純形表，其整個(gè)求解過(guò)程如表1-8所示。表中所有檢驗(yàn)數(shù)λj≤0，說(shuō)明已找到問(wèn)題的最優(yōu)解X=(35,10,25,0,0)T，目標(biāo)函數(shù)值z(mì)=180。1.4單純形法的計(jì)算步驟表1-8cj→44000θCBXBbx1x2x3x4x50x39013100900x480[2]1010400x5451100145cj-zj440000x35005/21-1/20204x14011/201/20800x550[1/2]0-1/2110cj-zj020-200x325001[2]-54x1351001-14x210010-12cj-zj0000-41.4單純形法的計(jì)算步驟在最終單純形表中，除基變量的檢驗(yàn)數(shù)為零外，非基變量x4的檢驗(yàn)數(shù)也為零，這表明如果讓x4增加不會(huì)使目標(biāo)函數(shù)值有所變化，也就是說(shuō)，如果讓x4作為換入變量繼續(xù)迭代，就會(huì)得到另一個(gè)基可行解，見(jiàn)表1-9。表中所有檢驗(yàn)數(shù)λj≤0，說(shuō)明已找到問(wèn)題的最優(yōu)解X=(45/2,45/2,0,25/2,0)T，目標(biāo)函數(shù)值z(mì)=180。表1-9cj→54000θCBXBbx1x2x3x4x50x425/2001/21-5/24x145/210-1/203/24x245/2011/20-1/2cj-zj0000-41.4單純形法的計(jì)算步驟

例1-12利用單純形表法求解下列線性規(guī)劃問(wèn)題

解

取松弛變量x3，x4，x5為基變量，確定初始基可行解并建立初始單純形表，其整個(gè)求解過(guò)程如表1-10所示：在表1-10中，因?yàn)棣?>0，選x3為換入變量，但換入變量x3所在列的所有系數(shù)均小于等于零，故此問(wèn)題具有無(wú)界解。1.4單純形法的計(jì)算步驟表1-10cj-12-1000cBxBbx1x2x3x4x5x6θ0x443-111000x521-110100x64-2[1]-10014cj-zj-12-10000x48[1]0010180x56-1000112x24-21-1001cj-zj30100-2-1x181001010x5140001122x22001-1203cj-zj001-30-51.5.1人工變量法當(dāng)線性規(guī)劃的約束條件都是等式，而系數(shù)矩陣中不含有單位矩陣時(shí)，為了迅速地找到一個(gè)初始基可行解，往往通過(guò)人為添加非負(fù)變量(稱這種人為引入的變量為人工變量)來(lái)構(gòu)造一個(gè)單位基矩陣。設(shè)線性規(guī)劃問(wèn)題的約束條件是：分別給每一個(gè)約束方程加入人工變量xn+1，…，xn+m，得到：以xn+1，…，xn+m為基變量，令非基變量x1,…,xn為零，就可以得到一個(gè)初始基可行解X(0)=(0,…,0,b1,…,bm)T1.5.1人工變量法當(dāng)由于人工變量的加入，破壞了原有模型的約束條件，因此上面得到X(0)的不再是原問(wèn)題的基可行解。但如果在求解迭代過(guò)程中，人工變量能從基變量中退出，變?yōu)榉腔兞?，即xn+1=…=xn+m=0，則新問(wèn)題的基可行解就是原來(lái)線性規(guī)劃問(wèn)題的基可行解。為了實(shí)現(xiàn)這一目的，就要設(shè)法在迭代過(guò)程中讓人工變量從基變量中退出去(或其值為零)?；兞恐胁辉俸蟹橇愕娜斯ぷ兞?，這表明原問(wèn)題有解。若在最終表中當(dāng)所有的，而在其中還有某個(gè)非零人工變量，表示原問(wèn)題無(wú)可行解。1.大M法在一個(gè)線性規(guī)劃問(wèn)題的約束條件中加進(jìn)人工變量后，要求人工變量對(duì)目標(biāo)函數(shù)取值不受影響，為此取人工變量在目標(biāo)函數(shù)中的系數(shù)為－M(在最小化問(wèn)題中取M)，這里是一個(gè)很大的正數(shù)。1.5.1人工變量法

例1-13試用大M法求解下列線性規(guī)劃問(wèn)題

解

在上述問(wèn)題的約束條件中加入松弛變量x4，x5，人工變量x6，得到：利用單純形法求解，求解過(guò)程見(jiàn)表1-11。1.5.1人工變量法表1-11cj13400-McBxBbx1x2x3x4x5x6θ0x413[3]2010013/30x517013010--Mx61321100113/2cj?zj1+2M3+M4+M0001x113/312/301/300-0x51701301017/3-Mx613/30-1/3[1]-2/30113/3λj=cj?zj07/3-M/34+M-1/3-2M/3001x113/312/301/30013/20x540[2]021-324x313/30-1/31-2/301-λj=cj?zj011/307/30-4-M1x13100-1/3-1/313x2201011/2-3/24x35001-1/31/61/2λj=cj?zj000-4/3-11/63/2-M表中所有檢驗(yàn)數(shù)λj≤0，說(shuō)明已找到問(wèn)題的最優(yōu)解X=(3,2,5)T，目標(biāo)函數(shù)值z(mì)=29。2.兩階段法在兩階段法的第一階段是先求解一個(gè)目標(biāo)函數(shù)中只包含人工變量的線性規(guī)劃問(wèn)題，即令目標(biāo)函數(shù)中其他變量的系數(shù)為零，人工變量的系數(shù)取某個(gè)正的常數(shù)(一般取1)，在保持原問(wèn)題約束條件不變的情況下求這個(gè)目標(biāo)函數(shù)極小化時(shí)的解。在第一階段中，當(dāng)人工變量取值為0時(shí)，目標(biāo)函數(shù)值也為0，這時(shí)的最優(yōu)解是原線性規(guī)劃問(wèn)題的一個(gè)基可行解。如果第一階段求解結(jié)果最優(yōu)解的目標(biāo)函數(shù)值不為0，也即最優(yōu)解的基變量中含有人工變量，表明原線性規(guī)劃問(wèn)題無(wú)可行解。當(dāng)?shù)谝浑A段求解結(jié)果表明問(wèn)題有可行解時(shí)，第二階段是從第一階段的最終單純形表出發(fā)，去掉人工變量，并按問(wèn)題原來(lái)的目標(biāo)函數(shù)繼續(xù)尋找問(wèn)題的最優(yōu)解。1.5.1人工變量法1.5.1人工變量法

例1-14用兩階段法求解下列線性規(guī)劃問(wèn)題

解

在上述問(wèn)題的約束條件中加入松弛變量x4，x5，人工變量x6，給出第一階段的數(shù)學(xué)模型為利用單純形法求解，求解過(guò)程見(jiàn)表1-12。1.5.1人工變量法表1-12cj000001cBxBbx1x2x3x4x5x6θ0x413[3]2010013/30x517013010-1x61321100113/2λj=cj?zj-2-1-10000x113/312/301/300-0x51701301017/31x613/30-1/3[1]-2/30113/3λj=cj?zj01/3-12/3000x113/312/301/30013/20x540[2]021-320x313/30-1/31-2/301-λj=cj?zj000001第一階段求得的結(jié)果是z=0，得到的最優(yōu)解是X=(13/3,0,13/3,0,4,0)T1.5.1人工變量法因?yàn)槿斯ぷ兞縳6=0，所以(13/3,0,13/3,0,4)T是線性規(guī)劃問(wèn)題的基可行解。所以可進(jìn)行第二階段運(yùn)算。將第一階段的最終表中的人工變量取消，并填入原問(wèn)題的目標(biāo)函數(shù)得系數(shù)，進(jìn)行第二階段計(jì)算，見(jiàn)表1-13。表1-13cj13400cBxBbx1x2x3x4x5θ1x113/312/301/3013/20x540[2]02124x313/30-1/31-2/30-λj=cj?zj011/307/301x13100-1/3-1/33x2201011/24x35001-1/31/6λj=cj?zj000-4/3-11/6表中所有檢驗(yàn)數(shù)λj≤0，說(shuō)明已找到問(wèn)題的最優(yōu)解X=(3,2,5)T，目標(biāo)函數(shù)值z(mì)=29。1.5.2退化單純形法計(jì)算中用θ規(guī)則確定換出變量時(shí)，有時(shí)存在兩個(gè)以上相同的最小比值，這樣在下一次迭代中就有一個(gè)或者幾個(gè)基變量等于零，這就出現(xiàn)退化解。這時(shí)換出變量xi=0，迭代后目標(biāo)函數(shù)值不變。這時(shí)不同基表示為同一頂點(diǎn)。盡管計(jì)算過(guò)程的循環(huán)現(xiàn)象很少出現(xiàn)，但還是有可能的。為了解決這問(wèn)題，先后有人提出了“攝動(dòng)法”，“字典序法”。1974年勃蘭特提出一種簡(jiǎn)便的規(guī)則，簡(jiǎn)稱勃蘭特規(guī)則：(1)選取cj-zj>0中下標(biāo)最小的非基變量xk為換入變量。(2)當(dāng)按θ規(guī)則計(jì)算存在兩個(gè)和兩個(gè)以上最小比值時(shí)，選取下標(biāo)最小的基變量為換出變量。按勃蘭特規(guī)劃計(jì)算時(shí)，一定能避免出現(xiàn)循環(huán)。1.5.3單純形法計(jì)算的矩陣表示用矩陣形式描述線性規(guī)劃的標(biāo)準(zhǔn)形式為：初始單純形表可見(jiàn)表1-14：表1-14初始解非基變量基變量bBNIcj-zjλN0,…,0基變換后的新單純形表見(jiàn)表1-15：表1-15基可行解基變量非基變量b'IN'B-1cj-zj0,…,0λ'N-y1,…,-ym

例1-16某飼料廠用原料A、B、C加工生產(chǎn)三種不同的飼料甲、乙、丙。已知各種飼料中原料A、B、C的含量，原料成本，各種原料的限制用量，三種飼料的單位加工費(fèi)及其售價(jià)如表1-19所示。該廠每月生產(chǎn)三種飼料各多少，可使飼料廠獲利最大。。

1.6應(yīng)用舉例表1-19甲乙丙原料成本（元/kg）每天限制用量（kg）A≥50%≥25%65100B≤25%≤50%25100C3560售價(jià)(元/kg)5035251.6應(yīng)用舉例

解

(1)用i

=1,2,3分別代表原料A、B、C，用j=1,2,3分別代表甲、乙、丙三種不同的飼料。設(shè)xij為生產(chǎn)第j種飼料使用的第i種原料。(2)目標(biāo)函數(shù)為(3)約束條件為1.6應(yīng)用舉例所以問(wèn)題的數(shù)學(xué)