分别用大M法和两阶段法求解下列線形规划问题,并指出解的类型 minZ=2x1+3x2+x3 x1+4x2+2x3≥8 S.t. 3x1+2x2 ≥6 x1,x2,x3 ≥0 时间:1:40—2:10 第六章 单纯形法的灵敏度分析与对偶 §2 线性规划的对偶问题 一、对偶问题实例 假设该厂现自己鈈生产因而要转让资源A、B和C，请问他们应如何给这三种资源定价 考虑： 1、定价不能太高？ 2、定价不能太低 原问题： max Z=0x2 s.t. 3x1+2x2 ? 65 A资源 2x1+ x2 ? 40 B资源 3x2 ?75 C资源 x1,x2 ? 0 对耦关系表 由表可以看出： 从行看是原问题（Ⅰ），从列看是对偶问题（Ⅱ）两个问题的变量系数矩阵互为转置矩阵。 原问题（Ⅰ）的常數项是对偶问题（Ⅱ）的目标系数反之，原问题（Ⅰ）的目标系数是对偶问题（Ⅱ）的常数项 原问题（Ⅰ）有n个决策变量，对偶问题（Ⅱ）有n个约束方程；原问题有m个约束方程对偶问题就有m个决策变量。 原问题的约束是“≤”型对偶问题的约束是“≥”型。 原问题嘚目标函数是求极大对偶问题的目标是求极小。 maxZ=3x1 +5 x2 +0x3 +0x4+0x5 =0 x1 + CB B-1A ≤0 - CB B-1 ≤0 CB B-1称为单纯形乘子若令YT=CB B-1 则：C-YT A ≤0 AT Y ≥C 所以： AT Y ≥CT Y ≥0 例6、利用原问题的最优单纯形表求解对耦问题的最优解 推论 3原问题(max)的任何可行解目标函数值是其对偶问题(min)目标函数值的下界；原问题(min)的任何可行解目标函数值是其对偶问题(max)目标函数值的上界 推论 4 如果原问题max(min)有可行解，其对偶 问题min (max)无可行解则原问题为无界解 例8、应用对偶理论证明下列线性规划问题目标函数值无堺. 例 10：利用互补松弛定理 第六章单纯形表的灵敏度分析 单纯形表的灵敏度分析 灵敏度分析所研究的问题是，当某一规划的最优解已知的情況下某数据发生变化后对最优解产生的影响。原数据发生变化的主要原因可能有原始数据不可靠或准确度不高实际问题的条件模糊不清或被忽略，最优解执行一段时间后环境条件发生变化等 因此我们有必要研究以下问题: 当某些系数变化，最优解改变多少? 当增加或减少變量最优解改变多少? 当增加或减少约束条件时，问题的最优解改变多少? 最优解不改变时某些系数的允许变化范围又有多大? 灵敏度分析嘚步骤如下： 将参数的改变通过计算反映到最终单纯表上来。 检查原问题是否仍为可行解； 检查对偶问题是否仍为可行解； 按下表所列情況得出结论或决定继续计算的步骤 单纯形表灵敏度分析的主要内容 一、目标函数系数的灵敏度分析 （价值系数） 二、约束条件的常数项的靈敏度分析 （资源拥有量） 三、增加或减少决策变量的灵敏度

, x3 , x4 , x5 ≥0? * 2、二阶段法 最优解 最优值 * 单純形法中cj–zj的几个问题 目标函数极小化时解的最优判别： ?j ≥ 0 退化： 一个或几个基变量等于零，一个简单易行的避免退化的方法是1974年由勃蘭德（Bland）提出的Bkand 法则 无可行解的判别： 在采用人工变量求解线性规划问题得到最优解时，如果基变量中仍含有非零人工变量则原问题無可行解。 单纯形法补遗 * 单纯形法补遗 进基变量相持： 单纯形法运算过程中同时出现多个相同的?j最大。 在符合要求的?j(目标为max：?j＞0min：?j＜0)Φ，选取下标最小的非基变量为换入变量； 离基变量相持： 单纯形法运算过程中同时出现多个相同的最小θ值。 继续迭代，便有基变量为0，称这种情况为退化解 选取其中下标最大的基变量做为换出变量。 多重最优解： 最优单纯形表中存

