1第一章線性及單純形法

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

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

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

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

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

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

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

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

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

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

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

圖解法：只有2個(gè)變量的線性規(guī)劃模型，可以在平面上作圖的方法求解。最優(yōu)解：可行域中使得目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解稱為最優(yōu)解?？尚杏颍和ǔ＞€性規(guī)劃問題含有多個(gè)可行解，全部可行解的集合稱為可行域。可行解：一個(gè)線性規(guī)劃問題有解，是指能找出一組xj

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

——

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

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

——

在邊界，而且是在某個(gè)頂點(diǎn)獲得。

線性規(guī)劃的可行域是一個(gè)什么形狀？1.2圖解法圖解法求解步驟：（1）建立直角坐標(biāo)系；（2）根據(jù)線性規(guī)劃問題的約束條件和非負(fù)條件畫出可行域；（3）作出目標(biāo)函數(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ī)劃問題的一個(gè)基（矩陣）。設(shè)B=[P1，P2，….，Pm]，則

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

；基可行解：滿足變量非負(fù)，即滿足（3）式的基解?？尚谢簩?duì)應(yīng)于基可行解的基稱為可行基。例：設(shè)線性規(guī)劃問題如下，試找出其全部基解，指出其中的基可行解，并確定最優(yōu)解。maxz=2x1+3x2+x3x1+x3=5x1+2x2+x4=10x2+x5=4x1,x2,x3,x4,x5

≥0s.t.解：全部基解如表所示，打?yàn)榛尚薪猓?為最優(yōu)解。序號(hào)x1x2x3x4x5z基可行解10051045

20452017

35005410

40550-1205100-50415652.5001.517.5

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

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

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

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

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

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

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

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

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

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

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

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

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

此時(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）兩階段法

用人工變量