资源描述
第四章第四章 运筹与优化模型运筹与优化模型 4.1 线性规划模型 4.2 非线性规划模型 4.3 动态规划模型 4.4 变分法模型 4.5 层次分析法模型第1页 数学规划第2页规划模型规划模型（1）效益最大化或费用最小化（2）各种条件约束第3页 数学规划许多实际问题都能够归结为以下形式 数学模型：第4页4.1 线性规划模型第5页 例1 某机床厂生产甲、乙两种机床，每台销售后利润分别为4000 元与3000 元。生产甲机床需用A、B 机器加工，加工时间分别为每台2 小时和1 小时；生产乙机床需用A、B、C 三种机器加工，加工时间为每台各一小时。若天天可用于加工机器时数分别为A 机器10 小时、B 机器8 小时和C 机器7 小时，问该厂天天应生产甲、乙机床各几台，才能使总利润最大？线性规划引例线性规划引例第6页 设该厂生产 台甲机床和 台乙机床时总利润最大，则 应满足 （目标函数）(约束条件)数学模型：第7页线性规划线性规划(linear Programming)模型模型目标函数约束条件决议变量第8页 1、相关线性规划问题几个例子 2、线性规划问题标准形式 3、关于整数规划 4、应用本节内容本节内容第9页1.线性规划问题几个例子 某化工厂生产A1，A2，A3，A4四种化工产品，每种产品生产1吨消耗工时、能源和取得利润以下表：产品A1A2A3A4工时(h)10025038075能源(吨标准煤)0.20.30.50.1利润(万元)2581 已知该厂明年工时限额为18480h，能耗限额为100t标准煤，欲使该厂明年总利润最高，请确定各种产品生产数量。第10页模型产品A1A2A3A4生产数量x 1x 2x 3x 4假设：工时限制供煤限制第11页例 某商品有m 个产地、n 个销地，各产地产量分别为 各销地需求量分别为 。若该商品由i 产地运到 j 销地单位运价为 ，问应该怎样调运才能使总运费最省？运输问题(产销平衡)第12页解：引入变量 ，其取值为由i 产地运往 j 销地该商品数量，数学模型为第13页运输问题(产销不平衡)上例中，若产大于销，即 时,运输模型可写为 第14页河流污染与净化问题 某河流边有两个化工厂,流经第一个化工厂河水流量是天天500万立方米,在两个工厂之间有一条流量为天天200万立方米支流.两个化工厂天天排放工业污水分别为2万与1.4万立方米,从第一个化工厂排出污水流到第二个化工厂之前,有20可自然净化.依据环境保护部门要求,河流中工业污水含量应小于0.2.所以两个化工厂都必须各自处理净化一部分污水,已知他们治污成本分别为0.1元和0.08元每立方米。问在满足环境保护要求条件下，两厂各需要处理多少污水，可使两厂总处理污水费用最少。第15页分析:(1)假设第一、二厂天天各自处理x1和x2万立方米污水;(2)依据环境保护部门要求，应有 同时应有 第16页 (3)记 f 为两厂治污总费用,则有从而该问题数学模型为第17页2.线性规划问题标准形式若写成向量和矩阵形式,则有 第18页求解方法：（1）单纯形法 （2）软件求解:Lindo，matlab，Lingo等 其中 注:任何线性规划模型都能够化为标准形式.第19页n实例实例 将以下将以下LP问题化为标准型问题化为标准型:第20页解 令得标准型为得标准型为松弛变量松弛变量剩下变量剩下变量第21页线性规划Matlab 标准形式其中c 和x 为n 维列向量，A、Aeq 为适当维数矩阵，b、beq 为适当维数列向量。第22页Matlabx,fval=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)fval 返回目标函数值，LB 和UB 分别是变量x 下界和上界，x0 是x 初始值，OPTIONS 是控制参数。第23页Matlabn（i）编写M 文件nc=2;3;-5;na=-2,5,-1;1,3,1;b=-10;12;naeq=1,1,1;nbeq=7;nx=linprog(-c,a,b,aeq,beq,zeros(3,1)nvalue=c*x （ii）将M文件存盘，并命名为example1.m。（iii）在Matlab指令窗运行example1即可得所求结果。nx=6.4286 0.5714 0.0000nvalue=14.5714求最大值求最大值第24页 编写Matlab程序以下：nc=2;3;1;na=1,4,2;3,2,0;nb=8;6;nx,y=linprog(c,-a,-b,zeros(3,1)第25页LP问题图解法问题图解法(仅适用二维问题仅适用二维问题)n实例实例 用图解法求解以下LP问题:第26页解:n最优解为(4,4/3)n最优目标值为44/3第27页3.整数规划整数规划(Integer Linear Programming)模型模型第28页 有一个徒步旅行者，其可携带物品重量程度为有一个徒步旅行者，其可携带物品重量程度为a 千克，千克，设有设有n 种物品可供他选择装入包中。已知每种物品重量种物品可供他选择装入包中。已知每种物品重量及价值（元），问此人应怎样选择携带物品（各几件）及价值（元），问此人应怎样选择携带物品（各几件），使所带物品价值最大？，使所带物品价值最大？物品物品 1 2 j n重量（千克/件）a1 a2 aj an每件价值每件价值 c1 c2 cj cn 这就是背包问题。类似还有工厂里下料问题、运输这就是背包问题。类似还有工厂里下料问题、运输中货物装载问题、人造卫星内物品装载问题等。中货物装载问题、人造卫星内物品装载问题等。背包问题背包问题第29页设设xj 为第为第j 种物品装件数（非负整数）则问题数学模型种物品装件数（非负整数）则问题数学模型以下：以下：第30页LP问题问题Lindo输入范例输入范例ST2)3)4)END第31页ST2)3)4)ENDGIN2 (!表示前两个变量为普通整数表示前两个变量为普通整数)ILP问题问题Lindo输入范例之一输入范例之一第32页ST2)3)4)ENDGIN(X1);GIN(X2);ILP问题问题Lingo输入范例输入范例第33页例：运输问题(产销不平衡)设有三个化肥厂供给四个地域农用化肥.各化肥厂产量(单位：万吨),各地域年需求量(单位：万吨)及从各化肥厂到各地域单位运价(单位：万元/万吨)如表所表示，试建立使总运费最省化肥调拨方案.表表4.1.4 地 区化 肥 厂 I II III IV产 量ABC 16 13 22 17 14 13 19 15 19 20 23 +506050最低需求最高需求 30 70 0 10 50 70 30 不限第34页 地 区化 肥 厂 I I II III IV IV产 量ABCD 16 16 13 22 17 17 14 14 13 19 15 15 19 19 20 23 M M M 0 M 0 M 050605050需求 30 20 70 30 10 50 210模型建立与求解 设 表示第i个化肥厂运到各地域满足最低需求部分，表示第i个化肥厂运到各地域满足最高需求部分，则调运方案数学模型为第35页例：综合运输问题0-1规划模型 设某种物质有 m 个产地 第 i 个产地产量为 该物资将销往 n 个销地 第 j 个销地销量为 且有 已知从各个产地运往各销地需经过 p 个中间编组站 转运,若启用第 k 个编组站，不论转运量多少，均发生固定费用 且第 k 个中间编组站转运最大容量限制为 用 和 分别表示从 到 和从 到 单位物质运输费用，试建立使总运费为最小该种物资调运方案数学模型。第36页 分析 从产地到中转站和从中转站到销地，均为运输问题，关键是各中转站是否启用，用哪几个。对于中转站而言，含有用与不用两种状态，故能够考虑引入0-1变量来处理。模型建立和求解 设 表示从产地 运至中转站 物资数量，表示从中转站运至销地 物资数量，记第37页 周一 18人 周二 15人 周三 12人 周四 16人 周五 19人 周六 14人 周日 12人例例 某百货商场每七天内最少需要售货员人数以下：某百货商场每七天内最少需要售货员人数以下：要求每个员工每七天连续工作要求每个员工每七天连续工作五天，休息两天。求总员工五天，休息两天。求总员工数最少排班方案。数最少排班方案。第38页第39页ILP问题图解法问题图解法(仅适用二维问题仅适用二维问题)n实例实例 用图解法求解以下ILP问题:第40页解解:n对应对应LP问题最优解为问题最优解为(4,4/3),不是不是ILP问题可问题可行解行解nILP问题最优解为问题最优解为X*=(4,1),最优目标值为最优目标值为 z*=14,可行域顶点能够是非可行解可行域顶点能够是非可行解第41页投资效益和风险投资效益和风险(1998年全国大学生数学建模竞赛年全国大学生数学建模竞赛A题题)第42页原题还有一组 n=25数据，现略去。第43页问题分析问题分析优化问题决议决议每种资产投资额（投资组合）目标目标净收益最大整体风险最小 在一定风险下收益最大决议 在一定收益下风险最小决议 收益和风险按一定百分比组合最优决议一组解(如在一系列风险值下收益最大决议)二者矛盾 冒险型投资者从中选择高风险下收益最大决议 保守型投资者则可从低风险下决议中选取第44页模型建立模型建立用数学符号和式子表述决议变量、结构目标函数、确定约束条件。xi i对Si(i=0,1,n)投资,x0表示存入银行.目标函数目标函数 总收益投资Si收益减去交易费，对i求和 总体风险投资Si风险，对i求最大值对Si投资xi i加交易费ci(xi i)，对i求和，不超出给定资金M.决议变量决议变量约束条件约束条件第45页0uixicipiui1）投资Si交易费、净收益、风险、资金表示式交易费净收益(收益率ri)风险资金(风险损失率qi)第46页2）投资方案、总收益、总体风险、资金表示式投资方案总收益总体风险资金3）两目标（总收益、总体风险）优化模型第47页4）单目标优化模型第48页模型简化模型简化交易费ui很小M很大资金约束设M=1投资Si百分比第49页设M=1线性规划模型线性规划模型LP1模型模型M1简化简化M1第50页模型模型M2简化简化M2极大极小规划模型线性规划模型线性规划模型LP2引入人工变量引入人工变量 xn+1第51页模型模型M3简化简化M3线性规划线性规划模型模型LP3模型求解模型求解LP1,LP2,LP3都很轻易用MATLAB,MATHEMATICA或其它数学软件求解第52页线性规划模型线性规划模型LP1第53页模型一求解第54页第55页第56页LP1结果结果风险水平取风险水平取k=02.5%,得投资百分比得投资百分比y0y4第57页LP1结果结果第58页LP3结果结果与LP1相同第59页实例实例 某厂生产A,B,C三种产品,每种产品单位利润分别为12,18和15,资源消耗和资源总数量以下表,求总利润最大生产方案.A B C 限制 原料1/单位产品 6 9 5 200 原料2/单位产品 12 16 17 360 人工/单位产品 25 20 12 780第60页解解:设生产设生产A,B,C分别为分别为x1,x2,x3个单位个单位,数学模型为数学模型为:第61页整数规划计算方法分枝定界法主要思绪 1.分枝 把全部可行解空间重复地分割为越来越小子集；2.定界对每个子集内解集计算一个目标下界（对于最小值问题）；3.剪枝在每次分枝后，凡是界限超出已知可行解集目标值那些子集不再深入分枝，这么，许多子集可不予考虑第62页 设有最大化整数规划问题A，与它对应线性规划为问题B，从解问题B 开始，若其最优解不符合A 整数条件，那么B 最优目标函数必是A 最优目标函数z*上界，记作 ；而A 任意可行解目标函数值将是z*一个下界 。分枝定界法就是将B 可行域分成子区域方法。逐步减小 和增大 ，最终求到z*.第63页 例 求解下述整数规划解（i）先不考虑整数限制，即解对应线性规划B，得最优解为：此时 取 第64页（ii）因为 当前均为非整数，故不满足整数要求，任选一个进行分枝。设选 进行分枝，把可行集分成2 个子集：这两个子集规划及求解以下：问题B1 问题B2第65页（iii）对问题 再进行分枝得问题 和 ,它们最优解为再定界：340 z*349，并将 剪枝。（iv）对问题 再进行分枝得问题 和 ，它们最优解为将 于是能够断定原问题最优解为：第66页n例例 某校篮球队准备从以下队员中选拔某校篮球队准备从以下队员中选拔3名为正名为正式队员，并使平均身高尽可能高，这式队员，并使平均身高尽可能高，这6名预备名预备队员情况以下表所表示。队员情况以下表所表示。预备队员预备队员 号码号码 身高身高 位置位置 大张大张 1 193 中锋中锋 大李大李 2 191 中锋中锋 小王小王 3 187 前卫前卫 小赵小赵 4 186 前卫前卫 小田小田 5 180 后卫后卫 小周小周 6 185 后卫后卫第67页 队员挑选要满足以下条件：队员挑选要满足以下条件：n最少补充一名后卫最少补充一名后卫(5、6)队员；队员；n大李大李(2号号)或小田或小田(5号号)中间只能入选一名；中间只能入选一名；n最多补充一名中锋最多补充一名中锋(1、2)；n若大李若大李(2)或小赵或小赵(4)入选，小周入选，小周(6)就不能入就不能入选。选。试建立此问题数学模型。试建立此问题数学模型。解:则该问题数学模型为则该问题数学模型为:第68页上述形式数学规划模型称为上述形式数学规划模型称为(0-1)规划规划 队员挑选要满足以下条件：队员挑选要满足以下条件：n最少补充一名后卫最少补充一名后卫(5、6)队员；队员；n大李大李(2号号)或小田或小田(5号号)中间只能入选一名；中间只能入选一名；n最多补充一名中锋最多补充一名中锋(1、2)；n若大李若大李(2)或小赵或小赵(4)入选，小周入选，小周(6)就不能入就不能入选。选。试建立此问题数学模型。试建立此问题数学模型。第69页 0-1规划 一个企业有22亿元资金用来投资，现有6个项目可供选择，各项目所需投资金额和预计年收益以下表所表示：项目123456投资526468收益0.50.40.60.50.91 应选择哪几个项目投资收益最大？第70页指派问题 0-1规划问题：第71页 上述指派问题可行解能够用一个矩阵表示，其每行每列都有且只有一个元素为1，其余元素均为0。问题中变量只能取0 或1，从而是一个0-1 规划问题。普通0-1 规划问题求解极为困难。但指派问题并不难解，其约束方程组系数矩阵十分特殊（被称为全全单位模矩阵单位模矩阵，其各阶非零子式均为 1），其非负可行解分量只能取0 或1，故约束 或 可改写为 而不改变其解。此时，指派问题被转化为一个特殊运输问题，其中m=n，。第72页指派问题计算机解法 第73页第74页解指派问题匈牙利算法解指派问题匈牙利算法第75页五、网络问题问题：右图是一公路交通图，弧上数字为旅程，求汽车从（1）到（7）最短路。第76页模型：第77页问题变形最大流问题上图第78页问题变形最小费用流问题上图第79页六、问题应用钢管下料问题：某钢管零售商从钢管厂进货，将钢管按用户 要求切割后售出，从钢管厂进货时得到 原料钢管都是19m。（1）现有一客户需要50根4m、20根6m和15根8m 钢管，应怎样下料最省。第80页问题(1)分析：首先，应该确定哪些切割模式是可行。所谓一个切割模式，是指按照客户需要在原料钢管上安排切割一个组合。显然，可行切割模式是很多。其次，应该确定哪些切割模式是合理。通常假设一个合理切割模式余料不应该大于或等于客户需要钢管最小尺寸。比如，将19m 长钢管切割成3 根4m钢管是可行，但余料为7m，能够深入将7m 余料切割成4m 钢管（余料为3m），或者将7m 余料切割成6m 钢管（余料为1m）。在这种合理性假设下，切割模式一共有7 种，如表3 所表示。第81页问题（1）解答钢管下料合理切割模式：4m钢管数6m钢管数8m钢管数余料（m）模式14003模式23101模式32013模式41203模式51111模式60301模式70023问题：按何种切割模式，切割多少根原钢管，最为节约。节约：1）余料最少 2）原钢管总数最少第82页模型设x i表示照第i种模式切割原材料钢管根数总余料最小 原钢管条数最少第83页求解 利用Lingo软件对上述整数规划问题分别求解.对第一个目标模型，求得:按照模式2 切割12 根原料钢管，按照模式5 切割15 根原料钢管，共27 根，总余料量为27m。但4m 长钢管比要求多切割了1 根，6m 长钢管比要求多切割了7 根。显然，在总余料量最小目标下，最优解将是使用余料尽可能小切割方式（模式2 和模式5 余料为1m），这会造成切割原料钢管总根数较多。第84页 对第二个目标模型，求得:按照模式2 切割15 根原料钢管，按模式5 切割5 根，按模式7 切割5 根，共25 根，可算出总余料量为35m。但各长度钢管数恰好全部满足要求，没有多切割。与上面得到结果比较，总余料量增加了8m，不过所用原料钢管总根数降低了2根。在余料没有什么用途情况下，通常选择总根数最少为目标。第85页（2）零售商假如采取不一样切割模式太多，将会导致生产过程复杂化，从而增加生产和管理成本，所以该零售商要求只能采取3种不一样切割模式。此外，该客户除需要（1）中三种钢管外，还需要10根5m钢管，应怎样下料最省。第86页问题（2）解答问题分析：按照问题（1）思绪，能够经过枚举法首先确定哪些切割模式是可行。但因为需要钢管规格增加到4 种，所以枚举法工作量较大。一合理切割模式余料不应该大于或等于客户需要钢管最小尺寸，故本题中合理切割模式余量不能大于3m。这里，仅选择总根数最少为目标进行求解。第87页模型建立设x i表示照第i种模式切割原材料钢管根数（i=1,2,3）r ji分别表示在第i种切割模式下一根原钢管生产第j种(j=1,2,3,4 分别对应长度是4,5,6,8米钢管)钢管数量(满足4米钢管数需求)(满足5米钢管数需求)(满足6米钢管数需求)(满足8米钢管数需求)(第i种模式所得钢管 总长度,i=1,2,3)第88页七、应用（AMCM-88B）将七种不一样规格包装箱装到两辆铁路平板车上，各包装箱宽、高均相等，但厚度t(厘米)与重量w(千克)不一样。每平板车有10.2米长地方用来装包装箱，载重40吨。因为货运限制，对c5、c6、c7类包装箱总数有限定：总厚度不超出302.7(厘米)。试把箱子装到平板车并使空间浪费最小。c1c2c3c4c5c6c7t45.75162.57149.25260w3000100050040001000件数8796648第89页八、应用（AMCM-89B）机场通常按“先来先走”标准来分配飞机跑道，即当飞机准备好离开登机口时，驾驶员电告地面控制中心，加入等候跑道队伍。假设控制中心能够从快速联机数据库中得到每架飞机以下信息：1、预定离开登机口时间 2、实际离开登机口时间 3、机上乘客人数 4、预定在下一站转机人数和时间 5、抵达下一站预定时间。又设飞机共有七种型号，载客量从100人起以50人递增，载客最多达400人。试开发和分析一个能使乘客和航空企业双方满意数学模型。第90页4.2 非线性规划非线性规划(Non-linear Programming)模型模型第91页约束回归问题 某大学希望为它毕业生安排工作岗位.为简单起见,假设每个毕业生接收政府部门、工业界或科学院中一个岗位。设 第j 年毕业生总人数，并 分别为第j年实际进入政府部门、工业界或科学院人数。一个简单想法就是假设给出每年进入上述部门人数百分比为 ,则在第j年可预计出参加各种工作人数分别为第92页 为了有依据地衡量上述模型可靠性，必须了解进入这三个部门实际人数与预计数字之间差异。按最小二乘法预计，要求到达最小。同时考虑到约束条件，得数学模型为:第93页投资问题 假设某企业在下一个计划期内可用于投资总资本为b万元，可供选择投资项目共有n个，分别记为 已知对第j 个项目标投资总额为万元，而收益总额为 万元。问怎样进行投资，才能使利润率最高。第94页模型建立 设投资决议变量则该问题数学模型为：第95页武器分配问题 用m组不一样类型兵器，来摧毁对方n个目标.设第 组兵器由 个单件组成，表示第 个目标主要性(或危险性)，表示用单件第 组兵器击中第 个目标概率，试问怎样分配现有兵器攻击对应目标，可使击毁目标主要性到达最大值？第96页模型建立 设 表示用于攻击第 个目标第 类兵器数量。击毁目标主要性为所以，兵器分配问题数学模型为第97页评价体系 为了进行多属性问题综合评价，就需要确定每个属性相对主要性，即求它们权重。为此将各属性进行两两比较，从而得出以下判断矩阵判断矩阵其中元素 是第 i 个属性主要性与第 j 个属性主要性之比。试从判断矩阵来确定各属性权重。第98页模型建立 设权向量为 ，即 表示第 j 个属性权 重 。衡量权重标准是在最小二乘意义下能最好地反应判断矩阵判断矩阵预计，即 由此得 预计值 所以得 数学模型为第99页
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
