[管理学]线性规划问题课件.ppt

1、h1一、线性规划问题二、Excel 求解线性规划问题三、实例讲解h2 线性规划是运筹学的一个重要分支，是运筹学的最基本的部分。线性规划的应用及其广泛，从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事和经济计划管理决策领域都可以发挥作用，它是现代科学管理的一种重要手段。h3引言引言在经济生活中，人们经常遇到这样两类实际问题：1、资源给定，如何对给定资源予以充分地、合理地运用，使之完成的任务尽可能地多。2、任务给定，如何以尽可能少的资源消耗来完成给定的任务。可见，上述两类问题都是寻求利润最大。第一类，是以最大收益扣除定量成本；第二类，是以定量收益扣除最小成本。在满足一定条件时，这类优

2、化问题都可以用线性规划的方法来予以解决。h4线性规划的概念线性规划的概念 当收益和消耗均与计划指标呈正比时，一个规划问题所列出的数学表达式都是关于计划指标的线性关系式，称此类型规划问题为线性规划问题。线性规划问题是：在一组线性约束条件下，求一组非负变量的值，使一个线性目标函数达到最大或最小。h5例1：某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品产品A产品产品B资源限制资源限制劳动力劳动力94360工时工时设备设备45200台时台时原材料原材料310300公斤公斤单位产品利润（元）单位产品利润（元）70120问题：如何安排生产计划，使得获利最多

