管理学线性规划问题课件

线性规划问题一、线性规划问题二、Excel求解线性规划问题三、实例讲解1h线性规划问题一、线性规划问题1h一、线性规划问题

——线性规划是运筹学的一个重要分支，是运筹学的最基本的部分。线性规划的应用及其广泛，从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事和经济计划管理决策领域都可以发挥作用，它是现代科学管理的一种重要手段。2h一、线性规划问题——线性规划是运筹学的一个重要分支，引言在经济生活中，人们经常遇到这样两类实际问题：1、资源给定，如何对给定资源予以充分地、合理地运用，使之完成的任务尽可能地多。2、任务给定，如何以尽可能少的资源消耗来完成给定的任务。

可见，上述两类问题都是寻求利润最大。第一类，是以最大收益扣除定量成本；第二类，是以定量收益扣除最小成本。

在满足一定条件时，这类优化问题都可以用线性规划的方法来予以解决。3h引言在经济生活中，人们经常遇到这样两类实际问题：3h线性规划的概念当收益和消耗均与计划指标呈正比时，一个规划问题所列出的数学表达式都是关于计划指标的线性关系式，称此类型规划问题为线性规划问题。线性规划问题是：在一组线性约束条件下，求一组非负变量的值，使一个线性目标函数达到最大或最小。4h线性规划的概念4h线性规划问题例1：某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品A产品B资源限制劳动力94360工时设备45200台时原材料310300公斤单位产品利润（元）70120问题：如何安排生产计划，使得获利最多？5h线性规划问题例1：某厂生产两种产品，需要三种资源，已知各产品分析：这是一个生产计划问题，设生产A产品X1kg,B产品X2kg.则该问题可以用如下模型来描述：MaxZ=70X1+120X2<目标函数>

9X1+4X2≤360

s.t.

4X1+5X2≤200<约束条件>

3X1+10X2≤300

X1≥0X2≥0

该模型的解为生产计划。线性规划问题6h分析：线性规划问题6h例2：某运输问题，已知资料如下表所示，问如何调运，使产销平衡且总运费最小？B1B2B3B4产量（吨）A15610360A2419740A3424860销量（吨）30504040单位运费产地销地单位：百万/吨7h例2：某运输问题，已知资料如下表所示，问如何调运，使产销平衡这是一个产销平衡运输问题，即：∑Ai

地产量ai=∑Bj地销量bj(i=1，2，3；j=1,2,3,4)

