【文章內(nèi)容簡(jiǎn)介】 1 4 1 0 0 1/4 0 0 x5 5 0 0 5/2 5/4 1 2 x2 2 0 1 1/2 1/4 0 cj zj 0 0 1 1/4 0 [ ] 最優(yōu)解是 (4,2,0,0,5), 最優(yōu)值 16 1/ 5第 33頁(yè) cj → 2 3 0 0 0 CB 基 b x1 x2 x3 x4 x5 cj zj x1 x4 x2 2 0 3 3 1 0 1/2 0 1/5 3 0 1 0 0 1/5 4 0 0 2 1 4/5 0 0 1 0 1/5 (2) 若目標(biāo)函數(shù)為 2211 )3()2(m a x xxz ?? ????問(wèn) 分別在什么范圍內(nèi)變化時(shí) , 問(wèn)題的最優(yōu)解不變？ 21 ??、cj → 2 3 0 0 0 CB 基 b x1 x2 x3 x4 x5 cj zj x1 x4 x2 2 0 3 3 1 0 1/2 0 1/5 3 0 1 0 0 1/5 4 0 0 2 1 4/5 0 0 1 0 1/5 解： 02 ??12 ??12 ??22 1???511??,022 1 ??? ? 05 11 ???當(dāng) 即 12 1??? ?最優(yōu)解不變 . 時(shí) , 類(lèi)似可討論，當(dāng) ,01 ?? ????? 21 ?最優(yōu)解不變 . 第 34頁(yè) cj → 2 3 0 0 0 CB 基 b x1 x2 x3 x4 x5 cj zj x1 x4 x2 2 0 3 3 1 0 1/2 0 1/5 3 0 1 0 0 1/5 4 0 0 2 1 4/5 0 0 1 0 1/5 (3) 若目標(biāo)函數(shù)為 2211 )3()2(m a x xxz ?? ????問(wèn) 在什么范圍內(nèi)變化時(shí) , 問(wèn)題的最優(yōu)解不變？ 21 ??、cj → 2 3 0 0 0 CB 基 b x1 x2 x3 x4 x5 cj zj x1 x4 x2 2 0 3 3 1 0 1/2 0 1/5 3 0 1 0 0 1/5 4 0 0 2 1 4/5 0 0 1 0 1/5 解： 12 ??12 ??22 1???5121 ????,022 1 ??? ?當(dāng) 即 1,2121 ???? ???最優(yōu)解不變 . 時(shí) , 23 ??23 ??05 121 ??? ??o 2?1?第 35頁(yè) 62 分析 bi的變化范圍 cj c1 c2 CB 基 b x1 x2 xn CB XB B1b I B1N ?j 0 CN CBB1N 原問(wèn)題 對(duì)偶問(wèn)題 結(jié)論或繼續(xù)計(jì) 算的步驟 可行解 可行解 仍為最優(yōu)解 可行解 非可行解 用單純形法繼 續(xù)迭代 非可行解 可行解 用對(duì)偶單純形 法繼續(xù)迭代 非可行解 非可行解 引入人工變量 , 編制新的單純表 , 重新計(jì)算 bi的變化引起基變量的取值發(fā)生變化，有可能發(fā)生 3兩種情況 第 36頁(yè) 21 32m a x xxz ??1222 21 ?? xx164 1 ?x155 2 ?x0, 21 ?xx. 例 已知下述線性規(guī)劃的最終單純形表為 cj → 2 3 0 0 0 CB 基 b x1 x2 x3 x4 x5 cj zj x1 x4 x2 2 0 3 3 1 0 1/2 0 1/5 3 0 1 0 0 1/5 4 0 0 2 1 4/5 0 0 1 0 1/5 (1) 若 b由 (12,16,15)變成 (15,12,20), 最優(yōu)基是否發(fā)生變化 ? (2) 若 b變成 ，分別分析 在什么范圍內(nèi)變化時(shí) , 問(wèn)題的最優(yōu)基不變。 )15,16,12( 321 ??? ???321 ??? 、(3) 當(dāng) 在什么范圍內(nèi)變化時(shí) , 問(wèn)題的最優(yōu)基不變。 321??? 、第 37頁(yè) 解： cj → 2 3 0 0 0 CB 基 b x1 x2 x3 x4 x5 cj zj x1 x4 x2 2 0 3 3 1 0 1/2 0 1/5 3 0 1 0 0 1/5 4 0 0 2 1 4/5 0 0 1 0 1/5 (1) 若 b由 (12,16,15)變成 (15,12,20), 最優(yōu)基是否發(fā)生變化 ? ),( 241 PPPB ???????????????????????????????????????422/72012155/1005/4125/102/11 bBTb )20,12,15( 1??則新規(guī)劃的最初單純形表為 cj → 2 3 0 0 0 CB 基 b x1 x2 x3 x4 x5 cj zj x1 x4 x2 2 0 3 1 0 1/2 0 1/5 0 1 0 0 1/5 0 0 2 1 4/5 0 0 1 0 1/5 7/2 2 4 [ ] 2 x1 3 1 0 0 1/4 0 0 x3 1 0 0 1 1/2 2/5 3 x2 4 0 1 0 0 1/5 cj zj 0 0 0 1/2 3/5 最優(yōu)基發(fā)生變化， T)0,0,1,4,3( 1最優(yōu)值為 18 最優(yōu)解為 第 38頁(yè) 解： cj → 2 3 0 0 0 CB 基 b x1 x2 x3 x4 x5 cj zj x1 x4 x2 2 0 3 3 1 0 1/2 0 1/5 3 0 1 0 0 1/5 4 0 0 2 1 4/5 0 0 1 0 1/5 ??????????????????????????311516125/1005/4125/102/1?bB當(dāng) 問(wèn)題的最優(yōu)基不變 (2) 若 ，分別分析 在什么范圍內(nèi)變化時(shí) , 問(wèn)題的最優(yōu)基不變。 )15,16,12( 321 ??? ????b321 ??? 、,021 ?? ?? )15,16,12( 3????bT?????? ???? 53,544,53 333 ???0530544053 333 ?????? ??? ，即 1553 ??? ?類(lèi)似可求得當(dāng) 231 4,0 ??? ????26,0 132 ????? ???問(wèn)題的最優(yōu)基不變 第 39頁(yè) 解： cj → 2 3 0 0 0 CB 基 b x1 x2 x3 x4 x5 cj zj x1 x4 x2 2 0 3 3 1 0 1/2 0 1/5 3 0 1 0 0 1/5 4 0 0 2 1 4/5 0 0 1 0 1/5 ???????????????????????????32111516125/1005/4125/102/1???bB當(dāng) T?????? ??????? 53,5424,523 332131 ??????即 問(wèn)題的最優(yōu)基不變 (3) 若 ，分析 在什么范圍內(nèi)變化時(shí) , 問(wèn)題的最優(yōu)基不變。 )15,16,12( 321 ??? ????b321 ??? 、05305424,0523332131???????????????155/44265/2331231?????????????第 40頁(yè) 63 增加新變量 (增加新產(chǎn)品 ) cj c1 c2 CB 基 b x1 x2 xn CB XB B1b I B1N ?j 0 CN CBB1N 分析步驟： (1)計(jì)算 jjjBjj YPcPBCc ???? ? 1?(2)計(jì)算 jj PBP 1???(3)若 0?j?，只需將 原最優(yōu)解不變 的值反映到最終單純形表中， 和 0?j? ，則按單純形法繼續(xù)迭代計(jì)算。 j? jP?若 第 41頁(yè) 21 32m a x xxz ??1222 21 ?? xx164 1 ?x155 2 ?x0, 21 ?xx. 例 已知下述線性規(guī)劃的最終單純形表為 cj → 2 3 0 0 0 CB 基 b x1 x2 x3 x4 x5 cj zj x1 x4 x2 2 0 3 3 1 0 1/2 0 1/5 3 0 1 0 0 1/5 4 0 0 2 1 4/5 0 0 1 0 1/5 若增加一個(gè)變量 x6 , 有 c6=4, P6=(2,4,5)T, 分析問(wèn)題最優(yōu)解的變化 . 解： 1542)5/1,0,1(46 ??????????????jj PBP 1?????????????????????????????????????1405425/1005/4125/102/1 或 1140)3,0,2(46 ??????????????第 42頁(yè) cj → 2 3 0 0 0 CB 基 b x1 x2 x3 x4 x5 cj zj x1 x4 x2 2 0 3 3 1 0 1/2 0 1/5 3 0 1 0 0 1/5 4 0 0 2 1 4/5 0 0 1 0 1/5 構(gòu)造新表 cj → 2 3 0 0 0 CB 基 b x1 x2 x3 x4 x5 cj zj x1 x4 x2 2 0 3 3 1 0 1/2 0 1/5 3 0 1 0 0 1/5 4 0 0 2 1 4/5 0 0 1 0 1/5 4 x6 0 4 1 1 [ ] 利用單純形法繼續(xù)迭代 第 43頁(yè) 64 增加約束條件 (增加工序 ) 分析步驟： 先將原問(wèn)題的最優(yōu)解變量取值代入新增的約束條件， 若滿足，說(shuō)明新增約束未起到限制作用，原最優(yōu)解不變 . 否則，將新增約束直接反映到最終表中，在進(jìn)行分析 . 21 32m a x xxz ??1222 21 ?? xx164 1 ?x155 2 ?x0, 21 ?xx. 例 已知下述線性規(guī)劃的最終單純形表為 cj → 2 3 0 0 0 CB 基 b x1 x2 x3 x4 x5 cj zj x1 x4 x2 2 0 3 3 1 0 1/2 0 1/5 3 0 1 0 0 1/5 4 0 0 2 1 4/5 0 0 1 0 1/5 若增加一個(gè)約束條件 , 分析問(wèn)題最優(yōu)解的變化