1、<p>　　本科畢業(yè)論文（設計）模板</p><p>　　本科畢業(yè)論文(設計)</p><p>　　論文題目： 線性規(guī)劃問題的解法 </p><p>　　學生姓名： </p><p>　　學 號： 1004970101 </p

2、><p>　　專 業(yè)： 數(shù)學與應用數(shù)學 </p><p>　　班 級： 數(shù)學 1001 </p><p>　　指導教師： </p><p>　　完成日期： 2014年5月20日</p><p><

3、;b>　　線性規(guī)劃問題的解法</b></p><p><b>　　內(nèi) 容 摘 要</b></p><p>　　線性規(guī)劃，是在運籌學的研究歷程中涉及早、發(fā)展快、應用廣的一個核心部分，它是幫助人類進行科學管理的一種數(shù)學方法,是研究線性約束條件下線性目標函數(shù)的極值問題的數(shù)學理論和方法，英文縮寫LP。為合理地利用有限的人力、物力、財力等資源作出的最優(yōu)決策、提

4、供科學的依據(jù)。</p><p>　　通常，線性目標函數(shù)在對應約束條件下的最大值和最小值的問題，統(tǒng)稱為線性規(guī)劃問題。求解線性規(guī)劃問題的基本方法是單純形法，現(xiàn)已有單純形法的標準軟件，例如MATLAB等。利用計算機，可以解決線性規(guī)劃的問題。為了提高求解效率，線性規(guī)劃的解法又有人工變量法、對偶單純形法。對于只有兩個或三個變量的簡單的線性規(guī)劃問題，也可采用圖解法求解。</p><p>　　本篇論文主

5、要針對線性規(guī)劃問題的一般解法和特殊解法進行歸納、總結和改進，并簡單闡述線性規(guī)劃的常用模型及應用。</p><p>　　關鍵詞：線性規(guī)劃 目標函數(shù) 一般解法 特殊解法 單純形法 </p><p>　　The Solution to Linear Programming Problem</p><p><b>　　Abstract&l

6、t;/b></p><p>　　Linear programming, is a core part which involved in the earlier, rapid development,wide application in the course of operations research study. It is a kind of mathematical method that it

7、can help people to make scientific management . It also is mathematical theory and method that research linear objective function extremum problems under the condition of linear constraints,English abbreviation is LP. It

8、 makes the optimal decision and provides scientific basis for reasonable use of the limited</p><p>　　Generally, the maximum and minimum value problems about linear objective function in the corresponding con

9、ditions referred to as linear programming problem. The basic method to solve the linear programming problem is simples method. Now it has had standard software of simples method, such as MATLAB. We can take advantage of

10、computer to solve linear programming problem . In order to improve the efficiency of solving, the solutions of linear programming also have artificial variable method, dual s</p><p>　　This thesis focused on

11、summarize and improvements which the general solution and special solution of linear programming problems. Simultaneously briefly discusses commonly used linear programming model and application.</p><p>　　K

12、ey words：linear programming linear objective function general solution special </p><p>　　solutions simples method </p><p><b>　　目錄</b></p><p><b>　

13、　序 言1</b></p><p><b>　　一、 研究基礎1</b></p><p>　?。ㄒ唬┙鉀Q線性規(guī)劃問題的一般思路1</p><p>　?。ǘ┚€性規(guī)劃數(shù)學模型建立的條件1</p><p>　?。ㄈ┚€性規(guī)劃數(shù)學模型的建立1</p><p>　?。ㄋ模┚€性規(guī)劃數(shù)學

14、模型的特點2</p><p>　?。ㄎ澹┚€性規(guī)劃解的有關概念及其關系2</p><p>　?。㎜P模型的表達形式2</p><p>　　二、 線性規(guī)劃的一般解法及實例3</p><p><b>　?。ㄒ唬﹫D解法3</b></p><p><b>　?。ǘ﹩渭冃畏?<

15、;/b></p><p>　?。ㄈ┤斯ぷ兞糠?</p><p><b>　　1.大M法8</b></p><p>　　2. 兩階段法10</p><p>　?。ㄋ模ε紗渭冃畏?2</p><p>　　三、 線性規(guī)劃的特殊求解及實例14</p><p>　

16、　運輸問題——表上作業(yè)法14</p><p>　　四、 模型及其解法的應用17</p><p><b>　　五、 總結18</b></p><p>　　參 考 文 獻19</p><p><b>　　序 言</b></p><p>　　在現(xiàn)實經(jīng)濟活動中，我們不斷碰到諸

