运筹学课件2 1

1、1.1 线性规划问题及数学模型,1.1.1 线性规划问题（LPLinear Programming ） 规划问题：如何合理利用有限的人力、物力、财力等资源，获得最大的收益。 例1：运输问题：已知几个地方生产同一种产品，而另一些地方需要该产品， 在已知各地运价情况下，如何组织运输才能满足需求并使总运费最少？ 例2：一交通工具，运输几种不同体积、重量的物资，如何装配使所运的物资 最多？ 例3：生产计划问题：某企业生产两种产品 和，这两种产品分别在A、B、C、D 四种不同设备上加工。每生产一件产品 所占用设备的时间，每天可用的设备能 力及每生产一件产品的获利情况如表所 示。问如何安排生产使利润最大？

2、,1.1 线性规划问题及数学模型,1.1.1 线性规划问题（LPLinear Programming ） 特点：1.问题解决要满足一定的条件约束条件。 2.问题有多个满足条件的解决方案。 3.问题解决有明确的目标要求，不同方案有不同的目标值目标函数。 约束条件：含变量的等式或不等式表示问题的限制条件，s.t.(subject to)。 目标函数：含变量的函数表示问题的目标,（objective function）。 规划问题：在一定约束条件下，求目标函数的极值（最大值或最小值）。 线性规划问题：当约束条件与目标函数均是线性的，为线性规划问题。 1.1.2 LP问题的数学模型 例1：上述例3中生

3、产计划问题 目标函数： 约束条件：,1.1 线性规划问题及数学模型,1.1.2 LP问题的数学模型 例2：从甲地调出物资2000吨，从乙地调出物资1100吨，分别供给A地1700吨 B地1100吨、C地200吨、D地100吨。已知每吨运费如表所示，运费与运 量成正比。如何组织才能使总的运费最小？,设 分别表示从甲地运往A、B、 C、D四地的物资数量， 分别表示 从乙地运往A、B、C、D四地的物资数量，则 目标函数：,约束条件：,1.1 线性规划问题及数学模型,1.1.2 LP问题的数学模型 从以上例子可以看出，线性规划问题的数学模型包含三个要素： 1.决策变量：问题中要确定的未知量。每个问题用

4、一组决策量表示，一组决策 量的值代表一个方案。 2.约束条件：决策变量受到各种可用资源的限制，表示为含决策变量的线性等 式或线性不等式。 3.目标函数：问题要达到的目标，表示为决策变量的函数。 满足以上三个条件的数学模型为线性规划的数学模型。 一般LP问题的数学模型：（ 个决策变量， 个约束条件）,1.1 线性规划问题及数学模型,1.1.2 LP问题的数学模型 一般LP问题的数学模型几种形式： 缩写形式：,向量形式：,其中， 为价值向量 为决策向量 为系数向量 为资源向量,1.1 线性规划问题及数学模型,1.1.2 LP问题的数学模型 矩阵形式：,其中， 为决策变量的系数矩阵。,1.1 线性规

5、划问题及数学模型,1.1.3 LP问题的标准形式,目标函数： 最大值 约束条件： 等于型 右端常数项：非负 决策变量： 非负,对于不符合标准形式的LP问题，通过如下方法将其数学模型转化为标准形式： 1.目标函数为求极小值 ：令 2.约束条件为不等式： 当约束条件为“”时，左端加上一个松弛变量； 当约束条件为“”时，左端减去一个剩余变量。 3.右端常数项 ，约束条件两边乘（-1）。 4.决策变量 时，令 ； 决策变量 无约束时，令 。,1.1 线性规划问题及数学模型,1.1.3 LP问题的标准形式 例：将下列线性规划问题化为标准型：,解：令 ， ， ，并引入松弛变量 和剩余变量 ，将上述模 型转

6、化为：,1.1 线性规划问题及数学模型,1.1.4 LP问题的解 LP问题的标准型：,（1） （2） （3）,可行解（feasible solution）：满足约束条件（2）（3）的解 所有可行解的集合称为可行域（feasible region）。 最优解（optimal solution）：使目标函数达到最大值的可行解为最优解。,1.1 线性规划问题及数学模型,1.1.4 LP问题的解,基（basis）：设 ，为 阶系数矩阵（ ），其秩为 。 是矩阵中 阶满秩子矩阵，B是LP问题的一个基。,基向量与非基向量：B中每一个列向量 称为基向量 A中除基向量之外的列向量为非基向量，用N表示。,基变量

