《线性规划模型自来水输送混合泳接力队的选拔.ppt》由会员分享，可在线阅读，更多相关《线性规划模型自来水输送混合泳接力队的选拔.ppt（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、线性规划模型指导老师指导老师:梁海峰梁海峰其他费用其他费用:450元元/千吨千吨 应如何分配水库供水量，公司才能获利最多？应如何分配水库供水量，公司才能获利最多？若水库供水量都提高一倍，公司利润可增加到多少？若水库供水量都提高一倍，公司利润可增加到多少？元元/千吨千吨甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理费引水管理费运输问题：自来水输送运输问题：自来水输送收入：收入：900元元/千吨千吨支出支出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40水水库库供供水水量量(千千吨吨)小小区区基基本
2、本用用水水量量(千千吨吨)小小区区额额外外用用水水量量(千千吨吨)（以天计）（以天计）总总供水量：供水量：160确定送水方案确定送水方案使利润最大使利润最大问题问题分析分析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40总需求量：总需求量：120+180=300总收入总收入900 160=144,000(元元)收入：收入：900元元/千吨千吨其他费用其他费用:450元元/千吨千吨支出支出引水管理费引水管理费其他其他支出支出450160=72,000(元)使引水管理费最小使引水管理费最小供应供应限制限制约束约束条件条件需求需求限制限制线性线性规划规
3、划模型模型(LP)目标目标函数函数 水库水库i 向向j 区的日供水量为区的日供水量为 xij（x34=0）决策变量决策变量 模型建立模型建立 确定确定3个水库向个水库向4个小区的供水量个小区的供水量引水管理费引水管理费(元元/千吨千吨)甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/模型求解模型求解 OBJECTIVEFUNCTIONVALUE1)24400.00VARIABLEVALUEREDUCEDCOSTX110.00000030.000000X1250.0000000.000000X130.00000050.000000X140.0000002
4、0.000000X210.00000010.000000X2250.0000000.000000X230.00000020.000000X2410.0000000.000000X3140.0000000.000000X320.00000010.000000X3310.0000000.000000利利润润=总总收收入入-其其它它费费用用-引引 水水 管管 理理 费费=144000-72000-24400=47600（元）（元）A(50)B(60)C(50)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)5050401010引水管理费引水管理费 24400(元元)丁的蛙泳成
5、绩退步到丁的蛙泳成绩退步到115”2；戊的自由泳成绩进戊的自由泳成绩进步到步到57”5,组成接力队的方案是否应该调整组成接力队的方案是否应该调整？如何选拔队员组成如何选拔队员组成4 4 100100米混合泳接力队米混合泳接力队?甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”45名候选人的名候选人的百米成绩百米成绩穷举法穷举法：组成接力队的方案共有组成接力队的方案共有5!=120种种。0-1规划规划分配问题：混合
6、泳接力队的选拔分配问题：混合泳接力队的选拔 目标目标函数函数若选择队员若选择队员i参加泳姿参加泳姿j 的比赛，记的比赛，记xij=1,否则记否则记xij=0 cij(秒秒)队员队员i 第第j 种泳姿的百米成绩种泳姿的百米成绩约束约束条件条件每人最多入选泳姿之一每人最多入选泳姿之一ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每种泳姿有且只有每种泳姿有且只有1 1人人 0-1规划模型规划模型模型求解模型求解 最最优优解解：x14=x21=x32=x
7、43=1,其它变量为其它变量为0;成成绩绩为为253.2(秒秒)=413”2MIN66.8x11+75.6x12+87x13+58.6x14+67.4x51+71x52+83.8x53+62.4x54SUBJECTTOx11+x12+x13+x14=1x41+x42+x43+x44=1x11+x21+x31+x41+x51=1x14+x24+x34+x44+x54=1ENDINT20输入输入LINDO求解求解 甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由
8、泳自由泳58”653”59”457”2102”4甲甲自由泳、乙自由泳、乙蝶泳、蝶泳、丙丙仰泳、丁仰泳、丁蛙泳蛙泳.丁蛙泳丁蛙泳c43=69.675.2，戊自由泳戊自由泳c54=62.457.5,方案是否调整？方案是否调整？敏感性分析？敏感性分析？乙乙蝶泳、丙蝶泳、丙仰泳、仰泳、丁丁蛙泳、戊蛙泳、戊自由泳自由泳IP规划一般没有与规划一般没有与LP规划相类似的理论，规划相类似的理论，LINDO输出的敏感性分析结果通常是没有意义的。输出的敏感性分析结果通常是没有意义的。最优解：最优解：x21=x32=x43=x51=1,成绩为成绩为417”7c43,c54 的新数据重新输入模型，用的新数据重新输入模
9、型，用LINDO求解求解 指派指派(Assignment)问题问题：每项任务有且只有一人承担，每项任务有且只有一人承担，每人只能承担一项每人只能承担一项，效益不同，怎样分派使总效益最大，效益不同，怎样分派使总效益最大.讨论讨论甲甲自由泳、乙自由泳、乙蝶泳、蝶泳、丙丙仰泳、丁仰泳、丁蛙泳蛙泳.原原方方案案为了选修课程门数最少，应学习哪些课程为了选修课程门数最少，应学习哪些课程？多目标规划：选课策略多目标规划：选课策略要求至少选两门数学课、三门运筹学课和两门计算机课要求至少选两门数学课、三门运筹学课和两门计算机课 课号课号课名课名学分学分所属类别所属类别先修课要求先修课要求1微积分微积分5数学数学
10、2线性代数线性代数4数学数学3最优化方法最优化方法4数学；运筹学数学；运筹学微积分；线性代数微积分；线性代数4数据结构数据结构3数学；计算机数学；计算机计算机编程计算机编程5应用统计应用统计4数学；运筹学数学；运筹学微积分；线性代数微积分；线性代数6计算机模拟计算机模拟3计算机；运筹学计算机；运筹学计算机编程计算机编程7计算机编程计算机编程2计算机计算机8预测理论预测理论2运筹学运筹学应用统计应用统计9数学实验数学实验3运筹学；计算机运筹学；计算机微积分；线性代数微积分；线性代数选修课程最少，且学分尽量多，应学习哪些课程选修课程最少，且学分尽量多，应学习哪些课程？0-1规划模型规划模型 决策变
11、量决策变量 目标函数目标函数 xi=1选修课号选修课号i 的的课程（课程（xi=0不选）不选）选修课程总数最少选修课程总数最少约束条件约束条件最少最少2门数学课，门数学课，3门运筹学课，门运筹学课，2门计算机课。门计算机课。课号课号课名课名所属类别所属类别1微积分微积分数学数学2线性代数线性代数数学数学3最优化方法最优化方法数学；运筹学数学；运筹学4数据结构数据结构数学；计算机数学；计算机5应用统计应用统计数学；运筹学数学；运筹学6计算机模拟计算机模拟计算机；运筹学计算机；运筹学7计算机编程计算机编程计算机计算机8预测理论预测理论运筹学运筹学9数学实验数学实验运筹学；计算机运筹学；计算机先修课
12、程要求先修课程要求最优解：最优解：x1=x2=x3=x6=x7=x9=1,其它为其它为0；6门课程，总学分门课程，总学分210-1规划模型规划模型 约束条件约束条件x3=1必有必有x1=x2=1模型求解（模型求解（LINDO）课号课号课名课名先修课要求先修课要求1微积分微积分2线性代数线性代数3最优化方法最优化方法微积分；线性代数微积分；线性代数4数据结构数据结构计算机编程计算机编程5应用统计应用统计微积分；线性代数微积分；线性代数6计算机模拟计算机模拟计算机编程计算机编程7计算机编程计算机编程8预测理论预测理论应用统计应用统计9数学实验数学实验微积分；线性代数微积分；线性代数学分最多学分最多
13、多目标优化的处理方法多目标优化的处理方法：化成单目标优化。化成单目标优化。两目标两目标(多目标多目标)规划规划 讨论：选修课程最少，学分尽量多，应学习哪些课程？讨论：选修课程最少，学分尽量多，应学习哪些课程？课程最少课程最少以以学分最多为目标，不学分最多为目标，不管课程多少。管课程多少。以以课程最少课程最少为目标，不为目标，不管学分多少。管学分多少。最优解如上，最优解如上，6门课门课程，总学分程，总学分21。最优解显然是选修所最优解显然是选修所有有9门课程门课程。多目标规划多目标规划 在在课程最少的前提下课程最少的前提下以以学分最多为目标。学分最多为目标。最优解：最优解：x1=x2=x3=x5
14、=x7=x9=1,其它为其它为0；总总学分由学分由21增至增至22。注意：最优解不唯一！注意：最优解不唯一！课号课号课名课名学分学分1微积分微积分52线性代数线性代数43最优化方法最优化方法44数据结构数据结构35应用统计应用统计46计算机模拟计算机模拟37计算机编程计算机编程28预测理论预测理论29数学实验数学实验3 LINDO无法告诉优化无法告诉优化问题的解是否唯一。问题的解是否唯一。可将可将x9=1易为易为x6=1增加约束增加约束 ，以学分最多为目标求解。以学分最多为目标求解。多目标规划多目标规划 对学分数和课程数加权形成一个目标，如三七开。对学分数和课程数加权形成一个目标，如三七开。最优解：最优解：x1=x2=x3=x4=x5=x6=x7=x9=1，其它为其它为0；总学分总学分28。课号课号课名课名学分学分1微积分微积分52线性代数线性代数43最优化方法最优化方法44数据结构数据结构35应用统计应用统计46计算机模拟计算机模拟37计算机编程计算机编程28预测理论预测理论29数学实验数学实验3 讨论与思考讨论与思考最优解最优解与与 1=0，2=1的结果相同的结果相同学分最多学分最多多目标规划多目标规划 最优解最优解与与 1=1，2=0的结果相同的结果相同课程最少课程最少实验见数学建模实验指导_02_Lindo求解线性规划问题.doc。