第二章+線性規(guī)劃課件

*第二章線性規(guī)劃2.1線性規(guī)劃模型2.2線性規(guī)劃理論2.3線性規(guī)劃的單純形法2.4單純形法的進(jìn)一步討論2.5改進(jìn)的單純形法*2.1線性規(guī)劃模型

例:某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三種設(shè)備可利用的時(shí)數(shù)如下表所示：

產(chǎn)品甲產(chǎn)品乙設(shè)備能力（h）設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤(rùn)（元/件）15002500

*

問(wèn)題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤(rùn)？解：設(shè)變量xi為第i種（甲、乙）產(chǎn)品的生產(chǎn)件數(shù)（i＝1，2）。根據(jù)題意，我們知道兩種產(chǎn)品的生產(chǎn)受到設(shè)備能力（機(jī)時(shí)數(shù)）的限制。對(duì)設(shè)備A，兩種產(chǎn)品生產(chǎn)所占用的機(jī)時(shí)數(shù)不能超過(guò)65，于是我們可以得到不等式：3x1

+2x2

≤65；對(duì)設(shè)備B，兩種產(chǎn)品生產(chǎn)所占用的機(jī)時(shí)數(shù)不能超過(guò)40，于是我們可以得到不等式：2x1

+x2

≤40；2.1線性規(guī)劃模型*

對(duì)設(shè)備C，兩種產(chǎn)品生產(chǎn)所占用的機(jī)時(shí)數(shù)不能超過(guò)75，于是我們可以得到不等式：3x2

≤75；另外，產(chǎn)品數(shù)不可能為負(fù)，即x1,x2≥0。同時(shí)，我們有一個(gè)追求目標(biāo)，即獲取最大利潤(rùn)。于是可寫出目標(biāo)函數(shù)z為相應(yīng)的生產(chǎn)計(jì)劃可以獲得的總利潤(rùn)：z=1500x1+2500x2

。綜合上述討論，在加工時(shí)間以及利潤(rùn)與產(chǎn)品產(chǎn)量成線性關(guān)系的假設(shè)下，把目標(biāo)函數(shù)和約束條件放在一起，可以建立如下的線性規(guī)劃模型：2.1線性規(guī)劃模型*目標(biāo)函數(shù)Maxz=1500x1+2500x2

約束條件s.t.3x1+2x2≤652x1+x2≤403x2≤75

x1,x2≥0

2.1線性規(guī)劃模型*

這是一個(gè)典型的利潤(rùn)最大化的生產(chǎn)計(jì)劃問(wèn)題。其中，“Max”是英文單詞“Maximize”的縮寫，含義為“最大化”；“s.t.”是“subjectto”的縮寫，表示“滿足于……”。因此，上述模型的含義是：在給定條件限制下，求使目標(biāo)函數(shù)z達(dá)到最大的x1,x2

的取值。它是一個(gè)目標(biāo)函數(shù)、約束函數(shù)都是線性函數(shù)的最優(yōu)化問(wèn)題，即線性規(guī)劃問(wèn)題。2.1線性規(guī)劃模型*一般形式

目標(biāo)函數(shù)：Min(Max)z=c1x1

+c2x2

+…+cnxn

約束條件：

a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2

...am1x1+am2x2

+…+amnxn≤(=,≥)bm

x1，x2，…

，xn≥02.1線性規(guī)劃模型*標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：Minz=c1x1+c2x2+…

+cnxn

約束條件：a11x1+a12x2+

…

+a1nxn

=

b1a21x1+a22x2+…

+a2nxn

=b2

...am1x1+am2x2+…+amnxn

=bm

x1，x2，…

，xn

≥02.1線性規(guī)劃模型*

可以看出，線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個(gè)特點(diǎn)：目標(biāo)最小化、約束為等式、決策變量均非負(fù)、右端項(xiàng)非負(fù)。對(duì)于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題，我們總可以通過(guò)以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式:2.1線性規(guī)劃模型*1.極大化目標(biāo)函數(shù)的問(wèn)題：設(shè)目標(biāo)函數(shù)為

