數(shù)據(jù)模型——線性規(guī)劃(編輯修改稿)
2024-08-28 16:51 本頁面
【文章內(nèi)容簡介】 ?圖解法 ?單純形法原理 ?單純形法計算步驟 ?單純形法進一步討論 ?數(shù)據(jù)包絡(luò)分析 ?其他應(yīng)用例子 單 純 形 算 法 ? 理論方法 ? 算法步驟 ? 單純形表 ? 算例 基 本 可 行 解 定 義 令 ),( NBA ? ， x = ( Bx , Nx ) 。 bAx ? 分塊 bNxBxNB?? 左乘1?B bBNxBx NB11 ???? 即 NBNxBbBx11 ???? Nx =0 ??????????01bBx 設(shè) B 是秩為 m 的約束矩陣 A 的一個 m 階滿秩子方陣，則稱B 為一個 基 ； B 中 m 個線性無關(guān)的列向量稱為 基向量 ，變量 x 中與之對應(yīng)的 m 個分量稱為 基變量 ，其余的變量為 非基變量 ，令所有的非基變量取值為 0 ，得到的解??????????01bBx稱為相應(yīng)于 B 的 基本解 。當 01 ?? bB 則稱基本解為 基本可行解 ，這時對應(yīng)的基陣 B 為 可行基 。 如果 01 ?? bB 則稱該 基可行解為非退化的 ，如果一個線性規(guī)劃的所有基可行解都是非退化的則稱該 規(guī)劃為非退化的 。 理 論 方 法 定理 （ 最優(yōu)性準則 ）如果0??，則基可行解 x 為原問題的最優(yōu)解。 定理 如果向量?的第 k 個分量0?k?，而向量01 ?? kAB，則原問題無界。 定理 對于非退化的基本可行解 x ，若向量?的第 k 個分量0?k?，而向量.1 kAB ?至少有一個正分量，則可以找到一個新的基本可行解 x? 使得 xcxc ?? ?? 。 給定一個非退化的基可行解 x，對應(yīng)的可行基為 B ，則等式約束變?yōu)椋? bBNxBx NB 11 ?? ?? 典式 NB NxBbBx11 ?? ?? 目標函數(shù)NNBB xcxcxc??? ?? ?NNNB xcNxBbBc???? ?? )( 11 ?NNBB xcNBcbBc )(11 ????? ?? 令??? ??NBN cNBc1?，0?B?， 則xbBcxc B ???? ?? ?1 規(guī)劃等價于 ????????????0..m i n111xbBNxBxtsxbBcNBB? 例 考慮問題： ?????????????????????5,4,3,2,1。052222..m i n52142132121jxxxxxxxxxxtsxxzj 系數(shù)矩陣 ??????????????100110102100112A 基陣為 ?????????? ??1000100011B ???????????1010110022B 對應(yīng)的基解分別為 ?? )5,2,2,0,0(1x 和 ??? )6,3,0,0,1(2x， 其中 x1 為基本可行解， x2 不是基本可行解。 算 法 步 驟 s te p 1 找一個初始可行基 s te p 2 求出典式和檢驗數(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得到 一個新的基，轉(zhuǎn) s te p 2 ； 單 純 形 表 一般假設(shè)當前的基 ), . . . ,(21 mAAAB ? 對應(yīng)的單純形表為 1x … rx … mx 1?mx … kx … nx 1 11 ?ma … ka 1 … na 1 ? ? ? ? ? ? 1 1?rma … rka … rna ? ? ? ? ? ? 1 1?mma … mka … mna 1b ? rb ? mb 如果kx 為入基變量，rx 為出基變量，則經(jīng)過變換單純形表為 1x … rx … mx 1?mx … kx … nx 1 ra 1? 11? ?ma … 0 … na 1? ? ? ? ? ? ? 1 / rka 1??rma … 1 … rna? ? ? ? ? ? ? mra? 1 1??mma … 0 … mna? 1?b ? rb? ? mb? 其中rkikrjijijaaaaa /? ??kjrimi ??? , . . . ,2,1。 rkrjrjaaa /? ?， rkrrabb /??，rkiikiiababb /???。 目標函數(shù)NNBB xcNBcbBcz )(11 ????? ???等價于 bBcxcNBcz BNNB 11 )( ????? ??? 由于0?B?，??? ??NBN cNBc1?，所以bBcxz B 1???? ?。把 Z 看成變量在 單純形表中加上一列，同時加上一行描述方程bBcxz B 1???? ?，則可以 得到新的單純形表： Z 1x … rx … mx 1?mx … kx … nx 1 0 … 0 … 0 1?m? … k? … n? bBc B 1?? 1 11 ?ma … ka 1 … na 1 ? ? ? ? ? ? 1 1?rma … rka … rna ? ? ? ? ? ? 1 1?mma … mka … mna 1b ? rb ? mb 當進行轉(zhuǎn)換時只需要把k?轉(zhuǎn)換成 0 對應(yīng)其它位置等價變換即可。 z 1x … rx … mx 1?mx … kx … nx 1 0 … k?
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1