数学建模-优化部分

大学生数学建模竞赛张朝伦4/30/20241什么是数学建模？数学建模用数学去解决实际问题就一定要用数学的语言、方法去近似地刻划该实际问题，而这种刻划的数学表述就是一个数学模型，其过程就是数学建模的过程。“对现实的现象通过心智活动构造出能抓住重要且有特征的表示，常常是形象化的或符号的表示”4/30/20242数学建模是指对现实世界的一特定对象,为了某特定目的,做出一些重要的简化和假设,用适当的数学工具得到一个数学结构,用它来解释特定现象的现实性态,预测对象的未来状况,提供处理对象的优化决策和控制,设计满足某种需要的产品等。从科学，工程，经济，管理等角度看数学建模就是用数学的语言和方法，通过抽象，简化建立能近似刻画并“解决”实际问题的一种强有力的数学工具。顾名思义，modelling一词在英文中有“塑造艺术”的意思，从而可以理解从不同的侧面，角度去考察问题就会有不尽的数学模型，从而数学建模的创造又带有一定的艺术的特点。而数学建模最重要的特点是要接受实践的检验，多次修改模型渐趋完善的过程。4/30/20243大学生数学建模竞赛的由来

1985年在美国出现了一种叫做MCM的一年一度的大学生模型竞赛。以前只有一种大学生数学竞赛—普特南数学竞赛：是由美国数学协会主持于每年12月的第一个星期六分两试进行，每试6题，每试各为3小时。这是一个历史悠久、影响很大的全美大学生数学竞赛（1938年开始至今）。主要考核基础知识和训练、逻辑推理的能力、思维敏捷、计算能力等。4/30/20244为什么会产生另一种数学模型竞赛？1、参加普特南数学竞赛是要有训练的，而很多学校的参赛队员素质差、受训时间时间短、没有经验，因而成绩差，影响了积极性。2、相当多的学生对数学的实际应用有兴趣，因而对普特南数学竞赛缺乏积极性。3、为了反对现行高校数学教学中过份强调纯粹性、形式方法、缺乏应用内容的倾向。4、普特南数学竞赛不用计算机。5、数学有如下几个重要组成部分：应用数学、计算数学、统计数学、纯粹数学。4/30/20245MCM的宗旨、规则和奖励

宗旨：鼓励大学师生对范围并不固定的各种实际问题给予阐明、分析并提出解法，通过这样一种结构鼓励师生积极参与并强调实现完整的模型构造的过程

规则：每个参赛队（3人）有一名指导教师，他（或她）在比赛开始前负责对队员的训练和战术指导；并接受考题，然后即由自行参赛。指导教师不得参赛

比赛于每年二月或三月的某个周末（三天时间）。每次只有两个考题（一般4/30/20246连续和离散各一题），每队只需任选一题。

考题是由在政府部门或工业工作的数学家提出建义由命题组选择的没有固定范围的实际问题。一般来源于工程技术和管理科学等方面经过适当简化加工的实际问题，不要求参赛者预先掌握深入的专门知识，只需要学过普通高校的数学课程。题目有较大的灵活性供参赛者发挥其创造能力。参赛者应根据题目要求，完成一篇包括模型假设、建立和求解、计算方法的设计和计算机实现、结果的分析和检验、模型的改进等方面的论文（即答卷）。竞赛评奖以假设的合理性、建模的创造性、结果的正确性和文字表述的清晰程度为主要标准。

4/30/20247

MCM的发展历程

1985年第一届70所大学90个队到1992年189所大学292个队。

1989年我国开始组队参加，到92年国内有12所大学以致24个队参赛。

1989年我国开始组队参加，到92年国内有12所大学24个队参赛。上海市率先于1990年12月7—9日举办了“上海市大学生（数学类）数学建模竞赛”。于1991年6月7日—9日举办了“上海市大学生（非数学类）数学建模竞赛”。接下来是西安市。由中国工业与应用数学学会举办了“1992年全国大学生数学模型联赛”。CUMCM就这样诞生了

从1994年开始CUMCM被国家教委高教司确定为面向全国大学生的一项竞赛。4/30/20248数模竞赛是由美国工业与应用数学学会在1985年发起的一项大学生竞赛活动，目的在于激励学生学习数学的积极性，提高学生建立数学模型和运用计算机技术解决实际问题的综合能力，鼓励广大学生踊跃参加课外科技活动，开拓知识面，培养创精神及合作意识，推动大学数学教学体系、教学内容和方法的改革。我国大学生数学建模竞赛是由教育部高教司和中国工业与数学学会主办、面向全国高等院校的、每年一届的通讯竞赛。其宗旨是：创新意识、团队精神、重在参与、公平竞争。１９９２年在中国创办，自从创办以来，得到了教育部高教司和中国工业与应用数学协会的得力支持和关心，呈现出迅速的发展发展势头，就２００３年来说，报名阶段须然受到“非典”影响，但是全国３０个省（市、自治区）及香港的637所院校就有5406队参赛，在职业技术学院增加更快，

2005年的759所院校就有8492队参赛。2006年全国有31个省/市/自治区(包括香港)864所院校、9985个队（其中甲组7682队、乙组2303队）、近3万名来自各个专业的大学生参加竞赛，是历年来参赛人数最多的！可以说：数学建模已经成为全国高校规模最大课外科技活动。4/30/20249

建模的步骤

建模是一种十分复杂的创造性劳动，现实世界中的事物形形色色，五花八门，不可能用一些条条框框规定出各种模型如何具体建立，这里只是大致归纳一下建模的一般步骤和原则：

