1、数学既不严峻，也不遥远，她和几乎所有的人类活动有关，还让每个对她感兴趣的人受益。 R.C.Buck,数学是理解世界及其发展的一把主要钥匙。 里约热内卢宣言,合金工厂的生产规划,实际问题1,为200kg、200kg和360kg. 工厂生产每吨甲种合金,某合金工厂生产甲、乙两种合金，生产每吨,甲种合金需用A元素20 kg、 B元素40kg 和C元素,90 kg，而生产每吨乙种合金需用A元素100 kg、,B元素80 kg和C元素60 kg.,试问：应如何安排生产，才能获得最大利润？,由于A、B、C三种元素都是原料市场上紧缺,货品,工厂每月所能得到的这些元素的供应量分别,利润为30万元，生产每吨乙种
2、合金利润为40万元.,数学模型,设每月生产甲种合金 x1t，乙种合金 x2 t ,x1, x2 满足约束条件,线性规划问题,求最优解,利润为 u万元, 那么,u= 30 x1+40 x2,求何时有,max u= max (30 x1+40 x2),二元一次方程 a1x1+a2x2 =b 代表x1 x2平面,图解法（回到问题1）,a1x1+a2x2 =b,a1 x1+a2 x2 b,则代表了以此直线为界的半平面,而二元一次不等式a1x1+a2x2 b,上的一条直线,线性规划的容许集,p Q R O S,集. 它是一个包含边界的凸多边形 OPQRS,x1,x2,这问题中约束条件意味着五个半平面的交
3、,x2 p Q R O S x1,30x1+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.5 t、
4、0.75t，才能获得最大,利润135万元.,较来求出最优解.但在约束条件多或多变量时，也,的顶点，再将目标函数在这些顶点上的值加以比,是难以做到的,单纯形法,的形式)若有最优解，其必定在容许集(在相应的,基本思路是：线性规划(通常是求最小值的,几何空间中是一个凸多面体)的顶点达到，故,从某一个顶点出发，沿着凸多面体的棱向另一,顶点迭代，使得目标函,数的值下降,经过有限次,迭代,将达到最优解点.,1.化标准型,(1)把问题变为求在约束下的极小,(2)引进新变量,将约束中的不等式化为等式(除了变量xi非负),单纯形法的步骤,利用矩阵的初等变换来实现单纯形法,x1x2x3 x4 x5 bi ix32
5、0100100 2002x44080010 200 2.5 x59060001 360630400000, 从末一行非基变量取正系数最大者x2 为新基，,由i=bi/(x2的各正系数)，最小者2，该行对应的x3 成, 作初等变换主元变成1,这列其他系数变成0, 选系数线性无关三个变量(x3,x4,x5 )为基;,用约束条件将目标函数写成仅含非基变量，列表,末一行,非基，交叉位的系数100 称主元;,2. 单纯形表,这样得到的单纯形表(矩阵)为,x1x2 x3 x4 x5 bi i x2 1/51 1/100 0 0 2 10 x4240 -4/5 1 0 40 5/3 x5780 -3/5 0
6、 1 240 120/39220 -2/3 0 0 -80,是22，x1成新基;, 再看i=bi/(x1的正系数）其最小者5/3，所在行, 再做初等变换主元变成1，这列其他系数变0, 现在x2, x4, x5成为基,这次末一行正系数最大者,对应 x4成非基,24 成为主元,初等变换：先选末行xi系数最大的列 算(最小正) 定主元,直至末行非基变量系数均负，对应表为,x1x2x3 x4 x5 bi i x2 01 0 3/160 -1/1203/4 x110 0 -1/80 1/60 7/2 x300 1 -13/8 1/2 5500 0 -3/8 -1/6 -135,这意味着目标函数,显然在
7、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 100;40 80;90 60;b=200,200,360;f=-30;-40;x,fval=linprog(f,A,b,0,0),问题1的程序,Optimization te
8、rminated.x = 3.5000 0.7500fval = -135.0000,甲乙合金生产数,目标函数的最小值,Matlab不仅有处理线性规划的功能，而且有处理非线性规划的功能（在工具箱optimization toolbox）。,关于线性规划的数学软件,当变量和约束条件个数增加时（数百甚至数千个是“小规模”的，往往是几万或几十万个），需要更有效的软件。,SoPlex, PCL为免费软件,Karmarker算法（Bell实验室） 收费,某人有100万资金打算投资债券，现有三类债,实际问题 2投资决策,券：债券A, 一年期,年利率6%；债券B，二年期，,年利率6.5%；债券C，三年期，年
9、利率7.5%；,债券A和B长期有售，但债券C隔年发售(现有售),且投资者对债券C每次投资不超过30万. 问他应该,如何作连续投资使得在第五年末取得最大收益?,建立模型,设投资者在第i年投资于A、B、C债券的数额依次,为xi1, xi2, xi3 (万)，那么问题即求,约束条件：,改写目标,利用MATLAB,f=zeros(1,11);f(8,10,11)=-1.225;1.13;1.06;A=-1.06 0 0 1 1 0 0 0 0 0 0;0 -1.13 0 -1.06 0 1 1 1 0 0 0; 0 0 -1.225 0 -1.13 -1.06 0 0 1 1 0; 0 0 0 0 0
10、 0 -1.13 0 -1.06 0 1;b=zeros(4,1);Aeq=1 1 1 0 0 0 0 0 0 0 0;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),Optimization terminated.x = 15.1475 54.8525 30.0000 0.0000 16.0563 14.4520 17.5314 30.0000 0.0000 70.2128 19.8104fval = -137.0895,最大收益(符号相反),要求整数条件的例
11、子,某汽车厂生产小中大三类型的汽车，各类型,每辆车对钢材、劳动时间的需求，利润及每月工,厂钢材、劳动时间的现有量如下表,试制定月生产计划，使工厂的利润最大.,模型与求解,用Matlab 求解可得到最优解,问题 出现小数，显然不符合实际, 在附近整数试探 (注意符合条件), 约束增加整数条件( 整数规划，lingo),x1=64或65,x2=167或168,数学规划是运筹学和管理科学中应用极广泛的分支，在多数情况下，数学规划的使用如此成功以致它超出运筹学的范畴，成为人们日常的规划工具。,关于数学规划,数学规划包括线性规划，非线性规划，整数规划，几何规划和多目标规划等，每个规划包含无数的实例，由于计算量的巨大，算法问题是极为重要的。,实验任务,本次任务选做教材中所附任务,必做题：1、4、5、7，其它可选做,谢谢各位！,
