A动画管理系统工程教学课件第六章：线性规划

管理系统决策定量分析模型：线性规划第一节线性规划模型、实例及求解第二节线性规划模型求解的一般方法：单纯形法第三节线性规划问题的对偶问题，对偶单纯形法第四节线性规划问题的灵敏性分析第五节多目标规划法中的目的规划法简介2/3/20231【第六章：线性规划*48*】有动画第一节线性规划模型、实例及求解一、线性规划予以解决的实际问题

1、资源给定，如何对给定资源予以充分地、合理地运用，使之完成的任务尽可能地多。

2、任务给定，如何以尽可能少的资源消耗来完成给定的任务。

可见，上述两类问题都是寻求利润最大。第一类，是以最大收益扣除定量成本；第二类，是以定量收益扣除最小成本。2/3/20232【第六章：线性规划*48*】有动画二、线性规划的定义：

当收益和消耗均与计划指标成正比时，一个规划问题所列出的数学表达式都是关于计划指标的线性关系式，称此类型规划问题为线性规划问题。

线性规划问题是：在一组线性约束条件下，求一组非负变量得值，使一个线性目标函数达到最大或者是最小。

2/3/20233【第六章：线性规划*48*】有动画三、线性规划的数学模型

例1：

某厂拟定利用三种资源：铸件、锻件、加工人时生产A、B两种型号的设备。已知资料如下表所示：

求总销售额最大的生产计划方案。4万元/台6万元/台设备售价120（百人时）24加工人时100（吨）32锻件270（吨）93铸件资源量BA2/3/20234【第六章：线性规划*48*】有动画

例1的模型（LP）

根据以上资料，建立（LP）模型如下：

（设A设备生产x1台；B设备生产x2台）〈1〉目标函数〈2〉约束条件该模型的解为生产计划2/3/20235【第六章：线性规划*48*】有动画

（LP）模型的形式：

1、矩阵形式

记：C=（c1、c2、c3、……cn）

X=（x1、x2、x3、……xn）TA=（aij）m×n

b=（b1、b2、b3、……bm）T

则（LP）模型的矩阵形式为：价值系数行向量决策变量列向量技术系数矩阵资源限定列向量2/3/20236【第六章：线性规划*48*】有动画2、极大化典型形式（实际问题一）3、极小化典型形式（实际问题二）2/3/20237【第六章：线性规划*48*】有动画

4、标准型形式（模型求解的基础）2/3/20238【第六章：线性规划*48*】有动画（LP）问题的基本术语

1、变量决策变量：对需要优化的经济量所设置的变量称之。附加变量：为求解（LP）模型所引入的变量称之。

（1）松弛变量：为处理约束条件所引入，又分为不足变量和剩余变量（2）人工变量：为人为地制造一个基而引入的变量2/3/20239【第六章：线性规划*48*】有动画2、目标函数；约束条件

3、（LP）模型的解的概念

可行解：称满足约束条件的解为可行解。最优解：能使目标函数得以满足的可行解称之为最优解。2/3/202310【第六章：线性规划*48*】有动画（LP）模型图解法x*1=20（台）、x*2=20（台）Z*=200（万元）2/3/202311【第六章：线性规划*48*】有动画图形放大2/3/202312【第六章：线性规划*48*】有动画（LP）模型图解法之步骤2/3/202313【第六章：线性规划*48*】有动画

图解法之结论：（1）（LP）模型的可行解域为一个凸多边形或凸多面体，它们的极点为有限多个。（2）（LP）模型的最优解如果存在，一定可以在凸集合的极点上得到。（3）若（LP）模型的最优解在一个极点上得到，则该模型最优解唯一；若在两个极点上同时取得，则该模型有多重最优解。（4）若作图以后；满足各约束条件的共同部分不存在，则该模型无可行解。（5）若找不到离目标函数线距离最远的可行解点，则该模型无有限最优解。（开区域时发生）2/3/202314【第六章：线性规划*48*】有动画1、线性规划模型的一般形式2/3/202315【第六章：线性规划*48*】有动画（LP）模型间相互转换的规则1、2、3、4、5、2/3/202316【第六章：线性规划*48*】有动画第二节

（LP）模型求解的单纯形法一、单纯形法的基本思想：