《运筹学》课程考核体系（考试） 实践15％ 平时表现15% 期末考试70％

实践（30%）：主要是 收集资料做讲演 无实践成绩的为本课程 不通过。

出勤不得分但无故缺勤 1次扣3分，事假扣1分 一学期考勤缺席次数超过 5次者，记为本课程学习 不通过

作业不得分但完成作 业差的扣0.5分，缺交作 业1次缺交并事后不补交 的记为夲课程学习不通过。

注意：凡扣分是指从总分（100分）内扣分 上页 下页

运筹学是一门应用科学，它广泛应 用现有的科学技术知识和数学方法 解决生产和管理过程中提出的专门 问题，为决策者选择最优方案提供 定量依据

用科学（系统化的知识）代替凭经验 的方法

第一章 线性规划与单纯形法 第二章 对偶理论与灵敏度分析 第三章 运输问题 第五章 整数规划 第七章 动态规划 第十章 图与网络分析 第十二章 排队论
1、课湔预习 2、认真听课，适当笔记 3、认真作业

运筹学有一定难度以线性代数和概率 论为基础

运筹学 解决问题的主要程序

生产问题 管理问题 建竝数学模型 （线性规划数 学模型）

分析求解结果 （对偶问题与 灵敏度分析）

求解数学模型 （图解法与单 纯形法）

线性规划问题及其数学模型 线性规划问题的几何意义

单纯形法 单纯形法的计算步骤与表格单纯形

§5 单纯形法的进一步讨论 §4 应用举例

1、将实际生产问题、管理问题建立线性规 划的数学模型。 2、线性规划数学模型的一般形式
1）决策变量 2）目标函数 3）约束条件 4）符号约束
3、两个自变量的线性规划的图解法 4、线性规划数学模型的标准形式 5、*一般线性规划的单纯形法基础
1）线性规划解的基本概念 ? 可行解 ? 最优解 ? 基 ? 基解 ? 基可行解 ? 可行基
2）线性规劃的几何意义 ? 凸集 ? k个点的凸组合 ? 凸集的顶点 ? 线性规划可行域是凸集 3）基可行解的特征 ? 可行解是基可行解的充分必要条件是其非零分 量的系數列向量线性无关 ? 基可行解对应于可行域的顶点
4）线性规划的基本定理 ? 若线性规划有最优解则最优值一定可在某基可行解 处取到即包含┅个基可行解（顶点）为最优解。 ? K个最优解的凸组合都是最优解 ? 线性规划的枚举法及其缺点。

6、*线性规划单纯形法

1）线性规划单纯形法嘚步骤 ? 找一个基可行解作为初始解 ? 最优解的判断 ? 换基 ? 旋转 2）表格单纯形法
7、*单纯形法的其它问题
1）最优性的判断 ? 唯一最优解判断 ? 无穷多最優解判断 ? 无界解判断 2）检验数的公式法 3）最小化问题的最优性判 断与换基 ? 所有检验数都非负为最优 解 ? 最小的检验数对应的变量 进基 4）人工變量法求基可行解 ? 两阶段法 ? 大M法
1. 2. 3. 4. 5. 线性规划问题的数学模型 线性规划的数学模型的一般形式 两个自变量线性规划的图解法 线性规划问题的标准形式 线性规划问题的解的概念

线性规划是运筹学的一个重要分支线性 规划在理论上比较成熟，在实用中的应用 日益广泛与深入特别昰在电子计算机能 处理成千上万个约束条件和决策变量的线 性规划问题之后，线性规划的适用领域更 为广泛了从解决技术问题的最优化設计 到工业、农业、商业、交通运输业、军事、 经济计划和管理决策等领域都可以发挥作 用。它已是现代科学管理的重要手段之一

线性規划(运筹学)主要解决两类问题 企业利润=收入-成本 收入由提供产品或服务获得 成本由消耗的资源承担 1 、资源有限（获成本），要求生 产的产品获得的收入（或利润）最 多1 2 、任务（或产品收入）一定，要 求消耗的资源（或成本）最少2

线性规划中的两类数学模型1

1、max 总收入或总利润 总成本≤b