7、与非基变量：与基向量对应的变量为基变量， 与非基向量对应的变量为非基变量。,1.1 线性规划问题及数学模型,1.1.4 LP问题的解 基解：在约束方程组（2）中，令所有的非基变量 ， 由于 ，则 个约束方程解出 个基变量的唯一解 ， 加上非基变量取0，有 ，为LP问题的基解。 基可行解：满足变量非负约束条件（3）的基解为基可行解。 可行基：与基可行解对应的基称为可行基。 其示意图为：,1.2 线性规划问题的图解法,1.2.1 图解法的特点（graphical solution） 优点：简单直观，反映了线性规划问题求解的基本原理。 局限性：只适用于具有两个决策变量的LP问题，可在二维直角坐标平面

8、上作 图。实际上LP问题的数学模型含有多个决策变量（三个或三个以 上），难以用图形描述。 1.2.2 图解法的步骤 （1）画直角坐标系； （2）根据约束条件画出可行域； （3）在可行域上寻找最优解。 例：,解：在直角坐标系上分别画直线 、 确定可行域,1.2 线性规划问题的图解法,1.2.2 图解法的步骤 等直线法：根据约束条件确定可行域，画出过原点的目标函数线，让目标函数 线沿着值增大方向（法线方向）平行移动，与可行域相交且有最大 目标函数值的顶点，即为LP问题的最优解。（此时该目标函数线 有最大截距） 试算法：将可行域所有顶点对应的目标函数值算出来，比较其大小。 1.2.3 线性规划问题解

9、的几种情况 线性规划问题的可行域和最优解有以下几种可能的情况： 1.可行域为有界区域 （1）有唯一的最优解； （2）有无穷多个最优解； 2.可行域为无界区域 （1）有唯一的最优解； （2）有无穷多个最优解； （3）无界解（无最优解）,1.2 线性规划问题的图解法,1.2.3 线性规划问题解的几种情况 3.可行域为空集：无可行解 约束条件矛盾 1.2.4 图解法引出的思考 1.若线性规划问题的可行域非空，则其可行域为凸集。 凸集：如果集合 中任意两点 、 ，其连线上所有点都是集合 中的点， 则 为凸集。 为 、 连线上的点。 凸集不能有凹陷、不能有空洞。 LP问题的可行域是由线性表达式构成，可行

10、域有棱有角，是个凸集。 2.线性规划的基可行解与可行域的顶点一一对应。 顶点：若 是集合 上的一个点，但此点不落在 上其它任意两点连线上，则 为 的顶点。 3.如果LP有最优解，则必可在其可行域的某个（多个）顶点上达到最优值。,LP问题的基的数目不超过,基解的数目不超过,可行域的顶点不超过,1.3 单纯形法（simplex method）,对于含两个决策变量的LP问题用图解法在二维平面上求解，对于含高维决 策变量的LP问题采用单纯形法。 1.3.1 单纯形法的基本原理 基本思路：从可行域中某个基可行解（顶点）开始，判别它是否是最优解，如 果不是，寻找下一个“更好”的基可行解（顶点），直到找到最

11、优 解或判定问题无解为止。,单纯形法解决的问题： 1.如何判别当前的基本可行解是否已达到了最优解。 2.若当前解不是最优解，如何去寻找一个改善了的基本可行解。 3.如何得到一个初始的基本可行解。,1.3 单纯形法（simplex method）,1.3.1 单纯形法的基本原理,（1）该LP问题的一个基 ，对应于B的基变量为 ， ，,则 ，其基可行解,目标函数 中有正系数的非基变量，说明目标函数还有可能增大。 将非基变量与基变量进行对换（一般选正系数最大的非基变量为换入变量）， 同时还要确定换出变量，即基变量中要换出来成为非基变量。,解：该LP问题的标准形式为：,例：,1.3 单纯形法（simp

12、lex method）,1.3.1 单纯形法的基本原理,（2）当 为换入变量时，从 ， ， 中换出一个，并保证其余的都是非负，则,当 时， ，此时 ，对应的,则用 替换 ，则 ，其基可行解,目标函数为 ，非基变量的系数是正的，说明函数值还可以增 大， 不是最优解。,（3）采用上述方法，确定换入、换出变量，再得到一个基可行解：,1.3 单纯形法（simplex method）,1.3.1 单纯形法的基本原理,（4）再经过一次迭代，得到一个基可行解：,此时目标函数的表达式为：,是最优解，,当所有非基变量系数均为负数时，目标函数达到最大值，有最优解。,单纯形法求解的基本过程：,初始基本可行解,1.3

