1第一章線性及單純形法

第1章線性規(guī)劃與單純形法本章要點：1.線性規(guī)劃問題的數(shù)學模型2.線性規(guī)劃問題的基本理論3.線性規(guī)劃問題的求解例1.1：美佳公司計劃制造I，II兩種家電產(chǎn)品。已知各制造一件時分別占用的設備A，B的臺時、調(diào)試工序時間及每天可用于這兩種家電的能力、各售出一件I，II產(chǎn)品時的獲利情況，如表所示。問該公司應制造這兩種家電各多少件，可使獲取的總利潤最大？項目III每天可用能力設備A（h）0515設備B（h）6224調(diào)試工序（h）115利潤（元）21一、問題的提出1.1線性規(guī)劃問題與及其數(shù)學模型Max解：設x1和x2分別表示美佳公司制造家電I和II的數(shù)量。則該問題可用線性規(guī)劃模型表示如下：1.1線性規(guī)劃問題與及其數(shù)學模型s.t.

表示“約束于”例1.2某工地租賃機械甲和乙來安裝A、B、C三種構件。已知這兩種機械每天的安裝能力如表所示。而工程任務要求共安裝250根A構件、300根B構件和700根C構件；又知機械甲每天租賃費為250元，機械乙每天租賃費為350元，試決定租賃機械甲和乙各多少天，才能使總租賃費最少？65A206機械乙108機械甲 CB每天安裝能力（根）機械構件1.1線性規(guī)劃問題與及其數(shù)學模型

設租賃甲X1天，機械乙X2天，為滿足A、B、C的安裝要求，則用數(shù)學模型可描述為：Min1.1線性規(guī)劃問題與及其數(shù)學模型1.1線性規(guī)劃問題與及其數(shù)學模型例1.3某公司1－4月份擬租用倉庫。已知各月份所需倉庫面積如下表，倉庫租借費用隨合同期而定，期限越長，折扣越大，如下表?？筛鶕?jù)需要每月初辦理租借合同，每份合同具體規(guī)定租用面積和期限。每次辦理可簽一份，也可簽若干份面積和租期不同的合同。試確定簽訂租借合同的最優(yōu)策略，使4個月總租借費用最少。月份1234所需倉庫面積15102012合同期限1個月2個月3個月4個月單位面積租費28004500600073001.1線性規(guī)劃問題與及其數(shù)學模型設xij為第i個月初簽訂的租期為j個月的倉庫面積合同，因5月份后不需租倉庫，故x24,x33,x34,x42,x43,x44均為零。則數(shù)學模型為：MinZ＝2800(x11+x21+x31+x41)(x12+x22+x32)(x13+x23)x14二、線性規(guī)劃的數(shù)學模型規(guī)劃問題的數(shù)學模型有三個組成要素：（1）（決策）變量：問題中的未知量，可由決策者決定；（2）目標函數(shù)：決策變量的函數(shù)，按優(yōu)化目標加Max或Min;

（3）約束條件：決策變量取值時受到各種資源條件的限制；

線性規(guī)劃數(shù)學模型：決策變量的取值是連續(xù)的，可以是整數(shù)、分數(shù)、小數(shù)或?qū)崝?shù)，目標函數(shù)是決策變量的線性函數(shù)，約束條件是含決策變量的線性等式或不等式。1.1線性規(guī)劃問題與及其數(shù)學模型二、線性規(guī)劃的數(shù)學模型

實際問題中“線性”的含義：（1）嚴格的比理性：如生產(chǎn)某產(chǎn)品對資源的消耗量和可獲取的利潤，同其生產(chǎn)數(shù)量嚴格成比例；（2）可疊加性：如生產(chǎn)多種產(chǎn)品時，可獲取的總利潤是各項產(chǎn)品的利潤之和，對某資源的消耗量等于各產(chǎn)品對該資源的消耗量之和；（3）可分性：模型中的變量可取值小數(shù)、分數(shù)或?qū)崝?shù)；（4）確定性：模型中的參數(shù)cj，aij，bi均為確定的常數(shù)。1.1線性規(guī)劃問題與及其數(shù)學模型線性規(guī)劃問題的數(shù)學模型可表示為：Max(Min)1.1線性規(guī)劃問題與及其數(shù)學模型xj

(j=1,…,n):規(guī)劃問題中的n個變量，取值受m項資源限制；cj(j=1,…,n):價值系數(shù)；bi

(i=1,…,m):第i種資源的擁有量；aij(技術系數(shù)):變量xj取值1個單位時所消耗第i種資源的數(shù)量。線性規(guī)劃模型可簡寫為：Max(或Min)1.1線性規(guī)劃問題與及其數(shù)學模型用向量形式表達時，設

