当前位置：文档之家 › 第5章：单纯形法

第5章：单纯形法

  • 格式：ppt
  • 大小：3.10 MB
  • 文档页数：78

下载文档原格式

  / 78

合集下载

第5章-单纯形法

第5章-单纯形法
所有变量的解都是大于等于零，才能断定这个解是基本可行解，这个基是可行
基。那么我们能否在求解之前，就找到一个可行基呢？也就是说我们找到的一个
基能保证在求解之后得到的解一定是基本可行解呢？由于在线性规划的标准型中
要求bj都大于等于零，如果我们能找到一个基是单位矩阵，或者说一个基是由单位 矩阵的各列向量所组成（至于各列向量的前后顺序是无关紧要的事）例如，
xm a x m ,m 1 m 1 a m ,n xn bm ,
x j 0. j 1, 2, , n
以下用 xii1,2, ,m表示基变量，用 x jj m 1 ,m 2 , ,n
表示非基变量。
§2 单纯形法的表格形式
把第i个约束方程移项，就可以用非基变量来表示基变量xi， xi bi ai,m1xm1ai,m2xm2 ai,nxn
i1
a1j
,cma2j
amj
c1,c2, ,cmpj
§2 单纯形法的表格形式
上面假设x1,x2,…xm是基变量，即第i行约束方程的基变量正好是xi，而 经过迭代后，基将发生变化，计算zj的式子也会发生变化。如果迭代后的 第i行约束方程中的基变量为xBi，与xBi相应的目标函数系数为cBi，系数列
三、 基变换 通过检验，我们知道这个初始基本可行解不是最优解。下面介绍如何进
行基变换找到一个新的可行基，具体的做法是从可行基中换一个列向量，得 到一个新的可行基，使得求解得到的新的基本可行解，其目标函数值更优。 为了换基就要确定换入变量与换出变量。 1.
从最优解判别定理知道，当某个σj＞0时，非基变量xj变为基变量不取 零值可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基 变量中去（称之为入基变量）。若有两个以上的σj＞0，则为了使目标函数 增加得更大些，一般选其中的σj最大者的非基变量为入基变量，在本例题 中σ2=100是检验数中最大的正数，故选x2为入基变量。

运筹学钱颂迪答案

运筹学钱颂迪答案

运筹学钱颂迪答案【篇一： 803 运筹学】class=txt>运筹学考试大纲一、考试性质运筹学是我校航空运输管理学院硕士生入学考试的综合考试科目之一，它是我校为招收交通运输规划与管理学科硕士研究生而实施的水平考试，其评价标准是普通高等院校优秀本科毕业生能够达到的及格以上水平，以保证被录取者较好地掌握了必备的专业基础知识。

本门课程主要考试内容包括：线性规划及其对偶理论、运输问题、目标规划、整数规划、动态规划、图与网络分析，注重考察考生是否已经掌握运筹学最基本的理论知识与方法。

二、考试形式与试卷结构1.答卷方式：闭卷、笔试2.答卷时间： 180 分钟3.题型比例：满分 150 分，基本概念 20% ，计算及证明题 80%三、考查要点1.线性规划及对偶理论：单纯形法，改进单纯形法。

线性规划的对偶理论，对偶单纯形法，灵敏度分析；2.运输问题：运输问题的数学模型；用表上作业法求解运输问题；产销不平衡的运输问题及其求解方法；3.目标规划：目标规划的数学模型，目标规划的图解法与单纯形法；4.整数规划：0－1 型整数规划，分支定界解法，割平面解法，指派问题；5.动态规划：动态规划的基本概念和基本方法，动态规划的最优性原理与最优性定理，动态规划与静态规划的关系，动态规划的应用；6.图与网络分析：图与树的基本概念，最短路问题，网络最大流问题，最小费用最大流问题，中国邮路问题，网络计划。

