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

单纯形法

  • 格式：doc
  • 大小：542.00 KB
  • 文档页数：56

下载文档原格式

  / 56

合集下载

单纯形法

单纯形法

单纯形法simplex method求解线性规划问题的通用方法。

单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。

它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。

顶点所对应的可行解称为基本可行解。

单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。

因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。

如果问题无最优解也可用此法判别。

根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。

使目标函数达到最大值（或最小值）的可行解称为最优解。

这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。

求解线性规划问题的目的就是要找出最优解。

最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。

单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。

②若基本可行解不存在，即约束条件有矛盾，则问题无解。

③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。

④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。

⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。

用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。

现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得。

第三节 单纯形法

第三节 单纯形法

θi 32.5 40 25
5 7. 5
注意：单纯形法中， 注意：单纯形法中， 1.每一步运算只能用矩阵初等行 1.每一步运算只能用矩阵初等行 变换； 变换； 2.表中第3列的数总应保持非负 2.表中第 表中第3 （≥ 0）； 3.当所有检验数均非正（≤ 0） 3.当所有检验数均非正 当所有检验数均非正（ 得到最优单纯形表。 时，得到最优单纯形表。
8
1.初始单纯形表： 1.初始单纯形表： 初始单纯形表
CB XB b b1 b2 ┇ bm f
m
cn+1 xn+1 cn+2 xn+2 ┇ ┇ cn+m xn+m m -z
c1 x1 a11 a21 ┇ am1 σ1
… … … … ┇ … …
cn xn a1n a2n ┇ amn σn
m
cn+1 xn+1 1 0 ┇ 0 m 0
-z
15
在最优单纯形表中，非基变量的检验数不 在最优单纯形表中， 是正数,于是得到最优解为X 是正数,于是得到最优解为X*=(15,10,0,0,45)T 最优目标值为z =32500。注意到非基变量x 最优目标值为z*=32500。注意到非基变量x4 的检验数是0 如果选x 为进基变量， 的检验数是0，如果选x4为进基变量，迭代 还可以进行下去，但是最优值不会增大， 还可以进行下去，但是最优值不会增大， 而只有最优解改变，这就是多解的情况。 而只有最优解改变，这就是多解的情况。 下面再迭代一步，如表2 所示。 下面再迭代一步，如表2-9所示。
19
解：单纯形法求解过程如下表。 单纯形法求解过程如下表。
CB XB
0 0 0 -z 7 0 0 -z x1 x6 x7 x5 x6 x7

单纯形法

单纯形法

定理2.2 定理
在已知一个基本可行 初始基本可行解）的前提下， 解（初始基本可行解）的前提下， 使用单纯形法求解线性规划时， 使用单纯形法求解线性规划时，若 每次迭代得出的基本可行解的基变 量均大于零（称为非退化）， ），则算 量均大于零（称为非退化），则算 法必有限步终止。 法必有限步终止。
P22
min z = 9 10 x1 +27 x3 s.t. x2 = 5 + x1 3x3 x4 = 6 2 x1 + 4 x3 x1 , x2 , x3 , x4 ≥ 0 T 是否为(2.9)的最优解 判断 (0,5,0,6) 是否为(2.9)的最优解
1 0 0 0 1 0
T
(2.9)
-2 1 7
0 0 1 0 -1/5 2/5 3/5 1/5
4 2 5 16 3 4 3 17
从表中知（ ， ， ， ， ） 从表中知（4，3，3，0，0）T为最优 略去松弛变量， 解，略去松弛变量，得：
x = (4,3)
T
——最优解 最优解Fra bibliotekz = 17
——最优值 最优值
§2.5
大M法 法
引入：问题提出， 引入：问题提出，当初始 基本可行解不知道时， 基本可行解不知道时，如何 求解？ 求解？ 先利用容许的运算使右列 为非负， 为非负，然后在中心部位人 工地添加一个单位子块。 工地添加一个单位子块。
最优解的读法： 最优解的读法： 单位子块中1所对应的变量取相应右列的值， 单位子块中 所对应的变量取相应右列的值，不在 所对应的变量取相应右列的值 单位子块位置中的变量取值为0。 单位子块位置中的变量取值为 。而右下端元素变号 即为LP的最优值 的最优值。 即为 的最优值。 单纯形法的步骤： 单纯形法的步骤：

运筹学第5章 单纯形法

运筹学第5章 单纯形法

