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