数学实验第五次讲稿

数学实验第五讲

————线性规划2023/2/3122023/2/31．理解优化模型的三个要素:决策变量，目标函数和约束条件；２．掌握用MATLAB优化工具箱求解线性规划的方法；３．体验由实际问题建立线性规划模型的全过程。实验目的一,优化问题的普遍性以及引例1，无处不在的优化每一个人，高致总统首相，总裁经理，平民百姓，无不在做决策：该做什么，该怎么做，才能有最好的效果?甚至自然中的动植物，也时刻面临这样的问题.类似的问题，还广泛的存在于无机世界中.2023/2/33一,优化问题的普遍性以及引例看看下面的例子分别属于哪一类？a)证券的投资组合；b)国家经济发展战略；c)产品规格、性能设计；d)球形的水滴；e)狼群的集体捕食；f)好的购物方案；g)物质分子结构；

h)生物的身体构造；i)乘务组排班表;j)光传播路径:直线,反射,折射课堂作业：和你的同桌讨论还有什么方面需要优化的。2023/2/34一,优化问题的普遍性以及引例2,一些成功的优化例子：“最优人员安排”为美国航空每年节约两千万美元.

“改进的出货流程”每年为YellowFreight公司节约一千七百多万美元.“改进的卡车分派”为

Reynolds公司每年节约七百万美元.最优全局供应链为数字设备行业节约超过三亿美元.重建的

NorthAmericaOperations,ProctorandGamble减少20%的工厂,每年节约两亿美元.大阪的Hanshin高速的最优安排每年节约一千七百万人小时.2023/2/35

为说明最优化的价值,建立了专门的网站,列举了哪些公司的什么问题,运用最优化方法节约和增加了多少金额.

有可选的行业,考察的方面,受益的方式,希望同学们各选择其中的一个,提一份报告,以说明最优化的价值.2023/2/36一,优化问题的普遍性以及引例Google上相关搜索的结果：Searchphrasenumberofhits（英文）短语点击数（中文）“optimizethesupplychain”1,160,000优化供应链414,000“optimize(the)return”2,490,000优化回报453,000“optimalexperience”32,400,000最优经历“optimalinvestment”8,320,000优化投资8,250,000“optimalsystem”84,200,000优化系统13,800,000“optimaldecision”28,800,000最优决策2,890,000“optimizeyourPC”3,300,000优化你的PC“optimalchoice”25,800,000最优选择10,900,000“optimaldesign”77,300,000优化设计1,270,000“optimalhealth”31,900,000优化健康还有如:优化产业结构2,830,000优化人员结构3,110,000同学们有没有发现,英文和中文短语间有很大的不同,原因可能是什么?2023/2/37一,优化问题的普遍性以及引例3,相关的几句格言：Wasteneithertimenormoney,butmakethebestuseofboth.--BenjaminFranklinObviously,thehighesttypeofefficiencyisthatwhichcanutilizeexistingmaterialtothebestadvantage.--JawaharlalNehruItismoreprobablethattheaveragemancould,withnoinjurytohishealth,increasehisefficiencyfiftypercent.--WalterScott请同学翻译上面的句子，你喜欢那一句？你有什么好的表述？2023/2/38引例1,动物饲料配置问题

美国一家公司以专门饲养并出售一种实验用的动物而闻名。这种动物的生长对饲料中的三种营养成分特别敏感，即蛋白质、矿物质和维生素。需要的营养量蛋白质：70克矿物质：3克维生素：9.1毫克

现有五种饲料，公司希望找出满足动物营养需要使成本达到最低的混合饲料配置。2023/2/39饲料蛋白质(克)矿物质(克)维生素(毫克)1(x1)2(x2)3(x3)4(x4)5(x5)需要量0.302.001.000.601.80700.100.050.020.200.0530.050.100.020.200.089.1每一种饲料每磅所含的营养成分每种饲料每磅的成本饲料12345成本(美元)0.020.070.040.030.052023/2/310引例2:供应与选址

