第3章-物流线性规划课件.ppt

1、第第3章章 物流线性规划物流线性规划 3.1 线性规划及单纯形法线性规划及单纯形法3.2 线性规划问题的解线性规划问题的解3.3 运输问题运输问题3.4 整数规划整数规划3.5 指派问题指派问题 第第3章章 物流线性规划物流线性规划本章重点：本章重点：线性规划是运筹学的一个最基本的分支，是科学、工程、管线性规划是运筹学的一个最基本的分支，是科学、工程、管理领域广泛应用的数学模型。本章了解线性规划问题的基本理领域广泛应用的数学模型。本章了解线性规划问题的基本概念；掌握线性规划模型的建立方法；掌握图解法求解线性概念；掌握线性规划模型的建立方法；掌握图解法求解线性规划模型的基本方法；掌握单纯形表法求

2、解线性规划模型；规划模型的基本方法；掌握单纯形表法求解线性规划模型；掌握线性规划模型的物流应用；了解整数规划问题的基本概掌握线性规划模型的物流应用；了解整数规划问题的基本概念及其数学模型；理解分支定界法求解整数规划的基本原理；念及其数学模型；理解分支定界法求解整数规划的基本原理；掌握掌握0-1规划问题的建模方法；掌握限枚举法求解规划问题的建模方法；掌握限枚举法求解0-1规划；规划；掌握指派问题的数学模型及其解法。掌握指派问题的数学模型及其解法。下一页返回第第3章章 物流线性规划物流线性规划在物流活动中，如何有效地利用有限的人力和物力取得最优在物流活动中，如何有效地利用有限的人力和物力取得最优的

3、经济效果，或在预定的目标条件下，如何花费最少的人力的经济效果，或在预定的目标条件下，如何花费最少的人力和物力去实现目标，这类问题统称为规划问题。规划问题用和物力去实现目标，这类问题统称为规划问题。规划问题用数学语言描述为：根据研究问题的目标选取适当的一组变量，数学语言描述为：根据研究问题的目标选取适当的一组变量，问题的目标用变量的函数形式表示，该函数称为目标函数，问题的目标用变量的函数形式表示，该函数称为目标函数，问题的约束条件用一组由选定变量组成的等式或不等式表达，问题的约束条件用一组由选定变量组成的等式或不等式表达，这些等式或不等式称为约束方程。即规划问题由一个或几个这些等式或不等式称为约

4、束方程。即规划问题由一个或几个目标函数和一组约束方程构成。目标函数和一组约束方程构成。返回上一页3.1 线性规划及单纯形法线性规划及单纯形法3.1.1 线性规划的定义线性规划的定义线性规划（线性规划（Linear Programming，简记为，简记为LP）是运筹）是运筹学的一个重要分支。学的一个重要分支。1960年，前苏联学者康托洛维奇以年，前苏联学者康托洛维奇以最佳资源利用的经济计算最佳资源利用的经济计算一文获诺贝尔奖。从此线性规一文获诺贝尔奖。从此线性规划方法用来解决企业的生产经营活动问题并取得了良好的效划方法用来解决企业的生产经营活动问题并取得了良好的效果。目前，大多数计算中心都有线性

5、规划的商用计算机程序果。目前，大多数计算中心都有线性规划的商用计算机程序可供使用。线性规划已发展成为物流系统现代化管理的有力可供使用。线性规划已发展成为物流系统现代化管理的有力工具之一。工具之一。线性规划只有一个目标函数，且目标函数和约束方程都是线线性规划只有一个目标函数，且目标函数和约束方程都是线性函数。用线性规划求解的典型问题有生产计划问题、混合性函数。用线性规划求解的典型问题有生产计划问题、混合配料问题、下料问题、运输问题等。配料问题、下料问题、运输问题等。下一页返回3.1 线性规划及单纯形法线性规划及单纯形法3.1.2 线性规划的数学模型线性规划的数学模型通常称现实世界中人们关心、研究

6、的实际对象为原型。模型通常称现实世界中人们关心、研究的实际对象为原型。模型是指将某一部分信息简缩、提炼而构造的原型替代物。数学是指将某一部分信息简缩、提炼而构造的原型替代物。数学模型则是对现实世界的一个特定对象，为达到一定目的，根模型则是对现实世界的一个特定对象，为达到一定目的，根据内在规律做出必要的简化假设，并运用适当数学工具得到据内在规律做出必要的简化假设，并运用适当数学工具得到的一个数学结构。的一个数学结构。一般线性规划模型可以表示如下：一般线性规划模型可以表示如下：（3-1）下一页返回上一页nnxcxcxcoptZ22113.1 线性规划及单纯形法线性规划及单纯形法建立线性规划问题的数