0 0 1
在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的 各列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基 本可行解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作 为初始可行基，我们将构造初始可行基，具体做法在以后详细讲述。
8Leabharlann §1 单纯形法的基本思路和原理
二、 最优性检验 所谓最优性检验就是判断已求得的基本可行解是否是最优解。
5
§1 单纯形法的基本思路和原理
线性规划解之间的关系：
1.可行解与最优解： 最优解一定是可行解，但可行解不一定是最优解。
2. 可行解与基本解： 基本解不一定是可行解，可行解也不一定是基本解。
3. 可行解与基本可行解： 基本可行解一定是可行解，但可行解不一定是基本可行解。
4. 基本解与基本可行解： 基本可行解一定是基本解， 但基本解不一定是基本可行解。
9
§1 单纯形法的基本思路和原理
2.最优解判别定理
对于求最大目标函数的问题中，对于某个基本可行解，如
果所有检验数 j≤0，则这个基本可行解是最优解。 下面我
们用通俗的说法来解释最优解判别定理。设用非基变量表示
的目标函数为: z z0 j xj jJ 由于所有的xj的取值范围为大于等于零，当所有的 j都小
由线性代数的知识知道，如果我们在约束方程组系数矩阵中找
到一个基，令这个基的非基变量为零，再求解这个m元线性方程组就
可得到唯一的解了，这个解我们称之为线性规划的基本解。
在此例中我们不妨找到
1 1 0 B3 1 0 0
为A的一个基，令这个基的非
1 0 1
基变量x１，s2为零。这时约束方程就变为基变量的约束方程：
第五章 单 纯 形 法

运筹学单纯形法

运筹学单纯形法

单纯形表
max z=x1+2x2 s.t. x1+x23 x2 1 x1, x2 0
Cj CB XB b 0 0 Z X3 3 X4 1 0 1 2 0 0
标准化
max z=x1+2x2 s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40
X1 X2 X3 X4 1 0 1 1 1 2 1 0 0 0 1 0
Z=x1+2x2 x1+x2+ x3 =3 x2 +x4=1 单纯形表
Cj
1
2
0
0
单纯形法原理 单纯形表 CB XB b
z=x1+2x2 x3 =3-x1-x2 x4=1 -x2
x2进基，x4离基
X1 X2 X3 X4

3/1 11
0
1 0
1 1
1 1
2 2 0 1 0 2 0 1 0 0 1 0 -1 0
max z=x1+2x2 s.t. x1+x2+x3 =3 x2 +x4=1 x1, x2, x3, x40
x1=0
(x1,x2,x3,x4)= (0,1,2,0), z=2 C (x1,x2,x3,x4)= (2,1,0,0), z=4,最优解
B
x4=0 x3=0
(x1,x2,x3,x4)= (0,0,3,1), z=0
1 0
0 0
0 1
0
CB XB b 0 2 Z Cj CB XB b 1 2 Z X1 2 X2 1 4 X3 2 X2 1 2 1 1 0 0
X1 X2 X3 X4 1 0 1 1 0 0 0 -1 1 -1

运筹学单纯形法

运筹学单纯形法
总结：①在迭代过程中要保持常数列向量非负，这能确保基 可行解旳非负性。最小比值能做到这一点。 ②主元素不能为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

单纯形法

单纯形法

基可行解单纯形法是针对标准形式的线性规划问题进行演算的，任何线性规划问题都可以化为标准形式。

