第二次和第三次课合订单纯形法

第二次和第三次课合订单纯形法演示文稿现在是1页\一共有40页\编辑于星期二优选第二次和第三次课合订单纯形法现在是2页\一共有40页\编辑于星期二找出一个初始基本可行解是否最优转移到另一个基本可行解（找出更小的目标函数值）最优解是否循环结束基本思想框图如何找初始基本可行解？如何判断是否最优解？如何转换基本可行解？现在是3页\一共有40页\编辑于星期二

求回顾上一节例1：的一个基本解和一个基本可行解.现在是4页\一共有40页\编辑于星期二解:约束方程的增广矩阵为：x2

x4注意到A是2×4矩阵,r(A)＝2.由于第2列和第4列线性无关,构成一个2阶单位子块，因此可构成一个基矩阵.取为基变量,为自由变量,用自由变量表表示基变量得如下同解方程组:现在是5页\一共有40页\编辑于星期二又因5>0,6>0,该解显然非负，因此这个解也是一个基本可行解。x2

x4现在是6页\一共有40页\编辑于星期二基变量取为其他变量的情况若取为基变量,为自由变量,由于基本解中自由变量全取零,所以只需对第一列,第二列以及常数项列组成的矩阵初等行变换至行最简形:由此可得基本解:又因3>0,8>0,该解显然非负，因此这个解也是一个基本可行解。现在是7页\一共有40页\编辑于星期二结论:

若系数矩阵A中存在m阶单位子块,得到基本可行解之后,如何判断它是否是最优解呢?

设约束线性方程组AX=b的系数矩阵A的秩R(A)=m,则有如下结论成立：记增广矩阵为（A,b），其中,基变量的取值为单位子块中1所对应的右边常数项非负,且对应的常数那么从增广矩阵中便可读出一个基本可行解.项的值,自由变量取值全为零.现在是8页\一共有40页\编辑于星期二该解是否最优呢?将代入目标函数表达式中消去得注意到的系数为-10<0,而可行域中可见,当时,目标函数值减小,所以不是最优解.思考:若此时目标函数中自由变量的系数均大于零,那么这个解是否是最优解?现在是9页\一共有40页\编辑于星期二1.单纯形表中心部位

A

右列

b

底行(检验行)

0

右下端目标函数中常数项的相反数目标函数中变量的系数底线二、单纯形表及容许的运算r(A)＝m现在是10页\一共有40页\编辑于星期二2.容许运算中心部位Ab右列底行

0右下端1)底线以上的行可进行初等行变换(三种);2)底线以上的行乘常数后加至底行(包括右下端).底线使表具备下面四个特点:①

②

③④现在是11页\一共有40页\编辑于星期二3.终止条件(最优性条件)当表格具备如下特点:②右列元素非负①

中心部位具有m阶单位子块③底行中相应于单位子块位置的元素为0(基变量对应的底行元素为零)④底行其他元素非负(自由变量对应的元素非负)则从表格中即可读得LP问题的最优解和最优值.满足①②时,可读出基本可行解满足①②③时,判断该解是否最优.满足①②③④时,可断定该基本可行解是最优解.现在是12页\一共有40页\编辑于星期二最优解(值)的读法:

单位子块中1所在列对应的变量(基变量)取相应右列的值,其余变量(自由变量)取值为零,将它们写在一起即是一个最优解.而此时右下端元素的相反数即为相应的最优值.现在是13页\一共有40页\编辑于星期二20-41

6-1130

5

1

-3

24

0

20-41

6-1130

5

-10

0

270

-9

的系数为-10<0满足①②满足①②③但④不满足4.举例现在是14页\一共有40页\编辑于星期二

以上讲述了利用单纯形表以及容许运算求得一个基本可行解,并判断其是否最优的方法.

若该基本可行解不是最优的,那么如何由当前表得到一个更优(对应的目标函数值下降)的基本可行解呢?

由上面例题知,取值大于零时,目标函数值下降.这就意味着将成为基变量,不再是自由变量;那么中至少一个将由基变量变为自由变量.单纯形法的后半部分讨论的主要内容.当前基本可行解不是最优怎么办?现在是15页\一共有40页\编辑于星期二设当前表格已具备①②③三个特点,但④不满足:三、基可行解的转换1)进基变量的确定对应的取为进基变量;从底行中任选一个负元素,比如现在是16页\一共有40页\编辑于星期二2)离基变量的确定“最小比例原则”也称

原则选取一个,记为