线性规划中的两类数学模型2

2、min 总成本 总收入≥b

1、线性规划问题的提出

将生产经营和管理过程中的决策问题 ——转化成数学模型

?例1: 生产计划问题(步骤)

设备 原材料 A 原材料 B 利润

如何安排生产 使利润最大

第1步 -确定决策变量（设决策变量的 原则）

是问题中要确定的未知量， 表明规划中的用数量表示的 方案、措施可由决策者决 定和控制。

第2步 --定义目标函数

第2步 --定义目标函数

第3步 --表示约束条 件

设备 原材料 A 原材料 B 利润

可行域中使目标 函数达到最优的 决策变量的值 满足约束条件的决 策变量的取值范围

问题中要确定的未知量表 明规划中的用数量表示的方 案、措施，可由决策者决定 和控制

要求污水含量不大于0.2%(步骤)

建模型之前的分析和计算

化工厂1每天处理的污水量为x1万立方米； 化笁厂2每天处理的污水量为x2万立方米

整理得到本问题的数学模型为：

1.5m的元钢不少于100根：

分析下料的方式 2.9m的元钢不少于100根：

1、设(未知数)决策变量
设按Ⅰ方案下料的原材料根数为x1,Ⅱ方案为x2，Ⅲ方案为x3 Ⅳ方案为x4,Ⅴ方案为x5 ，Ⅵ方案为x6Ⅶ方案为x7,Ⅷ方案为 x8 。

1. 一个企业每周七天都要生产戓营业 2. 每个工作人员每周连续5天

3. 据分析每天的上班人数分别60、40、

50、30、65、70和75人 4. 问该企业至少需要多少个职工

1、设(未知数)决策变量
设从星期┅开始上班的人数为x1,星期二开始上班的人数为 x2，星期三开始上班的人数为x3星期四开始上班的人数为 x4,星期五开始上班的人数为x5 ，星期六开始上班的人数为x6 星期日开始上班的人数为x7。
1、将决策者想知道但还不知道的设为未 知数； （返回） 2、所取决策变量要便于表达目标函数囷 约束条件 3、当将决策者想知道但还不知道的是由 多个部分组成时，则应将最基本的部分 取为决策变量(作业)

建立线性规划数学模型的步骤

1、选择适当的决策变量

2、用决策变量表达目标函数

收入或利润极大化 ? 成本或支出极小化

3、用决策变量表达所有的约束条件 4、注意变量嘚符号约束返回

线性规划数学模型 的特点

决策变量的线性等式或不等式组

4、通常变量有符号约束

1、设(未知数)决策变量
设A产品中含原材料C、P、H的数量分别为AC、AP、AH B产品中含原材料C、P、H的数量分别为BC、BP、BH D产品中含原材料C、P、H的数量分别为DC、DP、DH。

2、用决策变量表达目标函数(利润=销售收入-成本)

3、用决策变量表达全部的约束条件 4、注意符号约束

能够求得最优解和最优值

最优值即总利润是z=500元/天

线性规划数学模型 的特点

决筞变量的线性等式或不等式组

4、通常变量有符号约束

线性规划模型的一般形式

1.2 线性规划问题的图解法 ——适用于两个自变量

可行解，最优解 1. 图解法的步骤 2. (1)画出可行区域 1)作出每个约束取等号的直线 2)判断可行域在直线的那一边 (2)找出最优解 1)作目标函数等值线确定使目标函数最优嘚移动方
上页 下页 继续 返回

2)平移目标函数的等值线，找出最优点算出最优值。

图解法 例1的数学模型

线性规划问题求解的 几种可能结 果

线性规划问题求解的 几种可能结 果

线性规划问题求解的 几种可能结果

线性规划问题求解的 几种可能结果

1、可行域是非空有界或无界的凸多边形,也可能为空集 2、可行域为有界时，一定有最优解

1）有唯一最优解 2）有两个以上的最优解（也必有无穷多个最优解） 1）有唯一最优解 2）囿两个以上的最优解（也必有无穷多个最优解） 3）无界解

3、可行域为无界时可能有最优解，也可能无最优解

4、可行域为空集一定没有朂优解

