第7章 线性规划课件.pptVIP

第7章 线性规划 同济大学 经济与管理学院 管理科学与工程系 孙昌言 教授 运筹学——起源于第二次世界大战，是运用科学方法(系统方法和数学模型)研究客观世界中复杂系统的运行规律和系统的最优设计方案，帮助管理者和决策者进行科学决策的一门新兴的软科学，是当代管理科学的基础。 线性规划是运筹学最重要的一个分支。 运筹学的主要分支： 数学规划(线性规划、整数规划、非线性规划、目标规划、动态规划)、网络分析、网络计划方法、存储论、决策论、对策论、马尔柯夫分析、排队论、随机模拟等。 本章内容： §7.1 线性规划的应用及其数学模型 §7.2 单纯型形法的基本原理 §7.3 用 Excel 求解线性规划问题 §7.4 线性规划的对偶问题 §7.5 敏感性分析(自学) 本章重点： 线性规划的建模；求解线性规划的单纯形法的基本原理；解的基本概念；软件求解方法。 本章难点：根据实际问题建立线性规划模型。 线性规划(Linear Programming，简称 LP)是运筹学中最重要的一个分支。客观世界中的大量问题都可以用线性规划模型进行描述和分析求解。 线性规划广泛地应用于军事、工程技术、科学研究和经济管理等领域，这是由于： ⑴各领域中的大量问题都能使用线性规划模型来描述和分析； ⑵LP模型有有效的求解方法(单纯形法)； ⑶LP模型能有效地分析参数的变化(敏感性分析)。 ⑷线性规划是许多其他运筹学方法的基础。 ⑴ 决策变量 —— 实际问题所要确定的一组变量，记为 x1, x2, ···, xn ⑵ 约束条件 ———对决策变量取值的限制条件，由决策变量 的线性不等式组或线性方程组构成； ⑶ 目标函数 —— 是决策变量的线性函数，目标可以是最大化或最小化。 建立线性规划模型，是运用线性规划解决实际问题的首要和最重要的步骤。 建立 LP 模型的基本步骤： 1. 根据实际问题的需要设置决策变量； 2. 按所要达到的目标建立模型的目标函数； 3. 根据问题的要求和限制条件列出模型的约束条件组。 【典例 1】最优生产计划问题 设某厂生产甲、乙、丙三种产品，要经过三道工序加工，每种产品在各道工序的加工时间、各工序的生产能力和各产品的单位利润如下： 设 x1, x2, x3 分别为产品甲, 乙, 丙的计划日产量， x0 为每天的总利润，则 【典例 2】饲料配方问题 某饲料公司生产一种鸡饲料，每份饲料为100公斤，饲料中的营养成份要求、配料及其成本数据如下： 设 x1, x2, x3 分别为每 100 kg 饲料中大豆粉、玉米粉和石灰石的数量(kg)， 【典例 3】下料问题 某纸厂接到三种宽度卷纸的定单，要求见下表。 定单号 宽度要求(米) 需求量(米) 1 0.9 10,000 2 1.2 30,000 3 1.5 20,000 该厂生产两种标准宽度的卷纸(2米和3米宽)，现需要按订单要求的宽度切割(设切割下的卷纸长度可以连接以满足总长度要求)。 应如何切割下料，可使所耗用的标准卷纸面积为最少？ 2分钟讨论：如何建立LP模型？ 【典例 4】投资方案选择问题 某公司有5000万元闲置资金，现有四种投资项目可供选择： 项目 A：每年年初都可投资，于次年末可收回投资额的 115%； 项目 B：在第三年年初投入一笔资金，第五年年末可收回投资的 135%，但该项目至多只可投资 2000 万元； 项目 C：第二年年初投入一笔资金，第五年年末可收回投资额的 145%； 项目 D：每年年初可购买年利率为 6% 的一年期债券。 公司的所有资金必须在第五年年末全部收回。 问应如何安排投资，可使公司在第五年年末拥有的资金最多？ 2分钟讨论：如何建立LP模型？ 设：xai为第 i 年年初投入项目A 的资金，i =1, 2, 3, 4 xb, xc 分别为投入项目 B、C 的资金； xdi 为第 i 年年初购入的债券数，i =1, 2, 3,