单纯形法单纯形法SimplexMethod最优化设计最优化设计OptimizationDesignOptimizationDesign汕头大学工学院汕头大学工学院COLLEGEOFENGINEERING,STUCOLLEGEOFENGINEERING,STU本节的主要内容：单纯形法及其基本原理单纯形法的计算步骤单纯形表的定义单纯形表的求解步骤单纯形表计算例题演练有志有志有识有识有恒有恒有为有为11..单纯形法及其基本原理：有志有志有识有识有恒有恒有为有为1发现历史美国数学家美国数学家G.B.DantizigG.B.Dantizig19741974年提出年提出22基本思想在可行集的边界上，从一个顶点转移到改善当前目标的相邻顶点上，如此反复，直到需找到最优解33迭代步骤1.确定初始基本可行解2.判断是否为最优解3.从一个基本可行解转转换到相邻且改善的基本可行解单纯形法SimplexMethod单纯形法SimplexMethod22..单纯形法的计算步骤：有志有志有识有识有恒有恒有为有为A=（I，N），B0=I对应的X0σj≤0将σj最大的列向量进行初等变换，使其形成新的基变量33..单纯形表的定义：有志有志有识有识有恒有恒有为有为若线性规划问题为：等式替换表格化33..单纯形表的定义：有志有志有识有识有恒有恒有为有为初等变换单纯形表SimplexTable单纯形表SimplexTableTab.1Tab.2检验数σj44..单纯形表的求解步骤：有志有志有识有识有恒有恒有为有为55..单纯形表计算例题演练：有志有志有识有识有恒有恒有为有为解：原问题已经是标准形式的线性规划，其数据为C=(c1,c2,c3,c4)=(-3,-2,-1,2)b=(b1,b2)T=(4,5)TA=(P1,P2,P3,P4)=P1P355..单纯形表计算例题演练：有志有志有识有识有恒有恒有为有为其中已含有一个标准基：B0=(P1,P3)=I将上述数据填入数据表，可得Tab.3Tab.3Tab.4通过初等变换将基变量所在列的目标行元素化为零，得到初始单纯形表Tab.4检验数中σ4=16>0,且a14，a24>0表明该解不是最优解，但存在最优解θ=min(1,2.5)=1Tab.6Tab.555..单纯形表计算例题演练：有志有志有识有识有恒有恒有为有为选a14为主元，在单纯形表中将主元用括弧括起进行换基迭代，可得新的单纯形表Tab.5检验数中σ2=1>0,且a22>0，故还需继续迭代，以a22为主元迭代得到Tab.6检验数σi≤0,已达到最优解故该LP最优解为：X=(0,3/2,0,7/4)T最优基为：B=(P4,P2)=最大目标函数值为：Z=-(-1/2)=1/255..单纯形表计算例题演练：有志有志有识有识有恒有恒有为有为55..单纯形表计算例题演练：有志有志有识有识有恒有恒有为有为解：将原问题化为标准形式，得人工变量Tab.8其数据表为Tab.7，初始基为B0=（P4，P5）=I55..单纯形表计算例题演练：有志有志有识有识有恒有恒有为有为Tab.7Tab.7已经是单纯形表，既为初始单纯形表，最大检验数σ3=4>0，取a23为主元进行迭代，得到新的单纯形表Tab.8检验数σ1=9≥0,x11，x21<0,故可知该LP问题没有最优解最优化设计最优化设计OptimizationDesignOptimizationDesignEIP-CDIO请老师、同学批评指正请老师、同学批评指正！！谢谢谢谢！！
