運(yùn)籌學(xué)第4講 線(xiàn)性規(guī)劃3

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

（OperationsResearch）上海海事大學(xué)20131009任課教師：鄧偉郵箱：dengwei1663@單純形表總結(jié)

注：在單純形表中，檢驗(yàn)數(shù)的形式為

其中，對(duì)于基變量來(lái)說(shuō)，檢驗(yàn)數(shù)而(此因：基變量的系數(shù)矩陣為一個(gè)單位陣，當(dāng)前僅當(dāng)

)因此線(xiàn)性規(guī)劃所有變量的檢驗(yàn)數(shù)可統(tǒng)一為單純形表總結(jié)在初始的單純形表中，在常數(shù)項(xiàng)b的下方添加上當(dāng)前解（初始基本可行解）對(duì)應(yīng)的目標(biāo)函數(shù)值的相反數(shù)，這樣，經(jīng)過(guò)一系列的迭代，在最優(yōu)單純形表中，這個(gè)相反數(shù)經(jīng)過(guò)迭代后為最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值的相反數(shù)。單純形表總結(jié)cj02-210θCBXBbx1x2x3x4x50x15111000x4601-4100x52402601cj-zj-Z1=-601200初始目標(biāo)函數(shù)值的相反數(shù)人工變量法在應(yīng)用單純形法確定初始基本可行解X1時(shí)，如果約束矩陣中不含有單位陣，可以采用人工變量進(jìn)行處理。人工變量的引入在約束矩陣中不含單位陣時(shí)，一般要在模型中人為地添加一些非負(fù)變量，稱(chēng)為人工變量，構(gòu)造一個(gè)新的線(xiàn)性規(guī)劃問(wèn)題，使新問(wèn)題的約束矩陣中含有單位陣，從而可以方便地確定新問(wèn)題的一個(gè)基本可行解然后再根據(jù)新問(wèn)題與原問(wèn)題的解的關(guān)系，給出原問(wèn)題的解的結(jié)果。

人工變量法例5.1對(duì)于下面的模型

在加入人工變量之后，就得到新問(wèn)題的約束條件。

此約束矩陣中含有單位矩陣，可以取變量為基變量，確定新問(wèn)題的初始基本可行解。人工變量法下面介紹兩種人工變量方法。大M法引入人工變量的目的是為了使約束系數(shù)矩陣中含有單位矩陣，由于此模型已有x4的系數(shù)列向量為單位向量，只需要再有兩個(gè)單位向量就可以得到單位矩陣，所以只在第1個(gè)和第2個(gè)約束方程中添加兩個(gè)人工變量即可。添人工變量的原則是，只要在約束矩陣中出現(xiàn)一個(gè)單位矩陣即可。構(gòu)造上面模型對(duì)應(yīng)的“大M規(guī)劃”人工變量法其中x5,x6為人工變量，目標(biāo)函數(shù)中人工變量的負(fù)系數(shù)M是非常大的正數(shù)，大M法即因此得名。下面分析構(gòu)造大M規(guī)劃的原理根據(jù)上述大M規(guī)劃的形式，可以得到大M規(guī)劃的一個(gè)初始基本可行解

(x1,x2,……，x6)T=(0,0,0,26,15,20)T由于x5,x6>0，所以(x1,x2,x3,x4)T=(0,0,0,26)T不是原規(guī)劃問(wèn)題的可行解。顯然，為了使大M規(guī)劃的基本可行解，對(duì)于原規(guī)劃從不可行變?yōu)榭尚?，需要借助于目?biāo)函數(shù)使人工變量的值減小到零。人工變量法

由于在大M規(guī)劃的目標(biāo)函數(shù)中，M為很大的數(shù)，所以在原規(guī)劃存在可行解的情況下，只要人工變量不為零，目標(biāo)函數(shù)就不可能實(shí)現(xiàn)極大化。可以說(shuō)，大M對(duì)人工變量具有一種懲罰作用，一旦人工變量為零，這種懲罰作用就消失了，是大M使得人工變量趨于零的。由于非基變量是取零值的，所以M的作用反映在單純形法的計(jì)算中，就是將人工變量從基本可行解的基變量中替換出去，使它們成為非基變量。人工變量法

關(guān)于大M法的幾個(gè)結(jié)論：(1)大M規(guī)劃有最優(yōu)解，并且在最優(yōu)解中人工變量皆取零值，則在這個(gè)最優(yōu)解中去掉人工變量的部分后，就是原規(guī)劃的最優(yōu)解。(2)大M規(guī)劃有最優(yōu)解，但在最優(yōu)解中人工變量不全為零，則原規(guī)劃沒(méi)有最優(yōu)解。(3)大M規(guī)劃沒(méi)有最優(yōu)解，則原規(guī)劃也沒(méi)有最優(yōu)解。人工變量法

