运筹学基础线性规划

运筹学基础线性规划第一页，共三十九页，编辑于2023年，星期三另例：000-3-412-1023160-142x1

x2

x3x4

b问题：无标准的初始可行基，如何利用单纯形法求解化为标准形不是标准的初始可行基第二页，共三十九页，编辑于2023年，星期三

三、人工变量问题用单纯形法解题时，需要有一个单位矩阵作为初始基。当约束条件都是“≤”时，加入松弛变量就形成了初始基。但如果存在“≥”或“＝”型的约束，就没有现成的单位矩阵。采用人造基的办法：人为构造单位矩阵处理方法有两种：大M法两阶段法第三页，共三十九页，编辑于2023年，星期三（一）大M法maxZ=

3x1-x2-2x33x1+2x2-3x3=6x1-2x2+x3=4x1,x2,x3≥0S.t.没有单位矩阵，不符合构造初始基的条件，需加入人工变量。

maxZ=

3x1-x2-2x3-Mx4-Mx53x1+2x2-3x3+x4

=6x1-2x2+x3+

x5=4x1,x2,x3,x4,x5≥0人工变量最终必须等于0才能保持原问题性质不变。为保证人工变量为0，在目标函数中令其系数为-M。M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。第四页，共三十九页，编辑于2023年，星期三大M法求解按大M法构造人造基，引入人工变量x4,x5的辅助问题如下：

例如

maxZ=

3x1-x2-2x33x1+2x2-3x3=6x1-2x2+x3=4x1,x2,x3≥0S.t.

maxZ=

3x1-x2-2x3-M

x4-M

x53x1+2x2-3x3+

x4

=6x1-2x2+x3+x5=4x1,x2,x3,x4,x5≥0第五页，共三十九页，编辑于2023年，星期三

初始单纯形表为：0-M-2-13411-2160-323-M01～10M0-2-2M-13+4M4

11-216

0-3230

0

1

3+3M-1+2M-2-3M0-M6M所以，此时求解不是最优解，需要换基。x1

x2

x3x4x5b10M0-2-2M-13+4M411-2160-323001

3+4M-1-2-2M0

010M～第六页，共三十九页，编辑于2023年，星期三

10M0-2-2M-13+4M411-2160-323001～-6+2M0

1+2M-3-8M/30212-8/3020-12/31-1-4M/3-1/31/3-7-M-1/20-5/3011/21-4/3031/20-2/31-M-5/6-1/61/6～x2=0,x4=0,x5=0,x1=3,x3=1,σj<0，此时求解最优即X0=(3,0,1,0,0)T时，-Z=-7，最优解maxZ=7第七页，共三十九页，编辑于2023年，星期三试用大M法求解如下线性规划问题的最优解。划为标准型，并按大M法引入人工变量x4,x5的辅助问题如下：松驰变量剩余变量人工变量惩罚项第八页，共三十九页，编辑于2023年，星期三解：0-M0-1-1311010-230021-411011-2100-10-M010～4M00

-1+3M-1+M3-6M11010-230021-411011-21-M0-10

0010x1

x2

x3

x4

x5

x6x7bx1

x2

x3

x4

x5

x6x7b第九页，共三十九页，编辑于2023年，星期三M+1-3M+10

0-1+M111010-21-2001010-110-23-M0-1000102-M-10

00111010-21-2001012-51003-10-1-21-M012-2-M+23-1/3

0009-7/32/31001-200104-5/31/3001-1/3-4/3-1-2/31/3-M4/312/3～～令x4=0,x5,=0,x6=0,x7,=0,得x1=4,x2=1,x3=9即X0=(4,1,9,0,0,0,0)T此时-Z’=-2为最大,则最优解minZ=-2～第十页，共三十九页，编辑于2023年，星期三（二）两阶段法这种方法是在约束条件中加入人工变量，将线性规划问题分为两阶段进行求解。第一阶段是先求以人工变量等于0为目标的线性规划问题第二阶段利用已求出的初始基可行解来求原问题最优解。第十一页，共三十九页，编辑于2023年，星期三试用两阶段法求解如下线性规划问题解：先划约束条件为标准型第十二页，共三十九页，编辑于2023年，星期三初等变换0-10000-W11010-2030021-4011011-21000-10-1010～40031-6-W11010-2030021-4011011-210-10-100010-Z’

x1

x2

x3

x4

x5

x6x7b第十三页，共三十九页，编辑于2023年，星期三

～～0-10000-W

11010-20

1-200100