1）模型准备：首先要了解问题的实际背景，明确题目的要求，收集各种必要的信息．

2）模型假设：为了利用数学方法，通常要对问题做必要的、合理的假设，使问题的主要特征凸现出来，忽略问题的次要方面。

３）模型构成：根据所做的假设以及事物之间的联系，构造各种量之间的关系把问题化

4/30/202410４）模型求解：利用已知的数学方法来求解上一步所得到的数学问题，此时往往还要作出进一步的简化或假设。为数学问题，注意要尽量采用简单的数学工具。

５）模型分析：对所得到的解答进行分析，特别要注意当数据变化时所得结果是否稳定。

６）模型检验：分析所得结果的实际意义，与实际情况进行比较，看是否符合实际，如果不够理想，应该修改、补充假设，或重新建模，不断完善。

７）模型应用：所建立的模型必须在实际应用中才能产生效益，在应用中不断改进和完善。4/30/2024114/30/202412模型的分类按模型的应用领域分类

生物数学模型

医学数学模型

地质数学模型

数量经济学模型

数学社会学模型

按是否考虑随机因素分类

确定性模型

随机性模型按是否考虑模型的变化分类

静态模型

动态模型按应用离散方法或连续方法

离散模型

连续模型按建立模型的数学方法分类

几何模型

微分方程模型

图论模型

规划论模型

马氏链模型4/30/202413按人们对事物发展过程的了解程度分类

白箱模型：

指那些内部规律比较清楚的模型。如力学、热学、电学以及相关的工程技术问题。

灰箱模型：

指那些内部规律尚不十分清楚，在建立和改善模型方面都还不同程度地有许多工作要做的问题。如气象学、生态学经济学等领域的模型。

黑箱模型：

指一些其内部规律还很少为人们所知的现象。如生命科学、社会科学等方面的问题。但由于因素众多、关系复杂，也可简化为灰箱模型来研究。4/30/202414数学建模应用今天，在国民经济和社会活动的以下诸多方面，数学建模都有着非常具体的应用。

分析与设计

例如描述药物浓度在人体内的变化规律以分析药物的疗效；建立跨音速空气流和激波的数学模型，用数值模拟设计新的飞机翼型。

预报与决策

生产过程中产品质量指标的预报、气象预报、人口预报、经济增长预报等等，都要有预报模型。使经济效益最大的价格策略、使费用最少的设备维修方案，是决策模型的例子。

4/30/202415控制与优化

电力、化工生产过程的最优控制、零件设计中的参数优化，要以数学模型为前提。建立大系统控制与优化的数学模型，是迫切需要和十分棘手的课题。

规划与管理

生产计划、资源配置、运输网络规划、水库优化调度，以及排队策略、物资管理等，都可以用运筹学模型解决。4/30/202416大学生数学建模竞赛试题题目

85年：动物群体的管理战略物资储备问题

86年：对海底地型的插值选取两个应急设施的最优方案87年：盐堆稳定性问题停车场安排问题

88年：毒品走私船问题平板列车车厢的优化装载4/30/20241789年：最佳分类隔离飞机排队模型90年：脑中多巴胺的分布铲雪车的路径问题；铲雪效率问题91年：估计水塔的水流量寻找最优Steiner树92年：确定航空控制雷达系统的功效紧急修复系统的研制4/30/20241895年：一个飞行管理模型天车与冶炼炉的调度93年：混合物转化为有机肥的最隹过程煤炭装卸场的最优操作94年:逢山开路

锁具装箱4/30/20241997年：零件参数的设计截断切割98年：灾情巡视路线投资的收益与风险99年：自动化车床管理钻探布点96年：最优捕鱼策略节水洗衣机 4/30/2024202000年：DNA序列分类钢管订购和运输2001年：血管的三维重建公交车的调度2002年：车灯线光源的优化设计彩票中的数学2003年：关于sars控制和预测矿山车辆调度2004年：奥运会临时超市网点设计电力市场的输电阻塞管理4/30/2024212005年：长江水质的评价和预测

DVD在线租赁2006年：出版社的资源配置艾滋病疗法的评价及疗效的预测2007年：中国人口增长预测

乘公交，看奥运

2008年：数码相机定位高等教育学费标准探讨

4/30/202422分以下几个部分一、线性规划二、灵敏度分析三、动态规划四、图及网络五、多目标规划4/30/202423一、线性规划

1.线性规划问题的数学模型

2.两个变量问题的图解法

3.线性规划数学模型的标准形式及解的概念

3.1标准形式

3.2将非标准形式化为标准形式

3.3有关解的概念4/30/202424运筹学

OperationalResearch运筹帷幄，决胜千里

