§42 線性規(guī)劃的理論和方法

1、第 三 章,線 性 規(guī) 劃,3.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ù)如下表所示：,問(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

2、，于是我們可以得到不等式：3 x1 + 2 x2 ≤ 65； 對(duì)設(shè)備B，兩種產(chǎn)品生產(chǎn)所占用的機(jī)時(shí)數(shù)不能超過(guò)40，于是我們可以得到不等式：2 x1 + x2 ≤ 40；,3.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=1

3、500x1+2500x2 。綜合上述討論，在加工時(shí)間以及利潤(rùn)與產(chǎn)品產(chǎn)量成線性關(guān)系的假設(shè)下，把目標(biāo)函數(shù)和約束條件放在一起，可以建立如下的線性規(guī)劃模型：,3.1 線性規(guī)劃模型,目標(biāo)函數(shù) Max z =1500x1+2500x2 約束條件 s.t. 3x1+2x2≤ 65 2x1+x2≤ 40 3x2≤ 75 x1 ,x2 ≥0,3.1

4、 線性規(guī)劃模型,這是一個(gè)典型的利潤(rùn)最大化的生產(chǎn)計(jì)劃問(wèn)題。其中，“Max”是英文單詞“Maximize”的縮寫，含義為“最大化”；“s.t.”是“subject to”的縮寫，表示“滿足于……”。因此，上述模型的含義是：在給定條件限制下，求使目標(biāo)函數(shù)z達(dá)到最大的x1 ,x2 的取值。,3.1 線性規(guī)劃模型,一般形式 目標(biāo)函數(shù)：Max(Min)z = c1x1 + c2x2 + … + cnxn,約束條件： a11x1+a12x2+

5、…+a1nxn≤( =, ≥ )b1a21x1+a22x2+…+a2nxn≤( =, ≥ )b2 . . . am1x1+am2x2 +…+amnxn≤( =, ≥ )bm x1 ，x2 ，… ，xn ≥ 0,3.1 線性規(guī)劃模型,標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：Max z = c1x

6、1 + c2x2 + … + cnxn,約束條件：a11x1 + a12x2 + … + a1nxn = b1a21x1 + a22x2 + … + a2nxn = b2 . . .am1x1 + am2x2 + … + amnxn = bm x1 ，x2 ，… ，xn ≥ 0,3.1 線性規(guī)劃模型,可以看出，線

7、性規(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)形式:,3.1 線性規(guī)劃模型,1.極小化目標(biāo)函數(shù)的問(wèn)題： 設(shè)目標(biāo)函數(shù)為 Min f = c1x1 + c2x2 + … + cnxn 則可以令z ＝ -f ，該極小化問(wèn) 題與下面的極大化問(wèn)題有相同的最優(yōu) 解，即 Max z = -c1x1

8、 - c2x2 - … - cnxn 但必須注意，盡管以上兩個(gè)問(wèn)題的最優(yōu)解相同，但他們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào)，即 Min f ＝ - Max z,3.1 線性規(guī)劃模型,2、約束條件不是等式的問(wèn)題： 設(shè)約束條件為 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引進(jìn)一個(gè)新的變量s ，使它等于約束右邊與左邊之差 s=bi–(ai1 x1 + ai2 x2 + … + ain

9、 xn ) 顯然，s 也具有非負(fù)約束，即s≥0， 這時(shí)新的約束條件成為 ai1 x1+ai2 x2+ … +ain xn+s = bi,3.1 線性規(guī)劃模型,當(dāng)約束條件為 ai1 x1+ai2 x2+ … +ain xn ≥ bi 時(shí)，類似地令 s=(ai1 x1+ai2 x2+ … +ain xn)- bi 顯然，s 也具有非負(fù)約束，即s≥0，這時(shí)新的約束條件成為 ai1 x1+ai2

