《管理运筹学》（第2版）1-5章教案

《运 筹 学》教案

主讲人：李军华

课 程 名 称： 《运筹学》 课 程 主 讲 人： 李军华 专 业 班 级： 信息2001级合班 主讲人所在单位： 经济与管理学院信息管理学系

华南师范大学

经济与管理学院信息管理学系 2005年9月

面向21世纪课程教材

普通高等学校管理科学与工程类学科核心课程教材

管 理 运 筹 学

( 第2版) 韩伯棠 编著

高等教育出版社

高等教育电子音像出版社

1

目录

第一章 绪论 第二章 线性规划的图解法 第三章 线性规划问题的计算机求解 第四章 线性规划在工商管理中的应用 第五章 单纯形法 第六章 单纯形法的灵敏度分析与对偶 第七章 运输问题 第八章 整数规划 第九章 目标规划 第十章 动态规划 第十一章 图与网络模型 第十二章 排序与统筹方法 第十三章 存贮论 第十四章 排队论 第十五章 对策论 第十六章 决策分析 第十七章 预测

2

第一章 绪论

?§1 决策、定量分析与管理运筹学 ?§2 运筹学的分支

?§3 运筹学在工商管理中的应用

?§4 学习运筹学必须使用相应的计算机 软件，必须注重于学以致用的原则

第一章 绪论

运筹学（Operational Research) 直译为“运作研究”。

运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。

? 运筹学的产生和发展

运筹学产生于第二次世界大战，主要用于解决如何在与德军的对抗中最大限度地杀伤敌人，减少损失。二战以后，运筹

学得到了快速的发展，形成了许多分支，并且计算机的应用极大地推动了运筹学的应用与普及。

? 运筹学有广泛应用

运筹学不仅在军事上，而且在生产、决策、运输、存储等经济管理领域有着广泛的应用。

§1 决策、定量分析与管理运筹学

决策过程（问题解决的过程）： 1）认清问题；

2）找出一些可供选择的方案； 3）确定目标或评估方案的标准；

4）评估各个方案：解的检验、灵敏性分析等； 5）选出一个最优的方案：决策； 6）执行此方案：回到实践中；

7）进行后评估：考察问题是否得到完满解决；

1）2）3）：形成问题；

4）5）：分析问题：定性分析与定量分析。构成决策。

§2 运筹学的分支

???????

线性规划 整数线性规划 动态规划

图与网络模型 排队论

排序与统筹方法 决策分析

3

?对策论 ?非线形规划 ?模糊数学

§3 运筹学在工商管理中的应用

? 生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等，追求利润最大化和成本最小化

? 库存管理：多种物资库存量的管理，库存方式、库存量等运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等

人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等 市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等 财务和会计：预测、贷款、成本分析、定价、证券管理、现金管理等

*** 设备维修、更新，项目选择、评价，工程优化设计与管理等

? 由国际运筹与管理科学协会（INFORMS）和它的管理科学实践学会（College for the Practice of the Management Sciences）主持评奖的负有盛名的弗兰茨·厄德曼（Frany Edlman）奖，就是为奖励优秀的运筹学在管理中的应用的成就设立的，该奖每年举行一次，在对大量富有竞争力的入闱者进行艰苦的评审后，一般有六位优胜者获奖。关于这些获奖项目的文章都在第二年发表在著名刊物Interface的第一期上，下面列表就是发表在Interface期刊的一些获奖项目。

组织 联合航空公司 Citgo石油 荷马特发展公司 AT&T 标准品牌公司 施乐公司 宝洁公司 法国国家铁路 Delta航空公司 IBM 应用 满足乘客需求前提下,以最低成本进行订票及安排机场工作班次 优化炼油程序及产品供应、配送及营销 优化商业区和办公楼销售程序 优化商业用户的电话销售中心选址 控制成品库存（制定最优再订购点和订购量，确保安全库存） 通过战略调整，缩短维修机器的反应时间和改进维修人员的生产率 重新设计北美生产和分销系统以降低成本并加快了市场进入速度 制定最优铁路时刻表并调整铁路日运营量 进行上千个国内航线的飞机优化配置来最大化利润 重组全球供应链，保持最小库存的同时满足客户需求 Interface 每年节支（美元） 期刊号 1-2/1986 600万 1-2/1987 1-2/1987 1-2/1990 12/1981 11/1975第二部分 1-2/1997 1-2/1998 1-2/1994 1-2/20001 7000万 4000万 4.06亿 ，更多销售 380万 生产率提高50%以上 2亿 1500万更多年收入 1亿 第一年7.5亿 更优的服务 Merit青铜制品公司 安装统计销售预测和成品库存管理系统，改进客户服务 11-2/1993

4

运筹学方法使用情况(美1983)

运筹学方法在中国使用情况(随机抽样)

5

§4 学习管理运筹学必须使用相应的计算机软件，必须注重于学以致用的原则

? 学习运筹学要结合实际的应用，不要被一些概念、理论的困难吓倒。

? 学习运筹学要把注意力放在“结合实际问题建立运筹学模型”和“解决问题的方案或模型的解”两头，中间的计算过程尽可能让计算机软件去完成。

? 本书附有运筹学教学软件，使用方法很简单。学员必须尽快学会使用这个运筹学教学软件，并借助它来学好本课程。学习运筹学是为了用于实践，解决实际问题。以前重视人工计算是因为没有计算机，现在有了就应该好好利用。

§4 学习管理运筹学必须使用相应的计算机软件，必须注重于学以致用的原则

? 例如，有人要从北京去乌鲁木齐。在一百多年以前，我们应该告诉他如何配备粮草、银两、衣物，如何选购马匹、马车，挑选马夫和保镖，如何根据天气、地理条件和社会诸因素来确定行车路线和行程，更重要的是如何在几个月的行程中处理吃穿住行，应付突发事件等问题；但是现在我们只需告诉他如何去北京飞机场，如何在乌鲁木齐下飞机后提取行李和坐车就可以了，其余的问题交给航空公司和机组人员就行了。完全没有必要为了一次旅行攻读空气动力学、喷气发动机设计和制造、飞行器驾驶手册等厚厚的教科书。

? ―他山之石，可以攻玉‖。本书配套的计算机软件如同上例中的―飞机‖，它可以为你节省出大量的时间和精力用在问题建模，以及解决方案的分析和完善上。

6

第二章 线性规划的图解法

?§1 问题的提出

?§2 图解法

?§3 图解法的灵敏度分析

在管理中一些典型的线性规划应用

? 合理利用线材问题：如何在保证生产的条件下，下料最少 ? 配料问题：在原料供应量的限制下如何获取最大利润 ? 投资问题：从投资项目中选取方案，使投资回报最大

