線性規(guī)劃算法的改進(jìn)及在企業(yè)管理中的應(yīng)用【開(kāi)題報(bào)告+文獻(xiàn)綜述+畢業(yè)論文】

1、<p><b>　　畢業(yè)論文開(kāi)題報(bào)告</b></p><p><b>　　數(shù)學(xué)與應(yīng)用數(shù)學(xué)</b></p><p>　　線性規(guī)劃算法的改進(jìn)及在企業(yè)管理中的應(yīng)用</p><p>　　一、選題的背景與意義</p><p>　　線性規(guī)劃是運(yùn)籌學(xué)最基本、運(yùn)用最廣泛的分支，是其他運(yùn)籌學(xué)問(wèn)題研究的基礎(chǔ)。

2、在20世紀(jì)50年代到60年代期間，運(yùn)籌學(xué)領(lǐng)域出現(xiàn)許多新的分支：非線性規(guī)劃、商業(yè)應(yīng)用、大尺度方法、隨機(jī)規(guī)劃、整數(shù)規(guī)劃、互補(bǔ)轉(zhuǎn)軸理論、多項(xiàng)式時(shí)間算法等。20世紀(jì)70年代末,上述分支領(lǐng)域都得到了極大發(fā)展，但是卻都不完善。而且數(shù)學(xué)規(guī)劃領(lǐng)域中存在許多Np-hard問(wèn)題,如TSP問(wèn)題，整數(shù)規(guī)劃問(wèn)題等。這些問(wèn)題的基本模型都可以寫(xiě)成線性規(guī)劃形式，因此通過(guò)對(duì)線性規(guī)劃算法的進(jìn)一步研究，可以進(jìn)一步啟發(fā)及推動(dòng)數(shù)學(xué)規(guī)劃領(lǐng)域內(nèi)其他分支的發(fā)展。</p>

3、<p>　　用單純形法求解線性規(guī)劃問(wèn)題時(shí)，首先要找一個(gè)初始可行基，再用單純形迭代公式求最優(yōu)解。當(dāng)問(wèn)題無(wú)可行基時(shí)，通常是引入人工變量構(gòu)造初始可行基，然后利用兩階段法求解一個(gè)輔助問(wèn)題來(lái)得到一個(gè)原問(wèn)題的一個(gè)初始可行基。</p><p>　　多年來(lái)的實(shí)踐證明，兩階段法方便實(shí)用，但由于人工變量的引入不僅加大了計(jì)算機(jī)的儲(chǔ)存量還增加了計(jì)算量。本篇基于高斯消元法的思想，提出了一種不可引入人工變量，直接按一定的規(guī)則迭代

4、就可求出初始基本可行解或者得出原問(wèn)題無(wú)可行解的改進(jìn)算法。其次用單純形法求線性規(guī)劃問(wèn)題時(shí)可能產(chǎn)生循環(huán)，1955年Beale給出了一個(gè)特例，證明用單純形法求解線性規(guī)劃問(wèn)題時(shí)產(chǎn)生了循環(huán)，50多年來(lái)不少人提出了避免循環(huán)的辦法，最初是A.charnes 1952提出的攝動(dòng)法，其理論復(fù)雜，實(shí)際操作十分方便，1974年Dantzig提出了字典序法，Bland提出的勃蘭特規(guī)則，同樣是不利于實(shí)際操作。</p><p>　　隨著改革

5、開(kāi)放的不斷深入，如何提高企業(yè)的經(jīng)濟(jì)效益是一個(gè)大問(wèn)題。做為一個(gè)企業(yè)家，當(dāng)然首先根據(jù)國(guó)際國(guó)內(nèi)市場(chǎng)的信息確定生產(chǎn)的產(chǎn)品，然后再進(jìn)行產(chǎn)品的設(shè)計(jì)和工藝裝備的設(shè)計(jì)與研究，提高產(chǎn)品的質(zhì)量，降低成本并取得廣大用戶(hù)的信譽(yù)；同時(shí)在管理中盡量采用現(xiàn)代化的管理方法和電子計(jì)算機(jī)管理，為提高企業(yè)的經(jīng)濟(jì)效益尋找出有效的途徑。</p><p>　　二、研究的基本內(nèi)容與擬解決的主要問(wèn)題</p><p><b>　

6、　研究的基本內(nèi)容：</b></p><p>　　線性規(guī)劃問(wèn)題的中單純形法和兩階段法的算法改進(jìn)</p><p><b>　　1.1單純形法</b></p><p>　　1.1.1單純形法的算法介紹及分析</p><p><b>　　1.1.2舉例</b></p><p&

7、gt;<b>　　1.1.3結(jié)論</b></p><p><b>　　1.2兩階段法</b></p><p>　　1.2.1兩階段法的算法介紹及分析</p><p><b>　　1.2.2舉例</b></p><p><b>　　1.2.2結(jié)論</b>&l

8、t;/p><p>　　線性規(guī)劃增減約束條件的靈敏度分析</p><p>　　2.1增減約束條件對(duì)線性規(guī)劃的影響</p><p><b>　　2.2算例分析</b></p><p><b>　　2.3靈敏度分析</b></p><p>　　2.3.1產(chǎn)品市場(chǎng)價(jià)格變化分析</p

9、><p>　　2.3.2資源量的變化分析</p><p>　　2.3.3技術(shù)條件的變化分析</p><p>　　線性規(guī)劃在企業(yè)管理中的應(yīng)用</p><p>　　3.1線性規(guī)劃的概念及構(gòu)成要素</p><p>　　3.2線性規(guī)劃在企業(yè)管理中的應(yīng)用范圍介紹</p><p>　　3.3線性規(guī)劃求解方法介紹

10、</p><p><b>　　擬解決的主要問(wèn)題：</b></p><p>　　通過(guò)上述三個(gè)部分的闡述，主要列舉了線性規(guī)劃方法的介紹及算法的異同點(diǎn)，通過(guò)比較分析說(shuō)明線性規(guī)劃算法改進(jìn)后的優(yōu)點(diǎn)并應(yīng)用舉例。同時(shí)分析說(shuō)明增減約束條件對(duì)線性規(guī)劃的影響及實(shí)際應(yīng)用的分析。論述了線性規(guī)劃對(duì)企業(yè)管理的重大意義，通過(guò)合理的方法應(yīng)用，以期我國(guó)企業(yè)管理能夠得到更好的發(fā)展。</p>

11、<p>　　三、研究的方法與技術(shù)路線</p><p>　　本文通過(guò)文獻(xiàn)綜述法收集了大量國(guó)內(nèi)外線性規(guī)劃的理論分析及企業(yè)管理的發(fā)展現(xiàn)狀。通過(guò)比較分析對(duì)線性規(guī)劃算法改進(jìn)前后進(jìn)行比較，進(jìn)而選擇更優(yōu)良的方法。通過(guò)舉例分析增減約束條件對(duì)線性規(guī)劃的影響及其實(shí)際的應(yīng)用，從而使企業(yè)管理得到合理性和科學(xué)性的發(fā)展。</p><p>　　四、研究的總體安排與進(jìn)度</p><p>

12、;<b>　　五、主要參考文獻(xiàn)</b></p><p>　　[1] 呂游. 運(yùn)籌學(xué)的應(yīng)用與發(fā)展[J]. 大慶師范學(xué)院,2007.</p><p>　　[2] 陳寶林. 最優(yōu)化理論與算法[M]. 北京:清華大學(xué)出版社,2005.</p><p>　　[3] 曾梅清、田大鋼. 線性規(guī)劃問(wèn)題的算法綜述[J]. 科學(xué)技術(shù)與工程.2001,1.</

13、p><p>　　[4]. 周凱山、羅毅平. 兩類(lèi)特殊線性規(guī)劃算法的改進(jìn)[J]. 系統(tǒng)工程,1998,5.</p><p>　　[5]. 展丙軍. 單純形法的改進(jìn)及其應(yīng)用[J]. 大慶師范學(xué)院學(xué)報(bào).2007,4.</p><p>　　[6]. 金濤,劉三陽(yáng),孫小軍. 一種線性規(guī)劃問(wèn)題單純形法的改進(jìn)算法[J]. 2007,12.</p><p>　　

14、[7]. 白巖. 線性規(guī)劃中兩階段法的簡(jiǎn)便計(jì)算法[J]. 長(zhǎng)春師范學(xué)院學(xué)報(bào),2005.</p><p>　　[8]. 孫可欽. 線性規(guī)劃兩階段法的改進(jìn)算法[J]. 運(yùn)籌與管理,2000,3.</p><p>　　[9]. 夏少剛,劉心. 線性規(guī)劃增減約束條件的靈敏度分析[J]. 運(yùn)籌與管理2007,4.</p><p>　　[10]. 王昌貴. 線性規(guī)劃在企業(yè)管理中