10、 x2+ … +ain xn-s = bi,3.1 線性規(guī)劃模型,為了使約束由不等式成為等式而引進(jìn)的變量s稱為“松弛變量”。如果原問(wèn)題中有若干個(gè)非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，必須對(duì)各個(gè)約束引進(jìn)不同的松弛變量。,3.1 線性規(guī)劃模型,例2.2：將以下線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式  Min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 ≤1

11、5.7 4.1 x1 + 3.3 x3 ≥8.9 x1 + x2 + x3 = 38 x1 , x2 , x3 ≥ 0,3.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)題： Max z = - 3.6 x1

12、+ 5.2 x2 - 1.8 x3s.t. 2.3x1+5.2x2-6.1x3+x4= 15.7 4.1x1+3.3x3-x5= 8.9 x1+x2+x3= 38 x1 ,x2 ,x3 ,x4 ,x5 ≥ 0,3.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”其中

13、 xj’≥0，xj”≥0即用兩個(gè)非負(fù)變量之差來(lái)表示一個(gè)無(wú)符號(hào)限制的變量，當(dāng)然xj的符號(hào)取決于xj’和xj”的大小。,3.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，得到：-ai1 x1-ai2 x2- … -ain xn = -bi 。,3.1 線性規(guī)劃模型,例2.3：將以下線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形

14、式 Min f= -3 x1 + 5 x2 + 8 x3 - 7 x4s.t. 2 x1 - 3 x2 + 5 x3 + 6 x4 ≤ 28 4 x1 + 2 x2 + 3 x3 - 9 x4 ≥ 39 6 x2 + 2 x3 + 3 x4 ≤ - 58 x1 , x3 , x4 ≥ 0,3.1 線性規(guī)劃模型,解：首先，將目標(biāo)函數(shù)轉(zhuǎn)換成極大化： 令 z = -f = 3x1–5x2–

15、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)題：,3.1 線性規(guī)劃模型,Max z = 3x1–5x2’+5x2”–8x3 +7x4 s.t. 2x1–3x2’+3x2”+5x

16、3+6x4+x5= 28 4x1+2x2’-2x2”+3x3-9x4-x6= 39 -6x2’+6x2”-2x3-3x4-x7 = 58 x1 ,x2’,x2”,x3 ,x4 ,x5 ,x6 ,x7 ≥ 0,3.1 線性規(guī)劃模型,3.1 線性規(guī)劃模型,矩陣形式：線性規(guī)劃的標(biāo)準(zhǔn)形式： Max cTx(LP) s.t. Ax = b

17、 x≥0其中, c , x ?Rn b ?Rm A m?n 矩陣,,3.1 線性規(guī)劃模型,線性規(guī)劃的規(guī)范形式： Max cTx (P) s.t. Ax ≤ b x≥0其中, c , x ?Rn b ?Rm

18、 A m?n 矩陣,,3.2 線性規(guī)劃的單純形法線性規(guī)劃的理論：,考慮(LP)的最優(yōu)性條件約束多面體 S = { x?Rn?Ax = b , x≥0 }的極點(diǎn)和極方向定理 考慮(LP)及上述多面體S，設(shè) A滿秩，x(1),x(2) , …,x(k)為所有極點(diǎn)， d(1),d(2) , …,d(l)為所有極方向。那么， 1) (LP)存在有限最優(yōu)解 ? cTd(j) ≤0, ?j . 2) 若(LP

19、)存在有限最優(yōu)解, 則最優(yōu)解可以在某個(gè)極點(diǎn)達(dá)到 .,3.2 線性規(guī)劃的單純形法線性規(guī)劃的理論,定理 考慮(LP) , 條件同上，設(shè) x* 為極點(diǎn), 存在分解 A = [ B , N ]，其中B為m階非奇異矩陣，使 xT = [ xBT, xNT ], 這里 xB = B-1b≥0, xN =0， 相應(yīng) cT = [ cBT, cNT ] 。那么， 1）若 cNT- cBT B-1N≤

