數(shù)據(jù)、模型與決策_(dá)(第二版)第三章線性規(guī)劃(編輯修改稿)
2025-03-13 15:34 本頁面
【文章內(nèi)容簡介】 第三章 線性規(guī)劃 數(shù)據(jù)、模型與決策 (第二版 ) ? 實例分析： ? 某工廠生產(chǎn) A,B兩種產(chǎn)品，分別經(jīng)過三道工序，已知建立的模型如下所示，可行域為凸多邊形 OACDB, 試以圖解法求解最優(yōu)生產(chǎn)方案。 ? 目標(biāo)函數(shù) max z =20A+30B ? 工序一約束 2A+B≤ 40 ? 工序二約束 A+2B≤ 40 ? 工序三約束 A+B≤ 25 ? 非負(fù)約束 A≥ 0, B≥ 0 第三章 線性規(guī)劃 數(shù)據(jù)、模型與決策 (第二版 ) 第三章 線性規(guī)劃 數(shù)據(jù)、模型與決策 (第二版 ) ? A+2B=40 工序二約束 ? A+B=25 工序三約束 ?聯(lián)立以上方程，可以求得最優(yōu)解 ? A=10, B=15 ?代入目標(biāo)函數(shù)，求得最大目標(biāo)函數(shù)值為20*10+30*15=650。 第三章 線性規(guī)劃 數(shù)據(jù)、模型與決策 (第二版 ) 第三章 線性規(guī)劃 ? 線性規(guī)劃問題概述 ? 線性規(guī)劃問題的圖解法 ? 單純形法 ? 對偶問題 ? 敏感性分析 第三章 線性規(guī)劃 數(shù)據(jù)、模型與決策 (第二版 ) 單純形法 ? 線性規(guī)劃問題的標(biāo)準(zhǔn)形式 ? 線性規(guī)劃問題解的概念和基本定理 ? 單純形法解題步驟 第三章 線性規(guī)劃 數(shù)據(jù)、模型與決策 (第二版 ) 式 ? 規(guī)定線性規(guī)劃問題的一般形式： ? 目標(biāo)函數(shù) ? 約束條件 （ i =1,……m ） ? 非負(fù)約束 0 ( j =1,……,n) ??? njjj xcz1max jnjjji bxa ???1jx?第三章 線性規(guī)劃 數(shù)據(jù)、模型與決策 (第二版 ) 轉(zhuǎn)化為標(biāo)準(zhǔn)形式方法： ? 如果模型的目標(biāo)函數(shù)為極小值： ，那么令 z’=z , 。 ? 如果右端項 bi小于零，等式兩端同時乘以 1 。 ? 約束條件一般情況下是不等式。例如： x1+x2≤6, 令 x3=6x1x2 ， x3 ≥0，將約束條件轉(zhuǎn)化為 x1+x2+x3=6 ， x3稱作松弛變量。如果有x1+x2≥6 ,令 x4=6x1x2 , x4≥0，約束條件轉(zhuǎn)化為 x1+x2x4=6， x4稱作剩余變量。 ? 變量取值可能無約束。決策變量可以大于或等于零，也可以小于零。此時令 xj=xj’xj’’, xj’≥0, xj’’≥0, 將其代入線性規(guī)劃模型。 ? 決策變量小于等于零 , 即 xj≤0。令 xj’=xj , 將 xj’代入線性規(guī)劃模型。 ??? nj jj xcz 1min第三章 線性規(guī)劃 數(shù)據(jù)、模型與決策 (第二版 ) 和基本定理 ?目標(biāo)函數(shù) ?約束條件 （ i =1,……m ） ?非負(fù)約束 xj 0 ( j =1,……,n) ??? njjj xcz1max injjji bxa ???1?第三章 線性規(guī)劃 數(shù)據(jù)、模型與決策 (第二版 ) ? 可行解：滿足約束條件的解為可行解，全部可行解的集合為可行域。 ? 最優(yōu)解：使目標(biāo)函數(shù)值達(dá)到最大的可行解為最優(yōu)解。 ? 定理一 ： 若線性規(guī)劃問題存在可行解，則問題的可行域為凸集。 ? 定理二 ： 線性規(guī)劃問題的基可行解對應(yīng)于線性規(guī)劃問題可行域的頂點(diǎn)。 ? 定理三 ：若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解。 第三章 線性規(guī)劃 數(shù)據(jù)、模型與決策 (第二版 ) ?已知模型如下： ?目標(biāo)函數(shù) max z =20A+30B ?工序一約束 2A+B≤40 ?工序二約束 A+2B≤40 ?工序三約束 A+B≤25 ?非負(fù)約束 A≥0, B≥0 第三章 線性規(guī)劃 數(shù)據(jù)、模型與決策 (第二版 ) ?，引入三個松弛變量： C、 D、 E ?原問題轉(zhuǎn)變?yōu)槿缦滦问剑? max z =20A+30B+0C+0D+0E 2A+B+C=40 A+2B+D=40 A+B+E=25 A≥0, B≥0,C≥0,D≥0,E≥0 第三章 線性規(guī)劃 數(shù)據(jù)、模型與決策 (第二版 ) ?約束條件的系數(shù)矩陣為： ? U=(P1 ,P2 ,P3 ,P4 ,P5) = ? P3= ， P4= ， P5= 三個向量是線性無關(guān)的 ? 這些向量構(gòu)成基矩陣： V=(P3, P4, P5 ) = ??????????100110102100112??????????001??????????010??????????100??????????100010001第三章 線性規(guī)劃 數(shù)據(jù)、模型與決策 (第二版 ) ? 對應(yīng)于 V的變量為基變量，他們分別為： C=402AB D=40A2B E=25AB ? 將上述基變量代入目標(biāo)函數(shù)中，得到： Z=20A+30B+0 當(dāng)還未生產(chǎn)時， A=B=0，資源未被利用。取C=40 ,D=40 ,E=25，利潤值還未產(chǎn)生， 得到初始基本可行解： X(0) =(0， 0， 40， 40， 25)。 第三章 線性規(guī)劃 數(shù)據(jù)、模型與決策 (第二版 ) ? B的取值滿足： C=402AB≥0 D=40A2B≥0 E=25AB≥0 ? 因為 A=0,所以有： C=40B≥0 D=402B≥0 E=25B≥0 ? B的取值要求滿足上述三式，因此 B為 : ? B=min {40/1 ,40/2 ,25/1} =20 第三章 線性規(guī)劃 數(shù)據(jù)、模型與決策 (第二版 ) ?
試題試卷相關(guān)推薦
鄂ICP備17016276號-1