線性規(guī)劃及其單純形求解方法課件

線性規(guī)劃的數(shù)學模型線性規(guī)劃的標準形式及方法線性規(guī)劃的解及其性質線性規(guī)劃問題的求解方法——單純形法應用實例:農(nóng)場種植計劃模型

線性規(guī)劃及其單純形求解方法

（一）線性規(guī)劃模型之實例線性規(guī)劃研究的兩類問題：某項任務確定后，如何統(tǒng)籌安排，以最少的人力、物力和財力去完成該項任務；面對一定數(shù)量的人力、物力和財力資源，如何安排使用，使得完成的任務最多。它們都屬于最優(yōu)規(guī)劃的范疇。以下為一些實例。一、線性規(guī)劃的數(shù)學模型

運輸問題假設某種物資（譬如煤炭、鋼鐵、石油等）有m個產(chǎn)地，n個銷地。第i產(chǎn)地的產(chǎn)量為ai（i=1，2，…，m），第j

銷地的需求量為bj(j=1,2，…，n)，它們滿足產(chǎn)銷平衡條件。如果產(chǎn)地i到銷地j的單位物資的運費為Cij，要使總運費達到最小，可這樣安排物資的調運計劃：

設xij表示由產(chǎn)地i供給銷地j的物資數(shù)量，則上述問題可以表述為：

求一組實值變量xij(i=1，2，…，m；j=1，2，…，n)，使其滿足

而且使

資源利用問題

假設某地區(qū)擁有m種資源，其中，第i種資源在規(guī)劃期內的限額為bi(i=1，2，…，m)。這m種資源可用來生產(chǎn)n種產(chǎn)品，其中，生產(chǎn)單位數(shù)量的第j種產(chǎn)品需要消耗的第i種資源的數(shù)量為aij(i=1，2，…，m；j=1,2,…,n)，第j種產(chǎn)品的單價為cj(j=1，2，…，n)。試問如何安排這幾種產(chǎn)品的生產(chǎn)計劃，才能使規(guī)劃期內資源利用的總產(chǎn)值達到最大?

設第j種產(chǎn)品的生產(chǎn)數(shù)量為xj(j=1，2，…，n)，則上述資源問題就是：

求一組實數(shù)變量xj(j=1，2，…，n)，使其滿足

合理下料問題

用某種原材料切割零件A1，A2,…,Am的毛坯，現(xiàn)已設計出在一塊原材料上有B1，B2，…，Bn種不同的下料方式，如用Bj下料方式可得Ai種零件aij個，設Ai種零件的需要量為bi個。試問應該怎樣組織下料活動，才能使得既滿足需要，又節(jié)約原材料？

設采用Bj方式下料的原材料數(shù)為xj，則上述問題可表示為：

求一組整數(shù)變量xj(j=1，2，…，n)，使得

（二）線性規(guī)劃的數(shù)學模型

以上例子表明，線性規(guī)劃問題具有以下特征：

①每一個問題都用一組未知變量（x1，x2，…，xn）表示某一規(guī)劃方案，其一組定值代表一個具體的方案，而且通常要求這些未知變量的取值是非負的。

②每一個問題的組成部分：一是目標函數(shù)，按照研究問題的不同，常常要求目標函數(shù)取最大或最小值；二是約束條件，它定義了一種求解范圍，使問題的解必須在這一范圍之內。

③每一個問題的目標函數(shù)和約束條件都是線性的。

由此可以抽象出線性規(guī)劃問題的數(shù)學模型，一般形式為：在線性約束條件

以及非負約束條件

xj≥0（j=1，2，…，n）下，求一組未知變量xj

(j=1，2，…，n)的值，使

采用矩陣形式可描述為：在約束條件

AX≤(≥，＝)b

X≥0下，求未知向量，使得Z=CX→max(min)

其中

二、線性規(guī)劃的標準形式及方法