min cx f = （1） s.tb Ax =（2） 0≥x （3）其中Tmmn m m n n Tn n b b b b a a a a a a a a a A x x x x c c c c )...,(,..................,),...,,(),,...,(212122221112112121=⎪⎪⎭⎪⎪⎬⎫⎪⎪⎩⎪⎪⎨⎧===假设1≥≥m n ，并设系数矩阵A 的秩为m ，即设约束方程（2）中没有多余的方程，用jp 表示A 的第j 列，于是（2可写成bp xmk j j=∑=1（4）矩阵A 的任意一个m 阶非奇异子方阵为LP 的一个基（或基阵），若),...,(21jm j j p p p B = （5）是一个基，则对应变量jm j j x x x ,...,,21，称关于B 的基变量，其余变量成为关于B 的非基变量，若令非基变量都取零值，则（4）变为bp xmk jk jk=∑=1（6）由于此方程组的系数矩阵B 是满秩方阵，故知（6）有唯一解，记为Tjnj j x x x ),...,,()0()0(2)0(1于是按分量{}{}),...,,\,...2,1(0),....3,2,1(21)0(m j jkjk j j j n j x m k x x ∈===所构成的向量)0(x 是约束方程组b Ax =的一个解，称此)0(x 为LP 的对应于基B 的基解（或基本解），也可称为方程组b Ax =的一个基解，如果)0(x 为一基解，且满足0)0(≥x 即它的所有分量都非负，则称此)0(x 是LP 的一个基可行解，基可行解对应的基称为可行基。

设对应基阵),...,(21m p p p B =，即m x x x ,...,,21为基变量，n m m x x x ,...,,21++ 是非基变量，记),...,,(),...,,(),...,,(212121n m m Tn m m n Tm B p p p N x x x x x x x x ++++===从而A=（B,N ）,相应地分划),(N B c c c =,约束方程（2）可以写成b x x N B n B =⎪⎪⎭⎫⎝⎛),( 即b Nx Bx N B =+由此解得N B Nx B b B x 11---= （7）这是用非基变量表达基变量的公式 在（7）中令 0=N x 而知()TmB x x x x b B ),...,,()0()0(2)0(101==-如记则（7）相当于将（7）代入目标函数公式中所得非基变量表达目标函数式为或者目标函数在即则目标函数的表达式写成求解线性规划问题 min 4212x x x f +-=t s .223531=++x x x22432=+-x x x5532=++x x x)5,4,3,2,1(0 =≥j x j已知初始可行基,其对应典式为于是可列出0B 对应的单纯形表)(0B T ,如表所示从表可以看出，检验数中仅有02≥ λ，故取2x 为进基变量，由于最小比值12200min2=⎭⎬⎫⎩⎨⎧>i i b b b i在第2行取得，故取第2行对应的基变量4x 为离基变量，于是元素122=b 是上表的枢元 为求出新基()3211p p p B =对应的单纯形表，对)(0B T 作初等形变换，使2x 对应的列变为单位列向量。

§13 单纯形法

§13 单纯形法

单纯形法举例（续）
以上数学描述说明了每生产一件产品Ⅱ，需要 用掉各种资源数为(2，0，4)，由这些资源中的薄弱 环节，就确定了产品Ⅱ的产量。
这里就是由原材料B的数量确定了产品Ⅱ的产量 x2=12/4=3件。
14
Operational Research
单纯形法举例（续）
为了求得以x3, x4, x2为基变量的一个基可行解和
x1, x2, …, xm 为松弛变量
28
Operational Research
初始基可行解的确定（续）
于是含有m×m单位矩阵，以B 作为可行基。
1


B P1, P2 ,
Pm



1


1
29
Operational Research
初始基可行解的确定（续）
将(*)式每个等式移项得
单纯形法的表现形式： 代数法 表格法 矩阵法
2
Operational Research
单纯形法的基本原理
一般线性规划问题具有线性方程组的变量数大 于方程个数，这时有不定的解。但可以从线性方程 组中找出一个个的单纯形，每一个单纯形可以求得 一组解，然后再判断该解使目标函数值是增大还是 变小，决定下一步选择的单纯形。这就是迭代，直 到目标函数实现最大值或最小值为止，这样问题就 得到了最优解。
单纯形法举例（续）
将(1-7)式代入目标函数(1-1)式得到
z

9

2x1

3 4
x5
(1 8)
令非基变量x1=x5=0，得到z=9，并得到另一个
基可行解X(1)。
X (1) (0, 3, 2,16, 0)T

运筹学第2章 单纯形法

运筹学第2章 单纯形法

所有检验数 j 0 ，则这个基本可行解是最优解。
n
z z0 j x j
j m 1
m
j ciaij c j =CTBa j c j
i 1
m
m
z0 c j x j = cibi =CBT b
j 1
i 1
✓对于求目标函数最小值的情况，只需 σj≤0
0
XB
b
x1
-1 x5 0
0
0 x4 3
1
-3 0
0
00
x2
x3
x4
0
-2 0
2
-2 1
0 10
-1 bi/aik
x5
1
0
0
29 2020/3/4
2、无界解
在求目标函数最大值的问题中，所谓无界解是指在约束条件 下目标函数值可以取任意的大。
•存在着一个小于零的检验数，并且该列的系数向量的每个元素 都小于或等于零，则此线性规划问题是无界的，一般地说此类
2x1 x2 x3 x5 2
s.t. x1 2x2
x4
3

x1,
x2 , x3, x4 , x5 0
✓添加人工变量x5来人为的创造一个单位矩阵作为基 ✓M叫做罚因子，任意大的数。 ✓人工变量只能取零值。必须把x5从基变量中换出去，否 则无解。
cj
3
2
00
CB XB
2020/3/4
14
(2)出基变量和主元的确定——最小比值规则
min

bi aik
aik

0


bl alk
确定出基变量的方法：把已确定的入基变量在各约束方程中的正的系数

单纯形法

单纯形法

四、单纯形法的实现——单纯形表
例1：煤电油例 Max Z=7 x1 +12x2 9 x1 +4x2≤360 化为标准型 s.t. 4x1 +5x2 ≤200 3 x1 +10x2 ≤300 x1 , x2≥0 s.t. Max Z=7 x1 +12x2 9 x1 +4x2 +x3 4x1 +5x2 3 x1 +10x2 x1 ,…,x5≥0 +x4 =360 = 200
•
“≥”型约束，减松弛变量；
练习1.3 请将例1.1的约束化为标准型
Maxz = 7 x1 + 12 x 2 ⎧9 x1 + 4 x 2 ≤ 360 ⎪4 x1 + 5 x 2 ≤ 200 s.t.⎨ 3x1 + 10 x 2 ≤ 300 ⎪x , x ≥ 0 ⎩ 1 2
则约束化为
= 360 ⎧9 x1 + 4 x 2 + x3 ⎪4 x + 5 x 2 + x4 = 200 s.t.⎨ 1 3 x1 + 10 x 2 + x5 = 300 ⎪x , x , x , x , x ≥ 0 ⎩ 1 2 3 4 5
例4 下面为某线性规划的约束
=1 ⎧ x1 + 2 x2 + x3 ⎪ + x4 = 3 ⎨2 x1 − x2 ⎪ x1 , , x4 ≥ 0 ⎩ 请例举出其基矩阵和相应的基向量、基变量。
解：
本例中， A = ⎡1 2 1 0⎤，A中的2阶可逆子阵有 ⎢ 2 − 1 0 1⎥ ⎦ ⎣
问题：本例的A中一共有几个基？—— 6个。
易见，增加的松弛变量的系数恰构成一个单位阵I。
一般地，记松弛变量的向量为 X s，则

运筹学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阶排列阵

2.2 单纯形法

2.2 单纯形法

不过,若原(LP)是非退化的,则其任一个基本可行
解均是非退化的,从而不会出现此问题.
2＞ 检验数向量 有不只一个正分量. 理论上任意可选取一个正分量作为定理中的 k
0
由 Th3 , k x k : 0 1 , 目标函数的值减少 k

ˆ c x c x k
T T

T
x
目标函数的典式
令
j c B A j c j , j 1, , n 检验数
T
常数项
z0 c x cB b
T T
A1 , , Am
Aj e j

B
1
B Im
XJTU
第二章 线性规划
T T
OR
j 1, , m


T
j c B A j c j c B e j c j c j c j 0,
cB B
T 1
Ac
T
T
1 , , n
0 , cB BT 1 NhomakorabeaT
对应于 x 的
B , N
T



N cN

检验数向量
b 对应于基本可行解 x , 原标准形式(LP) 0

m in z z 0 s .t. xB B x 0
单纯形法求解原LP问题：或者求得一最优解，或者 判定原LP问题无界。
XJTU
设原LP问题为：
m in c x s .t.
T
第二章 线性规划
OR
Ax b 0 x 0
D
对此问题引入m个人工变量 x a ( x n+1 , , x n+m ) ，

运筹学第2章单纯形法

运筹学第2章单纯形法
==８ ==6
① ② ③
－２Ｘ４＋Ｘ５ ＝１２
得到新的基本可行解 X1 =(0,6,8,0,12)T
(1)、决定进基变量：1=--3, X1进基 (2)、决定离基变量：最小比值规则来确定主 元与离基变量.
则Xl为进基变量。 MIN(8/1,-,12/3)=12/3 此时可以确定X5为离基变量
Z
X(0) =(0, 0, 10, 15 )T
Z0 =0
Z-30X1-20X2 =0 选中X1从0↗，X2 =0 X3=10-(-X1 )0
X4=15-(-3X1 )0 求X1， X1→+ ,Z→+
2.2.3 单纯形法计算之例
2-3 人工变量法 (Artificial Variable)
+1/2X4
+X5 =42 =6
X3 +2/3X4 -1/3X5 =4
X2 +1/2X4
X1 -2/3X4+1/3X5=4 令X4 =X5 =0 X =(4, 6, 4, 0, 0)T Z =42
。此时4=1/2,
Z值不 再增大了,X值是最优基本解
5
=1,
* T * 即:X =(4,6) ,Z =42
检验数
当目标方程中基变量系数全为0时，非基 变量的系数可以作为检验当前的基本可 行解是否最优的标志，称之为检验数。
(2)、判定解是否最优 Z-3X1-5X2 =0 当X1从0↗或X2从0↗ Z从0↗ ∴ X0 不是最优解
(3)、由一个基可行解→另一个基可行解。 ∵ -5<-3 选X2从0↗，X1 =0 X3 =8 X4 =12-2X2 0 X2 12/2
N
沿边界找新 的基本可行解
结束

第五章 单纯形法

第五章 单纯形法
➢ 3、那有没有办法在求出解之前保证我 们取得的基为可行基？
➢ 解决办法：保证右端项非负，找到一个 单位矩阵，必定是一个可行基。
二、单纯形法的基本思路和原理
➢ 如范例系数阵：
右端项非负
1 1 1 0 0 300 2 1 0 1 0 400 0 1 0 0 1 250
存在3阶单位阵 （初始可行基）
二、单纯形法的基本思路和原理
➢ 如令x1＝0，x2＝0，则 ➢ x3＝300，x4＝400，x5＝250 ➢ 可得到解（0，0，300，400，250）
一、问题的提出
➢ 又如：令x3＝0，x5＝0， ➢ 由约束条件： ➢ x1+x2+x3＝300 ➢ 2x1+x2+x4＝400 ➢ x2+x5＝250 ➢ 可得到解（50，250，0，50，0）
27500-50x3-50x5
二、单纯形法的基本思路和原理
➢ 典式Z= 27500-50x3-50x5
➢ 如果x3增加1，Z会怎样？ ➢ 答案：Z减少50。 ➢ 如果x5的值增加1，Z会怎样？ ➢ 答案：Z减少50 。 ➢ 可见要使Z增加，只有使x3和x5减少。
二、单纯形法的基本思路和原理
➢ x3，x5的取值是否有减少的可能？ ➢ 分析：该解中非基变量 x1，x2的取值为
一、问题的提出
❖ 线性规划解的集合关系：
基
可
本最
基
行
可优
本
解
行解
解
解
一、问题的提出
❖显然，将搜索范围控制在基本可行 解内，将大大减少搜索工作量。
❖但是，即使取得一个基，得到的解 还不一定可行。
❖如何才能保证取得一个可行基呢？
一、问题的提出

单纯形法

单纯形法

XB =B-1b-B-1NX N 代入目标函数，使目标函数用非基变量
表示，即：
Z=cT X=(cTB
cTN) XB XN =cTBXB +cTN XN =cTB (B-1b-B-1NXN )+cTN XN
=cTBB-1b+(cTN -cTBB-1N)XN cBT B-1b+σNXN cBT B-1b+(σm+1,σm+1,
Z=CTBB-1b+(σm+1 ,
σm+k ,
xm+1

σ
n
)




CTB B-1b+σ m+k


xn
因为 m+k 0, 故当λ→+∞时，Z→－∞。
18
表格单纯形法
B
N
b
CBT
CNT
I
B-1N
B-1b
0
CNT -CBT B-1N
19
可将这些重要结论的计算设计成如下一个简单的表格， 即单纯形表来完成：
min z=－6x1－4x2
x3 =100－2x1－3x2
+x4 =120－4x1－2x2
令 有 则有：
XN=(0,0)T XB=(100,120)T X（1）=（0，0，100，120）T为对应于基B1的基可行解。
问：
X（1）是否最优呢？——否
因为： x1和x2在目标函数中的系数为正，当x1↑，z ；x2↑，z 。
础上寻找一个新的基本可行解，并使目标函数值有所改善。
具体做法是：
先从检验数为负的非基变量中确定一个换入变量，使它从非基

第五章 单纯形法

第五章 单纯形法

3.人工变量法
用单纯形法求最小值问题，与求最大值问题 类似，其区别在于判别数为零或者正值，即
Cj-Zj≥0时得到最优解，在决定“换入”及“换 时得到最优解，在决定“换入” 时得到最优解 变量时， 出”变量时，取Cj-Zj为负且绝对值最大者为主 为负且绝对值最大者为主 元列，其余步骤同求最大值问题。 元列，其余步骤同求最大值问题。 这种求线性规划的方法，称为“人工变量法” 这种求线性规划的方法，称为“人工变量法”或 称为“ 称为“大M”法，这就是当一个 线性规划问题在 法 仍不能提供基本可行解时， 增加了松弛变量后 仍不能提供基本可行解时， 需要采用“人工变量” 需要采用“人工变量”来获得一个初始的基本可 行解。 行解。
将线性规划问题转化为标准型 编制初始单纯行表 判别基本可行解是否为最优 找出“换入” 换出”变量， 找出“换入”或“换出”变量，以便进行换基
对于求最大值问 题，全部判别数 为零与负数时， 为零与负数时， ≤0， 即Cj-Zj ≤0，得最 优解
先找出主元行与主元列：对于求极大值问题， 先找出主元行与主元列：对于求极大值问题，取Cj-Zj 为正数且最大者所在的列为主元列， 为正数且最大者所在的列为主元列，取bi/aij为正数且最 大者所在的行为主元行， 大者所在的行为主元行，主元行与主元列之交点元素称 为主元素，在右上方记“ ” 为主元素，在右上方记“*”主元素正上方对应的变量 换入”变量，主元素左边对应的基变量为“换出” 为“换入”变量，主元素左边对应的基变量为“换出” 变量。 变量。
第五章
单纯形法
5.1 线性规划求解的相关概念
一、相关定理 定理1 线性规划问题的可行解集S是凸集。 定理1 线性规划问题的可行解集S是凸集。 定理2 线性规划问题的基本可行解X 定理2 线性规划问题的基本可行解X对应于可 行域S的顶点。也就是说， 行域S的顶点。也就是说，可行域的顶点就 是线性规划问题的基本可行解。 是线性规划问题的基本可行解。 定理3 若线性规划问题有最优解， 定理3 若线性规划问题有最优解，它一定在 其可行域的顶点上达到。 其可行域的顶点上达到。

单纯形法

单纯形法

单纯形法（不可以解空集问题，无初始解）一、单纯形法的基本思想1、顶点的逐步转移即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。

2．需要解决的问题：(1)为了使目标函数逐步变优，怎麽转移？(2)目标函数何时达到最优——判断标准是什么？（3）初始解的寻找二、单纯形法原理（用代数方法求解LP）第一步：引入非负的松弛变量（x3 x4 x5）和剩余变量（算完后剩余的资源）x3,x4,x5, 将该LP化为标准型第二步：寻求初始可行基（单位阵对应的），确定基变量第三步：写出初始基本可行解（很多之中找一个，必令原x为0）和相应的目标函数值两个关键的基本表达式：① 用非基变量表示基变量的表达式② 用非基变量表示目标函数的表达式第四步：分析两个基本表达式，看看目标函数是否可以改善？① 分析用非基变量表示目标函数的表达式非基变量前面的系数均为正数（必为负数才可以），所以任何一个非基变量进基都能使Z值增加通常把非基变量前面的系数叫“检验数”②选哪一个非基变量进基？排在最前面的负检验数对应的非基变量③确定出基变量“最小比值原则”（或θ原则）见本如果x2≤0，会出现什麽问题？最小比值原则会失效！基变换新的基变量——x2, x3,x4；新的非基变量x1, x5；写出用非基变量表示基变量的表达式：可得新的基本可行解X（1）=（0,3,2,16,0）T⑤写出用非基变量表示目标函数的表达式:检验数仍有正的第五步：上述过程何时停止？当用非基变量表示目标函数的表达式中，非基变量的系数（检验数）全部非正（0时表无穷解，负时表唯一解）时，当前的基本可行解就是最优解!为什麽？分析用非基变量表示目标函数的表达式，如果让负检验数所对应的变量进基，目标函数值将下降！（2）表格设计依据：将-Z 看作不参与基变换的基变量，把目标函数表达式改写成方程的形式，和原有的m 个约束方程组成一个具有n+m+1个变量、m+1个方程的方程组：取出系数写成增广矩阵的形式：⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛+++01100001000010212121222221111211mn n n n m mn m m nnc c c c c c b a a a b a a a b a a a-Z ，X n+1，…，X n+m 所对应的系数列向量构成一个基用矩阵的初等行变换将该基变成单位阵,这时 变成0，相应的增广矩阵变成如下形式：⎪⎪⎪⎩⎪⎪⎪⎨⎧=+++++-=++++=++++=+++++++++++01122112211222222121111212111m n m n n n n n mm n n mn m m n n n n n n x c x c x c x c x c Z bx x a x a x a b x x a x a x a b x x a x a x a其中， ， j=1，2，…，n ；增广矩阵的最后一行就是用非基变量表示目标函数的表达式, (j=1,2,…,n)就是非基变量的检验数。

§2.2单纯形法

§2.2单纯形法

Maxz 7 x 12 x
1
Maxz 7 x1 12x2 0x3 0x4 0x5
3) 当模型中有某变量 xk 没有非负要求， 称为自由变量, 则可令 x x x ,x ,x 0
/ // / // k k k k k
化为标准型。 4) 若某个bi<0,两边乘(-1) 5) 对负变量 x j 0 ，换元设 xj x j 0
2. 最优性检验
问题：用什么检验？ —— 目标。
1 1
X 而目标z CX (C C ) C (B b B N X ) C X X C B b (C C B N ) X