15、的應(yīng)用[J]. 大眾科技,2004,12.</p><p>　　[11]. 雷紅. 淺談線性規(guī)劃在企業(yè)管理中的應(yīng)用[J]. 科技情報(bào)開(kāi)發(fā)與經(jīng)濟(jì),2000,6.</p><p>　　[12]. Konstantinos Dosios, Konstantinos Paparrizos . Resolution of the problem of degeneracy in a primal a

16、nd dual simplex algorithm[J]. Operations Research Letters 1997.</p><p>　　[13]. Jian-Feng Hu . A note on“an improved initial basis for the simplex algorithm”[J]. Computers & Operations Research 34 (2007)

17、3397 – 3401.</p><p>　　[14]. Tamas Koltai ,Viola Tatay . A practical approach to sensitivity analysis in linear programming under degeneracy for management decision making[J]. Int. J. Production Economics. &l

18、t;/p><p><b>　　畢業(yè)論文文獻(xiàn)綜述</b></p><p><b>　　數(shù)學(xué)與應(yīng)用數(shù)學(xué)</b></p><p>　　線性規(guī)劃算法的改進(jìn)及在企業(yè)管理中的應(yīng)用</p><p>　　線性規(guī)劃是運(yùn)籌學(xué)最基本、運(yùn)用最廣泛的分支，是其他運(yùn)籌學(xué)問(wèn)題研究的基礎(chǔ)。在20世紀(jì)50年代到60年代期間，運(yùn)籌學(xué)領(lǐng)域出

19、現(xiàn)許多新的分支：非線性規(guī)劃、商業(yè)應(yīng)用、大尺度方法、隨機(jī)規(guī)劃、整數(shù)規(guī)劃、互補(bǔ)轉(zhuǎn)軸理論、多項(xiàng)式時(shí)間算法等。20世紀(jì)70年代末,上述分支領(lǐng)域都得到了極大發(fā)展，但是卻都不完善。而且數(shù)學(xué)規(guī)劃領(lǐng)域中存在許多Np-hard問(wèn)題,如TSP問(wèn)題，整數(shù)規(guī)劃問(wèn)題等。這些問(wèn)題的基本模型都可以寫(xiě)成線性規(guī)劃形式，因此通過(guò)對(duì)線性規(guī)劃算法的進(jìn)一步研究，可以進(jìn)一步啟發(fā)及推動(dòng)數(shù)學(xué)規(guī)劃領(lǐng)域內(nèi)其他分支的發(fā)展。</p><p>　　線性規(guī)劃理論和算法的研

20、究及發(fā)展共經(jīng)歷了三個(gè)高潮，每個(gè)高潮都引起了社會(huì)的極大關(guān)注。線性規(guī)劃研究的第一高潮是著名的單純形法的研究。這一方法是Dantzing在1947年提出的，它以成熟的算法理論和完善的算法及軟件統(tǒng)治線性規(guī)劃達(dá)三十多年。隨著60年代發(fā)展起來(lái)的計(jì)算性復(fù)雜理論的研究，單純形法在七十年代末受到了挑戰(zhàn)。1979年前蘇聯(lián)數(shù)學(xué)家Khachiyan提出了第一個(gè)理論上由于單純形法的所謂多項(xiàng)式時(shí)間算法--橢球法，曾成為轟動(dòng)一時(shí)的新聞，并掀起了研究線性規(guī)劃的第二個(gè)高

21、潮。但遺憾的是廣泛的數(shù)值試驗(yàn)表明，橢球算法的計(jì)算比單純形方法差。</p><p>　　1984年Karmarkar提出了求解線性規(guī)劃的另一個(gè)多項(xiàng)式時(shí)間算法。這個(gè)算法從理論上和數(shù)值上都由于橢球法，因而引起學(xué)術(shù)界的極大關(guān)注，并由此掀起了研究線性規(guī)劃的第三個(gè)高潮。從那以后，許多學(xué)者致力于改進(jìn)和完善這一算法，得到了許多改進(jìn)算法。這些算法運(yùn)用不同的思想方法均獲得通過(guò)可行域內(nèi)部的迭代點(diǎn)列，因此統(tǒng)稱(chēng)為解線性規(guī)劃問(wèn)題的內(nèi)點(diǎn)算法。

22、目前內(nèi)點(diǎn)算法正以不可抗拒的趨勢(shì)將超越和替代單純形法。</p><p>　　單純形法是求解線性規(guī)劃問(wèn)題很有效的方法，基本思想是從方程組AX=0的某個(gè)基可行解開(kāi)始，在不違背條件X 0的前提下，不斷生成新的基可行解，且基可行解的每次更新，均能確保目標(biāo)函數(shù)值有所改進(jìn)，一直獲得最優(yōu)解為止，是一個(gè)多次迭代的過(guò)程。此方法從理論上已趨于完善，但在求最優(yōu)解的過(guò)程中還有很多值得研究和改進(jìn)的，在現(xiàn)有的方法中，單純形表很煩瑣，在計(jì)算中，

23、光制表 就要浪費(fèi)很多的時(shí)間。另外，根據(jù)不同的類(lèi)型有大M法、兩階段法，而這兩種方 法求解過(guò)程更麻煩，迭代次數(shù)都較大，還要有很多語(yǔ)言敘述，即使一個(gè)很簡(jiǎn)單的題，要得到最優(yōu)解，也需要做大量的工作。針對(duì)上述問(wèn)題，可以利用單純形法的思想，將現(xiàn)有的單純形法進(jìn)行改進(jìn)，給出單純形表的矩陣形式，用矩陣的行的初等變換來(lái)實(shí)現(xiàn)求解過(guò)程，使方法更容易理解和掌握，求解過(guò)程更簡(jiǎn)捷，并通過(guò)例子來(lái)展示此種方法的優(yōu)越性。</p><p>　　展丙軍在

24、《單純形法的改進(jìn)及應(yīng)用》中提到，在利用線性規(guī)劃的單純形法求解時(shí)，首先，要在線性規(guī)劃問(wèn)題中引入人工變量，把問(wèn)題變?yōu)榧s束方程組的系數(shù)矩陣中含有單位矩陣，用以作為人造基，然后按單純形方法進(jìn)行換基迭代，求得最優(yōu)解或判定無(wú)最優(yōu)解，這種方法稱(chēng)為兩階段法。第一階段是判斷原線性規(guī)劃問(wèn)題是否存在基本可行解。第二階段是由第一階段最后求得原問(wèn)題的一個(gè)可行基開(kāi)始，運(yùn)用單純形方法，求得原問(wèn)題的最優(yōu)解或判定原問(wèn)題無(wú)最優(yōu)解。</p><p>

25、　　有些線性規(guī)劃問(wèn)題，引進(jìn)松馳變量化成標(biāo)準(zhǔn)形后，約束條件方程組的系數(shù)矩陣并不舍 m階單位矩陣，這樣就給單純形解法的換基迭代帶來(lái)了困難。線性規(guī)劃在利用兩階段法解這類(lèi)問(wèn)題時(shí)，尤其是一些具體的實(shí)際問(wèn)題，對(duì)于加人的人工變量Yi應(yīng)該根據(jù)問(wèn)題盡可能的少，使人工變量的個(gè)數(shù)小于（或等于)m。白巖在《線性規(guī)劃中兩階段法的簡(jiǎn)便算法》就線性規(guī)劃問(wèn)題的原問(wèn)題在加人人工變量 y中，如何根據(jù)所給問(wèn)題盡可能的少引人人工變量，通過(guò)例子來(lái)說(shuō)明線性規(guī)劃問(wèn)題兩階段法的簡(jiǎn)便計(jì)

26、算法。需要注意的是盡可能少引人人工變量y的同時(shí)，保證使約束條件方程組的系數(shù)矩陣中有一個(gè)可行基，這就要根據(jù)實(shí)際問(wèn)題，靈活運(yùn)用兩階段法。</p><p>　　劉心在《線性規(guī)劃增減約束條件的靈敏度分析》中，在靈敏度分析的基礎(chǔ)上， 面對(duì)增減約束條件，特別對(duì)減少約束的情形，給出新最優(yōu)方案的獲得方法，并指出其特殊的經(jīng)濟(jì)意義。 </p><p>　　一個(gè)企業(yè)要在市場(chǎng)競(jìng)爭(zhēng)中立于不敗之地，就必須改善經(jīng)營(yíng)管

27、理，提高經(jīng)濟(jì)效益，具體包括怎樣合理安排生產(chǎn)任務(wù)、合理配置資源，怎樣制定最優(yōu)的生產(chǎn)計(jì)劃，并對(duì)瞬息萬(wàn)變的市場(chǎng)信息及時(shí)作出反應(yīng)。隨著計(jì)算機(jī)技術(shù)的普及，線性規(guī)劃的數(shù)學(xué)方法在企業(yè)管理中應(yīng)用的范圍越來(lái)越廣泛。線性規(guī)劃產(chǎn)生于三十年代未和四十年代初，并隨著現(xiàn)代科技和管理實(shí)踐的發(fā)展而不斷發(fā)展。是運(yùn)籌學(xué)中起源較早、理論上較成熟的一個(gè)分支。線性規(guī)劃的“線性”特點(diǎn)，簡(jiǎn)化了數(shù)學(xué)模型的構(gòu)造和解題方法，容易被一般未具有高等數(shù)學(xué)知識(shí)的各級(jí)企業(yè)管理人員所掌握應(yīng)用。特別是

