線性規(guī)劃建模課件

線性規(guī)劃方法線性規(guī)劃（LinearProgramming,縮寫為LP）是運籌學(xué)的重要分支之一，在實際中應(yīng)用得較廣泛，其方法也較成熟，借助計算機，使得計算更方便，應(yīng)用領(lǐng)域更廣泛和深入。線性規(guī)劃通常研究資源的最優(yōu)利用、設(shè)備最佳運行等問題。例如，當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè)備、原標(biāo)材料、人工、時間等）去完成確定的任務(wù)或目標(biāo)；企業(yè)在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多、利潤最大）等等。一、應(yīng)用模型舉例生產(chǎn)計劃問題

2x1

+x2

8s.t.x1

3x2

4

x1，x2

0

maxf=5x1+2x2

求最大利潤三種材料量的限制生產(chǎn)量非負(fù)運輸問題解：設(shè)A1,A2調(diào)運到三個糧站的大米分別為x1，x2，

x3，

x4，

x5，

x6噸。題設(shè)量可總到下表：結(jié)合存量限制和需量限制得數(shù)學(xué)模型：m個產(chǎn)地A1,…,Am聯(lián)合供應(yīng)n個銷地B1,…,Bn,各產(chǎn)地至各銷地單位運價(單位:元/噸)為cij，問如何調(diào)運使總運費最少?一般運輸問題總運價產(chǎn)量限制需量限制運量非負(fù)

二、線性規(guī)劃的數(shù)學(xué)模型

以上例子表明，線性規(guī)劃問題具有以下特征：①每一個問題都用一組未知變量（x1，x2，…，xn）表示某一規(guī)劃方案，其一組定值代表一個具體的方案，而且通常要求這些未知變量的取值是非負(fù)的。②每一個問題的組成部分：一是目標(biāo)函數(shù)，按照研究問題的不同，常常要求目標(biāo)函數(shù)取最大或最小值；二是約束條件，它定義了一種求解范圍，使問題的解必須在這一范圍之內(nèi)。③每一個問題的目標(biāo)函數(shù)和約束條件都是線性的。即線性規(guī)劃的數(shù)學(xué)模型由決策變量

Decisionvariables

目標(biāo)函數(shù)Objectivefunction約束條件Constraints構(gòu)成。稱為三個要素。其特征是：1．解決問題的目標(biāo)函數(shù)是多個決策變量的線性函數(shù)，

通常是求最大值或最小值；2．解決問題的約束條件是一組多個決策變量的線性不

等式或等式。

由此可以抽象出線性規(guī)劃問題的數(shù)學(xué)模型。

一般地，假設(shè)線性規(guī)劃數(shù)學(xué)模型中，有m個約束，有n個決策變量xj,j=1,2…,n，目標(biāo)函數(shù)的變量系數(shù)用cj表示,cj稱為價值系數(shù)。約束條件的變量系數(shù)用aij表示，aij稱為工藝系數(shù)。約束條件右端的常數(shù)用bi表示，bi稱為資源限量。則線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式可寫成為了書寫方便，上式也可寫成：

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

AX≤(≥，＝)bX≥0下，求未知向量，使得Z=CX→max(min)

其中應(yīng)用市場營銷(廣告預(yù)算和媒介選擇，競爭性定價，新產(chǎn)品開發(fā)，制定銷售計劃)生產(chǎn)計劃制定(合理下料，配料，“生產(chǎn)計劃、庫存、勞力綜合”)庫存管理(合理物資庫存量，停車場大小，設(shè)備容量)運輸問題財政、會計(預(yù)算，貸款，成本分析，投資，證券管理)人事(人員分配，人才評價，工資和獎金的確定)設(shè)備管理(維修計劃，設(shè)備更新)城市管理(供水，污水管理，服務(wù)系統(tǒng)設(shè)計、運用)小結(jié)：建立線性規(guī)劃數(shù)學(xué)模型

建立數(shù)學(xué)模型是學(xué)習(xí)線性規(guī)劃的第一步也是關(guān)鍵的一步。建立正確的數(shù)學(xué)模型要掌握3個要素：研究的問題是求什么，即設(shè)置決策變量；問題要達(dá)到的目標(biāo)是什么，即建立目標(biāo)函數(shù)，目標(biāo)函數(shù)一定是決策變量的線性函數(shù)并且求最大值或求最小值；限制達(dá)到目標(biāo)的條件是什么，即建立約束條件。三、線性規(guī)劃問題的基本理論

（一）線性規(guī)劃的標(biāo)準(zhǔn)形式

在討論與計算時，需要將線性規(guī)劃問題的數(shù)學(xué)模型轉(zhuǎn)化為標(biāo)準(zhǔn)形式，即1．目標(biāo)函數(shù)求最大值（或求最小值）2．約束條件都為等式方程3．變量xj非負(fù)4．常數(shù)bi非負(fù)max(或min)Z=c1x1+c2x2+…+cnxn或?qū)懗上铝行问剑?/p>

或用矩陣形式通常x記為：

稱Ａ為約束方程的系數(shù)矩陣，m是約束方程的個數(shù)，n是決策變量的個數(shù)，一般情況m≤n，且r(Ａ)＝m。其中:

