or第二章线性规划的图解法.pptxVIP

§1. 问题的提出P10 例1. 生产安排问题某工厂在计划期内要安排I、II两种产品的生产，已知生产单位产品所需的设备台时及A，B两种原材料的消耗，以及资源的限制，如下表所示。 生产计划问题资源消耗表III资源限制设备原料A原料B120111300台时400千克250千克单位产品利润50元100元P10 例1.生产安排问题问工厂应分别生产多少个I产品和II产品才能使工厂获利最多？问题分析首先要明确要我们决定什么其次要了解要达到什么样的目标接下来需要找出各种限制条件建立文字模型文字模型目 标： 最大化总利润约束条件：生产所使用的设备台时≤拥有的设备台时生产所使用的原料A的数量≤原料A的拥有量生产所使用的原料B的数量≤原料B的拥有量决策变量的设定为将文字模型表示成数学模型，需要设定变量和符号。决策变量的设定一方面要便于写出数学模型，另一方面要便于确定决策。决策变量的设定最大化总利润总利润 = 产品I提供的利润 + 产品II提供的利润约束条件生产所使用的设备台时≤拥有的设备台时约束条件生产所使用的原料A的数量≤原料A的拥有量约束条件生产所使用的原料B的数量≤原料B的拥有量线性规划模型可行解满足所有约束条件的解称为该线性规划问题的可行解。最优解和最优值使目标函数最大的可行解称为最优解，此目标函数值称为最优目标函数值，简称最优值。生产安排问题的解决方案最优解 就对应最佳的生产方案。最优值 对应最佳生产方案产生的最大利润。这里的生产安排问题需要作出产品I和产品II的产量安排，即作出两个不同的决策，这是一种所谓的多重决策问题。这种问题可以采取顺序决策方法或同步决策方法解决。同步决策问题 指同时制定多重决策就会有利益，即使这些决策的实施过程要经历一段时间。对每一个管理者来说，一个必备的技能就是有能力识别出排序决策法无法产生有竞争力的决策，与此同时，有形成更好解决办法的悟性也是同样重要的。同步决策问题的共同特征1. 它们涉及到许多决策变量（通常上千，实际上有时上百万）且互相关联。2. 有一些稀缺资源必须被分配于有竞争的不同用途之间。3. 在能获得的或管理者想获得的条件方面有一些约束。4. 有一个相当清楚明确的目标。5. 决策的问题是相当容易理解的。用数学规划（Mathematical Programming，M P）的方法来解决这样的同步决策问题是常见的。（M P与计算机编程无关，这种方法先于计算机的出现。）数学规划问题是 寻找能使一个目标达到最大（或最小）并能满足一组约束条件的一组决策变量值。一般线性规划问题的建模过程参见教材P11线性规划问题建模的一般步骤Understand the problem thoroughly.Write a verbal statement of the objective function and each constraint.Define the decision variables.Write the objective function in terms of the decision variables.Write the constraints in terms of the decision variables. 线性规划模型的一般形式线性规划问题的假设Proportionality(比例性)决策变量变化引起的目标函数的改变量和决策变量的改变量成比例。每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。比例性假设意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是一个常数。 线性规划问题的假设Additivity（可加性）每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。线性规划问题的假设 Divisibility（可分性、连续性）线性规划问题中的决策变量应取连续值 线性规划问题的假设Certainty（确定性）线性规划中的所有参数都是确定的常数。线性规划是确定性问题，不包含随机因素。 §2. 图解法画可行域画目标函数等值线移动等值线求解 用图解法求解如下问题：P15 例2.原材料采购问题某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。P15 例2.原材料采购问题但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工 小时。P15 例2.原材料采购问题又知道每吨A原料的价格为2万元，每吨B价格为3万元。试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？P15 例2.原材料采购问题某公司由于生产需要，共需要A，