Maxf=c1x1

+c2x2

+…+cnxn

則可以令z

＝-f

，該極大化問(wèn)題與下面的極小化問(wèn)題有相同的最優(yōu)解，即

Maxz=-c1x1

-c2x2-…-cnxn

但必須注意，盡管以上兩個(gè)問(wèn)題的最優(yōu)解相同，但他們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào)，即

Minz

＝-Maxf2.1線性規(guī)劃模型*2、約束條件不是等式的問(wèn)題：設(shè)約束條件為

ai1x1+ai2x2+…+ainxn

≤bi

可以引進(jìn)一個(gè)新的變量s

，使它等于約束右邊與左邊之差

s=bi–(ai1x1

+ai2x2

+…+ainxn

)

顯然，s

也具有非負(fù)約束，即s≥0，這時(shí)新的約束條件成為

ai1x1+ai2x2+…+ainxn+s=bi2.1線性規(guī)劃模型*

當(dāng)約束條件為

ai1x1+ai2x2+

…

+ainxn

≥bi

時(shí)，類似地令

s=(ai1x1+ai2x2+…+ainxn)-bi

顯然，s

也具有非負(fù)約束，即s≥0，這時(shí)新的約束條件成為

ai1x1+ai2x2+…+ainxn-s=bi

2.1線性規(guī)劃模型*

為了使約束由不等式成為等式而引進(jìn)的變量s稱為“松弛變量”。如果原問(wèn)題中有若干個(gè)非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，必須對(duì)各個(gè)約束引進(jìn)不同的松弛變量。

2.1線性規(guī)劃模型*

例2.2：將以下線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式

Maxf=3.6x1

-5.2x2+1.8x3s.t.2.3x1

+5.2x2-6.1x3

≤15.74.1x1

+3.3x3

≥8.9

x1

+x2+x3

=38

x1

,x2,x3≥0

2.1線性規(guī)劃模型解：首先,將目標(biāo)函數(shù)轉(zhuǎn)換成極小化：令z=-f=-3.6x1+5.2x2-1.8x3

*其次考慮約束，有2個(gè)不等式約束，引進(jìn)松弛變量x4，x5

≥0。于是，我們可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題：

Minz=-3.6x1

+5.2x2-1.8x3s.t.2.3x1+5.2x2-6.1x3+x4=15.74.1x1+3.3x3-x5=8.9

x1+x2+x3=38

x1,x2,x3,x4,x5

≥02.1線性規(guī)劃模型*3.變量無(wú)符號(hào)限制的問(wèn)題：在標(biāo)準(zhǔn)形式中，必須每一個(gè)變量均有非負(fù)約束。當(dāng)某一個(gè)變量xj沒(méi)有非負(fù)約束時(shí)，可以令

xj=xj’-xj”其中

xj’≥0，xj”≥0即用兩個(gè)非負(fù)變量之差來(lái)表示一個(gè)無(wú)符號(hào)限制的變量，當(dāng)然xj的符號(hào)取決于xj’和xj”的大小。2.1線性規(guī)劃模型*4.右端項(xiàng)有負(fù)值的問(wèn)題：在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個(gè)分量非負(fù)。當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí)，如bi<0，則把該等式約束兩端同時(shí)乘以-1，得到：-ai1x1-ai2x2-…-ainxn

=-bi

。2.1線性規(guī)劃模型*例2.3：將以下線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式Maxf=-3x1

+5x2+8x3

-7x4s.t.2x1

-3x2+5x3+6x4

≤284x1

+2x2+3x3-9x4

≥396x2+2x3+3x4≤-58

x1,x3,x4