任何一個線性規(guī)劃問題都可以化為標(biāo)準(zhǔn)形式，我們的求解方法都是針對標(biāo)準(zhǔn)形式的。如果給定的LP問題是極小化問題,即可化為極大化問題約束條件不變,其最優(yōu)解是一致的,但目標(biāo)函數(shù)值的符號相反.則:結(jié)論:如果問題是求目標(biāo)函數(shù)的最小值,則化為求–f的最大值;1.關(guān)于目標(biāo)函數(shù)2.關(guān)于約束條件(1)如果給定的LP有約束不等式注意:新引入的變量在目標(biāo)函數(shù)中的系數(shù)為0.(2)如果給定的LP有約束不等式3.關(guān)于變量

在標(biāo)準(zhǔn)形式中,所有的變量都有非負(fù)限制,如果某些變量沒有非負(fù)限制,則稱這些變量為自由的.兩種處理辦法:【例1】將下列線性規(guī)劃化為標(biāo)準(zhǔn)形【解】（１）因為x3無符號要求，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以令(2)第一個約束條件是≤號，在≤左端加入松馳變量(slackvariable)x4，x4≥0,化為等式；(4)第三個約束條件是≤號且常數(shù)項為負(fù)數(shù)，因此在≤左邊加入松馳變量x6，x6≥0，同時兩邊乘以－1。（5）目標(biāo)函數(shù)是最小值，為了化為求最大值，令Z′=－Z,得到maxZ′=－Z，即當(dāng)Z達(dá)到最小值時Z′達(dá)到最大值，反之亦然。(3)第二個約束條件是≥號，在≥左端減去剩余變量(Surplusvariable)x5，x5≥0。也稱松馳變量綜合起來得到下列標(biāo)準(zhǔn)型

當(dāng)某個變量xj≤0時,令x/j=－xj

。當(dāng)某個約束是絕對值不等式時，將絕對值不等式化為兩個不等式，再化為等式，例如約束將其化為兩個不等式再加入松馳變量化為等式。

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

若x*滿足約束條件，則稱之為LP問題的可行解。所有可行解的集合稱為可行域。使目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解稱為最優(yōu)解。對給定的LP問題，若存在最優(yōu)解，則稱該LP問題有解，否則稱LP問題無解。線性規(guī)劃的標(biāo)準(zhǔn)形幾個概念（Ⅰ）用圖解法求解線性規(guī)劃問題圖解法的步驟：1.求可行解集合。分別求出滿足每個約束包括變量非負(fù)要求的區(qū)域，其交集就是可行解集合，或稱為可行域；2.繪制目標(biāo)函數(shù)圖形。先過原點作一條矢量指向點（c1,c2)，矢量的方向就是目標(biāo)函數(shù)增加的方向，稱為梯度方向，再作一條與矢量垂直的直線，這條直線就是目標(biāo)函數(shù)圖形；3.求最優(yōu)解。依據(jù)目標(biāo)函數(shù)求最大或最小移動目標(biāo)函數(shù)直線，直線與可行域相交的點對應(yīng)的坐標(biāo)就是最優(yōu)解。一般地，將目標(biāo)函數(shù)直線放在可行域中求最大值時直線沿著矢量方向移動求最小值時沿著矢量的反方向移動x1x2O1020304010203040(3,4)(15,10)最優(yōu)解X=(15,10)最優(yōu)值Z=85例3246x1x2246最優(yōu)解X=(3,1)最優(yōu)值Z=5(3,1)minZ=x1+2x2例4(1,2)246x1x2246X（2）＝（3,1）X（1）＝（1,3）(5,5)minZ=5x1+5x2例5有無窮多個最優(yōu)解即具有多重解,通解為0≤α≤1

當(dāng)α=0.5時Ｘ=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)246x1x2246(1,2)無界解(無最優(yōu)解)maxZ=x1+2x2例6x1x2O10203040102030405050無可行解即無最優(yōu)解maxZ=10x1+4x2例7由以上例題可知，線性規(guī)劃的解有4種形式：1.有唯一最優(yōu)解(例3、例4)2.有多重解(例5)3.有無界解(例6)4.無可行解(例7)1、2情形為有最優(yōu)解3、4情形為無最優(yōu)解從上述幾何直觀還可看出：⑴線性規(guī)劃問題的任意兩個可行解聯(lián)線上的點都是可行解；⑵線性規(guī)劃問題的任意兩個最優(yōu)解聯(lián)線上的點都是最優(yōu)解；⑶線性規(guī)劃問題的最優(yōu)值若存在，則一定在某個頂點達(dá)到。（Ⅱ）線性規(guī)劃的有關(guān)概念及基本定理1.線性規(guī)劃常用的概念：凸集、凸組合、極點（凸點）、可行解、基本解、基本可行解、最優(yōu)解、基本最優(yōu)解、基、可行基、最優(yōu)基。2.線性規(guī)劃的三個基本定理。凸集(Convexset)設(shè)K是n維空間的一個點集，對任意兩點

時，則稱K為凸集。

就是以X（1）、X（2）為端點的線段方程，點X的位置由α的值確定，當(dāng)α=0時，X=X（2），當(dāng)α=1時X=X（1）凸組合(Convexcombination)

設(shè)是Rn中的點若存在

使得成立，則稱X為的凸組合。極點(Extremepoint)