单纯形法的基本思想是从有限个基本可行解中选择几个予以比较，从而得到最优解。二、单纯形法的求解步骤：

1、以最简单的方法确定第一个基本可行解

2、判断该解是否最优，若是最优则最优解得到，若不是最优解则进行下一步

3、在保证目标函数至少不减（目标函数求最大值模型）的前提下，转换到另一个基本可行解上

4、重复判断步骤，直至寻找到最优解2/3/202317【第六章：线性规划*48*】有动画三、（LP）模型解的概念的扩充

基矩阵、非基矩阵、基向量、非基向量（口述）基变量、非基变量基向量对应的变量称之为基变量，非基向量对应的变量称之为非基变量。☆基本解当取定一个基以后，令全部的非基变量等于零，从方程组中解出基变量得值，由它们构成的解：

X=（x1、x2、……xj、……xn)T称之为一个基本解。显然，基本解的个数为有限多个，最多为个。☆基本可行解满足非负要求的基本解称之为基本可行解。2/3/202318【第六章：线性规划*48*】有动画四、单纯形法求解步骤及单纯形表结构特征求解步骤：

1、将模型变为标准型，列初表

2、判断解是否最优（判断准则：全部的σj≤0则达优），若不是最优则进行下一步

3、进行解的转换（1）确定基准列第k列（确定进基变量）

σk=max{σj}（σj＞0）（2）确定基准行第l行（确定退基变量）

θl=min{θi}θi=bi/aik

（aik＞0）（3）确定主元素：基准行与基准列交叉处的元素（4）进行矩阵的初等行变换，变换的目标是：

“基准列的主元素变为1；其余的元素变为0”4、重复判断步骤，直至寻求到最优解2/3/202319【第六章：线性规划*48*】有动画一、利用铸件、锻件、加工人时生产AB设备之例求解单纯形表2/3/202320【第六章：线性规划*48*】有动画例1求解的结论共搜索了三个基本可行解

X（1）=（0、0、270、100、120）

X（2）=（30、0、180、40、0）

X（3）=（20、20、30、0、0）最优解为：

X*=（20、20、30、0、0）

即：A、B设备各自生产20台最大销售收入为：Z*=200（万元）

2/3/202321【第六章：线性规划*48*】有动画单纯形表的结构特征

1、所有单纯形表共有特征

（1）基变量的列系数均为单位向量（2）基变量的检验数均为零（3）最右边的常量均大于等于零

2、最终单纯形表的特征（要会识别最终表）

（1）基变量的列系数均为单位向量（2）基变量的检验数均为零（3）最右边的常量均大于等于零

（4）检验数行全部小于等于零2/3/202322【第六章：线性规划*48*】有动画学生练习题1

用单纯形法求解2/3/202323【第六章：线性规划*48*】有动画2/3/202324【第六章：线性规划*48*】有动画学生练习题2用单纯形法求解2/3/202325【第六章：线性规划*48*】有动画2/3/202326【第六章：线性规划*48*】有动画五、用矩阵形式表出的单纯形表

公式（1）某非基变量检验数计算公式：

σj=Cj-CBB-1Pj

（2）某非基变量列系数计算公式：

Pj*=B-1Pj2/3/202327【第六章：线性规划*48*】有动画一、利用铸件、锻件、加工人时生产AB设备之例求解单纯形表2/3/202328【第六章：线性规划*48*】有动画六、利用ExcelSolver对线性规划模型求解步骤：

1、在电子表格中确定目标单元格、活动单元格，输入所有参数（aij、bi、cj）

2、利用数据组相乘公式（常用函数里SUMPRODUCT）确定好约束条件的左边对应的单元格

3、打开工具（T）栏里的规划求解（1）给定目标单元格、活动单元格，求最大（2）添加约束条件（3）选项栏里：线性、非负，确定（4）求解得下表链接2/3/202329【第六章：线性规划*48*】有动画利用ExcelSolver对（LP）模型例1求解链接2/3/202330【第六章：线性规划*48*】有动画物质配送问题之例例3：两个工厂生产同一种新产品，配送公司将该产品送到两个仓库。运送情况如下：

1、工厂1的产品通过铁路只能送到仓库1，产品的数量不限，单位运输成本为700元/单位。

2、工厂2的产品通过铁路只能送到仓库2，产品的数量不限，单位运输成本为900元/单位。