史记《张良传》4/30/202425目录绪论第一章线性规划问题及单纯型解法第二章线性规划的对偶理论及其应用第三章运输问题数学模型及其解法第四章整数规划第五章动态规划第六章图与网路分析第七章随机服务理论概论第八章生灭服务系统第九章特殊随机服务系统第十章存储理论4/30/202426绪论一、运筹学的起源与发展二、运筹学的特点及研究对象三、运筹学解决问题的方法步骤四、运筹学的发展趋势4/30/202427一、运筹学的起源与发展起源于二次大战的一门新兴交叉学科与作战问题相关如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深度、飞行员的编组、军事物资的存储等英国称为OperationalResearch美国称为OperationsResearch战后在经济、管理和机关学校及科研单位继续研究1952年，Morse和Kimball出版《运筹学方法》1948年英国首先成立运筹学会1952年美国成立运筹学会1959年成立国际运筹学联合会(IFORS)我国于1982年加入IFORS，并于1999年8月组织了第15届大会4/30/202428二、运筹学的特点及研究对象运筹学的定义为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法——Morse和Kimball运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测，比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策——英国运筹学会运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理——中国百科全书现代运筹学涵盖了一切领域的管理与优化问题，称为ManagementScience4/30/202429二、运筹学的特点及研究对象运筹学的分支数学规划：线性规划、非线性规划、整数规划、动态规划、目标规划等图论与网路理论随机服务理论：排队论存储理论决策理论对策论系统仿真：随机模拟技术、系统动力学可靠性理论金融工程4/30/202430三、运筹学解决问题的方法步骤明确问题建立模型设计算法整理数据求解模型评价结果明确问题建立模型设计算法整理数据求解模型评价结果简化？满意？YesNoNo4/30/202431四、运筹学的发展趋势运筹学的危机脱离实际应用，陷入数学陷阱IT对运筹学的影响MIS,DSS,MRP-II,CIMS,ERPORDept.-->Dept.OfOR&IS运筹学与行为科学结合群决策和谈判对策理论多层规划合理性分析服务行业中的应用金融服务业信息、电信服务业医院管理4/30/202432四、运筹学的发展趋势软计算面向强复杂系统的计算、实时控制、知识推理智能算法：模拟退火、遗传算法、人工神经网络、戒律算法等系统仿真面向问题后勤(Logistics)全球供应链管理电子商务：集成特性随机和模糊OR问题本身的不确定性人类知识的局限性4/30/2024331.2线性规划问题的单纯型解法1.2.1线性规划问题的标准形式为了使线性规划问题的解法标准，就要把一般形式化为标准形式4/30/202434(一)、运输问题例1、设某产品有m个产地A1,A2,…,Am,n个销地B1，B2，…,Bn。各产地的产量，各销地的销量以及各产地运往各销地的单位运价如下表,且设=.问在满足各地需求以及生命能力的情况下，如何调运使总运费最小。

4/30/202435

销地运价产地

B1B2...Bn产量A1c11c12

...c1na1A2c21c22

...c2na2

...

...

...

...

...

...Amcm1cm2

...

cmnam需求量b1b2

...

bn4/30/202436解设xij表示产地Ai运往销地Bj的数量，则可得线性规划模型如下：4/30/202437(二)、分派问题例设有工作m件，人员ｍ个,且一人做一件工作,第i人做j件工作的时间（或费用）为cij,，问如何分派这些人员使总时间（或费用）最少。解1，第i人做第j件工作，

设xij=0,否则

则得0-1规划：

4/30/202438(三)、网络问题

一个网络包括一些结点（用圆圈表示），每个结点由几条弧（用箭头表示）与其它结点相连，如图：

2154

20128915107

141081231364/30/202439最短路问题解：设1,有从i到期j的弧

xij=0,否则则得0-1规划：Minz=20x12+14x13+15x24+12x25+10x34+13x36+8x45+9x47+8x56+10x57+12x67(总路程）S.t.X12+x13=1(从1出发的汽车为一辆）-x12+x24+x25=0-x13+x34+x36=0-x24-x34+x45+x47=04/30/202440-x25-x45+x56+x57=0-x36-x56+x67=0-x47-x57-x67=-1（到达7的汽车为一辆）Xij=0,或1,i,j=1,2,…7.4/30/202441(四)、生产活动问题例：某公司有m种资源B1，B2，…，Bm(如机器的可用工时，劳力，原材料等），生产n种不同的产品A1，A2，．．．Ａn.其单位消耗，单位利润等如表．问如何安排生产使利润最大．解设xj表示第j种产品的产量，则可得线性规划模型：4/30/202442

产单品耗资源Ａ１，Ａ２，…,Ａn

资源量Ｂ１Ｂ２．．．Ｂma11a12…a1na21a22…a2n.....…...….am1am2…amn

b1b2...

bm单位利润

c1c2…cn4/30/202443注1若还要考虑固定成本，则需引入0–1变量。设第j种产品的固定成本为Mj，第j种产品的产量的上界为Lj引入0–1变量

0,生产第j种产品，

Yj=1，否则4/30/202444注2如果某些资源的使用是有选择的，即有些约束条件是互相排斥的，可引入0–1变量将其统一在同一模型中。如b1,b2为不同型号的两台机器的可用工时，而n种产品可在任一台上加工，这时第1，2两个约束条件就是互排斥的，只能选择一个进入模型。如果引入0–1变量4/30/202445

0,在型号i的机器上加工Yi=（i=1,2)1,否则则可以用下述条件来将它们统一同一个模型中：4/30/202446(五)、选址问题例、某公司拟定在东、西、南三区建立门市部，拟议中有7个地址A1，A2，…,A7可供选择，并规定：在东区，A1，A2，A3中至多选两个；在西区，A4，A5中至少选一个；在南区，A6，A7中至少选一个；若选Ai,投资bi元，每年可获利估计为ci元,总投资不超过b元.问如何选择门市部的地址公司的年利润最大.

4/30/202447解设1，选择Ai,xi=0，否则则得0-1规划模型：4/30/202448(六)、曲线拟合问题例已知变量y随变量x变化，并且已知一组观测值（xi,yi),I=1,2,…n.(1)拟合一条回归直线,使回归值与观察值的绝对偏差之和最小;(2)拟合一条回归直线,使回归值与观察值的最大偏差最小.4/30/202449解设所求回归直线方程为

y=a+bx(1)据题意，应求使最小的a,b。由于函数中带有绝对值，不便用数学分析方法来处理，但用线性规划方法来处理就变得较容易。令则得线性规划模型

4/30/202450模型中，xi,yi已知，ui,vi,a,b为决策变量。原问题化为含（2n+2)个决策变量，n个约束方程的一极小化问题。4/30/202451(七)、人员安排问题例某公司的营业时间是上午8点到22点，以两小时为一时段，各时段内所需的服务人员数如下表，每个服务人员可在任一时段开始上班，但要工作8小时，而工资都相同。问应如何安排服务人员使公司所付工资总数最少。4/30/202452序号时间区间需求人数1

