線性規(guī)劃及其發(fā)展概況

線性規(guī)劃及其發(fā)展概況本文初步闡述了線性規(guī)劃產(chǎn)生的歷史、社會(huì)背景,發(fā)展概述,以及線性規(guī)劃在現(xiàn)實(shí)生活中的廣泛應(yīng)用及意義．以科學(xué)發(fā)展觀的立場(chǎng)看線性規(guī)劃在全球化過(guò)程中的巨大推動(dòng)作用,特別是在合理配置資源方面所發(fā)揮的作用．從如何建立線性規(guī)劃問(wèn)題的數(shù)學(xué)模型出發(fā),進(jìn)而對(duì)線性規(guī)劃有個(gè)理性的、深層次的認(rèn)識(shí)．分析總結(jié)了線性規(guī)劃問(wèn)題中的幾種基本解法的優(yōu)、缺點(diǎn),以及提出了新的求解線性規(guī)劃問(wèn)題的方法．關(guān)鍵詞：線性規(guī)劃；數(shù)學(xué)模型；解法前言線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)基本的,也是最成熟的分支．為了解決二次世界大戰(zhàn)中的后勤供應(yīng)問(wèn)題,早在20世紀(jì)30年代末期康托洛維奇和希奇柯克等在生產(chǎn)的組織和運(yùn)輸問(wèn)題等方面就開(kāi)始研究應(yīng)用這一數(shù)學(xué)方法．10多年后Dantzing等人提出的單純形方法給線性規(guī)劃這一數(shù)學(xué)方法的成熟與發(fā)展奠定了堅(jiān)實(shí)的理論基礎(chǔ)．任何學(xué)科都是一個(gè)逐步完善的過(guò)程,線性規(guī)劃也不例外,對(duì)于求解線性規(guī)劃問(wèn)題,也是一步一步趨于完善的．在求解線性規(guī)劃問(wèn)題時(shí),各種求解方法也有其優(yōu)、缺點(diǎn)．2線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型在明白線性規(guī)劃問(wèn)題的概念之前,我們首先要明白什么是規(guī)劃．通俗地講,規(guī)劃是對(duì)一種特定的活動(dòng)（過(guò)程）可能產(chǎn)生的各種結(jié)果作出分析與評(píng)價(jià),并從中找出那些對(duì)當(dāng)事人（系統(tǒng)）最有利的結(jié)果,并了解應(yīng)該限制（減少）哪些活動(dòng)要素（單元）,加強(qiáng)（增加）那些活動(dòng)要素（單元）,哪些資源顯得剩余,哪些資源顯得不足．規(guī)劃的過(guò)程實(shí)質(zhì)上就是為了實(shí)現(xiàn)某個(gè)特定目標(biāo)對(duì)特定事物的發(fā)展進(jìn)程進(jìn)行優(yōu)化分析的過(guò)程．小到一個(gè)人、一個(gè)家庭、一個(gè)課程組,大到一個(gè)企業(yè)、一個(gè)科研院所,甚至一個(gè)國(guó)家,只要是一個(gè)利益主體,要想在推進(jìn)事物的過(guò)程中獲得最多的利益或最優(yōu)的結(jié)果就都要進(jìn)行科學(xué)的運(yùn)籌學(xué)的運(yùn)籌和規(guī)劃．比如說(shuō),在武器裝備與彈藥條件、作戰(zhàn)樣式一定的前提下,如何安排陣地或戰(zhàn)法才能獲得最好的攻擊（防御）效果；在機(jī)器設(shè)備與原材料、生產(chǎn)方式一定的前提下,如何安排生產(chǎn)才能獲得最大利潤(rùn)？可能獲得的最大利潤(rùn)是多少？；在有限的精力、一定的課程設(shè)置以及學(xué)習(xí)方式不變的條件下,如何分配時(shí)間,才能獲得盡可能好的學(xué)習(xí)效果、拿到更多的學(xué)分？；在土地資源和種植計(jì)劃,才能獲得更多的經(jīng)濟(jì)效益？如此等等,各行各業(yè)實(shí)際工作中遇到的類(lèi)似問(wèn)題,都可以用線性規(guī)劃的方法來(lái)解決．線性規(guī)劃是運(yùn)籌學(xué)中數(shù)學(xué)規(guī)劃（即最優(yōu)化理論）的一個(gè)發(fā)展最早的,也是最成熟的分支．有一類(lèi)實(shí)際問(wèn)題需要將某些對(duì)象最大化（如利潤(rùn)、安全等）或最小化（如支出、風(fēng)險(xiǎn)等）,數(shù)學(xué)規(guī)劃就是為這類(lèi)實(shí)際問(wèn)題提供數(shù)學(xué)模型的一種方法,具體地說(shuō),數(shù)學(xué)規(guī)劃尋求函數(shù)在規(guī)定必須滿足一定條件時(shí)的極?。ɑ驑O大）值,稱(chēng)為“目標(biāo)函數(shù)”,必須滿足的條件稱(chēng)為“約束條件”,如果目標(biāo)函數(shù)和約束條件都是線性的,就叫線性規(guī)劃．即線性規(guī)劃實(shí)質(zhì)上是研究在一組線性約束條件下,把一個(gè)線性函數(shù)極小化或極大值的問(wèn)題．下面我們來(lái)討論一個(gè)線性規(guī)劃問(wèn)題的引例,由此得到線性規(guī)劃的數(shù)學(xué)模型：例2.1（線性規(guī)劃問(wèn)題引例）某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品,要用Ａ、Ｂ、Ｃ３種不同的原料．從工藝資料知道：每生產(chǎn)１噸甲產(chǎn)品需耗用３種原料分別為１,１,０單位,生產(chǎn)１噸乙產(chǎn)品,需耗用３種原料分別為１、２、１單位,每天原料供應(yīng)的能力分別為６、８、３單位．又知道每生產(chǎn)１噸甲產(chǎn)品,企業(yè)利潤(rùn)收入為３００元,每生產(chǎn)１噸乙產(chǎn)品,企業(yè)利潤(rùn)收入為４００元．上述資料見(jiàn)表１表１ABC單位耗用（百元）甲１１０３乙１２１４供應(yīng)量６８３問(wèn)企業(yè)如何安排生產(chǎn)機(jī)劃使一天的總利潤(rùn)最大？這樣一個(gè)簡(jiǎn)單的生產(chǎn)計(jì)劃安排問(wèn)題,就屬于我們所討論為線性規(guī)劃范圍．為了準(zhǔn)確地回答上述問(wèn)題,我們用數(shù)學(xué)語(yǔ)言描述它這個(gè)過(guò)程稱(chēng)為建立其數(shù)學(xué)模型,簡(jiǎn)稱(chēng)建模．建模過(guò)程如下：①假設(shè)所求甲、乙產(chǎn)品每天生產(chǎn)的數(shù)量分別為、稱(chēng)為決策變量,簡(jiǎn)稱(chēng)變量．因?yàn)楫a(chǎn)量一般是一個(gè)非負(fù)數(shù),所以有、≥０,稱(chēng)為非負(fù)約束．②假設(shè)該企業(yè)生產(chǎn)、的甲、乙產(chǎn)品后獲得總利潤(rùn)值為Ｚ,顯然．我們希望總利潤(rùn)Ｚ能達(dá)到最大,這個(gè)關(guān)系可以用下面的公式表達(dá)：③給出的規(guī)劃問(wèn)題往往講明了一些限制條件．如本例中講到的３種原料每天的耗用料分別不能超過(guò)每天的供應(yīng)量６、８、３,這樣就約束了產(chǎn)品的生產(chǎn)量、．生產(chǎn)、的甲、乙產(chǎn)品其原料約束如下：耗用量供應(yīng)量A原料B原料C原料我們把上述所有數(shù)學(xué)公式歸納如下：s.t.(1)（１）式就是引例的線性規(guī)劃模型．線性規(guī)劃模型的一般形式及標(biāo)準(zhǔn)形式由（１）式可以看出線性規(guī)劃模型是由三部分組成的：①一組決策變量．②一個(gè)線性目標(biāo)函數(shù)．③一個(gè)線性約束方程．上述三點(diǎn)又稱(chēng)為線性規(guī)劃問(wèn)題的三要素．在（１）式中目標(biāo)函數(shù)是求最大值（maximum）,而有些問(wèn)題可能希望目標(biāo)函數(shù)最?。╩inimum）,例如若目標(biāo)函數(shù)表示生產(chǎn)費(fèi)用,則希望生產(chǎn)費(fèi)用最小,無(wú)論最大還是最小總之希望目標(biāo)函數(shù)達(dá)到最優(yōu)．在（１）式中約束條件的約束符號(hào)均為“”,但實(shí)際問(wèn)題中有許多約束條件的約束符號(hào)是“”或“”或“＝”,因此我們一般設(shè)有n個(gè)決策變量,m個(gè)約束方程,則線性規(guī)劃問(wèn)題的一般表達(dá)形式為：max（或min）也可記為max(或min)s.t.線性規(guī)劃問(wèn)題的數(shù)學(xué)模型有許多種,我們希望能把各種不同形式的線性規(guī)劃問(wèn)題的數(shù)學(xué)模型化為一種統(tǒng)一的標(biāo)準(zhǔn)形式,這樣只要對(duì)標(biāo)準(zhǔn)形式找出一種解法,就可以解決其余不同形式的規(guī)劃問(wèn)題了．線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式：mins.t.此標(biāo)準(zhǔn)形式可以寫(xiě)成矩陣的形式即：min,s.t.其中A=,b=X=b,0是n維零向量,表示.3線性規(guī)劃問(wèn)題的基本解法３.1圖解法例３.1求解線性規(guī)劃問(wèn)題：s.t.解：作出可行域K的圖形,如圖１－１所示由于目標(biāo)函數(shù)的等值線族恰與K的BC邊平行,故沿正法向量的方向平推等值線時(shí),最后與邊重合．因此BC邊上每一點(diǎn)都使目標(biāo)函數(shù)取最大值．即知問(wèn)題有無(wú)窮多個(gè)最優(yōu)解．最優(yōu)值為.由上例我們可以得出圖解法的基本步驟：第一步：畫(huà)出可行解域．第二步：畫(huà)出等值雙曲線．第三步：求最優(yōu)解．注意：目標(biāo)函數(shù)值的大小與“等值線”的移動(dòng)關(guān)系遵照如下法則：假設(shè)目標(biāo)函數(shù)為我們作該直線的法矢量以(則當(dāng)“等值線”沿的正方向平行移動(dòng)時(shí),值就增加,沿著的負(fù)方向平行移動(dòng)時(shí),就遞減．圖解法它具有直觀、簡(jiǎn)便的特點(diǎn),同時(shí)它還有助于理解４個(gè)及４個(gè)以上決策變量線性規(guī)劃問(wèn)題的最優(yōu)解的意義,而且,在當(dāng)今的高中數(shù)學(xué)教學(xué)中占了相當(dāng)?shù)谋戎?其優(yōu)化思想也作為重點(diǎn)去培養(yǎng)現(xiàn)代高中生的一種數(shù)學(xué)思想．但遺憾的是它一般只適合解含有三個(gè)或三個(gè)以下變量的線性規(guī)劃問(wèn)題,在解含有超過(guò)三個(gè)決策變量的線性規(guī)劃問(wèn)題,一般不能用圖解法求解,而需要用代數(shù)的方法求解,常用的方法是單純形法．3.2單純形法單純形法是求解線性規(guī)劃問(wèn)題的一般方法,原則上可適用任何線性規(guī)劃問(wèn)題,基本思想是：針對(duì)頂點(diǎn)可行解,建立一個(gè)便于檢驗(yàn)最優(yōu)性的準(zhǔn)則,然后對(duì)可行域的有限個(gè)頂點(diǎn),按照一定的法則依次加以檢驗(yàn),從中挑出最優(yōu)解．3.2.1基B的典式的引入設(shè)為L(zhǎng)P的一個(gè)基解,為敘述方便起見(jiàn),不妨設(shè)對(duì)應(yīng)基陣B=即為基變量,是非基變量．記,,N=.從而A=(B,N),相應(yīng)地分劃則線性規(guī)劃問(wèn)題可換成如下等價(jià)形式：（3.1）或?qū)憺椋?.2）（3.1）或者（3.2）的表達(dá)形式稱(chēng)為L(zhǎng)P對(duì)應(yīng)于基B的典式．對(duì)于一般的基B,其典式若用矩陣表示,仍具（3.1）的形式．若用代數(shù)式表達(dá),則應(yīng)（3.2）稍加改變．如設(shè)基記基變量的下表集為S,記非基變量的下標(biāo)集為R,即則LP對(duì)應(yīng)基B的典式可寫(xiě)為其中上述諸稱(chēng)為基B的（或者說(shuō)基解的）檢驗(yàn)數(shù),或者更清楚地說(shuō),是基B的對(duì)應(yīng)于非基變量的檢驗(yàn)數(shù)．等于目標(biāo)函數(shù)的非基賓量表達(dá)式中的系數(shù)反號(hào)．對(duì)應(yīng)于基變量的檢驗(yàn)數(shù)視為零．于是全體檢驗(yàn)數(shù)組成如下向量：＝亦即其中對(duì)應(yīng)于基變量的檢驗(yàn)數(shù)對(duì)應(yīng)于非基變量的檢驗(yàn)數(shù)亦即這一組檢驗(yàn)數(shù)即可用來(lái)判別一個(gè)基可行解是否為最優(yōu)解,因?yàn)橛腥缦陆Y(jié)論：3.2.2單純形法定理3.1對(duì)于LP的一個(gè)基B,若,且則對(duì)應(yīng)于B的基解便是LP的最優(yōu)解．定理3.2若基可行解所對(duì)應(yīng)的典式（4.3）～(4.5)中,有某個(gè)檢驗(yàn)數(shù),且相應(yīng)地有則LP無(wú)最優(yōu)解（此時(shí)目標(biāo)函數(shù)在可行域上無(wú)下界）．定理3.3若基可行解所對(duì)應(yīng)的典式（4.3）～(4.5)中,有某個(gè)檢驗(yàn)數(shù),而中至少有一個(gè)大于零,并且,則必存在另一基可行解,其對(duì)應(yīng)目標(biāo)函數(shù)值比小．綜合定理3.1～3.3,便可得出求解線性規(guī)劃問(wèn)題LP的一種方法,稱(chēng)之為單純形法,其基本過(guò)程是：如果已知的LP一個(gè)基可行解,首先求出LP相應(yīng)于的典式,然后檢查檢驗(yàn)數(shù)是否全部為正．若是,則根據(jù)定理3.1,已為最優(yōu)解；若不是,看定理3.2的條件是否成立．若成立,則LP無(wú)最優(yōu)解；若不成立,則按定理3.3,構(gòu)造一個(gè)新的基可行解．再對(duì)重復(fù)上述做法．如此反復(fù)進(jìn)行．若LP是非退化的,根據(jù)定理3.3,每次得出的新基可行解使目標(biāo)函數(shù)值嚴(yán)格下降,因此已出現(xiàn)過(guò)的基可行解不可能重復(fù)出現(xiàn)．又由于基可行解的個(gè)數(shù)有限,所以經(jīng)有限次反復(fù),必能得出LP的最優(yōu)解（即最優(yōu)基可行解）,或判斷LP無(wú)最優(yōu)解．當(dāng)然單純形法只能解決非退化的線性問(wèn)題,關(guān)于退化的情形,則應(yīng)以另一種方法求解．例3.2求解線性規(guī)劃問(wèn)題：解：取顯見(jiàn)是一個(gè)基．為得出對(duì)應(yīng)的典式,將第三個(gè)約束方程的（－２）倍加到第一個(gè)約束方程得用它代替第一個(gè)約束方程,然后,從第一、二方程分別解出代入目標(biāo)函數(shù)表達(dá)式；或者,將第一個(gè)方程的（－１）倍和第二個(gè)方程的（－１）倍加到表達(dá)式兩端,即可得出基對(duì)應(yīng)的典式：顯見(jiàn)是可行基,其對(duì)應(yīng)基可行解為由對(duì)應(yīng)于的檢驗(yàn)數(shù)可知,應(yīng)取為進(jìn)基變量．這時(shí)即知故應(yīng)取為離基變量．得新基為得出對(duì)應(yīng)的典式,將對(duì)應(yīng)典式中的第二個(gè)約束方程的２倍加到第一個(gè)約束方程上；將第二個(gè)方程的（－１）倍加到第三個(gè)約束方程上；將第二個(gè)方程的１倍加到的兩端,即得對(duì)應(yīng)的典式：對(duì)應(yīng)的基可行解為由可知,應(yīng)取為進(jìn)基變量.由,可知,故應(yīng)取為離基變量.得新基.為得出對(duì)應(yīng)的典式,將對(duì)應(yīng)的典式中的第三個(gè)約束方程兩端同除以3；然后,用它的3倍和2倍分別加到第一個(gè)和第二個(gè)約束方程；用它的1倍加到的兩端.即得對(duì)應(yīng)的典式:,,,現(xiàn)在非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)即知檢驗(yàn)數(shù)全部非正．因此,對(duì)應(yīng)的基可行解便是問(wèn)題的最優(yōu)解．目標(biāo)函數(shù)的最小值為.單純行法是一種即簡(jiǎn)便又有效,也適合于用計(jì)算機(jī)通用軟件求解的一種通用方法．但是按上述單純行法求解時(shí),每次迭代單純行表上的所有數(shù)據(jù)都參加運(yùn)算．實(shí)際上,其中有些運(yùn)算是不必要的,如果直接按這種方法編制程序上計(jì)算機(jī)解題,會(huì)在存儲(chǔ)量和計(jì)算方面造成浪費(fèi)．單純形法是從某一規(guī)范型出發(fā)的,若標(biāo)準(zhǔn)形不是規(guī)范型,則不能直接用單純形法求解．因?yàn)?對(duì)于不是規(guī)范型的標(biāo)準(zhǔn)型,我們看不出取哪組變量為基變量,可將標(biāo)準(zhǔn)型變換成規(guī)范型,也就是說(shuō),我門(mén)看不出取哪組變量為基變量,可得基可行解（因?yàn)閷?duì)規(guī)范型而言,只要取單位矩陣所對(duì)應(yīng)的變量為基變量,就可得一基可行解）．但經(jīng)初等行變換可將標(biāo)準(zhǔn)形化為規(guī)范形,也就是人為的添加一些變量,使其標(biāo)準(zhǔn)型人為的變成規(guī)范型．這就是人工變量法．3.3人工變量法因?yàn)閱渭冃伟l(fā)要從某一規(guī)范形出發(fā),對(duì)于不是規(guī)范型的標(biāo)準(zhǔn)型,用單純形法求解的辦法就是添加人工變量,使標(biāo)準(zhǔn)型人為的變成規(guī)范型形式．由于人工變量是人為地添加到原約束方程的虛擬變量,若人工變量不等于０,則不是原約束方程的可行解．有因?yàn)閱渭冃畏ㄊ谴_定入基變量和出基變量的過(guò)程,只要人工變量由基變量逐個(gè)替換出變?yōu)榉腔兞?基變量中不再含有人工變量,這時(shí)就可得到不含有人工變量的基可行解．具體說(shuō)來(lái),人工變量法有兩種：兩階段法和大M法．3.3.1兩階段法在通過(guò)添加人工變量后,把線性規(guī)劃問(wèn)題化為規(guī)范型,在求解過(guò)程中,如果人工變量不等于０,就不是原線性規(guī)劃問(wèn)題的可行解．因此,用單純形法求解帶有人工變量的線性規(guī)劃問(wèn)題,總是希望人工變量等于０．也就是說(shuō)希望人工變量都變成非基變量．其步驟是：第一階段：希望人工變量等于０,故此構(gòu)造僅含有人工變量的目標(biāo)函數(shù)要求實(shí)現(xiàn)最小化,然后用單純形法求解其模型,若得到目標(biāo)函數(shù)為０,則此時(shí)說(shuō)明,所添加的人工變量都為０,原問(wèn)題存在可行解,可以進(jìn)行第二階段計(jì)算,否則原問(wèn)題無(wú)可行解,應(yīng)停止計(jì)算．第二階段：將第一階段計(jì)算得到的最終表,去掉人工變量,將目標(biāo)函數(shù)換回原問(wèn)題的目標(biāo)函數(shù),作為第二階段計(jì)算,繼續(xù)單純形法,直至求到最優(yōu)解．3.3.2大M法大M法的思路與兩階段法基本一致,也是在添加人工變量之后用單純形求解時(shí)希望人工變量等于０（即希望人工變量全部為非基變量）．為此需要人工變量對(duì)目標(biāo)函數(shù)產(chǎn)生影響,一般設(shè)定人工變量在目標(biāo)函數(shù)中的系數(shù)為M（對(duì)于目標(biāo)為min型）或者-M（對(duì)于目標(biāo)為max型）,M假定為任意大的數(shù)．大M法適用于規(guī)模較小和數(shù)字比較簡(jiǎn)單的線性規(guī)劃問(wèn)題．但對(duì)于規(guī)模大、數(shù)字大的線性規(guī)劃問(wèn)題,用它不僅運(yùn)算量大,也容易出錯(cuò)．3.3.3對(duì)人工變量法的幾點(diǎn)體會(huì)：１、所引入的人工變量并不是規(guī)定幾個(gè),而只需引進(jìn)的個(gè)數(shù)與已存在的變量構(gòu)成一個(gè)單位矩陣即可.２、在使用大M法時(shí),目標(biāo)函數(shù)若是求最大值（max）引入-M倍,求最小值（min）引入M倍．３、要求原問(wèn)題的最優(yōu)解,首先得把人工變量變?yōu)椋埃谇笞畲笾禃r(shí),非基變量全部為正數(shù)；在求最小值時(shí),非基變量全不為負(fù)．倘使已達(dá)到所符合的要求時(shí),但有人工變量還是某一個(gè)數(shù)時(shí),則不存在最優(yōu)解．４、當(dāng)人工變量與松弛變量的比值相同時(shí),首選人工變量做為變基．５、在確定出基變量與入基變量時(shí),遵循勃蘭特規(guī)則：１）選取檢驗(yàn)數(shù)中下標(biāo)最小的非基變量為入基變量．２）當(dāng)按規(guī)則計(jì)算存在兩個(gè)或兩個(gè)以上最小值時(shí),選取下標(biāo)最小的基變量為出基變量．這樣可避免出現(xiàn)計(jì)算過(guò)程的循環(huán).3.4改進(jìn)單純形法3.4.1改進(jìn)單純形法（一）在實(shí)際生活中遇到的線性規(guī)劃問(wèn)題,變量與約束方程的個(gè)數(shù)往往大大超過(guò)我們書(shū)本中所接觸的．解決實(shí)際問(wèn)題都是用計(jì)算機(jī)來(lái)計(jì)算,所以怎樣節(jié)約存儲(chǔ)單元和減少計(jì)算時(shí)間就成了我們必須要考慮的問(wèn)題．仔細(xì)分析單純形法,就會(huì)發(fā)現(xiàn)在其迭代過(guò)程中,表格中的每列元素都參加了運(yùn)算,其中有些運(yùn)算是不必要的,如果直接按這種方法編制程序上計(jì)算機(jī)解題,會(huì)在存儲(chǔ)和計(jì)算方面造成浪費(fèi)．改進(jìn)單純形法就是針對(duì)這一問(wèn)題的．對(duì)于一個(gè)寫(xiě)成矩陣形式的線性規(guī)劃問(wèn)題,已知它的一個(gè)可行基,則改進(jìn)單純形法計(jì)算步驟可歸納如下：第一步,計(jì)算出,從而得到相應(yīng)的基可行解、目標(biāo)函數(shù)值、檢驗(yàn)數(shù)．第二步,驗(yàn)證基可行解是否為最優(yōu)解．若檢驗(yàn)數(shù)的分量皆為非負(fù),則基可行解為最優(yōu)解,而最優(yōu)值為,問(wèn)題得到解決,否則,繼續(xù)進(jìn)行下去．第三步,確定入基列向量．令,則確定為為入基列向量．并計(jì)算若所有的則此問(wèn)題無(wú)最優(yōu)解．若至少有一個(gè),如將轉(zhuǎn)入下一步．第四步,確定出基列向變量．令則確定為主元,令與對(duì)應(yīng)的出基,繼續(xù)進(jìn)行下步．第五步,計(jì)算這里,而為由取代了單位方陣中后得來(lái)．第六步,判斷新基可行解是否最優(yōu)．再回到第二步．3.4.2改進(jìn)單純形法（二）設(shè)關(guān)于可行基的典式為s.t..其中S和R分別是對(duì)應(yīng)的基變量下標(biāo)集和非基變量下標(biāo)集,但．檢驗(yàn)數(shù)為實(shí)數(shù),為實(shí)數(shù)．通過(guò)計(jì)算選擇主元：計(jì)算△Z=﹒(A)若△Z,則任選使上式成立的為主元進(jìn)行旋轉(zhuǎn)運(yùn)算；(B)若△Z=0,則選取,是使等式,成立的最小行下標(biāo),則以為主元旋轉(zhuǎn)運(yùn)算．其余步驟完全同單純形方法．證明：（1）利用單純形方法迭代一步后,目標(biāo)函數(shù)改進(jìn),其中,．而利用上述方法,目標(biāo)函數(shù)改進(jìn),顯然,所以同任何單純形法相比較,上述方法目標(biāo)函數(shù)改進(jìn)較快．（2）反證法．以和分別表示迭代的第階段的基變量和非基變量下標(biāo)集合．又假設(shè)出現(xiàn)了循環(huán),不妨設(shè)為()…這個(gè)循環(huán)過(guò)程是從以為基變量和非基變量下標(biāo)集的可行基開(kāi)始的,經(jīng)過(guò)次迭代后又回到了原來(lái)的可行基．由于在循環(huán)過(guò)程中目標(biāo)函數(shù)始終沒(méi)有改進(jìn),所以每次迭代△,因此主元的選取規(guī)則是按()進(jìn)行的．這時(shí)與法則完全相同．因此不可能出現(xiàn)循環(huán)．3.5對(duì)偶單純形法3.2節(jié)中所講的單純形法又稱(chēng)為原單純形法．從原則上講,它可以求任何線性規(guī)劃問(wèn)題．但在某些情況下,使用起來(lái)顯得不大方便．我們知道任何一個(gè)線性規(guī)劃問(wèn)題都伴隨著另一個(gè)線性規(guī)劃問(wèn)題,稱(chēng)為對(duì)偶問(wèn)題．對(duì)于復(fù)雜的線性規(guī)劃問(wèn)題我們便從其對(duì)偶命題的最優(yōu)單純形表去尋求原問(wèn)題的最優(yōu)解．對(duì)偶單純形法的基本思想是：原單純形法是從一個(gè)正則基解迭代到另一個(gè)基解在迭代過(guò)程中始終保持可行性,使其非正則性（即對(duì)偶不可行性）逐步消失,一旦滿足正則性（即對(duì)偶可行性）,便是最優(yōu)解．由對(duì)偶關(guān)系的啟發(fā),考慮這樣一個(gè)迭代過(guò)程：從一個(gè)基解迭代到另一個(gè)基解,在迭代過(guò)程中保持正則性,使其不可行性逐步消失,一旦滿足可行性,便是最優(yōu)解．對(duì)比原單純形法與對(duì)偶單純形法,兩者都是從一個(gè)基解迭代到另一個(gè)基解,但前者是在基可行解中迭代,后者是在正則解中迭代．在每一次迭代中,原單純形法是先確定進(jìn)基變量后確定離基變量,而對(duì)偶單純形法是先確定離基變量后確定進(jìn)基變量．至于旋轉(zhuǎn)變換方法,兩者是相同的．因此對(duì)偶單純形法也可通過(guò)單純形表（或簡(jiǎn)化單純形表）進(jìn)行．確定了樞元以后,從舊表到新表的演化方法與原單純形法完全相同．3.6改進(jìn)的對(duì)偶單純形法的思想及迭代步驟3.6.1改進(jìn)對(duì)偶單純形法（一）為引出改進(jìn)對(duì)單純形法的思想,先分析對(duì)偶單純形法的迭代過(guò)程,取SLP的一個(gè)對(duì)偶可行基B,有如下步驟：①計(jì)算=,若0,則已得到最優(yōu)解,停止計(jì)算；否則由,確定主元行和基變量．②若出基變量的的第列元素,問(wèn)題無(wú)可行解,停止計(jì)算；否則計(jì)算確定進(jìn)基變量為．③以為主元作轉(zhuǎn)軸運(yùn)算,返回（1）．如何計(jì)算,？如果把按行分塊,即：=則=第r行事實(shí)上,因?yàn)橹恍瓒兞抗手恍栌?jì)算．當(dāng)然,如果每一次迭代都必需從原始數(shù)據(jù)來(lái)構(gòu)造,計(jì)算量并不少,但在每次轉(zhuǎn)軸后,借助上一次迭代中的基陣之逆陣,通過(guò)簡(jiǎn)單計(jì)算獲得轉(zhuǎn)軸后基陣的逆陣,這樣對(duì)偶單純形法的迭代就可以繼續(xù)下去,而其它無(wú)關(guān)的數(shù)據(jù)賓并不需要計(jì)算和存貯,從而減少計(jì)算存貯量,減少計(jì)算誤差．現(xiàn)設(shè)出基,進(jìn)基,在對(duì)偶單純形迭代中,轉(zhuǎn)軸前和轉(zhuǎn)軸后的基陣分別為．．改進(jìn)對(duì)偶單純形法的關(guān)鍵在于如何由盡快產(chǎn)生,設(shè)為中第i個(gè)分量為1,其余分量為零的單位向量,由為單位陣,有=所以,=通過(guò)初等變換不難得到故用此公式來(lái)計(jì)算轉(zhuǎn)軸后基陣的逆陣,可大大減少計(jì)算量．下面給出改進(jìn)的對(duì)偶單純形法的算法步驟．步驟0：選取SLP的一個(gè)對(duì)偶可行基B,基指標(biāo)集為非基指標(biāo)集,計(jì)算基陣的逆陣,一般說(shuō)來(lái),初始陣常為單位陣．步驟1：計(jì)算,若,則已得最優(yōu)解,停止計(jì)算；若還存在,根據(jù)．確定基變量為出基變量,轉(zhuǎn)下一步．步驟2：計(jì)算乘子,及檢驗(yàn)數(shù)：為N的列向量,轉(zhuǎn)下一步．步驟3：計(jì)算,其中為的第r個(gè)行向量,如果,則問(wèn)題無(wú)可行解,停止計(jì)算,否則轉(zhuǎn)下一步．步驟4：根據(jù)以下規(guī)則,選取進(jìn)基變量,轉(zhuǎn)下一步步驟5：換基運(yùn)算,新基指標(biāo)集新非基變量,按（1）,（2）計(jì)算,令=,返回步驟1．3.6.2改進(jìn)對(duì)偶單純形法（二）對(duì)于改進(jìn)單純行法（二）完全可推廣到對(duì)偶單純行法上,這就是改進(jìn)對(duì)偶單純形法（二