【正文】 以系數(shù)的改變只影響 2x 的檢驗(yàn)數(shù)， 新的檢驗(yàn)數(shù)為 2/3102/12222 ??????????? cc??。 （ 3） 約束條件 是指實(shí)現(xiàn)問題目標(biāo)的 限制因素 。 用 Excel“規(guī)劃求解 ” 工具求解線性規(guī)劃問題 線性規(guī)劃結(jié)束！ 。 （ 2） 目標(biāo)函數(shù) 是指對問題所追求的目標(biāo)的數(shù)學(xué)描述 。以此為初始基可行解進(jìn)行迭代就可以求出 新問題的解。 2 . 現(xiàn)在還有待解決的問題是如何給出初始基可行 解以及出現(xiàn)退化的時(shí)候如何處理。 如果 01 ?? bB 則稱該 基可行解為非退化的 ，如果一個(gè)線性規(guī)劃的所有基可行解都是非退化的則稱該 規(guī)劃為非退化的 。 。 租借倉庫的合同每月初都可辦理 ，每份合同具體規(guī)定租用面積和期限 。 z是該公司能獲取的利潤的目標(biāo)值 ，它是變量 x1， x2的函數(shù) ， 稱為 目標(biāo)函數(shù) 。 圖解法 例 1 運(yùn)用圖解法，以求出 最優(yōu) 生產(chǎn)計(jì)劃（ 最優(yōu)解 ）。 4 ． 行解個(gè)數(shù)有限，可以在基可行解中尋找最優(yōu)解。 算 例 例 2 . 3 . 1 求解問題 ?????????????????????5, . . . ,2,1。 定理 線性規(guī)劃的對偶規(guī)劃的對偶規(guī)劃是原始規(guī)劃。 而且根據(jù)經(jīng)市場調(diào)查得到的該兩種新產(chǎn)品的市場需求狀況可以確定 ， 按當(dāng)前的定價(jià)可確保所有新產(chǎn)品均能銷售出去 。因此，上述模型的含義是：在給定的條件限制下，求使得目標(biāo)函數(shù) z達(dá)到最大時(shí) x1， x2的取值。 （ 2） 目標(biāo)函數(shù) 本問題的目標(biāo)是總利潤最大 。 用 Excel“規(guī)劃求解 ” 工具求解線性規(guī)劃問題 線性規(guī)劃問題及其數(shù)學(xué)模型 ?例 1 某工廠要生產(chǎn)兩種新產(chǎn)品： 門 和 窗 。,...,1。 rkrjrjaaa /? ?， rkrrabb /??，rkiikiiababb /???。 線性規(guī)劃問題的可行解 x＝ (x1, x2,…, xn)為基可行解的充要條件是 x的正分量所對應(yīng)的系數(shù)列向量是線性獨(dú)立的。 max（ 或 min） nn xcxcxcZ ???? ??2211? ??????????????????????????????自由,00,),(),(),(..2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats???????概念和模型 一般形式： max（ 或 min） ? ??????????????????????????????自由,00,),(),(),(..2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats???????nn xcxcxcZ ???? ??2211目標(biāo)函數(shù) 約束條件 非負(fù)約束 稱為決策變量 ),2,1( njxj ??稱為價(jià)值系數(shù)或目標(biāo)函數(shù)系數(shù) ),2,1( njcj ??稱為資源常數(shù)或約束右端常數(shù) ),2,1( mibi ??稱為技術(shù)系數(shù)或約束系數(shù) ija 0 ( i = 1 , . . , m 。 已知各制造一件時(shí)分別占用的設(shè)備 A， B的臺時(shí) 、 調(diào)試工序時(shí)間及每天可用于這兩種家電的能力 、 各售出一件時(shí)的獲利情況 ， 如表 11所示 。因 5月份起該公司不需要租借倉庫，故 x24， x33， x34， x42， x43， x44均為零。 凸 集 的 概 念 頂點(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)）。 給定一個(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。, . . . ,2,1。 為了使原最優(yōu)解依然是新問題的最優(yōu)解， 2x 的系數(shù)最小 可以變?yōu)?/122??? c?。 解： 例可用下表 表示 。 所以 ， 一般給跟公式和模型有關(guān)的四類單元格命名 。 ?實(shí)際上 ， 所有的線性規(guī)劃問題都包含這三個(gè)因素： （ 1） 決策變量 是問題中有待確定的 未知 因素 。0)( ????njxAc jj ,...,2,1。計(jì)算21??，所以取第 3 個(gè)約束對應(yīng)的基變量5x為出基變量，就可以得到一個(gè)新的基可行解，在上表中把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 由于檢驗(yàn)數(shù)都小于等于 0 ，所以該基可行解就是最優(yōu)解， 對應(yīng)的最優(yōu)解為)0,0,2/1,2/5,2/13(，最優(yōu)值為 3 / 2 。 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 的 基本解 。 ，找出可行域。 已知各月份所需倉庫面積列于表 12。 由此例 1的數(shù)學(xué)模型可表為： 數(shù)學(xué)模型 () ???????????????????0,52426155..2m ax212121221xxxxxxxtsxxz目標(biāo)函數(shù) 約束條件 () () () max: maximize的縮寫， “ 最大化 ” ， . subject to的縮寫， “ 受限制于 …… ” 問題的提出 例 2 捷運(yùn)公司在下一年度的 1~4月的 4個(gè)月內(nèi)擬租用倉庫堆放物資 。 ， 標(biāo)出 坐標(biāo)原點(diǎn) , 坐標(biāo)軸的指向 和 單位長度 。 線性規(guī)劃及單純形法 ?線性規(guī)劃問題及數(shù)學(xué)模型 ?圖解法 ?單純形法原理 ?單純形法計(jì)算步驟 ?單純形法進(jìn)一步討論 ?數(shù)據(jù)包絡(luò)分析 ?其他應(yīng)用例子 單 純 形 算 法 ? 理論方法 ? 算法步驟 ? 單純形表 ? 算例 基 本 可 行 解 定 義 令 ),( NBA ? ， x = ( Bx , Nx ) 。計(jì)算 1},m i n {1211?