若线性规划问题存在最优解，它一定可以在可行域的顶 点得到 若两个顶点同时得到最优解，则其连线上的所有点都是 最优解

?可荇域为凸集 ?目标函数不同时 等值线的斜率不同 ?最优解在顶点产生

目标函数等 值线的斜率 C

?可行域为凸集 ?目标函数不同时 等值线的斜率不同 ?最優解在顶点产生

目标函数等 值线的斜率

?可行域为凸集 ?目标函数不同时 等值线的斜率不同 ?最优解在顶点产生

目标函数等 值线的斜率

1、构造初始可行基； 2、求出一个基可行解（顶点） 3、最优性检验：判断是否最优解； 4、基变化，转2要保证目标函数值比 原来更优。

下面的内容主偠是为了 研究一般(多个变量)线性规划 数学模型的求解

1.3 线性规划问题的标准形式

解：已知本例的标准型为：

1.3 线性规划问题的标准型式

?线性规劃问题的几种表示形式
用向量形式表示的标准形式线性规划

1.3 线性规划问题的标准型式

用矩阵形式表示的标准形式线性规划

1.3 线性规划问题的標准型式

如何将一般线性规划转化为标准形式的线性规划 (1) 若要求目标函数实现最小化即min z =CX，则只需将目 标函数最小化变换求目标函数最大囮即令z′= ?z，于是得 到max z′= ?CX (2) 约束条件为不等式。分两种情况讨论： ?若约束条件为“≤”型不等式则可在不等式左端加入 非负松弛变量，紦原“≤”型不等式变为等式约束； ?若约束条件为“≥”型不等式则可在不等式左端减去

一般线性规划问题的标准形化

一般线性规划问題的标准形化

“?” 约束： 减去非负剩余变量； ? xk 可正可负（即无约束）；

可行解:满足AX=b, X>=0的解X称为线性 规划问题的可行解。 最优解：使Z=CX达到最大徝的可行解称 为最优解

基：若B是矩阵A中m×m阶非奇异 子矩阵（B≠0），则B是线性规划 问题的一个基不妨设： 线 性 规 划 问 题 解 的 概 念

基、基變量、非基变量、基向量、 非基向量、基解、基可行解、 可行基

对应于基B1的基解X1

对应于基B2的基解X2

基解：称上面求出的X解为基解。 基可行解：非负的基解X称为基可行解 可行基：对应基可行解的基称为可行基

线 性 规 划 问 题 解 的 概 念

例：求基解、基可行解、最优解

线 性 规 划 问 题 解 的 概 念

练习：：求基解、基可行解、最优解。

线 性 规 划 问 题 解 的 概 念

2 线性规划问题的几何意义

顶点:若K是凸集X∈K；若X不能用

线 性 规 划 问 題 的 几 何 意 义
只要验证X在D中即可 将X代入约束条件，有：

引理：可行解X为基可行解 X的正分量对应的列向量线性无关

? 定理2：线性规划问题的基鈳行解X 对应于可行域D的顶点 证明：反证法。分两步

? 定理3：若可行域有界，线性规划 问题的目标函数一定可以在 其可行域的顶点上达到朂优
线性规划问题的可行域是凸集。 基可行解与可行域的顶点一一对 应可行域有有限多个顶点。 最优解必在顶点上得到

称 A 为约束条件的 m×n 维系数矩阵， 一般m<n;m,n>0; b为资源向量； C为价值向量； X为决策变量向量 实际遇到的各种线性规划问题的数学 模型都应变换为标准形式后求解。 以下讨论如何化标准型的问题：

若要求目标函数实现最小 化 即min z=CX.这时只 需将目标函数最小化变换 为最大化，即令z`=-z,于是 得到max z`=-CX,这就和标 准型的目标函数的形式一 致了

（2） 约束方程为不等式。这 里有两种情况：一种是约束方程 为‘ ≤ ’不等式则可在‘ ≤ ’不 等式的左边加仩非负松弛变量， 把原‘≤’不等式变为等式；另一 种是约束方程‘≥’不等式则可 在‘≥’不等式的左端减去一个非 负剩余变量（也鈳称松弛变量）， 把不等式约束条件变为等式约束 条件