某公司有6个建筑工地要开工，每个工地的位置（用平面坐标a，b表示，距离单位：千米）及水泥日用量d吨由下表给出。目前有两个临时料场位于A(5,1),B(2,7)，日储量各有20吨。假设从料场到工地均有直线道路相连，（1）试制定每天的供应计划，即从A、B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。a1.258.750.55.7537.25b1.250.754.7556.57.75d35476112023/2/311二,优化问题建模的基本步骤介绍

在我们的生活中,始终有这样的问题:为了一定的目的做一些事情,我们可能要考虑有哪些重要的因素,这些因素和要完成的目标之间有什么样的关系.也就是说,我们在做一个决定时,会注意下面的三个要点:目的是什么?有哪些重要的因素?这些因素和你的目标之间有什么样的关系?2023/2/312二，优化问题的表述目标函数对应决策者而言,对其有利的程度必须定量的测度,在商业应用中，有效性的测度经常是利润或者成本,但对于政府，更经常的使用投入产出率来测度.

表示有效性测度的经常称为目标函数.目标函数要表出测度的有效性,必须说明测度和导致测度改变的变量之间的关系.系统变量分为决策变量和参数.决策变量是指能由决策者直接控制的变量.而参数是指不能由决策者决定的量.实际上，数学模型很少有能表达变量和有效性测度之间的精确关系的.实际上，运筹学分析者的任务就是找出对测度有最重要影响的变量然后找出这些变量和测度之间的数学关系.这个数学关系也就是目标函数.2023/2/313二，优化问题的表述决策变量和参数我们称对应决策者可控的量称为决策变量,决策变量的取值确定了系统的最终性能,也是决策者采用决策的依据.在系统中还有一些量,它不能由决策者所控制,而是由系统所处的环境所决定,我们称之为参数.2023/2/314二，优化问题的表述约束条件

约束条件就是决策变量和参数之间的关系.约束集界定决策变量可以取某些值而不能取其他的值.比如对应生产问题,任何活动中,时间和物品不能为负数.当然,也有一些优化问题不带约束条件,我们称之为无约束优化问题.而在实际问题中,决策变量带有约束是普遍的.2023/2/315三,优化问题的分类优化问题的分类可以从几个方面进行:1,从变量取值的连续和离散可以分成:连续优化,离散优化和混合优化2,从问题的线性非线性可以分为:线性规划和非线性规划3,从变量是确定性和随机性可以分为:随机规划和确定性问题.2023/2/316JohnVonNeumann

约翰·冯·诺依曼(1903－1957),美藉匈牙利人.20世纪最杰出的数学家之一,被誉为”计算机之父”,”博弈论之父”.被认为是数学规划的三大创始人之一.以下的三个人物和线性规划的出现有重要的关系.2023/2/317GeorgeB.Dantzig

GeorgeB.Dantzig(1914-2005),美国人,线性规划单纯形法的创始人,被誉为”线性规划之父”.美国科学院三院院士,美国军方数学顾问,教授.并以其名字设立Dantzig奖.数学规划的三大创始人之一.发现算法时非常年轻,以至到日本时,人们以为”线性规划之父”是个老人,而对他无人问津.2023/2/318LeonidVitalyevichKantorovichKantorovich(1912-1986)苏联人,著名数学家和经济学家,教授,年仅18岁获博士学位.因在经济学上提出稀缺资源的最优配置获诺贝尔奖.线性规划对偶理论的提出者,数学规划的三大创始人之一.2023/2/319非线性规划问题在实践中也是及其常见的.标志着这一学科的产生的奠基性工作由美国的数学家Tucker和Kuhn在1952年的一篇文章.该文章给出了非线性规划问题的必要条件和充分条件,后来成为Kuhn-Tucker条件.这为非线性规划问题的求解算法的提出提供了理论基础和算法的基本思路.相关的规划问题,比如多目标规划,决策论等等.2023/2/32021规划模型利润材料工时人力单耗

甲乙丙

x1x2x3限额材料工时工人231321.5325343640利润(元/件)432生产计划问题max目标函数约束条件决策变量x1,x2,x32023/2/322单耗

甲乙丙

x1x2x3限额材料工时工人231321.5325343640利润(元/件)432生产计划问题规划模型利润材料工时人力2023/2/323生产计划问题maxcTxs.t.Ax≤b

