数学建模规划模型讲解课件

最优化模型最优化模型 -线性规划线性规划 最优化模型1参考书目参考书目1.陈宝林。最优化理论与算法。清华大学出版陈宝林。最优化理论与算法。清华大学出版社社.2.谢金星，薛毅。优化建模与谢金星，薛毅。优化建模与lindo/lingo优化优化软件软件.清华大学出版社清华大学出版社.参考书目1.陈宝林。最优化理论与算法。清华大学出版社.2背景知识背景知识运筹学理论的一部分运筹学理论的一部分最早起源于中国古代最早起源于中国古代公元前公元前6世纪孙武所著的孙子兵法世纪孙武所著的孙子兵法孙膑孙膑“斗马术斗马术”，田忌与齐王赛马，博弈论，田忌与齐王赛马，博弈论运筹帷幄之中，决胜千里之外运筹帷幄之中，决胜千里之外”。这千古名句也。这千古名句也可以说是对张良运筹思想的赞颂和褒奖。可以说是对张良运筹思想的赞颂和褒奖。国外起源与发展国外起源与发展1738年年,D.Bernoulli首次提出了效用的概念，并以此作首次提出了效用的概念，并以此作为决策的标准。为决策的标准。背景知识运筹学理论的一部分3l1896年，年，V.Pareto首次从数学角度提出多目标优化问题，首次从数学角度提出多目标优化问题，引进了引进了Pareto最优的概念。最优的概念。l丹麦电话工程师丹麦电话工程师A.K.Erlang开展了关于电话局中继线数开展了关于电话局中继线数目的话务理论的研究，目的话务理论的研究，1909年发表了他将概率论应用于年发表了他将概率论应用于电话话务理论的研究论文：电话话务理论的研究论文：“概率论与电话会话概率论与电话会话”，开，开排队论研究的先河。排队论研究的先河。l1935-38年，英国为了正确地运用新研制的雷达系统来对年，英国为了正确地运用新研制的雷达系统来对付德国飞机的空袭，在皇家空军中组织了一批科学家，付德国飞机的空袭，在皇家空军中组织了一批科学家，进行新战术试验和战术效率评价的研究，并取得了满意进行新战术试验和战术效率评价的研究，并取得了满意的效果。他们把自己从事的这种工作命名为的效果。他们把自己从事的这种工作命名为“OperationalResearch”(运筹学，或直译为作战研究运筹学，或直译为作战研究)。l1939年，苏联的年，苏联的.总结了他对生产组织总结了他对生产组织的研究，写了生产组织与计划中的数学方法一书，的研究，写了生产组织与计划中的数学方法一书，是线性规划应用于工业生产问题的经典著作是线性规划应用于工业生产问题的经典著作 背景知识（续）背景知识（续）1896年，V.Pareto首次从数学角度提出多目标优化问题4l1947年年,G.B.Dantzig提出了单纯形方法后，线性规划便提出了单纯形方法后，线性规划便迅速形成为一个独立的分支。迅速形成为一个独立的分支。并逐级发展起来。并逐级发展起来。l英国运筹学会英国运筹学会1948年成立（年成立（1948-53年是运筹学俱乐部，年是运筹学俱乐部，1953年年11月起改名为学会）。月起改名为学会）。l二次大战胜利后，美英各国不但在军事部门继续保留了二次大战胜利后，美英各国不但在军事部门继续保留了运筹学的研究核心，而且在研究人员、组织的配备及研运筹学的研究核心，而且在研究人员、组织的配备及研究范围和水平上，都得到了进一步的扩大和发展，同时究范围和水平上，都得到了进一步的扩大和发展，同时运筹学方法也向政府和工业等部门扩展。运筹学方法也向政府和工业等部门扩展。l1951年出版了新版（年出版了新版（1946年的原版是保密的，年的原版是保密的，1948年才年才撤销保密）的撤销保密）的P.M.Morse和和G.E.Kimball的运筹学方法的运筹学方法（MethodsofOperationsResearch），这是二战结束），这是二战结束后，对战时整个运筹学工作做系统的专业叙述的一本著后，对战时整个运筹学工作做系统的专业叙述的一本著作。作。l1951年年,H.W.Kuhn与与A.W.Tucker提出了提出了Kuhn-Tucker条条件，标志着非线性规划理论的初步形成。件，标志着非线性规划理论的初步形成。背景知识（续）背景知识（续）1947年,G.B.Dantzig提出了单纯形方法后，线性规5l1952年年5月美国运筹学会成立，并创刊月美国运筹学会成立，并创刊OperationsResearch。l1953年年,R.Bellman提出动态规划的名称，并阐述了最优提出动态规划的名称，并阐述了最优化原理。化原理。l1954年，年，D.R.Dantzig等研究旅行推销员问题时提出了分等研究旅行推销员问题时提出了分解的思想，成为整数规划中两大方法解的思想，成为整数规划中两大方法割平面法与分枝割平面法与分枝定界法的萌芽。定界法的萌芽。l1955年年,G.Dantzig首先考虑出现随机变量的线性规划问首先考虑出现随机变量的线性规划问题，这是最早提出的随机规划中的有补偿二阶段问题。题，这是最早提出的随机规划中的有补偿二阶段问题。l1956年年,L.R.Ford,Jr.与与D.R.Fulkerson提出并解决了网提出并解决了网络最大流问题，加强了图论与线性规划的联系，促进了络最大流问题，加强了图论与线性规划的联系，促进了优化理论的研究优化理论的研究。背景知识（续）背景知识（续）1952年5月美国运筹学会成立，并创刊Operations6l1959年年1月月1日，国际运筹学会联合会日，国际运筹学会联合会(1FORS)正式宣告成正式宣告成立，当时的联合会只包括英、美、法三个国家的运筹学立，当时的联合会只包括英、美、法三个国家的运筹学会，首任（会，首任（1959-61年）主席（当时称为秘书，到年）主席（当时称为秘书，到1968年年第四届时才改称主席）为英国的第四届时才改称主席）为英国的CharlesGoodeve。背景知识（续）背景知识（续）1959年1月1日，国际运筹学会联合会(1FORS)正式宣告7l运筹学理论在中国的研究与发展运筹学理论在中国的研究与发展l1957年，经中国科学院力学研究所所长钱学森的倡导，年，经中国科学院力学研究所所长钱学森的倡导，在该所成立了由许国志领导的国内第一个运筹学研究组在该所成立了由许国志领导的国内第一个运筹学研究组(后成室后成室)。刘源张、周华章、桂湘云等是该组最早的一。刘源张、周华章、桂湘云等是该组最早的一批研究人员，从此在我国开始了现代运筹学的研究。当批研究人员，从此在我国开始了现代运筹学的研究。当年秋季，又有大学毕业生顾基发、董泽清、徐映波、陈年秋季，又有大学毕业生顾基发、董泽清、徐映波、陈锡康、郭绍僖、李秉全等分配进入该组。锡康、郭绍僖、李秉全等分配进入该组。l1958年，中国科学院数学研究所所长华罗庚率领广大研年，中国科学院数学研究所所长华罗庚率领广大研究人员，包括吴文俊、越民义、万哲先、王元等在内，究人员，包括吴文俊、越民义、万哲先、王元等在内，也开展了运筹学应用课题的研究，并影响和带动了全国也开展了运筹学应用课题的研究，并影响和带动了全国范围内各部门、各高校的运筹学应用和推广工作。运输范围内各部门、各高校的运筹学应用和推广工作。运输和农业等部门的和农业等部门的“图上作业法图上作业法”、“打麦场设计打麦场设计”、“中国邮递员问题中国邮递员问题”是典型的成果。是典型的成果。背景知识（续）背景知识（续）运筹学理论在中国的研究与发展背景知识（续）8l1959年年2月，山东大学在数学系中设置了国内最早的一个月，山东大学在数学系中设置了国内最早的一个运筹学专门化，由谢力同与郑汉鼎执教。自当年暑假开运筹学专门化，由谢力同与郑汉鼎执教。自当年暑假开始，每年都有运筹学方向的学生毕业，为我国运筹学事始，每年都有运筹学方向的学生毕业，为我国运筹学事业的发展作出了重要贡献。业的发展作出了重要贡献。l1959年，中国科学院数学研究所成立了运筹学研究室，年，中国科学院数学研究所成立了运筹学研究室，研究人员都由所内其它室组调入。孙克定任研究室主任，研究人员都由所内其它室组调入。孙克定任研究室主任，该室最早的一批研究人员有排队论组的越民义、吴方、该室最早的一批研究人员有排队论组的越民义、吴方、徐光煇、韩继业；对策论组的吴文俊、江加禾、施闺芳；徐光煇、韩继业；对策论组的吴文俊、江加禾、施闺芳；数学规划组的朱永津、应玫茜、马仲蕃、凌开诚等。与数学规划组的朱永津、应玫茜、马仲蕃、凌开诚等。与此同时，全国范围内很多高校也有大批教师转入运筹学此同时，全国范围内很多高校也有大批教师转入运筹学领域。领域。背景知识（续）背景知识（续）1959年2月，山东大学在数学系中设置了国内最早的一个运筹学9l1965年起，华罗庚和他的小分队在全国工业部门开始普年起，华罗庚和他的小分队在全国工业部门开始普及推广统筹法的群众运动。在此后的二十年中，为普及及推广统筹法的群众运动。在此后的二十年中，为普及推广双法（统筹法与从推广双法（统筹法与从1970年开始普及推广的优选法），年开始普及推广的优选法），他们走访了全国他们走访了全国23个省市中几百个城市的几千个工厂，个省市中几百个城市的几千个工厂，并向数百万人开设讲座开展工作，取得了巨大的社会效并向数百万人开设讲座开展工作，取得了巨大的社会效益和经济效益。益和经济效益。l1965年华罗庚统筹方法平话及其补充一书由中国工年华罗庚统筹方法平话及其补充一书由中国工业出版社出版。业出版社出版。l 1970年起，华罗庚和他的小分队开始在全国范围内普及年起，华罗庚和他的小分队开始在全国范围内普及推广优选法的群众运动。从此，统筹与优选双法变得家推广优选法的群众运动。从此，统筹与优选双法变得家喻户晓，双法的普及推广也取得了极为可观的社会、经喻户晓，双法的普及推广也取得了极为可观的社会、经济效益。济效益。l1971年华罗庚优选法平话及其补充一书由国防工业年华罗庚优选法平话及其补充一书由国防工业出版社出版。出版社出版。背景知识（续）背景知识（续）1965年起，华罗庚和他的小分队在全国工业部门开始普及推广统10l1980年年4月月22-26日在山东济南，召开了中国数学会运筹日在山东济南，召开了中国数学会运筹学会成立暨第一届代表大会。中国运筹学倡导者之一，学会成立暨第一届代表大会。中国运筹学倡导者之一，中国科学院副院长华罗庚主持了会议，有来自各地科研中国科学院副院长华罗庚主持了会议，有来自各地科研机构、高等院校、军事部门、工交企业等有关单位的机构、高等院校、军事部门、工交企业等有关单位的82名代表出席。华罗庚在大会开幕式与闭幕式上均发表了名代表出席。华罗庚在大会开幕式与闭幕式上均发表了讲话，回顾了他在全国范围普及推广讲话，回顾了他在全国范围普及推广“双法双法”的经验和的经验和成果，勉励大家以克敌攻坚的进取精神积极开展运筹学成果，勉励大家以克敌攻坚的进取精神积极开展运筹学研究。会议作了研究。会议作了12个专题学术报告和个人成果的几十个个专题学术报告和个人成果的几十个分组报告。中国数学会理事长华罗庚被推选兼任运筹学分组报告。中国数学会理事长华罗庚被推选兼任运筹学会理事长，越民义、许国志、余潜修为副理事长，桂湘会理事长，越民义、许国志、余潜修为副理事长，桂湘云为秘书长，推选常务理事云为秘书长，推选常务理事11名，理事名，理事42名。会议决定名。会议决定学会挂靠在中科院应用数学所学会挂靠在中科院应用数学所背景知识（续）背景知识（续）1980年4月22-26日在山东济南，召开了中国数学会运筹学11优化模型应用的广泛性1.系系统统分分析析，即即生生产产计计划划和和经经营营决决策策中中的的优优化化问题。例如：问题。例如：合合理理计计划划生生产产:运运输输，分分配配，布布局局，选选址址，指指派派，下料、配料等优化问题（下料、配料等优化问题（linearprogramming）;合合理理开开发发（或或配配置置）资资源源:可可再再生生资资源源的的持持续续开开发发,不不 可可 再再 生生 资资 源源 的的 优优 化化 配配 置置（linearprogramming）合理运行设备合理运行设备:设备的最有运行（维修）方案设备的最有运行（维修）方案.合合理理组组合合投投资资:追追求求最最大大受受益益、最最小小风风险险的的投投资资组合方案（组合方案（Multiobjectiveprogramming）优化模型应用的广泛性1.系统分析，即生产计划和经营决策中的122.工程设计和控制中的非线性分析工程设计和控制中的非线性分析（Non-linearprogrammingandoptimalcontrol）例如：例如：结构系统最优设计（人字架设计）结构系统最优设计（人字架设计）机机械械零零件件或或部部件件的的最最优优化化设设计计(轮轮轴轴颈颈,凸凸轮轮设设计计)化工设备最优设计（单件或连锁设备优化设计）化工设备最优设计（单件或连锁设备优化设计）电力网络和水力网络的优化设计（平衡条件电力网络和水力网络的优化设计（平衡条件）2.工程设计和控制中的非线性分析13历届数模竞赛所涉及的优化问题：历届数模竞赛所涉及的优化问题：9494年年 A A题题 逢山开路（工程设计优化问题）逢山开路（工程设计优化问题）目标：工程造价最低目标：工程造价最低决策：在若干约束下选择一条最佳线路决策：在若干约束下选择一条最佳线路9595年年 B B题：天车调度问题（生产操作优化问题）题：天车调度问题（生产操作优化问题）目标：年钢产量最大目标：年钢产量最大决策：天车调度的最优方案设计决策：天车调度的最优方案设计l9696年年 A A题：最优捕鱼策略（开发资源优化问题）题：最优捕鱼策略（开发资源优化问题）目标：可持续捕捞的努力量及最大捕捞量目标：可持续捕捞的努力量及最大捕捞量决策：在平衡条件下确定五年内最佳捕捞方案决策：在平衡条件下确定五年内最佳捕捞方案历届数模竞赛所涉及的优化问题：94年 A题 逢山开路（工14l9797年年 A A题：零件参数设计（产品参数优化设计）题：零件参数设计（产品参数优化设计）目标：产品总造价最低（产品质量损失费用目标：产品总造价最低（产品质量损失费用 零件制造成本费用）零件制造成本费用）决策：零件参数的最佳水平组合方案决策：零件参数的最佳水平组合方案l9898年年 A A题：组合投资问题（风险决策优化问题）题：组合投资问题（风险决策优化问题）目标（二目标）：收益最大，风险最小目标（二目标）：收益最大，风险最小 决策：组合投资方案决策：组合投资方案l9999年年 A A题：自动化车床管理（排队题：自动化车床管理（排队-更新问题）更新问题）目标：生产工序的效益（费用最低）最大目标：生产工序的效益（费用最低）最大 决策：最佳检验间隔河刀具更换策略决策：最佳检验间隔河刀具更换策略97年 A题：零件参数设计（产品参数优化设计）15l9999年年 B B题：钻井布局问题题：钻井布局问题(生产计划优化问题生产计划优化问题)目标：最大限度利用初步、勘探时的旧井数目标：最大限度利用初步、勘探时的旧井数 决决策策：在在规规定定精精度度的的前前提提下下确确定定系系统统勘勘探探时时的的最最 佳网络分布佳网络分布 2002 2002年年 A A题：车灯线光源的优化设计题：车灯线光源的优化设计 目标：线光源的功率最小目标：线光源的功率最小 决策决策:在满足设计规范的条件下在满足设计规范的条件下,计算线光源的长度计算线光源的长度 B B题：彩票中的数学题：彩票中的数学 目标：最大限度地吸引彩民积极购买彩票目标：最大限度地吸引彩民积极购买彩票 决决策策：在在保保证证彩彩民民和和彩彩票票公公司司的的利利益益上上如如何何设设置置最最佳佳彩票方案彩票方案99年 B题：钻井布局问题(生产计划优化问题)16l0404年年 A A题：奥运会场馆周围超市设计题：奥运会场馆周围超市设计 目标：经济效益最大化，各个区域的平衡问题目标：经济效益最大化，各个区域的平衡问题 05 05年年 B B题：题：DVDDVD在线租赁在线租赁 目标：满足顾客的需要，经济效益最大化目标：满足顾客的需要，经济效益最大化 06 06年年 A A题：出版社书号分配问题题：出版社书号分配问题 目标：经济效益最大化，不同学科书号的平衡问题目标：经济效益最大化，不同学科书号的平衡问题 07 07年年 B B题：北京公交线路设计题：北京公交线路设计 目标：时间最小化，车票钱最小化，转站最小化目标：时间最小化，车票钱最小化，转站最小化l0808年年 A A题：中国学费的评价系统题：中国学费的评价系统 目标：经济效益最大化，考虑到老百姓的支付能力目标：经济效益最大化，考虑到老百姓的支付能力 09 09年年 医院眼科病人的等待系统医院眼科病人的等待系统 目标：提高病床的周转率，降低病人的抱怨程度目标：提高病床的周转率，降低病人的抱怨程度04年 A题：奥运会场馆周围超市设计17优化模型的一般形式优化模型的一般形式x:决策变量决策变量 f(x):目标函数目标函数gi(x)0:约束条约束条件件可行解：满足约束条件的解可行解：满足约束条件的解最优解：取得最值的可行解最优解：取得最值的可行解次优解：一个较满意的可行解次优解：一个较满意的可行解可行集（域）：所有可行解组成的集合，可行集（域）：所有可行解组成的集合，优化模型的一般形式x:决策变量f(x):目标函数gi(x)18最优化问题至少有两要素：一是可能的最优化问题至少有两要素：一是可能的方案；二是要追求的目标。后者是前者的函方案；二是要追求的目标。后者是前者的函数。如果第一要素与时间无关就称为静态最数。如果第一要素与时间无关就称为静态最优化问题，否则称为动态最优化问题。优化问题，否则称为动态最优化问题。最优化问题至少有两要素：一是可能的方案；二是19建立最优化问题数学模型的三要素：建立最优化问题数学模型的三要素：（1）决策变量和参数。决策变量和参数。决策变量是由数学模型决策变量是由数学模型的解确定的未知数。参数表示系统的控制变量，有的解确定的未知数。参数表示系统的控制变量，有确定性的也有随机性的。确定性的也有随机性的。（2）约束或限制条件。约束或限制条件。由于现实系统的客观物由于现实系统的客观物质条件限制，模型必须包括把决策变量限制在它们质条件限制，模型必须包括把决策变量限制在它们可行值之内的约束条件，而这通常是用约束的数学可行值之内的约束条件，而这通常是用约束的数学函数形式来表示的。函数形式来表示的。建立最优化问题数学模型的三要素：20 一般的模型简化工作包括以下几类：一般的模型简化工作包括以下几类：（1）将离散变量转化为连续变量。）将离散变量转化为连续变量。（2）将非线性函数线性化。）将非线性函数线性化。（3）删除一些非主要约束条件。）删除一些非主要约束条件。（3）目标函数。目标函数。这是作为系统决策变量的这是作为系统决策变量的一个数学函数来衡量系统的效率，即系统追一个数学函数来衡量系统的效率，即系统追求的目标。求的目标。一般的模型简化工作包括以下几类：（3）目标函数。这是作21l线性规划线性规划(LP)l非线性规划非线性规划(NLP)l整数规划整数规划(IP)主要内容主要内容主要内容22线性规划线性规划1、概念和实例。、概念和实例。2、线性规划模型、线性规划模型3 3、线性规划的性质。、线性规划的性质。4 4、线性规划的主要算法。、线性规划的主要算法。5、用数学软件包求解线性规划问题、用数学软件包求解线性规划问题6、建模案例选讲：投资的收益与风险、建模案例选讲：投资的收益与风险线性规划1、概念和实例。23线性规划：就是一个线性函数在线性等式或不等式线性规划：就是一个线性函数在线性等式或不等式约束条件下的极值问题。约束条件下的极值问题。线性规划研究的问题主要有两类：线性规划研究的问题主要有两类：1、任务确定后，如何统筹安排，尽量做到用、任务确定后，如何统筹安排，尽量做到用尽量少的人力和物力资源来完成任务；尽量少的人力和物力资源来完成任务；2、有一定量的人力、物力资源，如何安排使、有一定量的人力、物力资源，如何安排使用他们，使完成的任务（创造的利润）最多。用他们，使完成的任务（创造的利润）最多。在生产管理和经济活动中经常提出这样一类问在生产管理和经济活动中经常提出这样一类问题，题，即如何合理地利用有限的人力、物力、财力即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。等资源，以便得到最好的经济效果。线性规划：就是一个线性函数在线性等式或不等式约束条件下的极值24l线性规划的数学模型有三要素，从实际问线性规划的数学模型有三要素，从实际问题提炼成数学模型时，首先寻找需求解的题提炼成数学模型时，首先寻找需求解的未知量未知量xj(j=1,n)，然后列举三要素：，然后列举三要素：1.列写与自变量（未知量）有关的若干个线列写与自变量（未知量）有关的若干个线性约束条件（等式或不等式）。性约束条件（等式或不等式）。2.列写自变量列写自变量xj取值限制（取值限制（xj0，xj0或不或不限）。限）。3.列写关于自变量的线性目标函数值（极大列写关于自变量的线性目标函数值（极大值或极小值）。值或极小值）。l其中，前两条称为可行条件，最后一条称其中，前两条称为可行条件，最后一条称为优化条件。符合这三个条件的数学模型为优化条件。符合这三个条件的数学模型通常称为线性规划的一般型（通常称为线性规划的一般型（general）。）。线性规划的数学模型有三要素，从实际问题提炼成数学模型时，首先25例例1：某厂每日某厂每日8小时的产量不低于小时的产量不低于1800件。为了进行质量控制，件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度计划聘请两种不同水平的检验员。一级检验员的标准为：速度25件件/小时，正确率小时，正确率98%，计时工资，计时工资4元元/小时；二级检验员的小时；二级检验员的标准为：速度标准为：速度15小时小时/件，正确率件，正确率95%，计时工资，计时工资3元元/小时。小时。检验员每错检一次，工厂要损失检验员每错检一次，工厂要损失2元。为使总检验费用最省，元。为使总检验费用最省，该工厂应聘一级、二级检验员各几名？该工厂应聘一级、二级检验员各几名？解：解：设需要一级和二级检验员的人数分别为设需要一级和二级检验员的人数分别为x1、x2人人,则应付检验员的工资为：则应付检验员的工资为：因检验员错检而造成的损失为：因检验员错检而造成的损失为：例1：某厂每日8小时的产量不低于1800件。为了进行质量控制26故目标函数为：故目标函数为：约束条件为：约束条件为：故目标函数为：约束条件为：27线性规划模型：线性规划模型：线性规划模型：28某车间有甲、乙两台机床，可用于加工三种工件。假定这两某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为台车床的可用台时数分别为800和和900，三种工件的数量分别，三种工件的数量分别为为400、600和和500，且已知用三种不同车床加工单位数量不同，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？工任务，才能既满足加工工件的要求，又使加工费用最低？例例2：任务分配问题：任务分配问题某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的29解：解：设在甲车床上加工工件设在甲车床上加工工件1、2、3的数量分别为的数量分别为x1、x2、x3，在乙车床上加工工件在乙车床上加工工件1、2、3的数量分别为的数量分别为x4、x5、x6。可建立以下线性规划模型可建立以下线性规划模型：解：30例例3:饮食问题饮食问题l每人每天食用的食品中含有各种必需的营养素，每人每天食用的食品中含有各种必需的营养素，家庭主妇面临着一种抉择：如何采购食品，才能家庭主妇面临着一种抉择：如何采购食品，才能在保证必需营养素最低需求量前提下花钱最少？在保证必需营养素最低需求量前提下花钱最少？l这是典型的线性规划问题。这是典型的线性规划问题。设有设有n种食品供选择，种食品供选择，m种营养素应保证一定量。令：种营养素应保证一定量。令：xj每天食用的每天食用的j种食品数量种食品数量 cj单位单位j种食品的价格种食品的价格 aij单位单位j 种食品含有种食品含有i种营养素数量种营养素数量 bi每天对营养每天对营养i的最低需求量的最低需求量例3:饮食问题31针对问题特点针对问题特点,可列写线性规划数学模型如下：可列写线性规划数学模型如下：(最低营养需求约束最低营养需求约束)(自变量约束，食品量不会为负自变量约束，食品量不会为负)(目标函数，使购食品费用取最小值目标函数，使购食品费用取最小值（i=1,2,m;j=1,2,n）针对问题特点,可列写线性规划数学模型如下：32例例4:Chebyslev近似近似给出一组方程给出一组方程l其中，其中，mn，希求一组近似解希求一组近似解x1，x2,xn使误差使误差尽量小。即求出一组解，使之代入方程组中，造成不尽量小。即求出一组解，使之代入方程组中，造成不满足约束的方程的最大误差量尽量小。这是长期以来满足约束的方程的最大误差量尽量小。这是长期以来被认为必存在的这样一个解而又很难找到解的问题，被认为必存在的这样一个解而又很难找到解的问题，然而用线性规划求解却比较方便。下面就讨论如何建然而用线性规划求解却比较方便。下面就讨论如何建立该问题的线性规划数学模型。立该问题的线性规划数学模型。设：设：例4:Chebyslev近似33l则问题变为求出一组则问题变为求出一组xj(j=1,2,n)使使尽量小，于是变为：尽量小，于是变为：即：即：且令且令min为为统一标志，令统一标志，令x0，则上述问题变为则上述问题变为下述线形规划问题下述线形规划问题：则问题变为求出一组 xj(j=1,2,n)使尽量小34自变量约束：自变量约束：x0 0，xj不限（不限（j=1,2,n）目标函数：目标函数：x0min自变量约束：x00，xj不限（j=1,2,n）35o从上面例子中看出，列写线性规划数学模从上面例子中看出，列写线性规划数学模型的关键步聚为：型的关键步聚为：根据问题性质，找出需求解的变量，即自根据问题性质，找出需求解的变量，即自变量。变量。根据问题的限制因素或条件，列出自变量根据问题的限制因素或条件，列出自变量的取值限制及与自变量有关的线性约束条的取值限制及与自变量有关的线性约束条件（等式约束或不等式约束）。件（等式约束或不等式约束）。根据问题的目标要求，列出自变量有关的根据问题的目标要求，列出自变量有关的线性目标函数（极大值或极小值）。线性目标函数（极大值或极小值）。从上面例子中看出，列写线性规划数学模型的关键步聚为：36线性规划的标准形式：线性规划的标准形式：2.2.线性规划的模型线性规划的模型线性规划的模型结构：线性规划的模型结构：目标函数：目标函数：约束变量：约束变量：变量符号：变量符号：目标函数：目标函数：约束变量：约束变量：变量符号：变量符号：线性规划的标准形式：2.线性规划的模型线性规划的模型结构：373.线性规划的性质线性规划的性质l线性规划的可行域是凸集线性规划的可行域是凸集l线性规划可能有解、无解或无有限的最优解线性规划可能有解、无解或无有限的最优解l线性规划的最优解在极点线性规划的最优解在极点(顶点顶点)上上凸集：对区域凸集：对区域D中的任意两个元素中的任意两个元素x,y 和人意和人意的非负数的非负数0a 1,元素元素ax+(1-a)y也在区域也在区域D中。中。3.线性规划的性质线性规划的可行域是凸集凸集：对区域D中38线性规划是最优化方法发展最迅速，成就最大的线性规划是最优化方法发展最迅速，成就最大的线性规划是最优化方法发展最迅速，成就最大的线性规划是最优化方法发展最迅速，成就最大的一个分支，线性规划发展的爆炸时期是一个分支，线性规划发展的爆炸时期是一个分支，线性规划发展的爆炸时期是一个分支，线性规划发展的爆炸时期是2020世纪世纪世纪世纪5050年代至年代至年代至年代至6060年代，其奠基人应是苏联数学家年代，其奠基人应是苏联数学家年代，其奠基人应是苏联数学家年代，其奠基人应是苏联数学家CantolovchCantolovch和美国数和美国数和美国数和美国数学家学家学家学家G.B.DanfzigG.B.Danfzig。19471947年年年年DantzigDantzig提出了轰动数学界的单纯形法，为提出了轰动数学界的单纯形法，为提出了轰动数学界的单纯形法，为提出了轰动数学界的单纯形法，为求解多维线性规划问题提供了一般的有效的工具；求解多维线性规划问题提供了一般的有效的工具；求解多维线性规划问题提供了一般的有效的工具；求解多维线性规划问题提供了一般的有效的工具；1950-19651950-1965年匈牙利的两位数学家年匈牙利的两位数学家年匈牙利的两位数学家年匈牙利的两位数学家H.W.KuhnH.W.Kuhn和和和和A.W.TuckerA.W.Tucker建立了线性规划的对偶理论，为求结鞍点建立了线性规划的对偶理论，为求结鞍点建立了线性规划的对偶理论，为求结鞍点建立了线性规划的对偶理论，为求结鞍点问题提供了数学工具，两位年轻的数学家建立了约束极问题提供了数学工具，两位年轻的数学家建立了约束极问题提供了数学工具，两位年轻的数学家建立了约束极问题提供了数学工具，两位年轻的数学家建立了约束极值的最优形条件，称为值的最优形条件，称为值的最优形条件，称为值的最优形条件，称为K-TK-T条件。为求解非线性规划奠条件。为求解非线性规划奠条件。为求解非线性规划奠条件。为求解非线性规划奠定了理论基础；定了理论基础；定了理论基础；定了理论基础；4.4.线性规划的算法线性规划的算法 线性规划是最优化方法发展最迅速，成就最大的一3919581958年年年年美国数学家美国数学家美国数学家美国数学家R.E.GomeryR.E.Gomery提出整数规划的割平面法；提出整数规划的割平面法；提出整数规划的割平面法；提出整数规划的割平面法；19601960年年年年RantzigandP.WolfeRantzigandP.Wolfe研究成功线性规划的分解算法，研究成功线性规划的分解算法，研究成功线性规划的分解算法，研究成功线性规划的分解算法，该算法为求解大规模线性规划提供了强有力的工具；该算法为求解大规模线性规划提供了强有力的工具；该算法为求解大规模线性规划提供了强有力的工具；该算法为求解大规模线性规划提供了强有力的工具；19791979年年年年-1984-1984年苏联数学家年苏联数学家年苏联数学家年苏联数学家L.G.KhachiyanL.G.Khachiyan和美国数学家和美国数学家和美国数学家和美国数学家N.A.KarmarkaN.A.Karmarka先后提出并完成了线性规划的多项式算法轰先后提出并完成了线性规划的多项式算法轰先后提出并完成了线性规划的多项式算法轰先后提出并完成了线性规划的多项式算法轰动了整个数学界动了整个数学界动了整个数学界动了整个数学界。1958年美国数学家R.E.Gomery提出整数规划的割平面40线性规划的主要算法线性规划的主要算法l单纯形法（单纯形法（19471947年美国年美国Dantzig）修正单纯形法，对偶单纯形法。非多项式时间方法，修正单纯形法，对偶单纯形法。非多项式时间方法，对中小规模问题非常有效，应用广泛对中小规模问题非常有效，应用广泛。l椭球方法（椭球方法（1979年苏联年苏联L.G.Khachiyan）多项式时间方法，理论价值高，不常用，效果不理想。多项式时间方法，理论价值高，不常用，效果不理想。时间复杂度为时间复杂度为lKarmarkar方法方法（1984美国美国N.A.Karmarka）内点方法，多项式时间方法，理论价值高，有效，时间内点方法，多项式时间方法，理论价值高，有效，时间复杂度为复杂度为，对大规模问题也十分有效对大规模问题也十分有效.线性规划的主要算法单纯形法（1947年美国Dantzig）41单纯形法算法思想单纯形法算法思想 从一个可行域的某个顶点出发（从一个可行域的某个顶点出发（基本可行基本可行解解）出发，转换到另一个更好的顶点（）出发，转换到另一个更好的顶点（使目使目标函数值有所改善的基本可行解，通过不断标函数值有所改善的基本可行解，通过不断改进基本可行解改进基本可行解），最终达到目标函数最优），最终达到目标函数最优的顶点的顶点(求得问题的最优解求得问题的最优解)。单纯形法算法思想 从一个可行域的某个顶点出发（基本可42Karmarkar内点方法算法思想内点方法算法思想 通过射影变换把原问题转化为在球域上通过射影变换把原问题转化为在球域上极小化另一个线性函数。求出问题在球域极小化另一个线性函数。求出问题在球域上的最优解后，再用逆变换将该解返回到上的最优解后，再用逆变换将该解返回到原决策空间里去，从而得到原问题的近似原决策空间里去，从而得到原问题的近似解。重复以上过程，得到的点列在多项式解。重复以上过程，得到的点列在多项式时间内收敛于原问题的最优解时间内收敛于原问题的最优解.Karmarkar内点方法算法思想 通过射影变435.求解线性规划问题的算法软件lMatlab 可以求解任意规模的线性规划问题。可以求解任意规模的线性规划问题。lLingo 可以求解任意规模的线性规划问题，特可以求解任意规模的线性规划问题，特别是整数线性规划问题别是整数线性规划问题,但是不易得到功但是不易得到功能强大的版本能强大的版本.5.求解线性规划问题的算法软件Matlab44用用MATLAB优化工具箱解线性规划优化工具箱解线性规划1、模型：、模型：命令命令：x=linprog(c，A，b)2、模型、模型：命令：命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：注意：若没有不等式：存在，则令存在，则令A=，b=.用MATLAB优化工具箱解线性规划 1、模型：命令：x=453、模型、模型：命令：命令：1 x=linprog(c，A，b，Aeq,beq,VLB，VUB)2x=linprog(c，A，b，Aeq,beq,VLB，VUB,x0)注意：注意：1若没有等式约束若没有等式约束:,则令则令Aeq=,beq=.2其中其中x0表示初始点表示初始点3、模型：命令：注意：464、命令：、命令：x,fval=linprog()返回最优解返回最优解x及及x处的目标函数值处的目标函数值fval.注意：在注意：在注意：在注意：在linproglinprog函数中，其中有一选择函数中，其中有一选择函数中，其中有一选择函数中，其中有一选择“largescale”“largescale”，如果命令为，如果命令为，如果命令为，如果命令为“on”“on”，则表示利用大规模的线性规划算法，则表示利用大规模的线性规划算法，则表示利用大规模的线性规划算法，则表示利用大规模的线性规划算法求解，如果命令为求解，如果命令为求解，如果命令为求解，如果命令为“off”“off”，则表示利用中小规模的线性规，则表示利用中小规模的线性规，则表示利用中小规模的线性规，则表示利用中小规模的线性规划算法求解。求解大规模的线性规划利用的是划算法求解。求解大规模的线性规划利用的是划算法求解。求解大规模的线性规划利用的是划算法求解。求解大规模的线性规划利用的是KarmarkarKarmarkar内点方法内点方法内点方法内点方法，求解中小规模的线性规划利用的是，求解中小规模的线性规划利用的是，求解中小规模的线性规划利用的是，求解中小规模的线性规划利用的是一种修正的一种修正的一种修正的一种修正的单纯形法单纯形法单纯形法单纯形法4、命令：x,fval=linprog()注意：在li47数学建模规划模型讲解课件48解解:编写编写M文件文件xxgh1.m如下：如下：c=-0.4-0.28-0.32-0.72-0.64-0.6;A=0.010.010.010.030.030.03;0.02000.0500;00.02000.050;000.03000.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)解:编写M文件xxgh1.m如下：49数学建模规划模型讲解课件50解解:编写编写M文件文件xxgh2.m如下：如下：c=634;A=010;b=50;Aeq=111;beq=120;vlb=30,0,20;vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)解:编写M文件xxgh2.m如下：51S.t.改写为：例例3:问题一的解答S.t.改写为：例3:问题一的解答52编写编写M文件文件xxgh3.m如下如下:f=13 9 10 11 12 8;A=0.4 1.1 1 0 0 0 0 0 0 0.5 1.2 1.3;b=800;900;Aeq=1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1;beq=400 600 500;vlb=zeros(6,1);vub=;x,fval=linprog(f,A,b,Aeq,beq,vlb,vub)编写M文件xxgh3.m如下:53结果结果:x=0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval=1.3800e+004即在甲机床上加工即在甲机床上加工600个工件个工件2,在乙机床上加工在乙机床上加工400个个工件工件1、500个工件个工件3，可在满足条件的情况下使总加工，可在满足条件的情况下使总加工费最小为费最小为13800。结果:54例例4:问题二的解答问题二的解答改写为：改写为：例4:问题二的解答改写为：55编写编写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)编写M文件xxgh4.m如下：56结果为：结果为：x=9.0000 0.0000 fval=360即只需聘用即只需聘用9个一级检验员个一级检验员。注：注：本问题应还有一个约束条件：本问题应还有一个约束条件：x1、x2取整数。故它是一取整数。故它是一个整数线性规划问题。这里把它当成一个线性规划来解，个整数线性规划问题。这里把它当成一个线性规划来解，求得其最优解刚好是整数：求得其最优解刚好是整数：x1=9，x2=0，故它就是该整，故它就是该整数规划的最优解。若用线性规划解法求得的最优解不是数规划的最优解。若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解。样的整数规划应用专门的方法求解。结果为：注：57投资的收益和风险投资的收益和风险 投资的收益和风险58二、基本假设和符号规定二、基本假设和符号规定二、基本假设和符号规定59二、基本假设和符号规定二、基本假设和符号规定二、基本假设和符号规定60三、模型的建立与分析三、模型的建立与分析1.总体风险用所投资的Si中最大的一个风险来衡量,即 max qixi|i=1，2,n三、模型的建立与分析1.总体风险用所投资的Si中最大的一个风61三、模型的建立与分析三、模型的建立与分析三、模型的建立与分析624.模型简化模型简化：4.模型简化：63数学建模规划模型讲解课件64数学建模规划模型讲解课件65四、模型四、模型1 1的求解的求解 由于由于a是任意给定的风险度，到底怎样给定没有一个准是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从则，不同的投资者有不同的风险度。我们从a=0开始，以开始，以步长步长a=0.001进行循环搜索，编制程序如下进行循环搜索，编制程序如下：四、模型1的求解 66a=0;while(1.1-a)1 c=-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);a x=x Q=-val plot(a,Q,.)，axis(0 0.1 0 0.5)，hold on a=a+0.001;end xlabel(a),ylabel(Q)To Matlab（xxgh5）a=0;To Matlab（xxgh5）67计算结果：计算结果：计算结果：68五、五、结果分析结果分析3.3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。2 2.当投资越分散时，投资者承担的风险越小，这与题意一致。即:冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。1.1.风险大，收益也大。五、结果分析3.曲线上的任一点都表示该风险水平的最大可能收69精品课件精品课件！精品课件！70精品课件精品课件！精品课件！71返 回4 4.在a=0.006=0.006 附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是a*=0.6%，Q*=20%，所对应投资方案为:风险度 收益 x0 x1 x2 x3 x40.00600.201900.24000.40000.10910.2212返 回4.在a=0.006 附近有一个转折点，在这一点左边72