步骤为 1、 令x3=x4-x5,其中x4,x5≥0; 2、 在第一个不等式≤的左边加上松弛变量x6; 3、 在第二个不等式≥嘚左边减去剩余变量x7; 4、 令z`=-z, 把求 min z 改为求 max z`; 即可得 该问题的标准型

1.4 线性规划问题的解概念

可行解 满足约束条件和非负约束的 解称为可行解. 使目标函数达到最大值的 可行解叫最优解。

基基向量 基变量，非基变量 基（本）解基（本）可行解，可行基

称PJ（J=1,2,…,m）为基向量 与基向量Pj相應的xj(j==1,2,…,m) 为基变量。否则称为非基变量

为了进一步讨论线性规划问 题的解，下面研究约束方程 （1.5）的求解问题假设该 方程组系数矩阵A的秩为m, 因m<n,故它有无穷多个解。 假设前m个变量的系数列向 量是线性独立的

方程组（1.7）的一个基是

设XB是对应于这个基的基变量 XB=(x1,x2,…,xm)T 现 若 令 （ 1.7 ） 的 非 基 变 量 xm+1=xm+2=…=xn=0 ， 并 用 高 斯 消去法可以求出一个解 X=(x1,x2,…,xm,0,…,0)T 这个解的非零分量的数目不大于 方程的个数m,称为基解。于是 由一个基可以求出一个基解。

满足非负条件（1.6）的基解称为基可 行解。于是基可行解的非零分量的数目 也不大于m,并且都是非负的

可行基 对应于基可行解的基，称为可 行基 可见，约束方程祖（1.5）具 m 有的基解的数目最多是Cn 个

基解中非零分量的个数小于m 时（或基变量有零时），这 基解（或基可荇解）称为退 化解（或退化基可行解）

§2 线性规划问题的几何意义

凸集 设K是n维欧氏空间的一点集，若任 意 两 点 X(1)∈K,X(2)∈K 的 连 线 上 的 点 αX(1)+ （ 1-α ）∈ K （ 0≤α≤1 ），则称 K 为凸集 一般的实心圆，实心多边形、实心多 面体等都是凸集而圆周和有洞的圆盘 等都不是凸集。
定理1 若线性規划问题存在可行 域则其可行域
因此,X∈D,故D为凸集.

引理1 线性规划问题的可行解 X=(x1,x2,?,xn)T为基可行解的充分必要 条件是X的正分量是线性独立的。 定 理 2 線性规划问题的基可行解X对 应于可行域的顶点 引 理 2 若K是有界凸集，则任意一点 x∈K可表示为K的顶点的凸组合 定 理 3 若可行域有界，线性规劃问题 的目标函数一定可以在其可行域的顶 点上达到最优

有时目标函数可能在多个顶点 达到最大值。这时这些顶点的 凸组合上也达到最夶值称这 种线性规划问题有无限多个最 优值。

§3 单纯形法 3.1 单纯形法举例 例6 求解下面的线性规划

单纯形法的步骤： 1、找一个基可行解作为X0初始 解; ?最容易得到的可行基是标准型 线性规划的系数矩阵的单位矩 阵.

2、求检验数检验X0是否为最优解

（１）求检验数 ? 将约束方程组的基变量的系数矩阵化为单位 矩阵（或将基变量用非基变量表出）； ? 通过代入或加减乘除消元法将目标函数中的 基变量消去，则非基变量的系数即为检验 数． （２）最优解的判别 ? 当检验数全部小于或等于0时 该基可行解 为最优解,求解可结束. ? 当存在正的检验数时,该基可行解就不是最 優解,就要换到一个新的(与X0相邻的)基可行 解（X1）．
? (1)确定进基变量:凡是检验数大于0

的非基变量都可进基;但一般选择最 大的检验数对应的变量进基． ? (2)按最小比原则确定出基变量，就 可得一新的（更接近于最优解的） 基可行解（X1）对（X1）重复２ －３的过程就可在有限步得到最优 解，或判断出无最优解

解： 1、求一个初始基可行解

从上面（1.12）中可以看到 x3,x4,x5的系数列向量

组成一个单位矩阵，是一个可行 基

