線性規(guī)劃大學(xué)畢業(yè)論文

1、 畢業(yè)論文（設(shè)計(jì)）畢業(yè)論文（設(shè)計(jì)）課題名稱課題名稱 線性規(guī)劃模型的求解及應(yīng)用線性規(guī)劃模型的求解及應(yīng)用 學(xué)學(xué) 院院 理理 學(xué)學(xué) 院院 專專 業(yè)業(yè) 數(shù)學(xué)與應(yīng)用數(shù)學(xué)數(shù)學(xué)與應(yīng)用數(shù)學(xué) （S S） 班班 級(jí)級(jí) 20102010 級(jí)級(jí) 數(shù)學(xué)數(shù)學(xué) 2 2 班班 指導(dǎo)教師指導(dǎo)教師 學(xué)生姓名學(xué)生姓名 佳佳 木木 斯斯 大大 學(xué)學(xué) 教教 務(wù)務(wù) 處處畢業(yè)論文 （設(shè)計(jì)）用紙佳木斯大學(xué)教務(wù)處佳木斯大學(xué)教務(wù)處 線性規(guī)劃模型的求解及應(yīng)用線性規(guī)劃模型的求解及應(yīng)用吳烈東吳烈東佳木斯大學(xué)理學(xué)院數(shù)學(xué)系佳木斯大學(xué)理學(xué)院數(shù)學(xué)系20142014 年年 6 6 月月畢業(yè)論文 （設(shè)計(jì)）用紙佳木斯大學(xué)教務(wù)處佳木斯大學(xué)教務(wù)處 第第 1 頁(yè)頁(yè)摘摘

2、要要線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，它輔助人們進(jìn)行科學(xué)管理，是國(guó)際應(yīng)用數(shù)學(xué)、經(jīng)濟(jì)、計(jì)算機(jī)科學(xué)界所關(guān)注的重要研究領(lǐng)域.線性規(guī)劃主要研究有限資源最佳分配問題，即如何對(duì)有限的資源進(jìn)行最佳地調(diào)配和最有利地使用，以便最充分發(fā)揮資源的效能來獲取最佳的經(jīng)濟(jì)效益.線性規(guī)劃運(yùn)用數(shù)學(xué)語(yǔ)言描述某些經(jīng)濟(jì)活動(dòng)的過程，形成數(shù)學(xué)模型，以一定的算法對(duì)模型進(jìn)行計(jì)算，為制定最優(yōu)計(jì)劃方案提供依據(jù).其解決問題的關(guān)鍵是建立符合實(shí)際情況的數(shù)學(xué)模型，即線性規(guī)劃模型.在各種經(jīng)濟(jì)活動(dòng)中，常采用線性規(guī)劃模型進(jìn)行科學(xué)、定量分析，安排生產(chǎn)組織與計(jì)劃，實(shí)現(xiàn)人力物力資源的最優(yōu)配置，獲得最佳的經(jīng)濟(jì)效益.目前，線性規(guī)劃模型被廣泛應(yīng)用與經(jīng)濟(jì)管理、交通運(yùn)輸、工

3、農(nóng)業(yè)生產(chǎn)等領(lǐng)域.本文主要介紹線性規(guī)劃的兩種基本解法即圖解法和單純形法，并討論了這兩種方法的優(yōu)缺點(diǎn)和在一些實(shí)際問題中的應(yīng)用.關(guān)鍵詞關(guān)鍵詞: : 線性規(guī)劃；圖解法；單純形法；數(shù)學(xué)模型；應(yīng)用畢業(yè)論文 （設(shè)計(jì)）用紙佳木斯大學(xué)教務(wù)處佳木斯大學(xué)教務(wù)處 第第 2 頁(yè)頁(yè)AbstractLinear programming is an important branch of operations research, which assist people to scientific management is an important area of research internationally appli

4、ed mathematics, economics, computer science communitys concerns. The main study of linear programming optimal allocation of limited resources, namely how to limited resources optimally deploy and most advantageously used in order to most fully effective resources to get the best value for money.Line

5、ar programming using mathematical language to describe the process of certain economic activities, the formation of mathematical models to a certain algorithm to calculate the model to provide a basis for the formulation of the optimal plan for. The key to solve the problem is to create a mathematic

6、al model in line with the actual situation, namely linear programming model. In various economic activities, often using linear programming model for scientific, quantitative analysis, organization and planning for production to achieve the optimal allocation of human and material resources, to get

7、the best value for money. At present, the linear programming model is widely used in economic management, transportation, industrial and agricultural production and other fields.This paper describes two basic solution that graphical method for linear programming and the simplex method, and discuss t