3、？h6分析：这是一个生产计划问题，设生产A产品X1kg,B产品X2kg.则该问题可以用如下模型来描述：Max Z=70X1+120X2 9X1+4X2360 s.t.4X1+5X2 200 3X1+10X2 300 X10 X20 该模型的解为生产计划。h7例2：某运输问题，已知资料如下表所示，问如何调运，使产销平衡且总运费最小？B B1 1B B2 2B B3 3B B4 4产量产量（吨）（吨）A15610360A2419740A3424860销量（吨）30504040单位运费产地销地单位：百万/吨h8这是一个产销平衡运输问题，即：Ai 地产量ai=Bj 地销量bj (i=1，2，3；j=1

4、,2,3,4)设从生产地Ai到销售地Bj的调运量为：Xij(i=1，2，3；j=1,2,3,4）该问题的数学模型为：Min Z=5 X11+6 X12+10X13+3X14+4X33+8 X34 X11+X12+X13+X14=60 X21+X22+X23+X24=40 s.t.X11+X21+X31=30 X14+X24+X34=40 Xij 0(i=1，2，3；j=1,2,3,4）产量约束销量约束h9从数学上来讲,它们的共同特征是:每个问题都用一组决策变量(x1,x2,xn)表示某一方案,这组未知数的值就代表一个具体的方案,通常要求这些未知数取值是非负的。(2)存在一定的限制条件(称为约束

5、条件),这些条件都可以用关于决策变 量的一组线性等式或不等式来表示。(3)都有一个目标要求,并且这个目标可表示为这组决策变量的线性函数(称为目标函数),按研究问题的不同,要求目标函数实现最大化或最小化。h10线性规划的三要素线性规划的三要素u 决策变量：根据影响所要达到目的的因素找到决策变量 生产产品量，运输分配量等u 目标函数：由决策变量和所要达到目的之间的函数关系确定目标函数；最大利润，最小运费等u 约束条件：由决策变量所受的限制条件确定决策变量所要满足的约束条件 原材料限制，工时限制等h11求解线性规划问题的方法：求解线性规划问题的方法：（1）数学方法：单纯形法，图解法等（2）计算机方法

6、：各种软件（lingo,matlab，excel等）h12二、利用二、利用Excel SolverExcel Solver求解线性规划问题求解线性规划问题h13如何加载如何加载Excel的的“规划求解规划求解”安装office的时候，系统默认的安装方式不会安装宏程序，需要用户根据自己的需求选择安装。下面是加载“规划求解”宏的步骤：（1）在“工具”菜单上，单击“加载宏”h14（2）在弹出的对话框中的“可用加载宏”列表框中，选定待添加的加载宏“规划求解”选项旁的复选框，然后单击“确定”。单击“确定”以后，“工具”菜单下酒会出现一项“规划求解”。h15实例实例11生产计划问题生产计划问题某公司最畅销

7、的3种商品单位利润不一，A为10元，B为8元，C为9元。不论哪一种商品，其生产过程都需要经过“制造”、“测试”、“品管”和“封装”四个部门，而每种商品在各个部门所耗费的工时也不一样，如下表。每个部门的可用工时也是有限制的，如下表。每单位所需人工工时（小时）每单位所需人工工时（小时）各部门可用各部门可用工时（小时）工时（小时）部门A产品B产品C产品制造1.120.840.767200测试0.480.680.724100品管0.880.71.046100封装0.120.440.381800问：如何安排生产，才能使总利润最大？h16excel求解结果：h17“规划求解规划求解”各参数解释和设置各参数

8、解释和设置单击“规划求解”按钮，将会出现以下的规划求解参数的对话框。h18（1）目标单元格：存放目标函数的计算值的位置（2）最大值、最小值：在此指定是否希望目标单元格为最大值、最小值或某一特定数值。如果需要指定书，请在右侧编辑框中键入该值。（3）可变单元格：在此指定可变单元格。求解时其中的数值不断调整，直到满足约束条件并且“设置目标单元格”框中指定的单元格达到目标值。（4）约束：在此列出了规划求解的所有约束条件。（5）最长运算时间：在此设定求解过程的时间。默认值100（秒），一般可以满足大多数小型规划求解要求。（6）迭代次数：在此设定求解过程中迭代运算的次数，限制求解过程的时间。默认值100次

9、，基本可以满足大多数小型规划求解要求。h19（7）精度：在此输入用于控制求解精度的数字，以确定约束条件单元格中的数值是否满足目标值或上下限。（8）允许误差：在此输入满足整数约束条件并可被接受的目标单元格求解结果与真实的最佳结果间的百分偏差。这个选项只用于具有整数约束条件的问题。设置的允许误差值越大，求解过程就越快。（9）采用线性模型：当模型中的所有关系都是线性的，并且希望解决线性优化问题时，选中此复选框可加速求解过程。（10）显示迭代结果：如果选中此复选框，每进行一次迭代都将中断“规划求解”，并显示当前的迭代结果。（11）假定非负：如果选中此复选框，则对于在“添加约束”对话框的“约束值”框中没

10、有设置下限的所有可变单元格，假定其下限为0.h20Excel Excel 求解线性规划问题的步骤：求解线性规划问题的步骤：1、在电子表格中确定目标单元格、活动单元格，输入所有参数；2、利用数据组相乘公式（常用函数里SUMPRODUCT)确定好约束条件的左边对应单元格；3、打开工具栏里的规划求解 （1）给定目标单元格、活动单元格，求最大或最小；（2）添加约束条件 （3）选项栏里：线性、非负，确定 （4）确定求解h21 某自动售货机制造商的仓储中心坐落于济南、杭某自动售货机制造商的仓储中心坐落于济南、杭州、厦门州、厦门3 3地区，而往来的客户主要位于北京、上海、广地区，而往来的客户主要位于北京、上

11、海、广州、天津、香港与西安州、天津、香港与西安6 6大城市。由于各仓储中心地利环大城市。由于各仓储中心地利环境、人力资源及区域性成本的不同，自动售货机的运送成境、人力资源及区域性成本的不同，自动售货机的运送成本或多或少会有所差异，如下表本或多或少会有所差异，如下表1 1。当前各仓储中心的自。当前各仓储中心的自动售货机的库存量如下表动售货机的库存量如下表2 2。各地的需求量如下表。各地的需求量如下表3 3。问：。问：为了能够有效降低运送成本，应如何安排运输，才能支付为了能够有效降低运送成本，应如何安排运输，才能支付最低的运费又同时能够满足所有地区的运送需求。最低的运费又同时能够满足所有地区的运送

12、需求。h22地区地区需求量需求量北京150上海225广州100天津250香港120西安150合计995地区地区济南济南杭州杭州厦门厦门库存量400350500表2 仓储中心库存总量（单位：台）实例2运费问题表1 运输成本（单位：元）仓储仓储中心中心地区地区济南济南杭州杭州厦门厦门北京5847108上海8746100广州1213057天津1496683香港62115164西安1282838h23实例2运费问题 仓储中仓储中心心 地区地区济南济南杭州杭州厦门厦门北京X11X12X13上海X21X22X23广州X31X32X33天津X41X42X43香港X51X52X53西安X61X62X63假设各

13、仓储中心运往各地区的数量如下表：h24实例2运费问题目标函数：Min Z=58 X11+47 X12+108 X13+87 X21+28 X62+38 X63 约束条件：Subject to X11+X12+X13=150 X21+X22+X23=225 X31+X32+X33=100 X41+X42+X43=250 X51+X52+X53=120 X61+X62+X63=150 X11+X21+X31+X41+X51+X61400 X12+X22+X32+X42+X52+X62350 X31+X32+X33+X43+X53+X63500 Xij0 且为整数（i,j=1,26）h25实例实例22运费问题运费问题