线性规划及其基本理论.ppt

《线性规划及其基本理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、运筹学OperationsResearch陈志松Mob.:138514279761线性规划及其基本理论线性规划概述线性规划问题线性规划数学模型一般模型标准模型线性规划解的概念可行解、最优解基阵、基解、基可行解线性规划的基本性质2线性规划概述线性规划（LinearProgramming，简记为LP）是运筹学中的一个最重要、应用最广泛的分支。线性规划及其通用解法--单纯形法一般认为是美国学者丹捷格（G.Dantzig）在1947年研究美国空军军事规划时提出的。苏联学者康托洛维奇在1939年解决工业生产组织与计划问题时就

2、提出类似线性规划的模型及解法；康托洛维奇的工作当时没有被重视，但直到1960年康托洛维奇再次发表《最佳资源利用的经济计算》一书后，才受到重视。一些常见的带有Spreadsheet的软件，如：Excel、Lotus1-2-3等，均有内置的线性规划求解功能。最优化问题求解软件，如：Lindo、Lingo、Matlab等。3线性规划问题提出在生产管理和经营活动中经常会提出这样一类问题：如何利用有限的人力、物力、财力等资源，取得最好的效果。例如：配载问题一交通工具，运输几种不同体积、重量的物资，如何装配，所运的物资最多？下

3、料问题用圆钢制造长度不等的机轴，如何下料，所剩的余料最少？生产计划问题企业生产A、B两种电器产品，两种产品的市场需求状况可以确定，按当前的定价可确保所有产品均能销售出去。企业可提供的两种原材料和劳动时间的数量是有限的。产品A与产品B各应生产多少，可使企业总利润最大?4线性规划问题提出上述这些问题有如下共同特点：问题解决要满足一定条件，称为约束条件；问题有多个满足条件的解决方案；问题解决有明确的目标要求，对应不同方案有不同目标值，可表示成目标函数。5何谓线性规划问题最优化问题我们称如下一般问题：“在一定约束条件下，求

4、目标函数的最大或最小值”为最优化问题，用数学模型描述的最优化问题，称为数学规划问题。线性规划问题在最优化问题中，如果约束条件与目标函数均是线性的，我们就称之为线性规划问题。6线性规划问题的三个要素决策变量决策问题待定的量值称为决策变量。决策变量的取值有时要求非负。约束条件任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件。约束条件是决策方案可行的保障。LP的约束条件，都是决策变量的线性函数。目标函数衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。目标函数是决策变量的线

5、性函数。有的目标要实现极大，有的则要求极小。7线性规划数学模型例生产计划问题某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最后都需在C车间装配，相关数据如表所示：问如何安排甲、乙两产品的产量，使利润为最大。35单位产品获利81236123234ABC生产能力工时单耗甲乙产品车间8线性规划数学模型建立数学模型的步骤：Step1分析实际问题；Step2确定决策变量；Step3找出约束条件；Step4确定目标函数；Step5整理、写出数学模型。9【例1.1】某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建

6、，各体系资源用量及今年供应量见下表：要求在充分利用各种资源条件下使建造住宅的总面积为最大(即求安排各住宅多少m2)，求建造方案。水泥(公斤/m2)4000(千工日)147000(千块)150000(吨)20000(吨)110000(千元)资源限量3.5——18025120大模住宅3.0——19030135壁板住宅4.521011012105砖混住宅人工(工日/m2)砖(块/m2)钢材(公斤/m2)造价(元/m2)资源住宅体系线性规划问题举例10【例1.2】最优生产计划问题。某企业在计划期内计划生产甲、乙、丙三种产品

7、。这些产品分别需要要在设备A、B上加工，需要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表1.1所示。已知在计划期内设备的加工能力各为200台时，可供材料分别为360、300公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为40、30、50元，假定市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？线性规划问题举例产品资源甲乙丙现有资源设备A312200设备B224200材料C451360材料D235300利润（元/件）403050产品资源消耗表11【例

8、1.3】某商场决定：营业员每周连续工作5天后连续休息2天，轮流休息。根据统计，商场每天需要的营业员如表1.2所示。表1.2营业员需要量统计表商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。星期需要人数星期需要人数一300五480二300六600三350日550四400线性规划问题举例12【例1.4】合理用料问题。某汽车需要用甲、乙、丙三种规格的