28、計(jì)算機(jī)的廣泛應(yīng)用，線性規(guī)劃的在企業(yè)管理中的應(yīng)用范圍更加廣泛和深入。漸漸成為管理人員必須掌握的一門(mén)現(xiàn)代化管理方法和優(yōu)化技術(shù)。</p><p>　　線性規(guī)劃在企業(yè)中的應(yīng)用范圍：企業(yè)的效益依賴(lài)于資源配置的優(yōu)化，即依賴(lài)于線性規(guī)劃模型的優(yōu)化，優(yōu)化的范圍越大，效果也就越好。首先，線性規(guī)劃可用于生產(chǎn)計(jì)劃確定后的優(yōu)化，內(nèi)容包括：其一，在一定的資金和風(fēng)險(xiǎn)條件下，確定最佳庫(kù)存量，使生產(chǎn)保持連續(xù)性 和資金占用最小。其二，在生產(chǎn)計(jì)劃、生

29、產(chǎn)設(shè)備、生產(chǎn)能力的條件限制下，在各種產(chǎn)品、原材料、零部件的價(jià)格、生產(chǎn)人員的約束條件下，求得產(chǎn)品的最大利益。其三，在運(yùn)輸分配計(jì)劃中，計(jì)算路徑、數(shù)量、人員的最佳效率和最小費(fèi)用。其四， 在原材料具有混合比例的限制下，求得價(jià)格、成本最低、利益最大。其五，各類(lèi)投資問(wèn)題：一定的資金總額，利率與回收期不同的項(xiàng)目之間，如何投放使用，才能使經(jīng)濟(jì)效益最好。其二：線性規(guī)劃支持企業(yè)未來(lái)的決策。管理者必須分析未來(lái)的經(jīng)濟(jì)走勢(shì)、分析未來(lái)的消費(fèi)趨勢(shì)并預(yù)測(cè)同行的產(chǎn)銷(xiāo)動(dòng)向

30、。然后確定自己的產(chǎn)品價(jià)格、廣告與促銷(xiāo)策略，最后再將這些數(shù)據(jù)進(jìn)行線性規(guī)劃。這是求解一個(gè)隨機(jī)線性規(guī)劃問(wèn)題。此類(lèi)問(wèn)題有待于進(jìn)一步探討。</p><p><b>　　參考文獻(xiàn)：</b></p><p>　　[1] 呂游. 運(yùn)籌學(xué)的應(yīng)用與發(fā)展[J]. 大慶師范學(xué)院,2007.</p><p>　　[2] 陳寶林. 最優(yōu)化理論與算法[M]. 北京:清華大學(xué)

31、出版社,2005.</p><p>　　[3] 曾梅清、田大鋼. 線性規(guī)劃問(wèn)題的算法綜述[J]. 科學(xué)技術(shù)與工程.2001,1.</p><p>　　[4]. 周凱山、羅毅平. 兩類(lèi)特殊線性規(guī)劃算法的改進(jìn)[J]. 系統(tǒng)工程,1998,5.</p><p>　　[5]. 展丙軍. 單純形法的改進(jìn)及其應(yīng)用[J]. 大慶師范學(xué)院學(xué)報(bào).2007,4.</p>

32、<p>　　[6]. 金濤,劉三陽(yáng),孫小軍. 一種線性規(guī)劃問(wèn)題單純形法的改進(jìn)算法[J]. 2007,12.</p><p>　　[7]. 白巖. 線性規(guī)劃中兩階段法的簡(jiǎn)便計(jì)算法[J]. 長(zhǎng)春師范學(xué)院學(xué)報(bào),2005.</p><p>　　[8]. 孫可欽. 線性規(guī)劃兩階段法的改進(jìn)算法[J]. 運(yùn)籌與管理,2000,3.</p><p>　　[9]. 夏少剛,

33、劉心. 線性規(guī)劃增減約束條件的靈敏度分析[J]. 運(yùn)籌與管理2007,4.</p><p>　　[10]. 王昌貴. 線性規(guī)劃在企業(yè)管理中的應(yīng)用[J]. 大眾科技,2004,12.</p><p>　　[11]. 雷紅. 淺談線性規(guī)劃在企業(yè)管理中的應(yīng)用[J]. 科技情報(bào)開(kāi)發(fā)與經(jīng)濟(jì),2000,6.</p><p>　　[12]. Konstantinos Dosios

34、, Konstantinos Paparrizos . Resolution of the problem of degeneracy in a primal and dual simplex algorithm[J]. Operations Research Letters 1997.</p><p>　　[13]. Jian-Feng Hu . A note on“an improved initial ba

35、sis for the simplex algorithm”[J]. Computers & Operations Research 34 (2007) 3397 – 3401.</p><p>　　[14]. Tamas Koltai ,Viola Tatay . A practical approach to sensitivity analysis in linear programming und

36、er degeneracy for management decision making[J]. Int. J. Production Economics.</p><p><b>　　本科畢業(yè)設(shè)計(jì)</b></p><p><b>　?。?0 屆）</b></p><p>　　線性規(guī)劃算法的改進(jìn)及在企業(yè)管理中的應(yīng)用&l

37、t;/p><p><b>　　摘　要</b></p><p>　　【摘要】線性規(guī)劃是運(yùn)籌學(xué)最基本、運(yùn)用最廣泛的分支，是其他運(yùn)籌學(xué)問(wèn)題研究的基礎(chǔ)。線性規(guī)劃的算法有若干種，本文僅對(duì)其中的幾種算法進(jìn)行改進(jìn)并研究。首先介紹了線性規(guī)劃問(wèn)題中的單純形法和兩階段法的算法改進(jìn)，并對(duì)這兩種方法進(jìn)行了分析和舉例說(shuō)明，然后對(duì)線性規(guī)劃增減約束條件的靈敏度進(jìn)行分析，最后說(shuō)明線性規(guī)劃在企業(yè)管理中的應(yīng)

38、用。線性規(guī)劃的“線性”特點(diǎn)，簡(jiǎn)化了數(shù)學(xué)模型的構(gòu)造和解題方法，容易被一般未具有高等數(shù)學(xué)知識(shí)的各級(jí)企業(yè)管理人員所掌握應(yīng)用，特別是計(jì)算機(jī)的廣泛應(yīng)用，線性規(guī)劃的在企業(yè)管理中的應(yīng)用范圍更加廣泛和深入，漸漸成為管理人員必須掌握的一門(mén)現(xiàn)代化管理方法和優(yōu)化技術(shù)。</p><p>　　【關(guān)鍵詞】單純形法；兩階段法；靈敏度分析；企業(yè)管理應(yīng)用。</p><p><b>　　Abstract</b

39、></p><p>　　【ABSTRACT】Linear programming is the most basic operations research, the most widely used branch operations research problems in other research.Linear programming algorithm has several, this is

40、only a few of the algorithm is improved and study.This paper first introduced algorithm improvement of the simplex method and two-stage method in the linear programming question and carried on to these two methods has an

41、alyzed and carries on explains with examples. Then it analysisd the sensitivity of addi</p><p>　　【KEYWORDS】Simplex method; two-stage method; sensitivity analysis; enterprise management applications.</p>

42、;<p><b>　　目　錄</b></p><p><b>　　摘　要9</b></p><p>　　Abstract10</p><p><b>　　目　錄11</b></p><p><b>　　1 引言12</b></p

43、><p>　　1.1 線性規(guī)劃簡(jiǎn)介12</p><p>　　2 線性規(guī)劃問(wèn)題單純形法的改進(jìn)算法12</p><p>　　2.1問(wèn)題的提出12</p><p>　　2.2單純形法的改進(jìn)算法113</p><p>　　2.2.1算法介紹13</p><p>　　2.2.2算法分析14<

44、/p><p>　　2.2.3舉例15</p><p>　　2.3單純形法的改進(jìn)算法219</p><p>　　2.3.1用矩陣的方法求解線性規(guī)劃問(wèn)題19</p><p>　　2.3.2舉例20</p><p>　　3線性規(guī)劃問(wèn)題兩階段法的改進(jìn)算法20</p><p>　　3.1問(wèn)題的提出

45、20</p><p>　　3.2兩階段法改進(jìn)算法121</p><p>　　3.2.1算法介紹21</p><p>　　3.2.2舉例23</p><p>　　3.3單純形法的改進(jìn)算法224</p><p>　　3.3.1兩階段法的簡(jiǎn)便算法25</p><p>　　3.3.2舉例25

