第一章线性规划课件

第一章线性规划

1.1线性规划的模型与图解法

1.2单纯形法

1.3对偶问题与灵敏度分析

1.4线性整数规划

1.5运输问题第一章线性规划

1.1线性规划的模型与图解法1.1线性规划的模型与图解法一、线性规划问题及其数学模型

在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源，以得到最大的效益。1.1线性规划的模型与图解法在生产管理和经营活动

例1.1某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：

试拟订使总收入最大的生产计划方案。例1.1某工厂可生产甲、乙两种产品，需消耗煤、电、油三1）决策变量：需决策的量，即待求的未知数；2）目标函数：需优化的量，即欲达的目标，用决策变量的表达式表示；3）约束条件：为实现优化目标需受到的限制，用决策变量的等式或不等式表示。线性规划模型的三要素1）决策变量：需决策的量，即待求的未知数；2）目标函数：需优

例1.1某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：

试拟订使总收入最大的生产计划方案。例1.1某工厂可生产甲、乙两种产品，需消耗煤、电、油三在本例中约束条件：分别来自资源煤、电、油限量的约束，和产量非负的约束，表示为决策变量：甲、乙产品的计划产量，记为；目标函数：总收入记为,则,为体现对其追求极大化，在的前面冠以极大号Max；在本例中约束条件：分别来自资源煤、电、油限量的约束，和产量非解：设安排甲、乙产量分别为,总收入为，则模型为：解：设安排甲、乙产量分别为,总收入为，则模型为：线性规划模型的一个基本特点：

目标和约束均为变量的线性表达式。如果模型中出现如的非线性表达式，则不属于线性规划。线性规划模型的一个基本特点：

目标和约束均为变量的线例1.2某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表：水泥(公斤/m2)4000(千工日)147000(千块)150000(吨)20000(吨)110000(千元)资源限量3.5——18025120大模住宅3.0——19030135壁板住宅4.521011012105砖混住宅人工(工日/m2)砖(块/m2)钢材(公斤/m2)造价(元/m2)

资源住宅体系要求在充分利用各种资源条件下使建造住宅的总面积为最大，求建造方案。例1.2某市今年要兴建大量住宅,已知有三种住宅体系可以大量

解:设今年计划修建砖混、壁板、大模住宅各为,为总面积,则本问题的数学模型为:

前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了12个变量，10个约束条件。解:设今年计划修建砖混、壁板、大模住宅各为练习：某畜牧厂每日要为牲畜购买饲料以使其获取A、B、C、D四种养分。市场上可选择的饲料有M、N两种。有关数据如下：

0.40.62.01.7

00.10.20.1

0.100.10.2410售价（元/公斤）牲畜每日每头需要量NM

每公斤含营养成分

ABCD试决定买M与N二种饲料各多少公斤而使支出的总费用为最少？练习：某畜牧厂每日要为牲畜购买饲料以使其获取A、B、C、D四解：设购买M、N饲料各为，则解：设购买M、N饲料各为，则线性规划模型的一般形式：以MAX型、约束为例决策变量：目标函数：约束条件：线性规划模型的一般形式：以MAX型、约束为例决策变量：模型一般式的矩阵形式则模型可表示为记模型一般式的矩阵形式则模型可表示为记回顾例1.1的模型其中表示决策变量的向量；表示产品的价格向量；表示资源限制向量；表示产品对资源的单耗系数矩阵。回顾例1.1的模型一般地

中称为决策变量向量，

称为价格系数向量,

称为技术系数矩阵,

称为资源限制向量。问题：为什么称为技术系数矩阵？一般地

中称为决策变量向量，称为价格系数向量,图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些重要性质。二、线性规划问题的图解法图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解1.做约束的图形

先做非负约束的图形；再做资源约束的图形。以例1.1为例，其约束为图解法步骤1.做约束的图形以例1.1为例，其约束为图解法步骤问题：不等式的几何意义是什么？怎样做图？问题：不等式的几何意义是什么？怎样做图？1.做约束的图形

先做非负约束的图形；再做资源约束的图形。以例1.1为例，其约束为图解法步骤各约束的公共部分即模型的约束，称可行域。1.做约束的图形以例1.1为例，其约束为图解法步骤各约束的公

对于目标函数任给二不同的值，便可做出相应的二直线，用虚线表示。2.做目标的图形以例1.1为例，其目标为，分别令，做出相应的二直线，便可看出增大的方向。对于目标函数2.做目标的图形以例1.1为例，其目标3.求出最优解将目标直线向使目标优化的方向移，直至可行域的边界为止，这时其与可行域的“切”点即最优解。

如在例1.1中，是可行域的一个角点，经求解交出的二约束直线联立的方程，可解得3.求出最优解如在例1.1中，由图解法的结果得到例1.1的最优解，将其代入目标函数求得相应的最优目标值。说明当甲产量安排20个单位，乙产量安排24个单位时，可获得最大的收入428。由图解法的结果得到例1.1的最优解练习：用图解法求解

下面的线性规划。练习：用图解法求解

下面的线性规划。-最优解在什么位置获得？-线性规划的可行域是一个什么形状？问题：在上两例中