记 C C B N，则当 0 时，当前基可行解为最 优。
1
方法：计算每个变量 x 的检验数 c C B P ,
1
若 0, 则当前解为最优；否则 非最优。
问题：非最优的特征为何？
至少有某个检验数 0。
3. 寻找更好的基可行解（换基迭代） （基变换）
由于基可行解与基对应，即寻找一个新的基可行 解，相当于从上一个基B0变换为下一个新的基B1，因此， 本步骤也称为基变换。 进基
1 1 1 1
360 90 4
[ ] 中表示进基列与出基行的交叉元，下一张表将实行以它为主 元的初等行变换（称高斯消去）。方法是：先将主元消成1，再用此1将 其所在列的其余元消成0。
特点： (1) 目标函数求最大值 (2) 约束条件都为等式方程； (3) 非负约束：决策变量xj为非负； 右端常数项bi非负。
标准型的矩阵表示：
Maxz CX AX b s.t. X 0
其中，A 的秩为m（m n） , b 0。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

线性规划及单纯形法线性规划问题及其数学模型两个变量问题的图解法单纯形法原理单纯形法计算步骤人工变量及其处理方法应用举例线性规划问题及其数学模型一、问题的提出资源有限和目标确定在生产管理和经营活动中，经常会遇到两类问题：一类是（资源有限）如何合理的使用现有的劳动力、设备、资金等资源，以得到最大的效益；另一类是（目标一定）为了达到一定的目标，应如何组织生产，或合理安排工艺流程，或调整产品的成分等，以使所消耗的资源（人力、设备台时、资金、原材料等）为最少。