17、如此類的問題：什么是最好的決策或者最佳的方案。例如企業(yè)在外在條件不變的情況下下，如何通過合理安排，改進生產(chǎn)計劃，合理安排人、物和資源，使得成本最低。這些問題都可以建立一些數(shù)學模型，轉(zhuǎn)化為線性規(guī)劃問題，通過數(shù)學運算得到最佳解決方法。</p><p>　　線性規(guī)劃在工業(yè)、商業(yè)的管理中，可以用來解決以下問題：人員分配問題、生產(chǎn)計劃問題，配料問題、動態(tài)投資問題以及運輸問題等。實際上存在大量的具體問題，但一般解決的問題為以

18、下兩種：</p><p>　　一種是給定了一定數(shù)量的資源，研究如何合理地使用它們，才能使完成的任務量最大。</p><p>　　另一種是確定了一項任務以后，研究如何統(tǒng)籌安排，能夠使完成此項任務所耗費的資源量為最少。</p><p>　　實際上，上述兩類問題本質(zhì)是相同的，都是求問題的最優(yōu)解（max或min），只是求解方向不同。</p><p>

19、<b>　　研究基礎</b></p><p>　?。ㄒ唬┙鉀Q線性規(guī)劃問題的一般思路</p><p>　　1.對問題進行系統(tǒng)分析，搞清決策什么和決策目標是什么？</p><p>　　2.明確影響決策目標（大小變化）的因素（人為可控制的，決策變量），確定決策變量對目標（函數(shù)）影響系數(shù)，且與目標函數(shù)是否成線性關系。</p><p&

20、gt;　　3.制約目標的條件有哪些？</p><p>　　4.建立線性規(guī)劃數(shù)學模型。</p><p>　　5.模型求解與解的調(diào)試。</p><p>　　6.方案實施與調(diào)整。</p><p>　?。ǘ┚€性規(guī)劃數(shù)學模型建立的條件[1]</p><p>　　1.優(yōu)化條件：線性規(guī)劃問題要達到的目標能夠用線性目標函數(shù)描述，且能

21、夠用極值（max或min）來表示。</p><p>　　2.限定條件：滿足目標需存在一些限定，這些限制能夠用決策變量的線性等式或不等式表示。</p><p>　　3.選擇條件：存在多重選擇的方案供決策者參考決定，以便找出最優(yōu)方案。</p><p>　?。ㄈ┚€性規(guī)劃數(shù)學模型的建立</p><p>　　從實際問題中建立數(shù)學模型一般有一下三個步驟

22、：</p><p>　　1.找到?jīng)Q策變量，根據(jù)影響達到目的的因素；</p><p>　　2.確定目標函數(shù)，取決于決策變量和要達到的目的之間的函數(shù)關系；</p><p>　　3.確定決策變量所要滿足的約束條件，根據(jù)決策變量所受限的條件。</p><p>　?。ㄋ模┚€性規(guī)劃數(shù)學模型的特點</p><p>　　1.每個模型都

23、有一定量的決策變量（，，……，），其中n為決策變量個數(shù)。它的一組數(shù)值表示一種決策方案，同時決策變量一般是非負的。</p><p>　　2.目標函數(shù)是決策變量的線性函數(shù)，根據(jù)具體問題可能為最大化（max）或最小化（min），二者統(tǒng)稱為最優(yōu)化（opt）。</p><p>　　3.約束條件也是決策變量的線性函數(shù)。</p><p>　　我們得到的數(shù)學模型的目標函數(shù)被稱為線性

24、函數(shù)，約束條件為線性等式或不等式時，稱此數(shù)學模型為線性規(guī)劃模型。</p><p>　?。ㄎ澹┚€性規(guī)劃解的有關概念及其關系[2]</p><p><b>　　有關概念</b></p><p>　?。?）可行解：能夠滿足約束條件的全部解。</p><p>　?。?）最優(yōu)解：使某線性規(guī)劃的目標函數(shù)達到最優(yōu)值（最大值或最小值）的

25、任一可行解。</p><p>　　（3）基本解:在約束方程組系數(shù)矩陣中找到一個基，令這個基的非基變量為零，再求解這個m元線性方程組就可得到唯一的解，這個解稱之為線性規(guī)劃的基本解。</p><p>　?。?）基本可行解：滿足非負約束的基本解稱為基本可行解。</p><p><b>　　解之間的關系</b></p><p>