——多边形，而且是“凸”形的多边形。——在边界，而且是在某个顶点获得。-最优解在什么位置获得？-线性规划的可行域是一个什么（1）线性规划的约束集（即可行域）是一个凸多面体。凸多面体是凸集的一种。所谓凸集是指：集中任两点的连线仍属此集。试判断下面的图形是否凸集：凸集中的“极点”，又称顶点或角点，是指它属于凸集，但不能表示成集中某二点连线的内点。如多边形的顶点。由图解法得到线性规划解的一些特性（1）线性规划的约束集（即可行域）是一个凸多面体。凸多面体因为，由图解法可知，只有当目标直线平移到边界时，才能使目标z达到最大限度的优化。问题：本性质有何重要意义？（2）线性规划的最优解（若存在的话）必能在可行域的顶点获得。——它使得在可行域中寻优的工作由“无限”上升为“有限”，从而为线性规划的算法设计提供了重要基础。因为，由图解法可知，只有当目标直线平移到边界时，才能使目标（3）线性规划解的几种情形1）唯一最优解2）多重最优解3）无可行解4）无有限最优解（无界解）（3）线性规划解的几种情形1）唯一最优解2）多重最优解3）无

内容回顾与思考1.线性规划解决的是一类什么问题？2.线性规划模型构成的三要素？3.线性规划模型的一般式？4.图解法的一般步骤？5.图解法得到线性规划哪些性质？内容回顾与思考

单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格（G.B.Danzig）提出。尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。1.2单纯形法单纯形法是求解线性规划的主要算法，1947年由美

早在二战期间，在美国空军服役的科学家丹捷格就提出了“单纯形方法”。这个方法当时曾经保密，直到战后的1947年，当丹捷格离开军队，转任斯坦福大学教授之后，才公开发表。

丹捷格不仅提出了单纯形法，而且在线性规划相关研究领域做出了一系列杰出的贡献。他被人们誉为“线性规划之父”，以他的名字命名的“丹捷格奖”成为运筹学界的最高奖项之一。（1914-2005）早在二战期间，在美国空军服役的科学家丹捷格就提出了“单一、单纯形法的预备知识1.线性规划的标准型来自实际问题的线性规划模型形式各异，在用单纯形法求解之前，先要将模型化为统一的形式——标准型：标准型的特征：Max型、等式约束、非负约束一、单纯形法的预备知识1.线性规划的标准型标准型的特征：M非标准形式如何化为标准？（1）Min型化为Max型因为，求一个函数的极小点，等价于求该函数的负函数的极大点。注意：Min化为Max后，最优解不变，最优值差负号。加负号如非标准形式如何化为标准？注意：Min化为Max后，最优解不（2）不等式约束化为等式约束分析：以例1.1中煤的约束为例

x3称为松弛变量。问题：它的实际意义是什么？——煤资源的“剩余”。之所以“不等”是因为左右两边有一个差额，可称为“松弛量”，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为x3

，则有（2）不等式约束化为等式约束x3称为松弛变量。问题：它的实练习：请将例1.1的约束化为标准型解：增加松弛变量则约束化为可见：松弛变量的系数恰构成单位阵问题：松弛变量在目标中的系数为何？问题：标准型与原来模型解的关系？练习：请将例1.1的约束解：增加松弛变量则约束化为可见：松弛一般地，记松弛变量的向量为Xs，则(3)当模型中有某变量xk没有非负要求，称为自由变量,则可令

化为标准型。一般地，记松弛变量的向量为Xs，则(3)当模型中有某例如可化为X2为自由变量例如可化为X2为自由变量2.基本概念（1）可行解与最优解直观上，可行解是可行域中的点，是一个可行的方案；最优解是可行域的边界角点，是一个最优的方案。2.基本概念直观上，可行解是可行域中的点，是一个可行的方案（2）基矩阵与基变量基矩阵(简称基)：系数阵A中的m阶可逆子阵，记为B；其余部分称为非基矩阵，记为N。基向量：基B中的列；其余称非基向量。基变量：与基向量Pj对应的决策变量xj，记其组成的向量为XB；与非基向量对应的变量称非基变量，记其组成的向量为XN。如指出A中的基。记A中的列为Pj，则每个Pj对应于一个xj，即。（2）基矩阵与基变量基矩阵(简称基)：系数阵A中的m阶可逆子第一章线性规划课件——6个。一般地，m×n

阶矩阵A中基的个数最多有多少个？问题：本例的中一共有几个基？——6个。一般地，m×n阶矩阵A中基的个数最多有多少个？（3）基本解与基本可行解（3）基本解与基本可行解可见：一个基本解是由一个基决定的。注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。称非负的基本解为基本可行解（简称基可行解）。可见：一个基本解是由一个基决定的。称非负的基本解为基本可行解例1.4

在例1.3的模型中，求相应于基B1和B2的基本解，它们是否基本可行解？例1.4在例1.3的模型中，求相应于基B1和B2的基本解第一章线性规划课件上二组概念间的联系：系数阵A中可找出若干个基B每个基B都对应于一个基本解非负的基本解就是基本可行解上二组概念间的联系：系数阵A中可找出若干个基B几种解之间的关系：可行解基本解非可行解基本可行解问题：基本可行解是可行域中的哪些点？几种解之间的关系：可行解基本解非可行解基本可行解问题：基本可3.基本定理（1）线性规划的可行域是一个凸多面体。（2）线性规划可行域的顶点与基本可行解一

一对应。（3）线性规划的最优解（若存在的话）必能

在可行域的顶点获得。3.基本定理（1）线性规划的可行域是一个凸多面体。（2）线

二、单纯形法的步骤确定初始基本可行解检验其是否最优？寻找更好的基本可行解否是stop单纯形法是一种迭代的算法，它的思想是在可行域的顶点——基本可行解中寻优。由于顶点是有限个（为什么？）,因此，算法经有限步可终止。方法前提：模型化为标准型二、单纯形法的步骤确定初始基本可行解检验其是否最优？寻找1.确定初始基可行解由于基可行解是由一个可行基决定的，因此，确定初始基可行解X0相当于确定一个初始可行基B0。方法：若A中含I，则B0=I；若A中不含I，则要用人工变量法构造一

