數(shù)據(jù)模型——線性規(guī)劃(存儲版)
【正文】 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。計算21??，所以取第 3 個約束對應(yīng)的基變量5x為出基變量，就可以得到一個新的基可行解，在上表中把3x對應(yīng)的列變成單位向量，系數(shù)矩陣第 3 行對應(yīng)的元素為 1 ，則可以得到該基可行解的單純形表： 1x 2x 3x 4x 5x 0 0 1 / 2 1 / 2 3 / 2 1 0 5 1 / 2 5 / 2 1 0 1 / 2 3 / 2 0 1 1 / 2 1 / 2 1 3 / 2 5 / 2 1 / 2 由于檢驗數(shù)都小于等于 0 ，所以該基可行解就是最優(yōu)解， 對應(yīng)的最優(yōu)解為)0,0,2/1,2/5,2/13(，最優(yōu)值為 3 / 2 。0,...,2,1。0)( ????njxAc jj ,...,2,1。 Bx Nx RHS Z Bx 0 ??? ? NB cNBc 1 bBcB 1?? I NB 1? bB 1? 當(dāng)只改變一個分量ssbb ?? 時： 11111)()(???????????????????sssBbbbbBbBbbbBbBb 其中1?sB 為1?B 的第 s 列。 ?實(shí)際上 ， 所有的線性規(guī)劃問題都包含這三個因素： （ 1） 決策變量 是問題中有待確定的 未知 因素 。 可設(shè)： x1為每周門的產(chǎn)量 （ 扇 ） ； x2為每周窗的產(chǎn)量 （ 扇 ） 。 所以 ， 一般給跟公式和模型有關(guān)的四類單元格命名 。 ?在 Excel電子表格中建立線性規(guī)劃模型 ?用 Excel“規(guī)劃求解 ” 工具求解線性規(guī)劃問題 ?在用電子表格建立數(shù)學(xué)模型 （ 這里是一個線性規(guī)劃模型 ） 的過程中 ， 有三個問題需要得到回答： （ 1） 要作出的決策是什么 ？ （ 決策變量 ） （ 2） 在作出這些決策時 ， 有哪些約束條件 ？（ 約束條件 ） （ 3） 這些決策的目標(biāo)是什么 ？ （ 目標(biāo)函數(shù) ） ? 用 Excel“規(guī)劃求解 ” 工具求解線性規(guī)劃問題 （如果 “ 工具 ” 菜單中沒有 “ 規(guī)劃求解 ” 選項，請參見 SOLVER文件夾下的 “ Excel規(guī)劃求解工具的安裝說明 .doc”） 在用 Excel的 “ 規(guī)劃求解 ” 工具求解線性規(guī)劃問題 ， 為 單元格命名 能使線性規(guī)劃問題的電子表格模型更加容易理解 。 解： 例可用下表 表示 。 ?問該 工廠應(yīng)如何安排這兩種新產(chǎn)品的生產(chǎn)計劃 ，可使總利潤最大 ？ ?在該問題中 ， 目標(biāo)是總利潤最大化 ， 所要決策的變量是新產(chǎn)品的每周產(chǎn)量 ， 而新產(chǎn)品的每周產(chǎn)量要受到三個車間每周可用于生產(chǎn)新產(chǎn)品時間的限制 。 為了使原最優(yōu)解依然是新問題的最優(yōu)解， 2x 的系數(shù)最小 可以變?yōu)?/122??? c?。 定理 如果一個線性規(guī)劃有最優(yōu)解，則其對偶規(guī)劃也有最優(yōu) 解， 且它們的最優(yōu)值相等。, . . . ,2,1。021322..2m i n53243232132jxxxxxxxxxxtsxxzj 初 始 單 純 形 表 以1x 、4x 和5x 為基變量就可以得到初始基可行解?)2,1,0,0,2( ， 其對應(yīng)的單純形表為 1x 2x 3x 4x 5x 1 2 1 2 1 1 3 1 1 1 1 2 1 2 迭 代 1 由于 012??? ，所以該基可行解不是最優(yōu)解，同時系數(shù)矩陣該列有大于 0的元素，所以取2x 為入基變量。 給定一個非退化的基可行解 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ī)劃等價于 ????????????0..m i n111xbBNxBxtsxbBcNBB? 例 考慮問題： ?????????????????????5,4,3,2,1。 剩余的問題是如何判斷一個基可行解是最優(yōu)解， 如果不是則如何從一個基可行解轉(zhuǎn)到另一個基可行解。 凸 集 的 概 念 頂點(diǎn) ——設(shè) K是凸集， X?K； 若 K中不存在兩個不同的點(diǎn) X（ 1） ? K， X（ 2） ? K 使 X=αX（ 1） +（ 1α） X（ 2） （ 0α1） 則稱 X為 K的一個 頂點(diǎn) （也稱為極點(diǎn)或角點(diǎn)）。 () ???????????????????0,52426155..2m ax212121221xxxxxxxtsxxz() () () 圖解法 由于線性規(guī)劃模型中只有兩個決策變量，因此只需建立平面直角坐標(biāo)系就可以進(jìn)行圖解了。因 5月份起該公司不需要租借倉庫，故 x24， x33， x34， x42， x43， x44均為零。 x1， x2的取值受到設(shè)備 A、 B和調(diào)試工序能力的限制 ， 用于描述限制條件的數(shù)學(xué)表達(dá)式稱為 約束條件 。 已知各制造一件時分別占用的設(shè)備 A， B的臺時 、 調(diào)試工序時間及每天可用于這兩種家電的能力 、 各售出一件時的獲利情況 ， 如表 11所示 。 倉庫租借費(fèi)用隨合同期而定 ， 期限越長 ， 折扣越大 ， 具體數(shù)字見表 13。 max（ 或 min） nn xcxcxcZ ???? ??2211? ??????????????????????????????自由,00,),(),(),(..21221122222121112121
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1