【正文】 1 0 x4 16 0 0 2/3 1 0 8/3 0 6 X1 14 1 0 0 0 0 1 0 4 x2 24 0 1 1/3 0 0 2/3 2 σj=cjzj 0 0 4/3 0 0 M10/3 M 練 習(xí) 用大 M法求解下列問(wèn)題： 、兩階段法 ? 為了克服大 M法的困難，對(duì)添加人工變量后的線性規(guī)劃問(wèn)題分兩個(gè)階段來(lái)計(jì)算，稱為兩階段法。 ? 解題思路： ? 兩階段法的第一階段是先求解一個(gè)目標(biāo)函數(shù)中只包含人工變量的線性規(guī)劃問(wèn)題，即令目標(biāo)函數(shù)中其它變量的系數(shù)取零，人工變量的系數(shù)取某個(gè)正的常數(shù)(一般取 1)，在保持原問(wèn)題約束條件不變的情況下求這個(gè)目標(biāo)函數(shù)極小化時(shí)的解。 ? 顯然在第一階段中，當(dāng)人工變量取值為 0時(shí)，目標(biāo)函數(shù)值也為 0。這時(shí)候的最優(yōu)解就是 原線性規(guī)劃問(wèn)題的一個(gè)基可行解 。如果第一階段求解結(jié)果最優(yōu)解的目標(biāo)函數(shù)值不為 0，也即最優(yōu)解的基變量中含有非零的人工變量，表明原線性規(guī)劃問(wèn)題無(wú)可行解。 作輔助問(wèn)題 minW= yi i=1 m ? Xj ， yi ? 0 j=1 n ? aij xj + yi =bi ( i=1,2, …,m ) (二 )、兩階段法： 原問(wèn)題 maxZ= Cj xj j=1 n ? xj ? 0 j=1 n ? aij xj =bi ( i=1,2, …,m ) maxZ= X1 +2X2 X1 +X2 ? 2 X1 +X2 ? 1 X2 ? 3 X1 X2 ?0 例 2： 解題過(guò)程： 第 1階段：解輔助問(wèn)題 當(dāng)進(jìn)行到最優(yōu)表時(shí)，①、若 W=0, 則得到原問(wèn)題的一個(gè)基本可行解，轉(zhuǎn)入第 2階段。 ②、若 W0, 則判定原問(wèn)題無(wú)可行解。 第 2階段 ：去除人工變量， 求解原問(wèn)題。第一階段的最優(yōu)解為原問(wèn)題的初始基可行解。 第 (1)階段： minW=X6 +X7 X1 +X2 X3 +X6 =2 X1 +X2 X4 +X7 =1 X2 +X5 =3 X1 … X7 ?0 列初始單純形表 Cj 0 0 0 0 0 1 1 θ CB XB b x1 x2 x3 x4 x5 x6 x7 1 x6 2 1 1 1 0 0 1 0 1 x7 1 1 1 0 1 0 0 1 0 x5 3 0 1 0 0 1 0 0 σj=cjzj 第二階段：去除人工變量，列新單純形表求解。 0 0 0 0 0 1 1 X1 X2 X3 X4 X5 X6 X7 CB XB 3 0 2 1 1 0 0 0 1 X6 2 1 1 1 0 0 1 0 1 X7 1 1 (1) 0 1 0 0 1 0 X5 3 0 1 0 0 1 0 0 CB XB 1 2 0 1 1 0 0 2 X6 1 (2) 0 1 1 0 1 1 X2 1 1 1 0 1 0 0 1 X5 2 1 0 0 1 1 0 1 XB 0 0 0 0 0 0 1 1 X1 1/2 1 0 1/2 1/2 0 1/2 1/2 X2 3/2 0 1 1/2 1/2 0 1/2 1/2 X5 3/2 0 0 1/2 1/2 1 1/2 1/2 1 2 0 0 0 X1 X2 X3 X4 X5 CB XB 3/2 0 0 1/2 3/2 0 1 X1 1/2 1 0 1/2 (1/2) 0 2 X2 3/2 0 1 1/2 1/2 0 0 X5 3/2 0 0 1/2 1/2 1 XB 4 3 0 2 0 0 X4 1 2 0 1 1 0 X2 2 1 1 1 0 0 X5 1 1 0 (1) 0 1 XB 6 1 0 0 0 2 X4 2 1 0 0 1 1 X2 3 0 1 0 0 1 X3 1 1 0 1 0 1 0123241123m i n31321321321???????????????ixxxxxxxxxxxxz練習(xí)： 用兩階段法求解下列線性規(guī)劃問(wèn)題： ?解 ： 第一階段 求解輔助問(wèn)題： 為人工變量1311,02242m i n7657676313214321?????????????????xxxxxxxxxxxxxxxxxi??7654321... xxxxxxxb11 1 2 1 1 0 0 0 3 4 1 2 0 1 1 0 1 2 0 1 0 0 0 1 4 6 1 3 0 1 0 0 11 1 10 3 2 0 1 0 0 0 1 0 1 0 0 1 1 2 1 2 0 1 0 0 0 1 1 0 1 0 1 0 0 3 1 12 3 0 0 1 2 2 5 1 0 1 0 0 1 1 2 1 2 0 1 0 0 0 1 0 0 0 0 0 0 1 1 ? 最優(yōu)解 x = （ 0， 1， 1， 12， 0， 0， 0 ） w =0 ? 原問(wèn)題有初始基可行解 x = （ 0， 1， 1， 12， 0） ?7654321... xxxxxxxb12 3 0 0 1 2 1 0 1 0 0 1 1 2 0 1 0 0 2 1 0 0 0 1 ?54321... xxxxxb4 4 1 0 0 1/3 2/3 1 0 1 0 0 1 9 0 0 1 2/3 4/3 2 0 0 0 1/3 1/3 ? 最優(yōu)解 x = （ 4， 1， 9） 最優(yōu)值 z = 2 作 業(yè) 課本 P45 （ 1）用大 M法 （ 2）用兩階段法 、計(jì)算中的幾個(gè)問(wèn)題 退化 ： （非退化 θ 值唯一 ） kllkllkllkikiittabababaab,1,...)0m i n (221???????? 在下一次迭代中有一個(gè)或幾個(gè)基變量為 0，從而出現(xiàn)退化解。 可能 會(huì)導(dǎo)致循環(huán)，永遠(yuǎn)達(dá)不到最優(yōu)解。 目標(biāo)函數(shù)極小化時(shí)解的最優(yōu)性判別 以 σ i ?0作為判別表中解是否最優(yōu)的標(biāo)志 tkllkllkllkikii lllabababaabtt ???????? ......)0m i n ()221,1,221且若離基。為主元素。則 11 , lkl xa? 則 xk進(jìn)基 kjj ?? ?? )0(m a x0?j?1）若有兩個(gè)以上檢驗(yàn)數(shù) ?如何解決退化問(wèn)題？ Dantzig 規(guī)則： ? 1951 年 Hoffman 給出反例。 （ 3個(gè)方程， 11個(gè)變量 ） ? 1955 年 3 個(gè)方程， 7個(gè)變量 。 6次迭代后，出現(xiàn)循環(huán)。 7,..,2,101035019021092516041650115043m i n7364321543214321???????????????????ixxxxxxxxxxxxxxxxxzi? 按照 Dantzig規(guī)則 ： ? （ 5， 6， 7） （ 1， 6， 7） （ 1， 2， 7） （ 3， 2， 7） （ 3， 4， 7） ? （ 5， 4， 7） （ 5， 6， 7） ? ? 進(jìn)基則若 ki xki ?? 0m i ?離基。中下標(biāo)最小者的基變量選 )0m i n (.2 ,?kikii aabBland 原則 （ 1976 年 第 9屆國(guó)際數(shù)學(xué)規(guī)劃大會(huì)） 無(wú)可行解的判別 當(dāng)線性規(guī)劃問(wèn)題中添加人工變量后，無(wú)論用人工變量法或兩階段法，初始單純形表中的解因含非零人工變量，故實(shí)質(zhì)上是非可行解。當(dāng)求解結(jié)果出現(xiàn)所有 σ i?0時(shí)， 如基變量中仍含有非零的人工變量 (兩階段法求解時(shí)第一階段目標(biāo)函數(shù)值不等于零 )，表明問(wèn)題無(wú)可行解。 例 7 用單純形法求解線性規(guī)劃問(wèn)題 解：添加松弛變量和人工變量，原模型化為標(biāo)準(zhǔn)型。 以 X3， X5為基變量列初始單純形表，進(jìn)行計(jì)算。 表中當(dāng)所有 Cj－ Zj=0時(shí)，基變量中仍含有非零的人工變量 X5＝ 2，故該線性規(guī)劃問(wèn)題無(wú)可行解。 7．應(yīng)用舉例 ? 什么樣的問(wèn)題可用 LP模型求解？ ? 1. 求解問(wèn)題的目標(biāo)函數(shù)可用數(shù)值指標(biāo)來(lái)反映，且為線性函數(shù)。 ? 2 . 存在多種方案。（多個(gè)可行解） ? 3. 要達(dá)到的目標(biāo)有一定的約束條件，且約束條件為線性的。 ? 例 1：用長(zhǎng) 100套鋼架，每套鋼架需長(zhǎng) , , 的料各一根， ? ？ 如何下料，使用的原料最省。 ? 分析：每一根鋼材都有多種下料