13、 单纯形法（simplex method）,1.3.2 单纯形法解决的问题 1.确定初始基可行解 要确定一基可行解，使A存在一个单位矩阵，为初始可行基B，令非基变量取 值为零，可得到基可行解。,（1）当约束条件为“”时，加上松弛变量，则对应的系数矩阵为单位阵， 作为初始可行基。,在每个约束条件的左端加上一个松弛变量 ，则,1.3 单纯形法（simplex method）,1.3.2 单纯形法解决的问题 1.确定初始基可行解,（2）当约束条件为“”或“”时，不存在单位矩阵，采用人造基方法： 对于“”，先减去一个剩余变量，再加上一个非负的人工变量； 对于“=”，加上一个非负人工变量。,其可行解为,

14、则,作为可行基,1.3 单纯形法（simplex method）,1.3.2 单纯形法解决的问题 2.最优性检验和解的判别 LP问题标准形式：,令 ，对应的基变量为 ，非基变量为,所有基变量可以用非基变量表示,即,基可行解为：,1.3 单纯形法（simplex method）,1.3.2 单纯形法解决的问题 2.最优性检验和解的判别,代入目标函数得：,令 ，,则 （ 为检验数）,（1）最优解判别：所有 ，则当前基可行解（顶点）为最优解。 （2）无穷多最优解判别：若所有 ，且对某个非基变量其检验数 ， 则有无穷多个最优解。 最优解为： ， 任意值,1.3 单纯形法（simplex method）

15、,1.3.2 单纯形法解决的问题 2.最优性检验和解的判别,（3）无界解判别：若存在某个非基变量对应的检验数 ，且对应的变量 系数 ，则该LP问题有无界解。,证：设线性规划问题的新解为：,则对任意 ，都为可行解,当 时，,说明目标函数可无限增加，即有无界解。,1.3 单纯形法（simplex method）,1.3.2 单纯形法解决的问题 3. 寻找改进的基可行解（基变换） 当某个基可行解不是最优解，也不是无界解时，需要找一个新的基可行解。 基本方法：在基变量中选出一个，使它成为非基变量；同时从非基变量中选 出一个，让它成为基变量，从而构造一个新基。每变换一次，就 得到一个新的基可行解。从一个

16、基可行解到另一个基可行解的变 换为一次基变换。,（1）换入变量的确定,选择 中最大者（可任选）,（2）换出变量的确定 设换入变量为 ，取值为 ，其余非基变量取值为0，则,且,1.3 单纯形法（simplex method）,1.3.2 单纯形法解决的问题 3. 寻找改进的基可行解（基变换）,（2）换出变量的确定 设换入变量为 ，取值为 ，其余非基变量取值为0，则,因为所有解必须非负，则,在非基变量表示的基变量的表达式中，观察换入变量增加时各基变量变 化情况，一般选择在换入变量增加过程中最先减少到0的变量，这样保证了所 有变量非负。,1.3 单纯形法（simplex method）,1.3.3

17、单纯形法的计算步骤 单纯形表：用单纯形法求解LP问题的计算工具。 初始单纯形表：含初始基可行解的单纯形表。 最终单纯形表：含最优解的单纯形表。 每找到一个新的基可行解，就对应一张单纯形表。 初始单纯形表的格式：,基变量,约束方程右端的常数项。,基变量的价值系数,非基变量对应的检验数 基变量检验数为0,基变量的价值系数， 即目标函数中基变量前系数。,1.3 单纯形法（simplex method）,1.3.3 单纯形法的计算步骤 单纯形法的计算步骤： 1.求初始基可行解，列出初始单纯形表。 2.最优性检验：在单纯形表中，若所有检验数 ，表中的基可行解即为最优 解，计算到此结束，否则转下一步。 3

18、.从基可行解转换到相邻的目标函数值更大的基可行解，列出新的单纯形表。 （1）确定换入变量： 对应的变量 为换入变量 （2）确定换出变量： 对应的变量 为换出变量，元素 为主元素，决定了基可 行解到相邻基可行解的转移方向。 （3）用换入变量 替换基变量中的换出变量 ，得到新基 。 通过迭代计算找到对应的基可行解，并画出新的单纯形表。,1.3 单纯形法（simplex method）,1.3.3 单纯形法的计算步骤 单纯形法的计算步骤： 在新的单纯形表中，基阵仍是单位阵，即 应变换为单位向量。因此必须从原 先的单纯形表作行的初等变换： 元素所在行的数字除以主元素 得 将刚刚计算的第 行的数字乘以

