畢業(yè)論文(設(shè)計(jì))線性規(guī)劃問(wèn)題的解法

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

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

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

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

5、要針對(duì)線性規(guī)劃問(wèn)題的一般解法和特殊解法進(jìn)行歸納、總結(jié)和改進(jìn)，并簡(jiǎn)單闡述線性規(guī)劃的常用模型及應(yīng)用。</p><p>　　關(guān)鍵詞：線性規(guī)劃 目標(biāo)函數(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>　　一、 研究基礎(chǔ)1</b></p><p>　?。ㄒ唬┙鉀Q線性規(guī)劃問(wèn)題的一般思路1</p><p>　　（二）線性規(guī)劃數(shù)學(xué)模型建立的條件1</p><p>　?。ㄈ┚€性規(guī)劃數(shù)學(xué)模型的建立1</p><p>　?。ㄋ模┚€性規(guī)劃數(shù)學(xué)

14、模型的特點(diǎn)2</p><p>　?。ㄎ澹┚€性規(guī)劃解的有關(guān)概念及其關(guān)系2</p><p>　　（六）LP模型的表達(dá)形式2</p><p>　　二、 線性規(guī)劃的一般解法及實(shí)例3</p><p><b>　　（一）圖解法3</b></p><p><b>　?。ǘ﹩渭冃畏?<

15、;/b></p><p>　?。ㄈ┤斯ぷ兞糠?</p><p><b>　　1.大M法8</b></p><p>　　2. 兩階段法10</p><p>　　（四）對(duì)偶單純形法12</p><p>　　三、 線性規(guī)劃的特殊求解及實(shí)例14</p><p>　

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

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

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

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

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

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

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

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

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

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

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

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

28、gt;<b>　　約束條件：</b></p><p><b>　　2.簡(jiǎn)約模型</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ī)劃的一般解法及實(shí)例</p><p><b>　?。ㄒ唬﹫D解法[3]</b></p><p><b>　　1.圖解法原理</b></p&g

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

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

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

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

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

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

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

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

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

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

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

42、lt;p><b>　　表-2</b></p><p><b>　　檢驗(yàn)數(shù)計(jì)算公式：</b></p><p><b>　　=cj-.</b></p><p>　　由公式計(jì)算得=3，=4兩個(gè)檢驗(yàn)數(shù)均大于0，故進(jìn)行下一步，從一個(gè)基可行解轉(zhuǎn)換到兩一個(gè)目標(biāo)值更大的基可行解。</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ī)劃問(wèn)題存在可行解，則該問(wèn)題的可行域是凸集。</p><p>　　定理2 線性規(guī)劃問(wèn)題的基可行解X對(duì)應(yīng)可行域（凸集）的頂點(diǎn)。</p><p>　　定理3 若問(wèn)題存在最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解

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

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

47、max Z=3+2-</p><p>　　解 先將其標(biāo)準(zhǔn)化得： </p><p>　　max Z=3+2-</p><p>　　其約束條件的系數(shù)矩陣：，系數(shù)矩陣中有一個(gè)單位向量，按照一般單純形法方法，故需要進(jìn)行初等變換，使得約束條件中出現(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>　　若用初等變換方法無(wú)法得出單位矩陣（即初始基可行解），那么在每個(gè)約束方程中加入人工變量便可形成一組向量，這種方法即為大M法或兩階段法。</p><p><b>　　1.大M法</b></p><p>　　人們?yōu)榱俗尲尤肴斯ぷ兞亢缶€性規(guī)劃問(wèn)

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

50、中可作為一個(gè)基變量。</p><p>　　將上述標(biāo)準(zhǔn)型化為人工變量單純形法模型：</p><p>　　max Z=3+2--M-M</p><p>　　約束條件中分別加入、，目標(biāo)函數(shù)中加入-M-M項(xiàng)。利用單純形表，進(jìn)行求解如下：</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>　　第一階段，先不考慮原問(wèn)題是否最在基可行解，先求解一個(gè)目標(biāo)函數(shù)中只包含人工變量的線性規(guī)劃問(wèn)題，即令目標(biāo)函數(shù)中其他變量的系數(shù)取零，人工變量的系數(shù)取某個(gè)正的常數(shù)，在保持原問(wèn)題約束條件不變的情況下，求這個(gè)目標(biāo)函數(shù)極小化的解。然后利用單純形法求解所構(gòu)造的新模型，若w=0，這時(shí)，若基變量中不含人工變量或人工變量取值為0，則說(shuō)明問(wèn)題存在基可行解，否則停止計(jì)算，原問(wèn)題無(wú)可行解。</p><p>　　第二階段，利用用

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

54、;　　在約束方程中加入人工變量，后，得出第一階段問(wèn)題為：</p><p><b>　　min w=+</b></p><p>　　用單純形法求解，得到第一階段問(wèn)題的計(jì)算表如下：</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)解為原問(wèn)題的一組基可行解，作為初始基可行解，第二階段問(wèn)題為：</p><p>　　max Z=3+2-</p><p>　　用單純形法計(jì)算得到下表：</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.人工變量法總結(jié)</b></p><p>　　在實(shí)際中，有些線性規(guī)劃問(wèn)題的模型中并不含有單位矩陣，為了得到一組基向量和初始基可行解，在約束條件等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量成為人工變量，主要為大M法和兩階段法求解。</p&

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

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

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

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

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

62、，以為標(biāo)準(zhǔn)，得-15/-5 < -9/-1 < -12/-1，故以為換入變量，進(jìn)行變量迭代。</p><p><b>　　表-8</b></p><p>　　由表中可得：以為換入變量，為換出變量。再次進(jìn)行變量迭代。</p><p><b>　　表-9</b></p><p>　　由表中可

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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