線性規(guī)劃算法的改進及在企業(yè)管理中的應(yīng)用【開題報告+文獻綜述+畢業(yè)論文】

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

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

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

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

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

6、　研究的基本內(nèi)容：</b></p><p>　　線性規(guī)劃問題的中單純形法和兩階段法的算法改進</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增減約束條件對線性規(guī)劃的影響</p><p><b>　　2.2算例分析</b></p><p><b>　　2.3靈敏度分析</b></p><p>　　2.3.1產(chǎn)品市場價格變化分析</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>　　擬解決的主要問題：</b></p><p>　　通過上述三個部分的闡述，主要列舉了線性規(guī)劃方法的介紹及算法的異同點，通過比較分析說明線性規(guī)劃算法改進后的優(yōu)點并應(yīng)用舉例。同時分析說明增減約束條件對線性規(guī)劃的影響及實際應(yīng)用的分析。論述了線性規(guī)劃對企業(yè)管理的重大意義，通過合理的方法應(yīng)用，以期我國企業(yè)管理能夠得到更好的發(fā)展。</p>

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

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

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

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

15、的應(yīng)用[J]. 大眾科技,2004,12.</p><p>　　[11]. 雷紅. 淺談線性規(guī)劃在企業(yè)管理中的應(yīng)用[J]. 科技情報開發(fā)與經(jīng)濟,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è)論文文獻綜述</b></p><p><b>　　數(shù)學(xué)與應(yīng)用數(shù)學(xué)</b></p><p>　　線性規(guī)劃算法的改進及在企業(yè)管理中的應(yīng)用</p><p>　　線性規(guī)劃是運籌學(xué)最基本、運用最廣泛的分支，是其他運籌學(xué)問題研究的基礎(chǔ)。在20世紀50年代到60年代期間，運籌學(xué)領(lǐng)域出

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

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

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

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

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

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

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

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

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

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

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

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

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

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

33、劉心. 線性規(guī)劃增減約束條件的靈敏度分析[J]. 運籌與管理2007,4.</p><p>　　[10]. 王昌貴. 線性規(guī)劃在企業(yè)管理中的應(yīng)用[J]. 大眾科技,2004,12.</p><p>　　[11]. 雷紅. 淺談線性規(guī)劃在企業(yè)管理中的應(yīng)用[J]. 科技情報開發(fā)與經(jīng)濟,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è)計</b></p><p><b>　?。?0 屆）</b></p><p>　　線性規(guī)劃算法的改進及在企業(yè)管理中的應(yīng)用&l

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

38、用。線性規(guī)劃的“線性”特點，簡化了數(shù)學(xué)模型的構(gòu)造和解題方法，容易被一般未具有高等數(shù)學(xué)知識的各級企業(yè)管理人員所掌握應(yīng)用，特別是計算機的廣泛應(yīng)用，線性規(guī)劃的在企業(yè)管理中的應(yīng)用范圍更加廣泛和深入，漸漸成為管理人員必須掌握的一門現(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ī)劃簡介12</p><p>　　2 線性規(guī)劃問題單純形法的改進算法12</p><p>　　2.1問題的提出12</p><p>　　2.2單純形法的改進算法113</p><p>　　2.2.1算法介紹13</p><p>　　2.2.2算法分析14<

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

45、20</p><p>　　3.2兩階段法改進算法121</p><p>　　3.2.1算法介紹21</p><p>　　3.2.2舉例23</p><p>　　3.3單純形法的改進算法224</p><p>　　3.3.1兩階段法的簡便算法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)計劃決策分析的線性規(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>　　參考文獻37</b></p><p>　　致謝錯誤!未定義書簽。</p><p>　　附錄錯誤!未定義書簽。</p><p><b>　　引言</b></p><p><b>　　線性規(guī)劃簡介</b></p><p

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

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

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

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

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

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

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

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

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

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

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

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

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

63、　同時我們是在每一個有基行中找第一個非零元為主元進行消去，這樣可以保證選擇的主元不在同一列。對于無基行，我們在步驟3中點明了以下三種情況 ： </p><p>　?。?）當(dāng)無基行在迭代表中對應(yīng)的，均小于等于零時，沒有可行解。因為無基行對應(yīng)的常數(shù)項大于零，且左邊小于等于0而右邊大于零，這樣就矛盾了；</p><p>　?。?）在無基行中選擇一個大于零的項，如果這項對應(yīng)的列中所有項(取從1到

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

102、的產(chǎn)品種類不變；一旦資源的擁有量超出上述各自的約束范圍，則可根據(jù)線性規(guī)劃的知識在原計劃的基礎(chǔ)上來重新調(diào)整生產(chǎn)計劃。</p><p>　?。?）技術(shù)條件的變化分析 </p><p>　　技術(shù)條件對應(yīng)的是線性規(guī)劃模型中的，生產(chǎn)某種產(chǎn)品的技術(shù)條件發(fā)生變化，將會影響到產(chǎ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>　　一個企業(yè)要在市場競爭中立于不敗之地，就必須改善經(jīng)營管理，提高經(jīng)濟效益，其中包括怎樣合理的安排生產(chǎn)任務(wù)、合理配置資源，怎樣制定最優(yōu)的生產(chǎn)計劃，并對瞬息萬變的市場信息及時作出反應(yīng)。隨著計算機技術(shù)的普及，線性規(guī)劃的數(shù)學(xué)方法在企業(yè)管理中的應(yīng)用范圍也越來越廣泛。</p><p>

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

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

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

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

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

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

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

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

112、t;<p><b>　　5.3案例分析</b></p><p>　　為了研究生產(chǎn)計劃決策分析線性規(guī)劃模型在企業(yè)實際中的應(yīng)用，給出幾個算例并簡要介紹線性規(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)品的單位利潤、原料消耗如下表所示，要使利潤最大，應(yīng)如何安排A、B、C、D的產(chǎn)量？</p><p>　　設(shè)分別為A、B、C、D產(chǎn)品的產(chǎn)量，獲得最大利潤，其線性規(guī)劃模型為：</p><p><b>　　約束條件為：</b></p><p><b>　　5.3.2案例2</b></p><p>　

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