C=(c1,c2,…,cn),1.1線性規(guī)劃問題與及其數(shù)學模型約束方程組系數(shù)矩陣則線性規(guī)劃模型可用矩陣和向量描述為：1.1線性規(guī)劃問題與及其數(shù)學模型

變量xj取值一般為非負，但數(shù)學意義上也可以有xj≤0,甚至xj無約束。線性規(guī)劃模型的標準形式規(guī)定如下：1.1線性規(guī)劃問題與及其數(shù)學模型

要求：目標函數(shù)求極大值，約束條件全為等式，約束條件右端常數(shù)項bi全為非負值，變量xj全為非負值。線性規(guī)劃問題的標準型也可表示為：Max標準型的向量形式為:maxZ=CX非標準形式的線性規(guī)劃可化為標準形式：（1）目標函數(shù)為求極小值時，即令z’=-z,求minz等價于求max(-z),即化為1.1線性規(guī)劃問題與及其數(shù)學模型（2）約束條件右端項bi<0時，只需將等式或不等式兩端同乘(-1),則右端項bi大于零。1.1線性規(guī)劃問題與及其數(shù)學模型（3）約束條件為不等式。當為≤時，引入“松弛變量”使之變?yōu)榈仁?，當為≥時，引入“剩余變量”使之變?yōu)榈仁?，這些引入的變量在目標函數(shù)中系數(shù)為零。（4）取值無約束的變量。令x=x’-x’’,x’和x’’均≥0（5）對x≤0的情況，令x’=-x例:將下面的線性規(guī)劃問題化成標準型MaxMax1.1線性規(guī)劃問題與及其數(shù)學模型又例：將下述線性規(guī)劃化為標準形式minz=x1+2x2+3x31.1線性規(guī)劃問題與及其數(shù)學模型解：(1)令z’=-z(2)令x1’=-x1(3)令x3=x3’-x3’’,其中x3’和x3’’均≥0，引入松弛變量x4、x5，則標準形式為：maxz’=x1’-2x2-3x3’+3x3’’+0x4+0x51.2圖解法圖解法：適用于兩個決策變量的情形鞍面法： 1992年中國沈陽化工學院尚毅教授發(fā)明內(nèi)點法：1984年美國籍印度數(shù)學家Karmarker發(fā)明橢球法：1979年蘇聯(lián)數(shù)學家Khachiyan發(fā)明單純形法：1952年美國斯坦福大學教授Dantzig發(fā)明，可以解決1.5萬至2萬個決策變量的問題1.2圖解法

圖解法：只有2個變量的線性規(guī)劃模型，可以在平面上作圖的方法求解。最優(yōu)解：可行域中使得目標函數(shù)達到最優(yōu)的可行解稱為最優(yōu)解。可行域：通常線性規(guī)劃問題含有多個可行解，全部可行解的集合稱為可行域。可行解：一個線性規(guī)劃問題有解，是指能找出一組xj

（xj=1,…,n），滿足約束條件，則這組xj為問題的可行解。1.2圖解法一、圖解法max z=x1+3x2 x1+x2≤6s.t.-x1+2x2≤8 x1≥0,x2≥0可行域目標函數(shù)等值線最優(yōu)解64-860x1x2問題：

——

多邊形，而且是“凸”形的多邊形。

最優(yōu)解在什么位置獲得？

——

在邊界，而且是在某個頂點獲得。

線性規(guī)劃的可行域是一個什么形狀？1.2圖解法圖解法求解步驟：（1）建立直角坐標系；（2）根據(jù)線性規(guī)劃問題的約束條件和非負條件畫出可行域；（3）作出目標函數(shù)等值線Z=c（c為一常數(shù)），并使其平移求得最優(yōu)解。1.2圖解法線性規(guī)劃的解的特殊情況唯一解X1X2X1X222X1X221無窮解例max

z=x1+x2s.t.2x1+2x2<=4x1>=0,x2>=0無界解（少了約束條件）例maxz=x1+2x2s.t.x1>=1x2>=21.2圖解法無可行解（有矛盾約束）例minz=x1-x2s.t.x1>=2x1<=1X1X222無可行解域1.3單純形法基本原理Max(i=1,2,…m)(1)(2)(3)1.概念可行解：滿足上面模型中的（2）和（3）式的解X；最優(yōu)解：滿足上面模型中的（1）的可行解X；基（矩陣）：A為約束方程組的m×n階系數(shù)矩陣，其秩為m，若B是A中的m×m階滿秩子矩陣，則B是線性規(guī)劃問題的一個基（矩陣）。設B=[P1，P2，….，Pm]，則