26、　　（1）最優(yōu)解一定是可行解，但可行解不一定是最優(yōu)解。</p><p>　?。?）基本解不一定是可行解，可行解也不一定是基本解。</p><p>　?。?）基本可行解一定是可行解，但可行解不一定是基本可行解。</p><p>　?。?）基本可行解一定是基本解，但基本解不一定是基本可行解。</p><p>　　（5）最優(yōu)解不一定是基本解，基本解

27、也不一定是最優(yōu)解。</p><p>　?。㎜P模型的表達形式</p><p><b>　　1.一般模型</b></p><p>　　決策變量：X=（x1,x2,......xn）T .</p><p>　　目標函數(shù)：max(min)z=c1x1+c2x2+......+cnxn .</p><p&

28、gt;<b>　　約束條件：</b></p><p><b>　　2.簡約模型</b></p><p>　　max(min)z=.</p><p><b>　　.</b></p><p><b>　　.</b></p><p>&l

29、t;b>　　3.矩陣形式</b></p><p>　　max(min)z=CX. </p><p><b>　　AX≤b.</b></p><p><b>　　X≥0.</b></p><p><b>　　其中，</b></p><p>

30、;　　A=m×n， X=.</p><p>　　C=(c1 c2 ... Cn)， b=.</p><p>　　線性規(guī)劃的一般解法及實例</p><p><b>　　（一）圖解法[3]</b></p><p><b>　　1.圖解法原理</b></p&g

31、t;<p>　　圖解法，通過作圖的形式來求解線性規(guī)劃問題的方法。此方法簡單、直觀，一般只適用于具有兩個決策變量的線性規(guī)劃問題。</p><p>　　選擇用圖解法對實際線性規(guī)劃問題求解，基本步驟為：</p><p>　　（1）建立直角坐標系；</p><p>　?。?）根據(jù)約束條件畫出可行域；</p><p>　　（3）劃過坐標原

32、點的目標函數(shù)線；</p><p>　?。?）判定目標函數(shù)值的增大方向；</p><p>　?。?）目標函數(shù)線向著增大方向平移，與可行域相交，有最大目標函數(shù)值的頂點，即為線性規(guī)劃問題的最優(yōu)解。</p><p><b>　　2.圖解法實例</b></p><p>　　例1 某場生產(chǎn)兩種產(chǎn)品，下表給出了制造產(chǎn)品的單位所需資源

33、及單位產(chǎn)品利潤。問：應如何安排生產(chǎn)計劃才能使總利潤最大？</p><p><b>　　表-1</b></p><p>　　解 決策變量：設產(chǎn)品I、II的產(chǎn)量分別為x1、x2</p><p>　　設利潤為z，則有目標函數(shù)：max z=2x1+3x2 . </p><p><b>　　約束條件：</b&

34、gt;</p><p>　　約束條件及目標函數(shù)在坐標系中的表現(xiàn)： </p><p>　　由圖解法中的坐標圖可得出：</p><p>　　最優(yōu)解X*=（2,4）T,</p><p><b>　　最優(yōu)值Z*=14.</b></p><p><b>　　3.圖解法解的種類</b>

35、;</p><p>　　由圖解法原理及實例可以得出，線性規(guī)劃問題的解有4種：</p><p>　　（1）有唯一最優(yōu)解。</p><p><b>　?。?）有多重解。</b></p><p><b>　　（3）有無界解。</b></p><p><b>　?。?）無可

36、行解。</b></p><p><b>　　4.圖解法求解總結</b></p><p>　　（1）圖解法求解線性問題的最優(yōu)解一般在可行域的頂點中尋找。</p><p>　?。?）利用圖解法進行求解時只可能出現(xiàn)四種解。</p><p>　?。?）線性規(guī)劃的可行域通常為是凸集（凸多邊形）。</p>

37、<p>　　（4）解題思路是，先找出凸集的任一頂點，計算函數(shù)值，再與周圍頂點的函數(shù)值相比較。如果不是最大，繼續(xù)比較，直至找出最優(yōu)解。</p><p><b>　?。ǘ﹩渭冃畏?lt;/b></p><p><b>　　1.單純形法原理</b></p><p>　　單純形算法必須解決的三個問題：</p>

38、<p>　?。?）如何確定初始的可行解？</p><p>　?。?）如何進行解的最優(yōu)性判別？</p><p>　?。?）如何尋找改進的可行解？</p><p>　　單純性方法的基本思路：</p><p>　　單純形法的核心：變量迭代。</p><p>　　2.單純形法的步驟[4]</p><

