单纯形法表的解题步骤

《单纯形法表的解题步骤》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、MadeByHaoweiSong单纯形法表的解题步骤单纯形法表结构如下：c→对应变量的价值系数jθiCBXbbx1x2x3?xj基变量的θ规则基变量资源列价值系数求的值σ检验数j①一般形式若线性规划问题标准形式如下：maxzxxxxx=++++2300012345⎧xxx++=28123⎪⎪41xx+=614⎨41xx+=2⎪25⎪xj≥=0,1,2,?5⎩j取松弛变量x,,xx为基变量，它对应的单位矩阵为基。这样就得到初始可345()0T行基解：X=()0,0,8,16,12。将有关数字填入表中，得到初始单

2、纯形表，如表1-1所示：()0T表1-1X=()0,0,8,16,12c→23000jθiCXbxxxxxBb123450x381210040x41640010-MadeByHaoweiSong0x5120[4]0013σ23000j若检验数均未达到小于等于0，则对上表进行调整。选择上表中检验数最大的列，该列对应的非变量为入基变量；再应用θ规则该列对应的各基变量对应的θ值，选出其中最小的一行，该行对应的基变量为出基变量。修改单纯形表，对各行进行初等变换，确保基变量组成的矩阵为单为矩阵。修改后的单纯形表如表1-

3、2所示：()1T表1-2X=()0,3,2,16,0c→23000jθiCXbxxxxxBb1234510x32[1]010−220x41640010413x230100-43σj2100−4检验数σ,0σ>，则进行继续调整，调整后的单纯形法表如表1-3所示：12()2T表1-3X=()2,3,0,8,0c→23000jθiCXbxxxxxBb1234512x121010−-20x4800-41[2]413x2301001241σj00-204MadeByHaoweiSong表1-3中，σ>0，则继续进行调整

4、，调整结果如表1-4所示：5()3T表1-4X=()4,2,0,0,4c→23000jθiCXbxxxxxBb1234512x141000410x5400-212113x2201−02831σj-20−−028检验数σ≤0，这表示目标函数值已不可能再增大，于是得到最优解：j*()3TXX==()4,2,0,0,4*z=14②带人工变量现有线性规划问题：minzxxx=−3++123⎧xxx−+≤211123⎪⎪−++≥42xxx3123⎨−+=21xx⎪13⎪xxx,,0≥⎩123将上述线性规划问题用大M法求

5、解，在约束条件中加入松弛变量x，剩余4变量x，人工变量x，x得到：567minz=−3x+x+x+0x+0x+Mx+Mx1234567⎧xxxx−++=2111234⎪⎪−++−+=42xxxxx312356⎨−++=21xxx⎪137⎪xj≥=0,1,2,?,7⎩jMadeByHaoweiSong其中，M是一个任意大的正数。用单纯形法表进行计算，由于是求MIN，所以用所有σ≥0来判别目标函数是否实现了最小化。初始单纯行表如表2-1所j示：c→-31100MMjθiCXbxxxxxxxBb12345670x4

6、111-211000113Mx63-4120-1102Mx71-20[1]00011σ-3+6M1-M1-3M0M00jc→-31100MMjθiCXbxxxxxxxBb12345670x4103-20100-1-Mx610[1]00-11-211x31-2010001-σ-11-M00M03M-1jc→-31100MMjθiCXbxxxxxxxBb12345670x412[3]001-22-541x210100-11-2-1x31-2010001-σ-10001M-1M+1jMadeByHaoweiSong

7、c→-31100MMjθiCXbxxxxxxxBb12345671225-3x14100−−33331x210100-11-224471x39001−−33331112σj000M-M-3333上表中得到最优解，xxxxxxxz========4,1,9,0,−21234567③两阶段法（含有人工变量的线性规划问题）下面介绍求解加入人工变量的线性规划问题的两阶段法。第一阶段：不考虑原问题是否存在基可行解，给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。如minω=+++++x??x

8、xx00nn++11mn⎧ax1++?axx+=b111nnn+11⎪ax++?axx+=b⎪2112nnn+22⎪⎨?⎪ax++?axx+=b⎪mm11nnn+mm⎪⎩xx,,,?x≥012nm+然后用单纯形法求解上述模型，若得到ω=0,这说明原问题存在基可行解，可以进行第二阶段计算。否则原问题无可行解，应停止计算。第二阶段：将第一阶段计算得到的最终表，除去人工变量。将目标函数行的系数，换成原问题