確定決策變量即用變量取不同的值來表示可供選擇的各種不同方案-在線瀏覽
2025-07-12 22:08本頁(yè)面
【正文】 40)(3.13321 sxxxxts 50)(79 23321 ????? ?? sxxxx2035 21 ??? xx0,0,0,0,0,0 213321 ?????? ?? ssxxxx???????????????nxxxX?21)( 21 ncccC ??,212222111211???????????????mnmmnnaaaaaaaaaA???????若取???????????????mbbbb?21CXz ?m a x3. 線性規(guī)劃問題的矩陣表達(dá)式： nn xcxcxcz ???? ?2211m a x對(duì)???????????????????mnmnmmnnnnbxaxaxabxaxaxabxaxaxats??????22112222212111212111.0, 21 ?nxxx ?0.??XbAXts)( 21 ?? nxxx ?)( 21 ?? mbbb ?一、線性規(guī)劃的解 可行解： ?????0XbAX滿足約束方程0.m ax)(???XbAXtsCXzLP對(duì)問題? ??? 002022 , nxxxX ?若的一個(gè)可行解為問題則稱 )(0 LPX可行域： （ LP）的全體可行解構(gòu)成的集合稱為可行域 ? ?0| ??? XbAXXS ，即：可行域最優(yōu)解及最優(yōu)值： 設(shè) S是（ LP）的可行域 不唯一 唯一 ，若存在 SX ?* ，使得對(duì)任意的 SX ?CXCX ?*都有）的最優(yōu)解，為問題（則稱 LPX * ）的最優(yōu)值稱為問題（ LPCXZ ** ?若對(duì)任意大的 M0,都存在可行解使得該線性規(guī)劃的目標(biāo) 函數(shù)值 MZ ?，則稱該線性規(guī)劃問題無界 二、兩個(gè)變量的線性規(guī)劃的圖解法 ????????????0,3482.52m a x121212121xxxxxxtsxxz劃用圖解法解以下線性規(guī)例解 ： （ 1）在直角坐標(biāo)系上 畫出可行域 （ 2）做目標(biāo)函數(shù)的等值線 3*,2*)4( 21 ?? xx最優(yōu)解為193522* ?????z最優(yōu)值0 1x2x..........82 21 ?? xx41 ?x32 ?x可行域 kxx ?? 21 521052 21 ?? xx求交點(diǎn)：)3(??????382221xxx )3,2(),( 21 ?xx凸多邊形 頂點(diǎn) . ????????????0,3482.2m a x221212121xxxxxxtsxxz劃用圖解法解以下線性規(guī)例解 ： （ 1）在直角坐標(biāo)系上 畫出可行域 （ 2）做目標(biāo)函數(shù)的等值線 8*)3( ?z最優(yōu)值0 1x2x..........82 21 ?? xx41 ?x32 ?x22 21 ?? xx求交點(diǎn)：??????382221xxx )3,2(),(21 ?xx22 21 ?? xx??????482121xxx )2,4(),(21 ?xx）之間的所有點(diǎn)。它可能是有界的；也可能是無界的。如果是唯一的，這個(gè)解一定在該凸多邊形的某 個(gè)頂點(diǎn)上；如果是無窮多個(gè)，則這些最優(yōu)解一定充滿凸多邊 形的一條邊界（包括此邊界的兩個(gè)頂點(diǎn)） 總之，若（ LP）問題有最優(yōu)解，則最優(yōu)解一定可以在凸多邊 形的某個(gè)頂點(diǎn)達(dá)到 若（ LP）問題有可行解，但沒有有限最優(yōu)解，此時(shí)凸多邊形 是無界的 （反之不成立） 若（ LP）問題沒有可行解，則該問題沒有最優(yōu)解 三、基與基本可行解 ???????????????nxxxX?21? ?ncccC ?21????????????????mnmmnnaaaaaaaaaA???????212222111211其中???????????????mbbbb?210,0.m ax)(????bXbAXtsCXzLP 問題對(duì)不妨設(shè) AX=b有解，且 m≤n ，解的結(jié)構(gòu)：對(duì) bAX ?，唯一解若 nrArAr ??? )()(有無窮多解bAX ?利用線性代數(shù)的方法求出無窮多解？ ? 只討論 rn, 此時(shí) nrArAr ??? )()(有解的充要條件是且 r(A)=r=m (若 rm,必有多余方程，可去掉） 0,0.m a x)(????bXbAXtsCXzLP 問題對(duì)由線性代數(shù)結(jié)論知 : 若 r(A)=m，則 A 中至少存在一個(gè) m階子式 |B|≠0 即 A中存在滿秩的 m階矩陣 B ,稱 B為（ LP）問題的一個(gè)基 ?????????????????325323222432143214321xxxxxxxxxxxx例如：???????????321115323221121A????????????110100000021121，對(duì) bAX ? nrArAr ??? )()(且不妨設(shè) m≤n ???????????321110000021121mArAr ??? 2)()(定義 在（ LP）問題中， A的任意一個(gè) m m階 的非奇異子方陣 B（即 |B|≠0）稱為 （ LP）問題的一個(gè) 基 一個(gè)線性規(guī)劃問題最多有 基 mnC0,0.m a x)(????bXbAXtsCXzLP 問題對(duì)設(shè) r(Amxn)=r=m ???????????????0,2162.7m a x211212121xxxxxxxtsxxz對(duì)線性規(guī)劃問題例??????????????????0,2162.7m a x543215142132121xxxxxxxxxxxxxtsxxz其標(biāo)準(zhǔn)型為????????????100010101100121A系數(shù)矩陣 ? ?54321 PPPPP?? ?5432 PPPB ?? ?3211 PPPB ? 基 基 ? ?4323 PPPB ? 不是基 設(shè) r(A)=mn 0,0.m a x)(????bXbAXtsCXzLP 問題對(duì)不妨設(shè) A的前 m列構(gòu)成 A的一個(gè)基 ???????????????nxxxX?21???????????????mnmmnnaaaaaaaaaA???????212222111211則??????????????????mnnnmmmmmmmmmmaaaaaaaaaaaaaaa?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1