用大M法求解線(xiàn)性規(guī)劃模型解加入人工變量x5,x6后，得到大M規(guī)劃模型。取x4,x5,x6為基變量，將目標(biāo)函數(shù)化為典式形式。建立大M規(guī)劃的單純形表，進(jìn)行計(jì)算，計(jì)算過(guò)程如下面的單純形表。人工變量法人工變量法由于M為很大的數(shù)，所以最后表中所有檢驗(yàn)數(shù)均已小于等于零，因此得到新規(guī)劃的最優(yōu)解為(x1,x2,……，x6)T=(25/3,10/3,0,11,0,0)T。由于人工變量已取零值，根據(jù)大M法的結(jié)論，得到原規(guī)劃問(wèn)題的最優(yōu)解為(x1,x2,x3,x4)T=(25/3,10/3,0,11)T

，最優(yōu)目標(biāo)函數(shù)值為112/3。

人工變量法例5.2

用大M法解下面模型先引入松弛變量x3,x4化為標(biāo)準(zhǔn)形式人工變量法

再引入人工變量x5,構(gòu)造大M規(guī)劃模型。取x3,x5為基變量，由約束條件解出代入目標(biāo)函數(shù)中，得到典式形式人工變量法建立單純形表進(jìn)行求解：在上面的最優(yōu)單純形表中，檢驗(yàn)數(shù)全部小于等于零，已得到大M規(guī)劃的最優(yōu)解。但是在最優(yōu)解中人工變量x5=3不為零，所以原規(guī)劃沒(méi)有可行解。人工變量法解引入人工變量x5,x6構(gòu)造大M規(guī)劃

例5.3用大M法求解下面線(xiàn)性規(guī)劃問(wèn)題：由約束條件解出人工變量法代入目標(biāo)函數(shù)，得到目標(biāo)的典式形式構(gòu)造單純形表進(jìn)行計(jì)算，得到人工變量法表中檢驗(yàn)數(shù)，而皆小于等于零，故大M規(guī)劃沒(méi)有最優(yōu)解。由大M法的結(jié)論可知，原規(guī)劃也沒(méi)有最優(yōu)解。人工變量法在機(jī)器計(jì)算時(shí)，大M法有時(shí)出現(xiàn)變量字長(zhǎng)限制的問(wèn)題。兩階段法是另一種人工變量法，它是分兩階段進(jìn)行求解的。兩階段法以下針對(duì)大M法中的模型進(jìn)行討論。1.引入人工變量構(gòu)造第一階段規(guī)劃，也稱(chēng)輔助規(guī)劃，求原規(guī)劃的一個(gè)基本可行解。輔助規(guī)劃的目標(biāo)函數(shù)是求所有人工變量的和的最小值。由于人工變量非負(fù)，因此，使人工變量之和趨于零，就是使每個(gè)人工變量趨于零。人工變量法關(guān)于第一階段規(guī)劃(輔助規(guī)劃)有以下結(jié)論：在第一階段規(guī)劃的最優(yōu)解中，如果人工變量不為零，則原規(guī)劃沒(méi)有可行解，計(jì)算停止；如果人工變量全為零，并且人工變量均為非基變量，則在第一階段規(guī)劃的最優(yōu)解中，去掉人工變量部分之后，就得到原規(guī)劃的一個(gè)基本可行解，繼續(xù)第二階段的計(jì)算。人工變量法經(jīng)過(guò)第一階段的求解，得到原規(guī)劃的一個(gè)基本可行解之后，要進(jìn)行第二階段的求解，即求解原規(guī)劃。求解原規(guī)劃不必另用新表，只需要在第一階段規(guī)劃的最優(yōu)單純形表中，將檢驗(yàn)數(shù)行數(shù)字去掉，并將原目標(biāo)函數(shù)用非基變量表示，得到檢驗(yàn)數(shù)后填入表中。另外，由于人工變量已不起作用，所以將人工變量對(duì)應(yīng)的兩列元素去掉，經(jīng)過(guò)這些調(diào)整之后，繼續(xù)按照單純形法步驟求解，直至得到最優(yōu)解。人工變量法例5.4用兩階段方法求解下面的線(xiàn)性規(guī)劃問(wèn)題。解求解第一階段規(guī)劃：上面模型的第一階段規(guī)劃為，人工變量法由約束條件解出建立單純形表進(jìn)行計(jì)算，得到最優(yōu)單純形表，從表中可以看出，檢驗(yàn)數(shù)已全部小于等于零，得到第一階段規(guī)劃的最優(yōu)解(0,15/7,25/7,52/7,0,0)T。由于最優(yōu)解中人工變量皆取零值，故得到原規(guī)劃的一個(gè)基本可行解(0,15/7,25/7,52/7)T。代入目標(biāo)函數(shù)w中，得到化為求極大人工變量法求解第二階段規(guī)劃：在最優(yōu)單純形表中，去掉人工變量部分的所有元素，并將檢驗(yàn)數(shù)行換成原規(guī)劃相應(yīng)于基本可行解