20、0, 則 x* -- opt. 2）若 cj- cBT B-1pj > 0, 且 B-1pj≤0, 則 (LP) 無(wú)有界解 .,3.2 線性規(guī)劃的單純形法,表格單純形法1、原理及算法過(guò)程 Max cTx(LP) s.t. Ax = b x≥0其中, c , x ?Rn b ?Rm

21、 A m?n 矩陣，秩（A）= m,,3.2 線性規(guī)劃的單純形法單純形法原理及算法過(guò)程,算法過(guò)程 (考慮一般步, k = 0,1,2,… )設(shè) x(k) 為極點(diǎn), 對(duì)應(yīng)分解 A = [ B , N ]，使 xT = [ xBT, xNT ], 這里 xB = B-1b>0, xN =0， 相應(yīng) cT = [ cBT, cNT ] 。那么， 1）若 cNT- cBT B-1N≤0,

22、則 x(k) – opt，停； 2）否則，存在 cj- cBT B-1pj > 0, a）若 B-1pj≤0, 則 (LP) 無(wú)有界解，停； b）若存在 (B-1pj)i > 0, 取 α = min{(B-1b)i / (B-1pj)i | (B-1pj)i >0} = (B-1b)r /(B-1pj)r >0,

23、3.2 線性規(guī)劃的單純形法單純形法原理及算法過(guò)程,(續(xù)) 得到 x(k+1) = x(k) + αd 是極點(diǎn)其中, dT = [ dBT, dNT ], 這里 j dB = -B-1pj , dN = (0, ... , 1, … ,0)T有, cTx(k+1) = cTx(k) + α cTd = cTx(k) + α (cj -

24、cBTB-1pj) > cTx(k) 所以，x(k+1) 比 x(k) 好 重復(fù)這個(gè)過(guò)程，直到停機(jī)。,,3.2 線性規(guī)劃的單純形法 表格單純形法,2、單純形表：設(shè) x 為初始極點(diǎn), 相應(yīng)分解 A = [ B , N ],作變換，使前m+1列對(duì)應(yīng)的m+1階矩陣變?yōu)閱挝痪仃嚒Ｏ喈?dāng)于該表左乘 1 cBT -1 1

25、- cBT B-1 0 B 0 B-1,,,,,=,3.2 線性規(guī)劃的單純形法表格單純形法,得到： 檢驗(yàn)數(shù),,為了計(jì)算方便，我們對(duì)規(guī)范形式建立如下單純形表：（注：引入了m個(gè)松弛變量）,3.2 線性規(guī)劃的單純形法,表格單純形法考慮： bi

26、 > 0 i = 1 , … , m Max z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn ≤ b1 a21 x1 + a22 x2 + … + a2n xn ≤ b2 ……

27、…… am1 x1 + am2 x2 + … + amn xn ≤ bm x1 ，x2 ，… ，xn ≥ 0,3.2 線性規(guī)劃的單純形法,加入松弛變量： Max z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn + xn+1 = b

28、1 a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2 …… …… am1 x1 + am2 x2 + … + amn xn+ xn+m = bm x1 ，x2 ，… ，xn ，xn+1 ，… ，xn+m ≥ 0,顯然，xj = 0 j = 1, … , n ; xn+i =

29、 bi i = 1 , … , m 是基本可行解 對(duì)應(yīng)的基是單位矩陣。以下是初始單純形表： m m其中：f = -∑ cn+i bi ?j = cj -∑ cn+i aij 為檢驗(yàn)數(shù) cn+i = 0 i= 1,…,m

30、 i = 1 i = 1 an+i,i = 1 , an+i,j = 0 ( j≠i ) i , j = 1, … , m,建立實(shí)用單純形表,利用求解線性規(guī)劃問(wèn)題基本可行解（極點(diǎn)）的方法來(lái)求解較大規(guī)模的問(wèn)題是不可行的。單純形法的基本思路是有選擇地取基本可行解，即是從可行域的一

