第六章模型决策法 线性规划等 时序与路径规划 分派问题 最短路问题 最大流问题
第六章 模型决策法 • 线性规划等 • 时序与路径规划 • 分派问题 • 最短路问题 • 最大流问题
模型决策法 优化模型 max(min)目标函数 s. t 约束条件
模型决策法 优化模型 max (min) 目标函数 s. t. 约束条件
线性规划模型的建立 实例1 两种产品的生产。已知生产单位产品所需的设备台时 及A、B两种原材料的消耗,资源限制及市场价格如下 表 II资源限制 设备 300台时 原材料A21400千克 原材料B01250千克 市场价格50100 问题:如何安排生产,才能使工厂获利最多?
线性规划模型的建立 实例 1 两种产品的生产。已知生产单位产品所需的设备台时 及A、B两种原材料的消耗，资源限制及市场价格如下 表： Ⅰ Ⅱ 资源限制 设备 1 1 300台时 原材料A 2 1 400千克 原材料B 0 1 250千克 市场价格 50 100 • 问题：如何安排生产，才能使工厂获利最多？
规划与决策 分析: 1)设x1一生产产品Ⅰ的数量 生产产品Ⅱ的数量 (2)目标函数:MAⅩ50×1+100X2 (3)约束条件: subject to(s.t.): 300 2x1+x2<400 X2<250 X12X2≥0
规划与决策 分析： （1）设 x1 — 生产产品Ⅰ的数量； x2 — 生产产品Ⅱ的数量。 （2）目标函数：MAX 50x1+100x2 （3）约束条件：subject to (s.t.): x1+x2 ≤300 2x1+x2 ≤400 x2 ≤250 x1 ,x2 ≥0
规划与决策 线性规划模型: max 50x,+100x St.x1+x2≤300 2x1+x2<400 2<250 0
规划与决策 线性规划模型： max 50x1+100x2 s.t. x1+x2 ≤300 2x1+x2 ≤400 x2 ≤250 x1 ,x2 ≥0
规划与决策 线性规划模型的一般形式 max c,xtC,Xot.+c s. t/ allX1+…+anXn(≥=)b1 nn C,=)b m mn 0i=1 n,j
规划与决策 线性规划模型的一般形式 max c1x1+c2x2+ …+ cn xn s. t. a11x1 + …+ a1nx n≤ (≥,=) b1 a21x1 + …+ a2nx n≤ (≥,=) b2 … am1x1 + …+ amnx n≤ (≥,=) bm xij ≥ 0 i = 1, …,n, j =1, …,m
规划与决策 线性规划应用领域: 合理利用板、线材问题; 配料问题 投资问题; 生产计划问题、劳动力安排问题; 运输问题、电子商务配送问题 企业决策问题;企业或商业竞争对 策问题等
规划与决策 线性规划应用领域： †合理利用板、线材问题； †配料问题； †投资问题； †生产计划问题、劳动力安排问题； †运输问题、电子商务配送问题； †企业决策问题；企业或商业竞争对 策问题等
规划与决策 般线性规划建模过程 Step1.理解及分析实际问题,资源状况,解决 问题实现的目标; Step2.确定决策变量(x1,…,xn)—解决问 题的具体方案(量化方案) Step3.确定目标函数及约束条件 Step4.应用线性规划软件求解 Step5.检验所求得的解决方案是否可行:如可 行,则开始具体实施;否则,转Step1或 Step2修改模型
规划与决策 一般线性规划建模过程 Step 1. 理解及分析实际问题，资源状况，解决 问题实现的目标； Step 2. 确定决策变量（x1, …，xn）— 解决问 题的具体方案（量化方案）； Step 3. 确定目标函数及约束条件； Step 4. 应用线性规划软件求解； Step 5. 检验所求得的解决方案是否可行：如可 行，则开始具体实施；否则，转Step 1 或 Step2 修改模型
规划与决策 案例2:(生产计划问题)某公司面临 外协加工还是自行生产问题。该公司生 产甲、乙、丙三种产品,这三种产品都 需要经过铸造、机加工和装配三个车间 甲、乙两种产品的铸造可以外协加工, 亦可以自行生产。但丙产品的铸造必须 自行生产才能保证质量。有关数据见下 表
规划与决策 案例2：（生产计划问题）某公司面临一个 外协加工还是自行生产问题。该公司生 产甲、乙、丙三种产品，这三种产品都 需要经过铸造、机加工和装配三个车间。 甲、乙两种产品的铸造可以外协加工， 亦可以自行生产。但丙产品的铸造必须 自行生产才能保证质量。有关数据见下 表：
规划与决策 时与成本甲乙丙总工时 每件铸造工时(小时) 107 8000 每件机加工工时(小时)648 12000 每件装配工时(小时)3 10000 自产铸件每件成本(元)354 外协铸件每件成本(元)5 机加工每件成本(元)213 装配每件成本(元) 每件产品售价(元) 231816 问题:如何安排生产计划,使公司获利最大?
规划与决策 工时与成本 甲 乙 丙 总工时 每件铸造工时（小时） 5 10 7 8000 每件机加工工时（小时） 6 4 8 12000 每件装配工时（小时） 3 2 2 10000 自产铸件每件成本（元） 3 5 4 外协铸件每件成本（元） 5 6 - 机加工每件成本（元） 2 1 3 装配每件成本（元） 3 2 2 每件产品售价（元） 23 18 16 问题：如何安排生产计划，使公司获利最大？