第二章 线性规划基本概念

1、Data, Model and Decisions 数据、模型与决策数据、模型与决策 Session 2 Linear Programming: Basic Conception 线性规划：基本概念线性规划：基本概念 Session Topics Three Classic Applications of LP 典型的线性规划问题典型的线性规划问题 Basic Concepts of Linear Programming 线性规划的基本概念线性规划的基本概念 The Graphical Method for Solving LP 线性规划的图解法线性规划的图解法 Using Excel Sol

2、ver to Solving 用微软用微软Excel Solver 求解求解 Key Categories of LP Problems 线性规划问题的主要类型线性规划问题的主要类型 2.2 案例研究：伟恩德玻璃制品公司产品组合问题案例研究：伟恩德玻璃制品公司产品组合问题 公司有三个工厂：公司有三个工厂： 工厂工厂1：生产铝框和五金件：生产铝框和五金件 工厂工厂2：生产木框：生产木框 工厂工厂3：生产玻璃和组装窗与门：生产玻璃和组装窗与门 公司打算生产的新产品公司打算生产的新产品 8英尺玻璃门英尺玻璃门 4英尺英尺 6英尺双层窗英尺双层窗 收集的所有数据信息如下表收集的所有数据信息如下表 工厂

3、工厂 单位产品生产时间单位产品生产时间 每周可利用时间每周可利用时间 门门窗窗 11小时小时04小时小时 202小时小时12小时小时 33小时小时2小时小时18小时小时 单位利润单位利润300500 理论模型理论模型 0, 1823 122 4 . . 500300max 21 21 2 1 21 xx xx x x ts xxz 2.3 在电子表格上建立伟恩德公司问题的模型在电子表格上建立伟恩德公司问题的模型 第一步：选择决策变量单元格第一步：选择决策变量单元格 决策变量的初始值一般赋决策变量的初始值一般赋0，并用较醒目的颜色表示。，并用较醒目的颜色表示。 Wyndor Glass Co.

4、Product-Mix Problem 门门窗窗 单位利润单位利润$300$500 可用工时可用工时 工厂工厂1104 工厂工厂20212 工厂工厂33218 门门窗窗 产品利润产品利润00 单位产品工时消耗单位产品工时消耗 第二步：目标单元格，用函数公式表示第二步：目标单元格，用函数公式表示 并用较醒目的颜色表示。并用较醒目的颜色表示。 门门窗窗 单位利润单位利润$300$500 可用工时可用工时 工厂工厂1104 工厂工厂20212 工厂工厂33218 门门窗窗Total Profit 生产量生产量11$800 单位产品工时消耗单位产品工时消耗 11 12 G Total Profit =

5、SUMPRODUCT(UnitProfit,UnitsProduced) 第三步：约束条件左边项也用函数表示第三步：约束条件左边项也用函数表示 门门窗窗 单位利润单位利润$300$500 已用工时已用工时可用工时可用工时 工厂工厂1101=4 工厂工厂2022=12 工厂工厂3325=18 门门窗窗总利润总利润 生产量生产量11$800 单位产品工时消耗单位产品工时消耗 5 6 7 8 9 E Hours Used =SUMPRODUCT(C7:D7,UnitsProduced) =SUMPRODUCT(C8:D8,UnitsProduced) =SUMPRODUCT(C9:D9,UnitsP

6、roduced) 门门窗窗 单位利润单位利润$300$500 已用工时已用工时可用工时可用工时 工厂工厂1104=4 工厂工厂2026=12 工厂工厂33218=18 门门窗窗总利润总利润 生产量生产量43$2,700 单位产品工时消耗单位产品工时消耗 The spreadsheet for the Wyndor problem with a trial solution (4 doors and 3 windows) entered into the changing cells. 第四步：试求最优解第四步：试求最优解 2.6 应用应用Excel 求解线性规划问题求解线性规划问题 (1)Ex

7、cel Solver 的安装 Excel工具菜单中选择加载宏 (2)确定可变单元格和目标单元格 3 4 5 6 7 8 9 10 11 12 BCDEFG DoorsWindows Unit Profit$300$500 HoursHours UsedAvailable Plant 1101=1 Plant 2022=12 Plant 3325=18 DoorsWindowsTotal Profit Units Produced11$800 Hours Used Per Unit Produced (3)增加约束条件增加约束条件 DoorsWindows Unit Profit$300$500

