运筹学线性规划ppt课件.ppt

《运筹学线性规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性规划线性规划的概念解的概念及性质单纯形法线性规划应用线性规划的概念线性规划问题的导出线性规划概念和模型线性规划的标准型线性规划的标准化问题的导出例2-1某工厂在生产过程中需要使用浓度为80%的硫酸100吨，而市面上只有浓度为30%，45%，73%，85%和92%的硫酸出售，每吨价格分别为400，700，1400，1900和2500元，问应购买各种浓度的硫酸各多少，才能满足生产要求，并使得所花费用最小？问题的导出初等数学（简单情形）用浓度为45%和92%的硫酸配制80%的硫酸100吨解法：设取浓度为45%和92%的硫酸量分别

2、为x1和x2吨，则依据题意有：问题的导出线性代数方法用浓度为30%，45%，73%，85%和92%的硫酸配制80%的硫酸100吨解法：设取浓度为30%，45%，73%，85%和92%的硫酸量分别为x1、x2、x3、x4、x5吨，则依据题意有：满足xj≥0（j=1，2，3，4，5）问题的导出管理角度出发：用浓度为30%，45%，73%，85%和92%的硫酸，花费最小，配制80%的硫酸100吨解法：要求成本最小Z=400x1+700x2+1400x3+1900x4+2500x5xj≥0（j=1，2，3，4，5）s.t.minmin:minimize的

3、缩写，“最小化”，s.t.subjectto的缩写，“受限制于……”问题的导出例2-2某工厂生产A、B、C三种产品，每吨利润分别为2000元，3000元，3000元；生产单位产品所需的工时及原材料如下表所示。若供应的原材料每天不超过9t，所能利用的劳动力日总工时为3个单位，问如何制定日生产计划，使三种产品总利润最大？产品生产每吨产品所需资源资源ABC工时材料111147问题的导出问题：工时和材料的日可供量已知求使利润最大的生产方案解：产品A，B，C的日生产量：x1，x2，x3每日工时=x1+x2+x3每日消耗材料量=x1+4x2+7x3每天可得利

4、润（以千元为单位）Z=2x1+3x2+3x3问题的导出利润最大工时约束材料约束非负约束max：maximize，“最大化”问题的导出例2-3某饲料公司生产一种鸡饲料，每份饲料为100公斤，饲料中的营养成份要求、配料及其成本数据如下：应如何配置该鸡饲料，可使成本最低？问题的导出例2-4某公司计划生产I和II两种家电产品。两种产品所需设备A和B的台时数和调试工序所需的时间，以及每天可用的能力数如下表所示，产品I的单位利润为2元，产品2的单位利润为1元。问该公司应如何制定生产计划才能使利润最大？问题的导出课堂练习一家家电公司准备将一种新型电视机在三家商

5、场进行销售，每一个商场的批发价和推销费及产品的利润如表所示。由于该电视机的性能良好，各商场都纷纷争购，但公司每月的生产能力有限，只能生产1000台，故公司规定：商场1至少经销100台，至多200台，商场2至少经销300台，商场3至少经销200台。公司计划在一个月内的广告预算费为8000元，推销人员最高可用工时数为1500。同时，公司只根据经销数进行生产，试问公司下个月的市场对策？概念和模型定义：对于求取一组变量xj(j=1,2,…..,n)，使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。max（或min）

6、概念和模型线性的含义：指量与量之间按比例、成直线的关系。严格的比例性生产某种产品对资源的消耗量与产量成正比可叠加性生产多种产品对某种资源的消耗量等于各产品对该资源的消耗量的和概念和模型一般形式：max（或min）目标函数约束条件非负约束称为决策变量称为目标函数系数称为资源常数或约束右端常数称为约束系数概念和模型紧缩形式：max（或min）i=1,2,…..,m概念和模型矩阵形式：max（或min）称为决策变量向量称为目标函数系数向量称为资源常数向量或约束右端常数向量称为约束系数矩阵概念和模型线性规划模型特点：①用一组未知变量（决策变量）表示要求的

7、方案。通常，根据决策变量所代表的事物的特点可以对变量的取值加以约束，例如非负约束。②存在一定的限制条件，通常称为约束条件，这些约束条件可以用一组线性等式或者线性不等式来表示③有一个目标要求，并且可以表示为决策变量的线性函数，称为目标函数，按所研究问题的不同，要求目标函数实现最大化或者最小化。标准型标准型的主要特征：①目标最大；②约束等式；③变量非负；④右端非负。标准型标准型的紧缩形式：标准型的矩阵形式：标准型标准型的向量形式：其中：标准化把一般的线性规划问题化成标准型的过程称为线性规划问题的标准化方法：1目标标准化minZ等价于max(-Z)ma

8、xZ’=-∑cjxj2化约束为等式加松弛变量、减剩余变量3变量非负化做变换或4右端非负标准化标准化举例（练习）：线形规划标准化情形目标函