運(yùn)籌學(xué)習(xí)題課ppt課件(編輯修改稿)
2025-01-04 06:02 本頁面
【文章內(nèi)容簡介】 用單純形法與對偶單純形法的比較。 單純形法最好是：約束全是“ ≤”，且常數(shù)項(xiàng)全非負(fù)， (求極大還是極小，目標(biāo)函數(shù)的系數(shù)正負(fù)倒是無所謂的 )。此時(shí)初始基可行解易得。 否則就要利用引進(jìn)人工變量等方法來尋找初始基可行解。 對偶單純形法最好是：求極大 (極小 )，且目標(biāo)函數(shù)的系數(shù)全負(fù) (正 )的，全是不等式約束 (但約束是“ ≤”還是“ ≥” ,常數(shù)項(xiàng)的符號倒是無所謂 )。此時(shí)初始正則基易得。 要善于選擇工具 !!! 2022/1/4 《運(yùn)籌學(xué)》習(xí)題課 17 單純形法 中 人工變量 的引進(jìn) 單純形法最好是：約束全是“ ≤”，且常數(shù)項(xiàng)全非負(fù)，此時(shí)初始基可行解易得。 引進(jìn)的人工變量實(shí)際上最后必須是 0，所以它們在求極大 (小 )問題的目標(biāo)函數(shù)的系數(shù)都是 M(M),這里的 M是一個(gè)很大的正數(shù)。此方法故也叫“ 大 M法 ”，也可叫“ 罰函數(shù)法 ”， M叫“ 罰因子 ”。 2022/1/4 《運(yùn)籌學(xué)》習(xí)題課 18 單純形法中無最優(yōu)解 LP問題沒有最優(yōu)解分兩種情況： (當(dāng)然沒有最優(yōu)解 ) :如引進(jìn)了人工變量，最后它們中有不能為 0的 . ：檢驗(yàn)數(shù)有正的但系數(shù)矩陣該列中所有系數(shù)沒有正數(shù)，不能繼續(xù)迭代，這就說明該 LP問題沒有有限的最優(yōu)解。 2022/1/4 《運(yùn)籌學(xué)》習(xí)題課 19 單純形法中無可行解 LP問題： Max z = 20x1 + 30x2 3x1 + 10x2 ≤ 150 . x1 ≤ 30 x1 + x2 ≥ 40 x1 , x2 ≥ 0 用 Excel的規(guī)劃求解得到： 2022/1/4 《運(yùn)籌學(xué)》習(xí)題課 20 圖解法求 1. 0 10 30 40 10 20 30 40 20 50 可行域?yàn)榭占?2022/1/4 《運(yùn)籌學(xué)》習(xí)題課 21 用單純形法求解 Max z=20x1+30x2 3x1 +10x2 ≤ 150 . x1 ≤ 30 x1+ x2 ≥ 40 x1 ,x2 ≥ 0 +x4 = +x3 = ,x6 x5 = ,x3 ,x4 ,x5 +x6 要化成等式約束，添加兩個(gè)松弛變量x3, x4，一個(gè)剩余變量 x5 。 用單純形法，再引進(jìn)一個(gè)人工變量 x6 。 +0x3+0x4+0x5 Mx6 用單純形法求解 x1 x2 x3 x4 x5 x620 30 0 0 0 1000x3 0 3 10 1 0 0 0 150 15x4 0 1 0 0 1 0 0 30 0x6 1000 1 1 0 0 1 1 40 401000 1000 0 0 1000 10001020 1030 0 0 1000 00迭代次數(shù)基變量 C B b 比值zjσj=cjzj40000x2 30 1 0 0 0 15 50x4 0 1 0 0 1 0 0 30 30x6 1000 0 0 1 1 25 691 30 103 0 1000 1000711 0 103 0 1000 01z jσ j =c j z j24550用單純形法求解 x1 x2 x3 x4 x5 x620 30 0 0 0 1000x2 30 0 1 0 0 6 0x1 20 1 0 0 1 0 0 30 0x6 1000 0 0 1 1 4 020 30 103 711 1000 10000 0 103 711 1000 02zjσj=cjzj3220迭代次數(shù)基變量 C B b 比值檢驗(yàn)數(shù)全非正，此解已是“最優(yōu)解”， 但人工變量 x6仍是基變量 ,且 x6=40，所以原線性規(guī)劃問題沒有可行解。 2022/1/4 《運(yùn)籌學(xué)》習(xí)題課 24 線性規(guī)劃中無可行解 1. (常數(shù)項(xiàng)非負(fù) ,全是不等式約束 .)不須引進(jìn)人工變量的 LP問題會(huì)不會(huì) 無可行解 ？ 在保證常數(shù)項(xiàng)非負(fù)的情況下，只有遇到等式約束或“ ≥”的不等式約束才會(huì)需要引進(jìn)人工變量。若一個(gè) LP問題全部是“ ≤”的不等式約束就不需要引進(jìn)人工變量。 (0,0,…,0) 就是該 LP問題的一個(gè)可行解 ,所以不會(huì)沒有可行解。 2022/1/4 《運(yùn)籌學(xué)》習(xí)題課 25 線性規(guī)劃中無可行解 2. 須引進(jìn)人工變量的 LP問題是否一定沒有可行解 ？ 當(dāng)然不一定。 3. 沒有最優(yōu)解的 LP問題是否一定 沒有可行解 ？ 當(dāng)然不一定。 2022/1/4 《運(yùn)籌學(xué)》習(xí)題課 26 線性規(guī)劃中無最優(yōu)解 的 LP問題會(huì)不會(huì) 有最優(yōu)解 ？ 答 :沒有可行解 的 LP問題一定 沒有最優(yōu)解 。 的 LP問題是否一定 有最優(yōu)解 ？ 答 :有可行解 的 LP問題也可能 沒有最優(yōu)解 。 有可行解 的 LP問題如可行域是有界的則它一定 有最優(yōu)解 。所以無最優(yōu)解只會(huì)出現(xiàn)在可行域是 空集 或是 無界集 的情況。 從一個(gè)一個(gè)的可行基迭代進(jìn)程中如沒有找到最優(yōu) (基 )解，而又不能再繼續(xù)迭代：出現(xiàn) 檢驗(yàn)數(shù)有正的，但系數(shù)矩陣的該列中沒有正的系數(shù) 。 下面就通過舉例來討論用單純形法如何判斷有可行解 的 LP問題 有 還是 沒有最優(yōu)解 。 2022/1/4 《運(yùn)籌學(xué)》習(xí)題課 27 無最優(yōu)解的線性規(guī)劃 LP問題： Max z = x1 + x2 x1 － x2 ≤ 1 . － 3x1 +2x2 ≤ 6 x1 , x2 ≥ 0 用 Excel的規(guī)劃求解得到： 2022/1/4 《運(yùn)籌學(xué)》習(xí)題課 28 圖解法求 2. 2 1 1 2 1 2 3 4 0 3 可行域?yàn)闊o界集 目標(biāo)函數(shù)等高線可無限上移 2022/1/4 《運(yùn)籌學(xué)》習(xí)題課 29 用單純形法求解 Max z= x1+ x2 x1 x2 ≤1 . 3x1 +2x2 ≤6 x1 , x2 ≥0 +x4 = +x3 = ,x3 , x4 化等式約束，添加兩個(gè)松弛變量 x3, x4。 +0x3 +0x4 先標(biāo)準(zhǔn)化 列出初始單純形表： x1 x2 x3 x41 1 0 0x3 0 1 1 1 0 1x4 0 3 2 0 1 60 0 0 01 1 0 0比值迭代次數(shù)基變量 C B b0z j0σ j =c j z j用單純形法求解 有兩個(gè)檢驗(yàn)數(shù)為正，選 ？ 進(jìn)基， x2 該列系數(shù)只有一個(gè)為正，選 ？ 出基。 x4 3 x3 0 0 1 4x2 1 1 0 3 1 0 0 0 1z j3σ j =c j z j讓 x1出基也類似 有兩個(gè)檢驗(yàn)數(shù)為正，選 ？ 進(jìn)基， x1 該列系數(shù)只有一個(gè)為正，選 ？ 出基。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1