3、卡车可将多达50个单位的产品由工厂送到配送中心，再从配送中心以最多50个单位的载运量运到各仓库，其单位运费如图所示。

4、各厂的生产量、各仓库的所需量如图所示。求最低运输成本对应的运输方案。2/3/202331【第六章：线性规划*48*】有动画例3的配送网络示意图配送中心仓库2工厂2仓库1工厂1生产70单位需要90单位生产80单位需要60单位700/单位900/单位图三：配送公司配送网络300/单位200/单位400/单位400/单位[最多50单位][最多50单位][最多50单位][最多50单位]2/3/202332【第六章：线性规划*48*】有动画例3的变量设置设：

x1——工厂1至仓库1的运输量

x2——工厂2至仓库2的运输量

x3——工厂1至配送中心的运输量

x4——工厂2至配送中心的运输量

x5——配送中心至仓库1的运输量

x6——配送中心至仓库2的运输量根据条件分析建立模型如下：2/3/202333【第六章：线性规划*48*】有动画例3的配送网络示意图配送中心仓库2工厂2仓库1工厂1生产70单位需要90单位生产80单位需要60单位700/单位900/单位图三：配送公司配送网络300/单位200/单位400/单位400/单位[最多50单位][最多50单位][最多50单位][最多50单位]x1x3x4x2x5x62/3/202334【第六章：线性规划*48*】有动画例3的（LP）模型2/3/202335【第六章：线性规划*48*】有动画例3ExcelSolver求解2/3/202336【第六章：线性规划*48*】有动画例3求解结果：运输方案

x1

工厂1——仓库1：x*1=30x2

工厂2——仓库2：x*2=40x3

工厂1——配送中心：x*3=50x4

工厂2——配送中心：x*4=30x5

配送中心——仓库1：x*5=30x6

配送中心——仓库2：x*6=50Z总运费最小总运费为：Zmin=110000（费用单位）2/3/202337【第六章：线性规划*48*】有动画第三节线性规划问题的对偶问题，对偶单纯形法

一、线性规划问题的对偶问题的提出

1、原问题（LP）例1中的铸件、锻件、加工人时用于生产A、B两种设备，出让设备以后获得销售收入，将这样考虑的问题称之为原问题。

2、对偶问题（LD）将例1中的铸件、锻件、加工人时制定相应的价格y1、y2、y3，直接出让资源获得收入，将这样考虑的问题称之为原问题的对偶问题。2/3/202338【第六章：线性规划*48*】有动画二、对偶模型及对偶模型的建立

该模型称之为原模型（LP）的对偶模型，记为：（LD）（y1

、y2

、y3的设置及含义解释一下）2/3/202339【第六章：线性规划*48*】有动画三、原模型（LP）与其对偶模型（LD）模型间的关系

1、原模型为极大化典型形式，则其对偶模型为极小化典型形式：

2、（LP）与（LD）的系数矩阵互为转置

3、（LP）为m个约束条件，（LD）有m个决策变量

4、（LP）为n个决策变量,（LD）有n个约束条件

5、一个模型的变量非负，则另一模型的约束条件为不等式

6、一个模型的变量为自由变量，则另一模型的约束条件为等式2/3/202340【第六章：线性规划*48*】有动画两个模型对比原模型对偶模型2/3/202341【第六章：线性规划*48*】有动画四、对偶问题的性质

1、对称性：（LP）与（LD）互为对偶

2、弱对偶定理：若X(0)，Y(0)分别是原问题和其对偶问题的任一可行解，则有：CX(0)≤Y(0)b

该性质说明：两个模型的目标函数值互为界。2/3/202342【第六章：线性规划*48*】有动画

3、设X*、Y*分别为（LP）与（LD）的某一可行解，当CX*=Y*b时，则X*、Y*分别为（LP）与（LD）的最优解。

4、检验数与解之间的对应关系：（1）原模型单纯形表上检验数的相反数对应着其对偶模型的一个基本解。（2）原模型最终单纯形表上检验数的相反数对应着其对偶模型的最优解。2/3/202343【第六章：线性规划*48*】有动画具体的对应规则：（以最终表为例，其余表规则相同）（a）原模型松弛变量检验数的相反数对应着其对偶模型的决策变量的值；（b）原模型决策变量检验数的相反数对应着其对偶模型的松弛变量的值。由例1的最终表可得：