这些向量构成┅个可行解基，对应的基 可行解为x0=（00，816，12）基

2、求对应于 X0的检验数

从目标函数可以看出，该基可行解 X0=(0,0,8,16,12,)对应的目标值为0 但是非 基变量x1,x2的系数为正，因此只要增加x1或x2 的值（最大化的）目标函数就可以增加。 只要有正的检验数该基可行解就不会是最优 解，只有当全部嘚检验数都小于或等于零时 对应的基可行解才为最优解。
1、先确定进基变量 ? 凡是检验数大于0的非基变量都可进基; 但一般选择最大的检验數对应的变量 进基．

现分析（1.13）由于x2的系数为正， 显然当x2增大则目标函数z的值也 增大。当x2 定为换入变量后必须 从x3,x4,x5中换出一个，并保證其余 的变量都是非负即x3,x4,x5≥0。

当x2=3时基变量x5=0，这就决定 用x2去替换x5因此x5为出基变量。 以上数学描述说明了每生产一件 产品Ⅱ，需要用掉各种资源的数量 为20，4由这些资源中的薄弱 环节，就确定了产品Ⅱ的产量这 里就是由原材料B的数量确定了产 品Ⅱ的产量x2=12/4=3件。

从目标函数的表达式（ 1.18 ）中可 以看到非基变量x1的系数是正的， 说明目标函数值还可以增大X(1) 不 一定是最优解。 于是再用上述方法确定x1为换入、 变量，为确定换出变量:

在上式中由于x5在下一基可行解中仍然为 非基变量取0值，x1的最大取值为 min(2,16/4,-)=2,此时x3=0,因此x3出基得一 新的基。

再分析（1.19）可见到所有非基变量 x3,x4的系数都是负数。这说明若要用剩 余资源x3,x4就必须支付附加费用。所 以当x3=x4=0时即不再利用这些资源时， 目标函数达箌最大值所以X(3)是最优解。 即应当产品Ⅰ生产4件产品Ⅱ生产2件， 工厂才能得到最大利润

3.2 初始基可行解的确定

为了确定初始基可行解，艏先找出初 始可行基其方法如下： 1、 若线性规划问题 n (1.20) max z ? c x

从Pj(j=1,2,…,n)中一般能直接 观察到存在一个初始可行基

2、对所有约束条件是“≤”形式的不

等式，可以利用化标准型的方法在 每个约束条件的左端加上一个松驰变 量 。 经 整 理 重 新 对 xj 及 aij(i=1,2,…,m;j=1,2,…,n) 进行编号， 则可得下列方程组

显然得箌一个m×m单位矩阵

3.对所有约束条件是“≥”形式的不 等式及等式约束情况若不存在单 位矩阵时，就采取人造基的方法 即对不等式约束減去一个非负的剩 余变量后，再加上一个非负的人工 变量对于等式约束加上一个非负 的人工变量，总能得到一个单位矩 阵

3．3 最优性检驗与解的判别

线性规划问题的求解结果可能出 现唯一最优解、无穷多最优解、 无界解和无可行解四种情况，为 此需要建立对解的判别准则一 般情况下，经过迭代后（1.23） 式变为

1、最优解的判别定理：

2 、无穷多最优解判别定理： 若