? 产品生产计划：合理利用人力、物力、财力等，使获利最大 ? 劳动力安排：用最少的劳动力来满足工作的需要 ? 运输问题：如何制定调运方案，使总运费最小 线性规划的组成：

?目标函数 Max F 或 Min F

?约束条件 s.t. (subject to) 满足于

?决策变量 用符号来表示可控制的因素

§1 问题的提出

例1.

某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：

问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？ 线性规划模型：

目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 ≤ 300 2 x1 + x2 ≤ 400 x2 ≤ 250

x1 , x2 ≥ 0

? 建模过程

1.理解要解决的问题，了解解题的目标和条件；

2.定义决策变量（ x1 ，x2 ，… ，xn ），每一组值表示一个方案；

3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标； 4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件

7

? 一般形式

目标函数： Max （Min） z = c1 x1 + c2 x2 + … + cn xn

约束条件： s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1 a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2 …… ……

am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0

对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。 下面通过例1详细讲解其方法：

例1.目标函数：

Max z = 50 x1 + 100 x2 约束条件：

s.t. x1 + x2 ≤ 300 (A) 2 x1 + x2 ≤ 400 (B) x2 ≤ 250 (C) x1 ≥ 0 (D) x2 ≥ 0 (E) 得到最优解：

x1 = 50， x2 = 250 最优目标值 z = 27500

(1) 分别取决策变量X1 , X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。

8

（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。

（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。

（4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为―等值线‖。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。

9

? 线性规划的标准化内容之一：——引入松驰变量（含义是资源的剩余量） 例1 中引入 s1， s2， s3 模型化为

目标函数：Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3 约束条件：s.t. x1 + x2 + s1 = 300 2 x1 + x2 + s2 = 400 x2 + s3 = 250

x1 , x2 , s1 , s2 , s3 ≥ 0 对于最优解 x1 =50 x2 = 250 ， s1 = 0 s2 =50 s3 = 0 说明：生产50单位Ⅰ产品和250单位Ⅱ产品将消耗完所有 可能的设备台时数及原料B，但对原料A则还剩余50千克。

? 重要结论：

– 如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；

– 无穷多个最优解。若将例1 中的目标函数变为max z=50x1+50x2， 则线段BC 上的所有

点都代表了最优解；

– 无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；

– 无可行解。若在例1 的数学模型中再增加一个约束条件

4x1+3x2≥1200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。

– 进 一 步 讨 论

例2 某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？

解：目标函数： Min f = 2x1 + 3 x2 约束条件：

s.t. x1 + x2 ≥ 350

x1 ≥ 125 2 x1 + x2 ≤ 600 x1 , x2 ≥ 0

采用图解法。如下图：得Q点坐标（250，100）为最优解。

10

§3 图解法的灵敏度分析

线性规划的标准化

? 一般形式

目标函数： Max （Min） z = c1 x1 + c2 x2 + … + cn xn

约束条件： s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1 a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2 …… ……

am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0 ? 标准形式

目标函数： Max z = c1 x1 + c2 x2 + … + cn xn

约束条件： s.t. a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a 22 x 2 + … + a……

2n xn …… = b 2 am1 x1 + am2 x2 + … + amn xn = bm x1 ，x2 ，… ，xn ≥ 0，bi ≥0

可以看出，线性规划的标准形式有如下四个特点：

– 目标最大化； – 约束为等式； – 决策变量均非负； – 右端项非负。

对于各种非标准形式的线性规划问题，我们总可

以通过以下变换，将其转化为标准形式: 1.极小化目标函数的问题： 设目标函数为

Min f = c1x1 + c2x2 + … + cnxn (可以)令 z ＝ -f ，

则该极小化问题与下面的极大化问题有相同的最优解， 即 Max z = - c1x1 - c2x2 - … - cnxn

但必须注意，尽管以上两个问题的最优解相同，但它们 最优解的目标函数值却相差一个符号，即 Min f ＝ - Max z 2、约束条件不是等式的问题： 设约束条件为

ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引进一个新的变量s ，使它等于约束右边与左边之差 s=bi–(ai1 x1 + ai2 x2 + … + ain xn ) 显然，s 也具有非负约束，即s≥0，

11

这时新的约束条件成为

ai1 x1+ai2 x2+ … +ain xn+s = bi 当约束条件为

ai1 x1+ai2 x2+ … +ain xn ≥ bi 时， 类似地令

s=(ai1 x1+ai2 x2+ … +ain xn)- bi

显然，s 也具有非负约束，即s≥0，这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn-s = bi 为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于”时称为―松弛变量‖；当不等式为“大于等于”时称为―剩余变量‖。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。

例：将以下线性规划问题转化为标准形式 Min f = 2 x1 -3x2 + 4 x3 s.t. 3 x1 + 4x2 - 5 x3 ≤6

2 x1 + x3 ≥8 x1 + x2 + x3 = -9 x1 , x2 , x3 ≥ 0

解：首先,将目标函数转换成极大化： 令 z= -f = -2x1+3x2-4x3

其次考虑约束，有2个不等式约束，引进松弛变量 x4，x5 ≥0。

第三个约束条件的右端值为负，在等式两边同时乘-1。

通过以上变换，可以得到以下标准形式的线性规划问题： Max z = - 2x1 + 3 x2 - 4x3 s.t. 3x1+4x2-5x3 +x4 = 6 2x1 +x3 -x5= 8 -x1 -x2 -x3 = 9 x1 ,x2 ,x3 ,x4 ,x5 ≥ 0 *** 变量无符号限制的问题***：

在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没 有非负约束时，可以令 xj = xj’- xj” 其中

xj’≥0，xj”≥0

即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj’和xj”的大小。

12

§3 图解法的灵敏度分析

灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）

ci , aij , bj 变化时，对最优解产生的影响。 3.1 目标函数中的系数 ci 的灵敏度分析

考虑例1的情况， ci 的变化只影响目标函数等值线的斜率，目标函数 z = 50 x1 + 100 x2

原 在 z = x2 (x2 = z 斜率为0 ) 到 z = x1 + x2 (x2 = -x1 + z 斜率为 -1 )之间时，

最优解 x1 = 50，x2 = 100 仍是最优解。 ? 一般情况：

z = c1 x1 + c2 x2 写成斜截式 x2 = - (c1 / c2 ) x1 + z / c2 目标函数等值线的斜率为 - (c1 / c2 ) ，

当 -1 ? - (c1 / c2 ) ? 0 （*） 时，原最优解仍是最优解。 ? 假设产品Ⅱ的利润100元不变，即 c2 = 100，代到式（*）并整理得 0 ? c1 ? 100