12-51003000-1-2-10121-30010-W11010-201-20010010-110-230-10-100010进行第二阶段的计算将第一阶段的人工变量列取消,并将目标函数系数换成原问题的目标函数系数,重新计算检验数行,可得如下第二阶段的初始单纯形表；应用单纯形算法求解得最终表。3-1-100

30-10-11

1000-12此时求解不是最优，继续迭代令x5=x6=x7=0，得最优解X=(0,1,1,12,0)T，minW=0。因人工变量x6=x7=0,所以是原问题的基可行解。于是可以开始第二阶段的计算。-Z’第十四页，共三十九页，编辑于2023年，星期三

～2-30001-Z’11010-201-20010012-110030-10-1-20010接上表-2-3-1/3000-Z’912/310001-2001004-11/30010-1/3-4/3-1-2/30010～σj<0，

x4=0,x5=0,x1=4,x2=1,x3=9,即X0=(4,1,9,0,0)T，此时最优解–Z’=-2而maxZ’=2则minZ=-2第十五页，共三十九页，编辑于2023年，星期三（二）试用两阶段法求解MinZ=10x1+8x2+

7x32x1+x2≥6x1+x2+x3≥4x1,x2,x3≥0S.t.maxZ=－10x1

－

8x2－

7x3－M

x5

－M

x7

2x1+x2

－

x4+

x5

=6x1+x2+x3

－

x6+

x7=4x1,x2,x3,

x4,x5,x6,

x7≥

0第十六页，共三十九页，编辑于2023年，星期三（二）试用两阶段法求解～～00000-Z’4011106-10120

-1010-10-1

1

010-1

1

2

3-Z’4011106-10120001-1-100

1

01/2

1

1/2

0-Z’11/211/2003-1/201/210-3/2-1/21/2-1-100

1

01第一阶段规划求解第十七页，共三十九页，编辑于2023年，星期三

～0

00

0-Z11/211/2003-1/201/210-1-1/21/20-10-1

1

00～令x3=x4=x6=0得x1=2,x2=2,此解最优

max-Z’=36σj<0-Z’-10-8-70-3/2

0

1/2

0

-Z’11/211/2003-1/201/2101/2-1/21/2-7-10-1

1

037～-2-1

0

0

-Z’2121002-11-10101/2-1/21/2-6-21-1

1

036从而得minZ=36σj<0第二阶段规划求解第一阶段规划最优第十八页，共三十九页，编辑于2023年，星期三四、单纯形法补遗进基变量相持：单纯形法运算过程中，同时出现多个相同的j最大。在符合要求的j(目标为max：j＞0，min：j＜0)中，选取下标最小的非基变量为换入变量；离基变量相持：单纯形法运算过程中，同时出现多个相同的最小θ值。继续迭代，便有基变量为0，称这种情况为退化解。选取其中下标最大的基变量做为换出变量。多重最优解：最优单纯形表中，存在非基变量的检验数j=0。让这个非基变量进基，继续迭代，得另一个最优解。无界解：在大于0的检验数中，若某个k所对应的系数列向量Pk′≤0，则此问题是无界解。无可行解：最终表中存在人工变量是基变量。第十九页，共三十九页，编辑于2023年，星期三解的判别：情况1—无穷最优解Cj比值CBXBb检验数j0x1x2x3x4x5x6240000221000120100X3X4X5X6000040001064-3Maxz=2x1+4x22x1+2x2≤12x1+2x2≤84x1≤164x2≤12x1,x2,x3≥0标准化

Maxz=2x1+4x2+0x3+0x4+0x5+0x62x1+2x2+x3=12x1+2x2+x4=84x1+x5=164x2+x6=12x1,…,x6≥00400012400001281612第二十页，共三十九页，编辑于2023年，星期三迭代结果Cj比值CBXBb检验数j-36x1x2x3x4x5x6240000001-200.5

1

0

0

1

0-0.5X3X1X5X20204000-4124-432010000.25000-2002288j<0令x4=0，x6=0，得x1=2，x2=8，x3=2，x5=8即X0=(2,8,2,0,8,0)T此时Z＝2×2+4×8=36是最优解第二十一页，共三十九页，编辑于2023年，星期三再次迭代结果Cj比值CBXBb检验数j-36x1x2x3x4x5x6240000001-1-0.25

0

1

0000.25

0X3X1X6X20204000-20.5

1

0

100.5-0.125

0000-1.50