8、he advantages and disadvantages of both methods and applications in a number of practical problems.Key words: Linear Programming；Graphic method; simplex method; mathematical model; Application畢業(yè)論文 （設(shè)計(jì)）用紙佳木斯大學(xué)教務(wù)處佳木斯大學(xué)教務(wù)處 第第 3 頁(yè)頁(yè)目目 錄錄摘摘 要要.AbstractAbstract.第第 1 1 章章 緒論緒論.1.1 線性規(guī)劃的基本概念.1.1.1 線性規(guī)劃簡(jiǎn)介.1.1

9、.2 線性規(guī)劃由來的時(shí)間簡(jiǎn)史.1.2 線性規(guī)劃的研究目的及意義.第第 2 2 章章 線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型.2.1 線性規(guī)劃模型的建立.2.2 線性規(guī)劃模型的求解方法.2.2.1 圖解法.2.2.2 單純形法.第第 3 3 章章 線性規(guī)劃在實(shí)際問題中的應(yīng)用線性規(guī)劃在實(shí)際問題中的應(yīng)用.3.1 線性規(guī)劃在企業(yè)管理中的應(yīng)用.3.1.1 線性規(guī)劃在企業(yè)管理中的應(yīng)用范圍.3.1.2 如何實(shí)現(xiàn)線性規(guī)劃在企業(yè)管理中的應(yīng)用.3.2 線性規(guī)劃在企業(yè)生產(chǎn)計(jì)劃中的應(yīng)用.3.3 線性規(guī)劃在運(yùn)輸問題中的應(yīng)用.結(jié)論結(jié)論.參考文獻(xiàn)參考文獻(xiàn).畢業(yè)論文 （設(shè)計(jì)）用紙佳木斯大學(xué)教務(wù)處佳木斯大學(xué)教務(wù)處 第第

10、4 頁(yè)頁(yè)第第 1 1 章章 緒論緒論 1.11.1 線性規(guī)劃的基本概念線性規(guī)劃的基本概念 1.1.11.1.1 線性規(guī)劃簡(jiǎn)介線性規(guī)劃簡(jiǎn)介線性規(guī)劃是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個(gè)重要分支,它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法.在經(jīng)濟(jì)管理、交通運(yùn)輸、工農(nóng)業(yè)生產(chǎn)等經(jīng)濟(jì)活動(dòng)中，提高經(jīng)濟(jì)效果是人們不可缺少的要求，而提高經(jīng)濟(jì)效果一般通過兩種途徑：一是技術(shù)方面的改進(jìn)，例如改善生產(chǎn)工藝，使用新設(shè)備和新型原材料.二是生產(chǎn)組織與計(jì)劃的改進(jìn)，即合理安排人力物力資源.線性規(guī)劃所研究的是：在一定條件下，合理安排人力物力等資源，使經(jīng)濟(jì)效果達(dá)到最好.一般地，求線性目標(biāo)函數(shù)在線性約束條件下的最大值或

11、最小值的問題，統(tǒng)稱為線性規(guī)劃問題.滿足線性約束條件的解叫做可行解，由所有可行解組成的集合叫做可行域.決策變量、約束條件、目標(biāo)函數(shù)是線性規(guī)劃的三要素.1.1.21.1.2 線性規(guī)劃由來的時(shí)間簡(jiǎn)史線性規(guī)劃由來的時(shí)間簡(jiǎn)史 法國(guó)數(shù)學(xué)家 J.- B.- J.傅里葉和 C.瓦萊普森分別于 1832 和 1911 年獨(dú)立地提出線性規(guī)劃的想法，但未引起注意.1939 年蘇聯(lián)數(shù)學(xué)家 .康托羅維奇在生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法一書中提出線性規(guī)劃問題，也未引起重視.1947 年美國(guó)數(shù)學(xué)家 G.B.Dantzing 提出求解線性規(guī)劃的單純型法，為這門學(xué)科奠定了基礎(chǔ).畢業(yè)論文 （設(shè)計(jì)）用紙佳木斯大學(xué)教務(wù)處佳木斯大學(xué)教務(wù)處

12、 第第 5 頁(yè)頁(yè)1947 年美國(guó)數(shù)學(xué)家 J.von 諾伊曼提出對(duì)偶理論,開創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域，擴(kuò)大了它的應(yīng)用范圍和解題能力.1951 年美國(guó)經(jīng)濟(jì)學(xué)家 T.C.庫(kù)普曼斯把線性規(guī)劃應(yīng)用到經(jīng)濟(jì)領(lǐng)域，為此與康托羅維奇一起獲 1975 年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng).50 年代后對(duì)線性規(guī)劃進(jìn)行大量的理論研究，并涌現(xiàn)出一大批新的算法.例如，1954年 C.萊姆基提出對(duì)偶單純形法，1954 年 S.加斯和 T.薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問題，1956 年 A.塔克提出互補(bǔ)松弛定理，1960 年 G.B.丹齊克和 P.沃爾夫提出分解算法等.線性規(guī)劃的研究成果還直接推動(dòng)了其他數(shù)學(xué)規(guī)劃問題包括整數(shù)

