【文章內(nèi)容簡介】 1500 容積 4000 5400 1500 商品 數(shù)量 體積 重量 運價 A 600 10 8 1000 B 1000 5 6 700 C 800 7 5 600 31 （三） LP問題的標準型 LP問題解的概念和解的性質(zhì)以及對 LP問題求解方便 ， 必須把 LP問題的一般形式化為統(tǒng)一的標準型： ???njjj xcz1m ax???????????),2,1(0),2,1(1njxmibxajnjijjLL或 maxz=cx ?????0XbAX標準型的特點： ① 目標函數(shù)是最大化類型 ② 約束條件均由等式組成 ③ 決策變量均為非負 ④ bi(i=1,2,… ,n)=0 32 ① 目標函數(shù)： minz?max(z)=cx ② 若約束為 “ ?” 型 ?左邊 +松馳變量； 若約束為 “ ?” 型 ?左邊－ “ 松馳變量 ” ③ 若變量 xj?0?xj?0變量 ， 若變量 xj無限制 ?令 xj=xj?－ xj? ④ 若右邊常數(shù) bi0?等式兩邊同乘以 (1)。 例 4 課本 P9 化下述問題為標準型 minz=x1+2x23x3 x1+2x2+3x3≦ 7 . x1+x2x3≦ 2 3x1+x2+2x3=5 x1,x3≥0,x2無約束 33 解：首先考察變量：令 ，并加入松馳變量 x4,x5化為如下標準型： xxx 222 ???? ????????????????????????????????????????????????0x,x,x,x,x,x5x2)xx(x32xx)xx(x7xx3)xx(2xxxxx54322132215322143221.3)(2zmax3221練習：課本 P64 （ 3） ???????????無約束y,x3x2yx.yxmax34 解：令 ???????0x,00x,xx當當?????????0x,x0x,0x當當???????0y,00y,yy當當?????????0y,0y,0y當當 則 xxx????? xxx ????? yyy yyy ?????加入松馳變量 s,w， 得到標準型如下： ????????????????????????????????????????0w,s,y,y,x,3wxx2syyxx.)yy()xx(zmax35 （四） LP問題解的概念 ： 可行解 （ Feasible Solution)： 滿足約束條件 ()和 ()的解 X=(x1,x2,… ,xn)T稱為可行解 。 所有可行解構(gòu)成可行解集 ，即可行域 。 最優(yōu)解 (Optimal Solution): 而使目標函數(shù)達到最大值的可行解稱為最優(yōu)解 ， 對應的目標函數(shù)值稱為最優(yōu)值 。 求解 LP問題就是求其最優(yōu)解和最優(yōu)值 ， 但從代數(shù)的角度去求是困難的 。 設 LP問題 ????????????)(0)(.)(zmaxxbxaxcjn1jijijn1ijj36 LP角度看： 基 (Basis)： 設 A為 mxn矩陣 ， r(A)=m， B是 A中的 mxn階非奇異子矩陣 （ 即 |B|?0） ， 則稱 B是 LP問題的一個基 。 若 B是 LP問題的一個基 ， 則 B由 m個線性獨立的列向量組成， 即 B=(Pr1,Pr2,… ,Prm)， 其中 Prj=(a1rj,a2rj,… ,amrj)T， (j=1,2,… ,m)稱為基向量 。 基變量 (Basic Variables)與非基變量 (Nonbasic Variable) 與基向量 Prj相對應的變量 xrj稱為基變量 ， 其它變量稱為非基變量 。顯然 ， 對應于每個基總有 m個基變量 ， n－ m個非基變量 。 基本解 (Basic Solution)： 設 B是 LP問題的一個基，令其 n－ m個非基變量均為零，所得方程的解稱為該 LP問題的一個基本解。顯然，基 B與基本解是一一對應的，基本解的個數(shù) ≤Cmn。 基可行解 : 在基本解中，稱滿足非負條件的基本解為基可行解，對應的基稱為可行基。 37 退化解 (Degenerate Solution)： 如果基解中非零分量的個數(shù)小于 m， 則稱此基本解為退化的 ， 否則是非退化的 。 最優(yōu)基解 (Optimal Basic Solution)： 如果對應于基 B的基可行解是 LP問題的最優(yōu)解 ， 則稱 B為 LP問題的最優(yōu)基 ， 相應的解又稱基本最優(yōu)解 。 ： 可行解 基解 最優(yōu)解 基最優(yōu)解 38 （五）兩個變量 LP問題的圖解法 LP問題圖解法的步驟： （ 1） 畫出直角坐標系； （ 2） 依次做每條約束直線 ， 標出可行域的方向 ， 并找出它們共同的可行域； （ 3） 任取一目標函數(shù)值作一條目標函數(shù)線 （ 稱等值線 ）,根據(jù)目標函數(shù) （ 最大或最小 ） 類型 ， 平移該直線即將離開可行域處 ， 則與目標函數(shù)線接觸的最終點即表示最優(yōu)解 。 例 1：用圖解法求解如下線性規(guī)劃問題 ????????????0,26232432.34zmaxxxxxxxxx212121212x1+3x2=24 3x1+2x2=26 Q2(6,4) Q1(26/3,0) Q3(0,8) A(12,0) B(0,13) 最優(yōu)解為x1=6,x2=4 最優(yōu)值為maxz=36 39 ????????????0,012416482212121xxxxxx① ② ③ ④ max=2x1+3x2 例 2：用圖解法求解下列線性規(guī)劃： ① Q3 Q 4 B x 1 3 2 1 0 1 2 3 4 Q2（ 4， 2） Q1 Q2（ 4， 2）為最優(yōu)解 ② ③ 40 解的幾種情況： （ 1） 此例有唯一解 Q2， 即 x1=4, x2=2, z=14 （ 2） 有無窮多最優(yōu)解 （ 多重解 ） ， 若將目標函數(shù)改為z=2x1+4x2 則線段 Q2， Q3上的點均為最優(yōu)解 。 （ 3） 無界解 求 m a x 無界但求 m i n 有唯一解x2x1041 (4)無可行解 0x1x2可行域與最優(yōu)解間的關系：可行域 最優(yōu)解空 集 無最優(yōu)解 （無可行解）有界集 唯一最優(yōu)解多重解無界集 無有限最優(yōu)解 （無界解）42 結(jié)論： （ 1） LP問題的可行域是凸集 （ 凸多邊形 ， 凸多面體 ， … ） 。 （ 2） LP問題最優(yōu)解若存在 ， 則必可在可行域的頂點上達到 。 （ 3） LP問題的可行域的頂點個數(shù)是有限的 。 （ 4） 若 LP問題若有兩個最優(yōu)解 ， 則其連線上的點都是最優(yōu)解 。 因此 ， 求解 LP問題可轉(zhuǎn)化為： “如何在可行域的頂點上求出使目標函數(shù)值達到最優(yōu)的點的問題： ” 。 43 對例 1 LP問題標準化為 maxZ=2x1+3x2 ??????????????0x,x12xx416xx48xx2x515241321?可求得它的所有的基本解： x(1)=(0,0,8,16,12)T(0點 ), x(2)=(4,0,4,0,12)T(Q1點 ) x(3)=(4,2,0,0,4)T(Q2點 ), x(4)=(2,3,0,8,0)T(Q3點 ) x(5)=(0,3,2,16,0)T(Q4點 ), x(6)=(4,3,2,0,0)T(C點 ) x(7)=(8,0,0,16,12)T(A點 ), x(8)=(0,4,0,16,4)T(B點 ) 但 A、 B、 C三點是非可行域上的點 ， 即非可行解 。 因此， x(1)， x(2)， x(3)， x(4)， x(5)才是基可行解 ， 它們與可行域的頂點相對應 。 于是還有 ①Q(mào)3Q4Bx132100 1 2 3 4A C Q1 Q2 44 結(jié)論： （ 5） 對于標準型的 LP問題 ， X是基可行解的充要條件是 X為可行域的頂點 。 （ 6） LP問題可行域頂點的個數(shù) =基可行解的個數(shù) ≤基的個數(shù) ≤Cmn （ 最多含三個變量 ）的 LP問題 。 LP問題方法的思考： ① 完全枚舉法 ， 對 m、 n較大時 ， Cmn是一個很大的數(shù) ， 幾乎不可能； ② 從可行域的一個頂點 （ 基可行解 ） 迭代到另一個頂點 （ 基可行解 ） 。 45 167。 2 單純形法與計算機求解 1. 解 LP 問題單純形法的基本思路： 求出一個初始基可行解 y 判別此基可行解是否 最 優(yōu) 解 換 基 迭 代 N 求出使目標函數(shù)值得到 改善的基可行解 停 LP 問題的標準形 46 ?????????????????????????),.. .,2,1(0...... .........11221122111111njxbxaxaxbxaxaxbxaxaxjmnmnmmmmnnmmnnmm將目標函數(shù)改寫為： Z+c1x1+c2x2+… +xn=0 把上述方程組和目標函數(shù)方程構(gòu)成 n+1個變量 ， m+1個方程的方程組 ， 并寫成增廣矩陣的形式： （ 表格形式 ） （ 1） 建立初始單純形表 ， 假定 B=I， b≥0 設 maxZ=c1x1+c2x2+… +xn 47 Z x1 x2 ? xm xm + 1 ? xn b 0 1 0 ? 0 a1 m + 1 ? a1n b1 0 0 1 ? 0 a2 m + 1 ? a2n b2 0 0 0 ? 1 am m + 1 ? amn bm 1 c1 c2 ? cm cm + 1 ? cn 0 以非基變量表示基變量形式?????n1mjjijiixabx ， 代入Z 中的基變量 , 有 ? ? ?? ?? ?????minmjnmjjjjijiixcXabcZ1 1 1)( ? ? ? ?? ? ?? ?????miminmjnmjjjjjiiiixcxacbc1 1 1 1)( ? ? ?? ?? ????minmjjjmiijiiixcacbc1 1 1)( 48 令? ?? ???mimijiijiiacZbcZ1 10,