x≥0矩阵形式：利润材料工时人力线性规划模型2023/2/324min(max)cTxs.t.Ax≤b,(或Ax

=b)

x≥0(或a≤x≤b)标准形式其中：x∈Rn，A∈Rm×n，b∈Rm，c∈Rn线性规划2023/2/325Ⅰ2X1+X2=40X1+2X2=50

X1

X2abcd可行点可行域凸多面体v内点边界点顶点vB线性规划解的若干概念线性规划模型maxz=5x1+3x2s.t.2x1+x2≤40

x1+2x2≤50x1，x2≥02023/2/326线性规划解的图示线性规划模型maxz=5x1+3x2s.t.2x1+x2≤40

x1+2x2≤50x1，x2≥02X1+X2=40X1+2X2=50

X1

X2a20x1=10,x2=2025问:什么样的问题可以使用图解法?你从图中得到什么启示?P=0P=50P=1102023/2/3求解LP的特殊情形Maxz=3x1+x2s.t.-x1+x2≤2----L1

x1-2x2≤2----L23x1+2x2≤14----L3

x1，x2≥0x1x2L2L1L30x1x2L2L1L30x1x2L2L10x1x2L2L1L30z=c②无最优解①无可行解③最优解不唯一2023/2/327线性规划的基本性质可行域线段组成的凸多边形目标函数等值线为直线最优解凸多边形的某个顶点LP的基本性质：可行域存在时，必是凸多面体；可行解对应于可行域中的点；最优解存在时，必在可行域的顶点取得。LP的通常解法是单纯形法。超平面组成的凸多面体等值线是超平面凸多面体的某个顶点2维n维2023/2/32829

Matlab中求解线性规划的命令为:linprog,解决的线性规划的标准格式为：

mincTx

x∈Rns.t.A·x<=b

Aeq·x=beqVLB≤x≤VUB

其中，A,b,c,x,Aeq,beq,VLB,VUB等均表示矩阵,特别b,c,x,beq,VLB,VUB为列矩阵。

MATLAB软件求解2023/2/330命令linprog的基本调用格式

如果没有等式约束,就在相应位置输入空数组[],不等式约束和上下界也类似.最后的输入项若没有,则可省略.

x=linprog(c,A,b,Aeq,beq,VLB,VUB)等式约束决策变量上下界不等式约束目标函数最优解MATLAB软件求解2023/2/331还可以增加输出