8、 HoursHours UsedAvailable Plant 1101=1 Plant 2022=12 Plant 3325=18 DoorsWindowsTotal Profit Units Produced11$800 Hours Used Per Unit Produced (4)完成求解对话框完成求解对话框 (5)求解方式的选择求解方式的选择 (6)求解结果对话框求解结果对话框 (7) 求解结果报告求解结果报告灵敏性报告灵敏性报告极限报告极限报告 伟恩德公司电子表格求解模型伟恩德公司电子表格求解模型 Wyndor Glass Co. Product-Mix Problem 门门窗窗

9、单位利润单位利润$300$500 已用工时已用工时可用工时可用工时 工厂工厂1102=4 工厂工厂20212=12 工厂工厂33218=50%50% 非联合001010 01 11 1 卡车010111 10 00 0720720=720720 铁路1 10 01 10 00 00 01 11 1505505=1919 决策变量 阿什利阿什利A 贝德福德贝德福德B康索康索C邓比邓比D厄勒姆厄勒姆E 弗洛伦斯弗洛伦斯F 加斯顿加斯顿G 霍普特霍普特H合计合计 购买数量(千吨)55556006000 020201001000 04504500 01225=12251225 = 生产容量（千吨）30

10、0300600600510510655655575575680680450450490490 目标函数 采购成本总计(美元) 73267.573267.5 电子表格电子表格 (1)为了使供应炼焦煤的成本最小化为了使供应炼焦煤的成本最小化,NBS应该与每个供应商签订多应该与每个供应商签订多 少煤炭的供应量少煤炭的供应量? 答案如上表所示。答案如上表所示。 (2)NBS的总供应成本是多少的总供应成本是多少? 答案：供应炼焦煤的总成本是：答案：供应炼焦煤的总成本是： 成本成本 =49.50A+50.00B+61.00C+63.50D+66.50E+71.00F+72.50G+80.00H =7326

11、7.50 (3)NBS的平均供应成本是多少的平均供应成本是多少? 答案答案:平均成本是平均成本是73267.50/1225=59.81(美元美元/吨吨) 我们现在可以回答斯蒂芬提出的三个问题：我们现在可以回答斯蒂芬提出的三个问题： （4）炼焦煤的边际成本是多少，也就是说，炼焦煤额外增加一吨）炼焦煤的边际成本是多少，也就是说，炼焦煤额外增加一吨 花费花费NBS多少费用？多少费用？ （5）NBS应该考虑扩大卡车的运输能力吗？如果回答是肯定的，应该考虑扩大卡车的运输能力吗？如果回答是肯定的， 那么它们应该愿意花费多少？那么它们应该愿意花费多少？ （6）NBS应该考虑扩大铁路的运输能力吗？如果回答是肯

12、定的，应该考虑扩大铁路的运输能力吗？如果回答是肯定的， 那么它们应该愿意花费多少？那么它们应该愿意花费多少？ （7）为了从贝德福德矿业公司或加斯顿矿业公司获得更多的煤，）为了从贝德福德矿业公司或加斯顿矿业公司获得更多的煤， 斯蒂芬愿意签订一个比较高的价格协议吗？如果回答是肯定的，那斯蒂芬愿意签订一个比较高的价格协议吗？如果回答是肯定的，那 么他应该愿意支付的价格是多少？么他应该愿意支付的价格是多少？ 更深入的问题：更深入的问题： 这需要从求解以后的敏感性报告中获取有关信息来回答这些问题这需要从求解以后的敏感性报告中获取有关信息来回答这些问题 敏感性报告敏感性报告 （4）炼焦煤的边）炼焦煤的边

13、际成本是多少，也际成本是多少，也 就是说，炼焦煤额就是说，炼焦煤额 外增加一吨花费外增加一吨花费 NBS多少费用？多少费用？ 答：炼焦煤额外增炼焦煤额外增 加一吨花费加一吨花费NBS 61.5美元的费用美元的费用 （5）NBS应该考应该考 虑扩大卡车的运输虑扩大卡车的运输 能力吗？如果回答能力吗？如果回答 是肯定的，那么它是肯定的，那么它 们应该愿意花费多们应该愿意花费多 少？少？ 答答:应该扩大卡车应该扩大卡车 的运输能力的运输能力,NBS 愿意花费愿意花费1千美元千美元/ 千元千元 （6）NBS应该考应该考 虑扩大铁路的运输虑扩大铁路的运输 能力吗？如果回答能力吗？如果回答 是肯定的，那么

14、它是肯定的，那么它 们应该愿意花费多们应该愿意花费多 少？少？ 答答:铁路的运载能铁路的运载能 力为力为650千吨千吨,而实而实 际只用了际只用了505千吨千吨, 因此不需要增加铁因此不需要增加铁 路的运输能力路的运输能力. （7）为了从贝德）为了从贝德 福德矿业公司或加福德矿业公司或加 斯顿矿业公司获得斯顿矿业公司获得 更多的煤，斯蒂芬更多的煤，斯蒂芬 愿意签订一个比较愿意签订一个比较 高的价格协议吗？高的价格协议吗？ 如果回答是肯定的如果回答是肯定的 ，那么他应该愿意，那么他应该愿意 支付的价格是多少支付的价格是多少 ？ 答答:可以增加贝德可以增加贝德 福德矿业公司或加福德矿业公司或加 斯

