卫生管理运筹学课件-线性规划-2

第一节 基本概念第二节 线性规划问题的图解法第三节 线性规划模型的解及性质第四节

单纯形法第五节 对偶规划第六节 运输问题及表上作业法线性规划第四节 单纯形法一、单纯形法的解题过程二、线性规划模型的变换三、单纯形法的计算方法四、一般情况的处理--人工变量法一、单纯形法的解题过程得到最优解或证明最优解不存在线性规划标准形检查该点是否最优解从可行域某个顶点开始不是取一个“相邻”、“更好”的顶点上次课讲授内容二、 线性规划模型的变换①目标求极大值②变量非负③右端项非负④全部等式约束单纯形法要求线性规划模型标准形式规范形式⑤系数矩阵中包含一个单位子矩阵每个约束方程中要有一个变量的系数１，而这个变量在其余方程中不出现。上次课讲授内容三、 单纯形法的计算方法单纯形法的基本步骤:（1）建立初始单纯形表确定基变量、非基变量以及基变量、非基变量（全部对于0）和目标函数的值，并求出相应的检验数（在用非基变量表达的目标函数表达式中，我们称非基变量xj的系数（或其负值）为检验数）

；上次课讲授内容（2）检验、确定进基变量如果任何一个非基变量的值增加都不能使目标函数值增加，即所有检验数非正，则当前的基本可行解就是最优解，计算结束。若存在检验数大于0，那么绝对值最大者对应的非基变量xj称为“进基变量”，转（3）。单纯形法的基本步骤:(3)

确定出基变量满足这个基变量xr称为出基变量。转（4）。如果进基变量的值增加时，所有基变量的值都不减少，即所有aij非正，则表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此时，不存在有限最优解，计算结束。单纯形法的基本步骤:（4）迭代运算将进基变量作为新的基变量，出基变

量作为新的非基变量，确定新的基、新的基本可行解和新的目标函数值。在新的基变量、非基变量的基础上重复（1）。单纯形法的基本步骤:注意：单纯形法中每一步运算只能用矩阵初等行变换；表中第3列(b列)的数总应保持非负（≥0）当所有检验数均非正（≤0）时，得到最优单纯形表。可能出现的特殊情况单纯形法求解中的特殊情况1．最终产生最优值的单纯形表中，某一非基本变量的检验数＝0，意味着作任何增大，目标函数的最优值不变．此时线性规划问题的最优解并不唯一，有多重最优解．（见下面例题）例

用单纯形法求解下列规划问题解:

令于是原线性规划问题变为标准形式：单纯形表迭代00-10013/81/4311

0

-1/8

1/40

0

-1

0126-3

-1

-1

-1x1

x2

x3

x4-2

[2]

1

03

1

0

1-2

2

0

0-1

1

½

0[4]

0

-1/2

1b-1

x3

4-1

x4

6Cj

-Zj-1

x2

2-1

x4

4Cj

-Zj-1-x32x1Cj

-Zj最优解为：最优值为：2．当枢列（进基变量所在列）中的每一项系数不是0就是负值时，说明所有约束条件对进基变量的增加都无约束作用，因此目标函数可以无限地增加．这种情况我们称为无有限最优解（或称有无界解或无最优解）．但在现实中，不可能有此情况，往往是模型建立错误，遗漏了一些约束条件所致．单纯形法求解中的特殊情况单纯形法求解中的特殊情况3．在选取进基变量时，有2个及2个以上变量的检验数具有相同的最大正值（极小化问题为相同的最小负值），这时可任选其中一个变量进基．选择进基变量的不同，可能在达到最优解前迭代的次数也不同，但事先无法预测．4．出现相同的最小比值，此时可从具有相同最小比值所对应的基本变量中，选择下标最大的那个基本变量为出基变量．这时有可能出现退化的基本可行解，即至少有一个基本变量为零（见规划教材例2-8中的表

2-6和表2-7）．出现退化的基本可行解对运算带来麻烦，理论上可能出现单纯形法陷入循环或闭环，在每次迭代中值保持不变，不能使解趋向最优解．但幸运的是，在实际应用中从未遇到或发生过这种情况．尽管如此，人们还是对如何防止出现循环作了大量研究。提出了各种避免循环的方法。单纯形法求解中的特殊情况在选择进基变量和出基变量时作以下规定：j①

在选择进基变量时，在所有

>

0的非基变量中选取下标最小的进基；②当有多个变量同时可作为出基变量时，选择下标最小的那个变量出基。这样就可以避免出现循环,当然，这样可能使收敛速度降低。#避免循环的方法：五、一般情况的处理--人工变量法一般情况的处理：主要是讨论初始基本可行解不明显时，常用的方法。例如

P53

3(4)规范化规范化标准化考虑一般问题：bi

>

0

，

i

=

1

,

…

,

mMax