46、</p><p>　　4 線性規(guī)劃增減約束條件的靈敏度分析28</p><p><b>　　4.1引言28</b></p><p>　　4.2增加約束條件28</p><p>　　4.3減少約束條件28</p><p><b>　　4.4舉例29</b></p

47、><p>　　4.5靈敏度分析31</p><p>　　5線性規(guī)劃在企業(yè)管理中的應(yīng)用31</p><p><b>　　5.1引言31</b></p><p>　　5.2線性規(guī)劃模型的描述和建立32</p><p>　　5.2.1線性規(guī)劃模型的描述32</p><p>

48、　　5.2.2建立生產(chǎn)計(jì)劃決策分析的線性規(guī)劃模型33</p><p>　　5.3案例分析34</p><p>　　5.3.1案例134</p><p>　　5.3.2案例234</p><p>　　5.3.3案例335</p><p><b>　　5.4結(jié)論36</b></p&g

49、t;<p><b>　　參考文獻(xiàn)37</b></p><p>　　致謝錯(cuò)誤!未定義書(shū)簽。</p><p>　　附錄錯(cuò)誤!未定義書(shū)簽。</p><p><b>　　引言</b></p><p><b>　　線性規(guī)劃簡(jiǎn)介</b></p><p

50、>　　線性規(guī)劃是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個(gè)重要分支，它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法。研究線性約束條件下線性目標(biāo)函數(shù)的極值問(wèn)題的數(shù)學(xué)理論和方法，英文縮寫(xiě)為L(zhǎng)P。它是運(yùn)籌學(xué)的一個(gè)重要分支，廣泛應(yīng)用于軍事作戰(zhàn)、經(jīng)濟(jì)分析、經(jīng)營(yíng)管理和工程技術(shù)等方面。為合理地利用有限的人力、物力、財(cái)力等資源作出的最優(yōu)決策，提供科學(xué)的依據(jù)。隨著計(jì)算機(jī)技術(shù)的發(fā)展和普及，線性規(guī)劃的應(yīng)用越來(lái)越廣泛。它已成為人們?yōu)楹侠砝糜邢拶Y源制

51、訂最佳決策的有力工具。線性規(guī)劃的算法中，包括單純形方法、兩階段法、對(duì)偶原理與對(duì)偶算法、靈敏度分析、分解算法、內(nèi)點(diǎn)算法，以及整數(shù)線性規(guī)劃等。</p><p>　　本文就線性規(guī)劃中的幾種算法進(jìn)行研究并改進(jìn)，其中包括單純形法算法的改進(jìn)、兩階段法算法的改進(jìn)，及增減約束條件的靈敏度進(jìn)行分析，最后討論線性規(guī)劃在企業(yè)管理中的應(yīng)用。</p><p>　　隨著改革開(kāi)放的不斷深入，如何提高企業(yè)的經(jīng)濟(jì)效益是一個(gè)

52、大問(wèn)題，作為一個(gè)企業(yè)家，首先當(dāng)然要根據(jù)國(guó)際國(guó)內(nèi)市場(chǎng)的信息來(lái)確定生產(chǎn)的產(chǎn)品，然后再進(jìn)行產(chǎn)品的設(shè)計(jì)和工藝裝備的設(shè)計(jì)研究，提高產(chǎn)品的質(zhì)量，降低成本并取得廣大用戶(hù)的信譽(yù)。同時(shí)，在管理中盡量采用現(xiàn)代化的管理方法和電子計(jì)算機(jī)管理，為提高企業(yè)的經(jīng)濟(jì)效益尋找出有效的途徑。</p><p>　　線性規(guī)劃問(wèn)題單純形法的改進(jìn)算法</p><p><b>　　2.1問(wèn)題的提出</b><

53、/p><p>　　單純形法求解線性規(guī)劃的問(wèn)題時(shí)，首先要找到一個(gè)初始可行基，再用單純形迭代公式來(lái)求最優(yōu)解。當(dāng)問(wèn)題無(wú)明顯的可行基時(shí)，通常是先引入人工變量構(gòu)造初始可行基，然后再利用兩階段法求解一個(gè)輔助問(wèn)題，來(lái)得到一個(gè)原問(wèn)題的一個(gè)初始可行基。</p><p>　　多年的實(shí)踐證明，兩階段法雖方便實(shí)用，但人工變量的引入不光加大了計(jì)算機(jī)的貯存量，還增加了計(jì)算量。文獻(xiàn)中曾采用，基于了高斯消元法的思想，提出了一

54、種不用引入人工變量，直接按一定的規(guī)則迭代來(lái)求出初始基本可行解或者求出原問(wèn)題無(wú)可行解的改進(jìn)算法。用單純形法求線性規(guī)劃問(wèn)題時(shí)可能產(chǎn)生循環(huán)，它提出的單純形法的改進(jìn)算法可以有效的避免循環(huán)，且操作簡(jiǎn)單。 </p><p>　　2.2單純形法的改進(jìn)算法1</p><p><b>　　2.2.1算法介紹</b></p><p>　　線性規(guī)劃問(wèn)題：

55、 </p><p>　　其中，是階的矩陣，，，且。</p><p>　　在很多情況下，線性規(guī)劃問(wèn)題并沒(méi)有明顯的可行基，通常是采用引入人工變量后用大M法或兩階段法，但都會(huì)使計(jì)算量增加，同時(shí)還增加了計(jì)算機(jī)的儲(chǔ)存量。此外當(dāng)線性規(guī)劃問(wèn)題出現(xiàn)退化時(shí)， 采用單純形法可能會(huì)產(chǎn)生循環(huán)。下面所提出的算法有效的避免了循環(huán)，提高了運(yùn)算速度。</p><p>　

56、　步驟1：先寫(xiě)出約束方程組的增廣矩陣，任取一個(gè)大于0的，并以第行的倍加入到第行 ，使第行的常數(shù)項(xiàng)變?yōu)?，得到了下表1（為檢驗(yàn)數(shù)）；轉(zhuǎn)步驟2。</p><p><b>　　表1</b></p><p>　　步驟2：令，對(duì)應(yīng)上表，若，則此行對(duì)應(yīng)的方程則為多余方程，去掉此行，否則取一個(gè)下標(biāo)最小且滿(mǎn)足的項(xiàng)，令其為主元實(shí)行一次高斯消元，然后將和寫(xiě)在該行左邊下對(duì)應(yīng)的位置；再令，當(dāng)

57、時(shí)，令，重復(fù)上述過(guò)程一直到取完從1到所有的不等于的整數(shù)為止；然后轉(zhuǎn)步驟3。</p><p>　　步驟3：若第行元素，結(jié)束：?jiǎn)栴}無(wú)可行解；否則就考查每一個(gè)，倘若存在某個(gè)H對(duì)應(yīng)的列滿(mǎn)足（取從1到中的不等于的整數(shù)），則以為主元進(jìn)行一次高斯消元，并將和寫(xiě)在該行左邊下對(duì)應(yīng)的位置，然后按公式修正常數(shù)項(xiàng)，按公式（是修正后的列向量）修正檢驗(yàn)數(shù)。然后轉(zhuǎn)步驟5；否則就轉(zhuǎn)步驟4。</p><p>　　步驟4：任

58、取一個(gè)（取從1到中的不等于的整數(shù)），實(shí)行一次高斯消元，并用和替換該行左邊下對(duì)應(yīng)的位置的元素，然后轉(zhuǎn)步驟3；</p><p>　　步驟5：若所有的檢驗(yàn)數(shù)>0或=0，則得到的最優(yōu)解，否則轉(zhuǎn)步驟6；</p><p>　　步驟6：找出所有對(duì)應(yīng)的列，并按規(guī)劃確定每列的主元素，并以這些元素為主元進(jìn)行相應(yīng)的試算，試算公式是，選擇對(duì)應(yīng)的主元為最終的主元迭代，若有幾個(gè)同時(shí)達(dá)到最大，就選擇最小的對(duì)應(yīng)的主

59、元為最終主元進(jìn)行迭代，然后轉(zhuǎn)步驟5。</p><p><b>　　2.2.2算法分析</b></p><p><b>　　一、準(zhǔn)備工作</b></p><p>　　一個(gè)基本可行解就是方程組的一個(gè)自由變量取零時(shí)的非負(fù)特解，能否不引入人工變量像解方程組一樣來(lái)找出這個(gè)問(wèn)題的特解？一般說(shuō)比較困難，就算找到了一個(gè)特解也無(wú)法保證其可行

60、性，但我們仔細(xì)研究一下輔助問(wèn)題的求解過(guò)程，可以注意以下3點(diǎn)。</p><p>　?。?）將人工變量逐個(gè)從基變量中換出來(lái)的過(guò)程，就是解輔助問(wèn)題的過(guò)程，每換出一個(gè)作一次迭代運(yùn)算。 </p><p>　?。?）每作一次迭代運(yùn)算，就決定了一個(gè)非人工變量作基變量，并將其系數(shù)列變化為單位向量。 </p><p>　?。?）每作一次迭代前總要通過(guò)計(jì)算“最小比值”來(lái)確定主元，以