≥02.1線性規(guī)劃模型*解：首先，將目標(biāo)函數(shù)轉(zhuǎn)換成極小化：令z=-f=3x1–5x2–8x3+7x4

；其次考慮約束，有3個(gè)不等式約束，引進(jìn)松弛變量x5,x6,x7

≥0；由于x2無(wú)非負(fù)限制，可令x2=x2’-x2”,其中 x2’≥0，x2”≥0；由于第3個(gè)約束右端項(xiàng)系數(shù)為-58，于是把該式兩端乘以-1。于是，我們可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題：2.1線性規(guī)劃模型*Minz=3x1–5x2’+5x2”–8x3+7x4s.t.2x1–3x2’+3x2”+5x3+6x4+x5=284x1+2x2’-2x2”+3x3-9x4-x6=39-6x2’+6x2”-2x3-3x4-x7

=58

x1,x2’,x2”,x3,x4,x5,x6,x7

≥0

2.1線性規(guī)劃模型*2.2線性規(guī)劃的理論線性規(guī)劃的標(biāo)準(zhǔn)形式：

MincTx(LP)s.t.Ax=b

x≥0其中,c,x

Rn

；

b

Rm；

A為

mn

矩陣*線性規(guī)劃問(wèn)題解的基本概念可行解:{x|Ax=b,

x≥0}最優(yōu)解:使目標(biāo)函數(shù)取最優(yōu)的可行解基，基變量，非基變量：若B=[P1P2…Pm]為A的一個(gè)m階可逆矩陣，則稱B為一個(gè)基或基矩陣，對(duì)應(yīng)的x1,…,xm稱為基變量，剩余的n-m個(gè)變量稱為非基變量。A=[BN]基本解:非基變量為0時(shí)，滿足約束Ax=b的解?；窘庵辽儆衝-m個(gè)分量為0，至多有m個(gè)非零分量非零分量的個(gè)數(shù)少于m時(shí)，稱為退化的基本解基本解的個(gè)數(shù)最多有C(n,m)=n!/(m!(n-m)!)基本可行解：還滿足非負(fù)約束x≥0的基本解?；究尚薪獾膫€(gè)數(shù)至多為C(n,m)=n!/(m!(n-m)!)最優(yōu)基本可行解：使目標(biāo)函數(shù)取最優(yōu)的基本可行解*線性規(guī)劃問(wèn)題解的基本概念*線性規(guī)劃問(wèn)題的性質(zhì)解的存在性：若(LP)的可行域非空，則可行域是個(gè)凸集，且(LP)一定存在有限最優(yōu)解或無(wú)界最優(yōu)解解在頂點(diǎn)的可達(dá)性：若(LP)存在有限最優(yōu)解，則最優(yōu)解可在某個(gè)頂點(diǎn)處達(dá)到頂點(diǎn)與基本可行解的關(guān)系：x0是(LP)的可行域頂點(diǎn)的充分必要條件是x0是(LP)的基本可行解→可通過(guò)求基本可行解得到有限最優(yōu)解*2.3線性規(guī)劃的單純形法一、引例：*2.3線性規(guī)劃的單純形法解：轉(zhuǎn)換為標(biāo)準(zhǔn)型：*2.3線性規(guī)劃的單純形法（1）求一個(gè)初始基本可行解*2.3線性規(guī)劃的單純形法（2）求一個(gè)改進(jìn)的基本可行解*（2）求一個(gè)改進(jìn)的基本可行解（續(xù)）*2.3線性規(guī)劃的單純形法（3）繼續(xù)上述過(guò)程直到非基變量的檢驗(yàn)數(shù)都為非正（或目標(biāo)函數(shù)不能再減少）*2.3線性規(guī)劃的單純形法定理：考慮(LP),設(shè)x

為其一個(gè)基本可行解，A=[B,N]，其中B為m階非奇異矩陣，使xT=[xBT,xNT],這里xB=B-1b≥0,xN=0，相應(yīng)地cT=[cBT,cNT]