Pj(j=1,..,m)為基向量，與Pj對應的變量xj為基變量。非基變量：X中除基變量外的變量；基解：在方程AX=b中，令所有非基變量xm+1=…=xn=0，由m個約束方程可解出m個基變量的唯一解Xb=(x1,…,xm)T，加上非基變量的0值得到線性規(guī)劃問題的基解：X=(x1,…,xm,0,…,0)T。一般m<n，故基解的個數(shù)≤Cnm

；基可行解：滿足變量非負，即滿足（3）式的基解?？尚谢簩诨尚薪獾幕Q為可行基。例：設線性規(guī)劃問題如下，試找出其全部基解，指出其中的基可行解，并確定最優(yōu)解。maxz=2x1+3x2+x3x1+x3=5x1+2x2+x4=10x2+x5=4x1,x2,x3,x4,x5

≥0s.t.解：全部基解如表所示，打為基可行解，*為最優(yōu)解。序號x1x2x3x4x5z基可行解10051045

20452017

35005410

40550-1205100-50415652.5001.517.5

7540-302282430019*總結：各種解之間的關系如下圖所示：基解可行解最優(yōu)解基可行解1.概念凸集：設C是一個點集，若C中任意兩點X1，X2都滿足：則稱C為凸集。

簡單地講，如果C中任意兩點的連線上所有點也都是集合C中的點，則C為凸集。例：以下哪些是凸集？(a)(b)(c)(d)答：(a)(b)是凸集，(c)(d)不是凸集1.概念頂點：C為凸集，點X∈C，若C中不存在兩點X1,X2,滿足：則稱X為凸集C的頂點。

簡單地講，如果C中不存在任意兩點X1,X2,使X成為這兩點連線上的點，則X為凸集C的頂點。2.基本定理定理1：若線性規(guī)劃問題存在可行解，則問題的可行域是凸集。定理2：線性規(guī)劃問題的基可行解X對應線性規(guī)劃問題可行域（凸集）的頂點。定理3：若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解。基本結論：線性規(guī)劃問題的所有可行解構成的集合是凸集；線性規(guī)劃問題的每一個基可行解都有對應可行域的一個頂點；若線性規(guī)劃問題有最優(yōu)解，必定在可行域的某個頂點上達到。1.3單純形法原理1.單純形法的基本思路若線性規(guī)劃問題存在最優(yōu)解，一定有一個基可行解是最優(yōu)解。因此，先找出一個（初始）基可行解，判斷它是否為最優(yōu)解，若不是，則轉(zhuǎn)換到相鄰的基可行解，并使目標函數(shù)值不斷增大，直到找到最優(yōu)解。如何確定初始基可行解？對于標準型的線性規(guī)劃問題：max

其約束方程組系數(shù)矩陣A中總會存在一個m階單位矩陣：如何確定初始基可行解？

當約束條件均為≤時，引入m個松弛變量，則松弛變量系數(shù)矩陣即為m階單位矩陣。若約束條件均為≥時，可以人為產(chǎn)生一個單位矩陣。

單位矩陣中，每個列向量Pj(j=1,…,m)都為基向量，其對應的變量xj為基變量，其它變量xm+1,…,xn為非基變量。令所有非基變量為0，可找到一個解：X=(x1,…,xm,xm+1,…,xn)T=(b1,b2,…,bm,0,…,0)T則X為一個基可行解，可作為初始基可行解。如何確定初始基可行解？例：請對下面線性規(guī)劃問題確定一個初始基可行解。Max解：先化成標準型Max因為存在2階單位矩陣，對應基變量為x4和x5，令其它非基變量x1,x2,x3都為0，解方程得到一個初始基可行解：X=(0,0,0,1,3)T對于標準型的線性規(guī)劃問題：max其單純形法的求解步驟如下：1.4單純形法計算步驟1.4單純形法計算步驟（1）求初始基可行解，列出初始單純形表為檢驗基可行解是否最優(yōu)，要與相鄰基可行解進行比較。每次計算出一個新的基可行解，就要重畫一個單純形表。非基變量xj下的數(shù)字是對應Pj向量由基向量線性組合時的系數(shù)，即：Pj=a1jP1+a2jP2+…+amjPm表11.4單純形法計算步驟檢驗數(shù)(cj-zj)用來檢驗基可行解是否為最優(yōu)解。2.最優(yōu)性檢驗若所有檢驗數(shù)(cj-zj)≤0，且基變量中不含人工變量時，表中基可行解即為最優(yōu)解，計算結束。若存在(cj-zj)>0，轉(zhuǎn)下一步。1.4單純形法計算步驟3.轉(zhuǎn)換到相鄰的目標函數(shù)值更大的基可行解，列出新的單純形表（1）確定換入基的變量。只要檢驗數(shù)σj>0,即(cj-zj)>0,對應的變量xj可作為換入基的變量，當有兩個以上檢驗數(shù)大于0，一般最大檢驗數(shù)值對應的變量xk作為換入變量。（2）確定換出基的變量。根據(jù)下面公式確定換出變量xl