31、個(gè)極點(diǎn)出發(fā)，沿著可行域的邊界移到另一個(gè)相鄰的極點(diǎn)，要求新極點(diǎn)的目標(biāo)函數(shù)值不比原目標(biāo)函數(shù)值差。,3.2 線性規(guī)劃的單純形法,單 純 形 法,單純形法的基本過(guò)程,例：用單純形法的基本思路解前例的線性規(guī)劃問(wèn)題 Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2

32、+ x5 = 75 x1 , x2 , x3 , x4 , x5 ≥ 0,3.2 線性規(guī)劃的單純形法,3.2 線性規(guī)劃的單純形法,最優(yōu)解 x1 = 5 x2 = 25 x4 = 5（松弛標(biāo)量，表示B設(shè)備有5個(gè)機(jī)時(shí)的剩余） 最優(yōu)值 z* = 70000,注意：?jiǎn)渭冃畏ㄖ校?1、每一步運(yùn)算只能用矩陣初等行變換； 2、表中第3列的數(shù)總應(yīng)保持非負(fù)（≥ 0）；

33、 3、當(dāng)所有檢驗(yàn)數(shù)均非正（≤ 0）時(shí)，得到最優(yōu)單純形表。,3.2 線性規(guī)劃的單純形法,一般情況的處理及注意事項(xiàng)的強(qiáng)調(diào)：主要是討論初始基本可行解不明顯時(shí)，常用的方法。要弄清它的原理，并通過(guò)例題掌握這些方法，同時(shí)進(jìn)一步熟悉用單純形法解題。 考慮一般問(wèn)題： bi > 0 i = 1 , … , m,3.2 線性規(guī)劃的單純形法,Max z = c1x1 + c2x2 + … + cnxn s.t.

34、 a11x1+a12x2 +…+a1nxn = b1 a21x1+a22x2 +…+a2nxn = b2 . . . am1x1+am2x2+…+amnxn = bm

35、 x1 ，x2 ，… ，xn ≥ 0,3.2 線性規(guī)劃的單純形法,大M法： 引入人工變量 xn+i ≥ 0 （i = 1 , … , m）及充分大正數(shù) M 。得到：Max z = c1x1 +c2x2 +…+cnxn -Mxn+1 -…-Mxn+m s.t. a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + …

36、 + a2n xn + xn+2 = b2 . . . am1 x1 + am2 x2 + … + amn xn + xn+m = bm x1 ，x2 ，… ，xn ，xn+1 ，… ，xn+m ≥0,3.2 線性規(guī)劃的單純形法,顯然，xj = 0 j=1, … , n ; xn+i = bi i =1 , … , m 是

37、基本可行解。對(duì)應(yīng)的基是單位矩陣。 結(jié)論：若得到的最優(yōu)解滿足 xn+i = 0 i = 1 , … , m 則是原問(wèn)題的最優(yōu)解；否則，原問(wèn)題無(wú)可行解。,單 純 形 法,兩階段法： 引入人工變量 xn+i ≥ 0，i = 1 ,…, m； 構(gòu)造: Max z = - xn+1 - xn+2 - … - xn+m s.t. a11x1+a12x2+ …

38、+a1nxn+xn+1 = b1 a21x1+a22x2+ … +a2nxn+xn+2 = b2 . . . am1x1+am2x2+ … +amnxn+xn+m = bm x1,x2 ... xn ,xn+1,…,xn+m ≥

39、0,單 純 形 法,第一階段求解上述問(wèn)題： 顯然，xj = 0 j=1, … , n ; xn+i = bi i =1 , … , m 是基本可行解,它對(duì)應(yīng)的基 是單位矩陣。,結(jié)論：若得到的最優(yōu)解滿足 xn+i=0 i=1 , … , m 則是原問(wèn)題的基本可行解;否則，原問(wèn)題無(wú)可行解。 得到原問(wèn)題的基本可行解后，第二階段求解原問(wèn)題。,單 純 形 法,例（LP）

40、Max z = 5x1 + 2x2 + 3x3 - x4 s.t. x1 + 2x2 + 3x3 = 15 2x1 + x2 + 5x3 = 20 x1 + 2x2 + 4x3 + x4 =