7、学模型一般要经过以下三个步骤。建立线性规划问题的数学模型一般要经过以下三个步骤。1.根据目标确定决策变量根据目标确定决策变量对于一个决策问题，首先要明确的是：有哪些可供选择的方对于一个决策问题，首先要明确的是：有哪些可供选择的方案。一般情况下，一个决策问题总应有一个以上可供选择的案。一般情况下，一个决策问题总应有一个以上可供选择的方案。因此可以将其设为变量，并以变量的不同取值来表示方案。因此可以将其设为变量，并以变量的不同取值来表示可供选择的各个不同方案，这些假设的变量就是决策变量。可供选择的各个不同方案，这些假设的变量就是决策变量。下一页返回上一页njxbxaxaxabxaxaxabxaxa

8、xatsjmnmnmmnnnn2,1,0.221122222121112121113.1 线性规划及单纯形法线性规划及单纯形法一个决策问题到底要设多少个决策变量，取决于决策问题本一个决策问题到底要设多少个决策变量，取决于决策问题本身，但所有假设的决策变量及其取不同的值，应反映并包含身，但所有假设的决策变量及其取不同的值，应反映并包含该决策问题中所有可供选择的方案，以免在建模计算分析中，该决策问题中所有可供选择的方案，以免在建模计算分析中，遗漏最优的决策方案。少设一个决策变量，实际上就意味着遗漏最优的决策方案。少设一个决策变量，实际上就意味着这个变量取值为零；而多设一个决策变量，则其取值可以是这

9、个变量取值为零；而多设一个决策变量，则其取值可以是零，也可以不为零，这大大增加了可供选择的决策方案，给零，也可以不为零，这大大增加了可供选择的决策方案，给了决策问题更多的机会与选择。不过，过多的决策变量，会了决策问题更多的机会与选择。不过，过多的决策变量，会使数学模型复杂，计算困难。所以必须在两者之间作出合理使数学模型复杂，计算困难。所以必须在两者之间作出合理恰当的选择。恰当的选择。下一页返回上一页3.1 线性规划及单纯形法线性规划及单纯形法2.建立目标函数建立目标函数作为一个决策问题，在决策者的心目中，必然会有各种决策作为一个决策问题，在决策者的心目中，必然会有各种决策的目标，如希望产品产量

10、最大、利润最大、成本最低等。而的目标，如希望产品产量最大、利润最大、成本最低等。而这些目标实现的好坏，取决于采用的决策方案。因此，决策这些目标实现的好坏，取决于采用的决策方案。因此，决策目标是决策方案的函数，也就是决策变量的函数，即目标函目标是决策方案的函数，也就是决策变量的函数，即目标函数。数。建立数学模型的第二步，就是要对每个决策目标，建立目标建立数学模型的第二步，就是要对每个决策目标，建立目标函数，找到目标值与决策变量的数量关系。在本章线性规划函数，找到目标值与决策变量的数量关系。在本章线性规划中，讨论的数学模型只含一个目标函数，且函数关系是线性中，讨论的数学模型只含一个目标函数，且函数

11、关系是线性的。的。下一页返回上一页3.1 线性规划及单纯形法线性规划及单纯形法3.确定约束条件确定约束条件一个决策问题的决策目标一般不可能无限制地被优化。在其一个决策问题的决策目标一般不可能无限制地被优化。在其实现优化的过程中，必然会受到有关外界条件的制约。这些实现优化的过程中，必然会受到有关外界条件的制约。这些限制用数学语言表述出来往往是决策方案（即决策变量）的限制用数学语言表述出来往往是决策方案（即决策变量）的等式或不等式，即约束条件。在一个决策问题中，增加一个等式或不等式，即约束条件。在一个决策问题中，增加一个约束条件，往往会给决策目标带来不利影响，当然也可能没约束条件，往往会给决策目标

12、带来不利影响，当然也可能没有影响，此时，这个约束条件就成为多余的了。相反，如果有影响，此时，这个约束条件就成为多余的了。相反，如果遗漏了一个或几个约束条件，则可能使计算出的最优目标最遗漏了一个或几个约束条件，则可能使计算出的最优目标最终无法得以实现，因为它不能满足那些遗漏的约束条件。因终无法得以实现，因为它不能满足那些遗漏的约束条件。因此，在建立决策问题的数学模型时，必须要全面地考虑所有此，在建立决策问题的数学模型时，必须要全面地考虑所有与决策目标有关的约束条件，建立一个完整的数学模型。与决策目标有关的约束条件，建立一个完整的数学模型。下一页返回上一页3.1 线性规划及单纯形法线性规划及单纯形

