北大光华-规划与决策(2).ppt

第六章 模型决策法
线性规划等
时序与路径规划
分派问题
最短路问题
最大流问题
1
模型决策法
优化模型
max (min) 目标函数
s. t. 约束条件
2
线性规划模型的建立
实例 1
两种产品的生产。已知生产单位产品所需的设备台时及A、B两种原材料的消耗，资源限制及市场价格如下表：
Ⅰ Ⅱ 资源限制
设备 1 1 300台时
原材料A 2 1 400千克
原材料B 0 1 250千克
市场价格 50 100
问题：如何安排生产，才能使工厂获利最多？
3
规划与决策
分析：
（1）设 x1 — 生产产品Ⅰ的数量；
x2 — 生产产品Ⅱ的数量。
（2）目标函数：MAX 50x1+100x2
（3）约束条件：subject to (.):
x1+x2 ≤300
2x1+x2 ≤400
x2 ≤250
x1,x2 ≥0
4
规划与决策
线性规划模型：
max 50x1+100x2
. x1+x2 ≤300
2x1+x2 ≤400
x2 ≤250
x1,x2 ≥0
5
规划与决策
线性规划模型的一般形式
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
6
规划与决策
线性规划应用领域：
合理利用板、线材问题；
配料问题；
投资问题；
生产计划问题、劳动力安排问题；
运输问题、电子商务配送问题；
企业决策问题；企业或商业竞争对策问题等。
7
规划与决策
一般线性规划建模过程
Step 1. 理解及分析实际问题，资源状况，解决问题实现的目标；
Step 2. 确定决策变量（x1, …，xn）— 解决问题的具体方案（量化方案）；
Step 3. 确定目标函数及约束条件；
Step 4. 应用线性规划软件求解；
Step 5. 检验所求得的解决方案是否可行：如可行，则开始具体实施；否则，转Step 1 或 Step2 修改模型。
8
规划与决策
案例2：（生产计划问题）某公司面临一个外协加工还是自行生产问题。该公司生产甲、乙、丙三种产品，这三种产品都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸造可以外协加工，亦可以自行生产。但丙产品的铸造必须自行生产才能保证质量。有关数据见下表：
9
规划与决策
工时与成本 甲 乙 丙 总工时
每件铸造工时（小时） 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
问题：如何安排生产计划，使公司获利最大？
10