41、26 x1 , x2 , x3 , x4 ≥ 0,3.2 線性規(guī)劃的單純形法,Max z = 5x1+2x2+3x3-x4-Mx5-Mx6 s.t. x1+2x2+3x3+x5 =15 2x1+x2+5x3+x6 =20

42、 x1+2x2+4x3+x4 =26 x1 ,x2 ,x3 ,x4 ,x5 ,x6 ≥ 0,大M法問(wèn)題(LP-M）,3.2 線性規(guī)劃的單純形法,大M法 （LP - M）,得到最優(yōu)解：(25/3，10/3，0，11)T 最優(yōu)目標(biāo)值：11

43、2/3,3.2 線性規(guī)劃的單純形法,第一階段問(wèn)題（LP - 1） Max z = - x5 - x6 s.t. x1 + 2x2 + 3x3 + x5 = 15 2x1 + x2 + 5x3 + x6 = 20 x1 + 2x

44、2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0,兩階段法 ：,3.2 線性規(guī)劃的單純形法,第一階段 (LP - 1）,得到原問(wèn)題的基本可行解: (0，15/7，25/7，52/7)T,3.2 線性規(guī)劃的單純形法,第二階段 把基本可行解填入表中,得到原問(wèn)題的最優(yōu)

45、解:(25/3，10/3，0，11)T 最優(yōu)目標(biāo)值：112/3,3.2 線性規(guī)劃的單純形法,3.3 線性規(guī)劃的對(duì)偶,對(duì)偶原理 對(duì)偶問(wèn)題定義—— 線性規(guī)劃問(wèn)題寫出其對(duì)偶問(wèn)題，要掌握在對(duì)稱形式和非對(duì)稱情況下由原問(wèn)題寫出對(duì)偶問(wèn)題的方法。 對(duì)偶定理—— 只需了解原問(wèn)題與對(duì)偶問(wèn)題解的關(guān)系，證明從略。,1.對(duì)偶問(wèn)題： 若3.1中的例題的設(shè)備都用于外協(xié)加工，工廠收取加工費(fèi)。試問(wèn)：設(shè)備 A、B、C 每工時(shí)各如何收費(fèi)

46、才最有競(jìng)爭(zhēng)力？ 設(shè) y1 ，y2 ，y3 分別為每工時(shí)設(shè)備 A、B、C 的收取費(fèi)用。,3.3 線性規(guī)劃的對(duì)偶,線性規(guī)劃原問(wèn)題,例:某工廠擁有A、B、C 三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三種設(shè)備可利用的時(shí)數(shù)如下表所示。求獲最大利潤(rùn)的方案。,,Max z = 1500x1

47、 + 2500x2 s.t. 3x1 + 2x2 ≤ 65 2x1 + x2 ≤ 40 原問(wèn)題 3x2 ≤ 75

48、 x1 ,x2 ≥ 0 Min f = 65y1+ 40y2 + 75y3 s.t. 3y1+2y2 ≥1500 （不少于甲產(chǎn)品的利潤(rùn)） 2y1+y2+3y3 ≥2500 對(duì)偶問(wèn)題 （不少于乙產(chǎn)品的利潤(rùn)） y1, y2 , y3 ≥ 0,3.3 線性規(guī)劃的對(duì)偶,2、對(duì)偶定義 對(duì)稱形式：

49、 互為對(duì)偶 (LP) Max z = cT x (DP) Min f = bT y s.t. Ax ≤ b s.t. AT y ≥ c x ≥ 0 y ≥ 0 “Max -- ≤ ”

50、 “Min-- ≥”,,,,3.3 線性規(guī)劃的對(duì)偶,一對(duì)對(duì)稱形式的對(duì)偶規(guī)劃之間具有下面的對(duì)應(yīng)關(guān)系。 (1)若一個(gè)模型為目標(biāo)求“極大”，約束為“小于等于”的不等式，則它的對(duì)偶模型為目標(biāo)求“極小”，約束是“大于等于”的不等式。即“max，≤”和“min，≥”相對(duì)應(yīng)。,3.3 線性規(guī)劃的對(duì)偶,(2)從約束系數(shù)矩陣看：一個(gè)模型中為Ａ，則另一個(gè)模型中為AT。一個(gè)模型是m個(gè)約束，n個(gè)變量，則它的對(duì)偶模型為n個(gè)約束，m個(gè)變量。 (

51、3)從數(shù)據(jù)b、C的位置看：在兩個(gè)規(guī)劃模型中，b和C的位置對(duì)換。 (4)兩個(gè)規(guī)劃模型中的變量皆非負(fù)。,3.3 線性規(guī)劃的對(duì)偶,非對(duì)稱形式的對(duì)偶規(guī)劃 一般稱不具有對(duì)稱形式的一對(duì)線性規(guī)劃為非對(duì)稱形式的對(duì)偶規(guī)劃。 對(duì)于非對(duì)稱形式的規(guī)劃，可以按照下面的對(duì)應(yīng)關(guān)系直接給出其對(duì)偶規(guī)劃。 （1）將模型統(tǒng)一為“max，≤”或“min，≥” 的形式，對(duì)于其中的等式約束按下面（2）、（3）中的方法處理；,3.3 線性

52、規(guī)劃的對(duì)偶,（2）若原規(guī)劃的某個(gè)約束條件為等式約束，則在對(duì)偶規(guī)劃中與此約束對(duì)應(yīng)的那個(gè)變量取值沒(méi)有非負(fù)限制； （3）若原規(guī)劃的某個(gè)變量的值沒(méi)有非負(fù)限制，則在對(duì)偶問(wèn)題中與此變量對(duì)應(yīng)的那個(gè)約束為等式。,3.3 線性規(guī)劃的對(duì)偶,3.3 線性規(guī)劃的對(duì)偶,例 寫出下面線性規(guī)劃的對(duì)偶規(guī)劃模型,解 先將約束條件變形為“≤”形式,3.3 線性規(guī)劃的對(duì)偶,再根據(jù)非對(duì)稱形式的對(duì)應(yīng)關(guān)系，直接寫出對(duì)偶規(guī)劃,3.3 線性規(guī)劃的對(duì)偶,對(duì)偶定理(原問(wèn)題與對(duì)偶問(wèn)

53、題解的關(guān)系）考慮（LP）和（DP）,定理3-1 (弱對(duì)偶定理） 若 x, y 分別為（LP) 和（DP）的可行解，那么cTx ≤ bTy。,推論 若（LP）可行，那么（LP）無(wú)有限最優(yōu)解的充分必要條件是（LD）無(wú)可行解。,3.3 線性規(guī)劃的對(duì)偶,定理3-2 (最優(yōu)性準(zhǔn)則定理) 若x,y分別(LP),(DP)的可行解,且cTx=bTy ，那么x,y分別為(LP)和(DP)的最優(yōu)解。,定理3-3 (主對(duì)偶定

54、理) 若(LP)和(DP)均可行 那么(LP)和(DP)均有最優(yōu)解,且最優(yōu)值相等。,以上定理、推論對(duì)任意形式的相應(yīng)性規(guī)劃的對(duì)偶均有效,3.3 線性規(guī)劃的對(duì)偶,影子價(jià)格 —— 是一個(gè)向量，它的分量表示最優(yōu)目標(biāo)值隨相應(yīng)資源數(shù)量變化的變化率。 若x*,y* 分別為（LP）和（DP）的最優(yōu)解， 那么， cT x* = bT y* 。 根據(jù) f = bTy*=b1y1*+b2y2*+?+bmym* 可知 ?f /

55、 ?bi = yi* yi* 表示 bi 變化1個(gè)單位對(duì)目標(biāo) f 產(chǎn)生的影響，稱 yi* 為 bi的影子價(jià)格。 注意：若 B 是最優(yōu)基， y* = (BT)-1 cB 為影子價(jià)格向量。,3.3 線性規(guī)劃的對(duì)偶,影子價(jià)格反映了不同的局部或個(gè)體的增量可以獲得不同的整體經(jīng)濟(jì)效益。如果為了擴(kuò)大生產(chǎn)能力，考慮增加設(shè)備，就應(yīng)該從影子價(jià)格高的設(shè)備入手。這樣可以用較少的局部努力，獲得較大的整體效益。,3.3 線性規(guī)劃的對(duì)偶,需要指出，

56、影子價(jià)格不是固定不變的，當(dāng)約束條件、產(chǎn)品利潤(rùn)等發(fā)生變化時(shí)，有可能使影子價(jià)格發(fā)生變化。另外，影子價(jià)格的經(jīng)濟(jì)含義（2），是指資源在一定范圍內(nèi)增加時(shí)的情況，當(dāng)某種資源的增加超過(guò)了這個(gè)“一定的范圍”時(shí)，總利潤(rùn)的增加量則不是按照影子價(jià)格給出的數(shù)值線性地增加。這個(gè)問(wèn)題還將在靈敏度分析一節(jié)中討論。,3.3 線性規(guī)劃的對(duì)偶,由最優(yōu)單純形表求對(duì)偶問(wèn)題最優(yōu)解 標(biāo)準(zhǔn)形式： Max z = 50 x1 + 100 x2 s.t.

57、 x1 + x2 + x3 = 300 2x1 + x2 + x4 = 400 x2 + x5 = 250 x1 ,x2 ,x3 ,x4 ,x5 ≥ 0,3.3 線性規(guī)劃的對(duì)偶,,,,,,,-cBTB-1,I,B=(p1, p4,p2 ),oT,B-1,最優(yōu)解 x1 = 50 x2 = 250 x4 = 50影子價(jià)格 y1 = 50 y2 = 0

58、 y3 = 50 , B-1對(duì)應(yīng)的檢驗(yàn)數(shù) ?T = cBTB-1 。,3.3 線性規(guī)劃的對(duì)偶,對(duì)偶單純形法的基本思想 對(duì)偶單純形法的基本思想是：從原規(guī)劃的一個(gè)基本解出發(fā)，此基本解不一定可行，但它對(duì)應(yīng)著一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非正），所以也可以說(shuō)是從一個(gè)對(duì)偶可行解出發(fā)；然后檢驗(yàn)原規(guī)劃的基本解是否可行，即是否有負(fù)的分量，如果有小于零的分量，則進(jìn)行迭代，求另一個(gè)基本解，此基本解對(duì)應(yīng)著另一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非正）。,對(duì)偶單純

59、形法,如果得到的基本解的分量皆非負(fù)則該基本解為最優(yōu)解。也就是說(shuō)，對(duì)偶單純形法在迭代過(guò)程中始終保持對(duì)偶解的可行性（即檢驗(yàn)數(shù)非正），使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚?，?dāng)同時(shí)得到對(duì)偶規(guī)劃與原規(guī)劃的可行解時(shí)，便得到原 規(guī)劃的最優(yōu)解。,對(duì)偶單純形法,對(duì)偶單純形法在什么情況下使用 ： 應(yīng)用前提：有一個(gè)基，其對(duì)應(yīng)的基滿足: ① 單純形表的檢驗(yàn)數(shù)行全部非正（對(duì)偶可行）； ② 變量取值可有負(fù)數(shù)（非可行解）。

60、注：通過(guò)矩陣行變換運(yùn)算，使所有相應(yīng)變量取值均為非負(fù)數(shù)即得到最優(yōu)單純形表。,對(duì)偶單純形法,1.建立初始對(duì)偶單純形表,對(duì)應(yīng)一個(gè)基本解,所有檢驗(yàn)數(shù)均非正,轉(zhuǎn)2； 2.若b’≥0,則得到最優(yōu)解,停止;否則,若有bk<0則選k行的基變量為出基變量,轉(zhuǎn)3 3.若所有akj’≥0( j = 1,2,…,n )，則原問(wèn)題無(wú)可行解,停止;否則,若有akj’<0 則選 ?=min{?j’ / akj’┃ak

61、j’<0}=?r’/akr’那么 xr為進(jìn)基變量,轉(zhuǎn)4； 4.以akr’為轉(zhuǎn)軸元,作矩陣行變換使其變?yōu)?,該列其他元變?yōu)?,轉(zhuǎn)2。,對(duì)偶單純形法求解線性規(guī)劃問(wèn)題過(guò)程：,對(duì)偶單純形法,例：求解線性規(guī)劃問(wèn)題：,對(duì)偶單純形法,表格對(duì)偶單純形法,單純形法和對(duì)偶單純形法步驟,<,單純形表的理解（例題）,上表中6個(gè)常數(shù) a1 , a2 , a3 , b , ?1 , ?2 取值在什么范圍可使1、現(xiàn)可行