四、主要参考书目1、郭耀煌，李军 .运筹学原理与方法. 成都：西南交通大学出版社，2004 ；2 、钱颂迪主编. 运筹学（修订版）. 北京：清华大学出版社，1991 。

【篇二：运筹学大纲(13 、 14 级使用)2014.9 】（理论课程）开课系（部）：数理教研部课程编号：380020 、 381703课程类型：专业必修课或学科必修课总学时： 48 或 32学分：3或2适用专业：信息管理与信息系统、投资学、工业工程、工程管理、经济统计学、物流管理开课学期： 3 或 4 或 5先修课程：高等数学、线性代数一、课程简述本课程是以经济活动方面的问题以及解决这类问题的原理和方法作为研究的对象，把经济活动中的问题归结为对应的某种数学模型，运用数学知识等工具求得最合理的工作方案。

第五章线性规划

第五章线性规划

15
解：设xij为第i个人做第j项工作，（xij=1或0）
Max Z＝0.6x11+0.2x12+0.3x13+0.1x14+0.7x21+0.4x22+0.3x23+0.2x24 +0.8x31+x32+0.7x33+0.3x34 +0.7x41+0.7x42+0.5x43+0.4x44
x11+x12+x13+x14=1
x1-x2≤2
x2
x1,x2≥0
4
可行解域 (1,1)
-2
2
x1
-2
23
4、无可行解
Min Z＝x1+2x2 s.t. x1+x2≤1 2x1+x2≥4 x1,x2≥0
可行域为空
x2
集，无可行 解!
4 (1,2)
1 12
x1
24
三、线性规划的几何意义
线性规划的可行解域为凸多边形（凸集）。 可行解域凸多边形有若干个顶点，顶点的个数是有限的。
8
解：设按第j种方案下料的原材料为xj根
min Z= 5x1 + 6x2＋23x3+5x4+24x5+6x6+23x7+5x8
2x1 + x2 +x3+x4
≥100
2x2 +x3+ 3x5+2x6+x7 ≥150
x1
+x3+3x4+ x6+3x7+5x8≥100
xi 0 (i =1,…,8)，且为整数
资源约束 变量非负约束3

运筹学单纯形法

运筹学单纯形法
总结：①在迭代过程中要保持常数列向量非负，这能确保基 可行解旳非负性。最小比值能做到这一点。 ②主元素不能为0。因为行旳初等变换不能把0变成1。 ③主元素不能为负数。因为用行旳初等变换把负数变成1会 把常数列中相应旳常数变成负数。
16
三、其他解旳情况 1、无穷多种解 例2 解LP问题：
min Z x1 2 x2 x3 0 x4 0 x5
xx51
1 2c 5 3c
其中c是满足非负性旳任意常数。
21
再由
x1,
x5
旳非负性，知：
x1 x2
1 2c c
0 0
x5 5 3c 0
解出 0 c 5 3
最优解为：
(2c 1, c,0,0,5 3c)T （其中0 c 5 ）
3
最优值为：max S 1.
22
2、无最优解旳两种情况：
相应地，将 X 0代入目的函数得 Z ( X 0 ) 0
从数学角度看，若让非基变量 x1, x2 取值从零增长，
6
min Z 2x1 x2 0x3 0x4 0x5
相应旳目旳函数值Z也将随之降低。所以有可能找到一种 新旳基本可行解，使其目旳函数值有所改善。即进行基变
换，换一种与它相邻旳基。再注意到 x1 前旳系数－2比 x2
x3
6 x1 x1
2x2 x2
x4 x5
xi 0
i 1,,5
15 24 5
目前可行基{ x3, x4 , x5 }所相应旳基本可行解
X 0 (0,0,15,24,5)T
(相应可行域旳 o(0,0) )
显然不是最优。 因为从经济意义上讲， x1 0, x2 0
意味着该厂不安排生产，所以没有利润。
2

运筹学02-单纯形法

运筹学02-单纯形法