z

=

c1

x1

+

c2

x2

+

…

+

cn

xns.t.a11

x1+

a12

x2

+…+

a1n

xn

=

b1a21

x1+

a22

x2

+…+

a2n

xn

=

b2...am1

x1+

am2

x2+…+

amn

xn

=

bmx1

，x2

，…

，xn

≥

0引入人工变量

xn+i

≥

0，i

=

1

,…,

m；a11

x1+

a12

x2+

…

+

a1n

xn+

xn+1=

b1=

b2+

xn+2a21

x1+

a22

x2+

…

+

a2n

xn...am1

x1+

am2

x2+

…

+

amn

xn

+

xn+m

=

bmx1,

x2

...

xn

,

xn+1,

…,

xn+m

≥

01．

两阶段法：两阶段法是把一般问题的求解过程分为两步：第一步：求解原问题的一个基本解：建立一个辅助问题。对于前面的约束方程组，构造一个标函数为：Min

z＝

xn+1

＋xn+2

＋…＋xn+m这样，从目标最优角度迫使人工变量取零值，以达到原问题一个基本可行解的目的。这个阶段的辅助问题有下列明显的事实：设X*

=(

x*

,

x*

,…

,

x*

,

x*

,

…,

x*

）1

2

n

n＋1

n＋m为这个问题的最优解，那么，若x*

x*

x*n+1

＝

n＋2＝…＝

n＋m＝0，则(x*

,

x*

,…

,

x*

）为原问题的一个基本可行解，这时1

2

n目标函数值为零；否则，即x*

,

…,

x*

不全为零时，说n＋1

n＋m明原问题无可行解。即引入人工变量

xn+i

≥

0，i

=

1

,…,

m；构造:Min

Ｚ＝

xn+1

＋

xn+2

＋

…

＋

xn+mMaxＺ

=

-

xn+1

-xn+2

-

…

-

xn+ma11

x1+

a12

x2+

…

+

a1n

xn+

xn+1

=

b1

a21

x1+

a22

x2+

…

+

a2n

xn+

xn+2

=

b2...am1

x1+

am2

x2+

…

+

amn

xn+

xn+m

=

bmx1

，

x2

，...，

xn

，

xn+1

，…，

xn+m

≥

0显然，xj

=

0

，

j

=

1,

…

,

n

;xn+i

=

bi

，

i

=

1,

…

,

m是基本解,它对应的基是单位矩阵。结论：若得到的最优解满足

xn+i

=

0i

=

1,…,m

，则是原问题的基本可行解;否则，原问题无可行解。得到原问题的基本可行解后，第二阶段求解原问题。第二步：求解原问题：以第一步得到的基本可行解为初始基本可行解，用单纯形法求解原问题。在表格计算过程中，这一步的初始单纯形表可这样产生（1）由第一步的最优单纯形表删去xn＋1

，xn＋2

，…，xn+m列；把第一行的目标函数系数行换为原问题目标函数的系数；检验数行直接用前文介绍的方法在表格上计算得到，即用xj的价值系数cj减去cB列的各元素与xj列各对应元素的乘积，把计算结果填入xj列的最后一行，得到检验数σj 。例1：Max

Z

=

5x1

+

2x2

+

3x3

-

x4x1

+

2x2

+

3x3

=

152x1

+

x2

+

5x3

=

20x1

+

2x2

+

4x3

+

x4

=

26x1

,

x2

,

x3

,

x4

≥

0第一步

求解原问题的一个基本解：Max

Z

=

-

x5

-

x6x1

+

2x2

+

3x3

+

x5

=

152x1

+

x2

+

5x3

+

x6

=

20x1

+

2x2

+

4x3

+

x4

=

26x1

,x2

,x3

,x4

,x5

,x6

≥

0第一阶段得到原问题的基本可行解:(0，15/7，25/7，52/7)T第二步，求解原问题：把基本可行解填入表中得到原问题的最优解:(25/3，10/3，0，11)T最优目标值：112/3引入人工变量

xn+i

≥

0

（i

=

1

,

…

,

m）及充分大正数

M

。得到：Max

Z

=

c1

x1

+

c2

x2

+

cn

xn

+

M

xn+1

+

Mxn+ma11

x1

+

a12

x2

+

…

+

a1n

xn

+

xn+1

=

b1a21

x1

+

a22

x2

+

…

+

a2n

xn

+

xn+2

=

b2...am1

x1

+

am2

x2

+

…

+

amn

xn

+

xn+m

=

bmx1

,x2

，…

，xn

，xn+1

，…

，xn+m

≥02．大M法Max

Z=

5x1+

2x2+

3x3-x4

-M

x5-M

x6x1+

2x

2+

3

x3+

x5

=152

x1+

x2+

5

x3+

x6

=

20x1+

2

x2+

4

x3+

x4

=

26x1