61、保證基本解的可行性。 </p><p>　　基于上述幾點(diǎn)，可以用高斯消元法的思想，融入一些技巧，則可以把兩階段法的上述步驟省略，以使求解初始可行解與解方程組的高斯消元法幾乎無(wú)異，可以說(shuō)做到了最大限度的簡(jiǎn)化。 </p><p><b>　　二、分析過(guò)程</b></p><p>　　無(wú)基行是，任意找一個(gè)常數(shù)項(xiàng)大于0的方程在初始表中對(duì)應(yīng)的行。其它方

62、程對(duì)應(yīng)的行則叫做有基行，步驟1實(shí)質(zhì)上是找一個(gè)無(wú)基行，并進(jìn)行一次高斯消元，把有基行的常數(shù)項(xiàng)都變?yōu)榱悖?然后在步驟2中進(jìn)行以下變動(dòng)，即在每一個(gè)有基行中找出第一個(gè)非零元素，接下來(lái)以此為主元進(jìn)行高斯消元，步驟1的作用在這里就體現(xiàn)出來(lái)了，因?yàn)椴还苓@個(gè)非零元素是正是負(fù)， 由于步驟 1已把有基行的常數(shù)項(xiàng)均變?yōu)榱悖@樣我們以為主元進(jìn)行消元時(shí)就可以保證對(duì)應(yīng)的基變量是可行的，因?yàn)閷?duì)應(yīng)的常數(shù)項(xiàng)是零，保證了其可行性。</p><p>　

63、　同時(shí)我們是在每一個(gè)有基行中找第一個(gè)非零元為主元進(jìn)行消去，這樣可以保證選擇的主元不在同一列。對(duì)于無(wú)基行，我們?cè)诓襟E3中點(diǎn)明了以下三種情況 ： </p><p>　　（1）當(dāng)無(wú)基行在迭代表中對(duì)應(yīng)的，均小于等于零時(shí)，沒(méi)有可行解。因?yàn)闊o(wú)基行對(duì)應(yīng)的常數(shù)項(xiàng)大于零，且左邊小于等于0而右邊大于零，這樣就矛盾了；</p><p>　?。?）在無(wú)基行中選擇一個(gè)大于零的項(xiàng)，如果這項(xiàng)對(duì)應(yīng)的列中所有項(xiàng)(取從1到

64、中的所有不等于的整數(shù))均小于等于零，就以為主元進(jìn)行高斯消元，同時(shí)將和寫(xiě)在該行左邊下對(duì)應(yīng)的位置，這樣各行均為有基行，并且可以保證各行對(duì)應(yīng)的常數(shù)項(xiàng)均大于等于零，不僅保證了解的可行性，還找到了一個(gè)非負(fù)特解即初始可行解；</p><p>　　（3）若對(duì)于每一個(gè)，其所對(duì)應(yīng)的列中有，則以為主元來(lái)進(jìn)行高斯消元 ，同時(shí)分別用和替換該行左邊下對(duì)應(yīng)的位置上的元素；再看（2）是否成立，不成立繼續(xù)進(jìn)行（3）。 </p>

65、;<p><b>　　2.2.3舉例</b></p><p>　　解：按照前述程序步驟1先建立初始迭代表，選擇第3行為無(wú)基行，迭代過(guò)程見(jiàn)下表3。</p><p><b>　　表3</b></p><p>　　經(jīng)過(guò)4次迭代得到最優(yōu)解，目標(biāo)函數(shù)的最大值是-8；</p><p>　　若是用單

66、純形法求最優(yōu)解，首先用最大M法求初始可行基，迭代4次后求得初始可行基，然后求原問(wèn)題的最優(yōu)解，然后利用單純形迭代公式再迭代1次，總共迭代5次后才得到最優(yōu)解；且因?yàn)橐M(jìn)了人工變量，所以計(jì)算量和儲(chǔ)存量都比本算法要大。</p><p>　　下面看Beale給的例子：</p><p>　　利用單純形法去做經(jīng)過(guò)6次迭代后得到的單純形表和初始單純形表一樣，做下去將無(wú)限循環(huán)，這樣復(fù)雜的多。用本算法去做可以

67、有效的避免循環(huán)，那么先按步驟1建立初始迭代表4。</p><p><b>　　表4</b></p><p>　　因?yàn)锽eale給的這個(gè)例子已經(jīng)有了一個(gè)明顯的初始可行基，所以可以直接把基變量和相應(yīng)的系數(shù)填在相應(yīng)的位置，見(jiàn)下表5。</p><p><b>　　表5 </b></p><p>　　計(jì)算相應(yīng)

68、的檢驗(yàn)數(shù)得和兩個(gè)檢驗(yàn)數(shù)均為負(fù)數(shù)，對(duì)這兩個(gè)檢驗(yàn)數(shù)對(duì)應(yīng)的列中所有正數(shù)項(xiàng)進(jìn)行試算，最后以對(duì)應(yīng)的主元1為最終元進(jìn)行迭代得到下表6。</p><p><b>　　表6</b></p><p>　　小零0，這個(gè)檢驗(yàn)數(shù)對(duì)應(yīng)的列按規(guī)則確定主元，最后以為主元來(lái)進(jìn)行迭代，得下表7。</p><p><b>　　表7</b></p>

69、<p>　　發(fā)現(xiàn)檢驗(yàn)數(shù)全是正數(shù)，所以這時(shí)得到可行解就為最優(yōu)解，最優(yōu)解是，最優(yōu)值是。由此例可以看出，本算法有效避免了循環(huán)。</p><p>　　以上例子可以看出改進(jìn)后的單純形法有兩大優(yōu)點(diǎn)：（1）不用引入人工變量，這樣可以減少計(jì)算機(jī)的存儲(chǔ)量，同時(shí)實(shí)驗(yàn)證明還降低了運(yùn)算量，減少了迭代次數(shù)；（2）可以避免循環(huán)。改進(jìn)后的單純形法大幅度的提高了單純形的效率。</p><p>　　2.3單純

70、形法的改進(jìn)算法2</p><p>　　上面的單純形法的改進(jìn)算法已趨于完善，但在其求最優(yōu)解的過(guò)程中還是有很多值得研究和改進(jìn)的。上面的方法中，單純形表很煩瑣，計(jì)算中，制表會(huì)浪費(fèi)很多的時(shí)間。另外，根據(jù)不同的類(lèi)型有大M法、兩階段法，而這兩種方法求解過(guò)程更麻煩，迭代次數(shù)也都較大，還要有很多語(yǔ)言敘述，即便一個(gè)很簡(jiǎn)單的題，要得到最優(yōu)解，也需要做大量的工作。針對(duì)上述問(wèn)題，本人利用單純形法的思想，將現(xiàn)有的單純形法又進(jìn)行了改進(jìn)，給出

71、了單純形表的矩陣形式，用矩陣的行的初等變換來(lái)實(shí)現(xiàn)求解過(guò)程，使方法更容易理解和掌握，求解過(guò)程更簡(jiǎn)捷，并通過(guò)例子來(lái)展示這種方法的優(yōu)越性。</p><p>　　2.3.1用矩陣的方法求解線性規(guī)劃問(wèn)題</p><p>　　單純形法的矩陣表示：</p><p><b>　　線性規(guī)劃：</b></p><p><b>　　

72、其中，，，，。</b></p><p>　　此線性規(guī)劃對(duì)應(yīng)的矩陣可以表示為：。</p><p>　　要想得到最優(yōu)解，就要求使檢驗(yàn)數(shù)為非負(fù)的基本可行解，這是最終目標(biāo)，要想完成此目標(biāo)，可以有很多方法來(lái)實(shí)現(xiàn)。</p><p>　　這個(gè)初等變換實(shí)際上就是方程組的恒等變形，了解這一點(diǎn)是靈活使用初等變換來(lái)求解線性規(guī)劃的關(guān)鍵。</p><p>

73、　　下面用矩陣及矩陣的初等變換法求解線性規(guī)劃，從而實(shí)現(xiàn)單純形法的改進(jìn)，方法如下：</p><p>　　化標(biāo)準(zhǔn)型（指求最大值問(wèn)題）</p><p><b>　　寫(xiě)出對(duì)應(yīng)的矩陣</b></p><p>　　用行的初等變換得到初始可行矩陣（要確保）</p><p>　　用行的初等變換求出最優(yōu)陣（此時(shí)）</p>&

74、lt;p><b>　　寫(xiě)出最優(yōu)解和最優(yōu)值</b></p><p>　　其中（2）、（3）、（4）步是連續(xù)的，可合為一步。</p><p><b>　　2.3.2舉例</b></p><p>　　求解： </p><p>　　解：化為標(biāo)準(zhǔn)型 </p><