設(shè)K是凸集，，若X不能用K中兩個不同的點的凸組合表示為<)10()1()2()1(<-+=aaaXXX則稱X是K的一個極點或頂點。X是凸集K的極點是指X不可能是K中某一線段的內(nèi)點，只能是K中某一線段的端點。O

設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型

maxZ=CX

（1.1）

AX=b

（1.2）

X≥0（1.3）式中A是m×n矩陣，m≤n并且r（A）=m，顯然A中至少有一個m×m子矩陣B，使得r（B）=m?；?/p>

(basis)A中m×m子矩陣B并且有r（B）=m，則稱B是線性規(guī)劃的一個基（或基矩陣basismatrix）。當(dāng)m=n時，基矩陣唯一，當(dāng)m<n時，基矩陣就可能有多個，但數(shù)目不超過【例8】線性規(guī)劃

求所有基矩陣?！窘狻考s束方程的系數(shù)矩陣為2×5矩陣容易看出r(A)=2，2階子矩陣有C52=10個，其中第1列與第3列構(gòu)成的2階矩陣不是一個基，基矩陣只有9個，即由線性代數(shù)知，基矩陣B必為非奇異矩陣并且|B|≠0。當(dāng)矩陣B的行列式等于零（即|B|=0）時就不是基當(dāng)確定某一矩陣為基矩陣時，則基矩陣對應(yīng)的列向量稱為基向量(basisvector)，其余列向量稱為非基向量（或自由向量）基向量對應(yīng)的變量稱為基變量(basisvariable)，非基向量對應(yīng)的變量稱為非基變量

在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基變量，x2、x3、x5是非基變量?；兞?、非基變量是針對某一確定基而言的，不同的基對應(yīng)的基變量和非基變量也不同?？尚薪?feasiblesolution)

滿足式（1.2）及（1.3）的解x=（x1,x2…，xn)T稱為可行解?；究尚薪?basis

feasiblesolution)

若基本解是可行解則稱為是基本可行解（也稱基可行解）。

基本解(basissolution)對某一確定的基B，令非基變量等于零，利用式（1.２）解出基變量，則這組解稱為基Ｂ的基本解。最優(yōu)解(optimalsolution)滿足式（1.1）的可行解稱為最優(yōu)解，即是使得目標(biāo)函數(shù)達(dá)到最大值的可行解就是最優(yōu)解。非可行解(Infeasiblesolution)

無界解

(unboundsolution)顯然，只要基本解中的基變量的解滿足式（1.３）的非負(fù)要求，那么這個基本解就是基本可行解。在例5中，對Ｂ１來說，x1，x2是基變量，x3，x4，x5是非基變量，令x3=x4=x5=0，則式（1.２）為對B2來說，x1,x4,為基變量，令非基變量x2,x3,x5為零，由式（1.2）得到

，x4=4，因|B1|≠０，由克萊姆法則知，x1、x2有唯一解x1＝2/5,x2=1則基本解為由于是基本解，從而它是基本可行解，在中x1<0,因此不是可行解，也就不是基本可行解。反之，可行解不一定是基本可行解例如滿足式（1.2）～（1.3），但不是任何基矩陣的基本解?；窘鉃榭尚谢尚薪鈱?yīng)的基稱為可行基；最優(yōu)基基本最優(yōu)解對應(yīng)的基稱為最優(yōu)基；如上述B3就是最優(yōu)基，最優(yōu)基也是可行基。當(dāng)最優(yōu)解唯一時，最優(yōu)解亦是基本最優(yōu)解，當(dāng)最優(yōu)解不唯一時，則最優(yōu)解不一定是基本最優(yōu)解。例如右圖中線段的點為最優(yōu)解時，Q1點及Q2點是基本最優(yōu)解,線段的內(nèi)點是最優(yōu)解而不是基本最優(yōu)解?；咀顑?yōu)解

最優(yōu)解是基本解稱為基本最優(yōu)解。例如，滿足式（1.1）~(1.3)是最優(yōu)解,又是B3的基本解,因此它是基本最優(yōu)解?；咀顑?yōu)解、最優(yōu)解、基本可行解、基本解、可行解的關(guān)系如下所示：基本最優(yōu)解基本可行解可行解最優(yōu)解基本解例如,B點和D點是可行解,不是基本解;C點是基本可行解;A點是基本最優(yōu)解,同時也是最優(yōu)解、基本可行解、基本解和可行解?！径ɡ?】若線性規(guī)劃可行解K非空,則K是凸集?！径ɡ?】線性規(guī)劃的可行解集合K的點X是極點的充要條件為X是基本可行解?！径ɡ?】若線性規(guī)劃有最優(yōu)解,則最優(yōu)值一定可以在可行解集合的某個極點上到達(dá),最優(yōu)解就是極點的坐標(biāo)向量。定理2刻劃了可行解集的極點與基本可行解的對應(yīng)關(guān)系，極點是基本可行解，反之，基本可行解一定是極點，但它們并非一一對應(yīng)，有可能兩個或幾個基本可行解對應(yīng)于同一極點（退化基本可行解時）。線性規(guī)劃的基本定理

定理3描述了最優(yōu)解在可行解集中的位置，若最優(yōu)解唯一，則最優(yōu)解只能在某一極點上達(dá)到，若具有多重最優(yōu)解，則最優(yōu)解是某些極點的凸組合，從而最優(yōu)解是可行解集的極點或界點，不可能是可行解集的內(nèi)點。

若線性規(guī)劃的可行解集非空且有界，則一定有最優(yōu)解；若可行解集無界，則線性規(guī)劃可能有最優(yōu)解，也可能沒有最優(yōu)解。

