【正文】 0 0 基變量 0 1 2 8 9 3 2 0 0 2 1 21 該問題具有無界解 λj 山東理工大學(xué)管理學(xué)院 用單純形法求解下列 LP問題 ??????????????0,10251553410m a x21212121xxxxxxxxf????????????????0,10251553410m a x432142132121xxxxxxxxxxxxf課堂練習(xí) 山東理工大學(xué)管理學(xué)院 xj x1 x2 x3 x4 b x3 3 5 1 0 15 x4 5 2 0 1 10 10 4 0 0 0 基變量 15/3=5 λj * 10/5=2 山東理工大學(xué)管理學(xué)院 xj x1 x2 x3 x4 b x3 0 19/5 1 3/5 9 x1 1 2/5 0 1/5 2 0 0 0 2 20 基變量 45/19 λj * 5 最優(yōu)解為 X*=( 2, 0, 9, 0 )T max f = 20 山東理工大學(xué)管理學(xué)院 xj x1 x2 x3 x4 b x2 0 1 5/19 3/19 45/19 x1 1 0 2/19 5/19 20/19 0 0 0 2 20 基變量 λj 最優(yōu)解為 X*=( 20/19, 45/19, 0, 0 )T max f = 20 山東理工大學(xué)管理學(xué)院 線性規(guī)劃問題的對偶理論 ? 線性規(guī)劃的對偶問題 ? 對偶問題的基本性質(zhì) ? 對偶問題的經(jīng)濟(jì)意義 ? 對偶單純形法 ? 小結(jié) ? 作業(yè) 山東理工大學(xué)管理學(xué)院 線性規(guī)劃的對偶問題 一、原問題與對偶問題 例 某廠在計(jì)劃期內(nèi)要安排生產(chǎn) A、 B兩種產(chǎn)品 ， 這兩種產(chǎn)品分別需要在甲 、 乙丙三種不同的設(shè)備上加工 ， 有關(guān)數(shù)據(jù)如表 314所示 。x3 +0 （改進(jìn)基可行解） ? 從 λj 0 中找最大者，其對應(yīng)變量 xk稱為 換入變量 ， ? xk所在 列稱為主元列 ? 確定換入變量的最大值和換出變量 ? 最小比值原則 0m in ?????? ??ikikiiaab?山東理工大學(xué)管理學(xué)院 68 ? 設(shè)第 l 行使 ? 最小，則第 l 行對應(yīng)的基變量 x l稱為 換出變量 ，第 l 行稱為主元行 迭代過程 ? 主元行 l 行與 主 元 列 k 列相交的元素 alk 稱為主元，迭代以主元為中心進(jìn)行 ? 迭代的實(shí)質(zhì)是線性變換，即要將主元 alk變?yōu)?1， 主列 上其它元素變?yōu)?0。 山東理工大學(xué)管理學(xué)院 ? 本節(jié)課的重點(diǎn)是線性規(guī)劃模型 的標(biāo)準(zhǔn)化 小 結(jié) ? 本節(jié)課的難點(diǎn)是線性規(guī)劃 的基本解和基本可行解的概念 山東理工大學(xué)管理學(xué)院 作業(yè) 考慮下列線性規(guī)劃問題： M a x z x x x x? ? ? ?2 4 5 61 2 3 4 x x x x1 2 3 44 2 8 2? ? ? ? ? ? ? ? ?x x x x1 2 3 42 3 4 11 x jj? ?0 1 2 3 4, , , , 試確定：（ 1 ）基本解的最大個(gè)數(shù)； （ 2 ）求出所有基本可行解； （ 3 ）寫出最優(yōu)基可行解。 ?LP問題的基本可行解對應(yīng)于可行域的頂點(diǎn)。 X為基可行解， B為可行基 山東理工大學(xué)管理學(xué)院 1 2 1 Ｂ 1 =(P1 P2 P3 )= 3 2 0 0 2 0 |B1|=6≠0, B1可逆 x1 + 2 x 2 +x 3 = 30 3x 1 +2x 2 +x 4 = 60 2x 2 +x 5 =24 x 1 … x 5 ? 0 1. LP問題解的概念 x1=12(1/3 x4 1/3 x5) x2=12(1/2 x5 ) x3 =6( 1/3 x4 2/3 x5 ) 令 x4=x5=0 解得 X=(12, 12, 6, 0, 0)T X為非基可行解， B1不是可行基。 ※ 基本解的數(shù)目不超過 Cnm = 個(gè)。對應(yīng)的基矩陣稱為可行基矩陣（簡稱可行基）。 山東理工大學(xué)管理學(xué)院 AX=b的求解過程： XB XN (B N) = b A = ( B N ) ?????????NBXXXbNXBX NB ??NB NXbBX ??NB NXBbBX 11 ?? ??1. LP問題解的概念 山東理工大學(xué)管理學(xué)院 定義 2 基本解 ——對應(yīng)于基 B，令非基變量為 0，求得基變量的 值 ，則稱 為 LP問題 的一個(gè)基本解。 線性規(guī)劃問題解的概念 假定： (1) R(A)=m (2) n m 我們考慮標(biāo)準(zhǔn)型的線型規(guī)劃問題： 1. LP問題解的概念 山東理工大學(xué)管理學(xué)院 定義 1 基 (基矩陣 ) ——若系數(shù)矩陣 A的一個(gè) m階子矩陣 B是可逆矩陣，則稱 B為 LP問題的一個(gè)基。 線性規(guī)劃問題的標(biāo)準(zhǔn)型 山東理工大學(xué)管理學(xué)院 課下練習(xí)：將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)型 21 52m i n xxf ?? 0,082421211?????xxxxx 21 2m a x xxf ?? 無限制212121,0321xxxxxx?????? 167。= f ② 引入松弛變量 x6 ③ 引入剩余變量 x7 ④ 令 x3 = x4 x5 max f39。 山東理工大學(xué)管理學(xué)院 min f = x1+2x2 –3x3 x1+x2 +x3? 7 x1 x2 +x3 ? 2 x1， x2?0， x3無限制 例 5 將下列 LP模型標(biāo)準(zhǔn)化 167。????則令山東理工大學(xué)管理學(xué)院 LP模型 標(biāo)準(zhǔn)化方法總結(jié)： 167。 線性規(guī)劃問題的標(biāo)準(zhǔn)型 f x 0 f y 1 1 ???njjj xcf1m i nffffm i nm a x 39。? 16 x139。 = x1 +6 0 ? x139。 , x2 ?0 例 4 167。 +x2 ? 11 x139。 , x1 ,x2 ?0 167。 – 3 x1 +2x2 ? 8 x139。 x1 , x139。 線性規(guī)劃問題的標(biāo)準(zhǔn)型 山東理工大學(xué)管理學(xué)院 (1) 約束條件的標(biāo)準(zhǔn)化 例 2 max f =2x1+ 5x2+6x3 +8x4 4x1+6x2+ x3 +2x4 ? 12 x1+ x2+7x3+5x4 ? 14 2x2+ x3+3x4 ? 8 x1 , …, x4 ?0 x5 = x6 = x7 = 1 , …, 7 剩余變量 167。x4+0 線性規(guī)劃問題的標(biāo)準(zhǔn)型 (4) 約束條件右端常數(shù)的標(biāo)準(zhǔn)化 山東理工大學(xué)管理學(xué)院 (1) 約束條件的標(biāo)準(zhǔn)化 例 1 max f=40x1+ 50x2 +0 線性規(guī)劃問題的標(biāo)準(zhǔn)型 山東理工大學(xué)管理學(xué)院 (2) LP問題標(biāo)準(zhǔn)型的向量表達(dá)形式 167。 線性規(guī)劃問題解的概念 1. LP問題解的概念 2. LP問題解的性質(zhì) 山東理工大學(xué)管理學(xué)院 41 LP問題數(shù)學(xué)模型的一般形式 max(min) f = c1x1+ c2x2+…+ xn a11x1+ a12x2+…+ a1nxn ?(=, ?)b1 a21x1+ a22x2+…+ a2nxn ?(=, ?)b2 … … … am1x1+ am2x2+…+ amnxn ?(=, ?)bm xj ?0( ? 0， 正負(fù)不限 ) j = 1, … , n 回顧 山東理工大學(xué)管理學(xué)院 1. LP標(biāo)準(zhǔn)型的定義 a11x1+ a12x2+…+ a1nxn =b1 a21x1+ a22x2+…+ a2nxn =b2 … … … … am1x1+ am2x2+…+ amnxn =bm xj ?0(j =1,2,…, n) max f=c1x1+ c2x2+…+ xn 其中 bi ?0 (i =1,2,…, m) 167。 線性規(guī)劃問題的標(biāo)準(zhǔn)型及解的概念 167。 (2) 若有最優(yōu)解，一定可在可行域的頂點(diǎn)得到。 （ 3）平移等值線，找出最優(yōu)點(diǎn) C，求出該點(diǎn)的坐標(biāo)（ 4， 1），即為最優(yōu)解。 x1 =159? x2 =+? (0? ? ? 1) X= = ? +(1? ) max f=1200 x1 6 15 x2 12 線性規(guī)劃圖解法 山東理工大學(xué)管理學(xué)院 最優(yōu)值無界 無有限最優(yōu)解 max f=2x1+ 4x2 2x1+x2 ?8 2x1+x2 ? 2 x1 , x2 ?0 f =0 2x1+ x2=8 2x1+ x2=2 8 2 4 6 x2 4 0 x1 例 3： 用圖解法求解下列線性規(guī)劃問題： 線性規(guī)劃圖解法 山東理工大學(xué)管理學(xué)院 max f =3x1+2x2 x1 x2 ?1 x1 , x2 ?0 因?yàn)樵摼€性規(guī)劃問題無可行解，因此，無最優(yōu)解。 C點(diǎn)： x1+2x2 = 30 3x1+2x2 = 60 線性規(guī)劃圖解法 山東理工大學(xué)管理學(xué)院 max f=40x1+ 80x2 x1+2x2 ? 30 3x1+2x2 ? 60 2x2 ? 24 x1 , x2 ?0 例 2： 用圖解法求解下列線性規(guī)劃問題： 線性規(guī)劃圖解法 山東理工大學(xué)管理學(xué)院 f= 40 x1 + 80x2 =0 x1 + 2x2 =30 x2 x1 最優(yōu)解： BC線段 B點(diǎn) C點(diǎn) X(1)=(6,12) X(2)=(15,) X=? X(1)+(1?) X(2) (0? ? ? 1) 解 : 0 D A B C max f=40x1+ 80x2 x1+2x2 ? 30 3x1+2x2 ? 60 2x2 ? 24 x1 , x2 ?0 線性規(guī)劃圖解法 山東理工大學(xué)管理學(xué)院 x1 =6?+ +(1 ? ) ? 一個(gè)二維