计算理论2011.1

《计算理论2011.1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、250（油漆工工时限制）解：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1=生产桌子的数量x2=生产椅子的数量2．确定目标函数：家具厂的目标是销售收入最大maxz=50x1+30x23．确定约束条件：4x1+3x2120（木工工时限制）2x1+x250（油漆工工时限制）4．变量取值限制：一般情况，决策变量只取正值（非负值）x10,x20数学模型maxS=50x1+30x2s.t.4x1+3x21202x1+x250x1,x20线性规划数学模型三要素：决策变量、约束条件、目标函数线性规划问题的数学模型例2

4、营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？各种食物的营养成分表解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：minS=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4300050x1+60x2+20x3+10x455400x1+200x2+300x3+500x4800x1，x2，x3，x40其

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

6、策埃克森炼油厂关于调节冶炼能力去适应关于无铅燃料生产的法律更改的决策线性规划问题的一般形式：Max(Min)S=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+….+a1nxn(=,)b1a21x1+a22x2+….+a2nxn(=,)b2………………….am1x1+am2x2+….+amnxn(=,)bmx1,x2….xn0线性规划问题隐含的假定：比例性假定：决策变量变化引起的目标函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。线性规划问题隐含

7、的假定：比例性假定：决策变量变化引起的目标函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。线性规划问题隐含的假定：连续性假定：线性规划问题中的决策变量应取连续值。线性规划问题隐含的假定：连续性假定：线性规划问题中的决策变量应取连续值。确定性假定：线性规划问题中的所有参数都是确定的参数。线性规划问题不包含随机因素。线性规划问题隐含的假定：比例性假定可加性假定连续性假定

8、确定性假定例3：配棉问题所谓的配棉问题就是要根据棉纱的质量指标，采用各种价格不同的棉花，按一定的比例配制成纱，使其即达到质量指标又使总成本最低。棉纱的质量指标一般有