數(shù)據(jù)模型——線性規(guī)劃(文件)
【正文】 . ,2,1。計(jì)算21??，所以取第 3 個(gè)約束對(duì)應(yīng)的基變量5x為出基變量，就可以得到一個(gè)新的基可行解，在上表中把3x對(duì)應(yīng)的列變成單位向量，系數(shù)矩陣第 3 行對(duì)應(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 由于檢驗(yàn)數(shù)都小于等于 0 ，所以該基可行解就是最優(yōu)解， 對(duì)應(yīng)的最優(yōu)解為)0,0,2/1,2/5,2/13(，最優(yōu)值為 3 / 2 。 z 1x … rx … mx 1?mx … kx … nx 1 0 … k?/rka … 0 1??m? … 0 … n?? bBc B 1? ?? 1 ra 1? 11? ?ma … 0 … na 1? ? ? ? ? ? ? 1/rka 1? ?rma … 1 … rna? ? ? ? ? ? ? mra? 1 1? ?mma … 0 … mna? 1?b ? rb? ? mb? 其中rkjrjjj aa /? ??? ??；rkkrBB abbBcbBc /?? 11 ??? ????。 算 法 步 驟 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 ? 對(duì)應(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。 定理 如果向量?的第 k 個(gè)分量0?k?，而向量01 ?? kAB，則原問題無界。 bAx ? 分塊 bNxBxNB?? 左乘1?B bBNxBx NB11 ???? 即 NBNxBbBx11 ???? Nx =0 ??????????01bBx 設(shè) B 是秩為 m 的約束矩陣 A 的一個(gè) m 階滿秩子方陣，則稱B 為一個(gè) 基 ； B 中 m 個(gè)線性無關(guān)的列向量稱為 基向量 ，變量 x 中與之對(duì)應(yīng)的 m 個(gè)分量稱為 基變量 ，其余的變量為 非基變量 ，令所有的非基變量取值為 0 ，得到的解??????????01bBx稱為相應(yīng)于 B 的 基本解 。 3 ． 如果最優(yōu)解不唯一， 則會(huì)有多個(gè)基本可行解是最優(yōu)解，它們必然在同一個(gè)面上。 定理 1 引理 定理 2 定理 3 若線性規(guī)劃問題存在可行解，則該問題的可行解集（即可行域）是凸集。 B 是由 m個(gè)線性獨(dú)立的列向量組成 ),( 21 mrrr pppB ??),2,1( mjx rj ??基向量 基變量 非基變量： 其余變量 解 的 概 念 AX=BXB+NXN=b 令 非基變量 XN=0 得 BXB=b 和特解 XB =B1b 結(jié)合 XN=0 稱為對(duì)應(yīng)于 B的 基本解； 基本解個(gè)數(shù) =基的個(gè)數(shù) ≤Cnm 基可行解 可行的基本解 XB≥0 XN=0 可行基 ：對(duì)應(yīng)于基可行解的基 ??????????NBTn XXxxxX ),(21 ?A=（ B | N） 解的概念 最優(yōu)基 ： 對(duì)應(yīng)的基本可行解也是最優(yōu) 基本可行解個(gè)數(shù) ≤基的個(gè)數(shù) ≤Cnm 基本可行解的非零分量均為正分量， 其正分量個(gè)數(shù) ≤ m。 ，找出可行域。 求解的思路是：先將約束條件加以圖解 ， 求得滿足約束條件的解的集合 （ 即可行域 ） ， 然后結(jié)合目標(biāo)函數(shù)的要求從可行域中找出最優(yōu)解 。 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 ， “最小化” 概念和模型 定義 ： 對(duì)于求取一組變量 xj(j=1,2,…..,n)，使之既滿足線性約束
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1