15、顿矿业公司的采斯顿矿业公司的采 购量购量,其价格分别其价格分别 为为51.5美元美元/吨和吨和 73.5美元美元/吨吨 案例案例 二：二： 最优季度生产供货方案最优季度生产供货方案 某柴油机厂接到的客户订货合同规定必须在各季度交货的柴油机生某柴油机厂接到的客户订货合同规定必须在各季度交货的柴油机生 产任务各不相同，与此同时，由于种种原因该厂的季度生产能力与产任务各不相同，与此同时，由于种种原因该厂的季度生产能力与 单台柴油机的生产成本也随季度而变化。各季度的合同交货任务、单台柴油机的生产成本也随季度而变化。各季度的合同交货任务、 生产能力与单台柴油机生产成本数据如下表所示生产能力与单台柴油机生

16、产成本数据如下表所示 季度交货任务（台）生产能力（台）生产成本（万元/台） 1102510.8 2153511.1 3253011.0 4201011.3 每台柴油机在仓库中保存一个季度的储存成本为每台柴油机在仓库中保存一个季度的储存成本为0.15万元万元.由于交货由于交货 任务与生产成本随季度而变任务与生产成本随季度而变,工厂为了降低成本必须恰当地安排各个工厂为了降低成本必须恰当地安排各个 季度的生产数量季度的生产数量(例如在成本较低的季度多生产一些以便用来满足例如在成本较低的季度多生产一些以便用来满足 成本较高的后续季度的合同需求成本较高的后续季度的合同需求)才能降低成本才能降低成本.试确

17、定在保证完成试确定在保证完成 合同交货任务的前提下使工厂全年生产与储存成本达到最低的各季合同交货任务的前提下使工厂全年生产与储存成本达到最低的各季 度柴油机的生产安排度柴油机的生产安排 分析：分析： 交货季度交货季度 生产季度生产季度 1234生产能力生产能力 1X11X12X13X1425 2-X22X23X2435 3-X33X3430 4-X4410 交货任务交货任务10152520 交货季度交货季度 生产季度生产季度 1234生产能力生产能力 110.810.8+0.1510.8+0.310.8+0.4525 2-11.111.1+0.1511.1+0.335 3-11.011.0+0

18、.1530 4-11.310 交货任务交货任务10152520 决决 策策 变变 量量 成成 本本 理论模型理论模型 11121314 222324 3334 44 11121314 222324 3334 44 11 1222 132333 14243444 min10.810.9511.111.25 11.111.2511.4 1111.15 11.3 25 35 30 10 10 15 25 20 Zxxxx xxx xx x xxxx xxx xx x x xx xxx xxxx 生产能力限制生产能力限制 交货量限制交货量限制 电子表格模型电子表格模型 单位成本交货季度 生产季度季度1

19、季度2季度3季度4 季度110.810.9511.111.25 季度2-11.111.2511.4 季度3-1111.15 季度4-11.3 决策变量交货季度 生产季度季度1季度2季度3季度4实际生产总量生产能力 季度110100525=25 季度205005=35 季度30025530=30 季度40001010=3% 液体洗涤剂3%2%18%=18% 洗衣粉-1%4%8%=4% 总成本 电视印刷媒体($millions) 广告数量4310 单位广告增加的市场占有率 电子表格模型电子表格模型: 案例研究之二：复杂的广告组合问题案例研究之二：复杂的广告组合问题 Pronuevo公司是一家小公司

20、，它最近将一种新产品投放到某公司是一家小公司，它最近将一种新产品投放到某 个地区的市场中个地区的市场中,并且希望通过各种媒体对此产品进行宣传。因此该并且希望通过各种媒体对此产品进行宣传。因此该 公司与当地的一家专门从事这种地区宣传的广告代理商公司与当地的一家专门从事这种地区宣传的广告代理商PRCo进行进行 了联系，并将此任务完全托付给对方，预算金额总数为了联系，并将此任务完全托付给对方，预算金额总数为250,000欧欧 元。此广告代理商对当地市场有充分的了解，即了解通过各种媒体，元。此广告代理商对当地市场有充分的了解，即了解通过各种媒体， 如杂志，广播电台，或电视台等进行的宣传能够让多少人了解

