1、2009.11.15 1 运筹学基础运筹学基础 李荣钧李荣钧 博士，教授，博士生导师博士，教授，博士生导师 2009.11.15 2 运筹学既是一门科学运筹学既是一门科学 又是一门艺术又是一门艺术 2009.11.15 3 教学内容教学内容 第一章：第一章： 绪言绪言 第二章：第二章： 线性规划线性规划 第三章：第三章： 运输模型与分配问题运输模型与分配问题 第四章：第四章： 整数规划整数规划 第五章：第五章： 图论基础与网络分析图论基础与网络分析 第六章：第六章： 网络计划技术网络计划技术 第七章：第七章： 库存论库存论 第九章：第九章： 决策论决策论 2009.11.15 4 第一章：绪言
2、第一章：绪言 2009.11.15 5 1.1 1.1 绪言：运筹学的产生与发展绪言：运筹学的产生与发展 运筹学在商业活动与行政事务中的早期应用可追溯 到几个世纪以前，但是系统的运筹学理论起源于二次大 战期间。最初是英国军方为了最大限度地利用已经十分 短缺的战争资源，召集了一批科学家与工程技术人员共 同筹划作战物资的分配问题。英国军方的这一举动很快 引起了美国军方的重视，类似的研究小组在美国三军机 构中相继成立，并开发出一套相对完整的新技术，用以 指导协约国方面在战略上和战术上的各种军事行动。许 多诺贝尔奖金获得者都为运筹学的建立与发展作出过重 要的贡献。其中，最早投入运筹学研究的诺贝尔奖金获
3、 得者是美国物理学家Blackett。他领导了第一个以运筹学 命名的研究小组。由于该小组的成员来自各个方面，既 有物理学家，也有经济学家、数学家、社会学家和心理 学家，因而被人们戏称为Blackett马戏团。可以看出，运 筹学是一门应用性极强的交叉科学。 2009.11.15 6 由于运筹学技术在二次大战中的成功运用，它与 许许多多受战争推动而产生的其它科学技术一样，在 战争结束后立即引起了民间组织和商业机构的浓厚兴 趣。因为随着社会工业化程度的逐步提高，各种生产 组织和商业机构变得越来越大，与之相关的管理决策 问题也变得越来越复杂。过去那种凭直观、凭感觉、 凭经验决策的方式已几乎不再可能。企
4、业家们迫切需 要一种定量分析的技术来帮助他们正确处理日益复杂 的经济决策问题。于是运筹学技术很快被运用到了民 间组织和商业机构的管理决策当中，且由于其影响之 大、应用之广，以至于在民间应用的特定环境中，运 筹学这一带有军事色彩的专业术语被代之以管理科学 这一颇具现代气息的新名词 2009.11.15 7 1.2 1.2 运筹学的科学性和艺术性运筹学的科学性和艺术性 作为科学，运筹学必须在科学方法论的指导下 进行科学探索。其工作步骤包括： (1) 确定问题：目标、约束、变量和参数。 (2) 建立模型：目标、约束、变量和参数之间 的关系。 (3) 求解模型：最优解、有效解和满意解。 (4) 解的检
5、验：正确性、有效性和稳定性。 (5) 解的控制：灵敏度分析。 (6) 解的实施：解释、培训和监测。 2009.11.15 8 作为艺术，运筹学涉及到决策者的社会环境、心理 作用、主观意愿和工作经验等多方面的因素，而这些因 素又大都具有模糊特征与动态性质。为了有效地应用运 筹学，前英国运筹学学会会长托姆林森提出以下原则： (1) 合伙原则：运筹学工作者与管理工作者相结合。 (2) 催化原则：多学科协作，打破常规。 (3) 渗透原则：跨部门、跨行业联合。 (4) 独立原则：不受某人或某部门的特殊政策所左 右。 (5) 宽容原则：广开思路，兼容并蓄。 (6) 平衡原则：平衡矛盾，平衡关系。 2009
6、.11.15 9 1.3 1.3 运筹学的方法论运筹学的方法论 模型是运筹学研究客观现实的工具和手段。常 见的模型有以下3种基本形式： (1) 思维模型：它是研究者对于某种事物的想象 或者概念性的描述，譬如公司主管头脑中对于公司 未来市场的规划。这虽然不是一种精确、具体、可 见的形式，但通常是其它模型的原源。 (2) 物理模型：它可以是一个与实物同等尺寸、 或者被放大、或者被缩小、或者被简化的几何模型， 用以形象地表现和演示被研究的对象；它也可以是 一些图表，用以说明事物的流程。 (3) 数学模型：它是采用数学符号来精确描述实 际事物中的变动因素和因素间的相互关系。 2009.11.15 10
7、 构造模型是一种创造性劳动，成功的模型往往是科学 和艺术的结晶。建模的方法和思路有以下4种： (1) 直接分析法：根据研究者对问题内在机理的认识 直接构造模型，并利用已知的算法对问题求解与分析。如 线性规划模型，动态规划模型，排队模型，存储模型，决 策与对策模型等等。 (2) 类比法：模仿类似问题的结构性质建立模型并进 行类比分析。如物理系统、化学系统、信息系统、和经济 系统之间都有某些相通的地方，因而可互相借鉴。 (3) 统计分析法：尽管机理未明，但可根据历史资料 或实验结果运用统计分析方法建模。 (4) 逻辑推理法：利用知识和经验对事物的变化过程 进行逻辑推理来构造模型。 2009.11.
8、15 11 数学模型是三种常见模型中最抽象、最复杂的模型， 它反映的是事物的本质。数学模型的一般形式可以写为： 目标的评价准则 U = f(xi, yj, k) 约束条件 g(xi, yj, k) 0 式中： xi为可控变量； yj为已知参数； k为不确定性因素。 目标的评价准则一般要求达到最佳(最大或最小)、适 中、满意等。准则可以是单一的，也可以是多个的。约束 条件可以有许多，也可以一个没有。如果g为等式，即为 平衡条件。当模型中没有不确定性因素时，称之为确定性 模型。如果不确定性因素是随机因素，则为随机模型；如 果是模糊因素，则为模糊模型；如果既有随机因素又有模 糊因素，则为模糊随机模型
9、。 1.4 1.4 数学模型与定量分析数学模型与定量分析 2009.11.15 12 在建立了问题的数学模型之后，如何求解模型是运筹 学的另一个关键所在。运筹学的进步有赖于定量分析技术 的应用与发展，尤其是近年来计算机技术的迅速提高，各 种管理决策方面的应用性软件相继推出，使决策者得以借 助于计算机对复杂的实际问题进行定量分析，大大改进了 定量技术的有效性。 必须指出的是，我们在应用数学模型和定量分析技术 的时候应该十分小心。因为实际问题通常是复杂的，它包 含着许许多多数字的和非数字的有用信息。在数学模型的 量化与抽象过程中，很容易由于理想化而偏离实际情况从 而失去代表性。 13 2009.1
10、1.15 第二章：线性规划第二章：线性规划 14 2009.11.15 2.1 2.1 线性规划的数学模型线性规划的数学模型 原材料消耗 (吨) 产品利润 (千元/吨) 产品需求量(吨) A B C 产品 I 10 6 8 5 不大于1500 II 5 20 15 7 不小于100 原材料最大供应 量(吨) 600 500 800 线性规划是运筹学的一个重要分支。自1947年美国数 学家Dantzig提出了求解线性规划的单纯形方法之后，已被 广泛应用于现代工业、农业、交通运输、军事、经济等各 种决策领域，成为科学管理的重要手段之一。 例2.1(生产计划问题) 某化工厂在计划期内拟安排生产I 、
11、 II两种产品，已知其市场需求量和单位利润及原材料的消耗 量如表2.1所示。问应如何安排生产计划以使该工厂的获利 最多？ 表2.1 生产计划综合信息 2009.11.15 15 max75 21 xxZ 800158 500206 600510 21 21 21 xx xx xx 1500 1 x 解解 该问题可用以下的数学模型描述：设x1、x2分别表 示产品I、II的产量，则工厂追求的目标可写成利润函数 式中：符号max表示对利润函数Z求极大值。目标追求所 受到的限制来自原材料供应和产品需求两个方面，其中 原材料供应施加的约束条件可以写为 表2.1提供的信息将第一种产品的计划产量限制在150
12、0吨 以内，但对第二种产品的产量并未构成实质性约束，即 2009.11.15 16 0, 1500 800158 500206 600510 . . 75max 21 1 21 21 21 21 xx x xx xx xxts xxZ 以上4个约束条件被称为显式约束条件。此外，考虑 到变量x1、x2分别表示产品I、II的产量，取值范围应满足 大于等于零的要求，否则没有意义。这一类公理性的约束 条件被称为隐式约束条件。 综上所述，该问题的数学模型可写为： 例2.2(边角余料问题) 某纸厂生产纸卷的标准宽度为20 英尺。现有三宗订单，所要求纸卷的宽度分别为5、7、9 英尺，需求量分别为150卷、2
13、00卷、300卷。厂家需从标 准宽度的纸卷上进行切割以满足顾客的订货要求。问应如 何切割以满足顾客的订购需求且使废弃的边角余料最少？ 解 该问题中纸卷的可能切割方式共有6种(见图2.1)。 |5|5|5|5| |5|5|7|3| |5|5|9|1| |5|7|7|1| |7|9| 4 | | 9 | 9 | 2 | 图图2.1 基本切割方式基本切割方式 2009.11.15 17 2009.11.15 18 其线性规划的数学模型可以表示为： 65432 43min Wxxxxx 150224 . 4321 xxxxts 2002 542 xxx 3002 653 xxx 且为整数， 0 i x
14、i 上述数学模型的目标函数也可以改写为： 6 1 654321 j j xxxxxxxW min 作为一个练习，请读者仔细思考上述两个模型的差别。 2009.11.15 19 例2.3(连续投资问题) 某公司考虑两种可能的连续投资 计划A和B。其中，计划A每元投资每年可赢利0.1元；计 划B每元投资每2年可赢利0.3元。设公司在第一年年初拟 用于投资的金额为100万元，问应如何安排投资计划可使 该公司在第3年年末所收回的资金最多？ 解 令xij 表示公司在第i年年初投资于计划j中的金额， 则今后3年可能的投资情况如表2.2所示： 表表2.2 投资分析表投资分析表 年份 年初可用金额 (万元)
15、投资计划 年末收回金额 (万元) A B 1 100 x1A x1B 1.1x1A 2 1.1x1A x2A x2B 1.1x2A+1.3x1B 3 1.1x2A+1.3x1B x3A 1.1x3A+1.3x2B 2009.11.15 20 jix xxx xxx xxts xx. ij BAA ABA BA BA , 0 3 . 11 . 1 1 . 1 100. 3 . 111 123 122 11 23 Zmax 故该投资问题的线性规划模型为： 从以上的例题分析可以看出，建立线性规划的数学模 型要求决策者回答三个问题：(1) 变量是什么？(2) 目标函数 是什么？(3) 约束条件是什么？
16、其中，变量是线性规划建模 的关键与基础。如果变量设计合理，便容易回答后面的两 个问题；否则不易找到目标函数与约束条件的表示形式， 即使勉强完成了建模，也难以理解模型的物理意义。 2009.11.15 21 2.2 2.2 线性规划的图解方法线性规划的图解方法 例2.4 考虑下面的线性规划问题： 0, 2 1- 82 62 . . 23 Z max 21 2 2 1 21 21 21 xx x xx xx xxts xx 2009.11.15 22 3/38 3/4 3/10 82 62 2 1 21 21 Z x x xx xx 步骤1 在约束条件的基础上确定线性规划的可行域 步骤2 在目标函
17、数的基础上确定可行域中的最优点 步骤3 求解最优点对应的变量值和目标函数值 2009.11.15 23 2 2. .3 3 线性规划的标准形式线性规划的标准形式 线性规划的标准形式： njx mibxats xcZ j ij n j ij n j jj ,.,2 , 1 , 0 ,.,2 , 1 , . . max 1 1 2009.11.15 24 1非负变量： 。 若变量 xi 无约束，可将其改写为两个非负变量之差 的表示形式，即 ，其中 2极大型目标函数：max。 对于极小型目标函数min，可采用等价变换转化为极 大型目标函数max，即 3等式约束条件：。 对于型或型的不等式约束条件，可
18、通过添加外在 变量的方法将不等式约束条件转换为等式约束条件。如： jx j , 0 iii xxx0, ii xx )- ( min maxZZ 25352535 10431043 5321321 4321321 xxxxxxx xxxxxxx 2009.11.15 25 例2.5 将以下线性规划改写为数学模型的标准形式 0 647 52 10. 32min 2 21 21 21 21 x xx xx xxts xxZ 解 )max(min, 1 11 ZZxxx 0, 6477 522 10. 322)(max 432 1 1 42 1 1 32 1 1 2 1 1 2 1 1 xxxxx
19、xxxx xxxx xxxts xxxZ 2009.11.15 26 2.4 2.4 常规单纯形方法常规单纯形方法 由线性代数的原理可知，一个包含n个变量和m个方程 的线性方程组，当nm时是一个不定型方程组，其中包含有 无穷多个解。此时，n个变量被分为两组，一组是基本变量， 数目等于m；另一组为非基本变量，数目等于nm。令非基 本变量的取值为零，然后对基本变量求解方程组，可以得到 一组唯一的解，称为基本解。如果基本解中全部变量的取值 是非负的，则称为可行基本解；否则为不可行基本解。关于 基本变量的选择，原则上是任意的，只要所选出的变量相互 独立即可。例如，考虑下面的线性方程组： 322 242
20、 4321 4321 xxxx xxxx 式中n=4, m=2, n-m=2，故4个变量中的2个是基本变量，另 外2个是非基本变量。显然，除了x1和x3因为线性相关而不 能同时选为基本变量外，变量间其他的两两组合都可以产 生一个基本解。 2009.11.15 27 若令 x3 = x4 = 0，则有 32 22 21 21 xx xx 若令 x1 = x2 = 0，则有 32 24 43 43 xx xx 线性规划的可行基本解与不可行基本解在线性规划 的单纯形算法中起着同等重要的作用，并因此形成 单纯形方法的两个分支：常规单纯形与对偶单纯形。 2009.11.15 28 0, 2 1 82 6
21、2. 23max 432121 42 321 221 121 21 ssssxx sx sxx sxx sxxts xx - Z , 重新考虑例2.4中的线性规划问题，旨在观察图解方法 的代数演绎过程。首先将线性规划的数学模型标准化，即 这里 n=6, m=4, n-m=2。若将x1和x2确定为非基本变量，其 对应的初始解是一个可行基本解： x1 = 0, x2 = 0, s1= 6, s2 = 8, s3 = 1, s4= 2 它相应于图2.2中的坐标原点A，其目标函数值Z = 0 2009.11.15 29 由图2.3可见，从A点出发，沿着可行域的边界有两条 路线可以到达最优点C。一条是：
22、 ，另一 条是： 。显然，两条路线的长度不一样。换言之， 不同搜索方式有着不同的效率。作为对方法的要求，这里 有两个问题需要解决：一是行走的方向，二是行走的距离。 前者涉及解的好坏，即优化性；后者涉及解的对错，即可 行性。 图图2.3 CDEFA CBA 2009.11.15 30 根据高斯约旦的消元法则，每次交换解中的一个非 基本变量与基本变量。其中，被交换的非基本变量称为进 入变量，而对应的基本变量称为退出变量。 为了解释进入变量和退出变量的选择原则，需要先回 顾线性规划数学模型的物理含义。一般而言，极大型目标 函数中变量的系数可视为相应产品的单位利润或单位收益 （例如生产计划问题）。本例
23、中坐标原点所对应的生产系 统尚处于计划实施前的空闲状态，即系统有能力生产两个 不同的产品，但目前一个产品都还没有生产。现在面临的 问题是：如果暂时只能生产一个产品，应该选择哪一个产 品作为生产对象？在不考虑其他方面影响因素的前提下， 一个直观的想法应该是选择单位利润或单位收益最大的产 品作为生产产品。换言之，进入变量应为目标函数中最大 正系数所对应的变量，这一原则被称为线性规划单纯形方 法的优化原则。 2009.11.15 31 根据优化原则，例2.4中下一步的进入变量应为非基本变量x1。相应 的退出变量则由各种资源允许产品I生产的数量来决定，其计算结果为： 资源1允许产品I生产的数量：6/1
24、 = 6 资源2允许产品I生产的数量：8/2 = 4 资源3允许产品I生产的数量：1/-1 = -1 资源4允许产品I生产的数量：2/0 = 其中负比值没有意义，无穷大意味着没有限制，故真正反映生产资源最 薄弱环节的比值应是其中的最小正比值，它表示资源允许产品I生产的 最大数量。本例中的最小正比值为4，由约束直线2取得，故与之对应的 基本变量s2应该退出，因为x1=4时，s2=0。上述退出变量的选择原则被 称为常规单纯形方法的可行性原则。x1和s2的交换导致新的基本可行解： x2 = 0, s2 = 0, x1= 4, s1= 2, s3= 5, s4= 2 它相应于图2-2中的B点，其目标函
25、数值Z = 12。 重复上述过程，可逐步达到问题的最优解： x1 = 10/3，x2 = 4/3，Z = 38/3 对应图2.2中的C点。 2009.11.15 32 常规单纯形方法的两个重要原则是： (1) 优化原则：极大问题中的进入变量是目标函数中最 大正系数所对应的非基本变量；如果目标方程中所有非基 本变量的系数均为负数，则该可行解即为最优解。 (2) 可行原则：极大问题中的退出变量都是在进入变量 轴上具有最小正比值的基本变量。如果存在两个或两个以 上的最小正比值，可任选其中之一。 常规单纯形方法的迭代步骤概括为： 步骤1 在线性规划标准模型的基础上确定一个可行基 本解作为初始解 步骤2
26、 依据优化原则从目前的非基本变量中选择一个 进入变量 步骤3 依据可行原则从目前的基本变量中选择一个退 出变量 步骤4 交换进入变量和退出变量以产生新的可行基本 解，然后返回步骤2。 2009.11.15 33 2.4.2 2.4.2 常规单纯形表上作业常规单纯形表上作业 单纯形方法的运算过程可基于Gauss-Jordan的消元 法则在单纯形表上完成。单纯形表的制作形式与线性规 划的数学模型一一对应。但在制作单纯形表之前，应先 将目标函数改写为方程式。例如： Z = 3x1+2x2 Z -3x1-2x2 = 0 为此，常规单纯形的优化原则需做如下修改： (1) 优化原则：极大问题的进入变量是目
27、标函数中 绝对值最大的负系数所对应的非基本变量；如果目标方 程中所有非基本变量的系数均大于等于零，则该可行解 即为最优解。 (2) 可行原则：极大问题的退出变量都是在进入变 量轴上具有最小正比值的基本变量。如果存在两个或两 个以上的最小正比值，可任选其中之一。 2009.11.15 34 依据优化和可行原则，x1和s2分别为进入变量和退出变 量，故表中与之对应的列和行被分别称为进入列和退出行。 同时，将位于进入列和退出行相交单元上的元素定义为基准 元素，它在单纯形的表上作业法中占有特殊的地位并发挥重 要作用。线性规划单纯形表上作业的有关说明见表2.7。 退出行 检验数 进 入 列 基准元素 表
28、表 2.7 目标与基 X1 X2 S1 S2 S3 S4 解 X1轴上截距 (比值) Z -3 -2 0 0 0 0 0 S1 1 2 1 0 0 0 6 6/1 = 6 8/2 = 4 1/-1 = -1 2/0 = S2 1 0 1 0 0 8 S3 -1 1 0 0 1 0 1 S4 0 1 0 0 0 1 2 35 2009.11.15 原基准行 2 1 0 1 0 0 8 原基准元素 2 新基准行 1 1/2 0 1/2 0 0 4 单纯形表上作的计算步骤可以概括为： (1) 先计算基准行：新基准行元素 = 原基准行元素 / 原基准元素 (2) 后计算其它行：新行元素 = 原行元素
29、原进入列对应元素 新基准行元素 本例中新基准行、新目标行和新的S3-行的计算结果为： (1) 新基准行 2009.11.15 36 原目标行 -3 -2 0 0 0 0 0 -(-3)新基准行 3 3/2 0 3/2 0 0 12 新目标行 0 -1/2 0 3/2 0 0 12 原S3行 -1 1 0 0 1 0 1 -(-1)新基准 行 1 1/2 0 1/2 0 0 4 新S3行 0 3/2 0 1/2 1 0 5 (2) 新目标行 (3) 新 S3 行 2009.11.15 37 例2.4: 完整的表上作业 目标与基 X1 X2 S1 S2 S3 S4 解 A点点 Z -3 -2 0
30、0 0 0 0 S1 1 2 1 0 0 0 6 S2 2 1 0 1 0 0 8 S3 -1 1 0 0 1 0 1 S4 0 1 0 0 0 1 2 B点点 Z 0 -1/2 0 3/2 0 0 12 S1 0 3/2 1 -1/2 0 0 2 X1 1 1/2 0 1/2 0 0 4 S3 0 3/2 0 1/2 1 0 5 S4 0 1 0 0 0 1 2 C点点 Z 0 0 1/3 4/3 0 0 38/3 X2 0 1 2/3 -1/3 0 0 4/3 X1 1 0 -1/3 2/3 0 0 10/3 S3 0 0 -1 1 1 0 3 S4 0 0 -2/3 1/3 0 1 2/
31、3 2009.11.15 38 2.4.4 2.4.4 单纯形应用中的特殊情形单纯形应用中的特殊情形 单纯形应用中可能出现的几种特殊情形为：退 化解，多优解，无界解，无可行解 (1) 退化解：在使用单纯形表确定退出变量时， 如果有两个以上的基本变量具有相同的最小比值， 那么在下一个单纯形表中会出现一个或几个基本变 量取值为零、而目标值不变的情形，这样得到的新 解被称为退化解。起因是模型的构造不合理，其中 包含了一个或多个冗余约束条件。 2009.11.15 39 例2.6 考虑以下线性规划问题： 0, 42 84. 93max 21 21 21 21 xx xx xxts xx Z 目标与基
32、X1 X2 X3 X4 解 比值 迭代1 Z -3 -9 0 0 0 X3 1 4 1 0 8 2 X4 1 2 0 1 4 2 迭代2 Z -3/4 0 9/4 0 18 X2 1/4 1 1/4 0 2 X4 1/2 0 -1/2 1 0 迭代3 Z 0 0 3/2 3/2 18 X2 0 1 1/2 -1/2 2 X1 1 0 -1 2 0 2009.11.15 40 (2) 多优解：当目标直线平行于包含最优解的 约束直线时，该约束直线在可行域中的任意一点 都是问题的最优解。 例2.7 考虑以下线性规划问题 0, 4 52 . . 42 max 21 21 21 21 xx xx xxt
33、s xxZ 2009.11.15 41 (3) 无界解：当极大问题的可行域上方无界或 极小问题的可行域下方无界时，目标函数值可增 至无穷大或减至无穷小，这样的解被称为无界解。 例2.8 考虑以下线性规划问题 0, 40 2 10 . . 2 Zmax 21 1 21 21 xx x xxts xx 2009.11.15 42 (4) 无可行解：约束条件互相矛盾，导致问题 的可行域不存在。 例2.9 考虑以下线性规划问题 0, 12 43 22 . . 23 Zmax 21 21 21 21 xx xx xxts xx 2009.11.15 43 2.5 2.5 对偶单纯形方法对偶单纯形方法 常
34、规单纯形方法是从一个欠优的可行基本解开始， 在求解过程中始终保持解的可行性而逐步改进解的优 化性；反之，对偶单纯形方法则从一个超优的不可行 基本解开始，在求解过程中始终保持解的优化性而逐 步改进解的可行性。 例2.10 给定线性规划的数学模型 0, 3 634 33 . . 23 Zmin 21 2 1 21 21 21 xx xx xx xxts xx 0, 3 634- 3 3- . . 23 Zmin 54321 52 1 421 321 21 xxxxx xxx xxx xxxts xx 2009.11.15 44 (1) 图解法：问题的初始解为 X = (0, 0, -3, -6,
35、3)T，Z=0 相应于图中的A点，即坐标原点。最优解为： 2 . 4 ,)2 . 1 , 6 . 0(Zx* T 2009.11.15 45 (2) 对偶单纯形方法 回顾常规单纯形方法的求解过程，现行解可行而未优 化，故先选择最可能改进优化性的非基本变量作为进入变 量，然后考虑退出变量的问题，其交换顺序是先进后出； 而在对偶单纯形方法中，现行解超优但不可行，故先选择 最不可行的基本变量让其离开，然后考虑进入变量的问题， 其交换顺序是先出后进。相应原则为： 可行性原则：离开变量是取负值且绝对值最大的基本 变量。 优化性原则：极小问题的进入变量是具有最小比值的 非基本变量；极大问题的进入变量是具有
36、最小绝对比值的 非基本变量。 比值的确定方式是用目标行系数除以退出行中相应的 负系数。如果退出行中所有的系数均大于或等于零，则该 问题不存在可行基本解。 2009.11.15 46 例2.10 的对偶表上作业过程介绍如下 目标与基 X1 X2 X3 X4 X5 解 迭代1 Z -3 -2 0 0 0 0 X3 -3 -1 1 0 0 -3 X4 -4 -3 0 1 0 -6 X5 1 1 0 0 1 3 比值 3/4 2/3 迭代2 Z -1/3 0 0 -2/3 0 4 X3 -5/3 0 1 -1/3 0 -1 X2 4/3 1 0 -1/3 0 2 X5 -1/3 0 0 1/3 1 1
37、 比值 1/5 2 迭代3 Z 0 0 -1/5 -3/5 0 21/5 X1 1 0 -3/5 1/5 0 3/5 X2 0 1 4/5 -3/5 0 6/5 X5 0 0 -1/5 2/5 1 6/5 2009.11.15 47 2.2.6 6 常规常规- -对偶算法对偶算法( (广义单纯形广义单纯形) ) 常规对偶算法是常规单纯形和对偶单纯形的自然扩展， 它允许使用者从一个既不可行、也未优化的任意基本解开始， 灵活运用常规单纯形方法或对偶单纯形方法，以最简捷的方 式趋近最优解。 例2.11 考虑以下线性规划问题 623 . . 2 Zmin 21 21 xxts xx 0, 5 32 2
38、1 21 21 xx xx xx 0, 5 32 623 . . 2 Zmin 32121 321 221 121 21 sssxx sxx sxx sxxts xx 2009.11.15 48 初始解：x1=0, x2=0, s1=-6, s2=-3, s3=5, Z=0 。此解既未优化， 也不可行，变换过程见下表，优化路径：AFG。 目标与基 X1 X2 S1 S2 S3 解 迭代1 Z -1 2 0 0 0 0 S1 -3 -2 1 0 0 -6 S2 -1 -2 0 1 0 -3 S3 1 1 0 0 1 5 迭代2 Z -4 0 1 0 0 -6 X2 3/2 1 -1/2 0 0
39、3 S2 2 0 -1 1 0 3 S3 -1/2 0 1/2 0 1 2 迭代3 Z -3 0 0 0 -2 -10 X2 1 1 0 0 1 5 S2 1 0 0 1 2 7 S1 -1 0 1 0 2 4 2009.11.15 49 一般来说，广义单纯形方法在确定进入和退出变量 时不需要计算比值。对于标准化线性规划(max)而言， 其进、出原则可自然实现如下： 1因为现行解未优化，则检验数中必然有负数， 故根据优化原则，应选择绝对值最大的负检验数对应的 非基本变量作为进入变量； 2因为现行解不可行，则基本变量的取值中必然 有负数，故故根据可行性原则，应选择绝对值最大的负 数所对应的基本变
40、量作为退出变量。 由本例的求解路线可以看出，广义单纯形方法的搜 索轨迹并不总是“一步一个脚印”，而有可能采取走 “捷径(cut path)”的方式，跨越线性规划的某些基本 解，如本例图2.9中的E点。 2009.11.15 50 2.2.7 7 改进单纯形改进单纯形 线性规划的矩阵模型 0 . . max x bAxts cxZ T m T nn bbbbxxxxcccc),.,( ,),.,( ),.,( 212121 其中： T mjjjj aaap),.,( 21 )( . :.: . . 21 21 22221 11211 n mnmm n n ,p,pp aaa aaa aaa AL
41、 2009.11.15 51 约束条件Ax = b是一个含m个方程和n个变量的线 性方程组，其中n m。依据线性代数理论，从系数矩 阵A中任选m个线性独立的列向量 均可产生问题的一 个基本解。这m个列向量所构成的方阵B被称为线性规 划的基： ).( . :.: . . 21 21 22221 11211 m mmmm m m ,p,pp aaa aaa aaa B 显然，这样的方阵必须是非奇异的，即：|B| 0。 2009.11.15 52 例2.12 设某线性规划的系数矩阵为： 100 0 325 01000 2 1 00 1 11 1 1 - - A 这里m = 3, n = 7, nm
42、= 4。容易验证，p1, p2, p3可以构 成一个基B，因为 09 325 021 111 但是p4和p5就不能同时被包含在任何基本矩阵中，因为 它们线性相关：p4 = p5 2009.11.15 53 线性规划单纯形方法中的初始基是一个单位矩阵，即 B = I。然后每次交换基内、外的一个列向量，逐步将现行 解推向优化(常规单纯形)或推向可行(对偶单纯形)。这一 过程的数学描述为：设xI, xII 分别代表初始基中的非基本 变量和基本变量，前者由决策变量和剩余变量组成，后者 由松弛变量和人工变量组成。则线性规划的矩阵模型可以 改写为： 0 )( . . )( max II III I II
43、I III ,xx b x x A,Its x x ,CCZ b x x Z IA -CC II I 0 0 1 21 2009.11.15 54 对于任何一个中间过程，用xB, cB表示与现行基B对 应的基本变量及其目标系数，考虑到非基本变量等于 零的事实，则线性规划的数学模型可以写为： 0 . max BB x x xZ bBts C B bx Z B C B B 0 0 1 B CB 0 1 1 1 0 1 B BCB 将上式的两边左乘矩阵 的逆矩阵 ,即 可导出目标值和基本变量取值的理论计算公式： bB bBC bB BC x Z BB B 1 1 1 1 0 0 1 2009.11.
44、15 55 上式对应单纯形表中的最后一列，即问题的结果部 分。为了判断和改进现行解的优化性，有必要进一步导 出单纯形表的其余部分，包括检验数与进入列或退出行 的计算公式。 bB bBC bB BC x x Z IA CC B BC BB II I III B 1 1 1 1 1 1 0 0 1 0 1 0 1 bB bBC x x Z IBAB CIBCC-ABC 1- 1- B II I 11 II 1 B 1 B 0 1 I 2009.11.15 56 上式可以改写成单纯形表的初始形式 目标与基 xI xII 解 Z CBB-1ACI CBB-1CII CBB-1b xB B-1A B-1 B-1b 上表所示的单纯形算法结构中，由于xI, xII 始终对应着 初始解中的基本变量和非基本变量，随着解的变换演进， 使用不很方便。故更常见的单纯形算法结构为： 目标
