给学生课件-新-2单纯形法

LP规划问题的最优解，可以从基可行解中找到图解法有局限性；枚举法计算量大；试图用枚举法求解线性规划是靠不住的，必须寻求其它的有效算法。主要内容2.1

单纯形法原理2.2

单纯形法的表格形式2.3

大M法和两阶段法2.4

问题2.5改进单纯形法2.1

单纯形法原理基本思路：根据问题的，从可行域中某个基本可行解（顶点）开始，转换到另一个基本可行解（顶点），并且使目标函数达到最优值时，停止转换，同时问题就得到了解决。开始初始基本可行解最优解？无穷多最优解？基交换结束无最优解？Y输出最优解NNY需要解决的问题能够求出一个初始基本可行解新的基本可行解比前一个结果更好（否则就成穷举法了）判断问题的解的情况，能根据判断结果及时停止计算，避免错误及无效运算。有唯一最优解，判断基本可行解是否是唯一最优解。有 解或无解，及时停止计算。有无限多最优解，找到一个最优解后停止计算。例：Min

Z=4x1

+3x2

+8x3x1

+x3

2x2

+2x3

5xj

0

(j=1,2,3)Min

Z=4x1

+3x2

+8x3x1

+x3-x4=2x2

+2x3-x5=

5xj

0

(j=1,2,3)转化为求解得到：X

(2,5,0,0,0)T显然，此解是可行解，是否最优？1、确定初始基本可行解系数矩阵0

1

2

0

11

2

3

4

5A

(

p

,

p

,

p

,

p

,

p

)

1

0

1

1 0

取基：B

(

p1,

p2

)用非基变量取代基变量和目标函数x1

x3

2x2

2x3

5此时

z

4(

x3

x4

x3

x4

3从目标函数中可以看出，x3如果取任意正数，则目标函数减小。所以，此解非最优解。

x3

x5

823确定初始基本可行解中需要注意的问题系数矩阵中有单位阵，则取此单位阵为基，可得到基本可行解。系数矩阵中没有单位阵，构造单位阵，得到基本可行解。约束条件存在“≤”形式不等式，采用增加松弛变量的方法得到初始可行基。约束条件不存在“≤”形式的不等式，如果直接观察不到单位阵，采用人造基的方法。若约束条件中附加变量的系数是-1或者原约束即为等式，需要引入人工变量x1

+

x3

-

x4

+

x6

=

2x2

+

2x3

-x5

+

x7

=

5(j=1,2,3,4,5,6,7)xj

0此时，目标函数为Min

Z=4x1

+3x2

+8x3

+0x4

+0x5

+Mx6

+Mx7注意引入人工变量后，约束条件与原问题不等价希望将它们逐渐从基变量

换出去方法：大M法和两阶段法2、求取新的基本解，原则：取得更好的目标函数值基本解可行3、确定换入变量显然，本题中取x3为换入变量，有利于取得更好的目标函数值一般的，取系统目标函数中负检验数中最小的一个为换入变量由约束条件，可得显然，取x1为换出变量，有利于保证新的基本解可行详细证明（见P21-22）负值情况下：3

2，则xx3

202因为

，则xx3

2/21因为4、确定换出变量–

若换出x1

，则x1成为非基变量，则X

)0,0,2,1,0(用非基变量表示基变量和目标函数，可得22

2x21

2显然，此解为最优解。1

2

z4、确定换出变量（2）–

若换出x2

，则x2成为非基变量，则X

(1

2,0,

3

2

,0,0)显然，此解非可行解。几个问题1、检验数相同

0}有两个或两个以上相同值，可任取其中一个变量入基（一般选下标小的变量入基）jmin{

j若存在两个以上相同的最小比值，就会出现解。理论上讲， 解可能使计算出现循环，从而得不到最优解。然而，实际问题中很少出现这种情况。当计算中出现最小比值相同的情况时，可按Bland规则来计算。Bland

规则：①在σj<0中，选下标小的非基变量入基；②对相同的最小比值，选下标小的基变量出基。0}

有相同值2、最小比值相同'a'b'aikiikmin{

i单纯形法基本步骤：1.

构造初始可行基；附加变量、人工变量2.