62、解最優(yōu)，且唯一？何時(shí)不唯一？2、現(xiàn)基本解不可行；3、問(wèn)題無(wú)可行解；4、無(wú)有限最優(yōu)解；5、現(xiàn)基本解可行，由 x1 取代 x6 目標(biāo)函數(shù)可改善。,進(jìn)一步理解最優(yōu)單純性表中各元素的含義考慮問(wèn)題 Max z = c1 x1 + c2 x2 + … + cn xn s.t. a11x1 + a12x2 + … + a1nxn = b1 a21x1 + a22x2 + … + a2nxn = b2

63、 . . . am1x1 + am2x2 + … + amnxn = bm x1 ，x2 ，… ，xn ≥ 0,3.4 靈敏度分析,3.4 靈敏度分析,無(wú)防設(shè)，xj = 0 j = m+1, … , n ; xi = bi’ i = 1 , … , m 是基本可行解, 對(duì)應(yīng)的目標(biāo)函數(shù)典式

64、為：z = -f + ?m+1xm+1+…+ ?nxn以下是初始單純形表： m m其中：f = -∑ ci bi’ ?j = cj -∑ ci aij’ 為檢驗(yàn)數(shù)。 向量 b’ = B-1 b i = 1

65、 i = 1 A= [ p1, p2, …, pn ], pj’ = B-1 pj, pj’ = ( a1j’ , a2j’ , … , amj’ )T ， j = m+1, … , n,內(nèi)容： ci , bj發(fā)生變化 增加一約束或變量,對(duì)于表格單純形法，通過(guò)計(jì)算得到最優(yōu)單純形表。 應(yīng)能夠找到最優(yōu)基 B