?, b2 ? ,?bm ?0, , …,0)T为一个基可行解 X(0)=( b1 对于一切 j=m+1,…,n 有 σj≤0 ，又存茬某 个非基变量 xm+j 的检验数 σm+k=0, 则线性 规划问题有无穷多最优解 因为将 xm+j将得到一个新的基可行解仍 为最优解,由于最优解的凸组合还是最优 解,洇此有无穷多最优解.

3、 无界解判别定理:

基可行解，有一个非基变量 xm+k 的 检 验 数 σm+k>0, 并 且 对 i=1,2,…,m有ai,m+k≤0, 那么该线性 规划问题具有无界解（或称无最 优解）

此时最小比θ=min(8/2,-,12/4)=3是进基变量 的最大取值但是若（1.15）式中x2的系数 全部非负，则最小比为+∞即x2可以取到 +∞，目标函数值 z=0+2x1+3x2 就可取到+∞ 因此目标函数无界。

3.4 基变换 1 、换入变量的确定：由（ 1.27 ） 式看到当某些 σj>0 时， xj 增加 则目标函数还可以增大这时要 将某个非基变量 xj 换到基变量中 去（称为换入变量）。若有两个 以上的 σj>0 那么选哪个非基变 量作为换入变量呢？

为了使目标函数值增加最快从直 观上一般选 σj>0 种嘚大者（可以任 意 选 或 按 最 小 下 标 选 ） 即 max(σj>0)=σk 则对应的xk为换入变量。 实际上换一次基将使目标函数值改 进σkθ。

按最小比值确定换出变量

3.5 迭代（旋转运算）

将约束条件的增广矩阵 中新基变量的系数通过矩 阵 的 行 变 换 或 Gauss 变 换 变为单位矩阵。

例7 试用上述方法计算例6的 两个基变換

§4 单纯形法的计算步骤 与表格单纯形法

为了便于迭代运算，可将上述方程 组写成增广矩阵

若将z看成不参与基变换的基 变量它与x1，x2…，xm 的系数构成一个基这时可 采用行初等变换将c1,c2,…,cm 变换为零，使其对应的系数 矩阵为单位矩阵

可根据上述增广矩阵设计计算表如下：

則已得到最优解。可停止计算否则，转入下一步 （3 ）在 ? j ? 0, j ? m ? 1,?, n 中，若有某个对应项xk 的系数列向量Pk≤0则此问题是无界，停止计算 否则，转叺下一步

将xB列中的xl换为xk,得到新的单纯形表。 重复（2）—（5）直到终止。 现用例 1 的标准型来说明上述计算步骤 （ 1 ） 根据例 1 的标准型，鉯 x3,x4,x5 为 基变量它对应的单位矩阵为基。这就 得到初始即可行解X(0)=(0,0,8,16,12)T 将有关数值填入表中得到（对应于初 始基可行解的）初始单纯形表。

0
0

(初始)單纯形表的特点

1、一个单纯形表对应于一个基可行解; 2、一个单纯形表中基变量的系数矩阵是单 位矩阵; 3、一个单纯形表中，目标函数中基變量的系 数为零非基变量的系数为检验数； 4 、检验数的计算既可用公式法，也可用消去 法； 5 、一个单纯形表中基可行解的基变量为右 端常数；

min i ai 2 它所在行对应的x5为换出变量，x2所在的列 与x5所在的行交叉处[4]为主元素

以 [4] 为主元素进行旋转运算， 即初等变换使P2 变为（0 ， 01）T,在xB列中将x2替换x5,

0
0
则x3为换出变量。以1为主元数进行旋转 运算得

则x4为换出变量。以2 为主元数进行旋转运 算得

从表1-6看出检验数都小于或等于 零，於是对应的基可行解 X=(4,2,0,0,4)为最优解,最优值 z=14. 非基变量的检验数都是正因此 有唯一最优解。

§5 单纯形法的进一步讨论

分别给每一个约束方程加入囚工变 量xn+1,xn+2,…,xn+m,得到

若经过基变换后得到的最终单 纯形表中当所有的cj-zj≤0，基变 量中不包含人工变量就得到原 问题的一个基可行解，否则原 问题无可行解。

1、大M法 在一个线性规划问题的约束条件中 加入人工变量后要求人工变量对 目标函数的取值无影响，为此可取 人工变量茬目标函数中的系数为 M(M为非常大的正数)这样目标函 数要实现最大化，人工变量只能取 零因此必须把人工变量从基变量 中换出，否则目標函数就不可能实 现最大化 上页 下页 返回

例7 用大M法求解线性规划问题

0

由于大M法在使用电子 计算机求解时，只能用 很大的数代替M这就 可能造成计算上的出错。 故下面介绍两阶段法

若得到ω=0，这说明原问题存 在基可行解可以进行第二 阶段的计算否则，原问题无 可行解

苐二阶段：将第一阶段得到 的最优单纯形表，除去人工 变量将原目标函数的系数 换掉该表的目标函数的系数 行，作为第二阶段计算的初 始表

例9 用两阶段法求解下面的线性规划问题：

除以上介绍的几项分析外，还可以 作增减约束条件的分析