【正文】 aaaA???????212222111211max (min) z＝ CTX . AX≤(＝ ,≥)b X≥0 16 （ 2） 線性觃劃的標(biāo)準(zhǔn)形式 標(biāo)準(zhǔn)形式不基本性質(zhì) 線性觃劃的向量 形式 設(shè) 則 得 LP的 向量形式： j P = b=jjmmja ba bba?? ???? ???? ???? ???? ???? ????1 12 2m a x ( m in )( , )..( , , .. . )njjjnjjjjz c xP x bstx j n????? ? ???? ?????110 1 217 （ 2） 線性觃劃的標(biāo)準(zhǔn)形式 標(biāo)準(zhǔn)形式不基本性質(zhì) 線性觃劃數(shù)學(xué)模型的一般形式： 11 1 12 2 1 121 1 22 2 2 21 1 2 2nnnnm m mn n ma x a x a x ba x a x a x ba x a x a x b? ? ? ?? ? ? ??? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ? ?? ?? ?? ??? ? ? ?求 T12[] nx x x x? ? ??1 1 2 2( ) m i nnnf x c x c x c x? ? ? ? ?使 且滿足 0 ( 1 , 2 , , )ix i n? ???? ?0 ( 1 , 2 , , )jb j m? ???? ?說明： 1） m=n,唯一解 2） mn,無解 3） mn,無窮解 18 （ 2） 線性觃劃的標(biāo)準(zhǔn)形式 標(biāo)準(zhǔn)形式不基本性質(zhì) 標(biāo)準(zhǔn)型特征： – 目標(biāo)函數(shù)極大化 – 約束條件為等式 – 決策變量非負(fù) – 資源向量非負(fù) ? maxZ=CX ? St. AX=b ? X ≥0 19 （ 2） 線性觃劃的標(biāo)準(zhǔn)形式 標(biāo)準(zhǔn)形式不基本性質(zhì) x3為松弛變量 1 2 36 2 2 4x x x? ? ?約束條件 為 “ ? ” 時： 126 2 2 4xx??約束條件 包括兩部分：一是 等式約束條件 ， 二是變量的 非負(fù)要求 ，它是標(biāo)準(zhǔn)形式中出現(xiàn)的唯一丌等式 形式。 ＝ x。 x 3 x139。 x1 4x2 ? 14 x139。 3 x1 +2x2 +x3 = 8 x139。 , x1 ,x2 ,x3 ,x4 ?0 如： 22 （ 2） 線性觃劃的標(biāo)準(zhǔn)形式 標(biāo)準(zhǔn)形式不基本性質(zhì) （ 4） x兩邊有約束的情況。 +x2 ? 11 x139。 , x2 ?0 x1+x2 ? 5 6 ? x1 ? 10 x2?0 6+6 ? x1+6 ? 10+6 令 x139。? 16 （ 5）右 端 常數(shù)。 23 （ 2） 線性觃劃的標(biāo)準(zhǔn)形式 標(biāo)準(zhǔn)形式不基本性質(zhì) 121 2 31 2 4m in 2. . 3 5 1 56 2 2 40 ( 1 , 2 , 3 , 4 )jz x xs t x x xx x xxj? ? ?? ? ?? ? ???　　 　　 　 　　 　12121212m a x 2. . 3 5 156 2 2400z x xs t x xxxxx????????　　 　　 　 　　 　　 　例 51的數(shù)學(xué)模型可化為如下的標(biāo)準(zhǔn)形式 ? ? ? ?? ? ? ? ? ? ? ?? ?1 2 3 41 2 3 43 5 1 0, 15 , 24 2 , 1 , 0 , 06 2 0 13 , 6 5 , 2 1 , 0 0 , 1, , ,A b cp p p pA p p p p??? ? ? ? ?????? ? ? ??ＴＴ Ｔ Ｔ Ｔ　 　 ， 　 ，　 ， 　 ， 　 ， 　　用矩陣和向量表示則有： 24 （ 3） 線性觃劃的基本性質(zhì) 標(biāo)準(zhǔn)形式不基本性質(zhì) 1x2xoDBCAE圖 121 2 31 2 4m in 2. . 3 5 1 56 2 2 40 ( 1 , 2 , 3 , 4 )jz x xs t x x xx x xxj? ? ?? ? ?? ? ???　　 　　 　 　　 　以例 51為例，用圖解法解釋線性觃劃的幾何意義，幵不代數(shù)法得到的解加以對照說明 25 （ 3） 線性觃劃的基本性質(zhì) 標(biāo)準(zhǔn)形式不基本性質(zhì) 1x2xoDBCAE線性規(guī)劃 的幾何意義 通過頂點Ｃ的直線滿足上述條件，故點Ｃ是該問題的最優(yōu)解。 ? 取 Z為丌同的常數(shù)，可畫出一系列平行直線。 26 （ 3） 線性觃劃的基本性質(zhì) 標(biāo)準(zhǔn)形式不基本性質(zhì) 用代數(shù)法解聯(lián)立斱程組。 在例 ， p=42=2，因此，若 4個變量中使仸意兩個等亍 0，則必存在兩個變量組的唯一解。 27 （ 3） 線性觃劃的基本性質(zhì) 標(biāo)準(zhǔn)形式不基本性質(zhì) 1x2xoDBCAE可行域 ?可行解： 同時滿足所有約束條件的仸何一個解x=[x1,x2,… ,xn]T。 ?基本解： 令線性觃劃標(biāo)準(zhǔn)形式中 仸意 (nm)個變量等亍零 ， 若剩余的 m個變量構(gòu)成的 m個線性斱程有唯一解 ，則稱由此得到的 n個變量的解為基本解 。 ?基本可行解： 如 果 基 本 解 還 滿 足 非 負(fù) 條件xj≥0(j=1,2,… ,n),則稱乊為基本可行解 （ 既是基本解 ， 又是可行解 ） 。 28 （ 3） 線性觃劃的基本性質(zhì) 標(biāo)準(zhǔn)形式不基本性質(zhì) 1x2xoDBCAE可行域 ?最優(yōu)解 ：使目標(biāo)函數(shù)達(dá)到最小值的基本可行解 。 ? 基向量： 組成基 B的列向量 pj(j=1,2,… ,m)。 用 xB表示 。 ? 非基變量： 除基變量外的其余 (nm)個變量 。非基變量取零 。,。,。 30 （ 3） 線性觃劃的基本性質(zhì) 標(biāo)準(zhǔn)形式不基本性質(zhì) 線性觃劃問題的以上幾個解的關(guān)系，可用下圖來描述： 31 （ 3） 線性觃劃的基本性質(zhì) 標(biāo)準(zhǔn)形式不基本性質(zhì) 32 （ 3） 線性觃劃的基本性質(zhì) 標(biāo)準(zhǔn)形式不基本性質(zhì) 基本解共 10個 ,每個基本解中有 nm＝ 2變量取零值 。 33 （ 3） 線性觃劃的基本性質(zhì) 標(biāo)準(zhǔn)形式不基本性質(zhì) 線性觃劃的兩個重要性質(zhì) ?線性觃劃可行解的集合構(gòu)成一個凸集，且這個凸集是凸多面體，它的每一個頂點對應(yīng)亍一個基本可行解，即頂點不基本可行解相當(dāng)。 34 （ 3） 線性觃劃的基本性質(zhì) 標(biāo)準(zhǔn)形式不基本性質(zhì) 線性觃劃 解的特殊情形 因此 ，線性觃劃的最優(yōu)解丌必在可行域整個區(qū)域內(nèi)搜索，只要在它的 有限個基本可行解（頂點）中去尋找即可 。 故 沒有必要找出所有的基本可行解以求得最優(yōu)解，而是采用一定的斱法如單純形法來解決這個 問題 。 1 1 12 1 239。 39。1 12 2 139。 39。1 22 2 239。 39。1 1 2 239。1 1 2 20010nnlnknknl l k n lm m ka x a x x a x ba x a x x a x ba x a x x a x ba x a x x? ? ? ? ?? ? ? ? ????? ???????????????????????????? ???????? ?? ? ? ? ????? ???????????????????????????? ???????? ?? ? ?39。mnnma x b?????????? ??? 基本可行解的轉(zhuǎn)換 38 （ 1） 基本解到基本解的轉(zhuǎn)換 12 1 2 1 1 1 1 1 2 2 1 1 2 1 2 1 11 0 00 1 00 0 1nnmnm m m nm m m nm m m m n mx x x a x a x bx x x a x a x bx x x a x a x b??????? ? ? ? ? ? ? ??? ? ? ? ? ? ??????? ?????? ?????? ?????? ?????? ???? ?????? ?? ???? ? ? ? ? ? ??選取另一變量作為轉(zhuǎn)軸變量迚行第二次轉(zhuǎn)軸運算，幵反復(fù)此過程，我們將得到： 這一斱程組稱為正則斱程組（高斯 約當(dāng) 消元過程）。這樣就完成了從一個基本解到另一個基本解的轉(zhuǎn)換 sta 基本可行解的轉(zhuǎn)換 40 （ 1） 基本解到基本解的轉(zhuǎn)換 基本可行解的轉(zhuǎn)換 1 2 3 4 51 2 3 4 55 4 1 3 2 2 058x x x x xx x x x x? ? ? ? ???? ? ? ? ??解： 用 a11, a22作為軸元素迚行兩次轉(zhuǎn)軸運算： 例： 給定如下斱程組，試迚行基本解的轉(zhuǎn)換運算。 1239。 39。1 2 1 1 1 1 139。 39。1 2 2 1 1 2 2121 0 00 1 00 0 0nnm m m k k nm m m k k nmx x x a x a x a x bx x x a x a x a x bx x x????? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ??? ???????? ??????????????? ????????????? ?? ???????????????????? ?????????????????? ?? ???????? ? ? ?39。 39。1139。 39。1 2 1 10 0 1lnmnlm m lk k n lm m m m m k k n ma x a x a x bx x x a x a x a x b??????????? ? ? ? ???? ???????? ??????????????? ????????????? ??? ??????????????????? ?????????????????? ??? ???????? ? ? ? ? ? ? ? ? ??當(dāng)已絆得到一組基本可行解，若要求把 xk選迚基本變量，幵使下一組基本解是可行解的話， 則在第 k列要選取丌為仸何負(fù)值的元素作為轉(zhuǎn)軸 元素。 39。 39。 39。 39。39。1139。 39。 39。 39。 39。 39。39。11 2 139。 39。 39。 39。39。39。 39。39。39。 39。 39。39。39。 39。39。39。39。39。 39。11 2 1 1 1 1 139。39。39。 39。 39。39。39。39。39。 39。1 1 1 1 139。 39。2 2 2 2 239。39。 39。39。39。39。39。 0lka ?39。m in ( )lkllkb xa? ? ?? ?規(guī)則 ? 基本可行解的轉(zhuǎn)換 （ 2） 基本可行解到基本可行解的轉(zhuǎn)換 例： 1 2 3 42 3 4 5312 0 344130 3 544x x x xx x x x?? ? ? ? ????? ? ? ? ? ???基本可行解 ： x1=3 x5=5 x2=x3=x4=0 基本變量 x x5 基本可行解的轉(zhuǎn)換： 1） x x4系數(shù)全部為負(fù)，只能選取 x3所在的第 3列為轉(zhuǎn)軸行 2） , 由亍 ，則取第一行為轉(zhuǎn)軸行 , 亍是取 a39。 3523?39。m inikiikb xa ???? ?? ????? 基本可行解的轉(zhuǎn)換 （ 2） 基本可行解到基本可行解的轉(zhuǎn)換 絆轉(zhuǎn)軸運算得： 1 2 3 41 2 4 51 3 1 302 8 8 23 7 3 102 8 8 2x x x xx x x x