alk稱為主元素，它決定了從一個基可行解到相鄰基可行解的轉(zhuǎn)移去向。1.4單純形法計算步驟（3）用換入變量xk替換基變量中換出變量xl，得到一個新的基矩陣，對應這個基矩陣可以找出新的基可行解，相應地可畫出新的單純形表，如下表所示。表21.4單純形法計算步驟

要使新表（表2）中的基矩陣仍然是單位矩陣，必須對舊表進行行的初等變換，然后將變換結果填入新表中。（1）將舊表主元素所在l行數(shù)字除以主元素alk，得到新表的值

（2）將新表中剛計算得到的第l行數(shù)字乘上(-aik)加到舊表的第i行數(shù)字上，得到的值寫入新表相應行中，即計算新表各檢驗數(shù)，進行最優(yōu)解檢驗。重復直至結束。例：用單純形法求解下面線性規(guī)劃問題解：先將線性規(guī)劃問題化為標準形式：其約束條件系數(shù)矩陣為：P3,P4,P5構成單位矩陣，即構成一個基，對應變量x3,x4,x5為基變量，令非基變量x1,x2=0,得到一個初始基可行解：X=(0,0,15,24,5)T列出初始單純形表cj→21000CB基bx1x2x3x4x50x315051000x424[6]20100x5511001cj-zj21000表中有大于零的檢驗數(shù)，其基可行解不是最優(yōu)解。由于σ1>σ2>0，故x1為換入變量。將b列除以P1（換入變量對應列）的同行數(shù)字并取最小值：以此確定6為主元素，其對應的x4為換出變量。用x1替換基變量x4，得到一個新的基P3,P1,P5,列出新的單純形表如下,計算出新的基可行解。cj→21000CB基bx1x2x3x4x50x315051002x1412/601/600x510[4/6]0-1/61cj-zj01/30-1/30

由于還存在大于零的檢驗數(shù)σ2

，故重復上述步驟，x2為換入變量，x5為換出變量，計算得到新的單純形表如下：cj→21000CB基bx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cj-zj000-1/4-1/2

此時檢驗數(shù)全部小于或等于0

，且基變量不含人工變量，表中基可行解為最優(yōu)解，即：X=(7/2,3/2,15/2,0,0)T，代入得目標函數(shù)值為z=17/21.5單純形法的進一步討論（1）人工變量法（大M法）線性規(guī)劃問題約束條件系數(shù)矩陣中含有單位矩陣時，以它作為初始基，求初始基可行解并作出初始單純形表。若其約束條件系數(shù)矩陣不含單位矩陣如何處理？Max加入人工變量化標準形式如下:例：MaxMaxx6,x7是人為添加的，即人工變量，添加后P4,P6,P7構成單位矩陣，可以求初始基可行解。在最優(yōu)解中人工變量全部必須為0，以滿足約束條件。在目標函數(shù)中“-M”為任意大的負值（M>0），稱為“罰因子”，只要人工變量取值大于零，目標函數(shù)就不可能最優(yōu)。在單純形法迭代過程中，M可作為一個數(shù)學符號一起運算。

此時x4,x6,x7為基變量，令非基變量x1,x2,x3,x5均為0，求得初始基可行解X=(0,0,0,4,0,1,9)T,建立初始單純形表，迭代過程如下表。θi6 [6] 0 4 0 3 -3 11 -2 1 -1 0 -1 1 03 3 0 2 1 1 -1 0x4x2x700-Mcj-zj 6M-304M+103M-4M01--1基 b x1 x2 x3 x4 x5 x6 x7CBCj -3 0 1 0 0 -M -M4 1 1 1 1 0 0 01 -2 [1] -1 0 -1 1 09 0 3 1 0 0 0 1x4x6x70-M-Mcj-zj-2M-34M10-M00413基 b x1 x2 x3 x4 x5 x6 x7CBCj -3 0 1 0 0 -M -Mx4x2x100-3cj-zj-9/20 0 0 0 1 -1/2 1/2 -1/21 1 0 [2/3] 0 1/2 -1/2 1/63 0 1 1/3 0 0 0 1/300303/2-M-3/2-M+1/2θi--93/23/2 3/2 0 1 0 3/4 -3/4 1/45/2 -1/21 0 0 -1/4 1/4 1/4000 01-1/21/2-1/2x4x2x3001cj-zj000-3/4-M+3/4-M-1/4最優(yōu)解X=(0,5/2,3/2,0,0,0,0)T（2）兩階段法

用人工變量