數(shù)據(jù)模型——線性規(guī)劃-wenkub
2022-08-29 16:51:56 本頁(yè)面
【正文】 ) ???????????????????0,52426155..2m ax212121221xxxxxxxtsxxz() () () 圖解法 由于線性規(guī)劃模型中只有兩個(gè)決策變量，因此只需建立平面直角坐標(biāo)系就可以進(jìn)行圖解了。 。 凸 集 的 概 念 頂點(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)）。 線性規(guī)劃問(wèn)題的基可行解 x對(duì)應(yīng)線性規(guī)劃問(wèn)題可行域 (凸集 )的頂點(diǎn) 解的幾何意義 猜想 1 線性規(guī)劃的可行域是凸集； 猜想 2 最優(yōu)解若存在 ， 則可以在可行域的頂點(diǎn)上得到； 猜想 3 可行域的頂點(diǎn)的個(gè)數(shù)是有限的； 猜想 4 若有兩個(gè)最優(yōu)解，則其連線上的點(diǎn)也是最優(yōu)解，即最優(yōu)解有無(wú)窮多個(gè) 猜想 5 對(duì)于標(biāo)準(zhǔn)型的線性規(guī)劃 X是可行域頂點(diǎn)的充分必要條件是 X是基本可行解。 剩余的問(wèn)題是如何判斷一個(gè)基可行解是最優(yōu)解， 如果不是則如何從一個(gè)基可行解轉(zhuǎn)到另一個(gè)基可行解。 如果 01 ?? bB 則稱該 基可行解為非退化的 ，如果一個(gè)線性規(guī)劃的所有基可行解都是非退化的則稱該 規(guī)劃為非退化的 。 給定一個(gè)非退化的基可行解 x，對(duì)應(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? 例 考慮問(wèn)題： ?????????????????????5,4,3,2,1。 目標(biāo)函數(shù)NNBB xcNBcbBcz )(11 ????? ???等價(jià)于 bBcxcNBcz BNNB 11 )( ????? ??? 由于0?B?，??? ??NBN cNBc1?，所以bBcxz B 1???? ?。021322..2m i n53243232132jxxxxxxxxxxtsxxzj 初 始 單 純 形 表 以1x 、4x 和5x 為基變量就可以得到初始基可行解?)2,1,0,0,2( ， 其對(duì)應(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í)系數(shù)矩陣該列有大于 0的元素，所以取2x 為入基變量。 2 . 現(xiàn)在還有待解決的問(wèn)題是如何給出初始基可行 解以及出現(xiàn)退化的時(shí)候如何處理。, . . . ,2,1。..m a x????實(shí) 例 例 寫出下列規(guī)劃的對(duì)偶規(guī)劃 ???????????????5, . . . ,2,1。 定理 如果一個(gè)線性規(guī)劃有最優(yōu)解，則其對(duì)偶規(guī)劃也有最優(yōu) 解， 且它們的最優(yōu)值相等。以此為初始基可行解進(jìn)行迭代就可以求出 新問(wèn)題的解。 為了使原最優(yōu)解依然是新問(wèn)題的最優(yōu)解， 2x 的系數(shù)最小 可以變?yōu)?/122??? c?。 經(jīng)測(cè)算 ，每生產(chǎn)一扇門需要在車間 1加工 1小時(shí) 、 在車間 3加工 3小時(shí)；每生產(chǎn)一扇窗需要在車間 2和車間 3各加工 2小時(shí) 。 ?問(wèn)該 工廠應(yīng)如何安排這兩種新產(chǎn)品的生產(chǎn)計(jì)劃 ，可使總利潤(rùn)最大 ？ ?在該問(wèn)題中 ， 目標(biāo)是總利潤(rùn)最大化 ， 所要決策的變量是新產(chǎn)品的每周產(chǎn)量 ， 而新產(chǎn)品的每周產(chǎn)量要受到三個(gè)車間每周可用于生產(chǎn)新產(chǎn)品時(shí)間的限制 。 （ 2） 目標(biāo)函數(shù) 是指對(duì)問(wèn)題所追求的目標(biāo)的數(shù)學(xué)描述 。 解： 例可用下表 表示 。 由于門和窗的單位利潤(rùn)分別為 300元和 500元 ， 而其每周產(chǎn)量分別為x1和 x2， 所以每周總利潤(rùn) z為： z = 300x1＋ 500x2 （ 元 ） （ 3） 約束條件 本問(wèn)題的約束條件共有 四 個(gè) 。 ?在 Excel電子表格中建立線性規(guī)劃模型 ?用 Excel“規(guī)劃求解 ” 工具求解線性規(guī)劃問(wèn)題 ?在用電子表格建立數(shù)學(xué)模型 （ 這里是一個(gè)線性規(guī)劃模型 ） 的過(guò)程中 ， 有三個(gè)問(wèn)題需要得到回答： （ 1） 要作出的決策是什么 ？ （ 決策變量 ） （ 2） 在作出這些決策時(shí) ， 有哪些約束條件 ？（ 約束條件 ） （ 3） 這些決策的目標(biāo)是什么 ？ （ 目標(biāo)函數(shù) ） ? 用 Excel“規(guī)劃求解 ” 工具求解線性規(guī)劃問(wèn)題 （如果 “ 工具 ” 菜單中沒(méi)有 “ 規(guī)劃求解 ” 選項(xiàng)，請(qǐng)參見(jiàn) SOLVER文件夾下的 “ Excel規(guī)劃求解工具的安裝說(shuō)明 .doc”） 在用 Excel的 “ 規(guī)劃求解 ” 工具求解線性規(guī)劃問(wèn)題 ， 為 單元格命名 能使線性規(guī)劃問(wèn)題的電子表格模型更加容易理解 。 用 Excel“規(guī)劃求解 ” 工具求解線性規(guī)劃問(wèn)題 線性規(guī)劃結(jié)束！ 。 所以 ， 一般給跟公式和模型有關(guān)的四類單元格命名 。其中，“ Max”是英文單詞“ Maximize”的縮寫，含義為“最大化”； “ .”是“ subject to”的縮寫，表示“滿足于 ……”。 可設(shè)： x1為每周門的產(chǎn)量 （ 扇 ） ； x2為每周窗的產(chǎn)量 （ 扇 ） 。 （ 3） 約束條件 是指實(shí)現(xiàn)問(wèn)題目標(biāo)的 限制因素 。 ?實(shí)際上 ， 所有的線性規(guī)劃問(wèn)題都包含這三個(gè)因素： （ 1） 決策變量 是問(wèn)題中有待確定的 未知 因素 。已知每扇門的利潤(rùn)為 300元 ， 每扇窗的利潤(rùn)為 500元 。 Bx Nx RHS Z Bx 0 ??? ? NB cNBc 1 bBcB 1?? I NB 1? bB 1? 當(dāng)只改變一個(gè)分量ssbb ?? 時(shí)： 11111)()(???????????????????sssBbbbbBbBbbbBbBb 其中1?sB 為1?B 的第 s 列。1226..215m i n5321432131jxxxxxxxxxtsxxzj1x 2x 3x 4x 5x 1/2 1 1/4 9/4 31 /4 1/2 1 1/4 1/4 1 2 1/2 3/2 1/4 1/2 由于 2x 為非基變量，所以系數(shù)的改變只影響 2x 的檢驗(yàn)數(shù)， 新的檢驗(yàn)數(shù)為 2/3102/12222 ??????????? cc??。0)( ????njxAc jj ,...,2,1。1226..215m i n32132131jxxxxxxxtsxxj 對(duì) 偶 理 論 定理 若x和 ?分別是原規(guī)劃和對(duì)偶規(guī)劃的可行解，則 x和 ? 分別是原規(guī)劃和對(duì)偶規(guī)劃的最優(yōu)解的 充要條件是bxc ???。0,...,2,1。, . .
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1