第章-线性规划与单纯形方法.pptVIP

第1章 线性规划与单纯形方法 应用最广泛的运筹学方法 根据统计，应用最广泛的运筹学学方法为： 数学规划（线性规划，整数规划） 模拟 网络模型（包括PERT/CPM） 决策分析 排队理论 库存模型 最基本的运筹学方法 网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的； 解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大； 引例 例1.1 生产计划问题 胜利家具厂生产桌子和椅子两种家具。桌子售价50元，椅子售价30元，生产一 个桌子需要木工4小时，油漆工 2 小时。生产一个椅子需要木工3小时，油漆工 1小时。该厂每月可用木工工时为120，油漆工工时为50 。该厂如何生产才能 使每月销售收入最大？ 生产方案 生产价格高的产品：能生产25个桌子，木工剩余20小时，销售收入1250元； 替代生产方案 1：生产20个桌子，10 个椅子，木工仍剩余10小时，销售收入1300元； 替代生产方案 2：生产15个桌子，20 个椅子，用完全部工时，销售收入1350元； 可能的生产方案 用手工计算也可找出很多可行方案； 对于简单问题有时也可找到最优方案； 当问题更复杂时，如有20种产品，消耗10种资源，用人工计算是否有效？ 一个很简单的问题都可能存在无数可行解，从中找出最优解不是容易的事。 线性规划模型是求解这类问题的有效工具。 生产计划数学模型 决策变量 ：模型要决定的未知量 x1 = 生产桌子的数量， x2 = 生产椅子的数量。 目标函数 ：决定线性规划优化方向 max: z = 50x1 + 30x2 约束方程 ：反映客观条件的限制 木工工时不能超过可用工时 4x1 + 3x2 ? 120 油漆工工时不能超过可用工时 2x1 + x2 ? 50 非负约束 ：变量取值的限制 x1 ?0，x2 ?0 生产计划问题的完整模型 max: z = 50x1 + 30x2 s.t. 4x1 + 3x2 ? 120 2x1 + x2 ? 50 x1 ?0，x2 ?0 1.1 线性规划的数学模型 例1.2 营养配餐问题 假定一个成年人每天需要从食物中获取3000大卡的热量、55克蛋白质和800毫克的钙，市场上只有四种食品可供选择。它们每公斤所含热量和营养成分以及市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小。 食物营养表 营养配餐模型 变量：xj 每天购入j 种食品数量。 目标函数：每天采购成本最小 min:z = 14x1 + 6x2 + 3x3 + 2x4 约束方程：满足每天的营养要求 满足3000大卡的热量要求 1000x1+800x2+900x3+200x4 ? 3000 满足蛋白质摄入量要求： 50x1 + 60x2 + 20x3 + 10x4 ? 55 满足钙摄入量要求： 400x1 +200x2 +300x3 +500x4 ? 800 非负约束--采购量不能为负值 x1，x2，x3，x4 ? 0 营养配餐问题的完整模型 min:z =14x1 + 6x2 + 3x3 + 2x4 s.t. 1000x1+800x2+900x3+200x4 ?3000 50x1+ 60x2+ 20x3+ 10x4 ? 55 400x1+200x2+300x3+500x4 ? 800 x1，x2，x3，x4 ? 0 线性规划是求一个线性函数在满足一组线性等式或不等式方程条件下极值的数学问题的统称。 线性规划的数学模型由三部分组成： 1 需要确定的决策变量； 2 需要优化（求极大或极小）的目标函数； 3 必须满足的约束条件。 某工厂用三种原料生产三种产品，已知的条件如表所示，试制订总利润最大的生产计划 问 题 分 析 数学模型 2. 线性规划的一般模型 线性规划问题的一般形式可以写为： max(min): z = c1x1+c2 x2+…+cnxn s.t. a11x1+a12x2+…+a1nxn ?(=, ?) b1 · · · · · · am1x1+am2x2+…+amnxn ? (=, ?) bm x1, x2, … , xn ? 0 x1, ..., xn为决策变量，表示第 n 种生产经营活动的规模， z = c1x1+???+cnxn 称为目标函数，反映生产活动的目标。cj (j = 1, 2,