单纯形法的步骤.ppt

《单纯形法的步骤.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学既不严峻，也不遥远，她和几乎所有的人类活动有关，还让每个对她感兴趣的人受益。―R.C.Buck数学是理解世界及其发展的一把主要钥匙。―里约热内卢宣言合金工厂的生产规划实际问题1为200kg、200kg和360kg.工厂生产每吨甲种合金某合金工厂生产甲、乙两种合金，生产每吨甲种合金需用A元素20kg、B元素40kg和C元素90kg，而生产每吨乙种合金需用A元素100kg、B元素80kg和C元素60kg.试问：应如何安排生产，才能获得最大利润？由于A、B、C三种元素都是原料市场上紧缺货品,工厂每月所能得到的这些元素的供应量分别利润为30万元，生产每吨乙种合金利润为40万元.数学模型设每月生产甲

2、种合金x1t，乙种合金x2t,x1,x2满足约束条件线性规划问题求最优解利润为u万元,那么u=30x1+40x2求何时有maxu=max(30x1+40x2)二元一次方程a1x1+a2x2=b代表x1x2平面图解法（回到问题1）a1x1+a2x2=ba1x1+a2x2b则代表了以此直线为界的半平面而二元一次不等式a1x1+a2x2b上的一条直线,线性规划的容许集pQROS集.它是一个包含边界的凸多边形OPQRSx1x2这问题中约束条件意味着五个半平面的交x2pQROSx130x1+40x2=u顶点时u再增将使直线离开容许集，则此临界状态直线所对应从图看出最优解应为R点的增减，直线向右上或左

3、下方平移.若直线经过容许集的某的u就是所求的最大值，此顶点的坐标就是问题的最优解将u视作参数，则30x1+40x2=u代表一条直线，随着u最优解在R点,由R是直线40x1+80x2=200与问题的解答图解法的局限画图并不方便，可以不画图而求出容许集所有直线90x1+60x2=360的交点,可得最优解为x1=3.5,x2=0.75,此时有最大值为u=135.说明安排月生产甲、乙种合金分别为3.5t、0.75t，才能获得最大利润135万元.较来求出最优解.但在约束条件多或多变量时，也的顶点，再将目标函数在这些顶点上的值加以比是难以做到的单纯形法的形式)若有最优解，其必定在容许集(在相应的基本思路是

4、：线性规划(通常是求最小值的几何空间中是一个凸多面体)的顶点达到，故从某一个顶点出发，沿着凸多面体的棱向另一顶点迭代，使得目标函数的值下降,经过有限次迭代,将达到最优解点.1.化标准型(1)把问题变为求在约束下的极小,(2)引进新变量,将约束中的不等式化为等式(除了变量xi非负)单纯形法的步骤利用矩阵的初等变换来实现单纯形法x1x2x3x4x5biix3201001002002x440800102002.5x59060001360630400000■从末一行非基变量取正系数最大者x2为新基，由i=bi/(x2的各正系数)，最小者2，该行对应的x3成■作初等变换主元变成1,这列其他系数变成0

5、■选系数线性无关三个变量(x3,x4,x5)为基;用约束条件将目标函数写成仅含非基变量，列表末一行非基，交叉位的系数100称主元;2.单纯形表这样得到的单纯形表(矩阵)为x1x2x3x4x5biix21/511/10000210x4240-4/510405/3x5780-3/501240120/39220-2/300-80是22，x1成新基;■再看i=bi/(x1的正系数）其最小者5/3，所在行■再做初等变换主元变成1，这列其他系数变0■现在x2,x4,x5成为基,这次末一行正系数最大者对应x4成非基,24成为主元初等变换：先选末行xi系数最大的列算θ(最小正)定主元直至末行非基变量系

6、数均负，对应表为x1x2x3x4x5biix20103/160-1/1203/4x1100-1/801/607/2x3001-13/81/255000-3/8-1/6-135这意味着目标函数显然在x4=0,x5=0时，v最小，u最大单纯形法的计算是线性规划算法中极为重要利用Matlablinprog函数的一般语法：[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)其中：f为目标函数（注意是求极小值）A,b为A*x<=b的不等式条件Aeq,beq为Aeq*x=beq的等式条件lb,ub为上下确界x为最优解，fval为目标函数的值以上所有均以矩阵或向量形式表示A=[20

7、100;4080;9060];b=[200,200,360];f=[-30;-40];[x,fval]=linprog(f,A,b,[],[],[0,0])问题1的程序Optimizationterminated.x=3.50000.7500fval=-135.0000甲乙合金生产数目标函数的最小值Matlab不仅有处理线性规划的功能，而且有处理非线性规划的功能（在工具箱optimization