8：00—10：00

202

10：00—12：00

25

3

12：00—14：00

10

4

14：00—16：00

30

5

16：00—18：00

20

6

18：00—20：00

10

7

20：00—22：00

54/30/202453解设xi为时段i开始工作的人数（i=1,2,3,4).由于各班工资相同，要求公司所付的工资最少也就是要求服务人员最少。于是可得整数规划模型：4/30/202454例某公司的营业时间是上午8点到21点。服务人员中途需要1小时吃饭和休息时间，每人的工作时间为8小时。上午8点到17点工作的人员月工资为800元，中午12点到21点工作的人员月工资为900元。为保证营业时间内都有人上班，公司安排了四个班次，其班次和休息时间安排如下表一。各时段需求的人数如上例之表，只是第6、7段合并为18点到21点，需求人数为10人。问应如何安排服务人员既满足需求又使公司所付工资总数最少。4/30/202455

表一班次工作时间休息时间月工资

18:00-17:0012:00-13:00

800

28:00-17:0013:00-14:00

800

312:00-21:0016:00-17:00

900

412:00-21:0017:00-18:00

9004/30/202456解为了便于建立模型，可用各班中途休息的起止时刻和上例之表中时间区间的起止时间分细，并求出各班工作的关联表，见表二。表中j列的“1”表示该班次在相应的时段内工作，“0”表示不工作。4/30/202457表二时段班次

1234需求人数

8:00-10:00

11002010:00-12:0011002512:00-13:000111

1013:00-14:0010111014:00-16:0011113016:00-17:0011012017:00-18:0000102018:00-21:000011104/30/202458设xi表示第i班安排的人数（i=1,2,3,4)，则可得整数规划模型：4/30/202459(八)、套裁下料问题例某车间接到制作100套钢架的定单，每套钢架要用长为2.9m,2.1m,1.5m的圆钢各一根，已知原料长7.4m。问应如何下料，可使所用原料最省解:可能截法

方法下料根数长度/m123456782.9211100002.1021032101.510130234合计料头7.30.17.10.36.50.97.406.31.17.20.26.60.66.01.44/30/202460

假设按方法1，2，…,8方式下料的原料根数分别为x1,x2,…,x8,则希望在得到长度为2.9m,2.1m,1.5m的圆钢各为100根的情况下，使总料头最小。模型为：4/30/202461(九)、生产工艺优化问题例某日化厂生产洗衣粉和洗涤剂。生产原料由市场提供：每kg5元，供应量无限制。该厂加工1kg原料可产出0.5kg普通洗衣粉和0.3kg普通洗涤剂。工厂还可以对普通洗衣粉和普通洗涤剂进行精加工。加工1kg普通洗衣粉可得0.5kg浓缩洗衣粉，加工1kg普通洗涤剂可产出0.25kg高级洗涤剂，加工示意图下图，市场售价为：每kg普通洗衣粉为8元；每kg浓缩洗衣粉为24元；每kg普通洗涤剂为12元；每kg高级洗涤剂为55元。每加工1kg原料的加工成本为1元，每1kg精加工产品的成本为3元，工厂设备每天最多可处理4t原料，而对精加工没有限制。若市场对产品也没有限制，问该厂应如何安排生产能使每日利润最大？4/30/202462

x1kg普通洗衣粉

0.5x0kg洗衣粉x2kg浓缩洗衣粉

X0kg原料x3kg普通洗涤剂

0.3x0kg洗涤剂x4kg高级洗涤剂4/30/202463解设每日生产普通洗衣粉的产量为x1kg

，生产浓缩洗衣粉x2kg，生产普通洗涤剂

x3kg

，生产高级洗涤剂x4kg，每日加工原料x0kg.

工厂利润Z应是每日的产品销售价减去原料成本与加工成本，故目标函数为：

约束条件为加工过程中物流的平衡约束及原料供应限制：4/30/202464