个I。问题：若B0=I，则X0=？1.确定初始基可行解由于基可行解是由一个可行基决定的，因此，2.最优性检验分析：用什么检验？——目标。记为σ，当σ≤0时，当前解为最优。σ称检验数向量。而目标所以2.最优性检验分析：用什么检验？——目标。记为σ，当σ方法：（1）计算每个xj的检验数（2）若所有σj

≤0，则当前解为最优；否则，非最优，转3。问题：非最优的特征为何？方法：（1）计算每个xj的检验数（2）若所有σj≤0，则3.寻找更好的基可行解由于基可行解与基对应，即寻找一个新的基可行解，相当于从上一个基B0变换为下一个新的基B1，因此，本步骤也称为基变换。3.寻找更好的基可行解由于基可行解与基对应，即寻找一个新的基第一章线性规划课件换基后，转2。即再检验，直至满足最优性条件。换基后，转2。即再检验，直至满足最优性条件。以例1.1为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。（1）先将模型化为标准型A中含I（P3，P4，P5），可以用单纯形法求解。以例1.1为例，可按上述单纯形法的步骤求出其最优解，其大致的(2)确定初始基可行解、检验(2)确定初始基可行解、检验计算检验数确定进基向量为P2计算检验数确定进基向量为P2再计算检验比确定出基向量为P5。再计算检验比确定出基向量为P5。（3）换基、计算下一个基可行解、再检验，直

至最优计算检验数，确定进基向量为P1再计算检验比，确定出基向量为P4（3）换基、计算下一个基可行解、再检验，直计算检验数，确定进第一章线性规划课件练习：对于下面的线性规划（1）先用图解法求解；（2）将模型化为标准型；（3）再用单纯形法步骤求出其最优解，并指出求解过程中每一个基可行解相当于可行域的哪一个角点。练习：对于下面的线性规划（1）先用图解法求解；解：（1）图解法求解0解：（1）图解法求解0（2）将模型化为标准型A中含I（P3，P4），可以用单纯形法求解。（2）将模型化为标准型A中含I（P3，P4），可以用单纯形法（3）用单纯形法求解计算检验数，确定进基向量为P1再计算检验比，确定出基向量为P4.确定初始基可行解、检验（3）用单纯形法求解计算检验数，确定进基向量为P1再计算检验第一章线性规划课件0求解过程中每一个基可行解相当于可行域的哪一个角点？0求解过程中每一个基可行解相当于可行域的哪一个角点？问题：当模型规模较大时，计算量很大。事实上，单纯形法的实现是在单纯形表上完成的。总结上述过程：问题：当模型规模较大时，计算量很大。事实上，单纯形法的实现是三、单纯形表

单纯形表是基于单纯形法的步骤设计的计算表格，是单纯形法的具体实现。回顾单纯形法步骤三、单纯形表单纯形表是基于单纯形法的步骤设而相邻两个之间只有一列不同，可分析其逆阵间关系：即每个可由上一个经以为主元的初等行变换得到，基于此设计了单纯形表。而相邻两个之间只有一列不同，可分析其逆阵间关系：即每个单纯形表的主要结构：表头的完整结构：θ第一张表的B-1是什么？第一组基变量是什么？单纯形表的主要结构：表头的完整结构：θ第一张表的B-1是什么用单纯形表计算的主要过程：（1）建立初表：（4）计算下一张表（用