13、規(guī)劃、隨機(jī)規(guī)劃和非線性規(guī)劃的算法研究.由于數(shù)字電子計(jì)算機(jī)的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如MPSX，OPHEIE，UMPIRE 等，可以很方便地求解幾千個(gè)變量的線性規(guī)劃問題.1979 年蘇聯(lián)數(shù)學(xué)家 L. G. Khachian 提出解線性規(guī)劃問題的橢球算法，并證明它是多項(xiàng)式時(shí)間算法.1984 年美國(guó)貝爾電話實(shí)驗(yàn)室的印度數(shù)學(xué)家 N.卡馬卡提出解線性規(guī)劃問題的新的多項(xiàng)式時(shí)間算法.用這種方法求解線性規(guī)劃問題在變量個(gè)數(shù)為 5000 時(shí)只要單純形法所用時(shí)間的 1/50.現(xiàn)已形成線性規(guī)劃多項(xiàng)式算法理論.50 年代后線性規(guī)劃的應(yīng)用范圍不斷擴(kuò)大. 建立線性規(guī)劃模型的方法畢業(yè)論文 （設(shè)計(jì)）用紙佳木斯大學(xué)教務(wù)處佳

14、木斯大學(xué)教務(wù)處 第第 6 頁(yè)頁(yè)第第 2 2 章章 線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型2.12.1 線性規(guī)劃模型的建立線性規(guī)劃模型的建立線性規(guī)劃是合理利用、調(diào)配資源的一種應(yīng)用數(shù)學(xué)的方法.它的基本思路是在滿足一定的約束條件下，使預(yù)定的目標(biāo)達(dá)到最優(yōu).它的研究?jī)?nèi)容可歸納為兩個(gè)方面：一是系統(tǒng)的任務(wù)資源數(shù)量已定，精細(xì)安排，用最少的資源去實(shí)現(xiàn)這個(gè)任務(wù)；二是資源數(shù)量已定，如何合理利用、調(diào)配，使任務(wù)完成的最多.前者是求極小，后者是求極大.線性規(guī)劃的一般定義如下： 對(duì)于求取一組變量 Xj（j=1,2,n)，使之既滿足線性約束條件，又使具有線性特征的目標(biāo)函數(shù)取得極值的一類最優(yōu)化問題稱為線性規(guī)劃問題.線性規(guī)

15、劃模型建立需具備以下條件：一是最優(yōu)目標(biāo).問題所要達(dá)到的目標(biāo)能用線性函數(shù)來描述，且能夠使用極值 （最大或最?。?來表示.二是約束條件.達(dá)到目標(biāo)的條件是有一定限制的，這些限制可以用決策變量的線性等式或線性不等式來表示.三是選擇條件，有多種方案可以供選擇，以便從中找出最優(yōu)方案.線性規(guī)劃問題的一般數(shù)學(xué)模型如下： (1)max (或) = 11+ 22 + a11x1+ a12x2+ + a1nxn ( = , ) 1 a21x1+ a22x2+ + a2nxn ( = , ) 2 s.t. (2) am1x1+ a2x2+ + anxn ( = , ) 1x2 0( 0) 稱為決策變量 j(j = 1

16、,2,) 稱為目標(biāo)函數(shù)系數(shù) j(j = 1,2,)畢業(yè)論文 （設(shè)計(jì)）用紙佳木斯大學(xué)教務(wù)處佳木斯大學(xué)教務(wù)處 第第 7 頁(yè)頁(yè) () 稱為約束右端系數(shù) j = 1,2, 稱為約束系數(shù)j( = 1,2, = 1,2,)其中式（1）為目標(biāo)函數(shù)，式（2）稱為約束條件 . 由于目標(biāo)函數(shù)和約束條件內(nèi)容和形式上的差別，線性規(guī)劃問題有多種表達(dá)式，為了便于討論和制定統(tǒng)一的算法，規(guī)定標(biāo)準(zhǔn)形式如下：（1）標(biāo)準(zhǔn)形式 ), 1(0max221122222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczjmnmnmmnnnnnn(2) 記號(hào)簡(jiǎn)寫式 ),.,2 , 1(0),.,2

