单纯形法的步骤

数学既不严峻，也不遥远，她和几乎所有的人类活动有关，还让每个对她感兴趣的人受益。―R.C.Buck数学是理解世界及其发展的一把主要钥匙。―里约热内卢宣言上海交通大学数学科学学院数学实验合金工厂的生产规划实际问题1为200kg、200kg和360kg.工厂生产每吨甲种合金某合金工厂生产甲、乙两种合金，生产每吨甲种合金需用A元素20kg、B元素40kg和C元素90kg，而生产每吨乙种合金需用A元素100kg、B元素80kg和C元素60kg.试问：应如何安排生产，才能获得最大利润？由于A、B、C三种元素都是原料市场上紧缺货品,工厂每月所能得到的这些元素的供应量分别利润为30万元，生产每吨乙种合金利润为40万元.数学模型设每月生产甲种合金x1t，乙种合金x2t,x1,x2满足约束条件0,0360609020080402001002021212121xxxxxxxx线性规划问题求最优解利润为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点的增减，直线向右上或左下方平移.若直线经过容许集的某的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万元.较来求出最优解.但在约束条件多或多变量时，也的顶点，再将目标函数在这些顶点上的值加以比是难以做到的单纯形法的形式)若有最优解，其必定在容许集(在相应的基本思路是：线性规划(通常是求最小值的几何空间中是一个凸多面体)的顶点达到，故从某一个顶点出发，沿着凸多面体的棱向另一顶点迭代，使得目标函数的值下降,经过有限次迭代,将达到最优解点.1.化标准型(1)把问题变为求在约束下的极小,(2)引进新变量,543,,xxxuv，增加)0004030(minmin54321xxxxxv求将约束中的不等式化为等式(除了变量xi非负)5,4,3,2,1,03606090200804020010020521421321ixxxxxxxxxxi约束条件单纯形法的步骤利用矩阵的初等变换来实现单纯形法x1x2x3x4x5biix3201001002002x440800102002.5x59060001360630400000■从末一行非基变量取正系数最大者x2为新基，由i=bi/(x2的各正系数)，最小者2，该行对应的x3成■作初等变换主元变成1,这列其他系数变成0■选系数线性无关三个变量(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成为主元00004030360100609020001080402000011002080005202224010530784001540242001001151/////3350012113100110141320035024130101350120160110//////////初等变换：先选末行xi系数最大的列算θ(最小正)定主元135618300055218131002760180100140312011603010//////////直至末行非基变量系数均负，对应表为x1x2x3x4x5biix20103/160-1/1203/4x1100-1/801/607/2x3001-13/81/255000-3/8-1/6-135这意味着目标函数)6183(13554xxv显然在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=[20100;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不仅有处理线性规划的功能，而且有处理非线性规划的功能（在工具箱optimizationtoolbox）。关于线性规划的数学软件当变量和约束条件个数增加时（数百甚至数千个是“小规模”的，往往是几万或几十万个），需要更有效的软件。SoPlex,PCL为免费软件Karmarker算法（Bell实验室）收费某人有100万资金打算投资债券，现有三类债实际问题2－投资决策券：债券A,一年期,年利率6%；债券B，二年期，年利率6.5%；债券C，三年期，年利率7.5%；债券A和B长期有售，但债券C隔年发售(现有售)且投资者对债券C每次投资不超过30万.问他应该如何作连续投资使得在第五年末取得最大收益?建立模型设投资者在第i年投资于A、B、C债券的数额依次为xi1,xi2,xi3(万)，那么问题即求)2251131061max(max334251x.x.x.u约束条件：3,2,1;5432130001310610225113106101310610061100351324142411322313332311221222111131211j,,,,i,x,xxx.x.xxx.x.x.xxxx.x.xxx.xxxiij改写目标)225.113.106.1min(min334251xxxv利用MATLABf=zeros(1,11);f([8,10,11])=-[1.225;1.13;1.06];A=[-1.060011000000;0-1.130-1.060111000;00-1.2250-1.13-1.0600110;000000-1.130-1.0601];b=zeros(4,1);Aeq=[11100000000];beq=100;lb=zeros(11,1);ub=inf*ones(11,1);ub([3,8])=[30;30];[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)Optimizationterminated.x=15.147554.852530.00000.000016.056314.452017.531430.00000.000070.212819.8104fval=-137.0895ABC第一年投资AB第二年投资ABC第三年投资AB第四年投资A第五年投资最大收益(符号相反)要求整数条件的例子某汽车厂生产小中大三类型的汽车，各类型每辆车对钢材、劳动时间的需求，利润及每月工厂钢材、劳动时间的现有量如下表小型中型大型现有量钢材（吨）1.535600劳动时间（小时）28025040060000利润（万元）234试制定月生产计划，使工厂的利润最大.123234Maxzxxx模型与求解123123123.:1.53560028025040060000,,0stxxxxxxxxx用Matlab求解可得到最优解12364.516129,167.741928,0xxx问题出现小数，显然不符合实际在附近整数试探(注意符合条件)约束增加整数条件(整数规划，lingo)x1=64或65,x2=167或168数学规划是运筹学和管理科学中应用极广泛的分支，在多数情况下，数学规划的使用如此成功以致它超出运筹学的范畴，成为人们日常的规划工具。关于数学规划数学规划包括线性规划，非线性规划，整数规划，几何规划和多目标规划等，每个规划包含无数的实例，由于计算量的巨大，算法问题是极为重要的。实验任务本次任务选做教材中所附任务必做题：1、4、5、7，其它可选做上海交通大学数学科学学院数学实验谢谢各位！