根据可行基确定基本可行解，及其对应的目标函数值；3.最优性检验，符合停止条件到第5步；否则继续下一步；依据－检验数

j判别原理：最优解、无穷多最优解、无可行解4.

基变换，返回第2步；通过基变换使得基本可行解在约束边界的相邻顶点中沿着优化方向切换，切换是相邻的。换入准则：

j

0

，且最小5.

计算结束，得到结果。ikikrka

min{

bi

a

0}a换出准则：最小非负比值

br单纯形法基本步骤：5、最优性检验问题最优性检验的依据—检验数（非基变量的系数）最优解判别定理：所有检验数0，最优解人工变量为03无穷多解判别定理：所有检验数0，人工变量为0无穷多解+人工变量不为0有一个非基变量的检验数≤0，且相应基中没有正元素人工变量不为05无解判别定理：所有检验数0，解某非基变量检验数为0解）判别定理：4无有限最优解（无解主要内容2.1单纯形法原理2.2

单纯形法的表格形式2.3

大M法和两阶段法2.4

问题2.5改进单纯形法2.2

单纯形法的表格形式单纯形法最常用的一种形式，使用方便。步骤：1，构造初始可行基，并列出初始单纯形表；2，最优性检验；3，从一个基本可行解转换到相邻的目标函数值更优的基本可行解，列出新的单纯形表；

4，重复2,3步，直到计算结束。Min

Z=4x1

+3x2

+8x3

+0x4

+0x5

+Mx6

+Mx7x1

+x3

-x4

+x6

=

2x2

+2x3

-x5

+x7=

5xj

0

(j=1,2,3,4,5,6,7)基变量的取值xB-z(-cBxB)更优可行单纯形法的计算步骤(最小化)①

确定初始基，求初始基本可行解。②

对应于非基变量检验数全

0,且人工变量为零。若是，停，得到最优解（若某非基变量检验数为0，则为无穷多最优解）；若否，转3。③

若所有检验数

0，且人工变量不为零，停止计算，问题没有可行解；若有检验数

<0,且所有比值为负数,人工变量为零，则原问题有解。④

进行基变换，求其对应的基本可行解，返回2。主要内容2.1单纯形法原理2.2

单纯形法的表格形式2.3

大M法和两阶段法2.4

问题2.5改进单纯形法2.3

大M法和两阶段法一、大M法：、人工变量在目标函数中的系数确定：若目标函数为maxZ，则系数为-M，否则为M。、计算方法：单纯形法二、两阶段法：第一阶段：求解一个目标函数仅含人工变量，且为极小化的线性规划问题，以判断原问题是否有可行解。第二阶段：去掉第一阶段中的人工变量，将第一阶段得到的最优解作为初始基本

可行解，利用单纯形法继续求解。例、用两阶段法求解min

z

=

x1

+

5x22x1

+

3x2

≤

62x1

+

x2

≥

1x1,x2

≥

0解：第一阶段：将问题化为等式约束min

z

=

x1

+

5x2+0x3+0x42x1

+

3x2

+x3

=

62x1

+ x2

–x4

=

1x1,x2

,x3,x4≥

0引进人工变量x5得辅助规划：min

w

=

x52x1

+

3x2

+x3

=

62x1

+ x2

–x4

+

x5

=

1x1,x2,x3,x4,x5

≥

0min

w

=

x52x1

+

3x2

+x3

=

62x1

+ x2

–x4

+x5

=

1x1,x2,x3,x4,x5

≥

0CBXB0x10x20x30x4bi0x32310066/21x5210-1111/2-2-10100x3021150x111/20-1/21/20000第一阶段有最优解。第二阶段：去掉人工变量，换上原线性规划目标函数（见下表）。最优解：X

*=(1/2

0

5

0)TZ*=1/2CBXB1500bx1x2x3x40x3021151x111/20-1/21/209/201/2主要内容2.1单纯形法原理2.2

单纯形法的表格形式2.3

大M法和两阶段法2.4

问题2.5改进单纯形法2.4问题?当基本解、基本可行解、最优基本可行解中有基变量为0时，即出现了

。的情况下，即使存在最优解，也可能出现循环现象，

达不到最优解。常用方法：摄动法和勃兰特法主要内容