运筹学第5章 线性规划(max)单纯形法

Chapter5线性规划LinearProgramming5.1标准型

StandardformofLP5.2单纯形法

SimplexMethod5.1线性规划的标准型StandardformofLP04二月20233

在用单纯形法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。5.1线性规划的标准型StandardformofLP线性规划问题的标准型为:1．目标函数求最大值;2．约束条件都为等式方程;3．变量xj非负;4．常数bi非负.04二月20234max

Z=c1x1+c2x2+…+cnxn5.1线性规划的标准型StandardformofLP线性规划问题的标准型为:04二月2023504二月2023604二月20237注：化标准型的方法1、目标极小化极大：min(f)=--max(-f)2、不等式化等式：（1）大于等于“≥”：在左边减去乘余变量（）≥b

（）--s=b（2）小于等于“≤”：在左边添加松驰变量（）≤b

（）+t=b04二月202383、常数项负化正：两边乘（－1）4、变量负化正：乘（－1）5、自由变量（无要求)04二月202396、对于a≤x≤b(a、b均大于零)的有界变量化为标准形式有两种方法。

一种方法是增加两个约束x≥a及x≤b

另一种方法是令x‘=x－a，则a≤x≤b等价于

0≤x‘≤b－a，增加一个约束x'≤b－a

并且将原问题所有x用x=x'+a替换。04二月202310

当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束将其化为两个不等式

再加入松驰变量化为等式。1.3线性规划的标准型StandardformofLP1.2单纯形法SimplexMethod04二月202312一、典范式线性规划的单纯形法1.形如：典范式线性规划04二月202313典范式线性规划04二月202314典范式线性规划04二月202315典范式线性规划04二月202316典范式线性规划04二月202317典范式线性规划04二月202318(1)系数矩阵2.基本概念04二月202319系数矩阵列向量04二月202320

单位阵.

单位向量.04二月202321其余列向量称为非基向量

单位向量对应的列向量称为基向量(2)基向量与非基向量

基向量非基向量04二月202322基向量对应的变量称为基变量，非基向量对应的变量称为非基变量

基向量非基向量(2)基变量与非基变量

基变量04二月202323(4)基本解

(basissolution)令非基变量等于零，由方程组

AX=b解出基变量，则这组解称为方程组的基本解。令则方程组为04二月202324则基本解为令则方程组为04二月202325(5)基本可行解(basis

feasiblesolution)

若基本解是可行解则称为是基本可行解（也称基可行解）可行点(解)：满足所有约束条件的点04二月202326基本可行解04二月202327(6)检验数的检验数:04二月20232804二月202329(7)单纯形表211040130130340000340004二月2023303.单纯形法计算步骤：(1).求初始基可行解:根据典范式列出初始单纯形表。(2).最优解判断：（a）若检验数λj≤０（j＝１，２，…，n）得到最优解；（b）某个检验数λk>0且aik≤０（i=1，2,…,m）则线性规划无最优解(具有无界解)。（c）若对λk>0,都有aik(i=1,…,m)不全为负，则进行换基；04二月202331第Ｌ个比值最小，选最小比值对应行的基变量为出基变量，aLk为主元素；