Y*=（01/25/400）

W*=270×0+100×1/2+120×5/4=200（万元）最终单纯型表64000x1x2x3x4x5bi0x1001-15/49/8304x20101/2-1/4206x3100-1/43/820zj6401/25/4σj000-1/2-5/42/3/202344【第六章：线性规划*48*】有动画2/3/202345【第六章：线性规划*48*】有动画五、对偶决策变量y*i

的经济含义

1、在给定资源最优配置时，y*i为单位第i种资源的增加给目标函数所带来的贡献。（边际贡献）

2、y*i称之为在给定资源最优配置时第i种资源的影子价格，影子价格是在给定资源最优配置时对第i种资源的一种估价。

3、y*i可理解为是可以利用的现行市场价格（边际成本）的最高限度。例如：y*2=1/2，则现行市场价格小于1/2时，对锻件可以适当予以增加；若现行市场价格大于1/2时，对锻件不能予以增加。

4、y*i=0的资源称之为富裕资源；y*i≠0的资源称之为紧缺资源。

5、需注意的问题（口述）2/3/202346【第六章：线性规划*48*】有动画五、对偶单纯形法单纯形法：保持原问题的解（B-1b）为可行解，让其对偶问题的解（CBB-1A-C）由非可行解逐步变化到可行解

对偶单纯形法：保持对偶问题的解为可行解（CBB-1A-C≥0），让原问题的解（B-1b）由非可行解逐步变化到可行解

CBB-1A-C=（0，CBB-1N-CN，CBB-1）为全部的检验数，即对偶问题的解XBXNXLB-1bIB-1NB-1检验数0CBB-1N-CNCBB-12/3/202347【第六章：线性规划*48*】有动画对偶单纯形法的步骤（参看例14）

第一步：列初始单纯形表

第二步：确定基准行（找出(B-1b)r=min{(B-1b)i|(B-1b)i＜0}，即bi列中负值中的最小者，则第r行为基准行，xr为退基变量。若bi列中没有负值，则已得最优解）

第三步：确定基准列，先计算：则第s列为基准列，xs为进基变量

〈若基准行没有负值，则该问题无可行解〉

第四步：以基准行、基准列交叉处的元素为主元素，进行初等行变换，得新的单纯形表后返回第二步。2/3/202348【第六章：线性规划*48*】有动画例14用对偶单纯形法求解下述线性规划模型解：将模型化为标准型Y*=（0，3/2，1/8，0）Z*=8×3/2+16×1/8=14Z*=－Z‘用对偶单纯形法求解的最优解：2/3/202349【第六章：线性规划*48*】有动画例14对偶单纯行法求解表2/3/202350【第六章：线性规划*48*】有动画第四节线性规划问题灵敏性分析

一、线性规划问题灵敏性分析的内容

1、参数bi、cj发生改变问题的分析

2、新增加一个约束条件问题的分析

3、新增加一个决策变量问题的分析二、参数bi发生改变问题的分析

1、bi参数发生改变的实际原因

2、求△bi的允许范围的前提条件（保持原各资源的影子价格不变）

3、△bi的确定过程（参看例子）

4、对第i种资源考虑予以增减的步骤（口述）2/3/202351【第六章：线性规划*48*】有动画

参数bi发生改变问题的分析

△bi的确定过程之例：求△b2最初单纯型表64000x1x2x3x4x5bi0x3931002700x4320101000x524001120zj00000σj64000最终单纯型表64000x1x2x3x4x5bi0x3001-15/49/8304x20101/2-1/4206x1100-1/43/820zj6401/25/4σj000-1/2-5/42/3/202352【第六章：线性规划*48*】有动画处理如下：最初单纯型表64000x1x2x3x4x5bi0x393100270+0△b20x432010100+1△b20x524001120+0△b2zj00000σj64000最终单纯型表64000x1x2x3x4x5bi0x3001-15/49/830-15/4△b24x20101/2-1/420+1/2△b26x1100-1/43/820-1/4△b2zj6401/25/4σj000-1/2-5/42/3/202353【第六章：线性规划*48*】有动画△bi的确定过程之例：求△b2（其他资源量不变）

1、设法确定出最终表上常量与△b2的关系：