整理化简并加上非负约束条件可得数学模型：4/30/202465(十)、有配套约束的资源优化问题例某公司计划用资金60万来购买A，B，C三种运输汽车。已知A种汽车每辆为1万元，每班需一名司机，可完成每公里2100吨。B种汽车每辆为2万元，每班需两名司机，可完成每公里3600吨。C种汽车每辆为2.3万元，每班需两名司机，可完成每公里3780吨。每辆汽车每天最多安排三班，每个司机每天最多安排一班。购买汽车数量不超过30辆、司机不超过145人。问：每种汽车应购买多少辆，可使公司今后每天可完成的公里吨数最大？4/30/202466解设购买A种汽车中，每天只安排一班的有x11辆，每天安排二班的有x12辆，每天安排三班的有x13辆；同样设购买B种汽车依次有x21,x22,x23辆;购买C种汽车依次有x31,x32,x33辆.因此有4/30/202467(十一)、多周期动态生产计划问题例某柴油机厂接到今年1至4季度柴油机生产订单分别为：3000台，4500台，3500台，5000台。该厂每季度正常生产量为3000台，若加班可多生产1500台，正常生产成本为每台5000元，加班生产还要追加成本每台1500元。库存成本为每台每季度200元，问该柴油机厂该如何组织生产才能使生产成本最低？4/30/202468解设xi1为第i个季度正常生产的柴油机台数，xi2为第i个季度加班生产的柴油机台数，xi3为第i个季度初库存数。i=1,2,3,4.第一季度初及年底的库存数均产零，若记di为第i季度的需求量；c1,c2,c3分别为正常生产、加班生产、库存（每季度）每台柴油机的成本。则其数学模型为：代入具体数据，得数学模型如下：4/30/2024694/30/202470(十二)、投资问题投资者经常会遇到投资项目的组合选择问题，要考虑的因素有收益率、风险、增长潜力等条件，并进行综合权衡，以求得一个最佳投资方案。例某投资公司有50万元可用于长期投资，可供选择的投资项目包括购买国库券、购买公司债券、投资房地产、购买股票、银行短期或长期储蓄。各种投资方式的投资期限，年收益率，风险系数，增长潜力的具体参数见下表。若投资者希望投资组合的平均年限不超过5年，平均的期望收益率不低于13%，风险系数不超过4，收益的增长潜力不低于10%。问在满足上述要求前提下，投机者该如何选择投资组合使平均年平均收益率最高？4/30/202471序号投资方式投资期限（年）年收益率(%）风险系数增长潜力(%）1国库券311102公司债券10153153房地产6258304股票2206205短期储蓄110156长期储蓄5122104/30/202472解设xi为第i种投资方式在总投资中所占的比利,则该数学模型为:4/30/202473例某投资者有资金10万元,考虑在今后5年内给下列4个项目进行投资,已知:

项目A：从第1年到第4年每年年初需要投资，并于次年末回收本利115%.

项目B:第3年初需要投资,到第5年末能回收本利125%,但规定投资额不超过4万元项目C:第2年初需要投资,到第5年末能回收本利140%,但规定最大投资额不超过3万元.

项目D:5年内每年初可购买公债,于当年亩归还,并加利息6%.

问该投资者应如何安排他的资金,确定给这些项目每年的投资额,使到第5年末能拥有的资金本利总额为最大?4/30/202474解记xiA,xiB,xiC,xiD(i=1,2,…5)分别表示第i年初给项目A,B,C,D的投资额,它们都是决策变量,为了便于书写数学模型,列表如下:

年份项目

1

2

3

4

5AX1AX2AX3AX4ABX3BCX2CDX1DX2DX3DX4DX5D4/30/202475根据项目A，B，C，D的不同情况，在第5年末能收回的本利分别为：1.15x4A,1.25x3B,1.40x2C,及1.06x5D。因此目标函数为：

maxz=1.15x4A+1.25x3B+1.40x2C+1.06x5D.约束条件是每年年初的投资额等于该投资者年初所拥有的资金。第1年年初该投资者拥有10万元资金，故有

x1A+x1D=10000.

第2年年初该投资者手中拥有资金只有（1+6%）x1D,故有

x2A+x2C+x2D=1.06x1D.

第3年年初该投资者拥有资金从D项目收回的本金：1.06x2D,及从项目A中第1年投资收回的本金：1.15x1A,4/30/202476故有

x3A+x3B+x3D=1.15x1A+1.06x2D.同理第4年、第5年有约束为：

X4A+X4D=1.15X2A+1.06X3D,X5D=1.15X3A+1.06X4D.故本例数学模型经化间后为maxz=1.15x4A+1.25x3B+1.40x2C+1.06x5D

x1A+x1D=10000x2A+x2C+x2D=1.06x1D

x3A+x3B+x3D=1.15x1A+1.06x2DX4A+X4D=1.15X2A+1.06X3DX5D=1.15X3A+1.06X4D

xiA,XiB,xiC,XiD>=0(I=1,2,3,4,5)

4/30/2024771线性规划问题及数学模型1.1问题的提出(见前述模型)1.2线性规划问题的数学模型4/30/202478

1、和式4/30/202479

3、矩阵式4/30/202480

1.1.3线性规划的图解法f(x)=364/30/202481

线性规划问题的几个特点：线性规划问题的可性解的集合是凸集线性规划问题的基础可行解一般都对应于凸集的极点凸集的极点的个数是有限的最优解只可能在凸集的极点上，而不可能发生在凸集的内部4/30/202482

1.2.2单纯型法的基本思路4/30/202483

1.2.3单纯型表及其格式4/30/202484

例1.2.2试列出下面线性规划问题的初始单纯型表4/30/2024851.2线性规划问题的单纯型解法1.2.1线性规划问题的标准形式为了使线性规划问题的解法标准，就要把一般形式化为标准形式4/30/202486

1.2.3单纯型表及其格式4/30/202487变换的方法：目标函数为min型，价值系数一律反号。令f

(x)=-f(x)=-CX,有minf(x)=-max[-

f(x)]=-maxf(x)第i个约束的bi

为负值，则该行左右两端系数同时反号，同时不等号也要反向第i个约束为型，在不等式左边增加一个非负的变量xn+i

，称为松弛变量；同时令cn+i

=0第i个约束为型，在不等式左边减去一个非负的变量xn+i

，称为剩余变量；同时令cn+i

=0若xj

0，令

xj=-xj

，代入非标准型，则有xj

0若xj

不限，令

xj=xj

-

xj

，

xj

0，xj

0，代入非标准型4/30/202488

1.2.2单纯型法的基本思路4/30/202489

1.2.3单纯型表及其格式4/30/202490例1.2.2试列出下面线性规划问题的初始单纯型表4/30/202491

关于检验数的数学解释设

B

是初始可行基，则目标函数可写为两部分(1)约束条件也写为两部分，经整理得XB的表达式(2)，注意XB中含有非基变量作参数把XB代入目标函数，整理得到(3)式第j

个非基变量的机会成本如(4)式若有cj

zj>0,则未达到最优4/30/202492表1.2.4例1.2.2单纯型表的迭代过程答：最优解为x1=20,x2=20,x3=0,OBJ=17004/30/202493

单纯型表中元素的几点说明任何时候，基变量对应的列都构成一个单位矩阵当前表中的b

列表示当前基变量的解值，通过变换B

1b

得到(资源已变成产品)当前非基变量对应的向量可通过变换B

1AN

得到，表示第j

个变量对第i

行对应的基变量的消耗率非基变量的机会成本由给出注意基变量所对应的行4/30/202494表1.3.1例1.3.1的单纯型表迭代过程答：最优解为x1=2,x2=2,x3=0,OBJ=364/30/202495从图解法作图结果来分析,线性规划应有以下几种可能出现的结果:(1)有唯一最优解(2)有无穷多最优解(3)无界解(也称无最优解)4/30/2024962.4线性规划的对偶理论及其应用窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象4/30/2024972.4.1对偶问题的提出例1、某工厂生产甲、乙两种产品，每件产品的利润、所消耗的材料、工时及每天的材料限额如下表，试问如何安排生产，使每天所得利润最大？设每天生产甲、乙两种产品分别为x1件,x2件甲乙

限额材料工时23322426利润

434/30/202498现在从另一种角度来讨论.假设工厂考虑不安排生产,而是出售材料,出租工时,部如何定价,可使工厂获利不低于安排生产所获得的收益,且又能使这些定价具有竞争力?设出售材料的定价为每单位y1元,出租工时定价为每工时y2元,从工厂考虑,这些定价的获利不应低于安排生产所获得的收益,否则工厂宁愿生产,而不出售和出租.由此,工厂生产一件单产品所消耗的材料和工时的总价值不低于4元,即有同样,从乙产品考虑,亦有为使这些定价有竞争力,目标函数为4/30/202499综合起来,该问题的数学模型为:4/30/2024100任何线性规划问题都有其对偶问题对偶问题有其明显的经济含义假设有商人要向厂方购买资源A和B，问他们谈判原料价格的模型是怎样的？4/30/2024101例2设A、B资源的出售价格分别为y1

和

y2显然商人希望总的收购价越小越好工厂希望出售资源后所得不应比生产产品所得少目标函数ming(y)=25y1+15y24/30/2024102

2.4.2线性规划原问题与对偶问题的表达形式

1.对称形式的对偶问题4/30/2024103见问题提出4/30/2024104原规划(LP)对偶规划(DP)4/30/2024105

对称形式的两个互为对偶问题进行比较可以看出:目标函数由max型变为min型对应原问题每个约束行有一个对偶变量yi，i=1,2,…,m对偶问题约束为型，有n

行原问题的价值系数C

变换为对偶问题的右端项原问题的右端项

b变换为对偶问题的价值系数原问题的技术系数矩阵A转置后成为对偶问题的技术系数矩阵矩阵原问题与对偶问题互为对偶对偶问题可能比原问题容易求解对偶问题还有很多理论和实际应用的意义4/30/2024106

xjyj

x1x2

…

xn原关系minW

y1y2

ym

a11a12…

a1n

a21a22.…

a2n

am1am2…

amn

≤≤

≤b1b1

b1

对偶关系≥≥…≥maxZ

c1c2

…

cn这些关系可用下表表示：4/30/20241072.非对称形式的对偶问题设线性规划问题由于（1）故（1）可改写为4/30/2024108从而对偶问题为：即：又令显然Y无约束，得（1）对偶问题：4/30/2024109表2.13对偶变换的规则约束条件的类型与非负条件对偶非标准的约束条件类型对应非正常的非负条件对偶变换是一一对应的4/30/2024110

非对称形式的对偶问题4/30/2024111例2试求下述问题的对偶问题：（1）（2）4/30/2024112解的对偶规划为：（1）4/30/2024113（2）的对偶规划为：4/30/2024114二、灵敏度分析线性规划是静态模型参数发生变化，原问题的最优解还是不是最优哪些参数容易发生变化C,b,A每个参数发生多大的变化不会破坏最优解灵敏度越小，解的稳定性越好4/30/2024115

1.边际值(影子价)qi以(max,)为例边际值(影子价)qi

是指在最优解的基础上，当第i

个约束行的右端项bi

减少一个单位时，目标函数的变化量4/30/2024116例14/30/2024117影子价格的说明影子价是资源最优配置下资源的理想价格，资源的影子价与资源的紧缺度有关松弛变量增加一个单位等于资源减少一个单位剩余变量增加一个单位等于资源增加一个单位资源有剩余，在最优解中就有对应松弛变量存在，且其影子价为0影子价为0，资源并不一定有剩余应用，邮电产品的影子价格4/30/2024118

2价值系数cj

的灵敏度分析cj

变动可能由于市场价格的波动，或生产成本的变动cj

的灵敏度分析是在保证最优解的基变量不变的情况下，分析cj

允许的变动范围

cj

cj

的变化会引起检验数的变化，有两种情况非基变量对应的价值系数变化，不影响其它检验数基变量对应的价值系数变化，影响所有非基变量检验数1、非基变量对应的价值系数的灵敏度分析4/30/2024119例24/30/20241202、基变量对应的价值系数的灵敏度分析由于基变量对应的价值系数在CB中出现，因此它会影响所有非基变量的检验数只有一个基变量的cj

发生变化，变化量为cj

令cj

在CB中的第k行，研究非基变量xj

机会成本的变化4/30/2024121设x4的价值系数增加

c4，对应k=2，

有一边为空集如何处理

为什么akj=0不出现在任何一边的集合中

与对偶单纯型法找入变量的公式一样4/30/2024122

3.右端项bi的灵敏度分析设XB=B

1b是最优解，则有XB=B

1b0b的变化不会影响检验数b的变化量

b可能导致原最优解变为非可行解4/30/2024123

4.右端项bi的灵敏度分析4/30/2024124以b2为例,x6是对应的初始基变量，所以有4/30/2024125

5.技术系数aij

的灵敏度分析技术系数aij变化的影响比较复杂对应基变量的aij

，且资源bi已全部用完对应基变量的aij

，但资源bi未用完对应非基变量的aij

，且资源bi全用完或未用完1、对应基变量的aij

，且资源bi已全部用完

aij=02、对应基变量的aij

，但资源bi未用完

aij

xn+i

/xj上述两个公式不充分，为什么？B–1发生变化，从而引起非基变量检验数cj–zj

的变化3、对应非基变量的aij只影响对应非基变量xj的检验数

cj–zj

若aij>0，不会破坏最优解若aij<0，必须保证cj–zj

04/30/20241264/30/2024127x1,x3为非基变量，q1=0,q2=0.25,q3=1,故有x2,x4为基变量，x5=100,b1有剩余，故有4/30/2024128

6.新增决策变量的分析例2.4.2中，若新增产品x8，问是否生产？已知c8=9,a18=5,a28=4,a38=3计算x8的检验数可知生产是否有利结论：生产x8有利。将B–1P8加入最优单纯型表中，以x8为入变量进行迭代4/30/2024129

7.新增约束条件的分析1、将最优解代入新的约束条件，若满足，则最优解不变2、若不满足，则当前最优解要发生变化；将新增约束条件加入最优单纯型表，并变换为标准型3、利用对偶单纯型法继续迭代为什么可以利用对偶单纯型法例2.4.2第2步4/30/20241304/30/2024131注意：最优解的目标函数减少了25个单位4/30/2024132

8灵敏度分析举例例3某工厂生产三种产品A,B,C，有五种生产组合方案。下两表给出有关数据。规定每天供应A产品至少110个，求收益最大的生产方案。4/30/2024133例4解：设xj为已选定各种组合方案的组数(j=1,2,…,5)，x6为A产品的剩余变量，x7，x8分别为工人工时和机器工时的松弛变量。4/30/2024134

最优解的B–1是什么产品A的影子价为多少第II组方案的生产费用提高2元，是否要调整生产组别若工人加班费为1元/小时，是否要采取加班措施若通过租借机器增加工时，租费的上限应为多少A产品的订购合同是否有利若要选用第IV组方案，该组的生产费用应降低多少若工人加班费为0.3元/小时，最多允许加班时间多少若机器租费低于44元/小时，问租几部机器才合适(每天8小时计)若第III组方案使机器工时减少0.5小时，能否被选入4/30/20241357.参数线性规划2.4

节中

aij,bi,cj

只有一个发生变化，多个同时发生变化则很难解析但在一些特殊情况下，用参数表示变化量，也可以用来进行多个系数的灵敏度分析

2.5.1参数cj的变化分析

i

第i种资源的单位费用变化量，

i

不限

i

i变化对cj

的影响率4/30/2024136

例5资源b1变化量

1，

j=a1j4/30/2024137例6资源b1变化量

1与

c54/30/2024138

9

参数bi的变化分析例2.4.2中，将b1,b2,b3理解为三个车间的周工时资源。假设从第1向2车间调动工人

个，每个工人的周工时为40小时，问调动多少工人不会破坏最优产品组合4/30/2024139三、动态规划有许多决策过程是多阶段的，即动态的，动态规划就是一类多阶段决策过程的最优化方法。一、动态规划的基本概念和基本原理例最短路问题。下图给出了一路线网络，箭杆旁的数字为两点间的路程。现求从A到E的最短路。

A到E有3×3×2×1=18条不同的路线，如果阶段数增加，则路的条数也增加，用穷举法显然不可取，而用动态规划方法只需计算其中一部分便可求A到E的最短路线，并且还可得出任何一点到终点F的最短路线。4/30/2024140AB1B2B3C1C2C3D1D2E243763244151463333343447611748114/30/2024141阶段：根据时间和空间将问题划分成若干个互相有关联的阶段，用k表示阶段变量，n表示总的阶段数。状态：某阶段出发的位置。它既是该段某支路的起点，又是前一段某支路的终点。通常一个阶段包含若干个状态。如上题中四个阶段的状态集合分别为{A}，{B1，B2，B3}，{C1，C2，C3}，{D1，D2}

描述状态的变量称为状态变量，记为sk.决策：当阶段和状态给定后，从该状态到下一阶段某状态的选择。描述决策的变量称为决策变量，记为xk或x(sk)，它表示第k阶段处于状态sk时采取的决策，是状态sk的函数。决策变量的取值范围称为允许决策集合，记为Xk

或X(Sk)，即xk∈Xk.4/30/2024142状态转移方程：描述状态转移规律的函数关系

sk=T(sk,xk)当sk和xk取定后，sk+1的取值就随之确定。策略：各阶段所确定的决策构成的决策序列。即

{x1(s1),x2(s2),…,xn(sn)}

目的是从众多的策略中选择最优策略，记为

{x1*(s1),x2*(s2),…,xn*(sn)}4/30/2024143报酬函数：当过程处于状态sk，采取决策xk时所得的报酬（或费用），通常记为vk(sk,xk)。上例中的vk为第k阶段到k+1阶段两点间的路程。目标（指标）函数：衡量策略好坏的函数从第k阶段的sk出发到终点的目标函数记为

vkn=vkn(sk,xk,…xn),最优目标函数值记为

fk*(sk)=optvkn(sk,xk,…xn)，上例是求f1*(A)对应的策略4/30/2024144最优化原理：从上例看出，

AB2C1D1E是A到E的最短路线，则

B2C1D1E是B2出发到E的最短路。

C1D1E是C1出发到E的最短路。

4/30/2024145即作为整个过程的最优策略具有如下性质：无论过去的状态和决策如何，对前面所形成的某确定状态而言，余下的决策必须构成最优子策略。利用此原理，可以把多阶段决策问题的求解过程看成是一个连续的递推过程，由后向前逐步推算。这相当于把原问题划成了许多相互联系的比原问题简单的子问题，在求解每个子问题时，均利用它的后部子问题的最优结果，依次从后向前推进，最后一个子问题的解就是原问题的最优解。4/30/2024146第4阶段：得最优策略得最优策略第3阶段得最优策略4/30/2024147得最优策略得最优策略4/30/2024148同理可推得第2阶段和1阶段的最小优决策。第2阶段：4/30/2024149第1阶段最后，由第1阶段到第4阶段的最优决策，可得出最短路三条：最短路程4/30/2024150一、一维资源分配问题例某工厂拟在一年中进行三种新产品试制，估价不成功的概率分别为40,0.60,0.80.为了促进三种新产品的研制,厂领导决定拨2万元补加研制费.假若这些补加研制费(以万元为单位)分配给不同新产品时,估计不成功的概率分别为下表所示.问如何分配这些补加研制费,使这三种新产品都不成功的概率最小4/30/2024151

产品研制费不成功的概率ABC

0

0.40

0.60

0.80

1

0.20

0.40

0.50

2

0.15

0.20

0.304/30/2024152解设xk为分配给第k种新产品(依次为A,B,C)的补加研制,k=1,2,3.pk(xk)表示分配xk万元补加研制费给第k种新产品时不成功的概率(k=1,2,3).则得非线性规划模型:

4/30/2024153若设由于sk,,xk均取几个离散值,所以可将三个阶段的计算过程分别列入下面三个表中新产品的补加研制费,则相应的动态规划为表示分配给第k至第3种4/30/2024154第三阶段（k=3)x3s3p3(x3)F3*(s3)X3*

0

1

200.800.80

0

10.500.50

1

20.300.30

2S3=x34/30/2024155第二阶段x2S2p2(s2)·f3*(s3)f2*(s2)X2*01200.480.48010.300.320.30020.180.200.160.162S2=x2+S34/30/2024156第一阶段x1S1p1(x1)·f2*(s2)f1*(s1)x1*

0

1

2

20.0640.060.0720.06

1S1=2=x1+S2于是得最优解:都不成功的概率为0.064/30/2024157二、背包问题背包问题的一般提法是：一旅行者携带背包去登山，已知他所能承受的背包重量限制为a千克，现有n种物品可供他选择装入背包,第i种物品的单件重量为ai千克,其价值(可以是表明本物品对登山的重要性的数量指标)是携带数量xi的函数ci(xi)(i=1...n).问旅行者如何选择携带各种物品的件数,以使总价值最大?

背包问题等同于车、船、飞机、人造卫星等工具的装载问题,还可以用于解决机床加工中零件最优加工、下料问题,投资决策等.4/30/2024158解设xi为第i种物品装入的件数，则下面用动态规划顺序解法建模求解4/30/2024159阶段k:将可装入物品按1，2，…,n排序，每段装一种物品，共划分n个阶段。K=1,2,…,n.状态变量sk+1:在第k段开始时，背包中允许装入前k种物品的总重量。决策变量xk:装入第k种物品的件数。状态转移方程：sk=sk+1-aksk允许决策集合：4/30/2024160最优指标函数fk(sk+1)表示在背包中允许装入物品的总重量不超过sk+1千克，采用最优策略只装前k种物品时的最大使用价值。则可得到动态规划的顺序递推方程为：用前向动态规划方法逐步计算f1(s2),f2(s3),…,fn(sn+1)及相应的决策函数x1(s2),x2(s3),…,xn(sn+1),最后得到的fn(a)即为所求的最大值，相应的最优策略则由反推计算得出。4/30/2024161三、设备更新问题

企业中经常会遇到因设备陈旧或损坏需要更新的问题。从经济学上分析，一