19、加到第 行数字上得：,计算各个变量的检验数,（4）重复步骤（2）（3），直到计算结束为止。,1.3 单纯形法（simplex method）,1.3.3 单纯形法的计算步骤,例：,解:该LP问题的标准形式为：,（1）取 为基变量，对应的基可行解为 ，初始单纯形表为：,1.3 单纯形法（simplex method）,1.3.3 单纯形法的计算步骤,（2）换入变量为 中最大者，即为 ；换出变量 ，即为 。 用 替换 ，则对应的基变量为 ，主元素为4。 新的单纯形表为：,表中存在 ，则目标函数值还能增加。,1.3 单纯形法（simplex method）,1.3.3 单纯形法的计算步骤,（3）换入

20、变量为 中最大者，即为 ；换出变量 ，即为 。 用 替换 ，则对应的基变量为 ，主元素为1。 新的单纯形表为：,表中存在 ，则目标函数值还能增加。,1.3 单纯形法（simplex method）,1.3.3 单纯形法的计算步骤,（4）换入变量为 中最大者，即为 ；换出变量 ，即为 或 ，这里选 。用 替换 ，对应的基变量为 ，主元素为0.5。 新的单纯形表为：,表中所有 ，表示目标函数值不可能增加。,则最优解为 ，目标函数最大值为 。,1.3 单纯形法（simplex method）,1.3.4 退化解 在单纯形法计算中用 规则确定换出变量时，有时存在有两个相同的最小比 值。在下一次迭代计算

21、中，就有一个或几个基变量取值为0，出现退化解。 退化的结构对单纯形法迭代会造成不利的影响。可能出现以下情况： 进行进基、出基变换后，虽然改变了基，但没有改变基本可行解（极 点），目标函数也不会改进。进行若干次基变换后，才脱离退化基本可行解 （极点），进入其他基本可行解（极点）。这种情况会增加迭代次数，使单纯 形法收敛的速度减慢。 在特殊情况下，退化会出现基的循环，一旦出现这样的情况，单纯形法 迭代将永远停留在同一极点上，因而无法求得最优解。在单纯形法求解线性规 划问题时，一旦出现这种因退化而导致的基的循环，单纯形法就无法求得最优 解，这是一般单纯形法的一个缺陷。,1.3 单纯形法（simple

22、x method）,1.3.4 退化解 为避免出现循环，有人提出一些方法，如勃兰特法： （1）选取 中下标最小的非基变量 为换入变量 （2）按 规则，出现两个或两个以上最小比值时，选取下标最小的基变量为换 出变量。,一般情况下，退化现象较为多见，但循环却很少发生。到目前为止，还 没有见到一个实际应用问题产生循环的例子。研究循环及其防止的方法目前 仍是理论上的问题。,1.4 单纯形法的进一步讨论 用单纯形法求解线性规划问题时，一般选单位阵为初始基阵。 当约束条件为“”时，添加松弛变量，其系数构成单位阵，作为初始基阵； 当约束条件为“”时，添加人工变量，其系数构成单位阵，作为初始基阵， 选加入的人

23、工变量为基变量。 当约束条件为“”时，先减去剩余变量化为等式，再添加人工变量，其系 数构成单位阵，作为初始基阵，选加入的人工变量为基变量。 人工变量法基本思路： 若原线性规划问题的系数矩阵中无单位阵，则在每一个约束方程中加入一 个人工变量，便在系数矩阵中形成一个单位阵。此时加入的人工变量为基变量。 通过基变换，使基变量中不再含有非零的人工变量，表示该LP问题有解。如果 当所有 时，还有非零人工变量，表示该问题无可行解。,1.4 单纯形法的进一步讨论,对于如下LP问题：,分别对每个约束方程加入一个人工变量,选 为基变量，令非基变量,则初始基可行解为,1.4 单纯形法的进一步讨论,1.4.1 大M

24、法（惩罚法） 在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数取值不受影响。因此假定人工变量在目标函数中的系数为（-M）（M为任意大的正数），要实现目标函数最大化，必须把人工变量从基变量中换出，否则目标函数不能实现最大化。,例：,解：此问题的标准型为：,添加人工变量后，原LP问题为：,1.4 单纯形法的进一步讨论,1.4.1 大M法（惩罚法） 1）基变量为 ，非基变量为 ， 初始基可行解为 ，初始单纯形表为：,将M当作一个 参数参加运算,1.4 单纯形法的进一步讨论,1.4.1 大M法（惩罚法） 2）换入变量： 换出变量： ，为 用 替换 ，主元素为1,1.4 单纯形法的进

