最优化设计单纯形法VIP免费

单纯形法单纯形法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请老师、同学批评指正请老师、同学批评指正！！谢谢谢谢！！