39、;p>　?。?）將線性規(guī)劃問題化成標準型。</p><p>　?。?）找出或構造一個m階單位矩陣作為線性規(guī)劃問題的初始可行基，建立初始單純性表。</p><p>　　（3）計算各非基變量xj的檢驗數(shù),若所有≤0，則問題已得到最優(yōu)解，停止計算，否則轉(zhuǎn)入下步。</p><p>　　（4）在大于0的檢驗數(shù)中，做某個所對應的系數(shù)列向量≤0，則此問題是無界解，停止計算，

40、否則轉(zhuǎn)入下步。</p><p>　?。?）根據(jù)原則，確定為換入變量（進基變量），再按θ規(guī)則計算：確定為換出變量。建立新的單純形表，此時及變量中取代了的位置。</p><p>　?。?）以為主元素進行迭代，把所對應的列向量變?yōu)閱挝涣邢蛄?，即變?yōu)?，同列中其他元素為0，然后轉(zhuǎn)到第（3）步。</p><p><b>　　3.單純形法實例</b><

41、;/p><p>　　例2 用一般單純形法求解下列線性規(guī)劃問題</p><p>　　max Z =3+4</p><p>　　解：將問題化為標準型，加入松弛變量，，則標準型如下：</p><p>　　max Z =3+4</p><p><b>　　建立初始單純性表：</b></p>&

42、lt;p><b>　　表-2</b></p><p><b>　　檢驗數(shù)計算公式：</b></p><p><b>　　=cj-.</b></p><p>　　由公式計算得=3，=4兩個檢驗數(shù)均大于0，故進行下一步，從一個基可行解轉(zhuǎn)換到兩一個目標值更大的基可行解。</p><

43、p>　　由于>,且=40/1=40，=30/3=10，>，所以以作為換入變量，以作為換出變量。新的單純形表形成，如下。</p><p><b>　　表-3</b></p><p><b>　　由單純型表得出：</b></p><p>　　最優(yōu)解X=（18,4,0,0）T,</p><p

44、><b>　　最優(yōu)值Z=70.</b></p><p>　　4.單純形法基本原理</p><p>　　定理1 若線性規(guī)劃問題存在可行解，則該問題的可行域是凸集。</p><p>　　定理2 線性規(guī)劃問題的基可行解X對應可行域（凸集）的頂點。</p><p>　　定理3 若問題存在最優(yōu)解，一定存在一個基可行解是最優(yōu)解

45、。</p><p>　　5.最優(yōu)解的判別定理[5]</p><p>　?。?）唯一最優(yōu)解的判斷：最優(yōu)表中所有的非基變量的檢驗數(shù)非零，則線性規(guī)劃問題具有唯一最優(yōu)解。</p><p>　?。?）多重最優(yōu)解的判斷：最優(yōu)表中存在非基變量的檢驗數(shù)為零，則線性規(guī)劃問題具有多重最優(yōu)解。</p><p>　?。?）無界解的判斷：某個>0且（i=1,2,

46、...,m）,則線性規(guī)劃具有無界解。</p><p>　?。ㄈ┤斯ぷ兞糠╗7]</p><p>　　若原線性規(guī)劃問題的系數(shù)矩陣中沒有初始基可行解（及形成單位矩陣），則先對約束條件的系數(shù)矩陣進行初等變換，形成單位矩陣后，也就形成了初始基可行解，看是否達到最優(yōu)解，進行運算。</p><p>　　例3 求解下列線性規(guī)劃問題</p><p>　　

47、max Z=3+2-</p><p>　　解 先將其標準化得： </p><p>　　max Z=3+2-</p><p>　　其約束條件的系數(shù)矩陣：，系數(shù)矩陣中有一個單位向量，按照一般單純形法方法，故需要進行初等變換，使得約束條件中出現(xiàn)完整的單位矩陣。得到如下矩陣：</p><p>　　最優(yōu)解X=（31/3,13,1

48、9/3，0,0）T,</p><p>　　最優(yōu)值Z=152/3.</p><p>　　若用初等變換方法無法得出單位矩陣（即初始基可行解），那么在每個約束方程中加入人工變量便可形成一組向量，這種方法即為大M法或兩階段法。</p><p><b>　　1.大M法</b></p><p>　　人們?yōu)榱俗尲尤肴斯ぷ兞亢缶€性規(guī)劃問