25、一步讨论,1.4.1 大M法（惩罚法） 3）换入变量： 换出变量： ，选 用 替换 ，主元素为6,1.4 单纯形法的进一步讨论,1.4.1 大M法（惩罚法） 4）换入变量： 换出变量： ，为 用 替换 ，主元素为2/3,所有 ， ，最优解,1.4 单纯形法的进一步讨论,1.4.2 两阶段法 第一阶段：求解原线性规划问题的一个基可行解。 方法：不考虑原问题是否存在基可行解，先求解一个目标函数中只含有人 工变量的LP问题，即令目标函数中其他变量系数为0，人工变量的 系数取某个正常数（一般取1），在保持原问题约束条件不变的情 况下求此目标函数最小化时的解。 即给原问题加人工变量，构造仅含人工变量的目

26、标函数，并使其最小化。,例：,用单纯形法求解该模型，若 且基变量中不含人工变量，说明 原问题存在基可行解，可进行第 二步计算，否则原问题无解。,1.4 单纯形法的进一步讨论,1.4.2 两阶段法 第二阶段：从可行解出发，继续寻找问题的最优解。 在第一阶段计算得到的最终单纯形表中除去人工变量，将目标函数 换成原问题的目标函数，作为第二阶段计算的初始表，继续求解。,例：,解：第一阶段： 该问题写成,标准形式为：,1.4 单纯形法的进一步讨论,1.4.2 两阶段法 1）初始单纯形表：,1.4 单纯形法的进一步讨论,1.4.2 两阶段法 2）换入变量： 换出变量： ，为 用 替换 ，主元素为1,1.4

27、 单纯形法的进一步讨论,1.4.2 两阶段法 3）换入变量： 换出变量： ，选 用 替换 ，主元素为6,此时 ，即,1.4 单纯形法的进一步讨论,1.4.2 两阶段法 第二阶段：将表中人工变量 除去，目标函数为：,单纯形表为：,1.4 单纯形法的进一步讨论,1.4.2 两阶段法,所有,最优解：,小结： 1.大M法 基本思想：在目标函数中赋予人工变量很大的惩罚系数 M，用线性规划的优 化机制迫使人工变量出基，如果无法使人工变量出基，原问题无 可行解。 优点：简单、直观，在单纯形表上的计算步骤与普通单纯形方法相同。 缺点：大 M 到底取多大值？M 取值太大将增加数值计算的困难，计算机计 算时取值上

28、的误差可能使结果发生错误。 2.两阶段法 基本思想：将求解过程分为两个阶段。 第一阶段寻找初始可行解或判断问题无可行解； 第二阶段寻找最优解或判断问题无界。,2.两阶段法 第一阶段：寻找初始可行解或判断问题无可行解。 引入人工变量并找一个初始基，另构造一个新的求极小值的目标 函数，该目标函数除人工变量的系数为1以外，其余变量的系数都 为零。求解该线性规划问题，如果最优目标函数值为零，表明所 有的人工变量已经不在基中，第一阶段的最优解即是原问题的一 个基本可行解；否则原问题无可行解。 第二阶段：寻找最优解或判断问题无界。 将原目标函数换回，以第一阶段得到的可行基为初始基进行迭 代，直到找到最优界

29、或判断问题无界为止，并删去所有人工变量。,1.5 改进的单纯形法,1.5.1 单纯形法的矩阵描述 设线性规划问题（矩阵形式）,加上松弛变量为：,其中,为 单位阵,用单纯形法计算时， 为初始基，对应的基变 量为 ，则初始的单纯形表为：,迭代若干次后，基变量为 ，其系数矩阵 为单位阵，非基变量为,即,则,即,1.5 改进的单纯形法,1.5.1 单纯形法的矩阵描述 代入目标函数得：,令所有非基变量为0，得到基可行解为：,对应的单纯形表为：,1.5 改进的单纯形法,1.5.1 单纯形法的矩阵描述 对于矩阵形式用单纯形法求解LP问题计算步骤：,1.根据给出的LP问题，在加入松弛变量或人工变量后，得到初始基变量，迭代 若干步后，基变量为 ，其对应的系数矩阵为 ，求