【正文】 c xa x a x a x ba x a x a x ba x a x a x bx j n? ? ? ?? ? ? ??? ? ?????? ? ??????1 1 2 2 111 1 12 2 1 1 121 1 22 2 2 2 21 1 2 2..... ......................................................0 1 , 2 , ..... , ...n n n n mn n nn n nm m m n n n m mjM ax z c x c x c x M x M xa x a x a x x ba x a x a x x ba x a x a x x bx j n n m?????? ? ? ? ? ? ?? ? ? ? ??? ? ? ?????? ? ? ??? ? ???原問(wèn)題 輔助問(wèn)題 人工變量 T1 2 m顯 然 輔 助 問(wèn) 題 的 約 束 條 件 已 經(jīng) 化 成 了 典 式 ，X=(0,0,...,0,b ,b ,...b ) 是 輔 助 問(wèn) 題 的 一 個(gè) 基 可 行 解 。 例 5：用大 M法求解下列線性規(guī)劃問(wèn)題 131 2 31 2 3231 2 3m a x 342139, , 0z x xx x xx x xxxx x x? ? ?? ? ???? ? ? ??????? ??131 2 3 41 2 3 523m a x 3421390 , 1 , . . . 5jz x xx x x xx x x xxxxj? ? ?? ? ? ???? ? ? ? ??????? ???化標(biāo)準(zhǔn)型 添加人工變量得輔助問(wèn)題 1 3 6 71 2 3 41 2 3 5 62 3 7m a x 3421390 , 1 , . . . 7jz x x M x M xx x x xx x x x xx x xxj? ? ? ? ?? ? ? ???? ? ? ? ? ???? ? ??? ???3 0 1 0 0 M M CB B b x1 x2 x3 x4 x5 x6 x7 0 x4 4 1 1 1 1 0 0 0 M x6 1 2 1 1 0 1 1 0 M x7 9 0 3 1 0 0 0 1 ?j 10M 2M3 4M 1 0 M 0 0 0 x4 3 3 0 2 1 1 1 0 0 x2 1 2 1 1 0 1 1 0 M x7 6 6 0 4 0 3 3 1 ?j 6M 6M3 0 4M+1 0 3M 4M 0 0 x4 0 0 0 0 1 1/2 1/2 1/2 0 x2 3 0 1 1/3 0 0 0 1/3 3 x1 1 1 0 2/3 0 1/2 1/2 1/6 ?j 3 0 0 3 0 3/2 M3/2 M+1/2 1 x3 3/2 3/2 0 1 0 3/4 3/4 1/4 0 x4 0 0 0 0 1 1/2 1/2 1/2 0 x2 5/2 1/2 1 0 0 1/4 1/4 1/4 ?j 3/2 9/2 0 0 0 3/4 M+3/4 M1/4 ? 4 1 3 1 1 9 3/2 例 6：用單純形法求解線性規(guī)劃問(wèn)題 12121212m a x 2 32 2 1 2. . 2 1 4,0z x xxxs t x xxx?????????? ??121 2 31 2 4m a x 2 32 2 12. . 2 140 ( 1 , 2 , ... 4)jz x xx x xs t x x xxj??? ? ? ??? ? ??? ???1 2 51 2 31 2 4 5m a x 2 32 2 12. . 2 140 ( 1 , 2 , ...5 )jz x x M xx x xs t x x x xxj? ? ?? ? ? ??? ? ? ??? ???添加人工變量，化成典式 2 3 0 0 M CB XB b X1 X2 X3 X4 X5 0 X3 12 2 2 1 0 0 M X5 14 1 2 0 1 1 ?j 14M 2+M 3+2M 0 M 0 3 X2 6 1 1 0 0 M X5 2 1 0 1 1 1 ?j 2M18 1M 0 M 0 所有的檢驗(yàn)數(shù)都不大于零，人工變量 X5 仍留在基變量中且不為零，故原問(wèn)題無(wú)可行解。 ? 4 1 3 1 1 第二階段：將上表中的人工變量去除，目標(biāo)函數(shù)換成原問(wèn)題的目標(biāo)函數(shù)從上表的最后一個(gè)單純形表出發(fā)，繼續(xù)計(jì)算。結(jié)束第一階段，去掉人工變量，進(jìn)入第二階段求原問(wèn)題的最優(yōu)解。（ M可以看成懲罰系數(shù)） 添加 M以后，直接求解輔助問(wèn)題，可能有兩種情況： ，此時(shí)去掉人工變量直接得到原問(wèn)題的最優(yōu)解。 最優(yōu)解 X2=(5,1,8,0,0)T， 最優(yōu)值 6。否則轉(zhuǎn) step 3. Step 3 選取一個(gè)檢驗(yàn)數(shù)大于零的非基變量為進(jìn)基變量 。設(shè)新基對(duì)應(yīng)的基可行解為X1=(x11,…, x n1)T,則 X1應(yīng)滿足約束條件，即 x11 + a1k? = ? 1 x21 + a2k ? = ? 2 ……………………………………………. xm1 +amk ? = ? m xj1?0 j=1,2,…,n 由于 xi1必須是非負(fù)的，即 xi1 = ? i aik? ?0 (i=1,2,…,m) xk1= ?0 如果 aik?0， 顯然只要 ?0， 就有 xi1 = ? i aik? ?0 ， 對(duì)于aik0， 就要求 iika???所以 ?應(yīng)滿足 0 m in iika??? ???? ????2. 最優(yōu)性檢驗(yàn)和解的判別 10 j? ?（ ） 當(dāng) 所 有 檢 驗(yàn) 數(shù) 時(shí) ， 當(dāng) 前 基 可 行 解 為 最 優(yōu) 解 。 2) 迭代： 得到新基對(duì)應(yīng)的典式。B.(6,0,3,3)。 基可行解： 滿足非負(fù)約束的基解稱為基可行解。 2. 可行域的凸性 定理 1： 若線性規(guī)劃問(wèn)題的可行域 D={x ?Rn|AX=b,X?0}非空，則必為凸集。 ? 可行域存在 ， 則一定是一個(gè)凸多邊形 。 }0,{ ??? xbAxxD一、幾個(gè)概念 ： 二、兩變量 LP問(wèn)題的圖解法 圖解法是根據(jù)平面直角坐標(biāo)系和二元一次方程（不等式）的特點(diǎn)設(shè)計(jì)的。1 2 2 3 4 5m a x ( )2 ( ) 22( ) 2( ) 5, , , , , 0z x x xx x x xx x x xx x x xx x x x x x? ? ?? ? ? ? ?? ? ? ?? ? ? ??. 先化變量和目標(biāo)函數(shù) 調(diào)整約束條件 調(diào)整目標(biāo)函數(shù) 作業(yè)： 、乙兩種產(chǎn)品，每件甲產(chǎn)品的利潤(rùn)是 2元，乙產(chǎn)品的利潤(rùn)是 4元。0 , 0jjxx??39。 （ 2）都有一組線性的約束條件，它們是線性等式或不等式。 ijx則問(wèn)題歸結(jié)為尋求一組 xij的值，使函數(shù) 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 43 1 3 2 3 3 3 42 1 2 5 7 1 5 5 1 5 1 3 7 1 54 3 3 8 2 6 1 7Z x x x x x x x xx x x x? ? ? ? ? ? ?? ? ? ?達(dá)到最小。 一、實(shí)例： 生產(chǎn)安排問(wèn)題 運(yùn)輸問(wèn)題 二、線性規(guī)劃問(wèn)題的結(jié)構(gòu)特征 線性規(guī)劃問(wèn)題的特征 線性規(guī)劃問(wèn)題的一般形式 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式 一般形式向標(biāo)準(zhǔn)形式的轉(zhuǎn)化 本節(jié)內(nèi)容安排 一、實(shí)例 例 1 [生產(chǎn)安排問(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ù)如下表所示： 產(chǎn)品甲 產(chǎn)品乙 設(shè)備時(shí)數(shù) 設(shè)備 A 3 2 65 設(shè)備 B 2 1 40 設(shè)備 C 0 3 75 利潤(rùn)（元 /件） 1500 2500 問(wèn)題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤(rùn)？ 可控因素：生產(chǎn)兩種產(chǎn)品的數(shù)量，設(shè)分別為 x1 , x2，目標(biāo)是生產(chǎn)利潤(rùn)最大，設(shè)生產(chǎn)利潤(rùn)為 z. 利潤(rùn)函數(shù)為 ： 121500 2500z x x??限制條件：三臺(tái)設(shè)備的使用時(shí)間不超過(guò)設(shè)備能力的限制 設(shè)備 A: 3x1+2x2≤65 設(shè)備 B: 2x1+ x2 ≤ 40 設(shè)備 C: 3x2 ≤ 75 蘊(yùn)涵約束：產(chǎn)量為非負(fù) x1?0, x2 ?0 目標(biāo)函數(shù) 約束條件 121212212m a x 1500 25003 2 652 403 750 , 0z x xxxxxxxx????????????? ???生產(chǎn)兩種產(chǎn)品的數(shù)量，設(shè)分別為為 x1,x2，總利潤(rùn)為 z. 在處理產(chǎn)、供、銷的經(jīng)濟(jì)活動(dòng)中，會(huì)經(jīng)常遇到物資調(diào)撥的運(yùn)輸問(wèn)題。并且下面的每一個(gè)約束條件都被滿足 11 12 13 1421 22 23 2431 32 33 3411 21 3112 22 3213 23 3314 24 3420226005001700.11002001000 , 1 , 2 , 3 。 （ 3）都有一個(gè)確定的目標(biāo)，這個(gè)目標(biāo)可以表示成決策變量的線性函數(shù)，根據(jù)問(wèn)題不同，有的要求實(shí)現(xiàn)極大化，有的要求實(shí)現(xiàn)極小化。j j jx x x??(4) 約束條件右端的負(fù)常數(shù)