例：(1)配载问题：某种交通工具（车、船、飞机等）的容积和载重量一定，运输几种物资，这些物资有不同的体积和重量，如何装载可以使这种运输工具所装运的物资最多？(2)下料问题：某厂使用某种圆钢下料，制造直径相同而长度不等的三种机轴，采用什么样的下料方案可以使余料为最少？(3)物资调运：某种产品有几个产地和销地，物资部门应太如何合理组织调运，从而既满足销地需要，又不使某个产地物资过分积压，同时还使运输费用最省？(4)营养问题：各种食品所含营养成分各不相同，价格也不相等，食堂应该如何安排伙食才能既满足人体对各种营养成分得需要，同时又使消费者得经济负担最少？此外，在地质勘探、环境保护……等方面也都有与上述情况类似的问题。

例1某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。

生产每吨药品所需要的维生素量分别为30K g ，20K g ，所占设备时间分别为5台班，1台班，该厂每周所能得到的维生素量为160k g ，每周设备最多能开15个台班。

且根据市场需求，甲种产品每周产量不应超过4t 。

已知该厂生产每吨甲、乙两种产品的利润分别为5万元及2万元。

问该厂应如何安排两种产品的产量才能使每周获得的利润最大？解：设该厂每周安排生产甲、乙两种药品的产量分别为x 1,x 2吨，则有⎪⎪⎩⎪⎪⎨⎧≥≥≤≤+≤++=04155162325max 211212121x x x x x x x x x z例2 喜糖问题设市场上有甲级糖和乙级糖，单价分别为20元/斤，10元/斤。