00447j<0令x4=0，x5=0，得x1=4，x2=7，x3=0，x6=4即X0=(4,7,0,0,0,4)T此时Z＝2×4+4×7=36也是最优解结论：非基变量检验数有为0的，此线性规划有无穷多个解两最优解对应可行域两顶点，两点间连线上的点都是最优解第二十二页，共三十九页，编辑于2023年，星期三解的判别：情况2—解无界maxZ=

2x1+3x2+0x34x1+x3=16x1,x2,x3≥0Cj比值CBXBb检验数jx1x2x323016401230x30确定x2进基，但x2所在列的系数为0，x2可以任意增大，解无界Maxz=2x1+3x2

4x1≤16x1,x2≥0说明此线性规划解无界第二十三页，共三十九页，编辑于2023年，星期三另例maxZ=

5x1+6x2+0x3–Mx4+0x52x1-x2-

x3+x4=2-2x1+3x2+x5=2x1,x2,x3,x4,x5≥0Cj比值CBXBb检验数jx1x2x3x4x5560-M022-1-1102-23001X4X5-M0Maxz=5x1+6x2

2x1-x2≥2-2x1+3x2≤2x1,x2≥0560-M0检验数j5+2M6-M

-M0011-1/2-1/21/20402-11

1-5017/25/2-M+5/20第二十四页，共三十九页，编辑于2023年，星期三另例Cj比值CBXBb检验数jx1x2x3x4x5560-M0210-3/4

3/41/42

01-0.50.50.5X1X256560-M00

027/4-M+27/4-17/4确定x3进基，但x3所在列的系数为负，此时解无界结论：入基变量系数均≤0的，该问题目标函数无界第二十五页，共三十九页，编辑于2023年，星期三解的判别：情况3—无解maxZ=

3x1+2x2-2x1+x2≥2x1-3x2≥3x1,x2≥0S.t.标准化

maxZ=

3x1+2x2-M

x5-M

x6-2x1+x2-x3+x5=2x1-3x2-x4+x6=3x1,x2,x3,x4≥0Cj比值CBXBb检验数j3200-M-Mx5x6-M-M此时检验数j<0，无进基变量,但x5,x6还没有替换出去。Z不能达到最优说明此线性规划无解x1x2x3x4x5x62-21-101

031-30-1013200-M-M检验数jx5x62-21-101031-30-1012M3-2M2+M-M00-M5M3-M2-2M-M-M0000结论：人工变量仍为基变量的，该问题无解第二十六页，共三十九页，编辑于2023年，星期三图示：无解maxZ=

3x1+2x2-2x1+x2≥

2

x1-3x2≥

3x1,x2≥0S.t.用图示法x1x22462460说明此线性规划无解第二十七页，共三十九页，编辑于2023年，星期三五、单纯形法的矩阵计算求解用矩阵描述的线性规划的标准形式为：求解问题：B和B-1是什么？，待后讨论第二十八页，共三十九页，编辑于2023年，星期三单纯形法小结1.根据实际问题给出数学模型，列出初始单纯形表，进行标准化第二十九页，共三十九页，编辑于2023年，星期三

添加松驰变量、人工变量列出初始单纯形表基变量中有非零的人工变量sk=max(sj)对所有aik>0计算qi=bi/aik令q=min(qi)所有sj≤0是否2.对目标函数求max的线性规划，用单纯形法计算步骤如下计算非基变量各列的检验数sj否某非基变量检验数为零否唯一最优解对任一sj≥0有Pj≤0是无界解无可行解是是无穷多最优解是迭代运算第三十页，共三十九页，编辑于2023年，星期三六、用计算机软件求解线性规划问题关于线性规划问题的求解，有许多好的专业软件和商务软件，通过计算机可十分方便地完成求解过程。其中简便易行的求解软件是Excel，下面介绍其使用方法。（1）建立Excsl工作表。用一组单元格表示变量，作为可变单元格（空）；用几组单元格分别表示各约束条件和目标函数的系数；用一些单元格输入公式表示各组系数和变量的关系。（2）打开工具栏中的“规划求解”对话框，指定存有目标函数的单元格为目标单元格，指定表示变量的单元格为可变单元格，建立约束条件。（3）在规划求解对话框中按下“求解”按钮，即可求出最优解和最优值。推出规划求解对话框。第三十一页，共三十九页，编辑于2023年，星期三利用EXCEL求线性规划的步骤1、激活“工具栏”中的“规划求解”第三十二页，共三十九页，编辑于2023年，星期三利用EXCEL求线性规划的步骤2、根据线性规划模型建立计算模板

maxZ=3x1+5x2x1

≤8