21、此产如杂志，广播电台，或电视台等进行的宣传能够让多少人了解此产 品。广告公司建议在六种不同的媒体上进行两个月的宣传。对于每品。广告公司建议在六种不同的媒体上进行两个月的宣传。对于每 种媒体，广告公司都了解在其上进行广告的成本以及此媒体能够影种媒体，广告公司都了解在其上进行广告的成本以及此媒体能够影 响到的人数。此外每种媒体的影响指数也已知。响到的人数。此外每种媒体的影响指数也已知。 广告公司也了解每种媒体的最大使用量（如，电视台广告播放广告公司也了解每种媒体的最大使用量（如，电视台广告播放 次数不能超过次数不能超过8次）。下面的表列出了这些信息。次）。下面的表列出了这些信息。Pronuevo公

22、司希公司希 望此广告宣传计划至少能够影响望此广告宣传计划至少能够影响100,000人。应如何选择这些媒体人。应如何选择这些媒体 的组合才能够使广告的总影响指数最高？的组合才能够使广告的总影响指数最高？ 编号编号 媒体类型媒体类型 影响人数影响人数 单位费用单位费用 最大使用量最大使用量 影响指数影响指数 1 周报周报 12,000 1,500 4个星期个星期 3 2 月刊月刊 1,500 8,000 2个月个月 7 3 周刊周刊 2,000 12,000 8个周期个周期 8 4 电台广播电台广播 6,000 9,000 60次播放次播放 2 5 4*3米的户外广告牌米的户外广告牌 3,000

23、24,000 4个广告牌个广告牌 6 6 电视台电视台 9,000 51,000 8次播放次播放 9 分析：决策变量：每种类型广告使用量分析：决策变量：每种类型广告使用量 目标：影响总指数最高目标：影响总指数最高 约束：影响人数限制，预算资金限制，最大使用量限制约束：影响人数限制，预算资金限制，最大使用量限制 编号编号 媒体类型媒体类型 影响人数影响人数 单位费用单位费用 最大使用量最大使用量 影响指数影响指数 1 周报周报 12,000 1,500 4个星期个星期 3 2 月刊月刊 1,500 8,000 2个月个月 7 3 周刊周刊 2,000 12,000 8个周期个周期 8 4 电台广

24、播电台广播 6,000 9,000 60次播放次播放 2 5 4*3米的户外广告牌米的户外广告牌 3,000 24,000 4个广告牌个广告牌 6 6 电视台电视台 9,000 51,000 8次播放次播放 9 理论模型理论模型 123456 123456 123456 123456 max378269 121.52639100 1.581292451250 4,2,8,60,4,8 Zxxxxxx xxxxxx xxxxxx xxxxxx 广告宣传问题广告宣传问题 媒体类型周报月刊周刊电台广播户外广告牌电视台实际总数可用资源 影响人数12000150020006000300090001030

25、00=100000 单位费用150080001200090002400051000250000=250000 影响指数378269 媒体类型使用量 决策变量428440 = 最大使用量4286048 目标总指数122 编号编号 媒体类型媒体类型 影响人数影响人数 单位费用单位费用 最大使用量最大使用量 影响指数影响指数 1 周报周报 12,000 1,500 4个星期个星期 3 2 月刊月刊 1,500 8,000 2个月个月 7 3 周刊周刊 2,000 12,000 8个周期个周期 8 4 电台广播电台广播 6,000 9,000 60次播放次播放 2 5 4*3米的户外广告牌米的户外广告

26、牌 3,000 24,000 4个广告牌个广告牌 6 6 电视台电视台 9,000 51,000 8次播放次播放 9 最优方案：最优方案： Components of the Model LP模型的组成部分模型的组成部分 Decision variables 决策变量决策变量 Objective function 目标函数目标函数 Constraints 约束约束 Mathematical Statement of LP Problem 线性规划的数学描述线性规划的数学描述 线性规划要确定决策变量线性规划要确定决策变量 x1, x2, , xn 使得使得 Maximize Z c1x1cnxn

27、 Objective Function subject to a11x1a1nxn b1 a21x1 a2nxn b2 M am1x1 amnxn bm Functional Constraints and x1 0,xn 0 Nonnegativity Constraints 已知参数已知参数 c1, , cn ; a11, , amn ; b1, , bm. Assumptions of Linear Programming 线性规划的假设线性规划的假设 Linearity 线性线性 Divisibility 可分性可分性 Certainty 确定确定性性 Nonnegativity 非负性非负性 Why Use Linear Programming? 为什么要使用线性规划为什么要使用线性规划 线性规划很容易而有效率地被求解线性规划很容易而有效率地被求解 如果存在最优解，则肯定能够找