单纯形法表的解题步骤

单纯形法表的解题步骤

ID:6000816

大小:121.55 KB

页数:8页

时间:2017-12-30

单纯形法表的解题步骤_第1页
单纯形法表的解题步骤_第2页
单纯形法表的解题步骤_第3页
单纯形法表的解题步骤_第4页
单纯形法表的解题步骤_第5页
资源描述:

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

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,这说明原问题存在基可行解,可以进行第二阶段计算。否则原问题无可行解,应停止计算。第二阶段:将第一阶段计算得到的最终表,除去人工变量。将目标函数行的系数,换成原问题

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。