運(yùn)籌學(xué)——3單純形矩陣描述與改進(jìn)單純形法-文庫(kù)吧在線文庫(kù)
【正文】 非基變量的檢驗(yàn)數(shù)，確定換入變量。bBX )(1B11Cz0????????????目標(biāo)函數(shù)的值基可行解6 （ 1）非基變量的系數(shù)表示為： )|(CC),2,1(c)(1Bj1NBBnjzNBCCjBN?????所有檢驗(yàn)數(shù)可表示為：對(duì)應(yīng)已用的檢驗(yàn)數(shù)符號(hào)?7 （ 2）單純形表與矩陣表示的關(guān)系 )72(0101111????????????????????? ????????????bBCbBXXzNBCCNBIBNBBNbBCXNBCCzbBNXBXBNBNNB1111)(。 3 若以 Xs為基變量 ， 并標(biāo)記成 XB， 可將系數(shù)矩陣 （ A， I）分為 （ B， N） 兩塊 。 ?設(shè) m?n系數(shù)矩陣為 A，求其逆矩陣時(shí)，可先從第 1列開(kāi)始。計(jì)算： ? ??243 P,P,P?????????? ???????????? ??????????????410121141021402112//E//P ；構(gòu)造主元素??????????? ?????????????????????? ??? ??4/1012/111114/1012/1110111 BEB23 （ 5）計(jì)算非基變量的系數(shù)矩陣 （ 6）計(jì)算 RHS ?????????? ?????????????????????? ???????????????410214114141012111411111////NBN??????????????????????????????? ???316212168410121111//bB24 第 2節(jié) 改進(jìn)單純形法 第 1步計(jì)算結(jié)束后的結(jié)果 ? ?? ?? ?? ? ? ?),(),(C,CC。確定，從而計(jì)算，）求（。 因 b列數(shù)字為負(fù)，故需進(jìn)行迭代運(yùn)算。若 所有 αlj≥0，則無(wú)可行解 ，停止 計(jì)算。 若所有α lj≥ 0，則無(wú)可行解 ，停止 計(jì)算。 45 c j → 2 3 4 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 3 2 x 2 x 1 2/5 11/5 0 1 1 0 1/5 7/2 2/5 1/5 1/5 2/5 c j z j 0 0 9 /5 8/5 1/5 表 28中 ， b列數(shù)字全為非負(fù) ， 檢驗(yàn)數(shù)全為非正 ， 故問(wèn)題的最優(yōu)解為 X*=(11/5， 2/5， 0， 0， 0)T 若對(duì)應(yīng)兩個(gè)約束條件的對(duì)偶變量分別為 y1和 y2， 則對(duì)偶問(wèn)題的最優(yōu)解為 Y*=(y1*,y2*)=(8/5,1/5) 46 對(duì)偶單純形法有以下優(yōu)點(diǎn)： ?(1) 初始解可以是非可行解 ，當(dāng)檢驗(yàn)數(shù)都為負(fù)數(shù)時(shí)就可以進(jìn)行基的變換，這時(shí) 不需要加入人工變量 ，因此可以簡(jiǎn)化計(jì)算。 即把某一參數(shù)作為參變量 ， 而目標(biāo)函數(shù)在某區(qū)間內(nèi)是這個(gè)參變量的線性函數(shù) ，含這個(gè)參變量的約束條件是線性等式或不等式 。 解： 將此模型化為標(biāo)準(zhǔn)型 ??????????????????????0,18231224)(0)5()23()(ma x54321521423154321xxxxxxxxxxxxxxxxtxttz52 c j → 3 5 0 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 0 5 3 x 3 x 2 x 1 2 6 2 0 0 1 0 1 0 1 0 0 1/3 1/2 – 1/3 1/3 0 1/3 c j z j 0 0 0 3/2 1 令 t=0， 用單純形法求解的結(jié)果 ， 見(jiàn)表 220。當(dāng) t＞ 5時(shí)， σ5＞ 0，這時(shí) x5作為換入變量，用單純形法迭代一步，得表 223。 321 422m i n xxxz ????????????????????無(wú)約束321321321321,0,534332243xxxxxxxxxxxx? ?試用對(duì)偶單純形法求解下列線性規(guī)劃問(wèn)題。 將此計(jì)算結(jié)果反映到最終表 224，得表 225。當(dāng) t＞ 9/7時(shí)， σ4＞0，這時(shí) x4作為換入變量。 若在 b列首先出現(xiàn)某負(fù)值時(shí) ， 則以它對(duì)應(yīng)的變量為換出變量；于是用對(duì)偶單純形法迭代一步 。 slide 58：例題 作業(yè) 3： 1. 課本 P74. (2)、 (3) ? 寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題 。換入、換出變量的所在列、行的交叉處“ ?2”為主元素。 41 ? 例 6 用對(duì)偶單純形法求解 min w=2x1+3x2+4x3 x1+2x2+x3≥3 2x1?x2+3x3≥4 x1， x2， x3≥0 解： 先將此問(wèn)題化成下列形式，以便得到對(duì)偶問(wèn)題的初始基可行解 max z= ? 2x1 ? 3x2 ? 4x3 ? x1 ? 2x2 ? x3+x4 = ? 3
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1