75、p>　　寫(xiě)出對(duì)應(yīng)的矩陣并對(duì)其進(jìn)行初等變換</p><p><b>　　可得最優(yōu)解，</b></p><p>　　所以原問(wèn)題的最優(yōu)解為：</p><p>　　3線性規(guī)劃問(wèn)題兩階段法的改進(jìn)算法</p><p><b>　　3.1問(wèn)題的提出</b></p><p>　　求解線

76、性規(guī)劃問(wèn)題的第一步，就是尋找一個(gè)初始可行基或?qū)ε伎尚谢?。一般的處理辦法是對(duì)約束條件加入松馳變量標(biāo)準(zhǔn)化后再引入人工變量，用大M法或兩階段法求初始可行基或者增加大M約束條件求對(duì)偶可行基。引入過(guò)多的人工變量必然會(huì)增加計(jì)算機(jī)的存儲(chǔ)量和計(jì)算量；增加大M約束條件的方法，首先因?yàn)镸是一個(gè)非常大的正數(shù)，容易產(chǎn)生計(jì)算錯(cuò)誤，其次計(jì)算機(jī)求解線性規(guī)劃問(wèn)題的時(shí)間隨約束條件數(shù)的立方倍數(shù)增加，增加約束條件勢(shì)必延長(zhǎng)計(jì)算時(shí)間。實(shí)際問(wèn)題的模型越大，這個(gè)問(wèn)題就越突出。在文獻(xiàn)

77、的啟發(fā)下，筆者探索出一種先求出問(wèn)題的一個(gè)基，再在最多使用一個(gè)人工變量條件下，尋求線性規(guī)劃問(wèn)題初始可行基的新算法， 這種方法能有效地節(jié)約計(jì)算機(jī)的存儲(chǔ)量和計(jì)算量。 </p><p>　　3.2兩階段法改進(jìn)算法1</p><p><b>　　3.2.1算法介紹</b></p><p>　　因?yàn)榈葍r(jià)于，可設(shè)實(shí)際問(wèn)題的線性規(guī)劃模型為：</p>

78、;<p>　　引入松弛變量，將不等式約束條件化為等式</p><p>　　步驟1：求出約束方程組的一個(gè)初始基，這時(shí)約束方程組的增廣矩陣</p><p><b>　　分塊為</b></p><p>　　下部子塊正好是后個(gè)等式構(gòu)成的方程組的增廣矩陣，首先將所有松弛變量定為基變量，以求解后個(gè)等式構(gòu)成的方程組為目標(biāo)，對(duì)增廣矩陣進(jìn)行迭代運(yùn)算

79、，得，</p><p><b>　　其中；。</b></p><p><b>　　當(dāng)時(shí)， ；</b></p><p>　　再以第行的第一個(gè)非零系數(shù)為旋轉(zhuǎn)元對(duì)繼續(xù)作迭代運(yùn)算，重復(fù)上述運(yùn)算。設(shè)方程組系數(shù)矩陣的秩為，一般重復(fù)次，可在原決策變量中得到個(gè)基變量，它們的系數(shù)列與松弛變量的系數(shù)列合在一起正好構(gòu)成一個(gè)階單位陣，取為初始基，

80、相應(yīng)的基變量記作；其中前個(gè)是松弛變量）。</p><p>　　步驟2：考查常數(shù)列是否成立？</p><p>　　是：此時(shí)的基是原的一個(gè)初始可行基。將目標(biāo)函數(shù)系數(shù)引入，用單純形法求出最優(yōu)解。</p><p>　　否：常數(shù)列中有負(fù)數(shù)，該基不可行，則轉(zhuǎn)步驟3。</p><p>　　步驟3：第一步得到的初始基為基礎(chǔ)，引入一個(gè)人工變量構(gòu)造輔助問(wèn)題，其目

81、標(biāo)函數(shù)為最小值，約束條件是原問(wèn)題約束條件經(jīng)第一步迭代后得到的所有方程等號(hào)左端減去得到的，即</p><p>　　若取負(fù)值的常數(shù)中絕對(duì)值最大的一個(gè)為，即，則讓為出基變量(若值為的基變量不止一個(gè)，則讓其中下標(biāo)最小的出基)，為進(jìn)基變量進(jìn)行換基迭代，迭代后的約束常數(shù)；當(dāng)時(shí)得到的基是的可行基。用單純形方法求解輔助問(wèn)題，因?yàn)橛锌尚薪馇夷繕?biāo)函數(shù)有下界，所以一定有最優(yōu)解。該方法是對(duì)兩階段法的改進(jìn)，原理不變，所以?xún)呻A段法的一切結(jié)論

82、在這里都成立。 </p><p>　　若的最優(yōu)值，原問(wèn)題一定有可行解</p><p>　　若最優(yōu)解中是非基變量，則的最優(yōu)基就是問(wèn)題的一個(gè)初始可行基；若的最優(yōu)解中是基變量，則的值一定是零，說(shuō)明有退化解，這時(shí)，</p><p>　　若所在方程中非基變量的系數(shù)都為零，則該方程是原問(wèn)題的多余方程，去掉該方程，得到原問(wèn)題的一個(gè)階的可行基；</p><p&

83、gt;　　若所在方程中存在系數(shù)不為零的非基變量，任取其中一個(gè)進(jìn)基，讓出基，迭代后能得到原問(wèn)題的一個(gè)初始可行基；</p><p>　　的最優(yōu)值，這時(shí)最優(yōu)解中，說(shuō)明原問(wèn)題存在互不相容的約束條件，即系統(tǒng)中的資源不夠充分，無(wú)法滿(mǎn)足要求，原問(wèn)題無(wú)可行解。</p><p><b>　　3.2.2舉例</b></p><p>　　求解線性規(guī)劃問(wèn)題

84、 </p><p>　　解：引入松弛變量將原問(wèn)題約束條件等式化</p><p>　　的系數(shù)列正好構(gòu)成一個(gè)初始基,該基不可行，加入人工變量，構(gòu)造輔助問(wèn)題，上表迭代三次后得到問(wèn)題的一個(gè)可行基及其對(duì)應(yīng)的單純形表。該例若采用大M法或兩階段法求解，需引入三個(gè)人工變量，至少要迭代四次才能得到原問(wèn)題的可行基。約束條件越多，迭代次數(shù)及迭代時(shí)間的差異就越大。 </p><p>

85、;　　運(yùn)用上述方法求解一般線性規(guī)劃問(wèn)題時(shí)，若原問(wèn)題的約束條件全部都是等式，需要迭代的次數(shù)可能比兩階段法多一次，但人工變量個(gè)數(shù)的減少將使迭代時(shí)間相應(yīng)縮短；當(dāng)原問(wèn)題中形式的約束條件個(gè)數(shù)較多時(shí)，使用上述方法的迭代次數(shù)將少于其他方法。</p><p>　　3.3單純形法的改進(jìn)算法2</p><p>　　在文獻(xiàn)的啟發(fā)下，本人認(rèn)為，根據(jù)所給問(wèn)題盡可能少的引入人工變量，可以使線性規(guī)劃問(wèn)題的計(jì)算變得更加簡(jiǎn)

86、單。</p><p>　　3.3.1兩階段法的簡(jiǎn)便算法</p><p>　　有些線性規(guī)劃問(wèn)題中，引進(jìn)松馳變量化為標(biāo)準(zhǔn)形后，約束條件方程組的系數(shù)矩陣并不含有m階單位矩陣，這樣就會(huì)給單純形解法的換基迭代帶來(lái)困難。線性規(guī)劃利用兩階段法解這類(lèi)問(wèn)題，尤其是一些具體的實(shí)際問(wèn)題時(shí)，對(duì)于加入的人工變量應(yīng)該根據(jù)問(wèn)題盡可能的少，使人工變量的個(gè)數(shù)小于(或等于)m。本人就線性規(guī)劃問(wèn)題的原問(wèn)題在加入人工變量 y中，

87、如何根據(jù)所給問(wèn)題盡可能的少引人人工變量，來(lái)說(shuō)明線性規(guī)劃問(wèn)題兩階段法的簡(jiǎn)便計(jì)算法。需要注意的是盡可能少引人人工變量y的同時(shí)，要保證使問(wèn)題的約束條件方程組的系數(shù)矩陣中有一個(gè)可行基，就要根據(jù)實(shí)際問(wèn)題，靈活運(yùn)用兩階段法。 </p><p><b>　　3.3.2舉例</b></p><p>　　線性規(guī)劃問(wèn)題： &l

88、t;/p><p>　　引入松弛變量，將問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式： </p><p>　　轉(zhuǎn)化后的形式?jīng)]有一個(gè)現(xiàn)成的可行基，因此要用兩階段法解，然后引入下面的輔助問(wèn)題。</p><p><b>　　其中，，</b></p><p>　　顯然，輔助問(wèn)題有一現(xiàn)成的可行基，，基變量為。</p><p&g