13、法例例3-1 设某工厂生产设某工厂生产A、B两种产品，已知生产两种产品，已知生产A、B产品产品时的资源消耗最、单位产品利润及资源限制量如时的资源消耗最、单位产品利润及资源限制量如表表3-1所示。所示。问问A、B各生产多少公斤，方能使总的利润最大？各生产多少公斤，方能使总的利润最大？首先，设生产首先，设生产A、B两种产品各为两种产品各为x1，x2公斤，根据已知条公斤，根据已知条件、要求，问题可归结为如下数学表达式：件、要求，问题可归结为如下数学表达式：求一组变量求一组变量 满足下列条件：满足下列条件：使得总利润使得总利润 取得最大值。取得最大值。下一页返回上一页)2,1(01122521553.

14、212121jxxxxxxxtsjTxx),(212145xxZ3.1 线性规划及单纯形法线性规划及单纯形法建立一个实用的线性规划模型必须明确以下四个组成部分的建立一个实用的线性规划模型必须明确以下四个组成部分的含义：含义：第一，决策变量。指决策者为实现规划目标采取的方案、措第一，决策变量。指决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量如式（施，是问题中要确定的未知量如式（3-2）中的。）中的。第二，目标函数。线性规划模型的目标是求系统目标的极值，第二，目标函数。线性规划模型的目标是求系统目标的极值，可以是求极大值，如企业的利润和效率等，也可以是求极小可以是求极大值，如企业的利

15、润和效率等，也可以是求极小值，如成本和费用等。式（值，如成本和费用等。式（3-1）即为最优化目标函数，简）即为最优化目标函数，简称目标函数。式中即称目标函数。式中即optimize（最优化）的缩写，根据问（最优化）的缩写，根据问题要求不同，可以表示为题要求不同，可以表示为max（最大化）或（最大化）或min（最小化）。（最小化）。下一页返回上一页3.1 线性规划及单纯形法线性规划及单纯形法第三，约束条件。约束条件是指实现系统目标的限制性因素，第三，约束条件。约束条件是指实现系统目标的限制性因素，通常表现为生产力约束、原材料约束、能源约束、库存约束通常表现为生产力约束、原材料约束、能源约束、库存

16、约束等资源性约束，也有可能表现为指标约束和需求约束。式等资源性约束，也有可能表现为指标约束和需求约束。式3-2中的中的s.t.是英文是英文Subject to的缩写，是约束条件的意思，的缩写，是约束条件的意思，式（式（3-2）中的个式子就是具体的约束条件。）中的个式子就是具体的约束条件。第四，非负限制。由于在生产实际问题中，资源总是代表一第四，非负限制。由于在生产实际问题中，资源总是代表一些可以计量的实物或人力，因而一般不能是负数。些可以计量的实物或人力，因而一般不能是负数。下一页返回上一页3.1 线性规划及单纯形法线性规划及单纯形法3.1.3 线性规划的标准形式线性规划的标准形式1.线性规划

17、的标准形式线性规划的标准形式线性规划问题的标准形要求所有约束必须为等式约束，变量线性规划问题的标准形要求所有约束必须为等式约束，变量为非负变量，目标函数求最大值。为非负变量，目标函数求最大值。（3-3）（3-4）下一页返回上一页nnxcxcxcZ2211max0,;2,1,0.2122112222212111212111mjmnmnmmnnnnbbbnjxbxaxaxabxaxaxabxaxaxats3.1 线性规划及单纯形法线性规划及单纯形法可将式（可将式（3-3）简写成）简写成 （3-3a）（3-4a）2.非标准化线性规划的标准化非标准化线性规划的标准化对于不符合标准形式（或称非标准形式）

18、的线性规划问题，对于不符合标准形式（或称非标准形式）的线性规划问题，可分别通过下列方法化为标准形式。可分别通过下列方法化为标准形式。（1）目标函数求极小值，即为：）目标函数求极小值，即为：（3-5）下一页返回上一页njjjxc1Zmax),2,1;,2,1(0,0.1minjbxbxatsijnjijijnjjjxc1minZ3.1 线性规划及单纯形法线性规划及单纯形法因为求因为求 等价于求等价于求 ，令，令 ，即化为：，即化为：（3-5a）（2）约束条件为不等式。当约束条件为）约束条件为不等式。当约束条件为“”时，在不等式时，在不等式的左端加上一个非负的的左端加上一个非负的“松弛变量松弛变量

19、”，可将不等式化为等式；，可将不等式化为等式；当约束条件为当约束条件为“”，在不等式的左端减去一个非负的，在不等式的左端减去一个非负的“剩剩余变量余变量”，可将不等式化为等式。松弛变量或剩余变量在实，可将不等式化为等式。松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超用的资源数，均际问题中分别表示未被充分利用的资源和超用的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。系数均为零。下一页返回上一页ZminZ)max(ZZnjjjnjjjxcxc11)(maxZ3.1 线性规划及单纯形法线性规划及单纯形法（

20、3）决策变量无约束。增加两个新的非负决策变量）决策变量无约束。增加两个新的非负决策变量 ，令，令 。例例3-2 将下列非标准型线性规划问题化为标准型。将下列非标准型线性规划问题化为标准型。下一页返回上一页0,0iixxiiixxx321423minxxxZ不限321321321321,0,020040065300432.xxxxxxxxxxxxts3.1 线性规划及单纯形法线性规划及单纯形法解：解：将将令令将第一个约束方程的左边减去一个非负的松弛变量将第一个约束方程的左边减去一个非负的松弛变量x4，将，将第第2、第、第3个约束方程的左边分别加上一个非负的松弛变量个约束方程的左边分别加上一个非负

21、的松弛变量x5和和x6。这样，可以将原来的线性规划问题标准化为：这样，可以将原来的线性规划问题标准化为：返回上一页max(-Z)Zmin0,0,33333xxxxx且65433210004423)max(xxxxxxxZ0,2004006653004432.6543321633215332143321xxxxxxxxxxxxxxxxxxxxxxts3.2 线性规划问题的解线性规划问题的解3.2.1 线性规划问题解的基本概念线性规划问题解的基本概念对于标准形线性规划问题：对于标准形线性规划问题：（3-6）（3-7）1.可行解。满足约束条件（可行解。满足约束条件（3-7）的解，称为线性规划问题）的

22、解，称为线性规划问题的可行解。全部可行解的集合称为可行域。的可行解。全部可行解的集合称为可行域。下一页返回njjjxc1Zmax),2,1;,2,1(0,0.1minjbxbxatsijnjijij3.2 线性规划问题的解线性规划问题的解2.最优解。使目标函数（最优解。使目标函数（3-6）达到最大值的可行解称为最）达到最大值的可行解称为最优解。优解。3.基、基变量、非基变量。基、基变量、非基变量。A为约束方程组的为约束方程组的mn维系数维系数矩阵，秩为矩阵，秩为m，B是矩阵是矩阵A中阶的满秩矩阵，称中阶的满秩矩阵，称B是线性规划是线性规划问题的一个基。问题的一个基。B中的每一个列向量中的每一个

23、列向量 为基向量，与基向量为基向量，与基向量 对应的变量对应的变量xj称为基变量，其余变量就称为非称为基变量，其余变量就称为非基变量。基变量。下一页返回上一页),(212111211mmmmmmaaaaaap pp pp pB B),2,1(miip p),2,1(miip p3.2 线性规划问题的解线性规划问题的解4.基解。对于基基解。对于基B，令非基变量为零，求得满足约束条件的，令非基变量为零，求得满足约束条件的解，称为基解，称为基B对应的基解。对应的基解。5.基可行解。满足变量基可行解。满足变量xj非负条件的基解称为基可行解。非负条件的基解称为基可行解。3.2.2 线性规划问题的图解法线

24、性规划问题的图解法线性规划问题的图解法是建立坐标系，将约束条件在图上表线性规划问题的图解法是建立坐标系，将约束条件在图上表示；确立满足约束条件的解的范围；绘制出目标函数的图形；示；确立满足约束条件的解的范围；绘制出目标函数的图形；确定最优解。图解法主要用于两个变量的线性规划问题。这确定最优解。图解法主要用于两个变量的线性规划问题。这种方法的优点是直观性强，计算方便，但缺点是只适用于问种方法的优点是直观性强，计算方便，但缺点是只适用于问题中有两个变量的情况。题中有两个变量的情况。下一页返回上一页3.2 线性规划问题的解线性规划问题的解例例3-3 用图解法求解下列线性规划模型的解。用图解法求解下列

25、线性规划模型的解。解：具体步骤如下（解：具体步骤如下（图图3-1）：）：下一页返回上一页212maxxxZ0,0233.212121xxxxxxts3.2 线性规划问题的解线性规划问题的解（1）由全部约束条件构造可行域图形。以）由全部约束条件构造可行域图形。以x1为横轴，为横轴，x2为为纵轴建立平面直角坐标系，变量的非负条件将图形限制在第纵轴建立平面直角坐标系，变量的非负条件将图形限制在第一象限。每个约束条件代表一个半平面，如：一象限。每个约束条件代表一个半平面，如：代表代表 边界线的下半平面。全部约束条件即各半边界线的下半平面。全部约束条件即各半平面的交集，成为该线性问题的可行域。显然，可行

26、域内各平面的交集，成为该线性问题的可行域。显然，可行域内各点都满足约束条件，都可作为解，称之为可行解。点都满足约束条件，都可作为解，称之为可行解。下一页返回上一页3321 xx3321 xx3.2 线性规划问题的解线性规划问题的解（2）做出目标函数的等值线。目标函数代表以）做出目标函数的等值线。目标函数代表以Z为参数，斜为参数，斜率为率为 的一簇平行线的一簇平行线 ，位于同一条直线上，位于同一条直线上的点具有相同的目标函数值，因而称它为等值线。的点具有相同的目标函数值，因而称它为等值线。（3）寻找最优解。沿垂直于等值线的方向（即等值线的法）寻找最优解。沿垂直于等值线的方向（即等值线的法线方向）

27、移动目标函数代表的平行线，当移动到点（线方向）移动目标函数代表的平行线，当移动到点（）时，目标函数达到最大。从而确定（时，目标函数达到最大。从而确定（）为最优点，即）为最优点，即 ，为最优解，为最优解，Z的最大值等于的最大值等于 。下一页返回上一页21Zxx122121,2321,23231x212x253.2 线性规划问题的解线性规划问题的解3.2.3 线性规划问题的单纯形法线性规划问题的单纯形法1947年，美国数学家丹齐格（年，美国数学家丹齐格（George Bernard Dantzig）在研究美国空军资源配置问题时，提出了求解线）在研究美国空军资源配置问题时，提出了求解线性 规 划 问

28、 题 的 一 般 解 法性 规 划 问 题 的 一 般 解 法 单 纯 形 法（单 纯 形 法（S i m p l e x Method），从而为线性规划这门学科奠定了基础，使求解），从而为线性规划这门学科奠定了基础，使求解大规模决策问题成为可能。大规模决策问题成为可能。20世纪世纪50年代初，应用电子计年代初，应用电子计算机求解线性规划问题又获得了成功。算机求解线性规划问题又获得了成功。1.单纯形法的原理单纯形法的原理预备知识：凸集和顶点预备知识：凸集和顶点下一页返回上一页3.2 线性规划问题的解线性规划问题的解如果集合中任意两个点如果集合中任意两个点X1、X2，其连线上的所有点也都是集，其

29、连线上的所有点也都是集合合C中的点，称中的点，称C为凸集。为凸集。顶点：凸集顶点：凸集C中满足下述条件的点中满足下述条件的点x称为顶点。称为顶点。定理定理1 若线性规划问题存在可行解，则问题的可行域是凸集。若线性规划问题存在可行解，则问题的可行域是凸集。引理引理 线性规划问题的可行解线性规划问题的可行解 为可行解的为可行解的充要条件是充要条件是X的正分量所对应的系数列向量是线性独立的。的正分量所对应的系数列向量是线性独立的。定理定理2 线性规划问题的基本可行解线性规划问题的基本可行解x对应线性规划问题可行对应线性规划问题可行域（凸集）的顶点。域（凸集）的顶点。定理定理3 若线性规划问题有最优解

30、，一定存在一个基可行解是若线性规划问题有最优解，一定存在一个基可行解是最优解。最优解。下一页返回上一页TnxxX),(13.2 线性规划问题的解线性规划问题的解2.单纯形法的计算步骤单纯形法的计算步骤两个变量的线性规划问题可以用图解法进行求解，而当变量两个变量的线性规划问题可以用图解法进行求解，而当变量是三个或三个以上且约束条件又多时，可行域所在的凸集表是三个或三个以上且约束条件又多时，可行域所在的凸集表现为一个凸多边形，在空间上必将是一个凸几何体；因此无现为一个凸多边形，在空间上必将是一个凸几何体；因此无法通过作图来找可行域，更无法找到最优解，此时图解法就法通过作图来找可行域，更无法找到最优

31、解，此时图解法就显得无能为力，但这些问题可以利用单纯形法进行求解。显得无能为力，但这些问题可以利用单纯形法进行求解。本书只介绍求解约束条件呈本书只介绍求解约束条件呈“”的线性规划问题的单纯形法。的线性规划问题的单纯形法。下一页返回上一页3.2 线性规划问题的解线性规划问题的解用例用例3-1来阐述单纯形法的具体步骤。来阐述单纯形法的具体步骤。解：解：（1 1）将线性规划问题化为标准形。引入松弛变量将线性规划问题化为标准形。引入松弛变量 后将其化为标准形：后将其化为标准形：下一页返回上一页543,xxx5432100045maxxxxxxZ,0,1122521553.54321521421321x

32、xxxxxxxxxxxxxts3.2 线性规划问题的解线性规划问题的解（2）寻找初始可行解。约束方程的系数矩阵寻找初始可行解。约束方程的系数矩阵易见易见 的系数列向量的系数列向量 可作为初始可行基可作为初始可行基下一页返回上一页1 0 0 2 20 1 0 1 20 0 1 5 3),(54321pppppA543,xxx321,ppp1 0 00 1 00 0 1),(321pppB3.2 线性规划问题的解线性规划问题的解对应的变量对应的变量 为基变量，为基变量，为非基变量。由约束条为非基变量。由约束条件得到：件得到：令非基变量令非基变量 ，得到一个基本可行解，得到一个基本可行解 ，于是目标

33、函数值，于是目标函数值下一页返回上一页543,xxx21,xx,0,221125531554321215214213xxxxxxxxxxxxxx021 xxTX)11,5,15,0,0(00045210 xxZ3.2 线性规划问题的解线性规划问题的解（3 3）最优性检验。最优性检验。当当 时，时，显见目标函数未达到最大值，此，显见目标函数未达到最大值，此时说明两种产品的产出均为零，即工厂处于停工状态，利润时说明两种产品的产出均为零，即工厂处于停工状态，利润为零。若从数学角度观察，为零。若从数学角度观察，Z是关于是关于 的一个二元函数，的一个二元函数，可见，只要将其中任何一个变量值增加，即由非基

34、变量变为可见，只要将其中任何一个变量值增加，即由非基变量变为基变量，都可使目标函数值增加。所以，只要在目标函数表基变量，都可使目标函数值增加。所以，只要在目标函数表达式中还存在正系数的非基变量，目标函数值就有增加的可达式中还存在正系数的非基变量，目标函数值就有增加的可能性。因而此时的解不是最优解。能性。因而此时的解不是最优解。下一页返回上一页021 xx0Z21,xx3.2 线性规划问题的解线性规划问题的解（4 4）换基。在目前情况下，将非基变量与基变量对换，都会换基。在目前情况下，将非基变量与基变量对换，都会使目标函数值增加，一般选取正系数比较大的那个非基变量使目标函数值增加，一般选取正系数

35、比较大的那个非基变量 入基，以便使目标函数值较快的增加，同时需要选择一个基入基，以便使目标函数值较快的增加，同时需要选择一个基变量出来成为非基变量。变量出来成为非基变量。由变量的非负条件，有：由变量的非负条件，有：换基后，换基后，成为基变量，而成为基变量，而 仍为非基变量，仍为非基变量，不变。不变。上式为：上式为：下一页返回上一页1x1x2x02x0221102505315215214213xxxxxxxxx3.2 线性规划问题的解线性规划问题的解若使上式均成立，取若使上式均成立，取 ，此时，此时，由，由此确定此确定 为换出基变量。为换出基变量。目前，目前，为非基变量，为非基变量，为基变量，新

36、的约束方为基变量，新的约束方程变为：程变为：下一页返回上一页21102112502550315115114113xxxxxxxxx25211,25,5min1x04x04x42,xx531,xxx3.2 线性规划问题的解线性规划问题的解此时目标函数，此时目标函数，得到一个基本可行解得到一个基本可行解 ，对应的目标函数值，对应的目标函数值 。而从目标。而从目标函数表达式中可以看到，非基变量函数表达式中可以看到，非基变量 的系数仍为正数，说的系数仍为正数，说明函数值还有增加的可能，明函数值还有增加的可能，不一定是最优解，继续使用不一定是最优解，继续使用上述方法对入基、出基变量进行迭代。上述方法对入

37、基、出基变量进行迭代。下一页返回上一页42542342162327215212125xxxxxxxxx422523225xxZTX)6,0,215,0,25(1225Z2x1X3.2 线性规划问题的解线性规划问题的解（5 5）继续换基。在这个过程中，继续换基。在这个过程中，作为入基变量，作为入基变量，仍为仍为非基变量，取零值。由变量的非负条件，有：非基变量，取零值。由变量的非负条件，有：同理，只有取同理，只有取 才能使不等式均成立，此才能使不等式均成立，此时时 ，选取，选取 出基作为非基变量。目前，出基作为非基变量。目前，为非基为非基变量，变量，为基变量，新一轮的约束方程变为：为基变量，新一轮

38、的约束方程变为：下一页返回上一页2x4x6,06715,0272155,02125225223221xxxxxxxxx7156,715,5min2x03x3x43,xx521,xxx3.2 线性规划问题的解线性规划问题的解此时目标函数此时目标函数 ，得到下一个基本可行，得到下一个基本可行解解 ，对应的目标函数值，对应的目标函数值 。非。非基变量的系数为负，说明基变量的系数为负，说明 的值再增加的话只能减少的值再增加的话只能减少Z的值，所以，此时的解已是最优解，的值，所以，此时的解已是最优解，最优值最优值 。下一页返回上一页435432431747272773727157571710 xxxxx

39、xxxx43713737110 xxZ)727,0,0,715,710(2X71102Z43,xxTX)727,0,0,715,710(*7110*Z3.2 线性规划问题的解线性规划问题的解3.单纯形表单纯形表上面介绍的方法中计算与迭代的过程都比较麻烦，而且稍有上面介绍的方法中计算与迭代的过程都比较麻烦，而且稍有不慎便会出错。所以一般采取一种更简洁、更紧凑的方法描不慎便会出错。所以一般采取一种更简洁、更紧凑的方法描述单纯形法，即单纯形表。述单纯形法，即单纯形表。仍以例仍以例3-1来说明单纯形表的使用方法。来说明单纯形表的使用方法。（1）将线性规划问题化为标准形。引入松弛变量后将其划）将线性规划

40、问题化为标准形。引入松弛变量后将其划为标准形：为标准形：下一页返回上一页5432100045maxxxxxxZ,0,1122521553.54321521421321xxxxxxxxxxxxxxts3.2 线性规划问题的解线性规划问题的解在该标准形中，约束方程的系数矩阵在该标准形中，约束方程的系数矩阵而而 的系数列向量的系数列向量 构成一个三阶单位矩阵，构成一个三阶单位矩阵，可作为初始可行基，对应的变量可作为初始可行基，对应的变量 为基变量，为基变量，为非基变量。令非基变量为非基变量。令非基变量 ，得到一个基本，得到一个基本可行解可行解 。下一页返回上一页1 0 0 2 20 1 0 1 20

41、 0 1 5 3),(54321pppppA543,xxx543,ppp543,xxx21,xx021 xxTX)11,5,15,0,0(03.2 线性规划问题的解线性规划问题的解（2）列出初始单纯形表（）列出初始单纯形表（表表3-2）符号与数字说明：符号与数字说明：行填入目标函数的系数。行填入目标函数的系数。列填入基变量，列填入基变量，列填入基变量在目标函数中的系数，列填入基变量在目标函数中的系数，b列填入约束方程等号右端的常数。列填入约束方程等号右端的常数。下对应约束方程当前的系数下对应约束方程当前的系数 。的计算方法，的计算方法，与，与 相交处填入目标函数相交处填入目标函数Z的当前值。的

42、当前值。下一页返回上一页jcBXBCjxijajz31iijTBjaCzi3.2 线性规划问题的解线性规划问题的解 行为检验数行，对应各变量行为检验数行，对应各变量 的检验数的检验数 ，所有所有 表示解达到最优（若要求实现目标函数的最小化，表示解达到最优（若要求实现目标函数的最小化，则所有则所有 表示解达到最优），否则继续进行迭代换基。表示解达到最优），否则继续进行迭代换基。确定入基变量确定入基变量 。此时，此时，确定，确定 入基。入基。列用来确定出基变量，找到入基变量列用来确定出基变量，找到入基变量 后，后，确定出基变量确定出基变量 ，此时，此时，从而确定，从而确定 为出基变量。为出基变量。

43、下一页返回上一页jjxjjjzc 0j0j jkmaxkx50,0,0,4,5maxk1xikx)(minikiilablx25)211,25,315(minil4x3.2 线性规划问题的解线性规划问题的解 所在列与所在列与 所在行交汇处的元素称为主元或枢轴元，所在行交汇处的元素称为主元或枢轴元，以以 表示，进行矩阵的初等行变换，将表示，进行矩阵的初等行变换，将 变为变为1使之所在使之所在列变为单位列向量。于是有列变为单位列向量。于是有表表3-3。此时得到的基本可行解此时得到的基本可行解 ，目标函数值，目标函数值 。（3）继续迭代。从表中可以看出）继续迭代。从表中可以看出 ，于是，于是 换入，

44、换入，换出，得到换出，得到表表3-4。此时此时表表3-4中的所有的中的所有的 ，得到最优解，得到最优解 ，最优值，最优值 。返回上一页kxixlkalkaTX6,0,215,0,2512251Z02322x3x0iTX727,0,0,715,710*7110*Z3.3 运输问题运输问题运输问题是一类特殊的线性规划问题，它最早是从物资调运运输问题是一类特殊的线性规划问题，它最早是从物资调运中提出来的。但以后有些其他问题的模型也归结为运输问题。中提出来的。但以后有些其他问题的模型也归结为运输问题。虽然运输问题也是线性规划问题，可以用单纯形法解决，但虽然运输问题也是线性规划问题，可以用单纯形法解决，

45、但考虑到运输问题数学模型的特点，人们提出了更简单的求解考虑到运输问题数学模型的特点，人们提出了更简单的求解方法：表上作业法。方法：表上作业法。3.3.1 运输问题的数学模型运输问题的数学模型物流中的运输问题可以用以下数学语言描述：物流中的运输问题可以用以下数学语言描述：下一页返回3.3 运输问题运输问题设有某种物资需要从设有某种物资需要从m个个 产地运到产地运到 n 个销地个销地 ，其中每个产地，其中每个产地 的产量为的产量为 ，每个销地每个销地 的销量为的销量为 。设从产地。设从产地 到销到销地地 的单位运价为的单位运价为 ，问该怎样，问该怎样进行物资调运才能使总费用最少进行物资调运才能使总

46、费用最少?这就是由多个产地供应多个销地的品种物资调运问题。如果这就是由多个产地供应多个销地的品种物资调运问题。如果该问题的总产量等于总销量，即有该问题的总产量等于总销量，即有 ，则称该问，则称该问题为产销平衡的运输问题；否则，称为产销不平衡的运输问题为产销平衡的运输问题；否则，称为产销不平衡的运输问题。题。下一页返回上一页mA,AA21nB,BB21iA),2,1(miaijB),2,1(njbjiAjB),2,1,2,1(njmicij；njjmiiba113.3 运输问题运输问题3.3.2 产销平衡问题运输产销平衡问题运输根据上述参量的意义列出产销运价根据上述参量的意义列出产销运价表表3-

47、5。表中：表中：的单位为吨、公斤、件等；的单位为吨、公斤、件等；的单位为吨、公斤、的单位为吨、公斤、件等；件等；的单位为元的单位为元/吨等。吨等。的单位应一致。的单位应一致。表的右下角表的右下角 表示各产地产量的总和，即总产量或总发量；表示各产地产量的总和，即总产量或总发量；表示各销地销量的总和。表示各销地销量的总和。令令 表示某物资从发点表示某物资从发点 到收点到收点 的调拨量（运输量），的调拨量（运输量），可以列出产销平衡可以列出产销平衡表表3-6。下一页返回上一页iajbijcijjicba,iajbijxiAjB3.3 运输问题运输问题将将表表3-3和和表表3-4合在一起，得到一个新表

48、，被称为运输表合在一起，得到一个新表，被称为运输表（或称为产销矩阵表），如（或称为产销矩阵表），如表表3-7所示。所示。根据根据表表3-7求解运输问题的数学模型为：求解运输问题的数学模型为：下一页返回上一页),2,1;,2,1(njmixij),2,1;,2,1(0),2,1(),2,1(11njmixnjbxmiaxijmjjijniiijminjijijxcZ11min3.3 运输问题运输问题从上面的运输问题的数学模型中可以看到，它包含从上面的运输问题的数学模型中可以看到，它包含 个个变量，有变量，有n个约束条件。如果用单纯形法求解，应先在每个个约束条件。如果用单纯形法求解，应先在每个约束

49、方程中引进一个人工变量。这样一来，即使是约束方程中引进一个人工变量。这样一来，即使是 ，这样简单的运输问题，变量数就有这样简单的运输问题，变量数就有12个，显然计算起个，显然计算起来非常繁杂；而用表上作业法来求解运输问题则比较简便。来非常繁杂；而用表上作业法来求解运输问题则比较简便。下一页返回上一页nm3m4n3.3 运输问题运输问题用表上作业法求解运输问题时，同单纯形法类似，首先要求用表上作业法求解运输问题时，同单纯形法类似，首先要求出一个初始方案（即线性规划问题的初始基本可行解）。一出一个初始方案（即线性规划问题的初始基本可行解）。一般来讲这个方案不一定是最优的，因此需要给出一个判别准般来

50、讲这个方案不一定是最优的，因此需要给出一个判别准则，并对初始方案进行调整、改进。每进行一次调整，就得则，并对初始方案进行调整、改进。每进行一次调整，就得到一个新的方案（基本可行解），而这个新方案一般比前一到一个新的方案（基本可行解），而这个新方案一般比前一个方案要合理些，也就是对应的目标函数个方案要合理些，也就是对应的目标函数Z值比前一个方案值比前一个方案要小些。经过若干次调整，我们就得到一个使目标函数达到要小些。经过若干次调整，我们就得到一个使目标函数达到最小值的方案最小值的方案最优方案（最优解），而这些过程都可在最优方案（最优解），而这些过程都可在产销矩阵表（运输表）上进行，故称为表上作业