反之，若经过迭代，不能把人工变量都变
为非基变量，则表明原LP问题无可行解。
19
第2章
单纯形法
2.3 人工变量法
2.3.1 大M法
在原问题的目标函数中添上全部人工变量，并令其系数 都为-M，
而M是一个充分大的正数。即
max z = c1x1 + c2x2 + c3x3 + … + cnxn – M( xn+1 + xn+2 +…+ xn+m )
思路：由一个基本可行解转化为另一个基本可行解。 等价改写为 目标方程 max z max z = 3x1+5x2 z -3x1 -5x2 = 0 z -3x1 -5x2 x1 +x3 x1 +x3 = 8 2x2 +x4 2x2 +x4 = 12 s.t. s.t. 3x1+4x2 +x5 3x1 + 4x2 +x5 = 36 x1 ， x2 ，x3，x4，x5 x1 ， x2 ，x3，x4，x5 ≥ 0
以主列中正值元素为分母，同行右端常数为分子，求比值；
6
第2章
单纯形法
2.1 单纯形法的基本思想
(Ⅰ)
用换基运算 将X0 转化为 另一个基本 可行解 X1。
z- 3x1 -5x2 = 0 0 换基运算—— x1 +x3 = 8 ① 方程组的初等变换 目的是把主列变为 22x2 +x4 = 12 ② 单位向量：主元变 3x1 + 4x2 +x5 = 36 ③ 为1，其余变为0。 X0 = ( 0, 0, 8, 12, 36 )T z0 = 0
⑴ 当前基：m阶排列阵

运筹学第五章

运筹学第五章

A 原材料（kg) 设备（台时） 2 1 B 1 2 限量 11 10
单位利润
8
10
minZ=P1 d1+ +P2 (d2-+ d2+) +P3 d3OR2 4
例2的解法
解：问题分析：找差别、定概念（与单目标规划相 比） 1）绝对约束：必须严格满足的等式约束和不 等式约束，称之为绝对约束。 2x1+1.5x2≤50 (1) (2) 2）目标约束：那些不必严格满足的等式约束和 不等式约束，称之为目标约束（软约束）。目标 约束是目标规划特有的，这些约束不一定要求严 格完全满足，允许发生正或负偏差，因此在这些 约束中可以加入正负偏差变量。
16

例4：min Z
x1 x1 s .t . x 1 x2 x1
OR2
p d p d p (2 d d x d d 40 x d d 50 d d 24 d d 30 , x ,d ,d 0 ( i 1, 2 , 3 ,4 )
OPERATIONS RESEARCH
运筹学
徐 玲
OR2
1
第五章

目标规划
要求 1、理解概念 2、掌握建模 3、掌握图解法和单纯形解法 4、理解目标规划的灵敏度分析
OR2
2
5.1目标规划的概念及数学模型1
多目标问题 多目标线性规划 产品 例1

资源 原材料（kg) 设备（台时） 单位利润
OR2 8
7）目标规划的目标函数： 目标规划的目标函数是按各约束的正、负偏 差变量和赋予相应的优先因子而构造的。 目标函数的基本形式有三种： 1、要求恰好达到目标值，即正负偏差变量都要尽 可能地小，这时， minZ＝f(d+＋d-). 2、要求不超过目标值，即允许达不到目标值但正 偏差变量要尽可能地小，这时， minZ＝f(d+). 3、要求超过目标值，即超过量不限但负偏差变量 要尽可能的小，这时， minZ＝f(d-) 显然，本题目标函数表示为：

第5章 灵敏度分析