66、 的逆矩陣 B-1 ， B-1b 以及 B-1N，檢驗(yàn)數(shù) ?j 等。,3.4 靈敏度分析,價(jià)值系數(shù)c發(fā)生變化：

67、 m 考慮檢驗(yàn)數(shù) ?j = cj -∑ cri arij j =1,2,……,n i = 1,1. 若ck是非基變量的系數(shù)： 設(shè)ck變化為 ck + ?ck ?k’= ck + ?ck -∑cri arik = ?k+ ?ck 只要 ?k’≤ 0 ,即 ?ck ≤ - ?k ，則

68、 最優(yōu)解不變；否則，將最優(yōu)單純形表 中的檢驗(yàn)數(shù) ?k 用 ?k’取代，繼續(xù)單 純形法的表格計(jì)算。,3.4 靈敏度分析,例: Max z = -2x1 - 3x2 - 4x3 S.t. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 ≥0,3.4 靈敏度分析,例：最優(yōu)單純形表

69、,從表中看到σ3= c3+Δc3-(c2×a13+c1×a23 ) 可得到Δc3 ≤ 9/5 時(shí)，原最優(yōu)解不變。,3.4 靈敏度分析,2、若 cs 是基變量的系數(shù)： 設(shè) cs 變化為 cs + ?cs ，那么 ?j’= cj -∑cri arij - ( cs + ?cs ) asj = ?j - ?cs asj ，