基础运筹学教程（第三版）- 第一章-1 数学模型.ppt

*******第一章线性规划*运筹学的一大分枝是数学规划，而线性规划又是数学规划的重要组成部分。线性规划从二十世纪40年代前后创始至今，其理论的完整、方法的多样、应用的广泛，都远较运筹学的其它分支来得成熟。*求解线性规划最常用的方法——单纯形法，由美国数学家丹捷格（G.B.Dantzig）于1947年提出，迄今为止，仍是一般意义下实际求解线性规划最为有效的方法，被誉为20世纪最好的10个算法之一。尽管后来又陆续出现一系列新的方法，如椭球法（Xачиян法）以及以Karmarkar算法为基础的内点法等，但在实用上仍未完全取代单纯形法。*目前，线性规划的发展几乎已被人们认为是二十世纪中叶最重要的科学进步之一，且在应用领域已成为一种标准的工具，在发达国家，即使是中等规模的企业，也会因线性规划的有效使用而节省数百万资金。*在这一部分，按照：§1-1数学模型§1-2图解法§1-3单纯形法§1-4对偶规划§1-5灵敏度分析§1-6运输问题等六大部分内容和顺序进行讲授。*§1-1数学模型模型的定义：模型是研究者对客观现实经过思维抽象后用文字、图表、符号、关系式以及实体模样描述所认识到的客观对象。模型的分类：模型一般分为数学模型和模拟模型。数学模型：也称符号模型，由决策变量和参数、约束条件以及目标三项要素组成。三者之间建立的函数关系表现了现实系统的基本特征，其解可用适当的方法求得。模拟模型：是采用一种易于求解的模型去模仿另一种难以求解的模型的方法。例如用电路系统去模拟一个力学系统等。*成功使用线性规划的前提之一是合理地构造问题的数学模型，图1-1给出的是运筹学（包括线性规划）建模的一般步骤：模型准备模型假设模型构成模型检验模型应用模型分析模型求解实际问题数据准备图1-1*下面，我们首先通过一些简单的范例来阐明什么是线性规划、如何构造问题的数学模型并化为标准型。一.范例例1、例2、例3二.线性规划的标准形式1.线性规划的一般形式2.线性规划的标准形式3.非标准形式的标准化4.标准形式的其它表示形式*一.范例例1:生产计划问题某工厂生产A、B两种产品，其成本决定于所用的材料。已知单位产品所需材料量、材料日供应量及单价如表1-1所示。若每生产A或B产品一个单位，所费工资同为30元，又A、B的每单位销售价分别为120元和150元。问：工厂应如何安排生产，才能使所获总利润最大。*表1-1材料AB日供应量(kg)材料单价(￥/kg)a621801.00b4104002.30c3521014.60*求解：由表1-1可得：生产A、B产品均需要用到材料a、b和c。生产A产品的单位材料成本为:1.00×6+2.30×4+14.60×3=59(元)单位工资成本为30（元）单位售价为120（元）因此，其单位利润为:120–59–30（工资）=31(元)材料AB日供应量(kg)材料单价(￥/kg)a621801.00b4104002.30c3521014.60*生产B产品的单位材料成本为:1.00×2+2.30×10+14.60×5=98(元)单位工资成本为30（元）单位售价为150（元）因此，其单位利润为:150–98–30（工资）=22(元)材料AB日供应量(kg)材料单价(￥/kg)a621801.00b4104002.30c3521014.60*设工厂日产A、B产品分别为x1,x2单位，可获利润为z元，则所得总