49、題的最優(yōu)目標函數(shù)值不受影響，我們預設人工變量為一個很大的負價值系數(shù)-M（M為任意大的正數(shù)）。</p><p>　　例3 用大M法求解線性規(guī)劃問題。</p><p>　　max Z=3+2-</p><p>　　解 在約束條件中加入剩余變量與松弛變量：</p><p>　　max Z=3+2-</p><p>　　其

50、中可作為一個基變量。</p><p>　　將上述標準型化為人工變量單純形法模型：</p><p>　　max Z=3+2--M-M</p><p>　　約束條件中分別加入、，目標函數(shù)中加入-M-M項。利用單純形表，進行求解如下：</p><p><b>　　表-4</b></p><p><

51、b>　　由單純形表得出：</b></p><p>　　最優(yōu)解X=（31/3,13,19/3,0，0）T,</p><p>　　最優(yōu)值Z=152/3.</p><p><b>　　兩階段法</b></p><p><b>　　兩階段法基本思路：</b></p><

52、p>　　第一階段，先不考慮原問題是否最在基可行解，先求解一個目標函數(shù)中只包含人工變量的線性規(guī)劃問題，即令目標函數(shù)中其他變量的系數(shù)取零，人工變量的系數(shù)取某個正的常數(shù)，在保持原問題約束條件不變的情況下，求這個目標函數(shù)極小化的解。然后利用單純形法求解所構造的新模型，若w=0，這時，若基變量中不含人工變量或人工變量取值為0，則說明問題存在基可行解，否則停止計算，原問題無可行解。</p><p>　　第二階段，利用用

53、單純形法求解剩余問題。</p><p>　　例4 用兩階段法求解例3線性規(guī)劃問題。</p><p>　　max Z=3+2-</p><p>　　解 在約束條件中加入剩余變量與松弛變量得：</p><p>　　max Z=3+2- </p><p>　　其中可作為一個基變量。</p><p>

54、;　　在約束方程中加入人工變量，后，得出第一階段問題為：</p><p><b>　　min w=+</b></p><p>　　用單純形法求解，得到第一階段問題的計算表如下：</p><p><b>　　表-5</b></p><p>　　由表中可以看出，最優(yōu)解X=（0,3/5,11/5,0,31

55、/5）T，最優(yōu)值w=0.</p><p>　　最優(yōu)解為原問題的一組基可行解，作為初始基可行解，第二階段問題為：</p><p>　　max Z=3+2-</p><p>　　用單純形法計算得到下表：</p><p><b>　　表-6</b></p><p>　　最優(yōu)解X=（31/3,13,19/

56、3,0，0）T,</p><p>　　最優(yōu)值Z=152/3.</p><p><b>　　3.人工變量法總結</b></p><p>　　在實際中，有些線性規(guī)劃問題的模型中并不含有單位矩陣，為了得到一組基向量和初始基可行解，在約束條件等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量成為人工變量，主要為大M法和兩階段法求解。</p&

57、gt;<p>　　在大M法中，M是一個很大的實際不存在的正數(shù)，不必須是具體的數(shù)值，可看做它能大于給定的任何一個確定的數(shù)。但是再用計算機處理數(shù)據(jù)時，只能用很大的數(shù)代替M，可能造成計算機上的錯誤，這時則采用兩階段法。</p><p>　　人工變量法中解的判別：</p><p>　?。?）唯一最優(yōu)解的判斷：最優(yōu)表中所有的非基變量的檢驗數(shù)非零，則該問題具有唯一最優(yōu)解。</p&g

58、t;<p>　?。?）多重最優(yōu)解的判斷：最優(yōu)表中存在非基變量的檢驗數(shù)為零，則線性規(guī)劃問題有多重最優(yōu)解。</p><p>　?。?）無界解的判斷：某個>0且（i=1,2,...,m）,則線性規(guī)劃具有無界解。</p><p>　?。?）無可行解的判別：當用大M單純形法計算得到最優(yōu)解并且出現(xiàn)所有的時，無解。</p><p>　?。?）退化解的判別：存在

59、某個基變量為零的基本可行解。</p><p><b>　?。ㄋ模ε紗渭冃畏?lt;/b></p><p>　　1.對偶單純形法基本思路[5]</p><p>　?。?）找出一個對偶問題的可行基。</p><p>　?。?）保持對偶問題為可行解的條件下，判斷XB是否可行（XB=b為非負），若可行則有最優(yōu)解，結束計算。若不可行進