初等行变换）：（2）计算检验数判断最优：（3）计算检验比换基：用单纯形表计算的主要过程：（1）建立初表：（4）计算下一张表例1.5用单纯形法解例1.1例1.5用单纯形法解例1.1标准模型的A中是否含I？——松弛变量系数恰好构成I。标准模型的A中是否含I？——松弛变量系数恰好构成I。[][]中表示进基列与出基行的交叉元，下一张表将实行以它为主元的初等行变换（也称高斯消去）。方法是：先将主元消成1，再用此1将其所在列的其余元消成0。[][]中表示进基列与出基行的交叉元，下一[][][][]（请解释其实际意义）[]甲乙产品产量的最优计划、相应的最大收入和资源剩余（请解释其实际意义）[]甲乙产品产量的最优计划、相基变量的检验数和系数列有何特征？检验数均为0，系数列均为单位向量列[][]本题全部单纯形表基变量的检验数和系数列有何特征？检验数均为0，系数列均为单位练习：用单纯形法求解下面的线性规划练习：用单纯形法求解下面的线性规划0前面曾用图解法和单纯形法步骤求解过：0前面曾用图解法和单纯形法步骤求解过：第一章线性规划课件[]注：1.表上每一列的含义：2.每张表上B-1的位置在哪？——对应于初表中I的位置。如果整个，则为无界解[]注：1.表上每一列的含义：2.每张表上B-1的位每张表的每一列都等于本表的B-1乘以初表的相应列[][]每张表的每一列都等于本表的B-1乘以初表的相应列[[]例1.6：填出下面表中的空白L[]例1.6：填出下面表中的空白L[]L基变量的系数列[]L基变量的系数列练习：用单纯形法求解下面的线性规划直观上有什么特点？——目标与某约束斜率相同练习：用单纯形法求解下面的线性规划直观上有什么特点？——目标第一章线性规划课件[]问题：本题的单纯形终表检验数有何特点？——

非基变量x2的检验数等于零。多重最优[]问题：本题的单纯形终表检验数有何特点？四、大M法设模型已经化为标准型但A中不含I。添加人工变量，将模型（1）化为（2）四、大M法添加人工变量，将模用单纯形法求解（2）的结果：-最优解基变量中不含，则（2）的最

优解的前n个分量即（1）的最优解；-最优解基变量中含有，则（1）无解。M称为罚因子，其作用是迫使出基。用单纯形法求解（2）的结果：M称为罚因子，其作用是迫使例1.7：用单纯形法求解下面的线性规划模型已经是标准型，但A中不含I。例1.7：用单纯形法求解下面的线性规划模型已经是标准型，但A解：增加人工变量将模型化为解：增加人工变量将模型化为[][]人工变量出基后，不会再进基，故其出基后的系数列不必再参加迭代运算。[][]人工变量出基后，不会再进基，故[]人工变量都已出基[]人工变量都已出基注：（1）解的几种情况在单纯形表上的体现-唯一最优：终表非基检验数均小于零；-多重最优：终表非基检验数有等于零；-无界解：有正检验数相应系数列均非正；-无解：最优基中含有人工变量。（2）Min型单纯形表与Max型的区别仅在于：

检验数反号，即-令负检验数中最小的对应的变量进基；-当检验数均大于等于零时为最优。

问题：Min型模型的大M法人工变量模型是什么？注：（2）Min型单纯形表与Max型的区别仅在于：问题：Mi

内容回顾与思考1.基本可行解的概念和几何意义？2.单纯形法的原理步骤？3.单纯形表的原理和结构？4.大M法的原理和步骤？5.Min型单纯形表计算方法？内容回顾与思考1.3对偶问题与灵敏度分析一、对偶问题及其模型

对偶理论是线性规划的重要基础理论，它揭示了：每一个线性规划都存在与它对偶的一个线性规划，二者之间有密切的联系，以至于把二者放在一起研究往往比单独研究一个问题更有意义。

1.3对偶问题与灵敏度分析一、对偶问题及其模型例1.8回顾例1.1的生产问题，记为（P）甲乙煤电油（P）这时有另一家厂商提出要购买其煤、电、油全部资源，并希望花费尽量少。试建立购买者的线性规划模型。例1.8回顾例1.1的生产问题，记为（P）甲乙煤电9y1+4y2+3y3≥74y1+5y2+10y3≥12解：设其购买三种资源的价格分别为y1,y2,y3，总花费为w，则MinW=360y1+200y2+300y3煤电油甲乙s.t.y1,y2,y3≥0（D）分析模型的三要素：购买者的决策变量、目标函数、约束条件9y1+4y2+3y3≥74y1+5y2+10y3≥12解：甲乙煤电油（P）煤电油甲乙（D）9y1+4y2+3y3≥74y1+5y2+10y3≥12Minw=360y1+200y2+300y3s.t.y1,y2,y3≥0≤bACmaxnm（P）≥minCTATbTnm（D）（D）称为（P）的对偶问题，（P）称为（D）的原始问题甲乙煤电油（P）煤电油甲乙（D）对偶模型的一般式（对偶定义）（P）（D）原始问题对偶问题这是最常见的对称式对偶模型。例1.8已经显示了二者间具有十分对称的对应关系。对偶模型的一般式（对偶定义）（P）（D）原始问题对偶问题这是二、对偶性质1.对称性：对偶的对偶就是原始问题。maxw’=-Ybs.t.-YA≤-C Y≥0minz’=-CXs.t.-AX≥-b X≥0对偶定义minw=Ybs.t.YA≥CY≥0maxz=CXs.t.AX

≤

b X≥0对偶定义即（P）和（D）互为对偶，是对称的。二、对偶性质maxw’=-Ybminz’=-CX对偶定义如果模型中含有等式约束或自由变量，则可转化为不等式约束和非负变量的形式分析。maxz=CXs.t.AX=b X≥0minw=Ybs.t.YA≥C

如果模型中含有等式约束或自由变量，则可转化为不等式约束和非负练习：写出下面线性规划的对偶模型练习：写出下面线性规划的对偶模型解：既然模型是Min型，可按（D）整理，令解：既然模型是Min型，可按（D）整理，令然后按（P）写出其对偶：设对偶变量为然后按（P）写出其对偶：设对偶变量为证：由（P），（D）的约束可得2.弱对偶性设

分别为（P），（D）的任一可行解，则。（P）（D）图示：问题：若(P),(D)有一为无界解，则另一为何？证：由（P），（D）的约束可得2.弱对偶性设3.解的最优性设，分别为（P）与（D）的可行解，且,则，

。

证：对任可行解，由弱对偶性，故，同理，。图示：3.解的最优性设，分别为（P）与（D）的可行解，设线性规划问题1为例1.9,Y*是其对偶问题的最优解；又设线性规划问题2为其中k是已知常向量。求证：设线性规划问题1为例1.9,Y*是其对偶问题的最优解；又设证：问题1与问题2的对偶问题分别是（Ⅰ）（Ⅱ）（Ⅰ）与（Ⅱ）的约束相同，故（Ⅰ）的最优解Y*是（Ⅱ）的可行解。由弱对偶性，而由解的最优性，，故证：问题1与问题2的对偶问题分别是（Ⅰ）（Ⅱ）（Ⅰ）与（Ⅱ）4.对偶定理若（P）有最优解，则（D）也有最优解，且最优值相同。证：对（P）增加松弛变量Xs，化为4.对偶定理若（P）有最优解，则（D）也有最优解，且最优值设其最优基为B，则终表为其检验数为则满足即是（D）的可行解，且，由解的最优性，。取，设其最优基为B，则终表为其检验数为则满足即是由对偶定理的证明过程可知，原始问题（P）的单纯形终表可同时得到（P）和（D）的最优解由对偶定理的证明过程可知，原始问题（P）的单纯形终表可同时得例如，在1.2的练习中已知的终表如下，指出其对偶问题的最优解和最优值。例如，在1.2的练习中已知的终表如下，指出其对偶问题的最5.互补松弛定理设

分别为（P）与（D）的可行解，则

是最优解的充要条件是。证：5.互补松弛定理设分别为（P）与（D）的y1…

yi…

ym

ym+1…ym+j…ym+nx1…xj…xnxn+1…xn+i…xn+m

对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量xjym+j=0，yixn+i=0（i=1,2,…,m;j=1,2,…,n），在一对变量中，一个大于0，另一个一定等于0。y1…yi…ymym+1…ym+j…例1.10已知线性规划问题其对偶问题的最优解为，利用对偶性质求原始问题的最优解。例1.10已知线性规划问题其对偶问题的最优解为解：先写出其对偶将代入约束，第二至四约束为严格不等式，由互补松弛性，又，故解得解：先写出其对偶将三、对偶的经济意义1.对偶最优解的经济解释：资源的影子价格（ShadowPrice）

——对偶问题的最优解：买主最低出价；

——原问题资源的影子价格：当该资源

增加1单位时引起的总收入的增量：卖主的内控价格。注意：影子价格是在最优解前提下，并且其他资源不变。三、对偶的经济意义1.对偶最优解的经济解释：资源的影子价格（例1.11

例1.1（煤电油例）的单纯形终表如下：（1）请指出资源煤电油的影子价格，并解释其经济意义。（2）由影子价格的定义推导电的影子价格。例1.11例1.1（煤电油例）的单纯形终表如下：（1）请解：（1）煤、电、油的影子价格分别是0，1.36，0.52；其经济意义是当煤、电、油分别增加1单位时可使总收入分别增加0、1.36、0.52。解：增量恰好为1.36。（2）由影子价格的定义，在最优解前提下，电再增加1单位引起总收入由变化为：增量恰好为1.36。（2）由影子价格的定义，在最优解前提下，2.对偶约束的经济解释——产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的收益y1y2ym增加单位资源可以增加的收益减少一件产品可以节省的资源2.对偶约束的经济解释——产品的机会成本机会成本y1增加3.对偶松弛变量的经济解释——产品的差额成本机会成本差额成本利润差额成本=机会成本－利润3.对偶松弛变量的经济解释——产品的差额成本机会成本差额成

在利润最大化的生产计划中（1）影子价格大于0的资源没有剩余；（2）有剩余的资源影子价格等于0；（3）安排生产的产品机会成本等于利润；（4）机会成本大于利润的产品不安排生产。4.互补松弛关系的经济解释在利润最大化的生产计划中4.互补松弛关系的经济解释练习：填空1.根据线性规划的互补松弛定理，影子价格大于零的资源一定

剩余；安排生产的产品机会成本一定

利润。（）A．没有，小于B．没有，大于C．没有，等于D．有，等于C2.若线性规划的原始问题增加一个变量，则其对偶问题就增加一个

；因而对偶的最优目标值将可能变

。（）A．约束，好B．约束，坏C．变量，好D．变量，坏B练习：填空CB四、对偶单纯形法回顾单纯形法是在保持可行性下改善最优性。能否尝试对称的思路，在保持下改善可行性？四、对偶单纯形法回顾单纯形法是在保持可行性下改主要步骤（1）确定初始基，使；（2）检验，若，是最优，否则转（3）；（3）基变换：先确定出基，再确定进基。基变换后再转（2）。效果：出基改善，进基保持。若，则无可行解主要步骤（1）确定初始基，使；基变例1.12：求解下面的线性规划特点：化为标准型后A中不含I，但能否不用大M法？如果检验数均非正则可。例1.12：求解下面的线性规划特点：化为标准型后A中不含I，引入松弛变量，化为标准型[]引入松弛变量，化为标准型[][][][][]将线性规划与经济问题相关联的研究贡献，使得

T.G.Koopman（库普曼）和

L.V.Kamtorovich（康脱罗维奇）二人共同分享了1975年的第7届诺贝尔经济学奖。将线性规划与经济问题相关联的研究贡献，使得主要讨论C、b和变量结构变化时对解的影响。讨论模型的系数或变量发生小的变化时对解的影响（如它们在何范围内变化时可使原最优解或最优基不变？）五、灵敏度分析对解怎样影响？可行性：最优性：主要讨论C、b和变量结构变化时对解的影响。讨论模型的系数或变1.b变化时的分析设第r种资源变为，因为它只影响可行性，故只要变化后的使得，则原最优基不变。只要由解出的范围即可。1.b变化时的分析设第r种资源变为例1.13

例1.1（煤电油例）的单纯形终表如下：问题：油的资源限量在何范围变化时，可使原最优基不变？例1.13例1.1（煤电油例）的单纯形终表如下：问题：油解：由解得：，即油的限量在增加100至减少72范围内变化时，原最优基保持不变。最优基不变是什么意思？——投产结构不变。解：由解得：，即油的限量在增加10价格变为时，因为它只影响最优性，即对检验数产生影响，故只要其使变化后的即可。2.C变化时的分析当是非基变量的价格系数时，只影响自己的检验数，由一个不等式解得的范围。当是基变量的价格系数时，要影响所有的检验数，由一组不等式解得的范围。价格变为时，因为它只影响最优性，即[]例1.14在下面的线性规划问题中，分析价格系数c2在何范围内变化时可使原最优解不变。解：c2是非基价格系数，由解得，即c2价格上涨不超过4都不会投产。[]例1.14在下面的线性规划问题中，分析价格系数3.增加新变量时的分析

主要讨论增加新变量xn+1是否有利。经济意义是第n+1种新产品是否应当投产，数学意义是xn+1是否应进基。方法：计算的检验数，

若，则增加，即投产有利；

若，则不增加，即投产无利。市场价影子价经济意义：3.增加新变量时的分析方法：计算的检验数[]例1.15在例1.14中，若再考虑一个新变量x5，其价格系数为3，对两种资源的单耗系数分别为2和1，请分析它是否应进基。x5应进基。[]例1.15在例1.14中，若再考虑一个新变量x（1）电的影子价格是多少？使最优基仍适用的电的变化范围为何？（2）若有人愿以每度1元的价格向该厂供应25度电，是否值得接受？（3）甲产品的价格在何范围内变化时，现最优解不变？例1.16

例1.1（煤电油例）的单纯形终表如下：（1）电的影子价格是多少？使最优基仍适用的电的变化范围为何？（4）若现又考虑一新产品丙，其资源单耗为10，2，5，售价为6.5，问该产品是否应投产？解：（1）电的影子价格是1.36。由解得，即是原最优基B仍适用的电的变化范围。（4）若现又考虑一新产品丙，其资源单耗为10，2，5，售价为（2）若有人愿以每度1元的价格向该厂供应25度

电，是否值得接受？解：（2）值得。

因25在B的适用范围内（即影子价格适用），且。（2）若有人愿以每度1元的价格向该厂供应25度（3）甲产品的价格在何范围内变化时，现最优解不变？解：甲产品的价格c1是基变量的价格系数。由得，故使不变的的变化范围为：。由得，（3）甲产品的价格在何范围内变化时，现最优解不变？解：甲产品（4）若现又考虑一新产品丙，其资源单耗为10，2，5，售价为6.5，问该产品是否可投产？因为故丙产品可以投产。解：（4）若现又考虑一新产品丙，其资源单耗为10，2，5，售价为综合案例：派公司的产品规划派公司是一个生产高尔夫器材的小型公司，近期推出了高、中价位的高尔夫袋新产品（标准袋和高档袋），经销商对此产品十分感兴趣，并订购了派公司下3个月的全部产品。该高尔夫袋的生产过程主要包括4道工序：切割并印染原材料、缝合、成型（插入支撑架和球棒分离装置等）、检验和包装。有关数据如表1。派公司需决定标准袋和高档袋各生产多少可使公司的总利润最大。综合案例：派公司的产品规划派公司是一个生产高尔夫器材（1）写出此问题的线性规划模型，约束及决策变量依表1中次序；工序时间单耗产品表1切割印染缝合成型检验包装

产品单位利润（美元）标准袋高档袋7/1011/25/612/31/101/41093个月内最大生产能力（小时）630600708135（小时）（1）写出此问题的线性规划模型，约束及决策变量依表1中次序；（2）引入松弛变量（依约束次序）后用单纯形法计算得某单纯形表如表2，请填完表中空白，并判断其是否终表，如果是，请写出最优生产计划、最大利润和资源剩余；表2（2）引入松弛变量（依约束次序）后用单纯形法计算得某单纯形表（3）写出此问题的对偶问题的模型，及对偶的最优解与最优值；（4）写出成型时间的影子价格，求使该影子价格不变的成型时间的变化范围；（5）若标准袋的利润可能发生变化，则其在何范围内变化时，可使原最优计划不改变？解：（1）设标准袋和高档袋的产量分别为，总利润为z,则模型为（3）写出此问题的对偶问题的模型，及对偶的最优解与最优值；解第一章线性规划课件

是终表，最优生产计划是生产标准袋540个，高档袋252个，最大利润7668美元，缝合时间余120，检验包装余18。（2）是终表，最优生产计划是生产标准袋540个，高档袋25（3）设对偶变量为

，对偶目标为w，则对偶模型为（3）设对偶变量为，对偶目标为w，则对偶（4）成型时间的影子价格为6.9375；由

解得

，从而

，即使该影子价格保持不变的成型时间变化范围。（5）由

和

解得

，从而

，即使原最优计划不改变的标准袋利润的变化范围。（4）成型时间的影子价格为6.9375；由解得教材第二章习题和参考书中有很多线性规划的习题，请尽量练习。教材第二章习题和参考书中有很多线性规划的习题，请尽量练习。线性规划计算软件：CPLEX、LINGO、EXCELEXCEL使用简介（以例1.1为例）（1）在EXCEL表格输入模型基本数据。123456线性规划计算软件：CPLEX、LINGO、EXCELEXCE（2）在工具栏规划求解的“规划求解参数”对话框输入模型完整信息：-“目标单元格”写入“$B$6”,选择“最大值”，可变单元格写入“$B$1:$B$2”；-在“约束”的添加栏的“添加约束”对话框依次输入约束信息，如约束，在“单元格引用”中添入“$B$1”，选“=>”，在“约束值”框中添入“0”。（2）在工具栏规划求解的“规划求解参数”对话框输入模型完整信（3）回到“规划求解参数”对话框，选择“求解”和输出选项。运算结果（包括灵敏度分析）报告（3）回到“规划求解参数”对话框，选择“求解”和输出选项。运第一章线性规划课件

内容回顾与思考1.对偶问题的定义是什么？2.对偶有哪些性质？3.对偶有哪些经济意义？4.对偶单纯形法的思想和主要步骤？5.灵敏度分析的方法？内容回顾与思考线性规划1-3节综合练习一、知识点

线性规划1-3节综合练习一、知识点二、综合练习

1．建模问题：某工厂在今后4个月内需租用仓库堆放物资。已知各月份所需仓库面积如表1；仓库租用费用随合同期定，期限越长折扣越大，具体数据如表2。租用仓库的合同每月初都可办理，每份合同将具体规定租用面积数和期限。因此该厂可根据需要在任何一个月初办理租用合同，每次可签一份或多份合同。工厂需决定如何租用可使总的所付租用费用最小。请建立此问题的线性规划模型（不解）。二、综合练习1．建模表1表2分析：建模需要确定三要素变量：如何租用（每月租的面积和时间，怎么表示）目标：费用最小约束：不低于所需面积表1表2分析：建模需要确定三要素解答：

设第i个月租用j个月期的面积为解答：2．图解法

问题：以下线性规划问题的图解如下图。在下面各问题中，选择一个或多个正确的答案填入相应的括号中。2．图解法的图解如下图。在下面各问题中，选择一个或多个正确的（1）这个线性规划的可行域为（

）；ABDDEFBDEOFHIFEIGOEGCAEOBFODIGEHG（2）这个线性规划的最优解位于（

），如果变量

，则最优解位于（

）；ABCDEFGHIO4321BAEx1-2-11234FDHIGCOx2（1）这个线性规划的可行域为（ ）；4BAEx1-2分析：

由图解法可确定约束的图形(DIG)，目标的图形向下移；

如果

，则可行域EFIG。4321BAEx1-2-11234FDHIGCOx2解答：（1）DIG；

（2）D、E分析：4BAEx1-2-113．解的概念问题：考虑线性规划问题

（P）证明：（1）若均为（P）的可行解，则也是（P）的可行解；（2）若B是A中一个可行基，且 ，则B为最优基。3．解的概念问题：考虑线性规划问题证明：分析：

（1）考察可行解的概念，证明结果说明可行域

是凸集；

（2）考察最优性检验的理解，即检验数的证明。证明：（1）是（P）的可行解。分析：

（1）考察可行解的概念，证明结果说明可行域

是凸集；(2)（P）的可行解可表示为目标可表示为∴任意（P）的可行解代入目标，都不大于B相应的基可行解的目标值，即B为最优基。(2)（P）的可行解可表示为目标可表示为∴任意（P）的可行解4．单纯形法（表）

问题：推导单纯形表任一次迭代前后检验数之间的关系，并由此说明变量出基后，在紧邻的下一阶段不会再进基。分析：考察对单纯形法步骤和单纯形表的熟

练掌握，并用一般式表示。4．单纯形法（表） 问题：推导单纯形表任一次迭代前后证明：单纯形表任一迭代前后的关系：证明：单纯形表任一迭代前后的关系：由检验数定义计算得迭代后的检验数代前的检验数的关系为与迭特别，对于迭代前出基的变量，即j=l，故下一阶段它不会再进基。有（为什么？）（说明检验数之间也具有同系数行之间的高斯消去关系）由检验数定义计算得迭代后的检验数代前的检验数的关系为与迭5．对偶理论问题：设，分别为下列两个问题的最优值，是问题(Ⅰ)的对偶问题的最优解。

试证明：

分析：（I）和（II）的目标相同，因此其对偶的约束相同，于是也是问题（II）的对偶问题的可行解。5．对偶理论问题：设，分别为下列两个问题的最优值，是问题(Ⅰ证明：（Ⅰ）和（Ⅱ）的对偶分别为和是的最优解，则也是的可行解。因此有最优解，记为则有，而，得证。证明：（Ⅰ）和（Ⅱ）的对偶分别为6．灵敏度分析问题：已知线性规划问题当

时，用单纯形法求得最终表如表3。6．灵敏度分析问题：已知线性规划问题当时，用表3要求：（1）确定

的值；（2）当

时，t2在什么范围内变化上述最优基不变；（3）当

时，t1在什么范围内变化上述最优解不变，图示并说明其几何意义。表3要求：（1）确定分析：（1）考察对单纯形表结构的掌握：单纯形表的每一列等于本表的

乘以初表的相应列、检验数公式（2）b变化时的分析（3）c变化时的分析解：（1）由，解得。分析：解：（1）由，解得。同理，解得

由，解得同理，解得由（2）由

，

解得

。（3）由，解得。

第一章线性规划课件

几何意义：当

的变化幅度

时，最优目标直线在如图箭头所示范围摆动，这时最优解都不变（图1）。图1几何意义：当的变化幅度时，最优目标直线在7．综合应用

问题:某公司生产家用的清洁产品，为了在高度的市场竞争中增加市场份额，公司决定进行一次大规模的广告行动。表4给出了公司准备做广告的三种产品名称、估计每做一单位广告（一个广告标准批量）使每种产品的市场份额增加量、公司拟定的广告后每种产品市场份额增加量的最低目标和两种可选的广告方式的单价。7．综合应用单位增量产品广告种类电视印刷媒体广告后市场份额最低增量去污剂液体洗涤剂洗衣粉0%1%3%3%2%18%-1%4%4%100200广告单位成本（万元）表4其中洗衣粉的市场份额出现负值是由于液体洗涤剂的份额增加会造成洗衣粉份额的减少。单位增量产品广告种类电视印刷媒体广告后市场份

现公司需拟定使广告总费用最少的广告计划，即决定电视和印刷媒体的广告数量（分别记为x1和x2）。

（1）请写出此问题的线性规划模型（约束依表4中产品的次序），并将模型化为标准型。

（2）用（Min型）单纯形法求解此问题，得单纯形终表如表5。现公司需拟定使广告总费用最少的广告计划，即决定电视和表5

请填完表中空白；由表指出最优广告计划并求出相应的最低广告费用，此最优计划使每种产品的市场份额最低增量目标达成情况如何？表5请填完表中空白；由表指出最优广告计划并求出相应的（3）写出此问题的对偶问题模型，由表5求出对偶最优解Y*，并解释Y*的实际意义。分析：（1）建立模型，标准型（min型）（2）填表，将解代入约束可得份额增量目标情况（3）对偶模型，对偶解的意义（min型的对偶解

一般含义是什么）（3）写出此问题的对偶问题模型，由表5求出对偶最优解Y*，并解：（1）解：（1）（2）

即做电视广告4，印刷媒体3，最低广告费1000，前两种产品正好达到目标，第三种超额4%；010001-14/32/3-1（3）填表：（2）00-14/3（3）填表：,实际意义是有另一个承包商来承揽三种产品增加份额的业务，承揽的目标是总收益最大化，约束是以不超过公司自己做广告的成本，

即承揽的最优单位收益。,实际意义是有另一个8．应用案例除尘器生产计划

某机器公司可以生产三种不同型号小型的除尘器，一种是政府用，另一种是工业用，还有一种是民用除尘器。但最后一种已经不生产了。政府用除尘器的单价是1500元，工业用除尘器的单价是1400元。

为了完成各月订货，生产车间必须制定出一个生产计划以使费用最低。因为政府用和工业用除尘器都分别有两种型号：一种是使用优质的高8．应用案例除尘器生产计划碳钢和一些铝；另一种是使用低碳钢和大量铝，而金属价格差别很大，所以制定最优生产计划并非易事。客户并不在意公司为他们生产的除尘器是属于两种型号中的哪一种，公司决定使用线性规划制定最优计划，问题的关键是满足客户的总订货要求，不超过公司的熟练工人与非熟练技术工人以及生产能力的限制，以使生产费用最小。

铝的费用：107元/10kg；高碳钢：38元/10kg，低碳钢：29元/10kg，表6给出生产三种除尘器所需的原材料及劳动力工时等。碳钢和一些铝；另一种是使用低碳钢和大量铝，而金属价格差别很大表6生产所需资源数据

公司下月的订货为：工业用除尘器300只，政府用除尘器500只，其金属费用为305820元。表6生产所需资源数据公司下月的订货为：工业用除尘器3

由于开工不足，公司决定再次生产民用轻型除尘器，售价为800元/只，数用量不超过100只。技术工人可以加班，费用15元/小时。

线性规划模型如表7，模型的变量有9个，前三个为三种金属的购买量，后五个是五种不同除尘器的生产数量；最后一个是熟练工加班小时数。约束也有9个，前三个表明购买的三种金属的数量至少应满足生产需求；后两个表明生产政府用和工业用除尘器的数量要满足订货；再后三个是熟练工、技术工和生产线生产能力的限制，最后一个表明最多可以生产100个民用轻型除尘器。由于开工不足，公司决定再次生产民用轻型除尘器，售价为80表7

线性规划模型表7线性规划模型问题1：下面各量哪些在目标函数中考虑了，哪些没有考虑？a)金属的费用

有______没有______；

b)正常劳动成本

