《第四讲线性规划数学模型的应用(生产、排版、广告投放)》由会员分享，可在线阅读，更多相关《第四讲线性规划数学模型的应用(生产、排版、广告投放)（69页珍藏版）》请在金锄头文库上搜索。
1、运筹学 第四章第四章 线性规划在管理中的应用线性规划在管理中的应用 运筹学 连续投资 问题 连续投资 问题 连续投资 问题 连续投资 问题 合理排班 问题 合理排班 问题 合理排班 问题 合理排班 问题 市场调 查问题 市场调 查问题 市场调 查问题 市场调 查问题 套材下料 问题 套材下料 问题 套材下料 问题 套材下料 问题 关于环境保 护问题 关于环境保 护问题 关于环境保 护问题 关于环境保 护问题 媒体选择 问题 媒体选择 问题 媒体选择 问题 媒体选择 问题 生产安排 问题 生产安排 问题 生产安排 问题 生产安排 问题 产品自制与外 购问题 产品自制与外 购问题 产品自制与外 购
2、问题 产品自制与外 购问题 配料或混合 问题 配料或混合 问题 配料或混合 问题 配料或混合 问题 营养配餐 问题 营养配餐 问题 营养配餐 问题 营养配餐 问题 线性规划线性规划线性规划线性规划 运筹学 产品自制与外购计划问题产品自制与外购计划问题 例例1 某工厂生产甲、乙、丙三种产品，这三种产品都要经过铸造、机 械加工和装配三道工序。甲、乙两种产品的铸件可以外包协作，亦可以自行 生产，但产品丙必须由本厂铸造才能保证质量。有关情况如下表所示，工厂 为了获得最大利润，甲、乙、丙三种产品各应生产多少件？甲、乙两种产品 的铸件有多少由本公司铸造？有多少为外包协作？ 某工厂生产甲、乙、丙三种产品，这
3、三种产品都要经过铸造、机 械加工和装配三道工序。甲、乙两种产品的铸件可以外包协作，亦可以自行 生产，但产品丙必须由本厂铸造才能保证质量。有关情况如下表所示，工厂 为了获得最大利润，甲、乙、丙三种产品各应生产多少件？甲、乙两种产品 的铸件有多少由本公司铸造？有多少为外包协作？ 16 2 3 - 4 2 8 7 丙丙 10000 12000 8000 工时限制工时限制 1823每件产品售价每件产品售价/元元 23装配每件成本装配每件成本/元元 12机械加工每件成本机械加工每件成本/元元 65外包协作铸件每件成本外包协作铸件每件成本/元元 53自行生产铸件每件成本自行生产铸件每件成本/元元 23每件
4、装配工时每件装配工时/小时小时 46每件机械加工工时每件机械加工工时/小时小时 105每件铸造工时每件铸造工时/小时 乙甲工时与成本 小时 乙甲工时与成本 运筹学 一、确定变量：设一、确定变量：设 x1、 、 x2、 、x3分别为三道工序都由本工厂加工的甲、乙、丙三种产品的件数 ； 分别为三道工序都由本工厂加工的甲、乙、丙三种产品的件数 ； x4、 、 x5分别为由外包协作铸造再由本工厂进行机械加工和装配的甲、乙两 种产品的件数 。如下表 分别为由外包协作铸造再由本工厂进行机械加工和装配的甲、乙两 种产品的件数 。如下表: 16-9=718-9=918-8=1023-10=1323-8=15利
5、润利润 161823每件产品售价每件产品售价 4+3+2=96+1+2=95+1+2=85+2+3=103+2+3=8成本成本 22233装配每件成本装配每件成本 31122机械加工每件成本机械加工每件成本 -6-5-外包协作铸件每件成本外包协作铸件每件成本 4-5-3自行生产铸件每件成本自行生产铸件每件成本 1000022233每件装配工时每件装配工时/小时小时 1200084466每件机械加工工时每件机械加工工时/小时小时 80007-10-5每件铸造工时每件铸造工时/小时小时 x3x5x2x4x1变量 可用工时丙乙甲 变量 可用工时丙乙甲 运筹学 二、确定目标函数：二、确定目标函数： 由
6、上表可得每件产品的利润如下：由上表可得每件产品的利润如下： 目标函数目标函数 15x1+10 x2+7x3+13x4+9x5为最大为最大 三、约束条件三、约束条件: 5x1+10 x2+7x38000 （铸造工时）（铸造工时） 6x1+4x2+8x3+6x4+4x512000 (机械加工工时机械加工工时) 3x1+2x2+2x3+3x4+2x510000 （装配工时）（装配工时） 运筹学 目标函数目标函数min 15x1+10 x2+7x3+13x4+9x5； S.T. 5x1+10 x2+7x38000 6x1+4x2+8x3+6x4+4x512000 3x1+2x2+2x3+3x4+2x5
7、10000 x1，x2，x3，x4，x50 线性规划模型线性规划模型: 运筹学 结果分析结果分析: 151600+9600=2940051600+9600=29400 总利润总利润 16-9=718-9=918-8=1023-10=1323-8=15 利润利润 1000031600+2600=600031600+2600=6000 每件装配工时每件装配工时/小时小时 1200061600+4600=1200061600+4600=12000 每件机械加工工时每件机械加工工时/小 时 小 时 800051600=800051600=8000 每件铸造工时每件铸造工时/小时小时 060000160
8、0 实际安排实际安排 可用工 时 丙乙甲丙乙甲 运筹学 最优解最优解 ( Optimal solution) 计算机求解结果分析计算机求解结果分析: 目标函数的最优值目标函数的最优值( Objective Function Value) 相差值相差值(缩减成本缩减成本) ( Reduced Costs) 松弛松弛/剩余变量剩余变量 ( Slack/Surplus) 对偶价格对偶价格 ( Dual Prices) 目标函数系数范围目标函数系数范围 ( Objective coefficient ranges) 常数项数范围常数项数范围 ( Right hand side ranges) 运筹学
9、连续投资问题连续投资问题 例例2 某部门现有资金某部门现有资金300万元，今后五年内考虑给以下的项目投 资： 项目 万元，今后五年内考虑给以下的项目投 资： 项目A：从第一年到第五年每年年初都可投资，当年末能收回本 利 ：从第一年到第五年每年年初都可投资，当年末能收回本 利110。 项目 。 项目B：从第一年到第四年每年年初都可以投资，次年末收回本 利 ：从第一年到第四年每年年初都可以投资，次年末收回本 利125，但规定每年最大投资额不能超过，但规定每年最大投资额不能超过50万元。 项目 万元。 项目C：第三年初需要投资，到第五年末能收回本利：第三年初需要投资，到第五年末能收回本利140，但规
10、 定最大投资额不能超过 ，但规 定最大投资额不能超过100万元。 项目 万元。 项目D：第二年初需要投资，到第五年末能收回本利：第二年初需要投资，到第五年末能收回本利155，但规 定最大投资额不能超过 ，但规 定最大投资额不能超过150万元。 应如何确定这些项目每年的投资额，从而使得第五年末拥有资金 的本利金额最大？ 万元。 应如何确定这些项目每年的投资额，从而使得第五年末拥有资金 的本利金额最大？ 运筹学 一、确定变量 如下表 一、确定变量 如下表: x11项目项目D x10项目项目C x9x8x7x6项目项目B x5x4x3x2x1项目项目A 第第5年投资额第年投资额第4年投资额第年投资额
11、第3年投资额第年投资额第2年投资额第年投资额第1年投资额年投资额 运筹学 二、确定目标函数二、确定目标函数 此问题要求在第五年末该部门所拥有的资金额达到最大，即目标函数最大化，看下表此问题要求在第五年末该部门所拥有的资金额达到最大，即目标函数最大化，看下表: 1.55 x11x11项目项目D（100/年）年） 1.40 x10 x10项目项目C（80/年）年） 1.25 x9x9x8x7x6项目项目B（30/年）年） 1.1 x5x5x4x3x2x1项目项目A 5年末收益第年末收益第5年第年第4年第年第3年第年第2年第年第1年年 得得5年末总收益年末总收益: z1.1 x51.25 x9十十1
12、.40 x101.55 x11 运筹学 三、确定约束条件三、确定约束条件 因为项目因为项目A每年都可以投资，并且当年末都能收回本息，所以该部门每年都应把资金 投出去，手中不应当有剩余的呆滞资金，因此可处下表： 每年都可以投资，并且当年末都能收回本息，所以该部门每年都应把资金 投出去，手中不应当有剩余的呆滞资金，因此可处下表： 1.1 x4+1.25 x81.1 x3+1.25 x71.1 x2+1.25 x61.1 x1300当年可投资额当年可投资额 x5x4+ x9x3+ x8+ x10 x2+ x7+ x11x1+ x6当年投资额当年投资额 x11 项目项目D（100/年）年） x10 项
13、目项目C（80/年）年） x9x8x7x6 项目项目B（30/年）年） x5x4x3x2x1 项目项目A 第第5年第年第4年第年第3年第年第2年第年第1年年 运筹学 第一年：该部门年初有资金第一年：该部门年初有资金300万元，故有万元，故有 x1+ x6=300 第二年：因第一年给项目第二年：因第一年给项目B的投资要到第二年末才能收回，所以该部门在第二年初拥 有资金仅为项目 的投资要到第二年末才能收回，所以该部门在第二年初拥 有资金仅为项目A在第一年投资额所收回的本息在第一年投资额所收回的本息110% x1，故有，故有 x2+ x7+ x11=1.1 x1 或或 -1.1 x1+ x2+ x7
14、+ x11=0 第三年：第三年初的资金额是从项目第三年：第三年初的资金额是从项目A第二年投资和项目第二年投资和项目B第一年投资所回收的本息总 和 第一年投资所回收的本息总 和1.1x2+1.25 x7，故有，故有 x3+ x8+ x10=1.1 x2+1.25 x6 或或-1.1 x2+ x3-1.25 x6+ x8+ x10=0 第四年：同以上分析，可得第四年：同以上分析，可得 x4+ x9=1.1 x3+1.25 x7 或或-1.1 x3+ x4-1.25 x7+ x9=0 第五年：第五年：x5=1.1 x4+1.25 x8 或或-1.1 x4+ x5- 1.25 x8=0 得到得到5个条
15、件个条件 运筹学 另外，对项目另外，对项目B，C，D的投资额的限制有的投资额的限制有 x650 (项目项目B每年限投每年限投50万元万元) x750 (项目项目B每年限投每年限投50万元万元) x850 (项目项目B每年限投每年限投50万元万元) x950 (项目项目B每年限投每年限投50万元万元) x10100 (项目项目C每年限投每年限投100万元万元) x11150 (项目项目D每年限投每年限投150万元万元) 又得到又得到6个条件个条件,这样就可建立如下数学模型这样就可建立如下数学模型: 运筹学 目标函数目标函数max 1.1 x51.25 x9十十1.40 x101.55 x11 约
16、束条件：约束条件：x1+ x6=300 -1.1 x1+ x2+ x7+ x11=0 -1.1 x2+ x3-1.25 x6+ x8+ x10=0 -1.1 x3+ x4-1.25 x7+ x9=0 -1.1 x4+ x5- 1.25 x8=0 x650 x750 x850 x950 x10100 x11150 xi0（i=1,2,.10,11） 第一问 ） 第一问: 这是一个连续投资问题这是一个连续投资问题 运筹学 用表格表示用表格表示: 5125年末总收益年末总收益 1.1 x4+1.25 x8 =70 1.1 x3+1.25 x7 =56.818 1.1 x2+1.25 x6 =150 1.1 x1 =275 300当年可投资额当年可投资额 x5=70 x4+ x9 =56.818 x3+ x8+ x10 =150 x2+ x7+ x11 =275 x1+ x6 =300 当年投资额当年投资额 1.55 x11=232.5x11=150项目项目D 1.40 x10=