? 假设产品Ⅰ的利润 50 元不变，即 c1 = 50 ，代到式（*）并整理得 50 ? c2 ? + ? ? 假若产品Ⅰ、Ⅱ的利润均改变，则可直接用式（*）来判断。 ? 假设产品Ⅰ、Ⅱ的利润分别为60元、55元，则

- 2 ? - (60 / 55) ? - 1 那么，最优解为 z = x1 + x2 和 z = 2 x1 + x2 的交点 x1 = 100，x2 = 200 。

3.2 约束条件中右边系数 bj 的灵敏度分析

当约束条件中右边系数 bj 变化时，线性规划的可行域发生 变化，可能引起最优解的变化。 考虑例1的情况：

假设设备台时增加10个台时，即 b1变化为310，这时可行

域扩大，最优解为 x2 = 250 和 x1 + x2 = 310 的交点 x1 = 60，x2 = 250 。 变化后的总利润 - 变化前的总利润 = 增加的利润

(50×60+ 100×250) - (50 × 50+100 × 250) = 500 ，500 / 10 = 50 元

说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。

假设原料 A 增加10 千克时，即 b2变化为410，这时可行域扩大，但最优解仍为 x2

= 250 和 x1 + x2 = 300 的交点 x1 = 50，x2 = 250 。此变化对总利润无影响，该约束条件的对偶价格为 0 。 解释：原最优解没有把原料 A 用尽，有50千克的剩余，因此增加10千克值增加了库存，而不会增加利润。

在一定范围内，当约束条件右边常数增加1个单位时

（1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）； （2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）； （3）若约束条件的对偶价格等于0，则最优目标函数值不变。

13

第三章 线性规划问题的计算机求解

§1 “管理运筹学”软件的操作方法 §2 “管理运筹学”软件的输出信息分析

随书软件为―管理运筹学‖2.0版（Window版），是1.0版（DOS版）的升级版。它包括：线性规划、运输问题、整数规划（0-1整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法，共15个子模块。

§1 “管理运筹学”软件的操作方法

1.软件使用演示：（演示例1）

第一步：点击“开始”->“程序”-> “管理运筹学 2.0”，弹出主窗口。

例1.目标函数：

Max z = 50 x1 + 100 x2 约束条件： s.t.

x1 + x2 ≤ 300 (A) 2 x1 + x2 ≤ 400 (B) x2 ≤ 250 (C) x1 ≥ 0 (D) x2 ≥ 0 (E)

第二步：选择所需子模块，点击主窗口中的相应按钮。本题中选用“线性规划”方 法。点击按钮弹出如下界面：

14

第三步：点击“新建”按钮，输入数据。本题中共有2个变量，4个约束条件，目标函 数取MAX。点击“确定”后，在表中输入Cj,bi和aij等值，并确定变量的正负约束。 输入数值后的界面如下。

第四步：点击“解决”按钮，得出计算结果。本题的运行结果界面如下。

15

第五步：分析运行结果。

– 本题中目标函数的最优值是27500，x1=50, x2=250。

– 相差值表示相应的决策变量的目标系数需要改进的数量，使得决策变量为正值，当决策变量已为正数时，相差数为零。

– 松弛/剩余变量的数值表示还有多少资源没有被使用。如果为零，则表示与之相对应的资源已经全部用上。

– 对偶价格表示其对应的资源每增加一个单位，将增加多少个单位的最优值。

– 目标函数系数范围表示最优解不变的情况下，目标函数的决策变量系数的变化范围。当前值是指当前的最优解中的系数取值。 – 常数项范围是指约束条件的右端常量。上限值和下限值是指当约束条件的右端常量在此范围内变化时，与其对应的约束条件的对偶价格不变。当前值是指现在的取值。

以上计算机输出的目标函数系数和约束条件右边值的灵敏度分析都是在其他系数值不变，只有一个系数变化的基础上得出的！ 2.当有多个系数变化时，需要进一步讨论。

百分之一百法则：对于所有变化的目标函数决策系数（约束条件右边常数值），当其所有允许增加的百分比与允许减少的百分比之和不超过100%时，最优解不变（对偶价格不变，最优解仍是原 来几个线性方程的解）。

* 允许增加量 = 上限 - 现在值 c1 的允许增加量为 100 - 50 = 50 b1 的允许增加量为 325 - 300 = 25 * 允许减少量 = 现在值 - 下限 c2 的允许减少量为 100 - 50 = 50 b3 的允许减少量为 250 - 200 = 50

* 允许增加的百分比 = 增加量 / 允许增加量 * 允许减少的百分比 = 减少量 / 允许减少量

例： c1 变为 74 , c2 变为 78, 则 (74 - 50) / 50 + (100 - 78 ) / 50 = 92%，故最优解不变。 b1 变为 315 , b3 变为 240, 则 (315 - 50) / 25 + (250 - 240 ) / 50 = 80%，故对偶价格不变（最优解仍是原来几个线性方程的解）。

在使用百分之一百法则进行灵敏度分析时，要注意：

1）当允许增加量（允许减少量）为无穷大时，则对任意增加量（减少量），其允许增加（减少）百分比均看作0；

2）百分之一百法则是充分条件，但非必要条件；也就是说超过100%并不一定变化；

3）百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变化的情况。这种情况下，只有重新求解。

? 下面用―管理运筹学‖软件来分析第二章的例2，其数学模型如下：

目标函数：

Min f = 2x1 + 3 x2 约束条件：

s.t. x1 + x2 ≥ 350 x1 ≥ 125 2 x1 + x2 ≤ 600 x1 , x2 ≥ 0

16

从上图可知，当购进原材料A 250t，原料B 100t时，购进成本最低，为800万元。

? 在松弛/剩余变量栏中，约束条件2的值为125，它表示对原料A的最低需求，即对A的剩余变量值为125；同理可知约束条件1的剩余变量值为0；约束条件3的松弛变量值为0。

? 在对偶价格栏中，约束条件3的对偶价格为1万元，也就是说如果把加工时数从600小时增加到601小时，则总成本将得到改进，由800万减少到799万。也可知约束条件1的对偶条件为-4万元，也就是说如果把购进原料A的下限从125t增加到126t，那么总成本将加大，由800万增加到804万。当然如果减少对原料A的下限，那么总成本将得到改进。

? 在常数项范围一栏中，知道当约束条件1的常数项在300—475范围内变化，且其他约束条件不变时，约束条件1的对偶价格不变；当约束条件2的常数项在负无穷到250范围内变化，而其他约束条件的常数项不变时，约束条件2的对偶价格不变，仍为0；当约束条件3的常数项在475—700内变化，而其他约束条件的常数项不变时，约束条件3的对偶价格不变，仍为1。

