[数学]线性规划
数学建模基本内容： 线性规划 非线性规划 图论及其应用 方程规划 资源分配、安排达到利润最大化问题 资源运输问题 煤、矿产、生活物资运输最短路问题 选址问题:在 n 个居民点v1, v2, , vn中 设置一银行.问设在哪个点,可使最大服 务距离最小? 若设两个银行,问设在哪两 个点?最小覆盖 系统监控模型:居民区如图所示,ei为街道 ,vi为交叉路口,计划在交叉路口安置消防 设施,只有与路口相邻的街道才能使用它 们.为使街道必要时都有消防设施使用, 在那些路口安置设施最节约?如图6个城镇v1 v2v6建立通 信系统,从中选几座城镇建中 心台站,要求它们与各城镇相邻 ,为减少造价使中心台站数目最 少.请提供建立方案.若在造价 最低的条件下,建两套通信中心 ,以备出故障时启用另一套请提 供建立方案.v6v2v1v3v4v5二部图的匹配 n个人x1, x2, , xn安排n项工作y1, y2, , yn. n个人中每个人能胜任若干项工作, 但并不是所 有人员都能从事任何一项工作. 比如x1能做y1, y2工作, x2能做y2, y3, y4工作等. 这样便提出一个问题, 对所有人能不能都 分配一件他能胜任的工作？ 研究生录取研究生录取中的最佳匹配问题褚瑞 晏小波 张雄明(国防科技大学) 某学校系计划招收10名考生，初试上线的前15名考生参加复 试，8位专家组成专家组。复试中，每位专家对每个复试考生个 方面各给一个等级评分，从高到低共分A,B,C,D四个等级，并将其 填入面试表内。该系四个研究方向的10名导师拟招收考生。导师的研究方向、 专业学术水平(发表论文数、论文检索数、编(译)著作数、科研项 目数)，以及对考生的期望要求见表(9)。导师和考生的基本情况都 公开。要解决的问题是： (1) 首先，综合考虑考生初试、复试成绩等因素，帮助确定 10名考生的录取名单。然后，被录取的考生与导师双向选择， 即考生报个志愿，根据导师基本情况和导师对考生的期望要 求选择导师；导师根据考生志愿、专家组对考生评价和自己对 考生的期望要求等选择考生。给出10名考生和导师间的最佳双 向选择方案(不要求一名导师只带一名考生)，使师生双方满意 度最大。(2) 根据已录取10名考生的志愿，每一位导师只带一名 考生，给出师生双向选择的最佳方案，使得师生双方尽量都满 意。(4) 学校充分考虑考生的志愿。要求根据10名导师和15名 考生综合情况选择5名导师招收考生，再让5名导师在15名考生中择 优录取10名考生。给出导师和考生的选择方案，以及每名导师带 名考生的双向选择最佳策略。(5) 请设计一种更能体现“双向选择”的考生录取方案，提 供给主管部门参考，并说明方案的优越性。 (3) 若由十位导师根据初试成绩及专家组评价和他们自己 对考生要求录取10名考生的录取方案是什么？为简化问题，假设无 申报专业志愿，给出10名考生各申报一名导师的策略和导师各选择 一名考生的策略。相互选中即确定；对剩下的导师和考生，再按上 述办法进行双向选择，直至定出每名导师带一考生的方案，使师生 都尽量满意。线性规划:内容:2、掌握用数学软件包求解线性规划问题。1、了解线性规划的基本内容。2、线性规划的基本算法。3、用数学软件包求解线性规划问题。1、两个引例。4、建模案例：投资的收益与风险问题一 ： 任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？两个引例解 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3， 在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立 以下线性规划模型：解答问题二： 某厂每日8小时的产量不低于1800件。为了进行质 量控制，计划聘请两种不同水平的检验员。一级检验员的标准 为：速度25件/小时，正确率98%，计时工资4元/小时；二级检 验员的标准为：速度15小时/件，正确率95%，计时工资3元/小 时。检验员每错检一次，工厂要损失2元。为使总检验费用最 省，该工厂应聘一级、二级检验员各几名？解 设需要一级和二级检验员的人数分别为x1、x2人, 则应付检验员的工资为：因检验员错检而造成的损失为：故目标函数为：约束条件为：线性规划模型：解答返 回1.线性规划的标准形式：用单纯法求解时，常将标准形式化为 ：2. 线性规划的基本算法单纯形法线性规划的基本算法单纯形法引入松弛变量x3, x4, x5, 将不等式化为等式, 即单纯形标准形:显然A的秩ran(A)=3, 任取3个线性无关的列向量,如P3 P4 P5称为 一组基, 记为B. 其余列向量称为非基, 记为N .A、用MATLAB优化工具箱解线性规划min z=cX 1、模型：命令：x=linprog（c，A，b） 2、模型：min z=cX 命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式： 存在，则令A= ，b= .3、模型：min z=cX VLBXVUB 命令：1 x=linprog（c，A，b，Aeq,beq, VLB，VUB）2 x=linprog（c，A，b，Aeq,beq, VLB，VUB, X0） 注意：1 若没有等式约束: , 则令Aeq= , beq= .2其中X0表示初始点 4、命令：x,fval=linprog()返回最优解及处的目标函数值fval.解 编写M文件xxgh1.m如下：c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6;A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08;b=850;700;100;900;Aeq=; beq=;vlb=0;0;0;0;0;0; vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub) To Matlab (xxgh1)解: 编写M文件xxgh2.m如下：c=6 3 4;A=0 1 0;b=50;Aeq=1 1 1;beq=120;vlb=30,0,20;vub=; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)To Matlab (xxgh2)S.t.改写为：例3 问题一的解答问题编写M文件xxgh3.m如下:f = 13 9 10 11 12 8; A = 0.4 1.1 1 0 0 00 0 0 0.5 1.2 1.3; b = 800; 900; Aeq=1 0 0 1 0 00 1 0 0 1 00 0 1 0 0 1; beq=400 600 500; vlb = zeros(6,1); vub=; x,fval = linprog(f,A,b,Aeq,beq,vlb,vub)To Matlab (xxgh3)结果:x =0.0000600.00000.0000400.00000.0000500.0000fval =1.3800e+004即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800。例2 问题二的解答问题改写为：编写M文件xxgh4.m如下：c = 40;36; A=-5 -3; b=-45; Aeq=; beq=; vlb = zeros(2,1); vub=9;15; %调用linprog函数： x,fval = linprog(c,A,b,Aeq,beq,vlb,vub)To Matlab (xxgh4)结果为： x =9.00000.0000 fval =360即只需聘用9个一级检验员。注：本问题应还有一个约束条件：x1、x2取整数。故它 是一个整数线性规划问题。这里把它当成一个线性规划来 解，求得其最优解刚好是整数：x1=9，x2=0，故它就是该 整数规划的最优解。若用线性规划解法求得的最优解不是 整数，将其取整后不一定是相应整数规划的最优解，这样 的整数规划应用专门的方法求解。返 回投资的收益和风险二、基本假设和符号规定三、模型的建立与分析 1.总体风险用所投资的Si中最大的一个风险来衡量,即max qixi|i=1，2,n4. 模型简化：三、模型的建立与分析4. 模型简化：三、模型的建立与分析4. 模型简化：三、模型的建立与分析4. 模型简化：四、模型1的求解 由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资 者有不同的风险度。我们从a=0开始，以步长a=0.001进行循环搜索，编 制程序如下：a=0; while(1.1-a)>1c=-0.05 -0.27 -0.19 -0.185 -0.185;Aeq=1 1.01 1.02 1.045 1.065; beq=1;A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026;b=a;a;a;a;vlb=0,0,0,0,0;vub=;x,val=linprog(c,A,b,Aeq,beq,vlb,vub);ax=x'Q=-valplot(a,Q,'.')，axis(0 0.1 0 0.5)，hold ona=a+0.001; end xlabel('a'),ylabel('Q')To Matlab（xxgh5）计算结果：五、 结果分析4.在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是a*=0.6%，Q*=20% ，所对应投资方案为:风险度 收益 x0 x1 x2 x3 x40.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212 3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。2.当投资越分散时，投资者承担的风险越小，这与题意一致。即: 冒险的投资者会出现集中投资的情况，保守的投资者，则尽量分散投资。1.风险大，收益也大。B、用Lindo软件解线性规划优化建模与LINDO/LINGO软件谢金星 薛毅 编著清华大学出版社,2005年7月美国芝加哥(Chicago)大学的Linus Schrage教授于1980 年前后开发, 后来成立 LINDO系统公司（LINDO Systems Inc.）， 网址：http:/www.lindo.com 企业生产计划奶制品的生产与销售 空间层次工厂级：根据外部需求和内部设备、人力、原料等 条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费 用参数等，以最小成本为目标制订生产批量计划。时间层次若短时间内外部需求和内部资源等不随时间变化，可 制订单阶段生产计划，否则应制订多阶段生产计划。本节课题例1 加工奶制品的
