第四次课表上作业法及大法和两阶段法

第四次课表上作业法及大法和两阶段法演示文稿第1页，共41页。优选第四次课表上作业法及大法和两阶段法第2页，共41页。E单位阵N非基阵基变量XB非基变量XN0单纯形表第3页，共41页。

21000

检验数单纯形表结构单纯形表

—24/65/1C已知第4页，共41页。

21000

—24/65/1C检验数单纯形表结构单纯形表基可行解：第5页，共41页。单纯形表结构单纯形表

21000

—24/65/1C检验数有时不写此项求第6页，共41页。单纯形表结构单纯形表

21000

—24/65/1C检验数求第7页，共41页。单纯形表结构单纯形表

21000

—24/65/1C检验数求不妨设此为主列主行第8页，共41页。单纯形表结构单纯形表

21000

—24/65/1C检验数主元第9页，共41页。用单纯形表求解LP问题例、用单纯形表求解LP问题第10页，共41页。解：化标准型第11页，共41页。

—24/65/1主元化为1主列单位向量换出换入表1：列初始单纯形表（单位矩阵对应的变量为基变量）正检验数中最大者对应的列为主列最小的值对应的行为主行第12页，共41页。

15/524/26/4

0*52*2/6+0*4/61-2/3=表2：换基

（初等行变换，主列化为单位向量，主元为1）检验数>0确定主列最小确定主列主元第13页，共41页。

21000

015/20015/4-15/2

2

7/21001/4-1/213/2010-1/43/2000-1/4-1/2

检验数<=0最优解为X=(7/2,3/2,15/2,0,0)目标函数值Z=8.5

2*7/21*3/2+0*15/28.5表3：换基

（初等行变换，主列化为单位向量，主元为1）第14页，共41页。练习:一般主列选择正检验数中最大者对应的列,也可选择其它正检验数的列.以第2列为主列,用单纯形法求解。正检验数对应的列为主列第15页，共41页。结束2.4单纯形法的计算步骤第16页，共41页。2.5.1单纯形法的进一步讨论一、大M法二、两阶段法----人工变量法第17页，共41页。人工变量法问题：线性规划问题化为标准形时，若约束条件的系数矩阵中不存在单位矩阵，如何构造初始可行基？

第18页，共41页。人工变量法加入人工变量设线性规划问题的标准型为：第19页，共41页。

加入人工变量,构造初始可行基.人工变量法系数矩阵为单位矩阵，可构成初始可行基。第20页，共41页。

约束条件已改变，目标函数如何调整？人工变量法第21页，共41页。“惩罚”人工变量！（1）大M法（2）两阶段法第22页，共41页。一、大M法人工变量在目标函数中的系数为-M,

其中，M为任意大的正数。目标函数中添加“罚因子”-M（M是任意大的正数）为人工变量系数，只要人工变量>0，则目标函数不可能实现最优。第23页，共41页。例:求解线性规划问题一、大M法第24页，共41页。

一、大M法解:加入松弛变量和剩余变量进行标准化,加入人工变量构造初始可行基.

第25页，共41页。求解结果出现检验数非正若基变量中含非零的人工变量，则无可行解；否则，有最优解。一、大M法用单纯形法求解（见下页）。目标函数中添加“罚因子”-M为人工变量系数，只要人工变量>0，则目标函数不可能实现最优。第26页，共41页。

1-21-412-201

3-6MM-13M-1

3

-1-1

x1

x2

x3

0

x411-M

x63-M

x71Cj-Zj

Cj

CBXBb

100-100

0-M

00

x4

x5

113/21

001001

00

-

M-M

x6

x7

表1（初始单纯形表）一、大M法（单纯形法求解）第27页，共41页。

3-20010

-201

1M-10

3

-1-1x1

x2

x3

0x410-M

x61-1x31Cj-Zj

Cj

CBXBb

100-100

0-M

00

x4

x5

1

0-11-201

01-3M

-

M-M

x6

x7

一、大M法（单纯形法求解）表2第28页，共41页。

3

00010-201

100

3

-1-1

x1

x2

x3

0x412-1x21-1x31Cj-Zj

Cj

CBXBb

1-20-100

0-1

00

x4

x5

4

i

2-51-2011-M-1

-M

-

M-M

x6

x7

表3一、大M法（单纯形法求解）第29页，共41页。

100010001

000

3

-1-1

x1

x2

x3

3x14-1x21-1x39

2

Cj

CBXB

b1/3-2/3

0-12/3-4/3

-1/3-1/3

00

x4

x5

2/3-5/3

1-24/3-7/3

1/3-M2/3-M

-

M-M

x6

x7

表4一、大M法（单纯形法求解）最优解为目标函数值z=2检验数均非正，此为最终单纯形表第30页，共41页。M在计算机上处理困难。分阶段处理——先求初始基，再求解。二、两阶段法第31页，共41页。二、两阶段法第一阶段:构造如下的线性规划问题人工变量的系数矩阵为单位矩阵，可构成初始可行基。

目标函数仅含人工变量，并要求实现最大化。若其最优解的目标函数值不为0，也即最优解的基变量中含有非零的人工变量，则原线性规划问题无可行解。第32页，共41页。

用单纯形法求解上述问题,若ω=0,进入第二阶段,否则,原问题无可行解。第二阶段：去掉人工变量，还原目标函数系数，做出初始单纯形表。用单纯形法求解即可。二、两阶段法下面举例说明，仍用大M法的例。第33页，共41页。例：二、两阶段法第34页，共41页。

二、两阶段法构造第一阶段问题并求解解：用单纯形法求解第35页，共41页。二、两阶段法—（第一阶段、求minω

）

1-21-412-201

-613

000

x1

x2

x3

0x411-1x63-1x71

Ci

CBXBb

1000-11000

0-10

00-1--1

x4

x5

x6

01103/211

0

-

1

x7

i表1第36页，共41页。

-1--211-

-3

-

1

x7

3-20010

-201

010

000

x1

x2x3

0x410-1x610x31

Ci

CBXBb

1000-11000

0-10

00-1

x4

x5

x6二、两阶段法—（第一阶段、求minω

）表2第37页，共41页。

-54-2-1-

-1

-

1

x7

3

00010-20

1

000

000

x1

x2x3

0x4120x210x31

Ci

CBXBb

1-220-11000

00-1

00-1

x4

x5

x6二、两阶段法—（第一阶段、求minω

）表3：最终单纯形表第二阶段不含人工变量且ω=0第38页，共41页。