设从生产地Ai到销售地Bj的调运量为：Xij(i=1，2，3；j=1,2,3,4）

该问题的数学模型为：MinZ=5X11+6X12+10X13+3X14···+4X33+8X34X11+X12+X13+X14=60X21+X22+X23+X24=40

……s.t.X11+X21+X31=30

……X14+X24+X34=40Xij≥0(i=1，2，3；j=1,2,3,4）

——产量约束——销量约束8h这是一个产销平衡运输问题，即：——产量约束——销量约束8h从数学上来讲,它们的共同特征是:每个问题都用一组决策变量(x1,x2,···,xn)表示某一方案,这组未知数的值就代表一个具体的方案,通常要求这些未知数取值是非负的。(2)存在一定的限制条件(称为约束条件),这些条件都可以用关于决策变量的一组线性等式或不等式来表示。(3)都有一个目标要求,并且这个目标可表示为这组决策变量的线性函数(称为目标函数),按研究问题的不同,要求目标函数实现最大化或最小化。

线性规划问题是：在一组线性约束条件下，求一组非负变量的值，使一个线性目标函数达到最大或最小。9h从数学上来讲,它们的共同特征是:线性规划问题是：线性规划的三要素

决策变量：根据影响所要达到目的的因素找到决策变量——生产产品量，运输分配量等

目标函数：由决策变量和所要达到目的之间的函数关系确定目标函数；——最大利润，最小运费等

约束条件：由决策变量所受的限制条件确定决策变量所要满足的约束条件——原材料限制，工时限制等10h线性规划的三要素10h求解线性规划问题的方法：（1）数学方法：单纯形法，图解法等（2）计算机方法：各种软件（lingo,matlab，excel等）11h求解线性规划问题的方法：11h二、利用ExcelSolver求解线性规划问题12h二、利用ExcelSolver求解线性规划问题12h如何加载Excel的“规划求解”安装office的时候，系统默认的安装方式不会安装宏程序，需要用户根据自己的需求选择安装。下面是加载“规划求解”宏的步骤：（1）在“工具”菜单上，单击“加载宏”13h如何加载Excel的“规划求解”安装office的时候，系统（2）在弹出的对话框中的“可用加载宏”列表框中，选定待添加的加载宏“规划求解”选项旁的复选框，然后单击“确定”。单击“确定”以后，“工具”菜单下酒会出现一项“规划求解”。14h（2）在弹出的对话框中的“可用加载宏”列表框中，选定待添加的实例1——生产计划问题某公司最畅销的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问：如何安排生产，才能使总利润最大？15h实例1——生产计划问题某公司最畅销的3种商品单位利润不一，Aexcel求解结果：16hexcel求解结果：16h“规划求解”各参数解释和设置单击“规划求解”按钮，将会出现以下的规划求解参数的对话框。17h“规划求解”各参数解释和设置17h（1）目标单元格：存放目标函数的计算值的位置（2）最大值、最小值：在此指定是否希望目标单元格为最大值、最小值或某一特定数值。如果需要指定书，请在右侧编辑框中键入该值。（3）可变单元格：在此指定可变单元格。求解时其中的数值不断调整，直到满足约束条件并且“设置目标单元格”框中指定的单元格达到目标值。（4）约束：在此列出了规划求解的所有约束条件。（5）最长运算时间：在此设定求解过程的时间。默认值100（秒），一般可以满足大多数小型规划求解要求。（6）迭代次数：在此设定求解过程中迭代运算的次数，限制求解过程的时间。默认值100次，基本可以满足大多数小型规划求解要求。18h（1）目标单元格：存放目标函数的计算值的位置18h（7）精度：在此输入用于控制求解精度的数字，以确定约束条件单元格中的数值是否满足目标值或上下限。（8）允许误差：在此输入满足整数约束条件并可被接受的目标单元格求解结果与真实的最佳结果间的百分偏差。这个选项只用于具有整数约束条件的问题。设置的允许误差值越大，求解过程就越快。（9）采用线性模型：当模型中的所有关系都是线性的，并且希望解决线性优化问题时，选中此复选框可加速求解过程。（10）显示迭代结果：如果选中此复选框，每进行一次迭代都将中断“规划求解”，并显示当前的迭代结果。（11）假定非负：如果选中此复选框，则对于在“添加约束”对话框的“约束值”框中没有设置下限的所有可变单元格，假定其下限为0.19h（7）精度：在此输入用于控制求解精度的数字，以确定约束条件单Excel求解线性规划问题的步骤：1、在电子表格中确定目标单元格、活动单元格，输入所有参数；2、利用数据组相乘公式（常用函数里SUMPRODUCT)确定好约束条件的左边对应单元格；3、打开工具栏里的规划求解

（1）给定目标单元格、活动单元格，求最大或最小；

（2）添加约束条件

（3）选项栏里：线性、非负，确定

（4）确定求解20hExcel求解线性规划问题的步骤：20h

某自动售货机制造商的仓储中心坐落于济南、杭州、厦门3地区，而往来的客户主要位于北京、上海、广州、天津、香港与西安6大城市。由于各仓储中心地利环境、人力资源及区域性成本的不同，自动售货机的运送成本或多或少会有所差异，如下表1。当前各仓储中心的自动售货机的库存量如下表2。各地的需求量如下表3。问：为了能够有效降低运送成本，应如何安排运输，才能支付最低的运费又同时能够满足所有地区的运送需求。实例2——运费问题21h某自动售货机制造商的仓储中心坐落于济南、杭州地区需求量北京150上海225广州100天津250香港120西安150合计995表3各地需求量（单位：台）地区济南杭州厦门库存量400350500表2仓储中心库存总量（单位：台）实例2——运费问题表1运输成本（单位：元）

仓储中心地区济南杭州厦门北京5847108上海8746100广州1213057天津1496683香港62115164西安128283822h地区需求量北京150上海225广州100天津250香港120实例2——运费问题

仓储中心地区济南杭州厦门北京X11X12X13上海X21X22X23广州X31X32X33天津X41X42X43香港X51X52X53西安X61X62X63假设各仓储中心运往各地区的数量如下表：23h实例2——运费问题实例2——运费问题目标函数：MinZ=58X11+47X12+108X13+87X21···+28X62+38X63约束条件：SubjecttoX11+X12+X13=150X21+X22+X23=225X31+X32+X33=100X41+X42+X43=250X51+X52+X53=120X61+X62+X63=150X11+X21+X31+X41+X51+X61≤400X12+X22+X32+X42+X52+X62≤350X31+X32+X33+X43+X53+X63≤500Xij≥0且为整数（i,j=1,2···6）24h实例2——运费问题目标函数：MinZ=58X11+4实例2——运费问题25h实例2——运费问题25h线性规划问题一、线性规划问题二、Excel求解线性规划问题三、实例讲解26h线性规划问题一、线性规划问题1h一、线性规划问题

——线性规划是运筹学的一个重要分支，是运筹学的最基本的部分。线性规划的应用及其广泛，从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事和经济计划管理决策领域都可以发挥作用，它是现代科学管理的一种重要手段。27h一、线性规划问题——线性规划是运筹学的一个重要分支，引言在经济生活中，人们经常遇到这样两类实际问题：1、资源给定，如何对给定资源予以充分地、合理地运用，使之完成的任务尽可能地多。2、任务给定，如何以尽可能少的资源消耗来完成给定的任务。

可见，上述两类问题都是寻求利润最大。第一类，是以最大收益扣除定量成本；第二类，是以定量收益扣除最小成本。

在满足一定条件时，这类优化问题都可以用线性规划的方法来予以解决。28h引言在经济生活中，人们经常遇到这样两类实际问题：3h线性规划的概念当收益和消耗均与计划指标呈正比时，一个规划问题所列出的数学表达式都是关于计划指标的线性关系式，称此类型规划问题为线性规划问题。线性规划问题是：在一组线性约束条件下，求一组非负变量的值，使一个线性目标函数达到最大或最小。29h线性规划的概念4h线性规划问题例1：某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品A产品B资源限制劳动力94360工时设备45200台时原材料310300公斤单位产品利润（元）70120问题：如何安排生产计划，使得获利最多？30h线性规划问题例1：某厂生产两种产品，需要三种资源，已知各产品分析：这是一个生产计划问题，设生产A产品X1kg,B产品X2kg.则该问题可以用如下模型来描述：MaxZ=70X1+120X2<目标函数>

9X1+4X2≤360

s.t.

4X1+5X2≤200<约束条件>

3X1+10X2≤300

X1≥0X2≥0

该模型的解为生产计划。线性规划问题31h分析：线性规划问题6h例2：某运输问题，已知资料如下表所示，问如何调运，使产销平衡且总运费最小？B1B2B3B4产量（吨）A15610360A2419740A3424860销量（吨）30504040单位运费产地销地单位：百万/吨32h例2：某运输问题，已知资料如下表所示，问如何调运，使产销平衡这是一个产销平衡运输问题，即：∑Ai

地产量ai=∑Bj地销量bj(i=1，2，3；j=1,2,3,4)

设从生产地Ai到销售地Bj的调运量为：Xij(i=1，2，3；j=1,2,3,4）

该问题的数学模型为：MinZ=5X11+6X12+10X13+3X14···+4X33+8X34X11+X12+X13+X14=60X21+X22+X23+X24=40

……s.t.X11+X21+X31=30

……X14+X24+X34=40Xij≥0(i=1，2，3；j=1,2,3,4）

——产量约束——销量约束33h这是一个产销平衡运输问题，即：——产量约束——销量约束8h从数学上来讲,它们的共同特征是:每个问题都用一组决策变量(x1,x2,···,xn)表示某一方案,这组未知数的值就代表一个具体的方案,通常要求这些未知数取值是非负的。(2)存在一定的限制条件(称为约束条件),这些条件都可以用关于决策变量的一组线性等式或不等式来表示。(3)都有一个目标要求,并且这个目标可表示为这组决策变量的线性函数(称为目标函数),按研究问题的不同,要求目标函数实现最大化或最小化。

线性规划问题是：在一组线性约束条件下，求一组非负变量的值，使一个线性目标函数达到最大或最小。34h从数学上来讲,它们的共同特征是:线性规划问题是：线性规划的三要素

决策变量：根据影响所要达到目的的因素找到决策变量——生产产品量，运输分配量等

目标函数：由决策变量和所要达到目的之间的函数关系确定目标函数；——最大利润，最小运费等

约束条件：由决策变量所受的限制条件确定决策变量所要满足的约束条件——原材料限制，工时限制等35h线性规划的三要素10h求解线性规划问题的方法：（1）数学方法：单纯形法，图解法等（2）计算机方法：各种软件（lingo,matlab，excel等）36h求解线性规划问题的方法：11h二、利用ExcelSolver求解线性规划问题37h二、利用ExcelSolver求解线性规划问题12h如何加载Excel的“规划求解”安装office的时候，系统默认的安装方式不会安装宏程序，需要用户根据自己的需求选择安装。下面是加载“规划求解”宏的步骤：（1）在“工具”菜单上，单击“加载宏”38h如何加载Excel的“规划求解”安装office的时候，系统（2）在弹出的对话框中的“可用加载宏”列表框中，选定待添加的加载宏“规划求解”选项旁的复选框，然后单击“确定”。单击“确定”以后，“工具”菜单下酒会出现一项“规划求解”。39h（2）在弹出的对话框中的“可用加载宏”列表框中，选定待添加的实例1——生产计划问题某公司最畅销的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问：如何安排生产，才能使总利润最大？40h实例1——生产计划问题某公司最畅销的3种商品单位利润不一，Aexcel求解结果：41hexcel求解结果：16h“规划求解”各参数解释和设置单击“规划求解”按钮，将会出现以下的规划求解参数的对话框。42h“规划求解”各参数解释和设置17h（1）目标单元格：存放目标函数的计算值的位置（2）最大值、最小值：在此指定是否希望目标单元格为最大值、最小值或某一特定数值。如果需要指定书，请在右侧编辑框中键入该值。（3）可变单元格：在此指定可变单元格。求解时其中的数值不断调整，直到满足约束条件并且“设置目标单元格”框中指定的单元格达到目标值。（4）约束：在此列出了规划求解的所有约束条件。（5）最长运算时间：在此设定求解过程的时间。默认值100（秒），一般可以满足大多数小型规划求解要求。（6）迭代次数：在此设定求解过程中迭代运算的次数，限制求解过程的时间。默认值100次，基本可以满足大多数小型规划求解要求。43h（1）目标单元格：存放目标函数的计算值的位置18h（7）精度：在此输入用于控制求解精度的数字，以确定约束条件单元格中的数值是否满足目标值或上下限。（8）允许误差：在此输入满足整数约束条件并可被接受的目标单元格求解结果与真实的最佳结果间的百分偏差。这个选项只用于具有整数约束条件的问题。设置的允许误差值越大，求解过程就越快。（9）采用线性模型：当模型中的所有关系都是线性的，并且希望解决线性优化问题时，选中此复选框可加速求解过程。（10）显示迭代结果：如果选中此复选框，每进行一次迭代都将中断“规划求解”，并显示当前的迭代结果。（11）假定非负：如果选中此复选框，则对于在“添加约束”对话框的“约束值”框中没有设置下限的所有可变单元格，假定其下限为0.44h（7）精度：在此输入用于控制求解精度的数字，以确定约束条件单Excel求解线性规划问题的步骤：1、在电子表格中确定目标单元格、活动单元格，输入所有参数；2、利用数据组相乘公式（常用函数里SUMPRODUCT)确定好约束条件的左边对应单元格；3、打开工具栏里的规划求解

（1）给定目标单元格、活动单元格，求最大或最小；

（2）添加约束条件

（3）选项栏里：线性、非负，确定

（4）确定求解45hExcel求解线性规划问题的步骤：20h

某自动售货机制造商的仓储中心坐落于济南、杭州、厦门3地区，而往来的客户主要位于北京、上海、广州、天津、香港与西安6大城市。由于各仓储中心地利环境、人力资源及区域性成本的不同，自动售货机的运送成本或多或少会有所差异，如下表1。当前各仓储中心的自动售货机的库存量如下表2。各地的需求量如下表3。问：为了能够有效降低运送成本，应如何安排运输，才能支付最低的运费又同时能够满足所有地区的运送需求。实例2——运费问题46h某自动售货机制造商的仓储中心坐落于济南、杭州地区需求量北京150上海225广州100天津250香港120西安150合计995表3各地需求量（单位：台）地区济南杭州厦门库存量400350500表2仓储中心库存总量（单位：台）实例2——运费问题