线性规划与整数规划-孟

《线性规划与整数规划-孟》由会员分享，可在线阅读，更多相关《线性规划与整数规划-孟（88页珍藏版）》请在金锄头文库上搜索。

1、 武汉学院数学建模培训优化模型（一）1. 什么是数学模型？数学模型是对于现实世界的一个特定对象，一个 特定目的，根据特有的内在规律，做出一些必要的假 设，运用适当的数学工具，得到一个数学结构简单地说：就是系统的某种特征的本质的数学表 达式（或是用数学术语对部分现实世界的描述），即 用数学式子（如函数、图形、代数方程、微分方程、 积分方程、差分方程等）来描述（表述、模拟）所研 究的客观对象或系统在某一方面的存在规律一、数学建模与优化在实际过程中用那一种方法建模主要是根据我们对研究对象的了解程度和建模目的来决定机理分析法建模的具体步骤大致可见右图符合实际不符合实际交付使用，从而可产生 经济、社会效

2、益实际问题抽象、简化、假设确定变量、参数建立数学模型并数学、数值地 求解、确定参数用实际问题的实测数据等 来检验该数学模型建模过程示意图模型数学模型的分类： 按研究方法和对象的数学特征分：初等模型、几何模型、优 化模型、微分方程模型、图论模型、逻辑模型、稳定性模型、 扩散模型等 按研究对象的实际领域（或所属学科）分：人口模型、交通 模型、环境模型、生态模型、生理模型、城镇规划模型、水资 源模型、污染模型、经济模型、社会模型等2、数学模型的分类优化模型是中国大学生建模竞赛常见的类型， 占很大的比重。92 年以来，优化模型有：94年A题：“逢山开路”设计最短路径。95年A题：“一个飞行管理问题”，

3、线性规划和非线性规划模型。96年A题：“最优捕鱼策略”，以微分方程为基础的优化模型。96年B题：“洗衣节水问题”，以用水量为目标函数的优化模型。 97年A题：“零件的参数设计”，随机优化模型。 97年B题：“截断切割”，动态优化模型。98年A题：“投资的收益和风险”，双目标优化模型。 98年B题：“灾情巡视的最佳路线”，0-1线性规划模型。99年A题：“自动化车床管理”，双参数规划模型。99年B题：“钻井布局”，非线性混合整数规划模型。00年B题：“钢管订购和运输”，二次规划模型。01年B题：“公交车调度”，双目标规划模型。02年A题：“车灯线光源的优化设计”，规划模型。03年B题：“露天矿生

4、产的车辆安排”，非线性规划模型。04年B题：“电力市场的输电阻塞管理”，双目标线性规划模型。05年B题：“DVD在现租赁”，0-1规划模型。06年A题：“出版社的资源优化配置”，线性规 划模型。 07年B题：乘公交，看奥运08 B题：高等教育学费标准探讨线性规划09 B题：眼科病床的合理安排问题排队轮10 B题： 2010年上海世博会影响力的定量评估实际问题中 的优化模型x是决策变量f(x)是目标函数gi(x)0是约束条件数学规划线性规划(LP) 二次规划(QP) 非线性规划(NLP)纯整数规划(PIP) 混合整数规划(MIP)整数规划(IP)0-1整数规划一般整数规划连续规划3、优化模型的分

5、类运筹学所使用的数学模型的特点： 一般由决策变量、约束或限制条件及目标函数所构 成，其实质表现为在约束条件允许的范围内，寻求 目标函数的最优解!4、运筹与优化“五划五论”运筹学的基本理论：规划论：线性规划、非线性规划、动态规划、 整数规划、目标规划排队论、存贮论、图与网络、决策论、对策论1、线性规划、2、整数规划、3、01规划、4、图论、5、排队论二、优化建模主要学习内容lingo优化软件建模线性规划 （Linear Programming ) 运筹学的一个重要分枝 研究较早 发展较快 理论较成熟 应用极为广泛简记为LP 线性规划研究的问题：1、在现有的人、财、物等资源的条件下，研究如何合理地

