數(shù)據(jù)模型——線性規(guī)劃-免費(fèi)閱讀
【正文】 主要表現(xiàn)在兩個(gè)方面： （ 1） 在公式中使用名稱使人們 更容易理解公式的含義 ； （ 2） 在 “ 規(guī)劃求解參數(shù) ” 對話框中使用名稱使人們 更加容易理解線性規(guī)劃模型的含義 。 車間 單位產(chǎn)品的生產(chǎn)時(shí)間（小時(shí)） 每周可獲得的生產(chǎn) 時(shí)間（小時(shí)） 門 窗 1 1 0 4 2 0 2 12 3 3 2 18 單位利潤（元） 300 500 （ 1） 決策變量 本問題的決策變量是每周門和窗的產(chǎn)量 。 因此 ， 該問題可以用 目標(biāo) 、 決策變量和約束條件 三個(gè)因素加以描述 。 改變右端向量 基 本 思 想 bBb ??? ? 1 ， bcz B ??? ?0 如果 0??b 則原最優(yōu)解還是最優(yōu)解，否則利用對 偶單純形算法求解新問題。 定理 給定一個(gè)原規(guī)劃 和對偶規(guī)劃，則下面三種情況必有其一： 1. 都有最優(yōu)解 2. 都無可行解 3. 一個(gè)有可行解另一個(gè)無界 定理 若x和 ?分別是原規(guī)劃和對偶規(guī)劃的可行解，則 x和 ? 分別是原規(guī)劃和對偶規(guī)劃的最優(yōu)解的充要條件是， mibxa iii ,...,2,1。..m i n221122112211無限制????????????????mpiqjcAnqjcAtsbijjjj,...,1。計(jì)算 1},m i n {1211??? ，所以取第二個(gè)約束對應(yīng)的基變量4x 為出基變量，就可以得到一個(gè)新的基可行解，在上表中把 2x 對應(yīng)的列變成單位向量，系數(shù)矩陣第 2 行對應(yīng)的元素為 1 ，則可以得到該基可行解的單純形表 1x 2x 3x 4x 5x 0 1 1 1 1 0 5 2 1 3 1 0 2 1 1 4 1 1 迭 代 2 由于013 ???，所以該基可行解不是最優(yōu)解，同時(shí)系數(shù)矩陣該列有大于 0的元素，所以取3x為入基變量。052222..m i n52142132121jxxxxxxxxxxtsxxzj 系數(shù)矩陣 ??????????????100110102100112A 基陣為 ?????????? ??1000100011B ???????????1010110022B 對應(yīng)的基解分別為 ?? )5,2,2,0,0(1x 和 ??? )6,3,0,0,1(2x， 其中 x1 為基本可行解， x2 不是基本可行解。 線性規(guī)劃及單純形法 ?線性規(guī)劃問題及數(shù)學(xué)模型 ?圖解法 ?單純形法原理 ?單純形法計(jì)算步驟 ?單純形法進(jìn)一步討論 ?數(shù)據(jù)包絡(luò)分析 ?其他應(yīng)用例子 單 純 形 算 法 ? 理論方法 ? 算法步驟 ? 單純形表 ? 算例 基 本 可 行 解 定 義 令 ),( NBA ? ， x = ( Bx , Nx ) 。 凸 集 的 概 念 凸集 凸集 不是凸集 頂點(diǎn) 基 本 定 理 若線性規(guī)劃問題有最優(yōu)解，一定存在一個(gè)基可行解（可行域頂點(diǎn)）是最優(yōu)解。 ， 標(biāo)出 坐標(biāo)原點(diǎn) , 坐標(biāo)軸的指向 和 單位長度 。該公司希望總的租借費(fèi)用為最小，故有如下數(shù)學(xué)模型： 目標(biāo)函數(shù) 約束條件 . ijm in a 0 ( i = 1 , .. , m 。 由此例 1的數(shù)學(xué)模型可表為： 數(shù)學(xué)模型 () ???????????????????0,52426155..2m ax212121221xxxxxxxtsxxz目標(biāo)函數(shù) 約束條件 () () () max: maximize的縮寫， “ 最大化 ” ， . subject to的縮寫， “ 受限制于 …… ” 問題的提出 例 2 捷運(yùn)公司在下一年度的 1~4月的 4個(gè)月內(nèi)擬租用倉庫堆放物資 。 線性規(guī)劃 Linear Programming 線性規(guī)劃及單純形法 ?線性規(guī)劃問題及數(shù)學(xué)模型 ?圖解法 ?單純形法原理 ?單純形法計(jì)算步驟 ?單純形法進(jìn)一步討論 ?其他應(yīng)用例子 線性規(guī)劃問題 ? 問題的提出 ? 線性規(guī)劃問題的數(shù)學(xué)模型 ? 線性規(guī)劃概念和模型 問題的提出 例 1 美佳公司計(jì)劃制造 Ⅰ 、 Ⅱ 兩種家電產(chǎn)品 。 已知各月份所需倉庫面積列于表 12。 j = 1 , .. , n )1 1 2 1 3 1 4 1 1 2 2 2 3 21 3 2 3 1 41 1 1 2 1 3 1 41 2 1 3 1 4 2 1 2 2 2 31 3 1 4 2 2 2 3 3 1 3 21 4 2 3 3 2 4 1z = 2 8 0 0 ( x + x + x + x ) + 4 5 0 0 ( x + x + x )+ 6 0 0 0 ( x + x ) + 7 3 0 0 xx + x + x + x 1 5x + x + x + x + x + x 1 0x + x + x + x + x + x 2 0x + x + x + x 1 2? ??????????? ??min： minimize ， “最小化” 概念和模型 定義 ： 對于求取一組變量 xj(j=1,2,…..,n)，使之既滿足線性約束條件，又使具有線性的目標(biāo)函數(shù)取得極值的一類最優(yōu)化問題稱為線性規(guī)劃問題。 ，找出可行域。 定理 1 引理 定理 2 定理 3 若線性規(guī)劃問題存在可行解，則該問題的可行解集（即可行域）是凸集。 bAx ? 分塊 bNxBxNB?? 左乘1?B bBNxBx NB11 ???? 即 NBNxBbBx11 ???? Nx =0 ??????????01bBx 設(shè) B 是秩為 m 的約束矩陣 A 的一個(gè) m 階滿秩子方陣，則稱B 為一個(gè) 基 ； B 中 m 個(gè)線性無關(guān)的列向量稱為 基向量 ，變量 x 中與之對應(yīng)的 m 個(gè)分量稱為 基變量 ，其余的變量為 非基變量 ，令所有的非基變量取值為 0 ，得到的解??????????01bBx稱為相應(yīng)于 B 的 基本解 。 算 法 步 驟 s te p 1 找一個(gè)初始可行基 s te p 2 求出典式和檢驗(yàn)數(shù) s te p 3 求}, . . . ,2,1m a x { njjk ?? ?? s te p 4 如果0?k?則該基可行解就是最優(yōu)解停止；否則轉(zhuǎn) s te p 5 ； s te p 5 如果01 ?? kAB，則問題無最優(yōu)解，停止；否則轉(zhuǎn) s te p 6 s te p 6 求rkrikiki abmiaab ?/},...,2,1,0??/m i n { ????? s te p 7 以kA替代rA得到 一個(gè)新的基，轉(zhuǎn) s te p 2 ； 單 純 形 表 一般假設(shè)當(dāng)前的基 ), . . . ,(21 mAAAB ? 對應(yīng)的單純形表為 1x … rx … mx 1?mx … kx … nx 1 11 ?ma … ka 1 … na 1 ? ? ? ? ? ?
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1