60、行下一步。</p><p>　?。?）通過變換基解，保持對偶問題為可行解的條件下，尋找LP的下一個基本可行解。</p><p>　　2.對偶單純形法實例</p><p>　　例5 求解下列問題:</p><p>　　min Z=9+12+15</p><p>　　解 因?qū)ε紗栴}可行，故將模型轉(zhuǎn)化為求最大化問題，約束

61、方程化為標準型，得出一組基本解。</p><p>　　max Z*=-9-12-15</p><p>　　利用單純形法列出如下單純形表：</p><p><b>　　表-7</b></p><p>　　由表中可得：-10 > -12 > -14，故以-14所在行變量為換出變量，并以此行為主行，此行中有三個負數(shù)

62、，以為標準，得-15/-5 < -9/-1 < -12/-1，故以為換入變量，進行變量迭代。</p><p><b>　　表-8</b></p><p>　　由表中可得：以為換入變量，為換出變量。再次進行變量迭代。</p><p><b>　　表-9</b></p><p>　　由表中可

63、得：>>，故以為換入變量，為換出變量。繼續(xù)進行變量迭代。</p><p><b>　　表-10</b></p><p>　　由表-7—表-10的一系列計算可得：</p><p>　　原問題最優(yōu)解X*=（2,2,2,0,0,0），最優(yōu)值Z*=72.</p><p>　　其對偶問題最優(yōu)解Y*=（-1/3，-3，-

64、7/3），最優(yōu)值W*=72.</p><p>　　3.對偶單純形法總結[9]</p><p>　　對偶單純形法是求解線性規(guī)劃問題的一種方法，并非去求對偶問題的最優(yōu)解。</p><p>　　初始表應當令對偶問題可行，也就是說檢驗數(shù)滿足最優(yōu)判別準則。</p><p>　　對偶單純形法與普通單純形法的換基順序不一樣，普通單純形法是先確定進基變量后確

65、定出基變量，而偶單純形法是先確定出基變量后確定進基變量。</p><p>　?。?）對偶單純形法通常用于需要進行靈敏度分析的線性規(guī)劃問題，利用對偶單純形法的最終表進行靈敏度分析，進而解決線性規(guī)劃問題。</p><p>　　線性規(guī)劃的特殊求解及實例</p><p>　　運輸問題——表上作業(yè)法[8]</p><p>　　運輸問題本質(zhì)上也是一種線性

66、規(guī)劃問題，其大體思路與單純形法本質(zhì)思路一致，只是由于運輸問題的變量多，因而不能用單純形法，而是用表上作業(yè)法進行求解。運輸問題就是研究在保證供需各方合理要求的前提下，如何合理安排調(diào)運，而取得最好的經(jīng)濟效益問題。 </p><p>　　對于求解運輸問題，表上作業(yè)法是既簡便又高效的方法，它是一種迭代法，迭代步驟為：先找出一個初始解（初始調(diào)運方案）；再對現(xiàn)形解作最優(yōu)性判別；若此解解并非最優(yōu)解，就在運輸表上對它進行調(diào)整改進

67、，得出一個新解；再次進行判別和改進；直至得到運輸問題的最優(yōu)解為止。</p><p>　　表上作業(yè)法中，在確定初始基可行解時最常用有三種方法：最小元素法，西北角法，沃格爾法。在解的最優(yōu)性檢驗中，閉回路法是最常用的方法。</p><p>　　例6 某公司有3個生產(chǎn)同類產(chǎn)品的工廠（產(chǎn)地），產(chǎn)品由4個銷售點（銷地）賣出，各工廠的生產(chǎn)量、各銷售點的銷售量（假定單位均設為t）以及各工廠到各銷售點的單

68、位運價（元/t）均列于于下表，使求解產(chǎn)品如何調(diào)運才能使總運費最小。</p><p><b>　　表-11</b></p><p>　　由于總產(chǎn)量與總銷量均為48，故此運輸問題為產(chǎn)銷平衡運輸問題。</p><p>　　用表示由第i個產(chǎn)地運往第j個銷地的產(chǎn)品數(shù)量，即可寫出該問題的數(shù)學模型：</p><p>　　=4+12+4

69、+11+2+10+3+9+8+5+11+6.</p><p>　　運輸問題解的每一個分量，都相應對應表中的一個方格。得出運輸問題的一個基可行解后，就將基變量的數(shù)值填入相應的格內(nèi)。</p><p>　　1.第一步：尋找初始基可行解[10]</p><p>　　為了減少費用，通常優(yōu)先考慮單位運價最少（或運距最短）的供銷業(yè)，最大限度地滿足其供銷量。即對所有的i和j，找出，