5.1 目标函数中价值系数的变化分析
由最优单纯形表可得
3 1 B p3 , p1 2 1 ,C 2 6 5 4 0 0,C B 5, 2 0 1 1 3 1 1 2 B 1 A 1 1 0 6 2 3
5.1 目标函数中价值系数的变化分析
其中， xi (i 1,2) 分别表示生产 1 产品和 2 产品的数量。用图解法如 图 5-1 所示求得最优解 B( x1 50, x2 250 ) ，即生产 1 产品 50 单位，生 产 2 产品 250 单位可以获得最大利润。假设两种产品中的某一产品的单位 利润增加或减少时，为了获取最大利润，就有可能增加或减少这一产品的 产量，也就是改变最优解。实际上产品利润在一定范围内变化时，整个线 性规划的最优解是不会变化的， 即仍然生产 50 单位的 1 产品和 250 单位的 2 产品而获利最大。当然其中某一产品利润变化超出一定范围的话，最优 解就会受到影响了。用图解法可以确定这一变化的范围，即确定其变化的 上限和下限。
用单纯形法可求得最优单纯形表如表 5-2 所示
5.1 目标函数中价值系数的变化分析
表 5-2 最优单纯形表
XB
x3
x1
0
x2
1
x3
1
x4
3 2
x5
1 -2
x6
-1
b
5
x1
1
1
0
6 -1 2
3
11
j
0
-1
0
-1
-1
47
最优方案是产品 A 生产 11 吨， 产品 C 生产 5 吨， 产品 B 和 D 不生产， 最大利润为 47 千元。
5.1 目标函数中价值系数的变化分析

《管理运筹学》第四版第5章单纯形法课后习题解析

《管理运筹学》第四版第5章单纯形法课后习题解析《管理运筹学》第四版课后习题解析第5章单纯形法1．解：表中a 、c 、e 、f 是可⾏解，f 是基本解，f 是基本可⾏解。

2．解：（1）该线性规划的标准型如下。

max 5x 1＋9x 2＋0s 1+0s 2+0s 3 s.t. 0.5x 1＋x 2＋s 1＝8 x 1＋x 2－s 2＝100.25x 1＋0.5x 2－s 3＝6 x 1，x 2，s 1，s 2，s 3≥0（2）⾄少有两个变量的值取零，因为有三个基变量、两个⾮基变量，⾮基变量取零。

（3）（4，6，0，0，-2）T（4）（0，10，-2，0，-1）T（5）不是。

因为基本可⾏解要求基变量的值全部⾮负。

（6）略 3.解：令333x x x ''-'=，z f -=改为求f max ；将约束条件中的第⼀个⽅程左右两边同时乘以-1，并在第⼆和第三个⽅程中分别引⼊松弛变量5x 和剩余变量6x ，将原线性规划问题化为如下标准型：j x '、j x ''不可能在基变量中同时出现，因为单纯性表⾥⾯j x '、j x ''相应的列向量是相同的，只有符号想法⽽已，这时候选取基向量的时候，同时包含两列会使选取的基矩阵各列线性相关，不满⾜条件。