6、计划、安排，可使得某一目标达到最大，寻求在一定约束条件下使某个指标达到最优如产量、利润等。2、在任务确定后，如何计划、安排，使用最少的人、财、物等资源，去实现该任务，如使生产成本、费用最少等。典型的线性规划在经济管理上的应用举例: 1、合理利用线材问题:现有一批长度一定的钢管,由于生产的需要, 要求截出不同规格的钢管若干。试问应如何 下料，既满足了生产的需要，又使得使用的 原材料钢管的数量最少。2、配料问题：用若干种不同价格不同成分含量的原料， 用不同的配比混合调配出一些不同价格不同 规格的产品。在原料供应量的限制和保证产 品成分的含量的前提下，如何获取最大的利润。3、投资问题： 从不同的投资

7、项目中选出一个投资方案，使投 资的回报最大。 4、产品生产计划： 合理充分利用厂里现有的人力、物力、才力， 作出最优的产品生产计划，使得工厂获利最大。 5、劳动力安排： 某单位由于工作需要，在不同时间段需要不同 数量的劳动力，在每个劳动力工作日连续工作 8小时的规定下，如何安排劳动力，才能用最少 的劳动力来满足工作的需要。 6、运输问题： 一个公司有若干个 生产单位与销售单位，根据 各生产单位的产量及销售单位的情况，如何制定 调运方案，将产品运到各销售单位而总的运费最少。 1、生产计划问题 2、产销平衡的运输问题 3、营养配方问题 4、钢材下料问题 5、人员安排问题 6、投资问题LP的数学模型

8、举例与练习例题1生产计划问题 某厂生产甲、乙两种产品，已知各产品的 利润、各资源的限量和各产品的资源消耗系 数如下表：产产品甲（ 每吨）产产品乙( 每吨）资资源限量工作日34300 小麦108700 利润润（千元 )89问题：如何安排生产，使得获利最大？例题1建模 步骤： 1、确定决策变量：设生产甲产品 吨,乙产品 吨 2、确定目标函数： 3、确定约束条件：工作日约束原材料约束非负性约束上述生产计划问题就是一个典型的线性规划问题，寻求以线性函数的最大（小）值为目标的数学模型.它是指在一组线性的等式或不等式的约束条件下，一、线性规划模型的建立及各种形式、建模的一般步骤：步骤一：确定决策变量即用变

9、量取不同的值来表示可供选择的各种不同方案 步骤二：建立目标函数即找到目标值与决策变量的数量关系 步骤三：确定约束条件即决策变量所受到的外界条件的制约。约束条件一般为决策变量的等式或不等式要求：目标函数与约束条件均是线性的，且目标函数只能是一个。、线性规划模型的一般形式：决策变量约束方程非负约束目标函数maximumminimumsubject to价值向量价值系数 、线性规划的标准形式、非标准型式线性规划问题的标准化（1）对求目标函数最大值:=（2）约束条件为“”型松弛变量（3）约束条件为“”型剩余变量(4) 约束条件右边为负（6）决策变量无符号限制（5）决策变量0例如带入约束方程及目标函数则

10、原线性规划问题的标准型为:、线性规划问题的矩阵表达式：二、线性规划的解 1、可行解：2、可行域： （LP）的全体可行解构成的集合称为可行域3、最优解及最优值：设S是（LP）的可行域不唯一唯一4、若对任意大的M0,都存在可行解使得该线性规划的目标函数值，则称该线性规划问题无界三、两个变量的线性规划的图解法解： （1）在直角坐标系上画出可行域（2）做目标函数的等值线0可行域凸多 边形顶点.图解法的基本步骤：（一般是一个凸多边形）注意：若是求目标函数的最小值， 目标函数直线向下移动关于线性规划解的结论：1、若（LP）问题有可行解，则可行域是一个凸多边形 （或凸多面体）。它可能是有界的；也可能是无界的

11、。2、若（LP）问题有最优解，则最优解可能是唯一的；也可能是无穷多个。如果是唯一的，这个解一定在该凸多边形的某个顶点上；如果是无穷多个，则这些最优解一定充满凸多边形的一条边界（包括此边界的两个顶点）总之，若（LP）问题有最优解，则最优解一定可以在凸多边 形的某个顶点达到3、若（LP）问题有可行解，但没有有限最优解，此时凸多边形是无界的（反之不成立）4、若（LP）问题没有可行解，则该问题没有最优解针对标准形式的线性规划问题，其解的理论分析已经很完备，在此基础上也提出了很好的算单纯形方法是线性规划问题的最为基础、也法单纯形方法及其相应的变化形式（两阶段关于线性规划模型的求解 法，对偶单纯形法等）.