70、并將的物品量由供應給。</p><p>　　若= ,則產(chǎn)地的可供物品已用完，那么此后不再繼續(xù)考慮這個產(chǎn)地，且的需求量由減少為-。</p><p>　　若= ，則銷地的需求以全部得到滿足，以后不再繼續(xù)考慮這個銷地，且的可供量由減少為-。</p><p>　　第一步：因到的單位運價2最小，故首先考慮這項運輸業(yè)務。由于min(,)==8,故在表中（，）格中填8，此時的可供

71、量為-=2；的需求量全部得到滿足，在今后的運輸量分配時不再考慮，故劃去列。 </p><p>　　第二步：在尚未劃去的各格中在尋求最小的單位運價，為3對應（，），供應后的供應能力為2小于=12，故在格中填2。此時的供應能力用盡，劃去。</p><p>　　第三步：在（，）格中填入10，劃去列。</p><p>　　第四步：在（，）格中填入14，劃去列。</p&

72、gt;<p>　　第五步：在（，）格中填入8，劃去行。</p><p>　　第六步：在未被劃去的格種填入6。使得供應量和的需求量同時得到滿足，并同時劃去行和列。此時所有的格都被劃掉，所有供銷要求均得到滿足。故得到如下表：</p><p><b>　　表-12</b></p><p><b>　　·</b&

73、gt;</p><p>　　這是得到了該運輸問題的一個初始解：=10，=6，=8，=2，=14，=8，其他變量全等于0。</p><p>　　由此得到總運費=246，</p><p>　　這個解滿足所有約束條件，其非零變量的個數(shù)為6。</p><p>　　2.第二步：解的最優(yōu)性檢驗</p><p>　　如果想確定運輸問

74、題的某個解是否為最優(yōu)解，可仿照一般單純形法，檢驗這個解的各非基變量的檢驗數(shù)，若有某個空格的檢驗數(shù)為負，說明當前解不是最優(yōu)解。若所有的檢驗數(shù)均為0或正數(shù)，那么這個解就是最優(yōu)解。經(jīng)過各個有空格的數(shù)字的加減，形成閉合回路，則數(shù)字稱為其檢驗數(shù)。</p><p>　　上述例題中，經(jīng)計算得各個空格的檢驗數(shù)如下：</p><p>　　=-+-+-=10-5+6-11+4-3=1，以此類推得=2，=-1，

75、=10，=12</p><p>　　由于=-1<0，故上述解并非最優(yōu)解。</p><p>　　3.第三步：解的改進</p><p>　　以為換入變量，尋找換入變量在運輸表中的閉回路。由于=-1<0，故以為換入變量，對應的閉回路如下表：</p><p><b>　　表-13</b></p><

76、;p>　　該閉合回路的偶數(shù)頂點位于格（，），（，），由于==2故作如下調(diào)整：</p><p>　?。杭?， ：減2，</p><p>　?。杭?， ：減2.</p><p>　　故新的基可行解是=12，=4，=8，=0，=14，=8，其他的為非基變量。此時的目標函數(shù)值為244。</p><p>　　用同樣的方法得到的檢驗數(shù)均

77、大于0，故此解為最優(yōu)解。 </p><p><b>　　4.表上作業(yè)法總結</b></p><p>　　運輸問題一般形式是：設某種原材料有m個產(chǎn)地，，...，(通常稱為發(fā)點)，產(chǎn)量分別為，，...，個單位（通常稱為供應量或發(fā)量），另外有n個銷地，，...，（通常稱為收點），銷量分別為，，...，個單位（通常稱為需求量或收量）。一般具有以下特點：</p>

78、<p>　?。?）運輸問題有有限最優(yōu)解</p><p>　　（2）其約束條件信息數(shù)矩陣的元素等于0或1。</p><p>　　（3）約束條件思數(shù)據(jù)幀的每一列有兩個非零元素，這對應于每一個變量在前m個約束方程中出現(xiàn)一次，在后n個約束方程中也出現(xiàn)一次。</p><p>　?。?）對于產(chǎn)銷平衡的運輸問題而言，所有結構約束條件都是等式約束，各產(chǎn)地產(chǎn)量之和等于各

79、銷地銷量之和。</p><p>　　模型及其解法的應用[6]</p><p>　　1.合理利用線材問題：如何下料能夠令使用的材料最少。</p><p>　　2.產(chǎn)品生產(chǎn)計劃：合理利用人力、物力、財力等，使某活動獲利最大。</p><p>　　3.勞動力安排：用最少的勞動力來滿足工作的需要。</p><p>　　4.運輸