今要筹办一桩婚事，筹备小组计划怎样花费不超过200元，使糖的总斤数不少于10斤，甲级糖不少于5斤。

问如何确定采购方案，使糖的总斤数最大。

解：设采购甲、乙两种糖各x 1,x 2斤 则二、线性规划问题的数学模型1. 从上述两个例子可以看出，它们有3个共同点(1)每个问题都有一组变量——称为决策变量 (2)都有一个关于决策变量的函数(3)每个问题都有一组决策变量需满足的约束条件2. 线性规划问题定义：将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规⎪⎪⎩⎪⎪⎨⎧≥≥≥≥+≤++=0502001020max 211212121x x x x x x x x x z划问题。

3. 建立线性规划问题的数学模型步骤(1)确定问题的决策变量(2)确定问题的目标，并表示为决策变量的线性函数(3)找出问题的所有约束条件，并表示为决策变量的线性方程或不等式4. 线性规划的数学模型假定线性规划问题中含n 个变量，分别用x j (j =1,…,n )表示，在目标函数中，x j 的系数为c j (通常称为价值系数)。

x j 的取值受m 项资源的限制，用b i (i =1,…,m )表示第i 种资源的拥有量，用a i j 表示变量x j 的取值为一个单位时所消耗或含有的第i 种资源的数量(通常称为技术系数或工艺系数)。