(一）線性規(guī)劃的標準形式

在討論與計算時，需要將線性規(guī)劃問題的數(shù)學模型轉化為標準形式，即在約束條件xj≥0（j=1，2，…，n）

下，求一組未知變量xj（j=1，2，…，n）的值，使其縮寫形式為：在約束條件

x≥0（j=1，2，…，n）

下，求一組未知變量（j

=1，2，…，n）的值，使得

常記為如下更為緊湊的形式

或（二）化為標準形式的方法

具體的線性規(guī)劃問題，需要對目標函數(shù)或約束條件進行轉換，化為標準形式。目標函數(shù)化為標準形式的方法

如果其線性規(guī)劃問題的目標函數(shù)為

minZ

=CX

顯然有minZ

=max(-Z)=max

Z′

則目標函數(shù)的標準形式為max

Zˊ=-CX約束方程化為標準形式的方法

若第k個約束方程為不等式，即

引入松弛變量,K個方程改寫為則目標函數(shù)標準形式為三、線性規(guī)劃的解及其性質

(一)線性規(guī)劃的解

可行解與最優(yōu)解滿足約束條件（即滿足線性約束和非負約束）的一組變量為可行解。所有可行解組成的集合稱為可行域。使目標函數(shù)最大或最小化的可行解稱為最優(yōu)解。

基本解與基本可行解

在線性規(guī)劃問題中，將約束方程組的m×n階矩陣A寫成由n個列向量組成的分塊矩陣

如果B是A中的一個階的非奇異子陣，則稱B為該線性規(guī)劃問題的一個基。不失一般性，不妨設則稱為基向量，與基向量相對應的向量為基變量，而其余的變量為非基變量。

如果是方程組的解,則就是方程組的一個解，它稱之為對應于基B的基本解，簡稱基解。滿足非負約束條件的基本解，稱為基本可行解。對應于基本可行解的基，稱為可行基。

線性規(guī)劃問題的以上幾個解的關系，可用下圖來描述：

(二)線性規(guī)劃解的性質

凸集和頂點

①凸集：若連接n維點集S中的任意兩點X(1)和X(2)之間的線段仍在S中，則S為凸集。

②頂點：若凸集S中的點X(0)不能成為S中任何線段的內點，則稱X(0)為S的頂點或極點。

線性規(guī)劃解的性質

①線性規(guī)劃問題的可行解集（可行域）為凸集。

②可行解集S中的點X是頂點的充要條件是基本可行解。

③若可行解集有界，則線性規(guī)劃問題的最優(yōu)值一定可以在其頂點上達到。

因此線性規(guī)劃的最優(yōu)解只需從其可行解集的有限個頂點中去尋找。四、線性規(guī)劃問題的求解方法——單純形法

（一）單純形表

根據(jù)以上討論，令則基變量，非基變量，則有變形得相應地，記目標函數(shù)記為則對應于基B的基本解為最優(yōu)解的判定當時，則由目標函數(shù)式可看出：對應于B的基本可行解為最優(yōu)解，這時，B也被稱為最優(yōu)基。由于與等價，故可得。最優(yōu)解的判定定理

對于基B

，若，且,則對應于基B

的基本解為最優(yōu)解，B為最優(yōu)基。在上式中，稱系數(shù)矩陣

為對應于基B的單純形表，記為T(B)?；驅δ繕撕瘮?shù)與約束不等式運用矩陣變形得如果記以及則(二)單純形法的計算步驟

第1步，找出初始可行基，建立初始單純形表。第2步，判別檢驗所有的檢驗系數(shù)

（1）如果所有的檢驗系數(shù),則由最優(yōu)性判定定理知，已獲最優(yōu)解，即此時的基本可行解就是最優(yōu)解。

（2）若檢驗系數(shù)中，有些為正數(shù)，但其中某一正的檢驗系數(shù)所對應的列向量的各分量均非正，則線性規(guī)劃問題無解。（3）若檢驗系數(shù)中，有些為正數(shù)，且它們所對應的列向量中有正的分量，則需要換基、進行迭代運算。

第3步，選主元。在所有大于零的檢驗數(shù)中選取最大的一個b0s，對應的非基變量為xs，對應的列向量為若則確定brs為主元項。

第4步，在基B中調進Ps，換出Pjr，得到一個新的基第5步，在單純形表上進行初等行變換，使第s列向量變?yōu)閱挝幌蛄?，又得一張新的單純形表。?步，轉入上述第2步。

例1：用單純形方法求解線性規(guī)劃問題

解：首先引入松弛變量，把原問題化為標準形式

具體步驟如下：第1步，確定初始單純形表5.1.1。x1x2x3x4-z02300x3121310x492101

第2步，判別。在初始單純形表中b01=2,b02=3，所以B1不是最優(yōu)基，進行換基迭代。第3步，選主元。根據(jù)選主元法則，確定主元項。第4步，換基，得一新基。表5.1.1

第5步，進行初等行變換，得B2下的新單純形表x1x2x3x4-z-1210-10x241/311/30x455/30-1/31

第6步，因檢驗系數(shù)有正數(shù)b01=1，重復以上步驟可得對應于

B3=[p2,p3]的單純形表，檢驗各檢驗數(shù)可知得最優(yōu)解X1=3,X2=3,X3=0,X4=0:目標函數(shù)最大值為

Z=15。x1x2x3x4-z-1500-4/5-3/5x23012/5-1/5x1

310-1/53/5表5.1.2表5.1.3

五、應用實例:農(nóng)場種植計劃模型

某農(nóng)場I、II、III等耕地的面積分別為100hm2、300hm2和200hm2，計劃種植水稻、大豆和玉米，要求3種作物的最低收獲量分別為190000kg、130000kg和350000kg。I、II、III等耕地種植3種作物的單產(chǎn)如表5.1.4所示。若3種作物的售價分別為水稻1.20元/kg，大豆1.50元/kg，玉米0.80元/kg。那么，（1）如何制訂種植計劃，才能使總產(chǎn)量最大？（2）如何制訂種植計劃，才能使總產(chǎn)值最大？表5.1.4不同等級耕地種植不同作物的單產(chǎn)(單位:kg/hm2)

I等耕地II等耕地III等耕地水稻1100095009000大豆800068006000玉米140001200010000表5.1.4

對于上面的農(nóng)場種植計劃問題，我們可以用線性規(guī)劃方法建立模型。根據(jù)題意，決策變量設置如表5.1.5所示,表中Xij表示在第j等級的耕地上種植第i種作物的面積。

3種作物的產(chǎn)量可以用表5.1.6表示。

作物種類總產(chǎn)量水稻大豆玉米表5.1.5作物計劃種植面積（單位:hm2)

表5.1.63種作物的總產(chǎn)量（單位:kg）

I等耕地II