? 注意：

?

当约束条件中的常数项增加一个单位时，最优目标函数值增加的数量称之为影子价格。在求目标函数最大时，当约束条件中的常数项增加一个单位时，目标函数值增加的数量就为改进的数量，所以影子价格等于对偶价格；在求目标函数值最小时，改进的数量就是减少的数量，所以影子价格即为负的对偶价格。

―管理运筹学‖软件可以解决含有100个变量50个约束方程的线性规划问题，可以解决工商管理中大量的问题。如果想要解决更大的线性规划问题，可以使用由芝加哥大学的L.E.Schrage开发的Lindo计算机软件包的微型计算机版本Lindo/PC。

?

17

第四章 线性规划在工商管理中的应用

?????

§1人力资源分配的问题； §2生产计划的问题； §3套裁下料问题； §4配料问题； §5投资问题。

§1人力资源分配的问题

例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：

设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?

解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 + x6

约束条件：s.t. x1 + x6 ≥ 60 x1 + x2 ≥ 70 x2 + x3 ≥ 60 x3 + x4 ≥ 50 x4 + x5 ≥ 20 x5 + x6 ≥ 30 x1,x2,x3,x4,x5,x6 ≥ 0

例2．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？ 解：设 xi ( i = 1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。

18

目标函数： Min x1 + x2 + x3 + x4 + x5 + x6 + x7 约束条件：s.t. x1 + x2 + x3 + x4 + x5 ≥ 28 x2 + x3 + x4 + x5 + x6 ≥ 15 x3 + x4 + x5 + x6 + x7 ≥ 24 x4 + x5 + x6 + x7 + x1 ≥ 25 x5 + x6 + x7 + x1 + x2 ≥ 19 x6 + x7 + x1 + x2 + x3 ≥ 31 x7 + x1 + x2 + x3 + x4 ≥ 28 x1,x2,x3,x4,x5,x6,x7 ≥ 0

§2生产计划的问题

例3．某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？

解：设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5 分别为由外协铸

造再由本公司加工和装配的甲、乙两种产品的件数。 求 xi 的利润：利润 = 售价 - 各成本之和

产品甲全部自制的利润 =23-(3+2+3)=15 产品甲铸造外协，其余自制的利润 =23-(5+2+3)=13 产品乙全部自制的利润 =18-(5+1+2)=10 产品乙铸造外协，其余自制的利润 =18-(6+1+2)=9 产品丙的利润 =16-(4+3+2)=7

可得到 xi （i = 1,2,3,4,5） 的利润分别为 15、10、7、13、9 元。

通过以上分析,可建立如下的数学模型:

目标函数： Max 15x1 + 10x2 + 7x3 + 13x4 + 9x5 约束条件： 5x1 + 10x2 + 7x3 ≤ 8000

6x1 + 4x2 + 8x3 + 6x4 + 4x5 ≤ 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 ≤ 10000 x1,x2,x3,x4,x5 ≥ 0

19

§2生产计划的问题

例4．永久机械厂生产Ⅰ、Ⅱ、Ⅲ三种产品，均要经过A、B两

道工序加工。设有两种规格的设备A1、A2能完成 A 工序；有三种规格的设备B1、B2、B3能完成 B 工序。Ⅰ可在A、B的任何规格的设备上加工；Ⅱ 可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；Ⅲ只能在A2与B2设备上加工。数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？

解：设 xijk 表示第 i 种产品，在第 j 种工序上的第 k 种设备上加工的数量。建立如下的数学模型: s.t. 5x111 + 10x211 ≤ 6000 （ 设备 A1 ） 7x112 + 9x212 + 12x312 ≤ 10000 （ 设备 A2 ） 6x121 + 8x221 ≤ 4000 （ 设备 B1 ） 4x122 + 11x322 ≤ 7000 （ 设备 B2 ） 7x123 ≤ 4000 （ 设备 B3 ）

x111+ x112- x121- x122- x123 = 0 （Ⅰ产品在A、B工序加工的数量相等） x211+ x212- x221 = 0 （Ⅱ产品在A、B工序加工的数量相等） x312 - x322 = 0 （Ⅲ产品在A、B工序加工的数量相等） xijk ≥ 0 , i = 1,2,3; j = 1,2; k = 1,2,3

目标函数为计算利润最大化，利润的计算公式为：

利润 = [（销售单价 - 原料单价）* 产品件数]之和 -（每台时的设备费用*设备实际使用的总台时数）之和。 这样得到目标函数：

Max(1.25-0.25)(x111+x112)+(2-0.35)x221+(2.80-0.5)x312 –

300/6000(5x111+10x211)-321/10000(7x112+9x212+12x312)-

250/4000(6x121+8x221)-783/7000(4x122+11x322)-200/4000(7x123).

经整理可得：

Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123

§3套裁下料问题

例5．某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？ 解： 共可设计下列5 种下料方案，见左表：

? ? ?

20

? 用―管理运筹学‖软件计算得出最优下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。 即 x1=30; x2=10； x3=0； x4=50； x5=0；

只需90根原材料就可制造出100套钢架。

? 注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。

§4配料问题

例6．某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如右表。问：该厂应如何安排生产，使利润收入为最大？

解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学模型时，要考虑： 对于甲： x11，x12，x13； 对于乙： x21，x22，x23； 对于丙： x31，x32，x33； 对于原料1： x11，x21，x31； 对于原料2： x12，x22，x32； 对于原料3： x13，x23，x33；

目标函数： 利润最大，利润 = 收入 - 原料支出 约束条件： 规格要求 4 个； 供应量限制 3 个。

从第2个表中，生产甲乙丙的原材料不能超过原材料的供应限额，故有

(x11+x21+x31)≤100 (x12+x22+x32)≤100 (x13+x23+x33)≤60

通过整理，得到以下模型：

目标函数：Max z = -15x11+25x12+15x13-30x21+10x22-40x31-10x33 约束条件：

s.t. 0.5 x11-0.5 x12 -0.5 x13 ≥ 0 （原材料1不少于50%） -0.25x11+0.75x12 -0.25x13 ≤ 0 （原材料2不超过25%） 0.75x21-0.25x22 -0.25x23 ≥ 0 （原材料1不少于25%） -0.5 x21+0.5 x22 -0.5 x23 ≤ 0 （原材料2不超过50%） x11+ x21 + x31 ≤ 100 (供应量限制） x12+ x22 + x32 ≤ 100 (供应量限制） x13+ x23 + x33 ≤ 60 (供应量限制） xij ≥ 0 , i = 1,2,3; j = 1,2,3

21

例7.汽油混合问题。一种汽油的特性可用两种指标描述，用“辛烷数”来定量描述其点火特性，用“蒸汽压力”来定量描述其挥发性。某炼油厂有1、2、3、4种标准汽油，其特性和库存量列于表4-6中，将这四种标准汽油混合，可得到标号为1，2的两种飞机汽油，这两种汽油的性能指标及产量需求列于表4-7中。问应如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标，又使2号汽油满足需求，并使得1号汽油产量最高？

解：设xij为飞机汽油i中所用标准汽油j的数量(L)。 目标函数为飞机汽油1的总产量： 库存量约束为：

产量约束为飞机汽油2的产量：

?x21?x22?x23?x24?250000由物理中的分压定律， n 可得有关蒸汽压力的约束条件：

PV?pjvj

j?1

2.85x11?1.42x12?4.27x13?18.49x14?02.85x21?1.42x22?4.27x23?18.49x24?0同样可得有关辛烷数的约束条件为：

16.5x11?2.0x12?4.0x13?17.0x14?07.5x11?7.0x12?13.0x13?8.0x14?0maxx11?x12?x13?x14?x21?x22?x23?x24?250000?x?x?380000?1121?x12?x22?265200??408100?x13?x23?x?x?130100?1424??2.85x11?1.42x12?4.27x13?18.49x14?0?2.85x21?1.42x22?4.27x23?18.49x24?0??16.5x11?2x12?4x13?17x14?0?7.5x?7x?13x?8x?021222324???xij?0,(i?1,2;j?1,2,3,4) 22

由管理运筹学软件求解得：

max(x11?x12?x13?x14)?933399.938x11?261966.078x12?265200x13?315672.219x14?90561.688x21?118033.906x22?0x23?92427.758x24?39538.309§5投资问题

例8．某部门现有资金200万元，今后五年内考虑给

项目 风险指数（次/万元） 以下的项目投资。已知：项目A：从第一年到第五年

A 1 每年年初都可投资，当年末能收回本利110%；项目

B 3 B：从第一年到第四年每年年初都可投资，次年末能

C 4 收回本利125%，但规定每年最大投资额

D 5.5 不能超过30万元；项目C：需在第三年年初投资，

第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五 年末能收回本利155%，但规定最大投资额不能超过100万元。

据测定每万元每次投资的风险指数如右表： 问：

a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？ b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？

2）约束条件：

第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是 x11+ x12 = 200； 第二年：B次年末才可收回投资，故第二年年初有资金1.1 x11，于是 x21 + x22+ x24 = 1.1x11； 第三年：年初有资金 1.1x21+ 1.25x12，于是 x31 + x32+ x33 = 1.1x21+ 1.25x12； 第四年：年初有资金 1.1x31+ 1.25x22，于是 x41 + x42 = 1.1x31+ 1.25x22； 第五年：年初有资金 1.1x41+ 1.25x32，于是 x51 = 1.1x41+ 1.25x32；

B、C、D的投资限制： xi2 ≤ 30 ( i =1、2、3、4 )，x33 ≤ 80，x24 ≤ 100 3）目标函数及模型：

a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24 s.t. x11+ x12 = 200

x21 + x22+ x24 = 1.1x11；

x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32；

23

xi2 ≤ 30 ( i =1、2、3、4 )，x33 ≤ 80，x24 ≤ 100 xij ≥ 0 ( i = 1、2、3、4、5；j = 1、2、3、4） b)所设变量与问题a相同，目标函数为风险最小，有 Min f =x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24

在问题a的约束条件中加上―第五年末拥有资金本利在330万元‖的条件，于是模型如下： Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24 s.t. x11+ x12 = 200

x21 + x22+ x24 = 1.1x11；

x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32；

xi2 ≤ 30 ( i =1、2、3、4 )，x33 ≤ 80，x24 ≤ 100 1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 ≥ 330

xij ≥ 0 ( i = 1、2、3、4、5；j = 1、2、3、4）

24

第五章 单 纯 形 法

? §1 单纯形法的基本思路和原理 ? §2 单纯形法的表格形式

? §3 求目标函数值最小的线性规划的问题的单纯形表解法 ? §4 几种特殊情况

§1 单纯形法的基本思路和原理

一．单纯形法的基本思路：

从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。 通过第二章例1的求解来介绍单纯形法: 在加上松弛变量之后我们可得到标准型如下： 目标函数： max 50x1+100x2 约束条件：x1+x2+s1≤300， 2x1+x2+s2≤400， x2+s3≤250.

xj≥0 （j=1，2）,sj≥0 （j=1，2,3）

它的系数矩阵 ,

其中pj为系数矩阵A第j列的向量。A的秩为3,A的秩m小于此方程组的变量的个数n，为了找到一个初始基本可行解，先介绍以下几个线性规划的基本概念。

基： 已知A是约束条件的m×n系数矩阵，其秩为m。若B是A中m×m阶非 奇异子矩阵（即可逆矩阵），则称B是线性规划问题中的一个基。 基向量：基B中的一列即称为一个基向量。基B中共有m个基向量。 非基向量：在A中除了基B之外的一列则称之为基B的非基向量。 基变量：与基向量pi相应的变量xi叫基变量，基变量有m个。

非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有n－m个。

由线性代数的知识知道，如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基

110???变量为零，再求解这个mB??元线性方程组就可得到唯一的解了，这个解我们称之为线性规划的基100???101?本解。 ??在此例中我们不妨找到了 为A的一个基，令这个基的非基变量x１，s2为零。

这时约束方程就变为基变量的约束方程：

x2+s1≤300， x2=400， x2+s3=250.

3 25

jj 求解得到此线性规划的一个基本解： x1=0，x2=400，s1=－100，s2=0，s3=－150

由于在这个基本解中s1=－100，s3=－150，不满足该线性规划??s1≥0，s3≥0的约束条件，显然不是此线性规划的可行解，一个基本解可以是可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解 是否满足非负的条件。我们把满足非负条件的一个基本解叫做基本可行解，并把这样的基叫做可行基。

一般来说判断一个基是否是可行基，只有在求出其基本解以后，当其基本解所有变量的解都是大于等于零，才能断定这个解是基本可行解，这个基是可行基。那么我们能否在求解之前，就找到一个可行基呢？也就是说我们找到的一个基能保证在求解之后得到的解一定是基本可行解呢？由于在线性规划的标准型中要求bj都大于等于零，如果我们能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺序是无关紧要的事）例如， ?001????100? ??

?010?那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。

实际上这个基本可行解中的各个变量或等于某个bj或等于零。

在本例题中我们就找到了一个基是单位矩阵。

?100?

?? B2??010? ?001???

在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基，

其相应的基本可行解叫初始基本可行解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，我们将构造初始可行基，具体做法在以后详细讲述。

二、 最优性检验

所谓最优性检验就是判断已求得的基本可行解是否是最优解。

1. 最优性检验的依据——检验数σj

一般来说目标函数中既包括基变量，又包括非基变量。现在我们要求只用非基变量来表示目标函数，这只要在约束等式中通过移项等处理就可以用非基变量来表示基变量，然后用非基变量的表示式代替目标函数中基变量，这样目标函数中只含有非基变量了，或者说目标函数中基变量的系数都为零了。此时目标函数中所有变量的系数即为各变量的检验数，把变量xi的检验数记为σi。显然所有基变量的检验数必为零。在本例题中目标函数为50x1+100x2。由于初始可行解中x1，x2为非基变量，所以此目标函数已经用非基变量表示了，不需要再代换出基变量了。这样我们可知σ1=50，σ2=100，σ3=0，σ4=0，σ5=0。

? 2.最优解判别定理

对于求最大目标函数的问题中，对于某个基本可行解，如果所有检验数 ? j ≤0，则这个基本

可行解是最优解。下面我们用通俗的说法来解释最优解判别定理。设用非基变量表示的目标函数为如下形式

z?z0???jxjj?J由于所有的xj的取值范围为大于等于零，当所有的 ? j都小 于等于零时，可知是一个小于等于

零的数，要使z的值最大，显然只有为零。我们把这些xj取为非基变量(即令这些xj的值为零)，所求得的基本可行解就使目标函数值最大为z0。

≥0. **对于求目标函数最小值的情况，只需把 ≤0改为

26

三、 基变换

通过检验，我们知道这个初始基本可行解不是最优解。下面介绍如何进行基变换找到一个新的可行基，

具体的做法是从可行基中换一个列向量，得到一个新的可行基，使得求解得到的新的基本可行解，其目标函数值更优。

为了换基就要确定换入变量与换出变量。 1. 入基变量的确定

从最优解判别定理知道，当某个σj＞0时，非基变量xj变为基变量不取零值可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基变量中去（称之为入基变量）。若有两个以上的σj＞0，则为了使目标函数增加得更大些，一般选其中的σj最大者的非基变量为入基变量，在本例题中σ2=100是检验数中最大的正数，故选x2为入基变量。

2. 出基变量的确定

在确定了x2为入基变量之后，我们要在原来的3个基变量s1，s2，s3中确定一个出基变量，也就是确定哪一个基变量变成非基变量呢？

如果把s3作为出基变量，则新的基变量为x2，s1，s2，因为非基变量x1=s3=0， 我们也可以从下式：

x2 +s1=300， x2+s2=400， x2=250，

求出基本解：x1=0，x2=250，s1=50，s2=150，s3=0。因为此解满足非负条件，是基本可行解，故s3可以确定为出基变量。

能否在求出基本解以前来确定出基变量呢？

以下就来看在找出了初始基本可行解和确定了入基变量之后，怎么样的基变量可以确定为出基变量呢？或者说出基变量要具有什么条件呢？

我们把确定出基变量的方法概括如下：把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的bj值都大于等于零。

x1?x2?s1?300, 在本例题中约束方程为

2x1?x2?s2?400,

x2?s3?250.

在第二步中已经知道x2为入基变量，我们把各约束方程中x2的为正的系数除对应的常量，得

b1300??300,a121b2400??400,a221b3250??250.a321 Tbe3? 其中 3 的值最小，所以可以知道在原基变量中系数向量为 ? 0,0,1 ?

a32

的基变量s3为出基变量，这样可知x2，s1，s2为基变量，x1，s3为非基变量。 令非基变量为零，得 x2+s1=300, x2+s2=400, x2=250.

求解得到新的基本可行解x1=0,x2=250,s1=50,s2=150.

这时目标函数值为 50x1+100x2=50×0+100×250=25000

显然比初始基本可行解x1=0,x2=0,s1=300,s3=250时的目标函数值为0要好得多。

下面我们再进行检验其最优性，如果不是最优解还要继续进行基变换，直至找到最优解，或者能够判断出线性规划无最优解为止。

27

§2 单纯形法的表格形式

在讲解单纯形法的表格形式之前，先从一般数学模型里推导出检验数 σj的表达式。 可行基为m阶单位矩阵的线性规划模型如下（假设其系数矩阵的前m列是单位矩阵）：

maxz?c1x1?c2x2???cnxn.x1?a1,m?1xm?1???a1,nxn?b1,x2?a2,m?1xm?1???a2,nxn?b2,????????????xm?am,m?1xm?1???am,nxn?bm,?j?1,2,?,n?x?j?m?1,m?2,?,n?, m? i ? 1, 以下用 x 2, ? ? 表示基变量，用 j 表示非基变量。

xj?0.i

把第i个约束方程移项，就可以用非基变量来表示基变量xi，

xi?bi?ai,m?1xm?1?ai,m?2xm?2???ai,nxn?bi?j?m?1?naijxj.?i?1,2,?,m?m 把以上的表达式带入目标函数，就有

z?c1x1?c2x2???cnxn??cixi?i?1j?m?1?cxjnj?z0? 其中：

j?m?1??cnj?zj?xj?z0?j?m?1??njxj?a1j???ma2j??zj??ciaij?c1a1j?c2a2j???cmamj??c1,c2,?,cm????i?1??a???mj???c1,c2,?,cm?pj 上面假设x1,x2,…xm是基变量，即第i行约束方程的基变量正好是xi，而经过迭代后，基将发生变化，计算zj

的式子也会发生变化。如果迭代后的第i行约束方程中的基变量为xBi，与xBi相应的目标函数系数为cBi，系数列 向量为 p 1, 2, ? , n 则 ?j ? j ?zj??cB1,?,cBm?p?j??cB?p?j,?

其中，(cB)是由第1列第m行各约束方程中的基变量相应的目标函数依次组成的有序行向量。

单纯形法的表格形式是把用单纯形法求出基本可行解、检验其最优性、迭代某步骤都用表格的方式来计算求出，其表格的形式有些像增广矩阵，

而其计算的方法也大体上使用矩阵的行的初等变换。以下用单纯形表格来求解第二章的例1。

max 50x1+100x2+0·s1+0·s2+0·s3.

x1+x2+s1=300， 2x1+x2+s2=400， x2+s3=250，

28

x1, x2, s1, s2, s3≥0. 把上面的数据填入如下的单纯形表格 ? 按照线性规划模型在表中填入相对应的值，如上表所示；

? ? ? ? ? ? ?

在上表中有一个m*m的单位矩阵，对应的基变量为s1,s2,s3；

在zj行中填入第j列与cB列中对应的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0，所在zi行中的第2位数填入0；

? z在 ? j ? c j j 行中填入cj-zj所得的值，如 ；

z表示把初始基本可行解代入目标函数求得的目标函数值，即b列*cB列； 初始基本可行解为s1=300,s2=400,s3=250,x1=0,x2=0; 由于250/1最小，因此确定s3为出基变量； 由于 ? 2 ? ? 1 ? 0 ，因此确定x2为入基变量。出基变量所在行，入基变量所在列的交汇处为主元，这里是a32=1，在表中画圈以示区别。

? 以下进行第一次迭代，其变量为x2,s1,s2,通过矩阵行的初等变换，求出一个新的基本可行解，具体的做法用行的

T初等变换使得x2的系数向量p2变换成单位向量，由于主元在p2的第3 分量上，所以这个单位向量是e 3 ??0,0,1? 也就是主元素变成1。这样我们又得到的第1次迭代的单纯表如下所示。

? 在上表中第3个基变量s1已被x2代替，故基变量列中的第3个基变量应变为x2。由于第0次迭代表中的主元a32已经为1，因此第3行不变。为了使第1行的a12为0，只需把第3行*(-1)加到第1行即可。同样可以求得第2行。 ? 求得第1次迭代的基本可行解为s1=50,s2=150,x2=250,x1=0,s3=0,z=25000. ? 从上表可以看出，第一次迭代的 ? ? 50 ? 0 ，因此不是最优解。设x1为入基变量，从此值可知b1/a11=50

1为最小正数，因此，s1为出基变量，a11为主元，继续迭代如下表所示。

? 从上表中可知第二次迭代得到的基本可行解为x1=50,x2=250,s1=0,s2=50, s3=0,这时z=27500。 ? 由于检验数都<0，因此所求得的基本可行解为最优解， z=27500为最优目标函数值。 ? 实际上，我们可以连续地使用一个单纯形表，不必一次迭代重画一个表头。

29

§3 求目标函数值最小的线性规划的问题的单纯形表解法

一、大M法

? 以第二章的例2来讲解如何用单纯形表的方法求解目标函数值最小的线性规划问题。 ? 目标函数： minf?2x?3x.12约束条件： x1?x2?350,

x1?125,2x1?x2?600,x1,x2?0.x1?x2?s1?350,x1?s2?125,2x1?x2?s3?600,x1,x2,s1,s2,s3?0.

? 加入松弛变量和剩余变量变为标准型，得到新的约束条件如下：

至于目标函数，在标准型中并不一定要求求最大值或最小值，但是为了使单纯形表解法有一个统一的解法，

我们把所有求目标函数最小值的问题化成求目标函数最大值的问题。具体做法只要把目标函数乘以（－1）。 要注意到人工变量是与松弛、剩余变量不同的。松弛变量、剩余变量它们可以取零值，也可以取正值，而人工变量只能取零值。一旦人工变量取正值，那么有人工变量的约束方程和原始的约束方程就不等价了，这样所 求得的解就不是原线性规划的解了。为了竭尽全力地要求人工变量为零，我们规定人工变量在目标函数中的系数为－M，这里M为任意大的数。这样只要人工变量M＞0，所求的目标函数最大值就是一个任意小的数。这样为了使目标函数实现最大就必须把人工变量从基变量中换出。如果一直到最后，人工变量仍不能从基变量中换出，也就是说人工变量仍不为零，则该问题无可行解。

此例的数学模型如下所示：

目标函数： max z=－2x1－3x2－Ma1－Ma2. 约束条件：x1+x2－s1+a1=350， x1－s2+a2=125， 2x1+x2+s3=600，

x1，x2，s1，s2，s3，a1，a2≥0.

像这样，为了构造初始可行基得到初始可行解，把人工变量“强行”地

加到原来的约束方程中去，又为了尽力地把人工变量从基变量中替换出来就令人工变量在求最大值的目标函数里的系数为

－M，这个方法叫做大M法，M叫做罚因子。

下面我们就用大M法来求解此题:

30

从上表中可知检验数都小于零。已求得最优解为：

x1=250,x2=100,s1=0, s2=125,s3=0,a1=0,a2=0，

其最优值为 f=-z=-(-800)=800。

二、两阶段法

两阶段法是处理人工变量的另一种方法，这种方法是将加入人工变量后的线性规划划分两阶段求解，

仍以上面的例题为例，阐述两阶段法的求解过程。

第一阶段：要判断原线性规划是否有基可行解，方法是先求解下列线性规划问题： 目标函数： maxz??a1?a2; 约束条件： x1?x2?s1?a1?350,

x1?s2?a2?125,2x1?x2?s3?600,x1,x2,s1,s2,s3,a1,a2?0.

注意：此线性规划的约束条件与原线性规划一样，而目标函数是求人工变量的相反数之和的最大

值。如果此值大于零，则不存在使所有人工变量都为零的可行解，停止计算。如果此值为零，即说明存在

31

一个可行解，使得所有的人工变量都为零。

第二阶段：将第一阶段的最终单纯形表中的人工变量取消，将目标函数换成原问题的目标函数，把此可行解作为初始可行解进行计算。

从表中可知其基本可行解x1=250,x2=100,s1=0,s2=125,s3=0是本例的最优解，其最优值为z=-(-800)=800。

32

§4 几种特殊情况

一、无可行解

例1、用单纯形表求解下列线性规划问题

目标函数maxz?20x1?30x2约束条件3x1?10x2?150,x1?30,x1?x2?40,x1,x2?0.

解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到：

目标函数maxz?20x1?30x2?Ma1约束条件3x1?10x2?s1?150,x1?s2?30,x1?x2?s3?a1?40,x1,x2,s1,s2,s3,a1?0.

填入单纯形表计算得：

从第二次迭代的检验数都小于零来看，可知第2次迭代所得的基本可行解已经是最优解了，其最大的目标函数值为780-4M。我们把最优解x1=30,x2=6,s1=0,s2=0,s3=0,a1=4,代入第三个约束方程得x1+x2-0+4=40,即有：x1+x2=36≤40. 并不满足原来的约束条件3，可知原线性规划问题无可行解，或者说其可行解域为空集，当然更不可能有最优解了。像这样只要求线性规划的最优解里有人工变量大于零，则此线性规划无可行解。

33

二、无界解

在求目标函数最大值的问题中，所谓无界解是指在约束条件下目标函数值可以取任意的大。下面我们用单纯形表来求第二章中的例子。

例2、用单纯形表求解下面线性规划问题。

目标函数maxz?x1?x2约束条件x1?x2?1,?3x1?2x2?6,x1,x2?0.目标函数maxz?x1?x2约束条件x1?x2?s1?1,?3x1?2x2?s2?6,x1,x2,s1,s2?0.解：在上述问题的约束条件中加入驰变量，得标准型如上： 填入单纯形表计算得：

从单纯形表中，从第一次迭代的检验数等于2，可知所得的基本可行解x1=1,x2=0,s1=0,s2=9不是最优解。同时我们也知道如果进行第2次迭代，那么就选x2为入基变量，但是在选择出基变量时遇到了问题： =-1, =-1,找不到大于零的 来确定出基变量。事实上如果我们碰到这种情况就可以断定这个线性规划问题是无界的，也就是说在此线性规划的约束条件下，此目标函数值可以取得无限大。从1次迭代的单纯形表中，得到约束方程：

x1?x2?s1?1,移项可得： x?1?x?s,121 ?x2?3s1?s2?9.s2?x2?3s1?9.

不妨设x2?M,s1?0,可得一组解：x1?M?1,x2?M,s1?0,s2?M?9.显然这是线性规划的可行解，此时目标函数z?x1?x2?M?1?M?2M?1.由于M可以是任意大的正数，可知此目标函数值无界。

上述的例子告诉了我们在单纯形表中识别线性规划问题是无界的方法：在某次迭代的单纯形表中，如果存在着一个大于零的检验数 ，并且该列的系数向量的每个元素aij(i=1,2,…,m)都小于或等于零，则此线性规划问题是无界的，一般地说此类问题的出现是由于建模的错误所引起的。

34

三、无穷多最优解

例3、用单纯形法表求解下面的线性规划问题。

目标函数maxz?50x1?50x2约束条件x1?x2?300,2x1?x2?400,x2?250,x1,x2?0.解：此题我们用图解法已求了解，现在用单纯形表来求解。

加入松弛变量s1,s2,s3，我们得到标准形：目标函数maxz?50x1?50x2约束条件x1?x2?s1?300,2x1?x2?s2?400,x2?s3?250,x1,x2,s1,s2,s3?0.填入单纯形表计算得：

这样我们求得了最优解为x1=50,x2=250,s1=0,s2=50,s3=0,此线性规划的最优值为15000。这个最优解是否是惟一的呢？由于在第2次迭代的检验数中除了基变量的检验数 ? 1 , ? 2 ,? 4 等于零外，非基变量s3的检验数也等于零，这样我们可以断定此线性规划问题有无穷多最优解。不妨我们把检验数也为零的非基变量选为入基变量进行第3次迭代。可求得另一个基本可行解，如下表所示：

35

从检验数可知此基本可行解x1=100,x2=200,s1=0,s2=0,s3=50,也是最优解，从图解法可知连接这两点的线段上的任一点都是此线性规划的最优解，不妨用向量Z1，Z2表示上述两个最优解即Z1 =（50，250，0，50，0）， Z2 =（100，200，0，0，50），则此线段上的任一点，即可表示为αZ1+（1- α ）Z2，其中0≤α≤1。如图5-1所示：

在一个已得到最优解的单纯形表中，如果存在一个非基变量的检验数为零，为什么我们把这个非基变量xs作为入基变量进行迭代时，得到的最优解仍为最优解呢？

不妨设出基变量为xk，则原最优单纯形表可表示如下：

xk?ckx1?xk?1xkxk?1?xmc1?ck?1?ck?cm??ck?1??0?010?00????xscsa1s??ak?1,sak,s?am,s0m?ak?1,s?j?cj?zj从此表可知?s?0,即有c1a1s?c2a2s???cmams?cs?0，也就是cs??ciais。i?1通过迭代，我们得到了新的单纯形表，其中xs为基变量了，而xk为非基变量了。我们可得到下表。

36

又显然在新的单纯形表中，基变量的检验数为零，用同样的方法可证明其他的非基变量的检验数不变，仍然小于零，这样就证明了新得到的基本可行解仍然是最优解。

这样我们得到了判断线性规划有无穷多最优解的方法：对于某个最优的基本可行解，如果存在某个非基变量的检验数为零，则此线性规划问题有无穷多最优解。

37

四、退化问题

在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。 3目标函数maxz?2x?x3例4.用单纯形表，求解下列线性规划问题。 12解：加上松驰变量s1,s2,s3化为标准形式后，

约束条件x1?x2?2,填入单纯形表计算得：

2x1?x3?4,x1?x2?x3?3,x1,x2,x3?0.

在以上的计算中可以看出在0次迭代中，由于比值b1/a11=b2/a21=2为最小比值，导致在第1次迭代中出现了退化，基变量s2=0。又由于在第1次迭代出现了退化，基变量s2=0，又导致第2次迭代所取得的目标函数值并没有得到改善，仍然与第1次迭代的一样都等于4。像这样继续迭代而得不到目标函数的改善，当然减低了单纯形算法的效率，但一般来说还是可以得到最优解的。像本题继续计算如下：

38

得到了最优解x1=1，x2=0，x3=2，s1=1，s2=0，s3=0，其最优值为5。

但有时候当出现退化时，即使存在最优解，而迭代过程总是重复解的某一部分迭代过程，出现了计算过程的循环，目标函数值总是不变，永远达不到最优解。 下面一个是由E.Beale给出的循环的例子。 例5

目标函数 ：min f =－（3/4）x4+20x5－（1／2）x6+6x7. 约束条件：x1+（1／4）x4－8x5－x6+9x7=0，

x2+（1／2）x4－12x5－（1／2）x6+3x7=0， x3+x6=1，

x1，x2，x3，x4，x5，x6，x7≥0.

这个例题的确存在最优解，但用一般单纯形表法，经过6次迭代后得到的单纯形表与第0次单纯形表一样，而目标函数都是零，没有任何变化，这样迭代下去，永远达不到最优解。为了避免这种现象，我们介绍勃兰特法则。

首先我们把松弛变量（剩余变量）、人工变量都用xj表示，一般松弛变量（剩余变量）的下标号列在决策变量之后，人工变量的下标号列在松弛变量（剩余变量）之后，在计算中，遵守以下两个规则： （1）在所有检验数大于零的非基变量中，选一个下标最小的作为入基变量。 （2）在存在两个和两个以上最小比值时，选一个下标最小的基变量为出基变量。 这样就一定能避免出现循环。

39

本文来源：https://www.bwwdw.com/article/w9m6.html