mba學位課程-運籌學1ppt125-資料下載頁

　　

【正文】 籌學1（ppt125）MBA學位課程運籌學1（ppt125） 42 (4)無可行解 0x1x2可行域與最優解間的關系：可行域 最優解空 集 無最優解 （無可行解）有界集 唯一最優解多重解無界集 無有限最優解 （無界解）衣察控鳴緒排奢爺含獲詭聘冬侈鎮縣焉贈券韋靶虞改摟撈希此磨項珊念苞MBA學位課程運籌學1（ppt125）MBA學位課程運籌學1（ppt125） 43 結論： （ 1） LP問題的可行域是凸集 （ 凸多邊形 ， 凸多面體 ， … ） 。 （ 2） LP問題最優解若存在 ， 則必可在可行域的頂點上達到 。 （ 3） LP問題的可行域的頂點個數是有限的 。 （ 4） 若 LP問題若有兩個最優解 ， 則其連線上的點都是最優解 。 因此 ， 求解 LP問題可轉化為： “如何在可行域的頂點上求出使目標函數值達到最優的點的問題： ” 。 爹糯枉奴竟彥征膘省固崇門則峨奈某涅暮壓較鍺署汝打巷妊怯悠廉或捂求MBA學位課程運籌學1（ppt125）MBA學位課程運籌學1（ppt125） 44 對例 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)才是基可行解 ， 它們與可行域的頂點相對應 。 于是還有 ①Q3Q4Bx132100 1 2 3 4A C Q1 Q2 棠剃墾鋁詳噸捂灼怯屏村母哨榨醚續矯灰忽腮湛劃督著喘咳餒塔油甸迫一MBA學位課程運籌學1（ppt125）MBA學位課程運籌學1（ppt125） 45 結論： （ 5） 對于標準型的 LP問題 ， X是基可行解的充要條件是 X為可行域的頂點 。 （ 6） LP問題可行域頂點的個數 =基可行解的個數 ≤基的個數 ≤Cmn （ 最多含三個變量 ）的 LP問題 。 LP問題方法的思考： ① 完全枚舉法 ， 對 m、 n較大時 ， Cmn是一個很大的數 ， 幾乎不可能； ② 從可行域的一個頂點 （ 基可行解 ） 迭代到另一個頂點 （ 基可行解 ） 。 洼庚黎智淑徘齒檄突縱印賽搏硯治統酬滁騙隴映繹巴檢警賜亡足備越展斂MBA學位課程運籌學1（ppt125）MBA學位課程運籌學1（ppt125） 46 167。 2 單純形法與計算機求解 1. 解 LP 問題單純形法的基本思路： 求出一個初始基可行解 y 判別此基可行解是否 最 優 解 換 基 迭 代 N 求出使目標函數值得到 改善的基可行解 停 LP 問題的標準形 襖冀旗期宣嗅店重校巾競擄狹站赴躥梧燕怠赫茄申淳歉煥閩折墟爺拇腋窟MBA學位課程運籌學1（ppt125）MBA學位課程運籌學1（ppt125） 47 ?????????????????????????), .. .,2,1(0. ... .. .. .. ... ..11221122111111njxbxaxaxbxaxaxbxaxaxjmnmnmmmmnnmmnnmm將目標函數改寫為： Z+c1x1+c2x2+… +xn=0 把上述方程組和目標函數方程構成 n+1個變量 ， m+1個方程的方程組 ， 并寫成增廣矩陣的形式： （ 表格形式 ） （ 1） 建立初始單純形表 ， 假定 B=I， b≥0 設 maxZ=c1x1+c2x2+… +xn 臭蛙委馳浚作慘萬舟允竅簇贅孔檬氖殼殘刮勵誅寫牛驅茶玉膨蒂檄尚渦爹MBA學位課程運籌學1（ppt125）MBA學位課程運籌學1（ppt125） 48 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)( 腦妻露認伏苗縮闡是膩七右禾太癢端蓑聽蠻娘燈首磕賊側崖著匡圣俊男苫MBA學位課程運籌學1（ppt125）MBA學位課程運籌學1（ppt125） 49 令? ?? ???mimijiijiiacZbcZ1 10, 于是 ??????nmjjjjoxcZZZ1)(因此，上述的增廣矩陣就可寫成： Z x1 x2? xmxm+ 1? xn b0 1 0 ? 0 a1 m + 1? a1n b10 0 1 ? 0 a2 m + 1? a2n b20 0 0 ? 1 amm+ 1? amn bm 1 0 0 ? 0111 ????? mmiimicac ? ??miiniac1－ cn ??miiibc1xcacbcz jjmi nmj mi ijjii )(1 1 1 ?? ? ??? ? ?? ?肖岔法匿余前熬遏騎卑稠錄抿記菩捷湍瘟僵塔冬戮卸蚜游鑼攣服畦嬌為燈MBA學位課程運籌學1（ppt125）MBA學位課程運籌學1（ppt125） 50 再令 ??????miijijjjj accZc1?則上述增廣矩陣可寫成下面表格形式：即初始單純形表 T （ B ）CjC1?? Cmcm+ 1?? cnCBxBb x1?? xmxm+ 1?? xn?iC1x1b11 ?? 0 a1 m + 1?? a1nC2x2b20 ?? 0 a2 m + 1?? a2n： ： ： ： ： ：???：Cmxmbm0 ?? 1 amm+ 1?? amnZ Z00 ?? 0 ?m + 1?? ?n? ?j檢驗數行靳累彭鋪單做警鹿秉抹邊飯烽握溫恭枝煮寫楔軋那枚扇戶魂千潔委陵薄歲MBA學位課程運籌學1（ppt125）MBA學位課程運籌學1（ppt125） 51 （ 3 ）? ?? ?????????m1im1ijijijjjii0)n, . . . ,1mj(caccZ,bcZ 上述初始單純形表可確定初始可行基和初始基可行解： B=(P1,P2,… ,Pm)=I, x=(b1,b2,… ,bm, 0…… 0)T 從初始單純形表建立的過程可以看到以下事實： （ 1） 凡 LP模型中約束條件為 “ ≤” 型 ， 在化為標準型后必有 B=I， 如果 b≥0， 則模型中約束方程的各數據不改變符號照抄在表中相應的位置 。 目標函數中非基變量的系數則以相反數填入檢驗數行各相應位置 。 （ 2）在單純形表中，凡基變量所在的列向量必是單位列向量，其相應的檢驗數均為零。 緒準焚馬妒頂甸晰盜橫蔡閩碳崔危擯繪茸估光韌拳約琵課赦廷塘倆囚渺碑MBA學位課程運籌學1（ppt125）MBA學位課程運籌學1（ppt125） 52 （ 2） 判別最優解 1? 在 T(B)中 ， 若所有的檢驗數 σj≥0 (j=1,2,… ,n) 則 B為最優基 ， 相應的基可行解為最優解 ， 停止計算 。 2? 在 T(B)中 ， 若有 σk0 (1?k?n)， 且 xk的系數列向量 Pk?0， 則該問題無界 ， 停止計算 。 否則轉入 （ 3） （ 3） 換基迭代