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

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

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

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

*

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

+2x2

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

+x2

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

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

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

。綜合上述討論，在加工時間以及利潤與產(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ī)劃模型*

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

的取值。它是一個目標(biāo)函數(shù)、約束函數(shù)都是線性函數(shù)的最優(yōu)化問題，即線性規(guī)劃問題。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)形式有如下四個特點：目標(biāo)最小化、約束為等式、決策變量均非負、右端項非負。對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式:2.1線性規(guī)劃模型*1.極大化目標(biāo)函數(shù)的問題：設(shè)目標(biāo)函數(shù)為

Maxf=c1x1

+c2x2

+…+cnxn

則可以令z

＝-f

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

Maxz=-c1x1

-c2x2-…-cnxn

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

Minz

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

ai1x1+ai2x2+…+ainxn

≤bi

可以引進一個新的變量s

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

s=bi–(ai1x1

+ai2x2

+…+ainxn

)

顯然，s

也具有非負約束，即s≥0，這時新的約束條件成為

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

當(dāng)約束條件為

ai1x1+ai2x2+

…

+ainxn

≥bi

時，類似地令

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

顯然，s

也具有非負約束，即s≥0，這時新的約束條件成為

ai1x1+ai2x2+…+ainxn-s=bi

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

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

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

例2.2：將以下線性規(guī)劃問題轉(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個不等式約束，引進松弛變量x4，x5

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

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.變量無符號限制的問題：在標(biāo)準(zhǔn)形式中，必須每一個變量均有非負約束。當(dāng)某一個變量xj沒有非負約束時，可以令

xj=xj’-xj”其中

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

=-bi

。2.1線性規(guī)劃模型*例2.3：將以下線性規(guī)劃問題轉(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個不等式約束，引進松弛變量x5,x6,x7

≥0；由于x2無非負限制，可令x2=x2’-x2”,其中 x2’≥0，x2”≥0；由于第3個約束右端項系數(shù)為-58，于是把該式兩端乘以-1。于是，我們可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題：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ī)劃問題解的基本概念可行解:{x|Ax=b,

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

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

。那么，

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

x

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

f=cBT

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

x

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

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

θ=min{i/aik|aik

>0}=r/ark

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

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

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

…0)T.（4）重復(fù)（2）、（3）直到得到最優(yōu)解.三、單純形法的計算步驟（續(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

檢驗數(shù)*

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

b1行

xB0IB-1NB-1bM行1列m列n-m列1列作變換，使前m+1列對應(yīng)的m+1階矩陣變?yōu)閱挝痪仃?得：fxBTxNTRHS目標(biāo)行1-cBT-cNT01行約束行0BNbM行1列m列n-m列1列*fx1x2x3x4x5RHSf1250000x30121008x40100104x50010013引例的單純型表：換入變量：x2，因為max{2,5}=5換出變量：x5,因為min{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單純形法的進一步討論初始基本可行解的確定退化情形的處理*初始基本可行解的確定當(dāng)初始基本可行解不能通過觀察法很容易得到時，如何確定初始基本可行解？*初始基本可行解的確定帶來的問題：人工變量的引入，改變了原問題的約束條件，得到的是與原問題不同的新問題，而新問題的最優(yōu)解不一定是原問題的最優(yōu)解（除非新問題的最優(yōu)解正好人工變量都為零）.（人工變量是“非法”的變量，松弛變量是“合法”的變量）解決方法：大M法兩階段法*大M法若(x,0)T是DMLP的有限最優(yōu)解，則x是LP的