【正文】 55 參數(shù) b的變化分析 ???????????????0,6263m ax21212121xxtxxtxxxxz例 13 分析以下線性規(guī)劃問(wèn)題 ， 當(dāng) t≥0時(shí) ， 其最優(yōu)解的變化范圍 。 其步驟是： 50 第 8節(jié) * 參數(shù)線性規(guī)劃 ? (1) 對(duì)含有某參變量 t的參數(shù)線性規(guī)劃問(wèn)題 。 計(jì)算 min(? 3, ? 4)= ? 4 故 x5為換出變量。檢查 b列的數(shù)字，若都為非負(fù)，檢驗(yàn)數(shù)都為非正，則已得到最優(yōu)解。x,x,xX。 并同時(shí)將決策變量也分為兩部分： 相應(yīng)地可將目標(biāo)函數(shù)系數(shù) C分為兩部分： CB和 CN， 分別對(duì)應(yīng)于基變量 XB和非基變量 XN， 并且記作 C=（ CB, CN） ?????????NBXXX4 線性規(guī)劃問(wèn)題可表示為： )23(0,X)22(BX)12( Czm axBBB????????NNNNBXbNXXCX非負(fù)條件約束條件目標(biāo)函數(shù)將（ 22）式移項(xiàng)及整理后得到： NBNBNBNBXNBCCbBCzNXBbBXNXbBX)(。用這方法可以求得單純形法的基矩陣 B的逆矩陣 B1 19 第 2節(jié) 改進(jìn)單純形法 以例 1為例進(jìn)行計(jì)算。 37 第 6節(jié) 對(duì) 偶單純形法 ? 在單純形表中進(jìn)行迭代時(shí) ， 在 b列中得到的是原問(wèn)題的基可行解 ， 而在檢驗(yàn)數(shù)行得到的是對(duì)偶問(wèn)題的 基解 。 重復(fù)步驟 (1)～ (4)。 ?對(duì)偶單純形法的 主要局限性 ：對(duì)大多數(shù)線性規(guī)劃問(wèn)題，很難找到一個(gè)初始基。 t=9/7為第一臨界點(diǎn)。 21m in xxz ????????????0,3742212121xxxxxx? 作業(yè) 4： 4. 課本 P76. (1)(5) 。 將 c的變化直接反映到最終表 220中，得表 221。 ?(2) 當(dāng) 變量多于約束條件 ，對(duì)這樣的線性規(guī)劃問(wèn)題用對(duì)偶單純形法計(jì)算可以減少計(jì)算工作量，因此 對(duì)變量較少，而約束條件很多的線性規(guī)劃問(wèn)題，可先將它變換成對(duì)偶問(wèn)題 ，然后用對(duì)偶單純形法求解。若存在 αlj＜ 0 (j=1,2,… ， n), 計(jì)算 lkkkljljjjj azcaazc ????????????? 0m i n?40 按 θ規(guī)則所對(duì)應(yīng)的列的非基變量 xk為換入變量，這樣才能保持得到的對(duì)偶問(wèn)題解仍為可行解。規(guī)則求出換出變量，根據(jù)，計(jì)算可得）從（。 ???????????????mmmmmmaaaaaaaaaA??????21222211121113 ?以 a11為主元素 , 進(jìn)行變換 )1(///11111121111112111???????????????????????????????aaaaaaaaPmm???主元素14 ?然后 構(gòu)造 含有（ 1）列，而其他列都是單位列的矩陣 ?????????????????1/1/00/11111121111aaaaaEm???15 ?可得到 ??????????????????????????????)(mm)(m)(m)()(m)(aaaaaaAE。1111???????????目標(biāo)函數(shù)：5 令非基變量 =0，由上式得到： bB。x,xX。若檢查 b列的數(shù)字時(shí)，至少還有一個(gè)負(fù)分量，檢驗(yàn)數(shù)保持非正，那么進(jìn)行以下計(jì)算。換入、換出變量的所在列、行的交叉處“ ?2”為主元素。 若在 b列首先出現(xiàn)某負(fù)值時(shí) ， 則以它對(duì)應(yīng)的變量為換出變量；于是用對(duì)偶單純形法迭代一步 。 將此計(jì)算結(jié)果反映到最終表 224，得表 225。當(dāng) t＞ 5時(shí)， σ5＞ 0，這時(shí) x5作為換入變量，用單純形法迭代一步，得表 223。 即把某一參數(shù)作為參變量 ， 而目標(biāo)函數(shù)在某區(qū)間內(nèi)是這個(gè)參變量的線性函數(shù) ，含這個(gè)參變量的約束條件是線性等式或不等式 。 若所有α lj≥ 0，則無(wú)可行解 ，停止 計(jì)算。 因 b列數(shù)字為負(fù)，故需進(jìn)行迭代運(yùn)算。計(jì)算： ? ??243 P,P,P?????????? ???????????? ??????????????410121141021402112//E//P ；構(gòu)造主元素??????????? ?????????????????????? ??? ??4/1012/111114/1012/1110111 BEB23 （ 5）計(jì)算非基變量的系數(shù)矩陣 （ 6）計(jì)算 RHS ?????????? ?????????????????????? ???????????????410214114141012111411111////NBN??????????????????????????