部分運籌學(xué)方法ppt課件(編輯修改稿)

　

【文章內(nèi)容簡介】 1, , , , , , ,r s r mB p p p p p p??? ? 3 對基 B 的單純形表 T ( B ) 進(jìn)行適當(dāng)?shù)淖儞Q，使向量sp?變?yōu)閱挝幌蛄浚ǚ至縭sb取 1 ，其它分量取 0 ），得新基 B ? 的單純形表? ?TB ?。 為了使1rsb ?，只需將原表數(shù)用rsb去除第r 行各數(shù)，得新表第 r 行各數(shù)，即rjrjrsbbb? ? ? ?0 jn??，為使新表中0isb ? ? ?0 i r m? ? ?，需將原表中第 i 行減去第 r 行相應(yīng)數(shù)的isrsbb倍，得新表第 i 行的數(shù)，即 isi j i j r jrsbb b bb? ? ? ?? ?0 , 0i j m j n? ? ? ? ? 換基后，新基 B ? 仍是一個可行基，且目標(biāo)函數(shù)值增加。如此循環(huán)，得最優(yōu)解。 4 . 如果基 B 對應(yīng)的單純形表 T ( B ) 中檢驗數(shù)有負(fù)數(shù)0 0sb ?，且對應(yīng)的列向量1210ssssmsbbp B pb???????????????????，那么，目標(biāo)函數(shù)無上界，即無最優(yōu)解。 求解 單純形法 ? 將所給問題化為標(biāo)準(zhǔn)形 ? 找出一個初始可行基 ,建立初始單純形表 ? 檢查所有檢驗數(shù) (若全為非負(fù) ,則已得到最優(yōu)解 ,計算停止 .否則繼續(xù)下一步 ) ? 考察是否無解 (若是 ,計算停止 ,否則繼續(xù)下一步 ) ? 確定入基變量 ,出基變量 ? 對初始單純形表進(jìn)行單純形變換 四 . 用單純形法解線性規(guī)劃問題 [ 例題 ] 1 2 3m a x 2Z x x x? ? ? 1 2 31 2 31 2 31 2 33 6 02 1 0..20, , 0x x xx x xstx x xx x x? ? ???? ? ???? ? ??? ?? 解： 引進(jìn)松弛變量，化為標(biāo)準(zhǔn)形： 1 2 3m a x 2Z x x x? ? ? 1 2 3 41 2 3 51 2 3 61 2 63 602 10..20, , , 0x x x xx x x xstx x x xx x x? ? ? ???? ? ? ???? ? ? ??? ?? 此時， p 變量1 2 6,x x x對應(yīng)的列向量為 1311p???????????，2111p????????????，3121p????????????，4100p???????????，???????????0105p，6001p??????????? 顯然，? ?1 4 5 61, , 11B p p p????????????是一可行基。 （ 1 ） 作對應(yīng)于基1B的單純形表 1 1x 2x 3x 4x 5x 6x Z 0 － 2 1 － 1 0 0 0 4x 60 3 1 1 1 0 0 5x 10 1 * － 1 2 0 1 0 6x 20 1 1 － 1 0 0 1 2 判別： 因為表中的檢驗數(shù)有負(fù)數(shù)，即01 2b ??，03 1b ??，基1B不滿足最優(yōu)解條件，又01b，03b對應(yīng)的 列向量中的分量有非負(fù)數(shù)，所以需換基迭代。 3 求軸心項 在兩個非負(fù)檢驗數(shù)中，取最左邊的01 2b ??，屬1x所在列，對應(yīng)1x的列向量為1p ?，1311p????? ???????，1p ?中 有三個正分量11 3b ?，121 ?b，31 1b ?，因為1 0 2 0 3 01 1 2 1 3 16 0 1 0 2 0m in , , m in , , 1 03 1 1b b bb b b?? ?????? ??????，所以 21b為軸心項，在表 1 中把 1 加上“ * ”號，即 1* 。 （ 4 ） 在基1B中調(diào)入1p，換出5p，得新基????????????110010031),(6142pppB。 （ 5 ）作對應(yīng)于基2B的單純形表? ?2TB： （ i ）在原表中用數(shù) 1* 去除第二行各數(shù)，得新表第二行各數(shù)； （ ii ）原表中第零行各數(shù)減去第二行相應(yīng)數(shù)0121bb倍，得新表第零行的數(shù)， 原表中第一行各數(shù)減去第二行相應(yīng)數(shù)1121bb倍，得新表第一行的數(shù)， 原表中第零行各數(shù)減去第二行相應(yīng)數(shù)3121bb倍，得新表第三 行的數(shù)， 對新基2B的單純形表? ?2TB的計算，只需用矩陣的初等變換將軸心項變?yōu)?1 ，該列其余分量為零即可。 經(jīng)過上述步驟的計算，可得對應(yīng)于基? ?2 4 1 6,B p p p?的單純形表 2 1x 2x 3x 4x 5x 6x Z 20 0 － 1 3 0 2 0 4x 30 0 4 － 5 1 － 3 0 1x 10 1 － 1 2 0 1 0 6x 10 0 2* － 3 0 － 1 1 由于表中的檢驗 數(shù)仍有負(fù)數(shù)，應(yīng)重復(fù)上述換基迭代過程，可得新基? ?3 4 1 2,B p p p?的單純形表 3 1x 2x 3x 4x 5x 6x Z 2 5 0 0 3 0 32 12 4x 10 0 0 － 1 1 － 1 － 2 1x 15 1 1 12 0 12 12 2x 5 0 1 32? 0 12? 12 表中的檢驗數(shù)已沒有負(fù)數(shù)，且所有? ?0 0 1 , 2 , 3ibi ??，最優(yōu)解已求出： 1 2 4 3 5 61 5 , 5 , 1 0 , 0x x x x x x? ? ? ? ? ?，1 2 3m a x 2 25Z x x x? ? ? ? [ 例題 ] 12m a x 2 5Z x x?? 122121258..2 3 3,0xxxstxxxx? ? ??????? ? ??? ?? 解： 化為標(biāo)準(zhǔn)型： 12m a x 2 5Z x x?? ???????????????????)5,2,1(033285..52142321?jxxxxxxxxxtsj 基為? ?345,p p p，? ?TB如下表： 1x 2x 3x 4x 5x Z 0 － 2 － 5 0 0 0 3x 5 － 1 1 1 0 0 4x 8 0 1 0 1 0 5x 3 － 1 2 0 0 1 對應(yīng)于基 B 的基本可行解為? ?0 , 0 , 5 , 8 , 3 Tx ?，0Z ?，但由于檢驗數(shù)01 20b ? ? ?，02 50b ? ? ?，且? ?1 0 1 , 2 , 3ibi ??，據(jù)定理 2 知，此問題無最優(yōu)解。 第五節(jié) 求解線性規(guī)劃的計算軟件 ? 一． 用 LINDO軟件解線性規(guī)劃 ? LINDO是“ Linear interactive and discrete optimizer”的縮寫，它是解決線性規(guī)劃，整數(shù)規(guī)劃等規(guī)劃問題的有力工具，在大型計算機(jī)上，它可用于解決 50000個約束條件，202200個變量的線性規(guī)劃問題。 ? 安裝好 LINDO軟件后，在桌面上雙擊LINDO圖標(biāo)，得一個空白圖框，然后在空白圖框內(nèi)輸入求解問題，如 1 2 3m a x 2 x x x?? 1 2 31 2 31 2 31233 602 10.20000x x xx x xstx x xxxx? ? ??? ? ??? ? ???????? 在下拉菜單中點擊命令 s o l ve 或直接用快捷組合鍵 C t r l +s ，即可得解。 二． 用 MATLAB優(yōu)化工具箱解線性規(guī)劃 ? MATLAB是 Matrix Laboratory（矩陣實驗室）的縮寫。它早期是線性代數(shù)課的教學(xué)軟件，后來逐步應(yīng)用于實際工程問題的計算，目前已成為工程界和應(yīng)用數(shù)學(xué)人員常用的數(shù)學(xué)軟件之一。 MATLAB是一種交互式的高級計算機(jī)軟件，有如下特點： ? 它以矩陣運算為基本運算，用命令式語句運行，附有數(shù)值計算，最優(yōu)化，信號處理，系統(tǒng)識別，控制系統(tǒng)等幾十個工具箱（ Toolbox）； ? MATLAB使用十分方便，幾乎是直接把算式鍵入計算機(jī)，立刻得出計算結(jié)果，因此有“電子草稿紙”的美譽； ? 具有很強(qiáng)的圖形表現(xiàn)能力。 ? ?,X LP c A b? 用于求解模型： m in..z c Xs t A X b?? 仍以上例為例，解法如下： ? ?2 1 1c ??； [ 3 1 1 。 1 1 2 。 1 1 1 ] 。A ? ? ? ? ?60 。 10 。 20b ?； ? ?,X LP c A b? Z c X?? ? Matlab軟件求解線性規(guī)劃的命令如下： 結(jié)果： x= Z= 第 三 部 分 運籌學(xué)方法 第五章 非線性規(guī)劃的概念和原理 ? 非線性規(guī)劃的實例及數(shù)學(xué)模型 ? 無約束非線性規(guī)劃問題 ? 約束非線性規(guī)劃問題 第一節(jié) 非線性規(guī)劃的實例及數(shù)學(xué)模型 ? [例題 ] 投資問題： ? 假定國家的下一個五年計劃內(nèi)用于發(fā)展某種工業(yè)的總投資為 b億元，可供選擇興建的項目共有幾個。已知第 j個項目的投資為 億元，可得收益為 億元，問應(yīng)如何進(jìn)行投資，才能使盈利率（即單位投資可得到的收益）為最高？ ja jc解： 令決策變量為jx，則jx應(yīng)滿足條件? ?10jjxx ?? 同時jx應(yīng)滿足約束條件1njjja x b??? 目標(biāo)函數(shù)是要求盈利率 ? ?1121, , ,njjjn njjjcxf x x xax?????最大。 [ 例題 ] 廠址選擇問題： 設(shè)有 n 個市場，第 j 個市場位置為 ? ?,jjpq，它對某種貨物的需要量為jb ? ?1 , 2 , ,jn?。現(xiàn)計劃建立 m 個倉庫，第 i 個倉庫的存儲容量為ia ? ?1 , 2 , ,im?。試確定倉庫的位置，使各倉庫對各市場的運輸量與路程乘積之和為最小。 解： 設(shè)第 i 個倉庫的位置為 ? ?,iixy ? ?1 , 2 , ,im?， 第 i 個倉庫到第 j 個市場的貨物供應(yīng)量為ijz ? ?1 , 2 , , , 1 , 2 , ,i m j n??，則第 i 個倉庫到第 j 個市場的距離為 ? ? ? ?22i j i j i jd x p y q? ? ? ? 目標(biāo)函數(shù)為 ? ? ? ?221 1 1 1m n m ni j i j i j i j i ji j i jz d z x p y q? ? ? ?? ? ? ?? ? ? ? 約束條件為： （ 1 ） 每個倉庫向各市場提供的貨物量之和不能超過它的存儲容量； （ 2 ） 每個市場從各倉庫得到的貨物量之和應(yīng)等于它的需要量； （ 3 ） 運輸量不能為負(fù)數(shù)。 因此，問題的數(shù)學(xué)模型為： ? ? ? ?2211m inmni