定理2及3還給了我們一個啟示，尋求最優(yōu)解不是在無限個可行解中去找，而是在有限個基本可行解中去尋求。下面將介紹一種有效地尋找最優(yōu)解的方法。（Ⅲ）單純形法求解線性規(guī)劃問題

單純形計算方法(SimplexMethod)是先求出一個初始基可行解并判斷它是否最優(yōu)，若不是最優(yōu)，再換一個基可行解并判斷，直到得出最優(yōu)解或無最優(yōu)解。它是一種逐步逼近最優(yōu)解的迭代方法。

當(dāng)系數(shù)矩陣A中可以觀察得到一個可行基時（通常是一個單位矩陣或m個線性無關(guān)的單位向量組成的矩陣），可以通過解線性方程組求得基本可行解?！纠?】用單純形法求下列線性規(guī)劃的最優(yōu)解【解】化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4則標(biāo)準(zhǔn)型為系數(shù)矩陣A及可行基B1r(B1)=2，B1是一個初始基,x3、x4為基變量，x1、x2為非基變量，令x1=0、x2=0由約束方程知x3=40、x4=30得到初始基本可行解X(1)=(0,0,40,30)T

以上得到的一組基可行解是不是最優(yōu)解，可以從目標(biāo)函數(shù)中的系數(shù)看出。目標(biāo)函數(shù)Z=3x1+4x2中x1的系數(shù)大于零，如果x1為一正數(shù)，則Z的值就會增大，同樣若x2不為零為一正數(shù)，也能使Z的值增大；因此只要目標(biāo)函數(shù)中非基變量的系數(shù)大于零，那么目標(biāo)函數(shù)就沒有達(dá)到最大值，即沒有找到最優(yōu)解，判別線性規(guī)劃問題是否達(dá)到最優(yōu)解的數(shù)稱為檢驗數(shù)，記作λj,j=1,2…,n。

本例中λ1=3,λ2=4,λ3=0,λ4=0。參看表1.4（a）。最優(yōu)解判斷標(biāo)準(zhǔn)當(dāng)所有檢驗數(shù)λj≤0（j=1，…，n）時，基本可行解為最優(yōu)解。當(dāng)目標(biāo)函數(shù)中有基變量xi時，利用約束條件將目標(biāo)函數(shù)中的xi消去即可求出檢驗數(shù)。檢驗數(shù)目標(biāo)函數(shù)用非基變量表達(dá)時的變量系數(shù)進(jìn)基列出基行bi/ai2，ai2>0θi表1(1)XBx1x2x3x4bx3211040x4130130λj3400

(2)x3x2λj

(3)x1

x2

λj

基變量110001/301/3105/31-1/3405/30-4/330103/5-1/51801-1/52/5400-1-1將3化為1乘以1/3后得到3018最優(yōu)解X=(18，4，0，0)T，最優(yōu)值Z=70O20301040(3,4)X(3)=(18,4)最優(yōu)解X=(18,4)最優(yōu)值Z=70X(1)=(0,0)2010x2x130X(2)=(0,10)單純形法全過程的計算，可以用列表的方法計算更為簡潔，這種表格稱為單純形表（表1）。計算步驟：1.求初始基可行解，列出初始單純形表，求出檢驗數(shù)。其中基變量的檢驗數(shù)必為零；2.判斷：（a）若λj≤０（j＝１，２，…，n）得到最優(yōu)解；（b）某個λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無界解(見例1.18)。（c）若存在λk>0且aik(i=1,…,m)不全非正，則進(jìn)行換基；第Ｌ個比值最小，選最小比值對應(yīng)行的基變量為出基變量，若有相同最小比值，則任選一個。aLk為主元素；