有______没有______；c)加班劳动成本

有______没有______；d)管理费用

有______没有______。问题2：为什么在目标函数中没有考虑工业用和政府用除尘器的收益，但却考虑了民用除尘器的收益？使用Lindo软件对模型计算的结果如下：案例分析√√√√（固定）问题1：下面各量哪些在目标函数中考虑了，哪些没有考虑？使用LOBJECTIVEFUNCTIONVALUE1)263280.000VARIABLE VALUE REDUCEDCOSTX1 240.000000 .000000X2 6600.000000 .000000X3 2200.000000 .000000X8 100.000000 .000000X9 200.000000 .000000X5 .000000 574.400000X6 100.000000 .000000X7 200.000000 .000000X4 500.000000 .000000ROW SLACKORSURPLUS DUALPRICES2 .000000 107.0000003 .000000 38.0000004 .000000 29.0000005 .000000 –776.2003006 .000000 –852.2003007 .000000 15.0000008 1400.000000 .0000009 .000000 36.40004010 .000000 296.799700RANGESINWHICHTHEBASISSUNCHANGEDLindo计算结果铝高碳低碳轻型加班政二工一工二政一铝高碳低碳政订工订技术熟练生产轻型OBJECTIVEFUNCTIONVALUELindo计

OBJCOEFFICIENTRANGESVARIABLE CURRENT COEFALLOWABLEINCREASEALLOWABLEDECREASEX1107.00000045.50005054.962920X238.000000 3.372724 3.033336X3 29.000000 3.309094 3.854542X8–800.000000 296.799700 INFINITYX915.000000 36.400040 15.000000X5.000000 INFINITY 574.400000X6.000000 42.399960 36.400040X7.000000 36.400040 42.399970X4 .000000 574.400000 INFINITYRIGHTHANDSIDERANGESROWCURRENTRHS ALLOWABLE INCREASEALLOWABLEDECREASE2.000000 240.000000 INFINITY3.000000 6600.000000 INFINITY4 .000000 2200.000000 INFINITY5 500.000000 25.000000 12.5000006 300.000000 28.571430 12.50000076400.000000 200.000000 INFINITY8 9600.000000 INFINITY