(0,15/7,25/7,52/7)T的檢驗(yàn)數(shù)。由于此時(shí)x2,x3,x4為基變量，由最優(yōu)單純形表可以得到：人工變量法人工變量法代入原規(guī)劃的目標(biāo)函數(shù)Z，得到將此檢驗(yàn)數(shù)代入表中進(jìn)行計(jì)算，去掉x5,x6兩列元素，得到檢驗(yàn)數(shù)全部非正，得到原規(guī)劃的最優(yōu)解(25/3,10/3,0,11)T,最優(yōu)值112/3。人工變量法人工變量法例5.5用單純形法求解下面線(xiàn)性規(guī)劃問(wèn)題解引入松弛變量x3,x4化為標(biāo)準(zhǔn)形，引入人工變量x5,x6求解第一階段規(guī)劃人工變量法將目標(biāo)函數(shù)化為求極大，并用非基變量表示建立單純形表進(jìn)行計(jì)算由這個(gè)最優(yōu)單純形表可以看出第一階段的最優(yōu)解為(0,1/2,0,0,0,3/2)T，其中人工變量x6=3/2不為零，所以原規(guī)劃沒(méi)有可行解。多個(gè)最優(yōu)解的討論關(guān)于多個(gè)最優(yōu)解的討論：在圖解法中已經(jīng)看到，一個(gè)線(xiàn)性規(guī)劃問(wèn)題可能存在多個(gè)最優(yōu)解，這里討論如何在單純形方法中識(shí)別一個(gè)模型是否有多個(gè)最優(yōu)解，在存在的情況下，如何將這些最優(yōu)解求出。在單純形表中，存在第二個(gè)最優(yōu)解的判別方法：如果在最優(yōu)單純形表中，除去基變量對(duì)應(yīng)的檢驗(yàn)數(shù)為零外，還存在非基變量xk對(duì)應(yīng)的檢驗(yàn)數(shù)也為零，并且xk所在列的各個(gè)系數(shù)aik不全小于等于零，則此模型存在第二個(gè)最優(yōu)解。事實(shí)上，這是因?yàn)槿绻麑⑦@個(gè)檢驗(yàn)數(shù)為零的非基變量作為進(jìn)基變量進(jìn)行迭代計(jì)算，則原最優(yōu)解將發(fā)生變化，得到一新解。但是，由于這個(gè)進(jìn)基變量的檢驗(yàn)數(shù)已經(jīng)為零，所以檢驗(yàn)數(shù)行并不需要再做初等變換，因此得到的新解與原最優(yōu)解取相同的函數(shù)值，所以新解也是最優(yōu)解。多個(gè)最優(yōu)解的討論在得到第二個(gè)最優(yōu)解后，可以通過(guò)下面方法得到無(wú)窮多個(gè)最優(yōu)解。設(shè)X1,X2為兩個(gè)最優(yōu)解，則仍為最優(yōu)解。當(dāng)取[0,1]區(qū)間上不同值時(shí)，對(duì)應(yīng)著不同的X0，因此可以得到無(wú)窮多個(gè)最優(yōu)解。注：記Z*為最優(yōu)值，X1,X2為最優(yōu)解，則Z*=CX1=CX2，而又可證明X0為可行解，所以X0為最優(yōu)解。多個(gè)最優(yōu)解的討論例5.6求出下面線(xiàn)性規(guī)劃問(wèn)題的多個(gè)最優(yōu)解：在最優(yōu)單純形表中，得到第一個(gè)最優(yōu)解X1=(0,2,16,4,0,0)T，最優(yōu)值為128.從最優(yōu)單純形表可以看出，非基變量x6的檢驗(yàn)數(shù)為零，并且，因此將x6引入基變量，求解第二個(gè)最優(yōu)解。解

加入松弛變量x4,x5,x6化為標(biāo)準(zhǔn)形，求第一個(gè)最優(yōu)解：多個(gè)最優(yōu)解的討論多個(gè)最優(yōu)解的討論第二個(gè)最優(yōu)解為X2=(0,4,16,0,0,2)T，因此原規(guī)劃的全部解可以表示為多個(gè)最優(yōu)解的討論第二個(gè)最優(yōu)解為X2=(0,4,16,0,0,2)T，因此原規(guī)劃的全部解可以表示為退化盡管計(jì)算過(guò)程的循環(huán)現(xiàn)象極少出現(xiàn)，但還是有可能的。先后有人提出了“攝動(dòng)法”、“字典序法”。1974年Bland提出一種簡(jiǎn)便的規(guī)則（Bland規(guī)則）：如何解決這個(gè)問(wèn)題？（1）選擇中下標(biāo)最小的非基變量xk為換入變量，即（2）當(dāng)按最小比值規(guī)則計(jì)算存在兩個(gè)以上的最小比值時(shí)，選取下標(biāo)最小的基變量為換入變量。當(dāng)按Bland規(guī)則計(jì)