。那么，

1）若對(duì)任意的j，非基變量檢驗(yàn)數(shù)j≤0,則

x

是最優(yōu)解.特別地，若還存在某個(gè)j，使j=0，則（LP）有無(wú)窮多個(gè)最優(yōu)解.2）若存在j，j>0,且B-1pj≤0,則(LP)無(wú)有限最優(yōu)解.二、最優(yōu)解的判斷*三、單純形法的計(jì)算步驟初始基本可行解是否最優(yōu)解或無(wú)限最優(yōu)解?結(jié)束沿邊界找新的基本可行解NY*（1）確定一個(gè)初始基本可行解:A=[B,N]，xT=[xBT,xNT],cT=[cBT,cNT],

f=cBT

xB.這里xB=B-1b≥0,xN=0.（2）計(jì)算非基變量檢驗(yàn)數(shù)=cNT-cBTB-1N,根據(jù)最優(yōu)解判別定理，判斷

x

是否為最優(yōu)解.若是，則停止，否則轉(zhuǎn)下一步.（3）求一改進(jìn)的基本可行解

1)確定換入變量:k=max{j|j∈NI},相應(yīng)的xk為換入變量. 2)確定換出變量:按θ規(guī)則計(jì)算

θ=min{i/aik|aik

>0}=r/ark

以xr為換出變量.這里=B-1b,ak=B-1pk3)用pk代替pBr,得到新的基矩陣B,并將B變換為單位矩陣:

以ark為主元素進(jìn)行迭代(即用高斯消去法)把 pk=(a1k…ark…

amk)T變?yōu)?0…1

…0)T.（4）重復(fù)（2）、（3）直到得到最優(yōu)解.三、單純形法的計(jì)算步驟（續(xù)）*四、單純形表：設(shè)x

為初始基本可行解,相應(yīng)分解A=[B,N]minfs.t.f-cBTxB-cNTxN=0

BxB+NxN=b

xB,

xN≥0minfs.t.f-0

xB+(cBTB-1N-cNT)xN=cBTB-1b

xB+B-1NxN=B-1b

xB,

xN≥0

檢驗(yàn)數(shù)*

檢驗(yàn)數(shù)fxBTxNTRHS目標(biāo)行10TcBTB-1N-cNTcBTB-1

b1行

xB0IB-1NB-1bM行1列m列n-m列1列作變換，使前m+1列對(duì)應(yīng)的m+1階矩陣變?yōu)閱挝痪仃?得：fxBTxNTRHS目標(biāo)行1-cBT-cNT01行約束行0BNbM行1列m列n-m列1列*fx1x2x3x4x5RHSf1250000x30121008x40100104x50010013引例的單純型表：換入變量：x2，因?yàn)閙ax{2,5}=5換出變量：x5,因?yàn)閙in{8/2,3/1}=3*fx1x2x3x4x5RHSf12000-5-15x301010-22x40100104x20010013fx1x2x3x4x5RHSf100-20-1-19x101010-22x4000-1122x20010013最優(yōu)解x*=(2,3,0,2,0)T,f*=-19*2.4單純形法的進(jìn)一步討論初始基本可行解的確定退化情形的處理*初始基本可行解的確定當(dāng)初始基本可行解不能通過(guò)觀察法很容易得到時(shí)，如何確定初始基本可行解？*初始基本可行解的確定帶來(lái)的問(wèn)題：人工變量的引入，改變了原問(wèn)題的約束條件，得到的是與原問(wèn)題不同的新問(wèn)題，而新問(wèn)題的最優(yōu)解不一定是原問(wèn)題的最優(yōu)解（除非新問(wèn)題的最優(yōu)解正好人工變量都為零）.（人工變量是“非法”的變量，松弛變量是“合法”的變量）解決方法：大M法兩階段法*大M法若(x,0)T是DMLP的有限最優(yōu)解，則x是LP的