80、問題：如何制定調(diào)運方案，使總運費最小。</p><p>　　5.配料問題：在原料供應量的限制下如何獲取最大的利潤。</p><p>　　6.投資問題：從投資項目中選取方案，使投資回報最大。</p><p>　　例7 某公司承諾為某建設項目從2003年起得四年中每年初分別提供一下數(shù)額貸款：03年100萬，04年150萬，05年120萬，06年110萬。以上貸款資金均

81、需于2002年底前籌集齊，但為了發(fā)揮這筆資金的運用，在滿足每年貸款額的情況下，可將多余資金分別用于下列投資項目。</p><p>　?。?）03年初購買A種債券，期限3年，到期后本息合計為投資額的140%，但限購60萬元。</p><p>　?。?）03年初購買B種債券，期限2年，到期后本息合計為投資額的125%，但限購90萬元。</p><p>　　（3）03年初

82、購買C種債券，期限2年，到期后本息合計為投資額的130%，但限購50萬元。</p><p>　　（4）于每年初將任意數(shù)額的資金存放于銀行，年息4%，與每年底取出。</p><p>　　問該公司應如何運用好這筆籌集到的資金，使2002年底需籌集到的資金數(shù)額為最少？</p><p>　　解 設x為2002年底公司需籌集到的資金額，、、分別為2003,2004,2005

83、年年初存放到銀行的資金數(shù)，、、為購買A、B、C債券的數(shù)額（單位均為萬元），則列出下列模型： </p><p><b>　　st.</b></p><p>　　經(jīng)過上述論文中的求解方法進行求解后得到：購買A、B、C分別為60,90,20萬元，03、04、05年初分別存放到銀行170，7.2，0萬元，使得至少籌集到420.2萬。 </p><p&g

84、t;<b>　　總結</b></p><p>　　從上述論文中可以清楚的看出，當線性規(guī)劃問題中只有兩個變量，圖解法是眾多方法中最簡便易行的，而且形象直觀。但是，如果決策變量多于2個時，圖解法則需要在三維立體圖形上畫出進而確定最優(yōu)解，但畫出立體圖形相對困難。當決策變量多于3個時，無法再畫出圖形，那么圖解法就失效了。因此有必要研究線性規(guī)劃問題更通用的解法，這種方法就是單純形法。該方法是以可行域的

85、一個頂點為基礎上，尋找目標函數(shù)在眾多頂點中，有所改進的另一點。這樣重復迭代，直到得出的一個最優(yōu)解為止。</p><p>　　在原始單純形算法中，先根據(jù)檢驗數(shù)和符號選取進基變量和出基變量，而在對偶單純形算法中，</p><p>　　先根據(jù)右端向量元素的符號選取出基變量，然后再確定進基變量。</p><p>　　線性規(guī)劃作為運籌學的核心部分，它在幫助企業(yè)制定經(jīng)營決策，針

86、對企業(yè)資源配置的優(yōu)化，成本的降低、實現(xiàn)效益最大化等都具有舉足輕重的作用。因此，學習線性規(guī)劃等相關方面的的知識，是非常必要的。</p><p><b>　　參 考 文 獻</b></p><p>　?。?］刁在筠，劉桂真，馬建華，蘇潔.運籌學（第三版）[M].高等教育出版社，2007</p><p>　?。?］胡運權，郭耀煌.運籌學教程（第二版）

87、［M].清華大學出版社，2002</p><p>　?。?］張干宗.線性規(guī)劃（第二版）[M].武漢大學出版社，2007</p><p>　　[4] 劉文德，孫秀梅，皮小平.線性規(guī)劃[M].哈爾濱工業(yè)大學出版社，2004</p><p>　　[5] 曾梅清.線性規(guī)劃問題的算法綜述[J].科學技術與工程，2010-01</p><p>　　[6]

88、 薛靜芳.線性規(guī)劃的單純性算法研究及應用[D].大連海事學院，2009-05</p><p>　　[7] 梁秀均.線性規(guī)劃算法的一些改進[J].系統(tǒng)工程理論與實踐，1986-04</p><p>　　[8] 張忠文，王世輝.求解線性規(guī)劃問題最優(yōu)解時常遇到的集中特殊情況[J].甘肅聯(lián)合大學學報，2010-03</p><p>　　[9] 熊偉.運籌學[M].機械工業(yè)出