4．解：（1）表5-10,,,,,, 24423 1863 1334 7234max 654332163321543321433214321≥'''=-''+'--=++''+'-+-=+''+'---++-=x x x x x x x x x x x x x x x x x x x x x x x x x x x f 约束条件：（2）线性规划模型如下。

max 6x 1＋30x 2＋25x 3 s.t. 3x 1＋x 2＋s 1=40 2x 2＋x 3＋s 2=50 2x 1＋x 2-x 3＋s 3＝20 x 1，x 2，x 3，s 1，s 2，s 3 ≥0（3）初始解的基为（s 1，s 2，s 3）T ，初始解为（0，0，0，40，50，20）T，对应的⽬标函数值为0。

单纯形法


矩阵A表示为： A = ( p1 ，p2 ，…，pn ) ， 其中 pj = ( a1j ，a2j ，…，amj )T。若找 到一个可行基，无防设 B = ( p1 ，p2 ，…，pm ) ，则m个基变 量为 x1 , x2 , …, xm，n-m个非基变量 为 xm+1 ，xm+2 ，…，xn 。通过运算， 所有的基变量都可以用非基变量来表 示：
f(x
6 )=3
二、单纯形法的基本思路 要找到线性规划问题的最优解，只要在基本 可行解中寻找就可以了。虽然基本可行解的数 目是有限个（不超过Cnm个），但当m,n较大时， 要用“穷举法”求出所有基本可行解是行不通 的。利用LP问题基本可行解（极点）的方法来 求解较大规模的问题是不可行的。 单纯形法的基本思路是：从线性规划问题的 一个基本可行解开始，沿边界转换到另一个使 目标函数值增大的基本可行解。反复迭代，直 到目标函数值达到最大时，就得到了最优解。



基本解 对于基B，令非基变量为零，求得满足AX=b的解,称 为基B对应的基本解。若得到的基变量的值均非负， 则称为基本可行解，同时称这个基B为可行基。 令非基变量 XN = 0，求得基变量 XB的值称为基本解 即 XB = B1 b XB 是基本解的必要条件为XB 的非零分量个数 m 基本可行解 基本解 XB 的非零分量都 0 时，称为基本可行解， 否则为基本非可行解 基本可行解的非零分量个数 < m 时，称为退化解
2.线性规划的基、基本解与基本可行解
基：设B是A矩阵中的一个非奇异（可逆）的 m×m子矩阵，则称B为线性规划的一个基。 与B中的这些列向量对应的变量称为基变量， m Cm n 个基。 其余变量称为非基变量。最多有
在标准型中，技术系数矩阵有 n×m 列，即 A = ( P1, P2 , … , Pn×m ) A中线性独立的 m 列，构成该标准型的一个基， 即 B = ( P1 , P2 , … , Pm )， | B | 0 P1 , P2 , … , Pm 称为基向量 与基向量对应的变量称为基变量，记为 XB = ( x1 , x2 , … , xm )T，其余的变量称为非基变 量，记为 XN = ( xm+1 , xm+2 , … , xm+n ) T ， 故有 X = XB + XN m Cm n 个基 最多有

单纯形法

目录第一章单纯形法的提出……………………………………………………………1.1 单纯形法提出背景……………………………………………………………第二章单纯形法的一般原理………………………………………………………2.1 单纯形法的基本思路…………………………………………………………2.2 确定初始基本可行解…………………………………………………………2.3 最优性检验……………………………………………………………………2.4 基变换…………………………………………………………………………2.5 解的判别定理…………………………………………………………………2.6 单纯形法求解线性规划问题的程序框图……………………………………第三章表格单纯形法………………………………………………………………3.1单纯型表求解…………………………………………………………………3.2 用单纯形法求解线性规划问题的举例………………………………………第四章人工变量及其处理方法……………………………………………………4.1大M法…………………………………………………………………………4.2两阶段法………………………………………………………………………4.3无最优解和无穷多最优解……………………………………………………4.4退化与循环……………………………………………………………………第五章单纯形法的矩阵表示………………………………………………………总结……………………………………………………………………………………参考文献………………………………………………………………………………第一章 单纯形法的提出1.1 单纯形法的提出背景单纯形法是1947年由George Bernard Dantzing(1914-2005)创建的，单纯形法的创建标志着线性规划问题的诞生。

线性规划问题是研究在线性约束条件下，求线性函数的极值问题。

然而，对这类极值问题，经典的极值理论是无能为力的，只有单纯形法才能有效解决这类极值问题的求解。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
出基变量的确定：最小比值原则
Page 25
min{300/1，400/1，250/1}= 250， s3出基
以进基变量系数列中的正数 为分母，以相应的方程右端 常数为分子,系数为0和负不 考虑。
5.1 单纯形法的基本思路和原理
Page 26
思考：若不按最小比值法确定出基变量会 怎么样？
请大家计算一下：
本解。
方程： 5
5.1 单纯形法的基本思路和原理
x2+s1=300， x2=400，
Page 6
x2+s3=250.
x1=0，x2=400，s1=－100，s2=0，s3=－150 由于在这个基本解中 s1= － 100 ， s3= － 150 ，不满足该线性规划 s1≥0，s3≥0的约束条件，显然不是此线性规划的可行解，一个 基本解可以是可行解，也可以是非可行解，它们之间的主要区别 在于其所有变量的解是否满足非负的条件。 基本可行解:我们把满足非负条件的一个基本解叫做基本可行
5.1 单纯形法的基本思路和原理
单纯形法的基本思路：
Page 12
首先找到一个顶点；
然后判断它是否最优； 如果不是，则通过更换顶点的方式找到更优的顶点 直到找到最优顶点。
5.1 单纯形法的基本思路和原理
Page 13
由于在线性规划的标准型中要求bj都大于等于零，如果我们能找到 一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成 （至于各列向量的前后顺序是无关紧要的事）例如，
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要好得多。 24
5.1 单纯形法的基本思路和原理

jJ
j
x j 是一个小于等于零的数，要使z
的值最大，显然 j x j 只有为零。
jJ
17
5.1 单纯形法的基本思路和原理
2.最优解判别定理
Page 18
我们把这些xj取为非基变量(即令这些xj的值为零)，所求得的 基本可行解就使目标函数值最大为z0。 **对于求目标函数最小值的情况，只需把 j≤0改为 j≥0
0 0 1 1 0 0 0 1 0 那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单 位矩阵各列向量组成的基一定是可行基。实际上这个基本可行解中 的各个变量或等于某个bj或等于零。
13
5.1 单纯形法的基本思路和原理
在本例题中我们就找到了一个基是单位矩阵。
Page 14
cn xn .
a1, n xn b1 , a2, n xn b2 , am,n xn bm , , n
b1 300 300, a12 1 b2 400 400, a22 1 b3 250 250. a32 1
23
5.1 单纯形法的基本思路和原理
为非基变量。
Page 24
b3 其中 的值最小， s3 为出基变量，x2，s1，s2为基变量，x1，s3 a32
令非基变量为零，得 x2+s1=300,
5.2 单纯形法的表格形式
Page 30
在讲解单纯形法的表格形式之前，先从一般数学模型里推导出 检数 j 的表达式。 可行基为m阶单位矩阵的线性规划模型如下（假设其系数矩阵 的前m列是单位矩阵）：
max z c1 x1 c2 x2 x1 a1, m1 xm1 x2 a2,m 1 xm 1
的非基变量为入基变量，在本例题中σ 2=100是检验数中最大的正数
，故选x2为入基变量。 20
5.1 单纯形法的基本思路和原理
进基变量的确定： 最大检验数原则，确保目标值增加最快。
Page 21
例中初始解1 ＝50， 2 ＝100， 则选x2 入基变量。
5.1 单纯形法的基本思路和原理
Page 8
P96习题1
P96习题2（1）——（5）
5.1 单纯形法的基本思路和原理
总结：
Page 9
1、可行域顶点对应的解必为基本可行解：有n-m个
变量取值为0，满足非负条件。
2、一个基对应一组基本解，可能可行，也可能不可
行；
3、最优解必定在基本可行解中；
单纯形法基本原理
Page 10
若在第一次迭代中不选s3出基，而让
S2或S1出基，会出现什么情况。
5.1 单纯形法的基本思路和原理
Page 27
若让S1出基，则新的基为(p2 ，p4 ，p5) ，求得解为
(0,300,0,100,-50)，非可行。
若让S2出基，则新的基为(p2 ，p3 ，p5) ，求得解为
(0,400,-100,0,150) ，非可行。 行。
2.
Page 22
在确定了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 。因为此解 满足非负条件，是基本可行解.
5.1 单纯形法的基本思路和原理
Page 5
非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有n
－m个。
基本解 : 由线性代数的知识知道，如果我们在约束方程组系数矩
阵中找到一个基，令这个基的非基变量为零，再求解这个 m元线
性方程组就可得到唯一的解了，这个解我们称之为线性规划的基
1 1 0 B3 1 0 0 在此例中我们不妨找到了 1 0 1 为A的一个基，令这 个基的非基变量x１，s2为零。这时约束方程就变为基变量的约束
一、找到初始基本可行解
目标函数： max 50x1+100x2 约束条件：x1+x2≤300， 2x1+x2≤400， x2≤250. xj≥0 （j=1，2） 3
5.1 单纯形法的基本思路和原理
1 1 1 0 0 它的标准形式系数矩阵 , A ( p1 , p 2 , p3 , p 4 , p5 ) 2 1 0 1 0 0 1 0 0 1
Page 4
已知 A 是约束条件的 m×n阶系数矩阵，其秩为 m 。此例题中， A 的
秩为3,A的秩m小于此方程组的变量的个数n 基：已知 A 是约束条件的 m×n 系数矩阵，其秩为 m 。若 B 是 A 中 m×m阶非奇异子矩阵（即可逆矩阵），则称 B是线性规划问题中 的一个基。 基向量：基B中的一列即称为一个基向量。基B中共有m个基向量。 非基向量：在A中除了基B之外的一列则称之为基B的非基向量。 基变量：与基向量pi相应的变量xi叫基变量，基变量有m个。 4
凸集：如果集合C中任意两个点X1、X2，其连线上的所有点 也都是集合C中的点，称C为凸集。
凸集
顶点
凸集
不是凸集
单纯形法基本原理
Page 11
定理1：若线性规划问题存在可行解，则该问题的可行域是 凸集。 定理2：线性规划问题的基可行解X对应可行域(凸集)的顶 点。 定理3：若问题存在最优解，一定存在一个基可行解是最优 解。（或在某个顶点取得）
讲述。
14
5.1 单纯形法的基本思路和原理
二、 最优性检验 1. 最优性检验的依据——检验数σ
j
Page 15
一般来说目标函数中既包括基变量，又包括非基变量。 现在我们要求只用非基变量来表示目标函数，这只要在约束等 式中通过移项等处理就可以用非基变量来表示基变量，然后用非基 变量的表示式代替目标函数中基变量，这样目标函数中只含有非基 变量了，或者说目标函数中基变量的系数都为零了。
结论：按最小比值原则确定出基变量，可确保解可
5.1 单纯形法的基本思路和原理
单纯形法的思路 找出一个初始可行解
Page 28
是否最优 循 环 否
是
最优解 结束
转移到另一个基本可行解 （找出更大的目标函数值） 核心是：变量迭代
单纯形法的基本思路和原理
单纯形法求解思路总结： 第一步
找到初始可行基（单位矩阵）； 第二步 检验解是否为最优（所有检验 数≤0）； 第三步 基变换（最大检验数原则确定 进基变量，最小比值原则确定出基变 量）。 重复以上步骤直到得到最优解。
此时目标函数中所有变量的系数即为各变量的检验数，把变量 xi的检验数记为σ i。显然所有基变量的检验数必为零。
15
5.1 单纯形法的基本思路和原理
二、 最优性检验 1. 最优性检验的依据——检验数σ
j
Page 16
在本例题中目标函数为 50x1+100x2 。由于初始可行解中 x1 ， x2 为非基变量，所以此目标函数已经用非基变量表示了，不需要再代 换出基变量了。这样我们可知 σ 1=50 ， σ 2=100 ， σ 3=0 ， σ 4=0 ， σ 5=0。
16
5.1 单纯形法的基本思路和原理
2.最优解判别定理
Page 17
对于求最大目标函数的问题中，对于某个基本可行解，如果 所有检验数 j ≤0，则这个基本可行解是最优解。 下面我们用通俗的说法来解释最优解判别定理。设用非基变量表示
的目标函数为如下形式
z z0 j x j
jJ
由于所有的xj的取值范围为大于等于零，当所有的 j 都小 于等于零时，可知
18
5.1 单纯形法的基本思路和原理