[x,fval,exitflag,output]=linprog(c,A,b,…）最优值>0：收敛=0:到最大迭代次数时都还未收敛<0：infeasible或方法失败迭代次数和算法类型MATLAB软件求解2023/2/332

看一个小例子

程序:c=-[5,3]’;A=[2,1;1,2];b=[40,50]’;L=[0,0];[x,fmin]=linprog(c,A,b,[],[],L);Pmax=-fminx1=x(1),x2=x(2)

输出结果:

Pmax=110,x1=10,x2=20.

模型:

maxP=5X1+3X2s.t.2X1+X2≤40X1+2X2≤50X1≥0,X2≥0

MATLAB软件求解2023/2/3

美国一家公司以专门饲养并出售一种实验用的动物而闻名。这种动物的生长对饲料中的三种营养成分特别敏感，即蛋白质、矿物质和维生素。需要的营养量蛋白质：70克矿物质：3克维生素：9.1毫克

现有五种饲料，公司希望找出满足动物营养需要使成本达到最低的混合饲料配置。鸟类饲养问题2023/2/333饲料蛋白质(克)矿物质(克)维生素(毫克)1(x1)2(x2)3(x3)4(x4)5(x5)需要量0.302.001.000.601.80700.100.050.020.200.0530.050.100.020.200.089.1每一种饲料每磅所含的营养成分每种饲料每磅的成本饲料12345成本(美元)0.020.070.040.030.052023/2/334建立数学模型决策变量：在混合饲料中，每天所需第j种饲料的磅数xj，j=1，2，3，4，5；②约束条件：蛋白质：0.30x1+2x2+x3+0.6x4+1.8x5≥70

矿物质：0.10x1+0.05x2+0.02x3+0.2x4+0.05x5≥3

维生素：0.05x1+0.1x2+0.02x3+0.2x4+0.08x5≥10自然约束条件：xi≥0③确定目标：混合饲料的成本最低

0.02x1+0.07x2+0.04x3+0.03x4+0.05x5→min2023/2/335完整的线性规划模型：min0.02x1+0.07x2+0.04x3+0.03x4+0.05x5s.t.0.30x1+2x2+x3+0.6x4+1.8x5≥700.10x1+0.05x2+0.02x3+0.2x4+0.05x5≥30.05x1+0.1x2+0.02x3+0.2x4+0.08x5≥10

xj≥0j=1,2,3,4,5;mincTxs.t.Ax≥b

x≥0归纳：返回2023/2/336linprogmincTxs.t.Ax≤bAeqx≤beqlb≤x≤ubSolvealinearprogrammingproblemwherec,x,b,beq,lb,andubarevectorsandAandAeqarematrices.调用格式:x=linprog(f,A,b,Aeq,beq)x=linprog(f,A,b,Aeq,beq,lb,ub)x=linprog(f,A,b,Aeq,beq,lb,ub,x0)x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)[x,fval]=linprog(...)[x,fval,exitflag]=linprog(...)[x,fval,exitflag,output]=linprog(...)[x,fval,exitflag,output,lambda]=linprog(...)2023/2/337原油生产计划原油类别买入价(元/桶)买入量(桶/天)辛烷值(%)硫含量(%)A45≤5000120.5B35≤500062.0C25≤500083.0汽油类别卖出价(元/桶)需求量(桶/天)辛烷值(%)硫含量(%)甲703000≥10≤1.0乙602000≥8≤2.0丙501000≥6≤1.01:1加工费:4元/桶能力:<=14000桶/天I:安排生产计划，在满足需求的条件下使利润最大2023/2/338决策变量：目标：甲(3000)乙(2000)丙(1000)A/45X1X2X3B/35X4X5X6C/25X7X8X9约束：总利润最大

需求限制；原料限制；含量限制；非负限制2023/2/339含量限制非负限制原料限制需求限制约束2023/2/340总盈利：126000元c=[45 45 45 35 35 35 25 25 25];a1=[1 0 0 1 0 0 1 0 0;0 1 0 0 1 0 0 1 0;0 0 1 0 0 1 0 0 1];a2=[1 1 1 0 0 0 0 0 0;0 0 0 1 1 1 0 0 0;0 0 0 0 0 0 1 1 1;-12 0 0 -6 0 0 -8 0 0;0 -12 0 0 -6 0 0 -8 0;0 0 -12 0 0 -6 0 0 -8;0.5 0 0 2 0 0 3 0 0;0 0.5 0 0 2 0 0 3 0;0 0 0.5 0 0 2 0 0 3];b1=[30002000 1000];b2=[50005000 5000 -30000 -16000 -6000 3000 4000 1000];v1=zeros(1,9);[xf]=linprog(c,a2,b2,a1,b1,v1)z=356000-f甲(3000)乙(2000)丙(1000)A/452400800800B/35000C/2560012002002023/2/341II:通过广告增加销售(1元广告费：增加10桶销售)决策变量：目标：甲(3000+)乙(2000+)丙(1000+)A/45X1X2X3B/35X4X5X6C/25广告销售X7X103000+10X10X8X112000+10X11X9X121000+10X12约束：总利润最大需求限制；原料限制；产量限制；含量限制；非负限制2023/2/342含量限制非负限制产量限制原料限制需求限制约束2023/2/343总盈利：287750元c=[4949493939392929 29 -699 -599 -499];a1=[10 01 0 0 1 0 0-10 00;01 00 1 0 0 1 00-100;00 10 0 1 0 0 10 0-10];a2=[1 1 1 0 0 0 00000 0;0 0 0 1 1 1 00000 0;0 0 0 0 0 0 11100 0;-12 0 0 -6 0 0 -800100 00;0 -12 0 0 -6 0 0-80 0 800;0