89、t;　　對(duì)應(yīng)于基的單純形表為</p><p><b>　?。?lt;/b></p><p>　　檢驗(yàn)數(shù)有正數(shù)，進(jìn)行換基迭代，得對(duì)應(yīng)于新基的單純形表為，：</p><p>　　檢驗(yàn)數(shù)仍有正數(shù)，繼續(xù)換基迭代，得到對(duì)應(yīng)于新基的單純形表：</p><p><b>　?。?lt;/b></p><p&

90、gt;　　檢驗(yàn)數(shù)仍然有正數(shù)，繼續(xù)換基迭代，得對(duì)應(yīng)于新基的單純形表：</p><p>　　單純形表的檢驗(yàn)數(shù)已全非正，所以基為輔助問(wèn)題的最優(yōu)基，，同時(shí)基的基變量無(wú)y變量，所以為原問(wèn)題的可行基，對(duì)應(yīng)的單純形表為：</p><p>　　檢驗(yàn)數(shù)已全非正，故為原問(wèn)題的最優(yōu)基，對(duì)應(yīng)的最優(yōu)解為，目標(biāo)函數(shù)的最小值為，所以原線性規(guī)劃問(wèn)題的最優(yōu)解為，目標(biāo)函數(shù)的最大值為。</p><p>

91、　　從上面的解題過(guò)程可以看出，對(duì)于線性規(guī)劃約束方程組的系數(shù)矩陣中不含有m階單位矩陣，求初始可行基的方法。問(wèn)題轉(zhuǎn)化后，注意約束條件的結(jié)構(gòu)，盡可能少的引入人工變量y，可以使方法更靈活些，也使得線性規(guī)劃問(wèn)題中的兩階段法的解題過(guò)程更加簡(jiǎn)單明了。</p><p>　　4 線性規(guī)劃增減約束條件的靈敏度分析 </p><p><b>　　4.1引言</b></p>&

92、lt;p>　　設(shè)線性規(guī)劃問(wèn)題 </p><p><b>　　（1）</b></p><p>　　現(xiàn)實(shí)世界是不斷發(fā)展變化的，主要體現(xiàn)在約束條件上，增加或減少約束條件則是隨時(shí)可能發(fā)生的。這將導(dǎo)致最優(yōu)方案的變化，如不與時(shí)俱進(jìn)，及時(shí)做相應(yīng)調(diào)整，必將造成經(jīng)濟(jì)損失。本文在靈敏度分析的基礎(chǔ)上，面對(duì)增加和減少約束條件的情形，給出新的最優(yōu)方案。<

93、/p><p><b>　　4.2增加約束條件</b></p><p>　　設(shè)增加的一個(gè)約束條件為 </p><p><b>　?。?）</b></p><p>　　在原問(wèn)題的最優(yōu)表給出的數(shù)據(jù)中，增加一行，然后用消去法，把這行中基變量的系數(shù)消為零，這顯然對(duì)檢驗(yàn)數(shù)沒(méi)有影響，可化為僅缺少一個(gè)基變量且的

94、問(wèn)題，故可用對(duì)偶單純形法規(guī)則，對(duì)新增之行確定主元，實(shí)行Gauss消元，便得一正解，然后用對(duì)偶單純形法迭代求最優(yōu)解。如果增加的約束不止一個(gè)，可一一處理。</p><p><b>　　4.3減少約束條件</b></p><p>　　減少約束條件的問(wèn)題，和增加約束條件一樣重要。減少約束條件還有特殊的經(jīng)濟(jì)意義。對(duì)于資源利用問(wèn)題來(lái)看，它意味著解除對(duì)某些資源的限制；而對(duì)于工廠里又

95、相當(dāng)于去掉一道工序，這些都為創(chuàng)新增值提供了途徑或指示了方向，故值得詳細(xì)討論。 </p><p>　　當(dāng)需要減少一個(gè)約束條件時(shí)，并不是將最優(yōu)表中與該約束相應(yīng)的行去掉就可以了，因?yàn)榇思s束的影響已通過(guò)Gauss消元施加在其它各行里了。如不重新求解，應(yīng)如何利用最優(yōu)表而達(dá)到去掉某些約束的目的呢? </p><p>　　設(shè)初始單純形表中含有一個(gè)單位矩陣，不妨假設(shè)它是由輔助變量形成的，現(xiàn)在要去掉原約

96、束條件中的一個(gè)約束，不妨設(shè)為第t個(gè)約束 ，采用以下步驟：</p><p>　　考慮原第t個(gè)約束所加輔助變量這一列，即（n+t）列，若為基變量，則去掉最優(yōu)表中第t個(gè)約束行和（n+t）列即可。否則，若該列某系列，取</p><p><b>　?。?）</b></p><p>　　若，則取 （4）<

97、;/p><p>　　然后以為主元實(shí)行Gauss消元，并去掉主元所在行與列。</p><p>　　檢查新檢驗(yàn)數(shù)是否仍非正：是，則已得去掉原第t個(gè)約束后的最優(yōu)解；否，用單純形法迭代求優(yōu)。</p><p><b>　　4.4舉例</b></p><p>　　某工廠去年根據(jù)市場(chǎng)需求和自身生產(chǎn)能力可以生產(chǎn)A、B兩種產(chǎn)品，當(dāng)時(shí)的條件如下

98、表所示：</p><p>　　表1 資源利用消耗表</p><p>　　據(jù)之可確定問(wèn)題的初始單純形表和最優(yōu)表如下：</p><p>　　表2 例題的初始單純形表和最優(yōu)解</p><p>　　今年，由于人民儲(chǔ)蓄的大幅度增加，銀行表示可以取消對(duì)該廠流動(dòng)資金供給量的限制。問(wèn)應(yīng)如何調(diào)整生產(chǎn)，才能獲得最大利潤(rùn)？ </p><p&

99、gt;　　由初始表4知關(guān)于流動(dòng)資金的約束方程是第4個(gè)，相應(yīng)松馳變量是，故考慮最優(yōu)表中一列，由（3）得 </p><p>　　故應(yīng)以為主元，實(shí)行Gauss消元，然后去掉4行，6列得：</p><p>　　這已經(jīng)是最優(yōu)表，按它進(jìn)行調(diào)整，可增加利潤(rùn)180-168=12（百元）。</p><p><b>　　4.5靈敏度分析</b></p>

100、<p>　　在如今市場(chǎng)經(jīng)濟(jì)的現(xiàn)實(shí)情況下，產(chǎn)品的市場(chǎng)價(jià)格條件、擁有的資源量以及企業(yè)的技術(shù)都有可能發(fā)生變化，這就需要管理者在這些條件發(fā)生變化時(shí)也隨著將原有生產(chǎn)計(jì)劃作相應(yīng)調(diào)整。</p><p>　　（1）產(chǎn)品的市場(chǎng)價(jià)格變化分析</p><p>　　產(chǎn)品市場(chǎng)發(fā)生變化，必將導(dǎo)致單件利潤(rùn)C(jī)也隨著變化，現(xiàn)分兩種情況研究。根據(jù)檢驗(yàn)數(shù)計(jì)算公式可知，它將會(huì)影響非基變量的檢驗(yàn)數(shù)。若想使原最優(yōu)解不變

101、，根據(jù)單純形法的計(jì)算原理可知，須，一旦，原最優(yōu)生產(chǎn)計(jì)劃將會(huì)發(fā)生改變，可以通過(guò)改進(jìn)最優(yōu)單純形表來(lái)求出新的最優(yōu)計(jì)劃。</p><p>　　（2）資源量的變化分析</p><p>　　資源量對(duì)應(yīng)的線性規(guī)劃模型中的，即求的靈敏度分析，由以前學(xué)的運(yùn)籌學(xué)的靈敏度分析知道，勞動(dòng)工時(shí)資源的擁有量在范圍內(nèi)變化時(shí)，原最優(yōu)生產(chǎn)計(jì)劃中安排生產(chǎn)的產(chǎn)品種類(lèi)不變；而原材料的擁有量在范圍內(nèi)變化時(shí)，原最優(yōu)生產(chǎn)計(jì)劃中安排生產(chǎn)

102、的產(chǎn)品種類(lèi)不變；一旦資源的擁有量超出上述各自的約束范圍，則可根據(jù)線性規(guī)劃的知識(shí)在原計(jì)劃的基礎(chǔ)上來(lái)重新調(diào)整生產(chǎn)計(jì)劃。</p><p>　?。?）技術(shù)條件的變化分析 </p><p>　　技術(shù)條件對(duì)應(yīng)的是線性規(guī)劃模型中的，生產(chǎn)某種產(chǎn)品的技術(shù)條件發(fā)生變化，將會(huì)影響到產(chǎn)品的檢驗(yàn)數(shù)或者現(xiàn)有生產(chǎn)產(chǎn)品法重新調(diào)整。 </p><p>　　5線性規(guī)劃在企業(yè)管理