2、要不改变影子价格，则要仍然为最终表，故要求：

3、联立上述不等式解之得：

2/3/202354【第六章：线性规划*48*】有动画

△b2=20时

0x3001-33/411/8-454x2010

1/2-1/4

306x1100-1/4

3/8

15

zi640

1/211/4

σj000-1/2-11/4

0x400-4/151-3/10

124x201

2/150-1/10

246x110-1/150

3/10

18

zi64

2/15012/5

σj00-2/150-12/5

当△b2=20时，超范围，右边出现负数，用对偶单纯型法处理一次得：新的最优解：x1=18，x2=24，Z*=6×18+4×24=204（8×1/2）

x4=12表明：增加的20单位的锻件多出12个单位，只能配置8个单位。2/3/202355【第六章：线性规划*48*】有动画三、参数cj发生改变问题的分析

1、cj参数发生改变的实际原因

2、求△cj的允许范围的前提条件（保持原最优解不变）

3、△cj的确定过程（参看例子）最终单纯型表64000x1x2x3x4x5bi0x3001-15/49/8304x20101/2-1/4206x1100-1/43/820zj6401/25/4σj000-1/2-5/42/3/202356【第六章：线性规划*48*】有动画最终单纯型表6+△c14000x1x2x3x4x5bi0x3001-15/49/8304x20101/2-1/4206+△c1x1100-1/43/820zj6+△c1401/2-1/4△c15/4+3/8△c1σj000-1/2+1/4△c1-5/4-3/8△c12/3/202357【第六章：线性规划*48*】有动画△cj的确定过程之例：求△c1（余下的cj不变）

1、确定出原终表上-1/2、-5/4与△c1的关系：

2、要保持原最优解不变，则要仍然为最终表，故要求检验数行全部小于等于零，即：

3、联立上述不等式组解之得：

2/3/202358【第六章：线性规划*48*】有动画关于△bi

、△cj的确定可用灵敏性分析报告2/3/202359【第六章：线性规划*48*】有动画四、新增加一个约束条件问题的分析

1、新增加一个约束条件后原最优解受到影响否的判断

2、若原最优解受到影响，新的最优解的确定判定方法一：将原最优解带入新增约束条件，若满足，则原解不变；若不满足，则原解要变。判定方法二：在原最终表上加一行、一列后，将基变量的列系数变为单位向量，若右边没有出现负数，则原解不变；若右边出行负数，则原解要变。当右边出现负数时，用对偶单纯型法处理之，可得新的最优解。2/3/202360【第六章：线性规划*48*】有动画例：电力资源约束：单位消耗：5，3电力可用总量：若为180万千瓦小时……

若为151万千瓦小时……

当电力总量为180万千瓦小时时，两种方法判定结论：原方案不变；当电力总量为151万千瓦小时时，两种方法判定结论：原方案要变；由方法二判定后，在判定的基础上，用对偶单纯型法处理可得新的最优解为：

x1=17，x2=22，Z*=1902/3/202361【第六章：线性规划*48*】有动画

640000

x1x2x3x4x5x6

0x3001-33/411/80304x2010

1/2-1/40206x1100-1/4

3/80200x6530001151

zi640

1/211/4

σj000-1/2-11/4

0x3001-33/411/80304x2010

1/2-1/40206x1100-1/4

3/80200x6000-1/4-11/81-91、变5为0

03011/4-17/8151

zi640

1/211/40

σj000-1/2-11/40

0x3001-401214x2010

5/90-2/9226x1100-1/30

1/3170x5000

2/91-8/98

zi640

2/9011/9

σj000-2/90-11/9

2/3/202362【第六章：线性规划*48*】有动画五、新增加一个决策变量问题的分析

1、新增加一个决策变量以后原最优解改变否的判断

通过计算新决策变量（此时为非基变量）的检验数来判定

2、若原最优解改变，新的最优解的确定用单纯型法来确定2/3/202363【第六章：线性规划*48*】有动画

P6488

15

6400011

x1x2x3x4x5x6

0x3001-33/411/8

30

4x2010

1/2-1/4

20

6x1100-1/4

3/8B-1P620

zi640

1/211/4

σj000-1/2-11/4σ6=？

-3c6=11的σ6

P6（488）

1c6=15的σ6

当c6=11时，新产品不投产，因为σ6=-3

；