(c）求新的基可行解：用初等行變換方法將aLk

化為１,k列其它元素化為零（包括檢驗數(shù)行）得到新的可行基及基本可行解，再判斷是否得到最優(yōu)解。（b）選出基變量，求最小比值：3.換基：（a）選進(jìn)基變量設(shè)λk=max｛λj|λj>0｝,xk為進(jìn)基變量【例10】用單純形法求解【解】將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：不難看出x4、x5可作為初始基變量，單純法計算結(jié)果如表2所示。Cj12100bθCBXBx1x2x3x4x50x42－3210150x51/3150120λj12100

0x42x2λj

1x1

2x2

λj

表21/3150120301713751/30－90－2M2025601017/31/31250128/9－1/92/335/300－98/9－1/9－7/3最優(yōu)解X=(25，35/3，0，0，0)T，最優(yōu)值Z=145/3【例11】用單純形法求解

【解】

這是一個極小化的線性規(guī)劃問題,可以將其化為極大化問題求解,也可以直接求解,這時判斷標(biāo)準(zhǔn)是：λj≥0(j=1，…，n)時得到最優(yōu)解。容易觀察到,系數(shù)矩陣中有一個3階單位矩陣,x3、x4、x5為基變量。目標(biāo)函數(shù)中含有基變量x4,由第二個約束得到x4=6+x1－x2，并代入目標(biāo)函數(shù)消去x4得XBx1x2x3x4x5bθx3x4x51-16[1]121000100015→6215621/2λj1-1↑000

x2x4x51-241001-1-20100015111

λj20100

表中λj≥0,j=1,2,…,5所以最優(yōu)解為X=(0,5,0,1,11,)最優(yōu)值

Z=2x1－2x2－x4=－2×5－1=－11極小值問題,注意判斷標(biāo)準(zhǔn),選進(jìn)基變量時,應(yīng)選λj<0的變量xj進(jìn)基。表3【例12】求解線性規(guī)劃【解】化為標(biāo)準(zhǔn)型初始單純形表為XBx1x2x3x4bx3x432－2－1100114λj－1100

λ2=1>0,x2進(jìn)基，而a12<0，a22<0，沒有比值，從而線性規(guī)劃的最優(yōu)解無界。由模型可以看出，當(dāng)固定x1使x2→+∞且滿足約束條件，還可以用圖解法看出具有無界解?！纠?3】求解線性規(guī)劃【解】:化為標(biāo)準(zhǔn)型后用單純形法計算如下表所示XBx1x2x3x4x5bθ(1)x3x4x5－111[2]2－11000100014→10225—λj24↑000(2)x2x4x5－1/2[2]1/21001/2－11/201000126→4—38λj4↑0－200(3)x2x1x50101001/4－1/2[3/4]1/41/2－1/40017/235/2→14—10/3λj000↑－20(4)x2x1x30101000011/31/3－1/3－1/32/34/38/314/310/3λj000－20

表(3)中λj全部非正,則最優(yōu)解為:

表(3)表明,非基變量x3的檢驗數(shù)λ3=0,x3若增加,目標(biāo)函數(shù)值不變,即當(dāng)x3進(jìn)基時Z仍等于20。使x3進(jìn)基

x5出基繼續(xù)迭代,得到表(4)的另一基本最優(yōu)解X(1),X(2)是線性規(guī)劃的兩個最優(yōu)解，它的凸組合

仍是最優(yōu)解，從而原線性規(guī)劃有多重最優(yōu)解。唯一最優(yōu)解的判斷：最優(yōu)表中所有非基變量的檢驗數(shù)非零,則線規(guī)劃具有唯一最優(yōu)解

。多重最優(yōu)解的判斷:最優(yōu)表中存在非基變量的檢驗數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解。無界解的判斷:

某個λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無界解退化基本可行解的判斷:存在某個基變量為零的基本可行解。（三）對偶問題

對偶理論是線性規(guī)劃的重要內(nèi)容之一。隨著線性規(guī)劃問題研究的深入，人們發(fā)現(xiàn)對應(yīng)于每個線性規(guī)劃問題都伴生一個相應(yīng)的線性規(guī)劃問題。前者是由矩陣Ａ，右端向量ｂ和價值向量Ｃ定義的，稱之為原問題；后者也是由相同的數(shù)據(jù)集合Ａ，ｂ和Ｃ構(gòu)成的，稱之為原問題的對偶問題。一對原問題和對偶問題是緊密關(guān)聯(lián)的，它們不但有相同的數(shù)據(jù)集合，相同的最優(yōu)目標(biāo)函數(shù)值，而且在求得一個線性規(guī)劃的最優(yōu)解的同時，也同步得到對偶線性規(guī)劃的最優(yōu)解。對偶理論深刻地指示了原問題和對偶問題的內(nèi)在聯(lián)系，由對偶問題引伸出來的對偶解還有著重要的經(jīng)濟(jì)意義，是研究經(jīng)濟(jì)學(xué)的重要概念和工具之一。（1）對偶問題的提出例1、某工廠生產(chǎn)甲,乙兩種產(chǎn)品，這兩種產(chǎn)品需要在A,B,C三種不同設(shè)備上加工。每種甲、乙產(chǎn)品在不同設(shè)備上加工所需的臺時，它們銷售后所能獲得的利潤，以及這三種設(shè)備在計劃期內(nèi)能提供的有限臺時數(shù)均列于表。試問如何安排生產(chǎn)計劃，即甲,乙兩種產(chǎn)品各生產(chǎn)多少噸，可使該廠所獲得利潤達(dá)到最大。

設(shè)備每噸產(chǎn)品的加工臺時可供臺時數(shù)甲乙ABC359448364076利潤（元/噸）3230用圖解法或單純形法可求得最優(yōu)解

(元)

即在計劃期內(nèi)甲產(chǎn)品生產(chǎn)4/3噸，乙產(chǎn)品生產(chǎn)8噸，可以使總利潤達(dá)到最大，為元。

假設(shè)計劃期內(nèi)甲乙兩種產(chǎn)品各生產(chǎn)x1x2

噸，設(shè)備每噸產(chǎn)品的加工臺時可供臺時數(shù)甲乙ABC359448364076利潤（元/噸）3230

例1'

現(xiàn)在從另一個角度來考慮該工廠的生產(chǎn)問題:

假設(shè)該廠的決策者打算不再自己生產(chǎn)甲,乙產(chǎn)品，而是把各種設(shè)備的有限臺時數(shù)租讓給其他工廠使用，這時工廠的決策者應(yīng)該如何確定各種設(shè)備的租價。

設(shè)y1y2y3

分別為設(shè)備A，B，C每臺時的租價，約束條件：把設(shè)備租出去所獲得的租金不應(yīng)低于利用這些設(shè)備自行生產(chǎn)所獲得的利潤目標(biāo)函數(shù)：所獲租金總額最小．為什么要最小化？由此可得兩個對稱的線性規(guī)劃：矩陣形式：（2）對偶定義1、對稱形式（典則形式）的對偶定義

一對對稱形式的對偶規(guī)劃之間具有下面的對應(yīng)關(guān)系。

(1)若一個模型為目標(biāo)求“極大”，約束為“小于等于”的不等式，則它的對偶模型為目標(biāo)求“極小”，約束是“大于等于”的不等式。即“max，≤”和“min，≥”相對應(yīng)。

(2)從約束系數(shù)矩陣看：一個模型中為Ａ，則另一個模型中為AT。一個模型是m個約束，n個變量，則它的對偶模型為n個約束，m個變量。

(3)從數(shù)據(jù)b、c的位置看：在兩個規(guī)劃模型中，b和c的位置對換。

(4)兩個規(guī)劃模型中的變量皆非負(fù)。

標(biāo)準(zhǔn)形式的對偶定義推導(dǎo)過程：

若原問題是極小化問題，則對偶問題是極大化問題；若原問題是極大化問題，則對偶問題是極小化問題在原問題和對偶問題中，約束右端向量與目標(biāo)函數(shù)的系數(shù)向量恰好互換對于極小化問題的“≥”型約束(極大化問題的“≤”型約束)，相應(yīng)的對偶變量有非負(fù)限制；對于極小化問題的“≤”型約束(極大化問題的“≥”型約束)，相應(yīng)的對偶變量有非正限制；對于原問題的“=”型約束，相應(yīng)的對偶變量無正負(fù)限制對于極小化問題具有非負(fù)限制的變量(極大化問題具有非正限制的變量),在其對偶問題中，相應(yīng)的約束為“≤”型約束；對于極小化問題具有非正限制的變量(極大化問題具有非負(fù)限制的變量),在其對偶問題中，相應(yīng)的約束為“≥”型約束；對于原問題中無正負(fù)限制的變量，在其對偶問題中，相應(yīng)的約束為“=”型約束對偶規(guī)則【例15】寫出下面線性規(guī)劃的對偶規(guī)劃模型練習(xí)：寫出對偶規(guī)劃。（2）對偶理論對稱性：對偶問題的對偶是原問題弱對偶性：若x和y分別是(LP)和(DP)的可行解，則c’x≥b’y.可行解為最優(yōu)的充分條件：設(shè)x和y分別是(LP)和(DP)的可行解，若c’x=b’y，則x和y分別是(LP)和(DP)的最優(yōu)解.無界性：若(LP)和(DP)之一為無界解，則其對偶問題無可行解.對偶定理：若(LP)和(DP)均有可行解，則它們都有最優(yōu)解，且最優(yōu)值相同.最優(yōu)基本可行解之間的關(guān)系：若(LP)存在一個對應(yīng)基B的最優(yōu)基本可行解，則單純形乘子是(DP)的一個最優(yōu)解.互補松弛性：設(shè)x和y分別是(LP)和(DP)的可行解，則x和y分別是(LP)和(DP)的最優(yōu)解的充要條件為y’(Ax-b)=0，且

(c’-y’A)x=0.（3）對偶單純形法

由對偶理論可以知道，對于一個線性規(guī)劃問題，我們能夠通過求解它的對偶問題來找到它的最優(yōu)解。

對偶單純形法是求解線性規(guī)劃的另一的基本方法。由于它是根據(jù)對偶原理和單純形法的原理而設(shè)計出來的，因此稱為對偶單純形法。不能簡單理解為是求解對偶問題的單純形法。原始單純形法從一個基本可行解迭代到下一個基本可行解時，總是保持解的可行性不變，變化的只是檢驗數(shù)例如對于極大化問題而言，檢驗向量從部分分量不滿足逐步過渡到，一旦達(dá)到，也就達(dá)到了最優(yōu)解。由于，是對偶問題的可行解?？梢赃@樣理解原始單純形法的迭代過程：從基本可行解向最優(yōu)解的迭代過程，是在始終保持原問題可行性的條件下，其對偶解由不可行向可行轉(zhuǎn)化。一旦對偶解也成為可行解時，原問題的可行解即成為最優(yōu)解。也就是說，當(dāng)原問題解保持可行性條件下，其最優(yōu)性條件與對偶解可行這個條件是一致的。這為我們提供了另一條求解思路：在迭代過程中，始終保持對偶問題解的可行性，而原問題的解由不可行向可行性轉(zhuǎn)化，一旦原問題的解也滿足可行性條件，也就達(dá)到了最優(yōu)值。這就是對偶單純形方法的思路。對偶單純形法并不需要把原問題轉(zhuǎn)化為對偶問題，而是利用原問題與對偶問題的數(shù)據(jù)相同，只是所處的位置不同這一特點，直接在反映原問題的單純形表上進(jìn)行運算。對偶單純形法不要求向量,處理帶剩余變量的一些問題很方便。（2）確定換出變量根據(jù)，確定基變量xl

作為換出變量。檢驗xl

所在行各元素若所有alj≥0,則無可行解，停止計算。否則轉(zhuǎn)入(３)，（3）確定換入變量按最小比值原則，若確定非基變量xk

為換入變量。（4）以alk

為主元進(jìn)行旋轉(zhuǎn)變換，得新的單純形表，重復(fù)（2）-（4），直到求得最優(yōu)解。對偶單純形法的計算步驟如下（對于極大化目標(biāo)函數(shù)問題）：（1）根據(jù)原始線性規(guī)劃，列出初始單純形表，檢查b列數(shù)字和檢驗行元素，若b列數(shù)字全部非負(fù)，檢驗數(shù)全部非負(fù)，則已經(jīng)求得最優(yōu)解，停止計算。若b列中至少有一個負(fù)分量，檢驗數(shù)全部非正，則轉(zhuǎn)入（2）,【例16】用對偶單純形法求解解：先化為標(biāo)準(zhǔn)型

對偶單純形允許約束方程右端為負(fù)，因此可將方程2，3兩端同乘-1，可得含單位矩陣的標(biāo)準(zhǔn)型：據(jù)此列出初始單純形表，并施行對偶單純形法迭代步驟如下：-5/4-7/4000-16-W-1/41/40102x2

-2-1/4-3/40014x1

-35/43/41004x3

0-2/3000-7/3-20/3-W-1/30011/310/3x2

-21/3100-4/3-16/3x4

0101018x3

0000-2-30-W100-3-1-10x5

00101-1-2x4

00013218x3

0x5

x4

x3

x2

x1

bXB

CB

000-2-3C可得最優(yōu)解是是是是否否否否所有所有得到最優(yōu)解計算計算典式對應(yīng)原規(guī)劃的基本解是可行的典式對應(yīng)原規(guī)劃的基本解的檢驗數(shù)所有所有計算計算以為中心元素進(jìn)行迭代以為中心元素進(jìn)行迭代停沒有最優(yōu)解沒有最優(yōu)解單純形法

對偶單純形法對偶單純形法的優(yōu)點和應(yīng)用的前提條件對偶單純形法的優(yōu)點是原問題的初始解不要求是可行解，可以從非可行解開始迭代，從而省去了引入人工變量的麻煩。當(dāng)然對偶單純形法的應(yīng)用也是有前提條件的，這一前提條件就是對偶問題的解是基可行解。五、線性規(guī)劃的靈敏度分析1.靈敏度分析的內(nèi)涵

一個標(biāo)準(zhǔn)形式的線性規(guī)劃問題可由約束矩陣Ａ，右端項向量b，和價值向量Ｃ完全確定，假如一個線性規(guī)劃問題對于給定的數(shù)據(jù)集合Ａ，b，Ｃ有最優(yōu)解，則最優(yōu)解。最優(yōu)目標(biāo)函數(shù)值，其中Ｂ為最優(yōu)基。但是線性規(guī)劃問題所對應(yīng)的數(shù)據(jù)集合Ａ，b，Ｃ常常是通過預(yù)測或估計所得到的統(tǒng)計數(shù)據(jù)，在實際使用中，不免會有一定的誤差。而且隨著市場環(huán)境，工藝條件和資源數(shù)量的改變，這些數(shù)據(jù)完全可能發(fā)生變化。因此有必要來分析一下當(dāng)這些數(shù)據(jù)發(fā)生波動時，對目前的最優(yōu)解，最優(yōu)值或者最優(yōu)基會產(chǎn)生什么影響，這就是所謂的靈敏度分析。

靈敏度分析主要討論如下二類問題：線性規(guī)劃的數(shù)據(jù)集合在什么范圍內(nèi)波動將不影響最優(yōu)解或最優(yōu)基？

若最優(yōu)解發(fā)生變化，應(yīng)如何用最簡單的方法找到新的最優(yōu)解。為討論方便，以下列出標(biāo)準(zhǔn)型線性規(guī)劃問題最優(yōu)單純形表的一般形式，其中B為線性規(guī)劃問題的最優(yōu)基：CC1

C2

…Cn

CB

XB

bx1

x2

…xn

CB1

XB1

B-1bB-1A=B-1(P1，P2，…，Pn)CB2

XB2

::CBm

XBm

ZCBB-1bC-CBB-1A1.價值向量C的改變當(dāng)價值向量由時，最優(yōu)單純形表發(fā)生變化的只是檢驗行的有關(guān)數(shù)據(jù)，其中基變量檢驗數(shù)保持為零。非基變量檢驗數(shù)應(yīng)修改為：目標(biāo)函數(shù)值應(yīng)為。只要變化以后的非基變量檢驗數(shù)那么原最優(yōu)解仍然為最優(yōu)。至于目標(biāo)函數(shù)值是否改變，取決于基變量價值系數(shù)的改變量以下分別就價值系數(shù)對應(yīng)非基變量或基變量兩種情況加以討論：若是非基變量的價值系數(shù)，為該價值系數(shù)的改變量。那么在最優(yōu)表中只有

的檢驗數(shù)發(fā)生變化。由只要即就可以保持現(xiàn)行最優(yōu)解仍為最優(yōu)，由此可以確定價值系數(shù)的可變化范圍。若超出穩(wěn)定范圍，那么的檢驗數(shù)，當(dāng)前解已不是最優(yōu)解。此時必須以修改后的單純形表出發(fā)，重新進(jìn)行單純形迭代，直至求出新的最優(yōu)解。非基變量價值系數(shù)的變化，可能使最優(yōu)基Ｂ改變，從而導(dǎo)致最優(yōu)解和最優(yōu)值的改變。

若是某基變量的價值系數(shù)，為價值系數(shù)的改變量。由于為基變量，所以在最優(yōu)表中所有的非基變量檢驗數(shù)均發(fā)生了變化，由只要非基變量檢驗數(shù)：

或即可最優(yōu)解仍然保持為最優(yōu)，其中為原最優(yōu)表中非基變量檢驗數(shù)，為最優(yōu)表系數(shù)矩陣中基變量所在行中所有非基變量對應(yīng)的系數(shù)。由上式可得到一個聯(lián)列不等式組，求解該不等式組就可得到價值系數(shù)的可變動范圍。基變量價值系數(shù)的變化，可能使最優(yōu)基Ｂ改變，從而導(dǎo)致最優(yōu)解的改變。而最優(yōu)值則一定改變。【例17】

、某工廠用甲乙兩種原料生產(chǎn)A，B，C，D四種產(chǎn)品，每種產(chǎn)品的利潤，現(xiàn)有原料數(shù)及每種產(chǎn)品消耗原料定額如表所示：

原料（公斤）產(chǎn)品（萬件）供應(yīng)量ABCD甲乙321040021/2183利潤（萬元/萬件）985019問應(yīng)該怎樣組織生產(chǎn)，才能使總利潤最大，若產(chǎn)品Ａ或Ｃ的利潤產(chǎn)生波動，波動范圍多大時，原最優(yōu)解保持不變？解：設(shè)生產(chǎn)Ａ，Ｂ，Ｃ，Ｄ四種產(chǎn)品各萬件，則此問題的線性規(guī)劃模型為：標(biāo)準(zhǔn)化，引入松弛變量x5,x6，，

利用單純形表求解：-4-2/300-13/3-10/388Z24/3012/3-10/3-1/2-1/310-1/64/321x4x319500202-3-1084Z2612/301/21/3-5/30011/401/213/2x1x395098013/20-2575Z1-3203/21-50011/401/233/2x5x3050985019000Z9/53/232104100021/201183x5x600

x1

x2x3

x4x5x6bXBCBθ98501900C即最優(yōu)生產(chǎn)方案是生產(chǎn)Ｃ產(chǎn)品1萬件，Ｄ產(chǎn)品2萬件，不生產(chǎn)Ａ,Ｂ兩種產(chǎn)品?？傻米畲罄麧櫈?8萬元。C

98501900θCBXBb

x1

x2x3

x4x5x61950x4x32124/3012/3-10/3-1/2-1/310-1/64/3Z88-4-2/300-13/3-10/3最優(yōu)表：(1)若Ａ產(chǎn)品的利潤，有改變量。因為為非基變量，由推得或（萬元）時原最優(yōu)解不變，最優(yōu)利潤值（萬元）也不變。(２)若Ｃ產(chǎn)品的利潤，有改變量。因為為基變量，由推得即當(dāng)或時原最優(yōu)解不變，最優(yōu)利潤值（萬元）2.右端項向量b的改變

當(dāng)右端項向量b由時，改變的只是表中右端常數(shù)列。此時基變量，目標(biāo)函數(shù)值。而檢驗行的檢驗向量保持不變。右端項向量b的波動會使最優(yōu)解和最優(yōu)目標(biāo)函數(shù)值發(fā)生變化，但原最優(yōu)解的檢驗向量仍能保持非正。為了使B可行，只要或若，因為檢驗向量仍保持非正，因此可用對偶單純形法再次進(jìn)行迭代，直到求得新最優(yōu)解。右端列向量b變化時，最優(yōu)解和最優(yōu)值一定改變。因此我們主要討論右端列向量b變化時，最優(yōu)基Ｂ是否改變【例8】、在例17中，若想增加甲種原料，問增加多少時原最優(yōu)基不變？

解：設(shè)甲種原料的改變量為,則由即

由此可以推得，即當(dāng)時，原最優(yōu)基不變。此時最優(yōu)解或最優(yōu)目標(biāo)函數(shù)值

(萬元)3.約束矩陣A的改變

約束矩陣A的改變可能導(dǎo)致不同的最優(yōu)解和最優(yōu)基.以下只涉及兩種較簡單的情形：增加或減少一個變量，增加或減少一個約束條件。

以下討論假設(shè)原線性規(guī)劃問題有一個最優(yōu)解其中Ｂ為最優(yōu)基，且約束矩陣被劃分為

增加或減少一個變量（1）增加一個新變量假設(shè)在獲得原線性規(guī)劃的最優(yōu)解之后，又發(fā)現(xiàn)了一個新變量，其對應(yīng)的價值系數(shù)為，在新的約束矩陣中對應(yīng)的系數(shù)列向量為，于是可得如下新的線性規(guī)劃問題：設(shè)，則

為新線性規(guī)劃問題的一個可行解。因此可在此基礎(chǔ)上開始單純形法，求新的最優(yōu)解。如果，則含的當(dāng)前解是新問題的最優(yōu)解。否則以為換入變量進(jìn)行基變換，繼續(xù)使用單純形算法為新的線性規(guī)劃尋求一個最優(yōu)解。（2）減少一個變量如果必須把某個變量從決策變量中去掉，那么原最優(yōu)解在新的線性規(guī)劃中一定發(fā)生改變。我們討論的目標(biāo)是如何用最小的工作量去尋求新的最優(yōu)解。如果原最優(yōu)解中的，則只需將從原最優(yōu)解中剔除即可保持最優(yōu)。如果原最優(yōu)解中的（此時必為基變量），則必須重新計算新的解。為此可建立一個輔助線性規(guī)劃：由于約束方程組沒有改變，因此原最優(yōu)解在輔助線性規(guī)劃中可以作為初始基本可行解用于單純形算法。如果輔助線性規(guī)劃最優(yōu)解的目標(biāo)函數(shù)值為零，則用此最優(yōu)解剔除以后，可得新的線性規(guī)劃問題的一個初始基本可行解，經(jīng)有限次迭代，即可求出新問題的最優(yōu)解。否則從原來問題中去除而得到的新的線性規(guī)劃必定是不可行的。增加或減少一個約束（1）