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

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