计算理论2011.1.ppt

1、线性规划基本概念 生产计划问题 如何合理使用有限的人力，物力和资金，使得收到最好的经济效益。 如何合理使用有限的人力，物力和资金，以达到最经济的方式，完成生产计划的要求。,例1 生产计划问题（资源利用问题） 胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30元/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？,解：将一个实际问题转化为线性规划模型有以下几个步骤：,解：将一个实际问题转化为线性

2、规划模型有以下几个步骤： 1确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量,解：将一个实际问题转化为线性规划模型有以下几个步骤： 1确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量 2确定目标函数：家具厂的目标是销售收入最大 max z=50 x1+30 x2,解：将一个实际问题转化为线性规划模型有以下几个步骤： 1确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量 2确定目标函数：家具厂的目标是销售收入最大 max z=50 x1+30 x2 3确定约束条件： 4x1+3x2 120（木工工时限制） 2x1+x2 50 （油漆工工时限制）,解：将一个实际问题转化为线性

3、规划模型有以下几个步骤： 1确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量 2确定目标函数：家具厂的目标是销售收入最大 max z=50 x1+30 x2 3确定约束条件： 4x1+3x2 120（木工工时限制） 2x1+x2 50 （油漆工工时限制） 4变量取值限制： 一般情况，决策变量只取正值（非负值） x1 0, x2 0,数学模型 max S=50 x1+30 x2 s.t. 4x1+3x2 120 2x1+ x2 50 x1,x2 0 线性规划数学模型三要素： 决策变量、约束条件、目标函数,线性规划问题的数学模型 例2 营养配餐问题 假定一个成年人每天需要从食物中获得300

4、0千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？,各种食物的营养成分表,解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为： min S=14x1+6x2 +3x3+2x4 s.t. 1000 x1+800 x2 +900 x3+200 x4 3000 50 x1+ 60 x2 + 20 x3+ 10 x4 55 400 x1+200 x2 +300 x3+500 x4 800 x1，x2 ， x3 ， x4 0,其他典型问题： 合理下料问题 运输问题

5、生产的组织与计划问题 投资证券组合问题 分派问题 生产工艺优化问题,用于成功决策的实例： 美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决策 美国国防部关于如何从现有的一些基地向海湾运送海湾战争所需要的人员和物资的决策 Chessie道路系统关于购买和修理价值40亿美圆货运汽车决策,用于成功决策的实例： 魁北克水利部门关于用哪几个水库来满足每天电力需求决策 农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年共计60亿美圆）来维持发展决策 北美长途运输公司关于每周如何调度数千辆货车的决策 埃克森炼油厂关于调节冶炼能力去适应关于无铅燃料生产的法律更

6、改的决策,线性规划问题的一般形式： Max(Min)S=c1x1+c2x2+.+cnxn s.t. a11x1+a12x2+.+a1nxn (=, )b1 a21x1+a22x2+.+a2nxn (=, )b2 . am1x1+am2x2+.+amnxn (=, )bm x1,x2.xn 0,线性规划问题隐含的假定： 比例性假定：决策变量变化引起的目标函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。,线性规划问题隐含的假定： 比例性假定：决策变量变化引起的目标函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约束方

7、程左端值的改变量和该变量的改变量成比例。 可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。,线性规划问题隐含的假定： 连续性假定：线性规划问题中的决策变量应取连续值。,线性规划问题隐含的假定： 连续性假定：线性规划问题中的决策变量应取连续值。 确定性假定：线性规划问题中的所有参数都是确定的参数。线性规划问题不包含随机因素。,线性规划问题隐含的假定： 比例性假定 可加性假定 连续性假定 确定性假定,例3：配棉问题 所谓的配棉问题就是要根据棉纱的质量指标，采用各种价格不同的棉花，按一定的比例配制成纱，使其即达到质量指标又使总成本最

8、低。 棉纱的质量指标一般有棉结和品质指标来决定，这两项指标都可以用数量形式来表示，一般来说，棉结粒越少越好，品质指标越大越好。 1个年纺能力为15000锭的小厂在采用最优化方法配棉时，某一产品32D纯棉纱的棉花配比质量指标及单价如下：,所给条件：,有关部门对32D纯棉纱规定的质量指标为棉结不多于70粒，品质指标不小于2900。 下面我们建立数学模型： 首先：根据问题需要设置变量：设 分别为国棉131,229,327的棉花配比，然后用所设置的变量把所追求的目标及所受的约束，用数学语言表达出来，即得到该问题的数学模型。,本例的目标是混棉单价最小，用 即可表示为： 本例关于32D纯棉纱的质量指标作为

9、约束条件表出，即有：,又因为 的实际意义，它们应为百分数且和为100%，故又有：,故32D纯棉纱配棉问题的数学模型为：,例4：资金使用问题 设有400万元资金，要求4年内使用完，若在一年内使用资金 万元，则可得到效益 万元，（效率不能再次使用），当年不使用的资金可存入银行，年利率为10%，试制定出资金的使用计划，以使4年资金效益之和最大。 很明显，不同的使用方案，所取得的效益之和是不同的，如第一年就把400万元全部用完，则效益总和为20万元，若前三年均不使用而存入银行，则第四年把本息和532.4万元全部用完，则效益总和为 万元，比第一种方案效益大3万多元 。,运用最优化方法：,效益总和为 万元，使第一种效益总和的两倍多。 注：此例反映出进行定量的优化计算作用，故一些工业人士称最优化方法是不需要增加投入而增加产出的