从所选元素所在的列(第j列)底线以上的正元素中按其中:3)进行旋转运算利用容许的运算将变为1,该列其它元素(包括底行相应的元素)变为0,从而实现将变为基变量的目的.现在是17页\一共有40页\编辑于星期二1.单纯形法的迭代步骤1）将问题化为标准型,写出相应的表格;2）建立满足①②③三个特点的初始单纯形表:若1)对应的表格满足①②③,直接进入第3)步;若1)对应的表格满足①②,但③不满足,则利用将底行以上行的若干倍数加到底行,使③满足;若1)对应的表格不满足①②,则借助大M法(下一节的内容)使①②满足,然后再使③满足.四、单纯形算法及应用现在是18页\一共有40页\编辑于星期二3）若底行元素全非负,则得到最优解，结束运算;否则转4）.4)确定进基变量对应的取为进基变量;从底行中任选一个负元素,比如令5)确定离基变量从所选元素所在的列(第j列)底线以上的正元素中按现在是19页\一共有40页\编辑于星期二“最小比例原则”选取一个,记为其中:6)进行旋转运算利用容许的运算将变为1,该列其它元素变为0,从而实现将变为基变量的目的.7）观察得到的新表(满足①②③).若底行所有元素均非负,则已得最优解,结束运算;否则,返回第4)步.现在是20页\一共有40页\编辑于星期二2.例题解析例1.求解LP20-41

6-1130

5

1

-3

24

0

解:该LP已是标准形,故直接列出如下表格:满足①②为判断该解是否最优,利用容许的运算使③满足,得:现在是21页\一共有40页\编辑于星期二

2

0

-4

1

6

-1

1

3

0

5

-10

0

270-9

1

0

-21/23

0

1

11/2800

75

21

满足①②③但④不满足满足①②③④可见此LP有最优解最优值为现在是22页\一共有40页\编辑于星期二例2.

求解LP解:先化LP为标准形,列出如下表格:现在是23页\一共有40页\编辑于星期二方法一：

-1

1

1

00

2

1

2

0

10

1031001

15

-2

-3

000

0

-1

1

1

00

2

3

0

-2

10

640-101

13

-5

0

300

6

现在是24页\一共有40页\编辑于星期二

0

1

1/31/30

4

1

0

-2/31/3

0

2

0

05/3-4/31

50

0-1/35/3016

010

3/5-1/53

1

0

0

-1/52/54

001-4/53/53

0

0

0

7/5

1/5

17

满足①②③④现在是25页\一共有40页\编辑于星期二

010

3/5-1/53

1

0

0

-1/52/54

001-4/53/53

0

0

0

7/5

1/5

17

满足①②③④是化为标准形的LP的最优解.

略去松弛变量，故原LP问题的最优解为最优值为现在是26页\一共有40页\编辑于星期二方法二：取底行中左边第一个负元素对应的变量为进基变量

-1

1

1

00

2

1

2

0

10

1031001

15

-2

-3

000

0

04/3

1

01/3

7

05/3

01-1/3

5

1

1/3

001/3

5

0-7/3

002/310

现在是27页\一共有40页\编辑于星期二

0

01-4/5

3/5

3

0

103/5

-1/5

3

1

0

0-1/5

1/5

4

0007/51/5

17

满足①②③④是化为标准形的LP的最优解.

略去松弛变量，故原LP问题的最优解为最优值为现在是28页\一共有40页\编辑于星期二3.注意事项（可能出现的情况）1）若迭代过程中右列元素中出现‘‘0’’元素(此时对应的基本可行解中某基变量的取值为0)，那么称该基本可行解是退化的,接下来的迭代可能出现循环.解决办法:在每次选进基变量时,每次选底行中左边第一个负元素对应的变量为进基变量,这就是改进的单纯形法.2）若最终表格中底行元素均非负,且所有自由变量(非基变量)对应的底行元素(检验数)均大于‘‘0’’

,则此时LP有唯一最优解.现在是29页\一共有40页\编辑于星期二3）若最终表格中底行元素均非负,且存在某自由变量(非基变量)对应的底行元素(检验数)等于‘‘0’’,则此时LP有无穷多最优解.4）若最终表格中底行存在负元素,且有一个进基变量所在的列中底线以上没有正元素(无法迭代下去),则此LP问题无最优解.以上结论的证明参见<<运筹学>>清华大学出版社.现在是30页\一共有40页\编辑于星期二例3.用单纯形法求解解:将上述线性规划化为标准形:现在是31页\一共有40页\编辑于星期二方法一：

1

1

1

1

00

12

2

1

-1

010

6-130001

9

-1

2

-1000

0

01/2

3/2

1

-1/20

9

1

1/2

-1/201/20

3

07/2

-1/201/21

12

05/2

-3/2

01/20

3

满足①②③但④不满足满足①②③但④不满足现在是32页\一共有40页\编辑于星期二

0

1/3

1

2/3

-1/30

6

1

2/3

0

1/3

1/30

6

0

11/3

01/3

1/31

15

0

3

0100

12

满足①②③④略去松弛变量,得原LP最优解为

最优解:注:由于最终表底行中自由变量

对应的系数为0,

故有无穷多最优解，即该最优解不是唯一最优解。现在是33页\一共有40页\编辑于星期二方法二：

1

1

1

1

00

12

2

1

-1

010

6-130001

9

-1

2

-1000

0

1

1

1

1

00

12

3

2

0