则上⎪⎪⎪⎩⎪⎪⎪⎨⎧⋅⋅⋅=≥≥=≤+⋅⋅⋅++⋅⋅⋅⋅⋅⋅≥=≤+⋅⋅⋅++≥=≤+⋅⋅⋅+++⋅⋅⋅++=),,1(0),(),(),(max(min)221122222121112121112211n j x b x a x a x a b x a x a x a b x a x a x a x c x c x c z j m n mn m m n n n n nn述线性规划问题的数学模型可以表示为5. 线性规划的标准型由于目标函数和约束条件内容和形式上的差别，线性规划问题有多种表达式，为了便于讨论和制定统一的算法，规定标准形式如下：(1)目标函数极大化；(2)约束条件为等式且右端项≥0；(3)决策变量≥0。

(1)一般表达式⎪⎪⎪⎩⎪⎪⎪⎨⎧⋅⋅⋅=≥=+⋅⋅⋅++⋅⋅⋅⋅⋅⋅=+⋅⋅⋅++=+⋅⋅⋅+++⋅⋅⋅++=),,1(0max 221122222121112121112211n j x b x a x a x a b x a x a x a b x a x a x a x c x c x c z j m n mn m m n n n n nn ⎩⎨⎧≥==0max X b AX CX z（2）Σ记号简写式 （3）矩阵形式式中C =(c 1,…,c n ) X =(x 1,….x n )’(4)向量形式⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=0...000,..., (3212)12222111211b b b b a a a a a a a a a A mn m m n n ⎪⎨⎧==∑max b x p CX z nj j式中C,X,b,0的含义与矩阵表达式相同，而P j=[a i j,a2j,…a m j](j=1,2,…,n)即A=(p1,p2,…p n)6将非标准形式化为标准形式（5种情况）(1)目标函数为求极小值min Z=CX,则作Z’=-CX, 即max Z’=-CX(2)右端项小于0只需将两端同乘(-1)，不等号改变方向，然后再将不等式改为等式。

例2x1+x2≥－6，－2x1－x2≤6，－2x1－x2＋x3＝6(3)约束条件为不等式当约束条件为“≤”时，则在左边加上一个新变量——称为松弛变量，将不等式改为等式。

如x1－2x2≤8，x1－2x2＋x3＝8，x3≥0；当约束条件为“≥”时，则在不等式左边减去一个新变量——称为松弛变量，将不等式改为等式。

如x1－2x2≥8，x1－2x2－x3＝8，x3≥0；(4)取值无约束的变量即可正可负，则可引入两个新变量，x ’，x ”，令x=x ’-x ”，其中x ’≥0，x ”≥0，将其代入线性规划模型即可。

(5) X ≤0的情况令x ’＝－x ，显然x ’≥0。

例 将下列线性规划模型化为标准形式解：令Z ’=-Z=-x 1+2x 2-3x 3 x 3=x 4-x 5 第一个约束条件左边加上松弛变量x6，第二个左边减去剩余变量x7，第三个两边同乘(-1)，则得到标准形式⎪⎪⎩⎪⎪⎨⎧≥≥-=++-≥+-≤+++-=无约束321321321321321005232732min x x x x x x x x x x x x x x x z ⎪⎪⎪⎨⎧=--=--+-=+-++⋅+⋅+--+-=5232700)(32'max 7542165421765421x x x x x x x x x x x x x x x x x x x z练习练习答案三、 两个变量问题的图解法图解法简单直观，对于两个变量的线性规划问题，可以通过在平面上作图的方法求解。

而且可以从中得到有关线性规划问题的许多重要结论，有助于我们理解线性规划问题求解方法的基⎪⎪⎩⎪⎪⎨⎧≥≤-=--≥++-≤++-++=无约束3213213213213210063244239232min x x x x x x x x x x x x x x x z ⎪⎪⎩⎪⎪⎨⎧≥=-++=--++=+-+++--=-06''3'32'44''22'39''''2''3'32''max 51332153321433213321x x x x x x x x x x x x x x x x x x x z本原理。

1. 图解法的基本步骤 (1)建立坐标系(2)图示约束条件，找出可行域 (3)图示目标函数，寻找最优解例 用图解法求解下列线性规划问题本例中目标函数与凸多边形的切点是B (2,5)，则X *=(2,5)为最优解，m a x Z =202. 线性规划问题的几种可能结果(1)有唯一最优解(如上例所示)⎪⎪⎩⎪⎪⎨⎧≥≥≤≤+≤++=04155162325max 211212121x x x x x x x x x z(2)有无穷多最优解(3)无界解(无最优解)⎪⎪⎩⎪⎪⎨⎧≥≥≤≤≤+--=0438242min 21122121x x x x x x x x z ⎪⎪⎩⎪⎪⎨⎧≥≥≤-≤+-+=0242max 21212121x x x x x x x x z(4)无可行解3. 由图解法得到的启示图解法虽然只能用来求解只具有两个变量的线性规划问题，但它的解题思路和几何上直观得到的一些概念判断，对将要学习的单纯形法有很大启示：(1)求解线性规划问题时，解的情况有：唯一最优解；无穷多最优解；无界解；无可行解。

(2)若线性规划问题的可行域存在，则可行域是一个凸集，顶点个数只有有限个。

(3)若可行域非空且有界则必有最优解，若可行域无界，则可能有最优解，也可能无最优解。

⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥≤≤≤+≥++=03482742max 2121212121x x x x x x x x x x z(4)若最优解存在，则最优解或最优解之一一定是可行域的凸集的某个顶点。

针对以上四个启示，得到新的解题思路（为单纯形法做铺垫）：先找出凸集的任一顶点，计算顶点处的目标函数值。

比较周围相邻顶点的目标函数值是否比这个大，如果为否，则该顶点就是最优解的点或最优解的点之一，否则转到比这个点的目标函数值大的另一顶点，重复上述过程，直到找到最优解。

四、有关线性规划问题的解的概念数学模型)3()2( )1((1)可行解与可行域：满足(2),(3)的解，称为线性规划问题的可行解，所有可行解的集合称为可行域。

(2)最优解：使目标函数值达到最优，即满足(1)式的可行解称为最优解。

(3)基：设线性规划约束方程组中的系数矩阵A m×n 的秩为m(m＜n)，则A中任一个m阶可逆矩阵B称为线性规划问题的一个基矩阵，简称为基。

(4)基(基本)解：取A中一个基B=(p j1,p j2,…p j m)，对应的基变量为(x j1,x j2,…x j m)，当基变量取值均为0，且满足约束条件(2)的一个解X，称为是关于基B的一个基本解。

对于A中每一个基B，只能找出一个基本解X，而A中最多有C n m个基，因此线性规划问题最多只有个C n m个基本解。

(5)基可行解：满足非负约束(3)的基本解称为基本可行解。

(6)可行基：对应于基可行解的基称为可行基。