(c）求新的基可行解：用行变换方法将aLk

化为１,其所在列的其它元素化为零,得到新的可行基及基本可行解，再判断是否得到最优解。（b）选出基变量

:求最小比值(3).换基(换基可行解)：（a）选进基变量设λk=max｛λj|λj>0｝,xk为进基变量04二月202332【例1】用单纯形法求下列线性规划的最优解04二月202333【解】化为标准型，加入松驰变量x3、x4则标准型为1.5单纯形法

SimplexMethod04二月202334初始单纯形表比值211040130130340000340004二月202335进基列出基行bi/ai2，ai2>0θi表1-4(1)XBx1x2x3x4bx3211040x4130130λj3400

(2)x3x2λj

(3)x1

x2

λj

基变量110001/301/3105/31-1/3405/30

-4/330103/5-1/51801-1/52/5400-1-1将3化为1乘以1/3后得到1.5单纯形法

SimplexMethod30183

4

0

0

0

0

0

4

4

3

04二月202336最优解X=(18，4，0，0)T，最优值Z=70O20301040(3,4)X(3)=(18,4)最优解X=(18,4)最优值Z=70X(1)=(0,0)2010x2x1301.5单纯形法

SimplexMethodX(2)=(0,10)04二月202337【例2】

用单纯形法求解【解】将数学模型化为标准形式：不难看出x4、x5可作为初始基变量，单纯法计算结果如表1.５所示。1.5单纯形法

SimplexMethod04二月202338Cj12

100bθCBXBx1x2x3x4x50x42－3210150x51/3-150120λj12100

0x4

2x2λj

1x1

2x2

λj

表1－51/3150120301713751/30-90-22025601017/31/31250128/9-1/92/335/300-98/9-1/9-7/3最优解X=(25，35/3，0，0，0)T，最优值Z=145/31.5单纯形法

SimplexMethod04二月202339【例3】求解线性规划【解】化为标准型1.5单纯形法

SimplexMethod04二月202340比值3-21012-1014-110000-1100初始单纯形表为04二月202341λ2=1>0,

而a12<0，a22<0，没有比值，从而线性规划的最优解无界。比值3-21012-1014-110000-110004二月202342由模型可以看出，当固定x1使x2→+∞且满足约束条件，还可以用图解法看出具有无界解。04二月202343【例4】求解线性规划【解】:化为标准型1.5单纯形法

SimplexMethod04二月202344用单纯形法计算如下表所示04二月202345

C24000CBXBx1x2x3x4x5bθ000x3x4x5－111[2]2－11000100014→10225—λj24↑000400x2x4x5－1/2[2]1/21001/2－11/201000126→4—38λj4↑0-200420x2x1x50101001/4－1/2[3/4]1/41/2－1/40017/235/2→14—10/3λj000↑-20420x2x1x30101000011/31/3－1/3－1/32/34/38/314/310/3λj000-2004二月202346420x2x1x50101001/4－1/2[3/4]1/41/2－1/40017/235/2→14—10/3λj000↑-20

表(3)中λj全部非负,则最优解为:420x2x1x30101000011/31/3－1/3－1/32/34/38/314/310/3λj000-20得到表(4)的另一基本最优解04二月202347X(1),X(2)是线性规划的两个最优解，它的凸组合

仍是最优解，从而原线性规划有多重最优解。04二月202348唯一最优解的判断：最优表中所有非基变量的检验数非零,则线规划具有唯一最优解

。多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解。无界解的判断:

某个λk>0且aik≤０（i=1，2,…,m）则线性规划具有无界解退化基本可行解的判断:存在某个基变量为零的基本可行解。1.5单纯形法

SimplexMethod04二月202349

通常线性规划的标准型并非典范式,为了得到典范式，在约束条件的等式左端加一组虚拟变量，这种人为加的变量称为人工变量。构成典范式后再用单纯形法求解，基于这种解法的有：大M法或两阶段法(人工变量法)。1.5.2大M法1.5单纯形法

SimplexMethod04二月202350【例5】用大M法解下列线性规划1.大M法04二月2023511.5单纯形法

SimplexMethod【解】首先将数学模型化为标准形式引进x4，x5(松弛变量)，得到标准型(非典范式)第一、三约束中分别加入人工变量x6、x7，目标函数中加入―Mx6―Mx7，得到典范式Cj32-100-M-MbCBXBx1x2x3x4x5x6x7-M

0-Mx6x5x7－4123－1－212[1]－1000101000014101→λj3-2M2+M-1+2M↑-M000-M0-1x6x5x3－6－32[5]3－2001－100010100-1-213→81λj5-6M5M↑0-M00-2M+120-1x2x5x3－6/5[3/5]－2/5100001-1/53/5-2/50101/5-3/52/5-1/5-13/5-2/53/531/5→11/5λj5↑0000-M-M04二月202353Cj32-100-M-MbCBXBx1x2x3x4x5x6x7-M

0-Mx6x5x7－4123－1－212[1]－1000101000014101→λj3-2M2+M-1+2M↑-M000-M0-1x6x5x3－6－32[5]3－2001－100010100-1-213→81λj5-6M5M↑0-M00-2M+120-1x2x5x3－6/5[3/5]－2/5100001-1/53/5-2/50101/5-3/52/5-1/5-13/5-2/53/531/5→11/5λj5↑0000-M-M23-1x2x1x301010000111025/32/3-1-10-27/5-13/3-32/51331/319/3λj000-5-25/3-M+2-M+22/504二月202354M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；最优解X＝（31/3，13，19/3，0，0)T；最优值Z＝152/3注意：1.5单纯形法

SimplexMethod04二月2023551.5单纯形法

SimplexMethod【例6】求解线性规划【解】加入松驰变量x3、x4化为标准型在第二个方程中加入人工变量x5，目标函数中加上Mx5一项，得到04二月202356用单纯形法计算如下表所示。

Cj-5800-MbCBXBx1x2x3x4x50-Mx3x5[3]11－