數(shù)據(jù)模型——線性規(guī)劃-文庫吧資料
2024-08-14 16:51本頁面
【正文】 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 ? ? ? ? ? ? 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。 給定一個(gè)非退化的基可行解 x，對應(yīng)的可行基為 B ，則等式約束變?yōu)椋? bBNxBx NB 11 ?? ?? 典式 NB NxBbBx11 ?? ?? 目標(biāo)函數(shù)NNBB xcxcxc??? ?? ?NNNB xcNxBbBc???? ?? )( 11 ?NNBB xcNBcbBc )(11 ????? ?? 令??? ??NBN cNBc1?，0?B?， 則xbBcxc B ???? ?? ?1 規(guī)劃等價(jià)于 ????????????0..m i n111xbBNxBxtsxbBcNBB? 例 考慮問題： ?????????????????????5,4,3,2,1。 定理 如果向量?的第 k 個(gè)分量0?k?，而向量01 ?? kAB，則原問題無界。 如果 01 ?? bB 則稱該 基可行解為非退化的 ，如果一個(gè)線性規(guī)劃的所有基可行解都是非退化的則稱該 規(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 的 基本解 。 剩余的問題是如何判斷一個(gè)基可行解是最優(yōu)解， 如果不是則如何從一個(gè)基可行解轉(zhuǎn)到另一個(gè)基可行解。 3 ． 如果最優(yōu)解不唯一， 則會有多個(gè)基本可行解是最優(yōu)解，它們必然在同一個(gè)面上。 線性規(guī)劃問題的基可行解 x對應(yīng)線性規(guī)劃問題可行域 (凸集 )的頂點(diǎn) 解的幾何意義 猜想 1 線性規(guī)劃的可行域是凸集； 猜想 2 最優(yōu)解若存在 ， 則可以在可行域的頂點(diǎn)上得到； 猜想 3 可行域的頂點(diǎn)的個(gè)數(shù)是有限的； 猜想 4 若有兩個(gè)最優(yōu)解，則其連線上的點(diǎn)也是最優(yōu)解，即最優(yōu)解有無窮多個(gè) 猜想 5 對于標(biāo)準(zhǔn)型的線性規(guī)劃 X是可行域頂點(diǎn)的充分必要條件是 X是基本可行解。 定理 1 引理 定理 2 定理 3 若線性規(guī)劃問題存在可行解，則該問題的可行解集（即可行域）是凸集。 凸 集 的 概 念 頂點(diǎn) ——設(shè) K是凸集， X?K； 若 K中不存在兩個(gè)不同的點(diǎn) X（ 1） ? K， X（ 2） ? K 使 X=αX（ 1） +（ 1α） X（ 2） （ 0α1） 則稱 X為 K的一個(gè) 頂點(diǎn) （也稱為極點(diǎn)或角點(diǎn)）。 B 是由 m個(gè)線性獨(dú)立的列向量組成 ),( 21 mrrr pppB ??),2,1( mjx rj ??基向量 基變量 非基變量： 其余變量 解 的 概 念 AX=BXB+NXN=b 令 非基變量 XN=0 得 BXB=b 和特解 XB =B1b 結(jié)合 XN=0 稱為對應(yīng)于 B的 基本解； 基本解個(gè)數(shù) =基的個(gè)數(shù) ≤Cnm 基可行解 可行的基本解 XB≥0 XN=0 可行基 ：對應(yīng)于基可行解的基 ??????????NBTn XXxxxX ),(21 ?A=（ B | N） 解的概念 最優(yōu)基 ： 對應(yīng)的基本可行解也是最優(yōu) 基本可行解個(gè)數(shù) ≤基的個(gè)數(shù) ≤Cnm 基本可行解的非零分量均為正分量， 其正分量個(gè)數(shù) ≤ m。 。 ，找出可行域。 () ???????????????????0,52426155..2m ax212121221xxxxxxxtsxxz() () () 圖解法 由于線性規(guī)劃模型中只有兩個(gè)決策變量，因此只需建立平面直角坐標(biāo)系就可以進(jìn)行圖解了。 求解的思路是：先將約束條件加以圖解 ， 求得滿足約束條件的解的集合 （ 即可行域 ） ， 然后結(jié)合目標(biāo)函數(shù)的要求從可行域中找出最優(yōu)解 。 j = 1 , . . , n )?概念和模型 緊縮形式： max（ 或 min） ???njjj xcZ1????????????????）（ njxmibxatsxcjnjijijnjjj,2,10),..,1(),(..zm a x 11?概念和模型 矩陣形式： max（ 或 min） 稱為決策變量向量 稱為價(jià)值系數(shù)向量或目標(biāo)函數(shù)系數(shù)向量 稱為資源常數(shù)向量或約束右端常數(shù)向量 稱為技術(shù)系數(shù)或約束系數(shù)矩陣 CX?Z???????0XbAXts ),(..???????????????nxxxX?21),( 21 ncccC
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1