【正文】 . . . am1x1+am2x2+ … +amnxn+xn+m = bm x1,x2 ... xn ,xn+1,… ,xn+m ≥ 0 單 純 形 法 第一階段求解上述問題： 顯然， xj = 0 j=1, … , n 。 xn+i = bi i =1 , … , m 是基本可行解 ,它對(duì)應(yīng)的基 是單位矩陣。 結(jié)論： 若得到的最優(yōu)解滿足 xn+i=0 i=1 , … , m 則是原問題的基本可行解 。否則，原問題無可行解。 得到原問題的基本可行解后，第二階段求解原問題。 單 純 形 法 例（ LP） Max z = 5x1 + 2x2 + 3x3 x4 . x1 + 2x2 + 3x3 = 15 2x1 + x2 + 5x3 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 ≥ 0 線性規(guī)劃的單純形法 Max z = 5x1+2x2+3x3x4Mx5Mx6 . x1+2x2+3x3+x5 =15 2x1+x2+5x3+x6 =20 x1+2x2+4x3+x4 =26 x1 ,x2 ,x3 ,x4 ,x5 ,x6 ≥ 0 線性規(guī)劃的單純形法 5 2 3 1 M M CB XB x1 x2 x3 x4 x5 x6 θ i M x5 15 1 2 3 0 1 0 5 M x6 20 2 1 (5) 0 0 1 4 1 x4 26 1 2 4 1 0 0 6 .5 z 35 M +2 6 3 M +6 3 M +4 8 M +7 0 0 0 M x5 3 1 /5 (7/5 ) 0 0 1 3 /5 1 5 /7 3 x3 4 2 /5 1 /5 1 0 0 1 /5 20 1 x4 10 3 /5 6 /5 0 1 0 4 /5 25/ 3 z 3 M 2 M /5+1 6 /5 7 /5 M +1 3 /5 0 0 0 8 /5 M 7 /5 2 x2 1 5 /7 1 /7 1 0 0 5 /7 3 /7 3 x3 2 5 /7 (3/7 ) 0 1 0 1 /7 2 /7 2 5 /3 1 x4 5 2 /7 3 /7 0 0 1 6 /7 2 /7 z 5 3 /7 2 5 /7 0 0 0 M 1 3 /7 M 2 /7 2 x2 1 0 /3 0 1 1 /3 0 2 /3 1 /3 5 x1 2 5 /3 1 0 7 /3 0 1 /3 2 /3 1 x4 11 0 0 1 1 1 0 z 1 1 2 /3 0 0 2 5 /3 0 M 2 /3 M +8 /3 ?大 M法 （ LP M） ? 得到 最優(yōu)解 ： (25/3， 10/3， 0， 11)T ? 最優(yōu)目標(biāo)值 ： 112/3 線性規(guī)劃的單純形法 第一階段問題（ LP 1） Max z = x5 x6 . x1 + 2x2 + 3x3 + x5 = 15 2x1 + x2 + 5x3 + x6 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0 線性規(guī)劃的單純形法 0 0 0 0 1 1 CB XB x1 x2 x3 x4 x5 x6 θ i 1 x5 15 1 2 3 0 1 0 5 1 x6 20 2 1 (5) 0 0 1 4 0 x4 26 1 2 4 1 0 0 6 .5 z 35 3 3 8 0 0 0 1 x5 3 1 /5 (7/5 ) 0 0 1 3 /5 1 5 /7 0 x3 4 2 /5 1 /5 1 0 0 1 /5 20 0 x4 10 3 /5 6 /5 0 1 0 4 /5 2 5 /3 z 3 1 /5 7/ 5 0 0 0 8 /5 0 x2 1 5 /7 1 /7 1 0 0 5 /7 3 /7 0 x3 2 5 /7 3 /7 0 1 0 1 /7 2 /7 2 5 /3 0 x4 5 2 /7 3 /7 0 0 1 6 /7 2 /7 z 0 0 0 0 0 1 1 ?第一階段 (LP 1） ? 得到原問題的基本可行解 : (0， 15/7， 25/7， 52/7)T 線性規(guī)劃的單純形法 5 2 3 1 C B X B x 1 x 2 x 3 x 4 θi 2 x 2 1 5 /7 1 /7 1 0 0 3 x 3 2 5 /7 (3 /7 ) 0 1 0 2 5 /3 1 x 4 5 2 /7 3 /7 0 0 1 z 5 3 /7 2 5 /7 0 0 0 2 x 2 1 0 /3 0 1 1 /3 0 5 x 1 2 5 /3 1 0 7 /3 0 1 x 4 11 0 0 1 1 z 1 1 2 /3 0 0 2 5 /3 0 ?第二階段 把基本可行解填入表中 ? 得到原問題的最優(yōu)解 :(25/3， 10/3， 0， 11)T ?最優(yōu)目標(biāo)值： 112/3 線性規(guī)劃的單純形法 線性規(guī)劃的對(duì)偶 對(duì)偶原理 對(duì)偶問題定義 —— 線性規(guī)劃問題寫出其對(duì)偶問題，要掌握在對(duì)稱形式和非對(duì)稱情況下由原問題寫出對(duì)偶問題的方法。 對(duì)偶定理 —— 只需了解原問題與對(duì)偶問題解的關(guān)系，證明從略。 ： 若 的設(shè)備都用于外協(xié)加工，工廠收取加工費(fèi)。試問：設(shè)備 A、 B、C 每工時(shí)各如何收費(fèi)才最有競(jìng)爭(zhēng)力？ 設(shè) y1 ， y2 ， y3 分別為每工時(shí)設(shè)備 A、B、 C 的收取費(fèi)用。 線性規(guī)劃的對(duì)偶 線性規(guī)劃原問題 例 :某工廠擁有 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)的方案 。 產(chǎn)品甲 產(chǎn)品乙 設(shè)備能力（ h） 設(shè)備 A 3 2 65 設(shè)備 B 2 1 40 設(shè)備 C 0 3 75 利潤(rùn)（元 /件） 1500 2500 Max z = 1500x1 + 2500x2 . 3x1 + 2x2 ≤ 65 2x1 + x2 ≤ 40 原問題 3x2 ≤ 75 x1 ,x2 ≥ 0 Min f = 65y1+ 40y2 + 75y3 . 3y1+2y2 ≥1500 （不少于甲產(chǎn)品的利潤(rùn)） 2y1+y2+3y3 ≥2500 對(duì)偶問題 （不少于乙產(chǎn)品的利潤(rùn)） y1, y2 , y3 ≥ 0 線性規(guī)劃的對(duì)偶 對(duì)偶定義 對(duì)稱形式 ： 互為對(duì)偶 (LP) Max z = cT x (DP) Min f = bT y . Ax ≤ b . AT y ≥ c x ≥ 0 y ≥ 0 “Max ≤ ” “Min ≥” 線性規(guī)劃的對(duì)偶 一對(duì) 對(duì)稱形式 的對(duì)偶規(guī)劃之間具有下面的對(duì)應(yīng)關(guān)系 。 (1)若一個(gè)模型為目標(biāo)求 “ 極大 ” ，約束為 “ 小于等于 ” 的不等式 ， 則它的對(duì)偶模型為目標(biāo)求 “ 極小 ” ， 約束是“ 大于等于 ” 的不等式 。 即 “ max， ≤ ”和 “ min， ≥ ” 相對(duì)應(yīng) 。 線性規(guī)劃的對(duì)偶 (2)從約束系數(shù)矩陣看：一個(gè)模型中為 Ａ ， 則另一個(gè)模型中為 AT。 一個(gè)模型是 m個(gè)約束 ， n個(gè)變量 ， 則它的對(duì)偶模型為 n個(gè)約束 ， m個(gè)變量 。 (3)從數(shù)據(jù) b、 C的位置看：在兩個(gè)規(guī)劃模型中 ， b和 C的位置對(duì)換 。 (4)兩個(gè)規(guī)劃模型中的變量皆非負(fù) 。 線性規(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） 中的方法處理； 線性規(guī)劃的對(duì)偶 （ 2） 若原規(guī)劃的某個(gè)約束條件為等式約束 ， 則在對(duì)偶規(guī)劃中與此約束對(duì)應(yīng)的那個(gè)變量取值沒有非負(fù)限制； （ 3） 若原規(guī)劃的某個(gè)變量的值沒有非負(fù)限制 ， 則在對(duì)偶問題中與此變量對(duì)應(yīng)的那個(gè)約束為等式 。 線性規(guī)劃的對(duì)偶 線性規(guī)劃的對(duì)偶 例 寫出下面線性規(guī)劃的對(duì)偶規(guī)劃模型 解 先將約束條件變形為 “ ≤ ” 形式 線性規(guī)劃的對(duì)偶 再根據(jù)非對(duì)稱形式的對(duì)應(yīng)關(guān)系 ， 直接寫出對(duì)偶規(guī)劃 線性規(guī)劃的對(duì)偶 ?對(duì)偶定理 (原問題與對(duì)偶問題解的關(guān)系） 考慮（ LP）和（ DP） 定理 31 (弱對(duì)偶定理） 若 x, y 分別為（ LP) 和（ DP）的可行解，那么 cTx ≤ bTy。 推論 若（ LP）可行，那么（ LP） 無有限最優(yōu)解的充分必要條件是（ LD）