17、, 1(max11njxmibxaxczjnjijijnjjj（3）矩陣形式 0maxXbAXCXz式中, =（1,） =（1,） 0.000 ,.,.321212222111211bbbbaaaaaaaaaAmnmmnn（4）向量形式畢業(yè)論文 （設(shè)計(jì)）用紙佳木斯大學(xué)教務(wù)處佳木斯大學(xué)教務(wù)處 第第 8 頁(yè)頁(yè) 0max1XbxpCXznjjj式中 C,X,b,0 的含義與矩陣的表達(dá)式相同，而 =,2,( = 1,2,)即 A=（）1,2, 將非標(biāo)準(zhǔn)形式化為標(biāo)準(zhǔn)形式的情況（3 種基本情況）（1）目標(biāo)函數(shù)為求極小值minZ=CX, 則作 Z=-CX, 即 maxZ=-CX(2)右端項(xiàng)小于 0 只需要將

18、兩端同乘（-1） ，不等號(hào)改變方向，然后再將 不等式改為等式（3）約束條件為不等式 若約束條件為“”則在不等式左側(cè)增加一個(gè)非負(fù)松馳變量，使其轉(zhuǎn)化為“” ；若約束條件為“” ，則在不等式左側(cè)減去一個(gè)非負(fù)剩余變量（也稱松馳變量） ，使其轉(zhuǎn)化為“”.2.22.2 線性規(guī)劃模型的求解方法線性規(guī)劃模型的求解方法 2.2.12.2.1 圖解法圖解法線性規(guī)劃可以在一定條件下合理安排人力、 物力等資源 ,使經(jīng)濟(jì)效果達(dá)到最好.一般來說 ,求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值的問題 ,統(tǒng)稱為線性規(guī)劃問題.滿足線性約束條件的解叫做可行解 ,由所有可行解組成的集合叫做可行域.決策變量、 約束條件、 目標(biāo)函數(shù)

19、是線性規(guī)劃的三要素.然而圖解法不適合解大規(guī)模的線性規(guī)劃的問題，局限性比較大.但對(duì)于只有兩個(gè)或者三個(gè)變量的線性規(guī)劃問題 ,可以用圖解法求最優(yōu)解 ,也就是作出約束條件的可行域 ,利用圖解的方法求出最優(yōu)解 ,其特點(diǎn)是過程簡(jiǎn)潔、 圖形清晰，簡(jiǎn)單易懂.下面僅做只有兩個(gè)變量的線性規(guī)劃問題. 只含兩個(gè)變量的線性規(guī)劃問題，可以通過在平面上作圖的方法求解，步驟如下：（1）以變量 x1為橫坐標(biāo)軸，x2為縱坐標(biāo)軸，適當(dāng)選取單位坐標(biāo)長(zhǎng)度建立平面坐標(biāo)直角坐標(biāo)系.由變量的非負(fù)性約束性可知，滿足該約束條件的解均在第一象限內(nèi).（2）圖示約束條件，找出可行域（所有約束條件共同構(gòu)成的圖形）.畢業(yè)論文 （設(shè)計(jì)）用紙佳木斯大學(xué)教務(wù)處

20、佳木斯大學(xué)教務(wù)處 第第 9 頁(yè)頁(yè)（3）畫出目標(biāo)函數(shù)等值線，并確定函數(shù)增大（或減?。┑姆较?（4）可行域中使目標(biāo)函數(shù)達(dá)到最優(yōu)的點(diǎn)即為最優(yōu)解.下面舉出一個(gè)實(shí)例來說明：例 1某木器廠生產(chǎn)圓桌和衣柜兩種產(chǎn)品，現(xiàn)有兩種木料，第一種有 72，第二種有 563m，假設(shè)生產(chǎn)每種產(chǎn)品都需要用兩種木料，生產(chǎn)一張圓桌和一個(gè)衣柜分別所需木3m料如下表所示.每生產(chǎn)一張圓桌可獲利 60 元,生產(chǎn)一個(gè)衣柜可獲利 100 元.木器廠在現(xiàn)有木料條件下,圓桌和衣柜各生產(chǎn)多少,才使獲得利潤(rùn)最多?木料(單位)3m產(chǎn) 品第 一 種第 二 種圓 桌0.180.08衣 柜0.090.28解：設(shè)生產(chǎn)圓桌張,生產(chǎn)衣柜個(gè),利潤(rùn)總額為元,則由已知

21、條件得到的線性規(guī)劃模xyz型為： ,max = 60 + 100 72,. 0.18 + 0.009 . 0, 0,5628. 008. 0yxyx 圖 2-1畢業(yè)論文 （設(shè)計(jì)）用紙佳木斯大學(xué)教務(wù)處佳木斯大學(xué)教務(wù)處 第第 10 頁(yè)頁(yè)這是二維線性規(guī)劃，可用圖解法解，先在 xy 坐標(biāo)平面上作出滿足約束條件的平面區(qū)域,即可行域 S，如上圖所示.再作直線,即,把直線 平移至010060:yxl053: yxll的位置時(shí),直線經(jīng)過可行域上點(diǎn),且與原點(diǎn)距離最遠(yuǎn),此時(shí)取最大值，為1lMyxz10060 了得到 M 點(diǎn)坐標(biāo)解方程組,得;5628. 008. 07209. 018. 0yxyx于是知點(diǎn)坐標(biāo)為(3

22、50,100)，從而得到使利潤(rùn)總額最大的生產(chǎn)計(jì)劃，即生產(chǎn)圓桌M350 張,生產(chǎn)衣柜 100 個(gè),能使利潤(rùn)總額達(dá)到最大值 31000 元.這表明，當(dāng)資源數(shù)量已知,經(jīng)過合理制定生產(chǎn)計(jì)劃,可使效益最好,這就是用圖解法解線性規(guī)劃來解決生產(chǎn)計(jì)劃安排的問題之一. 2.2.22.2.2 單純形法單純形法單純形是美國(guó)數(shù)學(xué)家 G.B.丹齊克于 1947 年首先提出來的.它的理論根據(jù)是：線性規(guī)劃問題的可行域是 n 維向量空間 Rn 中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點(diǎn)處達(dá)到.頂點(diǎn)所對(duì)應(yīng)的可行解稱為基本可行解.單純形法的基本思想是：先找出一個(gè)基本可行解，對(duì)它進(jìn)行鑒別，看是否是最優(yōu)解；若不是，則按照一定法

23、則轉(zhuǎn)換到另一改進(jìn)的基本可行解，再鑒別；若仍不是，則再轉(zhuǎn)換，按此重復(fù)進(jìn)行.因基本可行解的個(gè)數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問題的最優(yōu)解.如果問題無最優(yōu)解也可用此法判別.1953 年美國(guó)數(shù)學(xué)家 G.B.丹齊克為了改進(jìn)單純形法每次迭代中積累起來的進(jìn)位誤差，提出改進(jìn)單純形法.其基本步驟和單純形法大致相同，主要區(qū)別是在逐次迭代中不再以高斯消去法為基礎(chǔ)，而是由舊基陣的逆去直接計(jì)算新基陣的逆，再由此確定檢驗(yàn)數(shù).這樣做可以減少迭代中的累積誤差，提高計(jì)算精度，同時(shí)也減少了在計(jì)算機(jī)上的存儲(chǔ)量.1954 年美國(guó)數(shù)學(xué)家 C.萊姆基提出對(duì)偶單純形法.單純形法是從原始問題的一個(gè)可行解通過迭代轉(zhuǎn)到另一個(gè)可行解，直到檢驗(yàn)數(shù)滿足

24、最優(yōu)性條件為止.對(duì)偶單純形法則是從滿足對(duì)偶可行性條件出發(fā)通過迭代逐步搜索原始問題的最優(yōu)解.在迭代過程中始終保持基解的對(duì)畢業(yè)論文 （設(shè)計(jì)）用紙佳木斯大學(xué)教務(wù)處佳木斯大學(xué)教務(wù)處 第第 11 頁(yè)頁(yè)偶可行性，而使不可行性逐步消失.本節(jié)內(nèi)容只對(duì)一般單形法的進(jìn)行探討.下面舉出一個(gè)實(shí)際例子來做介紹例：求下列線性規(guī)劃問題的最優(yōu)解 004155160203025max211212121xxxxxxxxxz解：化為標(biāo)準(zhǔn)形式 （1）04155160203000025max515142132154321xxxxxxxxxxxxxxz第一步：確定一個(gè)初始基可行解；基可行解就是滿足非負(fù)條件的基本解，因此要在約束矩陣 A

25、中找出一個(gè)可逆的基矩陣. （2）10001010150012030A這里 m=3，3 階可逆方陣，可以看出 x3,x4,x5的系數(shù)列向量是線性獨(dú)立的，這些向量構(gòu)成一個(gè)基)，對(duì)應(yīng)的基變量為x3,x4,x5，x1,x2為非基變量.543)0(,(100010001pppB將基變量用非基變量表示，由(2)得：x3=160-30 x1-20 x2x4=15-5x1-x2 （3）x5=4-x1畢業(yè)論文 （設(shè)計(jì)）用紙佳木斯大學(xué)教務(wù)處佳木斯大學(xué)教務(wù)處 第第 12 頁(yè)頁(yè)將(3)代入目標(biāo)函數(shù)得 Z=5x1+2x2+0令非基變量 x1=x2=0,代入(3),得到一個(gè)基可行解 X(0)X(0)=(0,0,160,1

26、5,4)第二步：從當(dāng)前基可行解轉(zhuǎn)換為更好的基可行解；從數(shù)學(xué)角度看，x1,x2的增加將會(huì)增加目標(biāo)函數(shù)值，從目標(biāo)函數(shù)值中 x1,x2前的系數(shù)看，x1前的系數(shù)大于 x2前的系數(shù)，所以讓 x1從非基變量轉(zhuǎn)為基變量，稱為進(jìn)基變量，怎樣確定離基變量：因?yàn)?x2仍為非基變量，故 x2=0則(3)式變?yōu)閤3=160-30 x1 160/30=16/3x4=15-5x1 15/5=3x5=4-x1 4/1=4min=3，所以當(dāng) x1=3 時(shí)，x4第一個(gè)減少到 0，所以 x4出基,則X(1)=(3,0,70,0,1),(531)1(pppBZ(1)=15此時(shí)非基變量為 x2,x4,用非基變量表示基變量，代入(3)

27、x3=70-14x2+6x4x1=3-1/5x2-1/5x4 （4）x5=1+1/5x2+1/5x4將(4)代入目標(biāo)函數(shù)得 Z=15+x2-x4第三步：繼續(xù)迭代x2進(jìn)基，x4仍為非基變量，令 x4=0，則(4)式表示為x3=70-14x2 70/145x1=3-1/5x2 3/(1/5)15x5=1+1/5x2畢業(yè)論文 （設(shè)計(jì)）用紙佳木斯大學(xué)教務(wù)處佳木斯大學(xué)教務(wù)處 第第 13 頁(yè)頁(yè)min=5，所以當(dāng) x2=5 時(shí)，x3首先減少到 0，所以 x3出基則 X(2)=(2,5, 0,0,2),(521)2(pppBZ(2)=20此時(shí)非基變量為 x3,x4,用非基變量表示基變量，代入(4)x2=5-1

28、/14x3+3/7x4x1=2+1/70 x3-2/7x4 （5）x5=2-1/70 x3+2/7x4將(5)代入目標(biāo)函數(shù)得 Z=20-1/14x3-4/7x4此時(shí)若非基變量 x3,x4的值增加，只能使 Z 值下降所以 X(2)為最優(yōu)解，Z*=20, X*=(2,5, 0,0,2)第三章第三章 線性規(guī)劃模型在實(shí)際問題中的應(yīng)用線性規(guī)劃模型在實(shí)際問題中的應(yīng)用3.13.1 線性規(guī)劃在企業(yè)管理中的應(yīng)用線性規(guī)劃在企業(yè)管理中的應(yīng)用 3.1.13.1.1 線性規(guī)劃在企業(yè)管理中的應(yīng)用范圍線性規(guī)劃在企業(yè)管理中的應(yīng)用范圍 畢業(yè)論文 （設(shè)計(jì)）用紙佳木斯大學(xué)教務(wù)處佳木斯大學(xué)教務(wù)處 第第 14 頁(yè)頁(yè)線性規(guī)劃在企業(yè)管理中

29、的應(yīng)用廣泛，主要有以下八種形式：1.產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、財(cái)力等，是獲利最大.2.勞動(dòng)力安排 ：用最少的勞動(dòng)力來滿足工作的需要.3.運(yùn)輸問題 ：如何制定運(yùn)輸方案，使總運(yùn)費(fèi)最少.4.合理利用線材問題 ：如何下料，使用料最少.5.配料問題 ：在原料供應(yīng)的限制下如何獲得最大利潤(rùn).6.投資問題 ：從投資項(xiàng)目中選取方案，是投資回報(bào)最大.7.庫(kù)存問題 ：在市場(chǎng)需求和生產(chǎn)實(shí)際之間，如何控制庫(kù)存量從而獲得更高利益.8.最有經(jīng)濟(jì)計(jì)劃問題 ：在投資和生產(chǎn)計(jì)劃中如何是風(fēng)險(xiǎn)最小.3.1.23.1.2 如何實(shí)現(xiàn)線性規(guī)劃在企業(yè)管理中的應(yīng)用如何實(shí)現(xiàn)線性規(guī)劃在企業(yè)管理中的應(yīng)用在線性規(guī)劃應(yīng)用前要建立經(jīng)濟(jì)與金融體系的

30、評(píng)價(jià)標(biāo)準(zhǔn)及企業(yè)的計(jì)量體系，摸清企業(yè)的資源.首先通過建網(wǎng)、建庫(kù)、查詢、數(shù)據(jù)采集、文件轉(zhuǎn)換等，把整個(gè)系統(tǒng)的各有關(guān)部分的特征進(jìn)行量化，建立數(shù)學(xué)模型，即把組成系統(tǒng)的有關(guān)因素與系統(tǒng)目標(biāo)的關(guān)系，用數(shù)學(xué)關(guān)系和邏輯關(guān)系描述出來，然后白較好的數(shù)學(xué)模型編制成計(jì)算機(jī)語(yǔ)言，輸入數(shù)據(jù)，進(jìn)行計(jì)算，不同參數(shù)獲取的不同結(jié)果與實(shí)際進(jìn)行分析對(duì)比，進(jìn)行定量，定性分析，最終作出決策.3.23.2 線性規(guī)劃在企業(yè)生產(chǎn)計(jì)劃中的應(yīng)用線性規(guī)劃在企業(yè)生產(chǎn)計(jì)劃中的應(yīng)用 一：應(yīng)用線性規(guī)劃來進(jìn)行生產(chǎn)計(jì)劃問題分析，首先需要弄清楚以下幾點(diǎn)：1.必須明確目標(biāo)函數(shù).生產(chǎn)計(jì)劃的經(jīng)濟(jì)分析是一種定量分析方法，它以企業(yè)利潤(rùn)作為評(píng)價(jià)目標(biāo)值，所尋求的目標(biāo)是使企業(yè)利潤(rùn)最

31、大化的生產(chǎn)計(jì)劃決策，因此，企業(yè)利潤(rùn)最大化應(yīng)是生產(chǎn)計(jì)劃決策分析的目標(biāo)函數(shù).2.必須明確約束條件.企業(yè)的生產(chǎn)能力，原材料，設(shè)備使用，市場(chǎng)需求狀況等諸多制約因素與生產(chǎn)計(jì)劃分析密切相關(guān)，稱為生產(chǎn)計(jì)劃分析中目標(biāo)函數(shù)的約束條件.約束條件對(duì)生產(chǎn)計(jì)劃分析的影響較大，在不同條件下，決策分析的結(jié)論則會(huì)不同.比如，就市場(chǎng)需求和企業(yè)生產(chǎn)能力之間的關(guān)系而言，企業(yè)所處狀態(tài)可有三種類型:能力不足狀態(tài)，即市場(chǎng)對(duì)產(chǎn)品的需求超過了企業(yè)的生產(chǎn)能力;能力過剩狀態(tài)，即企業(yè)生產(chǎn)能力超過了市場(chǎng)需要:中間狀態(tài)，即供求平衡的狀態(tài)，或者有時(shí)處于不足狀態(tài)，有時(shí)又處于過剩狀態(tài).3.必須明確單件利潤(rùn).單件利潤(rùn)不僅牽扯到產(chǎn)品的單件收入，還要牽扯到生產(chǎn)所

32、耗費(fèi)的各項(xiàng)成本及費(fèi)用.畢業(yè)論文 （設(shè)計(jì)）用紙佳木斯大學(xué)教務(wù)處佳木斯大學(xué)教務(wù)處 第第 15 頁(yè)頁(yè) 二、建立生產(chǎn)計(jì)劃決策分析的線性規(guī)劃模型生產(chǎn)計(jì)劃決策分析的基本方法是以利潤(rùn)最大化作為優(yōu)化目標(biāo)，明確未知變量，確定約束條件，建立線性規(guī)劃模型，最終實(shí)現(xiàn)企業(yè)效益最大化的生產(chǎn)計(jì)劃.其一般模式: 目標(biāo)函數(shù)為利潤(rùn) P P=銷售收入 R R-(成本+費(fèi)用)C C.在各種約束條件下，使目標(biāo)函數(shù)達(dá)到最大值.分析企業(yè)實(shí)際生產(chǎn)過程中的日產(chǎn)量情況，設(shè)模型的未知變量為企業(yè)生產(chǎn)的產(chǎn)品種類日產(chǎn)量建立生產(chǎn)計(jì)劃決策分析線性規(guī)劃模型的過程如下:（ = 1,2,）( 1 )目標(biāo)函數(shù)企業(yè)進(jìn)行生產(chǎn)計(jì)劃決策的目標(biāo)值是企業(yè)利潤(rùn)最大化.現(xiàn)假設(shè)生產(chǎn)

33、各種產(chǎn)品所獲得的銷售收入 R;與所耗費(fèi)的產(chǎn)品成本和費(fèi)用 C;均已知，則可以得出生產(chǎn)計(jì)劃問題的目標(biāo)函數(shù)為: =(1 1)1+(2 2)2+ + ( )( 2 )原材料約束無論是生產(chǎn)何種產(chǎn)品都需要消耗一定的原材料，在企業(yè)實(shí)際中若需耗用多種原材料則可根據(jù)原材料的種類，增添相應(yīng)約束條件即可，建立約束不等式: 111+ 122+ 1 1上式中，分別為生產(chǎn)第 1,2，n 種產(chǎn)品的單件原材料消耗，11，12，1為企業(yè)每可用的原材料總量.1（3）生產(chǎn)能力約束. 此約束具體表現(xiàn)為企業(yè)的可用工作時(shí)間或可用設(shè)備，而企業(yè)在一定時(shí)期內(nèi)的可用工作是有限的，所以可建立如下的約束不等式： 211+ 222+ + 2 2上式中

34、，分別為生產(chǎn)第 1,2，種產(chǎn)品的單件消耗工時(shí)，為企21，22，2，2業(yè)的日可用的工時(shí)、料總量.（4）市場(chǎng)需求約束 為了說明問題的方便，假設(shè)企業(yè)生產(chǎn)的產(chǎn)品市場(chǎng)都有需求，即, 1+ 2+ + 0無上限約束.若第 j 種產(chǎn)品市場(chǎng)需求有限，最大需求為,則可增加約束. （5）非負(fù)約束因?yàn)樯a(chǎn)實(shí)際中最多即為不生產(chǎn)產(chǎn)品，所以所有變量 0（ = 1,2,）綜上所述，建立生產(chǎn)計(jì)劃決策分析的線性規(guī)劃模型如下：畢業(yè)論文 （設(shè)計(jì)）用紙佳木斯大學(xué)教務(wù)處佳木斯大學(xué)教務(wù)處 第第 16 頁(yè)頁(yè) =(1- 1)1+(2- 2)2+ + (- ) 111+ 122+ 1 1 211+ 222+ + 2 2 s. t 11+ 22+

35、 0（ = 1,2,）3.33.3 線性規(guī)劃在運(yùn)輸問題中的應(yīng)用線性規(guī)劃在運(yùn)輸問題中的應(yīng)用運(yùn)輸是物流活動(dòng)的核心環(huán)節(jié)，線性規(guī)劃是運(yùn)輸問題的常用數(shù)學(xué)模型，利用數(shù)學(xué)知識(shí)可以得到優(yōu)化的運(yùn)輸方案.運(yùn)輸問題的提出源于如何物流活動(dòng)中的運(yùn)輸路線或配送方案是最經(jīng)濟(jì)或最低成本的.運(yùn)輸問題解決的是已知產(chǎn)地的供應(yīng)量，銷地的需求量及運(yùn)輸單價(jià)，如何尋找總配送成本最低的方案；運(yùn)輸問題包含產(chǎn)銷平衡運(yùn)輸問題和產(chǎn)銷不平衡運(yùn)輸問題；通常將產(chǎn)銷不平衡問題轉(zhuǎn)化為產(chǎn)銷平衡問題來處理；運(yùn)輸問題的條件包括需求假設(shè)和成本假設(shè).需求假設(shè)指每一個(gè)產(chǎn)地都有一個(gè)固定的供應(yīng)量所有的供應(yīng)量都必須配送到目的地.與之類似，每一個(gè)目的地都有一個(gè)固定的需求量，整個(gè)

36、需求量都必須有出發(fā)地滿足；成本假設(shè)指從任何一個(gè)產(chǎn)地到任何一個(gè)銷地的配送成本和所配送的數(shù)量的線性比例關(guān)系.產(chǎn)銷平衡運(yùn)輸問題的一般提法是：假設(shè)某物資有 m 個(gè)產(chǎn)地;各地產(chǎn)量分別為物資從產(chǎn)1，2，1，2，地運(yùn)往銷地的單位運(yùn)價(jià)為,滿足：.其數(shù)學(xué)模型為：njjmiiba11Min Z=minjijijxc11 產(chǎn)地約束njijx1( = 1,2, ,)畢業(yè)論文 （設(shè)計(jì)）用紙佳木斯大學(xué)教務(wù)處佳木斯大學(xué)教務(wù)處 第第 17 頁(yè)頁(yè)s.t 銷地約束 （a）miijx1( = 1,2,) (非負(fù)約束 0 = 1,2, ,; = 1,2,)1：產(chǎn)銷不平衡運(yùn)輸問題分兩種情況：（1）總產(chǎn)量大于總銷量，既滿足，此時(shí)其數(shù)學(xué)模

37、型與表達(dá)式(a)基本相同，njjmiiba11只需將表達(dá)式（a）中的產(chǎn)地約束條件 改為 .njijx1njijx1（2）總產(chǎn)量小于總銷量，既滿足，此時(shí)其數(shù)學(xué)模型與表達(dá)式(a)也基本相同，njjmiiba11只需將表達(dá)式（a）中的產(chǎn)地約束條件 改為 .njijx1njijx12.運(yùn)輸問題的解決策略 現(xiàn)實(shí)生產(chǎn)的情況往往比較復(fù)雜，許多實(shí)際問題不一定完全符合運(yùn)輸問題的假設(shè)，可能一些特征近似但其中的一個(gè)或者幾個(gè)特征卻并不符合運(yùn)輸問題條件.一般來說，如果一個(gè)問題中涉及兩大類對(duì)象之間的聯(lián)系或往來，且該問題能提供運(yùn)輸問題所需要的三類數(shù)據(jù):供應(yīng)量、需求量、單位運(yùn)價(jià)，那么這個(gè)問題(不管其中是否涉及運(yùn)輸)經(jīng)適當(dāng)約束條件的處理后，基木都可以應(yīng)用運(yùn)輸問題模型來解決.例如:（1）追求的目標(biāo)是效益最大而非成木最低，此時(shí)僅將表達(dá)式(a)中目標(biāo)函數(shù)中的“Min Z”改為“Max Z”即可.（2）部分(或全部)