12、 是最核心的算法。它是一个迭代算法，先从一个特殊的可行解（极点）出发，通过判别条件去判断该可行解是否为最优解（或问题无界），若不是最优解，则根据相应规则，迭代到下一个更好 的可行解（极点），直到最优解（或问题无界）.关于线性规划问题解的理论和单纯形法具体的求 解过程可参见文献1.然后在实际应用中，特别是数学建模过程中，遇到线性规划问题的求解，我们一般都是利用现有的软件进行求解，此时通常并不要求线性规划 问题是标准形式. 比较常用的求解线性规划模型的软件包有LINGO和LINDO. 例2、设有三个仓库A、B、C分别贮存某 种商品700吨、400吨、900吨，现有四个商 店甲、乙、丙、丁需要该种商

13、品分别为300 吨、600吨、500吨、600吨，已知各仓库到 各商店每吨的运价如下表所示，问如何调 运，才能使总运费最省？例题2 产销平衡的运输问题甲乙丙丁库库存量A622620700B218416400C1482010900需求量 3006005006002000运价商店仓库设由A调到甲乙丙丁运量分别为由B调到甲乙丙丁运量分别为 由C调到甲乙丙丁运量分别为总运费为f,则例2 建模 解：解答一般的运输问题可以表述如下：数学模型： 若其中各产地的总产量等于各销地的总销量，即类似与将一般的线性规划问题转化为其标准否则，称为不平衡的运输问题，包括：，则称该问题为平衡的运输问题.总产量总销量和总产量

14、总销量.形式，我们总可以通过引入假想的销地或产地，将不平衡的运输问题转化为平衡的运输问题. 从而，我们的重点就是解决平衡运输问题的求解.显然，运输问题是一个标准的线性规划问题，因而当然可以运用单纯形方法求解. 但由于平衡的运输问题的特殊性质，它还可以用其它的一些特殊方法求解，其中最常用的就是表上作业法，该方法将单纯形法与平衡的运输问题的特殊性质结合起来，很方便地实行了运输问题的求解. 关于运输问题及其解法的进一步介绍可参考相关运筹学书籍. 例题3营养搭配问题 用3种原料配制某种食品，要求该食品 中蛋白质、脂肪、糖、维生素的含量不 低于15、20、25、30单位以上3种原料 的单价及每单位原料所

15、含各种成分的数 量，如下表2-2所示问应如何配制该食 品，使所需成本最低？营营养成分原料食品中营营养成 分的最低需要 量（单单位）蛋白质质（单单位/千克）56815脂肪（单单位/千克）34620糖（单单位/千克）85425维维生素（单单位/千克）1012830原料单单价（元/千克）202530例题3建模解答 解: 设 分别表示 原料的用量 （千克），f表示食品的成本（元），则这一食 品配制问题变为：对于线性规划问题，如果要求其决策变量取整数值，则称该问题为整数线性规划问题.平面法和分支定界法是两种常用的求解整数线性对于整数线性规划问题的求解，其难度和运整数线性规划模型算量远大于同规模的线性规划问题. Gomory割规划问题的方法. 此外，同线性规划模型一样，们也可以运用LINGO和LINDO软件包来求解整数线性规划模型.整数规划问题 一般形式 整数线性规划(ILP) 目标和约束均为线性函数 整数非线性规划(NLP) 目标或约束中存在非线性函数整数规划问题的分类 纯(全)整数规划(PIP) 决策变量均为整数 混合整数规划(MIP) 决策变量有整数，也有实数 0-1规划 决策变量只取0或12018/8/1048取消整数规划中决策变量为整数的限制（松弛），对 应的连续优化问题称为原问题的松弛问题整数规划问题对应的松弛问题松弛问题松弛整数规划问题最优解最 优 解整数