103、中的應(yīng)用</p><p><b>　　5.1引言</b></p><p>　　一個(gè)企業(yè)要在市場(chǎng)競(jìng)爭(zhēng)中立于不敗之地，就必須改善經(jīng)營(yíng)管理，提高經(jīng)濟(jì)效益，其中包括怎樣合理的安排生產(chǎn)任務(wù)、合理配置資源，怎樣制定最優(yōu)的生產(chǎn)計(jì)劃，并對(duì)瞬息萬(wàn)變的市場(chǎng)信息及時(shí)作出反應(yīng)。隨著計(jì)算機(jī)技術(shù)的普及，線性規(guī)劃的數(shù)學(xué)方法在企業(yè)管理中的應(yīng)用范圍也越來(lái)越廣泛。</p><p>

104、;　　在企業(yè)生產(chǎn)和經(jīng)濟(jì)管理的領(lǐng)域中，人們常會(huì)遇到這樣的問(wèn)題，如何從一切可能的方案中選擇最好、最優(yōu)的方案，在數(shù)學(xué)上把這類(lèi)問(wèn)題稱(chēng)為最優(yōu)化問(wèn)題。在當(dāng)今的商品經(jīng)濟(jì)環(huán)境下，解決這類(lèi)問(wèn)題是一個(gè)關(guān)系到國(guó)計(jì)民生的重要問(wèn)題。線性規(guī)劃探討的問(wèn)題是在由所提出問(wèn)題的性質(zhì)決定的一系列約束條下，如何把有限的人力、物力、設(shè)備、資金等資源進(jìn)行合理的分配，制定出最憂(yōu)實(shí)施方案。在企業(yè)的各項(xiàng)活動(dòng)中，例如計(jì)劃、生產(chǎn)、運(yùn)輸、技術(shù)等問(wèn)題。為達(dá)到目的所采用的各種手段，從各種限制條件

105、的組合中，選擇出最為合理的計(jì)算方法，從而求得最佳結(jié)果。決策變量、約束條件、目標(biāo)函數(shù)是線性規(guī)劃的三要素。</p><p>　　5.2線性規(guī)劃模型的描述和建立</p><p>　　在運(yùn)籌學(xué)的發(fā)展過(guò)程中，線性規(guī)劃給了工業(yè)運(yùn)籌學(xué)一個(gè)重要的援助，它已經(jīng)被廣泛應(yīng)用于生產(chǎn)企業(yè)、化工、交通、郵電、建筑、醫(yī)藥等經(jīng)濟(jì)管理的領(lǐng)域中。企業(yè)、政府部門(mén)的許多工作都使用了線性規(guī)劃方法，并且取得了豐碩的成果。線性規(guī)劃被廣

106、泛應(yīng)用的原因主要有三個(gè)：（1）在各個(gè)領(lǐng)域中有大量的問(wèn)題可以或近似可以用線性規(guī)劃模型表示；（2）存在可用的求解線性規(guī)劃問(wèn)題的有效方法；（3）通過(guò)線性規(guī)劃模型，利用靈敏度分析容易處理數(shù)據(jù)的變化問(wèn)題。</p><p>　　5.2.1線性規(guī)劃模型的描述</p><p>　　線性規(guī)劃問(wèn)題是一個(gè)優(yōu)化問(wèn)題，其數(shù)學(xué)依據(jù)為：</p><p>　　用一組未知數(shù)表示某一方案，這組未知數(shù)的

107、一組定值代表一個(gè)具體方案，通常要求這些未知數(shù)取值是非負(fù)的。</p><p>　　存在一定的限制條件，這些限制條件可以用一組線性等式或不等式來(lái)表達(dá)。</p><p>　　都有一個(gè)目標(biāo)要求，并且這個(gè)目標(biāo)可以表示一組未知數(shù)的線性函數(shù)，根據(jù)問(wèn)題的不同，要求函數(shù)實(shí)現(xiàn)最大化或者最小化。</p><p>　　從而建立了線性規(guī)劃的數(shù)學(xué)模型：</p><p>

108、<b>　　滿(mǎn)足約束條件</b></p><p>　　5.2.2建立生產(chǎn)計(jì)劃決策分析的線性規(guī)劃模型</p><p>　　生產(chǎn)計(jì)劃決策分析的基本方法是：以利潤(rùn)最大化作為優(yōu)化目標(biāo)，明確未知變量，確定約束條件，建立線性規(guī)劃模型，最終實(shí)現(xiàn)企業(yè)效益最大化的生產(chǎn)計(jì)劃。其一般模式為：</p><p>　　目標(biāo)函數(shù)為利潤(rùn)P=銷(xiāo)售收入R-（成本+費(fèi)用）C<

109、/p><p>　　在各個(gè)約束條件下，使目標(biāo)函數(shù)達(dá)最大值。分析企業(yè)生產(chǎn)過(guò)程中的日產(chǎn)量情況，設(shè)模型的未知變量為企業(yè)生產(chǎn)產(chǎn)品種類(lèi)日產(chǎn)量，建立生產(chǎn)計(jì)劃決策分析線性規(guī)劃模型過(guò)程如下：</p><p>　　目標(biāo)函數(shù)。企業(yè)進(jìn)行生產(chǎn)計(jì)劃決策的目標(biāo)值是企業(yè)利潤(rùn)最大化。假設(shè)生產(chǎn)各種產(chǎn)品所獲得的銷(xiāo)售收入與所耗費(fèi)的產(chǎn)品成本和費(fèi)用均已知，則可以得出生產(chǎn)計(jì)劃問(wèn)題的目標(biāo)函數(shù)為：</p><p>　　

110、原材料約束。無(wú)論是生產(chǎn)何種產(chǎn)品都需要消耗一定的原材料，在實(shí)際中企業(yè)若需耗用多種原材料則可根據(jù)原材料的種類(lèi)，增添相應(yīng)約束條件即可，建立約束不等式：</p><p>　　其中：分別為生產(chǎn)第1,2,...,n種產(chǎn)品的單件原材料消耗量，為企業(yè)每可用的原材料總量。</p><p>　　生產(chǎn)能力約束。此約束具體表現(xiàn)為企業(yè)的可用工時(shí)或可用設(shè)備工時(shí)，而企業(yè)在一定時(shí)期內(nèi)可用工時(shí)是有限的，所以可建立如下約束不

111、等式：</p><p>　　其中：分別為生產(chǎn)第1,2,...,n種產(chǎn)品的單件消耗工時(shí)，為企業(yè)的日可用的工時(shí)、料總量。</p><p>　?。?）市場(chǎng)需求約束。為使問(wèn)題方便，假設(shè)企業(yè)生產(chǎn)的產(chǎn)品市場(chǎng)都有需求，即，無(wú)上限約束。若第種產(chǎn)品市場(chǎng)需求有限，最大需求為，則可增加約束。</p><p>　　（5）非負(fù)約束。生產(chǎn)實(shí)際中最多即為不生產(chǎn)產(chǎn)品，所以所有變量。</p&g

112、t;<p><b>　　5.3案例分析</b></p><p>　　為了研究生產(chǎn)計(jì)劃決策分析線性規(guī)劃模型在企業(yè)實(shí)際中的應(yīng)用，給出幾個(gè)算例并簡(jiǎn)要介紹線性規(guī)劃模型的建立及求解過(guò)程。</p><p><b>　　5.3.1案例1</b></p><p>　　應(yīng)用舉例：某企業(yè)用甲乙兩種原料生產(chǎn)A、B、C、D等4種產(chǎn)品

113、，每種產(chǎn)品的單位利潤(rùn)、原料消耗如下表所示，要使利潤(rùn)最大，應(yīng)如何安排A、B、C、D的產(chǎn)量？</p><p>　　設(shè)分別為A、B、C、D產(chǎn)品的產(chǎn)量，獲得最大利潤(rùn)，其線性規(guī)劃模型為：</p><p><b>　　約束條件為：</b></p><p><b>　　5.3.2案例2</b></p><p>　

114、　某車(chē)間生產(chǎn)A和B兩種儀器，生產(chǎn)A和B所需的原料分別為2個(gè)和3個(gè)單位，而所需的工時(shí)分別為4個(gè)和2個(gè)單位，目前可以用的原料為100個(gè)單位，工時(shí)為120個(gè)單位，并且已知每生產(chǎn)一臺(tái)A和B可以獲利分別為6元和4元，應(yīng)當(dāng)安排生產(chǎn)A和B各多少臺(tái)才能獲得最大的利潤(rùn)？</p><p>　　分析：設(shè)應(yīng)該安排生產(chǎn)的A和B的數(shù)量分別為臺(tái)、臺(tái)，則問(wèn)題是求解最大值函數(shù)：</p><p>　　編寫(xiě)MATLAB程序&l