數(shù)據(jù)模型——線性規(guī)劃-在線瀏覽
2024-09-11 16:51本頁(yè)面
【正文】 ????????????????取值無(wú)約束321321321321,0,0632442392..xxxxxxxxxxxxts1 2 3 3 41 2 3 3 51 2 3 31 2 3 3 4 62 2 93 2 2 4..4 2 3 3 6, , , , , 0x x x x xx x x x xstx x x xx x x x x x? ? ???? ? ? ? ??? ? ???? ? ? ? ???? ???? ? ? ???? ??? ???線性規(guī)劃及單純形法 ?線性規(guī)劃問(wèn)題及數(shù)學(xué)模型 ?圖解法 ?單純形法原理 ?單純形法計(jì)算步驟 ?單純形法進(jìn)一步討論 ?其他應(yīng)用例子 圖解法 線性規(guī)劃的圖解法就是用幾何作圖的方法分析并求出其最優(yōu)解的過(guò)程 。 圖解法 例 1 運(yùn)用圖解法，以求出 最優(yōu) 生產(chǎn)計(jì)劃（ 最優(yōu)解 ）。 ， 標(biāo)出 坐標(biāo)原點(diǎn) , 坐標(biāo)軸的指向 和 單位長(zhǎng)度 。 。 圖 解 法 () ???????????????????0,52426155..2m ax212121221xxxxxxxtsxxz() () () 圖解法 (a)可行域有界 (b)可行域有界 (c)可行域無(wú)界 唯一最優(yōu)解 多個(gè)最優(yōu)解 唯一最優(yōu)解 (d)可行域無(wú)界 (e)可行域無(wú)界 (f)可行域?yàn)榭占? 多個(gè)最優(yōu)解 目標(biāo)函數(shù)無(wú)界 無(wú)可行解 線性規(guī)劃及單純形法 ?線性規(guī)劃問(wèn)題及數(shù)學(xué)模型 ?圖解法 ?單純形法原理 ?單純形法計(jì)算步驟 ?單純形法進(jìn)一步討論 ?數(shù)據(jù)包絡(luò)分析 ?其他應(yīng)用例子 單純形法原理 ? 線性規(guī)劃問(wèn)題的解的概念 ? 凸集及其頂點(diǎn) ? 幾個(gè)基本定理 解 的 概 念 可行解 ： 變量滿足所有約束條件的一組值 可行解集 ： 所有可行解構(gòu)成的集合 可行域 ： 可行解集構(gòu)成 n維空間的區(qū)域 ?????0xbAX}0{ ??? xb,Ax|xD??????????????）（ njxmibxatsxcjnjijijnjjj,2,10), . . ,1(..zm a x 11?線性規(guī)劃問(wèn)題 解的概念 最優(yōu)解： 使得目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解 最優(yōu)值： 最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值 目的： 求最優(yōu)解和最優(yōu)值 求解方法： 單純形法 CXZ ?m a x?????0.. XbAXts解的概念 先研究 AX=b 設(shè) 系數(shù)矩陣 A是 m n矩陣，秩為 m， B是 A中 m m階非奇異子矩陣（即 |B|≠0）， 則稱 B是線性規(guī)劃問(wèn)題的一個(gè) 基 。 退化的基本可行解 ： 基本可行解的非零分量個(gè)數(shù)小于m時(shí)，也就是在基本可行解中一個(gè)或多于一個(gè)的基變量取零值時(shí) 凸 集 及 其 頂 點(diǎn) 基本概念： 凸集 ——設(shè) K是 n維歐氏空間的一個(gè)點(diǎn)集 ，若任意兩點(diǎn) X（ 1） ∈ K， X（ 2） ∈ K的連線上的一切點(diǎn)： αX（ 1） +（ 1α） X（ 2） ∈ K （ 0α1） ， 則稱 K為 凸集 。 凸 集 的 概 念 凸集 凸集 不是凸集 頂點(diǎn) 基 本 定 理 若線性規(guī)劃問(wèn)題有最優(yōu)解，一定存在一個(gè)基可行解（可行域頂點(diǎn)）是最優(yōu)解。 線性規(guī)劃問(wèn)題的可行解 x＝ (x1, x2,…, xn)為基可行解的充要條件是 x的正分量所對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的。 幾個(gè)事實(shí) 1 ． 基本可行解不一定都是最優(yōu)解， 最優(yōu)解也不一定都是基本解 2 ． 如果有兩個(gè)基本可行解是最優(yōu)解， 則兩解的凸組合也都是最優(yōu)解。 4 ． 行解個(gè)數(shù)有限，可以在基可行解中尋找最優(yōu)解。 線性規(guī)劃及單純形法 ?線性規(guī)劃問(wèn)題及數(shù)學(xué)模型 ?圖解法 ?單純形法原理 ?單純形法計(jì)算步驟 ?單純形法進(jìn)一步討論 ?數(shù)據(jù)包絡(luò)分析 ?其他應(yīng)用例子 單 純 形 算 法 ? 理論方法 ? 算法步驟 ? 單純形表 ? 算例 基 本 可 行 解 定 義 令 ),( NBA ? ， x = ( Bx , Nx ) 。當(dāng) 01 ?? bB 則稱基本解為 基本可行解 ，這時(shí)對(duì)應(yīng)的基陣 B 為 可行基 。 理 論 方 法 定理 （ 最優(yōu)性準(zhǔn)則 ）如果0??，則基可行解 x 為原問(wèn)題的最優(yōu)解。 定理 對(duì)于非退化的基本可行解 x ，若向量?的第 k 個(gè)分量0?k?，而向量.1 kAB ?至少有一個(gè)正分量，則可以找到一個(gè)新的基本可行解 x? 使得 xcxc ?? ?? 。052222..m i n52142132121jxxxxxxxxxxtsxxzj 系數(shù)矩陣 ??????????????100110102100112A 基陣為 ?????????? ??1000100011B ???????????1010110022B 對(duì)應(yīng)的基解分別為 ?? )5,2,2,0,0(1x 和 ??? )6,3,0,0,1(2x， 其中 x1 為基本可行解， x2 不是基本可行解。 rkrjrjaaa /? ?， rkrrabb /??，rkiikiiababb /???。把 Z 看成變量在 單純形表中加上一列，同時(shí)加上一行描述方程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 當(dāng)進(jìn)行轉(zhuǎn)換時(shí)只需要把k?轉(zhuǎn)換成 0 對(duì)應(yīng)其它位置等價(jià)變換即可。 算 例 例 2 . 3 . 1 求解問(wèn)題 ?????????????????????5, . . . ,2,1。計(jì)算 1},m i n {1211??? ，所以取第二個(gè)約束對(duì)應(yīng)的基變量4x 為出基變量，就可以得到一個(gè)新的基可行解，在上表中把 2x 對(duì)應(yīng)的列變成單位向量，系數(shù)矩陣第 2 行對(duì)應(yīng)的元素為 1 ，則可以得到該基可行解的單純形表 1x 2x 3x 4x 5x 0 1
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1