《线性规划与电子表格》由会员分享，可在线阅读，更多相关《线性规划与电子表格（84页珍藏版）》请在金锄头文库上搜索。
1、Session 2Linear Programming With Spreadsheet线性规划与电子表格线性规划与电子表格Session Topics? An Class Working Example 一个课堂操作举例一个课堂操作举例? Basic Concepts of Linear Programming 线性规划的基本概念线性规划的基本概念 ?The Graphical Method for Solving LP线性规划的图解法线性规划的图解法? Using Excel Solver to Solving用微软用微软Excel Solver 求解求解? Key Categories
2、of LP Problems线性规划问题的主要类型线性规划问题的主要类型?Three Classic Applications of LP三个经典的线性规划应用三个经典的线性规划应用每个小组都有一组拼装玩具每个小组都有一组拼装玩具(8个小块和个小块和6 大块大块) ，这些是你们的原材料（，这些是你们的原材料（raw materials），你们要用这些原材料去生产桌和椅（），你们要用这些原材料去生产桌和椅（ tables and chairs）这两种产品（）这两种产品（products），具体拼装图如下一个幻灯片。），具体拼装图如下一个幻灯片。The Lego Production Proble
3、m 拼装玩具生产拼装玩具生产自己动手自己动手你怎么去分析呢？你怎么去分析呢？想想看！想想看！原材料原材料6 大块大块8 小块小块产品产品桌椅桌椅 Profit = $20/TableProfit = $15/Chair自己动手自己动手Maximize ($15)Chairs+($20)Tables subject toLarge Bricks:Chairs+2Tables6 Small Bricks:2Chairs+2Tables8andChairs 0, Tables0.为了最小化成本或最大化利润的目的需要对一 些稀缺资源进行配置为了最小化成本或最大化利润的目的需要对一 些稀缺资源进行配置自
4、己动手自己动手你的答案是什么？你的答案是什么？Components of the Model 模型的组成部分模型的组成部分?Decision variables 决策变量决策变量?Objective function 目标函数目标函数?Constraints 约束约束使用使用 EXCELEXCEL 求解线性规划求解线性规划Excel自自1991年问世，目前已有几千万用户；其免费的规划求解软件由年问世，目前已有几千万用户；其免费的规划求解软件由Frontline System提供提供 (http:/)，专为大多数没有受 过，专为大多数没有受 过OR/MS专门训练的用户设计；专门训练的用户设计；E
5、xcel将将GUI，各种函数功能，模型语言，优化软件 和编程功能，各种函数功能，模型语言，优化软件 和编程功能 (VBA) 结合在统一的环境下；结合在统一的环境下；Excel 提供了强大的数据组织、运算和呈现功能，在提供了强大的数据组织、运算和呈现功能，在 Excel表格中可用更工程化的方式提供模型使用 的数据，并可将输出结果用各种图表的方式表示 出来；表格中可用更工程化的方式提供模型使用 的数据，并可将输出结果用各种图表的方式表示 出来；EXCELEXCEL 模型的基本构成模型的基本构成Excel通过表格通过表格(cell)所含数据或公式来表示运筹模型 的变量、目标函数、约束方程和模型参数所
6、含数据或公式来表示运筹模型 的变量、目标函数、约束方程和模型参数:?数据：数据：Excel 强大的数据组织与呈现功能可使模型数据 组织的更简洁明了；强大的数据组织与呈现功能可使模型数据 组织的更简洁明了；?变量：变量：Excel 中的可变单元格定义决策变量，决策变量 是模型求解的未知量，也称为可变量；中的可变单元格定义决策变量，决策变量 是模型求解的未知量，也称为可变量；?目标函数：由目标单元格中的数学表达式表示；目标函数：由目标单元格中的数学表达式表示；?约束：约束由表示约束左边项与右边项的数学表达式或 数值的单元格定义，通常约束的左边项是数学表达式， 右边项既可是表达式，也可是参数约束：约
7、束由表示约束左边项与右边项的数学表达式或 数值的单元格定义，通常约束的左边项是数学表达式， 右边项既可是表达式，也可是参数如何进入如何进入Excel中的优化模块中的优化模块选择主菜单“工具”“规划求解”可进入“规划求解 参数” 定义窗口； 如找不到“规划求解”项，可通过“工具” “加载宏 ”加入该项功能。如果在选择主菜单“工具”“规划求解”可进入“规划求解 参数” 定义窗口； 如找不到“规划求解”项，可通过“工具” “加载宏 ”加入该项功能。如果在“加载宏加载宏”中找不到中找不到“规划求 解规划求 解”项，须用项，须用office 安装盘加入该项功能。安装盘加入该项功能。建立电子表格模型建立电
8、子表格模型步骤步骤1：数据单元格：数据单元格?把这个问题的所有数据输入到电子表格中把这个问题的所有数据输入到电子表格中?确定行和列的约束条件确定行和列的约束条件?将数据单元格填充颜色（如：蓝色）将数据单元格填充颜色（如：蓝色）3 4 5 6 7 8BCDE FG TablesChairs Profit$20.00$15.00Available Large Bricks216 Small Bricks228Bill of Materials建立电子表格模型建立电子表格模型步骤步骤2：可变单元格：可变单元格?在电子表格上为决策变量添加单元格在电子表格上为决策变量添加单元格?为决策变量单元格填充颜色
9、（如：黄色）为决策变量单元格填充颜色（如：黄色）TablesChairs Profit$20.00$15.00Available Large Bricks216 Small Bricks228TablesChairs Production Quantity:00Bill of Materials建立电子表格模型建立电子表格模型步骤步骤3：目标函数单元格：目标函数单元格?定义目标函数的等式模型，等式要包括所有的数据单元格 和可变单元格，以便确定收益（如：总利润或总成本）定义目标函数的等式模型，等式要包括所有的数据单元格 和可变单元格，以便确定收益（如：总利润或总成本）?为目标函数单元格填充颜色（
10、如：橙色）为目标函数单元格填充颜色（如：橙色）Total Profit=SUMPRODUCT(C4:D4,C11:D11)TablesChairs Profit$20.00$15.00Available Large Bricks216 Small Bricks228TablesChairsTotal Profit Production Quantity:10$20.00Bill of Materials建立电子表格模型建立电子表格模型步骤步骤4：约束条件：约束条件?为每个资源添加限制条件，在电子表格中计算总的资源 消耗量（输出单元格）。为每个资源添加限制条件，在电子表格中计算总的资源 消耗量（
11、输出单元格）。?在三个连续的单元格中定义约束条件。如：如果中输出 以下三个条款（数量在三个连续的单元格中定义约束条件。如：如果中输出 以下三个条款（数量A，数量，数量B）。）。 TablesChairs Profit$20.00$15.00Total UsedAvailable Large Bricks213=3% Liquid Detergent3%2%18%=18% Powder Detergent-1%4%8%=4%Total Cost TelevisionPrint Media($millions) Advertising Units4310Increase in Sales per
12、Unit of Advertising要从甲、乙两地调出物资，分别供应要从甲、乙两地调出物资，分别供应A、B、C、D。已知 各地的供应量、需求量及每吨运费如下表所示，假定运费 与运量成正比，试确定总运费最小的调拨方案。已知 各地的供应量、需求量及每吨运费如下表所示，假定运费 与运量成正比，试确定总运费最小的调拨方案。解解A B C D 甲乙甲乙x11x12x13 x14 x21x22x23x241700 1100 200 100量在运输表上对应地的物资数量，则各变地运到为从设jixijA B C D 供应量供应量甲乙甲乙2 5 7 4 2000 5 3 6 8 1100 1700 1100 2
13、00 100需求量需求量4 , 3 , 2 , 1; 2 , 1, 0100200110017001100200086354752min241423132212211124232221141312112423222114131211=+=+=+=+=+=+=jixxxxxxxxxxxxxxxxxxxxxxxxxzij数学模型数学模型线性规划的图解法线性规划的图解法图解法简单、直观，便于初学者了解线性规划基本原理和几何意义；例：用图解法求解生产计划问题图解法简单、直观，便于初学者了解线性规划基本原理和几何意义；例：用图解法求解生产计划问题max: z = 50x1 + 30x2s.t.4x1 +
14、 3x2 1202x1 + x2 50x1 0，x2 0x2x140 50 30 2x1+ x2 5020 10 10 20 30 4x1+3x2 120z = 50x1+30x2= 600z = 50x1+30x2= 900z = 50x1+30x2= 1350(15, 20)图解法求解步骤图解法求解步骤?画直角坐标系；画直角坐标系；?依次做每条约束线，找出可行域；若不存在可行域,该问题无解；依次做每条约束线，找出可行域；若不存在可行域,该问题无解；?做目标函数线，根据目标类型平移，直到该线即将离开可行域时与该线接触的最后一点即为一最优解；做目标函数线，根据目标类型平移，直到该线即将离开可行
15、域时与该线接触的最后一点即为一最优解；?若该线可无限制地在可行域内移动,则该问题无界。若该线可无限制地在可行域内移动,则该问题无界。?确定解的数值。确定解的数值。例例5：用图解法求解：用图解法求解 max: z = x1 + x2 s.t.x1 + 2x2 4 x1 2x2 5 x1, x2 0无可行解的线性规划问题无可行解的线性规划问题14235123x1x2 x1 + 2x2 4x1 - 2x2 5有无界解的线性规划问题 （有无界解的线性规划问题 （Unbounded Solution）max：x + 1/3y s.t.x + y 20 -2x + 5 y 150 x 5 x 0, y 0可行域可行域x301020y010204003040可行域可行域413120203最优解最优解如果改变优化方向如果改变优化方向min：x + 1/3y s.t.x + y 20 -2x + 5 y 150 x 5 x 0, y 0yx存在无穷多最优解存在无穷多最优解如果目标函数线平行与一个约束线，线性规划 问题
